×

Optimization of the keyboard arrangement problem using an ant colony algorithm. (English) Zbl 1037.90566

Summary: In order to solve the problem of the arrangement of letters on a computer keyboard, an abstract representation of a keyboard is introduced and an evaluation function taking account of ergonomic criteria is proposed. It results in a new optimization problem that we name the keyboard arrangement problem. Based on the generic framework of ant colony optimization, an algorithm is developed and applied to this problem. New effective keyboard arrangements are deduced for several languages. Comparisons are made with standard manually optimized keyboards.

MSC:

90B99 Operations research and management science

Software:

HAS-SOP; AntNet
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alden, D. G.; Daniels, R. W.; Kanarick, A. F., Keyboard design and operation: A review of the major issues, Human Factors, 14, 4, 275-293 (1972)
[2] Bullnheimer, B., Hartl, R.F., Strauß, C., 1997. A new rank based version of the ant system-a computational study. Technical Report POM-10/97, Institute of Management Science, University of Vienna; Bullnheimer, B., Hartl, R.F., Strauß, C., 1997. A new rank based version of the ant system-a computational study. Technical Report POM-10/97, Institute of Management Science, University of Vienna · Zbl 0941.90063
[3] Burkard, R.; Offermann, J., Entwurf von Schreibmaschinentastaturen mittels quadratischer Zuordnungsprobleme, Zeitschrift für Operations Research, 21, B121-B132 (1977) · Zbl 0353.90095
[4] Di Caro, G., Dorigo, M., 1997. AntNet: A mobile agents approach to adaptive routing. Technical Report 97-12, IRIDIA, Université Libre de Bruxelles; Di Caro, G., Dorigo, M., 1997. AntNet: A mobile agents approach to adaptive routing. Technical Report 97-12, IRIDIA, Université Libre de Bruxelles
[5] Di Caro, G.; Dorigo, M., AntNet: Distributed stimergetic control for communication networks, Journal of Artificial Intelligence Research (JAIR), 9, 317-365 (1998) · Zbl 0910.68182
[6] Corne, D.; Dorigo, M.; Glover, F., New Ideas in Optimization (1999), McGraw-Hill: McGraw-Hill NY
[7] Costa, D.; Hertz, A., Ants can colour graphs, Journal of the Operational Research Society, 48, 295-305 (1997) · Zbl 0890.90174
[8] Dorigo, M.; Caro, G. D.; Gambardella, L. M., Ant algorithms for discrete optimization, Artificial Life, 5, 2, 137-172 (1999)
[9] Dorigo, M., Maniezzo, V., Colorni, A., 1991. Ant system: An autocatalytic optimizing process. Technical Report 91-016, Dipartimento di Elettronica e Informazione, Politechnico di Milano, Italy; Dorigo, M., Maniezzo, V., Colorni, A., 1991. Ant system: An autocatalytic optimizing process. Technical Report 91-016, Dipartimento di Elettronica e Informazione, Politechnico di Milano, Italy · Zbl 0912.90240
[10] Dorigo, M.; Maniezzo, V.; Colorni, A., The ant system: Optimization by a colony of cooperating agents, IEEE Transaction on Systems, Man and Cybernetics—Part B, 26, 1, 29-41 (1996)
[11] Gambardella, L., Dorigo, M., 1997. HAS-SOP: A hybrid ant system for the sequential ordering problem. Technical Report 97-11, IDSIA, Lugano, CH; Gambardella, L., Dorigo, M., 1997. HAS-SOP: A hybrid ant system for the sequential ordering problem. Technical Report 97-11, IDSIA, Lugano, CH
[12] Gambardella, L. M.; Dorigo, M., Ant-Q: A reinforcement learning approach to the traveling salesman problem, (Proceedings of ML-95, Twelfth Intern. Conf. Machine Learning (1995), Morgan Kaufmann), 252-260
[13] Glover, D.E., 1986. Experimentation with an adaptive search strategy for solving a keyboard design/configuration problem. PhD thesis, University of Iowa; Glover, D.E., 1986. Experimentation with an adaptive search strategy for solving a keyboard design/configuration problem. PhD thesis, University of Iowa
[14] Kehl, S., Wagner, M.O., 2000. Modélisation et optimisation de la répartition des lettres sur un clavier d’ordinateur. Applied scientific project, Laboratoire Productique Logistique, Ecole Centrale Paris; Kehl, S., Wagner, M.O., 2000. Modélisation et optimisation de la répartition des lettres sur un clavier d’ordinateur. Applied scientific project, Laboratoire Productique Logistique, Ecole Centrale Paris
[15] Limayem, F., Yannou, B., 2002. Le tri croisé de Monte Carlo: une boı̂te à outils pour l’aide à la décision coopérative. To appear in Revue de CFAO et Informatique Graphique; Limayem, F., Yannou, B., 2002. Le tri croisé de Monte Carlo: une boı̂te à outils pour l’aide à la décision coopérative. To appear in Revue de CFAO et Informatique Graphique
[16] Marsan, C., 1976. Perfectionnements aux claviers de machines à écrire et similaires. Brevet d’invention no. 76-23323, déposé le 30 juillet 1976 à l’Institut National de la Propriété Industrielle, France; Marsan, C., 1976. Perfectionnements aux claviers de machines à écrire et similaires. Brevet d’invention no. 76-23323, déposé le 30 juillet 1976 à l’Institut National de la Propriété Industrielle, France
[17] Marsan, C., 1979. Demande de certificat d’addition no. 79-01065, du 17 janvier 1979 portant sur le brevet no. 76-23323: “Perfectionnements aux claviers de machines á écrire et similaires”, Institut National de la Propriété Industrielle, France; Marsan, C., 1979. Demande de certificat d’addition no. 79-01065, du 17 janvier 1979 portant sur le brevet no. 76-23323: “Perfectionnements aux claviers de machines á écrire et similaires”, Institut National de la Propriété Industrielle, France
[18] Marsan, C., 1987. Claviers alphanumériques ergonomiques pour machines à écrire et similaires. Brevet d’invention no. 87-03267, déposé le 3 mars 1987 à l’Institut National de la Propriété Industrielle, France; Marsan, C., 1987. Claviers alphanumériques ergonomiques pour machines à écrire et similaires. Brevet d’invention no. 87-03267, déposé le 3 mars 1987 à l’Institut National de la Propriété Industrielle, France
[19] Norman, D. A.; Fisher, D., Why alphabetic keyboards are not easy to use: Keyboard layout doesn’t much matter, Human Factors, 24, 5, 509-519 (1982)
[20] Oommen, B. J.; Valiveti, R.; Zgierski, J. R., Correction to an adaptive learning solution to the keyboard optimization problem, IEEE Transactions on Systems, Man and Cybernetics, 22, 5, 1233-1243 (1992)
[21] Pollatschek, M., Gershoni, M., Tadday, Y., 1975. Improving the Hebrew typewriter. Technical report, Haifa; Pollatschek, M., Gershoni, M., Tadday, Y., 1975. Improving the Hebrew typewriter. Technical report, Haifa
[22] Stützle, T., Dorigo, M., 1999. ACO algorithms for the traveling salesman problem. Technical report, IRIDIA, Université de Bruxelles, Belgium; Stützle, T., Dorigo, M., 1999. ACO algorithms for the traveling salesman problem. Technical report, IRIDIA, Université de Bruxelles, Belgium · Zbl 0972.90056
[23] Stützle, T., Hoos, H.H., 1996. Improving the ant system: A detailed report of the MAX-MIN ant system. Technical Report AIDA-96-12, Technical University of Darmstadt, Department of Computer Science-Intellectics Group, Germany; Stützle, T., Hoos, H.H., 1996. Improving the ant system: A detailed report of the MAX-MIN ant system. Technical Report AIDA-96-12, Technical University of Darmstadt, Department of Computer Science-Intellectics Group, Germany
[24] Wagner, M., Yannou, B., Kehl, S., Feillet, D., Eggers, J., 2001. Ergonomic modelling and optimization of the keyboard arrangement with an ant colony optimization algorithm. Technical Report CER 01-02 A, Laboratoire Productique Logistique, Ecole Centrale Paris. Available at <http://www.pl.ecp.fr/ feillet>; Wagner, M., Yannou, B., Kehl, S., Feillet, D., Eggers, J., 2001. Ergonomic modelling and optimization of the keyboard arrangement with an ant colony optimization algorithm. Technical Report CER 01-02 A, Laboratoire Productique Logistique, Ecole Centrale Paris. Available at <http://www.pl.ecp.fr/ feillet> · Zbl 1037.90566
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.