变分布的量子行为粒子群优化算法求解工程约束优化问题

施晓倩，陈祺东，孙 俊，冒钟杰

（1.江苏省物联网应用技术重点建设实验室（无锡太湖学院），江苏无锡214000；2.人工智能与模式识别国际联合实验室（江南大学），江苏无锡214000）

（∗通信作者电子邮箱cqd_jnu@hotmail.com）

0 引言

粒子群优化（Particle Swarm Optimization，PSO）算法是一种随机搜索算法，是群体智能算法中的重要一种，该算法在1995年由Kennedy等［1］提出。在这之后，为了改进粒子群优化算法的搜索能力，在基于原始粒子群优化算法的基础上增加策略或改进的算法被先后提出［2-10］，并广泛运用于交通［11］、军事工业［12］、医疗［13］或其他领域［14-16］。

近十几年来，大部分学者主要研究使用群体智能算法来求解无约束的优化问题，而对约束优化问题的研究则相对较少。约束优化问题（Constrained Optimization Problem，COP）是优化问题中比较复杂的问题，这类问题一般可描述为：

其中：X=（X1，X2，…，XD）是D维决策向量，f(X)是目标函数，gj(X)是第j个不等式约束，hk(X)是第k个等式约束，第i维变量Xi的取值范围为[XMINi，XMAXi]。等式约束一般可将其通过|hk()X|≤ε转换为两个不等式约束，ε是一个接近于0的阈值，通常取值10-5～10-3。

约束优化问题可以描述为在保证变量X满足式（1）等式和不等式约束的前提下，在变量定义的范围内使得目标函数搜索到最优点X*，使得f(X*)最小。若变量X违背一个及以上约束条件，则称其为不可行解；若变量X满足所有的约束条件，则称其为可行解，所有的可行解集合称为可行域，一般用F表示。X所有可能取值的集合称为搜索空间，一般用S表示，F⊆S。

使用粒子群算法求解约束优化问题主要的难点在于有效地处理约束条件，一般来说，这些处理方法可分为4种［17］：

1）保留满足约束条件的个体，即每次迭代只保留在可行域上的点。

2）修复不满足约束条件的个体，即用群中粒子满足约束条件的个体和不满足约束条件的个体进行杂交处理，直到其满足所有约束条件。

3）罚函数法。罚函数法是处理这类问题最多的方法，一般分为静态的罚函数和动态罚函数。

4）混合算法。即将不同的算法结合来求解约束优化问题。

方法1通过每次保留符合条件的粒子的做法，本质上是穷举的方式，时间复杂度高且浪费计算资源；方法2和方法4有较强的局部搜索能力，然而通过混合算法或者修复不满足条件个体的方式增加了许多参数，调整参数难度大，算法的适用性不高。因此，本文采用罚函数法来求解约束优化问题。

在以前的工作中，粒子群优化算法被证明是适合求解约束优化问题的：文献［18-19］直接使用经典的粒子群优化算法求解约束优化问题，并取得了很好的效果；文献［20］使用改进的粒子群优化算法RDPSO（Random Drift Particle Swarm Optimization）求解电力优化问题；文献［8］中证明粒子群优化算法或者改进的粒子群优化算法最终能够收敛，但是在解决优化问题时，由于粒子群优化算法的局部搜索能力弱导致不能精确搜索到全局最优点；为了改善粒子群优化算法的局部搜索能力，文献［21-22］采用和差分进化或遗传算法混合的方式来增强粒子群优化算法的局部能力；文献［23-25］通过控制粒子群的多样性使得算法在一定程度上避免算法陷入局部最优。

工程设计问题是现实生活中常见的约束优化问题，很多学者尝试用群体智能算法运用到该领域：文献［26］提出协同演化的粒子群优化算法；文献［27］使用引力群体算法结合遗传算法来求解优化问题取得了优异的表现；文献［28］首先使用基于高斯分布的量子行为粒子群优化算法求解工程设计问题，对比原始的也就是基于均匀分布的量子行为算法，该算法的局部能力大大增强，然而该算法的全局搜索能力没有得到维持。因此，本文提出了一种变分布的基于高斯分布的量子行为粒子群优化算法。

本文的贡献在于：第一，改进的策略简单但有效，即在迭代过程中不断缩小搜索的概率空间以此来达到算法从强全局搜索能力到强局部搜索能力的稳定迁移。第二，参数少，相比于结合遗传算法或差分进化，或者其他例如Powell等一维搜索算法，该算法只需要调整两个参数即高斯分布的方差和收缩扩张因子来满足不同问题精度的需求。

