论文部分内容阅读
【摘要】优化问题一直都是工程实践和科学研究中的重要问题，本文详细介绍了常用几种优化算法，比较了各种算法的优缺点，也列举了组合算法在多个领域的应用实例，展望了组合算法的发展方向和可能面临的问题。
【关键词】多目标优化 进化算法 遗传算法 组合算法
中图分类号：TP18
1引言
大多数多目标优化问题，每个目标函数之间可能是竞争的关系，优化某一个函数的同时，往往以牺牲另一个优化目标为代价，如果将多目标转化为单目标函数优化时，各优化目标加权值的分配带有很大的主观性，必然造成优化结果的单一性，没有考虑全局优化。而如果将多目标函数利用评价函数法转化为单目标函数求解，得到的仅仅是一个有效解，所以我们可以考虑直接采用多目标函数的优化方法对多目标进行优化[1-2]。
2多目标优化的发展现状
在多目标优化问题中，各分目标函数的最优解往往是互相独立的，很难同时实现最优。在分目标函数之间甚至还会出现完全对立的情况，即某一个分目标函数的最优解却是另一个分目标函数的劣解。求解多目标优化问题的关键，是要在决策空间中寻求一个最优解的集合，需要在各分目标函数的最优解之间进行协调和权衡，以使各分目标函数尽可能达到近似最优。多目标优化问题不存在唯一的全局最优解，而是要寻找一个最终解。得到最终解需要通过各种算法来实现，如进化算法、模拟退火算法、蚁群算法、粒子群算法和遗传算法等[3-4]。由于各种算法存在应用领域的差异和自身缺陷，人们也提出了一些改进算法和组合算法。
2.1进化算法
进化算法 （Evolutionary Algorithms，EA）是一种仿生优化算法，主要包括遗传算法、进化规划、遗传规划和进化策略等。根据达尔文的“优胜劣汰、适者生存”的进化原理及盂德尔等人的遗传变异理论，在优化过程中模拟自然界的生物进化过程与机制，求解优化与搜索问题。进化算法具有自组织、自适应、人工智能、高度的非线性、可并行性等优点[5]。
进化算法在求解多目标优化问题上优势在于：一是搜索的多向性和全局性，通过重组操作充分利用解之间的相似性，能够在一次运行中获取多个Pareto最优解，构成近似问题的Pareto最优解集；二是可以处理所有类型的目标函数和约束。三是采用基于种群的方式组织搜索、遗传操作和优胜劣汰的选择机制，不受其搜索空间条件的限制。
虽然基于Pareto最优解的多目标进化算法可以得到较好分布的最优解集，但如何保证算法具有良好的收敛性仍是一个热点问题。
2.2模拟退火算法
模拟退火（Simulated Annealing，SA）算法是根据物理中固体物质的退火过程与一般组合优化问题之间的相似性，基于Monte-Carlo迭代求解策略的一种随机寻优算法。SA在初始温度下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。SA具有以下优点：通用性强，对问题信息依赖较少，可有效避免陷入局部極小并最终趋于全局最优。因此在诸多工程和学术领域得到了研究与应用[6-7]。遗憾的是它在多目标优化领域的研究与应用尚少。
2.3蚁群算法
蚁群算法（Ant Colony Optimization， ACO）是一种用来在图中寻找优化路径的正反口的新型模拟进化算法。。蚁群算法具有并行性、分布性、正反馈性、自组织性、较强的鲁棒性和全局搜索能力等特点。目前运用这种方法已成功地解决了旅行商（TSP）问题、Job-shop调度问题、二次指派问题等组合优化问题。
由于蚁群算法需要的参数数目少，设置简单，在求解多目标优化问题时存在一些困难。首先，多目标函数优化问题是在连续空间中进行寻优，解空间以区域表示，蚂蚁在每一阶段可选的路径不再是有限的，蚂蚁在信息索的驻留和基于信息素的寻优上存在困难。文献[8]提出先使用遗传算法对解空间进行全局搜索，再运用蚁群算法对得到的结果进行局部优化；文献[9]修改了蚂蚁信息素的留存方式和行走规则，运用信息素交流和直接通讯两种方式来指导蚂蚁寻优；文献[10]将搜索空间划分为若干子域，根据信息量确定解所在的子域，在该子域内寻找解，也取得了满意的结果。
其次，蚂蚁算法需要较长的搜索时间、容易出现早熟停滞现象。文献[11]提出了具有免疫能力的蚂蚁算法和蚁群遗传算法，提高算法的寻优能力和寻优效率。
最后，多目标优化问题由于解的多样性，不仅要求所得的解能够收敛到Pareto前沿，而且要有效地保持群体的多样性。蚂蚁之间的这种信息素交流方式，会使所求得的解集中在解空间的某一区域内，不利于群体多样性的保持。
2.4粒子群算法
粒子群优化算法（Particle Swarm Optimization，PSO）是在1995年由美国社会心理学家Kennedy和电气工程师Eberhart共同提出的，源于对鸟群觅食过程中的迁徙和聚集的模拟。它收敛速度快、易于实现且仅有少量参数需要调整，目前已经被广泛应用于目标函数优化、动态环境优化、神经网络训练等许多领域。
由于直接用粒子群算法处理多目标优化问题，很容易收敛于非劣最优域的局部区域，以及如何保证算法的分布性等问题，Coello等人提出了基于Pareto的多目标粒子群算法（MOPS0），强调了粒子和种群之间作用的重要性[12]。
多目标粒子群优化算法作为一种新兴的多目标优化算法具有以下优点：（1）在编码方式上PSO算法比较简单，可以直接根据被优化问题进行实数编码；（2）对种群的初始化不敏感，可达到较快的收敛速度；（3）算法适用于绝大多数的多目标优化问题；（4）优化过程中，每个粒子通过自身经验与群体经验进行更新，具有学习和记忆的功能；（5）该算法在收敛性、解的分布性以及计算效率方面具有很大改善。 2.5遗传算法
遗传算法（Genetic Algorithm，GA）是进化算法的一种，是美国密执安大学的John Holland教授于七十年代中期首先提出来的，从生物进化的过程中得到灵感与启迪，模拟人自然“物竟天择，适者生存”的自然选择的法则创立的。
与其他优化算法相比，遗传算法求解多目标优化问题的主要优点：一是保证算法的收敛性，即在目标空间内，所求得的Pareto最优解集与实际Pareto尽可能的接近。二是多样性的维护，即希望找到的Pareto最优解集具有较好的分布特性（如均匀分布），且分布范围尽可能的宽阔。三是具有很好的鲁棒性，是一种高度并行、随机、自适应能力很强的智能搜索算法，因此特别适合于处理传统搜索算法解决不好的复杂非线性问题。四是新的遗传算法引入精英概念，使进化的每一代的Pareto最優解总是直接保留到下一代的群体中，提高了Pareto最优解的搜索效率。五是引入用户的偏好信息，以交互的方式表达偏好，使用决策者的偏好信息来指导算法的搜索过程和范围[13-14]。
3多目标优化研究的热点问题
多目标优化问题中，各个目标之间通过决策变量相互制约，对其中一个目标优化必须以其他目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。传统优化方法往往强调最优化，在解决因多种复杂因素难以建模，或根本不存在传统意义上的最优解或获得最优解的代价太大的优化问题时。由此，采用满意优化方法解决这类问题是较好的策略。满意优化本质上是一个多目标优化方法，它摒弃了传统的最优概念，它将优化问题的约束和目标融为一体，将性能指标要求的满意设计与参数优化融为一体，强调的是“满意”而不“最优”。所以，近年来，满意优化也逐渐成为各领域关心的问题。
4结束语
多目标优化问题是近年来人们越来越需要面对和解决的问题。除了以上单一优化算法外，很多学者已经在单一优化算法的基础上，结合多种优化算法解决了一些多目标优化问题，如NSGA-Ⅱ与MOPSP的结合算法[15]，模拟退火算法与遗传算法的结合算法[16]。然而，由于各种多目标优化算法的不同特点和缺陷，如何使这些优化算法能够更好地无缝对接，对解决多目标满意优化问题具有非常重要的意义。
参考文献
[1]玄光男，程润伟著.周根贵译.遗传算法与工程优化，清华大学出版社，2004.
[2] Liu Zhen Yu .Multi-objective optimization design analysis of primary surface recuperator for microturbines[J].Applied Thermal Engineering 28（2008）：601～610.
[3]肖晓伟等.多目标优化问题的研究概述.计算机应用研究，2011（03）
[4] Kalyanmoy Deb，Amrit Pratap，T Meyarivan.A fast and elitist multi-objective genetic 2002.6（2）：182～197.algorithm： NSGA-II [J].IEEE Transactions on Evolutionary Computation.
[5]杨海清.进化算法的改进及其应用研究.浙江工业大学硕士论文，2004.
[6]邓俊等.基于神经网络和模拟退火算法的配煤智能优化方法[J].冶金自动化，2007（3）.
[7]韩强.多目标应急设施选址问题的模拟退火算法[J].计算机工程与应用 ，2007（30）.
[8]陈峻等.蚁群算法求解连续空间优化问题的一种方法[J].软件学报 2002，13（12）.
[9]Dorigo M，Gambardella L M. Ant colony system： a cooperative learning approach to the traveling salesman problem[J].IEEE Trans. Evolutionary Computation，1997，1（1）：53-56.
[10]张德勇，黄莎白.多目标优化问题的蚁群算法研究[J].控制与决策 2005，20（2）
[11]毛宁.具有免疫能力的蚂蚁算法研究（硕士学位论文） 河北工业大学.2006
[12]张慧敏.改进的粒子群计算智能算法及其多目标优化的应用研究（硕士学位论文）.
杭州大学.2005.
[13]李金娟.遗传算法及应用的研究[J].电脑与信息技术，2013（02）.
[14]洪朝飞等.面向机械设计的一种改进的遗传算法.太原科技大学学报，2013（02）.
[15]王金华等.基于NSGA-Ⅱ与MOPSP融合的一种多目标优化算法[J].
计算机应用.2007（11）
[16]周明等.基于遗传模拟退火算法的机器人路径规划.航空学报 1998
【关键词】多目标优化 进化算法 遗传算法 组合算法
中图分类号：TP18
1引言
大多数多目标优化问题，每个目标函数之间可能是竞争的关系，优化某一个函数的同时，往往以牺牲另一个优化目标为代价，如果将多目标转化为单目标函数优化时，各优化目标加权值的分配带有很大的主观性，必然造成优化结果的单一性，没有考虑全局优化。而如果将多目标函数利用评价函数法转化为单目标函数求解，得到的仅仅是一个有效解，所以我们可以考虑直接采用多目标函数的优化方法对多目标进行优化[1-2]。
2多目标优化的发展现状
在多目标优化问题中，各分目标函数的最优解往往是互相独立的，很难同时实现最优。在分目标函数之间甚至还会出现完全对立的情况，即某一个分目标函数的最优解却是另一个分目标函数的劣解。求解多目标优化问题的关键，是要在决策空间中寻求一个最优解的集合，需要在各分目标函数的最优解之间进行协调和权衡，以使各分目标函数尽可能达到近似最优。多目标优化问题不存在唯一的全局最优解，而是要寻找一个最终解。得到最终解需要通过各种算法来实现，如进化算法、模拟退火算法、蚁群算法、粒子群算法和遗传算法等[3-4]。由于各种算法存在应用领域的差异和自身缺陷，人们也提出了一些改进算法和组合算法。
2.1进化算法
进化算法 （Evolutionary Algorithms，EA）是一种仿生优化算法，主要包括遗传算法、进化规划、遗传规划和进化策略等。根据达尔文的“优胜劣汰、适者生存”的进化原理及盂德尔等人的遗传变异理论，在优化过程中模拟自然界的生物进化过程与机制，求解优化与搜索问题。进化算法具有自组织、自适应、人工智能、高度的非线性、可并行性等优点[5]。
进化算法在求解多目标优化问题上优势在于：一是搜索的多向性和全局性，通过重组操作充分利用解之间的相似性，能够在一次运行中获取多个Pareto最优解，构成近似问题的Pareto最优解集；二是可以处理所有类型的目标函数和约束。三是采用基于种群的方式组织搜索、遗传操作和优胜劣汰的选择机制，不受其搜索空间条件的限制。
虽然基于Pareto最优解的多目标进化算法可以得到较好分布的最优解集，但如何保证算法具有良好的收敛性仍是一个热点问题。
2.2模拟退火算法
模拟退火（Simulated Annealing，SA）算法是根据物理中固体物质的退火过程与一般组合优化问题之间的相似性，基于Monte-Carlo迭代求解策略的一种随机寻优算法。SA在初始温度下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。SA具有以下优点：通用性强，对问题信息依赖较少，可有效避免陷入局部極小并最终趋于全局最优。因此在诸多工程和学术领域得到了研究与应用[6-7]。遗憾的是它在多目标优化领域的研究与应用尚少。
2.3蚁群算法
蚁群算法（Ant Colony Optimization， ACO）是一种用来在图中寻找优化路径的正反口的新型模拟进化算法。。蚁群算法具有并行性、分布性、正反馈性、自组织性、较强的鲁棒性和全局搜索能力等特点。目前运用这种方法已成功地解决了旅行商（TSP）问题、Job-shop调度问题、二次指派问题等组合优化问题。
由于蚁群算法需要的参数数目少，设置简单，在求解多目标优化问题时存在一些困难。首先，多目标函数优化问题是在连续空间中进行寻优，解空间以区域表示，蚂蚁在每一阶段可选的路径不再是有限的，蚂蚁在信息索的驻留和基于信息素的寻优上存在困难。文献[8]提出先使用遗传算法对解空间进行全局搜索，再运用蚁群算法对得到的结果进行局部优化；文献[9]修改了蚂蚁信息素的留存方式和行走规则，运用信息素交流和直接通讯两种方式来指导蚂蚁寻优；文献[10]将搜索空间划分为若干子域，根据信息量确定解所在的子域，在该子域内寻找解，也取得了满意的结果。
其次，蚂蚁算法需要较长的搜索时间、容易出现早熟停滞现象。文献[11]提出了具有免疫能力的蚂蚁算法和蚁群遗传算法，提高算法的寻优能力和寻优效率。
最后，多目标优化问题由于解的多样性，不仅要求所得的解能够收敛到Pareto前沿，而且要有效地保持群体的多样性。蚂蚁之间的这种信息素交流方式，会使所求得的解集中在解空间的某一区域内，不利于群体多样性的保持。
2.4粒子群算法
粒子群优化算法（Particle Swarm Optimization，PSO）是在1995年由美国社会心理学家Kennedy和电气工程师Eberhart共同提出的，源于对鸟群觅食过程中的迁徙和聚集的模拟。它收敛速度快、易于实现且仅有少量参数需要调整，目前已经被广泛应用于目标函数优化、动态环境优化、神经网络训练等许多领域。
由于直接用粒子群算法处理多目标优化问题，很容易收敛于非劣最优域的局部区域，以及如何保证算法的分布性等问题，Coello等人提出了基于Pareto的多目标粒子群算法（MOPS0），强调了粒子和种群之间作用的重要性[12]。
多目标粒子群优化算法作为一种新兴的多目标优化算法具有以下优点：（1）在编码方式上PSO算法比较简单，可以直接根据被优化问题进行实数编码；（2）对种群的初始化不敏感，可达到较快的收敛速度；（3）算法适用于绝大多数的多目标优化问题；（4）优化过程中，每个粒子通过自身经验与群体经验进行更新，具有学习和记忆的功能；（5）该算法在收敛性、解的分布性以及计算效率方面具有很大改善。 2.5遗传算法
遗传算法（Genetic Algorithm，GA）是进化算法的一种，是美国密执安大学的John Holland教授于七十年代中期首先提出来的，从生物进化的过程中得到灵感与启迪，模拟人自然“物竟天择，适者生存”的自然选择的法则创立的。
与其他优化算法相比，遗传算法求解多目标优化问题的主要优点：一是保证算法的收敛性，即在目标空间内，所求得的Pareto最优解集与实际Pareto尽可能的接近。二是多样性的维护，即希望找到的Pareto最优解集具有较好的分布特性（如均匀分布），且分布范围尽可能的宽阔。三是具有很好的鲁棒性，是一种高度并行、随机、自适应能力很强的智能搜索算法，因此特别适合于处理传统搜索算法解决不好的复杂非线性问题。四是新的遗传算法引入精英概念，使进化的每一代的Pareto最優解总是直接保留到下一代的群体中，提高了Pareto最优解的搜索效率。五是引入用户的偏好信息，以交互的方式表达偏好，使用决策者的偏好信息来指导算法的搜索过程和范围[13-14]。
3多目标优化研究的热点问题
多目标优化问题中，各个目标之间通过决策变量相互制约，对其中一个目标优化必须以其他目标作为代价，而且各目标的单位又往往不一致，因此很难客观地评价多目标问题解的优劣性。传统优化方法往往强调最优化，在解决因多种复杂因素难以建模，或根本不存在传统意义上的最优解或获得最优解的代价太大的优化问题时。由此，采用满意优化方法解决这类问题是较好的策略。满意优化本质上是一个多目标优化方法，它摒弃了传统的最优概念，它将优化问题的约束和目标融为一体，将性能指标要求的满意设计与参数优化融为一体，强调的是“满意”而不“最优”。所以，近年来，满意优化也逐渐成为各领域关心的问题。
4结束语
多目标优化问题是近年来人们越来越需要面对和解决的问题。除了以上单一优化算法外，很多学者已经在单一优化算法的基础上，结合多种优化算法解决了一些多目标优化问题，如NSGA-Ⅱ与MOPSP的结合算法[15]，模拟退火算法与遗传算法的结合算法[16]。然而，由于各种多目标优化算法的不同特点和缺陷，如何使这些优化算法能够更好地无缝对接，对解决多目标满意优化问题具有非常重要的意义。
参考文献
[1]玄光男，程润伟著.周根贵译.遗传算法与工程优化，清华大学出版社，2004.
[2] Liu Zhen Yu .Multi-objective optimization design analysis of primary surface recuperator for microturbines[J].Applied Thermal Engineering 28（2008）：601～610.
[3]肖晓伟等.多目标优化问题的研究概述.计算机应用研究，2011（03）
[4] Kalyanmoy Deb，Amrit Pratap，T Meyarivan.A fast and elitist multi-objective genetic 2002.6（2）：182～197.algorithm： NSGA-II [J].IEEE Transactions on Evolutionary Computation.
[5]杨海清.进化算法的改进及其应用研究.浙江工业大学硕士论文，2004.
[6]邓俊等.基于神经网络和模拟退火算法的配煤智能优化方法[J].冶金自动化，2007（3）.
[7]韩强.多目标应急设施选址问题的模拟退火算法[J].计算机工程与应用 ，2007（30）.
[8]陈峻等.蚁群算法求解连续空间优化问题的一种方法[J].软件学报 2002，13（12）.
[9]Dorigo M，Gambardella L M. Ant colony system： a cooperative learning approach to the traveling salesman problem[J].IEEE Trans. Evolutionary Computation，1997，1（1）：53-56.
[10]张德勇，黄莎白.多目标优化问题的蚁群算法研究[J].控制与决策 2005，20（2）
[11]毛宁.具有免疫能力的蚂蚁算法研究（硕士学位论文） 河北工业大学.2006
[12]张慧敏.改进的粒子群计算智能算法及其多目标优化的应用研究（硕士学位论文）.
杭州大学.2005.
[13]李金娟.遗传算法及应用的研究[J].电脑与信息技术，2013（02）.
[14]洪朝飞等.面向机械设计的一种改进的遗传算法.太原科技大学学报，2013（02）.
[15]王金华等.基于NSGA-Ⅱ与MOPSP融合的一种多目标优化算法[J].
计算机应用.2007（11）
[16]周明等.基于遗传模拟退火算法的机器人路径规划.航空学报 1998