现代优化算法简介与MATLAB实现.pdf-资料库

现代优化算法是 80 年代初兴起的启发式算法。这些算法包括禁忌搜索（tabu search），模拟退火（simulated annealing），遗传算法（genetic algorithms），人工神经网络（neural networks）。它们主要用于解决大量的实际应用问题。目前，这些算法在理论和实际应用方面得到了较大的发展。无论这些算法是怎样产生的，它们有一个共同的目标－求 NP-hard 组合优化问题的全局最优解。虽然有这些目标，但 NP-hard 理论限制它们只能以启发式的算法去求解实际问题。启发式算法包含的算法很多，例如解决复杂优化问题的蚁群算法（Ant Colony Algorithms）。有些启发式算法是根据实际问题而产生的，如解空间分解、解空间的限制等；另一类算法是集成算法，这些算法是诸多启发式算法的合成。现代优化算法解决组合优化问题，如 TSP（Traveling Salesman Problem）问题，QAP （Quadratic Assignment Problem）问题，JSP（Job-shop Scheduling Problem）问题等效果很好。第二十三章现代优化算法 §1 模拟退火算法 1.1 算法简介模拟退火算法得益于材料的统计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火），粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。如果用粒子的能量定义材料的状态，Metropolis 算法用一个简单的数学模型描述了退火过程。假设材料在状态i 之下的能量为 )(iE ，那么材料在温度T 时从状态i 进入状态 j 就遵循如下规律： ≤ > （1）如果（2）如果 iE )( ，接受该状态被转换。 iE )( ，则状态转换以如下概率被接受： jEiE )( − )( KT jE )( jE )( e 其中 K 是物理学中的波尔兹曼常数，T 是材料温度。在某一个特定温度下，进行了充分的转换之后，材料将达到热平衡。这时材料处于状态i 的概率满足波尔兹曼分布： xP ( T = i ) = − iE )( KT − jE )( KT e e ∑ Sj ∈ 其中 x 表示材料当前状态的随机变量， S 表示状态空间集合。显然 lim T ∞→ − iE )( KT − jE )( KT e e ∑ Sj ∈ = 1 S | | -451-

| S 表示集合 S 中状态的数量。这表明所有状态在高温下具有相同的概率。而当温其中 | 度下降时， lim T 0 → − )( EiE − KT min − )( EjE − KT min e e ∑ Sj ∈ = lim T 0 → e EjE − KT )( − e − )( EiE − KT min min + ∑ Sj ∉ min − )( EjE − KT min e ∑ min Sj ∈ 1 ⎧ ⎪ S | | ⎨ min ⎪ 0 ⎩ i 若 ∈ S min 其它 = lim T 0 → − )( EiE − KT min − )( EjE − KT min e = e ∑ Sj ∈ = min 其中 S min 且 jE )( min Sj∈ E 上式表明当温度降至很低时，材料会以很大概率进入最小能量状态。假定我们要解决的问题是一个寻找最小值的优化问题。将物理学中模拟退火的思 iEi |{ )( 。 E min min = = } 想应用于优化问题就可以得到模拟退火寻优方法。 xf : 考虑这样一个组合优化问题：优化函数为 R 问题的一个可行解，的一个邻域集合。 =+ yRyy |{ , ∈ > }0 +→ R ，其中 S ，S 表示函数的定义域。 x ∈ ，它表示优化表示 x ⊆)( xN S 解首先给定一个初始温度 0T 和该优化问题的一个初始解 )0(x ，并由 )0(x 生成下一个 xNx ∈ ' ，是否接受 'x 作为一个新解 )1(x 依赖于下面概率： xf ))0(( ))0(( xf )'( 若 < xP )0(( =→ )' x 1 ⎧ ⎪ ⎨ xf xf )'( ))0(( − ⎪⎩ T e 0 − 其它换句话说，如果生成的解 'x 的函数值比前一个解的函数值更小，则接受 x )1( = 作为 x ' 一个新解。否则以概率 xf )'( − xf ))0(( − T 0 e 接受 'x 作为一个新解。泛泛地说，对于某一个温度 iT 和该优化问题的一个解 )(kx ，可以生成 'x 。接受 'x 作为下一个新解 ( +kx )1 kxP )(( =→ )' x 的概率为： 1 ⎧ ⎪ ⎨ xf kxf )'( (( − ⎪⎩ e iT )) − 若 xf )'( < kxf (( )) 其它（1）。在 1+iT 下重复上述在温度 iT 下，经过很多次的转移之后，降低温度 iT ，得到过程。因此整个优化过程就是不断寻找新解和缓慢降温的交替过程。最终的解是对该问题寻优的结果。 T <+1 i T i 我们注意到，在每个 iT 下，所得到的一个新状态 ( +kx )1 完全依赖于前一个状态 )1 −kx (, x L ),0( )(kx ，可以和前面的状态无关，因此这是一个马尔可夫过程。使用马尔可夫过程对上述模拟退火的步骤进行分析，结果表明：从任何一个状态 )(kx 生成 'x 的中是均匀分布的，且新状态 'x 被接受的概率满足式（1），那么经过概率，在有限次的转换，在温度 iT 下的平衡态 ix 的分布由下式给出： -452- kxN (( ))

− ) xf ( i T ) xf ( i T i 若 x i ∈ S min 其它（2） ) = TP ( i i e ∑ 当温度T 降为 0 时， ix 的分布为： Sj ∈ e − * P i = 1 ⎧ ⎪ S | | ⎨ min ⎪⎩ 0 并且 * =∑ P i ∈Sx i min 1 这说明如果温度下降十分缓慢，而在每个温度都有足够多次的状态转移，使之在每一个温度下达到热平衡，则全局最优解将以概率 1 被找到。因此可以说模拟退火算法可以找到全局最优解。在模拟退火算法中应注意以下问题：（1）理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算机实现中，如果降温速度过缓，所得到的解的性能会较为令人满意，但是算法会太慢，相对于简单的搜索算法不具有明显优势。如果降温速度过快，很可能最终得不到全局最优解。因此使用时要综合考虑解的性能和算法速度，在两者之间采取一种折衷。（2）要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续 m 次的转换过程没有使状态发生变化时结束该温度下的状态转换。最终温度的确定可以提前定为一个较小的值 eT ，或连续几个温度下转换过程没有使状态发生变化算法就结束。（3）选择初始温度和确定某个可行解的邻域的方法也要恰当。 1.2 应用举例已知敌方 100 个目标的经度、纬度如表 1 所示。表 1 经度和纬度数据表经度纬度 53.7121 15.3046 56.5432 21.4188 20.1050 15.4562 26.2418 18.1760 28.2694 29.0011 8.9586 24.6635 8.1519 9.5325 31.9499 17.6309 43.5474 3.9061 23.9222 7.6306 21.5051 24.0909 17.1168 20.0354 52.1181 0.4088 37.5848 16.8474 14.4703 13.6368 58.6849 27.1485 经度纬度 51.1758 0.0322 10.8198 16.2529 1.9451 0.2057 44.0356 13.5401 32.1910 5.8699 16.5618 23.6143 22.1075 18.5569 0.7732 0.4656 53.3524 26.7256 51.9612 22.8511 15.2548 27.2111 34.1688 22.7571 9.5559 11.4219 35.6619 9.9333 19.8660 15.1224 39.5168 16.9371 经度纬度 46.3253 28.2753 22.7891 23.1045 26.4951 22.1221 28.9836 25.9879 36.4863 29.7284 10.5597 15.1178 0.1215 18.8726 47.4134 23.7783 30.8165 13.4595 12.7938 15.7307 6.2070 5.1442 9.4402 3.9200 24.4509 6.5634 24.4654 3.1644 3.1616 4.2428 56.5089 13.7090 经度纬度 30.3313 6.9348 10.1584 12.4819 31.4847 8.9640 38.4722 20.1731 0.9718 28.1477 50.2111 10.2944 48.2077 16.8889 41.8671 3.5667 27.7133 5.0706 4.9568 8.3669 49.2430 16.7044 11.5812 14.5677 26.7213 28.5667 0.7775 6.9576 18.5245 14.3598 52.5211 15.7957 -453-

50.1156 23.7816 19.9857 5.7902 52.8423 27.2880 28.7812 27.6659 33.6490 0.3980 36.9545 23.0265 39.7139 28.4203 36.9980 24.3992 41.1084 27.7149 51.8181 23.0159 34.0574 23.3960 58.8289 14.5229 47.5099 24.0664 9.1556 14.1304 49.9816 6.0828 11.5118 17.3884 38.3392 19.9950 40.1400 20.3030 8.9983 23.6440 23.0624 8.4319 18.6635 6.7436 10.1121 27.2662 53.7989 0.2199 19.3635 17.6622 44.0398 16.2635 24.6543 19.6057 23.9876 9.4030 38.4300 8.4648 13.7909 1.9510 40.8801 14.2978 39.9494 29.5114 8.0831 27.6705 1.3496 16.8359 15.7320 19.5697 6.9909 23.1804 4.1591 3.1853 我方有一个基地，经度和纬度为（70,40）。假设我方飞机的速度为 1000 公里/小时。我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目标点的侦察时间不计，求该架飞机所花费的时间（假设我方飞机巡航时间可以充分长）。这是一个旅行商问题。我们依次给基地编号为 1，敌方目标依次编号为 2，3，…，， 102 × ，这里 D 为实对称矩阵。则问题是 101，最后我方基地再重复编号为 102（这样便于程序中计算）。距离矩阵其中 ijd 表示表示 j 求一个从点 1 出发，走遍所有中间点，到达点 102 的一个最短路径。 i, 两点的距离， L=j ijdD 102, ,2,1 102) = ( i , 上面问题中给定的是地理坐标（经度和纬度），我们必须求两点间的实际距离。设 BA, 两点的地理坐标分别为，过 BA, 两点的大圆的劣弧长即为两点的实际距离。以地心为坐标原点O ，以赤道平面为 XOY 平面，以 0 度经线圈所在的平面为 XOZ 平面建立三维直角坐标系。则 BA, 两点的直角坐标分别为： 1 yx , 1 2 y , ( ， x ) ) ( 2 sin sin x 1 x cos cos Ry , 1 Ry , 2 y ) sin 1 y sin 2 2 ) 其中 2 x 1 x cos cos cos cos RA ( RB ( 6370 Ry , 1 Ry , 2 为地球半径。 =R BA, 两点的实际距离 ⎛ ⎜ arccos ⎜ ⎜ ⎝ OA OA Rd = ⋅ ⋅ OB OB ⎞ ⎟ ⎟ ⎟ ⎠ ， = − x 1 Rd arccos[cos ( 化简得 ) 求解的模拟退火算法描述如下：（1）解空间解空间 S 可表为{ ,2,1 L S |) = = 102,101, (,1 πππ 1 {( 102 x , , , 2 2 1 L cos y 1 cos y 2 + sin y 1 sin y 2 ] 。 ππ L ,3,2{) 为 L }的所有固定起点和终点的循环排列集合，即 , }102 i =π 表示在第 1−i 次侦察目，本文中我们先使用 Monte Carlo 方法求得一个较好 , π 的循环排列 }101, = 102 101 j 其中每一个循环排列表示侦察 100 个目标的一个回路，标 j ，初始解可选为的初始解。 ,2,1( L )102, （2）目标函数此时的目标函数为侦察所有目标的路径长度或称代价函数。我们要求 min f -454- ( πππ L 1 , , , 102 ) 2 = 101 ∑ i 1 = id ππ i + 1

对于 2 变换法，路径差可表示为 ) − + d ππ v 1 − ππ vu + 1 ( d ππ u 1 − u + d ππ v v + 1 ) u d f ( =Δ （5）接受准则 1 ⎧ ⎨ exp( ⎩ P = f <Δ f ≥Δ 0 0 Δ− Tf / ) 如果 exp( 0<Δf / ) 大于 0 到 1 之间的随机数则接受。 TfΔ− （6）降温利用选定的降温系数α进行降温即：，则接受新的路径。否则，以概率 exp( TfΔ− / ) 接受新的路径，即若 T α← ，得到新的温度，这里我们取 T 而一次迭代由下列三步构成：（3）新解的产生 ① 2 变换法任选序号 vu, （ v u < ）交换u 与 v 之间的顺序，此时的新路径为： v 1 u u v u 1 − v 1 − 1 + 1 + L L ππππππππ 102 L ② 3 变换法任选序号 vu, 和 w ，将 u 和 v 之间的路径插到 w 之后，对应的新路径为（设 wv 1 − （4）代价函数差） ππππππππ wv uw L L L L 102 1 + 1 + u v 1 u << .0=α 999 。（7）结束条件用选定的终止温度当前状态。文件 sj.txt 中 =e 10− 30 ，判断退火过程是否结束。若 T < ，算法结束，输出 e 我们编写如下的 matlab 程序如下： clc,clear load sj.txt %加载敌方 100 个目标的数据，数据按照表格中的位置保存在纯文本 x=sj(:,1:2:8);x=x(:); y=sj(:,2:2:8);y=y(:); sj=[x y]; d1=[70,40]; sj=[d1;sj;d1]; sj=sj*pi/180; d=zeros(102); %距离矩阵 d for i=1:101 for j=i+1:102 temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)); d(i,j)=6370*acos(temp); end end d=d+d'; S0=[];Sum=inf; rand('state',sum(clock)); for j=1:1000 S=[1 1+randperm(100),102]; temp=0; -455-