1 自适应的高斯量子行为粒子群优化算法

本章首先介绍经典的量子行为粒子群优化算法的由来，然后详细描述该算法中粒子的更新迭代过程，接着分析该算法的优点和不足点，进一步提出本文的算法——自适应的基于高斯分布的量子行为粒子群优化算法，并将该算法求解工程约束优化问题的过程以流程图的方式给出。

1.1 量子行为粒子群优化算法

群体智能算法是模拟自然界群体行为提出的，粒子群优化算法是其中的一种。近十几年来，很多改进的粒子群被提出，并广泛运用到工程、医疗、经济管理等领域中。Kennedy在“Swarm Intelligence”中提到粒子群优化算法的随机性代表了算法的智能，根据他的论述，文献［2］提出了具有量子行为的粒子群优化（Quantum-behaved Particle Swarm Optimization，QPSO）算法。该算法通过模拟量子系统中态叠加性的强不确定性，使得QPSO算法能够在迭代过程中仍旧有概率覆盖整个概率搜索空间，而不是像其他一些粒子群优化算法在搜索过程的末尾失去全局搜索能力，停滞在局部最优点附近。

QPSO算法步骤如下：

步骤1 在搜索空间中初始化粒子群中粒子的位置，全局最优位置和个体最优位置；

步骤2 根据式（6）计算粒子群的平均最优位置。

步骤3 根据式（5）计算收缩扩张因子αt；

步骤4 通过式（7）更新粒子位置并计算粒子的当前适应值。

步骤5 更新各粒子的个体最优位置和群体当前的全局最优位置；

步骤6 重复步骤2～5，直至满足一定的循环结束条件。

1.2 自适应的高斯量子行为粒子群优化算法

得益于引入概率分布使得具有量子行为的粒子群在搜索过程中能够使粒子能以一定几率到达搜索空间的任何一个位置，所以算法具有很强的全局搜索能力。然而，这种很强的随机性也减弱了量子行为的粒子群优化算法的局部搜索能力。

图1展示了算法在搜索过程的末尾阶段种群的分布，然而在更新过程中如果问题的全局最优点区域幅度小，对具有量子行为的粒子群优化算法来说，由于其包含随机值变动范围大，个体极其容易跳过全局最优点。因此，文献［27］将均匀概率分布替换成由标准高斯概率分布产生的随机数，使得粒子在更新过程中能够以较高的概率使更新位置接近吸引子，这种方法能够提升局部搜索能力尤其是在进化过程的后期，但是其全局搜索能力却大大减弱。

图1 全局最优附近区域的种群分布Fig.1 Swarmdistribution near global optimum

因此，本文提出了一种自适应的基于高斯概率分布的量子行为粒子群优化算法（Adaptive Gaussian Quantum-behaved Particle Swarm Optimizer，AG-QPSO），通过使高斯分布随时间动态变化来逐步调整需求，即从强的全局搜索能力需要逐步转化为强的局部搜索能力需要。如图2所示，随着种群的不断迭代和搜索过程的进行，粒子更新位置范围（距离吸引子的距离）将不断收缩减小直到收缩到吸引子，其中Gt代表第t次迭代过程。

其中σ呈线性下降，可以表示为：

其中：N(0，σ2)是均值为0、σ2为标准差的高斯概率分布。σu和σl分别代表初始最大值方差和最小值方差，这两个参数可根据问题调整。和基于高斯分布的量子行为粒子群优化算法不同的是，AG-QPSO不需要使用收缩扩张因子αt来控制种群的搜索过程。使用收缩扩张因子极难控制种群的多样性（一般会出现种群多样性的迅速收缩），而通过变高斯的方法控制种群搜索范围的优点是它让种群多样性缓慢下降，通过随时间调整高斯分布的标准差来实现粒子更新位置的范围，从而达到自适应调整全局搜索和局部搜索能力。

图2 AG-QPSO搜索过程中的种群分布变化Fig.2 Changeof swarmdistribution in AG-QPSOsearch process

如图3所示，当标准差σ2越大，高斯概率分布越接近于扁平，从而与标准分布图4所示的标准均匀近似，因而初始的更新过程具有很强的全局搜索能力。逐步地，随着标准差变小，随机值在0附近的概率就越大，也就使得粒子更新的范围越接近吸引子，因而在搜索过程末尾算法的局部搜索能力越来越强。

图3 随方差变化的高斯分布图Fig.3 Gaussian distribution varyingwith variancechange

图4 均匀概率分布Fig.4 Uniform probability distribution

1.3 罚函数法

罚函数法是处理约束条件常用的一种方式，一般可以描述为：

其中，f(X)是约束优化问题的目标函数，如果个体满足所有的约束条件，则它的适应值等于目标函数的值；如果不满足也就是约束条件大于0时，则当前个体的适应值等于式（12）的第二个等式，也就是加上了惩罚值。惩罚项由两个参数构成，r是一个正值，在本文中，它设定为5000，q是当前个体不满足约束条件的个数。需要注意的是，所有的约束条件在最初都处理成小于等于0的不等式。

自适应高斯分布的量子行为粒子群优化算法求解工程约束优化问题的流程如5所示。

图5 基于罚函数的AG-QPSO算法流程Fig.5 Flowchart of the penalty function based AG-QPSOalgorithm

2 工程优化问题描述

2.1 压力容器设计问题

在这个问题中，圆柱形容器的两端安装着半球形的容器盖，由两个纵向焊缝组合形成一个圆柱体，如图6所示。

图6 压力容器设计问题Fig.6 Design problem of pressure vessel

该问题的目标值由4个决策变量决定，分别是：压力容器的厚度Ts，头部厚度Th，容器内半径R和容器去掉头部的长度L。因此，压力容器设计问题的优化问题模型Y=[Ts，Th，R，L]=[X1，X2，X3，X4]可以描述为：

这个优化问题的目标是使得材料成本、制作成本、焊接成本的和最小。

2.2 张弦（压力弦）设计问题

张弦（压力弦）设计问题的目标是最小化张弦的重量，如图7所示。该问题主要有3个决策变量，分别是平均线圈直径X1、线径X2和有效线圈数X3，该问题定义如下：

限制条件为：

图7 张弦（压力弦）设计问题Fig.7 Design problem of tension string

3 实验结果与分析

本章首先将AG-QPSO算法运用于解决压力容器设计问题和张弦（压力弦）设计问题，以验证算法的能力，然后比较了AG-QPSO算法与其他算法的时间复杂度。需要说明的是，本文所有的实验都是在python 2.7环境下单线程运行的，实验所用的配置为Intel酷睿双核CPU，4 GB内存。

3.1 参数设定

AG-QPSO只需要设置高斯分布方差的初始值和终值，针对本文中这两个工程设计问题，σ2u和σ2l的值分别为5和0.001。实验中，种群的个数M为80，最大迭代次数T为1000，每个问题都运行50轮来验证。

3.2 压力容器设计问题

针对压力容器设计问题，文献［29］结合外部惩罚函数或二次规划方法实现分支定界过程，变量边界独立于设计约束进行处理，省去了每个分支节点重新构造问题；文献［30］利用随机优化技术模拟退火来求解混合离散非线性优化问题；文献［31］提出了一种求解含整数、离散、零一和连续变量的机械设计优化问题的混合变量进化规划（Mixed Variable Evolutionary Programming，MVEP），该算法改进了混合变量空间的全局搜索和收敛性能；文献［32］提出了一种求解非线性工程设计优化问题的稳健优化设计算法。该算法根据遗传算法的原理，使用二元编码和实数编码的组合来处理这些混合变量，简称为遗传自适应搜索；文献［33］提出了一种协同进化的遗传算法，并取得了良好的结果；文献［27］在量子行为粒子群优化算法基础之上，使用高斯分布替代均匀分布来提高局部搜索能力。

本文将提出的AG-QPSO算法运用到该问题，并取得了显著的成绩。如表1所示，在满足所有约束条件的情况下，AGQPSO找到的最优值为5 885.332 8，其中，表1中的变量g1、g2、g3、g4分别是由约束不等式（14）、（15）、（16）和（17）在决策向量为X=(X1，X2，X3，X4)得到的值。由于算法是在量子行为粒子群的基础上进行改进，因此，本文首先将该算法与经典的PSO、原始的QPSO和在该约束优化问题上取得很好结果 的 G-QPSO（Gaussian Quantum-behaved Particle Swarm Optimization）进行比较，实验结果发现，不管是均值、中值还是最优值，AG-QPSO均优于其他所有的算法且算法搜索更为稳定，如表2所示（50轮结果计算得到）。与本文之前分析的一样，粒子群相关的算法有较强的全局搜索能力，而欠缺局部搜索能力，尤其是面对这类在最优点附近搜索区域极为尖锐的工程约束优化问题。

