Extensions of genetic algorithms

Abstract

Genetic algorithms (GA) (Holland, 1975) are higher-level procedures to provide a sufficiently good solution to an optimization problem when there is imperfect information, or computational capacity is limited. GAs are based on the natural selection process that belongs to evolutionary algorithms. GAs rely on evolutionary factors like crossover, mutation, and selection based on Darwin's theory that led to the evolution of species. Selection: First step in the process, selection helps the survival of the fittest and to pass on their genes to future generations Crossover: This is a mating operation where two chromosomes are chosen and are mated in which the genes at random crossover sites are interchanged to create an entirely new chromosome. Mutation: This is mainly done to avoid early local minima. In this mutation operation, randomly chosen genes are inserted into the chromosomes to increase the diversity of the population. GA are generally applied to solve global optimization problems in contrast to algorithms that can quickly identify local optima to a problem. Lots of applications are built for scheduling problems using GA. It also has its applications in natural sciences, mathematics, finance, social sciences, etc. In this project, we have used modified Genetic Algorithms to solve a Multiple Facility Location Problem (MFLP) and Travelling Salesman Problem (TSP).