蚂蚁算法解顶点覆盖问题
%这是最小顶点覆盖的蚁群算法主程序%最小顶点覆盖是指：
%图G=(V，E)
%找到一个V'，V'包含于V
%min |V'|
%s.t. (u,v)是E中的任一边，存在u或者v属于V'
%主程序运行过程
%1 初始化
%2 随机生成初始可能解：蚂蚁走的路线
%3 判定路线是不是最好的，如果是最好的，给出结果，结束程序
%4 把最好的路线保留下来。给路线赋概率，也就是信息素
%5 按信息素选路线
%6 改变路线，产生新路线
%7 到3
主程序调用的函数：
函数(1)：随机生成用于计算的图G G=randomGraph(vertexN,edgeN);
函数(2)：判定蚂蚁路线是否可以覆盖边集
%判定路线的上点是否可以覆盖边集E
%cover:包含路线是否覆盖了边集的信息
cover=includeEdgeDot(pathGroup,G);
函数(3)：计算路线上的点数
%如果路线不能覆盖边集E，pathVertexN=Inf,即无穷大
pathVertexN=patheVertex(cover,pathGroup);
函数(4)：通过本次的最好路线bestRoad与上次保留的最好路线holdBestRoad比较，保存迭代中的最优路线
...
=compareBestRoad(holdBestRoad,holdVertexN,...
bestRoad,minVertexN);
函数(5)：给路线赋概率，也就是信息素
=roadProbability(pathVertexN);
函数(6)：按照信息素选择路线
selectePath=selecteRoad(pathGroup,p);
函数(7)：改变路线
pathGroup=antClimb(selectePath,cover);
clear,clc
%%%%%%%%%%%%%%%1:初始化
vertexN=10;%G中顶点的个数
edgeN=10;%G中边的个数
%G中有三个数组，第1个：顶点集，第2个：边的端点集，第3个：边的末尾点集
G=randomGraph(vertexN,edgeN);%生成图G
antN=3;%蚂蚁数
pathN=antN;%道路数，一条蚂蚁走一条路
minVN=3;%最小顶点集中的顶点数,此值只能估计
holdBestRoad=0;%强制保留的最好的路，防止改变路线时丢失
holdVertexN=Inf;
circleN=20;%迭代次数
%%%%%%%%%%%%%%%%2：随机生成初始可能解：蚂蚁走的路线路线
%为每个蚂蚁随机生成一条路，一条路是一个二进制串
pathGroup=round(rand(pathN,vertexN));
stopWhile=0;
circle=0;
while stopWhile==0
circle=circle+1;
%%%%%%%%%%%%%3:判定路线的好坏
%判定路线的上点是否可以覆盖边集E
%cover:包含路线是否覆盖了边集的信息
%roadGroup:路线
%cover(i)=0,第i条路线roadGroup(i)不能覆盖边集
%cover(i)=1,第i条路线roadGroup(i)覆盖了边集
cover=includeEdgeDot(pathGroup,G);
%计算路线上的点数
%如果路线不能覆盖边集E，pathVertexN=Inf,即无穷大
pathVertexN=patheVertex(cover,pathGroup);
%找出最好的路线以及路线上的顶点数
=min(pathVertexN);
bestRoad=pathGroup(minVertexNP,:);%最好路线
if minVertexN<minVN
'程序结束'
circle
minVertexN
pathGroup(minVertexNP,:)
return
end
%本次的最好路线bestRoad与上次保留的最好路线holdBestRoad比较
...
=compareBestRoad(holdBestRoad,holdVertexN,...
bestRoad,minVertexN);
%把保留的最好的最好路线holdBestRoad加入到路线组中
order=round(rand(1)*pathN);
if order==0
order=1;
end
pathGroup(order,:)=holdBestRoad;
pathVertexN(order)=holdVertexN;
%%%%%%%%%%%%%%%4: 给路线赋概率，也就是信息素
=roadProbability(pathVertexN);
if trueP =='Fail'
'可能解 严重不适应问题，请重新开始'
return%结束程序
end
%%%%%%%%%%%%%%%5：按照信息素选择路线
selectePath=selecteRoad(pathGroup,p);
if circle>circleN
'已达到迭代次数'
G{:}
circle
pathGroup
cover
holdBestRoad
holdVertexN
return
end
%%%%%%%%%%%%%%%6：改变路线
pathGroup=antClimb(selectePath,cover);
end 函数(1)：随机生成用于计算的图G G=randomGraph(vertexN,edgeN);
%随机构造图函数，vertexN:顶点数，edgeN:边数
function G=randomGraph(vertexN,edgeN)
vertexSet=1:vertexN;%顶点集
maxEdgeN=vertexN*vertexN;%图的最大边数
%边的开始点集
edgeStartSet=round(rand(1,edgeN)*vertexN)+1;
outRange(1,:)=edgeStartSet(:)>vertexN;%检查是否越界
edgeStartSet(outRange)=vertexN;
clear outRange
%边的结束点集
edgeEndSet=round(rand(1,edgeN)*vertexN)+1;
outRange(1,:)=edgeEndSet(:)>vertexN;%检查是否越界
edgeEndSet(outRange)=vertexN;
%为了防止有重复的边，进行检查
n=edgeN;
for i=1:n
for j=i+1:n
if ((edgeStartSet(i)==edgeStartSet(j))...
&& (edgeEndSet(i)==edgeEndSet(j)))...
||...
((edgeEndSet(i)==edgeStartSet(j))...
&& (edgeStartSet(i)==edgeEndSet(j)))
edgeStartSet(j)=0;%为相同的边做记号
edgeEndSet(j)=0;
end
end
end
i=0;
while i<n
for i=1:n%删除相同的边
if edgeStartSet(i)==0
edgeStartSet(i)=[];
edgeEndSet(i)=[];
n=size(edgeStartSet,2);
break
end
end
end
if edgeStartSet(n)==0
edgeStartSet(n)=[];
edgeEndSet(n)=[];
end
G{1}=vertexSet;%图的顶点集
G{2}=edgeStartSet;%图的边集上的开始点集
G{3}=edgeEndSet;%图的边集上的结束点集 函数(2)：判定蚂蚁路线是否可以覆盖边集
%判定路线的上点是否可以覆盖边集E
%cover:包含路线是否覆盖了边集的信息
cover=includeEdgeDot(pathGroup,G);
function cover=includeEdgeDot(roadGroup,G)
%这个函数检查蚂蚁选择的路线(顶点集V中若干个点的组合)是否可以覆盖边集
%roadGroup:蚂蚁走的路线。
%G:图G，包含3个向量：顶点集V，边的开端集E1，边的末端集E2
E1=G{2};%取得开端集。行向量
E2=G{3};%取得末端集。行向量
edgeN=size(E1,2);%取得边数
roadN=size(roadGroup,1);%路线数，也是蚂蚁数
vertexN=size(roadGroup(1,:),2);%取得图G中的顶点数
%检查路线是否覆盖边集的算法如下
%1 取一条蚂蚁走的路线
%2 从边集E中取出一条边
%3 把边的两个端点逐一与路线上的点比较，如果路线上的点就是边的端点(头或者尾)，
% 把这条边删除。
%4 如果E={}，E被路线覆盖，检查停止，到6
%5 到2
%6 到1
for roadi=1:roadN%对路线循环环，也就是取出路线
stopWhile=0;e1=E1;e2=E2;
while stopWhile==0 %对边循环，也就是从E中取出一条边
%把边的两个端点逐一与路线上的点比较，如果路线上的点就是边的端点(头或者尾)，
%把这条边删除
%循环停止的2个条件：
%1 检查完边集E中所有的边
%2 检查完路线上所有的点
deleteEdge=0;
for vertexi=1:vertexN%检查路线上的所有点
%对于for循环，在end(for结束处)检查vertexi是否到界
%顶点集V中的第vertexi顶点在第roadi条路上
if roadGroup(roadi,vertexi)==1
%边集E中的第edgei条边的头或者尾是顶点vertexi，把这条边删除
%相当于一个堆栈，从顶比较，从顶删
if e1(1)==vertexi || e2(1)==vertexi
e1(1)=[];%删除第edgei条边
e2(1)=[];
deleteEdge=1;
EedgeN=size(e1,2);
if EedgeN==0;
stopWhile=1;
cover(roadi,1)=1;%第roadi条路线可以覆盖边E
break
end
end
end
end
if vertexi==vertexN && deleteEdge==0 %
cover(roadi,1)=0;
stopWhile=1;
end
end
end 函数(3)：计算路线上的点数
%如果路线不能覆盖边集E，pathVertexN=Inf,即无穷大
pathVertexN=patheVertex(cover,pathGroup);
%cover:包含路线是否覆盖了边集的信息
%roadGroup:路线
%cover(i)=0,第i条路线roadGroup(i)不能覆盖边集
%cover(i)=1,第i条路线roadGroup(i)覆盖了边集
%pathVertexN:路线上的顶点数
%如果路线不能覆盖边集E，pathVertexN=Inf,即无穷大
function pathVertexN=patheVertex(cover,roadGroup)
pathN=size(cover,1);
for i=1:pathN
if cover(i,1)==0%路线不能覆盖边集E，pathVertexN=Inf,即无穷大
pathVertexN(i,1)=Inf;
else%路线覆盖边集E，pathVertexN=点数
pathVertexN(i,1)=sum(roadGroup(i,:),2);
end
end 函数(4)：通过本次的最好路线bestRoad与上次保留的最好路线holdBestRoad比较，保存迭代中的最优路线
...
=compareBestRoad(holdBestRoad,holdVertexN,...
bestRoad,minVertexN); 函数(5)：给路线赋概率，也就是信息素
=roadProbability(pathVertexN);
%根据待解的非线性函数的误差计算染色体的概率
function =roadProbability(chromosomeRedundance)
redundanceSum=size(chromosomeRedundance,1);
InfN=sum(isinf(chromosomeRedundance));%估计非线性方程计算的结果
if InfN==redundanceSum
isP='Fail';
p=0;
return
else
isP='True';
errorReciprocal=1./chromosomeRedundance;
sumReciprocal=sum(errorReciprocal);
p=errorReciprocal/sumReciprocal;%p:可能解所对应的染色体的概率
end 函数(6)：按照信息素选择路线
selectePath=selecteRoad(pathGroup,p);
function chromosome=selecteRoad(chromosomeGroup,p)
cumuP=cumsum(p);%累积概率,也就是把每个染色体的概率映射到0~1的区间
=size(chromosomeGroup);
for i=1:chromosomeSum%这个循环产生概率值
rN=rand(1);
if rN==1%取最后一条路
chromosome(i,:)=chromosomeGroup(chromosomeSum,:);
elseif (0<=rN) && (rN<cumuP(1))
chromosome(i,:)=chromosomeGroup(1,:);%第1条染色体被选中
else
for j=2:chromosomeSum%这个循环确定第1条以后的哪一条染色体被选中
if (cumuP(j-1)<=rN) && (rN<cumuP(j))
chromosome(i,:)=chromosomeGroup(j,:);
break
end
end
end
end 函数(7)：改变路线
pathGroup=antClimb(selectePath,cover);
%改变路线
%改变方法：
%在一条路线上随机确定一个点位
%如果这条路线不能覆盖边E，
% 这个点位=0，让这个点位=1，即添加与点位对应的点
%如果这条路线覆盖边E，
% 这个点位=1，让这个点位=0，即去掉与点位对应的点
function path=antClimb(path,cover)
=size(path);
for i=1:pathN
pathDotP=fix(rand(1)*pathLength)+1;%随机确定改变路线的点位
if pathDotP>pathLength%防止点位超出路线长度
pathDotP=pathLength;
end
if cover(i,1)==0%这条路线不能覆盖边E，
if path(i,pathDotP)==0%添加点
path(i,pathDotP)=1;
else%强制添加点
for j=1:pathLength
if path(i,j)==0
path(i,j)=1;
break
end
end
end
else%这条路线覆盖边E，
if path(i,pathDotP)==1%删除点
path(i,pathDotP)=0;
else%强制删除点
for j=1:pathLength
if path(i,j)==1
path(i,j)=0;
break
end
end
end
end
end
来自搜狐博客=〉人工智能 怎么通过不了啊,函数(4)好像有问题
[ 本帖最后由 jiataba3 于 2009-2-15 11:15 编辑 ]
页:
[1]