Improving Edge Recombination through Alternate Inheritance and Greedy Manner
Chuan-Kang Ting
Abstract:
Genetic Algorithms (GAs?) are well-known heuristic algorithms and have been widely applied to solve combinatorial problems. Edge recombination is one of the famous crossovers designed for GAs? to solve combinatorial problems. The essence of edge recombination is to achieve maximal inheritance from parental edges. This paper presents two strategies to improve edge recombination. First, we encourage alternation of parents in edge inheritance. Second, a greedy method is used to handle the failures occurred in edge recombination. A modified edge recombination, called edge recombination with tabu (Edge-T), is proposed according to these two strategies. The traveling salesman problem is used as a benchmark to demonstrate the effectiveness of the proposed methof. Experimental results indicate that Edge-T can achieve better performance than the conventional edge recombination Edge-3 in terms of both solution quality and convergence speed.
Bibliographical:
@InProceedings{ting:evocop04, author = "Chuan-Kang Ting", title = "Improving Edge Recombination through Alternate Inheritance and Greedy Manner", booktitle = "Evolutionary Computation in Combinatorial Optimization -- {EvoCOP}~2004", year = "2004", month = "5-7 " # apr, editor = "Jens Gottlieb and G{\"u}nther R. Raidl", series = "LNCS", volume = "3004", address = "Coimbra, Portugal", publisher = "Springer Verlag", publisher_address = "Berlin", pages = "210--219", keywords = "evolutionary computation", notes = "EvoCOP2004", }
URL:
http://wwwcs.uni-paderborn.de/cs/ag-klbue/en/staff/ckting/publications/evocop2004.pdf