优化算法及其分类

所谓优化算法，其实就是一种搜索过程或规则，根据现有优化问题的特点，利用某种思想或机制，按照相应的某种途径和方法来得到满足现实要求的问题的解。现有的优化算法大致可以分为以下几类：

（1）经典算法：包括线性规划、动态规划、整数规划和分支定界等传统算法。它们对目标函数的解析性质要求较高，而且计算复杂性一般很大，所以只适应于求解小规模的简单问题，在工程中往往不能广泛应用。

（2）构造型算法：通过对问题的分析，希望用构造的方法快速建立问题的解。通常这样的算法不是很有效，对于庞大复杂的问题，很难满足需要。比如调度问题中的典型构造方法有：Johnson法、Gupta法、CDS法、Palmer法、Daunenbring的快速接近法等。

（3）基于系统动态演化的方法：将优化的过程转换为系统动态的演化过程，如神经网络和混沌搜索等。

（4）改进型算法：这种算法从任意解出发，通过对其邻域的不断搜索，用得到的更好解来替换当前找到的最好解，层层迭代，不断提高当前最好解的质量，从而达到全局最优。代表性的方法有进化算法及归于其中的遗传算法等。

（5）混合型算法：指根据不同问题的具体需要，利用上述各种算法的优点，克服其弊端，从结构或操作上混合而产生的各种算法。实践证明这种方法往往是快捷有效的。

1.求解无约束优化问题的算法

现有的众多算法大致可分为确定性方法和随机方法两类：确定性算法往往对目标函数的解析性质要求比较高，要用到目标函数的梯度信息或者高维导数信息，代表性的方法如Levy的隧道法［125］和R.Ge的填充函数法［126］以及Brianin的下降轨线法等：

（1）隧道算法。隧道算法的思想是从当前最好点出发，通过在该点建立一个隧道函数，希望能打通一条隧道，从而进入另一个深谷里，找到相应的具有下降方向的点，再通过局部搜索，找到新的深谷里的局部最小点，这样层层迭代，直到全局最优。其思想可以通过下面图形形象地表示，如图1.1所示。

图1.1　一元函数隧道方法示意图

（2）填充函数法。填充函数法也是基于当前最好点，根据该点建立一个相应的辅助函数，该函数能够填平当前最好点所在的深谷，帮助搜索跳出局部极小，转移到一个“地势更低的深谷”，获取该深谷的一个点，从该点重新搜索，希望能找到比当前点更好的点。该方法的关键在于如何去建立一个合适的填充函数。

随机性方法对目标函数要求低，稳定性好，但收敛速度慢。代表性的方法有遗传算法、Monte－Carlo随机试验法、模拟退火法（simulated annealing）等：

（1）Monte－Carlo随机试验法。Monte－Carlo随机试验法是按均匀分布在搜索空间随机产生大量的试验点，然后找出其在可行域中最好点作为最优解的一种随机近似方法。

（2）模拟退火法：模拟退火法（simulated annealing）是基于固体冷却过程和一般组合优化问题之间相似的特点而产生的一种优化算法。固体物质退火的物理模型与随机过程的理论结合形成了模拟退火法的基本思想。事实证明，对离散变量的组合优化问题和连续变量函数的极小化问题模拟退火算法都是有效可行的。模拟退火法求解极小化问题的基本步骤［127］为：

①定义极小化的目标函数F（x）。

②给定初始解x0和初始温度θ0＞0。

③循环直到满足结束条件：

i）循环L次。任选一个x的邻近值x′，求出Δ＝F（x′）－F（x）。

如果Δ≤0，则x＝x′；

如果Δ＞0，则x＝x′的概率是exp（－Δ／C）。

ii）令Ck＋1＝rCk，（0＜r＜1，即降低温度）。

④输出最终解x。

2.求解约束优化问题的算法

约束优化问题的求解方法众多，最常见最基本的是罚函数法。它把约束优化问题转化为无约束优化问题，再用无约束问题的方法去解。和众多的方法相比较，罚函数法是一种相当有效、成功率较高的方法。另有一些是改进无约束优化问题的方法，通过对处理无约束优化问题的方法的改进，使之能用于约束优化的情况。下面对几种方法进行简单介绍。

（1）基于罚函数的方法

静态罚函数法［128］：考虑如下非线性规划问题

（2）基于搜索容许解的方法

如行为记忆法［130］：该方法逐步处理约束，每次处理一个，使得种群中满足该约束的个体达到预先规定的比例，如在处理第j个约束的时候，要保持前j－1个约束均满足，这样使得最后种群中有足够多的可行解。相关的方法还有容许点优先法等。

（3）混合方法

基于各种处理约束问题的方法，涌现出大量的混合算法，代表性的有把进化算法与其他传统方法结合。1979年，Jan Paredis提出了协同进化算法（Coevolutionary Genetic Algorithm，CGA）解决一般的约束满足问题，其中一个种群由问题的解组成，称为解种群（solution population）；另一个种群由约束组成，称为测试种群（test population）。这两个种群协同进化，种群间的相互作用通过适应度评价来实现。作为一种混合方法，协同进化算法是一种有效的优化算法。