Edge recombination with edge sensitivity in TSP problem

• Autorzy: Kęsy J. , Domański Z.
• Języki publikacji: EN

Abstrakty

EN

We use an evolutionary algorithm with a modified version of edge recombination crossover to search near optimal tours in the Traveling Salesman Problem (TSP). We introduce so called edge sensitivity to estimate the importance of having a given edge within an optimal solution. In order to test this approach we used the data files gr24, bays29 and gr48. Results we obtained show that edge sensitivities allow us to find solutions quicker than other similar algorithms with an edge recombination crossover.

Słowa kluczowe

EN

traveling salesman problem; recombination operators; edge recombination

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Prace Naukowe Instytutu Matematyki i Informatyki Politechniki Częstochowskiej
• Rocznik: 2003
• Tom: Vol. 2, nr 1
• Strony: 55--60
• Opis fizyczny: Bibliogr. 12 poz., tab.

Twórcy

autor

Kęsy J.

• Institute of Mathematics and Computer Science, Czestochowa University of Technology

autor

Domański Z.

• Institute of Mathematics and Computer Science, Czestochowa University of Technology
• Polonia University, Czestochowa

Bibliografia

• [1] Kirkparick S., Gelatt C.D., Jr., Vecchi M.P., Science 1983, 220, 671.
• [2] Holland J.H., Adaptation in Natural nad Artificial Systems, University of Michigan Press, Ann Arbor 1975.
• [3] Fogel D.B., Evolutionary Computation - Toward a New Philosophy of Machine Intelligence, IEEE, Piscataway 1995.
• [4] Koza J.R., Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, Cambridge 1992.
• [5] Michalewicz Z., Genetics Algorithms + Data Structures = Evolution Programs, Springer-Verlag, Berlin, Heidelberg 1996.
• [6] Garey M., Johnson D., Computers and Intractability, W.H. Freeman, San Francisco 1979.
• [7] Whitley D., Starkweather T., Fuquay D.A., Scheduling Problems and Traveling Salesman: The Genetic Edge Recombination Operator, Proc. 3th Int. Conf. on Genetic Algorithms, J. Schaffer (Editor), Morgan Kaufmann Publishers 1988, 133-140.
• [8] Robles V., Miguel P.D., Larranaga P., Solving the traveling salesman problem with EDAs, Estimation of Distribution Algorithms, eds P. Larranaga, J.A. Lozano, Kluwer Academic Publishers 2002, Chapter 10, 211-229.
• [9] Oliver I., Smith D., Holland J., A study of permutation crossover operators on the travel salesman problem, Proc. 2nd Int. Conf. on Genetic Algorithms, Lavrence Erlbaum Associates, Hillsdale 1987, 224-230.
• [10] Starkweather T., McDaniel S., Mathias K., Whitley D., Whitley C., A comparison of genetic sequence operators, Proc. 4th Int. Conf. on Genetic Algorithms, Morgan Kaufmann Publishers 1991, 69-76.
• [11] Goldberg D.E., Genetic algorithms in search, optimization and machine learning, Addison-Wesley Publishing Company 1989.
• [12] Tsutsui S., Goldberg D.E., Pelikan M., Solving Sequence Problems by Building and Sampling Edge Histograms, IlliGAL Report No. 2002024, August 2002, http//www-illigal.ge.uiuc.edu

Uwagi

EN

The papers have been presented during the session devoted to application of mathematics (as part of International Conference on Parallel Processing and Applied Mathematics).