Incremental Genetic Algorithm

Abstract

Classical Genetic Algorithms (CGA) are known to find good sub-optimal solutions for complex and intractable optimization problems. In many cases, problems undergo frequent minor modifications, each producing a new problem version. If these problems are not small in size, it becomes costly to use a genetic algorithm to reoptimize them after each modification. In this paper, we propose an Incremental Genetic Algorithm (IGA) to reduce the time needed to reoptimize modified problems. The idea of IGA is simple and leads to useful results. IGA is similar to CGA except that it starts with an initial population that contains chromosomes saved from the CGA run for the initial problem version (prior to modifying it). These chromosomes are best feasible and best infeasible chromosomes to which we apply two techniques in order to ensure sufficient diversity within them. To validate the proposed approach, we consider three problems: Optimal regression software testing, general optimization, and exam scheduling. The empirical results obtained by applying IGA to the three optimization problems show that IGA requires a smaller number of generations than those of a CGA to find a solution. In addition, the quality of the solutions produced by IGA is comparable to those of CGA.