運用邊界探索方案於遺傳算法求解約束優化問題

A Boundary-Exploration Scheme for Genetic Algorithms to Solve Constrained Optimization Problems

高佑豪(Yu-Hao Kao)

指導教授 ： 于天立

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2021年)

https://doi.org/10.6342/NTU202103280

摘要

為了使用遺傳演算法解決約束優化問題，已經提出了許多不同的方法來處理各種不同的限制，但沒有一種是專門為模型構建遺傳算法設計的。本文首先研究了五種現有的約束處理方法、消除、支配概念、ASCHEA、懲罰和FI-2Pop，將其套用在SGA、hBOA、LT-GOMEA和DSMGA-II，並以其來解決在六個不同的約束優化問題。其中，FI-2Pop以最高的效率找到全局最優值，同時需要最少的函數評估次數。受FI-2Pop的啟發，本文提出了一種用於建模遺傳算法的三群方案，命名為B-3Pop。由於約束優化問題的最優值通常發生在可行空間和不可行空間之間的邊界處，因此保留了第三個種群來探索邊界區域。實證結果表明，B-3Pop在所有六個測試約束優化問題的函數評估次數方面優於上述五種約束處理方法。此外，B-3Pop的適配版本被提出來自動調整第三種群的大小。根據實驗結果，在所有測試問題上，自適應版本比靜態版本需要更少的評估次數。

關鍵字

遺傳演算法 ； 約束優化

並列摘要

In order to solve constrained optimization problems (COPs) with genetic algorithms (GAs), different methods have been proposed to handle constraints, but none of them are specifically designed for model-building genetic algorithms (MBGAs). This thesis firstly investigates five existing constraint-handling
methods, elimination, dominance concept, penalization, adaptive segregational constraint-handling (ASCHEA) method, and feasible-infeasible two-population scheme (FI-2Pop). These five methods are tested on six COPs by applying on simple GA (SGA), hBOA, LTGOMEA, and DSMGA-II. Among the constraint-handling methods, FI-2Pop achieves the highest rate to find the global optimum while requiring fewest function evaluations (FEs). Inspired by FI-2Pop, this thesis proposes a three-population scheme, named B-3Pop, for MBGAs. Since the optima of COPs usually occur at the boundary between feasible and infeasible regions, a third population is maintained to explore the boundary. Empirical results show that B-3Pop outperforms the five constraint-handling methods mentioned above in terms of number of FEs on all six tested COPs. In addition, an adaptive version of B-3Pop is proposed to automatically adjust the size of the third population. Empirically, the adaptive version requires even fewer FEs than the static version on all tested problems.

並列關鍵字

genetic algorithms ； constraint optimization

參考文獻

[1] J. Beasley. An sst-based algorithm for the steiner problem in graphs. Networks,19:1–16, 1989.

[2] J. Beasley. Lagrangean heuristics for location problems. European Journal of Operational Research, 65(3):383–399, 1993.

[3] S. Ben Hamida and M. Schoenauer. Aschea: new results using adaptive segregational constraint handling. InProceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No.02TH8600), volume 1, pages 884–889vol.1, 2002.

[4] P. A. Bosman and D. Thierens. Linkage neighbors, optimal mixing and forced improvements in genetic algorithms. InProceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, GECCO ’12, page 585–592, New York, NY, USA, 2012. Association for Computing Machinery.

[5] K. M. Chandy and T. Lo. The capacitated minimum spanning tree.Networks,3(2):173–181, 1973.