计算智能与深度学习 课件 7模拟退火算法、8禁忌搜索算法

第三章模拟退火算法

智能优化计算山东大学威海分校信息工程学院

2009年3.1模拟退火算法及模型

3.1.1物理退火过程

3.1.2组合优化与物理退火的相似性

3.1.3模拟退火算法的基本思想和步骤

3.2模拟退火算法的马氏链描述

3.2.1马尔可夫链

3.2.2模拟退火算法与马尔可夫链

3.3模拟退火算法的关键参数和操作的设计

3.3.1状态产生函数

3.3.2状态接受函数

3.3.3初温

3.3.4温度更新函数

3.3.5内循环终止准则

3.3.6外循环终止准则

智能优化计算山东大学威海分校信息工程学院

2009年3.4模拟退火算法的改进

3.4.1模拟退火算法的优缺点

3.4.2改进内容

3.4.3一种改进的模拟退火算法3.5模拟退火算法实现与应用

3.5.130城市TSP问题（d*=423.741byDBFogel）

3.5.2模拟退火算法在管壳式换热器优化设计中的应用智能优化计算山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算算法的提出

模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。

3.1.1物理退火过程山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算物理退火过程

什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。

3.1.1物理退火过程山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算物理退火过程

加温过程——增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程——对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程——使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。

3.1.1物理退火过程山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算数学表述

在温度T，分子停留在状态r满足Boltzmann概率分布

3.1.1物理退火过程山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算数学表述在同一个温度T，选定两个能量E1<E2，有在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。

3.1.1物理退火过程<1>0山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算数学表述

若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；当温度趋于0时，分子停留在最低能量状态的概率趋于1。

3.1.1物理退火过程能量最低状态非能量最低状态山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算Metropolis准则（1953）——以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。

3.1.1物理退火过程山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算Metropolis准则（1953）——以概率接受新状态若在温度T，当前状态i→新状态j

若Ej<Ei，则接受j为当前状态；否则，若概率p=exp[-(Ej-Ei)/kBT]

大于[0,1)区间的随机数，则仍接受状态j

为当前状态；若不成立则保留状态i

为当前状态。

3.1.1物理退火过程山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算Metropolis准则（1953）——以概率接受新状态

p=exp[-(Ej-Ei)/kBT]

在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。

3.1.1物理退火过程山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算相似性比较

3.1.2组合优化与物理退火的相似性组合优化问题金属物体解粒子状态最优解能量最低的状态设定初温熔解过程Metropolis抽样过程等温过程控制参数的下降冷却目标函数能量山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算基本步骤

给定初温t=t0，随机产生初始状态s=s0，令k=0；

RepeatRepeat

产生新状态sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；

Until算法终止准则满足；输出算法搜索结果。

3.1.3模拟退火算法的基本思想和步骤山东大学威海分校信息工程学院2009年3.1模拟退火算法及模型

智能优化计算影响优化结果的主要因素

给定初温t=t0，随机产生初始状态s=s0，令k=0；

RepeatRepeat

产生新状态sj=Genete(s)；

ifmin{1,exp[-(C(sj)-C(s))/tk]}>=randrom[0,1]s=sj;Until抽样稳定准则满足；退温tk+1=update(tk)并令k=k+1；

Until算法终止准则满足；输出算法搜索结果。

3.1.3模拟退火算法的基本思想和步骤三函数两准则初始温度山东大学威海分校信息工程学院2009年3.2模拟退火算法的马氏链描述

智能优化计算定义

3.2.1马尔科夫链特性：马氏链具有记忆遗忘特性，它只记忆前一时刻的状态。山东大学威海分校信息工程学院2009年3.2模拟退火算法的马氏链描述

智能优化计算定义

一步转移概率：

n步转移概率：若解空间有限，称马尔可夫链为有限状态；若，称马尔可夫链为时齐的。

3.2.1马尔科夫链山东大学威海分校信息工程学院2009年3.2模拟退火算法的马氏链描述

智能优化计算模拟退火算法对应了一个马尔可夫链

模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为时齐算法；若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。分析收敛性

3.2.2模拟退火算法与马尔科夫链山东大学威海分校信息工程学院2009年3.3模拟退火算法关键参数和操作的设计智能优化计算原则

