文档介绍：第6章现代优化算法简介
第1节关于算法页:1
邢文训,谢金星. 现代优化计算方法. 清华大学出版社. 2001,5
的基本认识
在现代物流的诸多环节,常常涉及到构造模型并需对这些模型进行求解。构造的模型合适、采用的算法恰当,可以取得事半功倍的效果。因此,有必要对算法有一个初步的了解。
现代优化算法包括禁忌搜索、模拟退火、遗传算法、神经网络和拉格朗日松弛算法,这些算法涉及生物进化、人工智能、数学和物理科学神经系统和统计力学等概念,都是以一定的直观基础而构造的算法,我们称之为启发式算法。启发式算法的兴起与计算复杂性理论的形成有密切都关系。当人们不满足于用常规算法求解复杂问题时,现代优化算法开始体现其作用。现代优化算法自20世纪80年代兴起以来,至今发展迅速。
组合最优化问题
组合最优化是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等,是运筹学中一个经典且重要的分支,所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络、选址、配送等诸多领域。该问题可用数学模型描述为:
minf(x)
. g(x)≥0,
x∈D,
其中,f(x)为目标函数,g(x)为约束函数,x为决策变量,D表示有限个点组成的集合。
一个组合最优化问题可用三参数(D,F,f)表示,其中,D表示决策变量的定义域,F表示可行解区域F={x∣x∈D , g(x)≥0},F中的任何一个元素称为该问题的可行解,f表示目标函数。满足f(x*)=min{f(x) ∣x∈F}的可行解x*称为该问题的最优解。组合最优化的特点是可行解集合为有限点集。由直观可知,只要将D中有限个点逐一判别是否满足g(x)的约束和比较目标值得大小,该问题的最优解一定存在和可以得到,因为现实生活中的大量优化问题是从有限个状态中选取最好的,所以大量的实际优化问题是组合最优化问题。
计算复杂性的概念
由组合最优化问题的定义可知,每一个组合最优化问题都可以通过枚举的方法求得最优解。枚举是以时间为代价的。有的枚举时间可以接受,有的则不可能接受。例如,对于TSP问题(见下表)。
表6-1 TSP问题采用枚举方法时城市数目与计算时间的关系*
城市数目
24
25
26
27
28
29
30
31
计算时间
1s
24s
10min
约325a
注:这里假设计算机处理24个城市时所用时间为1s。
问题通常是一个抽象的模型或概念,它通过一些具体的数据表现出来。问题是需要回答的一般性提问,通常含有若干个满足一定条件的参数。问题通过下面的描述给定:
描述所有参数的特性;
描述答案所满足的条件。
通过给出的具体条件而使问题具体化。目前计算机可以求解的是这些给出具体条件的具体问题。一个算法常常是针对一个问题来设计的。如上面TSP枚举算法可以求解任何一个TSP的最优解。而若用计算机求解,则必须对问题中的参数赋予具体值,如TSP中的城市数目和城市间的距离。问题中的参数赋予了具体值的例子称为问题的实例。一个问题通过它的所有实例表现。
衡量一个算法的好坏通常是用算法中的加减乘除和比较等基本运算的总次数同实例在计算机计算时的二进制输入数据的大小关系来衡量。对于一个正整数x,二进制表示是以
x=as2s+as-12 s-1+……+a1×2+a0 (as ≠0)
的系数(as as-1 …a1 a0)来表示,其中,ai∈{0,1},i=0,1,…,s。由
2s≤=x≤2s+1≤,
这个二进制数的位数是s+1,也称为x的输入长度,在log2x与log2x+1之间。于是,x的二进制数的位数是整数 log2x取整数或log2x取整数再加1,但不超过后者。虽说log20没有意义、log21=0,特别需要注意的是,,,在特别定义log20=0后,上面的二进制表示方法和输入长度的结论可以推广到非负整数。常规理解的计算机只能用有限位表示一个实数,因此,我们限定只考虑有理数。
,当城市数目为n且第一个城市为始终点时,计算一条路径(1,i2,…,in)长度的基本运算为两两城市间距离的n个求和,因为有(n-1)!条路径,枚举所有路径进行(n-1)!次比较,可以得到最优路径。这个枚举算法的基本计算总次数为{(n-1)!}n=n!。实例在计算机计算时只需输入城市数目和所有城市之间的距离。于是,输入数据是城市数目n和城市间的距离S={dij︱1≤i,j≤n,i≠j},且假设这些数为整数。对任何一个非零距离dij,它的二进制输入数据的输入长度不超过log2︱dij︱+