求解非凸、非线性约束优化问题的广义蚁群算法

求解非凸、非线性约束优化问题的广义蚁群算法

1广义优化算法及其在高维网规划中的应用经济负荷分配（ed）是在满足能源系统运营约束条件的基础上最小化能源生产成本的一个非常重要的问题。这是电气系统中典型的优化问题。由于电力系统本质上具有高维、非线性、且约束条件多的特点，因此计算较为复杂。由于经济负荷分配问题的重要性，各国学者展开了大量的研究。基于经典优化算法的方法有：线性规划法（LP）、同伦线性规划法（HomogenousLP）、二次规划法（QP）、非线性规划法（NLP）以及动态规划法（DP）动态比较法等。这些方法可以求解ED模型，但也存在一些问题。线性规划法将模型线性化时难以避免误差；二次规划和非线性规划一般要求目标函数连续可导，在实际应用中受到限制；动态规划法对于高维问题将面临维数灾。近年来，人工智能技术取得飞速发展，与严格的数学优化方法不同，它可以处理离散、非凸的非线性问题，比较适于求解ED问题。文采用遗传算法（GA）求解该类问题，考虑了耗量曲线的阀点效应（ValvePointEffect）和网络损耗，取得与动态规划相似的结果；文采用改进遗传算法，提高了求解速度和精度；文将人工神经网络用于求解ED；文提出用混沌优化方法求解ED问题；文采用整数进化规划、tabu搜索、模拟退火算法和二次规划结合的方法求解非凸的ED问题。文提出系统进化算法，用于求解机组组合优化问题。蚁群算法（AntColonyOptimizationACO）模拟蚂蚁的群体行为，由Dorigo等人提出。ACO本质上是一种基于群体的多代理算法，运用了正反馈、分布式计算和贪婪式启发搜索。ACO问世以来，已成功地运用于旅行商问题（TSP）、不对称旅行商问题(ATSP)、二次分配问题(QAP)、生产计划问题(SP)、冗余分配、哈密顿图辨识、子集问题、随机二元约束问题(CSPs)以及单机总延时问题(SMTTP)等。在电力系统中，ACO可用于求解输电网络扩展规划、热机组短期发电计划等问题。蚁群算法是通过类比蚂蚁群体行为与旅行商问题得出的，主要适用于求解组合优化问题。本文根据ACO基本思想提出一种通用优化算法,该方法可用于求解一般形式的非凸、非线性约束优化问题，称之为广义蚁群算法（GeneralizedAntColonyOptimizationGACO）。同时，基于压缩映象下的不动点理论讨论其收敛性。多个经济负荷分配问题的仿真算例表明该方法是成功可行的。2电气系统经济负荷分配的数学模型2.1发电机侧进气阀控制ED问题是在满足系统运行约束条件下优化系统中发电机出力，使系统总发电成本最小，其数学模型如下：ED目标最小化总费用为式中F为系统总发电费用；Ng为系统内发电机总数；Pi为第i台发电机有功功率；Fi(Pi）为第i台发电机耗量特性。对于Fi(Pi）一般用二次函数近似表示为式中ai、bi、ci为参数。文提出，在汽轮机进气阀突然开启时出现的拔丝现象会在机组耗量曲线上叠加一个脉动效果，产生阀点效应（ValvePointEffect）。考虑阀点效应的耗量特性为式中Ei为阀点效应引起的耗量特性变化；gi、hi为参数；Pimin为第i台发电机有功功率下限。研究表明：忽略阀点效应会使求解精度受到明显的影响。2.2网损由潮流计算或b系数法求解发电机运行约束为式中Pimax、Pimin为发电机有功功率上下限；Pi为第i台发电机出力。电力平衡约束为式中PL为系统总网损；PD为系统总负荷。网损一般采用潮流计算或B系数法求得。如果采用B系数法，网损与发电机有功功率关系为式中P为Ng维发电机有功功率列矢量；PT为P转置；B为Ng×Ng维对称方阵；B0为Ng维列矢量；B00为常数。若网损由潮流计算得出，还可计及以下约束条件：(1）线路容量约束为式中Lfi为第i条线路潮流；Lfimax为第i条线路潮流上限；NL为线路数。(2）系统稳定性约束为式中i,j为有线路相连的节点;δi、δj为i,j的相角;δijmax为i,j相角差上限;ND为系统节点数。3一般蚂蚁群算法3.1基于种优化算法的求解蚁群算法（ACO）是人们受到真实世界中蚂蚁群体行为的启示而提出的一种优化算法，通过个体之间的信息交流与相互协作，最终得到待求问题的解。本节将在ACO基本思想的基础上描述一种通用优化算法——广义蚁群算法（GACO），并在压缩映象的不动点理论基础上对其收敛性进行讨论。3.2基于信息密度的加害算法及步骤对于一般定义在紧集合上的约束优化问题，可用外点法构造辅助函数，将不便于计入可行域的约束以罚函数计入目标函数中，其表达式为式中X=(x1,x2,…,xn)T为待优化向量；l,u分别为原问题等式约束和不等式约束的个数。式(10)可行域记为为了加速迭代，本文中σi与当前迭代次数K有关：式中α为正系数，用以调节σi的变化速度；σi0为σi(K)上限；T为迭代次数上限；式(12)使σi(K)由0逐步趋近于σi0。开始罚系数较小，有助于大范围搜索，后逐步变大，使最终结果即为原问题所求。经过处理后，对式(10)的广义蚁群算法基本步骤为：(1）初始化。当前迭代次数K=0，在S中取N组服从均匀分布的随机数，给定N只蚂蚁的初始位置，形成初始蚁群C0，且C0=（X1,X2，…，XN)T，其中，Xi∈S。初始化信息密度矩阵τN×N，τij=τ0，τ0为一小正数。设b(i)为位置i的蚂蚁数目，初始时：b(i)=1,i=1,2,…,N初始化蚂蚁可见域D(K)，当时，蚂蚁i,j可互相移动至对方位置。|·|为某种范数。为减小计算量，本文采用|·|，即为Rn上2范数。D(K)与迭代次数K有关，本文采用式中D0为可见域上限，其余同式(12)。式(14)使每只蚂蚁开始能大范围搜索，后来逐步精细化。(2）搜索策略。对于蚂蚁位置i(i=1,2,…,N），当b(i)≥1时，形成集合Ai,且当Ai≠Φ时，转步骤（3）；当Ai=Φ时，转步骤（4）。其中Φ为空集。(3）计算设Ai中元素个数为m，计算令ηijmin=|min(ηij)|，G=(1+ε)ηijmin，ε为一小正数。定义转移概率式中γ1、γ2为常数，本文取γ1=γ2=1。由式(18)、(19)得随着F(Xj)的减小，τij增大，Pij增大。P0为进行邻域搜索的概率，与可见域中蚂蚁对应目标函数的平均值及当前迭代次数有关。对P0,Pij进行赌轮选择，以选择不同的修正规则：若选中某一Pij，则执行修正规则1。修正规则1Xi处蚂蚁转向Xj处,Δτij=Pij;bi=bi-1;bj=bj+1;Xi←Xj。转向步骤(5)。若选中P0，则执行修正规则2。修正规则2在Xi邻域中用某种优化算法进行搜索，邻域定义为式中β∈（0,1），为系数。设搜索结果为Y，则转向步骤（5）。(4）直接邻域搜索搜索域同式(21)。设搜索结果为Y，则执行修正规则3。修正规则3式中r为常数。(5）修正信息密度矩阵式中ρ为信息密度蒸发系数，ρ∈(0,1)。注：(1)当Δτij由修正规则1得到时，仅修正i至j的连接；当Δτi由修正规则2得到时，对于所有Xj∈Ai，且Xi≠Xj的τij都修正；当Δτij由修正规则3得到时，则所有Xj∈CK，且Xi≠Xj的τij都修正。CK为第K次迭代形成的蚁群。(2)仅修正τij，τji不修正。(6）对所有Xi∈CK，都完成一次移动，统计结果为(1)若不满足接受条件，取消本次迭代步骤（2）、（3）、（4）的结果，转步骤（2）。接受条件将在后面讨论。(2)若连续多次迭代蚁群统计结果不变，则对蚁群加扰动。本文采取扰动为扩大可见域、扩大邻域搜索范围；将任一只蚂蚁随机放置于S中某一点。多次扰动无效，输出结果。(3)当K<T,K=K+1时，转步骤（2）；否则，输出结果。3.3c是完备的度量空间本节将基于压缩映象的不动点理论，对广义蚁群算法的收敛性进行简单的分析，并给出广义蚁群算法收敛的充分条件。定义1广义蚁群算法空间Ω：式中CK=（X1K,X2K,…,XNK），为第K次迭代形成的蚁群，其中，N为蚁群规模（下同）；S为可行域；由第3.2节描述可知：∀X∈S，都可找到CK，使X∈CK，且CK∈Ω。定义2Ω中Ci、Cj距离d(Ci,Cj):式中式中Xti∈Ci,L为F′(Ci)的一个下界，由于待求为最小化问题，L必存在；Ci∈Ω；ε为小正数。证明首先，d(Ci,Cj)为Ω上的一个度量其次，Ω是完备的：设{Ci}是Ω中任一Cauchy列，则∀ε>0,存在N，当i,j>N时有在式(25)中，令j→∞，Ci→C(i→∞)。由定义1得C∈Ω。因此，（Ω，d）是完备的度量空间。由广义蚁群算法的描述可将其看成Ω→Ω的映射，记为ö。则在完备的度量空间（Ω，d）上，ö为Ω的自映象，当ö满足以下压缩映象条件之一时，ö在Ω中存在唯一不动点。∀Ci,Cj∈Ω有满足式(26)～(29)的一个充分条件是因此步骤（6）(1)中的一个接受条件为由此可得结论2结论2在完备度量空间（Ω，d）中，若广义蚁群算法构成的映射ö：Ω→Ω满足式(30)，则ö存在唯一的不动点C*，对任一C0∈Ω，蚁群算法形成的迭代序列式中K为迭代次数。4计算4.1广义昆虫群算法以3机6母线电力系统为例，原始数据见文，考虑耗量曲线的阀点效应，忽略网损。发电机承担的总负荷为PD=850MW。用本文提出的广义蚁群算法计算结果见表1。文用遗传算法得出P1=300.0MW,P2=400.0MW,P3=150.0MW，总费用为8237.6$，与本文计算结果近似，本文结果略优。4.2广义昆虫群算法计算结果与算例1采用的系统相同，优化时考虑耗量曲线的阀点效应和网损，网损用B系数法计算，数据见文。发电机承担的总负荷为PD=500MW，用本文提出的广义蚁群算法计算结果见表2。文用遗传算法得出的P1=300.01MW,P2=170.20MW,P3=100.10MW，网损为70.99MW，总费用为5745.11$；用混沌优化得出算法P1=299.46MW,P2=172.00MW,P3=98.84MW，网损为：70.24MW，总费用为5735.93$，与本文计算结果近似。4.3基于二次规划的计算方法此算例对文中给出的包括6台发电机、10个用户、10条母线、13条线路的系统进行优化计算。用牛顿-拉夫逊法计算潮流，求得网损。计算中考虑了线路容量约束和系统稳定性约束。其中取δijmax=25o。广义蚁群算法优化结果见表3。由于篇幅所限，线路潮流及相角差略。文用二次规划得到符合线路潮流约束的结果为P1=1.146pu;P2=0.565pu;P3=0.405pu;P4=0.325pu;P5=0.995pu；总费用为140.62$,与本文计算结果近似，本文结果略优。5广义昆虫群算法本文研究了广义蚁群算法的基本算法、收敛条件和实际运用，下面将讨论几个相关问题：(1）本文范数使用|·度量距离是合理的：因为第K代蚁群CK构成有限维赋范空间（证明略），又因X∈CK，由于有限维赋范空间互相拓扑同构，导致有限维赋范空间任何两个范数互相等价，因此使用哪种范数并不影响收敛性。但要注意的是，在计算过程中只能使用同种范数。(2）第3.3节中给出的收敛性证明是针对空间中只有唯一不动点的情况，若存在多个不动点，试验表明本文算法还是可以收敛的。其结果可以这样解释：设Ci,Cj是Ω中两个最优群体，且Ci≠Cj，由3.3节中讨论可知由式(13)～(15)可知，由于可见域逐步缩小，蚁群将形成若干个孤立子群体，子群体之间相对独立，可收敛至多个最优解。另外，由于步骤（6）中引入随机扰动，使子蚁群陷入局部最优解后可以跳出。(3）在式（24）中取与3.3中分析类似，可得到式(31)～(31)类似的判据。(4）算法步骤（6）中对连续多次迭代蚁群统计结果不变时，对蚁群加扰动。这种方法可以避免陷入局部最优解。图1是对算例1分别采用扰动和不采用扰动时蚁群中最小值的变化。扰动方法为：随机选取一只蚂蚁，将其本次迭代中将可见域与直接邻域搜索范围均置为D0。(5）广义蚁群算法用于经济负荷分配问题在保证收敛精度的前提下，收敛速度较快，稳定性高。对算例2，取蚁群中蚂蚁数N=10；初始信息密度τ0=1.0；可见域上限D0=500.0；迭代次数上限T=400；直接邻域搜索中信息密度矩阵修正常数r=0.08～0.4；信息密度蒸发系数ñ=0.9，式(12)、(14)中正系数á=10.0，独立计算20次，当目标函数值F(X)<5742.0,认为收敛。收敛迭代次数平均值为261.75，样本标准差为59.725。文对同样算例用遗传算法计算目标函数需5000次，用混沌优化算法计算目标函数需3000次。因此本文计算量相对较小，收敛稳定性较高。(6）采取适当的邻域搜索算法，广义蚁群算法可以求解非凸的优化问题。本文中采取蒙特卡罗算法进行邻域搜索。它不要求待求问题定义在凸集上，且由式(21)定义的邻域在迭代中逐步缩小，小范围内，蒙特卡罗算法简单有效。仿真结果表明，在本文涉及的算例中该方法是可行的。6算法有效性及优越性本文提出了一种用