产生的候选解应遍布全部解空间方法

在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生

3.3.1状态产生函数山东大学威海分校信息工程学院2009年3.3模拟退火算法关键参数和操作的设计智能优化计算原则

(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；

(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；

(3)当温度趋于零时，只能接受目标函数下降的解。方法

具体形式对算法影响不大一般采用min[1,exp(-∆C/t)]

3.3.2状态接受函数山东大学威海分校信息工程学院2009年3.3模拟退火算法关键参数和操作的设计智能优化计算收敛性分析

通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；初温应充分大；实验表明

初温越大，获得高质量解的机率越大，但花费较多的计算时间；

3.3.3初温山东大学威海分校信息工程学院2009年3.3模拟退火算法关键参数和操作的设计智能优化计算方法

（1）均匀抽样一组状态，以各状态目标值得方差为初温；（2）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；（3）利用经验公式。

3.3.3初温山东大学威海分校信息工程学院2009年3.3模拟退火算法关键参数和操作的设计数值计算估计方法示例智能优化计算山东大学威海分校信息工程学院2009年3.3模拟退火算法关键参数和操作的设计智能优化计算时齐算法的温度下降函数

（1），α越接近1温度下降越慢，且其大小可以不断变化；（2），其中t0为起始温度，K为算法温度下降的总次数。

3.3.4温度更新函数山东大学威海分校信息工程学院2009年3.3模拟退火算法关键参数和操作的设计智能优化计算非时齐模拟退火算法

每个温度下只产生一个或少量候选解时齐算法——常用的Metropolis抽样稳定准则

（1）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；（3）按一定的步数抽样（固定长度）。 （4）有接受和拒绝的比率控制跌代步数（比如给定一个跌代步长上限U和接受比率指标R）

3.3.5内循环终止准则山东大学威海分校信息工程学院2009年3.3模拟退火算法关键参数和操作的设计智能优化计算常用方法

（1）设置终止温度的阈值；（2）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；（4）概率分析方法(接受概率控制法）。

3.3.6外循环终止准则山东大学威海分校信息工程学院2009年3.4模拟退火算法的改进智能优化计算模拟退火算法的优点

质量高；初值鲁棒性强；简单、通用、易实现。模拟退火算法的缺点

由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。

3.4.1模拟退火算法的优缺点山东大学威海分校信息工程学院2009年3.4模拟退火算法的改进智能优化计算改进的可行方案

（1）设计合适的状态产生函数；（2）设计高效的退火历程；（3）避免状态的迂回搜索；（4）采用并行搜索结构；（5）避免陷入局部极小，改进对温度的控制方式；（6）选择合适的初始状态；（7）设计合适的算法终止准则。

3.4.2改进内容山东大学威海分校信息工程学院2009年3.4模拟退火算法的改进智能优化计算改进的方式

（1）增加升温或重升温过程，避免陷入局部极小；（2）增加记忆功能（记忆“Bestsofar”状态）；（3）增加补充搜索过程（以最优结果为初始解）；（4）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；（5）结合其它搜索机制的算法；（6）上述各方法的综合。

3.4.2改进内容山东大学威海分校信息工程学院2009年3.4模拟退火算法的改进智能优化计算改进的思路

（1）记录“Bestsofar”状态，并即时更新；（2）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续m1步保持不变则认为Metropolis抽样稳定，若连续m2次退温过程中所得最优解不变则认为算法收敛。

3.4.3一种改进的模拟退火算法山东大学威海分校信息工程学院2009年3.4模拟退火算法的改进智能优化计算改进的退火过程

（1）给定初温t0，随机产生初始状态s，令初始最优解s*=s，当前状态为s(0)=s，i=p=0；（2）令t=ti，以t，s*和s(i)调用改进的抽样过程，返回其所得最优解s*’和当前状态s’(k)，令当前状态s(i)=s’(k)；（3）判断C(s*)<C(s*’)?若是，则令p=p+1；否则，令s*=s*’，p=0；（4）退温ti+1=update(ti)，令i=i+1；（5）判断p>m2?若是，则转第(6)步；否则，返回第(2)步；（6）以最优解s*作为最终解输出，停止算法。

3.4.3一种改进的模拟退火算法山东大学威海分校信息工程学院2009年3.4模拟退火算法的改进智能优化计算改进的抽样过程

（1）令k=0时的初始当前状态为s’(0)=s(i)，q=0；（2）由状态s通过状态产生函数产生新状态s’，计算增量∆C’=C(s’)-C(s)；（3）若∆C’<0，则接受s’作为当前解，并判断C(s*’)>C(s’)?若是，则令s*’=s’，q=0；否则，令q=q+1。若∆C’>0，则以概率exp(-∆C’/t)接受s’作为下一当前状态；（4）令k=k+1，判断q>m1?若是，则转第(5)步；否则，返回第(2)步；（5）将当前最优解s*’和当前状态s’(k)返回改进退火过程。

3.4.3一种改进的模拟退火算法山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算

3.5.130城市TSP问题（d*=423.741byDBFogel）

TSPBenchmark问题

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算算法流程

3.5.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算初始温度的计算

fori=1:100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0))/log(0.9);

3.5.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算状态产生函数的设计（1）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。

3.5.130城市TSP问题（d*=423.741byDBFogel）

283591467283591467283591467281593467283419567235981467山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算参数设定

截止温度tf=0.01;

退温系数alpha=0.90;

内循环次数L=200*CityNum;

3.5.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算运行过程

3.5.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算运行过程

3.5.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算运行过程

3.5.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算运行过程

3.5.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算运行过程

3.5.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算运行结果

3.5.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算换热器模型两级管壳式换热器组成的换热器系统，数学模型高度非线性，其目标函数通常是多峰(谷)的，具有很多局部最优解。

3.5.2模拟退火算法在管壳式换热器优化设计中的应用山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算优化目标以换热器系统的总费用年值最小作为优化设计的目标。其中，f1(X)是两级换热器的初始投资，f2(X)是两级换热器年维护费(包括除垢、保养、维修等)，f3(X)是冷却水资源费以及管程压降能耗费，f4(X)是壳程压降能耗费。

3.5.2模拟退火算法在管壳式换热器优化设计中的应用山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算优化目标经过分析，优化问题的独立变量共12个，分别是一级换热器煤油出口温度t2、冷却水流量G1、两个换热器的管内径d1，d2和管间距S1，S2、折流板间距B1，B2、折流板开口角α1，α2、单管长度L1，L2。

3.5.2模拟退火算法在管壳式换热器优化设计中的应用山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算应用模拟退火算法解决优化设计状态表示——12个变量的实数表示；初始温度——100；结束温度——0.001；状态产生函数——，η为扰动幅度参数，ξ为随机扰动变量，随机扰动可服从柯西、高斯、均匀分布。降温因子——0.98；马氏链长度——1200。

3.5.2模拟退火算法在管壳式换热器优化设计中的应用山东大学威海分校信息工程学院2009年3.5模拟退火算法的实现与应用智能优化计算优化结果优化目标值——0.25565E＋06

独立变量取值——

3.5.2模拟退火算法在管壳式换热器优化设计中的应用t2℃G1Kg/sd1mmS1mmB1mα1弧度64.419415.9716615.5716334.097160.924361.93421L1md2mmS2mmB2mα2弧度L2m5.9423416.7793527.740120.729532.199285.78314山东大学威海分校信息工程学院2009年第三章结束智能优化计算山东大学威海分校信息工程学院2009年第二章禁忌搜索算法

智能优化计算山东大学威海分校信息工程学院20092.1局部搜索

2.1.1邻域的概念

2.1.2局部搜索算法

2.1.3局部搜索示例

2.2禁忌搜索

2.2.1算法的主要思路

2.2.2禁忌搜索示例2.3禁忌搜索的关键参数和操作

2.3.1变化因素

2.3.2禁忌表

2.3.3其他

2.4禁忌搜索的实现与应用

2.4.130城市TSP问题（d*=423.741byDBFogel）

2.4.2基于禁忌搜索算法的系统辨识智能优化计算山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算函数优化问题中

在距离空间中，通常的邻域定义是以一点为中心的一个球体；组合优化问题中

2.1.1邻域的概念

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算例

TSP问题解的一种表示方法为D={x=(i1,i2,…,in)|i1,i2,…,in是1,2,…,n的排列}，定义它的邻域映射为2－opt，即x中的两个元素进行对换，N(x)中共包含x的Cn2=n(n-1)/2个邻居和x本身。例如：x=(1,2,3,4)，则C42=6，N(x)={(1,2,3,4),(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3)}2.1.1邻域的概念

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算例

TSP问题解的邻域映射可由2－opt，推广到k－opt，即对k个元素按一定规则互换。邻域概念的重要性

邻域的构造依赖于决策变量的表示，邻域的结构在现代优化算法中起重要的作用。2.1.1邻域的概念

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算STEP1

选定一个初始可行解x0，记录当前最优解xbest:=x0,T=N(xbest)；STEP2

当T\{xbest}=Φ时，或满足其他停止运算准则时，输出计算结果，停止运算；否则，从T中选一集合S，得到S中的最好解xnow；若f(xnow)<f(xbest)，则xbest:=xnow

，T=N(xbest)；否则T:=T\S；重复STEP2。2.1.2局部搜索算法

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题

初始解为xbest=(ABCDE)，f(xbest)=45，定义邻域映射为对换两个城市位置的2-opt，选定A城市为起点。2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题方法1：全邻域搜索

第1步

N(xbest)={(ABCDE)，(ACBDE)，(ADCBE)，(AECDB)，(ABDCE)，(ABEDC)，(ABCED)}，对应目标函数为f(x)={45,43,45,60,60,59,44}

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

ABCDE山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题方法1：全邻域搜索

第2步

N(xbest)={(ACBDE)，(ABCDE)，(ADBCE)，(AEBDC)，(ACDBE)，(ACEDB)，(ACBED)}，对应目标函数为f(x)={43,45,44,59,59,58,43}

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题方法2：一步随机搜索

第1步

从N(xbest)中随机选一点，如xnow=(ACBDE)，对应目标函数为f(xnow)=43<45

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题方法2：一步随机搜索

第2步

从N(xbest)中又随机选一点，如xnow=(ADBCE)，对应目标函数为f(xnow)=44>43

xbest:=xnow=(ACBDE)2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算五个城市的对称TSP问题简单易行，但无法保证全局最优性；局部搜索主要依赖起点的选取和邻域的结构；为了得到好的解，可以比较不同的邻域结构和不同的初始点；如果初始点的选择足够多，总可以计算出全局最优解。2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题解（solution)的表示：向量五个任务分到三台计算机上的一种分配方安：2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域（Neighborhood）定义我们定义两种邻域映射：1、单向移动（one-waymoveortransfer):重新分配一个任务从其当前机器到另一台机器。2、双向移动（two-wayexchange):交换分配于两台不同机器上的任务。2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域解（Neighbor）评估（evaluation）对于目标1最小化执行与通信代价之和。任务重分配收益（reassignmentgain)就是代价（cost）的减少。

