應用演算法結合數學規劃求解 多目標問題

Apply Algorithm with Mathematical Planning Optimization to Multi-Objective Problem

林煌諭(Huang-Yu, Lin)

指導教授 ： 陳育欣

中原大學/電機資訊學院/工業與系統工程研究所/碩士(2017年)

https://doi.org/10.6840/cycu201700762

摘要

啟發式演算法從1960年代發展至今已有50餘年的歷史，對於現今NP-hard問題有著重要的貢獻，啟發式演算法有著在時限內可以得到良好不錯的解，但隨著科技的發展與進步，計算機的處理器功能已然越見強大，而人類所面對問題再也不是一個單一問題，而是有著許多矛盾與關連的問題，其答案也不再是單一選擇而是多重選擇，然而演算法雖然已有多目標演算法，求解方式卻缺乏有效的求解策略。

隨著數學方法的進步，多目標問題得以有更多系統化解決方式，然而數學方法需要龐大的時間計算與處理，面對非線性問題時，容易受到轉換上的限制，而啟發式演算法雖然易於處理不同框架的問題，也能夠在限定的時間內得到良好的答案，但同時也缺乏系統化的方式解決問題。

本研究希望透過數學方法的啟發，建構全新多目標啟發式演算法，使演算法透過分治法(divide and conquer)更有系統化將問題分成多個階段與多個區域求解非支配解，最後再將這些非支配解合併起來，提高演算法搜尋能力，透過柏拉圖最佳解的概念求解多目標二次分配問題，並以學界已知並具有指標性的表現指標來評量演算法表現與狀態。

關鍵字

多目標 ； 二次分配問題 ； 柏拉圖最佳解 ； 蟻群演算法 ； 禁忌搜尋演算法

並列摘要

The Metaheuristics has been developing for more than 50 years since the 1960s, made important contribution to NP-hard problem. The heuristic algorithm has a good solution in limited time but human face of the problem is no longer a single problem, but with many contradictions and related issues, the answer is no longer a single choice but multiple choice, although algorithm find the way to resolve multi-objective problem, it is not effective method.

With the advance of mathematical methods, multi-objective problem is resolved by Systematic method. But mathematical methods need enormous time to resolve and has incompatibility with nonlinear programming. While heuristic algorithms are easy to deal with different frameworks, they can also get a good answer within a limited time, but at the same time lack a systematic way to solve the problem.

This study enlightened by mathematical methods to construct a new multi-objective metaheuristics, the algorithm can divide the problem into multiple stages and regions by divide and conquer systematically and combine these solutions for improve the search ability of the algorithm. Through the concept of Pareto optimal solution to resolve multi-objective quadratic assignment problem and measured algorithm’s state and performance by the generally acknowledged performance indicators in Academics.

Keyword: multi-objective, quadratic assignment problem, Pareto optimal solution, Ant Colony Optimization, Tabu Search

並列關鍵字

multi-objective ； quadratic assignment problem ； Pareto optimal solution, Ant Colony Optimization ； Tabu Search

參考文獻

Azevedo, C. R. B., & Araujo, A. F. R. (2011). Correlation between diversity and hypervolume in evolutionary multiobjective optimization. 2743-2750. doi:10.1109/cec.2011.5949962

Bringmann, K., & Friedrich, T. (2013). Approximation quality of the hypervolume indicator. Artificial Intelligence, 195, 265-290. doi:http://dx.doi.org/10.1016/j.artint.2012.09.005

Bruengger, A., Marzetta, A., Clausen, J., & Perregaard, M. (1996). .

Eleyan, H. M. (2015). .

Hadley, S. W., Rendl, F., & Wolkowicz, H. (1992). A new lower bound via projection for the quadratic assignment problem. Mathematics of Operations Research, 17(3), 727-739. doi:10.1287/moor.17.3.727