A Lamarckian Genetic Algorithm Applied to the Travelling Salesman Problem
Bereket Tesfaldet, Augusto Y. Hermosilla · Advances in Complex Systems · 1999
Genetic Algorithms (GAs) comprise a class of adaptive heuristic search methods analogous to genetic inheritance and Darwinian strife for survivial of individuals within a population. Today, GAs are widely used to solve complex optimization problems, including ill-conditioned and NP-complete types arising in business, commerce, engineering, large-scale industries, and many other areas. To address these wide areas of applications and to improve upon their drawbacks, many variations and modifications of GAs have been proposed. The GA variation proposed in this paper has four basic operators: reproduction, recombination and two mutation operators, particularly applied to the famous and extensively studied Traveling Salesman Problem (TSP) in large-scale combinatorial optimization. Three of the operators use diversity information (standard deviation of costs) from the current population to adjust the diversity of the next population. The fourth one is an introduced new mutation operator called p-displacement that simulates the Lamarckian evolutionary learning and training concepts of gene improvement to bring chromosomes to their local optimum. We call the proposed GA: Lamarckian Genetic Algorithm-Traveling Salesman Problem (LGA-TSP). Emprical results show performance improvements compared to the classic and other modified GAs, as well as simulated annealing.