没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
SIMULATED ANNEALING FOR TRAVELING SALESMAN
PROBLEM
ARAVIND SESHADRI
1. Traveling Salesman Problem
Traveling Salesman Problem (TSP) has been an interes ting problem for a long
time in classical optimization techniques which are based on linea r and no nlinear
programming. TSP can be described as follows: Given a number of cities to visit
and their distances from all other cities know, an optimal travel route has to be
found so that each city is visited one and only once with the least possible distance
traveled. This is a simple problem with handful of cities but be c omes c omplicated
as the number increases.
2. Simulated Annealing
There are several well know classical methods for finding a near optimal solution
using linear and nonlinear programming for TSP’s. Simulated Annealing is not
based on any of the classical optimization techniques but is based on heuristics
from annealing process. Based on the motivation from how crystalline structures are
formed from annealing proc e ss, a heuristic method called simulated annealing was
developed and had a lot of interesting results. I have not put the effort to explain
everything in detail about simulated annea ling but a quick google on simulated
annealing would ge t you started.
To make the long story short, simulated annealing is similar to hill climbing or
gradient search with a few modifications. In gradient based search the search direc-
tion is dependent on gradient and hence the function to be optimized should be a
continuous function without dis c ontinuities. Simulated Annealing does not r e quire
the function to be smooth and co ntinuous since it is not based on gradient of the
function. Consider a minimization problem with a lot of local optima. During
the initial search phase (when temperature is high) loca l search
1
is carried out and
routes which minimize the total distance are always acc epted. To escape the prob-
lem of getting stuck in a local minima occa sionally routes with distance more than
the curr ent route is also accepted but with a proba bility similar to the probability
in the dynamics of the annealing process. As the temperature decr e ases, this prob-
ability of accepting a bad solution is decreas e d and in the final stages it becomes
similar to gradient based search. This idea is blend between a co mpletely random
search and a gradient based search with some heuristics based on the annealing
process.
1
Search meaning random routes are made and their corresponding distances calculated.
1
2 ARAVIND SESHADRI
3. 20 Cities TSP
A generic simulated annealing for 20 cities traveling salesman problem from
TSPLIB
2
archive. The b e st solution found is given in figure 1 and the total optimal
distance to travel 20 cities is 4 .030656 units.
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
The roundtrip for minimal total length for 20 cities is 4.030656 units
Figure 1. The Best Solution
3.1. Algorithm. The algor ithm for simulated annealing is given below. The MAT-
LAB source code is provided below. Feel free to edit the code and make changes.
Yo u can use this code to run any of the problem in the TSPLIB as long as you
follow the procedure for loading the corresponding data file as described in the next
subsection. I will have to warn you that running a large data set will take a lot
of time and requires a lot of memory and processing . I am only trying to g e t you
started on simulated annealing and I am sure my code is not optimized for large
data se t. I would be re ally happy if someone is willing to help me out in optimizing
my code a s well as in r e fining my algorithm.
3.1.1. Load Data File. This is an example for loading the data file.
function d = datafile()
cities =
2
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/
SIMULATED ANNEALING 3
[0.6606,0.9695,0.5906,0.2124,0.0398,0.1367,0.9536,0.6091,0.8767,...
0.8148,0.3876,0.7041,0.0213,0.3429,0.7471,0.5449,0.9464,0.1247,0.1636,...
0.8668,;0.9500,0.6740,0.5029,0.8274,0.9697,0.5979,0.2184,0.7148,0.2395,...
0.2867,0.8200,0.3296,0.1649,0.3025,0.8192,0.9392,0.8191,0.4351,0.8646,...
0.6768];
save cities.mat cities -V6;
When datafile function is called an array containing the coordinates of the cities
are loaded into a file called cities.mat. The file is stored in structure format. You
can write your own datafile function by visiting
www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp
and you c an use any data file in the web site. An example is shown below.
function c = loadeil101()
% LOADEIL101 Loads the data file.
% COMMENT : 101-city problem (Christofides/Eilon)
% TYPE : TSP
% DIMENSION : 101
% Source: www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp
clear all; temp_x = [1 41 49 2 35 17 3 55 45 . . . . . . 98 19 21 99
20 26 100 18 18 101 35 35]; cities = [temp_x(:,2)’;temp_x(:,3)’];
save cities.mat cities -V6;
The first column of the data file from TSPLIB is usually the city number and
the next couple of columns represent the coordinates for the cities. My function
looks for file named as cities.mat in a structure format which when loaded to
the workspace has the variable name cities. I sure there is an elegant way to make
everything completely independent but I am lazy to modify anything. Hence make
sure the data file has the last c ouple of lines the sa me unless you know what you
are doing.
3.1.2. Function for calculating the total distance.
function d = distance(inputcities)
% DISTANCE
% d = DISTANCE(inputcities) calculates the distance between n cities as
% required in a Traveling Salesman Problem. The input argument has two rows
% and n columns, where n is the number of cities and each column represent
% the coordinate of the corresponding city.
d = 0;
for n = 1 : length(inputcities)
if n == length(inputcities)
d = d + norm(inputcities(:,n) - inputcities(:,1));
else
d = d + norm(inputcities(:,n) - inputcities(:,n+1));
end
end
The cost function for a symmetric traveling sa le sman problem is the dista nce be-
tween the cities. This function c alculates the distance been n cities when distance(n)
function is called.
剩余13页未读,继续阅读
资源评论
- 凌雪飞鸿2014-01-26不错的资料,可以直接用了
- L_Tender2015-07-30正好,建模用上,可以学习
- louissunset2014-09-19挺好的一份资料,初步了解了模拟退火
- glmyzh12282021-10-08英文的pdf而已,没啥帮助
yuerbo
- 粉丝: 1
- 资源: 9
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功