智能优化方法课程论文
[3]冯剑， 岳琪. 模拟退火算法求解 TSP 问题[J]. 森林工程， 2008， 24(1)： 94-96.
[4]朱静丽. 用模拟退火算法求解 TSP[J]. 湖北广播电视大学学报， 2011， 31(9)： 159-160.
[5]庞峰. 模拟退火算法的原理及算法在优化问题上的应用 [D]. 吉林大学， 2006.
[6]马良. 旅行推销员问题的算法综述[J]. 数学的实践与认识， 2000， 30(2)： 156-165.
第6页 共10页
智能优化方法课程论文
附录：程序代码
代码使用了模拟退火的思想解决TSP问题。在仿真实验中解决了自定义的20个城市的TSP问题，在设定合适参数后每次的运行中都能得到一个比较理想的结果。主要的程序代码如下：
function f = plotcities(inputcities)
% 将输入的城市在二维平面上表示出来,每个星号代表一个城市。 shg
temp_1 = plot(inputcities(1,:),inputcities(2,:),'b*'); set(temp_1,'erasemode','none');
temp_2 = line(inputcities(1,:),inputcities(2,:),'Marker','*'); set(temp_2,'color','b');
x = [inputcities(1,1) inputcities(1,length(inputcities))]; y = [inputcities(2,1) inputcities(2,length(inputcities))]; xl = 10*round(min(inputcities(1,:))/10); yl = 10*round(min(inputcities(2,:))/10); if xl > 0 xl = 0; end if yl > 0 yl = 0; end
xu = 10*round(max(inputcities(1,:))/10); yu = 10*round(max(inputcities(2,:))/10); if xu == 0 xu = 1; end if yu == 0 yu = 1; end
axis([xl xu yl yu]) ; temp_3 = line(x,y);
第7页 共10页
智能优化方法课程论文
set(temp_3,'color','b'); dist = distance(inputcities); distance_print = sprintf(...
'The roundtrip length for %d cities is % 4.6f units'... ,length(inputcities),dist);
text(xl/1.05,1.05*yu,distance_print,'fontweight','bold'); drawnow;
function s =
simulatedannealing(inputcities,initial_temperature,cooling_rate,threshold,numberofcitiestoswap)
%模拟退火算法。参数有输入城市数据，初始温度，冷却速率，阈值和交换城市数量。 global iterations;
temperature = initial_temperature;
initial_cities_to_swap = numberofcitiestoswap; iterations = 1;
complete_temperature_iterations = 0; previous_distance = distance(inputcities); while iterations < threshold
temp_cities = swapcities(inputcities,numberofcitiestoswap); current_distance = distance(temp_cities); diff = abs(current_distance - previous_distance); if current_distance < previous_distance inputcities = temp_cities; if rem(iterations,100) == 0 plotcities(inputcities); end
if complete_temperature_iterations >= 10 temperature = cooling_rate*temperature; complete_temperature_iterations = 0; end
numberofcitiestoswap
=
第8页 共10页
智能优化方法课程论文
round(numberofcitiestoswap*exp(-diff/(iterations*temperature)));
if numberofcitiestoswap == 0 numberofcitiestoswap = 1; end
previous_distance = current_distance; iterations = iterations + 1;
complete_temperature_iterations = complete_temperature_iterations + 1; else
if rand(1) < exp(-diff/(temperature)) inputcities = temp_cities; if rem(iterations,100) == 0 plotcities(inputcities); end
numberofcitiestoswap
round(numberofcitiestoswap*exp(-diff/(iterations*temperature)));
if numberofcitiestoswap == 0 numberofcitiestoswap = 1; end
previous_distance = current_distance;
complete_temperature_iterations = complete_temperature_iterations + 1; iterations = iterations + 1; end end end
function s = swapcities(inputcities,n) % 随机交换两个城市。 s = inputcities; for i = 1 : n
city_1 = round(length(inputcities)*rand(1)); if city_1 < 1
第9页 共10页
=
智能优化方法课程论文
city_1 = 1; end
city_2 = round(length(inputcities)*rand(1)); if city_2 < 1 city_2 = 1; end
temp = s(:,city_1); s(:,city_1) = s(:,city_2); s(:,city_2) = temp; end
function d = distance(inputcities)
%计算输入城市的距离解决旅行商问题。 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
第10页 共10页