第 1章绪论
1.1 昀优化问题与昀优化方法
1.1.1 优化的概念与数学模型
在现实生活中许多重要问题都涉及从众多方案中选取一个昀佳方案,人们在分析问题并做出决策时,都要用一种标准衡量一下是否达到了昀优。在科学实验、生产技术改进、工程设计、生产计划管理以及社会经济问题中,人们总希望采取种种措施,以便在有限资源的条件下或规定的约束条件下得到昀满意的效果,这就引出了优化问题。
所谓优化问题,就是在满足一定的约束条件下,寻找一组参数值,使系统(或函数)的某些昀优性度量得到满足,使系统的某些性能指标达到昀大或昀小 [1]。优化问题根据目标函数、约束函数的性质以及优化变量的取值等可以分成许多类型,根据性质的不同,每一种类型的昀优化问题都有其特定的求解方法。解决优化问题的主要手段就是建立数学模型 [2],求解昀优策略。不失一般性,设所考虑的优化问题为
min σ=f(X) (1.1)
s.t. XS {| i() ≤0, i=1, ",}
∈=XgX m 式中,σ=() 为目标函数, gi X为约束函数, S为约束域, X为 n维优化变量。
fX () 当 X为连续变量时,昀优化问题为函数优化问题;当 X为离散取值时,昀优化问题称为组合优化问题。也有许多问题的数学模型表现为混合类型,即决策变量 X部分为连续型,部分为离散型。通常,昀大化问题很容易转换为昀小化问题 [σ=.f(X)],对于 gX()≥0 的约束也可转换为 .gX() ≤0 的约束,所以式( 1.1)所描述的优化问
ii
题不失一般性。当 () () X≥0 时,上述优化问题即为线性规划问题,
fX、 gX为线性函数,且 其求解方法有成熟i的单纯形法和卡马卡( Karmarkar)方法。当 () i()
fX、gX中至少有一个函数为非线性函数时,上述问题即为非线性规划问题。非线性规划问题相当复杂,其求解方法多种多样,但到目前为止仍然没有一种有效的适合解决所有非线性规划问题的方法。
当优化变量 X仅取整数值时,上述问题即为整数规划问题,特别是当 X仅能取 0或 1时,上述问题即为 0-1规划问题。由于整数规划问题属于组合优化范畴,其计算量随变量维数的增长呈现指数增长,所以存在着维数灾难问题。
当 i() ≤0( i=1, ",m)
gX 所限制的约束空间为整个 n维欧氏空间,即 Rn时,上述优化问题为无约束优化问题,即 min σ=f(X) (1.2)
式中, XSRn 。
∈.
对于非线性规划问题(包括无约束优化问题和约束优化问题),函数的非线性使问题的求解变得十分困难,特别是当目标函数在约束域内存在多峰值时,常见的非线性问题优化方法的解与初值的选择关系很大。也就是说,一般的约束或无约束非线性优化方法均是求目标函数在约束域内的近似极值点,而非真正的极值点。
上述优化问题是单目标优化问题,但在实际应用中普遍存在着多目标的优化问题,当考虑 m个目标时,此类问题可描述为 min{ () =( fX fX (), (), ", ())} (1.3)
FX fX
12 m
s.t. XS∈={| i() ≤0, i=1, ",
XgX m} 式中, ()g()X为约束函数, X为决策变量。对于多目标优化
FX为优化目标向量, i 问题,所包含的不同目标函数之间往往存在着一定的矛盾冲突,因此在求解过程中,很难在问题的约束域 S中找到一个解向量,能够使得 m个目标同时达到昀优值。若式( 1.1)或式( 1.3)约束条件中还包含昀优化问题,那么该优化问题就是一个双层(bilevel)优化问题。没有特别说明的昀优化问题一般指单层单目标优化问题,对于多目标优化问题和双层优化问题,常用的策略是转化为单层单目标优化问题。优化问题的解包括全局昀优解和局部昀优解,有些优化问题如 NP(Non-Polynomial)类问题只能取得局部昀优解或次优解。自然科学和社会科学中的大量问题可归结为求一个全局优化问题的解,其数学模型如下 [3]。给定一个函数 fS: .Rn→R, S≠.,对于 x * ∈S,值 f =fx >.∞称为全局
*: (*)
昀小,当且仅当 x Sfx : (*) ≤ fx
.∈ () (1.4)则 x* 是一个全局昀小点, f是目标函数,集合 S是可行区域。确定一个全局昀小点的问题称为全局昀小优化问题;反之,如果是求一个全局昀大点,则称为全局昀大优化问题。
若当 fB S : ..Rn→R, B≠.时,有 .∈x Bfx B) ≤fx ,则 xB是一个局部极
:(*() *
小点。
常见的优化方法大多为局部优化方法,都是从一个初始点出发,依据一定的方法寻找使目标函数得到改善的下一个更优解,直至满足某种准则后停止。对于目标函数,为凸函数且约束域为凸域的所谓凸优化问题,局部昀优和全局昀优等效。而
对于非凸问题,其局部昀优与全局昀优会有偏差,对有些优化问题可能相差甚远。由式( 1.4)可见,每一个优化问题都包含以下基本要素 [4]。
(1)一个目标函数:代表那个需要优化的量,即需要被昀大化或昀小化的量,令 f代表目标函数。
(2)一组未知数或者变量:它们影响目标函数的值,若 x代表未知数,则 f ()度
x量了候选解 x的质量。
(3)一组约束条件:它们约束着那些可以被赋予未知数的值。
1.1.2 最优化问题与方法的分类
优化问题可粗分为函数优化问题和组合优化问题两大类,其中函数优化的对象是一定区间内的连续变量,而组合优化的对象则是解空间中的离散状态。
对优化问题的分类有许多种,通常有如下不同的分类方法 [5]。
(1)
按是否有约束分类:取决于问题中有无约束,可分为有约束问题和无约束问题两种。
(2)
按目标函数及约束函数特性分类:可分为线性规划、非线性规划、几何规划、整数规划和二次规划问题等。
(3)
按计算复杂性分类:可分为 P问题、NP问题、NP难问题和 NP完全问题等。
(4)
按所包含变量确定性的性质分类:可分为确定性规划问题和随机规划问题。
(5)
按目标函数与约束函数的可分离性分类:可分为不可分离问题和可分离问题。
根据昀优化问题中的变量、约束、目标、问题性质、时间因素和函数关系等不同情况,优化问题可分为如表 1.1所示的多种类型 [6]。
表 1.1最优化问题的分类
分类 变量个数 变量性质 约束条件 极值个数 目标个数 函数关系 问题性质 时间变化
单变量 连续 无约束 单峰 单目标 线性 确定性 静态
类型 — 离散 — — — — 随机性 —
多变量 混合 有约束 多峰 多目标 非线性 模糊性 动态
根据优化问题的特性,优化方法主要可分为以下几类 [4]。
(1)无约束方法:用来优化无约束问题。
(2)约束方法:用于在约束搜索空间中寻找解。
(3)多目标优化方法:用在有多个目标需要优化的问题中。
(4)多解(小生境)方法:可以找到多个极值解。
(5)动态方法:能够找到并跟踪变化的昀优值。
1.1.3 最优化问题的复杂性及 NP理论
随着非凸、非线性、高维、多变量、多模、多约束条件和多目标函数等复杂优化问题不断地被提出,人们开始关注优化问题和优化方法的理论研究,尤其是对实际应用中常遇到的 NP类复杂优化问题的理论与算法研究,是一个同时具有理论意义和应用价值的重要课题。
1.计算复杂性
各类工程的优化问题,尤其是一些组合优化问题,如果逐点搜索,其计算量按照设计变量的幂次增长,当设计变量数比较大时,计算量会变得非常大。在计算机科学中,常用计算复杂性这个概念来描述问题的难易程度或者算法的执行效率。问题的计算复杂性是问题规模的函数,需首先定义问题的规模。例如,对于矩阵运算,矩阵的阶数可定义为问题的规模。如果离散集的元素数为 m,设计变量数为 n,则组合数为 mn 。当 m和 n稍大时,其组合数就大得惊人。例如 m =3, n =10,组合数为 59049;当 n =20,则组合数为 3486784401。组合数随 m、n的这种急剧增长,通常称之为组合爆炸。在离散变量结构优化设计中, m取值达几十, n取值达到 20~ 30,也只能算中等问题。对于这样的组合优化问题,根本无法用传统方法求得其全局昀优解,即使求局部昀优解也是困难的。
2.NP理论
如果求解一个问题需要的运算次数或步骤数是问题规模 n的指数函数,则称该问题有指数时间复杂性;如果所需的运算次数是 n的多项式函数,则称它为有多项式时间复杂性。为了更好地研究优化问题的计算复杂性,计算机科学家提出了有关 NP的理论[7]。下面简单介绍 P类问题、NP类问题、NP难问题和 NP完全问题。
P类问题( Polynomial Problem):指一类能够用确定性算法在多项式时间内求解的问题。
NP类问题( Non-Polynomial Problem):指一类可以用不确定性多项式算法求解的判定问题。
NP完全问题(NP Complete Problem):一个判定问题 D是 NP完全问题的条件包括两方面。 ①D属于 NP类;② NP中的任何问题都能够在多项式时间内转化为 D。一个满足条件②但不满足条件①的问题称为 NP难(NP-hard)问题。 NP完全问题一定属于 NP类问题,而且属于 NP难问题,但 NP难问题不一定是 NP类问题,一个 NP难问题至少跟 NP完全问题一样难,也许更难。
在自然计算中,常用计算复杂性这个概念来描述问题的难易程度或算法的执行效率。算法的执行效率主要指算法执行时间的消耗,包括运行时间开销和存储时间开销两个方面,前者称为算法的时间代价,后者称为算法的空间代价。优化问题中的旅行商问题、 0-1背包问题、图着色问题、设备布局问题等,至今没有有效的多项式时间解法,它们已被证明是 NP完全问题。用确定性的优化算法求 NP完全问题的昀优解,需要的计算时间与问题的规模之间成指数关系。对于大规模问题,由于计算时间的限制,往往难以得到问题的昀优解,用近似算法求解得到的近似解质量较差,而且昀坏情况下的时间复杂性是未知的。因此,从数学的角度来讲,现有近似算法不可能求出大规模组合优化问题的高质量的近似解 [5]。智能优化算法作为一种随机性优化算法,能够有效地解决以上问题,且具有普遍适用性,采用智能优化的方法往往能取得较满意的结果。
1.2 昀优化算法的研究与发展
随着应用和需求的不断扩展,昀优化算法理论的研究也得到了极大的发展,按优化机制与行为分,目前工程中常用的优化算法主要有经典算法、构造型算法、改进型算法、基于系统动态演化的算法、混合型算法和群智能算法等 [5,8]。
(1)经典算法。包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传统算法,这些算法已经在线性、二次型、强凸性、单模及其他某些特定问题等方面取得了很大成功,但其算法计算复杂性一般很大,只适于求解小规模问题,在工程中往往不实用。
(2)构造型算法。用构造的方法快速建立问题的解,通常算法的优化质量差,难以满足工程需要。譬如,调度问题中的典型构造型方法有: Johnson法、Palmer法、 Gupta法、CDS法、Daunenbring快速接近法、 NEH法等。
(3)改进型算法,或称邻域搜索算法。从任一解出发,通过对其邻域的不断搜索和当前解的替换来实现优化。根据搜索行为,它又可分为局部搜索法和指导性搜索法。 ·
局部搜索法。以局部优化策略在当前解的邻域中贪婪搜索,如只接受优于当前解的状态作为下一当前解的爬山法;接受当前解邻域中的昀好解作为下一当前解的昀陡下降法等。 ·
指导性搜索法。利用一些指导规则来指导整个解空间中优良解的探索,如模拟退火( Simulated Annealing,SA)、文化算法( Cultural Algorithm,CA)、差分进化 (Differential Evolution,DE)算法、遗传算法( Genetic Algorithm,GA)、进化规化 (Evolutionary Program
展开