蚂蚁算法解顶点覆盖问题

frogfish

%这是最小顶点覆盖的蚁群算法主程序

%最小顶点覆盖是指：
%图G=(V，E)
%找到一个V'，V'包含于V
%min |V'|
%s.t. (u,v)是E中的任一边，存在u或者v属于V'

1. %主程序运行过程
   
2. %1 初始化
   
3. %2 随机生成初始可能解：蚂蚁走的路线
   
4. %3 判定路线是不是最好的，如果是最好的，给出结果，结束程序
   
5. %4 把最好的路线保留下来。给路线赋概率，也就是信息素
   
6. %5 按信息素选路线
   
7. %6 改变路线，产生新路线
   
8. %7 到3
   
9. 主程序调用的函数：
   
10. 函数(1)：随机生成用于计算的图G G=randomGraph(vertexN,edgeN);
    
11. 函数(2)：判定蚂蚁路线是否可以覆盖边集
    
12. %判定路线的上点是否可以覆盖边集E
    
13. %cover:包含路线是否覆盖了边集的信息
    
14. cover=includeEdgeDot(pathGroup,G);
    
15. 函数(3)：计算路线上的点数
    
16. %如果路线不能覆盖边集E，pathVertexN=Inf,即无穷大
    
17. pathVertexN=patheVertex(cover,pathGroup);
    
18. 函数(4)：通过本次的最好路线bestRoad与上次保留的最好路线holdBestRoad比较，保存迭代中的最优路线
    
19. [holdBestRoad,holdVertexN]...
    
20. =compareBestRoad(holdBestRoad,holdVertexN,...
    
21. bestRoad,minVertexN);
    
22. 函数(5)：给路线赋概率，也就是信息素
    
23. [p,trueP]=roadProbability(pathVertexN);
    
24. 函数(6)：按照信息素选择路线
    
25. selectePath=selecteRoad(pathGroup,p);
    
26. 函数(7)：改变路线
    
27. pathGroup=antClimb(selectePath,cover);
    
28. 
    
29. clear,clc
    
30. %%%%%%%%%%%%%%%1:初始化
    
31. vertexN=10;%G中顶点的个数
    
32. edgeN=10;%G中边的个数
    
33. %G中有三个数组，第1个：顶点集，第2个：边的端点集，第3个：边的末尾点集
    
34. G=randomGraph(vertexN,edgeN);%生成图G
    
35. antN=3;%蚂蚁数
    
36. pathN=antN;%道路数，一条蚂蚁走一条路
    
37. minVN=3;%最小顶点集中的顶点数,此值只能估计
    
38. holdBestRoad=0;%强制保留的最好的路，防止改变路线时丢失
    
39. holdVertexN=Inf;
    
40. circleN=20;%迭代次数
    
41. 
    
42. 
    
43. 
    
44. %%%%%%%%%%%%%%%%2：随机生成初始可能解：蚂蚁走的路线路线
    
45. %为每个蚂蚁随机生成一条路，一条路是一个二进制串
    
46. pathGroup=round(rand(pathN,vertexN));
    
47. stopWhile=0;
    
48. circle=0;
    
49. while stopWhile==0
    
50. circle=circle+1;
    
51. %%%%%%%%%%%%%3:判定路线的好坏
    
52. %判定路线的上点是否可以覆盖边集E
    
53. %cover:包含路线是否覆盖了边集的信息
    
54. %roadGroup:路线
    
55. %cover(i)=0,第i条路线roadGroup(i)不能覆盖边集
    
56. %cover(i)=1,第i条路线roadGroup(i)覆盖了边集
    
57. cover=includeEdgeDot(pathGroup,G);
    
58. %计算路线上的点数
    
59. %如果路线不能覆盖边集E，pathVertexN=Inf,即无穷大
    
60. pathVertexN=patheVertex(cover,pathGroup);
    
61. %找出最好的路线以及路线上的顶点数
    
62. [minVertexN,minVertexNP]=min(pathVertexN);
    
63. bestRoad=pathGroup(minVertexNP,:);%最好路线
    
