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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：20

、訪客IP：18.217.194.39

姓名

林耀堂(Yao-Tang Lin) 查詢紙本館藏

畢業系所

資訊管理學系

論文名稱

以關係基因演算法為基礎之一般性架構解決包含限制處理之集合切割問題
(A General Framework of Relation-based Genetic Algorithms for Set Partitioning Problems with Constraint Handling)

相關論文

★ 零售業商業智慧之探討	★ 有線電話通話異常偵測系統之建置
★ 資料探勘技術運用於在學成績與學測成果分析 -以高職餐飲管理科為例	★ 利用資料採礦技術提昇財富管理效益 -以個案銀行為主
★ 晶圓製造良率模式之評比與分析－以國內某DRAM廠為例	★ 商業智慧分析運用於學生成績之研究
★ 運用資料探勘技術建構國小高年級學生學業成就之預測模式	★ 應用資料探勘技術建立機車貸款風險評估模式之研究－以A公司為例
★ 績效指標評估研究應用於提升研發設計品質保證	★ 基於文字履歷及人格特質應用機械學習改善錄用品質
★ 關聯式資料庫之廣義知識探勘	★ 考量屬性值取得延遲的決策樹建構
★ 從序列資料中找尋偏好圖的方法 - 應用於群體排名問題	★ 利用分割式分群演算法找共識群解群體決策問題
★ 以新奇的方法有序共識群應用於群體決策問題	★ 利用社群網路中的互動資訊進行社群探勘

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

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

摘要(英)

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)

論文目次

1 Introduction 1
1.1 Motivations 1
1.2 Research Objectives 2
1.3 Expected Contributions 3
1.4 Organization of the Dissertation 5
2 Set Partitioning Problem 6
2.1 Problem Description and General Constraint 6
2.2 Classic Set Partitioning Problems 7
2.2.1 Partition Targeting 7
2.2.2 Equal Piles and Similar Piles 7
2.2.3 Bin Packing 8
2.2.4 Map Coloring and Graph Coloring 8
2.3 Specific Constraints and Classification 9
2.4 A General Form of SPP 12
2.5 Previous Works for Solving SPPs 13
3 Previous GAs for Solving SPPs 14
3.1 GA with Candidate Representation 14
3.1.1 Candidate Encoding 14
3.1.2 Drawbacks of Candidate Representation 15
3.2 GA with Objected-oriented Representations 16
3.2.1 GA with Membership Encoding 16
3.2.2 Permutation Encoding 17
3.2.3 Drawbacks of Objected-oriented Representations 17
3.3 GA with Group-oriented Representation 20
3.3.1 Grouping Encoding 21
3.3.2 Crossover 21
3.3.3 Mutation 23
3.3.4 Inversion 24
3.3.5 Drawbacks of Group-oriented Representation 25
4 Relational Genetic Algorithms 26
4.1 Introduction and Conceptual Framework 26
4.2 Phenotypic RGA 30
4.2.1 Set-based Abstract Representation 30
4.2.2 Phenotypic Genetic Operators 31
4.2.2.1 Crossover 31
4.2.2.2 Mutation 33
4.3 Genotypic RGA 34
4.3.1 Relational Encoding 34
4.3.2 Genotypic Genetic Operators 35
4.3.2.1 Crossover 36
4.3.2.2 Mutation 39
4.4 Constraint Handling in RGAs 39
4.4.1 Constraint Satisfaction in Artificial Intelligence 40
4.4.2 Constraint Handling Schemes in GAs 40
4.4.3 Constraint Handling Schemes in Genotypic RGA 41
4.5 Qualitative Evaluations and Comparisons 43
4.6 Simulated GGA 44
5 Experiments for Solving Classic SPPs 47
5.1 Experiment 1: Partition Targeting 48
5.2 Experiment 2: Equal/Similar Piles 49
5.3 Experiment 3: Bin Packing 51
5.4 Experiment 4: Map/Graph Coloring 53
5.5 Summary and Discussion of Experiment Results 55
6 An Extended Application: Partitioned Portfolio Insurance Strategy 58
6.1 Motivations and Objectives 58
6.2 Traditional Portfolio Insurance Strategy 59
6.2.1 Static Approaches 59
6.2.2 Dynamic Approaches 60
6.2.3 Bottlenecks of Traditional PI 61
6.3 Idea of PPI strategy 62
6.3.1 A Simplified Model for PI and PPI 62
6.3.2 Portfolio Partitioning Problem 67
6.4 Experiment Results 68
6.5 Brief Summary 70
7 Conclusion and Future Works 71
7.1 Conclusion 71
7.2 Research Contributions 72
7.3 Future Works 73
Reference 74

參考文獻

