Multiobjective Evolutionary Algorithms: Classifications, Analyses and New Innovations


Abstract

Although computational techniques for solving Multiobjective Optimization Problems (MOPs) have been available for many years, the recent application of Evolutionary Algorithms (EAs) to such problems provides a vehicle with which to solve very large scale MOPs. This research organizes, presents, and analyzes contemporary Multiobjective Evolutionary Algorithm (MOEA) research and associated MOPs. Under the umbrella of "a priori", progressive, and "a posteriori" algorithms, all known MOEAs proposed in the literature are classified and cataloged. The classification also incorporates detailed algorithmic characteristics, such as objective aggregation, interactive methods, sampling, ranking, and niching. Using a consistent MOEA terminology and notation, each cited MOEAs' key factors are presented in tabular form for ease of MOEA identification and selection. This effort currently classifies 218 distinct MOEA research efforts and applications (representing 272 separate references). A detailed quantitative and qualitative MOEA analysis is presented. The classified efforts provide a basis for conclusions about various algorithmic techniques, fitness functions, gene representations, and the problem domains within which MOEAs are applied. On a qualitative level MOEA ``state of the art'' is discussed, addressing topics such as MOEA characteristics, theory, additional populations, complexity, and well-engineered MOEA implementations. This research also extends the traditional notion of "building blocks" to the MOP domain in an effort to develop more effective and efficient MOEAs. An innovative extension of an existing building block-based EA to the MOP domain (named the MOMGA), and the engineering design decisions made during its construction are presented. The MOEA community's limited de facto test suite contains various functions, many of whose origins and rationale for use are unknown. Thus, example MOPs from the current MOEA literature are presented in tabular form and classified based upon problem domain genotype and phenotype characteristics; these include connectivity, disjointness, concave or convex shape, constraints, and symmetry. Using general test suite guidelines, appropriate MOEA test function suites are generated based upon MOP characteristics and applicable MOEA theory. Few efforts quantitatively measure MOEA performance; fewer still compare MOEA results to MOPs with known optima. Using the developed MOEA test function suite, an experimental methodology incorporating a solution database and appropriate test suite metrics is offered as a proposed evaluation framework allowing absolute comparisons of specific MOEA approaches. This framework is then used in experiments with three well-known MOEAs and the MOMGA, examining their performance in regard to test MOPs. Experimental results, their statistical analyses, and other germane observations are presented. The MOMGA is shown to be at least as effective as other MOEAs tested and often more so. Taken together, this document's classifications, analyses, and new innovations present a complete, contemporary view of current MOEA ``state of the art'' and possible future research. Researchers with basic EA knowledge may also use part of it as a largely self-contained introduction to MOEAs.