针对混合变量优化问题的协同进化蚁群优化算法

韦铭燕，陈 彧，张 亮

（武汉理工大学理学院，武汉 430070）

（*通信作者电子邮箱chymath@gmail.com）

0 引言

科学研究和工程计算中的许多问题都可以建模为具有连续和离散决策变量的混合变量优化问题（Mixed-Variable Optimization Problem，MVOP）［1-4］。利用随机启发式算法（Random Heuristics Algorithm，RHA）求解MVOP，可以克服传统数学优化问题难以定位到全局最优解的不足，但如何实现混合变量搜索空间中的高效协同搜索，设计出能够快速收敛到MVOP 的全局最优解的混合变量启发式算法（Mixed-Variable Random Heuristics Algorithm，MVRHA），已成为RHA研究的一个具有挑战性的课题。

根据离散变量的可能取值是否具有大小（或先后）顺序，可以将离散变量分为序数变量和分类变量。由于序数变量的取值具有大小（或先后）顺序，可以根据序数变量取值的大小（或先后顺序）将其映射到连续实数搜索空间，利用实数空间的搜索策略得到实数值并将其转化为对应的序数变量值［5］。为了降低连续变量和离散变量之间的转化所产生的额外计算代价，Chen 等［6］设计了一种模仿连续差分进化（Differential Evolution，DE）算法搜索策略的离散编码DE 算法，并借鉴粒子群优化（Particle Swarm Optimization，PSO）的社会学习机制提高其对离散变量空间的搜索效率；Chen 等［7］提出了基于集合的PSO 算法，在离散解空间模仿PSO 在连续搜索空间中的动力学行为来提高算法在离散变量空间的搜索效率。对于取值集合没有大小（或先后）顺序的分类变量，Liao 等［8］则通过档案库构建面向分类变量的信息素模型，并采用蚁群优化（Ant Colony Optimization，ACO）策略来实现分类变量空间的有效搜索；Lin 等［9］设计了基于集合的DE 算法来模仿连续DE算法的搜索机制，从而实现在离散解空间的高效搜索。

为了实现对混合变量决策空间的高效协同搜索，Li 等［10］分别设计了针对连续变量和离散变量的变异策略；Liao 等［8］利用离散ACO 和连续ACO 来生成离散变量和连续变量子种群，并提出了相应的自适应参数设置方案［11］；Lin 等［9］分别采用基于集合的DE策略和连续DE策略来生成处理离散变量和连续变量；Wang等［12］分别构建了针对离散变量和连续变量空间的柱状图概率模型，设计了求解报童问题的混合变量模型的分布估计算法（Estimation of Dsitribution Algorithm，EDA）。这些研究工作在连续和离散变量子空间采用了同一类个体生成策略来实现子空间的协同搜索，试图在离散和连续变量空间中采用具有类似动力学特性的搜索机制来提高MVRH 算法的求解效率。

然而，离散变量的不连续跳跃取值可能产生具有强支配性的局部吸引域，即使采用同一类个体生成策略来得到连续和离散变量，也可能在连续和离散空间中产生完全迥异的搜索进程从而导致算法收敛到局部最优解。特别地，当离散变量为取值无序的分类变量时，模拟连续搜索策略的离散个体生成机制无法对离散取值空间的适应值分布进行有效的学习，更加难以实现对全局最优解的准确定位。为了解决无序性分类变量空间给定位全局最优解所造成的难题，本文采用协同进化（Coevolution）策略［13］来定位混合变量全局最优解，提出了求解MVOP 的协同进化蚁群优化算法（Coevolutionary Ant Colony Optimization Algorithm for MVOP，CACOAMV）。通过档案库来学习分类变量空间的适应值分布，CACOAMV利用离散变量的蚁群搜索策略来生成分类变量子向量；同时，利用连续蚁群搜索策略生成连续解向量，实现连续解空间的高效率局部开发；通过协作解（Cooperator）来对连续子向量和分类子向量进行评价，并基于评价结果对连续和分类种群进行更新，CACOAMV能够学习到分类变量的跳跃取值目标函数的适应值地形产生的支配性的影响，从而通过在混合变量空间的协同进化来收敛到MVOP的全局最优解。

