Presentation | 2003/7/25 A Proposal and Evaluation of Heuristic Scheme for Solving TSP Based on the Evolution of Instances Shin'ichiro UMEZANE, Satoshi FUJITA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Evolutionary computation is a method for solving combinatorial optimization problems, that is based on the imitation of livings that could evolve themselves into the environment. Actual livings take different ways of evolutions when they are placed on different environment. From the viewpoint of mathematical optimization, such a phenomenon could be regarded as a modification of the energy space according to the change of the actual environment whose concrete landscape depends on the current instance. In addition, we could observe in many cases that a good solution could be easily obtained for the instances with a simple landscape, that motivates the study of "evolution" of the given instance depending on the change of the environment, as was originally pointed out by Papadimitriou and Sideri in 1998. In this paper, we extend the observations made by Papadimitriou and Sideri, and propose a new scheme based on a similar idea on the evolution of instances. The result of experiments implies that our extension really improves the performance of the previous scheme. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | traveling salesman problem / evolutionary computation / genetic algorithm |
Paper # | COMP2003-24 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 2003/7/25(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Theoretical Foundations of Computing (COMP) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | A Proposal and Evaluation of Heuristic Scheme for Solving TSP Based on the Evolution of Instances |
Sub Title (in English) | |
Keyword(1) | traveling salesman problem |
Keyword(2) | evolutionary computation |
Keyword(3) | genetic algorithm |
1st Author's Name | Shin'ichiro UMEZANE |
1st Author's Affiliation | Department of Information Engineering, Garaduate School of Engineering Hiroshima University() |
2nd Author's Name | Satoshi FUJITA |
2nd Author's Affiliation | Department of Information Engineering, Garaduate School of Engineering Hiroshima University |
Date | 2003/7/25 |
Paper # | COMP2003-24 |
Volume (vol) | vol.103 |
Number (no) | 246 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |