Evolutionary Algorithms for Constrained Optimization

Abstract

Most real world optimization problems, and their corresponding models, are complex. This complexity arises from different sources, such as existence of the constraints, function characteristics, and high dimensionality. Evolutionary Algorithms (EAs) and specially Genetic Algorithms (GAs) have proven themselves as efficient optimization techniques over the last two decades; as they have the ability to overcome the drawbacks of conventional optimization methods. Therefore, this thesis addresses the GAs as a solution methodology for solving Constrained Optimization Problems (COPs). In COPs for practical applications, it is more likely that the optimal solution lies on the feasible region boundary. Utilizing this feature, this thesis introduces a new genetic algorithm for solving small-scale COPs. A new ranking and selection scheme is introduced in conjunction with both a new crossover method based on three parents, and a mixed mutation between two currently existing mutation methodologies. A number of well known benchmark problems have been solved and compared with the state of the art algorithms, and the proposed algorithm shows a competitive and even superior performance for some problems. In addition, a detailed parametric analysis is provided to show the individual effect of each of the proposed components. Furthermore, this thesis introduces another algorithm that breaks down the complexity of the constrained optimization process into smaller dimensions. Every sub-component of the algorithm maintains a part of the problem, and the whole problem optimization is treated through a designed communication process. This algorithm deals with a special problem structure, in which the problems are entirely or almost decomposable based on what is called in the literature as a block angular structure. The proposed algorithm decomposes the constraints as well as the chromosomes. It facilitates solving such problems both with and without overlapping variables between the sub-components. Some experiments have been carried out to show how the designed communication process controls the optimization and what the best parameter settings are. Then, the algorithm has been implemented in a parallel environment on a scalable practical test problem and using this shows how the proposed algorithm outperforms the other single population based algorithms in higher dimensions.