1 求解MVOP的协同进化蚁群优化算法

考虑具有混合决策变量的最小化问题：

其中：X=(XR，XO，XC)由连续变量子向量XR=[x1，x2，…，xr]、序数变量子向量XO=[xr+1，xr+2，…，xr+o]以及分类变量子向量XC=[xr+o+1，xr+o+2，…，xr+o+c]构成，r、o、c分别是连续、序数和分类变量子向量的维数。连续变量xi的取值区间为（i=1，2，…，r），序数变量xj和分类变量xk的取值集合分别记为Oj（j=r+1，r+2，…，r+o）和Ck（k=r+o+1，r+o+2，…，r+o+c）。由于序数变量的取值可以按数的大小（或先后）排序，可以模仿连续优化搜索策略进行可行解空间的高效搜索［6-8］；然而分类变量的取值却没有明确的大小（或先后）顺序，更难确定全局最优的分类变量取值的吸引区域。因此，本文重点研究连续变量和分类变量共存的MVOP。

1.1 CACOAMV的算法框架

在MVOP（1）中，连续变量与离散变量具有性质迥异的可行区域，目标函数f(X)与两类变量也具有完全不同的相关关系，需要设计面向不同变量类型的空间搜索策略；同时，由于连续和离散变量空间的迭代搜索过程具有不同的动力学特性，分别采用面向连续变量和离散变量的个体生成策略来生成MVRSH 的连续变量子种群和离散变量子种群，并利用协同进化机制来实现两个子种群的合作协同搜索。

合作协同进化算法（Cooperative Co-Evolutionary Algorithm，CCEA）通过学习决策变量的相关关系来对决策变量进行分组，将复杂优化问题分解成若干个子问题，每个子问题都由一个单独的子种群来进行可行域搜索；各个子种群在迭代过程中通过协作解相互作用来实现子种群之间的协同进化，从而实现在MVOP 的混合变量可行域的全局搜索［13］。CCEA 的求解性能与其待优化问题中决策变量的相关关系的学习效率及问题的分解策略紧密相关，对决策变量相关关系的学习和子问题的分解策略是CCEA 设计的一个关键问题。然而，由于MVOP 中连续变量和分类变量具有显著的不同数学特性，可以分别将连续变量和分类变量分为一组，构建连续变量子种群PR和分类变量子种群PC来对连续变量子空间和分类变量子空间进行协同搜索，得到如下所示的CACOAMV。

算法1 CACOAMV。

输入 决策变量的个数n，连续决策变量个数r，分类决策变量个数c，档案库规模NA，蚁群大小M，最大迭代次数MaxIt；

输出 最优协作解B，最优解的目标函数值f*。

1.2 解档案库的构建和更新

为了使蚁群优化搜索过程具有较好的全局开发能力，需要构建反映全局适应值地形的档案库和信息素模型。为此，混合变量的蚁群优化（Mixed-Variable Ant Colony Optimization，ACOMV）［8］构建了面 向MVOP 可行解的解档案库（Solution Archive，SA），并由此来构建蚁群搜索的信息素模型。然而，构建面向MVOP的混合变量解向量档案库忽略了连续变量子空间和离散变量子空间的不同属性，不能准确反映和满足两个子空间的不同适应值分布对档案库中解分布的需求。因此，ACOMV所构建的信息素模型无法对离散和连续子空间的适应值地形进行准确刻画。

