面向离散优化问题的改进二元粒子群算法

印桂生，崔晓晖，董宇欣，杨雪

（哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001）

面向离散优化问题的改进二元粒子群算法

印桂生，崔晓晖，董宇欣，杨雪

（哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨150001）

二元粒子群算法被广泛用于求解离散组合优化问题。在求解离散优化问题时，二元粒子群算法会出现解空间利用率低，速度和状态趋同以及退化和波动等演化问题。针对这些问题，提出一种改进的二元粒子群算法。算法使用Gray码演化基编码，混沌初始化过程，改进速度和状态调整方法以及子代处理方法用于提高种群利用率和种群多样性。在不同类型的检验函数以及多选择背包问题上，和现有优化算法及其他二元粒子群算法相比，改进算法能够获得较高的收敛精度以及较快的收敛速度，体现出多离散优化问题的实际效用。

二元粒子群；Gray码；混沌；子代处理；离散优化

粒子群优化（particle swarm optimization，PSO）用于求解连续解空间的优化问题［1］。在实际中，存在这大量离散优化问题［2⁃4］，为解决这类问题，学者们提出了用于离散问题的二元PSO［5⁃10］。

随问题维度的上升，现有二元PSO通常增大种群规模或增加迭代次数来提高求解精度，导致算法的时间复杂度以及空间复杂度随之升高，丧失了优化算法在处理离散问题上的实际效用。为此，本文提出一种面向离散问题的改进二元PSO算法。该算法采用的Gray码演化基编码方式，混沌初始化过程，改进的速度和状态调整过程以及子代处理过程，旨在问题维度上升的情况下，仍能够高效且稳定的收敛到高精度的演化状态，提高算法对离散问题的实际效用。

1 经典二元粒子群算法及其问题

Kennedy借鉴经典连续PSO的速度调整和状态调整思路，设计了用于离散问题的二元粒子群算法BPSO（binary particle swarm optimization）［5］，其速度和状态调整过程表示为

式中：ωvi，j（t）为第t代的第i个粒子在第j维的速度，t）∈｛0，1｝分别表示第i个粒子的个体最优位置和种群最优位置。U（0，φ1）和U（0，φ2）生成（0，1）间的随机数。vmax表示速度的上限。

式中：sig（x）为sigmoid函数，用于将速度变量转换成（0，1）内的概率。

BPSO以及基于BPSO的改进算法［5⁃6，8⁃10］主要存在以下问题：解空间的利用率较差。由于缺乏有效的演化基初始化策略，导致算法无法充分利用有限的种群规模。速度趋同现象。迭代后期，BPSO随着各个维速度的不断累加，演化基上各维状态只能无限趋近于1，从而出现趋同现象［8］。状态遗忘特征。BPSO现有状态完全依赖于速度转换后的概率，导致状态调整过程呈现遗忘特征。演化波动以及退化现象。BPSO的收敛精度曲线随迭代次数增加而不断波动且出现退化的现象。

针对上述问题，提出一种面向离散优化问题的改进二元粒子群算法（improved binary particle swarm opti⁃mization，IBPSO），采用混沌初始化种群，引入二维速度变量并设计子代处理过程。

2 高效离散粒子群算法

2.1 IBPSO的编码方式

IBPSO的演化基编码形式包括：用于适应度计算以及满足约束判断的整数演化基形式I；用于中间状态的二进制BCD码形式B；用于演化过程的Gray码形式。各形式的表示以及转换方法如下：

针对种群规模为s和问题规模为n的离散问题，种群中某一整数演化基Ik表示为

假设Ik中每一维ikl的取值约束为［al，bl］，则可通过ikl-al将ikl转换为无符号的正整数i'kl进而转换为无符号的二进制BCD码Bkl，即

为便于IBPSO在约束范围内有效演化，通过左补0的方式使Bkl的宽度等于「lb（bl-al）。

式（4）的BCD编码虽然是整数演化基的直观二元表示，但存在Hamming悬崖问题［9］，因此，IBPSO采用式（6）将BCD编码的演化基转换为对应的Gray码Gkl＝（gkl，1，gkl，2，…，gkl，d），并使用Gkl作为种群中速度和状态调整的操作对象。

