一些解决TSP问题的算法及源代码模拟退火算法

一些解决 TSP 问题的算法及源代码模拟退火算法

计算机算法交流区 搜一搜相关精彩主题 【大熊论坛】 → 【软件开发】 → 【算法世界】

→ 找到的一些解决 TSP 问题的算法及源代码

标题：找到的一些解决 TSP 问题的算法及源代码大熊

--------------------------------------------------------------------------------

找到的一些解决 TSP 问题的算法及源代码模拟退火算法

　　模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时

固体内部粒子随温升变为无序状，

解 i 和控制参数初值 t 开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭

代，并逐步衰减 t 值，算法终止时的

当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。

退火过程由冷却进度表(Cooling

Schedule)控制，包括控制参数的初值 t 及其衰减因子 Δt、每个 t 值时的迭代次数 L 和停止条

件 S。

3.5.1 模拟退火算法的模型

　　模拟退火算法可以分解为解空间、目标函数和初始解三部分。

　模拟退火的基本思想:

　　(1) 初始化：初始温度 T(充分大)，初始解状态 S(是算法迭代的起点)， 每个 T 值的迭

终止条件通常取为连续若干个新解都没有被接受时终止算法。

　　(7) T 逐渐减少，且 T->0，然后转第 2 步。

算法对应动态演示图：

模拟退火算法新解的产生和接受可分为如下四个步骤：

　　第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和

接受，减少算法耗时，通常选择由当

前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、

互换等，注意到产生新解的变换方法

决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。

　　第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以

事实表明，对大多数应用而言，这是计算目标函数差的最快方法。

　　第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是

Metropo1is 准则: 若 Δt′<0 则接受 S′作

为新的当前解 S，否则以概率 exp(-Δt′/T)接受 S′作为新的当前解 S。

解时的变换部分予以实现，同时修正

目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新

解被判定为舍弃时，则在原当前解的

3.5.2 模拟退火算法的简单应用

　　作为模拟退火算法应用，讨论货郎担问题(Travelling Salesman Problem，简记为 TSP)：

设有 n 个城市，用数码 1,…,n 代表

。城市 i 和城市 j 之间的距离为 d(i，j) i, j=1,…,n．TSP 问题是要找遍访每个域市恰好一次

的一条回路，且其路径总长度为最

短.。

　　求解 TSP 的模拟退火算法模型可描述如下：

　　解空间 解空间 S 是遍访每个城市恰好一次的所有回路，是{1，……，n}的所有循环排

　　新解的产生 随机产生 1 和 n 之间的两相异数 k 和 m，若 k<m，则将

　　(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)

　　变为：

　　(w1, w2 ,…，wm , wm-1 ,…，wk+1 , wk ,…，wn).

　　如果是 k>m，则将

　　(w1, w2 ,…，wk , wk+1 ,…，wm ,…，wn)

　　(wm, wm-1 ,…，w1 , wm+1 ,…，wk-1 ,wn , wn-1 ,…，wk).

　　上述变换方法可简单说成是“逆转中间或者逆转两端”。

到一种更好方法。

　　代价函数差 设将(w1, w2 ,……，wn)变换为(u1, u2 ,……，un), 则代价函数差为：

　begin

　　init-of-T; { T 为初始温度}

　　S={1，……，n}; {S 为初始值}

　　termination=false;

　　while termination=false

　　　begin

　　　　for i=1 to L do

　　　　　　begin

　　　　　　　　IF(Δt<0) OR (EXP(-Δt/T)>Random-of-[0,1])

　　　　　　　　S=S′;

　　　　　　　　IF the-halt-condition-is-TRUE THEN

　　　　　　　　termination=true;

　　　　　　End;

　　模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(Max Cut Problem)、0-1

背包问题(Zero One Knapsack

Problem)、图着色问题(Graph Colouring Problem)、调度问题(Scheduling Problem)等等。

因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。

实际应用过程中，初始温度一般需要

依据实验结果进行若干次调整。

　　(2) 退火速度问题。

分”搜索(退火)是相当必要的，但这

　　(3) 温度管理问题。

　　温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计

用如下所示的降温方式：

T(t+1)＝k×T(t)

式中 k 为正的略小于 1.00 的常数，t 为降温的次数

使用 SA 解决 TSP 问题的 Matlab 程序：

欢迎光临 http://www.daxiongonline.com

头衔：站长

等级：管理员

文章：219

积分：682

门派：无门无派

注册：2005 年 11 月 18 日第 2 楼

% TSP by itself will generate 20 cities within a unit cube and

% then use SA to slove this problem.

%

% TSP(LOC) solve the traveling salesman problem with cities'

% coordinates given by LOC, which is an M by 2 matrix and M is

% the number of cities.

%

% For example:

%

% loc = rand(50, 2);

% Hopfield & Tank's 1985 paper in Biological Cybernetics

% (Vol 52, pp. 141-152).

loc = [0.3663, 0.9076; 0.7459, 0.8713; 0.4521, 0.8465;

0.7624, 0.7459; 0.7096, 0.7228; 0.0710, 0.7426;

0.5974, 0.6436; 0.3630, 0.5908; 0.6700, 0.5908;

0.6172, 0.5495; 0.6667, 0.5446; 0.1980, 0.4686;

0.3498, 0.4488; 0.2673, 0.4274; 0.9439, 0.4208;

0.8218, 0.3795; 0.3729, 0.2690; 0.6073, 0.2640;

0.4158, 0.2475; 0.5990, 0.2261; 0.3927, 0.1947;

0.5347, 0.1898; 0.3960, 0.1320; 0.6287, 0.0842;

0.5000, 0.0396; 0.9802, 0.0182; 0.6832, 0.8515];

end

NumCity = length(loc); % Number of cities

distance = zeros(NumCity); % Initialize a distance matrix

% Fill the distance matrix

for i = 1:NumCity,

for j = 1:NumCity,

distance(i, j) = norm(loc(i, - loc(j, );

distance(i, j) = norm(loc(i, - loc(j, );

%path = randperm(NumCity);

for i = 1:count

path = randperm(NumCity);

energy = sum(distance((path-1)*NumCity + [path(2:NumCity)

path(1)]));

new_path = path;

index = round(rand(2,1)*NumCity+.5);

inversion_index = (min(index):max(index));

new_path(inversion_index) = fliplr(path(inversion_index));

all_dE(i) = abs(energy - ...

sum(sum(diff(loc([new_path new_path(1)],)'.^2)));

out = [path path(1)];

plot(loc(out(, 1), loc(out(, 2),'r.', 'Markersize', 20);

axis square; hold on

h = plot(loc(out(, 1), loc(out(, 2)); hold off