论文导读:遗传算法是一种较新的全局优化搜索算法,它使用了群体搜索技术,用种群代表一组问题解,通过对当前种群施加选择、交叉和变异等一系列遗传操作,从而产生新的一代种群,并逐渐使种群进化到包含最优解或近似最优解的状态。近几年来遗传算法作为优良的全局寻优方法日趋成熟,尤其是和其他寻优方法的结合,进一步提高了遗传算法的性能,其中借助于混沌改进遗传算法的性能,是近年来遗传算法领域研究的热点之一,遗传算法和混沌优化的组合,可以使遗传算法的全局寻优能力,搜索精度,搜索速度等几方面得到较明显的改进。
关键词:遗传算法,混沌,优化方法
0引言
遗传算法是一种较新的全局优化搜索算法,它使用了群体搜索技术,用种群代表一组问题解,通过对当前种群施加选择、交叉和变异等一系列遗传操作,从而产生新的一代种群,并逐渐使种群进化到包含最优解或近似最优解的状态。但由于算法复杂度的限制, 遗传算法虽然能以概率收敛到全局最优解,其局部搜索速度和精度并不能得到很好的保证。近几年来遗传算法作为优良的全局寻优方法日趋成熟,尤其是和其他寻优方法的结合,进一步提高了遗传算法的性能,其中借助于混沌改进遗传算法的性能,是近年来遗传算法领域研究的热点之一,遗传算法和混沌优化的组合,可以使遗传算法的全局寻优能力,搜索精度,搜索速度等几方面得到较明显的改进。
1混沌的特征和虫口方程
混沌是存在于非线形系统中的一种较为普遍的现象。混沌并不是一片混乱,而是有着精致内在结构的一类现象。混沌运动具有遍历性、随机性等特点,混沌运动能在一定的范围内按照其自身的规律不重复地遍历所有状态。因此,如果利用混沌变量进行优化搜索,无疑会比随机搜索更具有优越性。
描述生态学上的虫口模型Logistic映射自May于1976年开始研究以来,受到了非线形科学家的高度关注,Logistic映射是混沌理论发展史上不可多得的典范性的混沌模型,如下式所示:
2混沌遗传算法
GA较传统数学优化方法更易找到全局最优解,但对于一些问题也存在过早收敛、收敛速度较慢、难以找到较精确解的情况。因此,本文通过Logistic映射及相关混沌理论提出了一种运算性能较好的混沌遗传函数优化算法。混沌遗传算法(CGA)的主要步骤如下:
1.初始化:预先确定运行参数,包括:种群规模M,交叉概率pc,变异概率pm,最大迭代次数n。随机产生一个分布均匀的初始群体(包含n个初始解),计算各个个体的适应度值;
2.采用比例选择算子对当前种群进行选择操作,实现强留劣汰;
3.对当前种群进行交叉运算。将种群内个体两两随机组合,对每个配对的组合,首先由系统随机生成一个(0,1)之间的数,由交叉概率决定是否交叉。论文参考。论文参考。若交叉,则采用映射生成的序列经简单映射后利用高斯函数来决定交叉位置,否则,看下一对组合。所有的交叉位置由一个混沌序列即可决定;
5.若终止条件满足,则算法中止,否则转向步骤(2)。
本文尝试在将改进后的遗传算法与混沌优化算法相结合,提出一种基于混沌理论的混合遗传算法,算法的流程如下页流程图所示:
图1 改进后的混沌遗传算法(ICGA)流程图
3仿真分析
本文选用一维和多维多峰值函数为例,见表1,用遗传算法(GA)、混沌遗传算法(CGA)和本文算法(ICGA)进行比较研究。
表1 测试函数
实验结果比较如下(以下图纵坐标表示最大适应值,横坐标表示演化代数)
图2 f2实验结果比较示意图图3 f3实验结果比较示意图
从图2、图3的比较结果看,本文中算法初始种群较好,进化开始就能找到高的最大值,加快搜索的速度,整个算法的寻优结果比遗传算法好。论文参考。考虑到算法中使用了随机操作,仅仅由一次实验得到的结果是不能够充分说明问题的,因此,再进行统计比较。本文中进行了20次统计实验。比较结果如表2
表2 比较结果
算法 |
函数 |
最差值 |
最优值 |
平均最优值 |
平均运行代数 |
GA |
f1 |
16.6558 |
16.9950 |
16.9917 |
16 |
CGA |
f1 |
16.9871 |
16.9963 |
16.9984 |
7 |
ICGA |
f1 |
16.9963 |
16.9950 |
16.9984 |
5 |
GA |
f2 |
4.2430 |
4.2532 |
4.25153 |
80 |
CGA |
f2 |
4.2499 |
4.2530 |
4.2531 |
32 |
ICGA |
f2 |
4.2515 |
4.2539 |
4.2531 |
15 |
GA |
f3 |
-130.2786 |
-186.7038 |
-182.7013 |
150 |
CGA |
f3 |
-186.4309 |
-186.6610 |
-186.7286 |
60 |
ICGA |
f3 |
-186.5892 |
-186.7309 |
-186.7038 |
36 |
从试验得到的各种图形和表格数据的比较中,可以看到:在多峰值函数的寻优过程中,本文的ICGA能产生较好的初始种群,有效的维持种群的多样性,具有更快的搜索速度,更好的搜索能力。
4结论
由此可见,对于搜索空间较大的全局优化问题,本文提出的改进的混沌遗传算法在一定程度上增强了避免过早收敛的能力,同时算法也很好地改善了寻优性能,有更好的实用性。
参考文献
[1]张晓绩,戴冠中,徐乃平.一种新的优化搜索算法-遗传算法.控制理论与应用.1995, 12(3):265-273
[2]宋莹,陈增强,袁著祉.基于混沌优化的非线性预测控制器. 控制理论与应用. 2007, 8:561-563
[3]王小平,曹立明.遗传算法-理论、应用与软件实现.西安交通大学出版社.2002
|