因此，CACOAMV分别对分类变量和连续变量构建解档案库。记档案库规模为NA，SA 将r维连续变量（或c维分类变量）子向量和对应的适应值存储在解档案库AR（或AC）中。在算法迭代初始，AR（或AC）由NA个随机生成的连续（或分类）变量子向量初始化，然后根据评价结果（评价策略见1.3.3 节）从优到劣对其进行排序。在迭代过程中，对生成的M个连续（或分类）解向量进行评价，将所有的NA+M个连续（或分类）解向量按适应值从优到劣进行排序，并将最好的NA个保留下来作为新的档案库AR（或AC）。

1.3 解的构造及评价策略

1.3.1 连续变量的解向量构造

根据档案库AR中个体的评价结果来构建信息素模型，采用高斯函数来对解的影响力进行量化［8］：

其中rank(j)是解Sj在档案库AR中的排名。解档案库中的最佳解将获得最大的影响力，而其他解的影响力则随着其排名呈指数下降。为了让算法能够适应不同优化问题中不同适应值地形对算法性能的影响，式（2）中引入了参数q来调节档案库中随着排名降低的解的影响力的衰减速度。

根据式（2）中所得到的影响力指标ωj，CACOAMV应用ACOR［14］中的连续变量生成策略，以概率pconj=从档案库AR中选择一个连续子向量XR(j)=(x1(j)，x2(j)，…，xr(j))来构造新的连续解向量TXR(j)=(tx1(j)，tx2(j)，…，txr(j))。对任意的1 ≤i≤r，txi(j)服从均值为xi(j)、标准差为σji的正态分布，其中，标准差σji由解档案库中所有解的第i个连续变量取值和参数ξ共同决定：

其中：参数ξ的值越大，则变异的标准差越大，在连续子空间的收敛速度越慢。

1.3.2 分类变量的解向量构造

设分类变量xj具有tj个可能的取值ν1，ν2，…，，则分类变量解生成策略以概率将值νk分配给xj，其中，概率分布由沉积在变量xj的取值νk上的信息素τj，k所确定：

信息素的挥发和沉积策略为：

其中信息素挥发率为ρ，在分类变量xj的值νk上的信息素沉积量［15］为：

其中me为精英蚂蚁数量的正整数。与MAX-MIN 蚂蚁系统［16］类似，CACOAMV对信息素的累积量的上下限进行了限制。信息素累积量的上、下限分别为：

当分类变量种群PC停滞代数超过设定值limit时，CACOAMV采用如下平滑机制调整沉积在变量xj的取值νk上信息素：

其中0 ＜θ＜1。式（9）对信息素的分布进行了重置，缩小了算法后期当前种群最优解中的信息素量与其他较差解的信息素量之间的差值，使得蚂蚁有可能选择非当前最优解，从而重新赋予了算法较强的全局探索能力。本文θ取值为0.5。

1.3.3 解的评价策略

根据协同进化算法的个体生成评价策略，CACOAMV分别生成连续变量子向量XR和分类变量子向量XC，并分别结合B=(BR，BC)的分类变量子向量BC和连续变量子向量BR来进行评价，即

1.4 重启机制

为了进一步提高CACOAMV的全局收敛能力，当算法所搜索到的最优解的连续停滞代数大于设定值StagIt时，则会触发重启机制。重启机制被触发后，将连续和分类变量子种群随机初始化，并保留所搜索到的最佳连续和分类变量子向量。对重启后子种群PR和PC中的个体的评价采用如图1 所示的“最佳+随机合作者”评价策略。

图1 “最佳+随机”合作者策略Fig.1 “Best+random cooperators”strategy

在图1（a）所示的最佳合作者策略中，将子种群P1的个体Xi与子种群P2中的最佳个体Ybest构成一个完整解TX；在图1（b）的随机合作者策略中，另一个完整解TY由P1的个体Xi与P2中随机选择的个体Yrnd结合而得到；利用目标函数对TX和TY进行评价，将较好的目标函数值作为P1的个体Xi的适应值，即：

2 仿真实验与结果分析