这里xip表示第i个任务在第p台机器上的执行代价（时间）2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域解（Neighbor）评估（evaluation）重新分配任务i之后，需要更新（update）第i个任务的邻接任务的重分配收益：2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域解（Neighbor）评估（evaluation）重新分配任务i之后，需要更新（update）第i个任务的邻接任务的重分配收益：2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域解（Neighbor）评估（evaluation）重新分配任务i之后，需要更新（update）第i个任务的邻接任务的重分配收益：2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题邻域解（Neighbor）评估（evaluation）重新分配任务i之后，需要更新（update）第i个任务的的重分配收益：2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题约束惩罚收益？2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.1局部搜索

智能优化计算TAP问题对于目标2，最小化周转时间（turnaroundtime)或者说最小化完成时间（completiontime)

邻域结构的定义：分流负载最终的机器（themostloadedmachine,i.e.criticalmachine):transferandexchange。2.1.3局部搜索示例

山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算算法的提出

禁忌搜索（Tabusearch）是局部邻域搜索算法的推广，FredGlover在1986年提出这个概念，进而形成一套完整算法。算法的特点禁忌——禁止重复前面的工作。跳出局部最优点。2.2.1算法的主要思路

/~glover/山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

初始解x0=(ABCD)，f(x0)=4，邻域映射为两个城市顺序对换的2－opt，始、终点都是A城市。2.2.2禁忌搜索示例

