以關係基因演算法為基礎之一般性架構解決包含限制處理之集合切割問題

A General Framework of Relation-based Genetic Algorithms for Set Partitioning Problems with Constraint Handling

林耀堂(Yao-Tang Lin)

指導教授 ： 陳彥良 ； 陳稼興

國立中央大學/管理學院/資訊管理學系/博士(2008年)

摘要

集合切割問題之多樣性和其上個別問題之獨特性，使其缺乏可作為單一整合性解決方案的一般性架構。本論文提出一個以基因演算法為基礎之一般性架構，以有效率地解決多種類型的集合切割問題。該架構以創新的關係基因演算法為基礎，並導入一組整合性限制處理機制，以處理多種類型的限制問題。我們採用抽象的集合表示法和關係導向的編碼表示法（關係編碼），並分別設計對應之演化運算，來建構關係基因演算法。關係編碼以等價關係矩陣表示切割，而等價關係矩陣和切割所組成的集合形成一對一且映成的關係。關係編碼消除了在既有之基因表示法上重複性和非法解的問題，並改善了演化搜尋的效率。而重新設計的一般性問題獨立之運算，在演化過程中可不使用和問題相依之經驗法則。此外，關係基因演算法亦允許子集合個數變動，而非限制固定之子集合個數。實驗設計中，我們以關係基因演算法（單點交配、雙點交配、群組交配）分別解決四個擁有不同類別限制之代表性古典集合切割問題。實驗結果顯示，我們所提出之一般性架構和關係基因演算法成功地解決了所有實驗問題，並成功地處理了我們所識別出的所有類型限制問題。最後，我們展示了一組延伸應用，成功地利用關係基因演算法發展出最佳化切割式投資組合保險策略。

關鍵字

切割式投資組合保險策略 ； 關係編碼 ； 等價關係矩陣 ； 關係基因演算法 ； 群組基因演算法 ； 集合切割問題

並列摘要

Set partitioning problems’ (SPPs) plural nature makes them essentially individual problem specific, with various informative information and specific hard constraints in each occasion, and therefore SPPs do not have any general framework to serve as an integrated problem solver. This dissertation proposes a GA-based general framework for solving various classes of SPPs efficiently. The framework is based on new relation-based genetic algorithms named relational genetic algorithms (RGAs) which are generalized from the state-of-the-art grouping genetic algorithm (GGA). This framework also naturally integrates a set of constraint handling schemes into RGAs to handle various classes of hard constraints for SPPs. In our RGAs, a phenotypic set-based abstract representation and a genotypic relation-based representation named relational encoding are adopted, and sets of corresponding genetic operators are redesigned. In genotypic RGA, the relational encoding is represented by the equivalence relation matrix which has a 1-1 and onto correspondence with the collection of all possible partitions. It eliminates the redundancy and infeasibility of previous GA representations, and improves the performance of genetic search. The generalized problem-independent operators that we redesigned manipulate the genes without requiring problem-specific heuristics during the process of evolution. In addition, our RGAs allow the number of subsets to vary, instead of fixing it at a predetermined number. We perform experiments for solving four representative classic SPPs with various classes of hard constraints by RGAs with one-point, two-point and grouping crossovers, respectively. Experiment results show that our proposed general framework works well for solving all tested SPPs and successfully handles all classes of hard constraints that we have identified. We also demonstrate an extended application for developing optimized partitioned portfolio insurance strategies and how to solve the induced portfolio partitioning problem by RGAs.

並列關鍵字

relational genetic algorithm (RGA) ； set partitioning problem (SPP) ； equivalence relation matrix ； partitioned portfolio insurance (PPI) strategy ； relational encoding ； grouping genetic algorithm (GGA)

參考文獻

[4] Bird, R., D. Dennis, and M. Tippett, “A Stop Loss Approach to Portfolio Insurance,” Journal of Portfolio Management, 15(1), pp. 35-40, Fall 1988.

[5] Black, F. and R. Jones, “Simplifying Portfolio Insurance,” Journal of Portfolio Management, 14(1), pp. 48-51, Fall 1987.

[6] Brown, E. C. and R. T. Sumichrast, “Evaluating Performance Advantages of Grouping Genetic Algorithms,” Engineering Applications of Artificial Intelligence, 18, pp. 1-12, 2005.

[7] Bowen, J., O’Grady, P. and Smith, L., “A constraint programming language for life-cycle engineering,” Artificial Intelligence in Engineering, 5, pp. 206–220, 1990.

[8] Chen, J. S., and Y. T. Lin, “A Partitioned Portfolio Insurance Strategy by Relational Genetic Algorithm,” Lecture Notes in Artificial Intelligence (AI 2006), 4304, pp. 857 – 866, 2006.