2.2 算法改进思路

2.2.1 混沌初始化方法

可利用混沌过程产生初始种群，充分利用解空间，形成分布均匀的初始种群。IBPSO的混沌初始化的步骤为：

1）产生与问题规模n一致的（0，1）随机种子集合｛Z0l｝（l＝1，2，…，n）。

2）将Z0l作为输入，通过式（6）所示的混沌发生器，产生2倍种群规模的｛Zkl｝（k＝1，2，…，2s）。

3）将具有同样下标k的ikl构成候选初始整数演化基Ik＝（ik1，ik2，…，ikn）。根据适应度，对2s个候选初始整数演化基进行排序，选择适应度较优的前s个不同个体作为初始种群。

4）根据l维的约束条件［al，bl］，通过式（7），将Zkl映射为相应的整数变量ikl。

5）利用2.1节中的介绍的方法，将整数演化基转换为Gray码演化基，并初始化速度变量Vk。对于Vkl（l＝1，2，…，n）的每一维变量vkl，o，初始化为［vkl，o（t，0），vkl，o（t，1）］（o∈［1，2，…，d］），其中，vkl，o（t，0）为第t代第k个Gray码演化基的第l维上所对应二进制的第o个分量趋近于0的程度，vkl，o（t，1）为趋近1的程度。vkl，o的初值为vkl，o（0，0）＝vkl，o（0，1）＝vmax／2。

2.2.2 改进的速度调整过程

以二维速度向量为基础，改进BPSO的速度调整过程，采用式（8）调整演化基中每一分量gkl，o（o∈［1，2，…，d］）的速度。

式中：vkl，o（t-1，s）表示在t-1代演化基接近s的程度，pkl，o（t-1）表示在t-1代，个体k的最优演化基在该维的取值，gkl，o（t-1）表示在t-1代，种群最优演化基在该维的取值。ω为非惯性权重。当s取0或1时，IBPSO依据vkl，o（t-1，s），pkl，o（t-1）和gkl，o（t-1）的取值情况，同时调整vkl，o（t，0）和vkl，o（t，1），如式（9）。

由于pkl，o（t-1），gkl，o（t-1）∈｛0，1｝，式（9）还可继续转换为4种形式，以其中pkl，o（t-1）＝1和gkl，o（t-1）＝1为例。

当pkl，o（t-1）＝1时，说明个体k的最优演化基在该维的状态为1，此时，为促进个体k的快速收敛到最优状态，应增强趋近于1的程度，同时，减弱趋近于0的程度。当gkl，o（t-1）＝1时，说明种群中最优演化基在该维的状态为1，为促进个体k向全局状态收敛，应增强趋近于1的程度，同时，减弱趋近于0的程度。根据上述思路，粒子在解空间中可自由移动，避免速度趋同现象。

2.2.3 改进的状态调整过程

IBPSO采用式（10）调整Gray码演化基中每一分量gkl，o（o∈［1，2，…，d］）的状态。

式中：U（0，1）为（0，1）的随机数，sgn（x）为符号函数。当x＞0时，sgn（x）＝1；否则，sgn（x）＝0，sig（x）为sig⁃moid函数。

以gkl，o（t-1）＝0为例，考察gkl，o（t-1）的相反取值gkl，o（t-1）所对应的速度vkl，o（t-1，1）和随机产生数值U（0，1）的大小关系，确定符号函数sgn的取值。当sgn＝0时，说明gkl，o（t-1）的取值更趋近于1，则利用式（10）将gkl，o（t-1）取反，当sgn＝1时，说明gkl，o（t-1）的取值更趋近于0，保持gkl，o（t-1）不改变。在gkl，o（t-1）＝1，式（10）的状态调整思路同gkl，o（t-1）＝0。上述过程中IBPSO的状态调整参考前一代的状态，缓解了迭代过程中的状态趋同问题。

2.2.4 子代处理过程

将演化基上不满足约束的维度调整到约束范围内，如式（11）所示：

