优化搜索算法概述

“优化”是我们经常听到的一个词。简单而言，优化就是指通过实施一些我们可以控制的修改（设计变量）到关注的系统，从而使该系统的某些我们想要的指标变得更好（目标），同时另一些指标在我们可以接受的范围内（约束）。由于我们对所关注系统的认知有限，且影响系统性能的环境经常变化，我们无法直接确定具有最优性能的系统，从而需要使用优化搜索算法进行寻找。所以有句俗话是这样说的“万物皆可优，万物皆需优”，这里的“优”就是优化的意思。优化和设计经常同时出现，它们可以表达相同的意思，本文对他们不加区分（设计作为动词，与优化作用类似，而设计作为名词时则是指代一个确定的系统）。

根据需要优化的目标特性的数目，优化问题可以分为单目标优化和多目标优化；而根据是否需要使用设计变量关于目标特性的梯度信息可将优化设计方法分为两类：基于梯度的优化设计（Gradient-based Optimization）和无梯度优化设计（Gradient-free Optimization）。虽然梯度算法可以快速收敛到一个优于初始的解，但由于其局部搜索性，而不能保证得到全局最优。而且对于多目标优化问题，由于不同目标的梯度方向的不一致性，会给优化带来新的问题。所以基于梯度的优化方法不作为本文的讨论重点。基于启发式优化算法的无梯度优化设计可以更好地实现全局寻优，并能较好地处理多目标优化问题。由于基于梯度的优化搜索算法不具备全局寻优能力且不适合多目标优化，无梯度优化搜索算法得到了长足的关注和发展。目前使用较多的是元启发算法[1]（Metaheuristics Algorithm）。元启发算法具有以下特点：1）它们的优化原理是基于物理、生物或社会等行为的某些原则发展而来, 即自然启发（nature-inspired）；2）在优化过程中会用到随机变量，即随机性；3）不需要使用梯度信息；4）它们都有一些需要根据优化问题而指定的参数。元启发算法对目标函数没有特殊要求，可以用于求解各种复杂的优化问题。基于自然原则的寻优原理和随机性可以使算法具有较强的全局寻优能力。根据可以处理的优化问题目标个数，可以把元启发算法分为单目标优化算法和多目标优化算法。

常见的单目标元启发算法有模拟退火算法（Simulated Annealing，SA)[2]，遗传算法（Genetic Algorithm，GA）[3]，粒子群算法（Particle Swarm Optimization，PSO）[4]，协方差矩阵自适应进化策略(Covariance Matrix Adaptation Evolution Strategy，CMA-ES)[5]，差分进化算法（Differential Evolutionary，DE）[6]等。上述算法可以分为基于单个解和基于种群的算法。SA算法是基于单个解的算法，即在优化过程中算法只保留一个当前最优解，通过对这个解进行扰动产生新解，如果新解的目标函数优于当前最优解，则把新解作为当前最优解；否则，新解以一定的概率作为当前最优解，然后进入下一轮迭代。基于种群的算法在优化过程中保留一组解（种群），并通过对这组解的操作产生新的种群，通过循环迭代逐步改善种群的目标特性。这类算法可以分为进化算法和群智能算法。进化算法是基于达尔文的优胜劣汰、适者生存的生物进化机制，通过模拟生物的进化过程发展而来。常用的进化算法包括GA、CMA-ES和DE等，该类算法通过交叉和变异等算子由父代种群产生子代种群，并根据目标函数优劣对种群进行更新，进入下一轮迭代。群智能算法通过对自然界中昆虫、动物等群体的社会行为进行模拟，实现优化搜索。PSO算法是典型的群智能算法，它通过模拟鸟群的捕食行为发展而来。PSO算法使用粒子的局部最优位置和群的全局最优位置更新粒子，通过目标函数的优劣对局部和全局最优位置进行更新，进入下一轮迭代。对于常用的元启发单目标优化算法，它们往往包含需要使用者设定的参数。只有在这些参数值与要处理问题的特征吻合较好时，算法才能得到好的优化结果。但是对于工程优化问题，很难在优化之前对问题的特征有比较详尽的了解，从而为优化算法参数的设置造成了困难。因此，改善优化算法性能的鲁棒性，即不需要改变算法参数也可以对不同特征的优化问题得到较为满意的结果，很有必要。

多目标优化问题是指需要同时对不少于2个目标函数进行寻优的优化问题。通常，目标函数之间是相互矛盾的，即某一个目标性能的提升要以至少一个其他目标性能的降低为代价。对于这样的多目标优化问题，不存在一个可以对所有目标函数都同时取得最优的单一解，而是需要寻找一组被称为Pareto前缘[7]的解集。最简单直接的处理方法是把多个目标加权处理为一个目标，然后使用单目标优化算法处理。这种方法的优化结果严重依赖权系数的选择，而且随着目标个数增加，影响权系数选择的不确定性因素增多；另外，一组权系数只能给出一个优化结果，无法反映不同目标的相互影响。多目标进化算法（Multi-objective Evolutionary Algorithm，MOEA）是基于种群的优化算法，它可以通过一次运行得到对Pareto前缘近似的一组解。MOEA算法的目标是对整个Pareto前缘进行近似，得到一组多样性好且与Pareto前缘的距离尽量小的解集。MOEA在近些年得到了蓬勃的发展，常用的多目标优化算法有PAES[8]，SPEA2[9]，NSGA-II[10]，MOPSO[11]，MOEA/D[12]等。但是，多目标优化算法的性能也受其相应参数的影响，而选择适当的参数需要对优化问题的特征有一定的了解，这就为求解工程优化问题造成了困难。另一方面，传统的多目标优化算法是为了搜索得到一组对整个Pareto前缘近似较好的解集，提供给决策者（decision maker，DM）从中选择最符合其偏好的解作为最终方案，即DM感兴趣的往往只是Pareto前缘的某个部分，而不是整个Pareto前缘。于是传统寻找整个Pareto前缘的做法会得到较多DM不感兴趣的解，造成计算资源的浪费并增加DM的负担。如果可以结合DM的偏好，使优化搜索集中在DM感兴趣的Pareto前缘区域，可以提高计算资源的利用效率并有望得到更优的结果^[217]。