函数优化的遗传算法（通用12篇）
函数优化的遗传算法 篇1
遗传算法(Genetic Algorithm,缩写为GA)是Holland教授首先提出来的一种借鉴生物界自然选择和遗传原理的随机优化搜索策略,一种高度并行、随机和自适应的仿生型优化算法,具有全局搜索能力,鲁棒性强等特点[1]。因此,遗传算法广泛用于组合优化、机器学习、自适应控制、规划设计和神经网络等领域,是21世纪有关智能计算中的关键技术之一。函数优化(Function Optimization)是遗传算法的经典应用领域,也是对遗传算法进行性能评价的常用算例,可以用各种各样的函数来验证遗传算法的性能。
1 函数优化问题
对于一个求函数最大值的优化问题(求函数最小值也类同),一般可以描述为下列数学规划模型:
式中x为决策变量,式1-1为目标函数式,式1-2、1-3为约束条件,U是基本空间,R是U的子集。满足约束条件的解X称为可行解,集合R表示所有满足约束条件的解所组成的集合,称为可行解集合。
2 云模型
云模型是定性定量间的不确定性转移模型,它用期望值Ex、熵En和超熵He表征定性概念,将概念的模糊性和随机性集成在一起,为定性与定量相结合的信息处理提供了有力手段[2]。期望值Ex反应了云层的重心位置;熵En反应了云层的陡峭程度,En越小越陡峭;超熵He反应了云层的厚度,He越大云层越厚,正态云模型的三个数字特征示意图如图1所示。图1表示当x=Ex时其确定度为1,当x>Ex时,确定度随着x的增大而减小。要使遗传算法的收敛速度加快,不易陷入局部极小,得到正确的结果,必须使适度值小的个体有较大的交叉概率和变异概率,适度值大的个体有相对较小的交叉概率和变异概率。从图1可以看出当x>Ex时云模型具有这一特点,可以将x作为遗传算法中两交叉个体的最大适应度以及变异个体的适应度,确定度作为交叉概率和变异概率,并且云模型中云滴集中在区间[Ex-3En,Ex+3En],云层厚度为He,具有很好的随机性和稳定倾向性。
3 遗传算法求解过程
遗传算法是一个迭代过程,在每次迭代中都保留一组候选解。并按某种原则从中选出一些解,利用一些遗传算子对其进行运算,产生新一代的一组候选解,重复此过程,直至满足某种收敛条件,具体过程如下:
1)初始化:根据求解问题选择合适的编码,随机生成M个个体作为初始群体。
2)个体评价:计算群体中各个个体的适应度。
3)选择运算:选择操作建立在群体中个体的适应度评估基础上,将选择算子作用于群体。选择的目的是将优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。
4)交叉运算:交叉算子选择两个不同个体的染色体的部分基因进行交换,形成新个体。该算子确定和扩充解空间,是一个随机化的重组算子,在很大程度上,遗传算法的性能取决于所使用的交换算子的性能。
5)变异运算:变异算子对某些个体的某些基因进行变异,自爱通常的二进制编码方式下,变异操作就是简单地将基因值取反(1变0或者0变1)[3]。
群体经过选择、交叉、变异运算之后得到下一代群体。
6)终止条件判断:达到最大进化代数或者收敛,则以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。其具体算法流程如图2所示。
4 函数优化实验原理及结果
设优化问题的目标函数为:式中x的取值范围是1~31,求f(x)的最大值。
4.1 初始化编码
遗传算法的第一步是将x编码为有限长度的串,针对本例中自变量的定义域,考虑采用二进制数来对二编码,恰好可用5位二进制数来表示,例如01001对应x=9,11111对应x=31[4]。
4.2 选择
为了克服适应度比例法的选择误差,即适应度高的个体也存在淘汰的可能。因此,提出根据每个个体在下一代群体中的生存期望值进行随机选择,其过程如下:
1)计算群体中每个个体Ai在下一代群体中的生存期望数目Mi:
该式中,N表示群体中个体的数量;f(Ai)表示个体Ai的适应度。
2)若某个个体被选择参与交叉,则它在下一代中的生存期望数目减去0.5,若不参与交叉,则该个体的生存期望数目减去1。
3)若个体的生存期望数目小于0,则不参与选择。
4.3 交叉
交叉将染色体的基因进行互换,从而产生新的后代,本文采用单点交叉:随机选取某个基因位,从此位开始交换两父本后面的序列,相应地产生两个后代,实例如下:
父本1:α1,α2,α3,α4,α5,α6,α7,α8
父本2:β1,β2,β3,β4,β5,β6,β7,β8
子代1:α1,α2,α3,α4,β5,β6,β7,β8
子代2:β1,β2,β3,β4,α5,α6,α7,α8
交叉概率pc[5]由云模型产生,公式如下:
4.4 变异
变异的情况是遗传算法的三个主要操作之一,符合生物进化的规律,只有通过变异才能更好的丰富生物多样性。
变异作用在单个染色体上,并且产生一个不同于父本的染色体,变异方式有多种,本文采用简单变异:简单变异又称为点变异或二进制变异,一个个体中任一位按某一概率pm进行取反运算,即1变0或0变1。示例如下:
个体:10110011新个体:10010011
第三位由1变为0。
变异概率pm公式[5]如下:
交叉概率和变异概率中的为群体的平均适应度,fmax为群体的最大适应度,f为变异个体的适应度,f'为两交叉个体中的最大适应度值,ci(i=1,2)和k为控制参数,c1用来控制云的陡峭程度,根据“3En”规则,一般取3附近的值,c2用来控制云层的厚度,一般取10附近的值;k可取0.95~1之间的常数。
4.5 适应度函数
函数本身的值。
4.6 实验结果
在编码方案、选择算子、交叉算子、变异算子、适应度函数相同的情况下,分别用固定的交叉概率和变异概率即标准的遗传算法以及自适应的交叉概率和变异概率即云遗传算法连续运行程序10次。10次实验的进化代数与收敛值对比结果如表1所示。通过表1可以看出,10次实验中标准遗传算法以及云遗传算法全部都收敛,都是8次收敛于全局极大值100,2次收敛到局部极值,在收敛次数以及极值上是相同的。但是,云遗传算法的进化代数明显少于标准遗传算法的进化代数,收敛速度快。
5 结束语
交叉概率越大,新个体产生的速度就越快。然而,当交叉概率过大时,遗传模式被破坏的可能性也越大,使得具有高适应度的个体结构很快就会被破坏;但是如果交叉概率过小,会使搜索过程缓慢,以至停滞不前。对于变异概率,如果变异概率过小,就不易产生新的个体结构;如果变异概率取值过大,那么遗传算法变成了纯粹的随机搜索算法。由X条件云发生器产生改进的自适应交叉概率和变异概率,能够使适应度大的采用小的交叉或变异概率,适应度小的采用大的交叉或变异概率,选择自适应的交叉概率和变异概率,可以使群体平均拟合和最优模式拟合都能较迅速地改进,快速收敛。
摘要：遗传算法是基于进化理论,并采用遗传结合、遗传变异及自然选择等设计方法的优化技术。遗传算法中交叉概率和变异概率的选择是影响遗传算法行为和性能的关键所在,直接影响算法的收敛性。该文结合正态云模型云滴的随机性和稳定倾向性,由X条件云发生器产生自适应交叉概率和变异概率。函数优化实验结果表明,云遗传算法只需要较少的进化代数就可以收敛,收敛速度明显快于标准遗传算法。
关键词：云模型,遗传算法,函数优化,交叉,变异
参考文献
[1]韩红燕,潘全科,任文娟,张凤荣.基于遗传和声算法求解函数优化问题[J].计算机应用研究,2010,27(5):1723-1725.
[2]刘常昱,李德毅,杜鹢等.正态云模型的统计分析[J].信息与控制,2005,34(2):236-239.
[3]张云涛,龚玲.数据挖掘原理与技术[M].北京:电子工业出版社,2004:123-157.
[4]杨建刚.人工神经网络实用教程[M].杭州:浙江大学出版社,2001:148-157.
[5]Zhu Yunfang,Dai Chaohua,Chen Weirong,Lin Jianhui.Adaptive probabilities of crossover and mutation in genetic algorithms based oncloud generators[J].Journal of Computational Information Systems,2005,1(4):671-678.
函数优化的遗传算法 篇2
摘要:为了很好地解决物流车辆的线路优化问题（简称VRP），借鉴DNA算法局部寻优能力强的优点，提出新编码方法，以及车辆的行使路线的新的测序方式，很好地解决遗传算法的早熟、局部寻优能力差的问题。通过测试，发现交替使用遗传算法和DNA算法进行全局寻优和局部寻优可以相对较准确、快速的实现车辆线路的寻优。
关键词:遗传算法；DNA算法；VRP
一、引言
物流被誉为经济活动中的“未开发的黑大陆”、企业的“第三利润源泉”。物流的目标在于以最小的费用满足消费者的最大需求，而运输的费用占整个企业物流的40％左右。在运输过程中，配送是其中一个重要的直接与消费者相连接的环节，物流配送车辆的线路优化问题，更是物流配送优化中的关键环节，正确合理的安排车辆的配送线路，可以有效的减少车辆的空驶率，实现合理线路运输，从而降低运输成本，节约运输时间，提高经济效益，达到物流科学化管理。
二、遗传算法与DNA算法
遗传算法是一种基于自然选择和自然遗传机制的自适应的随机搜索算法，它是一种有效的解决最优化问题的方法。
遗传算法求解工程实际最优化问题的基本步骤是：首先对可行域中的个体进行编码；然后在可行域中随机挑选指定群体大小的一些个体组成作为进化起点的第一代群体，并计算每个个体的目标函数值，即该个体的适应度。利用选择机制从群体中随机挑选个体作为繁殖过程前的个体样本。选择机制保证适应度较高的个体能够保留较多的样本；而适应度较低的个体则保留较少的样本，甚至被淘汰。在繁殖过程中，遗传算法提供了交叉和变异两种算法对挑选后的样本进行交换和基因突变。交叉算法交换随机挑选的两个个体的某些位，变异算子则直接对一个个体中的随机挑选的某一位进行突变。这样通过选择和繁殖就产生了下一代群体。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。
遗传算法是一种自适应随机搜索方法,具有极强的并行机制，在解决整体的搜索问题时，具有很强的鲁棒性和全局寻优能力。但遗传算法忽视了个体潜力的开发而只重视群体整体性能的提高。也就是说，遗传算法能够以较大的概率找到最优区域而不是最优点。因此遗传算法在应用中也有一些不尽人意的地方，主要表现在算法收敛慢、效率低、容易早熟、局部寻优能力差等。
三、基于DNA算法对VRP的局部寻优
为追求DNA计算局部寻优解的质量，我们在算法中加入基于启发式知识的方向搜索策略。在网络拓扑图中，求解某几个节点的最短回路，不需要对整个网络进行问题求解，可以只提取出与节点紧密相关的节点与弧段构成子网络，在子网络中进行问题求解，降低问题规模，提高算法效率。即基于方向策略的限制搜索区域方法[7]，比如搜索从北京到沈阳的最短路径，完全可以把南京、重庆等节点排除在搜索空间以外。该方法是一种有损局部寻优算法，即排除了概率极小的子网络外最优路径的可能。
在单条路径寻优中，以该点集作最小凸包，并以该凸包区域作适当扩充的缓冲区，落在缓冲区内的节点与弧段构成子网络进行搜索计算。DNA计算模型即构建在该子网络上进行，在保证有效搜索的基础上多余的边(辅助边)尽量少。
我们这里的VRP可描述为：已知n 个代售点之间的相互费用大小(在编码时用DNA片段的长度来表示)，现有一辆配送车必须访遍n个代售点 ,最后又必须返回起始送货点。如何安排车对这些代售点的有向行使路线，可使其行驶路线的总费用最少？以图论术语来说，假设有一个图G =(V,E,W)，其中，V是顶点集，E是边集，W是顶点和边的权值集，设D=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，VRP就是求出一条通过所有顶点完成配送任务并且总费用最少的有向路径。
（一）算法思想
依据上述思想，为了便于利用DNA计算，我们设计如下的求解该VRP的基本算法：
步骤1 ：搜索出所有闭合路径。
步骤2 ：找出那些开始于0、结束也是0的固定顶点的闭路经，也就是说，保留那些经过0的固定顶点的闭路经。
步骤3：找出那些经过所有节点至少一次的闭合路径，也就是说，保留0的所有广义Euler闭迹。
步骤4：找出最短的广义Euler闭迹，这就是我们所需的解。
步骤5：确定出配送车路线。
（二）VRP的DNA计算编码以及实施
1、构建VRP的DNA计算编码
先选取节点和弧段的基本寡聚核苷酸片断，通常是根据相应权值的大小先同等放大为正整数，再分别求出节点和弧段的最小公倍数作为基本寡聚核苷酸长度的制定标准。
由于DNA编码片断的数目随着路径条数的增加呈指数增长，如此复杂的编码也将成为DNA计算的技术瓶颈。本文采用基本寡聚核苷酸（K个）连接组合（单独长为4的一条就能形成K4/2种组合，因此所需的寡聚核苷酸的种类大大减少）从很大程度上简化这个过程，尽量减少DNA生物操作而更多地通过合理的编码进行处理，从而大大减少了误差的来源，这也是DNA计算研究的难以解决的问题之一。
2、VRP的DNA计算实施改进
步骤1：将以上各节点和弧段编码好的核苷酸放在不同的试管中加入底物（具有各自相同同位素标记的DNA分子）、适量的引物（固定点所对应的寡聚核苷酸片断的补链）、DNA聚合酶及缓冲液进行PCR扩增，这样在聚合酶的作用下可以使得DNA链成指数增加，各自产生大量的寡聚核苷酸。
步骤2：将第一步中合成的各节点所对应的寡聚核苷酸片断和边所对应的寡聚核苷酸片断混合在一起，加入缓冲液、DNA连接酶使之进行连接反应，这样可以生成所有闭路径，保留这些那些以0点开始和结束DNA链。
步骤３：将第2步的产物进行纯化，然后对于纯化后的产物进行分离。在分离过程中我们首先以表示边权的寡聚核苷酸片断的补链为模板构造探针，然后利用构造的探针对纯化后的产物进行分离。与该探针杂交的DNA链中一定含有该寡聚核苷酸片断，再将之加热变性后保留这些DNA链。这些被保留的DNA链一定包含所有边，也就是说我们找到了所有广义Euler闭迹。
步骤４：对第３步的产物进行琼脂糖浆凝胶电泳，跑在最前面的就是最优的DNA链。
步骤５：将上述步骤的标记产物直接由相关仪器进行读取，从而确定所求VRP的配送路线。
四、总结和展望
VRP是一种NP难题，本文结合遗传算法和DNA算法的各自优势，交替进行全局寻优和局部寻优，从而具有良好的全局性和局部性，在通过对算法本身经过创新改进后对解决VRP等NP难题将有不错的成效。
本文提出采用以基本单位的寡聚核苷酸相连接从而形成不同长度的片断对节点和弧段进行编码，从而避免在融合的过程当中形成发夹结构从而产伪解，而且也减少了生物操作（变性、退火等），使得到所需的DNA寡聚核苷酸源片断变得更加容易。其次，本文提出新的测序方式，即事先就各自进行带标记的核苷酸基片进行PCR复制，从而在检测目标时只需通过强度检验就可以知道寡聚核苷酸片断的连接顺序，映射得到车辆的行使路线，减少了测序操作。
参考文献：
[1] 丁立言,张铎.物流管理[M].北京:清华大学出版社,1999:15-16
函数优化的遗传算法 篇3
摘 要：电力系统的无功优化是降低网损、保障电压质量的有效手段，遗传算法是解决这种多约束非线性组合优化问题的很好方法。简单遗传算法（SGA）中的交叉率和变异率分别是一个过大或者过小的固定值，造成了高适应度基因遭到破坏和算法陷入迟钝，本文中改进遗传算法（IGA）使用变化的交叉率和变异率避免了此类现象。文献中以IEEE33节点系统为例，分别用两种算法进行了无功优化的计算，通过比较得到结论，IGA具有最优解更加准确、收敛速度更加迅速的优点。
关键词：无功优化；改进遗传算法；交叉率；变异率
1 概述
近年来，越来越多的专家将目光投向电力系统的无功功率上来，希望通过调节无功功率的潮流分布，从而减小系统有功网损，使电力系统更加经济、高效。
电力系统的无功优化是指电力系统在满足安全稳定运行的所有约束条件下使有功网损、电压质量和无功补偿等预期目的总体最佳的多约束非线性组合优化问题。为了解决此问题，产生了多种无功优化方法[1]，其中包括：非线性规划法[2]、线性规划法[3]、混合整数规划法[4]、动态规划法[5]、人工智能法等，其中人工智能法又包括人工神经网络、专家系统、模糊算法、Tabu搜索法、模拟退火法、遗传算法等一系列算法。本文的改进遗传算法是在传统的简单遗传算法的基础上对交叉和变异环节进行了改进，使运算过程更加迅速、运算结果更加准确。
2 无功优化的数学模型
电力系统无功优化是指在满足系统各种运行约束的条件下，通过优化计算确定发电机的机端电压、有载调压变压器的分接头档位和无功补偿设备投入量等，以达到系统有功网损最小的目的[6]。
①本文以系统有功网损最小为优化目标：
minF=PS
PS表示系统的有功网损。
②功率平衡的约束在潮流计算中是绝对满足的，如下：
PGi-PLi=UiUj（Gijcosδij+Bijsinδij）
QGi+QCi-QLi-QRi=UiUj（Gijcosδij-Bijsinδij）
式中，n代表电网节点总数；Ui、Uj代表节点i、j的电压；PGi、PLi代表节点i发电机有功功率和有功负荷；QGi、QCi、QLi、QRi代表节点i发电机无功功率、容性无功补偿容量、无功负荷和感性无功补偿容量；代表电网中节点i和j之间的电导、电纳和节点电压相角差。
③网络中，不等式的约束条件为：
Uimin?Ui?Uimaz （节点电压约束）
Qmin?Qi?Qimaz （节点无功约束）
Timin?Ti?Timaz （变压器分接头约束）
3 改进遗传算法
基本遗传算法（简单遗传算法，Simple Genetic Algorithm，简称SGA）是一种仿造生物遗传和进化机制得到的适合于复杂系统优化的自适应概率优化技术。
简单遗传算法中，交叉率（pc）为一恒定值，这种运算虽然简单，但存在很严重的缺陷，如果PC为一适中大小的固定值，那么对于迭代初期来说交叉率相对较低，会引起迭代迟钝，影响遗传算法的整体过程；对于迭代后期而言交叉率相对较高，会导致新的搜索区域被开辟，造成迭代趋向随机化的严重后果。
针对上述缺陷，本文献采用了一种变化交叉率的改进方法，为了满足迭代前期对较大交叉率的要求，我们设初始交叉率pc为一个较大值，同时为了满足迭代后期对较小交叉率的需要，我们让pc在每次迭代过程中逐渐减小，直到减小到某一固定值为止恒定。
同理，变异率（pm）也为一恒定值，同样存在缺陷，如果pm为一适中大小的固定值，那么对于迭代初期来说变异率相对较高，在迭代初期会导致原本就极少的具有高适应度的个体基因被变异破坏，大大阻碍了遗传基因的进一步优化；对于迭代后期而言变异率相对较低，会导致迭代后期没有新的具有活力的基因注入，从而使整个遗传算法陷入局部最优解。
针对上述缺陷，本文献同样采用了变化变异率的改进方法，为了满足迭代前期对较小遗传率的要求，我们设初始遗传率pm为一个较小值，同时为了满足迭代后期对较大遗传率的需要，我们让pm在每次迭代过程中逐渐增大，直到增大到某一固定值为止恒定。
我们把上面对交叉率和遗传率的改进植入简单遗传算法中，从而得到改进遗传算法（Improved genetic algorithm，简称IGA）。
4 算例分析比较
下面以IEEE33节点系统为例，此系统中有支路32条、联络开关支路5条。本算例中，33节点系统为一配网系统且无变压器，不可通过调节变压器分接头档位来进行优化。0号节点为平衡节点，其余32个节点为PQ节点，可以通过向17号节点添加无功补偿装置的方法对系统节点电压进行调节，以达到减小有功损耗的目的。
两种遗传算法的种群规模均为popsiza=40、最大迭代次数为T=30、二进制编码方式、赌轮盘选择。简单遗传算法（SGA）的交叉率为固定值pc=0.8，变异率为固定值pm=0.1；而改进遗传算法（IGA）的交叉率为初始值pcmax=0.8，以0.02为步长递减到pcmin=0.2的变化值，最后pc恒定在0.2，交叉率为初始值pmmin=0.1，以0.005为步长递增到pmmax=0.2的变化值，最后pm恒定在0.2。
图2和图3分别为两种遗传算法运算的结果曲线图。
通过图2、3的结果对比可以看出，改进遗传算法进行无功优化得到的最优适应度更好。
对17号节点的无功补偿后，网络的节点电压得到优化，数据如表1。
从上述表1对比结果可知，与简单遗传算法相比，改进遗传算法进一步降低了无功优化的网损，提高了降损率，并且有着更短的运行时间，更好的运行效率。
5 结论
本文对简单遗传算法进行无功优化所存在的高适应度基因易造成破坏和运算易陷入迟钝状态的现象进行了分析，从而增加了递减交叉率和递增变异率的运算环节，分别用两种遗传算法进行了无功优化的仿真运算。算例结果表明，改进遗传算法具有求解更准确、收敛速度更迅速的优点。
参考文献：
[1]陈燕萍.基于改进遗传算法的电力系统无功优化[J].南京师范大学，2008，5.
[2]李林川，王建勇，陈礼义.电力系统无功优化规划[J].中国电机工程学报，1999，19（2）：66-69.
[3]赵尤新，徐国禹.灵敏度法分析计算电力系统无功和电压最优控制问题[J].重庆大学学报，1985，8（2）：1-11.
[4]Rama Iyer S，Ramachandran K，Hariharan S. Optimal Reactive Power Allocation for Improved System Perfor-mance[J].IEEETransactions Power and System，1984，PAS-103（6）.
[5]李文沉.电力系统安全经济運行——模型与方法[M].重庆大学出版社，1989.
[6]张利生.电网无功控制与无功补偿[M].中国电力出版社，2012.
作者简介：
函数优化的遗传算法 篇4
现实生活中遇到的很多工程设计、组合优化等均属于多峰值函数优化问题, 在可行域内寻求其全局最优解和满足需要的局部最优解一直是人们关注的焦点。学者们提出了很多启发式信息算法, 如遗传算法、蚁群算法等。作为一种随机搜索算法, 遗传算法借鉴了生物界自然选择和自然遗传机制, 通过选择、交叉、变异等基本操作搜索最优解。这种优化算法比较简单, 求解过程中不需要导数信息, 鲁棒性强, 具有并行计算的能力;但其收敛速度慢、迭代次数多, 易陷入局部最优。
第一个量子算法——求解大数质因子分解是1994年Shor提出的[1], 1996年Grover又提出随机数据库搜索的量子算法[2], 它们打开了量子算法研究的大门。从此, 量子计算以其优越性能迅速成为了前沿研究领域。量子计算属于新兴交叉学科, 它将量子力学和信息科学结合起来, 以量子态为基本的信息单元, 利用其叠加、纠缠和相干等特征实现信息的传输、处理等, 采用量子并行计算, 尤其适用于求解经典计算中的NP问题。
量子遗传算法 (QGA) 是一种基于量子计算原理的遗传算法, 它将量子计算和遗传算法相结合, 在遗传编码中引入量子的态矢量表达, 信息的多种状态只需采用一条染色体, 既丰富了种群又减小了种群规模;利用量子逻辑门实现染色体的更新操作[3], 从而对目标进行优化。
本文提出了一种用于多峰函数优化的量子遗传算法, 介绍了该算法的实现方法, 以典型的多元多峰函数Shubert为例进行仿真研究, 并进行了性能分析。
1 量子遗传算法
1.1 量子比特编码
在量子计算机中, 采用量子比特表示信息的载体。与经典位不同, 量子比特既可以表示“1”态和“0”态, 也可以表示它们的任意叠加, 如式 (1) 所示:
式中, |0〉表示自旋向下态;|1〉表示自旋向上态。a和b为复常数, 代表相应状态出现的概率幅, 并且满足:
其中, |a|2和|b|2分别表示量子比特处于|0和|1的概率。
量子比特编码可以将多个态的叠加用一个染色体表示, 从而增加了染色体的多样性;当|a|2→0或|b|2→1时, 染色体收敛到单一状态, 从而获得最优解, 因此量子遗传算法又具有较好的收敛性[4]。
设种群规模为n, 则QGA中第k代量子种群可表示为
ixk (i=1, 2, …, n) 为第i个个体的染色体, 其具体形式可用 (4) 式描述为:
其中, m为染色体的基因个数, l为每个基因的量子比特数。
1.2 量子旋转门调整策略
为了保持种群的多样性, 传统的遗传算法采用了交叉、变异等操作, 与SGA不同, QGA一般采用量子旋转门作用于各叠加态或纠缠态的基态, 通过改变它们的概率幅去更新种群[5]。量子旋转门的调整策略如下式所示:
式中, 分别为更新前后染色体中第i个量子比特旋转门的概率幅。
由式 (5) 可得:
则1, 可见:更新后量子比特旋转门的概率幅仍满足式 (2) 。
式 (5) 中, i (28) F (a i, b i) (35) i为旋转角, 其旋转的方向F (a i, b i) 和角度 (35) i由表1所示的调整策略来确定, 其中, iq表示当前染色体的第i位, q_besti表示当前最优染色体的第i位。调整策略为:
1) 测量ixk, 并比较其适应度f (q) 与当前的目标值f (q_best) 的大小;
2) f (q) >f (q_best) 时, 调整个体ixk中相应位量子比特, 使〔a i bi〕向着有利于iq的方向演化;
3) f (q)
1.3 量子遗传算法流程
算法的具体流程如图1所示。
1) 产生种群X (k0) , 初始化其参数, 为了将全部可能状态等概率表示出来, 一般令全部染色体的量子比特编码;
2) 测量种群中的所有个体, 获得一组确定解P (t0) , 并对其进行适应度评估;
3) 记录最优个体及其适应度;
4) 判断是否满足终止条件, 若满足, 则结束程序;否则, 利用预先设定的量子旋转门调整策略对个体实施调整, 得到新的种群X (k (10) 1) , 并返回步骤2。
2 仿真实验与性能分析
选取典型的多峰函数Shubert[6]进行仿真测试, 其表达式为:
该函数共760个局部极小值, 其中全局最小值18个, 理论上的全局最小解fmin〔x1, x2〕=-186.731, 其三维图形如图2所示。
为了验证本算法的优越性和有效性, 本文采用SGA和QGA对Shubert函数进行同条件比较, 主要参数设置如下:最大遗传代数为200, 种群大小为40, 交叉概率cp=0.7, 变异概率mp=0.05。运行4次后, 两种算法的优化结果分别如表2、表3所示, 进化过程分别如图3、图4所示。
可以看出:标准遗传算法的优化结果不稳定, 甚至偏离了理论最优解;而量子遗传算法稳定性较好, 收敛速度快。
4 结束语
针对多峰函数的寻优问题, 提出了一种量子遗传优化算法, 该算法将量子的态矢量表达引入到遗传编码中, 既增加了染色体的多样性又减小了种群规模, 通过量子旋转门调整策略更新种群, 从而实现对目标函数的优化。仿真结果表明该优化算法具有较高的搜索效率, 能跳出局部最优, 收敛速度快, 在多峰函数寻优中显示出了优良的特性。
参考文献
[1]P.W.Shor.Algorithms for quantum computation:Discrete logarithms and factoring.Proc.of the 35th Annual Symp.on Foundations of Computer Science.New York, USA:IEEE Computer Society Press.1994:124-134.
[2]L.K.Grover.A fast quantum mechanical algorithm for database search.Proc.of the 28th Annual ACM Symp.on Theory of Computing.New York, USA:ACM Press.1996:212-219.
[3]杨俊安, 庄镇泉.量子遗传算法研究现状[J].计算机科学, 2003, 30 (11) :13-15, 43.
[4]董武世, 柯宗武, 陈年生.基于量子遗传算法的QoS多播路由算法[J].计算机工程与应用, 2007, 43 (27) :144-147.
[5]孟维嘉, 庞伟正.基于量子遗传算法的多约束QoS路由算法[J].应用科技, 2007, 34 (3) :11-14.
函数优化的遗传算法 篇5
研究在造价、体积和重量约束条件下,多级串联系统和桥式网络系统可靠性优化问题.使用遗传算法对该问题进行求解,利用基于排名的选择方法和最优保存策略,改善了遗传算法的收敛性能.计算机仿真实验结果表明,用遗传算法求解该问题是有效的.
作 者：张铁柱 滕春贤 韩志刚 作者单位：张铁柱,滕春贤(哈尔滨理工大学,系统工程研究所,黑龙江,哈尔滨,150080)
韩志刚(黑龙江大学,应用数学研究所,黑龙江,哈尔滨,150080)
函数优化的遗传算法 篇6
DOI：10.13340/j.jsmu.2016.04.001
文章编号：1672-9498（2016）04000106
摘要：为实现远洋渔船船队调度路径优化，提高调度工作效率，减少船队的运营成本，对远洋渔船船队调度路径问题建立数学模型.运用在选择和交叉策略上改进的遗传算法对模型进行求解.仿真结果表明，改进的遗传算法能有效解决传统的遗传算法易陷入早熟收敛的问题.利用该算法能快速生成具体的调度方案，且使运营成本减少，可有效解决远洋渔船船队调度路径问题.
关键词：
远洋渔船船队； 数学模型； 船队调度； 路径优化； 改进遗传算法
中图分类号： U692.4 文献标志码： A
收稿日期： 20160322
修回日期： 20160504
基金项目：
国家远洋渔业工程技术研究中心开放基金（02091305051）；上海市科学技术委员会创新行动计划（15DZ1202202）
作者简介：
陈成明（1978—），汉，安徽萧县人，讲师，博士，研究方向为物联网工程、人
因工程，（Email）cmchen@shou.edu.cn
虞丽娟（1963—），汉，浙江义乌人，教授，博导，博士，研究方向为物联网工程、海洋工程、体育工程和高等教育管理，（Email）ljyu@shou.edu.cn
0引言
远洋渔业资源是人类社会的宝贵财富，大力发展远洋渔业，合理开发利用远洋渔业资源，有利于缓解我国人均资源短缺问题，保障优质动物蛋白供给.同时，发展远洋渔业不仅能带动船舶及装备设计制造、水产品冷藏加工和物流等相关产业的发展，而且对建设现代渔业、促进经济社会发展、增加农渔民就业和收入、调剂国内市场水产品供给等也具有重要意义[1].
组建远洋渔船船队会极大地提升我国远洋渔业的国际竞争力，我国很多沿海城市已拥有或正在建设大规模的远洋捕捞船队.经调研发现，目前远洋渔船船队调度大多依靠调度员人工调度，这种调度方式不仅效率低且调度方案缺乏科学性.在当今信息技术快速发展的环境下，如何利用计算机技术实现远洋渔船船队调度路径优化，快速调整资源配置，提高调度工作效率，减少船队运营成本，成为许多远洋渔业企业的重大课题.
目前国内外对船队调度路径问题的研究并不多，对远洋渔船船队调度路径优化问题的研究更是少之又少.对船队调度的研究主要是对商船船队调度优化问题的研究[2].商船多以运输货物为主，受最大载重量限制，出航一次只能运载容量限定的货物.然而，远洋渔船是靠出海捕捞获得渔获物的，因为渔获物可以由补给船带回，所以渔船会在达到或超过规定捕捞任务量时返回.远洋渔业企业捕捞特定鱼种会用专门的船队，比如捕捞金枪鱼要用金枪鱼捕捞船队.大型渔场内有很多捕捞点，这些捕捞点一年中会有几个月的渔汛期，即捕捞带有时间窗约束[34]，因此对商船船队调度问题的研究不适用于远洋渔船船队.对路径优化问题的研究主要有旅行商问题（Traveling Salesman Problem，TSP）、车辆路径问题（Vehicle Routing Problem， VRP）等.虽然远洋渔船船队调度路径问题与VRP比较相似，都是按照路径最优原则分配给多目标，但与VRP还是有一定区别的.VRP是送货问题，车辆受最大载重量限制，根据客户需求将定量的货物送出，送完即可返回；远洋渔船船队调度问题是收货问题，是将鱼捕捞到船上储存起来，部分渔获物可以由补给船带回，当渔船捕捞总量达到或超过任务量时返回.解决路径优化问题有很多方法，如遗传算法、蚁群算法、粒子群算法和模拟退火算法[59]，遗传算法是其中比较常见的方法.
遗传算法是根据达尔文的进化论提出的类似生物进化过程的算法.作为一种智能全局优化搜索算法，遗传算法拥有简单通用、鲁棒性强、适用于并行处理以及效率高等特点.遗传算法也有缺点，如局部搜索能力差、编码较难、容易出现早熟现象，需要根据具体问题调整选择、交叉和变异策略，例如：刘芳华等[10]利用改进的遗传算法对物流配送路径进行优化，发现采用改进编码方案和选择算子能使遗传算法有更好的收敛性；廖良才等[11]基于混合遗传算法对物流配送车辆调度优化问题进行求解，发现采用遗传算法与节约算法相结合的混合遗传算法能够增强局部搜索能力.在对远洋渔船船队调度路径问题进行分析的基础上，本文采用在选择和交叉策略上改进的遗传算法（采用带精英策略的选择算子和具有自适应能力的交叉算子）来解决早熟收敛问题.
1建立数学模型
1.1问题描述
研究远洋渔船船队调度路径问题的目的是使
船队的路线调度方案
运营成本较小.根据对船队运作具体情况的分析，远洋渔船船队调度路径问题主要有以下特点：
（1）准时性.
渔船如果未能在渔汛期到达捕捞点，若要完成同样的捕捞任务，则需投入更多的成本，因此应将时间窗的惩罚成本加入到目标函数中.
（2）路径最短.
远洋渔船调度要考虑渔船闲置费用、渔船启用成本等，但远洋渔船出海捕鱼最主要的成本是油耗成本.油耗量与航行距离成正比，因此应采用路径优化方法减少船队总的航行距离.
（3）渔船资源利用最大化.
要扩大远洋渔船船队的规模，即要尽可能多地派出渔船出海捕鱼，这是因为渔船不出海作业会产生闲置费、折旧费、维护费等费用，且不会产生任何经济效益.目前，远洋渔业资源较为丰富，虽然渔船出海作业会有启用成本，但捕鱼收益要远大于启用成本和渔船消耗所造成的成本，因此应尽可能多地利用渔船资源.
根据上述特点，可以将远洋渔船船队调度路径问题描述为：某中心港口拥有相同型号、捕捞同一鱼种的渔船船队，渔船被派遣到多个捕捞点（一个捕捞点只派遣一艘渔船）进行捕捞作业，渔船完成捕捞任务量即可返回；根据鱼情信息和往年数据，可估计渔船在某捕捞点的渔获量，每个捕捞点会有渔汛期，渔船应尽量在渔汛期内到达捕捞点.根据以上描述可将问题转化为带时间窗的远洋渔船船队调度路径优化问题，即在满足渔汛期时间窗和渔船任务指标的条件下，确定一套从中心港口到渔场各捕捞点的调度路径方案，最大限度地减少船队的运营成本.
1.2模型假设
（1）船队的渔船为同一型号，比如都是捕捞鱿鱼的或都是捕捞金枪鱼的；
（2）根据鱼情信息和往年数据，确定渔场的捕捞点；
（3）取渔船航行的平均速度为计量速度；
（4）只有一个中心港口，每条航线的开始和结束位置都在这个中心港口；
函数优化的遗传算法 篇7
关键词：遗传算法,样条函数,拱轴线
关于拱的合理形式, 长期以来人们作了很多研究, 以往多采用悬链线作为拱轴线, 三次样条函数作为拱轴线也有它的合理和有效性。最理想的拱轴线是与拱上各种荷载作用下的压力线相吻合的, 这时主拱圈截面只有轴向压力, 而无弯矩和剪力作用, 应力均匀, 能充分利用圬工材料的强度和抗压性能[1]。但事实上, 这样的拱轴线是不可能获得的, 因为主拱圈除了承受荷载作用外, 还要承受活载、温度变化和材料收缩等因素的作用, 当恒载压力线与拱轴线吻合时, 在活载作用下就不再吻合了;又因为相应于活载的各种不同布置, 压力线也是不相同的。
空腹式拱桥的恒载自拱顶向拱脚不再是连续分布的, 其空腹部分的荷载由两部分组成, 即拱圈自重的分布荷载和拱上立柱 (或横墙) 传来的集中荷载。其相应的恒载压力线, 也不再是一条平滑的悬链线, 而是一条在腹孔墩处有转折的多段曲线。所以采用三次样条函数曲线作为拱轴线是合理的。在进行拱桥设计时, 可以计算出压力线上的一些点, 但是这些离散点通常不在一条拱形曲线上。用插值法通过这些点配出一条曲线, 这条曲线将是弯曲的 (如图1所示) 。
这样一条曲线不能作为拱轴线, 自然人们会期望构造出一条拱轴线来, 并且尽可能逼近已经规定出来的压力线。通常的方法是用悬链线作拱轴线来逼近。一般用“五点法”[2]。拱顶、四分点、拱脚五点重合, 然后利用由此确定的悬链线来计算各项内力, 且在空腹式拱桥中, 用五点重合法确定的悬链线拱轴, 其偏离弯矩对拱顶和拱脚都是有利的。但以往手工计算中, 需先假定一个m值定出拱轴线, 使之满足判别条件∑M1/4/∑Mj=y1/4/f, 若判别条件不满足时重新选择拱轴系数, 由于m假定的不同, 这个过程往往不止计算一次而且需查阅拱桥手册, 使求解过程复杂。本文应用遗传算法优化样条函数来作最优拱轴线, 从而为日后桥梁设计师在拱桥设计过程中增加一种方法。
1 设计方法及数学模型
如何逼近:假如我们规定了压力线上的n+1个点 (xi, yi) (0≤i≤n) 。使用
f (xi) 与yi的数值是不完全相同的, 我们称它们之间的差的绝对值为残差[3], 记作:
显然, 残差的大小是衡量被确定的待定系数好坏的标志。这里的残差实际上就是压力线与拱轴线的偏离。我们不妨认为待定系数的确定, 将使残差最大的一个达到最小, 即
这就意味着使得配出来的拱轴线与恒载压力线或与恒载加活载的压力线包络线的最大偏离达到最小。这样设计出来的拱轴线将具有最优良的受力性能, 不妨称它为最优拱轴线。由于 (xi-xj) +=xi-xj, i≥0; (xi-yi) +=0, i≤0, 可以把式 (3) 化为:
这个不等式里A0, A1, …, An是待定系数, λ是满足式 (1) 的所有λ中最小的一个, 也是需要确定的, 即ϕ (λ, A0, A1, …, An) =λ为最小。应用遗传算法对该样条函数及λ作局部优化使三次样条函数更有效的逼近那些离散的压力线上的点, 使得在局部范围内该三次样条函数作为最优拱轴线是有意义的。
2 算例
2.1 设计条件假定
四肋拱桥如图2所示。
计算跨径l=30 m, 二铰拱, 拱圈为矩形断面, 其尺寸为H=0.8 m, B=0.4 m;等距离布置6根立柱, 立柱为矩形断面, 其尺寸为H=0.4 m, B=0.4 m。桥面系形式不拘, 但假定为相当于H=1.1 m, B=0.8 m的连续梁作用于立柱。
2.2 荷载条件假定
1) 恒载:
施工分两阶段, 一阶段是拱肋和立柱, 二阶段是桥面系。
2) 荷载等级:
公路Ⅱ级, 横向分布系数0.35。
2.3 约束条件假定
拱肋, 立柱允许应力为σmax=9 MPa, σmin=-0.8 MPa;桥面系允许应力σmax=9 MPa, σmin=-2.8 MPa。根据已知拱桥理想拱轴线的设计原理, 求出压力线点坐标, 如表1所示。
应用遗传算法原理对式 (3) , 约束条件 (4) 及式
3 结语
应用遗传算法解样条函数作为拱桥的拱轴线是合理的, 也是误差比较小的一种方法。此外在拱圈内力调整方面, 样条函数拱轴线具有更大的优越性。当拱圈在弹性压缩及温度变化、材料收缩、活载等作用下, 都可能使原先相吻合的拱轴线与压力线又产生偏移。当某局部拱轴线上其偏离值超过了容许值时, 只需调整此局部拱轴纵坐标, 即可达到减小偏离的目的。而悬链线拱轴线常采用的假载法, 则因其线型所限制, 必须重新调整全拱轴坐标, 无法局部改善拱轴受力状况。
参考文献
[1]汪莲.桥梁工程[M].合肥:合肥工业大学出版社, 2006.
[2]范立础.桥梁工程 (下册) [M].第2版.北京:人民交通出版社, 1987.
[3]李志文.桥梁结构优化设计基础[M].北京:人民交通出版社, 1999.
函数优化的遗传算法 篇8
在石油勘探等领域的科学研究和工程设计中,很多问题是以非线性数学模型来描述其本质,将该模型线性化处理后,对这些数学模型求解就可归结为对各种大型线性方程组的求解问题。然而有些时候这样的线性方程组的系数矩阵确是病态的。对于严重病态的线性方程组在使用直接解法和迭代法求解时,数值解的误差非常大,甚至是失真的。为了提高病态线性方程组数值解的精度,研究人员尝试使用遗传算法等一类的进化算法进行求解[1,2,3,4]。
遗传算法是一种基于自然选择和遗传机制的随机搜索算法[5]。遗传算法从一组给定的随机产生的种群作为初始解开始搜索过程,通过选择、交叉和变异来产生新的种群个体。这些新的个体中具有更好的适值的那些个体将存活下来并遗传到下一代。通过这样一代一代地进化,最后算法收敛于最好的那些个体就作为求解问题的最优解或次优解。
然而简单遗传算法使用的选择算子,交叉算子和变异算子都具有固定的概率,进化过程会产生“早熟现象”,即数据解收敛到局部最优解而无法跳出,并收敛到全局最优解。尤其对于严重病态的线性方程组,当运行简单遗传算法时,算法迅速早熟并陷入进化停滞状态。此时数值解的误差非常大,甚至产生失真。本中提出一种结合惩罚函数最佳个体保留和种群迁移措施的改进遗传算法,该算法从一定程度上提高了其自身的自适应性,进而从一定程度上克服简单遗传算法的“早熟”现象。
1 适应度函数设计
生物种群中优胜劣汰的依据是个体对环境的适应程度。较好地适应环境的个体得以生存下来,而不能适应环境的个体被淘汰出局。在遗传算法中引入了适应度函数来度量种群个体的适应程度。选择算子主要根据计算出的每个个体的适应度值的大小来进行选择。适应度较高的个体遗传到下一代的概率就较大,反之,则较小。考虑如下形式线性方程组:
要想使用遗传算法来求解方程组(4),需要将方程组(4)求解问题转换为函数优化问题。假设右端向量为一组真解代入方程组(1)后所得,则将数值解代入方程组(1)后,可得各部分残差:
2 遗传算子设计
同传统优化算法寻优过程不同,遗传算法无需借助一阶或者二阶导数来确定寻优的方向。它是使用遗传算子模拟生物进化的过程来求得问题的最优解。每进化出来新一代中那些具有更高的适值的子代以更高的概率被保留,而那些具有更低适值的子代以更高的概率被舍弃。通过每一代的优胜劣汰的过程来使初始种群(问题的初始解)逐渐向最优解逼近。一般来说,一个完整的遗传算法中应该包含三个遗传算子:选择算子,交叉算子和变异算子。
2.1 选择算子
从群体中选择优胜的个体,淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子。选择的目的是把优化的个体(或解)直接遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的,选择算子通过对个体的适值进行计算,保留那些适值比较高的个体遗传到下一代,而淘汰那些适值比较低的个体。文中选择算子采用随机遍历抽样法。随机遍历抽样法的特点是对于不同适值的个体,被选中的机会是均等的,所以在遗传算法进化的过程中,种群的多样性的保持可以相对持久,这会提高算法抗“早熟”的能力。随机遍历抽样法原理如下:
它使用N个相等距离的指针[ptr,ptr+1,ptr+2,…,ptr+N-1],这里N是要求选择的个数。第一个指针位置由[0,1/N]区间的均匀随机数确定,指针之间的距离为1/N。哪个个体落在N个指针所指的范围内,该个体被选中。
由于交叉操作和变异操作的随机性,那些在进化早期的适值比较差但是却包含最终最优解的个体可能会被淘汰掉。为了降低这种风险,文中采用两种措施:一是最佳个体保留策略,一是惩罚函数。最佳个体保留策略是进化的每一代中选择若干个适值最大的个体不参与交叉和变异操作,直接进入下一代。实验结果表明最佳个体的数量需要仔细确定。数量太多可能会使那些属于局部最优解的个体迅速地占据种群的主导地位,降低了种群多样性,出现“早熟”。而最优个体数量太少,又达不到保护优良个体的目的。使用惩罚函数的目的是对于适值比较差的的那些个体不是简单地淘汰掉,而是将其适值减去一个固定的值,使之变得更小,但是仍然保留了遗传到下一代的机会,保护了在进化过程中虽然适值比较差但是却包含了优良模式的那些劣势个体,很好地维护了种群的多样性。加入惩罚函数后的适应度函数表达式如公式(4)所示:
式中:F′(x)为修正后的适应度函数,P(x)惩罚函数。当P(x)满足约束条件,P(x)=0,否则,P(x)=100。
2.2 交叉算子
在自然界生物进化过程中起核心作用的是生物遗传基因的重组。同样,遗传算法中起核心作用的是遗传操作的交叉算子。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。交叉操作是遗传算法产生新个体的主要方法,它提高了算法在解空间中的全局搜索能力。按照种群个体编码方式的不同,有不同的交叉算法,由于本文中种群个体为实数编码,所以交叉算子使用中间重组[6]。并且文中求解的病态线性方程组的解有均大于等于0的约束,所以子个体按如下公式产生:
子个体=|父个体1+α*(父个体2-父个体1)|(5)
式中:α为比例因子。
2.3 变异算子
变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。遗传算法引入变异的目的有两个:一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时,利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然,此种情况下的变异概率应取较小值,否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可维持群体多样性,以防止出现“早熟”现象。此时收敛概率应取较大值。遗传算法中,交叉算子因其全局搜索能力而作为主要算子,变异算子因其局部搜索能力而作为辅助算子。遗传算法通过交叉和变异这对相互配合又相互竞争的操作而使其具备兼顾全局和局部的均衡搜索能力。本文变异算子使用高斯变异算法,把算法产生基于高斯分布的具有均值0的随机数加到父代的个体上,从而产生出新的子代。高斯变异算子能够根据进化的代数控制每一代种群中个体的方差。方差计算公式见公式(6)所示:
式中:G是进化总代数,s是方差的收缩率,k是当前代数。如果s=1,则最后一代种群的方差为0。从公式(5)可得知:进化初期种群个体方差大,种群个体多样性强,搜索能力强,随着进化代数的增加,种群的方差逐渐减小,种群中个体多样性降低,种群个体逐渐收敛于最优解附近。这样就降低了算法在进化后期陷入随机搜索的概率。
为了减少交叉操作和变异操作对个体中良好模式的破坏,在文中提出的IGA算法中也使用了种群迁移策略,将每一代中最好的若干个个体直接迁移到下一代中,而不参与交叉和变异运算。迁移的个数取决于两个参数:迁移间距,即两次迁移要隔多少代发生;迁移比率,即第n代向第n+1代迁移的百分比。
3 实验结果及分析
为了验证IGA算法的有效性,本文以核磁共振测井回波线性方程组为例,在Matlab环境中编写了适应度函数,IGA算法和SGA算法对应的程序,对二者的求解结果进行了对比测试。核磁共振测井回波线性方程组的系数矩阵为如下形式:
式中:i=1,2,…,1000,j=1,2,…,30。T2j是布点数据。经过计算,该系数矩阵A的条件数cond(A)=2.3361×1016>>1,所以该线性方程组严重病态。该方程组的右端向量是人为给定一组真解,代入该方程中得到。并且为了验证IGA算法对病态线性方程组求解的有效性,还在右端向量上添加了信噪比为50%的高斯噪声。IGA与SGA算法求解结果对比图见图1所示。
4 结论
虽然遗传算法是并行的全局搜索算法,但是由于简单遗传算法容易产生“早熟”现象,特别是求解严重病态线性方程组时,算法迅速出现“早熟”而陷入进化停滞状态。文中通过在设计的遗传算子中加入惩罚函数,最优个体保留和种群迁移等措施,在一定程度上提高算法抗“早熟”能力,对数值解的精度有所提高。进一步的研究工作可以将遗传算法和某种传统的局部寻优算法结合起来。在遗传算法停止后,再使用局部优化算法对遗传算法计算的数值解,做局部精细化寻优,可以进一步提高数值解的精度。
参考文献
[1]殷福亮,殷福新,林淑云.解病态线性方程组的遗传算法[J].大连理工大学学报,1994,34(6):732-736.
[2]郝博,胡玉兰,卢有文,聂义勇.用遗传算法解病态线性方程组的研究[J].计算机工程与设计,1998,19(3):19-21.
[3]黄松奇,黄守佳.用遗传算法求解病态线性方程组[J].数学的实践与认识,2003,33(8):97-100.
[4]赖鑫生,谭国律,周玉林.用遗传算法解大规模病态线性方程组[J].上饶师范学院学报,2006,26(6):85-88.
[5]玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社,2000:1-25.
[6]雷英杰,张善文,李继武等.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社.2005:52-55.
论不可微函数的一种混合遗传算法 篇9
关键词：全局最优,混合算法,遗传算法,Powell方法
1 引言
遗传算法是从代表问题可能潜在的解集的一个种群 (population) 开始的, 而一个种群则由经过基因 (gene) 编码的一定数目的个体 (individual) 组成。每个个体实际上是染色体 (chromosome) 带有特征的实体。染色体作为遗传物质的主要载体, 即多个基因的集合, 其内部表现 (即基因型) 是某种基因组合, 它决定了个体的形状的外部表现, 如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此, 在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂, 我们往往进行简化, 如二进制编码, 初代种群产生之后, 按照适者生存和优胜劣汰的原理, 逐代 (generation) 演化产生出越来越好的近似解, 在每一代, 根据问题域中个体的适应度 (fitness) 大小选择 (selection) 个体, 并借助于自然遗传学的遗传算子 (genetic operators) 进行组合交叉 (crossover) 和变异 (mutation) , 产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境, 末代种群中的最优个体经过解码 (decoding) , 可以作为问题近似最优解。
不可微非线性函数优化问题具有广泛的工程和应用背景, 如结构设计中使得结构内最大应力最小而归结为极大极小优化 (minmax) 问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视, 常用的算法有模式搜索法、单纯形法、Powell方法等, 但是这些方法都是局部优化方法, 优化结果与初值有关。
近年来, 由Holland研究自然现象与人工系统的自适应行为时, 借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法, 是一种较为有效的求不可微非线性函数全局最优解的方法。以遗传算法为代表的进化算法发展很快, 在各种问题的求解与应用中展现了其特点和魅力, 但是其理论基础还不完善, 在理论和应用上暴露出诸多不足和缺陷, 如存在收敛速度慢且存在早熟收敛问题。为克服这一问题, 早在1989年Goldberg就提出混合方法的框架, 把GA与传统的、基于知识的启发式搜索技术相结合, 来改善基本遗传算法的局部搜索能力, 使遗传算法离开早熟收敛状态而继续接近全局最优解。近来, 文献[3]和[4]在总结分析已有发展成果的基础上, 均指出充分利用遗传算法的大范围搜索性能, 与快速收敛的局部优化方法结合构成新的全局优化方法, 是目前有待集中研究的问题之一, 这种混合策略可以从根本上提高遗传算法计算性能。文献[5]采用牛顿-莱佛森法和遗传算法进行杂交求解旅行商问题, 文献[6]把最速下降法与遗传算法相结合来求解连续可微函数优化问题, 均取得良好的计算效果, 但是不适于不可微函数优化问题。
本文提出把Powell方法融入浮点编码遗传算法, 把Powell方法作为与选择、交叉、变异平行的一个算子, 构成适于求解不可微函数优化问题的混合遗传算法, 该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。
2 混合遗传算法
编码是遗传算法应用中的首要问题, 与二进制编码比较, 由于浮点编码遗传算法有精度高, 便于大空间搜索的优点, 浮点编码越来越受到重视。考虑非线性不可微函数优化问题 (1) , 式中n为变量个数, xundefined、xundefined分别是第i个变量xi的下界和上界。把Powell方法嵌入到浮点编码遗传算法中, 得到求解问题 (1) 如下混合遗传算法:
minf (x) =f (xi, x2, …, xn) xundefined≤xi≤xuii-1, 2, …, n (1)
step1给遗传算法参数赋值。这些参数包括种群规模m, 变量个数n, 交叉概率pc、变异概率pm, 进行Powell搜索的概率pPowell和遗传计算所允许的最大代数T。
Step2随机产生初始群体, 并计算其适应值。首先第i个个体适应值取为fi′=fmax-fi, fi是第i个个体对应的目标函数值, fmax为当前种群成员的最大目标函数值, i=1, 2, …, m。然后按Goldberg线性比例变换模型式 (2) 进行拉伸。
fi'=a·fi'+b (fi≥0) (2)
step3执行比例选择算子进行选择操作。
step4按概率pc执行算术交叉算子进行交叉操作。即对于选择的两个母体sundefined和sundefined, 算术交叉产生的两个子代为sundefined+r·sundefined+ (1-r) ·sundefined和sundefined=r·sundefined+ (1+r) ·sundefined, r是[0, 1]上的随机数, 1≤i, j≤m。
step5按照概率pm执行非均匀变异算子。若个体sundefined= (v1, v2, …, vk, …, vn) 的元素vk被选择变异, vk∈[xundefined, xundefined], 则变异结果为sundefined= (v1, v2, …, vk, …, vn) , 其中
undefined
Δ (t, y) 返回区间[0, y]里的一个值, 使Δ (t, y) 靠近0的概率随代数t的增加而增加。这一性质使算子在初始阶段均匀地搜索空间, 而在后面阶段非常局部化。r是[0, 1]之间的随机数, T为最大代数, b为决定非均匀度的系统参数。
step6对每个个体按照概率pPowell进行Powell搜索。若个体sundefined被选择进行Powell搜索操作, 则以sundefined作为初始点执行Powell方法得sundefined, 若xundefined≤sundefined≤xundefined则把所得计算结果sundefined作为子代sundefined, 否则, 若sundefined≤xundefined取sundefined=xundefined;若sundefined≥xundefined取sundefined=xundefined, 1≤i≤m。
step7计算个体适应值, 并执行最优个体保存策略。
step8判断是否终止计算条件, 不满足则转向step3, 满足则输出计算结果。
作为求解无约束最优化问题的一种直接方法, Powell法的整个计算过程由若干轮迭代组成, 在每一轮迭代中, 先依次沿着已知的n个方向搜索, 得一个最好点, 然后沿本轮迭代的初始点与该最好点连线方向进行搜索, 求得这一阶段的最好点。再用最后的搜索方向取代前n个方向之一, 开始下一阶段的迭代。为了保持算法中n个搜索方向是线性无关的, 保证算法的收敛性, 对替换方向的规则进行改进, 在混合法的计算步骤step6中采用文[9]中的改进Powell方法, 其求解过程如下:
(1) 变量赋初值x0, n个线性无关的n个方向d1, 1, d1, 2, …, d1, n, 和允许误差ε>0, 令k=1。
(2) 令x (k, 0) =x (k+1) , 从x (k, 0) 出发, 依次沿方向d (k, 1) , d (k, 2) , …, d (k, n) 作一维搜索, 得到点x (k, 1) , x (k, 2) , …, x (k, n) 求指标m, 使得f (x (k, m-1) ) -f (x (k, m) ) =max{f (x (k, j-1) ) -f (x (k, j) ) }, 令d (k, n+1) =x (k, n) -x (k, 0) 。若||x (k, n) -x (k, 0) ||≤ε, 则Powell方法计算结束, 否则, 执行 (3) 。
(3) 求λn+1使得f (x (k, 0) +λn+1d (k, n+1) ) =minf (x (k, 0) +λd (k, n+1) ) , 令x (k+1, 0) =x (k) =x (k, 0) +λn+1d (k, n+1) , 若||x (k) -x (k-1) ||≤ε, 则Powell方法计算结束, 得点x (k) ;否则, 执行 (4) 。
(4) 若λ, 否则令d (k+1, j) =d (k, j) (j=1, 2, …, n) , 然后置k=k+1,
3 算例
undefined
函数f (x) 有相当多的极小点, 全局极小点是xi=-420.97, i=1, 2, …, n, 最优值为-837.97;次最优点为xi={ (xi1, xi2, …, xin) :xij=-420.97, j≠i, xii=302.52}, i=1, 2, …, n, 次优值-719.53。变量个数n=2时函数f (x) 特性如图1示。程序编制和运行环境采用Fortran Power Station4.0, 随机数由内部随机函数产生, 在奔腾133微机上运行。
采用改进的Powell方法计算100次, 初值在区间[-500, 500]内随机产生, 只有6次 (即以概率0.06) 搜索到全局最优, 计算成功的概率极低。
Holland建立的标准 (或简单) 遗传算法, 其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。取种群规模m=30, 交叉概率pc=0.95、变异概率pm=0.05, 最大进化代数T=1000, 每个变量用串长为L=16的二进制子串表示。二进制编码比浮点编码遗传算法计算精度低, 对于标准遗传算法以目标函数小于-800为搜索成功, 标准遗传算法运行100次。当取最大进化代数为T=200时, 40次 (以概率0.40) 搜索到全局最优, 平均计算时间为0.51秒;当取T=500时, 51次 (以概率0.51) 搜索到全局最优, 平均计算时间为1.13秒。
采用本文混合法计算, 取m=30, pc=0.85、pm=0.2, T=100, 进行Powell搜索的概率pPowell取不同值, 混合法运行100次, 计算结果见如表1。对于这个具有多极值的算例, 多次计算表明pPowell=0.3时, 混合法能以完全概率搜索到全局最优的准确值, 但是此时混合法计算时间约为标准遗传算法取T=500时计算时间的4/5。对应的浮点编码遗传算法, 取m=30, pc=0.85、pm=0.2, T=100, 运行100次, 82次 (以概率0.82) 搜索到全局最优 (如表1中PPowell=0所示) , 计算时间约为标准遗传算法取T=500时计算时间的1/8, 但是搜索到全局最优的概率却远远高于标准遗传算法。
4 结语
针对不可微函数的全局优化问题, 本文提出一种把Powell方法与浮点编码遗传算法相结合的混合遗传算法, 该算法兼顾了遗传算法全局优化方面的优势和Powell方法局部搜索能力较强的特点, 提高求得全局解的概率。计算结果表明混合法优于遗传算法和Powell法, 可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息, 本文混合法不仅适用于不可微函数优化问题, 也适合可微函数全局优化问题。
参考文献
[1]周明, 孙树林.遗传算法原理及应用[M].北京:国防工业出版社, 1999.
[2]孟庆春, 贾培发.关于Genetic算法的研究及应用现状[M].北京:清华大学出版社, 1995, 35 (5) :44-48.
[3]戴晓晖, 李敏强, 寇纪松.遗传算法理论研究综述[J].控制与决策, 2000, 15 (3) :263-268.
[4]赵明旺.连续可微函数全局优化的混合遗传算法[J].控制与决策, 1997, 12 (5) :589-592.
函数优化的遗传算法 篇10
1 函数型小波神经网络
2 基于多值编码的遗传算法优化小波神经网络
遗传算法是全局优化算法, 目标函数既不要求连续, 也不要求可微, 仅要求问题可计算。本文提出的遗传小波神经网络在WNN的学习过程中将网络结构、权值因子、尺度因子和平移因子描述为染色体, 并选取适当的适应度函数, 然后进行GA迭代, 直到网络收敛得到最优值。
2.1 多值编码方式
因此本文提出了二进制与实值编码共存的多值编码方式。GA的一个染色体对应一个待求解问题的解。
2.2 适应度函数
适应度函数对遗传算法有全局性的影响, 是算法成功求得全局极值的关键之一。WNN的一个重要特点就是网络的实际输出值与期望的输出值之间的误差平方和越小, 表示网络性能越好, 这里定义适应度函数为式中, y (i) '为网络对应第i个输入样本点的实际输出, y (i) 为期望输出, F为网络误差 (能量函数) 加1的倒数, L为总的学习样本数。这样, 可以保证通过该适应度函数所选择出的优质个体的网络误差较小。
2.3 交叉
由于对WNN的参数和结构采用多值编码方式, 因此在进行交叉运算时, 需判断交叉基因位的编码方式, 如果交叉基因采用实值编码, 交叉操作可采用线性组合的方式。例如, 设t为进化代数, xit和xjt分别为两个被选择进行交叉的父代个体, 则交叉产生的子代个体xit+1和xjt+1分别为:xit+1=pcxit+ (1-pc) xjt1) xjt+1=pcxjt+ (1-pc) xit2) pc为交叉的概率。如果交叉的基因位采用二进制编码, 则调用库函数中的单点交叉函数操作。
2.4 变异
在变异操作时, 也要判断该基因的编码方式, 变异位为二进制编码时, 以一定的概率pm对其进行求反运算。变异位是实值编码时, 则采用下式进行变异操作:
式中为均匀分布的随机数。
2.5 选择
采用适应值排名, 最优保存策略与比例选择机制相结合的选择策略。这样即可抑制比例选择机制的过早收敛和停滞现象, 又可以克服交叉、变异带来的随机漫游现象, 加快收敛速度。
2.6 动态调整隐层节点及连接权个数
对交叉变异之后的染色体, 根据第二段基因中0和1的总数m, 分别把第一段基因中权值分为m份, 这m个实数分别代表隐层与前后两层的连接权值。判断第二段基因编码中第i个基因是否为0, 如果是, 则将与其相应的权值全部置为0。如果为1, 则不做任何改变。
3 实验仿真
为了验证本文所描述方法的有效性, 本文选择Mackey-glass时延微分方程进行预测, Mackey-glass混沌时间序列可由时滞微分方程得到:
令α=0.2, β=0.1, γ=10, γ为唯一可调参数, Mackey-Glass方程称为时滞参数γ的函数, 当γ>16.8时方程3) 产生混沌现象。因此采用γ=17时Mackey-Glass混沌时间序列。这里采用4阶Runge-Kutta方法求解, 即根据以下的方程式:
可以得到方程5) 的数值解, 为训练网络产生训练数据集和检验数据集。时间序列预测任务是用时刻之前的值, 对未来时间t+p内的值进行估计。一般这类问题的标准方法是, 建立当前时刻t以前的D个点x (t- (D-1) △, …, x (t-△) , x (t) 到未来时间的映射关系。通常情况下, p=△。在本次得到一个“4输入-1输出”的格式, 在这里选取了D=4, p=6, 我们抽取了1500组数据, 则其输入输出的具有如下的格式xΣ (t-18) , x (t-12) , x (t-6) , x (t) ;x (t+6) Σ:
4 结论
针对小波神经网络的优化问题, 本文提出了用多值编码的遗传算法来优化网络的结构和参数, 结果表明了采用该多值编码优化的小波神经网络具有更好更稳健。
参考文献
[1]黄敏, 方晓柯, 王建辉, 顾树生.基于多值编码的混合遗传算法的小波神经网络优化[J].系统仿真学报, 2004.
[2]何永勇, 褚福磊, 钟秉林.进化小波网络及其在设备状态预测中的应用[J].机械工程学报, 2002.
[3]董富贵, 张世英, 谭忠富, 张文泉.基于遗传算法的小波神经网络在电价预测中的应用[J].计算机工程, 2005.
[4]王伟, 王科均, 邵克勇.混沌时间序列的混合粒子群优化预测[J].控制与决策, 2007.
函数优化的遗传算法 篇11
关键词：遗传算法网架结构配电网优化
1 问题的提出
配电系统中的网架结构优化问题主要有两个特点：非线性和整数性，这也正是解决问题的困难所在。用非线性规划方法解题常常会遇到搜索方向错误，迭代不收敛，逼近速度慢等问题。当变量和约束条件数目较多时，这些问题更加突出。另外，线路都是按整回和确定的电压等级来架设的，若变量取线路的某电气量，则变量应是整数值或某种离散值。对于这样的非线性整数规划问题，目前还没有理想的优化算法。若试图严格地解决这种问题，将会遇到一个典型的组合数目以指数形式增长，即所谓“组合爆炸”问题。综观以前的各种传统优化方法，各有优势，要么容易偏离最优解陷入局部最优，要么受到维数的限制而难以达到实用的目的。为了解决这两个方面的问题，下面把遗传算法引入城市电力网网架结构的优化中来，以欺得到一个较满意的解决问题的办法。
2 遗传算法介绍
遗传算法是一种搜索算法，是通过模拟自然进化过程来搜索最优解的方法。其目的是解释自然界的自适应过程而设计的一个体现自然界进化机理的软件系统。大多数生物体是通过自然选择和有性生殖这两种基本过程进行演化的。自然选择决定了群体中哪些个体能够存活并繁殖，即适者生存，不适者淘汰；有性生殖保证了后代基因中的混合与重组，加快了进化过程。由于该方法隐含并行性和全局信息的有效利用能力，尤其适合于处理传统搜索方法解决不了的复杂问题，近十多年來在各领域得到广泛应用。
遗传算子：一个简单的遗传算法由复制、杂交和变异三个遗传算子组成。其中复制算子是把当前群体中的个体按与适应值成正比的概率复制到新群体中去。这样，低适应值的个体趋向于被淘汰，高适应值的个体趋向于被复制，复制算子的作用效果提高了群体的平均适应值，也充分体现了“优胜劣汰”这种自然进化机制；杂交算子是模拟生物界的有性繁殖，可以产生新的个体，使其比它的两个父代有更高的适应值。杂交算子是遗传算法的重要组成部分；变异算子是用一个很小的概率随机地改变染色体串上的位置，其效果是增加群体的多样性，扩大搜索空间。
主要特点：遗传算法与传统的优化算法相比，主要体现在它不是直接作用参变量集上，而是利用参变量集的某种编码；不是从单个点，而是从一个点的群体开始搜索，因而能够快速全局收敛；它还利用了概率转移规则，而非确定性规则，因而能够搜索离散的有噪声的多峰值复杂空间；以及利用适应值信息，无须导数或辅助信息，具有广泛的适应性；在解空间内进行充分的搜索，但并不是盲目地穷举或瞎碰，因此在其搜索时间和效率上往往优于其他优化方法。首先，它在搜索过程中不容易陷入局部最优，即使在所定义的适应函数是不连续的、非规则的或有噪声情况下，它也能以很大的概率找到整体最优解。为了寻找最优解，传统方法是用启发式策略，在单个猜测解的领域寻找，即使算法中允许偶尔地跳到解空间中更远的部分，这些启发式算法也往往趋于局部最优。理论上遗传算法像撒网一样，通过保持在参变量的解空间区域中的多个点的搜索可以以很大的概率找到全局最优解。其次，由于它固有的并行性，遗传算法非常适用于大规模并行计算机。由于遗传算法的操作主要是在单个位串上，至多是一对位串之间的杂交，所以可让每个处理机负责处理单个位串，从而可以并行处理整个群体。
计算步骤：在进行个体遗传算法之前，需要作好如下准备工作。首先是选择编码；一般编码选择由多个二进制串（0，1）构成，其中“0”、“1”分别表示支路不连通和连通。应注意的是编码不局限于二进制，根据对象不同也可选其他的数来编码。其次是确定适应值函数；相当于确定数学规划中的目标函数。然后在选择控制算法的参数；最后确定停止运行的准则。
3 网架结构优化的遗传算法
网络结构优化的目标函数：网络结构优化问题是基于现有网架结构，在已知水平年电源及负荷需求下，并假定变电站的扩建或新建的时间、地点和容量都已确定，决定在规划期内何时何地架设多少回输电线路，以使得线路年费用最小。这里采用考虑了贴现的线路建设投资费用和运行费用的最小年费用法，即。其中Z为方案总的线路建设投资费用，为方案第年的运行费用。
编码的选择：遗传算法是一个搜索特征串空间的过程，其目的是找到具有相对高适应值的串。在应用遗传算法求解特殊问题之前，第一步就要确定用类似于染色体的串来表示问题的办法，即染色体的编码形式。这里采用二进制编码形式，直接对待选线路进行编码，反映其是否架设，以及选用多大截面等。这种编码形式非常直观，便于规划方案和染色体之间的编码和解码。若只考虑线路架设与否，则可将各待选线路排序，然后按此顺序将每条待选线路作为染色体串中的一个基因，每个基因是一个一位的二进制数。当基因值为1时，表示其对应的待选线路被选中加入系统，当基因值为0时，则相反。但考虑到对方案进行评估时需对方案所表示的网络进行潮流分析，这样的染色体解码成规划方案时应能得到线路参数，所以需在基因中加入线路截面的信息。
城网优化遗传算法的计算过程：首先输入原始数据；其中包括网络拓扑，即节点数、已有和待架线路数、各线路的首末节点号和线路的有关参数。节点的发电出力及负荷，遗传算数本身所需参数，即群体大小、基因位数、最大遗传代数、变异率和计算适应函数时用到的有关参数等。然后形成初始方案，接着计算适应值，进行遗传操作，最后输出计算结果。
适应函数的建立：在编码方案选定以后，接着就是要确定适应函数以检测由特定位串所表示的规划方案的好坏程度，从而指引遗传操作的正常进行。适应函数应该反映电网规划的目的和要求，即要使规划方案在满足正常运行要求和安全运行要求的情况下，使电网的建设和运行费用最小。建设费用和运行费用最小的目标函数，在考虑约束条件后的增广函数数学模型为。其中为方案的年费用，为惩罚因子，为方案的约束条件。电网规划的目的是希望电网的建设和运行费用最小，为符合遗传算法最大值的特点，适应函数可表示为。其中的选取以保证为非负数为准。由的表达式可知适应函数是一个非线性的、不连续和非凸的，这对于严格的数学规划方法是难以求解的，而遗传算法则是在解码得到一个解之后才对适应函数进行计算评估的，因此对适应函数形式无任何限制，这充分显示了遗传算法的优越性。
参考文献：
[1]孙杰.基于单亲遗传算法的配电网络优化规划[D].华北电力大学（河北）.2005年.
[2]闫大威.基于遗传算法的城市中压配电网规划自动布线[D].天津大学；2005年.
函数优化的遗传算法 篇12
关键词：小生境遗传算法,罚函数,matlab
1. 引言
生物学上,小生境(niche)是指在特定环境中一种组织(organism)的功能,把有共同特性的组织称作物种(species)。小生境技术就是将每一代个体划分为若干类,每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个群,再在种群中以及不同种群中之间杂交、变异产生新一代个体群。同时采用预选择机制和排挤机制或分享机制完成任务。基于这种小生境的遗传算法(Niching Genetic Algorithms,NGAs),可以更好地保持解的多样性,同时具有很高的全局寻优能力和收敛速度,特别适合于复杂多峰函数的优化问题。常见的小生境遗传算法主要有适应值共享遗传算法、拥挤遗传算法、隔离小生境遗传算法等。在小生境遗传算法中,为了使个体能够在整个约束空间分散开来,更好地维护种群的多样性,有学者提出在传统的小生境遗传算法中引入罚函数的思想。本文从编程角度出发,详细阐述如何使用MATLAB语言实现该算法并给出数值实验测试。
2. 罚函数法
实际应用中的优化问题一般都含有一定的约束条件,它们的描述形式多种多样[1]。在构造遗传算法时,罚函数法是处理约束条件的常用方法之一。
这种处理方法的基本思想是:对在解空间中无对应可行解的个体,计算其适应度时,处以一个罚函数,从而降低该个体的适应度,使该个体被遗传到下一代群体中的机会减少。即用下式来对个体的适应度进行调整:
式中,F(X)为原适应度,f(x)为考虑了罚函数后的新适应度,G(X)为罚函数。
在确定合理的罚函数时既要考虑到度量解对约束条件不满足的程度,又要考虑遗传算法在计算效率上的要求。如果罚函数的强度太小,部分个体仍有可能破坏约束条件,所以保证不了遗传运算所得到的个体一定是满足约束条件的一个可行解;反之,如果罚函数的强度太大,又有可能使个体的适应度差异不大,降低了个体之间的竞争力,从而影响遗传算法的运行效率。
3. 基于罚函数的小生境遗传算法思想
在小生境遗传算法中引入罚函数的目的是为了使个体能够在整个约束空间分散开来,更好地维护种群的多样性。该算法的思想是:首先两两比较群体中各个个体之间的距离,若这个距离在预先指定的距离L之内的话,再比较两者之间的适应度大小,并对其中适应度较低的个体施加一个较强的罚函数,极大地降低其适应度。这样,对于在预先指定的某一个距离L之内的两个个体,其中较差的个体经处理后其适应度变得更差,它在后面的进化过程中被淘汰掉的概率就极大。也就是说,在距离L之内将只存在一个优良的个体,从而维护了群体的多样性,又使得各个个体之间保持一定的距离,并使得个体能够在整个约束空间分散开来。算法的步骤可描述如下:
(1)设置进化代数计数器t=1;随即生成M个初始个体组成初始群体P(t),并求出各个个体的适应度Fi(i=1,2,…,M)。
(2)依据各个个体的适应度对其进行降序排序,记忆前N个个体(N
(3)选择运算。对群体P(t)进行比例选择运算,得到P1(t)。
(4)交叉运算。对选择出的个体集合P1(t)作单点交叉运算,得到P2(t)。
(5)变异运算。对P2(t)作均匀变异运算,得到P3(t)。
(6)小生境淘汰运算。将第(5)步得到的M个个体和第(2)步所记忆的N个个体合并在一起,得到一个含有M+N个个体的新群体;对这M+N个个体,按照下式求出每两个个体Xi和Xj之间的海明距离:
当时‖Xi-Xj‖
(7)依据这M+N个个体的新适应度对各个个体进行降序排序,记忆前N个个体。
(8)终止条件判断。若不满足终止条件,则更新进化代数计数器t=t+1,并将第(7)步排序中的前M个个体作为新的下一代群体P(t),然后转到第(3)步;若满足终止条件,则输出计算结果,算法结束。
4. 算法实现
MATLAB是Matwork公司的产品,是一个功能强大的数学软件,其优秀的数值计算能力使其在工业界和学术界的使用率都非常高。MATLAB还十分便于使用,它以直观、简洁并符合人们思维习惯的代码给用户提供了一个非常友好的开发环境[2]。本算法的程序是在MATLAB环境下编写完成的,具体代码如下:
4.1 编码运算
本文中的编码方案采用的是最常用的二进制编码,即用二进制数构成的符号串来表示一个个体。使用randint函数实现编码并产生初始群体:
在上述代码中,PS是种群个数,GL是个体编码长度,VN是决策变量的个数。此代码的含义是随机产生一个种群大小为PS的初始化群体initpop,且每个个体的二进制编码长度为GL*VN+VN+2。
4.2 解码运算
初始化的种群initpop必须通过解码才能计算函数值与适应度。代码过程如下:
4.3 选择运算
选择操作建立在对个体的适应度进行评价的基础之上。选择操作的主要目的是为了避免基因缺失,提高全局收敛性和计算效率。本文中的选择算子是最常用的比例选择算子。代码过程如下:
4.4 交叉运算
本文采用单点交叉的方法来实现交叉算子,具体代码过程如下:
4.5 变异运算
本文采用均匀变异的方法来实现变异算子,具体代码过程如下:
4.6 小生境淘汰运算
在小生境淘汰运算中,正确地选择罚函数是关键。具体代码过程如下:
4.7 降序排序运算
利用MATLAB中的Sort()函数对种群进行排序,具体代码如下:
5. 数值实验
以Shubert函数为测试函数,测试参数为种群规模200,个体编码长度20,交叉概率0.9,变异概率0.01,罚函数Penalty=1.0e-030。
此函数共有760个局部极小点,其中18个为全局最小点,最小值为-186.7309。
图1给出某一次计算出的18个全局最小点的具体数值,其中第1、2列为横、纵坐标,第3列为目标函数值,第4列为适应度。这个结果的精确度不仅超过了所有公开报道的计算结果,而且比以往我们计算的结果更好。
6. 结论
本文介绍了基于罚函数的小生境遗传算法,给出了用MATLAB编写的完整代码,并通过MTALAB测试。数值实验结果表明随着进化代数的增加,基于罚函数的小生境遗传算法具有较好的多峰搜索能力。
参考文献
[1]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.