全局混沌杂交的粒子群优化算法及应用

李 娅，张德丰，王 东

(佛山科学技术学院机电与信息工程学院，中国 佛山 528000)

粒子群算法是一种基于群体迭代，群体在解空间中追随最优粒子进行搜索的算法，该算法简单方便，收敛速度快，并且对目标函数要求较少，因此发展十分迅速，在函数优化，神经网络训练，TSP问题求解，模糊系统控制等领域得到广泛应用．

作为一种有导向的随机性的启发式算法，在求解复杂优化问题时，粒子群算法存在易陷入局部极值点，进化后期收敛速度慢，鲁棒性较差等缺陷．目前解决这类问题的主要方法是增加粒子群的规模，或者改进粒子群算法的一些计算参数，或者将粒子群算法与其他算法结合产生各种混合算法．

文献[1]提出的混沌粒子群优化算法(CPSO)立足于利用混沌变量的遍历性，以粒子群当前搜索到的全局最优位置为基础迭代产生一个混沌序列，然后将序列中的最优粒子位置随机替代当前粒子群中的某一粒子的位置并进行迭代，从而解决了因为粒子停滞导致的算法早熟问题．

CPSO算法仅仅是对粒子群中全局最优位置用混沌序列替代，但粒子速度计算公式中的参数还是以随机数出现，所以不能完全保证能提高CPSO算法的种群多样性和优化的遍历性．本文作者在此算法的基础之上，提出一种新的全局混沌杂交粒子群优化算法(EC-CPSO)，将CPSO算法中的随机数用混沌随机序列来替代，同时应用早熟判断机制，借鉴遗传算法中杂交的概念，在对最优粒子进行混沌化处理之外，将其余粒子随机两两杂交，用杂交后的子代粒子替换亲代粒子，在一定程度上提高了种群的多样性，降低整个粒子群收敛于局部极值点的可能性，提高了运算的速度，将之用于(N+M)容错系统优化模型证明该算法与CPSO相比具有一定的优势．

1 基本粒子群算法(PSO)

PSO算法首先初始化一群随机粒子，然后粒子们就追随当前的最优粒子在解空间中搜索，即通过迭代找到最优解．假设d维搜索空间中的第i个粒子的位置和速度分别为xi(xi,1,xi,2，…，xi,d)和vi(vi,1,vi,2，…，vi,d),在每一次迭代中，粒子通过跟踪两个最优解来更新自己，一个就是粒子本身所找到的最优解，即个体极值pi=(pi,1,pi,2，…，pi,d)；另一个是整个种群目前找到的最优解，即全局最优解pg=(pg,1,pg,2，…，pg,d)．在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置[2]．

vi,j(t+1)=wvi,j(t)+c1r1[pi,j-xi,j(t)]+c2r2[pg,j-xi,j(t)]，

(1)

xi,j(t+1)=xi,j(t)+vi,j(t+1),j=1,2,…,d，

(2)

其中w为惯性权因子，c1和c2为正的学习因子，r1和r2为0到1之间均匀分布的随机数．从式(1)可以发现，新速度由3部分组成．第1部分反映粒子维持原速度的程度；第2部分反映粒子的自我认知，表示粒子对自身过去成功经验的肯定；第3部分反映粒子间的社会交流，表明粒子间的信息交流与合作．粒子在解空间不断跟踪个体极值点和全局极值点进行搜索，直到结果满足终止条件或者达到最大迭代次数为止．

2 基于混沌的粒子群优化改进算法

2.1 混沌运动

混沌是存在于非线性系统中的一种较为普遍的现象，是由确定性方程得到的具有随机性的运动状态．在一定范围内混沌变量的变化具有随机性，遍历性和规律性，利用混沌变量的这些特征优化搜索，能使算法跳出局部最优，保持群体多样性，改善算法的全局搜优性能．一个典型的混沌映射系统Logistic方程是[3]：

yn+1=4yn(1-yn),n=1,2,3,…

(3)

式中yn为混沌变量，yn∈[0,1]．

2.2 全局混沌杂交粒子群优化算法(EC-CPSO)

本文作者在混沌粒子群优化算法(CPSO)基础上，除用混沌变量对粒子的位置和速度进行初始化，提高种群的多样性和遍历性外，还把具有混沌遍历机制的混沌变量嵌入到PSO算法的参数中，即用不同的混沌随机序列分别替代PSO算法中的随机数r1,r2参数，使混沌变量在每次算法迭代时产生一个PSO算法所需要的随机数．混沌的遍历性和混沌的搜索机制与PSO算法的有机结合，有利于提高PSO算法全局搜索寻优能力和鲁棒性．

