__2017-12-11 如一模式识别研究

如一模式识别研究

基本数学知识>>遗传算法求解旅行商(TSP)问题

1. TSP问题概述

TSP问题即旅行商问题,是数学领域的著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要使求得的路径路程为所有路径之中的最小值。

2. 基于遗传算法的TSP问题求解

(1)基因编码

针对TSP问题,编码规则通常采用实数(n进制)编码,即每个染色体仅从1到n的整数里面取一个值,每个个体的长度为n,n为城市总数。即用一串基因编码表示遍历的城市顺序,如:(2 3 4 5 1 7 9 8 6),表示九个城市中,先经过城市2,再经过城市3,以此类推。

(2)交叉算子设计

采用部分匹配交叉(PMX)法:先随机产生两个交叉点,定义这两点间的区域为匹配区域,并交换两个父代的匹配区域。

父代A:872|130|9546

父代B:983|567|1420

TEMP A:872|567|9546

TEMP B:983|130|1420

对于TEMP A、TEMP B中匹配区域以外出现的数码重复,要依据匹配区域内的位置逐一进行替换。匹配关系:1<------>5 3<----->6 7<---->0

子代A:802|567|9143

子代B:986|130|5427

(3)变异算子设计

对于TSP问题,一般采用倒位变异法,即首先在父体中随机选择两截断点,然后将该两点所夹的子串中的城市进行反序。

例如;

设原个体:(1 2 3 4 5 6 7 8 9)

随机选择两点:(1 2|3 4 5 6| 7 8 9)

倒位后的个体:(1 2 |6 5 4 3|7 8 9)

(4)适应度函数

TSP问题的目标是路径总长度为最短,可以用常数L除以某个体的路径总长度作为该个体的是适应度函数。

3 . 算法步骤

Step1:参数设置及种群初始化;

Step2;适应度评价;

Step3:轮盘赌选择;

Step4:部分匹配交叉;

Step5:倒位变异;

Step6:适应度评价;

Step7:终止条件判断,若未达到终止条件,则转到step3;

Step8:输出结果。

4.实现代码

[javascript] view plaincopyprint?

%功能:基于遗传算法的TSP问题求解

function GA_for_TSP

clc;clear all;close all;

%初始化数据

city_num=30;

[city_distance,city_coordinate]=tsp_info(city_num);%距离矩阵和城市坐标

pop=100;ger=800;pc=0.8;pm=0.2;history_best=inf;

for i=1:pop

individual(i,:)=randperm(city_num);%产生1~30之间的随机排列数

end

[fitness,f]=evaluate_fitness(individual,city_distance);

it=1;

while it<=ger

disp(it)

new_individual=select(fitness,individual);%轮盘赌

new_individual=cross(new_individual,pc);

new_individual=mutation(new_individual,pm);

[fitness,f]=evaluate_fitness(new_individual,city_distance);

%取出最佳适应度的个体

[best_fitness,best_index]=max(fitness);

[worst_fitness,worst_index]=min(fitness);

best_f=f(best_index);

best_individual=new_individual(best_index,:);

new_individual(worst_index,:)=best_individual;

plot_dsp(city_coordinate,best_individual,best_f,it);

individual=new_individual;

if best_f

history_best=best_f;

history_best_individual=best_individual;

best_individual_last(it,:)=best_f;%???

else

best_individual_last(it,:)=history_best;

end

it=it+1;

end

disp(sprintf('最短路径:%2.5f',history_best))

disp('路径方案:')

disp(sprintf('%4d',history_best_individual));

%给每个城市标号

for i=1:size(city_coordinate,1)

text(city_coordinate(i,1),city_coordinate(i,2),num2str(i));

end

figure(2)

plot(best_individual_last,'r');hold on;

title('搜索过程');

legend('最优路径长度');

gtext(['(' num2str(it-1) ',' num2str(history_best) ')']);

%end

%******************Data子程序tsp_info***************************

function [city_distance,city_coordinate]=tsp_info(city_num)

%fid=fopen('city_coordinate.txt','r');

%city_coordinate=fscanf(fid,'%d',[50,2]);

%fclose(fid);

city_coordinate=[41,94;37,84;54,67;25,62;7,64;2,99;68,58;71,44;54,62;83,69;64,60;18,54;22,60;

83,46;91,38;25,38;24,42;58,69;71,71;74,78;87,76;18,40;13,40;82,7;62,32;58,35;45,21;41,26;44,35;4,50];

for i=1:city_num

for j=1:city_num

city_distance(i,j)=sqrt((city_coordinate(i,1)-city_coordinate(j,1))^2+(city_coordinate(i,2)-city_coordinate(j,2))^2);

end

end

%********************The end of tsp_info*****************

%********************适应度-->evaluate_fitness*************************

