| 联系我们 |
 |
合作经济与科技杂志社
地址：石家庄市建设南大街21号
邮编：050011
电话：0311-86049879 |
|
|
| 经济/产业 |
［提要］ 为了提高遗传算法的搜索效率，给出了一种改进的遗传算法。该算法提出了新的交叉操作和仿粒子群变异，扩大了搜索范围。通过经典函数的测试表明，改进算法与一般自适应遗传算法相比较，在函数最优值、平均收敛代数、收敛概率等方面都取得了令人满意的效果。
关键词：自适应遗传算法；适应度函数；交叉操作；仿粒子群变异
中图分类号：TP3 文献标识码：A
收录日期：2012年1月12日
一、引言
遗传算法（GA）由美国Michigan大学的Holland教授于1975年首先提出，后经De Jong、GoldBerg等人改进推广，广泛应用于各类问题。它是一种模拟自然界生物进化过程与机制的全局概率优化搜索方法。
早期遗传算法在进化过程中易出现早熟收敛和局部收敛性差等问题，为了克服上述问题，人们提出了多种改进算法，本文针对遗传算法的不足，采用实数编码对遗传算法中的交叉和变异操作进行改进，提高了算法全局搜索能力，最后使用改进的算法进行仿真实验，结果表明本算法具有收敛概率高和平均收敛代数少的优点。
二、改进的遗传算法
1、改进的交叉操作。本文遗传算法采用实数编码，改进的交叉操作是先在交叉前产生三个服从均匀分布的随机数a∈［0，1］、b∈［－1，1］、c∈［－1，1］，然后假设x1，x2是要交叉的两个父代，个体变量为m维，则x1，x2可以表示为x1=（x11，x12，…，x1m），x2=（x21，x22，…，x2m），其中xi j∈［?琢，?茁］，设定?驻1＝（?驻11，?驻12，…，?驻im），?驻2＝（?驻21，?驻22，…，?驻2m）为位移变量，其中?驻ij=min｛（xi j-?琢），（?茁－xij）｝（i=1，2；j＝1，2，…m），最后进行两次操作得：
x1'=x1+b•?驻1x2'=x2+c•?驻2 （1）
x1''=ax1'+（1－a）x2'x2''=ax2'+（1-a）x1' （2）
x1'，x2'，x1''，x2''分别为两次操作所产生的子代，从这4个子代中选取适应度大的两个保留到下一代。通过这种操作可以有效地避免两个数值相近的个体进行“近亲繁殖”（数值相近的个体若只进行（2）式的操作会导致种群多样性快速下降），同时由于b，c的选取，生成的x1'，x2'是两个不相干的个体，彼此之间独立，由（2）式决定的后代还可以使子代遗传父代的某些有用因素，同时由于（1）式的位移调整，使得（2）式生成的后代比一般的算数交叉产生后代的范围扩大，提高算法的搜索范围，避免搜索陷入一个局部区域而出现“早熟”，最后再引入竞争机制在这四个后代中选出两个最好后代个体，这样在保证多样性的同时可以加快收敛的速度。
2、仿粒子群变异。由于粒子群算法概念简单，收敛速度快，易于实现且具有很强的全局优化能力，所以本文将遗传算法的变异操作改成如下：
假设xi=（xi1，xi2，…，xim）为待变异个体，变异之后的个体为xi'。变异操作依据方程xi'=?棕xi+c1r1（?琢－xi）＋c2r2（x-xi），其中?琢为个体的上界，x为前一代的最优个体，?棕为加权系数，c1，c2是两个正常数，r1，r2是两个0～1区间的服从均匀分布随机数。本文取?棕=0.7298，c1=c2=1.49445。
三、算法步骤
Step1 采用实数编码产生初始种群，在函数定义域内按照均匀分布随机产生n个个体｛xi｝（i＝1，2，…n），设定最大进化代数为T。
Step2 计算每个个体的函数值，之后根据■=■计算种群函数的平均值，最后按照适应度函数计算当前种群中每个个体的适应度。其中适应度函数的设定为：
f'（xi）=f（xi）－■ t＜0.6Ttan（■•■）•f（xi）＋fmax t＞0.6T （3）
其中，fmax为上一代最优解所对应的函数值，t为当前代数，T为预先设置好的最大迭代次数。
Step3 根据每个个体的适应度，采用比例选择法。通过这种适应度转换，使得在进化前期原本函数值小的个体将有更大的概率被选择，保持了种群的多样性。
Step4 按照概率
pc＝pc1-■，f≥favgpc1，f'＜favg在种群中随机选择父代个体，f'为两个要交叉个体适应度大的个体适应度值，之后应用本文改进的交叉操作进行交叉，最后通过竞争选取两个最好的个体作为子代个体。
Step5 依据变异概率
pm=pm1-■，f≥favgpm1，f＜favg选定变异个体，其中将选定的个体依照本文的拟粒子群变异方法进行变异。
Step6 最优保存策略，本文将最优保存策略算法做如下修改：第一步，计算每个个体的函数值，然后排序，找出最优解、最差解；第二步，若上一代最优解的函数值比当前最优解的函数值大，则用上一代的最优解替换当前最优解；若上一代的最优解函数值小，则用上一代的最优解替换当前中的最差解。这样基于Markov链的数学理论分析表明，保留最优个体策略的遗传算法能够以概率1收敛于最优解。
Step7 满足迭代次数即停止，否则代数加1，转入Step2。
四、仿真试验
1、测试函数。选取测试函数为：
maxf1=xsin（10?仔•x）+2.0；-1≤x≤2
maxf2＝（■）2＋（x12+x22）2；-5.12≤x1，x2≤5.12
它们的函数图像如图1、图2所示。（图1、图2）
f1是一维连续且含三角函数的多峰函数，其中，当x＝1.8505时，全局最大值为3.8503；f2是一个典型的大海捞针类函数，当（x1，x2）=（0，0）时函数有最大值3600，并且函数有4个局部极值点，它们为（5.12，5.12）、（5.12，-5.12）、（-5.12，5.12）、（-5.12，-5.12），函数值为2748.78。
2、测试结果对比分析。用本文算法同一般自适应遗传算法进行比较，其中取种群规模m=100，一般自适应遗传算法的交叉概率和变异概率也依照本文改进的遗传算法步骤中的Step4和Step5决定，其中pc1=0.85，pc2=0.65，pm1=0.15，pm2=0.05，最大迭代次数设为T=100，对函数f1应用这两种方法独立运行20次，如图3、图4所示。（图3、图4）（注：AGA表示一般自适应算法；IAGA表示本文的自适应遗传算法）
图3表示的是函数f1独立运行20次每代得到的函数值的平均值，可以清楚地看到改进之后的算法明显比一般的自适应算法收敛的速度快。图4表示的是函数f2经过改进的算法运行20次之后得到的每代的平均值，可以清楚地看到20次中每次都收敛到的全局最大值3600，再独立运行算法100次其中有93次都得到全局最大值，而之前的一般自适应算法收敛概率只有67%，所以本文的算法摆脱了模式欺骗，取得了极为理想的效果。
通过实验表明本文的算法在对函数f1、f2的测试中，达到最优值的收敛代数明显地减少，得到了令人满意的效果。特别是对函数f2的测试中本文算法不仅提高了算法的收敛概率，同时还使收敛代数明显地减少，所以本文的算法在减少收敛代数方面和提高收敛概率方面是具有优越性的。
五、结束语
本文通过改进交叉操作中，使得在避免“近亲繁殖”的基础上扩大了搜索范围，最后利用粒子群优化算法寻优快的特点，采用仿粒子群变异，大大提高了算法全局收敛能力，使本文算法具有较高的计算效率。
（作者单位：1.河北金融学院；2.中国地质大学长城学院）
主要参考文献：
[1]王力，侯燕玲.基于遗传算法通用试题库系统研究[J].微计算机信息，2008.5.3.
[2]Srinvivas M，Patnaik L M.Adaptive probabilities of crossover and mutation in genetic algorithms[J].IEEE Transaction on Systems，Man，and Cybernetics，1994.24.4.
[3]李敏强，寇纪淞，林丹等.遗传算法的基本理论与应用[M].北京：科学出版社，2004.
[4]魏平，熊伟清.一种改进的实数编码遗传算法[J].计算机应用研究，2004.21.9.
[5]吉根林.遗传算法研究综述[J].计算机应用与软件，2004.21.2.
[6]蒲若昂，李志华，宋国新.一种新的改进遗传算法及其应用[J].计算机应用与软件，2007.24.10. |
|
|
|
