双编码遗传算法（精选6篇）
双编码遗传算法 篇1
摘要：遗传算法是—类基于自然选择和自然遗传机制的自适应全局优化概率搜索算法, 编码策略是设计遗传算法的一个重要步骤, 通过研究二进制码和格雷码的编码策略, 分析了编码差异、个体差异和适应度差异之间的关系, 得到了两种不同编码对遗传算子搜索能力的影响和它们的特性。
关键词：遗传算法,编码策略,二进制码,格雷码
遗传算法是—类借鉴生物界自然选择和自然遗传机制的自适应全局优化概率搜索算法, 它起源于60年代对自然和人工自适应系统的研究, 主要特点是群体搜索策略和群体中个体之间的信息交换和搜索不依赖于梯度信息, 它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题。作为一种全局优化搜索算法, 以其简单、通用、较强的自适应性和鲁棒性, 以及适于并行处理等特点, 被广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域[1]。
按照遗传算法的工作流程, 当用遗传算法求解问题时, 必须在目标问题实际表示与遗传算法的染色体位串结构之间建立联系, 即确定编码, 遗传算法以决策变量的编码作为运算对象, 三种基本的遗传算子的选择和设计都依赖于编码的方式[2], 编码策略对于遗传算子, 尤其是对交叉和变异算子的功能和设计有很大的影响。编码作为遗传算法流程的第一步, 在遗传算法中起着重要作用, 因而提出了许多不同的编码方法[3]。
主要分析了两种主要的编码方式 (二进制码和格雷码) 自身具有的特点, 以及这些特点对于算法的搜索能力的影响。
1 遗传算法流程
遗传算法将m维决策向量X=[x1, x1, …, xm]T用m个记号Xi (i=1, 2, …, m) 所组成的符号串来表示:
X=XiX2…Xm⇒X=[x1, x1, …, xm]T
把每一个Xi看作一个遗传基因, X就可以看做是由m个遗传基因所组成的一个染色体。—般情况下, 染色体的长度是固定的, 但对于一些问题m也可以是变化的, 根据不同的情况, 等位基因可以是一组整数, 也可以是某一范围内的实数值, 或者是一个纯粹的记号。最简单的等位基因是由0和1这两个整数组成的, 相应的染色体就可表示为一个二进制符号串。这种编码所形成的排列形式X是个体的基因型, 与它对应的X值是个体的表现型。对于每一个个体X, 要按照一定的规则确定出其适应度, 个体的适应度与其对应的个体表现型X的目标函数值相关联, X越接近于目标函数的最优点, 其适应度越大;反之, 其适应度越小。
遗传算法中, 决策变量X组成了问题的解空间, 对问题最优解的搜索是通过对染色体X的搜索过程来进行的, 由所有的染色体X就组成了问题的搜索空间。遗传算法的运算对象是由N个个体所组成的集合, 称为群体, 遗传算法的运算过程也是一个反复迭代过程, 第t代群体记做P (t) , 经过一代遗传和进化后, 得到第t+1代群体, 它们是由多个个体组成的集合, 记做P (t+1) , 这个群体不断地经过遗传和进化操作, 并且过次都按照优胜劣汰的规则将适应度较高的个体更多的遗传到下一代, 这样最终在群体中将会得到一个优良的个体X, 它所对应的表现型X将达到或接近于问题的最优解X*。
2 编码策略
编码策略是设计GA的一个重要步骤。三种基本GA算子的选择和设计都依赖于编码的形式。编码成为GA应用中的首要问题, 因而对编码策略的研究也成为研究GA的热点之一, 见表1。
3 编码分析
以前对编码策略的研究, 多以仿真对比来说明不同编码策略对算法的影响。并没有从编码本身的区别上说明原因。Schraudolph的动态编码研究、Goldberg双倍体编码分析等研究就属于此类。对编码本身特点的分析是设计遗传基本算子的基础, 因此, 结合遗传算子分析编码的本身特点来研究。
3.1 二进制码分析
个体编码长度主要由搜索空间和问题精度要求决定。一般函数优化问题的编码精度是唯一的, 考虑到实际应用中, 不同决策变量可能有不同的精度要求, 因此, 将编码长度的结论扩展到多精度的情形。
定义决策变量个数为m, 变量xi (i=1, 2, …, m) 满足xi∈[ui, vi], xi的搜索精度为δi, 即:
∀变量xi的两个值xundefined, xundefined∈[ui, vi], 如果|xundefined-xundefined|<δi/2, 则认为xundefined=xundefined, 则有:
undefined
二进制编码不能保持群体稳定性。这是由于个体和编码之间的映射关系决定的。即对于任意给定的第t代第i (i∈{1, 2, …, n}) 个个体的二进制编码Xundefined, 如果只变异一位, 产生新个体X*t, 不妨假设第k (k∈{1, 2, …, m}) 个变量xk发生变异, 且第k个变量的编码长度为l, 定义变异前后个体的差异为s, 记第k个变量发生变异前后两个个体的数值差为sk:
undefined
则s的最大值为:
undefined
s的最小距离为:
undefined
以上说明了对于二进制编码, 变异操作不能保证父个体与新个体充分接近。即编码相近, 但个体未必相近, 这就导致了变异后的个体与原个体的差异不可预估, 种群的稳定性较差。但是这个结论只说明了编码相差1位的个体的数值差的最大和最小值, 通过下面的分析, 将给出编码差异和数值差所有可能的对应关系, 首先考虑只有一个连续变量x的情形, 多变量编码时可以通过简单的组合得出类似结论。变量x满足x∈[u, v], 在搜索精度δ时, 根据 (1) 式得出的编码长度为l, 变量x对应的编码用X表示, 对二进制编码而言, 采用B表示, 设二进制编码B可以表示为:B=blbl-1…b2b1 (其中bi, i=1, 2, …, l∈{0, 1}) 。任给变量x的两个相异值x1、x2, 他们分别对应的编码是B1、B2。
由二进制数和整数之间的转换公式知, 二进制编码从高位到低位的权值依次为:2l-1, 2l-2, …, 2l, 20。则有个体x的编码B=blbl-1…b2b1对应的解码公式是:
undefined
其中, undefined。
数值差异为:
dx (x1, x2) =round (|x1-x2|/δ) (5)
其中, round () 表示就近取整函数。将解码公式 (4) 代入式 (5) 得:
undefined
式 (6) 可以看作二进制码对应的数值差异定义, 可以看出编码精度和变量的取值区间已经对数值差异不存在影响。编码差异用dH (X1, X2) 表示, 定义为两个编码X1、X2的海明距离 (Hamming Distance) 。对于二进制码, 编码差异为:
undefined
[定理1]当dH (B1, B2) =1时, 如果固定其中一个个体编码B1, 则有:
1) B2存在的种类个数为Cundefined=l;
2) dx (x1, x2) 的可能取值分别为2l-1, 2l-2, …, 2l, 20;
3) P{dx (x1, x2) =2k-1}=1/l (8)
其中 (∀k∈{1, 2, …, l})
证明:undefined
又∵bi, i=1, 2, l∈{0, 1}
∴∃唯一的k (k∈{1, 2, …, l}) ,
undefined
(8) 代入 (6) 得:
undefined
再由k在集合{1, 2, …, l}内取值的任意性知 (8) 式成立。
下面以十进制数0～7的数值差异 (数值差) 和二进制编码差异的对比为例来说明以上结论, 见表2, 其中, 表的首行和首列的数据格式为“个体数值/二进制编码”, 表内的数据格式为“数值差异/编码差异”。从表中得不出数值差异和编码差异的有规律性的联系。但是从式 (10) 可得如下结论:编码差异为1的两个个体的差值可能为{4, 2, 1}, 或者表示为{23-1, 21, 20}。即, 一发生变异产生的新个体与父个体的数值差异是无法预估的。表2的*部分就说明了这一点。
二进制编码因为具有编解码操作简单易行、遗传操作便于实现、符合最小字符集编码原则、便于利用模式定理对算法进行理论分析等优点而得到广泛的应用。但是, 由于二进制编码使得编码差异的大小不能代表数值差异的大小, 导致变异算子的局部搜索能力不足。
3.2 格雷码分析
二进制编码不便于反映所求问题的结构特征, 对于一些连续的函数优化问题等, 也由于遗传运算的随机特性而使其局部搜索能力较差。为改进这个特性, 人们提出了格雷码 (Gray Code) 来对个体进行编码。例如, 十进制数0～7之间的二进制码和相应的格雷码见表3。
格雷码是这样的一种编码方法:其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的, 其余码位都完全相同。
假设个体x的二进制编码为B=blbl-1…b2b1, 其对应的格雷码为G=glgl-1…g2g1 (gi, i=1, 2, …, l∈{0, 1}) 。由二进制编码到格雷码的转换公式为:
undefined
由格雷码到二进制编码的转换公式为[5]:
undefined
上面两种转换公式中, ⊕表示异或运算符。
格雷码的编码差异同样用编码的海明距离来表示:
undefined
[定理2]dx (x1, x2) =1⇒dH (G1, G2) =1 (14)
证明:由dx (x1, x2) =1及 (6) 得:
undefined
并且bi, i=1, 2, …, l∈{0, 1}, 不妨设x1>x2, 并令两个个体的二进制编码B1和B2的编码存在差异的最高位是k (其可能取值范围为k∈{1, 2, …, l}) , 则有:
undefined
(16) 代入 (11) 并由gi, i=1, 2, …, l∈{0, 1}得:
undefined
由式 (17) 代入式 (13) 得,
undefined
下面以整数0～7的格雷码编码为例, 分析一下数值差异 (整数值的差) 与海明距离的关系, 见表4。其中, 表的首行和首列的数据格式为“个体数值/格雷码”, 表内的数据格式为“数值差异/编码差异”。
从表4的*部分可知, 数值差异为1时, 其编码差异全部是1, 验证了 (13) 的成立。从定理2可以看出, 格雷编码方式使相近个体具有相似编码, 这是采用格雷码的遗传算法局部搜索能力强的原因。类似于上面的分析, 可以给出数值差异为任何一个值时的编码差异。但是, 从遗传算法的运行过程可知, 需要的编码方式是满足编码相似可以推导出个体相近的编码策略。定理2表明了格雷码数值差异和编码差异的关联性要好于二进制码。
4 结论
主要分析了两种主要的编码方式 (二进制码和格雷码) 自身具有的特点, 以及这些特点对于算法的搜索能力的影响。这种分析方法也适用于十进制编码和符号编码, 但浮点数编码不同于二进制码等编码方式, 需要结合具体的遗传算子通过搜索能力的对比, 来分析浮点数编码和其他编码方式对某一类问题的优劣对比。通过分析个体差异和编码差异的关系, 得出了格雷码的一些有利于遗传算法局部搜索的特性, 这是格雷码得到广泛应用的原因。
参考文献
[1]Chao Chen, Jianghai Xia, Jiangping Liu, GuangdingFeng.Nonlinear inversion of potential-field data usinga hybrid-encoding genetic algorithm[J].Computers&Geosciences, 2006, 132 (2) :230-239.
[2]李敏强, 寇纪淞, 林丹, 李书全.遗传算法的基本理论与应用[J].北京:科学出版社, 2002.
[3]Alan Crispin, Paul Clay, Gaynor Taylor etl.Genetic Algo-rithm Coding Methods for Leather Nesting[J].AppliedIntelligence 23, 0-20, 2005.
[4]Serkan Bekiro lu, Tayfun Dede, Yusuf Ayvaz.Implementation of different encoding types on structural optimiza-tion based on adaptive genetic algorithm[J].Finite Ele-ments in Analysis and Design, 2009, 45 (11) :826-835.
[5]Ying-Hua Chang, Young-Chang Hou.Dynamic pro-gramming decision path encoding of genetic algorithms forproduction allocation problems[J].Computers&Indus-trial Engineering, 2008, 54 (1) :53-65.
[6]Carlos Fernandes, Agostinho C.Rosa.Self-adjusting theintensity of assortative mating in genetic algorithms[J].Soft COMPUT, 2008 (12) :955-979.
双编码遗传算法 篇2
在工业过程控制的发展史上,PID控制是历史最悠久,生命力最强的控制方式,目前90%以上的控制回路仍采用PID控制器[1]。由于常规理论整定法复杂、繁琐且效果不佳,而工程整定法实际上属于人工整定法,需要实际操作者有一定的控制领域知识和丰富的经验,整定往往费时且难以满足控制要求。因此,研究智能控制优化PID参数具有十分重要的工程实际意义。
2 遗传算法的基本原理
常规遗传算法是1962年由美国的J.H.Holland提出的一种模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律,是一种全局迭代搜索算法。遗传算法把待优化的参数编码,然后形成一个初始种群作为待求问题的候选解,并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中选择、交叉和变异构成了遗传算法的遗传操作;参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。通过不断计算各个个体的适应值,选择最好的个体,获得最优解[2]。
3 应用浮点数遗传算法实现PID控制器参数寻优的过程
3.1 确定参数寻优范围和参数编码方式
确定参数寻优范围,按照经验公式计算出PID参数的参考值,然后将寻优范围设置在参考值附近,这样有利于缩小搜索空间,迅速找到最优解的位置。
迄今为止已提出遗传算法许多种编码方案,总体来说,这些编码方法可分为二进制编码方法、格雷码编码方法、浮点数编码方法、符号编码方法。目前常采用的编码方法主要是二进制编码和浮点数编码。
采用二进制编码的遗传算法,搜索能力较强,然而二进制编码不能反映问题的结构,并且个体长度大,占用计算机内存多,难以提高精度;十进制编码对于变异操作的种群稳定性比二进制编码好,且十进制编码的可操作性强,可以减少编、解码的计算时间,能使搜索效率增加,还可以避免二进制编码带来的“Hamming悬崖”现象的影响。本文采用浮点数编码方法。
3.2 选择控制参数
控制参数主要包括群体规模大小M,交叉概率Pc,变异概率Pm和最大进化代数G。在运行遗传算法程序时,需要对这些参数进行预先设置,它们对遗传算法的性能有很重要的影响。
一般来说,选择较大数目的初始种群可以同时处理更多的解,因而容易找到全局最优解,但这样会增加每次迭代的时间,一般M可取20-100;交叉概率的选择决定了交叉操作的频率,频率越高,可以越快的收敛到最有希望的最优解区域,因此一般选取较大的交叉概率,但是不能太大,否则可能导致过早收敛,一般Pc取值0.4-0.9。变异概率的选择一般受种群大小、染色体长度等因素的影响,通常取值很小,一般Pm取0.001-0.1。最大进化代数作为一种模拟终止条件,一般视情况而定,G取100-500代。
3.3 确定适应度函数
适应度是指优化计算中群体中各个个体接近最优解的优良程度。适应度高的个体遗传到下一代的概率较大,适应度小的个体就会被淘汰掉。遗传算法在搜索时基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。因此,适应度函数的选取至关重要,直接影响到遗传算法的收敛速度以及能否找到最优解。适应度函数是非负且数值越大越好。常用的性能目标函数有以下几种:
本文采用
作为目标函数,由于PID控制器参数寻优是求目标函数的极小值问题,即:
而遗传算法是寻找适合度最高的解。因而要将目标函数进行改造,将极小值问题转换为极大值问题。在此采用其倒数作为适应度函数:
这样,当找到有最大适合度的解,也就找到了最小目标函数值的解,寻优成功。
3.4 产生初始群体
根据群体规模大小,随机产生一个含M个个体的初始群体。
3.5 选择操作
选择又称复制,是在群体中选择生命力强的个体产生下一代群体的过程。遗传算法使用选择算子来对种群中的个体进行选择操作;根据每个个体的适应度大小来进行选择,适应度高的被遗传到下一代的概率较大,适应度小的被遗传到下一代的概率较小。选择操作的目的是为了避免有用的遗传信息的丢失,提高全局收敛性和计算效率。
选择操作用于保留高性能的个体,首先要计算个体的适配值,常用的方法是按比例选择,即个体适配值按比例转化为选中概率。若个体i,其适配值fi,则被选中的概率为
式中:M—种群规模;
fi—种群中第i个个体的适应度;
Pi—第i个个体被选中的概率。
然后对其父代进行选择,常用的选择方法为轮盘赌选择方法。
轮盘赌选择法,即将个体的Pi依次排列为一段[0,1]的区间,每轮产生一个[0,1]均匀随机数,这个随机数所在位置位于Pi范围内,则该范围对应的个体即被选中,就是将该随机数作为选中指针来确定被选个体。
3.6 交叉和变异,产生新一代群体
随机选择交叉父代,父代以线性交叉的方式产生子代,具体操作如下:
式中:x1和x2—交叉父代;
x'1和x'2—生成子代;
α—[0,1]之间的随机数。
变异操作即在该参数所在区间随机产生一个实数代替被选中的变异个体,具体操作如下:
式中:x—变异前个体;
x'—变异后生成个体;
β—[0,1]之间的随机数。
经过交叉和变异后产生新一代群体。
遗传算法引入变异运算有以下两个好处:
1)改善遗传算法的局部搜索能力,对于选择和交叉运算得来的优秀个体,已经很接近于最优解,通过变异算子来调整个体编码串中的部分基因值,就可以从局部的角度出发使个体更逼近最优解;
2)维持群体的多样性,防止出现早熟现象。变异算子用新的基因值替换原有的基因值,从而改变个体编码的结构,维持群体的多样性。
3.7 判断进化终止条件是否满足
对产生的新一代群体进行评价,判断进化终止条件是否满足,若满足则得到最优解,寻优结束。否则,返回步骤3.5。
4 仿真结果
根据算法流程,采用M语言编写相关程序,并对算法性能进行仿真测试。
对于工业上常用的二阶惯性对象和二阶惯性加纯迟延对象进行讨论,对于工业上某两个对象的传递函数为:
设计过程中采用J=∫0∞t2|e(t)|dt作为参数选择得最小目标函数,输入指令为阶跃信号r=1。
本文遗传算法程序中使用的群体规模大小M=8 0,交叉概率Pc=0.85,变异概率Pm=0.025,最大进化代数G=100。
PID的控制规律为:
在工业过程中PID控制器使用的PI作用最为广泛,采样PI作用基本可以达到控制要求,取Td=0,优化δ和Ti,δ取值范围设为[0.5,4],Ti取值范围设为[1,300]。
对于被控对象(1),遗传算法寻优得到:
仿真结果如图1所示:
对于被控对象(2),遗传算法寻优得到:
仿真结果如图2所示:
对于含有纯迟延的被控对象(2),与不含纯迟延的被控对象(1)相比,其调节时间延长,控制特性相对变差,但是仍能满足控制要求,具有良好的控制品质。
5 结束语
将遗传算法用到PID控制器参数的优化中去,无论是对于不含纯迟延的被控对象还是含有纯迟延的被控对象,都可使系统具有很好的动态品质。仿真结果表明,遗传算法在参数寻优速度和有效性方面具有明显的优势,寻优简单,效率高,不失为一种具有实用价值的PID参数优化方法,在很大程度上解决了PID控制器参数整定难的问题。
摘要：本文介绍了基于浮点数编码遗传算法寻优的PID参数优化方法,采用误差绝对值时间平方积分性能指标作为参数选择的目标函数,利用遗传算法的全局搜索能力,实现对全局最优解的寻优,以降低PID参数整定的难度,达到总体提高系统性能的目的。仿真结果表明,通过浮点数编码遗传算法进行PI参数优化可使系统具有很好的动态品质和稳态特性。
关键词：遗传算法,PID控制器,参数优化
参考文献
[1]刘金馄.先进PID控制及其Matlab仿真[M].北京:电子工业出版社,2003.
[2]玄光男,程润伟等.遗传算法与工程优化[M].北京:清华大学出版社,2004.
[3]邓华昌,方康玲,梁开,张鹏.一种混合遗传算法在PID参数优化中的应用[J].机械设计与制造,2009,(7):89-91.
[4]任志淼,卢慕超.遗传算法及其在PID参数优化中的应用[J].山西电子技术,2008,(3):43-44.
双编码遗传算法 篇3
关键词：MIMO雷达,波形优化,遗传算法,正交编码信号
MIMO雷达通过在不同天线上发射接收正交信号,利用目标的空间分集机制改善目标的检测性能[1,6,7]。为最大程度地发挥MIMO雷达的优势,系统对发射信号的设计提出了更高的要求:首先,与传统的单基雷达一样,要求发射信号为大时宽、宽带宽的脉冲信号,在接收端对大时宽、高带宽的信号进行压缩处理,从而得到脉冲宽度为信号带宽倒数的窄脉冲信号,解决雷达探测距离和分辨率之间的矛盾。压缩输出信号须具有高的主副瓣比,以避免弱目标被强目标副瓣淹没和副瓣带来的错误检测;其次,由于MIMO内各信号间的干扰也不容忽视,所以它还要求网络雷达系统内各发射机发射的信号互不相关,从而使雷达在不同方位获得独立的空间分集增益[6,7],并降低雷达间干扰带来的虚警概率。
相位编码压缩和时间频率编码压缩技术是常用的脉冲压缩技术,要找到一组L个码长为N的具有高分辨特性的正交多相或多频编码信号是一个典型的非线性优化问题。基于概率模型的遗传算法[8,9]是解决非线性寻优的一种有效方法,具有智能化全局寻优,且收敛性不受初始值限制的优点。文中将MIMO雷达发射信号的自相关函数副瓣峰值和互相关函数的峰值之和作为目标函数,通过构造适应度函数,利用遗传算法实现发射信号波形优化设计。仿真结果和实验分析验证了该算法的有效性和可行性。
1 正交MIMO雷达发射编码信号模型
考虑正交MIMO雷达有L个发射天线,每个天线均发射相互正交的编码脉冲信号{sl(t),l=1,2,3,…,L},每个信号有N个持续时间为T1的子脉冲组成。由于信号间的正交性,那么任意两个发射信号自相关函数满足
C(sp,sq,τ)=∫tsp(t)s*q(t+τ)dt=0,p≠q,∀τ∈R,p,q=1,2,3,…,L (1)
其中,“*”表示共轭运算操作符号。为使信号具有高的距离分辨力,信号的非周期自相关函数有以下形式
其中E为信号sl(t)能量。
对于有M个可能相位状态的正交多相编码脉冲信号{sl(n)=ejφl(n),n=1,2,3,…,N},l=1,2,3,…,L,其中,
其中,k表示离散时间。当
2 信号波形优化设计算法
2.1 适应度函数构造
正交信号的性能可以由自相关函数的副瓣电平峰值(ASP)和互相关函数的电平峰值(CP)表征,受ASP和CP约束的代价函数
其中,λ为自相关函数与互相关函数之间加权系数。与遗传算法相结合,将代价函数转化为适应度函数
式中,λ此时为适应度因子,λ越大,表示互相关对环境的适应影响越大;Cmax1为E1的最大值,保证适应度函数的非负性。考虑互相关能量和自相关函数副瓣能量的分布,适应度函数
其中,Cmax2为自相关副瓣能量和互相关能量之和的最大值。适应度函数式(9)通过约束相关函数能量,均匀地分布在所有可能时刻上来最小化ASP和CP,具有良好的稳健性[10]。因此,在进行波形优化设计时,采用式(9)作为适应度函数。
2.2 基于遗传算法的正交多相编码序列优化设计
由于遗传算法主要模拟生物的进化过程进行搜索,而生物的进化过程主要通过染色体之间的交叉和变异来完成,所以需要对正交编码序列组模拟染色体进行二进制编码。鉴于多相编码序列本身就是一种多元伪随机序列,故采用二进制编码时,可以将每个相位状态向二进制数进行简单的映射。以常用的四相编码信号为例,则有
Step1 对i =0产生初始化种群
Step2 根据各个个体的适应度值,采用轮盘赌方式从第i代种群
Step3 将种群
Step4 对种群
Step5 对种群
2.3 正交多频编码序列优化设计
由于多频编序列本身也是一种伪随机编码序列,在进行遗传编码时,将编码序列为的任意排列影射为一个多相编码序列。同时由于多频编码序列中每个码元的不可重复性,使得交叉操作不易进行,将采取扩大种群、加大变异概率等措施避免算法早熟。其主要步骤如下:
Step1 对i =0产生初始化种群
Step2 根据各个个体的适应度值,采用轮盘赌方式从第i代种群
Step3 行变异操作,产生多个互异的随机变异位,然后将不同位置的码元随机互换,从而生成新的个体。为防止早熟现象,变异概率要比多相编码设计时的大,并采用自适应算法[10]进行对其进行自适应调节。
Step4 对种群
3 MIMO雷达波形优化设计结果分析
在进行正交多相编码信号设计时,主要参数为:种群大小P=100;起始交叉概率pc1=0.8;最小交叉概率pc2=0.5;起始变异概率pm1=0.05;最大变异概率为pm2=0.15;最大迭代步数为1 200。在进行正交多频编码信号设计时,主要参数为:种群大小P=150,起始变异概率pm1=0.10,最大变异概率为pm2=0.30最大迭代步数为2 000。
表1给出了L=4,N=40,M=4,λ=1时优化得到的一组正交多相编码序列的相位值,其中
表3列出了L=3,N=32,λ=0.56时,优化得到的正交多频序列编码。表4给出了多频编码序列的归一化ASP和CP,其中对角线元素表示归一化ASP,其余元素表示不同信号间的归一化CP。ASP平均约为0.038 4或-28.3 dB,CP平均约为0.071或-23 dB。在其他条件相同的情况下,当式(9)中λ由0.56变为1.25时,ASP平均约为0.039 3或-28.1 dB,CP平均约为0.067 3或-23.4 dB。实验表明,适应度因子对基于遗传算法的正交多频编码信号优化起到了有效的调节作用,增大意味着CP对适应度函数影响变大,使得CP降低,ASP升高。
4 结束语
双编码遗传算法 篇4
现代配电网一般采用闭环设计、开环运行的运行方式, 由于网络中存在大量开关, 运行人员可以根据网络中负荷的变化情况改变开关的状态, 实现对配电网拓扑结构的变换, 从而实现配电网的优化运行。配电网重构是一个非线性优化问题, 进行重构时不但要力求找到全局最优解, 而且要提高求解速度。按侧重面不同, 重构可分为故障恢复和网络优化重构。以网络优化为目的的重构是一个多目标的组合优化问题, 其目标主要包括:降低网损、均衡负荷、消除线路过载以及提高供电电压质量等。
目前, 配电网重构的主要方法有最优流算法[1]、支路交换算法[2,3]和人工智能算法[4,5,6]等。最优流算法首先进行闭环下只计支路电阻的潮流计算, 得到网络的最优流模式, 然后以每次断开最优流模式下电流最小的一条支路为启发规则, 逐次解环, 直到网络呈辐射状。但由于在求解时各环网相互影响, 使得分段开关的开断顺序对结果影响较大, 因而并不能保证得到最优解[7]。人工智能算法中的遗传算法[8,9,10,11,12], 具有全局搜索和不依赖梯度信息的特点, 在解决配电网重构问题上取得了良好的效果, 但是其寻优过程中会产生大量无法满足“配电网辐射运行约束”的不可行解, 影响算法的计算效率。文献[8]提出了对不可行解破圈和消除孤岛的方法, 但其操作复杂且只能在产生不可行解后进行修正;文献[9]采用扩展生成树的方法, 有效避免了环网的形成, 但其计算量大, 不具有通用性, 且产生的解不具有随机性。文献[10]将节点深度编码 (NDE) 技术引入配电网故障恢复问题中, 在寻优过程中能始终保证配电网的辐射状结构。但该算法需依靠启发性规则来确定支路切除点, 因而算法寻优性能在较大程度上依赖于支路切除点的选择。文献[11]将环路分解引入遗传算法, 通过搜索网络中的所有环路, 随机断开环路中的支路解环。环路分解能够有效产生可行的初始种群, 或修正交叉、变异中产生的不可行解, 但对于复杂网络, 要得到所有回路并反复搜索这些回路以生成可行解需要大量计算;另外这种穷举式算法无法体现各回路之间的关联关系, 难以应用于一些带有启发规则、需要灵活进行开关交换的算法中。
另外, 由于没有考虑电力系统本身的特性, 传统的遗传算法只是一个随机的寻优过程, 存在着搜索范围大、迭代次数多、局部寻优能力差、收敛速度慢的缺陷, 不适用于大规模配电网的重构。文献[12]提出动态调整交叉率和变异率的方法;文献[13]提出缩短染色体长度的措施, 都在一定程度上提高了遗传算法的搜索效率, 但作用有限, 上述缺陷没有得到根本改观。
针对上述问题, 本文将利用配电网的回支关联矩阵动态切割及合并回路以保证辐射状拓扑结构, 避免频繁的拓扑搜索。此外, 本文以最优流算法为基础进一步提炼启发规则, 将迭代过程分解为确定电流分点周围开关最优断开组合和电流分点转移2个步骤, 有效缩小了遗传算法的寻优范围, 提高了收敛速度。
1 数学模型
1.1 目标函数
本文以网损最小为主要优化目标, 在满足约束条件的情况下, 调整各开关状态对配电网实现重构, 目标函数为:
式中:ki表示支路i的状态, ki=0表示支路打开, ki=1表示支路闭合;Ri为支路i的电阻;Pi和Qi分别为流过支路i的有功功率和无功功率;Ui为支路i末端的节点电压;b为支路总数。
1.2 约束条件
1) 网络拓扑约束
在重构过程中配电网应始终保持辐射状网络结构, 即有
式中:GΦ为重构后网络拓扑结构;G为辐射状网络拓扑结构。
2) 节点电压约束
式中:Vi为节点i电压;Vi.max和Vi.min分别为节点i允许的电压上下限。
3) 潮流越限约束
式中:Sj为支路j的功率;Sj.max为支路j的最大容许功率。
2 回路解环技术
遗传算法在寻优过程中会产生大量无法满足“配电网辐射运行约束”的不可行解, 严重影响算法的计算效率。本文通过动态操作网络回支关联矩阵[14], 快速得到辐射状结构。
回支关联矩阵B是电力系统计算中的一个常用工具, 其每一行代表一个基本回路, 且仅包含一条连支。本文将B适当简化, 不计网络的支路方向, 其每个元素按属于或不属于所在行代表的基本回路分别记为1和0。对于含有L条连支的连通图, 如果进行L次解环操作, 剩下的必定为树[15]。因此, 对回路的解环操作步骤如下。
步骤1:从矩阵B的i=1行开始, 任选一个值为1的元素Bi.j置零。此时, 将产生2种结果:①支路j仅与回路i关联, Bi.j置零后, 仅对回路i解环。如图1 (a) 所示;②支路j同时与回路i和回路k关联, Bi.j置零后, 在对回路i和k解环的同时产生了一个新的环路k′, 如图1 (b) 所示。以新的环路k′替代原来的环路k, 则后续的解环操作仍能正常进行。而从数学上讲, 形成新的环路k′其实就是对矩阵B的第i行和第k行进行异或运算, 记为:Bk′·=Xor[Bi·, Bk·]。
步骤2:i=i+1, 循环上述操作, 直到对矩阵B各行全部完成解环。
通过上述对网络中回路动态合并的过程, 就能保证在对B逐行解环时, 其后各行仍能始终代表一个完整的回路。又由于在异或运算中只是合并了回路的公共部分, 能够唯一标志一个回路的连支不会消失, 也就说明剩下还没有解环的各回路仍然各不相同, 且都为基本回路, 便于后续循环操作。
3 算法简介
3.1 算法流程
图2所示为算法流程图。
3.2 染色体编码
以支路状态为编码对象的遗传算法, 需要面对庞大的染色体维数以及种群数量, 这就使它很难应用于大规模的配电网重构中。本文提出了以电流分点为编码对象的编码方法, 大幅缩短了染色体长度, 减少了迭代时间。
在闭环网络中, 电流局部最小的支路只可能是以下2种:①回路中与电流分点相连的支路;②不成环的线路的末端支路。在最优流算法中, 启发规则为在迭代计算中依次断开电流最小的支路。若电流最小的支路对应第1种情况, 则对应回路解环;若对应第2种情况, 则网络解列形成孤岛。综上, 最优流算法最终断开的支路仅可能是在每次潮流计算中与某电流分点相连的支路。
对配电网进行潮流计算得到各支路电流后, 就可以确定出网络的电流分点 (入度r≥2) , 定义入度r=2的电流分点为基本分点。如果存在入度r≥3的分点, 可认为它由r-1个基本分点组成。因而, 对于具有L个回路的网络而言, 共有L个基本分点。
假设闭合配电网中所有联络开关后形成L个独立回路, 借鉴“断开与基本分点相连支路”的规则, 则网络重构可归结到断开基本分点的哪一侧支路的问题上。
本文基于基本分点进行染色体编码, 0代表断开与其相连的小号入度支路, 1代表断开大号入度支路。对于入度r=2的分点, 1个基因对应1个分点, (见图3 (a) ) , 0代表断开a, 1代表断开b;对r≥3的分点, 用r-1个基因 (基本分点) 组合表示, (见图3 (b) ) , 在交叉和变异过程中需要整体处理。
3.3 交叉和变异
本文采用均匀交叉和均匀变异算子。
由于对入度r=2的分点, 其两侧支路对网络中环的隶属性相同, 断开其中任一条均不会影响解的可行性。而对于在分点转移过程中 (详见3.4节) 所产生的新的入度r≥3的分点, 则有必要应用第2节提出的回路解环技术对该阶段交叉、变异产生解的可行性进行考察和修正。例如:图4中当属于回路1的分点1在经过2次分点转移至如图所示位置时, 断开分点1左侧的入度支路, 将会产生不可行解。
但需指出的是, 配电网中大量存在的是入度r=2的节点, 而出现如图4所示入度r≥3的分点数量较少。因此, 算法在实际运行时需进行不可行解的验证且修复量较少。
3.4 分点转移与收敛条件
由于忽略支路开断顺序对结果的影响, 而将L条支路一次性全部断开, 通过一个阶段的遗传算法寻优所求得的解只是在该组分点附近的最优开关组合, 而不是全局最优。因此, 需要把整个寻优过程分成若干个上述阶段, 在进行第2阶段寻优时所有分点将向断开的支路方向转移, 如图5 (a) 所示。如此迭代下去, 直到相邻2个阶段产生的最优解相同, 且都优于之前历次迭代结果为止, 如图5 (b) 所示。
4 算例分析
本文采用IEEE 33节点配电网以及某典型的118节点配电网[16]为计算对象, 从计算结果以及计算速度方面对上文方法进行考查。
4.1 算例1
IEEE 33节点配电网系统如图6所示。系统共包含37条支路, 其中5条为联络开关支路, 电源基准电压为12.66kV, 网络初始状态下总负荷为5 084.26+j2 547.32kVA。分别采用文献[11]中提出的环路分解遗传算法 (以下简称CBGA) 和本文提出的算法对网络进行重构。CBGA中种群数量为30, 迭代次数为50;本文算法中种群数量为6, 每阶段迭代次数为10, 其他参数相同。计算结果见表1, 收敛过程如图7所示。
由表1可以看出2种算法最终都收敛于相同的最优解。图7显示本文算法的迭代共分2个阶段, 因为搜索范围小, 每个阶段的收敛速度非常快, 致使总迭代次数只需要20次;由于采用了新的编码方式, 染色体长度短, 算例中新算法种群数量只有6个, 就能够达到很好的计算效果。相比之下, CBGA一般需要种群数量达到30以上、迭代次数达到40以上, 才能较为可靠地收敛, 本文算法与CBGA的实际耗时约为1∶12, 凸显了本文算法在大规模配电网重构中的实用性。
另外, 本文算法具有明确的收敛条件, 即相邻2个阶段产生的最优解相同, 且都优于之前历次迭代结果;而遗传算法只能通过增加迭代次数来保证逼近最优解。
图8显示了本文算法的一个迭代过程。可以看到, 由于第2阶段迭代没有及时达到本阶段最优, 致使分点转移发生了明显错误, 但由于不符合收敛条件, 计算无法立即收敛, 经过第3阶段的迭代, 分点重新转移回第2阶段开始前的位置。上述过程体现出本算法具有一定的纠错能力, 可以在每阶段迭代次数较小的情况下以更大的概率收敛到最优解。
4.2 算例2
为了验证本文算方法在大规模配电网重构中的有效性, 将其在118节点系统中进行了测试。系统共包含132条支路, 其中15条为联络开关支路, 电源基准电压为11kV, 网络初始状态下总负荷为22 709.7+j17 041.1kVA。各支路详细参数见文献[16]。
测试同样包括了CBGA和本文算法, 并引入了文献[16-17]的计算结果加以对比。CBGA中种群数量为100, 迭代次数为200;本文算法中种群数量为20, 每阶段迭代次数为20, 其他参数相同。计算结果见表2, 收敛过程如图9所示。
对比计算结果可以看到, 本文算法取得的降损效果最佳, 网损为807.3kW, 低于其他几种算法;同时, 由于断开的支路都位于电流分点附近, 使得本文算法得到的电压质量也最为理想, 最低电压为10.321kV。
图9所示为本文算法的收敛过程, 迭代收敛共经历了6个阶段, 总迭代次数为120次。另外, 本文算法中启发规则的精度直接影响到计算效率, 如果分点定位准确, 只需2个阶段迭代就能完全收敛。相比之下, CBGA (见图10) 虽然收敛速度很快, 但得到的解劣于本文算法的最优解。由此可见, 本文算法具有更好的全局寻优性能。此外, CBGA的种群数量较大、迭代次数较多、单步迭代耗时较长 (约为本文算法的5倍) , 因此, 在计算速度上, 本文算法也具有一定的优势。
5 结语
本文使用回支关联矩阵B形成辐射网络, 随着支路断开, 动态合并回路, 使B中还没有被操作到的行始终代表回路, 有效地防止了不可行解的产生, 提高了遗传算法的效率。通过只计电阻的网络潮流计算, 一次性地确定网络中全部电流分点, 并以断开与分点相连并指向该点的支路为启发规则, 有效缩小了遗传算法的寻优范围。引入新的染色体编码规则, 以基本分点为基本的编码单元, 将整个问题分解为寻找分点周围支路最优开断组合和分点移动2个步骤, 有效地缩短了染色体长度、减少了迭代次数、节省了每次迭代的时间。
如果网络更为复杂, 本文算法仍可能陷入局部最优中而得不到全局最优解, 这就需要进行以下2个方面的改进。
1) 提高启发式算法的精度, 力求把遗传算法的求解范围限制在不包含其他局部最优解的邻域内。
双编码遗传算法 篇5
1 基于传统染色体编码的遗传算法特点及其缺陷
遗传算法借鉴了自然界生物进化思想,它模拟生物的自然选择和遗传变异来求解复杂问题,遗传算法只需使用目标函数的适应度值即可确定搜索范围和方向,它无需要求目标函数连续可导,甚至目标函数无法求导时,遗传算法也能取得优化结果,这样的特点很适合使用在许多目标函数无法求导的系统中使用,遗传算法作为一种实用高效的寻优算法其发展非常迅速,在国内外的研究也十分普遍。
遗传算法的主要特点是群体并行搜索,它的寻优是实际上采用迭代过程,将问题的解空间编制成编码空间,以个体的适应度作为优化算法的依据,通过不断的选择、变异和交叉等一系列操作,产生更新的较优个体,然后继续进行迭代过程并最终收敛得到问题的最优解。
在算法不断的迭代和搜索过程中,种群不断地得到优化,在每一次搜索过程中,种群中的优秀个体被保留到下一次搜索种群中,随着搜索的进行,某些适应度高的个体在种群中不断增长,会使得种群中的个体各基因位逐渐趋于一致,种群的多样性逐渐减小,理论上,当种群多样性不断减小能使问题最终收敛成最优解,而这是建立在无限规模种群的基础上,而无限规模的种群在实际应用中是不存在的,例如,在《会计职业道德与财经法规》考试题库中,虽然每次的题库都在可以增加(至少目前如此),但它总是有限的,这样,由于时间和资源的限制,会导致种群的多样性过早地丧失并趋于零,在此情况下,有可能出现搜索算法停止不前从而过早收敛产生非最优解,根据《会计职业道德与财经法规》考试的要求,每位考生得到的试题应在试题难度和适应性上大致相同,此要求的目的是使考试更加公平;但各个考生得到的题目本身必须有所区别,以防止考试中产生舞弊等情况出现。如果过早出现收敛,即遗传算法的“早熟”现象[1],则无法体现考试的全局最优,即我们通常所说的考题并非最佳,从而使考试失去公平性。
染色体编码策略的选择是实现遗传算法的关键,传统遗传算法采用二进制染色体编码方式,它把问题映射成二进制序列,组成长度为m的二进制串,即:(B1B2B3......Bm),其中Bi为二进制串中的位,Bi=1表示该题被抽中,Bi=0表示该题未被抽中,若考试中有n道题,则(B1B2B3......Bm)中有n个1,但是,传统的遗传算法的这种通用编码方式并不能适合会计从业资格考试的实际情况,《会计职业道德与财经法规》的考试以客观题为主要考试题型,它需要考核考生的会计基础应用技能,因此,其考试内容几乎涵盖了《会计职业道德与财经法规》的各个章节,为了区分每个章节的重要程度,考试大纲还给出了考试的分值分布,根据不同的分值,各种题型和章节均需在考试中有所体现,单选题每题分值为0.5分,总分25分,多选题为30分,每题1分,其他题型也各有不同分值,所以,按通用的染色体编码策略不能满足组卷要求。
2 系统组卷数学模型的确立
组卷其实是多重目标约束优化问题,即一个目标函数和多个约束条件的组合,在确立系统组卷算法之前,首先应确立《会计职业道德与财经法规》考试系统的约束条件,根据对考试要求的分析,确立试题约束条件属性定义如下:
1)题号:该属性是试题在题库中的唯一标识,在数据库中是关键字段值;
2)题型:《会计职业道德与财经法规》考试有四种题型,即单选题、多选题、判断题和不定项选择题,为每种题型设置题型代号;
3)试题分值:每小题的分值;
4)知识点:该试题所属的知识点代号;
5)难度系数:该试题的难度值,根据考试大纲,一般设为易、中、难三个等级。
系统有5个试题约束条件属性,根据约束条件所确定的解空间,可以确立试题的目标矩阵为m×5:
矩阵S代表一份试卷,其目标函数如下:
其中为第i个属性的权值。
约束条件如下:
1)试题总分
2)平均难度系数
3)知识点分值,其中
4)题型分值,其中
3 改良后的分段染色体编码策略及其遗传算法设计
遗传算法是基于种群优化进行的一种寻求最优的算法,利用种群的不断进化从而产生最优结果,其关键点在于种群的选择,种群直接关系到遗传算法的效率与最终结果。
一般的遗传算法中,染色体编码采用二进制编码策略,即将问题映射成0、1的二进制串,由(B1B2B3…Bm)组成,m为二进制串的长度,但是,这种编码方式存在编码与解码算法复杂,搜索计算量大以及容易产生过早收敛的缺点,并不利于在实际应用中推广。
在《会计职业道德与财经法规》考试系统中,为了使种群避免产生过早收敛即所谓的“早熟”现象,同时兼顾组卷的效率,采用分段染色体编码策略是一个有效解决问题的办法[2],因为考试中涉及4种题型,每题型间又无严格的关联度,所以采用分段染色体编码能显著提高组卷的效率,这里把4种题型的题目分在4个段内,每段进行独立编码,各种题型分别进行独立的遗传操作,最终组合而成,得出整份试卷,例如单选题分段为(a1a2a3…an),其中ai为每题的题目序号(唯一),n=单选题总题目数;多选题分段为(m1m2…mn),同样的,mi为每题的题目序号,其他判断题和不定项选择题也按同样的分段进行,基于分段编码的遗传算法采用了题目序号作为唯一的基因标识,其实质是在编码策略阶段就将问题简单化,减少了题目属性的复杂度,有效地提高了遗传算法效率,同时也避免了在传统遗传算法中经常遇到的编码和解码的问题。
传统遗传算法采用固定交叉算子和变异算子来实现个体的进化,不过并不适用于《会计基础》考试系统的要求,固定交叉算子容易产生重复率高的试题,即所谓的局部最优而非全局最优现象,因此,需要防止这种情况产生,不同适应度的个体应该采用不同的交叉算子Pc和变异算子Pm[3],公式如下:
取值:k1=k2=0.8,k3=k4=0.3,其中fmax为群体最大适应值,favg为群体平均适应值,f'为配对交叉个体中的适应值较大值,f为变异个体的适应值。
4 组卷算法仿真实验
仿真题库取自2010年江苏省会计从业资格考试《会计职业道德与财经法规》复习及模拟练习题库,其中单选题库总数为500题,多选题库500题,判断题库500题,不定项选择题库500题。测试采用传统染色体编码遗传算法和分段染色体编码遗传算法分别进行,以平均迭代次数、组卷用时二项指标,采用一般染色体编码结果如图1所示。
而采用改良后的分段染色体,其结果如图2所示。
从结果可以看出,采用改良后的分段染色体编码策略无论在平均迭代次数还是在组卷用时都要优于传统遗传算法,实验所采用的题库仅是近几年来采用的考试题库的一部分,可以预见,随着题库量的不断增加,采用改良后的分段染色体编码的遗传算法可以省却大量的计算时间,有效地提高组卷的效率。
摘要：研究探索在无纸化课程考试中采用遗传算法进行智能组卷的数学模型,传统遗传算法采用二进制染色体编码实现搜索,该文采用改良的染色体编码进行考试的智能组卷,从而实现考试组卷的全局优化和适应度,通过研究实验表明,改良以后,染色体编码更适合于无纸化考试的组卷要求。
关键词：遗传算法,改良,染色体编码,智能组卷
参考文献
[1]周洪伟,张来顺.遗传算法早熟现象及改进策略研究[J].解放军电子技术学报,2004(1).
[2]林健,闰华,武兵.计算机自适应考试理论分析[J].太原理工大学学报,2004(2).
双编码遗传算法 篇6
关键词：双概率,原对偶遗传算法,最大最小蚁群算法,融合
0 引言
当今的中国处于社会经济改革的快速通道, “一带一路”、“海上丝绸之路”的详细规划逐步出台, 因此在未来几年, 中国社会将会出现令人无法想象的变化。自然而然, 随之产生的问题也将会变得愈加复杂, 科学工作者对模型的建立、求解难度加大, 新算法、改进型算法的需求问题, 将对这一切产生不可忽略的影响。全新算法的理论研究进程比较缓慢, 而在现有算法基础上进行改进的相关研究却日新月异。算法融合思想[1,2,3]是改进算法性能的一个重要途径, 算法的融合能有效的弥补单一算法各自的不足。
传统遗传算法在环境不变的情况下, 能较好的找到最优解, 然而, 在动态环境中, 随着迭代次数的增加, 种群的多样性逐步遗失, 环境一旦发生改变, 难以对其作出反应[4,5,6,7,8]。为了克服传统遗传算法的这一不足, Yang提出了原对偶遗传算法 (Primal-Dual Genetic Algorithm, 简称PDGA) [9,10], 在初始种群中引入原对偶映射 (Primal-Dual Mapping) 算子, 每个个体都在给定Hamming距离空间内定义一个对偶个体, 从而提高了种群的多样性。之后, Wang基于PDGA提出了改进型算法 (IPDGA) [11], 较传统遗传算法而言, PDGA、IPDGA在搜索性能上有所提高。但由于这两种算法中种群染色体上的基因参与PD映射的概率相等, 这必然限制了种群多样性范围。在持续变化的环境中, 随着迭代的增加, 后期将产生无为的冗余。刘黎黎等针对这一不足, 提出了双概率原对偶遗传算法 (Double Probability-based Primal-Dual Genetic Algorithm, 简称DPPDGA) [12], 进一步提高了进化种群的多样性。
然而, 这些算法始终具有遗传算法的共性, 都没有利用系统中的反馈信息, 这使得算法在运行中后期, 会降低运算效率, 影响求解效果。蚁群算法正好能够利用反馈信息并加以更新来收敛到最优路径, 但蚁群算法运行初始信息较为匮乏, 这是制约蚁群算法性能的重要因素。将这两类算法进行融合, 正好可以弥补各自缺陷, 提高求解效率。
1 双概率原对偶遗传算法
定义1:设种群数目为N, 在某一基因位上, 位值为x的数目小于N/2, 则称该基因位值为弱势基因位值, 反之为强势基因位值。
在DDPDGA中, 每个染色体上每个基因参与PD映射的概率因其位值的不同而不同, 从而进一步增强了种群的多样性。
1.1 双概率的计算
设在第t代种群中, 种群数为N, 染色体长度为L;αt (k) 表示没有参加PD映射的染色体中第k基因位值为弱基因位值的染色体数目;βt (k) 为参加PD映射的染色体中第k基因位值为弱基因位值的染色体数目;Nd为参加PD映射的染色体数;Pwt (k) 表示Nd中第k基因位值为弱势基因位值时参加PD映射的概率;Pst (k) 表示Nd中第k基因位值为强势基因位值时参加PD映射的概率;Et (k) 表示第k基因位值为弱势基因位值的期望数。
其中:
显然, 当 αt (k) +βt (k) ≥Et (k) 时, 第k基因位值为弱势基因位值的期望数已经达到, 故Pwt (k) =Pst (k) =0, 故在此重点分析 αt (k) +βt (k) <Et (k) 的情况:
(1) 当Nd=βt (k) 时, 参加PD映射的都是弱势基因位值, 则Pwt (k) =Pst (k) =0。
(2) 当Nd>βt (k) 时, 若 βt (k) =0, 则, 此时在第k基因位无弱势基因位值, 故Pwt (k) =0;若βt (k) >0, 则, 此时, 存在Cm∈ (0, 1) , 使得。
表一给出了上述推算的结果。
1.2 Et (k) 的确定与自适应调整
应动态变化的环境, Et (k) 按照最优个体适应值的变化进行自适应调整。设 η (t) 为Et (k) 的衰减因子, 计算如下:
式 (2) 中, f (t-1) 表示第t-1 代最优解的适应值, f (t-2) 表示第t-2 代最优解的适应值, 第2 代之后, 弱势基因期望数在前两代适应度的影响下进行自适应调整, 具体调整如下式所示:
由于弱势基因位值数目是按照相邻两代的最优解的适应值进行自适应调整, 所以能较好的提高算法的收敛性能。
2 最大最小蚂蚁系统算法
蚁群算法依据蚁群在不同路径上遗留信息素浓度的强弱对全局进行最优路径的搜索, 随着时间的推移, 最优路径的信息素浓度最高。最大最小蚂蚁系统算法 (MAX-MIN Ant System, 简称MMAS) [13,14,15]是基本蚁群算法的改进型算法, 能够避免因某一路径信息素过浓, 而导致所有个体全部集中在这一条路径上, 使得算法过早收敛。
要将DPPDGA与MMAS进行融合, 需要对MMAS的相关参量进行设置, 具体设置如下:
(1) MMAS信息素的初始值设置
τmax为MMAS算法中各路径信息素的最大限定值;τmin为适应求解问题的规模而预先设定的一个信息素;τG是DPPDGA阶段得到的较优解转换后的信息素值。经过对DPPDGA阶段产生的解进行信息素转换, 节省了MMAS算法信息素积累的时间, 所以把信息素的初始值设置为:
(2) 蚂蚁转移概率的设置
蚂蚁在各节点上的运动, 是根据各路径上的信息量决定其转移过程, 记Pkij (t) 为蚂蚁k在t时刻由节点i运动到节点j的概率, 具体表达式如下:
式 (5) 中, ηij表示节点i与节点j之间的能见度 (一般取节点间距离的反比) ;α 表示轨迹的相对重要性;β 表示能见度的重要性;allowedk表示蚂蚁k下一步可以选择的节点。
(4) 信息素更新模型
在算法循环过程中, 仅当前循环中的最优路径上的蚂蚁才进行信息素积累。采用如下轨迹更新方程进行操作:
式 (6) 中, τij为路径 (i, j) 在t时刻的信息素轨迹强度;△τkij (t) 为蚂蚁k在路径 (i, j) 上留下的单位长度轨迹信息素数量;ρ 表示轨迹的持久性, 0≤ρ<1, 将 (1-ρ) 理解为轨迹衰减度。
MMAS程序主要设计如下:
步骤1:当前节点、轨迹持久性、轨迹相对重要性、能见度相对重要性、蚂蚁数目等参数的设置;
步骤2:在Matlab中编写节点间的距离;
步骤3:在循环内编写禁忌表、转移概率、记录当前最优、更新路径信息素;
步骤4:达到预定迭代次数, 输出最优解;
步骤5:在Matlab中绘制图形。
3 双概率原对偶遗传算法- 蚁群算法融合
双概率原对偶遗传算法 (DPPDGA) 尽管是原对偶遗传算法 (PDGA) 的改进型算法, 相比PDGA而言, 能更好的保持种群的多样性, 但对系统中的反馈信息不能充分利用, 产生大量冗余迭代, 浪费计算资源。MMAS则能够很好的利用系统中的反馈信息, 通过对信息的累积、更新而找到最优解, 然而在算法初期需要浪费较长时间进行信息积累, 影响求解效率。
为弥补DPPDGA与MMAS的不足, 将两种算法进行融合, 将融合算法称为双概率原对偶遗传算法- 蚁群算法 (Double Probability-based Primal-Dual Genetic-Ant Algorithm, 简称DPPDGAA) 。首先利用DPPDGA算法对问题进行求解, 找出一些问题的较优解, 并将其转化为MMAS的初始信息素分布, 然后利用蚁群算法的并行性、正反馈机制等特征寻求最优解, 基本思路流程如图一所示。
4 实验仿真
4.1 测试函数
为测试融合算法性能, 选用多变量、多峰值函数进行测试。
4.2 评价标准
为了评价双概率原对偶遗传蚁群算法 (DPDGAA) 的性能, 本次测试, 将对标准遗传算法 (SAG) 、PDGA、MMAS、原对偶遗传蚁群算法 (PDGAA) 、DPPDGA、DPPDGAA五种算法分别运行20 次, 每次运行将得到一个最优值。现在从函数的稳定性、求解精度、全局寻优性、效率四方面进行评价:
(1) 稳定性评价:整个测试中, 所有最优值的平均值。
(2) 求解精度评价:在整个测试中, 最优值中最优的一个为最优解。
(3) 全局寻优性能:在整个测试中, 找到理论最优解的次数。
(4) 求解效率:每一次运行, 求最优解所需迭代次数越少, 算法的时间效率越高。
4.3 参数取值
在二进制的环境下对算法进行测试, 相关参数设置如下:
染色体规模为100;染色体长度为20*NVAR (NVAR为维数) ;交叉概率为0.9, 变异概率0.7/ (20*NVAR) ;节点数N为120, 蚂蚁数500, 启发式因子 α 为1.3, 信息素发挥因子Q为0.99, 信息素强度为500。
4.4 测试结果
测试是在处理器为Inter (R) CPU G1840 @2.80GHz, 2.00GB内存, 64 位操作系统的Lenovo计算机中进行, 通过MATLAB语言编写算法。
测试结果如表二和表三所示。
从对两个函数的测试结果来看, 双概率原对偶遗传蚁群算法 (DPPDGAA) 在求解精度、稳定性、全局搜索性等方面要优于其他四种算法。
5 结束语