进化规划算法范文（精选7篇）
进化规划算法 第1篇
在No C测试过程中, 往往用多条TAM (Test Access Mechanism, 测试访问机制) 进行并行测试。但为了防止功耗过大损坏芯片, 必须限制并行测试的TAM的条数, 控制测试功耗[3]。如何在一定功耗限制下, 将IP核合理地分配到各条TAM上, 优化测试时间, 是No C测试中的一个重要课题。
文中利用基于云模型的进化算法对No C调度规划问题进行了研究, 使得在功耗限制下优化No C的测试时间。
1 No C测试调度问题
1.1 基于No C重用的测试访问机制
在So C测试中, 测试向量通过TAM进行传输[4]。而在No C系统中, 重用No C系统中的路由 (Router) 和通道 (Channel) 等资源作为TAM, 不仅能够避免增加额外的硬件开销, 还能有效提高测试效率[5]。
1.2 No C并行测试
在文中, 采用XY路由方式, 在测试过程中采用非抢占式测试机制。具体的测试流程为[6]:外部测试设备ATE通过I/O端口连接到No C, 测试向量通过input端口输入到网络中, 通过路由输送到待测IP核中;测试响应同样通过路由输送到output端口, 被外部测试响应分析机制接收:这样就完成了一个IP核的测试。图2给出了d695中对8号和6号IP核进行并行测试时的测试路径。
1.3 NOC测试规划问题描述
在No C测试中, 如何在众多IP核的分配方案中寻找最优方案, 是No C调度规划的关键。如图2所示, 将10个待测IP核, 按照A、B两种规划调度方式分别分配到3条TAM上进行测试, B种调度方式的测试时间T2<A种调度方式的测试时间T1。任务是在众多调度方案中找到最优方案, 使测试时间最短。
2 功耗约束下No C测试规划数学模型
假设在一个No C中, 有a条TAM, TAMj上有k个待测IP核, 第i号待测IP核测试时间为Ti, 则TAMj的测试时间为
则No C总的测试时间为测试时间最长的那条TAM的测试时间
No C的测试功耗为当前所有TAM上功耗的总和
3 基于云进化算法的测试规划
基于云模型的进化算法利用云模型C (Ex, En, He) 描述进化过程[7,8], 其中Ex成为优良种子个体;En成为进化熵;He成为进化超熵。Ex正态云发生器产生下一代云滴。
3.1 算法编码
根据IP核在TAM上的分配编码, 如图1 (b) 所示, 可以得到此个体的编码为010202101, 表示编号为3、9、5、1的IP核在0号的TAM上;编号为2、7、8、10的IP核在1号TAM上;编号为6、4的IP核在2号的TAM上。
3.2 算法实现
算法包括以下步骤:初始化种群、适应度值计算、个体更新和终止判断。
(1) 初始化种群。对于一个有N个待测IP核的No C系统。随机生成一个N位的整数代码串, 表示各待测IP核在TAM上的分配方式。
(2) 适应值计算。分析种群中每个个体的染色体信息, 通过式 (2) 计算方案的测试时间作为此个体的适应值。选取当代个体中适应度值最优的n_s个个体作为种子, 利用种子进化生成新一代个体。
(3) 个体更新。分为进化和变异两部分。
种群进化采用云进化策略和自然进化策略相结合的方法。
云进化策略指利用n_s个种子, 运用一维正向云发生器产生新一代个体。将种子个体的代码串如0102021021作为一个整数, 此整数即为正态云期望Ex;Ex的取值范围ε≥ (a-1) ×109 (a为TAM个数) , 令En=ε/6;He=En/c2, c2一般取5~15之间的整数[9], 根据实验数据比较分析, 取c2=10时算法具有较好的收敛性。
当连续φ1代出现跨代精英时, 算法可能找到了新的极值领域或更加逼近原有极值领域, 这时令减小En和He的值降低算法搜索范围, 并提高搜索精度。输入数字特征值Ex、En、He, 产生nc个云滴。
自然进化策略是指采用轮盘赌的方式, 随机选择种子个体进行交叉变异, 生成新个体。
假设算法的连续平凡带数为λ, 阈值为λ1、λ2和λ3 (λ1<λ2<λ3) 。当λ<λ1时, 只采用云进化策略更新个体;当λ>λ1时, 云进化策略和自然进化策略联合更新个体, 其中云进化策略更新nc个新个体, 自然进化策略更新ne个新个体, k=ne/nc。当λ>λ2时, 增大k以提高自然进化算法生成新个体的数目;同时提高En、He, 增大搜索范围。当λ>λ3时, 对部分种子个体进行变异操作。若最大迭代次数为λmax, 本文取λ1=λmax/10, λ2=2λ1, λ3=5λ1时, 算法的效率较高。
变异操作针对种子个体进行。针对适应度值最好的前h个种子个体的编码串, 逐位求平均数然后4舍5入取整, 作为新的种子。
(4) 终止判断。如果进化代数达到最大的迭代次数, 或达到进化最大平凡代数, 则终止迭代输出结果;否则转到步骤 (2) 。
4 结果及分析
文中采用ITC'02 So C标准电路中的d695电路作为实验对象, 其作为3×4网格结构的No C系统, 有10个待测IP核。测试的基准时钟为fT=1 GHz, 限制功耗设置为测试总功耗的50%。实验环境为:Intel (R) (CoreTM) -2410M i5 2.3 GHz CPU, 4 GB内存;程序源代码通过C++语言编写, 并在VC 6.0上编译运行, 其中正向云发生器用Matlab 7.0的MCC方式与VC混编实现, 程序在Windows XP操作系统下运行。
实验分别对No C系统上有2条、3条和4条TAM进行测试, 且有功耗限制和无功耗限制两种情况。并将得到的测试数据和文献[10]中基准测试数据作比较。文献[10]将待测IP核按照测试时间进行排序后, 根据资源空闲和功耗约束, 将IP核依次分配到各TAM上, 属于传统的测试规划方案。二者对d695电路的测试数据比较如表1所示。
通过表中数据可以看出, 当TAM的数量增多时, 由于并行测试IP核的数量增加, 相应的总测试时间是逐渐降低的;相比于无功耗限制和50%功耗限制两种情况, 无功耗限制时的测试时间更小。
对比本文中的测试方法和文献[10]的基准测试数据可以发现, 应用云进化算法的应用明显提高了测试效率, 其中最大的优化幅度达到了28.8%。
由以上测试数据可得, 由于云进化算法拥有搜索范围大且收敛快的特点, 将其运用到测试规划中, 相对比与传统的测试规划方案能够有效地降低测试时间, 提高了测试的效率。
5 结束语
文中在功耗限制下对No C中待测IP核的测试进行规划。在2D网格结构下, 重用No C的路由和通道作TAM进行测试, 并用XY路由方式选择测试路径, 运用云进化算法对待测IP核在TAM上分配方式进行寻优。实验结果表明, 通过本文设计的方法所得到的测试方案能有效降低测试时间, 提高No C系统待测IP核并行测试的效率。
参考文献
[1]DALLY W, TOWLES B.Router packets, not wires:on-chip interconnection networks[C].Las Vegas, NV:Proc.The Design Automation Conference, 2001:684-689.
[2]谭耀东, 刘有耀.NoC系统研究综述[J].西安邮电学院学报, 2008, 13 (1) :5-9.
[3]许川佩, 姚芬, 胡聪.基于云进化算法的NoC资源节点优化测试研究[J].电子测量与仪器学报, 2012, 26 (3) :192-196.
[4]许川佩, 胡红波.基于量子粒子群算法的SoC测试调度研究[J].仪器仪表学报, 2011, 32 (1) :113-119.
[5]LIU Chunsheng, LINK Z, PRADHAN D K.Reuse-based test access and integrated test scheduling for network-onchip[J].Computer Science, 2006 (2) :90-95.
[6]欧阳一鸣, 张岚, 梁华国.一种时间优化的NoC低功耗测试调度方法[J].中国科学技术大学学报, 2010, 40 (5) :540-545.
[7]叶琼, 李绍稳, 张友华, 等.云模型及应用综述[J].计算基础工程与设计, 2011, 32 (12) :4198-4201.
[8]张光卫, 何锐, 刘禹, 等.基于云模型的进化算法[J].计算机学报, 2008, 31 (7) :1082-1091.
[9]许川佩, 覃上洲.基于云子粒子群算法的SoC测试规划研究[J].桂林电子科技大学学报, 2010, 30 (5) :463-468.
进化规划算法 第2篇
差分进化算法[5](DE)是Storn和Price在1995年提出的一种在连续空间中进行启发式随机搜索的优化算法。 该算法直接采用实数直接运算,不需要编码和解码操作,收敛速度快,稳定性好,其性能被证明要优于其他进化算法[6]。 目前DE已成功应用于求解经济负荷分配[7]、无功优化[8]、变电站选址定容[9]等电力系统优化问题。虽然DE算法实现简单、收敛快速,但是该算法以随机概率选取试验个体进行进化, 容易陷入局部最优,出现早熟收敛现象,若通过增加种群规模以提高种群多样性的方式会降低算法的收敛速度。为改善DE的性能,更好地解决电网规划问题,本文构造一种改进的混合差分进化算法(IHDE),进一步提高算法的收敛速度和全局寻优性能,并以Garver-6节点系统和18节点系统算例验证了此算法的寻优能力。
1电网规划数学模型
本文在单阶段静态电网扩展规划问题中, 主要考虑电网扩建的投资费用、 固定运行维护费用以及系统年运行费用(即网损费用),在满足约束条件的情况下使总费用最小,规划方案能满足N-1检验。其各种费用的计算考虑了资金的时间价值,采用等年值费用法。 模型采用的目标函数为:
式(1)中:第一项为规划方案的建设投资费用,万元;第二项为线路的可变运行费用,用年网损费用表示,万元。其中k1为资金回 收系数 ,r为贴现率,%;n为工程经济使用年限;k2为工程固定运行费用率,%;cj为单位长度线路造价,万元 /km; xj为线路j中新建线路回路数;lj为线路j的长度,km;Ω1为待选新建线路集合;k3为年网损费用系数;这里k2=ρτ/U2;ρ 为网损电价,元 /(k W·h);τ 为最大负荷损耗时间,h;U为系统额定电压,k V;rj为线路j的电阻;Pj为正常情况下线路j输送的有功功率,MW;Ω2为网络中已有的和新建的线路集合。
模型考虑的约束条件包括系统潮流约束,线路容量约束,输电走廊最大可建线路约束,其数学表达见文献 [10]。 潮流计算采用直流潮流模型。
2差分进化算法及其改进
2.1基本差分进化算法
差分进化算法由Np(种群规模)个D(决策变量个数)维参数矢量xij(i=1,2,…, Np;j=1,2,…,D)在搜索空间进行并行直接的搜索。DE的基本操作包括变异、交叉和选择3种操作。
(1) 变异。
式(2)中:为第G代中随机采样的个体;是与目标个体对应的变异个体,且随机F为缩放因子,用于控制差异向量的缩放程度。
(2) 交叉。
式(3)中:CR∈(0,1),为交叉概率,它控制着种群的多样性,帮助算法从局部最优解中脱离出来;rj为第j个变量的随机数;ri是从[1,D]中随机选取的一个整数。
(3) 选择。 对于最小化问题,选择操作可表述为:
2.2差分进化算法的改进
DE采用贪婪策略进行选择操作,虽然加快了算法的收敛速度,但在算法的后期收敛速度较慢, 甚至会陷
入局部最优出现早熟现象[11]。 鉴于此,本文构造一种改进的混合差分进化算法(IHDE),该算法在求解过程中能够随进化过程动态调整DE的缩放因子和交叉概率, 在保持种群多样性的同时提高DE的全局寻优能力;而针对DE早熟收敛问题,以种群的适应度方差判断种群中个体的聚集程度,引入混沌搜索策略,提高算法后期的搜索能力。
(1) 控制参数的改进。 DE算法的主要控制参数F和CR影响搜索过程的收敛速度和鲁棒性,F和CR取值较大可以得到较好的搜索但算法的收敛速度会较慢, 取值较小会使算法陷入局部最优。 良好的搜索策略应该是在搜索的初始阶段保持种群多样性, 进行全局搜索,而在搜索的后期应加强局部搜索能力,以提高算法的精度。 本文对F和CR采取根据进化代数动态调整策略,即在算法的初期取较小的F和CR,随着种群进化, 不断增大两参数的取值,以保证其收敛性。
式(5,6)中:Fmin和Fmax为最小和最大缩放因子;CRmin和CRmax为最小和最大交叉概率;G为当前迭代次数; Gmax为最大迭代次数。
(2) 种群适应度方差。 随着种群的不断进化,个体之间的差异越来越小, 而个体位置决定了个体的适应度, 根据种群中所有个体的适应度的整体情况可以判断种群的状态。 种群的适应度方差定义为:
式(7)中:Np为种群个体数目;个体i的适应度为fi;当前种群的平均适应度为fav; f为归一化定标因子, 其作用是限制 σ2的大小。
f的取值采用式为:
适应度方差反映了种群中个体的聚集程度,σ2越小,种群中个体的聚集程度越严重。 当 σ2< C(C为某一给定的阈值,本文取C= 0.05Np)时,认为算法出现早熟收敛现象。
(3) 混沌搜索策略。 针对早熟收敛现象, 本文在DE算法陷入局部最优时对当代最优个体进行混沌搜索,使算法脱离聚集状态。 混沌是自然界广泛存在的一种非线性现象,由于混沌运动的固有特点及混沌遍历的规律性及不重复性,使混沌处理方法被广泛用于处理优化搜索问题[12]。 混沌搜索常用的映射方式为线性载波:
式(9)中:μ 为控制参数,其数值直接影响映射情况;k为混沌搜索的迭代次数;yk为混沌变量Yk的各维分量。
设当代最优个体为Xbest,将Xbest通过载波的方式映射为混沌变量Yk,运用混沌优化的搜索机理,将混沌变量Yk转换到解空间,计算其适应度f(Y'k+1) 并更新混沌迭代得到的最优解Y'best, 直到达到混沌搜索的最大迭代次数kmax。 如果混沌搜索得到的最优解Y'best优于Xbest,则用Y'best随机取代种群中的一个非最优个体。
2.3改进混合差分进化算法流程
本文利用混沌搜索机制, 并将其融合到差分进化算法中,构造了改进的混合差分算法(IHDE)。 其基本思想是基于差分进化机制,动态调整其控制参数,以种群适应度方差判断算法是否出现早熟收敛现象,若陷入局部最优,则对当代最优个体进行混沌搜索,在搜索达到给定次数后,用混沌搜索得到的最优解随机替代种群中的个体,从而增强算法的搜索性能。 该算法流程如图1所示。
3基于改进混合差分的电网规划问题求解
基于上述改进的混合差分进化算法, 对第1节描述的单价段输电网规划数学模型求解步骤:(1) 输入原始数据。 包括网络拓扑、线路参数、各节点发电出力及负荷以及算法本身需要的控制参数;(2) 形成初始种群。 本文对n条待选线路走廊的各种可能扩建回路数进行编码,n条待选线路走廊的扩建回路数集为{x1,x2,…,xn},该线路集构成一个规划方案,对应于种群中的一个个体;(3) 差分进化操作。 采用第2.1节中的变异和交叉机制形成新一代种群;(4) 个体适应度计算。 将每一个体对应的网络行潮流计算,若个体不满足约束条件的要求,则通过适应度中的惩罚项将个体自然淘汰, 对满足约束的个体计算方案的投资和网损费用, 进而求出个体的适应度值;(5) 计算种群适应度方差,若 σ2< C,则对最优个体进行混沌搜索,否则到步骤(6);(6) 根据差分进化代数调整F和CR;(7) 如满足中止条件,则到步骤(8), 否则返回到步骤(3);(8) 输出规划结果。
4算例及分析
以修改过的Garver-6节点和18节点系统为算例进行计算与分析,系统中节点数据、支路数据和可扩建走廊数参见文献[13]和文献[10]。 设资金贴现率r取10%;工程经济使用年限n为15年 ,工程固定运行费用率k2为5%,网损电价 ρ 为0.3元 /(k W·h),最大负荷损耗时间 τ 为3000 h, 单位长度线路的投资费用为80万元 /km,取单回线走廊宽度为48.27 m ,双回线走廊宽度为68.27 m ,三回线走廊宽度为88.27 m,四回线走廊宽度为108.27 m。
以MATLAB2007为仿真环境,对电网规划问题各进行50次计算,各算法求得平均计算时间和搜索成功率,如表1、表2所示。
6节点系统算例中, 本文同时也利用GA,PSO算法进行了编程计算。 表1列出各算法对在满足线路的N-1安全准则的条件下所求得的规划方案的投资维护费用、网损费用以及综合费用。 其中文献[14]采用基于适应度函数值共享的小生境改进遗传算法求解该问题; 文献[15]采用改进的带双重变异算子的粒子群算法求解该问题;而文献[16]采用基于精英策略的非支配排序遗传算法(NSGA-II),采用投资维护费用、网损费用和 “N-1”过负荷量最小的多目标优化方法。 文献[14—16] 中3种改进算法的各部分费用均按本文设定的系数进行了折算作为比较。
由于18节点系统是按静态安全的“N”准则来研究输电规划的常用算例,因此对18节点系统设定各线路走廊的可架线路回数为3回, 以使规划方案能够满足 “N-1”安全准则。18节点系统的2种最优规划方案见表2,DE算法和本文采用的IHDE算法能够得到相同的2种最优方案,2种方案下的线路扩建结果虽略有不同, 但费用相等。
IHDE和DE算法的种群适应度方差的变化曲线如图2所示。
由图2可见,IHDE算法在进化后期对最优个体进行混沌搜索,使种群脱离聚集状态,拓展了种群的搜索空间,改善了群体适应度方差的分布情况,避免算法陷入早熟收敛,从而有更好的全局寻优能力。
图3展示了GA,PSO,DE以及IHDE 4种算法下的电网规划方案费用随种群进化代数的变化情况。
综合表1、表2和图3可见,DE算法本身具有较好的寻优能力和搜索精度,DE及改进的IHDE算法在优化结果和算法性能上(如搜索时间和搜索成功率)都优于GA,PSO算法。 比较IHDE算法和基本DE算法,虽然两者得到的最优结果相同,但是由于IHDE采用了控制参数调整和混沌搜索策略,IHDE算法性能更加稳定, 搜索到最优解的成功率明显高于基本DE算法,且能够比DE算法更早求得最优解。 而由于IHDE算法需要实时跟踪群体的聚集程度, 其计算速度略不如基本DE算法。
5结束语
本文提出了一种改进的IHDE算法,利用差分进化机制实现简单、收敛速度快的优点,对基本DE算法进行了改进。 该算法能够随进化过程动态调整控制参数, 进一步提高搜索性能; 同时针对算法后期容易陷入局部最优的问题, 以种群的适应度方差判断种群中个体的聚集程度,对最优个体采取混沌搜索。 将IHDE算法应用于求解单阶段静态电网规划问题, 通过对修改过的Garver-6节点系统和18节点系统的计算和分析表明, 相对GA,PSO和基本DE算法,IHDE算法在搜索效率、计算精度、收敛稳定性、全局寻优能力等方面都有一定的优越性。
摘要：提出了一种改进的混合差分进化算法求解电力系统输电网扩展规划问题。在进化过程中,该算法能够动态调整差分进化的控制参数,并根据种群的聚集程度对最优个体进行混沌搜索,提高后期的搜索能力。该算法在保持基本差分进化算法结构简单的特点的基础上,进一步提高了算法的全局寻优能力。运用该算法对修改后的Garver-6节点系统和18节点系统的进行计算,将其结果与遗传算法、粒子群算法、基本差分进化等算法相比较,表明了算法在求解电网规划问题上的可行性和优越性。
进化规划算法 第3篇
进化规划(EvolutionaryProgramming,简称EP)是模拟自然进化过程的一种随机方法,是60年代由美国的L.J.Fogel等人为求解离散有限状态机的演化规划而提出的[1]。进化规划是进化算法中的一种,由于在进化过程中的“变异”算子,这种搜索策略有利于避免搜索过程陷入局部极小,有利于提高求得全局最优解的可能性。但应用实际表明,在优化问题中,进化规划对于局部收敛性问题并不具有优势。
单纯形法(SimpleX Method,SM),也可称为可变多面体搜寻法,是求解非线性多元函数、无约束极小化问题的有效方法之一,由尼尔德(J.A.Nelder)和米德(R.Mead)于1965年提出[2]。单纯形法是一种直接搜索法,其优点是方法简单、计算量小、收敛速度快,且不要求目标函数可导,因而适用范围较广。但是单纯形法只是一种局域的搜索方法,不能保证是全局最优点。
针对上述进化规划(EP)和单纯形法(SM)的不足,综合两种方法的优势,文献[3]提出了基于进化规划和单纯形法的混合算法-EPSM策略。现对该算法的收敛性进行了分析并给出了收敛性的证明。
1 改进的进化规划算法-EPSM算法策略
1.1 标准进化规划
具体请参见文献[3],这里不赘述。
1.2 EPSM算法步骤
Step1编码与初始群体的设定
选择合适的群体对进化规划算法的收敛具有很重要的影响,一般群体的规模选为50—150之间。与传统的进化方法不同,参数基因的表达方式不用二进制,而采用十进制随机数初始化,形成初始群体。置t=0,t为进化的代数。
Step2适应度的计算
根据问题的需要选择合适的适应度函数,这里选择目标函数为适应度函数,并计算各个体的适应度值F(xi(t)),其中,t为进化代数,i=1,2,…,m。
Step3选择过程
采用联赛选择方法。联赛选择方法即从群体中任意选择一定数目的个体(称为联赛规模),其中适应度最高的个体保存到下一代,这一过程反复进行,直到保存到下一代的个体数目达到预先设定的数目为止。联赛规模取2。在比较过程中,对每个比较都要重新采样,这样保证最好的个体被置为适应值最大而保存
Step4变异
将需要变异的个体,按指数变化规律,通过增加高斯随机数,进行变异,具体方法如下:
上式中Δcij为参数的改变量,αp为参数变化率,其一般为介于0到1之间的常数,Fmax,Fk分别为每代中个体的最大适应度和第k个个体的适应度,γij是均值为0,方差为1的高斯随机数[4]。
Step5反射操作
单纯形法的迭代运算由反射、扩张、压缩、收缩等四种运算组成。现只选择单纯形法的四种迭代运算中的反射,这种方法也被称为基本单纯形法。具体策略是将单纯法中的对称点即反射操作作为一种进化算子,它将与变异算子同为进化算法中的算子。基本单纯形法首先由Spendley等人提出。可以定义单纯形点的数目等于搜索空间的维数加1。对于一个有N个变量优化问题,用单纯形法搜索最优解,可通过赋值X1,X2,…,XN+1一组点。这种方法通过产生新的点XR来代替单纯形中最坏的点XW,这样反复进行以连续形成新的单纯形。具体操作如下。
假如被选定的“坏”样本是XW,则代替该样本的新样本为XR,
其中,XW是被选定的“坏”样本,XR是XW的对称点即反射点,新的单纯形的点为X1,X2,…,XW-1,XW+1,…,XN+1,XR,反复迭代循环直到步长小于给定值或在最优解的范围内[5]。
每个个体在产生其反射点时,都以群体规模中的N+1个个体构成单纯形为参照,设单纯形法概率即反射率为Ps,则所产生的个体数N等于反射率乘以群体规模。具体操作是在群体规模中随机选取N+1个个体,再按其适应值将它们排序。将适应值最低的选为“坏”个体,然后按(3)式求出其反射点并用其反射点代替它
按上述过程反复进行,若不满足要求,则t置为t+1,返回Step2进行适应度的计算,直到满足要求为止。
2 收敛性分析
有关EP的理论分析还很少,其数学基础尚未建立。主要工作是D.B.Fogel给出的EP的收敛性分析。现假设为中R n的有界单连通闭区域,函数f(x)是区域上的连续函数,X∈且有有限个极值点[6]。下面给出连续空间的EPSM算法收敛性的分析。
考虑全局优化问题
则(5)的多个可行解的一个集合称为一个种群,种群中的每一个元素(可行解)称为一个个体,种群中个体的数目称为种群的规模。
定义2如果对某个ε﹤0,可以确定水平集:
引理1设X(t)={x1(t),x2(t),…,xm(t)}为进化规划产生的第t代种群,t为进化代数。则进化过程{X(t),t∈Gen}是单调不增的,其中Gen为进化代数。
证明∵由进化规划的算法结构,min{f(s)│s∈X(t+1)}≤min{f(s)│s∈X(t)}成立,
∴进化过程{X(t),t∈Gen}是单调不增的。
引理2假设整体最优点不孤立,即μ(Lf﹡+ε)﹥0,其中μ(·)为Lebesgue测度。则ε﹥0,μ(Lf﹡+ε)>0,有条件概率序列μk满足
证明取正数r,0﹤r﹤1,则存在正数M,当k﹥M时,μk(Lf﹡+ε)≥1-r,
即1-μk(Lf﹡+ε)≤r,
定理1设{xk(t)}是EP算法产生的序列,k=1,2,…,m,t为进化代数,且假设成立,则序列{f(xk(t))}以概率1收敛于f*,即
证明设xk(t)∈Lf*+ε,t′≥t+1,∵由引理1知{x(t),t∈Gen}是单调不增的,
定理2 EPSM混合算法以概率1收敛全局最优解。
证明设x﹡=argminf(x),{xk(t)}是EP算法产生的序列,{yk(t)}是EPSM混合算法产生的序列,k=1,2,…,m,t为进化代数。
由进化规划算法和EPSM混合算法结构可得,f(xk(t))≥f(yk(t))≥f(x﹡),
又∵由定理1知{xk(t)}是收敛序列,
∴由序列夹逼定理得,{yk(t)}也是收敛序列,即
为EPSM混合算法产生的第t代种群,故得证。
3 仿真算例
为了比较EPSM算法与EP算法的性能,采用相同的控制参数与初始权值来训练RBF网络。考虑如下被辨识系统:
采用具有一个输入节点、一个输出节点且隐节点数待定的RBF网络拟合该函数,形象化地描述为1-4-1的RBF网络[3]。训练初始值为:群体规模为70,αp=0.1,变异率为0.1,反射率为0.1。训练最大迭代代数为2 000代。2 000代中最优个体误差的变化如图1。由仿真结果可知,EPSM算法比EP算法具有更快的收敛速度与收敛精度。
4 结论
针对进化规划(EP)和单纯形法(SM)的不足,综合两种方法的优势,本文提出了基于进化规划和单纯形法的混合算法(EPSM),并对EPSM算法的收敛性进行了分析和证明。该算法以单纯形法中的反射操作为进化规划的一个算子,结合进化规划与单纯形法二者的优点。该算法包含了随机性搜索和确定性搜索,在一定程度上避免了EP过早收敛的缺点,同时也增强了EP的寻优能力,是一种很有潜力的优化算法。通过仿真结果表明此法不仅收敛速度快计算简单而且拟合精度和跟踪性能也好。
参考文献
[1]陈国良,王煦法,庄镇泉,等.遗传算法及其应用.北京:人民邮电出版社,1996:271—284
[2]何献忠,李萍.优化技术及其应用(第二版).北京:北京理工大学出版社,1995:19—31
[3]Wang Xiaolan,Dong Jianghui,Wang Huizhong.Evolutionary Pro-gramming Algorithm With an Operator of Simplex Method.Journal of Gansu University of Technology,2002;E—6(1):65—69
[4]Hwang H S,Automatic design of fuzzy rule base for modeling and control using evolutionary programming.IEE Proc-control Theory Ap-pl.,1999;146(1):1—15
[5]Yen John,Liao J C.,Lee Bogju,et al.Ahybrid approach to model-ing metabolic system using agenetic algorithom and simplex method.IEEE Trans on Systems,Man and Cybrnetics,1998;28(2):173—191
进化规划算法 第4篇
输电网络规划是电力系统规划的重要组成部分,其任务是根据电力系统的负荷及电源发展规划,在现有电网的基础上,合理地选择扩建线路以满足电力系统安全运行和经济性最优[1]。输电网络规划在本质上是一个具有离散性、非线性等多重约束的混合整数规划问题[2]。现有的输电网络规划方法主要有:(1)数学优化方法[3,4],该算法将电网规划问题转化为运筹学中的数学规划模型而进行求解,但规划中有些决策因素难以用数学模型表达,且数学上的最优解未必是符合工程实际的最优方案。(2)启发式方法[1],以直观分析为依据,基于网络系统某一性能指标对可行路径上一些线路参数进行灵敏度分析,选择最能改善网络性能的一条或多条待选线路,不断修正规划方案直到满足要求为止,其优点是直观、灵活、计算时间短,但由于没有考虑待选线路之间的相互影响,理论上无法找到最优解。(3)人工智能算法,如模拟退火算法[5,6]、粒子群算法[7]、遗传算法[8,9,10]、Tabu搜索法[11,12]、模拟植物生长算法[13]等。这些具有随机性和协同性的人工智能算法能以较大概率收敛于全局最优解,但它们都属于单模式,各自都有其自身的缺点,如模拟退火算法计算量大,全局搜索能力较弱,搜索效率不高;Tabu搜索法对初始值的依赖性强。
食物链生态进化算法(Ecology Evolutionary Algorithm of Food Chain,EEAFC)是一种多模式协同进化的生态进化算法,多种群模式并存的隔离进化机制可以使得算法同时具有良好的全局搜索能力和局部搜索能力,已在布局优化问题[14]及配电网重构[15]中获得了应用,并取得了理想结果。
本文根据食物链生态进化算法各级种群的不同特点,从改善EEAFC的收敛性能出发,提出了改进的食物链生态进化算法(Improved Ecology Evolutionary Algorithm of Food Chain,IEEAFC),并应用其求解了输电网络优化规划模型。选用18节点系统作为测试系统,验证了本文所提方法的可行性和优越性,并用一个实际系统检验了算法的适应性。
1 输电网络规划的数学模型
输电网络规划的任务是寻找满足相关约束条件的输电网络最优建设方案。鉴于输电网络的运行费用远小于其投资费用,本文目标函数只计及线路的建设投资费用,即式(1)。
约束条件s.t.
式中:J为目标函数;Ω为待扩建走廊首、末节点集合;Cij为待扩建走廊i-j中每条新增线路的投资;nij为走廊i-j中新增线路回数;B为系统节点导纳矩阵;θ为节点相角列向量;PG为发电机出力列向量;PD为负荷列向量;xij为走廊i-j线路电抗;nij,0为走廊i-j中已经存在的线路回路数;θi为节点i的相角;Pij为走廊i-j的总潮流;Pij,max为走廊i-j的单条线路容量上限;nij,max为走廊i-j可新增线路回数的上限。约束条件中还包括网络连通无弧岛。
2 食物链生态进化算法
2.1 食物链生态进化算法的基本思想
食物链生态进化算法将生态环境压力对应于待优化问题的适应度函数值,食物链上每个生物体映射为待优化问题的一个候选解,模拟食物链能量传递方式构造进化链。它是以自然基因选择机制和物种竞争机制为基础的多种群模式协同进化搜索算法,在搜索过程中不断更新各种群内的个体并进行种群间的个体调整。
求解优化问题时,EEAFC从代表问题可能潜在解集的初始种群出发,种群内部采用选择、交叉、变异等操作算子纵向进化,种群外部通过种群间模式调整横向进化,实现了个体之间、种群之间信息交换和结构重组,使得种群品质不断提高并逐渐逼近全局最优解。食物链生态进化算法一般取高级、中级、低级三个种群模式用于求解优化问题,详细的计算流程可参考文献[14]。
2.2 算子选取及改进
食物链生态进化算法在种群内部采用选择、交叉、变异等算子纵向进化,这些算子直接影响到算法的计算效率及收敛性能,需根据所求解问题的特点进行选取。
2.2.1 选择算子
选择算子的作用是从当前代群体中选择出一些比较优良的个体,并将其复制到下一代群体中。最常用的是比例选择操作,其基本原理是个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。比例选择方法给予了适应度函数值低的个体被选择的机会,但另一方面也可能淘汰适应度函数值高的个体。为确保适应度函数值高的个体一定能够被保留到下一代群体,出现了确定式采样选择操作,其基本思想是按照一种确定的方式来进行选择操作,具体操作过程是:按照式(6)计算群体中各个个体在下一代群体中的期望生存数目Ni;根据Ni的整数部分确定各个对应个体在下一代群体中的生存数目,其中表示取不大于Ni的最大整数,由此可确定出下一代群体中的个个体;然后按照Ni的小数部分对个体进行降序排序,顺序取前个个体加入到下一代群体中[16]。
式中:NPOP为种群规模;Fitness(i)为食物链上个体i的适应度函数值。
食物链生态进化算法将种群分成多种模式,从低级模式到高级模式,种群的规模逐渐减少而种群的质量逐步提高。基于这个特点,提出各种群采取以下的选择方法:(1)低级模式种群规模较大,弱势个体相对较多,为保证优势个体一定能够被选择,采用确定式采样选择操作;(2)中级模式相对于低级模式其种群数量显著减少,个体质量也普遍较高,为保持食物链上种群的多样性,避免优势个体大量复制而较差的个体也有一定的进化机会,采用比例选择操作;(3)高级模式种群规模很小,个体品质很高,不进行选择操作而直接进交叉环节。
2.2.2 交叉算子
对随机选定的两个个体随机确定交叉位进行一点交叉。由于交叉操作具有随机性,交叉后有可能产生网络不连通的新个体,因此对交叉产生的两个新个体进行连通性校核,若两个新个体都满足连通性要求,则用两个新个体取代交叉前的两个个体;只要有一个新个体不满足连通性要求,则放弃两个新个体而继续保留交叉前的两个个体。
2.2.3 变异算子
随机选定变异的个体并随机选定变异位,对选定的变异位取[0,n]范围的但不包括变异位现有取值的随机整数,其中n为变异位所对应走廊可新增线路回数上限。对变异后新个体进行连通性校核,若新个体满足连通性要求,则用新个体取代变异前的个体;若不满足连通性要求,则放弃新个体而继续保留变异前的个体。
2.2.4 优良种群保留策略
在食物链生态进化算法的运行过程中,通过对个体进行交叉、变异等操作而不断产生出新的个体。随着计算过程的进行,优良个体将不断增加。但交叉、变异等操作的随机性也可能破坏掉当前群体中适应度最好的个体,从而对算法的运行效率和收敛性产生负面影响。为了解决这一问题,采用了最优保存策略,其具体操作是:将经过交叉、变异操作后的高级种群个体与当代进化前记忆的高级种群个体进行适应性比较,如果前者种群中的最大适应度函数值小于后者种群中的最大适应度函数值,则用后者种群中的最大适应度函数值所对应个体替换前者种群中的最小适应度函数值所对应个体,更新高级种群信息。
3 基于IEEAFC的输电网络规划
3.1 基于线路走廊的实数编码
合理的编码形式应能够恰当地描述解的结构和形态并能有效地提高算法的搜索效率以及便于评价方案的优劣性。根据输电网络规划的特点,本文选用具备新建(扩建)线路的走廊作为决策变量,将决策变量表示成适合于IEEAFC求解的码串形式,并采用实数编码方法。染色体长度即待添加线路的走廊数,染色体基因位上的实数编码值对应一条待扩建走廊中添加的线路回数,一条染色体即个体表示一个输电网络规划扩建方案。染色体结构形式如图1所示。
基于线路走廊的实数编码将输电网络规划问题的解用实数来表示,较二进制编码方法显著降低了变量的维数,缩小了搜索空间,提高了寻优效率,同时便于引入问题的相关信息(如约束条件)。
3.2 约束条件处理
输电网络规划是一个非线性整数规划问题,本文对约束条件的处理方法如下:
a)上述基于线路走廊的实数编码的设计方法使得式(5)所示的待扩建走廊能架设的最大线路回数约束自动得到满足。
b)对交叉、变异后的方案进行网络连通校核,不满足连通约束的方案直接淘汰,满足连通性约束的方案则进一步进行过负荷校核。
c)采用过负荷惩罚系数将过负荷约束并入到适应度函数中。
3.3 适应度函数
适应度函数应反映输电网络规划的目标函数及网络过负荷的状况,如式(7)所示。
式中:ω为调节系数;L为反映规划方案的投资费用及网络过负荷约束违背程度,其计算式如式(8)所示。
式中:Nsum为规划方案建设新线路的走廊总数;Ck为第k条扩建走廊新增一回线路的投资;xk为第k条扩建走廊新添加线路回数;Pen为过负荷惩罚系数;Pover为输电网络总过负荷量,其计算式如式(9)所示。
式中:Nover为规划方案中引起系统过负荷的走廊总数;Pk为第k条过负荷走廊总潮流;xk,0为第k条过负荷走廊已有线路回数;Pk,max为第k条过负荷走廊单条线路容量上限。
3.4 基于IEEAFC算法的输电网络规划流程
基于改进食物链生态进化算法的输电网络规划流程如图2所示。
1)输入计算所需的原始数据,包括各节点的负荷和发电出力、待选线路参数、现有电网结构及参数等。
2)设置食物链进化参数,包括初始种群规模NPOP、林德曼生态效率ρ、各种群交叉率pci、各种群变异率pmi、过负荷惩罚系数pen、调节系数ω、循环最大迭代次数Imax。
3)初始化种群。按3.1节所述方法将待优化问题解Z=[z 1,z 2,zl]进行编码,在满足A≤Z≤B的范围内随机产生满足连通性约束的、种群规模为NPOP的初始种群,其中A=[0,0,,0]为决策变量下限,对应整个网络待扩建线路走廊都不架设线路;B=[b 1,b 2,,b l]为决策变量上限,对应待扩建线路走廊可扩建线路回数上限。
4)按式(7)计算初始群体适应度函数值并从大到小排序,模拟食物链能量传递方式,构造高、中、低三个初始子种群。
5)多模式独立进化。中、低两个种群内部分别进行选择、交叉、变异操作,高级种群内部进行交叉、变异及优良种群保留操作,更新种群信息。
6)将进化后高、中、低三个子种群全部个体合成为一条规模为NPOP=NM1∪NM2∪NM3的食物链,将食物链上的个体按适应度函数值从大到小排序,高、中、低三个子种群依次选取食物链上个体,直至达到各级子种群规模。
7)更新最优解集Nbest,其规模Nbest可根据所求解问题的实际需要而定。从食物链顶端开始选取Nbest个相异的且不同于现有最优解集中个体的个体形成局优解集Ngood,将最优解集Nbest与局优解集Ngood合并成为一条规模为Nbest∪Ngood=2Nbest的食物链,将食物链上的个体按适应度函数值从大到小排序,选取食物链顶端Nbest个个体,形成新的最优解集Nbest。
8)判断是否满足结束条件,若循环次数I≥Imax则跳出循环并输出结果;否则,进行种群调整。
9)种群调整,开始新一轮进化。高一级种群模式中的个体将对低一级种群的部分个体根据调整度进行模式调整,然后返回到步骤5)开始新一轮的进化。
4 算例分析
4.1 18节点系统及分析
采用Matlab编程,对18节点系统进行了规划,该系统在原有10个节点的基础上新增8个节点,原有输电走廊9条,随着新节点的出现,有21条走廊可建新线路。图3给出了其初始网络及待选线路,具体的网络结构和系统参数可参考文献[1]。在计算中,假定所有线路建设投资费用为100万元/km。IEEAFC运行参数设置见表1。
采用文中规划模型及算法得到的18节点系统最优及部分次优规划方案如表2所示。通过采用保存最优解集的策略,得到了包含最优解在内的多个局部最优方案。方案1是文献[1,7-8,10-11,13]都得到的18节点系统最优方案。支路6-13代替方案1中的支路7-13得到与方案1目标值相同的方案2。方案3和方案4的路径1~11的建设回路数分别少于方案1和方案2、但路径5~11的建设回路分别多于方案1和方案2,即分别得到了比最优方案多20km线路的局部最优方案3和方案4。另外,本文还新得到其他文献未给出的方案5~8,它们比文献[13]N安全方案4、方案5少了10 km线路。体现了IEEAFC算法能在局部最优方案的基础上进一步搜索到全局最优方案的较强搜索能力。
图4显示了该算法的迭代过程,图中实线A、虚线a分别为低级种群采用确定式采样选择而中级种群采用比例选择算法(本文)的最优个体适应度函数值及全体种群的平均适应度函数值曲线,为比较起见,图中还给出了其他三种算法的计算结果,其中实线B、虚线b[实线C、虚线c]{实线D、虚线d}分别为低级及中级种群都采用确定式采样选择[低级及中级种群都采用比例采样选择]{低级种群采用比例选择而中级种群采用确定式采样选择}的最优个体适应度函数值、全体种群平均适应度函数值曲线。采用上述四种方法对算例进行计算时交叉、变异操作算子保持一致。从图4中可以观察到以下几点:(1)本文提出的低级种群采用确定式采样选择而中级种群采用比例选择算法比低、中级种群都采用同一种选择法(确定式采样或比例采样)的收敛性能都好;(2)低、中级种群都采用确定式采样选择较两者都采用比例选择收敛性能好;低级种群采用比例选择而中级种群采用确定式采样选择的收敛性能最差;(3)确定式采样所占比例越大,种群平均适应度函数值越高。
4.2 某实际系统及分析
本算例为某500 k V输电网络,该系统现有13个节点、14条支路,随着负荷的增长,到未来某一规划水平年,系统新增10个节点,有13条可增线路的走廊。取食物链上高、中、低级种群规模分别为194、50、6,线路投资费用为1 500万元/km,各种群优化参数及罚函数取值与18节点算例相同。优化得到的最优扩展规划方案见图5,扩建线路总长度1 937 km,总投资为2 905 500万元。
5 结论
根据食物链生态进化算法各级种群的规模和品质的不同特点,提出了依据各级种群的特性选取不同算子的思想。采用具备新建(扩建)线路的走廊作为决策变量,并用实数进行编码,缩短了码串长度,提高了寻优效率。通过理论分析和对算例的计算可以得出以下结论:
1)改进的食物链生态进化算法改善了多种群之间的协调性能,进一步均衡了算法的全局搜索能力和局部搜索能力,18节点系统在得到已有文献给出的多个全优和局优方案的同时,还获得了其他文献还未给出的四个比较理想的局部最优方案。
多蜂群进化遗传算法 第5篇
遗传算法(GA)是一种借鉴生物界自然选择和自然遗传机制的高度并行、随机、自适应搜索算法。它是模仿自然界生物进化过程中“物竞天择,适者生存”的原理而进行的一种多参数、多群体的并行优化方法,其应用优势在于处理传统搜索方法难于解决的复杂的非线性问题。经过20多年的发展,遗传算法已经在组合优化、生产调度、函数优化、机器学习、图象处理等许多领域得到成功的应用,并显示出其良好的性能。
通过遗传算法求解问题时,人们总是期望在尽量短的时间内达到或尽可能接近问题的全局最优解。当遗传算法停止时,往往只是取出种群中最优个体作为遗传算法的结果。这是因为,群体中最优个体和全局最优解之间的亲和度[1]要大于群体中其他个体和全局最优解之间的亲和度。因此,在遗传算法中如何利用每一代的最优个体所包含的特征信息去产生下一代更优秀个体是其必须考虑的问题。Eiben等用Markov链证明了保留最优个体(Elitist Preserved)遗传算法的概率全局收敛性[2];Rudolph用齐次有限Markov链证明了带有选择、交叉、变异操作的经典遗传算法收敛不到全局最优解[3]。但是,若在遗传算法中保留每一代的最优个体,则算法将收敛到全局最优解。这些都表明种群最优个体对算法的重要意义。在遗传算法中采用最优保留策略可以保证算法的全局收敛性。因此,对保留下来的最优个体如何利用,以提高算法性能则需要进一步研究。
蜜蜂进化型遗传算法(BEGA)[4]从蜜蜂的繁殖进化过程中抽取出适合遗传算法的一些机制并融入算法之中。BEGA充分利用种群中最优个体对种群的进化作用,同时,为维持个体的多样性,引入了蜜蜂繁殖过程中“外来种群”的思想,在算法性能上较标准遗传算法有了很大提高。本文受到启发,提出一种多蜂群进化型遗传算法(MBEGA),算法中保持多个蜂群同时进化,蜂王可以选择同一蜂群或其他蜂群中的雄蜂进行交配,蜂王在其所处蜂群中采用相似性判断,以抑制其中产生过于接近蜂王的个体,最后选取多个蜂群中最优的蜂王作为问题的解。这样,既提高了种群的多样性,又避免了进化过程中的“早熟”现象,通过对函数优化问题的求解表明,这种MBEGA算法能够有效提高遗传算法的性能。
1 多蜂群遗传的抽象模型
关于蜂群的数量:蜂群数量设为M(2～50),以模拟自然界中的多个不同蜜蜂群体,在并行计算中可以将M理解为并行的处理机个数。
关于种群的构成:为降低算法复杂度,将工蜂和雄蜂统一看作普通蜜蜂,每个蜂群由一个蜂王和若干普通蜜峰构成。在与蜂王交配产生后代时,普通蜜蜂被当作雄蜂;在受到蜂王信息素抑制时,普通蜜蜂被当作工蜂。普通蜜蜂数量设为N(30～100)。
关于参与交配的雄蜂选择:在交叉概率Pc的作用下,通过选择算子按照比例γ从本种群中选择γ·N/2个个体;将其余M-1个种群看作一个整体,从中随机选择(1-γ)·N/2个个体,最后这N/2个选中个体作为选中雄蜂参与同蜂王的交配。
关于蜂王和雄蜂交配:蜂王作为种群中的最优个体,与选中的N/2雄蜂个体交配产生子代C。
关于争夺蜂王:C中的最优个体与此蜂群的蜂王竞争,失败者不是消亡(死亡或逃走),而是成为子代C中普通的蜜蜂个体,胜利者晋升成为新蜂王。
关于新蜂群:新蜂王与子代C构成新的蜂群。
关于蜂王信息素抑制:蜂王与蜂群中的工蜂逐个比较,若工蜂与蜂王间的海明距离小于阈值τ时,认为此工蜂威胁到蜂王的地位,驱逐此工蜂,并用随机算法生成新的工蜂个体补齐蜂群。
2 多蜂群遗传算法
2.1 算法描述
设定M表示蜂群个数;N表示种群大小;Bee(i,j)表示第i个蜂群中的第j个个体;Bee(i).Queen表示第i个蜂群中的蜂王;γ表示本蜂群中选择雄蜂个体的概率;τ表示抑制的阈值;Pc表示交叉概率;Pm表示变异概率。
2.2 编码方案
针对函数优化问题的特点,采用二进制编码,每个变量采用20位的0/1串表示,包括1个符号位,若干整数位(根据约束条件中的取值范围决定,若-5≤x1,x2≤5,则整数位取3),剩余位表示小数位,为解码方便,编码采用反码方案。
如染色体编码:
0011100000000000000010010011001100110000将被解码成x1=3.5,x2=-0.199 951。
2.3 杂交算子
采用均匀模板杂交算子:对选出的2个个体,随机产生一个与其串长相同的0/1串作为模板,当模板中某基因位为1时,母体中两个个体的相应位基因进行杂交互换。杂交过程如下所示。这种杂交算子对个体串中的每个基因位以等概率杂交,以等概率对每个解空间进行搜索,提高了搜索的并行性与效率。
模板:10001101000011010100
蜂王:01110010000010110010
雄蜂:11001000001011010000
子代1:11111010000011110010
子代2:01000000001010010000
2.4 变异算子
采用级联单点变异:首先将个体串拆分成每一个参量子串;然后对各子串进行单点变异;最后将子串拼接成总个体串。变异过程如下所示:
变异前:
0111001000001011000000101111001100000000
拆分:
01110010000010110000
00101111001100000000
分别在3,4位变异:
01100010000010110000
00100111001100000000
拼接:
0110001000001011000000100111001100000000
这种变异算子使每个解空间都获得相同的变异概率,不易造成参量解之间精度差异过大。同时,每个解的变异只限一位,不易因随机变异面积过大而造成个体适应值振荡,具有较好的稳定性。
2.5 选择算子
在交叉概率Pc的作用下,选择算子选出与蜂王进行交叉运算的雄蜂。算法采用两种选择方式:轮赌选择法、随机选择法。
例如:当给Bee(i).Queen选择雄蜂时,用轮赌选择法从Bee(i)蜂群中选出γ·N/2个个体;用随机选择法从其余的M-1个蜂群中选出(1-γ)·N/2个个体。
2.6 抑制算子
算法计算蜂王与本蜂群中普通蜜蜂的海明距离d(x,y)=∑(x[i]⊕y[i]),若d<τ,说明蜂王与蜜蜂个体间的相似度太高,将来杂交时难以产生相异子代,蜂王抑制该个体,将其驱逐,然后采用随机算法重新产生新的蜜蜂个体加入蜂群。抑制算子可以避免蜂群中普通蜜蜂与蜂王间的血缘太近,相似度太高,而在杂交时产生近亲繁殖,难以产生有效的相异子代,对进化无法提供有效的支持;新蜜蜂的引入,增加了蜂群的生物多样性,提高了杂交效率,有利于跳出局部最优解。
2.7 停止准则
定义1s∈S是规模为N的种群,种群s的适应度定义为该种群中最优个体的适应度。
为考察算法的性能,排除遗传算法中大量随机操作的影响,在统计学原理上采用平均进化代数和平均最大适应度[4]两个性能指标对算法进行评估。
针对种群最优个体的进化能力,为衡量算法优劣,采用两种不同的停止准则:
停止准则1:给定整数T≥1,如果
停止准则2:种群的适应度与全局最大适应度的差小于等于0.001。为保证各种不同算法均在有限迭代次数内停止,设最大迭代次数为2 000,若算法在迭代2 000次后,仍不能收敛到全局最大适应度,认为该次实验失败,否则认为成功。
2.8 改进措施
在BEGA[4]基础上,MBEGA提出两种改进策略:
(1) 将蜂群个数增加到多个,雄蜂的选择来自于其他蜂群而不是随机产生。
(2) 根据蜂王分泌信息素抑制工蜂卵巢发育的生物学特点,引入抑制算子,驱逐与蜂王个体差异小于阈值的蜜蜂个体。
第一个改进策略主要针对于BEGA中外来雄蜂随机产生的问题。在BEGA中随机产生的个体虽然能保证个体多样性,但这些参与交配的个体带有不可预知性,无法保证其质量,其产生的子代可能进化,也可能退化,带有盲目性,与生物学上“优胜劣汰”的基本思想相矛盾。
而在MBEGA中,外来雄蜂来自于其他蜂群,这样既避免了单个蜂群内部繁殖带来的“早熟”问题,又避免了随机蜂群的不可预知性,并且来自于其他蜂群的雄蜂会携带其他蜂群中的优良基因片段产于参与本蜂群的进化,对进化具有指导意义。
此外,MBEGA中引入多个蜂群能提高算法开采解空间的能力。因为MBEGA中规定多蜂群中所有的蜜蜂(包括蜂王和普通蜜蜂)都必须互不相同,这种限制使多个蜂群在同时进化时,其中的蜜蜂个体分布于解空间的不同角落上,这样不但扩大了对解空间的搜索范围,而且能减少陷入局部最优的可能性。
在算法的实现过程中,发现存在这样一种问题:由于蜂王是蜂群中的优势个体,蜂群进化若干代后,蜂群中的普通蜜蜂都会与现任蜂王存在直接或间接的血缘关系,蜂群中的生物多样性不足,其中与蜂王个体差异很小的个体与蜂王进行杂交时,杂交算子局部搜索能力下降,无法顺利产生出不同于蜂王的后代,导致算法效率下降或失败。第二个改进策略专门用于解决这一问题。
例如:假设算法采用16位二进制编码,蜂王与雄蜂如下,则均匀模板杂交很生成有效的模板序列,使杂交后的子代与父代相异。
蜂王:0100101100010101
雄蜂:1100101100010101
通过计算海明距离,对这种不利于进化的个体进行驱逐,由随机算法重新构建新的个体,可以有效地保持蜂群的生物多样性,帮助算法开辟新的搜索空间,提高算法的勘探能力。
3 实验结果与分析
3.1 实验设计
为验证MBEGA的有效性,选择五个典型函数进行性能测试,并与简单遗传算法(SGA)、最优保持遗传算法(EGA)[5]及BEGA进行了比较。
典型测试函数如下:
其中:f1,f2,f3,f4,f5的适应度函数分别为
实验中,采用二进制编码,除f2个体长度为20,其余均为40。种群规模N=50,Pc=0.85,Pm=0.01,蜂群算法中,γ=0.2;多蜂群算法中,M=20,τ=4,T=5。
针对平均进化代数、平均最大适应度两个性能指标,分别根据不同的停止准则做了两个实验。
实验一:采用停止准则1与时间边界法结合。若算法在连续T代中平均适应度值没有发生改变或算法已运行400 ms(考虑到MBEGA需要同时优化20个种群,将时间适当延长为2 000 ms)停止。SGA,EGA,BEGA和MBEGA分别对每个函数独立求解1 000次,计算其平均最大适应度,实验结果如表1所示。
实验二:采用停止准则2。SGA,EGA,BEGA和MBEGA分别对每个函数独立求解1 000次,计算其平均进化代数(只包含成功实验)和成功率,试验结果如表2所示。
3.2 实验结果及分析
实验结果及分析如表1,表2所示。
与SGA相比,EGA,BEGA和MBEGA增加了寻找最佳个体和替换最佳个体的操作,BEGA额外增加了随机生成新个体操作,MBEGA额外增加了抑制操作,并且需要同时对20个种群进行优化。虽然BEGA与MBEGA在选择候选个体时减少了一半的数量,但从总体上来看,在每次迭代过程中花费的时间超过了SGA和EGA,因此单纯比较算法寻优的时间没有实际意义。为比较的合理性,实验一中设定了算法运行时间的上限(对MBEGA做了适当延长)。表1的结果表明,在规定的时间内,MBEGA得到的解都优于SGA,EGA,在部分函数上优于BEGA,因此从平均最大适应度来看,MBEGA的优化效果最好。
实验2中的成功率是一种对算法在规定时间内优化到全局最优解的概率统计。从表2可以看出,在规定解的精度(0.001)要求下,SGA,EGA在函数f1上基本失败,在其他函数上的收敛速度(平均进化代数)也很慢,BEGA的收敛速度和成功率都有所提高,而MBEGA在收敛速度和成功率上都获得了最好的结果。因此从收敛速度和成功率上来看,MBEGA的优化效率最好。
根据表1和表2的结果可以看出,不论是优化效率还是优化效果,MBEGA均优于SGA,EGA和BEGA。
4 结 语
受BEGA的启发,本文提出了一种新型的遗传算法——MBEGA。结合蜜蜂群体的生物学特点,针对BEGA的不足,提出了两种改进措施:多蜂群同时优化,提高算法在解空间中的勘探能力,杂交个体部分来自于其他蜂群提高优化效率和抗“早衰”能力;引入抑制算子增加蜂群的生物多样性,提高了跳出局部最优的能力。最后的实验结果表明,MBEGA很好地提高了BEGA的优化效率和优化效果,因此MBEGA是一种提高遗传算法性能的有效改进算法。
参考文献
[1]王煦法,张显俊,曹先彬,等.一种基于免疫原理的遗传算法[J].小型微型计算机系统,1999,20(2):117-120.
[2]Eiben A E,Arts E H,Van Hee K M.Global Convergence ofGenetic Algorithms:An Infinite Markov Chain Analysis[A].Parallel Problem Solving from Nature[C].Heidelberg,Berlin:Springer-Verlag,1991:4-12.
[3]Rudolph G.Convergence Analysis of Canonical Genetic Al-gorithms[J].IEEE Trans.on Neural Networks,1994,5(1):96-101.
[4]孟伟,韩学东,洪炳镕.蜜蜂进化型遗传算法[J].电子学报,2006,34(7):1 294-1 300.
[5]Goldberg D E.Genetic Algorithms in Search,Opti mizationand Machine Learning[M].New York:Addison-Wesley,1989.
[6]梁艳春,周春光,李寿范.基于遗传算法的Rosenbrock函数优化问题的研究[J].软件学报,1997,8(9):701-708.
差分进化算法研究及其应用 第6篇
关键词：差分进化算法,多元函数的极值,最小值
多元函数极值问题是一类经常出现在工程设计中的问题。传统的算法大都基于传统的梯度类算法,并依赖于初始点的选取,而在一些实际问题中如何选取合适的初始点本身是一个比较困难的问题[1,2,3]。此外,对一般函数,要求出它的次梯度,甚至近似梯度都是相当困难,所以在不可微规划方面还有许多工作要做。
近年来,随着计算机技术的发展,一些群体智能算法也得到了迅速发展,文献[4]尝试应用粒子群算法求解函数极值问题,获得较好的数值结果。Storn R和Price K于1995年提出的差分进化(Differential Evolution, DE)算法[5,6]是一种随机的并行直接搜索算法,它可对非线性不可微连续空间函数进行最小化,以其易用性、稳健性和强大的全局寻优能力在多个领域取得成功。在1996年举行的第一届国际IEEE进化优化竞赛上,对提出的各种方法进行了现场验证,DE被证明是最快的进化算法。目前,DE已经在许多领域得到了应用[7,8]。
本文首先介绍了DE的算法原理、算法流程和控制参数选择,然后利用DE算法求解了多元函数的极值问题。数值实验结果表明了该方法的正确性和有效性。实验表明,和其它算法相比,该算法在搜索成功率和计算效率上有很大的优势,是求解此类不可微优化问题一种好的计算方法。
1 差分进化算法
差分进化算法(Differential Evolution,DE)是一种新兴的进化计算技术。它是由Storn等人于1995年提出的,最初的设想是用于解决切比雪夫多项式问题,后来发现DE也是解决复杂优化问题的有效技术。DE与人工生命,特别是进化算法有着极为特殊的联系。DE和微粒群算法(PSO,也称粒子群算法)一样,都是基于群体智能理论的优化算法,通过群体内个体间的合作与竞争产生的群体智能指导优化搜索。DE算法通过把种群中两个成员之间的加权差向量加到第三个成员上来产生新参数向量,该操作称为“变异”。然后将变异向量的参数与另外预先确定的目标向量参数按一定规则混合来产生试验向量,该操作称为“交叉”。若试验向量的代价函数比目标向量的代价函数低,试验向量就在下一代中代替目标向量。最后的操作称为“选择”,种群中所有成员必须被作为目标向量这样操作一次,以便在下一代中出现相同个竞争者。在进化过程中对每一代都评价最佳参数向量,以记录最小化过程,这样利用随机偏差扰动产生新个体的方式可以获得一个有非常好收敛性的结果。
1.1 基本DE算法
1.1.1 初始化
DE利用NP个维数为D的实数值参数向量作为每一代的种群,每个个体表示为:
(i=1,2,…,NP) (1)
式(1)中:i—个体在种群中的序列;G—进化代数;NP—种群规模,在最小化过程中NP保持不变。
为了建立优化搜索的初始点,种群必须被初始化。通常寻找初始种群的一个方法是从给定边界约束内的值中随机选择。在DE研究中,一般假定对所有随机初始化种群均符合均匀概率分布。设参数变量的界限为x
式(2)中:rand[0,1]——在[0, 1]之间产生的均匀随机数。如果预先可以得到问题的初步解,初始种群也可以通过对初步解加入正态分布随机偏差来产生,这样可以提高重建效果。
1.1.2 变异
对于每个目标向量xi,G, i =1,2,…,NP,基本DE算法的变异向量如下产生:
vi,G+1=xr1,G+F(xr2,G-xr3,G) (3)
式(3)中,随机选择的序号r1,r2和r3互不相同,且r1,r2和r3与目标向量序号i也应不同。所以须满足NP≥4。变异算子F∈[0,2]是一个实常数缩放因子,控制偏差变量的放大作用。
1.1.3 交叉
为了增加干扰参数向量的多样性,引入交叉操作。则试验向量变为:
ui,G+1=(u1i,G+1,u2i,G+1,…,uDi,G+1) (4)
式(5)中:randb(j)—产生[0, 1]之间随机数发生器的第j个估计值;rnbr(i)∈1,2,…,D—个随机选择的序列,用它来确保ui,G+1至少从vi,G+1获得一个参数;CR—交叉算子,取值范围为[0,1]。
1.1.4 选择
为决定试验向量ui,G+1是否会成为下一代中的成员,DE按照贪婪准则将试验向量与当前种群中的目标向量xi,G进行比较。如果目标函数要被最小化,那么具有较小目标函数值的向量将在下一代种群中赢得一席地位。下一代中的所有个体都比当前种群的对应个体更佳或者至少一样好。注意在DE选择程序中试验向量只与一个个体相比较,而不是与现有种群中的所有个体相比较。
1.1.5 边界条件的处理
在有边界约束的问题中,确保产生新个体的参数值位于问题的可行域中是必要的,一个简单方法是将不符合边界约束的新个体用在可行域中随机产生的向量代替。即若uji,G+1<x
另外一个方法是根据式(6)重新产生试验向量,然后进行交叉操作,直到产生的新个体满足边界约束为止,但这样做效率较低。
1.2 DE算法流程
(1) 确定DE控制参数和所采用的具体策略,DE控制参数包括:种群数量、变异算子、交叉算子、最大进化代数、终止条件等;
(2) 随机产生初始种群,进化代数k = l;
(3) 对初始种群进行评价,即计算初始种群中每个个体的目标函数值;
(4) 判断是否达到终止条件或进化代数达到最大。若是,则进化终止,将此时的最佳个体作为解输出;若否,继续;
(5) 进行变异和交叉操作,对边界条件进行处理,得到临时种群;
(6) 对临时种群进行评价,计算临时种群中每个个体的目标函数值;
(7) 进行选择操作,得到新种群;
(8) 进化代数k =k+1,转步骤(4)。
2 多元函数极值问题的求解
下面通过例子来阐明该方法。
算例1 试确定函数z=f(x,y)=(x2-2x)e-x2-y2-xy,|x|≤3,|y|≤2 极值。
解 首先绘制出该函数的图形,这里我们采用数学软件Matlab作图[9](见图1(a))。从图形上我们明显可以看到存在极值点;因此绘制该函数的等高线(见图1(b)),即把函数投影到二维空间,观察等高线的走向。
从三维图形不能很好的观察出该函数的极值所在的精确范围,但是通过画等高线,立刻可以观察出该函数的2个极值分别在(-1,0.5)和(0.8,-0.3)附近.因此可以在这两个点的附近取一个初始值,然后调用一些优化软件包便可以快速地达到最优解,传统算法在选取初试点的时候必须这样做。
下面我们采用DE算法来求解该函数在给定范围内的最小值,DE算法的初始点是随机产生的,DE算法的选择操作直接将目标函数值作为适应度值,然后比较适应度值,适应度值小的个体保存到下一代(目标函数值为最小值),而不像遗传算法有各种复杂的选择策略。与遗传算法相比,差异演化算法操作简单,控制参数少,易编程实现,它尤其擅长求解多变量、非凸、多峰以及非线性的函数优化问题,所以很受研究者的青睐。取群体规模NP=60,初始交叉CR=0.3,初始缩放因子F=0.1,算法终止的最大进化代数G=50, 调用DE算法,运行结果如图2所示。
由计算结果知,DE算法能够快速收敛到上述函数在给定范围内的最优值(0.611 05, -0.305 52),
相应的目标值为-0.641 424。
算例2 试确定函数
解 参数设置和算例1一致,调用DE算法,计算结果如图3所示。
由计算结果知,DE算法能够快速收敛到上述函数在给定范围内的最优值(0.228 28, -1.625 5),相应的目标值为-6.551 133。
3 结束语
本文针对多元函数极值问题,给出了此类问题的一种新的有效算法——差分进化算法来搜索最优解。计算结果表明,在计算的准确性方面能够得到和文献[10]相当的结果。可见,利用差分进化优化算法求解此类问题,可使算法简单直观,容易实现,计算成功率高,是求解此类问题的一种有效算法。
参考文献
[1]陈宝琳.最优化理论与算法.北京:清华大学出版社,1989
[2]粟塔山.最优化计算原理与算法程序设计.长沙:国防科技大学出版社,2001
[3]袁亚湘,孙文瑜.最优化理论与方法.北京:科学出版社,1997
[4]赵晓颖,刘国志,姜凤利.求解一类不可微优化问题极大熵微粒群混合算法.江西师范大学学报,2007;31(2):193—196
[5] Storn R,Price K.Differential evolution——a simple and efficient a-daptive scheme for global optimization over continuous spaces.Berke-ley:University of California,2006
[6] Lampinen J.A bibliography of differential evolution algorithm.ht-tp://www.lut.fi/~jlampine/debiblio.htm.2002-10-14
[7] Lin Y C,Hwang K S,Wang F S.Co-evolutionary hybrid differentialevolution for mixed-integer optimization problems.Engineering Opti-mization,2001;33(6):663—682
[8] Cheng S,Hwang C.Optimal approximation of linear systems by a dif-ferential evolution algorithm.IEEE Trans on Systems,Man and Cy-bernetics:A,2001;31(6):698—707
[9]王沫然.MATLAB 5.X与科学计算.北京:清华大学出版社,2000
进化规划算法 第7篇
近年来, 随着我国改革开放的不断深入和社会经济的迅速发展, 公安机关的执法面临更多的挑战。由于警力不足以及管理体制的原因, 应急指挥经常呈现反应不及时和处置滞后等弱点。运用现代化的计算工具提高警力合理使用与调度的水平对于进一步提高公安机关的服务水平和实战能力显得尤为重要。
随着城市规模日益扩大, 公安机关指挥处理重大突发事件时需要调度警力资源对交通要道进行封锁。相对于整个城市来说, 警力资源肯定是不足的, 处理突发事件时需要将平时分散部署的警力资源调度到某些位置实现“堵控”, 这是一个受到资源不足约束的调度问题。如何构建合理的模型并利用快速有效的算法求解警力的调度与指挥方案, 对公安机关提高处理应急事件的能力具有重要的意义。
本文为研究犯罪嫌疑人的堵控问题, 建立以犯罪嫌疑人在逃时间最短为目标的堵控模型, 设计基于差分进化算法的全市警力资源调度的算法求解该问题。
模型建立
设某城市有n个路口{P1, P2, …Pn}及m个警力资源{S1, S2…, Sm}, 在t0时刻接到报警称在城市kP, (k=1, 2, …, n) 路口发生了重大刑事案件, 犯罪嫌疑人乘坐交通工具正在逃跑, 为了堵控犯罪嫌疑人, 需要搜索堵控路口集合{P1, P2, …Pq}以及相应警力资源{S1, S2…, Sq}的调度方案, 确保将犯罪嫌疑人有效“围住”。该问题的最优方案需要满足警力资源{S1, S2…, Sq}能在最短时间从原先部署位置{P'1, P2'…P'q}调度到堵控路口集合{P1, P2…Pq}, 且犯罪嫌疑人没有逃出堵控路口集合所形成的包围圈。
假设各路口交通畅通, 案发地点和警力资源的位置在路口节点, 每个路口只需要一个警车的警力即可封锁, 罪犯逃跑方向是远离案发地点, 罪犯的逃跑速度仅为60km/h。设xij为0-1变量, xij=1表示从第i个路口的警力资源向第j个路口节点处调度, xij=0表示不从第i个路口的警力资源向第j个路口节点处调度。xij是决策变量, 也是问题的解。问题的最优方案应该满足三个要求: (1) 犯罪嫌疑人最大堵控时间最小化; (2) 警力资源由外向内调度; (3) 犯罪嫌疑人到达某路口的时间大于或等于警力资源到达该路口的时间。
(1) 堵控方案的最主要目标就是警力资源最短时间内控制犯罪嫌疑人的逃窜, 使其可能的在逃时间最小, 即警力资源到达所有堵控节点所用时间的最大值最小化, 由此建立目标函数:
其中, tij表示第i个警力资源到达第j个路口节点的最短时间, max (tijxij) 表示调度方案中警力部署到指定路口节点的最长时间。
(2) 考虑到追捕嫌疑人的策略, 警力资源从外向内调度, 建立约束条件如下:
(3) 为保证第i个警力资源调度到第j个路口围住犯罪嫌疑人, 则警力资源一定要在犯罪嫌疑人之前到达第j个路口节点, 所以警力资源从第i个到第j个路口所用调度时间一定要小于等于犯罪嫌疑人到达第j个路口节点的时间, 建立约束条件如下:
综上所述, 堵控问题的数学模型可以表示为:
算法设计
该模型是一个0-1非线性规划问题, 求解此类问题的传统方法有共轭梯度法、变尺度法、分支定界法、广义Benders分解法、外近似法等。由于上述传统方法计算量随着变量维数的增加而急剧增大, 一般不能用于实时控制, 难以满足本文提出的问题的要求。近年来, 随着人工智能技术的提高, 各种智能优化算法如遗传算法、粒子群优化算法、蚁群算法以及差分进化算法在不同领域得到了广泛的应用。差分进化算法 (DE) 是Storn等人于1995年共同提出的一种采用浮点矢量编码, 和其它演化算法一样, 是一种模拟生物进化的随机模型, 在连续空间中进行启发式随机搜索的优化算法, 具有较强的全局收敛能力和鲁棒性。
差分进化算法采用浮点数编码, 要将其用于求解0-1非线性整数规划问题, 必须先对其进行改进, 主要是编码转为0-1整数。由于DE的基本操作包括变异、交叉, 选择是根据适应值大小进行, 这与其他进化算法是类似的。改进主要是进行初始化时对0-1变量先在{0, 1}实数空间取值, 然后根据其特点对变异操作进行改进, 即采用四舍五入法进行取整运算, 得到对应的0-1变量, 就可以将DE用于0-1非线性规划问题。
变量描述与初始化
DE种群的每个个体是调度优化问题的一个解决方案, 由n个决策变量组成, 用矩阵Xkt表示 (k=1, 2, (43) , n, 其中t表示第t代) :
其中, xij为0-1变量, 表示从第i个路口的警力资源向第j个路口节点处调度。
按照式子 (7) 对决策变量X初始化, 其中, XL和XU分别为下限和上限, r为在[0, 1]上服从均匀分布的随机数。首先在{0, 1}实数空间随机取值, 然后四舍五入取整, 得到0-1整数变量:
变异操作
DE算法中, 变异个体是由种群内个体的差分向量经过缩放之后与种群内其他相异个体相加得到的。根据变异个体的生成方法不同, 对应就有多种不同的差分进化策略。本文对0-1变量进行变异操作并采用四舍五入的方法进行取整的方程为:
其中, r1≠r2≠r3≠s为互不相同的随机个体, 缩放因子F∈[0, 2]。
交叉操作
DE的交叉操作可以保持种群的多样性, 进而保持多个可能全局最优的个体, 提高搜索的广度。DE算法包括二项式交叉和指数交叉两种交叉方式。本文采用指数交叉。
试验个体XT由群体中第t代第k个个体Xkt与变异个体Xs进行交叉操作, 可以看成是个体Xkt的进化。首先通过随机选择使得试验个体XT至少有一位由变异个体Xs提供, 其他位可以根据交叉概率因子CR决定由Xs还是Xkt提供。交叉操作的方程为:
若CRmin和CRmax分别为最小交叉概率和最大交叉概率, Tmax为最大迭代次数, 则CR由下面式子确定:
其中参数a=30, b=3
选择操作
DE采用“贪婪”选择策略, 将变异和交叉操作后生成的试验个体XT与Xkt进行竞争, 根据适应度值f (⋅) 来选择最优个体, 若试验个体XT适应度值比Xkt更优时, 则将其选为子代, 否则将Xkt选为子代。选择操作的方程为:
约束条件处理
由于约束条件通常都是非线性的, 一般采用惩罚函数法将带约束条件的原问题转为无约束问题。经过惩罚函数转化后的无约束问题可定义为:
其中αj和βi为大于零的惩罚因子。
算法流程
算法流程如图1所示。
仿真实验
系统环境
硬件CPU频率2.4GHz, 内存16GB, 操作系统Centos7.0, 仿真软件平台Matlab2015。
实验数据及参数设置
以2011年大学生数学建模竞赛B题数据为实验数据, 根据算法思想编程求解, 得到警力资源的堵控方案如下:
结语