为了测试CACOAMV的性能，本文采用了由CEC’05 连续基准测试问题［17］生成的人造混合变量基准测试问题进行数值实验。首先，确定n维混合变量测试函数中的连续变量和分类变量的维数r和c（r+c=n）；然后，将CEC’05 连续基准测试问题的前r维连续变量保持不变，后c维连续变量通过如下方法转化为分类变量并确定其取值集合：在后c维连续变量的取值区间使用等距网格生成tj个数据点，再将其进行随机排列得到分类变量Cj的取值集合Tj={θj，1，θj，2…，θj，tj}，j=r+1，r+2，…，n。本文令测试问题的决策变量个数n为偶数，r=c=n/2，分类变量取值集合的大小为tj=100，j=r+1，r+2，…，n，生成的基准测试问题如下：

其中

式（12）～（17）分别代表6 个人造混合变量基准测试函数；式（18）表示经过旋转和移位后的混合变量，其中M为旋转矩阵，s*为问题的全局最优解；式（19）表示未经过旋转和移位处理的混合变量；式（20）表示连续变量的取值范围；式（21）表示分类变量的取值范围；式（22）表示n维决策变量由r维连续变量和c维分类变量组成。

2.1 CACOAMV的参数分析

为了能得到合适的参数设置，使得CACOAMV达到最佳的收敛性能，以10维的单峰函数f1和多峰函数f2作为测试问题，分析CACOAMV的分类变量解生成策略中的参数ρ和b对算法收敛性能的影响，FEs为算法运行过程中的目标函数评价次数。考虑到算法中的重启策略会对全局探索及局部开发能力产生影响，本节中的参数分析中关闭了CACOAMV中的重启机制。

函数f1具有椭球形的等值面，求解f1的高效算法需要具有能够适应不同位置的不同适应值地形的自适应局部开发能力。从图2 中的收敛曲线可以发现，CACOAMV的收敛进程在y=1(lgy=0)附近会出现停滞，而参数ρ和b的值越大，停滞阶段的持续时间越长。由此可见，在（局部）最优解的吸引区域，CACOAMV的开发能力随着ρ和b的值的增大而增大。

图2 CACOAMV求解f1的收敛曲线Fig.2 Convergence curves of CACOAMV on solving f1

从图3中的收敛曲线对比分析中可以发现，对于多峰问题f2，在经历了初期的快速收敛过程以后，由于分类变量子种群多样性的降低，离散子种群的收敛几乎停滞，而对连续变量子空间的局部开发使得其收敛曲线具有一个长期的缓慢收敛过程。虽然ρ的不同取值需要不同的b的取值相配合来获得相对较好的收敛效果，但从最终收敛结果来看，当ρ=0.15时，算法的收敛精度最好。这是因为当ρ较小，信息素的挥发速度较慢，信息素值的上限更大，从而使得蚁群具有更好的全局开发能力，无论是对于测试问题f1还是f2都可以得到更加好的全局探索能力，从而提高了CACOAMV在离散子空间的全局探索能力。

图3 CACOAMV求解f2的收敛曲线Fig.3 Convergence curves of CACOAMV on solving f2

2.2 在目标函数值空间的收敛结果比较

通过参数实验分析可以看到，较小的参数ρ和b的取值可以在获得较好的全局探索能力的同时得到较强的局部开发能力。考虑到CACOAMV可以通过重启机制来提高算法的全局收敛性能，本文中ρ和b都取得了较小的值，如表1所示。对于基准测试函数f1～f6，将 CACOAMV与 ACOMV［8］和L-SHADEACO［15］独立运行50 次，每次运行记录1.0E+06 次个体评价以后种群中的最佳目标函数值。若所得到的近似最优解的误差小于1.00E -10，则认为算法已经收敛到了精确的全局最优解，即近似误差为0。

表1 算法参数设置Tab.1 Algorithm parameter setting

