《第二十三章现代优化算法简介》由会员分享，可在线阅读，更多相关《第二十三章现代优化算法简介（10页珍藏版）》请在金锄头文库上搜索。
1、第二十三章 现代优化算法简介1 现代优化算法简介现代优化算法是 80 年代初兴起的启发式算法。这些算法包括禁忌搜索( tabu search),模拟退火(simulated annealing),遗传算法(genetic algorithms),人工神经网 络(neural networks)o它们主要用于解决大量的实际应用问题。目前，这些算法在理论 和实际应用方面得到了较大的发展。无论这些算法是怎样产生的，它们有一个共同的目 标一求NP-hard组合优化问题的全局最优解。虽然有这些目标，但NP-hard理论限制它 们只能以启发式的算法去求解实际问题。启发式算法包含的算法很多，例如解决复杂优化
2、问题的蚁群算法( Ant Colony Algorithms)o有些启发式算法是根据实际问题而产生的，如解空间分解、解空间的限 制等；另一类算法是集成算法，这些算法是诸多启发式算法的合成。现代优化算法解决组合优化问题，如TSP (Traveling Salesman Problem)问题，QAP (Quadratic Assignment Problem )问题，JSP (Job-shop Scheduling Problem )问题等效 果很好。本章我们只介绍模拟退火算法，初步介绍一下蚁群算法，其它优化算法可以参看 相关的参考资料。2 模拟退火算法2.1 算法简介 模拟退火算法得益于材料的统
3、计力学的研究成果。统计力学表明材料中粒子的不 同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和 重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温(这个过 程被称为退火)，粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形 成处于低能状态的晶体。如果用粒子的能量定义材料的状态，Metropolis算法用一个简单的数学模型描述了 退火过程。假设材料在状态i之下的能量为E(i)，那么材料在温度T时从状态i进入状 态 j 就遵循如下规律：(1) 如果E(j) E(i)，则状态转换以如下概率被接受：E (i)-E (j) e KT其中K是物理学中
4、的波尔兹曼常数，T是材料温度。 在某一个特定温度下，进行了充分的转换之后，材料将达到热平衡。这时材料处 于状态i的概率满足波尔兹曼分布：_ E （/）e KTE （八E_e KTjwS其中 x 表示材料当前状态的随机变量， S 表示状态空间集合。 显然_ E(i)e _ kt 1l i m二T * V _ Ej I S I e KTjwS其中I S I表示集合S中状态的数量。这表明所有状态在高温下具有相同的概率。而当温度下降时，E (八一Emine KT lim - T t0 V eEmnKT二 lim Tt0 V eE (八一Emine KTEjEmnKTEmnKTjwSE (i) Emin
5、e KT=limT TO V_ E ( j)_Emine KTjeS mmjVS .min丨S Imin0若i g Smin其它min其中 E= min E(j)且 S= i I E(i) = E 。minminminjgS上式表明当温度降至很低时，材料会以很大概率进入最小能量状态。假定我们要解决的问题是一个寻找最小值的优化问题。将物理学中模拟退火的思 想应用于优化问题就可以得到模拟退火寻优方法。考虑这样一个组合优化问题：优化函数为F : x T R+，其中x g S，它表示优化 问题的一个可行解，R+二y I y g R, y 0，s表示函数的定义域。n(x)匸S表示x的一个邻域集合。首先给
6、定一个初始温度T和该优化问题的一个初始解x(0)，并由x(0)生成下一个 0解xg N(x(0)，是否接受x作为一个新解x(1)依赖于下面概率：P(x(0) T x)= ef (x)f (x (0)T0若f (x) f (x(0)其它换句话说，如果生成的解x的函数值比前一个解的函数值更小，则接受x(1) = x作为f (x)f (x (0)一个新解。否则以概率et0接受x作为一个新解。泛泛地说，对于某一个温度T和该优化问题的一个解x(k)，可以生成x。接受x i作为下一个新解x(k +1)的概率为：卩若/(x) f (x(k)P(x(k) T x) =1 f (x)f (x(k)eT0其它在温
7、度T下，经过很多次的转移之后，降低温度T，得到T T。在T下重复上述iii +1ii+1过程。因此整个优化过程就是不断寻找新解和缓慢降温的交替过程。最终的解是对该问 题寻优的结果。我们注意到，在每个T下，所得到的一个新状态x(k +1)完全依赖于前一个状态 ix(k)，可以和前面的状态x(0), ,x(k 1)无关，因此这是一个马尔可夫过程。使用马尔可夫过程对上述模拟退火的步骤进行分析,结果表明:从任何一个状态x（k）生成x的 概率，在N（x（k）中是均匀分布的，且新状态X被接受的概率满足式（1）,那么经过有限次的转换，在温度T下的平衡态x的分布由下式给出:iiP (T)=iif(X )ieT
8、2)-宀eTijwS当温度T降为0时，x的分布为：i1若 x e SP * 二 | S |i minimin0其它并且z P * 二 1ixieSmin这说明如果温度下降十分缓慢，而在每个温度都有足够多次的状态转移，使之在每一个 温度下达到热平衡，则全局最优解将以概率1被找到。因此可以说模拟退火算法可以找 到全局最优解。在模拟退火算法中应注意以下问题:（1）理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算 机实现中，如果降温速度过缓，所得到的解的性能会较为令人满意，但是算法会太慢， 相对于简单的搜索算法不具有明显优势。如果降温速度过快，很可能最终得不到全局最 优解。因此使用时
9、要综合考虑解的性能和算法速度，在两者之间采取一种折衷。（2）要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续m次的 转换过程没有使状态发生变化时结束该温度下的状态转换。最终温度的确定可以提前定 为一个较小的值T，或连续几个温度下转换过程没有使状态发生变化算法就结束。e（3）选择初始温度和确定某个可行解的邻域的方法也要恰当。2.2 应用举例例 已知敌方100个目标的经度、纬度如下:经度纬度经度纬度经度纬度经度纬度53.712115.304651.17580.032246.325328.275330.33136.934856.543221.418810.819816.252922.78
10、9123.104510.158412.481920.105015.45621.94510.205726.495122.122131.48478.964026.241818.176044.035613.540128.983625.987938.472220.173128.269429.001132.19105.869936.486329.72840.971828.14778.958624.663516.561823.614310.559715.117850.211110.29448.15199.532522.107518.55690.121518.872648.207716.888931.949
11、917.63090.77320.465647.413423.778341.86713.566743.54743.906153.352426.725630.816513.459527.71335.070623.92227.630651.961222.851112.793815.73074.95688.366921.505124.090915.254827.21116.20705.144249.243016.704417.116820.035434.168822.75719.44023.920011.581214.567752.11810.40889.555911.421924.45096.563
12、426.721328.566737.584816.847435.66199.933324.46543.16440.77756.957614.470313.636819.866015.12243.16164.242818.524514.359858.684927.148539.516816.937156.508913.709052.521115.795738.43008.464851.818123.01598.998323.644050.115623.781613.79091.951034.057423.396023.06248.431919.98575.790240.880114.297858
13、.828914.522918.66356.743652.842327.288039.949429.511447.509924.066410.112127.266228.781227.66598.083127.67059.155614.130453.79890.219933.64900.39801.349616.835949.98166.082819.363517.662236.954523.026515.732019.569711.511817.388444.039816.263539.713928.42036.990923.180438.339219.995024.654319.605736
14、.998024.39924.15913.185340.140020.303023.98769.403041.108427.7149我方有一个基地，经度和纬度为(70,40)。假设我方飞机的速度为1000 公里/小时。 我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目 标点的侦察时间不计，求该架飞机所花费的时间(假设我方飞机巡航时间可以充分长)。这是一个旅行商问题。我们依次给基地编号为1，敌方目标依次编号为2，3， 101,最后我方基地再重复编号为102(这样便于程序中计算)。距离矩阵D = (d ),ij 102x102 其中d表示表示i, j两点的距离，i, j = 1,2,102，这里