新的混沌粒子群算法的粒子速度迭代公式为：

vi,j(t+1)=wvi,j(t)+c1R1,j(t)[pi,j-xi,j(t)]+c2R2,j(t)[pg,j-xi,j(t)]，

(4)

式中：R1,R2是混沌变量映射值的函数，R1,R2替代PSO中的r1,r2随机数．

在CPSO算法中，以粒子群当前搜索到的全局最优位置为基础迭代产生一个混沌序列，然后将序列中的最优粒子位置随机替代当前粒子群中的某一粒子的位置并进行迭代，从而解决了因为粒子停滞导致的算法早熟问题．为进一步提高算法的速度，本文在此基础之上，借鉴遗传算法的思想[4]，对其余粒子进行杂交处理，进一步加强了对粒子区域的搜索能力，摆脱局部最优，获得改进的搜索结果，提高搜索的速度和精度．遗传算法是一种随机搜索最优化方法，它的基本操作是复制，杂交和变异．粒子群中的粒子被赋予一个杂交概率，这个杂交概率是随机的，与粒子的适应值无关．在每次迭代中，依据杂交概率选取指定数量的粒子放入一个池中．池中的粒子随机的两两杂交，产生同样数目的孩子粒子，并用孩子粒子代替父母粒子，以保持种群粒子数目不变．孩子粒子的位置child(x)由父母粒子的位置parent1(x),parent2(x)进行算术交叉来计算[2]，即：

child(x)=p·parent1(x)+(1-p)·parent2(x).

(5)

孩子粒子的速度child(v)由下式来计算：

(6)

其中parent1(v),parent2(v)为父母粒子的速度．

粒子群用产生的孩子粒子取代父母粒子．杂交操作使孩子粒子继承了父母粒子的优点，例如两个父母粒子均处于不同的局部最优区域，那么两者杂交产生的孩子粒子往往能够摆脱局部最优，从而获得改进的搜索结果，保证了搜索速度和搜索精度．

算法的具体流程如下：

2)初始化一群粒子，并使R1,R2分别用Logistic映射产生混沌随机序列．R1,R2产生的混沌随机序列值在0.0～1.0之间．

3)计算每个粒子的适应度值f，更新个体最优值pi和全局最优值pg．

4)若满足停止条件(通常为预设的运算精度或迭代次数)，搜索停滞，输出结果，否则转(5)．

5)判断算法是否进入早熟．判断的标准为粒子的平均粒距和粒子的适应度方差[5]：

粒子的平均粒距D(t)：

(7)

种群的适应度方差σ2[6]：

(8)

其中，fi为第i个粒子的适应度值，favg为当前种群的平均适应度值，fmax为当前粒子的最大适应度．

种群适应度方差反映的是种群中个体的聚集程度．σ2越小，则种群中个体的聚集程度越大；反之，则聚集程度越小．随着迭代次数的增加，种群的个体适应度会越来越接近，因此σ2会越来越小．

如果σ2α(α为预先给定的值，本文取0.1)同时D(t)β(β为预先给定的值,本文取2.5)，认为算法出现早熟收敛现象．如果算法早熟，转步骤(6)，否则，转步骤(9)．

6)对粒子群最优位置xgbest进行混沌优化，方法为[7-8]：

将xgbest通过方程映射到Logistic方程的定义域[0，1]上：

(9)

将混沌序列通过下面的方程逆映射回原解空间：

(10)

9)对剩下的粒子，根据杂交概率选取指定数量的粒子放入杂交池，池中的粒子随机两两杂交产生同样数目的孩子粒子，孩子粒子的位置和速度按公式(5)和(6)计算．

10)利用公式(4)和(2)更新所有粒子的位置和速度．转步骤3．

3 性能分析

为验证EC-CPSO算法的性能，将之用于(N+M)容错系统优化模型求解，并与CPSO算法进行比较．

3.1 (N+M)容错系统优化模型

(N+M)容错系统优化模型如下[9]：

(11)

上述费用模型是一个同时具有离散和连续变量的混合优化问题，决策变量为n,m,λ/μ,其中n和m是整型变量，λ/μ为连续变量．当n为一定值时，上述问题即求解m和λ/μ，使(N+M)容错系统的费用最小．

3.2 初始粒子群的确定和约束条件的处理

在本算法中，(m,λ/μ)1×21维数组构成1个粒子，(m,λ/μ)(pop-size)×2数组构成1个初始化粒子群，因此，在确定粒子的过程中，应首先确定包含最优解的区域，在此最优解区域为A≥GA产生随机点，并验证其是否满足约束条件，即共产生pop-size个粒子，在迭代过程中，每个粒子也要验证是否满足约束条件，如不满足，则需调整，直到满足条件为止．

