一种结合混沌搜索的改进云自适应遗传算法_岳茹.pdf

一一种种结结合合混混沌沌搜搜索索的的改改进进云云自自适适应应遗遗传传算算法法岳茹（山西省政法管理干部学院，山西 太原）摘 要针对传统云自适应遗传算法由于初始种群质量不高、局部搜索能力较差、交叉和变异概率的云模型控制参数为固定值而造成的早熟和收敛速度较慢的问题，提出一种结合混沌搜索的改进云自适应遗传算法（）。利用混沌模型生成初始种群，提高初始种群多样性；在进化过程中对最优个体进行混沌扰动，加强算法局部搜索能力；设计了随进化代数和种群规模变化的云模型控制参数，增强交叉和变异概率的自适应变化，克服早熟和收敛过慢的缺陷。实例仿真结果表明，算法既保持了云自适应遗传算法的稳定倾向性和随机性，又进一步加强了算法的寻优能力。关键词云模型；云自适应遗传算法；混沌搜索；云模型参数中图分类号 文献标志码 文章编号（）引言云模型最先由李德毅院士提出，主要用于解决定性概念与定量描述的转换问题，目前已被广泛应用于大数据、智能计算等领域。为了解决标准遗传算法收敛速度较慢、容易陷入局部最优解的问题，近年来很多学者利用云模型理论的随机性和稳定倾向性对遗传算法进行研究，而且取得了一定成果。戴朝华等分别利用 和 条件云发生器来设计遗传算法的交叉变异操作，提高了遗传算法求解精度和收敛速度，但是文中云模型控制参数采用固定值，使得算法初期不容易搜索到优秀新个体，而算法后期优秀个体容易被破坏，影响了算法性能的进一步提升。韩勇等对自适应云遗传算法进行了改进，引入在线性和非线性间平滑过渡的自适应算子，使得交叉和变异概率的控制参数根据种群适应度进行调整，算法的收敛性能和搜索能力得到了提高。但分析遗传算法原理可知，初始种群的质量直接决定着算法收敛速度，而该文献忽略了这点，限制了算法收敛速度。蹇洁等对标准遗传算法中的固定交叉和变异概率进行了改进，设计了基于最大保留机制的交叉、变异算子，提高了算法的收敛性和鲁棒性，并将该算法应用于有约束的车辆调度优化中，证明了该算法的优越性。针对文献研究中存在的不足，本文在云自适应遗传算法的基础上，利用混沌模型设计了改进算法。首先利用混沌模型的随机性和遍历性生成算法初始种群，提高初始种群多样性，加快算法收敛。在进化过程中对最优个体进行混沌扰动，使最优个体能够跳出局部最优解，同时保持算法全局和局部搜索能力。同时，设计了随进化代数和种群规模变化的云模型控制参数，解决了由固定参数带来的问题。最后通过仿真实验验证了本文算法的求解性能。云理论 云模型定义 设 为数值论域，是 上的语言值，若数值 ，且 是语言值 上的一次随机实现，对 的确定度是有稳定倾向的随机数，（）：，（），（）收稿日期作者简介岳茹，女，讲师，硕士，从事计算机科学与技术研究。则 在论域 上的分布称为 的隶属云，简称云，每一个 即一个云滴。如果（）服从正态分布，则称该模型为正态云模型，其主要特征包括期望、熵和超熵。其中，期望 表示云模型的水平位置，熵 表示云滴离散程度和可接受的取值范围，熵 用于度量 的不确定性。云发生器云发生器指云的生成算法，其主要程序段如下：，；输入期望、熵、超熵和拟生成的云滴数：（）；生成满足正态分布且期望和方差为、的随机数（）（）；（）（）（）；生成第 个云滴（），（）：（），（），（），（），（），（）；云自适应遗传算法传统自适应遗传算法的作用机理：让高于种群平均适应度的个体，随着适应度的增加，交叉和变异概率逐渐减小，以便对较优模式进行“保护”；而对于低于种群平均适应度的个体，则赋予较大的概率，使其通过交叉和变异产生较优个体。根据云模型特征可知，利用云滴的随机性和稳定倾向性设计遗传算法的交叉和变异概率，则更能实现该机理。本文利用云发生器来设计遗传算法的交叉和变异概率，云自适应遗传算法交叉概率 和变异概率 生成公式如下：（），；，其中，为交叉操作中的适应度值，是平均适应度值，表示最大适应度值，（），（），为，之间的常数，为控制系数。（），；，其中，（），（），为，之间的常数，为控制系数。的取值影响自适应交叉和变异概率。正态云模型“中间大，两头小”，期望、熵 分别影响其水平位置和陡峭程度，超熵 与云滴的离散程度成正比。根据“”规则，越大，云覆盖的水平宽度越大，个体交叉和变异范围越大。若 均为固定值，算法初期个体质量较差，自然难以找到优秀个体。同时，在算法后期，优秀个体也非常容易被破坏，进而影响算法求解性能。结合混沌搜索的云自适应遗传算法 混沌及其特性混沌是自然界广泛存在的一种非线性现象，指由确定性方程得到的随机性运动状态。混沌变量即呈混沌状态的变量，具有随机性、遍历性和规律性等特征，能够在一定范围内不重复地遍历所有状态，因此常用于复杂函数的优化，以提高种群多样性和全局寻优能力。较常用的混沌模型是一维 映射，其模型如下：（），（）其中，为控制参数，且当 ，时，式（）处于混沌状态。设定初始值 （，）（不能为、和），则由式（）可以产生混沌变量序列。混沌搜索与云自适应遗传算法的结合针对云自适应遗传算法初始种群多样性和进化过程中种群质量的缺陷，将混沌搜索与云自适应遗传算法相结合，主要采取以下两点措施。混沌优化生成初始种群初始种群的多样性和质量直接决定着最终解的质量和算法的收敛速度。而随机生成的初始种群一方面多样性较差，另一方面相当大一部分个体远离最优解，因此限制了算法的求解性能。利用混沌的随机性和遍历性不仅能够扩大种群的多样性，而且能够从混沌搜索结果中选取适应度较高的个体作为初始种群，也能够提高初始种群的质量，从而加快算法的收敛速度。首先为式（）中 赋予 个不同的初始值，设定 ，利用式（）得到 维、个不同轨迹的混沌变量序列，；，。通过式（）将混沌变量分别映射到优化变量，的取值范围内。，（），（）其中，分别表示第 维变量的最小值和最大值。对于固定的 值，（，）表示一个可行解。计算每个可行解对应的适应度值，选择适应度较高的 个个体组成初始种群。为了使混沌变量能够充分遍历，在初始种群的混沌生成过程中，混沌序列应该有足够的迭代次数（的取值范围一般为）。混沌扰动最优个体为了加强算法局部搜索和收敛速度，避免算法陷入局部最优解，对每次迭代过程中的最优解进行小幅度的混沌扰动。具体操作步骤如下：步骤 将当前最优个体 （，）的第 维分量，映射到区间，有，（）步骤 随机产生一个初始值，（，），利用式（）进行混沌扰动得到混沌变量，。步骤 将，和，进行线性组合，可得到扰动后的新决策变量，（），（），（）其中，为正整数，本文取 。步骤 将，通过式（）反映射到区间，得到扰动后的个体。依次取值，反复执行步骤 至步骤，直到生成 个新分量为止。结合混沌搜索的云自适应遗传算法分析 编码策略及参数设定与二进制编码相比，十进制浮点数编码具有直观、节省时空开销、计算效率高的优势，因此本文算法采用十进制浮点数编码。设定种群规模、混沌迭代次数、云自适应遗传算法控制参数 的值。混沌优化生成初始种群利用前文所述的初始种群生成机制，得到质量更高的初始种群。适应度值计算及最优个体混沌扰动选择目标函数或者目标函数的适当变型作为算法的适应度函数，并计算个体适应度值。对最优秀个体进行混沌扰动，并将扰动后的个体作为保留精英直接加入下一代种群。选择算子计算个体适应度值并由小到大排序，根据适应度值划分赌盘。个体越优秀，越容易进入下一代。交叉算子待交叉概率按交叉概率 的计算公式进行调整，同时采用适合浮点数编码的算术交叉算子，即 （），（）（），（）其中，表示待交叉个体，表示交叉后新个体，表示（，）内的随机数。变异算子变异概率按第 章中的 公式进行调整，随机选择待变异个体的一个基因作为变异点，生成（，）内的随机数 ，按下式变异：，（），（）其中，表示个体 的第 位基因变异后的值。终止条件如果达到了设定的最大迭代次数，则算法终止。否则转到 小节进行下一次迭代。典型函数优化仿真 测试函数采用如下测试函数：（，）（），；（，）()（），；（，）（）（），仿真结果分别用本文算法（）、文献的云自适应遗传算法（）、自适应遗传算法（）和标准遗传算法（）进行测试。本文算法参数设置：三个适应度函数分别选取、（）和 （），其阀值设定为、和 ；初始种群混沌迭代次数 ，种群规模 ，最大迭代次数 ，；控制参数 （），（），（和先大后小，取值范围为），其中，为当前种群迭代次数。对 个测试函数的仿真结果进行统计分析，算法、算法和 算法的结果来自文献。具体仿真结果详见表。在表 中，标准偏差表示函数理论最优值和算法求得最优值的标准差，平均迭代次数表示 次实验中最优个体适应度值达到指定阀值时进化代数的平均值，失败次数表示最优个体适应度值小于指定阀值的实验次数。表 测试函数仿真结果函数优化算法标准偏差失败次数平均代数平均耗时 从表 可知，算法利用了云滴稳定倾向性特点，收敛的平均代数小于 算法和 算法。而 算法的迭代次数远小于 算法，这是由于 算法随机生成的初始种群多样性较差，且大部分初始值远离最优解，算法则通过混沌模型的随机性和遍历性特点对初始种群进行优化，不仅增加了种群多样性，而且提高了初始种群质量，从而加快了算法的收敛速度。通过不同函数下各算法寻优的标准偏差和失败次数可以看出，由于云自适应调整的概率值的随机性，使得个体适应度值最大时其交叉和变异概率值并非绝对为零，一定程度上保持了算法进化过程中种群的多样性，所以 算法和 算法的全局寻优能力远优于 算法和 算法。但比起 算法，算法对最优个体进行了混沌扰动，利用混沌的随机性，使得最优个体能够在其邻域范围进行局部搜索，跳出了局部最优解，进一步加强了算法的局部寻优能力，从而避免了算法出现早熟现象。由于算法更加复杂，所以 算法耗时是最长的，但增加幅度并不大，且由于算法收敛速度最快，因此如果当算法达到阀值即停止迭代，其运行时间反而会小于 算法、算法和 算法。结语本文针对云自适应遗传算法的不足，利用混沌模型设计了结合混沌搜索的改进云自适应遗传算法。在原有云自适应遗传算法的基础上，利用混沌模型的随机性和遍历性生成初始种群，改善了初始种群的质量，加快了算法收敛速度。同时对进化过程中的最优个体进行混沌扰动，加强了算法局部搜索能力。通过对云自适应遗传算法控制参数的分析和反复实验，得出了与种群规模和迭代次数有关的控制参数，解决了由固定参数带来的问题。通过仿真实验可知，本文算法在继承了云自适应遗传算法的稳定倾向性和随机性的基础上进一步加强了算法的寻优能力，同时提高了算法收敛速度，具有一定的实用价值。参考文献杨欣，曾珍香，孙学珊基于云模型 法的云制造资源评价问题研究数学的实践与认识，（）：杜文军，孙斌基于正态云模型的果蝇优化算法东北电力大学学报，（）：戴朝华，朱云芳，陈维荣云遗传算法西南交通大学学报，（）：戴朝华，朱云芳，陈维荣云自适应遗传算法控制理论与应用，（）：韩勇，曹兴华，杨煜普一种改进的自适应云遗传算法计算机仿真，（）：，蹇洁，王旭，葛显龙云自适应遗传算法有能力约束的车辆调度优化重庆大学学报，（）：陈善学，唐义嫄基于混沌系统的 彩色图像三重置乱算法重庆邮电大学学报（自然科学版），（）：米永强，高岳林非线性 规划问题的混沌粒子群算法数学的实践与认识，（）：吴军，王龙龙基于双鸟群混沌优化的 图像分割算法微电子学与计算机，（）：，（）：，（）：，（）：（，）：（），（），：；（责任编辑：周巧姝）