1、-271-第二十三章 现代优化算法简介1 现代优化算法简介现代优化算法是 80 年代初兴起的启发式算法。这些算法包括禁忌搜索（tabu search） ，模拟退火（ simulated annealing） ，遗传算法（genetic algorithms） ，人工神经网络（neural networks） 。它们主要用于解决大量的实际应用问题。目前，这些算法在理论和实际应用方面得到了较大的发展。无论这些算法是怎样产生的，它们有一个共同的目标求 NP-hard 组合优化问题的全局最优解。虽然有这些目标，但 NP-hard 理论限制它们只能以启发式的算法去求解实际问题。启发式算法包含的算法很多，
2、例如解决复杂优化问题的蚁群算法（Ant Colony Algorithms） 。有些启发式算法是根据实际问题而产生的，如解空间分解、解空间的限制等；另一类算法是集成算法，这些算法是诸多启发式算法的合成。现代优化算法解决组合优化问题，如 TSP（Traveling Salesman Problem）问题，QAP（Quadratic Assignment Problem）问题，JSP（Job-shop Scheduling Problem）问题等效果很好。本章我们只介绍模拟退火算法，初步介绍一下蚁群算法，其它优化算法可以参看相关的参考资料。2 模拟退火算法2.1 算法简介模拟退火算法得益于材料的统
3、计力学的研究成果。统计力学表明材料中粒子的不同结构对应于粒子的不同能量水平。在高温条件下，粒子的能量较高，可以自由运动和重新排列。在低温条件下，粒子能量较低。如果从高温开始，非常缓慢地降温（这个过程被称为退火） ，粒子就可以在每个温度下达到热平衡。当系统完全被冷却时，最终形成处于低能状态的晶体。如果用粒子的能量定义材料的状态，Metropolis 算法用一个简单的数学模型描述了退火过程。假设材料在状态 之下的能量为 ，那么材料在温度 时从状态 进i)(iETi入状态 就遵循如下规律：j（1）如果 ，接受该状态被转换。)(Ej（2）如果 ，则状态转换以如下概率被接受：iKTje)(其中 是物理学
4、中的波尔兹曼常数， 是材料温度。K在某一个特定温度下，进行了充分的转换之后，材料将达到热平衡。这时材料处于状态 的概率满足波尔兹曼分布：iSjKTjEiTeixP)()()(其中 表示材料当前状态的随机变量， 表示状态空间集合。S显然-272-|1lim)()(SeSjKTjEiT其中 表示集合 中状态的数量。这表明所有状态在高温下具有相同的概率。而当|温度下降时， mininmininminmini )()()(0)()(0lli SjKTEjSjKTEjTSjKEjT eee其 它若 0|1li ii)()(0mininieSjKTEjT其中 且 。jj )(|minminES上式表明当温
5、度降至很低时，材料会以很大概率进入最小能量状态。假定我们要解决的问题是一个寻找最小值的优化问题。将物理学中模拟退火的思想应用于优化问题就可以得到模拟退火寻优方法。考虑这样一个组合优化问题：优化函数为 ，其中 ，它表示优化RxF:Sx问题的一个可行解， ， 表示函数的定义域。 表示0,|yRSN)(的一个邻域集合。x首先给定一个初始温度 和该优化问题的一个初始解 ，并由 生成下一0T)0(个解 ，是否接受 作为一个新解 依赖于下面概率：)0(Nx)1(x其 它若 )0()( 1TxfexffxP换句话说，如果生成的解 的函数值比前一个解的函数值更小，则接受 作为 )1(x一个新解。否则以概率 接
6、受 作为一个新解。0)()(Txf泛泛地说，对于某一个温度 和该优化问题的一个解 ，可以生成 。接受i )(kx作为下一个新解 的概率为：x)1(kx（1）其 它若 )()(0 TkxfeffP在温度 下，经过很多次的转移之后，降低温度 ，得到 。在 下重复上iTi iiT1i述过程。因此整个优化过程就是不断寻找新解和缓慢降温的交替过程。最终的解是对该问题寻优的结果。我们注意到，在每个 下，所得到的一个新状态 完全依赖于前一个状态i )(kx-273-，可以和前面的状态 无关，因此这是一个马尔可夫过程。使用)(kx )1(,)0kx马尔可夫过程对上述模拟退火的步骤进行分析，结果表明：从任何一个
7、状态 生成)(kx的概率，在 中是均匀分布的，且新状态 被接受的概率满足式（1） ，那么 (kxNx经过有限次的转换，在温度 下的平衡态 的分布由下式给出：iTi（2）SjTxffiiieP)()()(当温度 降为 0 时， 的分布为：Tix其 它若 |1minmin*xPii并且1min*Sx这说明如果温度下降十分缓慢，而在每个温度都有足够多次的状态转移，使之在每一个温度下达到热平衡，则全局最优解将以概率 1 被找到。因此可以说模拟退火算法可以找到全局最优解。在模拟退火算法中应注意以下问题：（1）理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算机实现中，如果降温速度过缓，所
8、得到的解的性能会较为令人满意，但是算法会太慢，相对于简单的搜索算法不具有明显优势。如果降温速度过快，很可能最终得不到全局最优解。因此使用时要综合考虑解的性能和算法速度，在两者之间采取一种折衷。（2）要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续 次m的转换过程没有使状态发生变化时结束该温度下的状态转换。最终温度的确定可以提前定为一个较小的值 ，或连续几个温度下转换过程没有使状态发生变化算法就结束。eT（3）选择初始温度和确定某个可行解的邻域的方法也要恰当。2.2 应用举例例 已知敌方 100 个目标的经度、纬度如下：经度 纬度 经度 纬度 经度 纬度 经度 纬度53.7121 1
9、5.3046 51.1758 0.0322 46.3253 28.2753 30.3313 6.934856.5432 21.4188 10.8198 16.2529 22.7891 23.1045 10.1584 12.481920.1050 15.4562 1.9451 0.2057 26.4951 22.1221 31.4847 8.964026.2418 18.1760 44.0356 13.5401 28.9836 25.9879 38.4722 20.173128.2694 29.0011 32.1910 5.8699 36.4863 29.7284 0.9718 28.14778
10、.9586 24.6635 16.5618 23.6143 10.5597 15.1178 50.2111 10.29448.1519 9.5325 22.1075 18.5569 0.1215 18.8726 48.2077 16.888931.9499 17.6309 0.7732 0.4656 47.4134 23.7783 41.8671 3.566743.5474 3.9061 53.3524 26.7256 30.8165 13.4595 27.7133 5.070623.9222 7.6306 51.9612 22.8511 12.7938 15.7307 4.9568 8.36
11、69-274-21.5051 24.0909 15.2548 27.2111 6.2070 5.1442 49.2430 16.704417.1168 20.0354 34.1688 22.7571 9.4402 3.9200 11.5812 14.567752.1181 0.4088 9.5559 11.4219 24.4509 6.5634 26.7213 28.566737.5848 16.8474 35.6619 9.9333 24.4654 3.1644 0.7775 6.957614.4703 13.6368 19.8660 15.1224 3.1616 4.2428 18.524
12、5 14.359858.6849 27.1485 39.5168 16.9371 56.5089 13.7090 52.5211 15.795738.4300 8.4648 51.8181 23.0159 8.9983 23.6440 50.1156 23.781613.7909 1.9510 34.0574 23.3960 23.0624 8.4319 19.9857 5.790240.8801 14.2978 58.8289 14.5229 18.6635 6.7436 52.8423 27.288039.9494 29.5114 47.5099 24.0664 10.1121 27.26
13、62 28.7812 27.66598.0831 27.6705 9.1556 14.1304 53.7989 0.2199 33.6490 0.39801.3496 16.8359 49.9816 6.0828 19.3635 17.6622 36.9545 23.026515.7320 19.5697 11.5118 17.3884 44.0398 16.2635 39.7139 28.42036.9909 23.1804 38.3392 19.9950 24.6543 19.6057 36.9980 24.39924.1591 3.1853 40.1400 20.3030 23.9876
14、 9.4030 41.1084 27.7149我方有一个基地，经度和纬度为（70,40） 。假设我方飞机的速度为 1000 公里/小时。我方派一架飞机从基地出发，侦察完敌方所有目标，再返回原来的基地。在敌方每一目标点的侦察时间不计，求该架飞机所花费的时间（假设我方飞机巡航时间可以充分长） 。这是一个旅行商问题。我们依次给基地编号为 1，敌方目标依次编号为2，3，101，最后我方基地再重复编号为 102（这样便于程序中计算） 。距离矩阵，其中 表示表示 两点的距离， ，这里 为实102)(ijdDijdji, 102,ji D对称矩阵。则问题是求一个从点 1 出发，走遍所有中间点，到达点 102
15、 的一个最短路径。上面问题中给定的是地理坐标（经度和纬度） ，我们必须求两点间的实际距离。设 两点的地理坐标分别为 ， ，过 两点的大圆的劣弧长即为BA, ),(1yx),(2BA,两点的实际距离。以地心为坐标原点 ，以赤道平面为 平面，以 0 度经线圈所OXOY在的平面为 平面建立三维直角坐标系。则 两点的直角坐标分别为：XOZ,)sin,cosin,cos( 111yRxR222xy其中 为地球半径。6370两点的实际距离BA,，OBRdAarcos化简得。sincos)(r 212121 yyx求解的模拟退火算法描述如下：（1）解空间解空间 可表为 的所有固定起点和终点的循环排列集合，即
16、S0,-275-102,10,32),(,1|),( 102102 的 循 环 排 列为 S其中每一个循环排列表示侦察 100 个目标的一个回路， 表示在第 次侦察 点，jiij初始解可选为 ，本文中我们使用 Monte Carlo 方法求得一个较好的初始解。,（2）目标函数此时的目标函数为侦察所有目标的路径长度或称代价函数。我们要求1021 1102),(miniidf 而一次迭代由下列三步构成：（3）新解的产生 2 变换法任选序号 （ ）交换 与 之间的顺序，此时的新路径为：vu,uv10211 v 3 变换法任选序号 和 ，将 和 之间的路径插到 之后，对应的新路径为（设,ww）vu10
17、211 vuvu（4）代价函数差对于 2 变换法，路径差可表示为 )()( 1111 vuvuvu ddf （5）接受准则 0)/exp( fTfP如果 ，则接受新的路径。否则，以概率 接受新的路径，即0f )/exp(Tf若 大于 0 到 1 之间的随机数则接受。)/exp(T（6）降温利用选定的降温系数 进行降温即： ，得到新的温度，这里我们取。9.（7）结束条件用选定的终止温度 ，判断退火过程是否结束。若 ，算法结束，输301e eT出当前状态。我们编写如下的 matlab 程序如下：clc,clearload sj.txt %加载敌方 100 个目标的数据，数据按照表格中的位置保存在纯
18、文本文件 sj.txt 中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;-276-%距离矩阵 dd=zeros(102);for i=1:101for j=i+1:102temp=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);endendd=d+d;S0=;Sum=inf;rand(state,sum(clock);for j=1:1000S
19、=1 1+randperm(100),102;temp=0;for i=1:101temp=temp+d(S(i),S(i+1);endif temprand(1)S0=S0(1:c1-1),S0(c2:-1:c1),S0(c2+1:102);Sum=Sum+df;endT=T*at;if Tebreak;endend% 输出巡航路径及路径长度S0,Sum计算结果为 44 小时左右。其中的一个巡航路径如下图所示：-277- 3 蚁群算法3.1 蚁群算法简介蚁群是自然界中常见的一种生物，人们对蚂蚁的关注大都是因为“蚁群搬家，天要下雨”之类的民谚。然而随着近代仿生学的发展，这种似乎微不足道的小东西
20、越来越多地受到学者们地关注。1991 年意大利学者 M. Dorigo 等人首先提出了蚁群算法，人们开始了对蚁群的研究：相对弱小，功能并不强大的个体是如何完成复杂的工作的（如寻找到食物的最佳路径并返回等） 。在此基础上一种很好的优化算法逐步发展起来。蚁群算法的特点是模拟自然界中蚂蚁的群体行为。科学家发现，蚁群总是能够发现从蚁巢到食物源的最短路径。经研究发现，蚂蚁在行走过的路上留下一种挥发性的激素，蚂蚁就是通过这种激素进行信息交流。蚂蚁趋向于走激素积累较多的路径。找到最短路径的蚂蚁总是最早返回巢穴，从而在路上留下了较多的激素。由于最短路径上积累了较多的激素，选择这条路径的蚂蚁就会越来越多，到最后
21、所有的蚂蚁都会趋向于选择这条最短路径。基于蚂蚁这种行为而提出的蚁群算法具有群体合作，正反馈选择，并行计算等三大特点，并且可以根据需要为人工蚁加入前瞻、回溯等自然蚁所没有的特点。在使用蚁群算法求解现实问题时，先生成具有一定数量蚂蚁的蚁群，让每一只蚂蚁建立一个解或解的一部分，每只人工蚁从问题的初始状态出发，根据“激素”浓度来选择下一个要转移到的状态，直到建立起一个解，每只蚂蚁根据所找到的解的好坏程度在所经过的状态上释放与解的质量成正比例的“激素” 。之后，每只蚂蚁又开始新的求解过程，直到寻找到满意解。为避免停滞现象，引入了激素更新机制。3.2 解决 TSP 问题的蚁群算法描述现以 TSP 问题的求
22、解为例说明蚁群系统模型。首先引进如下记号： 为城市的个n数； 为蚁群中蚂蚁的数量； 为两城市 和 之间距离； 为 时刻位于城市mijdij)(tbi的蚂蚁的个数， ； 为 时刻边弧 的轨迹强度（即 连线上残initb1)(tij,(jiij留的信息量） ，且设 （ 为常数） ， ， ； 为 时刻cj0 nji21,ji)(tij边弧 的能见度，反映由城市 转移到城市 的期望程度。),(ji i根据上述原理，蚂蚁 在运动过程中根据各条路径上的信息量决),2(mk-278-定转移方向。与真实蚁群系统不同，人工蚁群系统具有一定的记忆功能。随着时间的推移，以前留下的信息逐渐消逝，经 个时刻，蚂蚁完成一
23、次循环，各路径上信息量n要作调整。由此得到下述的人工蚁群系统模型：1）设人工蚁群在并行地搜索 TSP 的解，并通过一种信息素做媒介相互通信，在每个结点上且和该结点相连的边上以信息素量做搜索下一结点的试探依据，直到找到一个 TSP 问题的可行解。2）在时刻 人工蚁 由位置 转移至位置 的转移概率为tkijSjjttpSvivijjkij ,0 ,)()(（3）其中参数 为轨迹的相对重要性（ ） ； 为能见度的相对重要性（ ） ；00为可行点集，即蚂蚁 下一步允许选择的城市。 分别反映了蚂蚁在运动过程中Sk,所积累的信息及启发式因子在蚂蚁选择路径中所起的不同作用。3）当 个人工蚁按（3）式找到了可
24、行解，则将各边的信息量用下式修改。即调m整信息量的轨迹强度更新方程为， ijijij tt)()1( )1,0(（4） mkijij1其中 为第 只蚂蚁在本次循环中留在路径 上的信息量； 为本次循环中ij ),(jiij路径 上的信息量的增量；参数 为轨迹的持久性； 为轨迹衰减度，表示信),( 1息消逝程度。对上述系统模型，采用人工蚁群方法求解的算法步骤可归结为：step 1： （ 为迭代步数或搜索次数） ；各 和 的初始化；将0NCijij个蚂蚁置于 个顶点上。mnstep 2：将各蚂蚁的初始出发点置于当前解集中；对每个蚂蚁 （ ）km,21按概率 转移至下一顶点 ；将顶点 置于当前解集。k
25、ijpjjstep 3：计算各蚂蚁的目标函数值 ，记录当前的最好解。),1(mkzstep 4：按更新方程修改轨迹强度。step 5： ，若 预定的迭代次数且无退化行为（即找到的都是1NC相同解） ，则转 step 2。若为了简化计算，增加处理较大规模的 TSP 问题的能力，则可将（ 4）式修改为：，ijijij tt )()1( )1,0(其中-279-其 它 ,0)(1BEjidijkij此处 为本次最优路线上的边集。BE3.3 人工蚁群算法性能的讨论人工蚁群算法是一种基于种群的进化算法。作为一个新兴的研究领域，虽它还远未像 GA、SA 等算法那样形成系统的分析方法和坚实的数学基础，但目前
26、已有一些基本结果。在 M. Dorigo 三种不同的模型中，循环路径 上信息量的增量 不同。),(ji ij1）Ant-quantity system 模型中，其 它 之 间 经 过和只 蚂 蚁 在 时 刻若 第 ,01ijtkdQijkij2）在 Ant-density system 模型中，其 它 之 间 经 过和只 蚂 蚁 在 时 刻若 第 , ijtkkij3）在 Ant-cycle system 模型中，其 它 过只 蚂 蚁 在 本 次 循 环 中 经若 第 ,0ijkLQkij其中 是反映蚂蚁所留轨迹数量的常数， 表示第 只蚂蚁在本次循环中所走路径的kL长度；且 时， ， 。算法中模型 1） 、2）利用的是局部信息，tckij)(0kij模型 3）利用的是整体信息。人工蚁群算法中， 等参数对算法性能也有很大的影响。 值的大小表明Q,留在每个结点上的信息量受重视的程度， 值越大，蚂蚁选择以前选过的点的可能性越大，但过大会使搜索过早陷于局部极小点； 的大小表明启发式信息受重视的程度；值会影响算法的收敛速度， 过大会使算法收敛于局部极小值，过小又会影响算法Q的收敛速度，随问题规模的增大 的值也需要随之变化；蚂蚁的数目越多，算法的全局搜索能力越强，但数目加大将使算法的收敛速度减慢。
