《PSO求解约束优化问题》由会员分享，可在线阅读，更多相关《PSO求解约束优化问题（86页珍藏版）》请在金锄头文库上搜索。
1、2018/8/29,CO-PSO,1,PSO求解约束优化问题,1）约束优化问题(Constrained Optimization， CO) 2）CPSO 3) 函数扩展技术,2018/8/29,CO-PSO,2,构造算法,为了简化CO问题的寻优过程，通常可采用如下的思路去构造算法：将约束优化问题转化为无约束优化问题、将非线性规划问题转化为线性规划问题、将复杂问题转化为简单问题。,2018/8/29,CO-PSO,3,约束优化问题描述,2018/8/29,CO-PSO,4,约束优化问题的求解难点,(1) 优化曲面的复杂性。复杂的优化曲面对约束优化带来的求解难点类似于无约束优化问题， (2) 不可
2、行域的存在性。约束的存在，导致决策 变量的搜索空间产生了不可行域。(3) 满足约束与优化目标的不平衡。,2018/8/29,CO-PSO,5,求解约束极值问题的传统方法,可行方向法（Feasible Direction）、 梯度投影法(Gradient Projection Method)、 约束集法(Active Set Method)、 罚函数法（Penalty Function Method)等等。 这些方法各有不同的适用范围及局限性，其中大多数方法需要借助问题的梯度信息，要求目标函数或约束条件连续可微，并且常常为满足严格的可行性要求而付出很大的计算代价。,2018/8/29,CO-PS
3、O,6,约束优化问题的求解思路,2018/8/29,CO-PSO,7,2.智能约束处理技术,无约束化处理罚函数法是最常用的约束处理技术，其基本思想是通过序列无约束最小化技术（Sequential Unconstrained Minimization Technique， SUMT），将约束优化问题转化为一系列无约束优化问题进行求解，其原理简单，实现方便，对问题本身没有苛刻要求。,2018/8/29,CO-PSO,8,罚函数法,罚函数法就是将目标函数和约束同时综合为一个罚函数，典型的罚函数如下:,2018/8/29,CO-PSO,9,G(x),H(x)常用形式,如何合理设置罚因子，是利用罚函数法
4、求解约束优化问题的一个瓶颈，也是约束优化领域的关键问题。,2018/8/29,CO-PSO,10,定常罚函数法,该类方法将罚因子在整个算法流程中设置为定值，但算法通常因数值的单一性而效果不佳。分层罚因子法，采用如下罚函数：,2018/8/29,CO-PSO,11,2.动态罚函数法,在动态罚函数法中,罚因子的数值是时变的，通常随进化代数增大而增大。 理由：在进化初期采用较小的罚因子，算法将有可能对不可行域进行一定程度的搜索；而进化后期采用较大的罚因子，将使算法的搜索集中在可行域，寻找目标更优的可行解。 动态罚函数,2018/8/29,CO-PSO,12,3.退火罚函数法,一种基于模拟退火策略的罚
5、函数法，罚因子每隔一定的进化代数就随温度的减小而增大，到算法后期罚因子则因温度很低而变得很大。该技术可认为是一种特殊的动态罚函数方法，但可通过控制温度来调整罚因子。,其中，表示温度，Vi(x)为各约束违反量的函数。,2018/8/29,CO-PSO,13,4.适应性罚函数法,适应性罚函数法，把搜索过程中获得的信息作为反馈，来指导罚因子的调整。,2018/8/29,CO-PSO,14,非固定多段映射罚函数法,通常，所构造的广义目标函数具有如下形式：,其中f(x)代表原目标函数；h(k)H(x)称为惩罚项，H(x)表示惩罚力度, h(k)为惩罚因子。 如果在求解CO问题的整个过程中固定不变，则称之
6、为固定罚函数法（Stationary PFM，SPFM）； 相反则称之为非固定罚函数法（Non-Stationary PFM NSPFM）。 通常NSPFM对CO问题的求解结果总是要优于SPFM。,2018/8/29,CO-PSO,15,动态调整,其中h(k)可以被动态调整，H(x)具体定义如下,2018/8/29,CO-PSO,16,4.2.2基于排序的方法,基于排序的约束处理技术不再进行无约束化处理，而是通过综合考虑目标函数值和约束违反的程度来对不同候选解进行比较。 1）随机排序法 2）改进的随机排序法 3）基于可行性规则的方法,2018/8/29,CO-PSO,17,4. 2. 3基于多
7、目标的方法,多目标优化问题通常可描述如下:,对于问题的两个可行解x1和x2，若下式满足，则称解x1支配解x2，记作x1x2,2018/8/29,CO-PSO,18,Pareto最优解,给定一个可行解x，若S中不存在支配x的解，则称x为Pareto最优解或非支配解(non-dominated solution)或非劣解。所有Pareto最优解构成目标空间的Pareto前沿(Pareto front) 。,2018/8/29,CO-PSO,19,目标函数和约束函数当作并列的多个目标,基于多目标的约束处理技术就是把目标函数和约束函数当作并列的多个目标来处理。譬如，第4. 1节描述的约束优化问题，可转
8、化为式(4-15）描述的多目标优化问题或式(4-16)描述的双目标优化问题。,通过采用非支配解的概念来比较解，可使搜索向Pare-to前沿方向前进，其中非支配解集中第一个目标函数值最小且其余目标值均等于0的解就是原约束优化问题的最优解。,2018/8/29,CO-PSO,20,2.基于支配的选择技术,一种基于支配的约束处理规则: (1)可行解总优于不可行解; (2)若两个解均可行，则目标值好的解为优; (3)若两个解均不可行且其中一个解为非支配解而另一个解为受支配解，则非支配解为优; (4)若两个解均不可行且它们同为非支配解或受支配解，则约束违反量小的解为优。,2018/8/29,CO-PSO
9、,21,基于协进化PSO算法的约束优化,罚函数法求解约束优化问题的性能取决于两个关键环节: (1)罚函数形式的设计。罚函数要综合考虑约束和目标两个方面，因此设计罚函数时应该考虑挖掘不可行解违反约束的信息，设计有效的约束违反函数，合理体现可行解与不可行解在综合评价上的差异。 (2）罚因子的选取。罚因子直接平衡约束违反量和目标间的平衡。,2018/8/29,CO-PSO,22,一种基于协进化模型的微粒群优化,设计思路归纳为，在设计罚函数方面，不但考虑不可行解违反约束的总量，而且还利用各不可行解违反约束的个数这一信息; 在罚因子选择方面，基于协进化模型，把罚因子也作为寻优变量，在搜索过程中利用PSO
10、算法自适应地进行调整，使算法最终不仅获得约束优化问题的优良解，同时还获得适合于问题的最佳罚因子。,2018/8/29,CO-PSO,23,4. 3 .2 协进化模型,协进化的原理可解释为，算法采用多个种群，或者将一个种群分为多个部分，各种群在各自独立进化的同时相互间共享和交互信息，各种群不仅利用从外界获得的信息来指导自身的搜索，同时还把探索得到的经验与其他种群分享，从而使整个系统协同进化，直至获得最优解。 本节的CPSO算法采用如图4. 7所示的协进化模型。,2018/8/29,CO-PSO,24,协进化模型示意图（图4.7）,2018/8/29,CO-PSO,25,cpso算法包含两类种群,
11、一类种群包含M2个子种群Swarm1,j(j=1, , M2，子种群规模均为M1，种群中的每个微粒Ai(i=l,k)则表示问题的一个决策解，该类种群用于进化决策解; ， 另一个规模为M2的种群Swarm 2，其每个微粒Bjj=1,.,M2)代表一组罚因子。用于计算Swarm1 , j中各微粒的罚函数值(或称适配值)。,2018/8/29,CO-PSO,26,协进化的每代进化过程,Swarm1 , j中的每个微粒利用B，表示的罚因子计算适配值， 并连续采用PSO算法进化G、代获得一个新的解的种群Swarm1 ,j; 然后，根据Swarm1 , j中所有解的优劣信息，评价Swarm 2中微粒Bj的
12、优劣，即评价罚因子; 当Swarm 2中所有微粒B，均得到评价后，Swarm 2采用PSO算法进化一代，从而获得新的种群Swarm 2，即得到M:组新的罚因子。 在一代协进化结束后Swarm1,j(j=1.2,M2)再分别用新的M2组罚因子进行评价，以此类推，直到满足算法终止准则，例如达到给定的最大协进化代数G2。 算法通过比较所有Swarm1,j得到的历史最好解，将最优者作为最终解输出，同时算法输出终止时Swarm 2中的最优微粒。即最佳罚因子。,2018/8/29,CO-PSO,27,CPSO小结,协进化就是两类种群的交互进化工程，第一类种群Swarm1 ,j用PSO算法来进化解向量，第二
13、类种群Swarm 2 用PSO算法来调整罚因子。 通过协进化模型下的PSO算法，不但算法在解空间进化探索决策解，而且在罚因子空间进化探索罚因子，最终同时获得最优决策解和一组合适的罚因子。,2018/8/29,CO-PSO,28,CPSO算法设计,1. Swarm1 , j的评价函数 罚函数既是违反约束数量的函数，又是违反约束程度的函数，则其效果要比罚函数仅为约束数量的函数的情况好。基此，采用如下适配值函数评价Swarm1,j中第i个微粒,其中，f(x)表示第i个微粒的目标值，sum_viol表示该微粒违反约束的总量，num_ viol表示该微粒违反约束的个数，w1,w2是由Swarm 2中微粒
14、Bj对应的罚因子。,2018/8/29,CO-PSO,29,sum_ viol按如下公式计算,2018/8/29,CO-PSO,30,2. Swarm 2的评价函数,Swarm 2的每一个微粒B，均代表一组罚因子，即w1和w2。当Swarm1 ,j进化G1代后，Swarm 2的第j个微粒B，采用如下方法进行评价。(1)若Swarm 1 , j中至少有一个可行解，则称B，为一个有效(valid)微粒，并按下式评价B,2018/8/29,CO-PSO,31,(2)若Swarm1 ,j中没有可行解(可认为惩罚项太小了)，则称B，为一个无效( invalid)微粒，并采用下式评价B;,2018/8/2
15、9,CO-PSO,32,（3） Swarml , j和Swarm 2的进化方程,两类种群中的微粒均采用标准PSO算法进行进化。特别地， Swarm 2里的每个微粒表示一组罚因子，即w1和w2, Swarml , j里的每个微粒表示一个决策解向量。,2018/8/29,CO-PSO,33,（4）CPSO算法框架,2018/8/29,CO-PSO,34,4. 3 .4 数值仿真与分析,对于每个测试问题，CPSO算法采用如下统一的一组参数。M1=50,M2 =20,G125,G2 =8,惯性因子LDW法，0.9-0.2, 加速因子c1=c2=2。 另外，Swarm1, j中微粒位置的最大值和最小值(
16、即X1,max和X1,min对应于各问题变量的取值上下界，Swarm 2中微粒位置的最大值和最小值(即X2, max和X2.min设置为w1max= w2.max=1000. w1min= w2.min=0。 第一个例子的可行域相对较小，算法单独将罚因子的上下界设置为w1maxw2max=10000,w1min= w2min =5000。两类种群中微粒速度的上下界设置,2018/8/29,CO-PSO,35,该问题来自文献23 ，焊接条结构如图4. 9所示。优化目标是寻求满足切应力、弯曲应力、杆条弯曲载荷Pc、末端偏差和边界条件等约束的4个设计变量h(x1)、l(x2:) ,c(x2)和b(x4)，使得制造焊接条所需的总费用最小。,2018/8/29,CO-PSO,36,2018/8/29,CO-PSO,37,该设计问题的数学模型描述如下:,2018/8/29,CO-PSO,38,其中,2018/8/29,CO-PSO,39,24-GA传统罚函数, 25几何规划法 26基于协进化模型的GA, 12基于支配选择机制的GA,
