四川大学MATLAB基础与应用课件-第11-12章蚁群算法的仿真与实现

第11章

蚁群算法的仿真与实现蚁群算法是近年来兴起的一种新型仿生优化算法，具有其他进化算法不可比拟的优势。该算法是继神经网络、遗传算法、模拟退火算法、粒子群算法、免疫算法等仿生搜索算法以后的又一种应用于组合优化问题的启发式搜索算法。由于蚁群算法采用分布式并行计算机制，具有较强的鲁棒性，容易与其它算法结合等优点，一经提出，立即受到各个领域学者的重视，展开了对其的研究。目前蚁群算法已经被广泛的应用于求解旅行商问题，自动组卷系统问题等等、本章则对于这两个问题做出了详细的阐述。四川大学《MATLAB基础与应用》11.1

蚁群算法介绍生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，看起来没有集中的指挥，但它们却能协同工作，集中食物，建起坚固漂亮的蚁穴并抚养后代，依靠群体能力发挥出超出个体的智能。蚁群算法(ant

colony

optimization,ACO)是最新发展的一种模拟昆虫王国中蚂蚁群体智能行为的仿生优化算法。它具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法相结合等优点尽管蚁群算法的严格理论基础尚未奠定，国内外的相关研究还处于实验探索和初步应用阶段，但是目前人们对蚁群算法的研究已经由当初单一的旅行商问题(traveling

salesman

problem，TSP)领域渗透到了多个应用领域，由解决一维静态优化问题发展到解决多维动态组合优化问题，由离散域范围内的研究逐渐拓展到了连续域范围内的研究，而且在蚁群算法的硬件实现上也取得了很多突破性的研究进展，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的发展前景。蚁群算法是从自然界中真实蚂蚁觅食的群体行为得到启发而提出的，其很多观点都来源于真实蚁群，因此算法中所定义的人丁蚂蚁与真实蚂蚁存在如下共同点。都存在一个群体中个体相互交流通信的机制都要完成一个相同的任务利用当前信息进行路径选择的随机选择策略在从真实蚁群行为获得启发而构造蚁群算法的过程中，人工蚂蚁还具备了真实蚂蚁所不具有的一些特性：人工蚂蚁存在于一个离散的空间中，它们的移动是从一个状态到另一个状态

的转换；人工蚂蚁具有一个记忆其本身过去行为的内在状态；人工蚂蚁存在于一个与时间无关联的环境之中；人工蚂蚁不是完全盲从的，它还受到问题空间特征的启发。例如有的问题中

人工蚂蚁在产生一个解后改变信息量，而有的问题中人工蚂蚁每作出一步选择

就更改信息量，但无论哪种方法，信息量的更新井不是随时都可进行的；为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测未来、局部优

化、回退等，这些行为在真实蚂蚁中是不存在的。在很多具体应用中，人工蚂

蚁可在局部优化过程中相互交换信息，还有一些改进蚁群算法中的人工蚂蚁可

实现简单预测。11.2

蚁群算法原理11.2.1

蚁群行为描述根据仿生学家的长期研究发现：蚂蚁虽没有视觉，但运动时会通过在路径上释放出一种特殊的分泌物——信息素来寻找路径。当它们碰到～个还没有走过的路口时，就随机地挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口的时候，选择信息量较大路径的概率相对较大，这样便形成了一个正反馈机制。最优路径上的信息量越来越大，而其他路径上的信息量却会随着时间的流逝而逐渐消减，最终整个蚁群会找出最优路径。同时蚁群还能够适应环境的变化，当蚁群的运动路径上突然出现障碍物时，蚂蚁也能很快地重新找到最优路径。可见，在整个寻径过程中，虽然单只蚂蚁的选择能力有限，但是通过信息素的作用使整个蚁群行为具有非常高的自组织性，蚂蚁之间交换着路径信息，最终通过蚁群的集体自催化行为找出最优路径。模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入的，该算法基于如下基本假设：蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境做出反应，也只对其周围的局部环境产生影响。蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其基因的适应性表现，即蚂蚁是反应型适应性主体。在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。11.2.2

