利用點距策略發展合作式DE演算法解多目標最佳化問題之研究

A Novel Cooperative Differential Evolution with Distance Ranking Strategy for Multiobjective Optimization

黃玉清(Yu-Qing Huang)

指導教授 ： 范書愷

元智大學/工程學院/工業工程與管理學系/碩士(2009年)

https://doi.org/10.6838/YZU.2009.00015

摘要

多目標最佳化問題普遍存在於生活中，這些問題通常不會只有一個目標，而是多個目標必須同時被進行最佳化處理，而這些目標彼此間通常存在著衝突的特性，除此之外這些目標往往不能合併為單一目標來進行最佳化程序。由於上述特性，因此多目標的解通常不只有一個，而是存在著數個柏拉圖解（Pareto-optimal solutions）。因此，解多目標最佳化問題的要務就是要找出能兼顧收斂與多樣性兩者特性的集群解。然而，這類的問題很難被解決，由於其決策空間（decision space）不能直接對應到目標空間域（objective space），再者決策空間的複雜度通常是未知的，在最近幾年，演化式計算（evolutionary computations）被發現適合解多目標問題。
本研究發展了一個以DE（differential evaluation）為基礎的多目標最佳化演算法。而合作（cooperative）的行為是進化式計算裡使搜尋更有效率的方法之一。本研究透過集群合作（cooperative coevolution）的概念將母體分為兩群，分別執行全域搜尋與區域搜尋（local search）的DE，藉此讓彼此發揮合作搜尋的目的。關於區域搜尋這部份是用本研究所提議的區域搜尋法做搜尋，它能豐富化搜尋能力。收斂性（正確性）和多樣性（均勻性加上延展性）是解決多目標問題最重要的兩項要務，在本研究提出了點距策略（distance ranking strategy）的方式來保持解的多樣性，此外還有一特殊的突變機制於本研究之中提出，以強化演算法搜尋之收斂性。
為了評估本演算法的優劣，本方法與文獻上四個較為著名之多目標最佳化演算法進行比較，且使用數題測試例題為評估範例，經由實驗模擬結果發現，本研究所提方法是個具有高度競爭性的演算法，對於解決複雜型的多目標問題非常有潛力，是解決多目標最佳化問題中非常成功的替代方案。

關鍵字：差分進化法（Differential Evaluation）；多目標最佳化；柏拉圖最佳化；合作式。

關鍵字

差分進化法 (Differential Evaluation) ； 多目標最佳化 ； 柏拉圖最佳化 ； 合作式

並列摘要

Multiobjective optimization is ubiquitous around human lives. This type of optimization involves the simultaneously optimization of multiple noncommensurable and often competing objectives. In single-objective optimization, there exists a global optimum, while in the multiobjective case, no single optimal solution but rather a set of solutions, called the Pareto-optimal solutions exist. Thus, the goal of multiobjective optimization is to generate a set of nondominated solutions as an approximation to the true Pareto-optimal front. However, the majority of problems of this kind are very hard to solve because the decision space can not directly map to the objective space. In addition, the complexity of the decision space is unknown. In recent years, evolutionary computations (ECs) have been recognized to be well suited for multiobjective optimization.
This thesis presents a new algorithm, called “cooperative multiobjective differential evolution” (C-MODE), which allows the differential evolution (DE) algorithm to be capable of dealing with multiobjective optimization problems. The cooperative behavior is a recent trend in evolutionary computation that can help to make the search more efficient. In this thesis, the cooperative concept is incorporated as to enhance the search performance by means of two cooperative subpopulations, which perform the general DE and local search in DE, respectively. To conduct the local search, a unique method is proposed to enrich the exploratory capabilities. The convergence (i.e., accuracy) and diversity (uniformity and extensibility) are the main tasks in solving multiobjective optimization problems. In C-MODE, the distance ranking strategy (DRS) is proposed to maintain diversity. Additionally, a special mutation operator is opted to drive the search toward favorable directions and accelerate the search.
The proposed algorithm is validated using several test functions and metrics taken from the open literature of evolutionary multiobjective optimization. The proposed algorithm is compared against four well-known multiobjective optimizers, SPEA2, NSGAII, PAES and MOPSO. Simulation results indicate that the algorithm is very competitive with the four well-known algorithms and shows great promise in dealing with complicated problems. Thus, C-MODE can be considered a successful alternative to solve multiobjective optimization problems.

Key Words: Differential evolution; Multiobjective optimization; Pareto optimality; Cooperative behavior.

並列關鍵字

Differential evolution ； Multiobjective optimization ； Pareto optimality ； Cooperative behavior

參考文獻

Bäck, T., Hammel, U. and Schwefel, H.-P. (1997). Evolutionary computation: comments on the history and current state. IEEE Transactions on Evolutionary Computation, 1(1), 3-17.

Branke, J. (1999). Memory enhanced evolutionary algorithms for changing optimization problems. In: Congress on Evolutionary Computation (CEC’99), 1875-1882.

Branke, J. and Mostaghim, S. (2006). About selecting the personal best in multi-objective particle swarm pptimization. In: Runarsson, T. P. et al., editors, Proceedings of the Parallel Problem Solving from Nature IX (PPSN IX), Lecture Notes in Computer Science (LNCS), 4193, 523-532. Springer.

Charnes, A. and Cooper, W. W. (1961). Management models and industrial applications of linear programming, vol. I, John Wiley, New York.

Chatterjee, A. and Siarry, P. (2006). Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimization. Computers and Operations Research 33, 859-871.