山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第1步解的形式禁忌对象及长度候选解

f(x0)=42.2.2禁忌搜索示例

ABCDBCDABC对换评价值CD4.5BC7.5BD8☻山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第2步解的形式禁忌对象及长度候选解

f(x1)=4.52.2.2禁忌搜索示例

ABDCBCDABC3对换评价值CD4.5BC3.5BD4.5☻T山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第3步解的形式禁忌对象及长度候选解

f(x2)=3.52.2.2禁忌搜索示例

ACDBBCDAB3C2对换评价值CD8BC4.5BD7.5☻TT山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第4步解的形式禁忌对象及长度候选解

f(x3)=7.5

禁忌长度的选取2.2.2禁忌搜索示例

ACBDBCDAB23C1对换评价值CD4.5BC4.5BD3.5TTT山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第4步（如果减小禁忌长度）解的形式禁忌对象及长度候选解

f(x3)=7.52.2.2禁忌搜索示例

ACBDBCDAB12C0对换评价值CD4.5BC4.5BD3.5☻TT山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第5步解的形式禁忌对象及长度候选解

f(x4)=4.52.2.2禁忌搜索示例

ADBCBCDAB01C2对换评价值CD7.5BC8BD4.5☻TT山东大学威海分校信息工程学院20092.2禁忌搜索