进一步，本文将算法与其他现有算法进行比较，如表3所示，从表中实验结果可以看出，本文提出的AG-QPSO算法明显优于其他算法。

表1 压力容器设计问题中使用AG-QPSO的最佳结果Tab.1 Optimal resultsof pressurevessel designproblemusing AG-QPSO

表2 压力容器设计问题中PSO、QPSO、G-QPSO和AG-QPSO的对比结果Tab.2 Comparison resultsof PSO，QPSOand G-QPSOon pressurevessel design problem

表3 压力容器设计问题上所提算法与其他算法的比较Tab.3 Comparison of theproposed algorithm and other algorithmson pressurevessel design problem

3.3 张弦（压力弦）设计问题

文献［33］首先采用8种优化方法解决张弦设计问题。文献［34-37］也用其他优化方法解决了这个问题。同样，本文将AG-QPSO运用到张弦（压力弦）设计问题。如表4所示，本文挑选了在算法运行50轮后最优的结果，在满足所有约束条件的情况下，算法取得了最优值0.010 95788的结果。

表4 张弦（压力弦）设计问题中使用AG-QPSO的最佳结果Tab.4 Optimal results of tension string design problem using AG-QPSO

同样，与PSO、QPSO、G-QPSO相比，AG-QPSO不管在中值、均值还是最优值上都仍旧远远超过这些算法，而且方差小只有7.663 53×10-17，如表5所示，意味着算法具有很高的鲁棒性。

表5 张弦（压力弦）设计问题中4种算法的对比结果Tab.5 Comparison results of four algorithms ontension stringdesign problem

表6展示了之前一些算法在该问题上的最优解，可以清晰地看到，相比于之前的一些算法，AG-QPSO在这个问题上表现最优。

3.4 时间复杂度分析

衡量群体智能优化算法性能的标准是算法求解问题的精度和算法求解问题的速度。在压力容器问题和张力弦两个多约束优化问题上的实验结果表明，与其他现有的针对多约束优化问题的算法相比，AG-QPSO算法求解问题的精度最好。而优化算法求解问题速度的比较将通过对算法进行时间复杂度的分析。因此，本文将重点分析AG-QPSO算法与标准PSO、标准QPSO、G-QPSO和其他一般的混合算法的时间复杂度。

表6 张弦（压力弦）设计问题上所提算法与其他算法的比较Tab.6 Comparison of theproposed algorithmand other algorithmson tension stringdesign problem

在本文中，参考文献［38］对优化算法时间复杂度的分析，将分为4个方面，即初始化时间复杂度、算法评估的时间复杂度、粒子位置更新的时间复杂度和算法总体的时间复杂度来进行评判。表7中给出了这五类算法这4个方面的时间复杂度。

表7 五种算法复杂度比较Tab.7 Complexity comparison of fivealgorithms

从表7中可以看出，混合算法例如标准PSO结合遗传算法由于在粒子位置更新中增加了变异、交叉、选择操作，因此该算法的粒子位置更新的时间复杂度相对于其他四种算法更高，与标准PSO算法、标准QPSO算法、G-QPSO算法相比时间复杂度更高。

由于AG-QPSO算法没有增加更多的计算过程，因此本文提出的AG-QPSO算法在求解问题的速度上与其他算法是一致的。

4 结语

本文设计了一种自适应基于高斯分布的量子行为粒子群优化算法，用于求解工程设计问题。首先，本文调研了许多关于利用群体智能算法来求解约束优化问题的文献，发现这些文献都围绕提高算法在搜索末尾阶段的局部搜索能力来改进算法。然而，这些算法大大增加了算法的时间复杂度和调整参数的难度。因此本文在基于量子行为粒子群优化算法的基础之上，通过改变围绕吸引点邻域概率分布，即从简单的均匀分布到从开始阶段利用高方差的高斯分布近似均匀分布到搜索末尾阶段利用低方差的高斯分布提高其局部搜索能力，从而使算法稳定地从强全局搜索能力到强局部搜索能力迁移。进一步为了验证算法的求解能力，本文使用该算法测试了压力容器设计问题和张弦（压力弦）设计问题2个实际工程设计问题，并与近几年表现优异的算法进行了比较，发现自适应基于高斯分布的量子行为粒子群优化算法表现更为突出。

未来，本文考虑到实际问题并不需要考虑求解的时间长短，而更注重结果的精度，因此，之后本文将考虑采用控制种群多样性的策略来保持更为稳定的全局搜索能力。