【原创】基于遗传算法的有向图的边序列遍历算法Matlab源码

[greensim]

如何从任意一个指定的节点出发，遍历有向图中所有的边，并且使得遍历序列最短，是一个比较复杂的优化问题，其应用背景也有很多，比如用于网页链接的测试系统，下面的源码使用遗传算法实现边序列的优化。本源码由GreenSim团队原创，转载请注明，有意购买源码或代写相关程序，请与GreenSim团队联系（主页http://blog.sina.com.cn/greensim）。

function [BESTX,BESTY,ALLX,ALLY,LC1,LC2]=MYGA(K,N,Pm,VA,VB,P,D)
%% 此函数实现遗传算法，用于用于有向图的边遍历序列的优化
% GreenSim团队原创作品，转载请注明
% Email:[email protected]
% GreenSim团队主页：http://blog.sina.com.cn/greensim
% 欢迎访问GreenSim——算法仿真团队→http://blog.sina.com.cn/greensim
%% 输入参数列表
% K 迭代次数
% N 种群规模，要求是偶数
% Pm 变异概率
% VA 对偶图各边的起点在原图中对应的节点标号
% VB 对偶图各边的终点在原图中对应的节点标号
% P 对偶图各边对应的最短路径，细胞结构
% D 原图的邻接矩阵
%% 输出参数列表
% BESTX K×1细胞结构，每一个元素是M×1向量，记录每一代的最优个体
% BESTY K×1矩阵，记录每一代的最优个体的评价函数值
% ALLX K×1细胞结构，每一个元素是M×N矩阵，记录全部个体
% ALLY K×N矩阵，记录全部个体的评价函数值

%% 第一步：
M=length(VA);%决策变量的个数
%种群初始化，每一行是一个样本
farm=zeros(N,M);
for i=1:N
x=randperm(M);
farm(i,:)=x;
end
%输出变量初始化
ALLX=cell(K,1);%细胞结构，每一个元素是N×M矩阵，记录每一代的种群
ALLY=zeros(K,N);%K×N矩阵，记录每一代评价函数值
BESTX=cell(K,1);%细胞结构，每一个元素是1×M向量，记录每一代的最优个体
BESTY=zeros(K,1);%K×1矩阵，记录每一代的最优个体的评价函数值
k=1;%迭代计数器初始化
LC1=zeros(1,K);
LC2=zeros(1,K);
%% 第二步：迭代过程
while k<=K
%% 以下是交叉过程
newfarm=zeros(4*N,M);
Ser=randperm(N);%两两随机配对的配对表
A=farm(Ser(1),:);
B=farm(Ser(N),:);
[a,b,c,d]=CrossOver(A,B);
newfarm(4*N-3,:)=a;%加入子代种群
newfarm(4*N-2,:)=b;
newfarm(4*N-1,:)=c;
newfarm(4*N,:)=d;

for i=1:(N-1)
A=farm(Ser(i),:);
B=farm(Ser(i+1),:);
[a,b,c,d]=CrossOver(A,B);
newfarm(4*i-3,:)=a;%加入子代种群
newfarm(4*i-2,:)=b;
newfarm(4*i-1,:)=c;
newfarm(4*i,:)=d;
end

FARM=[farm;newfarm];

%% 选择复制
SER=randperm(5*N);
FITNESS=zeros(1,5*N);
fitness=zeros(1,N);
for i=1:(5*N)
x=FARM(i,:);
[y,f]=FIT1(x,VA,VB,P,D);
FITNESS(i)=f;
end

for i=1:N
f1=FITNESS(SER(5*i-4));
f2=FITNESS(SER(5*i-3));
f3=FITNESS(SER(5*i-2));
f4=FITNESS(SER(5*i-1));
f5=FITNESS(SER(5*i));
if f1<=f2&&f1<=f3&&f1<=f4&&f1<=f5
farm(i,:)=FARM(SER(5*i-4),:);
fitness(i)=FITNESS(SER(5*i-4));
elseif f2<=f1&&f2<=f3&&f2<=f4&&f2<=f5
farm(i,:)=FARM(SER(5*i-3),:);
fitness(i)=FITNESS(SER(5*i-3));
elseif f3<=f1&&f3<=f2&&f3<=f4&&f3<=f5
farm(i,:)=FARM(SER(5*i-2),:);
fitness(i)=FITNESS(SER(5*i-2));
elseif f4<=f1&&f4<=f2&&f4<=f3&&f4<=f5
farm(i,:)=FARM(SER(5*i-1),:);
fitness(i)=FITNESS(SER(5*i-1));
else
farm(i,:)=FARM(SER(5*i),:);
fitness(i)=FITNESS(SER(5*i));
end
end

%% 记录最佳个体和收敛曲线
X=farm;
Y=fitness;
ALLX{k}=X;
ALLY(k,:)=Y;
minY=min(Y);
meanY=mean(Y);
pos=find(Y==minY);
BESTX{k}=X(pos(1),:);
BESTY(k)=minY;
LC1(k)=minY;
LC2(k)=meanY;
%% 变异
for i=1:N
if Pm>rand&&pos(1)~=i
A=farm(i,:);
B=randperm(M);
[a,b,c,d]=CrossOver(A,B);
farm(i,:)=a;
end
end
disp(k);
k=k+1;
end