The property analysis of evolutionary algorithms applied to spanning tree problems

被引：0
作者：
Sang-Moon Soak
Moongu Jeon
机构：
[1] KIPO,Information Examination Team
[2] Gwangju Institute of Science and Technology,Department of Information and Communications
来源：
Applied Intelligence | 2010年 / 32卷
关键词：
Evolutionary algorithms; Genetic encoding method; Property analysis; Constrained spanning tree problems;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The search behavior of an evolutionary algorithm depends on the interactions between the encoding that represents candidate solutions to the target problem and the operators that act on that encoding. In this paper, we focus on analyzing some properties such as locality, heritability, population diversity and searching behavior of various decoder-based evolutionary algorithm (EA) frameworks using different encodings, decoders and genetic operators for spanning tree based optimization problems. Although debate still continues on how and why EAs work well, many researchers have observed that EAs perform well when its encoding and operators exhibit good locality, heritability and diversity properties.
引用
收藏
页码：96 / 121
页数：25
相关论文
共 37 条
[1]  
Bean JC(1994)Genetic algorithms and random keys for sequencing and optimization ORSA J Comput 6 154-160
[2]  
Chou H(2001)Genetic algorithms for communications network design-an empirical study of the factors that influence performance IEEE Trans Evol Comput 5 236-249
[3]  
Premkumar G(1998)A genetic algorithm for the multidimensional knapsack problem J Heuristics 4 63-86
[4]  
Chu CH(2001)Comparison of algorithms for the DC-MST J Heuristics 7 587-611
[5]  
Chu PC(2000)Fitness landscapes, memetic algorithms, and greedy operators for graph bipartitioning Evol Comput 8 61-91
[6]  
Beasley JE(1995)An approach to a problem in network design using genetic algorithms Networks 26 151-163
[7]  
Krishnamoorthy M(2006)From the dandelion code to the rainbow code: a class of bijective spanning tree representations with linear complexity and bounded locality IEEE Trans Evol Comput 10 108-123
[8]  
Ernst A(1957)Shortest connection networks and some generalisations Bell Syst Tech J 36 1389-1401
[9]  
Sharaiha Y(2005)Empirical analysis of locality, heritability and heuristic bias in evolutionary algorithms: a case study for the multidimensional knapsack problem Evol Comput 13 441-475
[10]  
Merz P(2003)Edge-sets: an effective evolutionary coding of spanning trees IEEE Trans Evol Comput 7 225-239
1234