论文部分内容阅读
摘 要 多目标优化是最优化领域的一个重要研究方向，本文简要介绍了多目标优化的模型和几种多目标优化的进化算法，并对算法进行了简要比较。
关键词 多目标优化 粒子群 遗传算法 蚁群算法 人工免疫系统
中图分类号：TP391 文献标识码：A
一、背景
多目标优化（Multiobjective OptimizaTionProblem，MOP）是最优化的一个重要分支，多目标问题中的各目标往往是有着冲突性的，其解不唯一，如何获得最优解成为多目标优化的一个难点，目前还没有绝对成熟与实用性好的理论。近年来，粒子群算法、遗传算法、蚁群算法、人工免疫系统、等现代技术也被应用到多目标优化中，使多目标优化方法取得很大进步。本文将其中四种多目标优化的进化算法进行一个简单的介绍和比较。
二、不同算法介绍
（一）多目标遗传算法。
假定各目标的期望目标值与优先顺序已给定，从优先级最高的子目标向量开始比较两目标向量的优劣性，从目标未满足的子目标元素部分开始每一级子目标向量的优劣性比较，最后一级子目标向量中的各目标分量要全部参与比较。给定一个不可实现的期望目标向量时，向量比较退化至原始的Pareto排序，所有目标元素都必须参与比较。算法运行过程中，适应值图景可由不断改变的期望目标值改变，种群可由此被引导并集中至某一特定折中区域。当前种群中（基于Pareto最优概念）优于该解的其他解的个数决定种群中每一个向量解的排序。
（二）人工免疫系统。
人工免疫算法是自然免疫系统在进化计算中的一个应用，将抗体定义为解，抗原定义为优化问题，抗原个数即为优化子目标的个数。免疫算法具有保持个体多样性、搜索效率高、群体优化、避免过早收敛等优点。其通用的框架是：将优化问题的可行解对应抗体，优化问题的目标函数对应抗原，Pareto最优解被保存在记忆细胞集中，并采取某种机制对记忆集进行不断更新，进而获得分布均匀的Pareto最优解。
（三）多目标PSO约束算法。
将粒子群优化算法运用于优化问题，关键是如何确定群体全局最优位置pbest和每个粒子的最优位置gbest。由于多目标优化问题并无单个的最优解，所以不能直接确定gbest，pbest。PSO算法的优势在于：第一，有着高效的搜索能力。第二，并行地同时搜索多个非劣解。第三，有着较好的通用性。PSO算法在处理多目标约束优化问题时，主要是解决自身和群体最佳位置，对于群体最佳位置的选择，一是所得到的解要在Pareto边界上具有一定得分散性，二是要求算法收敛速度好。对于自身最佳位置的选择要求是通过较少的比较次数达到非劣解的更新。PSO算法在处理约束时，多采用惩罚函数法。
（四）多目标蚁群算法。
多目标蚁群算法的思想是：根据目标函数的数目将蚂蚁分成若干子群体，为每个子群体分配一个目标函数，在其他子群体优化结果的基础上通过Pareto过滤器来获得均衡解。基本步骤如下：
1、转移概率：对每一个目标k需要考虑一些信息素轨迹 k，在算法的每一代中，每一只蚂蚁都计算一组权重p=（p1，p2，…，pk），并且同时使用启发式信息和信息素轨迹。
2、局部信息素更新：当每只蚂蚁走完aij边之后，对每个目标k我们采取更新：
ijk=（1- ） ijk+ 0
其中， 0是初始信息素的值， 是信息素挥发速率。
3、全局信息素更新：对每个目标k，在当前代只对产生最好和第二好的解进行信息素更新，使用规则如下：
ijk=（1- ） ijk+ △ ijk
4、设置Pareto解集过滤器：
设置Pareto解集过滤器来存放算法运行时产生的Pareto解。
三、结论
四种进化算的优缺点总结如下：
多目标遗传算法：有着良好的鲁棒性和优越性，在拥挤选择算子时，限制种群大小使用拥挤比较过程，使算法失去了收敛性。人工免疫系统：可以得到优化问题的多个Pareto最优解，算法运行缺乏稳定性。多目标PSO约束算法：能够实现对多维复杂空间的高效搜索，研究还处于起步阶段。多目标蚁群算法：Pareto前沿均匀性以及Pareto解集多样性，早熟停滞和在控制参数难以确定。□
（作者单位： 四川大学商学院）
参考文献：
[1]马小姝.传统多目标优化方法和多目标遗传算法的比较综述[J].电气传动自动化 ，2010.
[2]谢涛， 陈火旺.多目标优化与决策问题的演化算法[J].中国工程科学，2002.
[3]王鲁，罗婷，赵琳，段海峰.基于遗传算法的多目标优化技术[J].科技广场，2009.
[4]樊纪山， 王经卓.基于人工免疫系统的多目标优化算法的研究[J].福建电脑2008.
[5]池元成，蔡国飙.基于蚁群算法的多目标优化[J].计算机工程，2009.
[6]孔翔宇.基于蚁群算法的多目标优化问题研究[J]四川理工学院学报，2010.
[7]薛洪波， 伦淑娴.粒子群算法在多目标优化中的应用综述[J].渤海大学学报，2009.
[8]吴庆洪.粒子群优化算法及其应用综述[J].微计算机信息，2010.
关键词 多目标优化 粒子群 遗传算法 蚁群算法 人工免疫系统
中图分类号：TP391 文献标识码：A
一、背景
多目标优化（Multiobjective OptimizaTionProblem，MOP）是最优化的一个重要分支，多目标问题中的各目标往往是有着冲突性的，其解不唯一，如何获得最优解成为多目标优化的一个难点，目前还没有绝对成熟与实用性好的理论。近年来，粒子群算法、遗传算法、蚁群算法、人工免疫系统、等现代技术也被应用到多目标优化中，使多目标优化方法取得很大进步。本文将其中四种多目标优化的进化算法进行一个简单的介绍和比较。
二、不同算法介绍
（一）多目标遗传算法。
假定各目标的期望目标值与优先顺序已给定，从优先级最高的子目标向量开始比较两目标向量的优劣性，从目标未满足的子目标元素部分开始每一级子目标向量的优劣性比较，最后一级子目标向量中的各目标分量要全部参与比较。给定一个不可实现的期望目标向量时，向量比较退化至原始的Pareto排序，所有目标元素都必须参与比较。算法运行过程中，适应值图景可由不断改变的期望目标值改变，种群可由此被引导并集中至某一特定折中区域。当前种群中（基于Pareto最优概念）优于该解的其他解的个数决定种群中每一个向量解的排序。
（二）人工免疫系统。
人工免疫算法是自然免疫系统在进化计算中的一个应用，将抗体定义为解，抗原定义为优化问题，抗原个数即为优化子目标的个数。免疫算法具有保持个体多样性、搜索效率高、群体优化、避免过早收敛等优点。其通用的框架是：将优化问题的可行解对应抗体，优化问题的目标函数对应抗原，Pareto最优解被保存在记忆细胞集中，并采取某种机制对记忆集进行不断更新，进而获得分布均匀的Pareto最优解。
（三）多目标PSO约束算法。
将粒子群优化算法运用于优化问题，关键是如何确定群体全局最优位置pbest和每个粒子的最优位置gbest。由于多目标优化问题并无单个的最优解，所以不能直接确定gbest，pbest。PSO算法的优势在于：第一，有着高效的搜索能力。第二，并行地同时搜索多个非劣解。第三，有着较好的通用性。PSO算法在处理多目标约束优化问题时，主要是解决自身和群体最佳位置，对于群体最佳位置的选择，一是所得到的解要在Pareto边界上具有一定得分散性，二是要求算法收敛速度好。对于自身最佳位置的选择要求是通过较少的比较次数达到非劣解的更新。PSO算法在处理约束时，多采用惩罚函数法。
（四）多目标蚁群算法。
多目标蚁群算法的思想是：根据目标函数的数目将蚂蚁分成若干子群体，为每个子群体分配一个目标函数，在其他子群体优化结果的基础上通过Pareto过滤器来获得均衡解。基本步骤如下：
1、转移概率：对每一个目标k需要考虑一些信息素轨迹 k，在算法的每一代中，每一只蚂蚁都计算一组权重p=（p1，p2，…，pk），并且同时使用启发式信息和信息素轨迹。
2、局部信息素更新：当每只蚂蚁走完aij边之后，对每个目标k我们采取更新：
ijk=（1- ） ijk+ 0
其中， 0是初始信息素的值， 是信息素挥发速率。
3、全局信息素更新：对每个目标k，在当前代只对产生最好和第二好的解进行信息素更新，使用规则如下：
ijk=（1- ） ijk+ △ ijk
4、设置Pareto解集过滤器：
设置Pareto解集过滤器来存放算法运行时产生的Pareto解。
三、结论
四种进化算的优缺点总结如下：
多目标遗传算法：有着良好的鲁棒性和优越性，在拥挤选择算子时，限制种群大小使用拥挤比较过程，使算法失去了收敛性。人工免疫系统：可以得到优化问题的多个Pareto最优解，算法运行缺乏稳定性。多目标PSO约束算法：能够实现对多维复杂空间的高效搜索，研究还处于起步阶段。多目标蚁群算法：Pareto前沿均匀性以及Pareto解集多样性，早熟停滞和在控制参数难以确定。□
（作者单位： 四川大学商学院）
参考文献：
[1]马小姝.传统多目标优化方法和多目标遗传算法的比较综述[J].电气传动自动化 ，2010.
[2]谢涛， 陈火旺.多目标优化与决策问题的演化算法[J].中国工程科学，2002.
[3]王鲁，罗婷，赵琳，段海峰.基于遗传算法的多目标优化技术[J].科技广场，2009.
[4]樊纪山， 王经卓.基于人工免疫系统的多目标优化算法的研究[J].福建电脑2008.
[5]池元成，蔡国飙.基于蚁群算法的多目标优化[J].计算机工程，2009.
[6]孔翔宇.基于蚁群算法的多目标优化问题研究[J]四川理工学院学报，2010.
[7]薛洪波， 伦淑娴.粒子群算法在多目标优化中的应用综述[J].渤海大学学报，2009.
[8]吴庆洪.粒子群优化算法及其应用综述[J].微计算机信息，2010.