基于文化基因算法的多目标优化

温 攀，王社伟，陶 军，杨尚君

(空军航空大学，长春 130022)

在科研和实践中，经常会遇到需要使多个相互冲突的目标均尽可能最佳的优化问题，这类问题一般被称为多目标优化问题(multi-objective optimization problem，MOP)。大多数工程和科学问题都是多目标优化问题，存在多个彼此冲突的目标，如何获取这些问题的最优解，一直是学术界和工程界关注的焦点问题［1］。

1989年，Moscato 在Moscato P.On evoltion，search，optimization，genetic algorithms and martial arts:towards Memetic algorithms 中，首次把memetic 这一术语引入计算机科学领域。文化基因算法(memetic algorithm)是一种较宽松的优化算法框架，采用不同的搜索策略可构成不同的Memetic 算法。本文采用粒子群算法为全局搜索策略，模拟退火算法为局部搜索策略，针对粒子群容易陷入局部最优而进行改进，保留粒子群算法快速收敛的特点，融入模拟退火算法全局性好的特点。通过将多目标优化AI-NN--PR 问题的求解仿真结果进行比较表明，与NSGA-Ⅱ相比，本文提出的Memetic 算法能得到更好的优化结果。

1 多目标优化问题描述

通常在多目标优化领域被普遍接受的多目标优化问题定义如下［5］。

定义1 一般的多目标优化问题由n 个决策变量、M 个目标函数和K 种约束条件组成，最优化目标如下:

其中:x=(x1，x2…，xn)T是n维向量，称x 为决策向量;x 所在的空间为决策空间En;f1(x)，…，fm(x)称为目标函数;m维向量(f1(x)，…，fm(x))所在的空间称为目标空间Em;gi(x)，hk(x)为约束函数。

在单目标优化中，可行集中的解可根据目标函数的优劣关系进行排列，最终得到1 个全局最优解。但在MOP 中，可行集中的解对应多个目标函数，很难对可行域中的解进行优劣关系排列，因此不能像单目标优化中一样得出1 个全局最优解。针对该问题，法国经济学家V.Pareto 提出了Pareto 的最优的概念［6］，所有Pareto 最优解对应的目标函数值所形成的区域称为Pareto 最优前端，求解多目标优化问题的目的就是尽可能多地获取问题的Pareto 最优解。

2 基于粒子群的Memetic 算法

2.1 算法的改进策略

Memetic 算法主要根据待优化问题的性质来选择适当的全局和局部搜索方法。粒子群算法比较适合于连续问题，而且具有比遗传算法更高的执行效率。模拟退火算法的并行技术能大幅度改进系统性能，加大信息吞吐量和提高运算速度;求解不同的非线性问题，对不可微甚至不连续的函数优化，能以较大概率求得全局最优解，具有较强的鲁棒性、全局收敛性、隐含并行性以及广泛的适应性，并且能处理不同类型的优化设计变量(离散的、连续的和混合型的)，不需要任何辅助信息，对目标函数和约束函数没有任何要求。本文采用改进粒子群作为全局搜索策略，模拟退火作为局部搜索策略，来验证该组合的Memetic 算法对多无人机任务分配的有效性。

根据以上特点对算法做出如下改进。文化基因算法主要进行的是全局搜索和局部搜索2 个步骤，下面将具体说明。

1)采用粒子群算法作为全局搜索策略，以粒子群的更新机制作为进化的机制。

2)以模拟退火算法作为局部搜索策略，在粒子搜寻到极值的同时对极值的周围进行局部搜索，提高解的精确性。同时对粒子群进化后的适应度值按Metropolis 准则接受优化解的同时概率接受恶化解。

3)在全局搜索中引入交叉和变异操作，产生新的粒子，并对新的粒子进行搜索，帮助跳出局部最优。

4)借鉴粒子群寻优思想，在每一迭代过程中保留粒子个体的历史最优解和种群的全局最优解，以便交叉和变异的个体在下1 次搜索中依然朝着最优的方向寻找，保证算法的快速性。

2.2 算法步骤

综上所述，文化基因算法的主要步骤如下:

第1 步 初始化算法参数(包括种群数量n、粒子位置x和速度v，各粒子的适应度d，初始温度T，迭代次数L 等)。

第2 步 计算各粒子的适应度，记录个体极值pbest和群体极值gbest。