基本蚁群算法的机制原理由于蚁群算法是对自然界中真实蚂蚁觅食行为的一种模拟，是一种机理上的应用，因此首先必须对真实蚂蚁进行抽象，而不可能也没必要对蚂蚁个体进行完全再现。抽象的目的就是为了能够更加有效地刻画出真实蚁群中能够为算法所借鉴的机理，同时摒弃与建立算法模型无关的因素。这样抽象出来的人工蚂蚁可以看做是一个简单的智能体，能够完成所求问题简单解的构造过程，也能通过一种通信手段相互影响。11.2.3对蚂蚁个体的抽象自然界中的真实蚂蚁存在于一个三维的环境中，而问题空间的求解一般是在平面内进行的，因此需要将蚂蚁觅食的三维空间抽象为一个平面。这一点比较容易理解，因为蚂蚁觅食所走的路径本来就存在于一个二维空间（平面或者曲面）上。另外一个问题是真实蚂蚁是在一个连续的二维平面中行走的，而我们无法用计算机直接来完整的描述一个连续的平面，因为计算机处理的是离散事件，因此必须将连续的平面离散化由一组点组成的离散平面，人工蚂蚁可在抽象出来的点上自由运动。这个抽象过程的可行性在于，尽管蚂蚁是在连续平面行动，但其行动经过的总是离散点，因此抽象过程只是提高了平面点离散分布的粒度，与其觅食行为的本身机理没有任何冲突。基于上述分析，很容易得到蚁群算法所求解的问题空间可用一个重要的数学工具——图(graph)来描述。在工程实际中的很多问题都可以用图来描述，这便使蚁群算法的广泛应用成为可能。11.2.4

问题空间的描述真实蚂蚁在觅食过程中主要按照所处环境中的信息量来决定其前进的方向，而人工蚂蚁是在平面的节点上运动的，因此可把觅食过程抽象成算法中解的构造过程，将信息素抽象为存在于图的边上的轨迹。在每一节点，人工蚂蚁感知连接该节点与相邻节点边上的信息素轨迹浓度，并根据该浓度大小决定走向下一节点的概率。用任意两个节点分别表示蚂蚁的巢穴（初始节点）和食物源（目标节点），人工蚂蚁从初始节点按照一定状态转移概率选择下一节点，依此类推，最终选择行走到目标节点，这样便得到了所求问题的一个可行解。11.2.5

寻找路径的抽象自然界中的真实蚂蚁总是在所经路径上连续不断地留下信息素，而信息素也会随着时间的推移而连续不断地挥发。由于计算机处理的事件只能是离散事件，所以必须使信息素的挥发离散发生。通常的做法是，当蚂蚁完成从某一节点到下一节点的移动后，即经过一个时间单位之后，进行一次信息素的挥发，而这种在离散时间点进行信息素挥发的方式与蚂蚁觅食过程的机理是完全相符的。11.2.6

信息素挥发的抽象以上几点是对真实蚂蚁觅食行为的抽象，整个过程体现了蚁群算法的自组织性，但是这种自组织系统存在一个缺陷，即系统的演化需要耗费较长的时间。而实际应用时对算法运行时间的要求也是必不可少的，因此在决定蚂蚁行走方向的状态转移概率时，引入了一个随机搜索的过程，即引入了启发因子，根据所求问题空间的具体特征，给蚁群算法一个初始的引导，这个过程极大地增加了算法的时间有效性，从而使蚁群算法的有效应用成为可能。以上几点是对真实蚂蚁觅食行为的抽象，整个过程体现了蚁群算法的自组织性，但是这种自组织系统存在一个缺陷，即系统的演化需要耗费较长的时间。而实际应用时对算法运行时间的要求也是必不可少的，因此在决定蚂蚁行走方向的状态转移概率时，引入了一个随机搜索的过程，即引入了启发因子，根据所求问题空间的具体特征，给蚁群算法一个初始的引导，这个过程极大地增加了算法的时间有效性，从而使蚁群算法的有效应用成为可能。11.2.7

启发因子的引入蚁群算法具有很强的自学习能力，可根据环境的改变和过去的行为结果对自身的知识库或自身的组织结构进行再组织，从而实现算法求解能力的进化，而这种进化是环境变化与算法自学习能力交互作用的产物，同时算法机理的复杂性和环境变化的不确定性进一步增加了蚁群算法的不可预测性。11.3

