The Film Copy Deliverer Problem (FDP),much more difficult than TSP,is a new problem in the combination optimization. In this paper,a new algorithm is introduced. First,the FDP is converted to TSP. Then an evolutionary...The Film Copy Deliverer Problem (FDP),much more difficult than TSP,is a new problem in the combination optimization. In this paper,a new algorithm is introduced. First,the FDP is converted to TSP. Then an evolutionary algorithm based on inversion operator is adopted. Compared with other Genetic Algorithms,it is not only more simple and easier to realize but also faster and more accurate.展开更多
Abstract In this paper, we introduce a hybrid algorithm to search the approximate solution of TSP, which contains the advantage of Lin's algorithm, simulate annealing algorithm, genetic algorithm and Domain Decomp...Abstract In this paper, we introduce a hybrid algorithm to search the approximate solution of TSP, which contains the advantage of Lin's algorithm, simulate annealing algorithm, genetic algorithm and Domain Decomposition method. The algorithm has been successfully used in solving many TSP problems from 100 to 100000 cities. Those applications demonstrate the efficiency of the algorithm.展开更多
Based on the analysis of previous genetic algorithms (GAs) for TSP, a novel method called Ge- GA is proposed. It combines gene pool and GA so as to direct the evolution of the whole population. The core of Ge- GA is t...Based on the analysis of previous genetic algorithms (GAs) for TSP, a novel method called Ge- GA is proposed. It combines gene pool and GA so as to direct the evolution of the whole population. The core of Ge- GA is the construction of gene pool and how to apply it to GA. Different from standard GAs, Ge- GA aims to enhance the ability of exploration and exploitation by incorporating global search with local search. On one hand a local search called Ge- Lo-calSearch operator is proposed to improve the solution quality, on the other hand the modified Inver-Over operator called Ge InverOver is considered as a global search mechanism to expand solution space of local minimal. Both of these operators are based on the gene pool. Our algorithm is applied to 11 well-known traveling salesman problems whose numbers of cities are from 70 to 1577 cities. The experiments results indicate that Ge- GA has great robustness for TSP. For each test instance, the average value of solution quality, found in accepted time, stays within 0. 001% from the optimum.展开更多
文摘The Film Copy Deliverer Problem (FDP),much more difficult than TSP,is a new problem in the combination optimization. In this paper,a new algorithm is introduced. First,the FDP is converted to TSP. Then an evolutionary algorithm based on inversion operator is adopted. Compared with other Genetic Algorithms,it is not only more simple and easier to realize but also faster and more accurate.
文摘Abstract In this paper, we introduce a hybrid algorithm to search the approximate solution of TSP, which contains the advantage of Lin's algorithm, simulate annealing algorithm, genetic algorithm and Domain Decomposition method. The algorithm has been successfully used in solving many TSP problems from 100 to 100000 cities. Those applications demonstrate the efficiency of the algorithm.
基金Supported by the National Natural Science Foundation of China(70071042,60073043,and 60133010)
文摘Based on the analysis of previous genetic algorithms (GAs) for TSP, a novel method called Ge- GA is proposed. It combines gene pool and GA so as to direct the evolution of the whole population. The core of Ge- GA is the construction of gene pool and how to apply it to GA. Different from standard GAs, Ge- GA aims to enhance the ability of exploration and exploitation by incorporating global search with local search. On one hand a local search called Ge- Lo-calSearch operator is proposed to improve the solution quality, on the other hand the modified Inver-Over operator called Ge InverOver is considered as a global search mechanism to expand solution space of local minimal. Both of these operators are based on the gene pool. Our algorithm is applied to 11 well-known traveling salesman problems whose numbers of cities are from 70 to 1577 cities. The experiments results indicate that Ge- GA has great robustness for TSP. For each test instance, the average value of solution quality, found in accepted time, stays within 0. 001% from the optimum.
