遺傳演算為基並應用目標隨機更替策略的多目標規劃方法

A Genetic Algorithm and Objective Randomly Switched Strategy Based Multi-Objective Programming Method

鍾禮駿(Li-Chun Chung)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.00112

摘要

本論文針對求解多目標規劃問題（Multi-Objective Problem）的啟發式演算法進行研究，提出以目標函數隨機更替策略及遺傳演算法為基的多目標規劃方法。遺傳演化過程就所有的目標函數中隨機選取單一個函數進行適存值求算。演化過程儲存並更新求解過程產生的非臣服解集合。演算結束時此解集合即為多目標規劃的類柏拉圖解集合。每代次演化時，先區分出非臣服解，再與已儲存的非臣服解集合的解進行臣服與否比對。剔除遭凌駕的解，並加入新非臣服解。為了維持群體的多樣性及增加求解的柏拉圖解個數，本研究所提出內外插法染色體更新策略維持演算中群體內的多樣性。本研究並根據所提出的方法實作一套求解系統，對五組測試問題驗證其可行性。為比較不同方法的優劣，本研究並提示四種量化的效能評估指標。五組測試問題在所有指標的評估下，本研究提示的方法皆優於其他求解策略下的多目標遺傳演算法。

關鍵字

加權法 ； 非臣服解 ； 柏拉圖解 ； 多目標規劃 ； 遺傳演算法

並列摘要

This thesis proposes an objective randomly switched strategy and genetic algorithms embedded method to solve multi-objective problems. Within each evolution procedure, the method randomly selects one objective function, from the problem, to compute the fitness for the genetic algorithm. Non-dominated solutions obtained from each evolution generation are stored and kept in a non-dominated solution set. In each evolution generation, domination competition between solutions is carried out within the population first and then against the stored non-dominated solution set. At first, Non-dominated solutions are identified and extracted from the population by carrying out a domination examination. The solutions from the population are then one by one competed with the solutions in the non-dominated set. Solutions in the set that are dominated by the solution from the population are discarded first. Then, the solutions from the population can be added to the non-dominated solution set only when they are not dominated by any solution in the set. To maintain population diversity, this methods replaces partial chromosomes with new chromosomes generated by inter- and extrapolation between pairs of solutions in the non-dominated solution set. This method is implemented in a software system, and other traditional methods are developed in the system as well, to facilitated results comparisons. Four brand-new evaluation factors for different solving methods are proposed and defined in this thesis. Five numerical examples are testes against our method and other methods. Results show that our method in general can obtain more and better non-dominated solutions than others.

並列關鍵字

Pareto Solution ； Multi-Objective Planning ； Non-dominated Solution ； Genetic Algorithm

參考文獻

1. Alexandre, H.F., Dias and Jõao A. de Vasconcelos, 2002, “Multiobjective Genetic Algorithms Appliedto Solve Optimization Problems,” IEEE Transactions on Magnetics, Vol. 38, No. 2, 1133-1136.

2. Charnes, A., and Cooper, W.W., 1961, Management Models and Ind-ustrial Applications of Linear Programming, Wiley, New York.

5. David, A., Van, V., and Gary, B.L., 1999, “Multi-Objective Evolutionary Algorithm Test Suites,”.

7. Deb, K., Zitzler, E., Thiele, L., Laumanns, M., 2002, “Scalable Multi-Objective Optimization Test Problem,” IEEE.

10. Goldberg, D., 1989, Genetic Algorithms in Search Optimization and Machine Learning, Addison-Wesley.