(3.238.173.209) 您好!臺灣時間:2021/05/12 14:05
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:鐘聖堯
研究生(外文):Chung, Sheng-Yao
論文名稱:使用群聚分群演算法和演化式計算同時搜尋連結關係與最佳解
論文名稱(外文):Online Linkage Discovery Using Affinity Propagation
指導教授:丁川康丁川康引用關係
指導教授(外文):Ting, Chuan-Kang
口試委員:陳穎平蔣宗哲
口試委員(外文):Cheng, Ying-PingChiang, Tsung-Che
口試日期:2011-07-05
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:英文
論文頁數:54
中文關鍵詞:基因演算法基因連結關係
外文關鍵詞:Genetic algorithmlinkage identification
相關次數:
  • 被引用被引用:0
  • 點閱點閱:258
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:13
  • 收藏至我的研究室書目清單書目收藏:0
Genetic algorithm is widely used to solve the optimization problem. The success of GA can attribute to the tight building BBs which are generated in the evolutionary process, but tight building BBs are not always formed for all problems, especially on GA-hard problems. Therefore, our goal is to find the linkage between variables and bind them to form BBs. This study proposed the method that combines GA, similarity measure and clustering algorithm for linkage identification. The genes with dependency would be bound together to form BBs. The clustering algorithm is used to group genes according to similarity measure. Each group is taken as a BB. This research adopts affinity propagation (AP) to deal with clustering problem. The input information, for the AP, comes from similarity measure. Then GA evolves the better solution and BBs simultaneously.