基本蚁群算法的数学模型设hi(t)表示t时刻位于元素i的蚂蚁数目，Гij(t)为，时刻路径(i,j)上的信息量，

n表示TSP规模，m为蚁群中蚂蚁的总数目，则是t时刻集合C中元素（城市）两两连接lij上残留信息量的集合。在初始时刻各条路

径上信息量相等，并设rij(0)=const，基本蚁群算法的寻是通过有向图g=(C,L,Г)实现的。蚂蚁k(k=l,2,…,m)在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表tabuk(k=l,2,…,m)来记录蚂蚁k当前所走过的城市，集合随着tabuk进化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。pkij(t)表示在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率式中，allowedk=(C-tabuk）表示蚂蚁k下一步允许选择的城市；α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过

程中所积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂

蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间协作性越强；β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动

过程中启发信息在蚂蚁选择路径中的受重视程度，其值越大，则

该状态转移概率越接近于贪心规则；ηij(t)为启发函数，其表达式如下式中，dij表示相邻两个城市之间的距离。对蚂蚁k而言，dij越小，则ηij(t)越大，pkij(t)也就越大。显然，该启发函数表示蚂蚁从元素（城市）j转移到元素（城市）j的期望程度。为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历（也即一个循环结束）后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存人大脑的同时，存储在大脑中的旧信患随着时间的推移逐渐淡化，甚至忘记。由此，

t+n时刻在路径(i,j)上的信息量可按如下规则进行调整式中，ρ表示信息素挥发系数，则1-ρ表示信息素残留因子，为了防止信息的无限积累，ρ的取值范围为：ρ⊂[0,1]；ΔГij(t)表示本次循环中路径(i,j)上的信息素增量，初始时刻ΔГij(0)=0，ΔГijk(t)表示第k只蚂蚁在本次循环中留在路径

(I,j)上的信息量。根据信息素更新策略的不同，Dorigo

M提出了三种不同的基本蚁群算法模型，分别称之为Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型，其差别在于

ΔГijk(t)求法的不同。在Ant-Cycle模型中式中，Q表示信息强度，它在一定程度上影响算法的收敛速度；Lk表示第k只蚂蚁在本次循环中所走路径的总长度。在Ant-Quantity模型中在Ant-Density模型中Ant-Quantity模型和Ant-Density模型中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素；而Ant-Cycle模型中利用的是整体信息，即蚂蚁完成一个循环后更新所有路径上的信息素，在求解TSP时性能较好，因此通常采用此方法作为蚁群算法的基本模型。11.4基本蚁群算法的实现步骤以TSP为例，基本蚁群算法的具体实现步骤如下：参数初始化。令时间t=0和循环次数Nc=0，设置最大循环次数Nc

max，将m蚂蚁置于n个元素（城市）上，令有向图上每条边(i,j)的初始化信息量

Гij(t)=const，其中const表示常数，且初始时刻△Гij(0)=0。循环次数Nc←Nc+1。蚂蚁的禁忌表索引号k=l。(4)蚂蚁数目k←k+1。(5)蚂蚁个体根据状态转移概率公式计算的概率选择元素（城市）j并前进，j∈{C-tabuk）。修改禁忌表揩针，即选择好之后将蚂蚁移动到新的元素（城市），并把该元素（城市）移动到该蚂蚁个体的禁忌表中。若集合C中元素（城市）未遍历完，即k<m，则跳转到第(4)步，否则执行第(8)步。根据更新每条路径上的信息量。(9)若满足结束条件，即如果循环次数Ne≥Nc

max，则循环结束并输出程序计算结果，否则清空禁忌表并跳转到第(2)步。11.5用蚁群算法建模求解智能组卷系统问题表示第i道试题的难题，m表示试卷的总题式中，表示第i题的分值，量。11.5.1

试卷质量评价的指标体系构建试卷指标体系是指试卷一些重要参数，是对试卷的特征和功能进行定性的或定量的描述，因此试卷的指标系统是实现计算机自动组卷的关键。（1）试卷的平均难度试卷难度是指测试的全体学生在该试卷上的失分率，用符号D表示。试卷难度的计算公式为：（2）试卷区分度试卷分度称之为试卷鉴别力，用来衡量试卷对参加测试的不同能力水平学生的区分程度，用符号P表示，其计算公式如下：式中，表示考生的高分得分率，该试卷区分能力越强。（3）试卷的信度表示考生低分得分率，P越大表示试卷信度指测试结论与数据的可靠性程度，是衡量试卷质量稳定性和可靠性的重要指标，采用如下的估计方法：式中，n表示题总数，表示考试总分的方差，表示题目i的通过率，r表示信度系统。（1）自动组卷系统的数学模型描述自动组卷是指计算机从题库中选取一定数量的试题组成试卷，使试卷既能满足考查要求又能满足用户要求。设一份试卷所含的试题数为m，每一道试题有n个属性指标，则一份试卷就是一个m×n矩阵，即：11.5.2

自动组卷系统的数学模型（2）自动组卷问题的目标函数根据计算机组卷的数学模型可知，自动组卷问题是一个典型的多目标优化问题，其通过利用单目标函数的优化方法对其求解。本文采用目标加权法来对自动组卷进行建模，其基本思想是给每一个目标一个权重，将所有的目标分量乘上各自相应的权重系数，然后再加起来构成一个新的目标函数，具体为：式中，最后得到组卷问题的具体目标函数为：其中，表示权重系数。自动组卷问题的蚁群算法设计试卷编码方式适应度函数设计试卷编码方式

状态转移概率蚁群算法的自动组卷过程▲设置试卷的组卷要求。▲蚁群和路径的初始化。所有试题路径上的初始信息素0；初始时间t＝0。▲将所有蚂蚁从试题库随机选择一个试题编号放入相对应的禁忌列表中，令蚂蚁的禁忌表的索引号为1。▲循环次数加1。▲蚂蚁个体根据状态转移概率公式来来选择下一步应该选择的试题编号。▲将选择好之后的蚂蚁移到新试题上，并将该试题编号插入到禁忌表中，并修改禁忌表的索引号。▲将每个蚂蚁所抽出的试题与用户输入的要求进行对比，如果满足要求，得到一套试卷。▲信息素局部和全部更新。▲结束条件判断，如果满足结束条件，则输入最优试卷，否则跳转到步骤3，继续组卷。11.5.3

蚁群算法的自动组卷问题求解本章详细介绍了蚁群算法的算法核心，并对其原理进行了深刻的剖析，讲解了基本蚁群算法的数学模型，通过两个实例问题进行了应用和实践。旅行商问题中通过MATLAB的实现给出了算法运行的最优结果、最差结果、平均结果及运行时间与结果图。为在其他领域中的应用和进一步的改进提供了基础。自动组卷系统问题中充分利用了蚁群算法群体智能特点，提高了组卷效率和成功率，具有很强的实用性，很好满足自动组卷的实时性。在机计算机辅助考试中有着广泛的应用前景。11.6

本章总结模拟退火算法（Simulated

Annealing

algorithm，简称SA）是柯克啪垂克于1982年受热力学中的固体退火过程与组合优化问题求解之间的某种“相似性”所启发而提出的，用于求解大规模组合优化问题的一种具有全局搜索功能的随机性近似算法。与求解线性规划的单纯形法、Karmarkar投影尺度法，求解非线性规划的最速下降法、Newton法、共轭梯度法，求解整数规划的分支定界法、割平面法等经典的优化算法相比，模拟退火算法在很大程度上不受制于优化问题的具体形式和结构，具有很强的适应性和鲁棒性，因而也具有广泛的应用价值。本章我们将学习模拟退火算法的matlab实现；运用模拟退火算法解决相关实际问题第12章 模拟退火算法的仿真与实现与实现12.1.1物理退火过程固体退火是先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程。退火过程是系统在每一温度下达到平衡的过程可以用封闭系统的等温过程来描述。由Boltzmann有序性原理，退火过程遵循热平衡封闭系统的热力学定律——自由能减少定律：对于与周围环境交换能量而温度保持不变的封闭系统，系统状态的自发变化总是朝着自由能减少的方

向进行当自由能达到最小值时，系统达到平衡态。设E为系统的微观状态的能量，则系统处在状态i的概率为：其中A是无关的常数。(2)式Gibbs正则分布.。该分布给出温度T时固体处于能量的微观态i的概率。显然，固体处于能量较低的微观态概率大，在温度降低时，那些能量相对较低的微观态最有可能出现。当温度趋于零时，固体基本上只能处于能量为最小值的基态。12.1.2

Metropolis准则固体在恒定温度下达到平衡的过程可以用MonteCarl方法加以模拟，该方法虽然简单，但必须大量采样才能得到比较精确的结果，因而计算量很大。1953年，Metropolis等提出了重要性采样法，即以概率接受新状态。具体而言：在温度为T，由当前状态i产生新状态j，两者的能量分别为

和

，若

<则接受新产状态j为当前状态；否则，若概率大于[0,1]区间内的随机数接受新状态J为当前状态，若不成立则保留状态i为当前状态。当这种过程多次重复，即经过大量迁移后系统趋于能量较低的平衡态，固体状态的概率分布趋于(2)式的Gibbs分布。上述接受新状态的准则称为Metropolis准则，相应的算法称为Metropolis算法，这种算法的计算显著减少。12.1.3

模拟退火算法介绍模拟退火算法(Simulated

Annealing，SA)最早由Kirkpatrick等应用于组合优化领域，它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、生产调度、控制工程、机器学习、神经网络、信号处理等领域。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。12.1.4

模拟退火算法要素状态空间与状态产生函数（邻域函数）搜索空间也称为状态空间，它由经过编码的可行解的集合组成。状态产生函数（邻域函数）应尽可能保证产生候选解遍布全部解空间。通常由俩部分组成，即产生候选解产生的概率分布。候选解一般采用按照某一概率密度函数对解空间进行随机采样来获得。概率分布可以是均匀分布，正太分布，指数分布等等。状态转移概率（接受概率）状态转移概率是指从一个状态向另一个状态的转移概率；通俗的理解是接受一个新解为当前解的概率；它与当前的温度参数T有关，随温度参数T有关，随温度下降而减小。一般采用Metropolis准则。3.冷却进度表T(t)冷却进度表是指从某一高温状态T(t)来表示，则经典模拟退火算法的降温方式为：而快速模拟退火算法的降温方式为：这俩种方式都能够使得模拟退火算法收敛于全局最小点。实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：均匀抽样一组状态，以各状态目标值的方差初温。随机产生一组状态，确定倆状态间的最大目标值差

，然后依据差值，利用一定的函数确定初温。比如，

其中

为初始接受概率。利用经验公式给出。内循环终止准则或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。常用的抽样稳定准则包括：检验目标函数的均值是否稳定；连续若干步的目标值变化较小；按一定的步数抽样。外循环终止准则即算法终止准则，常用的包括：设置终止温度的阈值；设置外循环迭代次数；算法搜索到的最优值连续若干步保持不变；检验系统熵是否稳定。12.1.5模拟退火算法流程图见下图：12.2.1模拟退火算法基本内容初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L对k=1，……，L做第(3)至第6步：产生新解S1计算增量

，其中

为评价函数。若

则接受s1作为新的当前解否则以概率

，接受S1作为新的当前解。如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。T逐渐减少，且T->0，然后转第2步。#include

"stdafx.h"/*

MIN[f(x,y)=5sin(xy)+x^2+y^2]*/#include

<math.h>#include

<stdio.h>#include

<string.h>#include

<stdlib.h>#include

<time.h>/*

Objective

Function

*/double

objectfunction(double

x,double

y){double

z=0.0;z=5.0*sin(x*y)+x*x+y*y;return

z;}/*

Random

Number

from

0

to

1

*/double

rnd(){double

r;r=(double)

rand()/RAND_MAX;return

r;}int

main(){int

i;int

markovlength=10000;//马可夫链double

decayscale=0.95;//衰减参数double

stepfactor=0.02;//Metropolis的步长double

temperature=100;//初始温度double

tolerance=1e-8;//容差

double

prex,nextx;double

prey,nexty;double

prebestx,prebesty;double

bestx,besty;double

acceptpoints=0.0;//Metropolis过程中总接受点double

xmax,ymax;

time_t

t;srand((unsigned)

time(&t));printf("The

Max

Number

X

is:\n");scanf("%lf",

&xmax);printf("The

Max

Number

Y

is:\n");scanf("%lf",

&ymax);printf("xmax=%f,ymax=%f\n",xmax,ymax);prex=-xmax*rnd();prey=-ymax*rnd();prebestx=bestx=prex;prebesty=besty=prey;do{temperature*=decayscale;acceptpoints=0.0;for(i=0;i<markovlength;i++){do{//在此点附近随机选下一点nextx=prex+stepfactor*xmax*(rnd()-0.5);//随机数在正负0.5之间

nexty=prey+stepfactor*ymax*(rnd()-0.5);}while(!(nextx>=-xmax

&&

nextx<=xmax

&&

nexty>=-ymax

&&

nexty<=ymax));if

(objectfunction(bestx,besty)>objectfunction(nextx,nexty))//是否全局最优解{//保留上一个最优解prebestx=bestx;prebesty=besty;//此为新的最优解bestx=nextx;besty=nexty;}//Metropolis过程if

(objectfunction(prex,prey)>objectfunction(nextx,nexty)){//接受,此处lastPoint即下一个迭代的点以新接受的点开始prex=nextx;prey=nexty;acceptpoints++;}else{doublechange=(objectfunction(prex,prey)-objectfunction(nextx,nexty))/temperature;if(exp(change)>rnd()){prex=nextx;prey=nexty;acceptpoints++;}//不接受,保存原解}}}while(fabs(objectfunction(bestx,besty)-objectfunction(prebestx,prebesty))>tolerance);printf("abs=%g\n",fabs(objectfunction(bestx,besty)-objectfunction(prebestx,prebesty)));printf("%f,%f,%f,%f\n",prex,prey,objectfunction(prex,prey),temperature);printf("The

Min

points

is:%lf,%lf\n",bestx,besty);printf("The

Min

data

is:%lf\n",objectfunction(bestx,besty));getchar();getchar();}12.2.2模拟退火的算法描述模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火

算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的

最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会

到达D点，于是就跳出了局部最大值A。图1：关于爬山算法与模拟退火，有一个有趣的比喻：爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。在模拟退火算法中应注意以下问题：理论上，降温过程要足够缓慢，要使得在每一温度下达到热平衡。但在计算机实现中，如果降温速度过缓，所得到的解的性能会较为令人满意，但是算法会太慢，相对于简单的搜索算法不具有明显优势。如果降温速度过快，很可能最终得不到全局最优解。因此使用时要综合考虑解的性能和算法速度，在两者之间采取一种折衷。要确定在每一温度下状态转换的结束准则。实际操作可以考虑当连续m次的转换过程没有使状态发生变化时结束该温度下的状态转换。最终温度的确定可以提前定为一个较小的值eT，或连续几个温度下转换过程没有使状态发生变化算法就结束。（3）选择初始温度和确定某个可行解的邻域的方法也要恰当。模拟退火算法的参数控制问题：模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主要问题有以下三点：温度T的初始值设置问题。温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。退火速度问题:模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。温度管理问题:温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：式中k为正的略小于1.00的常数，t为降温的次数。main.mzuobiao=[0.37

0.75

0.45

0.76

0.71

0.07

0.42

0.59

0.32

0.6

0.3

0.67

0.62

0.67

0.20

...0.35

0.27

0.94

0.82

0.37

0.61

0.42

0.6

0.39

0.53

0.4

0.63

0.5

0.98

0.68;0.91

0.87

0.85

0.75

0.72

0.74

0.71

0.69

0.64

0.64

0.59

0.59

0.55

0.55

0.5...0.45

0.43

0.42

0.38

0.27

0.26

0.25

0.23

0.19

0.19

0.13

0.08

0.04

0.02

0.85]plot(zuobiao(1,),zuobiao(2,),"g"),hold

onplot(zuobiao(1,),zuobiao(2,))length=max(size(zuobiao));%求初始距离..zhixu=randperm(length)

%随机生成一个路线经过点的顺序temp=zuobiao(1,);newzuobiao(1,)=temp(zhixu);temp=zuobiao(2,);newzuobiao(2,)=temp(zhixu);newzuobiaof=juli(newzuobiao)%参数定义区%初始温度为10000tmax=100;tmin=0.001;down=0.95;%退火算法的函数..

figuret=tmax;while

ttminfor

n=1500newzuobiao=newpath(zuobiao,length);newf=juli(newzuobiao);if

newffzuobiao=newzuobiao;f=newf;endendhuatu=[zuobiao,zuobiao(,1)];plot(huatu(1,),huatu(2,)),hold

onplot(huatu(1,),huatu(2,),"ro"),hold

offpause(0.00001)t=tdownendnewpath.mfunction

zuobiao=newpath(zuobiao,length)%随机交换两个点的坐标..a=ceil(rand(1,2)length);qian=a(1);hou=a(2);temp=zuobiao(,qian);zuobiao(,qian)=zuobiao(,hou);zuobiao(,hou)=temp;juli.m

function

lucheng=juli(zuobiao)length=max(size(zuobiao));s=0;for

i=2lengths=s+sqrt(sum((zuobiao(,i)-zuobiao(,i-1)).^2));endif

length~=2s=s+sqrt(sum((zuobiao(,1)-zuobiao(,length)).^2));endlucheng=s;12.2.3模拟退火算法的伪代码实现while(

T

>

T_min

){dE

=

J(

Y(i+1)

)

-

J(

Y(i)

)

;if(dE>=0)//表达移动后得到更优解，则总是接受移动Y(i+1)=Y(i);//接受从Y(i)到Y(i+1)的移动else{//函数exp(dE/T)的取值范围是(0,1)，dE/T越大，则exp(dE/T)也

if(exp(dE/T)>random(0,1))Y(i+1)=Y(i);//接受从Y(i)到Y(i+1)的移动}T=r

*

T;//降温退火，0<r<1。r越大，降温越慢；r越小，降温越快/**若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值*/i

++

;}12.2.4使用模拟退火算法解决旅行社问题旅行商问题(TSP,Traveling

Salesman

Problem)：有N个城市，要求从其中某个问题出发，唯一遍历所有城市，再回到出发的城市，求最短的路线。旅行商问题属于所谓的NP完全问题，精确的解决TSP只能通过穷举所有的路径组合，其时间复杂度是O(N!)。使用模拟退火算法可以比较快的求出TSP的一条近似最优路径。（使用遗传算法也是可以的）模拟退火解决TSP的思路：产生一条新的遍历路径P(i+1)，计算路径P(i+1)的长度L(P(i+1))若L(P(i+1))<L(P(i))，则接受P(i+1)为新的路径，否则以模拟退火的那个概率接受P(i+1)，然后降温重复步骤1，2直到满足退出条件产生新的遍历路径的方法有很多，下面列举其中3种：随机选择2个节点，交换路径中的这2个节点的顺序。随机选择2个节点，将路径中这2个节点间的节点顺序逆转。随机选择3个节点m，n，k，然后将节点m与n间的节点移位到节点k后面。Main.mclear

all;close

all;clcn=20;

%城市个数temperature=100*n;

%初始温度iter=100;

%内部蒙特卡洛循环迭代次数%随机初始化城市坐标city=struct([]);for

i=1:ncity(i).x=floor(1+100*rand());city(i).y=floor(1+100*rand());endl=1;

%统计迭代次数len(l)=computer_tour(city,n);

%每次迭代后的路线长度netplot(city,n);

%初始旅行路线while

temperature>0.001

%停止迭代温度for

i=1:iter

%多次迭代扰动，一种蒙特卡洛方法，温度降低之前多次实验len1=computer_tour(city,n);

%计算原路线总距离tmp_city=perturb_tour(city,n);

%产生随机扰动len2=computer_tour(tmp_city,n);

%计算新路线总距离delta_e=len2-len1;

%新老距离的差值，相当于能量

if

delta_e<0

%新路线好于旧路线，用新路线代替旧路线city=tmp_city;else

%温度越低，越不太可能接受新解；新老距离差值越大，越不太可能接受新解if

exp(-delta_e/temperature)>rand()%以概率选择是否接受新解city=tmp_city;

%可能得到较差的解endendendl=l+1;len(l)=