首先，将三种算法对6 维和10 维测试问题的求解结果进行比较，结果见表2。结果表明，对于单峰的测试函数f1、f5以及在全局最优解附近具有平坦山谷的f4，CACOAMV的寻优成功率均达到了100%，表明CACOAMV在（局部或全局）最优解的吸引区域内能快速收敛到（局部或全局）最优解，具有较好的局部开发能力；对于多模态测试问题f2、f3、f6，CACOAMV的求解性能与ACOMV相比有显著提升，且其收敛结果也优于LSHADEACO，表明基于协同进化的迭代机制也提高了算法对混合变量可行域的全局探索和局部开发能力。

表2 对6维和10维测试问题f1～f6的实验结果比较Tab.2 Experimental results of solving 6-and 10-dimensional f1～f6 problems

通过横向比较可以看到，当测试问题的维数从6 维增加到10 维时，ACOMV和L-SHADEACO的收敛性能发生了较大的退化；相对而言，CACOAMV的收敛结果只发生了轻微的退化现象，对于大多数统计数据均优于其他两个算法的对应指标。

为了进一步比较算法性能随着维数的退化速度，将CACOAMV和L-SHADEACO在14 和18 维的测试问题上的优化结果进行比较，所得结果的平均值和标准差如表3所示。

表3 L-SHADEACO和CACOAMV对14、18维测试问题f1～f6的优化结果比较Tab.3 Performance comparison of L-SHADEACO and CACOAMV for solving 14-and 18-dimensional f1～f6 problems

表3 结果表明，CACOAMV在对于单峰和多峰问题的求解性能总体上均优于L-SHADEACO，CACOAMV中所采用的协同进化机制使其具有更好的全局探索和局部开发能力，降低了算法的收敛性能随着所求解优化问题的维数增加的退化速度。

2.3 在决策变量空间的收敛结果比较

由于不同的测试问题的目标函数值具有迥异的适应值地形，对最优目标函数值的近似误差不能准确反映其在决策空间中对全局最优解的近似程度，因此，本文将CACOAMV与GA、ACO-DE、GA-DE、ACOMV［8］和DEMV［9］进行了比较。其中，ACO-DE 和GA-DE 采用ACO 和GA 来生成分类变量解，并用经典的DE 算法来生成连续变量子向量。根据CEC’05 的基准测试集［17］中的5个单峰函数和8个多峰函数生成了13个10维的混合变量测试问题（记为F1～F6，F8～F14），测试CACOAMV在决策空间中的收敛性能。

为了得到公平的比较结果，本文对测试函数采用了与文献［9］相同的设置：每个测试问题中具有5 个连续变量和5 个分类变量，分类变量的取值集合包含100 个均匀分布的离散取值。以50 000次个体评价后所得到的最佳近似结果在决策空间中与全局最优解的距离作为评价指标，经过100 次独立运行后的平均距离和平均排名如表4 所示。数值实验结果表明，从决策空间中对全局最优解的近似程度来看，CACOAMV的近似性能整体上来看优于其他五种算法，表明基于协同进化框架下的混合变量优化方法能够更好地实现混合变量决策空间的协同搜索，大大提高随机启发式算法对MVOP 的优化性能。

表4 决策变量空间中的近似性能比较Tab.4 Comparison of approximation performances in decision variable space

3 结语

针对MVOP 中连续变量子空间和离散变量子空间的合作搜索难题，本文提出了一种基于协同进化框架的混合变量蚁群优化算法CACOAMV。通过构建连续搜索空间和离散搜索空间的信息素模型，CACOAMV分别生成连续和离散解向量并通过协同进化机制来实现连续、分类变量解向量的评价和混合决策变量空间的合作协同搜索。通过与信息素平滑机制和重启机制相结合，CACOAMV具有更强的局部开发能力和全局探索能力，其在混合变量解空间的搜索能力由空间维数的上升所导致的性能退化更加缓慢。由此可见，基于协同进化的随机启发式搜索是一种求解MVOP 的有效搜索机制，有望在复杂的高维MVOP中取得令人满意的优化性能。