64. if minVertexN<minVN
    
65. '程序结束'
    
66. circle
    
67. minVertexN
    
68. pathGroup(minVertexNP,:)
    
69. return
    
70. end
    
71. %本次的最好路线bestRoad与上次保留的最好路线holdBestRoad比较
    
72. [holdBestRoad,holdVertexN]...
    
73. =compareBestRoad(holdBestRoad,holdVertexN,...
    
74. bestRoad,minVertexN);
    
75. %把保留的最好的最好路线holdBestRoad加入到路线组中
    
76. order=round(rand(1)*pathN);
    
77. if order==0
    
78. order=1;
    
79. end
    
80. pathGroup(order,:)=holdBestRoad;
    
81. pathVertexN(order)=holdVertexN;
    
82. %%%%%%%%%%%%%%%4: 给路线赋概率，也就是信息素
    
83. [p,trueP]=roadProbability(pathVertexN);
    
84. if trueP =='Fail'
    
85. '可能解 严重不适应问题，请重新开始'
    
86. return%结束程序
    
87. end
    
88. %%%%%%%%%%%%%%%5：按照信息素选择路线
    
89. selectePath=selecteRoad(pathGroup,p);
    
90. if circle>circleN
    
91. '已达到迭代次数'
    
92. G{:}
    
93. circle
    
94. pathGroup
    
95. cover
    
96. holdBestRoad
    
97. holdVertexN
    
98. return
    
99. end
    
100. %%%%%%%%%%%%%%%6：改变路线
     
101. pathGroup=antClimb(selectePath,cover);
     
102. end

复制代码

frogfish

函数(1)：随机生成用于计算的图G G=randomGraph(vertexN,edgeN);

1. %随机构造图函数，vertexN:顶点数，edgeN:边数
   
2. function G=randomGraph(vertexN,edgeN)
   
3. vertexSet=1:vertexN;%顶点集
   
4. maxEdgeN=vertexN*vertexN;%图的最大边数
   
5. %边的开始点集
   
6. edgeStartSet=round(rand(1,edgeN)*vertexN)+1;
   
7. outRange(1,:)=edgeStartSet(:)>vertexN;%检查是否越界
   
8. edgeStartSet(outRange)=vertexN;
   
9. clear outRange
   
10. %边的结束点集
    
11. edgeEndSet=round(rand(1,edgeN)*vertexN)+1;
    
12. outRange(1,:)=edgeEndSet(:)>vertexN;%检查是否越界
    
13. edgeEndSet(outRange)=vertexN;
    
14. %为了防止有重复的边，进行检查
    
15. n=edgeN;
    
16. for i=1:n
    
17. for j=i+1:n
    
18. if ((edgeStartSet(i)==edgeStartSet(j))...
    
19. && (edgeEndSet(i)==edgeEndSet(j)))...
    
20. ||...
    
21. ((edgeEndSet(i)==edgeStartSet(j))...
    
22. && (edgeStartSet(i)==edgeEndSet(j)))
    
23. edgeStartSet(j)=0;%为相同的边做记号
    
24. edgeEndSet(j)=0;
    
25. end
    
26. end
    
27. end
    
28. i=0;
    
29. while i<n
    
30. for i=1:n%删除相同的边
    
31. if edgeStartSet(i)==0
    
32. edgeStartSet(i)=[];
    
33. edgeEndSet(i)=[];
    
34. n=size(edgeStartSet,2);
    
35. break
    
36. end
    
37. end
    
38. end
    
39. if edgeStartSet(n)==0
    
40. edgeStartSet(n)=[];
    
41. edgeEndSet(n)=[];
    
42. end
    
43. 
    
44. G{1}=vertexSet;%图的顶点集
    
45. G{2}=edgeStartSet;%图的边集上的开始点集
    
46. G{3}=edgeEndSet;%图的边集上的结束点集

复制代码

frogfish

函数(2)：判定蚂蚁路线是否可以覆盖边集

1. %判定路线的上点是否可以覆盖边集E
   