筛选并形成子代的过程：将调整后的候选演化基I'（t）和父代演化基I（t-1）构成数量为2s的集合IS＝｛I'（t），I（t-1）｝，按适应度排序，将排序中适应度较大且不同的前s个演化基形成子代I（t）。

2.3 IBPSO的主要步骤

1）执行混沌初始化操作。生成初始Gray码演化基G、速度变量V、种群和个体最优位置。

2）速度以及状态调整。更新速度变量，生成候选子代G'（t）。

3）按约束调整演化基。将不满足约束的整数演化基调整为有效演化基。

4）筛选并形成子代。依据子代筛选过程，从IS中生成子代I（t）。

5）更新操作。更新演化基每一维的最优位置以及种群最优位置。

6）结束判断。

2.4 IBPSO的时间复杂度

IBPSO的时间复杂度包括初始化、速度调整、状态调整及子代处理等过程。初始化的时间复杂度为

O（n（2+2s）+2sz（n）+2slb2s+

速度和状态调整过程时间复杂度为

子代处理的时间复杂度为

如果假设IBPSO设定的结束代数为tmax，则IBPSO时间复杂度为

2.5 IBPSO的收敛性分析

在任意代t，种群中每个的粒子，通过式（8）和（10）确定Ik转换的Gray码表示Gk上的每一维转移概率pkl，o（t）。由于pkl，o（t）∈（0，1），因此，粒子的每一步转移概率为（k）＞0，转移过程构成Markov链，即任意解间依概率可达。同时，IBPSO邻代种群序列是单调的。由上述理论分析，IBPSO满足依概率1收敛到全局最优解的充要条件。

3 仿真分析

以检验函数以及背包问题为基础，分析算法在经典离散问题和实际离散问题上的寻优效果。参数设置如表1所示。限定s＝10以及tmax＝100。

表1 PSO相关参数设定情况Table1 Experimental parameters setting of PSO

3.1 检验函数的实验及结果分析

3.1.1 实验设计

本文选择具有单峰、多峰等典型特征的检验函数［11］构成测试环境，如表2所示。

表2 检验函数列表Table2 List of test functions

将BPSO［5］，NBPSO［7］和EBPSO∗作为第1组对比算法，分析IBPSO的改进效果。NBPSO：采用与IBPSO类似的速度及状态调整，但未采用混沌初始化以及子代处理过程。EBPSO∗：采用混沌初始化但未采用子代处理过程。

将SPSO［13］、EnBPSO［14］以及MBPSO［15］作为第2组对比算法，分析IBPSO与其他改进的二元粒子的求解差异。SPSO：与经典BPSO的状态调整方法相同，仅在速度调整过程中，速度变量偏向全局最优的比例随迭代次数的增加而增大。EnBPSO：在SPSO基础上，引入非线性惯性权重。MBPSO：使用线性函数而非sig⁃moid函数。

3.1.2 结果分析

在检验函数f1～f5上，分别取维度n＝｛10，30，50｝，计算IBPSO以及各算法执行100次的实验结果，如表3所示。AVG为平均演化精度。ENUM为计算代价，z（n）为适应度函数执行一次计算的单位时间。

对于AVG指标，BPSO无论在单峰检验函数还是多峰检验函数下，都无法收敛到全局最优。NBPSO仅在高维检验函数上，陷入局部最优解。EBPSO∗一定程度的缓解NBPSO陷入局部最优解的问题，但仍然无法收敛到全局最优解。SPSO在低维度问题中能够收敛到全局最优解，但在高维度问题上难以收敛到全局最优解。和SPSO相比，MBPSO对单峰问题具有较好求解能力，但对多峰问题较差。IBPSO无论是单峰还是多峰函数，均可有效收敛。

在衡量指标ENUM上，SPSO、EnBPSO和MBPSO与BPSO的算法结构类似，因此，它们的ENUM与BP⁃SO相同。由于IBPSO和EBPSO∗采用的混沌初始化过程，因此IBPSO和EBPSO∗的ENUM数量增加了10个单位的z（n）。虽然增加了较少的计算代价，但IBP⁃SO和EBPSO∗的收敛精度AVG普遍优于BPSO和NB⁃PSO。