for i=1:101 temp=temp+d(S(i),S(i+1)); end if temprand(1) S0=[S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102)]; Sum=Sum+df; end T=T*at; if T

2.1 遗传算法简介遗传算法（Genetic Algorithms，简称 GA）是一种基于自然选择原理和自然遗传机制的搜索（寻优）算法，它是模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。遗传算法的实质是通过群体搜索技术，根据适者生存的原则逐代进化，最终得到最优解或准最优解。它必须做以下操作：初始群体的产生、求每一个体的适应度、根据适者生存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染色体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化，直到满足进化终止条件。其实现方法如下：（1）根据具体问题确定可行解域，确定一种编码方法，能用数值串或字符串表示可行解域的每一解。（2）对每一解应有一个度量好坏的依据，它用一函数表示，叫做适应度函数。（3）确定进化参数群体规模 M 、交叉概率 cp 、变异概率 mp 、进化终止条件。为便于计算，一般来说，每一代群体的个体数目都取相等。群体规模越大、越容易找到最优解，但由于受到计算机的运算能力的限制，群体规模越大，计算所需要的时间也相应的增加。进化终止条件指的是当进化到什么时候结束，它可以设定到某一代进化结束，也可以根据找出近似最优是否满足精度要求来确定。表 2 列出了生物遗传概念在遗传算法中的对应关系。生物遗传概念适者生存表 2 生物遗传概念在遗传算法中的对应关系遗传算法中的作用算法停止时，最优目标值的解有最大的可能被留住个体染色体基因适应性种群交配变异解解的编码解中每一分量的特征适应度函数值根据适应度函数值选取的一组解通过交配原则产生一组新解的过程编码的某一分量发生变化的过程（ 2.2 模型及算法我们用遗传算法研究 1.2 中的问题。求解的遗传算法的参数设定如下：种群大小：最大代数：交叉率： 50=M =G 1000 1=cp ，交叉概率为 1 能保证种群的充分进化。 1.0=mp ，一般而言，变异发生的可能性较小。变异率：（1）编码策略采用十进制编码，用随机数列 ,3,2 L=i 1 1 =ω ， 102 =ω 101, ）， 0 1 1 ωωω K 作为染色体，其中；每一个随机序列都和种群中的一个个体相对 < iω < 102 0 2 -457-