2. %cover:包含路线是否覆盖了边集的信息
   
3. cover=includeEdgeDot(pathGroup,G);
   
4. function cover=includeEdgeDot(roadGroup,G)
   
5. %这个函数检查蚂蚁选择的路线(顶点集V中若干个点的组合)是否可以覆盖边集
   
6. %roadGroup:蚂蚁走的路线。
   
7. %G:图G，包含3个向量：顶点集V，边的开端集E1，边的末端集E2
   
8. E1=G{2};%取得开端集。行向量
   
9. E2=G{3};%取得末端集。行向量
   
10. edgeN=size(E1,2);%取得边数
    
11. roadN=size(roadGroup,1);%路线数，也是蚂蚁数
    
12. vertexN=size(roadGroup(1,:),2);%取得图G中的顶点数
    
13. %检查路线是否覆盖边集的算法如下
    
14. %1 取一条蚂蚁走的路线
    
15. %2 从边集E中取出一条边
    
16. %3 把边的两个端点逐一与路线上的点比较，如果路线上的点就是边的端点(头或者尾)，
    
17. % 把这条边删除。
    
18. %4 如果E={}，E被路线覆盖，检查停止，到6
    
19. %5 到2
    
20. %6 到1
    
21. for roadi=1:roadN%对路线循环环，也就是取出路线
    
22. stopWhile=0;e1=E1;e2=E2;
    
23. while stopWhile==0 %对边循环，也就是从E中取出一条边
    
24. %把边的两个端点逐一与路线上的点比较，如果路线上的点就是边的端点(头或者尾)，
    
25. %把这条边删除
    
26. %循环停止的2个条件：
    
27. %1 检查完边集E中所有的边
    
28. %2 检查完路线上所有的点
    
29. deleteEdge=0;
    
30. for vertexi=1:vertexN%检查路线上的所有点
    
31. %对于for循环，在end(for结束处)检查vertexi是否到界
    
32. %顶点集V中的第vertexi顶点在第roadi条路上
    
33. if roadGroup(roadi,vertexi)==1
    
34. %边集E中的第edgei条边的头或者尾是顶点vertexi，把这条边删除
    
35. %相当于一个堆栈，从顶比较，从顶删
    
36. if e1(1)==vertexi || e2(1)==vertexi
    
37. e1(1)=[];%删除第edgei条边
    
38. e2(1)=[];
    
39. deleteEdge=1;
    
40. EedgeN=size(e1,2);
    
41. if EedgeN==0;
    
42. stopWhile=1;
    
43. cover(roadi,1)=1;%第roadi条路线可以覆盖边E
    
44. break
    
45. end
    
46. end
    
47. end
    
48. end
    
49. if vertexi==vertexN && deleteEdge==0 %
    
50. cover(roadi,1)=0;
    
51. stopWhile=1;
    
52. end
    
53. end
    
54. end

复制代码

frogfish

函数(3)：计算路线上的点数

1. %如果路线不能覆盖边集E，pathVertexN=Inf,即无穷大
   
2. pathVertexN=patheVertex(cover,pathGroup);
   
3. %cover:包含路线是否覆盖了边集的信息
   
4. %roadGroup:路线
   
5. %cover(i)=0,第i条路线roadGroup(i)不能覆盖边集
   
6. %cover(i)=1,第i条路线roadGroup(i)覆盖了边集
   
7. %pathVertexN:路线上的顶点数
   
8. %如果路线不能覆盖边集E，pathVertexN=Inf,即无穷大
   
9. function pathVertexN=patheVertex(cover,roadGroup)
   
10. pathN=size(cover,1);
    
11. for i=1:pathN
    
12. if cover(i,1)==0%路线不能覆盖边集E，pathVertexN=Inf,即无穷大
    
13. pathVertexN(i,1)=Inf;
    
14. else%路线覆盖边集E，pathVertexN=点数
    
15. pathVertexN(i,1)=sum(roadGroup(i,:),2);
    
16. end
    
17. end

复制代码

frogfish

