[科普中国]-约束优化

不失一般性，约束优化问题可以描述为如下形式：

其中 x 是决策变量，f( x )是目标函数，是不等式约束，是等式约束，D={|}是搜索空间， D中所有满足约束条件的解构成可行域S，即 S={x|}，可行域中的点称为可行解。对于不等式约束，若在 x 点处满足，则称在x点处是积极约束。等式约束在所有可行解处是积极约束。1

若对某一，存在常数，使得对{x| }，有，则称为局部最优解；若对一切都有，则称为全局最优解。求解最优化问题NLP，就是要求目标函数f(x)在约束条件下的极小点，即求出其全局最优解，但在一般情况下，往往只能求出它的一个局部最优解。2

当f(x)为线性函数时称为线性规划问题，反之如果是非线性则为非线性规划问题。当约束问题包含一个目标函数时，称为单目标约束优化问题；当约束问题包含多个目标函数时，称为多目标约束优化问题。3

传统方法的实现如牛顿法、梯度法等，其基本思想就是将动态的转化为静态的，将多目标转化为单目标，由点及面的搜索思想。3

传统方法存在如下问题：

(1) 传统的基于梯度的优化方法(如可行方向法、约束变尺度法)对约束条件的处理往往是先寻找一个可行且下降的方向，然后沿此方向进行线性搜索，并重复上述步骤以得到问题的最优解，然而该最优解往往是局部最优的。

(2) 对于许多实际的约束优化问题，一方面，由于目标函数往往形式复杂，不仅问题的维数比较高，而且优化曲面中存在多个极小点，这使得传统的基于梯度的算法难以奏效。另一方面，实际问题中目标函数往往是不连续或不可微，有些问题目标函数甚至没有解析表达式，传统算法难以解决这类问题。

(3) 由于约束的存在，使得决策变量的可行搜索空间不规则(如非凸，不连通等)，从而增加了搜索到最优解的难度，有时甚至很难找到可行解。1

进化算法是一种智能的全局优化方法，它对函数本身性质要求非常低，往往只要求目标函数值是可以计算的，不要求它具有连续性、可微性及其它解析性质，同时它又是基于群体进化的算法，因此可采用进化算法解决约束优化问题。用进化算法解决约束优化问题的关键在于如何进行有效的约束处理，即如何有效均衡在可行区域与不可行区域的搜索。

常见的用于求解约束优化问题的进化算法有罚函数法、遗传算法、进化策略、进化规划、蚁群算法和粒子群算法等。

(1) 在一般情况下，进化算法能否收敛到全局最优解与初始群体无关，而传统优化方法则依赖于初始解；

(2) 进化算法具有全局搜索能力，而很多传统优化方法往往会陷入局部最优；

(3) 进化算法的适用范围广，能有效地解决不同类型的问题，而传统优化方法在设计时往往就只能解诀某一类型的问题。

(1) 进化算法中的参数，如群体规模、进化代数、重组概率、变异概率等，往往需要根据经验设定，且在一定程度上与问题相关；

(2) 进化算法的收敛问题，进化算法求解实际问题时的收敛性判定缺乏理论指导。4