线性加权编码遗传算法局部搜索能力分析.pdf

线性加权编码遗传算法局部搜索能力分析*
莫鸿强1 Jin Bae PARK2 Young-Hoon JOO 3 李向阳1

(1华南理工大学自动化科学与工程学院·广州,510641)
(2 Dept. of Electrical and Electronic Eng., Yonsei Univ., Seoul, Korea)
(3 School of Electronic and Information Eng., Kunsan Univ., Kunsan, Korea)

摘要:根据模式定理,遗传算法的编码应该提供更多的低阶高适应度模式以便加速搜索过程。而“没有
免费午餐定理”表明,很可能不存在通用高效的编码方法。本文以一阶模式适应度为指标从两方面讨论
该问题。一方面分别针对二次函数、多周期函数,分析了线性加权编码遗传算法在搜索最优值时生成一
阶积木块的能力。结果表明,为保证计算精度,无论加权值如何变化,总有相当部分基因座上无法生成
一阶积木块,因而在对应的搜索子空间中搜索随机性强而效率低。另一方面,若要求在所有基因座上都
能生成一阶积木块,则函数曲线呈“针”状,搜索空间中绝大多数个体适应度都很低,不利于通过选择
确定有效的搜索方向而导致搜索效率低下。本文结果在一定程度上反映了线性加权编码在遗传算法局部
搜索方面的局限性。
关键词:遗传算法;局部搜索;线性加权编码;积木块


On the Local-Search Efficiency of Linear-Weighted-Coded
ic Algorithms
Hong-qiang MO1 Jin-Bae PARK2 Young-Hoon JOO3 Xiang-yang LI1

(1Department of Automatic Control Engineering, South China University of Technology, Guangzhou)
(2 Dept. of Electrical and Electronic Eng., Yonsei Univ., Seoul, Korea)
(3 School of Electronic and Information Eng., Kunsan Univ., Kunsan, Korea)

Abstract: Abstract: According to Schema Theorem, the encoding of a ic algorithm should provide more
highly fit low-order schemata so as to accelerate the search. However, the "No Free Lunch Theorems" implies that,
there would be no encoding with high efficiency as well as generality. In this paper, the Local-Search Efficiency of
Linear-Weighted-Coded ic Algorithms is analyzed in two folds with the fitness of order-1 schema as
measurement of encoding efficiency. The first fold is the ability of a Linear-Weighted-Coded ic Algorithm to
generate highly fit order-1 schemata, ., order-1 building blocks, when it is applied to the quadratic functions and
multiple periodical functions. It is showed that, for the sake of accuracy, there are always considerable loci on which
no order-1 building blocks can be generated, no matter what the weights of the encoding are. As a result, the
search in the corresponding sub-spaces are highly random and therefore