(3.230.143.40) 您好!臺灣時間:2021/04/23 16:36
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林耀堂
研究生(外文):Yao-Tang Lin
論文名稱:以關係基因演算法為基礎之一般性架構解決包含限制處理之集合切割問題
論文名稱(外文):A General Framework of Relation-based Genetic Algorithms for Set Partitioning Problems with Constraint Handling
指導教授:陳彥良陳彥良引用關係陳稼興陳稼興引用關係
指導教授(外文):Yen-Liang ChenJiah-Shing Chen
學位類別:博士
校院名稱:國立中央大學
系所名稱:資訊管理研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:86
中文關鍵詞:切割式投資組合保險策略關係編碼等價關係矩陣關係基因演算法群組基因演算法集合切割問題
外文關鍵詞:relational genetic algorithm (RGA)set partitioning problem (SPP)equivalence relation matrixpartitioned portfolio insurance (PPI) strategyrelational encodinggrouping genetic algorithm (GGA)
相關次數:
  • 被引用被引用:0
  • 點閱點閱:145
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
集合切割問題之多樣性和其上個別問題之獨特性,使其缺乏可作為單一整合性解決方案的一般性架構。本論文提出一個以基因演算法為基礎之一般性架構,以有效率地解決多種類型的集合切割問題。該架構以創新的關係基因演算法為基礎,並導入一組整合性限制處理機制,以處理多種類型的限制問題。我們採用抽象的集合表示法和關係導向的編碼表示法(關係編碼),並分別設計對應之演化運算,來建構關係基因演算法。關係編碼以等價關係矩陣表示切割,而等價關係矩陣和切割所組成的集合形成一對一且映成的關係。關係編碼消除了在既有之基因表示法上重複性和非法解的問題,並改善了演化搜尋的效率。而重新設計的一般性問題獨立之運算,在演化過程中可不使用和問題相依之經驗法則。此外,關係基因演算法亦允許子集合個數變動,而非限制固定之子集合個數。實驗設計中,我們以關係基因演算法(單點交配、雙點交配、群組交配)分別解決四個擁有不同類別限制之代表性古典集合切割問題。實驗結果顯示,我們所提出之一般性架構和關係基因演算法成功地解決了所有實驗問題,並成功地處理了我們所識別出的所有類型限制問題。最後,我們展示了一組延伸應用,成功地利用關係基因演算法發展出最佳化切割式投資組合保險策略。
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.
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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