Właściwości i zastosowania algorytmów ewolucyjnych w optymalizacji

• Autorzy: Słowik A.
• Języki publikacji: PL

Abstrakty

PL

W artykule przedstawiono charakterystykę algorytmów ewolucyjnych. Można zauważyć, że ich stosowanie do zagadnień optymalizacyjnych jest bardzo szerokie. Do dnia dzisiejszego powstało wiele algorytmów optymalizacji wielomodalnej, wielokryterialnej, oraz optymalizacji z ograniczeniami, które bazują na ewolucyjnym przetwarzaniu informacji. W niniejszej pracy przedstawiono jedynie krótką charakterystykę kilku poszczególnych metod.

EN

In the paper a characteristics of evolutionary algorithms is presented. Such parameters of algorithm as: representation of individuals, fitness function, selection, mutation, and cross-over are described. Different kinds of evolutionary algorithms are shortly presented, and also chosen kinds of optimization, and techniques of their realizations using these algorithms are shown, hi the paper a multi-modal optimization, multi-objective optimization, and optimization with constraints are discussed as well.

Słowa kluczowe

PL

sztuczna inteligencja; algorytmy ewolucyjne; optymalizacja ewolucyjna

EN

artificial intelligence; evolutionary algorithms; evolutionary optimization

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Metody Informatyki Stosowanej
• Rocznik: 2007
• Tom: nr 2(Tom 12)
• Strony: 143--163
• Opis fizyczny: Bibliogr. 52 poz., rys., tab.

Twórcy

autor

Słowik A.

• Politechnika Koszalińska, Wydział Elektroniki i Informatyki

Bibliografia