表3 各二元PSO算法在检验函数上的实验结果Table3 Experimental results of the different binary PSO algorithms on the test functions

以多峰函数f3为例分析各算法在处理50维问题时的收敛情况，如图1所示。

图1 各算法求解50维f3时的收敛情况Fig.1 Convergence of each algorithm on f2with 50 di⁃mensions

图1 中，BPSO与IBPSO在收敛速度方面的差异较单峰函数f1更加明显，在100代演化结束时，IBPSO能够获取f3的全局最优值，但BPSO仍未收敛。SPSO和EnBPSO的收敛情况类似，虽然波动较低，但仍无法避免退化问题。

上述分析表明：和其他算法相比，IBPSO能够在有限迭代次数内，收敛到理想状态。

3.2 多选择背包问题实验及结果分析

多维多选择背包问题（multi⁃dimensional multi⁃choice knapsack problem，MMKP）是经典0⁃1背包问题的扩展，其约束包括：物品分为M类，指定第m个类中最多有Nm个物品，第i类中第j个物品的重量和价值分别为wij和vij，背包总容量为C，背包中对于一类物品至多有一个，其目标是最大化背包内组合物品数量的收益。

实验数据来源自Brunel University提供的测试集［12］，选取该数据集中13个测试用例，每个测试用例中物品分类数量从5个到400个不等，且各类数量中物品数量相同。记录运行结果的平均值AVG以及适应度最大值MAX，如表4所示，其中，M为物品类别数，N为物品总个数，R为每类物品数。

根据表4，在低维度多选择背包问题上，贪心算法能够获得较优的收益平均值，但随着物品种类数量以及每类物品数量的上升（M＞15和R＞10），GA，PSO，IB⁃PSO和EnBPSO和MPSO表现出较高的平均收益和最大收益。在智能优化算法中，二元粒子群系列改进算法（IBPSO，EnBPSO和MBPSO）所获得的收益高于经典优化算法（GA和PSO）。

表4 各二元PSO算法在背包问题上的实验结果Table4Experimental results of the different binary PSO algorithms on knapsack problem

综合背包问题的实验分析结果，在多选择背包问题维度上升时，适合采用IBPSO算法进行求解。

4 结束语

针对现有二元PSO求解离散优化问题时存在的问题，提出一种改进的二元PSO算法（IBPSO）。实验结果表明，在经典检验函数以及实际背包问题中，IBPSO较相同参数设定下其他优化算法具有更高的收敛精度以及更有效的收敛过程，体现了对离散问题的求解优势。

在今后的研究中，将IBPSO与其他离散问题相结合，研究与问题相关的特定启发式过程，指导IBPSO求解相关领域的离散问题。同时，基于策略融合是提高优化算法的有效手段，可将IBPSO与其他离散演化策略相互融合，借鉴其他演化策略的收敛优势，设计混合策略的离散优化算法。

［1］ZHU Hanhong，WANG Yi，WANG Kesheng，et al.Particle swarm optimization（PSO）for the constrained portfolio opti⁃mization problem［J］.Expert Systems with Applications，2011，38（8）：10161⁃10169.

［2］ZHANG Zike，ZHOU Tao，ZHANG Yicheng.Personalized recommendation via integrated diffusion on user⁃item⁃tag tri⁃partite graphs［J］.Physica A：Statistical Mechanics and its Applications，2010，389（1）：179⁃186.

［3］WU Changjun，KALYANARAMAN A.An efficient parallel approach for identifying protein families in large⁃scale met⁃agenomic data sets［C］／／Proceedings of the 2008 ACM／IEEE Conference on Supercomputing［S.l.］，2008：1⁃10.

［4］CAVUSLU M，KARAKUZU C，KARAKAYA F.Neural i⁃dentification of dynamic systems on FPGA with improved PSO learning［J］.Applied Soft Computing，2012，12（9）：2707⁃2718.

