Alternative Techniques to Handle Constraints in Evolutionary Optimization.
Computer Science Section, Electrical Eng. Department.
Defended on December 7th, 2004
Adviser: Dr. Carlos A. Coello Coello
CINVESTAV-IPN, Computer Science Section, Electrical Eng. Department.
In this dissertation, a study about constraint handling in evolutionary algorithms is presented. This research has led to five main contributions: (1) A study about exploring the capabilities of using multiobjective concepts to handle constraints in global optimization using four representative approaches. The aim of this study was to make unnecessary the use of a penalty function to handle constraints in an evolutionary algorithm. Based on the results obtained, (2) we proposed a novel and competitive approach to solve constrained problems using an evolutionary algorithm (an evolution strategy in our case) which does not require the use of a penalty function. Instead, it is based on handling the objective function and the constraints of the problems separately. The approach also uses a simple diversity mechanism based on allowing infeasible solutions close to the feasible region and with a good value of the objective function to remain in the population. A simple feasibility-based comparison mechanism is adopted to guide the process towards the feasible region of the search space. Also, the initial stepsize of the evolution strategy is reduced in order to perform a finer search and a combined (discrete/intermediate) panmictic recombination technique improves its exploitation capabilities. We performed experiments in order to know which of those mechanisms (diversity mechanism, fine mutation movements and a combined recombination) was the main responsible for the good performance of the algorithm. This approach was statistically compared against state-of-the-art algorithms using well-known benchmark problems. Furthermore, (3) we performed some statistical analysis that allows to understand better the behavior of the proposed approach. Such analysis was based on the use of three performance measures related to how fast the feasible region is reached, to evaluate how is the progress once inside the feasible region and to how useful is a diversity mechanism to maintain or generate good infeasible solutions. We also performed a study to analyze the sensitivity of our approach to its parameters by means of an analysis of variance and we suggested values derived from such an analysis. In addition, (4) we performed an empirical study which aims to identify the main features that make a constrained problem difficult to solve by our proposed evolutionary algorithm. Finally, based on previous theoretical studies found in the literature, (5) we mathematically proved the global convergence of our proposed algorithm.