[1] Abken, P.A., “An Introduction to Portfolio Insurance,” Economic Review, Federal Reserve Bank of Atlanta, pp. 2-25, Nov 1987.
[2] Appel, K. and W. Haaken, “Every Map is Four-colourable I: Discharging,” Illinois J. Math 21, pp. 429-490, 1997.
[3] Appel, K. and W. Haaken, “Every Map is Four-colourable II: reducibility,” Illinois J. Math 21, pp. 491-567, 1997.
[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.
[9] Chen, J. S., Y. T. Lin, and L. Y. Chen, “A Relation-Based Genetic Algorithm for Partitioning Problems with Applications,” Lecture Notes in Artificial Intelligence (IEA/ AIE 2007), 4570, pp. 217 - 226, 2007.
[10] Chiang, W-C., and P. Kouvelis, “An improved tabu search heuristic for solving facility layout design problem,” International Journal of Production Research, 34(9), pp. 2565-2585, 1996.
[11] Chu, P. C. and J. E. Beasley, “Constraint Handling in Genetic Algorithms: The Set Partitioning Problem,” Journal of Heuristics, 11, pp. 323-357, 1998.
[12] Dechter, R. and Pearl, J., “Network-based heuristics for constraint-satisfaction problems,” Aartificial Intelligence, 34, pp. 1-38, 1988.
[13] Eiben, A. E., J. K. van der Hauw, and J. I. van Hemert, “Graph Coloring with Adaptive Evolutionary Algorithms,” Journal of Heuristics, 4(1), pp. 25-46, 1998.
[14] Estep, T. and M. Kritzman, “TIPP: Insurance without Complexity,” Journal of Portfolio Management, 14(4), pp. 38-42, Summer 1988.
[15] Etzioni, E.S., “Rebalance Disciplines for Portfolio Insurance,” Journal of Portfolio Management, 13(1), pp. 59-62, Fall 1986.
[16] Falkenauer, E., “Solving Equal Piles with the Grouping Genetic Algorithm,” Proc. 6th Intnl. Conf. on Genetic Algorithms, ed. L. J. Eshelman, Morgan Kaufmann, San Francisco, pp. 492-497, 1995.
[17] Falkenauer, E., “The Grouping Genetic Algorithms－Widening The Scope of The GAs,” JORBEL－Belgian Journal of Operations Research, Statistics and Computer Science, 33(1,2), pp. 79-102, 1992.
[18] Freuder, E., “A sufficient condition for backtrack-free search,” J. ACM, 29, pp. 24-32, 1982.
[19] Galinier, P. and J-K. Hao, “Hybrid Evolutionary Algorithms for Graph Coloring,” Journal of Combinatorial Optimization, 3, pp. 379–397, 1999.
[20] Garey, M. R. and D. S. Johnson, “Computers and Intractability－A Guide to the Theory of NP-completeness,” W.H. Freeman, San Francisco, USA, 1979.
[21] Greene, W. A., “Genetic Algorithms for Partitioning Sets,” International Journal on Artificial Intelligence Tools, 10(1&2), pp. 225-241, 2001.
[22] Holland, J., Adaptation in Natural and Artificial System, University of Michigan Press, 1975.
[23] Johnson, D., C. Aragon, L. McGeoch, and C. Schevon, “Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning,” Operations Research, 39(3), pp. 378-406, 1991.
[24] Johnson, D. S. and M. A. Trick (Eds.), in Proceedings of the 2nd DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26, American Mathematical Society, 1996.
[25] Jones, D. R. and M. A. Beltramo, “Solving partitioning problems with genetic algorithms,” Proc. 4th Intnl. Conf. on Genetic Algorithms, eds. K. R. Belew and L. B. Booker,Morgan Kaufmann, San Francisco, pp. 442-449, 1991.
[26] Martello, S. and P. Toth, Knapsack problems. Wiley, Chichester, 1990.
[27] Nadel, B., Tree search and arc consistency in constraint-satisfaction algorithms. In Search in Artificial Intelligence, edited by L. Kanal and V. Kumar, pp. 287–342, 1988 (Springer: New York).
[28] Purdom, P., “Search Rearrangement Backtracking and Polynomial Average Time,” Aartificial Intelligence, 21, 117-133, 1983.
[29] Richardson, J. T., M. R. Palmer, G. Liepins, and M. Hilliard., “Some Guidelines for Genetic Algorithms with Penalty Functions.” In J.D. Schaffer (ed.), Proceedings of the Third International Conference on Genetic Algorithms. Morgan Kaufmann, pp. 191-197, 1989.
[30] Rubinstein, M. and H. E. Leland, “Replicating Options with Positions in Stock and Cash,” Financial Analysts Journal, 37, pp. 63-71, Jul/Aug 1981.
[31] Rubinstein, M., “Alternative Paths to Portfolio Insurance,” Financial Analysts Journal, 41(4), pp. 42-52, 1985.
[32] Smith, A. E. and D. M. Tate., “Genetic Optimization Using a Penalty-Function.” In S. Forrest (ed.), Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, pp. 499-505, 1993.
[33] Smith, D., “Bin Packing with Adaptive Search,” Proceeding of an International Conference on Genetic Algorithms and Their Application, pp. 202-206, 1985.

指導教授

陳彥良、陳稼興
(Yen-Liang Chen、Jiah-Shing Chen)

審核日期

2008-1-21

推文