An Evolutionary Approach to Multi-Objective Optimization Problems

Abstract

Multi-objective Optimization Problems (MOPs) are the processes of exploiting solutions to satisfy a set of objectives. Difficulties arise as there usually exist several objectives which are incommensurable or competing against each other. In consequence, for these problems there is no single optimal solution, but rather a set of alternatives to which no other solutions are superior in all the objectives simultaneously. These alternatives are known as Pareto-optimal solutions. In recent years, an ever-growing trend in solving MOPs is to exploit diversified and comprehensive Pareto optima which can constitute a complete knowledge base to meet various requirements. In such applications, Evolutionary Algorithms (EAs) have been widely adopted as powerful tools because of their population-based search approach and strong global optimization capability. This thesis focuses on designing effective and efficient Evolutionary Algorithms for Multi-objective Optimization Problems. Our efforts are two-fold: (1) designing sequential Multi-Objective EAs with sound theoretical basis, and (2) designing parallel Multi-Objective EAs with strong scalability and speedup capability. The sequential algorithms (Chapters 5 and 8) are designed with emphases on both their Pareto optimization capability and, equally important, their stability concerns. For this purpose, several techniques (say, the annealing-like controller and Coverage Quotient) are contrived. These techniques can one on hand enhance the algorithms' exploration strength and on the other hand ensure their persistent performance. In addition, on the basis of these techniques, a series of theories are established, which rigorously prove the convergence properties of these algorithms. The parallel algorithms (Chapters 6 and 7) achieve strong scalability and speedup capability by their full asynchronous collaboration strategies. In these algorithms, a two-level asynchronous adjustment operation in conjunction with a concise information exchange operation can provide precise and flexible harmonization amongst a set of distributed sub-processes, which in turn leads to superior scalability and speedup capability. The proposed algorithms are compared with some state-of-the-art Multi-Objective EAs on a variety of benchmark problems. The comparison results show the success of our algorithms. Lastly, it should be noted that despite originally designed for the multi-objective optimization purpose, some techniques presented in this thesis (say, the annealing-like controller and two-level adjustment operations) are not limited to the MOP domain. Instead, they are general-purpose operations which are applicable to other EA applications with minor or even without modifications.