Experimental results show that evolving BBs and solutions together can reduce the computational costs. However, it uses more population. Separately identifying BBs and exploring solutions will confront with a problem which is how to determine that the accuracy of BBs, without any given information, is enough to enter into the next step. As a whole, evolving BBs and solutions together has good performance and saves the parameter setting issue.
Contents 2
List of Figures 4
List of Tables 6
1 Introduction 7
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1 Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1.1 Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.1.1.2 GA-hard problem . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.1.2 Competent Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1.3 Entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.1.4 Clustering Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.2 Objective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 Organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Related Work 16
3 Proposed Method 19
3.1 Three Main Components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Proposed Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.1 GALD1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2.2 GALD2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2.3 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.3.1 Adaptive mutation . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2.3.2 BB-wise crossover . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 Similarity Metric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2CONTENTS 3
3.3.1 Similarity Matrix Construction (SMC) . . . . . . . . . . . . . . . . . . . 23
3.3.2 Mutual Information (MI) . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3.3.3 Differential Mutual Complement (DMC) . . . . . . . . . . . . . . . . . . 24
3.3.4 Distance Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Affinity Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4.1 Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4.2 Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4.3 Responsibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.4 Availability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4.5 Update Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.4.6 Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4 Experimental Results 30
4.1 Test Problem and Parameter Setting . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1.1 Test Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1.2 Parameter Setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.2 Analysis and Discussion of Experiments . . . . . . . . . . . . . . . . . . . . . . . 32
4.2.1 Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2.2 Analysis of Mutation Rate . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.2.3 Performance Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2.3.1 Numerical Optimization Problem . . . . . . . . . . . . . . . . 35
4.2.3.2 Combinatorial Optimization Problem . . . . . . . . . . . . . . 36
4.2.4 Pros and Cons of GALD1 and GALD2 . . . . . . . . . . . . . . . . . . 37
4.2.5 Performance Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2.5.1 Comparison with DSMGA . . . . . . . . . . . . . . . . . . . . 38
4.2.6 Costs for BBs Identification and Solution Exploration . . . . . . . . . . 42
4.2.7 Turn Point Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2.8 Verification on Nonlinear Functions . . . . . . . . . . . . . . . . . . . . . 45
5 Conclusion and Future Work 47
Bibliography 49
A Trap3 with k BBs 52
B Trap-k with 30BBs 54
[1] Chatchawit Aporntewan and Prabhas Chongstitvatana. Chi-square matrix: An approach for
building-block identification. In Michael J. Maher, editor, ASIAN, volume 3321 of Lecture Notes
in Computer Science, pages 63–77. Springer, 2004.
[2] Chatchawit Aporntewan and Prabhas Chongstitvatana. Building-block identification by simul-
taneity matrix. Soft Comput, 11(6):541–548, 2007.
[3] Ying-Ping Chen, Wen-Chih Peng, and Ming chung Jian. Particle swarm optimization with
recombination and dynamic linkage discovery. IEEE Transactions on Systems, Man, and Cy-
bernetics, Part B, 37(6):1460–1470, 2007.
[4] Chung-Yao Chuang and Ying ping Chen. Likage identification by perturbation and decision
tree induction. In IEEE Congress on Evolutionary Computation, pages 357–363. IEEE, 2007.
[5] Thyago S. P. C. Duque, David E. Goldberg, and Kumara Sastry. Enhancing the efficiency of
the ECGA. In Parallel Problem Solving from Nature – (10th PPSN’08), volume 5199 of Lecture
Notes in Computer Science (LNCS), pages 165–174. Springer-Verlag (New York), Dortmund,
Germany, 2008.
[6] Leonardo Emmendorfer and Aurora Pozo. A clustering-based approach for linkage learning
applied to multimodal optimization. In Linkage in Evolutionary Computation, pages 225–248.
Springer-Verlag, Berlin Heidelberg, 2008.
[7] Leonardo R. Emmendorfer and Aurora Pozo. Effective linkage learning using low-order statistics
and clustering. CoRR, abs/0710.2782, 2007. informal publication.
[8] Kai-Chun Fan, Jui-Ting Lee, Tian-Li Yu, and Tsung-Yu Ho. Interaction-detection metric with
differential mutual complement for dependency structure matrix genetic algorithm. In IEEE
Congress on Evolutionary Computation, pages 1–8. IEEE, 2010.
49BIBLIOGRAPHY 50
[9] Brendan J. Frey and Delbert Dueck. Clustering by passing messages between data points.
Science, 315:2007, 2007.
[10] David E. Goldberg. The design of innovation: Lessons ffom genetic algorithms, lessons for the
real world. Technical report, Illinois Genetic Algorithms Laboratory, Department of General
Engineering, University of Illions at Urbana-Champaign, 1998.
[11] Georges R. Harik and David E. Goldberg. Learning Linkage. Morgan Kaufmann, San Mateo,
CA, 1997.
[12] Georges R. Harik, Fernando G. Lobo, and Kumara Sastry. Linkage learning via probabilis-
tic modeling in the extended compact genetic algorithm (ECGA). In Scalable Optimization
via Probabilistic Modeling, volume 33 of Studies in Computational Intelligence, pages 39–61.
Springer, 2006.
[13] Ping-Chu Hung and Ying-Ping Chen. iECGA: integer extended compact genetic algorithm. In
GECCO, pages 1415–1416. ACM, 2006.
[14] Zhenhua Li and Erik D. Goodman. Learning building block structure from crossover failure. In
GECCO, pages 1280–1287. ACM, 2007.
[15] Cláudio F. Lima, Carlos Fernandes, and Fernando G. Lobo. Investigating restricted tournament
replacement in ECGA for non-stationary environments. In GECCO, pages 439–446. ACM, 2008.
[16] Fernando G. Lobo, Kalyanmoy Deb, David E. Goldberg, Georges R. Harik, and Liwei Wang.
Compressed introns in a linkage learning genetic algorithm. In Genetic Programming 1998:
Proceedings of the Third Annual Conference, pages 551–558, University of Wisconsin, Madison,
Wisconsin, USA, 1998. Morgan Kaufmann.
[17] Masaharu Munetomo and David E. Goldberg. Identifying linkage groups by nonlinearity/non-
monotonicity detection. In Proceedings of the Genetic and Evolutionary Computation Confer-
ence, volume 1, pages 433–440, Orlando, Florida, USA, 1999. Morgan Kaufmann.
[18] Martin Pelikan and David E. Goldberg. Hierarchical bayesian optimization algorithm. In
Scalable Optimization via Probabilistic Modeling, volume 33 of Studies in Computational Intel-
ligence, pages 63–90. Springer, 2006.
[19] Martin Pelikan, David E. Goldberg, and Erick Cantú-Paz. Bayesian optimization algorithm,
population sizing, and time to convergence. IlliGAL Report No. 2000001, Illinois Genetic
Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 2000.BIBLIOGRAPHY 51
[20] Ying ping Chen, Chung-Yao Chuang, and Yuan-Wei Huang. Inductive linkage identification on
building blocks of different sizes and types. International Journal of Systems Science, 2011.
[21] Ying ping Chen and David E. Goldberg. Introducing start expression genes to the linkage
learning genetic algorithm. Lecture Notes in Computer Science, 2439:351–360, 2002.
[22] Kumara Sastry and David E. Goldberg. Designing competent mutation operators via proba-
bilistic model building of neighborhoods. CoRR, cs.NE/0405064, 2004. informal publication.
[23] Masaru Tezuka, Masaharu Munetomo, and Kiyoshi Akama. Linkage identification by nonlin-
earity check for real-coded genetic algorithms. In Genetic and Evolutionary Computation –
GECCO-2004, Part II, volume 3103 of Lecture Notes in Computer Science, pages 222–233,
Seattle, WA, USA, 26-30 June 2004. Springer-Verlag.
[24] Miwako Tsuji, Masaharu Munetomo, and Kiyoshi Akama. Modeling dependencies of loci with
string classification according to fitness differences. In Genetic and Evolutionary Computation
– GECCO-2004, Part II, volume 3103 of Lecture Notes in Computer Science, pages 246–257,
Seattle, WA, USA, 26-30 June 2004. Springer-Verlag.
[25] Yuan wei Huang and Ying ping Chen. Detecting general problem structures with inductive
linkage identification. In International Conference on Technologies and Applications of Artificial
Intelligence (TAAI), pages 508 – 515, 2010.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