• [l] M. Dorigo, G. Di Caro, The Ant Colony Optimization Meta-Heuristic, In D. Corne, M. Dorigo. F. Glover, editors, New Ideas in Optimization, McGraw-Hill, 11-32.1999.
• [2] M. Dorigo, M. Birattari. T. Stützle, Ant Colony Optimization - Artificial Ants as a Computalional Intelligence Technique, IEEE Computational Intelligence Magazine, 2006.
• [3] J. Kennedy, R. C. Eberhart, Particle swarm optimization, Proceedings of IEEE International Conference on Neural Networks, Piscataway, NJ. pp. 1942-1948, 1995.
• [4] J. Kennedy, R. C. Eberhart, Y. Shi, Swarm intelligence, San Francisco, Morgan Kaufmann Publishers, 2001.
• [5] Sławomir T. Wierzchoń, Sztuczne systemy immunologiczne. Teoria i zastosowania, Wydawnictwo Exit, 2001.
• [6] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machinę Learning, Addison-Wesley Publishing Company Inc, 1989.
• [7] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag Berlin Heidelberg, 1992.
• [8] J. Arabas, Wykłady z algorytmów ewolucyjnych, WNT, 2001.
• [9] G. Di Caro and M. Dorigo, AntNet: A mobile agents approach to adaptive routing, Technical report IRIDIA/97-12, IRID1A, Universite Librę do Bruxelles, 1997. Later published as AntNet: Distributed Strigmergic Control for Communication Networks. Journal of Artificial Intelligence Research (JAIR), 9, 317-365, 1998.
• [10] M. Dorigo, L.M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, Technical Report TR/IRIDIA/1996-5, IRIDIA, Universite Librę de Bruxelles, 1996. Later published in IEEE Transaitions on Evolutionary Computation.
• [11] Al-kazemi, B. and Mohan, C. K., Training feedforward neural networks using multi-phase particle swarm optimization, Proceedings of the 9th International Conference on Neural Information Processing (ICONIP 2002), Singapore 2002.
• [12] Coello Coello, Carlos A.; Cortes Rivera, Daniel and Cruz Cortes, Nareli, Use of an Artificial Immune System for Job Shop Scheduling, in Jon Timmis, Peter Bentley and Emma Hart (editors), Second International Conference on Artificial Immune Systems (ICARIS'2003), pp. 1-10, Edinburgh, Scotland, Lecture Notes in Computer Science, Vol. 2787, Springer-Verlag, Septiembre de 2003.
• [13] A. Słowik, M. Białko, Ewolucyjne projektowanie filtrów cyfrowych IIR o nietypowych charakterystykach amplitudowych, III Krajowa Konferencja Elektroniki, Politechnika Koszalińska, Wydział Elektroniki, Kołobrzeg, Czerwiec 2004, ss. 345-350.
• [14] A. Słowik, M. Białko, Design and Optimization of Combinational Digital Circuits Using Modified Evolutionary Algorithm,, Proceedings of Seventh International Conference on Artifficial Intelligence and Soft Computing, ICAISC 2004, Lecture Notes in Artificial Intelligence. Volume 3070/2004, pp. 468-473, Springer-Verlag, Zakopane, June 2004.
• [15] A. Słowik, M. Białko, Partitioning of VLSI Circuits on Subcircuits with Minimal Number of Connections Using Evolutionary Algorithm, Eigth International Conference on Artifficial Intelligence and Soft Computing, ICAISC 2006, Lecture Notes in Artificial Intelligence, Volume 4029/2006, Springer-Verlag, Zakopane, June 2006, pp. 470-478.
• [16] M. D. Vose, G. E. Leipins, Schema disruption, In Proceedings of the Fourth International Conference on Genetic Algorithms, pp. 237-243, Morgan Kaufmann (San Mateo), 1991.
• [17] S. Kozieł, Algorytmy ewolucyjne, i ich zastosowania do optymalizacji i modelowania analogowych układów elektronicznych, Rozprawa doktorska, Politechnika Gdańska, Wydział Elektroniki, Telekomunikacji i Informatyki, Gdańsk 1999.
• [18] D. Whitley, S. Rana, R. Heckendorn, Representation Issues in Neighborhood Search and Evolutionary Algorithms, Genetic Algorithms and Evolution Strategies in Engineering and Computer Science, D. Quagliarella, J. Periaux, C. Poloni, G. Winter (eds.), pp. 39-57, John Wiley, 1997.
• [19] N. .J. Radcliffe, P. D. Surry, Fundamental Limitations on Search Algorithms: Evolutionary Computing in Perspective, Lecture Notes in Computer Science, Vol. 1000, J. Van Leeuwen (ed.), Springer-Verlag, 1995.
• [20] A. Słowik, Projektowanie i optymalizacja cyfrowych układów elektronicznych przy użyciu algorytmów ewolucyjnych, Rozprawa doktorska, Politechnika Koszalińska, Wydział Elektroniki i Informatyki, Marzec 2007.
• [21] Z. Michalewicz, M. Schoenauer, Evolutionary computation for constrained parameter optimization problems, Evolutionary Computation, Vol. 4, No. 1, pp. 1-32, 1996.
• [22] D. Whitley, The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best, In .J. D. Schaffer (ed.), Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann Publishers, San Mateo, CA, pp. 116-121, 1989.
• [23] L. B. Booker, Improving Search in Genetic Algorithms, In L. Davis (ed.), Genetic. Algorithms and Simulated Annealing: An Overview, Morgan Kaufmann Publishers, San Mateo, CA, pp. 61-73, 1987.
• [24] J. J. Grefenstette, J. E. Baker, How genetic algorithms work: A critical look at implicit parallelism, In J. I). Shaffer, Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kaufmann Publ., pp. 20-27, San Mateo, CA, 1989.
• [25] P. J. B. Hancock, An empirical comparison of selection methods in evolutionary algorithms, In T. C. Fogarty (ed.), Evolutionary Computing, AISB Workshop, Volume 865 of Lecture Notes in Computer Science, Springer Verlag, Berlin, pp. 80-94, 1994.
• [26] J. Stańczak. Rozwój koncepcji i algorytmów dla samodoskonalących się systemów ewolucyjnych, Rozprawa doktorska, Politechnika Warszawska, Wydział Elektroniki i Technik Informacyjnych, Warszawa 1999.
• [27] K. A. De Jong, An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Doctoral Dissertation, University of Michigan, 1975.
• [28] P. C. Winter, G. I. Hickey, H. L. Fletcher, Krótkie wykłady - Genetyka, PWN, Warszawa 2002.
• [29] T. Bäck, F. Hoffmeister, H. P. Schwefel, A Survey of Evolution Strategies, Proceedings of the Fourth International Conference on Genetic Algorithms (ICGA), R. K. Belew, L. B. Booker (eds.), Morgan Kaufmann Publ., pp. 2-9, 1991.
• [30] Murawski K., Obliczenia ewolucyjne - geneza i zastosowanie, Biuletyn Instytutu Automatyki i Robotyki WAT. Numer 15/2001.
• [31] Holland J.H.. Adaptation in natural and artificial systems, University of Michigan Press, 1975.
• [32] Fogel L. J., Owens J. A., Walsh M. J., Artificial intelligence through simulated evolution, John Wiley & Sons Publishing, 1966.
• [33| Fogel D., Evolving Artificial Intelligence, PhD Thesis, University of California, San Diego, CA, 1992.
• [34] Reachenberg I., Evolutionstrategie,: optimierung technischer systeme nach prinzipien der biologischen evolution, Frommann - Holzboog, 1973.
• [35] Bäck T., Evolutionary Algorithms in Theory and Practice. Oxford University Press. New York, 1996.
• [36] Koza J., Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, Cambridge, MA, 1992.
• [37] Cavicchio D. .J., Adaptive search using simulated evolution. Unpublished doctoral dissertation, University of Michigan, Ann Arbor, 1970.
• [38] Goldberg D. E, Richardson J., Genetic algorithms with sharing for multimodal function optimization, Genetic algorithms and their applications. Proceedings of the Second International Conference on Genetic Algorithms. pp. 41-49, 1987.
• [39] Fonseca C. M., Multiobjective Genetic Algorithms with Application to Control Engineering Problems, PhD thesis, Department of Automatic Control and Systems Engineering, University of Sheffield, 1995.
• [40] Schaffer J. D., Multiple. objective optimization with vector evaluated genetic algorithms, In Genetic Algorithms and their Applications, Proceedings of the First International Conference on Genetic Algorithms, pp. 93-100, Lawerence Erlnaum, 1985.
• [41] Grefenstette J. J., GENESIS: A system for using genetic search procedures, In Proceedings of 1984 Conference on Intelligent Systems and Machines, pp. 161-165, 1984.
• [42] Tamaki H., Kita H., Kobayashi S., Multi-Objective Optimization by Genetic Algorithms: A Review, In Toshio Fukuda and Takeshi Furuhashi (Eds.), Proceedings of the 1996 International Conference on Evolutionary Computation (ICEC'96), pp. 517-522, Nagoya, Japan, 1996.
• [43] Fonseca C. M., Fleming P. J., Genetic. Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization, In Stephanie Forrest (Ed.), Proceedings of the Fifth International Conference on Genetic Algorithms, pp, 416-423, San Mateo, California, University of Illinois at Urbana-Champaign. Morgan Kauffman Publishers, 1993.
• [44] Srinivas N., Deb K., Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Evolutionary Computation, 2:3, pp. 221-248, 1995.
• [45] Horn J., Nafpliotis N., Multiobjective Optimiazation using the Niched Pareto Genetic Algorithm, Technical Report IlliGAl Report 93005, University of Illinois at Urbana-Champaign, Urbana, Illinois, USA, 1993.
• [46] Michalewicz Z., Dasgupta D., Le Riche R. G., Schoenauer M., Evolutionary Algorithms for Constrained Engineering Problems, Computers & Industrial Engineering Journal, Vol. 30, No. 4, pp. 851-870, 1996.
• [47] Michalewicz, Z. and Schoenauer, M., Evolutionary Algorithms for Constrained Parameter Optimization Problems, Evolutionary Computation, Vol.4, No.1, 1996, pp.1-32.
• [48] Michalewicz Z., Janikow C. Z., Handling constraints in genetic algorithrns, In R.K. Belew, L. B. Booker (Eds.), Proceedings of Fourth International Conference on Genetic Algorithms, pp. 151-157, Morgan Kaufmann, 1991.
• [49] Schoenauer M., Xanthakis S., Constrained GA optimization, In S. Forrest (Ed.), Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 573-580, Morgan Kaufmann, 1993.
• [50] Powel D., Skolnick M. M., Using genetic algorithms in engineering design optimization with non-linear constraints, In S. Forrest (Ed.), Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 424-430, Morgan Kaufmann, 1993.
• [51] Michalewicz Z., Nazhiyath G., GENOCOP III: A co-evolutionary algorithm for numerical optimization problems with nonlinear constraints. In D. B. Fogel (Ed.), Proceedings of the Second IEEE International Conference On Evolutionary Computation, pp. 647-651, IEEE Press, 1995.
• [52] A. Słowik, M. Białko, Modified Version of Roulette Selection for Evolution Algorithm - The Fan Selection, Proceedings of Seventh International Conference on Artifficial Intelligence and Soft Computing, ICAISC 2004, Lecture Notes in Artificial Intelligence, Volume 3070/2004, pp. 474-479, Springer-Verlag, Zakopane, June 2004.