Theory and Applications of Efficient Multi-objective Evolutionary Algorithms


Abstract

Many real-world optimization problems involve multiple incommensurable and often competent objectives in nature; these problems are known as multi-objective optimization problems (MOOPs). Instead of obtaining a single optimal solution, the ultimate goal of solving MOOPs is to find a complete set of Pareto-optimal solutions. Recently, multi-objective evolutionary algorithms (MOEAs) have been recognized to be well-suited for solving MOOPs because their abilities to exploit and explore multiple solutions in parallel and to find a widespread set of non-dominated solutions in a single run. This dissertation emphasizes on advancing the understanding of MOEAs to design effective and efficient MOEAs. Three major contributions of this dissertation are summarized as follows. First, a quality-time analysis of MOEAs based on schema theorem and building blocks (BBs) hypothesis is developed. Convergence time, first and last hitting time models are constructed for analyzing the performance of MOEAs. Population sizing model is constructed for determining appropriate population sizes. The theoretical results indicate how the convergence time and population size of a MOEA scale up with the problem size, the dissimilarity of Pareto-optimal solutions, and the number of Pareto-optimal solutions of a MOOP. A preliminary theoretical analysis on the convergence time of MOOPs with scale, length and linkage disequilibriums are also investigated. The results demonstrate that disequilibriums between multiple objectives affect the convergence time of MOEAs and may pose difficulties to MOEAs in maintaining the diversity of population. Second, a novel approach to multi-objective evolutionary optimization, intelligent multi-objective evolutionary algorithm IMOEA, is analyzed. IMOEA combines the concept of BBs identification/mixing, elitism and a novel fitness assignment strategy in a unique manner. IMOEA efficiently identify good BBs of parents and then generate good children by taking advantage of the reasoning ability of orthogonal experimental design in selecting the potentially best combination of better levels of factors. Empirical studies of several state-of-the-art MOEAs and IMOEA on well-known multi-objective knapsack problems and test functions show that IMOEA has high performance in solving the foregoing problems. Two real-world applications are conducted using IMOEA: multi-objective production planning of flexible manufacturing systems and multi-objective design of nearest neighbor classifiers. The experimental results demonstrate the efficiency of IMOEA in solving large-scale problems. Finally, an efficiency enhancement technique for MOEAs, fitness inheritance, is proposed to improve the performance of MOEAs. Because computational time of MOEAs are usually bounded by the numbers of function evaluations, the concept of fitness inheritance is to reduce computation costs of MOEAs by inheriting objective function values of offsprings from their parents. The convergence time and population sizing models of MOEAs using fitness inheritance are derived to determine the optimal proportion of fitness inheritance and speed-up of MOEAs using fitness inheritance. Theoretical results are compared with experimental results in two cases: fitness inheritance with/without fitness sharing. The results indicate that fitness inheritance can speed-up the convergence time of MOEAs around 25%. This dissertation presents the following achievements: the theoretical developments that improve our understanding of the effects of problem characteristics on MOEAs; the development of IMOEA that demonstrates the advantage of using BBs identification/mixing; and the development of fitness inheritance to enhance the performance of MOEAs. These developments can be guidelines in designing efficient MOEAs to obtain high-quality solutions. Keywords: Multi-objective optimization, evolutionary algorithms, convergence, population sizing, orthogonal experimental design, intelligent multi-objective evolutionary algorithm, intelligent evolutionary algorithm, flexible manufacturing systems, production planning, data mining, nearest neighbor classifier, fitness inheritance.