The massively parallel mixing genetic algorithm for the traveling salesman problem
| Autor: | Swetha Varadarajan, Darrell Whitley |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
education.field_of_study
Computer science Offspring Population Crossover MathematicsofComputing_NUMERICALANALYSIS Evolutionary algorithm 0102 computer and information sciences 02 engineering and technology Evaluation function ComputingMethodologies_ARTIFICIALINTELLIGENCE 01 natural sciences Travelling salesman problem 010201 computation theory & mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Genetic algorithm 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing SIMD education Algorithm Massively parallel |
| Zdroj: | GECCO |
| Popis: | A new evolutionary algorithm called the Mixing Genetic Algorithm is introduced for the Traveling Salesman Problem. The Mixing Genetic Algorithm does not use selection or mutation, and the children replace the parents every generation. The recombination operator is partition crossover. Partition crossover is respectful and transmits alleles (edges); this makes it possible to generate two offspring, the best possible offspring and the worst possible offspring, such that no edges are lost during recombination. The Mixing Genetic Algorithm organizes the population so that better solutions are usually recombined with other good solutions. Because no edges are lost or created during recombination, there is no need to access the evaluation function after the first generation. This dramatically reduces communication costs; this makes it possible to implement the Mixing Genetic Algorithm on massively parallel SIMD machines with limited memory. The Mixing Genetic Algorithm never loses diversity and cannot prematurely converge. We compare the Mixing Genetic Algorithm to EAX, one of the best inexact solvers for the Traveling Salesman Problems. For many problems the Mixing Genetic Algorithm finds optimal solutions using fewer recombinations than EAX. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|