【文件属性】：
文件名称：基于lf蚁群聚类算法
文件大小：128B
文件格式：MAT
更新时间：2013-09-23 08:45:16
蚁群算法
%-- Unknown date --%
else
p(:,j)=0;
end;
if maxp(1)bestsolution_NC(NC)
bestsolution=bestsolution_NC(NC);
end;
linear_index2=find(bestsolution==bestsolution_NC);
size4[1,NC];
[r_index2,c_index2]=ind2sub(size4,linear_index2(1));
bestroute(1,:)=bestroute_NC(c_index2,:);
initao=tao;
end;
%% ******** Otuput the best rusult of TSP ******** %%
for NC-1:NCmax
bestroute_NC(NC,n)=g(NC,c_index1(NC));
t(NC)=NC;
end;
bestroute(1,n)=bestroute_NC(c_index2,n);
polt(x(bestroute(n)),y(bestroute(n)),'*');
hold on;
end;
line([x(bestroute(n)),x(bestroute(1))],[y(bestroute(n)),y(bestroute(1))]);
hold on;
for j=1:(n-1)
line([x(bestroute(j)),x(bestroute(j+1))],[y(bestroute(j)),y(bestroute(j+1))]);
hold on;
end;
hold off;
xlabel('X coordinate');
ylabel('Y coordinate');
title('best tour in NCmax iterations');
%% ********Funtion: Open and improt file of city coordinate in TSP
%% ******** %%
[fname,pname,fiterindex]=uigetfile('*.*','All Files(*.*)');
set(handles.text_filename,'string',filename);
fid=fopen(filename,'r')'
if fid==-1;
warndlg('can't open the file','WARN');
fclose(fid);
end;
[A0,COUNT]=fscanf(fid,'%g');
n=COUNT/3;
set(handles.edit_citysum,'string',n);
fclose(fid);
m=str2double(get(handles.edit_citysum,'string'));
NCmax=str2double(get(handles.edit_ncmax,'string'));
for NC=1:NCmax
for k=1:m
g(NC,k)=fix((n-1)*rand(1))+1;
end;
end
%-- 10-9-1 下午4:54 --%
%-- 10-9-1 下午8:09 --%
load('E:\苏雪敬个人资料\苏雪敬-开题报告\程序代码\matlab.mat')
%-- 10-9-2 上午9:01 --%
load('E:\苏雪敬个人资料\苏雪敬-开题报告\程序代码\matlab.mat')
%% ******Initialization phase ****** %%
global A0
global n; %city number
global g;
m=str2double(get(handles.edit_antsum, 'String')); %set ant number by using Matlab GUI
initao=str2double(get(handles.edit_tao, 'String'));
alpha=str2double(get(handles.edit_alpha, 'String'));
beta=str2double(get(handles.edit_beta, 'String'));
Q=str2double(get(handles.edit_q, 'String'));
rou=str2double(get(handles.edit_rou, 'String'));
NCmax=str2double(get(handles.edit_ncmax, 'String'));
A=reshape(A0,3,n); %get the city coordinates in TSP
x=A(2,:); %get x=coordinate
y=A(3,:); %get y=coordinate
for i=1:n
for j=1:n
distance(i,j)=sqrt((x(i)-x(j)+(y(i)-y(j))*y(i)-y(j)));
end;
for i=1:n
for j=1:n
if j!=i
tao(i,j)=initao;
yita(i,j)=1/distance(i,j);
end;
initao=initao.*ones(n,n);
detatao=zeors(n,n);
bestsolution=10000000000000;
%% ******This is in phase in which ants build tours ****** %%
for NC=1:NCmax
tabu=zeros(m.n)l
for k=1:m
tabu(k,g(NC,k))=1;
maxp(1)=0;
for j=1:n
if tabu(k,j)==0
psum_medium0(1,j)=(tao(g(NC,k)^alpha).*(yita(g(NC,k),j)^beta);
else
psum_medium0(1,j)=0;
end;
psum_medium=psum_medium0.';
psum(k,1)=sum(psum_medium(:,1));
for j=1:n
if tabu(k,j)==0
p(1,j)=(tao(g(NC,k)^alpha).*(yita(g(NC,k),j)^beta/psm(k,1);
else
p(:,j)=0;
end;
if maxp(1)bestsolution_NC(NC)
bestsolution=bestsolution_NC(NC);
end;
linear_index2=find(bestsolution==bestsolution_NC);
size4[1,NC];
[r_index2,c_index2]=ind2sub(size4,linear_index2(1));
bestroute(1,:)=bestroute_NC(c_index2,:);
initao=tao;
end;
%% ******** Otuput the best rusult of TSP ******** %%
for NC-1:NCmax
bestroute_NC(NC,n)=g(NC,c_index1(NC));
t(NC)=NC;
end;
bestroute(1,n)=bestroute_NC(c_index2,n);
polt(x(bestroute(n)),y(bestroute(n)),'*');
hold on;
end;
line([x(bestroute(n)),x(bestroute(1))],[y(bestroute(n)),y(bestroute(1))]);
hold on;
for j=1:(n-1)
line([x(bestroute(j)),x(bestroute(j+1))],[y(bestroute(j)),y(bestroute(j+1))]);
hold on;
end;
hold off;
xlabel('X coordinate');
ylabel('Y coordinate');
title('best tour in NCmax iterations');
%% ********Funtion: Open and improt file of city coordinate in TSP
%% ******** %%
[fname,pname,fiterindex]=uigetfile('*.*','All Files(*.*)');
set(handles.text_filename,'string',filename);
fid=fopen(filename,'r')'
if fid==-1;
warndlg('can't open the file','WARN');
fclose(fid);
end;
[A0,COUNT]=fscanf(fid,'%g');
n=COUNT/3;
set(handles.edit_citysum,'string',n);
fclose(fid);
m=str2double(get(handles.edit_citysum,'string'));
NCmax=str2double(get(handles.edit_ncmax,'string'));
for NC=1:NCmax
for k=1:m
g(NC,k)=fix((n-1)*rand(1))+1;
end;
end
%-- 10-9-2 下午4:47 --%
%-- 10-9-2 下午8:02 --%
%{
? 当前蚂蚁移到邻近区域内的没有被其他蚂蚁占据的节点
a) 输入参数
? 蚂蚁编号ant_no
? S局部查找范围
? ant_matrix（蚂蚁的窗格矩阵）
? Z平面窗格总区域
b) 输出参数
? 蚂蚁前往的结点坐标
%}
function ant_matrix=ant_move(ant_no,S,ant_matrix,Z)
%1、获得ant_no点坐标
%[x,y,z]=ant_matrix(ant_no,:);
one_ant=ant_matrix(ant_no,:);
x=one_ant(1);
y=one_ant(2);
z=one_ant(3);
%2、获得上下界限
x_low=x-S/2;
x_high=x+S/2;
if(x_low<0)
x_low=0;
end
if(x_high>Z)
x_high=Z;
end
y_low=y-S/2;
y_high=y+S/2;
if(y_low<0)
y_low=0;
end
if(y_high>Z)
y_high=Z;
end
%获得所有邻接结点下标数组
%{
allneighbours=[];
[row,col]=size(ant_matrix);
for i=1:row
if i~=ant_no
[x,y,z]=ant_matrix(i,:);
if x>=x_low && x<=x_high && y>=y_low && y<=y_high
allneighbours=[allneighbours i];
end
end
end
allneighbours=[allneighbours ant_no];
%}
[row,col]=size(ant_matrix);
positions=[];
%遍历所有上下界之间的点
for i=x_low:x_high
for j=y_low:y_high
status=0;
for k=1:row
% [x,y,z]=ant_matrix(k,:);
one_ant=ant_matrix(k,:);
x=one_ant(1);
y=one_ant(2);
z=one_ant(3);
if x==i && y==j
status=1;
end
end
if status==0
positions=[positions;i j];
end
end
end
%随机产生这个位置
[row,col]=size(positions);
i=ceil(rand*row);
position=positions(i,:);
ant_matrix(ant_no,1)=position(1);
ant_matrix(ant_no,2)=position(2);
%{
? 求Oi点在平面窗格内S*S区域内的邻接点的下标矩阵
a) 输入参数：
? Oi点
? S局部查找范围
? Item_Window（结点的窗格矩阵）
? Z平面窗格总区域
b) 输出参数
? 所有在S*S区域内的结点的下标
具体算法：
1、S区域的上界
2、S区域的下界
3、比较一下点在哪些区域内
%}
function allneighbours=get_allneighbours(Oi,S,item_window,Z)
%1、获得Oi点坐标
%[x,y]=item_window(Oi,:);
one_item=item_window(Oi,:);
x=one_item(1);
y=one_item(2);
%2、获得上下界限
x_low=x-S/2;
x_high=x+S/2;
if(x_low<0)
x_low=0;
end
if(x_high>Z)
x_high=Z;
end
y_low=y-S/2;
y_high=y+S/2;
if(y_low<0)
y_low=0;
end
if(y_high>Z)
y_high=Z;
end
%获得所有邻接结点下标数组
allneighbours=[];
[row,col]=size(item_window);
for i=1:row
if i~=Oi
% [x,y]=item_window(i,:);
one_item=item_window(i,:);
x=one_item(1);
y=one_item(2);
if x>=x_low && x<=x_high && y>=y_low && y<=y_high
allneighbours=[allneighbours i];
end
end
end
%{
? 求两点空间的距离函数
a) 输入参数：
? Oi点
? Oj点
? 点的空间矩阵Item_Space
b) 输出参数：
? 两点之间的距离
%}
function distance=get_distance(Oi,Oj,item_space)
distance=0.0;
X1=item_space(Oi,:);
X2=item_space(Oj,:);
size=length(X1);
for i=1:size
distance=distance+(X1(i)-X2(i))^2;
end
distance=sqrt(distance);
%{
? 设计函数计算群体相似度计算
a) 输入参数：
? Oi点（需要计算的点）、
? S（S*S区域内）、
? Alpha、
? Item_Window（结点的窗格矩阵）
? Z（Z*Z区域）
? item_space（结点的空间矩阵）
b) 输出参数：
? Oi点的相似度
程序流程：
1、计算Oi的所有邻居
2、所有邻居的距离相应的和
3、判断和值和0的关系
4、最后决定值的大小
%}
function fi=get_Fi(Oi,S,Alpha,item_window,Z,item_space)
%1、计算Oi的所有邻居
allneighbours=get_allneighbours(Oi,S,item_window,Z);
%2、所有邻居的距离相应的和
len=length(allneighbours);
fi=0;
for i=1:len
distance=get_distance(Oi,allneighbours(i),item_space);
fi=fi+(1-distance)/Alpha;
end
if(fi>0)
fi=fi/(S^2);
else
fi=0;
end
%{
? 放下概率的计算
a) 输入参数：
? Oi点（需要计算的点）、
? S（S*S区域内）、
? Alpha、
? Item_Window（结点的窗格矩阵）
? K2
? Z（Z*Z区域）
? item_space（结点的空间矩阵）
b) 输出参数
? 放下概率
程序流程
1、先计算群体相似概率
2、计算放下概率
%}
function Pd=get_Pd(Oi,S,Alpha,item_window,K2,Z,item_space)
%1、计算群体相似概率
fi=get_Fi(Oi,S,Alpha,item_window,Z,item_space);
%2、计算放下概率
if fi
%{
? 拾起概率的计算
a) 输入参数：
? Oi点（需要计算的点）、
? S（S*S区域内）、
? Alpha、
? Item_Window（结点的窗格矩阵）
? K2
b) 输出参数
? 拾起概率
程序流程：
1、首先计算群体相似概率
2、计算拾起概率
%}
function Pp=get_Pp(Oi,S,Alpha,item_window,K1,Z,item_space)
%1
fi=get_Fi(Oi,S,Alpha,item_window,Z,item_space);
%2
Pp=(K1/(K1+fi))^2;
%{
? 判断蚂蚁所在处是否有点
a) 输入参数
? x蚂蚁横坐标
? y蚂蚁纵坐标
? item_window所有点的坐标矩阵
b) 输出参数
? 蚂蚁所在处是否有点，有点返回这个点在item_window中的行号，无点0
%}
function position=has_item(x,y,item_window)
%{
[row,col]=size(item_window);
for i=1:row
end
%}
%position=find(item_window(find(item_window(:,1)==x),2)==y)
position=0;
[row,col]=size(item_window);
for i=1:row
if ~isempty(find(x==item_window(i,1))) && ~isempty(find(y==item_window(i,2)))
position=i;
end
end
%{
? 初始化函数
a) 输入参数
? 蚂蚁的数目ant_number
? 点的数目item_number
? 空间尺寸Z，空间大小Z*Z
b) 输出参数
? 蚂蚁的平面窗格矩阵
? 点的平面窗格矩阵
%}
function [ant_matrix,item_window]=initialize(ant_number,item_number,Z)
ant_matrix_x=randperm(Z);
ant_matrix_y=randperm(Z);
item_matrix_x=randperm(Z);
item_matrix_y=randperm(Z);
%生成蚂蚁矩阵
for i=1:ant_number
ant_matrix(i,1)=ant_matrix_x(i);
ant_matrix(i,2)=ant_matrix_y(i);
ant_matrix(i,3)=0;
end
for i=1:item_number
item_window(i,1)=item_matrix_x(i);
item_window(i,2)=item_matrix_y(i);
end
%{
test
测试程序
整个程序流程
1、初始化：
2、迭代tmax次
3、所有的蚂蚁运动一次
4、产生一个0-1之间的随机数R
5、如果当前蚂蚁处于未负载状态，而且当前蚂蚁所在处的有点Oi
5.1、计算群体相似度f(Oi)和拾起概率Pp(Oi)
5.2、如果拾起概率Pp(Oi)》R
5.2.1、当前蚂蚁拾起点Oi（注意Oi在窗格中的位置是不断变动的）
5.3 5.2结束
6、如果条件5不成立，如果当前蚂蚁处于负载状态，持有点Oi，而且当前位置没有其他点
6.1计算群体相似度f(Oi)和放下概率Pd(Oi)
6.2如果放下概率Pd(Oi)》R
6.2.1放下节点Oi（注意点Oi在窗格中的位置是不断变动的）
6.2.2修改蚂蚁状态为卸载
6.3 6.2结束
7、5结束
8、当前蚂蚁移到邻近区域内的没有被其他蚂蚁占据的节点
9、所有的蚂蚁运动一次结束
10、迭代tmax次结束
输入参数：
1、ant_number 蚂蚁数
2、item_number 点数
3、Z 区域范围
4、tmax 最大迭代次数
5、S 邻接区域
6、Alpha 相异度参数
7、item_space 点的空间矩阵
8、K1 拾起概率参数
9、K2 放下概率参数
%}
clear;
clc;
K1=0.1;
K2=0.15;
Alpha=0.15;
%S=6;
S=30;
tmax=300;
ant_number=20;
Z=50;
axis([0 Z 0 Z]);
item_space=[ 5.1 3.5 1.4 0.2;
4.9 3.0 1.4 0.2;
4.7 3.2 1.3 0.2;
4.6 3.1 1.5 0.2;
5.0 3.6 1.4 0.2;
5.4 3.9 1.7 0.4;
4.6 3.4 1.4 0.3;
5.0 3.4 1.5 0.2;
];
[row,col]=size(item_space);
item_number=row;
%1、初始化：
[ant_matrix,item_window]=initialize(ant_number,item_number,Z);
item_window
%2、迭代tmax次
for i=1:tmax
%3、所有的蚂蚁运动一次
for j=1:ant_number
%4、产生一个0-1之间的随机数R
r=rand;
%5、如果当前蚂蚁处于未负载状态，而且当前蚂蚁所在处的有点Oi
%[x,y,z]=ant_matrix(j,:);
one_ant=ant_matrix(j,:);
x=one_ant(1);
y=one_ant(2);
z=one_ant(3);
%rows1=find(item_window(:,1)==x);
%rows2=find(item_window(:,2)==y);
%Oi=find(item_window(find(item_window(:,1)==x),2)==y);
Oi=has_item(x,y,item_window);
if z==0 && Oi>0
%5.1、计算群体相似度f(Oi)和拾起概率Pp(Oi)
%fi=get_Fi(Oi,S,Alpha,item_window,Z,item_space);
Pp=get_Pp(Oi,S,Alpha,item_window,K1,Z,item_space);
Pp;
%5.2、如果拾起概率Pp(Oi)》R
if Pp>=r
%5.2.1、当前蚂蚁拾起点Oi（注意Oi在窗格中的位置是不断变动的）
ant_matrix(j,3)=Oi;
end
elseif ant_matrix(j,3)>0 && Oi==0
%6、如果条件5不成立，如果当前蚂蚁处于负载状态，持有点Oi，而且当前位置没有其他点
%6.1计算群体相似度f(Oi)和放下概率Pd(Oi)
Oi=ant_matrix(j,3);%代表当前蚂蚁所携带的点的行号
Pd=get_Pd(Oi,S,Alpha,item_window,K2,Z,item_space);
Pd;
%6.2如果放下概率Pd(Oi)》R
if Pd>=r
%6.2.1放下节点Oi（注意点Oi在窗格中的位置是不断变动的）
item_window(Oi,1)=x;
item_window(Oi,2)=y;
ant_matrix(j,3)=0;
end
end
%8、当前蚂蚁移到邻近区域内的没有被其他蚂蚁占据的节点
ant_matrix=ant_move(j,S,ant_matrix,Z);
end
end
item_window
axis([0 Z 0 Z]);
plot(item_window(:,1),item_window(:,2),'--rs');
%-- 10-9-2 下午9:11 --%
load('E:\苏雪敬个人资料\苏雪敬-开题报告\程序代码\matlab.mat')
%-- 10-9-3 下午2:54 --%
load('E:\苏雪敬个人资料\苏雪敬-开题报告\程序代码\lf蚁群算法.mat')
matlab7
