约束优化(Constrained Optimization),即
约束优化问题,是优化问题的分支。它是在一系列约束条件下,寻找一组参数值,使某个或某一组函数的目标值达到最优。其中
约束条件既可以是等式约束也可以是不等式约束。寻找这一组参数值的关键可是:满足约束条件和目标值要达到最优。求解约束问题的方法可分为传统方法和进化算法。
定义
其中 x 是决策变量,f( x )是目标函数,是不等式约束,是等式约束,D={|}是搜索空间, D中所有满足约束条件的解构成可行域S,即 S={x|},可行域中的点称为可行解。对于不等式约束,若在 x 点处满足,则称在x点处是积极约束。等式约束在所有可行解处是积极约束。
若对某一,存在常数,使得对{x| },有,则称为局部最优解;若对一切都有,则称为全局最优解。求解
最优化问题NLP,就是要求目标函数f(x)在约束条件下的极小点,即求出其全局最优解,但在一般情况下,往往只能求出它的一个局部最优解。
当f(x)为线性函数时称为线性规划问题,反之如果是非线性则为非线性规划问题。当约束问题包含一个目标函数时,称为单目标约束优化问题;当约束问题包含多个目标函数时,称为多目标
约束优化问题。
传统方法
传统方法的实现如
牛顿法、
梯度法等,其基本思想就是将动态的转化为静态的,将多目标转化为单目标,由点及面的搜索思想。
传统方法存在如下问题:
(1) 传统的基于梯度的优化方法(如可行方向法、约束变尺度法)对约束条件的处理往往是先寻找一个可行且下降的方向,然后沿此方向进行线性搜索,并重复上述步骤以得到问题的最优解,然而该最优解往往是局部最优的。
(2) 对于许多实际的
约束优化问题,一方面,由于目标函数往往形式复杂,不仅问题的维数比较高,而且优化曲面中存在多个极小点,这使得传统的基于梯度的算法难以奏效。另一方面,实际问题中目标函数往往是不连续或不可微,有些问题目标函数甚至没有解析表达式,传统算法难以解决这类问题。
(3) 由于约束的存在,使得决策变量的可行搜索空间不规则(如非凸,不连通等),从而增加了搜索到最优解的难度,有时甚至很难找到可行解。
进化算法
简介
进化算法是一种智能的全局优化方法,它对函数本身性质要求非常低,往往只要求目标函数值是可以计算的,不要求它具有连续性、可微性及其它解析性质,同时它又是基于群体进化的算法,因此可采用进化算法解决
约束优化问题。用进化算法解决约束优化问题的关键在于如何进行有效的约束处理,即如何有效均衡在可行区域与不可行区域的搜索。
常见的用于求解约束优化问题的进化算法有
罚函数法、
遗传算法、
进化策略、进化规划、
蚁群算法和
粒子群算法等。
与传统方法相比的优势
(1) 在一般情况下,进化算法能否收敛到全局最优解与初始群体无关,而传统优化方法则依赖于初始解;
(2) 进化算法具有全局搜索能力,而很多传统优化方法往往会陷入局部最优;
(3) 进化算法的适用范围广,能有效地解决不同类型的问题,而传统优化方法在设计时往往就只能解诀某一类型的问题。
存在的不足
(1) 进化算法中的参数,如群体规模、进化代数、重组概率、变异概率等,往往需要根据经验设定,且在一定程度上与问题相关;
(2) 进化算法的收敛问题,进化算法求解实际问题时的收敛性判定缺乏理论指导。