Algorytmy genetyczne, ewolucyjne i metaheurystyki : Wybrane zagadnienia

• Autorzy: Tadeusz (red.) Trzaskalik

Warianty tytułu

Selected Issues on Genetic, Evolutional and Metaheuristics Algorithms.

• Języki publikacji: PL

Abstrakty

Celem publikacji jest wprowadzenie w problematykę algorytmów genetycznych, ewolucyjnych i metaheurystyk, ze szczególnym uwzględnieniem ich zastosowania do rozwiązywania problemów optymalizacji. Omówiono klasyczny algorytm genetyczny w optymalizacji. Zaprezentowano badanie możliwości konstrukcji portfela bezpiecznego przy wykorzystaniu algorytmu genetycznego (rozpatrywano model zawierający zmienne binarne). Przedstawiono rozwiązanie problemu układania optymalnych tras dla cystern w spółdzielni mleczarskiej przy wykorzystaniu metod programowania ewolucyjnego. Opisano przykładowe wzorce projektowe, które mogą być stosowane podczas projektowania algorytmów optymalizacji na podstawie metaheurystyki, takich jak lokalne przeszukiwanie i algorytmy ewolucyjne.

EN

The issues on genetic, evolutional and metaheuristics algorithms, their application and solving problems of optimization have been the aim of the paper. Classical genetic algorithm in optimization has been discussed. Possibilities of construction a safe portfolio using the genetic algorithm were presented. An attempt to solve a problem of the optimal vehicle routing in creamery using evolutional programming methods has been also presented. An exemplary design patterns used for optimization algorithms design based on metaheuristics such as local search and evolutional algorithms have been described. (AŁ)

Słowa kluczowe

PL

Programowanie matematyczne; Algorytmy genetyczne; Optymalizacja matematyczna; Programowanie genetyczne

EN

Mathematical programming; Genetic algorithms; Mathematical optimization; Genetic programming

• Czasopismo: Prace Naukowe / Akademia Ekonomiczna w Katowicach
• Rocznik: 2005
• Strony: 137

Twórcy

autor

Tadeusz (red.) Trzaskalik

Bibliografia

