多种群竞争遗传算法
DOI:10. 13207/j.cn k i . jn w af u. 2005. 04. 035第33卷 第4期西北农林科技大学学报(自然科学版) 2005年4月J o ur. of N o rthw est Sci-T ech Univ. o f Ag ri. a nd Fo r. (Na t. Sci. Ed. )
V ol. 33N o. 4
April 2005
多种群竞争遗传算法及其性能分析
吴养会, 王乃信, 刘瀛洲
(西北农林科技大学生命科学学院, 陕西杨凌712100)
[摘 要] 在指出传统遗传算法收敛中所存在的收敛速度慢及局部收敛问题的基础上, 引入了一种新的改进遗传算法——多种群竞争遗传算法。该算法以种群间竞争为基础, 不断淘汰相似个体, 并不断补充新个体, 增加种群的多样性, 以提高收敛速度。最后, 用一个典型的测试函数对传统遗传算法和多种群遗传算法进行测试, 结果表明多种群遗传算法的性能优于传统遗传算法。
[关键词] 遗传算法; 多种群竞争; 改进算法[中图分类号] O 224 [文献标识码] A
[文章编号] 1671-9387(2005) 04-0154-03
遗传算法是由美国Michiga n 大学的Holland
教授在1975年提出的, 它是一种基于达尔文进化论思想的新的优化算法。遗传算法的求解过程是:首先产生一定数量的染色体形成一个种群, 再根据一个与目标函数相关的适应度函数评价各染色体的优劣, 依染色体的大小进行选择、交叉及变异操作, 得到新的染色体构成一个新的种群, 然后对新的种群再进行选择、交叉及变异操作, 如此进行一定代数的迭代后, 得到的最优染色体便是优化问题的最优解。
遗传算法提供了一种求解复杂问题的通用框架, 它的特点表现在求解过程中不依赖于问题的具体领域, 不需要求导或其他辅助知识, 是一种启发式搜索算法, 对给定的问题可以产生很多潜在解等方面。因此, 遗传算法在函数优化、生产调度、自动控制、图像处理和模式识别等领域已得到广泛应用。
尽管遗传算法的思路直观, 操作简单, 但由于其在初始种群的产生、选择、交叉、变异概率的选取上的随机性, 导致该算法存在收敛速度慢及不能收敛到全局最优解等缺点。因此, 近年来, 人们提出了不同的改进型遗传算法, 其中大多是集中在选择、交叉、变异概率的选取及适应度函数的选取上, 而忽视了对算法设计上的改进, 这种小细节上的变动在提高算法的执行效率, 加速收敛速度等方面有很大的局限性。本研究以生物进化理论为基础, 提出一种新的多种群竞争遗传算法, 该算法能从根本上提高优化问题的执行效率, 理论上可以证明其对模式定理是成立的[4,5]。通过实例验证表明, 该算法在提
[2,3]
[1]
高进化速度及获得全局最优解方面, 较简单遗传算法有很大提高。
1 多种群竞争遗传算法
1. 1 基本概念
(1) 相同长度的以a 为基的两个字符串中, 对应位不相同的数量称为两者间的广义海明距离。记 () 为第代进化种群, 其第个和第个个体分X t t i j 别为X i (t ) 和X j (t ) , 它们的海明距离为
H (X i (t ) , X j (t ) ) =体
X i (t ) =[1**********]11, X j (t ) =[1**********]01。
它们间的广义海明距离为
13
x ∑|
k =1
l
ik
(t ) -x jk (t ) |。
如含有相同基1**1001*****1的2个个
|=4。H (X i (t ) , X j (t ) )=∑x ik (t ) -x jk (t ) |k =1
(2) 对于种群X , 若任意i , j =1, 2, …, N , X i =
[6]
X j 恒成立, 则称X 为齐次种群。1. 2 一种新的多种群竞争遗传算法
对某一特定问题, 可随机产生N (N ≥2) 个子种群, 每个子种群包含n 个个体, 对每个子种群独立运行各自的遗传算法, 这些算法在设置特性上应该有较大差异, 再将N 个子种群经过遗传算子操作后的结果集中进行一定处理, 直至满足终止条件为止。该算法的执行过程如下。
[收稿日期] 2004-06-28
[作者简介] 吴养会(1971-), 男, 陕西乾县人, 讲师, 在读硕士, 主要从事农业工程中数学方法的研究。
第4期吴养会等:多种群竞争遗传算法及其性能分析
1) 根据问题的特性, 确定二进制编码的长度, 随机产生N (N ≥2) 个子种群, 每个子种群包含n 个个体。
2) 对每个独立的种群分别进行不同的选择、交叉及变异操作, 将其结果记录到数组R [i , j ](i =1……n ) 中。并计算每一个体的适应度值, 将其N , j =1
记录到数组A [i , j ](i =1…N , j =1…n ) 中。3) 对A [i , j ]按适应度值大小进行排序, 记为数组B [i ](i =1…(n ×N ) ) , 然后计算相邻个体间的广义海明距离H 。当H 的数值首次小于阀值d 时, 就删除其中适应度较小的个体, 代之以B [i ]中第一个个体B [1],依次类推, 否则, 保留这2个个体加入到中间群体。对d 的数值应适当选择, 以提高群体的多样性, d 值过大可能将优秀个体删除, 过小则可能起不到过滤作用, 其数值应随进化代数而变化。在进化过程的前期, 增加种群的多样性是主要目的, 此时应使d 值大一些, 而到进化的后期, 种群趋于齐次种群, 增加种群的多样性已不是主要目的, 此时d 值的选取应很小。因而d 应是变量, 且随着进化代数的增加而减少, 最终趋于零, 这是符合进化规律的。
4) 第3步中所得到的新的中间群体, 按照其所属的种群循环执行第2～3步操作, 直至得到满意的结果。
上述算法称为多种群遗传算法, 该算法与传统遗传算法的不同在于, 一方面增加了初始个体的数量, 扩大了算法的搜索范围; 另一方面通过删除相似个体, 减少了群体中齐次种群出现的机会, 增加了群
体的多样性, 避免算法的过早收敛及收敛到局部最优解。
2 多种群竞争遗传算法的性能测试
为验证算法的有效性, 将算法的全局收敛性和收敛速度与简单遗传算法进行了比较。考虑具有相当复杂度的典型的测试函数Shaffer F 6函数
2
2
2
[7,8]
:
12f (x 1, x 2) =0. 5-。(1+0. 001(x 1+x 2) )
S. T. -100
此函数有无限个局部极大点, 其中只有一个(0, 0) 为
全局最大, 最大值为1。此函数最大值峰周围有一个圈脊, 它们的取值均为0. 99028, 因此很容易停滞在此局部极大值。
对Shaffer F 6函数分别利用传统遗传算法和多种群竞争遗传算法进行寻优处理, 各算法的参数设置如下:
种群大小pop-size=20; 最大代数g en -max =100; 交叉概率p c =0. 3; 变异概率p m =0. 08。
图1为传统遗传算法进化代数-适应值曲线, 由图1可以看出, 无论经过多少次的进化, 其解均收敛于局部最大值0. 99028, 始终不能收敛到全局最大值1。而从图2多种群竞争遗传算法进化代数-适应值曲线可以看出, 利用多种群竞争遗传算法仅仅经过几十代的操作, 函数就已收敛到全局最优解1, 无论初始群体如何选取均收敛到全局最优解
。
图1 传统遗传算法进化代数-适应值曲线
Fig. 1 Fitness-g eneration curv e o f tr aditio n G
A
图2 多种群竞争遗传算法进化代数-适应值曲线
Fig. 2 Fit ness-g ene ratio n curv e o f impro ved G A
西北农林科技大学学报(自然科学版) 第33卷
3 结 论
本文就传统遗传算法中所存在的收敛慢、局部收敛等问题, 提出了一种基于生物种群竞争的多种群竞争遗传算法。该算法的基本思想是:分别独立的产生二相异种群, 对其进行不同的选择、交叉和变异操作, 将所得的所有个体进行排序, 依广义海明距离
H 与阀值d 的大小关系删除相似个体, 补充较优个体, 提高样本的适应度, 提高收敛速度。
用非常复杂的多值Shaffer F 6函数对传统遗传算法和多种群竞争遗传算法进行了测试, 结果表明, 多种群竞争遗传算法加快收敛速度且不会陷入局部最优。因此可以认为, 多种群遗传算法是一种较优的搜索寻优算法。
[参考文献]
[1] Holland J H. Ad ap tation in national and artificial s ys tems [M].M ich iban :Th e University of M ich igan Press , 1975. [2] 巩敦卫, 孙小燕, 郭西进. 一种新的优胜劣汰遗传算法[J].控制与决策, 2002, 11(6):908-912. [3] 韩万林. 遗传算法的改进[J ].中国矿业大学学报, 2001, 3(1):102-105.
[4] 陈长征, 王 楠. GA 中交叉和变异概率选择的自适应方法及作用机理[J ].控制理论与应用, 2002, 2(1):41-44. [5] 张文修, 梁 怡. 遗传算法的数学基础[M].西安:西安交通大学出版社, 2000. [6] 刘 勇. 数值计算优化方法——遗传算法[M].北京:科学出版社, 1998.
[7] 王小平, 曹立明. 遗传算法理论、应用与软件实现[M].西安:西安交通大学出版社, 2002. [8] 陈国良. 遗传算法及其应用[M ].北京:人民邮电出版社, 1996.
Several po pula tions competed g enetic alg orithm and its property analy sis
W U Yang -hui , WANG N ai -xin , LIU Ying -zhou
(Colle ge of L if e Scie nc es , N orthwe st A &F Univ e rsity , Yangling , Shaanx i 712100, China )
Abstract :In o rder to avoid the slo w-conv ergence and local conv ergence of traditional genetic algo-rithm, an im prov ed g enetic algo rithm -sev eral populations com peted g enetic algo rithm w as pro po sed in this
paper . This algo rithm w as based on the co mpetitio n of sev ertal popula tions , used unceasing elimina tion of similar individuals to increase the multiplicity of po pulatio n, a nd this paper tested with a com plex function fo r algo rithm. The experimental results show this algo rithm has g rea t adva ntage ov er traditio nal g enetic a l-g orithm.
Key words :g enetic algo rithm ; sev ertal populations com petition ; improved genetic algo rithm IGA