函数(4)：通过本次的最好路线bestRoad与上次保留的最好路线holdBestRoad比较，保存迭代中的最优路线

1. [holdBestRoad,holdVertexN]...
   
2. =compareBestRoad(holdBestRoad,holdVertexN,...
   
3. bestRoad,minVertexN);

复制代码

frogfish

函数(5)：给路线赋概率，也就是信息素

1. [p,trueP]=roadProbability(pathVertexN);
   
2. %根据待解的非线性函数的误差计算染色体的概率
   
3. function [p,isP]=roadProbability(chromosomeRedundance)
   
4. redundanceSum=size(chromosomeRedundance,1);
   
5. InfN=sum(isinf(chromosomeRedundance));%估计非线性方程计算的结果
   
6. 
   
7. if InfN==redundanceSum
   
8. isP='Fail';
   
9. p=0;
   
10. return
    
11. else
    
12. isP='True';
    
13. errorReciprocal=1./chromosomeRedundance;
    
14. sumReciprocal=sum(errorReciprocal);
    
15. p=errorReciprocal/sumReciprocal;%p:可能解所对应的染色体的概率
    
16. end

复制代码

frogfish

函数(6)：按照信息素选择路线

1. selectePath=selecteRoad(pathGroup,p);
   
2. function chromosome=selecteRoad(chromosomeGroup,p)
   
3. cumuP=cumsum(p);%累积概率,也就是把每个染色体的概率映射到0~1的区间
   
4. [chromosomeSum,chromosomeLength]=size(chromosomeGroup);
   
5. for i=1:chromosomeSum%这个循环产生概率值
   
6. rN=rand(1);
   
7. if rN==1%取最后一条路
   
8. chromosome(i,:)=chromosomeGroup(chromosomeSum,:);
   
9. elseif (0<=rN) && (rN<cumuP(1))
   
10. chromosome(i,:)=chromosomeGroup(1,:);%第1条染色体被选中
    
11. else
    
12. for j=2:chromosomeSum%这个循环确定第1条以后的哪一条染色体被选中
    
13. if (cumuP(j-1)<=rN) && (rN<cumuP(j))
    
14. chromosome(i,:)=chromosomeGroup(j,:);
    
15. break
    
16. end
    
17. end
    
18. end
    
19. end

复制代码

frogfish

函数(7)：改变路线

1. pathGroup=antClimb(selectePath,cover);
   
2. %改变路线
   
3. %改变方法：
   
4. %在一条路线上随机确定一个点位
   
5. %如果这条路线不能覆盖边E，
   
6. % 这个点位=0，让这个点位=1，即添加与点位对应的点
   
7. %如果这条路线覆盖边E，
   
8. % 这个点位=1，让这个点位=0，即去掉与点位对应的点
   
9. function path=antClimb(path,cover)
   
10. [pathN,pathLength]=size(path);
    
11. for i=1:pathN
    
12. pathDotP=fix(rand(1)*pathLength)+1;%随机确定改变路线的点位
    
13. if pathDotP>pathLength%防止点位超出路线长度
    
14. pathDotP=pathLength;
    
15. end
    
16. if cover(i,1)==0%这条路线不能覆盖边E，
    
17. if path(i,pathDotP)==0%添加点
    
18. path(i,pathDotP)=1;
    
19. else%强制添加点
    
20. for j=1:pathLength
    
21. if path(i,j)==0
    
22. path(i,j)=1;
    
23. break
    
24. end
    
25. end
    
26. end
    
27. 
    
28. else%这条路线覆盖边E，
    
29. if path(i,pathDotP)==1%删除点
    
30. path(i,pathDotP)=0;
    
31. else%强制删除点
    
32. for j=1:pathLength
    
33. if path(i,j)==1
    
34. path(i,j)=0;
    
35. break
    
36. end
    
37. end
    
38. end
    
39. end
    
40. end

复制代码

来自搜狐博客=〉人工智能

jiataba3

怎么通过不了啊,函数(4)好像有问题

[ 本帖最后由 jiataba3 于 2009-2-15 11:15 编辑 ]