论文摘要
多目标优化问题的理论和求解方法在诸如经济、管理、工程等领域有着很强的应用价值。现如今,多目标优化的应用越来越广。多目标优化问题大都是NP-难的,因此,寻求该问题的高效算法一直备受瞩目。针对Pareto局部搜索（PLS）算法在解决多目标组合优化问题中所得到的解集与初始点的选取有关,本文提出该算法的改进,即PLSⅠ算法与PLSⅡ算法。改进算法同样利用Pareto占优的思想求解多目标组合优化问题,即从任意初始解开始进行PLS搜索产生一组改进解集VF,然后对VF中的所有解再进行PLS搜索,如此重复直到满足终止条件。与PLS算法比较,PLS I算法和PLSⅡ算法采用了并行局部搜索,扩大了搜索的范围,使算法在解决问题时不再完全依赖初始解。PLSⅠ算法的时间复杂度为O（|N（S）∪VT∩VF|2）,算法能得到比PLS算法更大的一个Pareto局部最优解集。而PLS Ⅱ算法最终能得到比PLS Ⅰ算法更大的Pareto局部最优解集。实例计算表明,改进算法能得到很好的解且解的质量优于PLS算法。为找双目标连续优化问题的一个Pareto最优解,本文构造了Pareto局部搜索算法,研究了双目标优化问题下降方向与梯度之间的关系,以及步长的选择。其次,构造了问题（P）的辅助函数T（x,k,p）。研究表明：当p足够大时,辅助函数T（x,k,p）与问题（P）有相同的Pareto最优解；当辅助函数T（x,k,P）陷入Pareto局部最优解时,可以通过增加k的值跳出Pareto局部最优解。最后,给出了基于辅助函数的局部搜索算法,并证明了该算法是渐进收敛的。