智能优化计算四城市非对称TSP问题

第6步解的形式禁忌对象及长度候选解

f(x5)=82.2.2禁忌搜索示例

ADCBBCDAB20C1对换评价值CD3.5BC4.5BD4☻TT山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌表的主要指标（两项指标）禁忌对象：禁忌表中被禁的那些变化元素禁忌长度：禁忌的步数状态变化（三种变化）解的简单变化解向量分量的变化目标值变化

2.3.1变化因素

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算解的简单变化

2.3.1变化因素

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算向量分量的变化

设原有的解向量为(x1,…,xi-1,xi,xi+1,…,xn)，向量分量的最基本变化为

(x1,…,xi-1,xi,xi+1,…,xn)→(x1,…,xi-1,yi,xi+1,…,xn)

即只有第i个分量发生变化。也包含多个分量变化的情形。2.3.1变化因素

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算目标值的变化

目标值的变化隐含着解集合的变化。2.3.1变化因素

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化禁忌长度为4，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45，H={(ABCDE;45)}。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化第1步——

xnow=(ABCDE)，f(xnow)=45，H={(ABCDE;45)}Can_N(xnow)={(ACBDE;43)，(ABCDE;45)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。2.3.2禁忌表

xnext=(ACBDE)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化第2步——

xnow=(ACBDE)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43)}Can_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。2.3.2禁忌表

xnext=(ACBED)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化第3步——

xnow=(ACBED)，f(xnow)=43，H={(ABCDE;45)，(ACBDE;43)，(ACBED;43)}Can_N(xnow)={(ACBED;43)，(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)}。2.3.2禁忌表

xnext=(ABCED)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化第4步——

xnow=(ABCED)，f(xnow)=44，H={(ABCDE;45)，(ACBDE;43)，(ACBED;43)，(ABCED;44)}Can_N(xnow)={(ACBED;43)，(AECBD;44)，(ABCDE;45)，(ABCED;44)，(ABDEC;58)}。2.3.2禁忌表

xnext=(AECBD)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况1：禁忌对象为简单的解变化第5步——

xnow=(AECBD)，f(xnow)=44，H={(ACBDE;43)，(ACBED;43)，(ABCED;44)，(AECBD;44)}Can_N(xnow)={(AEDBC;43)，(ABCED;44)，(AECBD;44)，(AECDB;44)，(AEBCD;45)}。2.3.2禁忌表

xnext=(AEDBC)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况2：禁忌对象为分量变化禁忌长度为3，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况2：禁忌对象为分量变化第1步——

xnow=(ABCDE)，f(xnow)=45，H=ΦCan_N(xnow)={(ACBDE;43)，(ADCBE;45)，(AECDB;60)，(ABEDC;59)，(ABCED;44)}。2.3.2禁忌表

xnext=(ACBDE)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况2：禁忌对象为分量变化第2步——

