Commonality and Genetic Algorithms
作者： Stephen Chen , Stephen E Smith
DOI:
关键词: Order (group theory) 、 Operator (computer programming) 、 Schema (psychology) 、 Hybrid genetic algorithms 、 Operations research 、 Travelling salesman problem 、 Basis (linear algebra) 、 Power (physics) 、 Theoretical computer science 、 Crossover 、 Engineering
摘要: The comnionality hypothesis introduced in this paper sugrcsts that the prescrvation of cummnn schemata i ? centml source power n rccomhination operators. A commonalilyhared crossovcr operator proceeds two steps: I idcntify maximal coininon schema parents. and 2) coinplcte solution with a construction hcuristic. Using framework, new crossover opcrators are proposed for sequcncing problcms. first uses partial order basis cummonalily. This is shown lu perform well on Traveling Salesman Problem (TSP); it finds best-known soIution~ many Sequential Ordcring (SOP) instances. second based sub-tours/edgesl t used to demonstrate utility liamework designing hybrid genetic algorithms.
参考文章(17)
L. Darrell Whitley, Timothy Starkweather, Keith E. Mathias, S. McDaniel, C. Whitley, A Comparison of Genetic Sequencing Operators. international conference on genetic algorithms. pp. 69- 76 ,(1991)
D. J. Smith, J. R. C. Holland, I. M. Oliver, A study of permutation crossover operators on the traveling salesman problem international conference on genetic algorithms. pp. 224- 230 ,(1987)
Brian J. Rosmaita, John J. Grefenstette, Dirk Van Gucht, Rajeev Gopal, Genetic Algorithms for the Traveling Salesman Problem international conference on genetic algorithms. pp. 160- 168 ,(1985)
Prasanna Jog, Jung Y. Suh, Dirk van Gucht, The effects of population size, heuristic crossover and local improvement on a genetic algorithm for the traveling salesman problem international conference on genetic algorithms. pp. 110- 115 ,(1989)
Lawrence Davis, Applying adaptive algorithms to epistatic domains international joint conference on artificial intelligence. pp. 162- 164 ,(1985)
Gerhard Reinelt, The traveling salesman: computational solutions for TSP applications Springer-Verlag. ,(1994)
S.N. Talukdar, P.S. de Souza, Scale efficient organizations systems, man and cybernetics. pp. 1458- 1463 ,(1992) , 10.1109/ICSMC.1992.271577
DARRELL WHITLEY, TIMOTHY STARKWEATHER, GENITOR II.: a distributed genetic algorithm Journal of Experimental and Theoretical Artificial Intelligence. ,vol. 2, pp. 189- 214 ,(1990) , 10.1080/09528139008953723
L.F. Escudero, An inexact algorithm for the sequential ordering problem European Journal of Operational Research. ,vol. 37, pp. 236- 249 ,(1988) , 10.1016/0377-2217(88)90333-5
S. Lin, B. W. Kernighan, An Effective Heuristic Algorithm for the Traveling-Salesman Problem Operations Research. ,vol. 21, pp. 498- 516 ,(1973) , 10.1287/OPRE.21.2.498