• Arabas J. (2001). Wykłady z algorytmów ewolucyjnych. WNT, Warszawa.
• Benson H.Y., Shanno D.F., Vanderbei R.J. (2000). Interior-point Methods for Nonconvex Nonlinear Programming: Filter Methods and Merit Functions. Technical Report GRFE-OO-O6. Operation Research and Financial Engineering, Princeton University, Princeton.
• Benson H.Y., Shanno D.F., Vanderbei R.J. (2002). Interior-point Methods for Nonconvex Nonlinear Programming: Complementarity Constraints. Technical Report ORFE-O2-O2. Operation Research and Financial Engineering, Princeton University, Princeton.
• Boese K., Kahng A., Muddu S. (1994). A New Adaptive Multistart Technique for Combinatorial Global Optimization. Operations Research Letters, 16, 101 113.
• Broyden C.G. (1970). The Convergence of a Class of Double Rank Minimization Algorithms. Parts I and II. Journal of the Institute of Mathematics and Its Applications, 6, 76-90 and 222-231.
• Bunch J.R., Kaufman L., Parlett B.N. (1976). Decomposition of a Symmetrie Matrix. Numerische Mathematik, 27, 95-109.
• Całczyński A. (1992). Metody optymalizacji w obsłudze transportowej rynku. PWE, Warszawa.
• Całczyński A., Kędzierska-Stróż D., Orzechowska D., Śleszyński Z. Elementy badań operacyjnych w zarządzaniu.
• Clarke G., Wright J.W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Reseach, 12, 568-581.
• Cooper J.W. (2001). Java. Wzorce projektowe. Helion, Gliwice.
• Cytowski J. (1996). Algorytmy genetyczne. Podstawy i zastosowania. Akademicka Oficyna Wydawnicza PLJ.
• Elton E., Gruber M., Padberg M. H998). Nowoczesna teoria portfelowa i analiza papierów wartościowych. WIG-Press, Warszawa.
• Fisher M., Jaikumar R. (1981). A Generalized Assignment Heuristic for the Vehicle Routing. Networks, 11, 109-124.
• Fletcher R. {1970). A New Approach to Variable Metric Algorithms. Computer Journal, 13, 317-322.
• Galinier P., Hao J.-K. [1999]. Hybrid Evolutionary Algorithms for Graph Coloring. Journal of Combinatorial Optimization, 3, 4, 379 397.
• Gillet B.E., Miller L.R. (1974). A Heuristic Algorithm for the Vehicle Dispatch Problem. Operations Research, 22, 340-349.
• Glover F. (1989), Tabu Search - Part I, ORSA J. Comput., 1, 190-206.
• Goldberg David E. {1995). Algorytmy genetyczne i ich zastosowania. Wydawnictwa Naukowo-Techniczne, Warszawa.
• Goldfarb D. M 970). A Family of Variable Metric Methods Derived by Varational Means. Mathematics of Computation, 24, 23-26.
• Grefenstette J: J. (1990). A User's Guide to GENESIS Version 5.O.
• Gwiazda T.: (1998). Algorytmy genetyczne. Zastosowania w finansach. Wydawnictwo Wyższej Szkoły Przedsiębiorczości i Zarządzania im. L. Koźmińskiego, Warszawa.
• Haugen R. (1996). Teoria nowoczesnego inwestowania. WIG-Press, Warszawa.
• Hjoring C. (1995). The Vehicle Routing Problems and Local Search Metaheuristics. Pch.D., Department of Engineering Science, The University of Auckland, USA.
• Holland J.H. [1975). Adaptation In natural and Artificial Systems. The University of Michigan Press, Michigan.
• Hornberger J., Gehring H. [1999). Two Evolutionary Meta-heuristics for the Vehicle Routing Problem with Time Windows. INFOR, 37, 297 318.
• http://www.prism.uvsq.fr/~vdc/ROADEF/CHALLENGES/2O03/
• Ignasiak E. (1996). Badania operacyjne. PWE, Warszawa.
• Jadczak R. (2001). Zastosowanie zadań rozwózkowo-zwózkowych w transporcie mleczarskim. W: Metody i zastosowania badań operacyjnych 2000. Red. D. Kopańska-Bródka. AE, Katowice.
• Jarek S. (2O04). Modyfikacja metod programowania nieliniowego przy pomocy algorytmów genetycznych i jej zastosowanie do konstrukcji portfela akcji na Warszawskiej Giełdzie Papierów Wartościowych. PhD thesis, Uniwersytet Łódzki, Łódź.
• Jasiński L.J. (1987). Optymalizacja dostawy towarów na zaopatrzenie rynku w warunkach niepewności. Instytut Rynku Wewnętrznego i Konsumpcji, Warszawa.
• Jaszkiewicz A. (1997). Inżynieria oprogramowania. Helion, Gliwice.
• Jaszkiewicz A. (1999). Improving Performance of Genetic Local Search by Changing Local Search Space Topology. Foundations of Computing and Decision Sciences, 24, 2, 77 84.
• Jaszkiewicz A., (20O4). Adaptation of the genetic local search algorithm to the management of Earth observation satellites, VII Krajowa Konferencja Algorytmy Ewolucyjne i Optymalizacja Globalna, Kazimierz Dolny, 24-26.05.2O04, 67-74.
• Jaszkiewicz A., Kominek P. (2003). Genetic Local Search with Distance Preserving Recombination Operator for a Vehicle Routing Problem. European Journal of Operational Research, 151/2, 352-364.
• Jaszkiewicz A., Kubiak M., Kominek P. (2004). The Application of the Genetic Local Search Algorithm to Car Sequencing Problem. VII Krajowa Konferencja Algorytmy Ewolucyjne i Optymalizacja Globalna. Kazimierz Dolny, 24-26.05.2004, 75-82.
• Kataoka S. (1963). A Stochastic Programming Model. Econometrica, 31. 181-196.
• Kirkpatrick S., Gelatt C.D. Vecchi M.P. (1983). Optimization by Simulated Annealing. Science, 220, 671-680.
• Kopańska-Bródka D. (1991). Metody stochastycznego programowania liniowego i ich praktyczne zastosowanie w badaniach naukowych. AE, Katowice.
• Kopańska-Bródka D. (2001). Optymalne decyzje inwestycyjne. AE, Katowice.
• Krawczyk S. (1990). Matematyczna analiza sytuacji decyzyjnych. PWE, Warszawa.
• Krawczyk S. (2001). Metody ilościowe w logistyce (przedsiębiorstwa). Academia Oeconomica, Warszawa.
• Kühn H., Tucker A. (1951). Nonlinear Programming. In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability. Univeresity of California Press, Berkeley.
• Lin S., Kernighan B.W. (1973). An Effective Heuristic Algorithm for the Traveling Salesman Problem. Operations Research, 21, 498-516.
• Lin S., Kernighan B.W. (1973). An Effective Heuristic for the Traveling Salesman Problem. Operations Research, 21, 498-516.
• Markowitz H.M. (1952). Portfolio Selection. Journal of Finance, 7, 77-91.
• Markowitz H.M. (1959). Portfolio Selection - Efficient Diversification of Investments. Yale University Press, New Haven.
• Mayo H. (1997). Wstęp do inwestowania. K.E. Liber, Warszawa.
• Merz P., Freisieben B. (2000). Fitness Landscape Analysis and Memetic Algorithms for the Quadratic Assignment Problem. IEEE Transactions on Evolutionary Computation, 4, 4, 337 352.
• Merz P.. Freisieben B. f 1997). Genetic Local Search for the TSP: New Results. In: Proceedings of the 1997 IEEE International Conference on Evolutionary Computation. IEEE Press, 159 164.
• Michalewicz Z. (1998). Algorytmy genetyczne + struktury danych = programy ewolucyjne. Wydawnictwa Naukowo-Techniczne, Warszawa.
• Mitchell M. (1999)- An Introduction to Genetic Algorithms. MIT Press, New York.
• Neumann von J. (1966). Theory of Self-reproducing Automata. The University of Illinois Press, Illinois.
• Osman I. and Laporte G. (1996). Metaheuristics: A Bibliography. Annals of Operations Research, 65, 513-623.
• Pedrycz W. (1998). Computational Intelligence An Introduction. CRC Press, New York.
• Pirlot M. (1996). General local search methods. European Journal of Operational Research, 92, 3: 493-511.
• Powell M.J.D. (1972). Problems Related to Unconstrained Optimization. W: Numerical Methods for Unconstrained Optimization. Red. W. Murray. Academic Press, London.
• Ross P. (2001). The PGA v4.0 manual.
• Rutkowska D., Piliński M., Rutkowski L. (1999). Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. Wydawnictwo Naukowe PWN, Warszawa-Łódź.
• Sengupta J.K. (1985). Optimal Decisions Under Uncertainty: Methods, Models, and Managment. Springer-Verlag, Berlin and New York.
• Shano D.F. (1970). Conditioning of Quasi-newton Methods for Function Minimization. Mathematics of Computation, 24, 647-656.
• Sysło M., Deo N., Kowalik J. (1995]. Algorytmy optymalizacji dyskretnej z programami w języku Pascal. WN PWN, Warszawa.
• Tarczyński W. (1997). Rynki kapitałowe. Metody ilościowe, Vol. 2. Agencja Wydawnicza "Placet", Warszawa.
• Teghem J. and Pirlot M. (2O02). Optimisation approchee en recherche operationelle. Hermes.
• van Breedam A. [1994). An Analysis of the Behaviour of Heuristics for the Vehicle Routing Problem for a Selection of Problems with Vehicle-related, Customer-ralated and Time-related Constraints. Pch.D., University of Antwerp, Antwerpia.
• Walukiewicz S. (1991). Integer Programming. PWN, Warszawa.
• Whitley D. (1994). A Genetic Algorithms Tutorial. W: Statistic & Computing, Special Issue on Evolutionary Computation. Red. Z. Michalewicz. 4, 65-85.
• Wit R. (1986). Metody programowania nieliniowego. WNT, Warszawa.
• Wolpert D.H., Macready W.G. (1997). No free Lunch Theorem for Optimization. IEEE Transactions on Evolutionary Computation, 1 (1), 67-82.
• www.cplex.corn