xnow=(ACBDE)，f(xnow)=43，H={(B,C)}Can_N(xnow)={(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)，(AEBDC;59)}。2.3.2禁忌表

xnext=(ACBED)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况2：禁忌对象为分量变化第3步——

xnow=(ACBED)，f(xnow)=43，H={(B,C)，(D,E)}Can_N(xnow)={(ACBDE;43)，(ABCED;44)，(AEBCD;45)，(ADBEC;58)，(ACEBD;58)}。2.3.2禁忌表

xnext=(AEBCD)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况3：禁忌对象为目标值变化禁忌长度为3，从2－opt邻域中选出最佳的5个解组成候选集Can_N(xnow)，初始解xnow=x0=(ABCDE)，f(x0)=45。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况3：禁忌对象为目标值变化第1步——

xnow=(ABCDE)，f(xnow)=45，H={45}Can_N(xnow)={(ABCDE;45)，(ACBDE;43)，(ADCBE;45)，(ABEDC;59)，(ABCED;44)}。2.3.2禁忌表

xnext=(ACBDE)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

情况3：禁忌对象为目标值变化第2步——

xnow=(ACBDE)，f(xnow)=43，H={45，43}Can_N(xnow)={(ACBDE;43)，(ACBED;43)，(ADBCE;44)，(ABCDE;45)，(ACEDB;58)}。2.3.2禁忌表

xnext=(ADBCE)山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌对象的选取

解的简单变化比解的分量变化和目标值变化的受禁范围要小，可能造成计算时间的增加，但也给予了较大的搜索范围；解分量的变化和目标值变化的禁忌范围大，减少了计算时间，可能导致陷在局部最优点。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌长度的选取

（1）t可以为常数，易于实现；（2），t是可以变化的数，tmin和tmax是确定的。

tmin和tmax根据问题的规模确定，t的大小主要依据实际问题、实验和设计者的经验。（3）tmin和tmax的动态选择。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算禁忌长度的选取禁忌长度过短，一旦陷入局部最优点，出现循环无法跳出；禁忌长度过长，造成计算时间较大，也可能造成计算无法继续下去。（例）2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算特赦（藐视）原则（1）基于评价值的规则，若出现一个解的目标值好于前面任何一个最佳候选解，可特赦；（2）基于最小错误的规则，若所有对象都被禁忌，特赦一个评价值最小的解；（3）基于影响力的规则，可以特赦对目标值影响大的对象。2.3.2禁忌表

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算候选集合的确定（1）从邻域中选择若干目标值最佳的邻居入选；（2）在邻域中的一部分邻居中选择若干目标值最佳的状态入选；（3）随机选取。2.3.3其他

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算评价函数（1）直接评价函数，通过目标函数的运算得到评价函数；（2）间接评价函数，构造其他评价函数替代目标函数，应反映目标函数的特性，减少计算复杂性。2.3.3其他

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算记忆频率信息根据记忆的频率信息（禁忌次数等）来控制禁忌参数（禁忌长度等）。例如：如果一个元素或序列重复出现或目标值变化很小，可增加禁忌长度以避开循环；如果一个最佳目标值出现频率很高，则可以终止计算认为已达到最优值。2.3.3其他

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算记忆频率信息可记录的信息：（1）静态频率信息：解、对换或目标值在计算中出现的频率；（2）动态频率信息：从一个解、对换或目标值到另一个解、对换或目标值的变化趋势。2.3.3其他

山东大学威海分校信息工程学院20092.3禁忌搜索的关键参数和操作

智能优化计算终止规则（1）确定步数终止，无法保证解的效果，应记录当前最优解；（2）频率控制原则，当某一个解、目标值或元素序列的频率超过一个给定值时，终止计算；（3）目标控制原则，如果在一个给定步数内，当前最优值没有变化，可终止计算。2.3.3其他

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算TSPBenchmark问题

4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;4502.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算算法流程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算初始条件禁忌长度为50

从2－opt邻域中随机选择200个邻域解，选出其中100个最佳解组成候选集终止步数20002.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.130城市TSP问题（d*=423.741byDBFogel）

山东大学威海分校信息工程学院20092.4禁忌搜索的实现与应用

智能优化计算运行过程

2.4.1