function [fitness,f]=evaluate_fitness(individual,city_distance)

[M,N]=size(individual);

for i=1:M

temp=0;

for j=1:N-1

temp=temp+city_distance(individual(i,j),individual(i,j+1));

end

f(i)=temp+city_distance(individual(i,N),individual(i,1));

fitness(i)=1000/f(i);

end

%*********************************the end*************************************

%*************************轮盘赌-->selcet***********************************

function new_individual=select(fitness,individual)

[m,n]=size(fitness');

for i=1:m

fit(i)=fitness(i)^20;

end

%fit=fitness.^20;

for i=1:m

sp(i)=fit(i)/sum(fit);

end

for i=2:m

sp(i)=sp(i-1)+sp(i);

end

for i=1:m

p=rand(1);

j=1;

while(p>sp(j))%找到sp(j)大于p的 j 值

j=j+1;

end

new_individual(i,:)=individual(j,:);

end

%***************************The End***********************************

%**************************交叉子程序*****************************

%功能:片段交叉

function new_individual=cross(new_individual,pc)

[M,N]=size(new_individual);

%先将顺序打乱

for i=1:M

point=unidrnd(M-i+1);%产生随机数

temp=new_individual(i,:);

new_individual(i,:)=new_individual(i+point-1,:);

new_individual(i+point-1,:)=temp;

end

for i=1:2:M-1

if pc>rand(1)

%产生两个交叉位置

location_num1=round(rand(1)*(N-2))+1;

location_num2=round(rand(1)*(N-2))+1;

min_location=min([location_num1,location_num2]);

max_location=max([location_num1,location_num2]);

%交换相邻两行的片段

middle=new_individual(i,min_location+1:max_location);

new_individual(i,min_location+1:max_location)=new_individual(i+1,min_location+1:max_location);

new_individual(i+1,min_location+1:max_location)=middle;

%交叉完之后检查个体序号是否有重复

for j=1:min_location%前半段

while find(new_individual(i,min_location+1:max_location)==new_individual(i,j))

num=find(new_individual(i,min_location+1:max_location)==new_individual(i,j));

new_num=new_individual(i+1,min_location+num);

new_individual(i,j)=new_num;

end

while find(new_individual(i+1,min_location+1:max_location)==new_individual(i+1,j))

num=find(new_individual(i+1,min_location+1:max_location)==new_individual(i+1,j));

new_num=new_individual(i,min_location+num);

new_individual(i+1,j)=new_num;

end

end

for j=max_location+1:N%后半段

while find(new_individual(i,1:max_location)==new_individual(i,j))

num=find(new_individual(i,1:max_location)==new_individual(i,j));

new_num=new_individual(i+1,num);

new_individual(i,j)=new_num;

end

while find(new_individual(i+1,1:max_location)==new_individual(i+1,j))

num=find(new_individual(i+1,1:max_location)==new_individual(i+1,j));

new_num=new_individual(i,num);

new_individual(i+1,j)=new_num;

end

end

end

end

%***************************The End***************************

%************************画图:plot_dsp*************************************

function plot_dsp(city_coordinate,best_individual,best_fitness,it)

[city_num,city]=size(city_coordinate);

for i=1:city_num-1

plot([city_coordinate(best_individual(i),1),city_coordinate(best_individual(i+1),1)],...

[city_coordinate(best_individual(i),2),city_coordinate(best_individual(i+1),2)],...

'm.-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','b');

hold on;grid on;

end

plot([city_coordinate(best_individual(city_num),1),city_coordinate(best_individual(1),1)],...

[city_coordinate(best_individual(city_num),2),city_coordinate(best_individual(1),2)],...

'm.-','LineWidth',2,'MarkerEdgeColor','k','MarkerFaceColor','b');

title([num2str(city_num),'城市数量TSP问题']);grid on;

hold off;

pause(0.05);

%**************************the end************************************

%***************************变异子程序*******************************

%功能:变异子函数,片段倒序

function new_individual=mutation(new_individual,pm)

[M,N]=size(new_individual);%M:个体数,N:城市数

for i=1:N

if rand(1)

location_num1=round(rand(1)*(N-2))+1;%产生1~N-1之间的随机数

location_num2=round(rand(1)*(N-2))+1;

min_location=min([location_num1,location_num2]);%变异片段的最小序号

max_location=max([location_num1,location_num2]);%变异片段的最大序号

new_individual(i,min_location:max_location)=new_individual(i,max_location:-1:min_location);

end

end

%***************** The End ***************************

评论留言区

:
  

作者: 游客 ; *
评论内容: *
带*号为必填项目

如一模式识别更新提示

matlab在图像处理方面的应用有更新

如一模式识别 友情链接

关于本站作者     chinaw3c     mozilla