3.3 计算结果和算法性能比较

在本优化模型中，给定K0=15；λ0/μ0=0.01；j=0.1；k1=120 000；保证可用度GA=0.999 5；取n=1,2,…26．粒子群规模为40，最大迭代次数M=100，混沌搜索迭代次数T=10，惯性权重w=0.5；学习因子C1,C2取值2.0．分别计算m和λ/μ，结果见表1，当n一定时，得到最优的m和λ/μ组合．

表1 (N+M)容错系统优化模型混沌粒子群算法结果

从表1可以看出：当n一定时，用EC-CPSO算法可以得到m和λ/μ的最优解．在采用相同数量备件m的情况下，随着n的增加，λ/μ相应减少，即在备用控制器不变的条件下，随着工作控制器的增加，对每一台控制器的可靠性的要求也越高．

为全面评价EC-CPSO算法的性能，本文选用文献[1]提出的CPSO算法与该算法进行比较．每一算法程序在n=20的条件下各自运行30次．

图1给出了进化代数t和最优粒子所得的系统总费用C的变化曲线，最优粒子所得的系统总费用取30次实验的平均值．

在n=20的条件下,由表1可知EC-CPSO算法达到全局最优时m=5,λ/μ=0.0281，表2给出的全局最优成功率为30次实验中m和λ/μ达到全局最优的次数与30的商，每次实验的迭代次数为50次．CPSO算法全局最优成功率计算与此类似．

表2 算法实验结果比较(n=20，迭代50次)

从图1可以看出，EC-CPSO相对于CPSO，扩大了搜索空间，提高了搜索速度，在搜索效率上有较大程度的提高．从表2可以看出，EC-CPSO算法在50次迭代内达到全局最优的成功率和搜索成功所用时间均优于CPSO算法．

为了考察改进后EC-CPSO算法收敛的稳定性，对30次实验的最终结果进行统计分析，每次实验结束后得到群体最优粒子，根据最优粒子的位置值计算出系统的总费用，同时计算实验结束后群体中所有粒子位置的平均值，根据这个平均值计算出系统的平均总费用，如图2所示.

图1 进化代数t和最优粒子所得的系统总费用C的变化曲线 图2 系统总费用和系统平均总费用在实数次数下的C的变化曲线

由图2可见，EC-CPSO算法每次实验得到的系统总费用(包括平均费用和最优解费用)的变化总在较小的范围，标准偏差也较小，由此可知，该改进算法的收敛性能比较稳定，显示了该算法的优越性．

4 结论

1)全局混沌杂交粒子群优化算法(EC-CPSO)相对于单纯的混沌粒子群算法(CPSO)，因其将具有混沌遍历机制的混沌变量嵌入到PSO算法的参数r1,r2中去，同时引入早熟判断机制，借鉴遗传算法的思想，在对最优粒子进行混沌化处理之外，对其余粒子进行杂交处理，提高了算法的寻优能力，能有效避免算法陷入局部最优并防止过早收敛，计算成本亦不致增加太大．

2)基于(N+M)容错系统优化模型仿真实验证明了该算法的正确性和有效性，性能分析表明，该算法能够摆脱局部极值，得到全局最优解，该算法在搜索速度，搜索效率等方面均优于CPSO算法，同时具有较好的收敛稳定性．

参考文献：

[1] 高 鹰，谢胜利.混沌粒子群优化算法[J].计算机科学， 2004， 31(8):13-15.

[2] 龚 纯,王正林.精通MATLAB最优化计算[M].北京：电子工业出版社，2009.

[3] 纪 震，廖惠连，吴青华.粒子群算法及应用[M].北京：科学出版社，2009.

[4] CHEN R Q, YU J S. Study and application of chaos-particle swarm optimization based hybrid optimization algorithm[J]. Journal of System Simulation, 2008, 20(6):685-688.

[5] 段晓东，高红橄，张学东，等.粒子群算法种群结构与种群多样性的关系研究[J].计算机科学, 2007, 34 (11):164-166.

[6] 刘军民，高岳林.混沌粒子群优化算法[J].计算机应用， 2008， 28(2):323-324.

[7] 高 尚, 杨静宇. 混沌粒子群优化算法研究[J]. 模式识别与人工智能, 2006, 19(2):266-270.

[8] 孟红记, 郑 鹏, 梅国晖, 等. 基于混沌序列的粒子群优化算法[J].控制与决策, 2006， 21(3):263-266.

[9] WANG S T. Intelligent networked (N+M) fault tolerant systems for hydro power station[J]. International Journal of Hydroelectric Energy, 1999, 17(1)：46-50.