应，例如一个 9 目标问题的一个染色体为 [0.23，0.82，0.45，0.74，0.87，0.11，0.56，0.69，0.78] 其中编码位置i 代表目标i ，位置i 的随机数表示目标i 在巡回中的顺序，我们将这些随机数按升序排列得到如下巡回： 6－1－3－7－8－4－9－2－5 （2）初始种群本文中我们先利用经典的近似算法—改良圈算法求得一个较好的初始种群。即对于初始圈 = C 1 v v u u u 1 − 1 − 1 + 1 + ， L L L ππππππππ 102 交换u 与 v 之间的顺序，此时的新路径为： ππππππππ L 1 102 d ( ) ，若 ππ v L ) − 记经，直到不能修改为止。（3）目标函数 f =Δ L d u 1 + d ( 1 − + ππ u 1 + + v d ππ vu ππ v 1 − 1 − 1 − + 1 + 1 u v v u v u u v 2 ≤<≤ u v 101 ， 2 ≤ u ππ v < ≤ 101 ， 0<Δf ，则以新的路经修改旧的路目标函数为侦察所有目标的路径长度，适应度函数就取为目标函数。我们要求 min f （4）交叉操作 ( πππ L 1 , , , 102 ) 2 = 101 ∑ i 1 = id ππ i + 1 ' ' 1 2 1 2 ， =f 2 ' ωωω K 我们的交叉操作采用单点交叉。设计如下，对于选定的两个父代个体 =f ，我们随机地选取第 t 个基因处为交叉点，则 ωωω K 1 102 经过交叉运算后得到的子代编码为 1s 和 2s ， 1s 的基因由 1f 的前 t 个基因和 2f 的后 102 个基因构成， 2s 的基因由 2f 的前 t 个基因和 1f 的后 102 个基因构成，例如： ,0.19, ,0.24, 0.27, | 0.56, | t− 1] 1] 0.54, 0.21, 0.25, 0.44, 0.14, 0.23, 0.29, 0.74, t− =f 1 =f 2 0,[ 0,[ 102 L L 设交叉点为第四个基因处，则 0,[ 0,[ =s 1 =s 2 交叉操作的方式有很多种选择，我们应该尽可能选取好的交叉方式，保证子代能继 0.27, | 0.56, | ,0.24, ,0.19, 0.14, 0.23, 0.74, 0.29, 0.25, 0.44, 0.21, 0.54, 1] 1] L L 承父代的优良特性。同时这里的交叉操作也蕴含了变异操作。（5）变异操作变异也是实现群体多样性的一种手段，同时也是全局寻优的保证。具体设计如下，，按照给定的变异率，对选定变异的个体，随机地取三个整数，满足把 vu, 之间（包括u 和 v ）的基因段插到 w 后面。 <<< wv 102 < u 1 （6）选择采用确定性的选择策略，也就是说选择目标函数值最小的 M 个个体进化到下一代，这样可以保证父代的优良特性被保存下来。 2.3 模型求解及结论编写 MATLAB 程序如下： tic clc,clear load sj.txt %加载敌方 100 个目标的数据 -458-

资料库

现代优化算法简介与MATLAB实现.pdf

相关推荐

开发技术

热门标签

最新资料