［5］KENNEDY J，EBERHART R C.A discrete binary version of the particle swarm algorithm［C］／／Proceedings of the Con⁃ference on Systems，Man，and Cybernetics.Piscataway，USA，1997：4104⁃4109.

［6］QIN Jin，LI Xin，YIN Yixin.An algorithmic framework of discrete particle swarm optimization［J］.Applied Soft Com⁃puting，2012，12：1125⁃1130.

［7］MOJTABA A K，TOOSI K N.A novel binary particle swarm op⁃timization［C］／／Proceedings of the 15th Mediterranean Confer⁃ence on Control and Automation.［S.l.］，2007：33⁃41.

［8］RATHI A，RATHI P，VIJAY R.Optimization of MSA with swift particle swarm optimization［J］.International Journal of Computer Allication，2010，12（8）：28⁃33.

［9］GANESH M，KRISHNA R，MANIKANTAN K，et al.Entro⁃py based binary particle swarm optimization and classification for ear detection original research article［J］.Engineering Applications of Artificial Intelligence，2014，27：115⁃128.

［10］BANSAL J，DEEP K.A modified binary praticle swarm op⁃timization for knapsack problems［J］.Applied Mathematics and Computation，2012，218（22）：11042⁃11069.［11］CHEN Enxiu，LI Jianqin，LIU Xiyu.In search of the essential binary discrete particle swarm［J］.Applied Soft Computing，2011，11：3260⁃3269.

［12］YANG Xiaohua，YANG Zhifeng，YIN Xinan，et al.Chaos gray⁃coded genetic algorithm and its application for pollu⁃tion source identifications in convection⁃diffusion equation［J］.Communications in Nonlinear Science and Numerical Simulation，2008，13（8）：1678⁃1688.

［13］AIHARA K.Chaos and its applications［J］.Procedia IU⁃TAM，2012，5：199⁃203.

［14］De JONG K A.An analysis of the behavior of a class of ge⁃netic adaptive systems［D］.Ann Arbor：University of Michi⁃gan，1975：196⁃249.

［15］KHAN S，LI K F，MANNING E G，et al，Solving the knapsack problem for adaptive miltimedia system［J］.Stu⁃dia Informatica：Special Issue on Cutting，Packing and Knapsacking Problems，2001，9：157⁃178.

An Improved binary particle swarm optimization for discrete optimization problems

YIN Guisheng，CUI Xiaohui，DONG Yuxin，YANG Xue
（College of Computer Science and Technology，Harbin Engineering University，Harbin 150001，China）

Binary particle swarm optimization（BPSO）is wildly used to solve discrete combinational optimization problems.With the low amount of population size and limit iterations，BPSO would have the evolutional problems such as low utilization of solution space，convergence of the speed and status of particles，as well as the degradation and volatility during the iterations.To solve these problems，an improved binary PSO（IBPSO）is designed，which uses the Gray code evolution based coding，chaos initialization process of population，improved modification of the speed and status of particles and the off⁃spring processing to increase the diversity and utilization of the population.According to the experimental results on the test functions with different types and multiple choice knapsack prob⁃lems，IBPSO outperforms the existing optimization algorithms and other binary algorithms with higher precision solu⁃tion and faster convergence speed，which shows the practicality of multiple discrete optimization problems.

binary particle swarm optimization；Gray code；chaos；off⁃spring processing；discrete optimization

10.3969／j.issn.1006⁃7043.201306024

http：／／www.cnki.net／kcms／doi／10.3969／j.issn.1006⁃7043.201306024.html

TP181

A

1006⁃7043（2015）02⁃0191⁃05

2013⁃06⁃05.网络出版时间：2014⁃11⁃27.基金项目：国家自然科学基金资助项目（61272186，61100007）；黑龙

江省自然科学基金资助项目（F200937，F201110）；黑龙江省博士后基金资助项目（LBH⁃Z12068）；中央高校基本科研业务费专项资金资助项目（HEUCF100608）.

印桂生（1964⁃），男，教授，博士生导师；

崔晓晖（1984⁃），男，博士研究生.

印桂生，E⁃mail：yinguisheng＠hrbeu.edu.cn.