A Lamarckian Genetic Algorithm Applied to the Travelling Salesman Problem

Genetic Algorithms(GAs) comprise aclass of adaptive heuristic search methodsanalogous 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, recombinationand twomutation operators, particularly applied to the famous and extensively studiedTraveling 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 calledp-displacementthat simulates theLamarckian evolutionary learning and trainingconcepts 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.