×

A framework for the description of evolutionary algorithms. (English) Zbl 0970.90122

Summary: Evolutionary algorithms (EA) are optimisation techniques inspired from natural evolution processes. They handle a population of individuals that evolve with the help of information exchange procedures. Each individual may also evolve independently. Periods of co-operation alternate with periods of self-adaptation. We define a terminology and give a general framework for the description of the main features of any particular evolutionary algorithm. Such a description does not provide, nor does it replace, algorithm pseudo-codes. The aim is to develop tools that may help understanding the “philosophy” of such methods.

MSC:

90C59 Approximation methods and heuristics in mathematical programming

Software:

GIDEON
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beasley, J. E.; Chu, P. C., A genetic algorithm for the set covering problem, European Journal of Operational Research, 94, 393-404 (1996) · Zbl 0953.90565
[2] Blazewicz, J.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Scheduling subject to resource constraints: Classification, Discrete Applied Mathematics, 5, 11-24 (1983) · Zbl 0516.68037
[3] Blazewicz, J., Ecker, K., Schmidt, G., Weglarz, J., 1993. Scheduling in Computer and Manufacturing Systems. Springer, Berlin; Blazewicz, J., Ecker, K., Schmidt, G., Weglarz, J., 1993. Scheduling in Computer and Manufacturing Systems. Springer, Berlin · Zbl 0767.90033
[4] Calégari, P., Coray, G., Hertz, A., Kobler, D., Kuonen, P., 1997. Evolutionary algorithm revisited: the TEA Classification. Technical Report ORWP 97/02, Swiss Federal Institute of Technology, Lausanne, Switzerland; Calégari, P., Coray, G., Hertz, A., Kobler, D., Kuonen, P., 1997. Evolutionary algorithm revisited: the TEA Classification. Technical Report ORWP 97/02, Swiss Federal Institute of Technology, Lausanne, Switzerland
[5] Calégari, P.; Coray, G.; Hertz, A.; Kobler, D.; Kuonen, P., A taxonomy of evolutionary algorithms in combinatorial optimization, Journal of Heuristics, 5, 145-158 (1999) · Zbl 1071.90572
[6] Cantù-Paz, E., 1995. A summary of research on parallel genetic algorithms. Technical Report, Illinois Genetic Algorithms Laboratory, USA; Cantù-Paz, E., 1995. A summary of research on parallel genetic algorithms. Technical Report, Illinois Genetic Algorithms Laboratory, USA
[7] Chu, P.C., Beasley, J.E., 1996. A genetic algorithm for the multidimensional knapsack problem. Technical Report, Imperial College, London, UK; Chu, P.C., Beasley, J.E., 1996. A genetic algorithm for the multidimensional knapsack problem. Technical Report, Imperial College, London, UK · Zbl 0913.90218
[8] Colorni, A., Dorigo, M., Maniezzo, V., 1991. Distributed optimization by ant colonies. In: Proceedings of the First European Conference on Artificial Life, Bradford Books. MIT Press, Cambridge, MA, pp. 134-142; Colorni, A., Dorigo, M., Maniezzo, V., 1991. Distributed optimization by ant colonies. In: Proceedings of the First European Conference on Artificial Life, Bradford Books. MIT Press, Cambridge, MA, pp. 134-142
[9] Colorni, A., Dorigo, M., Maniezzo, V., 1992. An investigation of some properties of an ant algorithm. In: Männer, R., Manderick, B. (Eds.), Proceedings of the Second European Conference on Parallel Problem Solving from Nature. Elsevier, Amsterdam, pp. 509-520; Colorni, A., Dorigo, M., Maniezzo, V., 1992. An investigation of some properties of an ant algorithm. In: Männer, R., Manderick, B. (Eds.), Proceedings of the Second European Conference on Parallel Problem Solving from Nature. Elsevier, Amsterdam, pp. 509-520
[10] Colorni, A.; Dorigo, M.; Maniezzo, V.; Trubian, M., Ant system for job shop scheduling, Belgian Journal of Operations Research, Statistics and Computer Science, 34, 39-53 (1994) · Zbl 0814.90047
[11] Costa, D.; Hertz, A.; Dubuis, O., Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs, Journal of Heuristics, 1, 105-128 (1995) · Zbl 0855.05063
[12] Costa, D.; Hertz, A., Ants can colour graphs, Journal of the Operational Research Society, 48, 295-305 (1997) · Zbl 0890.90174
[13] Davis, L., 1991. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York; Davis, L., 1991. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York
[14] Dorigo, M.; Gambardella, L. M., Ant colony system: A cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1, 53-66 (1997)
[15] Falkenauer, E., Delchambre, A., 1992. A genetic algorithm for bin packing and line balancing. In: Proceedings of the 1992 IEEE International Conference on Robotics and Automation. IEEE Computer Society Press, Silver Spring, MD, pp. 1186-1192; Falkenauer, E., Delchambre, A., 1992. A genetic algorithm for bin packing and line balancing. In: Proceedings of the 1992 IEEE International Conference on Robotics and Automation. IEEE Computer Society Press, Silver Spring, MD, pp. 1186-1192
[16] Falkenauer, E., A hybrid grouping genetic algorithm for bin packing, Journal of Heuristics, 2, 5-30 (1996)
[17] Fleurent, C., Ferland, J.A., 1996. Genetic and hybrid algorithms for graph coloring. In: Laporte, G., Osman, I.H. (Eds.), Metaheuristics in Combinatorial Optimization. Baltzer Science Publishers; Annals of Operations Research 63, 437-461; Fleurent, C., Ferland, J.A., 1996. Genetic and hybrid algorithms for graph coloring. In: Laporte, G., Osman, I.H. (Eds.), Metaheuristics in Combinatorial Optimization. Baltzer Science Publishers; Annals of Operations Research 63, 437-461 · Zbl 0851.90095
[18] Fogel, L.J., Owens, A.J., Walsh, M.J., 1966. Artificial Intelligence Through Simulated Evolution. Wiley, New York; Fogel, L.J., Owens, A.J., Walsh, M.J., 1966. Artificial Intelligence Through Simulated Evolution. Wiley, New York · Zbl 0148.40701
[19] Gambardella, L.M., Dorigo, M., 1996. Solving symmetric and asymmetric TSPs by ant colonies. In: Proceedings of the 1996 IEEE International Conference on Evolutionary Computation. IEEE Press, New York, pp. 622-627; Gambardella, L.M., Dorigo, M., 1996. Solving symmetric and asymmetric TSPs by ant colonies. In: Proceedings of the 1996 IEEE International Conference on Evolutionary Computation. IEEE Press, New York, pp. 622-627
[20] Glover, F., Heuristics for integer programming using surrogate constraints, Decision Sciences, 8, 156-166 (1977)
[21] Glover, F., Genetic algorithms and scatter search: Unsuspected potentials, Statistics and Computing, 4, 131-140 (1994)
[22] Goldberg, D., 1989. Genetics Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA; Goldberg, D., 1989. Genetics Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA · Zbl 0721.68056
[23] Golden, B. L.; Laporte, G.; Taillard, E. D., An adaptive memory heuristic for a class of vehicle routing problems with minmax objective, Computers and Operations Research, 24, 445-452 (1997) · Zbl 0882.90031
[24] Gordon, V., Whitley, D., 1993. Serial and parallel genetic algorithms as function optimizers. In: Forrest, S. (Ed.), Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, Los Altos, CA, pp. 177-183; Gordon, V., Whitley, D., 1993. Serial and parallel genetic algorithms as function optimizers. In: Forrest, S. (Ed.), Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, Los Altos, CA, pp. 177-183
[25] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling theory: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044
[26] Holland, J. H., Outline for a logic theory of adaptative systems, Journal of the ACM, 3, 297 (1962)
[27] Kuntz, P., Snyers, D., 1994. Emerging coloration and graph partitioning. In: Proceedings of the Third International Conference of Adaptative Behavior. MIT Press, Cambridge, MA, pp. 494-500; Kuntz, P., Snyers, D., 1994. Emerging coloration and graph partitioning. In: Proceedings of the Third International Conference of Adaptative Behavior. MIT Press, Cambridge, MA, pp. 494-500
[28] Laszewski, G. von., 1991. Intelligent structural operators for the \(k\); Laszewski, G. von., 1991. Intelligent structural operators for the \(k\)
[29] Levine, D., 1994. A parallel genetic algorithm for the set partitioning problem, Ph.D. thesis. Illinois Institute of Technology, USA; Levine, D., 1994. A parallel genetic algorithm for the set partitioning problem, Ph.D. thesis. Illinois Institute of Technology, USA
[30] Liepens, G.E., Potter, W.D., 1991. A genetic algorithm approach to multi-fault diagnosis. In: Davis, L. (Ed.), Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, pp. 237-250; Liepens, G.E., Potter, W.D., 1991. A genetic algorithm approach to multi-fault diagnosis. In: Davis, L. (Ed.), Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York, pp. 237-250
[31] Manderick, B., Spiessens, P., 1989. Fine-grained parallel genetic algorithms. In: Schaffer, J.D. (Ed.), Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, Los Altos, CA, pp. 428-433; Manderick, B., Spiessens, P., 1989. Fine-grained parallel genetic algorithms. In: Schaffer, J.D. (Ed.), Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, Los Altos, CA, pp. 428-433
[32] Maniezzo, V., Colorni, A., Dorigo, M., 1994. The ant system applied to the quadratic assignment problem. Technical Report 94/28, IRIDIA, Université Libre de Bruxelles, Belgium; Maniezzo, V., Colorni, A., Dorigo, M., 1994. The ant system applied to the quadratic assignment problem. Technical Report 94/28, IRIDIA, Université Libre de Bruxelles, Belgium · Zbl 0912.90240
[33] Mühlenbein, H., 1989. Parallel genetic algorithms, population genetics and combinatorial optimization. In: Schaffer, J.D. (Ed.), Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, Los Altos, CA, pp. 416-421; Mühlenbein, H., 1989. Parallel genetic algorithms, population genetics and combinatorial optimization. In: Schaffer, J.D. (Ed.), Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, Los Altos, CA, pp. 416-421
[34] Rechenberg, I., 1965. Cybernetic solution path of an experimental problem. Royal Aircraft Establishment Transl. 1122, B.F. Toms Transl. Ministry of Aviation, Royal Aircraft Establishment, Farnborough, Hants, UK; Rechenberg, I., 1965. Cybernetic solution path of an experimental problem. Royal Aircraft Establishment Transl. 1122, B.F. Toms Transl. Ministry of Aviation, Royal Aircraft Establishment, Farnborough, Hants, UK
[35] Rochat, Y.; Taillard, E. D., Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1, 147-167 (1995) · Zbl 0857.90032
[36] Taillard, E.D., Gambardella, L.-M., Gendreau, M., Potvin, J.-Y., 1997. Programmation à mémoire adaptative, technical report IDSIA-79-97, IDSIA, Lugano, Switzerland; Taillard, E.D., Gambardella, L.-M., Gendreau, M., Potvin, J.-Y., 1997. Programmation à mémoire adaptative, technical report IDSIA-79-97, IDSIA, Lugano, Switzerland
[37] Tanese, R., 1989. Distributed genetic algorithms. In: Schaffer, J.D., Philips Laboratories, (Eds.), Proceedings of the Second International Conference on Genetic Algorithms. Morgan Kaufmann, Los Altos, CA; Tanese, R., 1989. Distributed genetic algorithms. In: Schaffer, J.D., Philips Laboratories, (Eds.), Proceedings of the Second International Conference on Genetic Algorithms. Morgan Kaufmann, Los Altos, CA
[38] Thangiah, S.R., Nygard, K.E., Juell, P.L., 1991. GIDEON: A genetic algorithm system for vehicle routing with time windows. In: Proceedings of the Seventh IEEE Conference on Artificial Intelligence Applications. IEEE Computer Society Press, Silver Spring, MD, pp. 322-328; Thangiah, S.R., Nygard, K.E., Juell, P.L., 1991. GIDEON: A genetic algorithm system for vehicle routing with time windows. In: Proceedings of the Seventh IEEE Conference on Artificial Intelligence Applications. IEEE Computer Society Press, Silver Spring, MD, pp. 322-328
[39] Yamada, T., Nakano, R., 1992. A genetic algorithm applicable to large-scale job-shop problems. In: Männer, R., Manderick, B. (Eds.), Proceedings of the Second European Conference on Parallel Problem Solving from Nature. Elsevier, Amsterdam, pp. 281-290; Yamada, T., Nakano, R., 1992. A genetic algorithm applicable to large-scale job-shop problems. In: Männer, R., Manderick, B. (Eds.), Proceedings of the Second European Conference on Parallel Problem Solving from Nature. Elsevier, Amsterdam, pp. 281-290
[40] Zufferey, N., Hertz, A., 1997. Coloration de graphes à l’aide de fourmis, Technical Report. Swiss Federal Institute of Technology, Lausanne, Switzerland; Zufferey, N., Hertz, A., 1997. Coloration de graphes à l’aide de fourmis, Technical Report. Swiss Federal Institute of Technology, Lausanne, Switzerland
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.