第3 步 应用粒子群算法进行全局搜索，将种群中各粒子个体按照粒子群更新机制更新位置。记录每次迭代产生的个体极值pbest和群体极值gbest。

第4 步 对每次迭代产生的解S1产生随机扰动生成新解S2，对新解S2进行模拟退火搜索。

第5 步 如果达到指定迭代次数，算法继续，否则转向第2 步。

第6 步 随机选取粒子个体与个体极值pbest和群体极值gbest分别进行交叉操作，个体极值和群体极值自身进行变异操作，产生新的粒子ωi，并对新的粒子进行搜索。

第7 步 如果达到最大迭代次数或是搜索到满足要求的解，则算法停止并输出结果，否则将返回第3 步。

算法步骤如图1 所示。

3 仿真实验

3.1 仿真测试

为了验证Memetic 算法解决多目标优化问题的快速性、有效性以及Pareto 解的分布性能，将该算法与多目标进化算法SPEA2 和NSGA-Ⅱ算法［5］进行对比分析。

测试实验中，Memetic 算法主要参数设置为:粒子群种群n=50，迭代次数L=500，产生游荡者次数S=4，适应度函数权值a=0.3，b =0.3，c =0.4。NSGA -Ⅱ算法参数设置为:与Memetic 算法迭代次数相同，n = L* S =500，交叉概率0.9，变异概率0.1，SPEA2 进化代数为500，每个算法独立运行20 次，从中选取1 次最好的结果进行比较，实验结果见图2。

图1 算法步骤

图2 仿真结果比较

3.2 性能评价指标［8］

1)收敛性能评价指标γ

收敛性能评价指标γ 表示所求解与问题的真实Pareto最优解的逼近程度，其计算公式为

2)分布性能评价指标Δ

分布性能评价指标Δ 是通过度量多目标优化算法求得的Pareto 最优解集中的解在目标空间中象点分布的均匀程度来评价算法分布性能的。

进行分布均匀程度度量时，首先将这些点按其中1 个目标值的大小进行排列，然后分别计算其中的2 个边界点到全局Pareto 前沿面的2 个边界点的欧几里德距离de1和de2，以及每两相邻点之间的欧几里德距离di，i =1，2，…，l -1 和这些距离的平均值¯d，最后再按下式进行计算

Δ 的值越小表示求得的Pareto 最优解集在目标空间中的象点集分布越均匀。

从仿真图可以看出，改进后的多目标优化文化基因算法具有很好的搜索最优解的能力和求解精度。

4 结束语

本文将粒子群算法进行有效改进作为全局搜索，多目标模拟退火作为局部搜索，保持了粒子群算法收敛速度快和模拟退火算法获取全部最优值的能力，并根据非劣解的拥挤度决定最优值的选取，使得求得的非劣解集具有良好的分布性和求解精度。通过与NSGA -Ⅱ算法和SPEA2 算法进行仿真对比表明，本文算法在解决多目标优化问题上能取得更好的结果。

［1］申晓宁.基于进化算法的多目标优化方法研究［D］.南京:南京理工大学，2008.

［2］Zitzler E，Deb K，Thiele L. Comparison of multi-objective evolutionary algorithms:empirical results［J］. Evolutionary Computation，2000，8(2):173-195.

［3］Deb K，Agrawal S，Pratap A，et al.A fast and elitist multiobjective genetic algorithms:NSGAⅡ［J］.IEEE Transactions on Evolutionary Computation，2002，6(2):182-197.

［4］Deb K.Multi-objective genetic algorithms:Problem difficulties and construction of test problems［J］. Evolutionary Computation，1999，7(3):205-230.

［5］雷德明，严新平.多目标智能优化算法及其应用［M］.北京:科学出版社，2009.

［6］Pareto V. Cours Deconmie Politique［M］. Lausance:F.Rouge，1986.

［7］梁艳春，吴春国，时小虎，等.群智能优化算法理论与应用［M］.北京:科学出版社，2009.

［8］郑金华.多目标进化算法及其应用［M］.北京:科学出版社，2007.

［9］刘漫丹. 文化基因算法(Memetic algorithm)研究进展［J］.自动化技术与应用，2007，26(11):1-4.

［10］郭辉，徐浩军，谷向东，等. 基于改进粒子群算法的协同多目标攻击空战决策［J］.火力与指挥控制，2011(6):49-51.