Efficiency of selected meta-heuristics applied to the TSP problem: a simulation study

• Autorzy: Kwaśnicka H.
• Języki publikacji: EN

Abstrakty

EN

The paper presents a simulation study of the usefulness of a numberof meta-heuristicsused as optimisation methods forTSPproblems. The five considered approaches are outlined: GeneticAlgorithm, Simulated Annealing, Ant Colony System, Tabu Search and Hopfield Neural Network.Using a purpose-developed computer program, efficiency of the meta-heuriticshas been studied andcompared. Results obtained from about 40000 simulation runs are briefly presented and discussed.

Słowa kluczowe

EN

ant colony; genetic algorithms; simulated annealing; tabu search; neural networks

• Wydawca: Politechnika Gdańska
• Czasopismo: TASK Quarterly : scientific bulletin of Academic Computer Centre in Gdansk
• Rocznik: 2003
• Tom: Vol. 7, No 1
• Strony: 73--91
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

Kwaśnicka H.

• Department of Computer Science, Wroclaw University of Technology, Wyb. Wyspiańskiego 27, 50-370 Wrocław, Poland

Bibliografia

• [1] Goldberg D E 1989 Genetic Algorithms in Search, Optimization and Machine Learning,Addison-Wesley
• [2] Holland J H 1975 Adaptation in Natural and Artificial Systems, The University of Michigan
• [3] Kwaśnicka H 1999 Evolutionary Computations in Artificial Intelligence, Oficyna Wydawnicza,Wroclaw University of Technology, Wroclaw, Poland (in Polish)
• [4] Michalewicz Z 1992 Genetic Algorithms + Data Structures = Evolutionary Programs, Sprin-ger-Verlag
• [5] Schmit L and Amini M M 1998 European J. Operational Research108551
• [6] Cerny V 1985 J. Optim. Theory Appl.4541
• [7] Kirkpatrick S, Gellat C D and Vecchi M P 1983 Science22067
• [8] Metropolis N, Rosenbluth A, Rosenbluth M, Teller A and Teller E 1953 J. Chem. Phys.211087
• [9] Davis L 1987 Genetic Algorithms and Simulated Annealing, Morgan Kaufmann Publishers,Inc., San Mateo, California
• [10] Dorigo M, Di Caro G and Gambardella L M 1998 Tech. Rep. IRIDIA/98-10, Universit’e Librede Bruxelles, Belgium, http://iridia.ulb.ac.be/∼mdorigo/ACO/ACO
• [11] Dorigo M 1992 Optimization, Learning and Natural Algorithms, PhD Thesis, Dipartimentodi Elettronica, Politecnico di Milano, Italy,http://iridia.ulb.ac.be/∼mdorigo/ACO/ACO.html
• [12] Bonabeau E, Dorigo M and Theraulaz G 1999 From Natural to Artificial Swarm Intelligence,Oxford University Press
• [13] Deneubourg J L, Aron S, Goss S and Pasteels J M 1990 J. Insect Behaviour3159
• [14] Tsubakitani S and Evans J R 1998 Computers Ops. Res. Elsevier Science Ltd.2(25) 91
• [15] Helsgaun K 2000 European J. Operational Research126106
• [16] Korbicz J and Obuchowicz A 1994 Artificial Neural Networks. Basis and Applications,Akademicka Oficyna Wydawnicza PLJ, Warsaw, Poland (in Polish)
• [17] Mueller B, Reinhardt J and Strickland M 1995 Neural Networks, Springer Verlag
• 18] Tadeusiewicz R 1993 Neural Networks, Akademicka Oficyna Wydawnicza, Warsaw, Poland(in Polish)
• [19] Stefaniak A 2001 Comparison of Selected Methods Inspired by Nature UsingTSPProblemas an Example, MSc Thesis, Department of Computer Science, Wroclaw University of Technology, Wroclaw, Poland (in Polish)
• [20] Podleśny A 1999 About Simulated Annealing and its Application to Optimal Block Generation,http://chimera.ae.krakow.pl/ketrii/sssg/sssgdaw/a99/podlesny.htm