遗传算法路径
1. 遗传算法求最短路径的matlab程序，急求！！
function [path, totalCost, farthestPreviousHop, farthestNextHop] = dijkstra(n, netCostMatrix, s, d, farthestPreviousHop, farthestNextHop)
% path: the list of nodes in the path from source to destination;
% totalCost: the total cost of the path;
% farthestNode: the farthest node to reach for each node after performing
% the routing;
% n: the number of nodes in the network;
% s: source node index;
% d: destination node index;
% clear;
% noOfNodes = 50;
% rand('state', 0);
% figure(1);
% clf;
% hold on;
% L = 1000;
% R = 200; % maximum range;
% netXloc = rand(1,noOfNodes)*L;
% netYloc = rand(1,noOfNodes)*L;
% for i = 1:noOfNodes
% plot(netXloc(i), netYloc(i), '.');
% text(netXloc(i), netYloc(i), num2str(i));
% for j = 1:noOfNodes
% distance = sqrt((netXloc(i) - netXloc(j))^2 + (netYloc(i) - netYloc(j))^2);
% if distance = R
% matrix(i, j) = 1; % there is a link;
% line([netXloc(i) netXloc(j)], [netYloc(i) netYloc(j)], 'LineStyle', ':');
% else
% matrix(i, j) = inf;
% end;
% end;
% end;
%
%
% activeNodes = [];
% for i = 1:noOfNodes,
% % initialize the farthest node to be itself;
% farthestPreviousHop(i) = i; % used to compute the RTS/CTS range;
% farthestNextHop(i) = i;
% end;
%
% [path, totalCost, farthestPreviousHop, farthestNextHop] = dijkstra(noOfNodes, matrix, 1, 15, farthestPreviousHop, farthestNextHop);
% path
% totalCost
% if length(path) ~= 0
% for i = 1:(length(path)-1)
% line([netXloc(path(i)) netXloc(path(i+1))], [netYloc(path(i)) netYloc(path(i+1))], 'Color','r','LineWidth', 0.50, 'LineStyle', '-.');
% end;
% end;
% hold off;
% return;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% all the nodes are un-visited;
visited(1:n) = 0;
distance(1:n) = inf; % it stores the shortest distance between each node and the source node;
parent(1:n) = 0;
distance(s) = 0;
for i = 1:(n-1),
temp = [];
for h = 1:n,
if visited(h) == 0 % in the tree;
temp=[temp distance(h)];
else
temp=[temp inf];
end
end;
[t, u] = min(temp); % it starts from node with the shortest distance to the source;
visited(u) = 1; % mark it as visited;
for v = 1:n, % for each neighbors of node u;
if ( ( netCostMatrix(u, v) + distance(u)) distance(v) )
distance(v) = distance(u) + netCostMatrix(u, v); % update the shortest distance when a shorter path is found;
parent(v) = u; % update its parent;
end;
end;
end;
path = [];
if parent(d) ~= 0 % if there is a path!
t = d;
path = [d];
while t ~= s
p = parent(t);
path = [p path];
if netCostMatrix(t, farthestPreviousHop(t)) netCostMatrix(t, p)
farthestPreviousHop(t) = p;
end;
if netCostMatrix(p, farthestNextHop(p)) netCostMatrix(p, t)
farthestNextHop(p) = t;
end;
t = p;
end;
end;
totalCost = distance(d);
return;
2. 求MATLAB高手 解决路径问题的遗传算法
可以把路径节点看作遗传算法中染色体的基因
这样路径问题就可以转化为函数优化问题
从网上找到基本的遗传算法，稍加改动应该是可以对路径问题进行求解的
建议搜索TSP问题，也可以考虑蚁群算法求解
个人观点，仅供参考
3. 我在做一个车辆路径问题,用遗传算法的,不会MATLAB编程,有人能帮我一下吗
% Optimizing a function using Simple Genetic Algorithm with elitist preserved
%Max f(x1,x2)=10-x1*x1-x2*x2+x1*x2; -2.0480<=x1,x2<=2.0480
clc;clear all;
format long;%Set the data format(设定数据显示格式)
%parameters Initialization (初始化参数)
T=100;% Generation( 仿真代数)
N=80;% Population size ( 群体规模)
pm=0.05;pc=0.8;%Crossover and mutation probability(交叉变异概率)
umax=2.048;umin=-2.048;%Parameter range(参数取值范围)
L=10;%Single parameter string length, the total coding length is 2L(单个参数字串长度，总编码长度2L)
bval=round(rand(N,2*L));%Population Initialization(初始种群)
bestv=-inf;%Optimal fitness Initialization(最优适应度初值)
%Iteration stsar(迭代开始)
for ii=1:T
%Decoding, and the fitness calculation(解码，计算适应度)
for i=1:N
y1=0;y2=0;
for j=1:1:L
y1=y1+bval(i,L-j+1)*2^(j-1);
end
x1=(umax-umin)*y1/(2^L-1)+umin;
for j=1:1:L
y2=y2+bval(i,2*L-j+1)*2^(j-1);
end
x2=(umax-umin)*y2/(2^L-1)+umin;
obj(i)=10-x1*x1-x2*x2+x1*x2; %The objective function(目标函数)
xx(i,:)=[x1,x2];
end
func=obj;%Objective function into the fitness function(目标函数转换为适应度函数)
p=func./sum(func);
q=cumsum(p);%Cumulative(累加)
[fmax,indmax]=max(func);%seeking the best in this generation(求当代最佳个体)
if fmax>=bestv
bestv=fmax;%So far, the best fitness value(到目前为止最优适应度值)
bvalxx=bval(indmax,:);%So far the best bit string(到目前为止最佳位串)
optxx=xx(indmax,:);%So far the optimal parameters(到目前为止最优参数)
end
Bfit1(ii)=bestv; % So far the optimal parameters(存储每代的最优适应度)
%%%%Genetic operation starts(遗传操作开始)
%Roulette wheel selection(轮盘赌选择)
for i=1:(N-1)
r=rand;
tmp=find(r<=q);
newbval(i,:)=bval(tmp(1),:);
end
newbval(N,:)=bvalxx;%Optimal retention(最优保留)
bval=newbval;
%Single-point crossover(单点交叉)
for i=1:2:(N-1)
cc=rand;
if cc<pc
point=ceil(rand*(2*L-1));%To obtain one integer from 1 to 2L-1(取得一个1到2L-1的整数)
ch=bval(i,:);
bval(i,point+1:2*L)=bval(i+1,point+1:2*L);
bval(i+1,point+1:2*L)=ch(1,point+1:2*L);
end
end
bval(N,:)=bvalxx;%Optimal retention(最优保留)
%Locus mutation(位点变异)
mm=rand(N,2*L)<pm;%N lines(N行)
mm(N,:)=zeros(1,2*L);%Variation of the last line not change set to 0(最后一行不变异，强制赋0)
bval(mm)=1-bval(mm);
end
%Output(输出)
plot(Bfit1);% Draw the best fitness evolution curves(绘制最优适应度进化曲线)
bestv %Output the optimal fitness value(输出最优适应度值)
这个遗传的我没试过
下面这个是蚁群的结果
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%%-------------------------------------------------------------------------
%% 主要符号说明
%% C n个城市的坐标，n×2的矩阵
%% NC_max 最大迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因子重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳路线
%% L_best 各代最佳路线的长度
%%=========================================================================
%%第一步：变量初始化
C=[1304,2312;3639,1315;4177,2244;3712,1399;3488,1535;3326,1556]
NC_max=200;
m=31;
Alpha=1;
Beta=5;
Rho=0.1;
Q=100;
n=size(C,1);%n表示问题的规模（城市个数）
D=zeros(n,n);%D表示完全图的赋权邻接矩阵
for i=1:n
for j=1:n
if i~=j
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
else
D(i,j)=eps;
end
D(j,i)=D(i,j);
end
end
Eta=1./D;%Eta为启发因子，这里设为距离的倒数
Tau=ones(n,n);%Tau为信息素矩阵
Tabu=zeros(m,n);%存储并记录路径的生成
NC=1;%迭代计数器
R_best=zeros(NC_max,n);%各代最佳路线
L_best=inf.*ones(NC_max,1);%各代最佳路线的长度
L_ave=zeros(NC_max,1);%各代路线的平均长度
while NC<=NC_max%停止条件之一：达到最大迭代次数
%%第二步：将m只蚂蚁放到n个城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';
%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1));%已访问的城市
J=zeros(1,(n-j+1));%待访问的城市
P=J;%待访问城市的选择概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0
J(Jc)=k;
Jc=Jc+1;
end
end
%下面计算待选城市的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));
%按概率原则选取下一个城市
Pcum=cumsum(P);
Select=find(Pcum>=rand);
to_visit=J(Select(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end
%%第四步：记录本次迭代最佳路线
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1));
end
L(i)=L(i)+D(R(1),R(n));
end
L_best(NC)=min(L);
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:);
L_ave(NC)=mean(L);
NC=NC+1
%%第五步：更新信息素
Delta_Tau=zeros(n,n);
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
end
Tau=(1-Rho).*Tau+Delta_Tau;
%%第六步：禁忌表清零
Tabu=zeros(m,n);
end
%%第七步：输出结果
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:)
Shortest_Length=L_best(Pos(1))
subplot(1,2,1)
DrawRoute(C,Shortest_Route)
subplot(1,2,2)
plot(L_best)
hold on
plot(L_ave)
function DrawRoute(C,R)
%%=========================================================================
%% DrawRoute.m
%% 画路线图的子函数
%%-------------------------------------------------------------------------
%% C Coordinate 节点坐标，由一个N×2的矩阵存储
%% R Route 路线
%%=========================================================================
N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
hold on
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
hold on
end
4. 遗传算法求最短路径
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<malloc.h>
#include<stdlib.h>
#include<string>
using namespace std;
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define INFINITY 200//最大值
#define MAX_VERTEX_NUM 20//最大顶点个数
typedef char VertexType;//定义为char类型
//以下是全局变量,用于保存弗洛伊德算法的路径和长度
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//记录最短路径长度
int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];//记录最短路径标记
//以下是全局变量,用于保存迪杰斯特拉算法的路径和长度
int Distance[MAX_VERTEX_NUM];
VertexType former[MAX_VERTEX_NUM];//终点的前一个顶点
bool final[MAX_VERTEX_NUM];//记录顶点是否在V-S中
typedef struct ArcCell
{
int adj; //顶点关系类型
int weight; //该弧相关信息的指针,在此记录为权值
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum; //顶点数
int arcnum; //弧数
}MGraph;
void InitialMGraph(MGraph &G)//初始化
{
G.arcnum=G.vexnum=0; //初始化边数跟顶点数都为零
for(int i=0;i<MAX_VERTEX_NUM;i++)
for(int j=0;j<MAX_VERTEX_NUM;j++)
{
if(i==j)
G.arcs[i][j].weight=0;
else
G.arcs[i][j].weight=INFINITY; //初始化为200,以200认为是无穷大
}
}
void InsertVex(MGraph &G,VertexType v)//插入顶点
{
if(G.vexnum<=MAX_VERTEX_NUM)
G.vexs[G.vexnum++]=v;
}
void InsertArc(MGraph &G,VertexType v1,VertexType v2)//插入边
{
int m,n;
G.arcnum++;
for(int k=0;k<G.vexnum;k++)
{
if(G.vexs[k]==v1)
m=k;
if(G.vexs[k]==v2)
n=k;
}
//插入
ArcCell A;
cout<<"请输入权值:";
cin>>A.weight;
G.arcs[m][n].weight=A.weight;
}
//迪杰斯特拉最短路径,假设始点就存储在数组中的第一个
void ShortestPath_DIJ(MGraph G,int v0)
{
//初始化距离
for(int v=0;v<G.vexnum;++v)
{
final[v]=false;
Distance[v]=G.arcs[v0][v].weight;
if(Distance[v]<INFINITY&&Distance[v]!=0)
{
former[v]=G.vexs[v0];
}
else
former[v]='#';
}
final[v0]=true;
former[v0]=G.vexs[v0];
for(int i=1;i<G.vexnum;++i)//剩余的G.vexnum-1个顶点
{
int w;
int min=INFINITY;
int v=-1;
for(w=0;w<G.vexnum;++w)
{
if(!final[w]&&Distance[w]<min)
{
v=w;
min=Distance[w];
}
}
if(v!=-1)
{
final[v]=true;//将离顶点V0最近的顶点v加入S集合中
for(w=0;w<G.vexnum;++w)//更新当前的最短路径及距离
{
if(!final[w]&&(min+G.arcs[v][w].weight<Distance[w])&&G.arcs[v][w].weight<INFINITY)
{
Distance[w]=min+G.arcs[v][w].weight;
former[w]=G.vexs[v];
}
}
}
}
}
//输出迪杰斯特拉中的最短路径
void output_ShortestPath_DIJ(MGraph G,int v0)
{
int i;
for(i=1;i<G.vexnum;i++)
{
cout<<G.vexs[v0]<<"->"<<G.vexs[i]<<":";
if(Distance[i]!=INFINITY)
{
cout<<"最短路径长度为:"<<Distance[i]<<" 最短路径的前一个顶点为:"<<former[i];
cout<<endl;
}
else
cout<<"此两顶点之间不存在路径"<<endl;
}
}
//弗洛伊德最短路径
void shortestPath_FLOYD(MGraph G)
{
for(int v=0;v<G.vexnum;++v)
{
for(int w=0;w<G.vexnum;++w)
{
D[v][w]=G.arcs[v][w].weight;
for (int k=0;k< G.vexnum;k++)
P[v][w][k]=-1;
if(D[v][w]<INFINITY) //从v到w有直接路径
P[v][w][v]=w;
}
}
for(int k=0;k<G.vexnum;++k)
{
for(int v=0;v<G.vexnum;v++)
for(int w=0;w<G.vexnum;++w)
if(D[v][w]>D[v][k]+D[k][w])
{
D[v][w]=D[v][k]+D[k][w];
for(int i=0;i<G.vexnum;i++)
{
if(P[v][k][i]!=-1)//原来存了顶点
P[v][w][i]=P[v][k][i];
else
P[v][w][i]=P[k][w][i];
}
}
}
}
//输出弗洛伊德中的最短路径
void output_shortestPath_FLOYD(MGraph G)
{
for(int i=0;i<G.vexnum;++i)
{
for(int j=0;j<G.vexnum;++j)
{
if(i!=j)//自己不能到达自己
{
cout<<G.vexs[i]<<"->"<<G.vexs[j]<<":";
if(D[i][j]==INFINITY)
{
cout<<"此两顶点之间不存在路径"<<endl;
}
else
{
cout<<"最短路径长度为:"<<" "<<D[i][j]<<" ";
cout<<"最短路径为:";
cout<<G.vexs[i];
for(int k=i;k!=-1;k=P[i][j][k])
{
if(k!=i)
cout<<G.vexs[k];
}
cout<<endl;
}
}
}
}
}
int main()
{
int num1;//顶点个数
int num2;//弧个数
cout<<"请输入顶点个数:";
cin>>num1;
cout<<"请输入弧个数:";
cin>>num2;
VertexType v;
MGraph G;
InitialMGraph(G);
cout<<"请输入顶点的信息:"<<endl;
for(int i=0;i<num1;++i)
{
cin>>v;;
InsertVex(G,v);
}
VertexType v1,v2;
for(int j=0;j<num2;++j)
{
cout<<"请输入两个结点数据来表示的边:";
cin>>v1>>v2;
InsertArc(G,v1,v2);
}
ShortestPath_DIJ(G,0);
cout<<"迪杰斯特拉中的最短路径如下:"<<endl;
output_ShortestPath_DIJ(G,0);
cout<<endl<<endl;
shortestPath_FLOYD(G);
cout<<"弗洛伊德中的最短路径如下:"<<endl;
output_shortestPath_FLOYD(G);
return 0;
}
5. 遗传算法求解最短路径问题
#include "stdafx.h"
#include "stdio.h" //标准输入输出库
#include "stdlib.h" //标准函数库
#include "time.h"
#include "iostream.h"
#include "iomanip.h"
#include "math.h" //数学函数库
#define MAX 1 //设定求最大适应值
#define MIN 2
#define CHROMLENGTH 15 //染色体长度，注意编码变化时，要随时修改
#define MAXNUM 1000
#define Cmax 30 //估计最大值
#define Cmin 0 //估计最小值
int PopSize = 150; //每代最大个体数
int FunctionMode = MIN;
double m_fPc = 0.9; //交叉概率
double m_fPm = 0.009; //变异概率
int MaxGeneration = 20; //最大世代数
int d[150][15]; //找到染色体并拷贝到这个数组中
int s[150][15];
int generation; //世代数
int Best_Index; //最好个体下标
int Worst_Index; //最坏个体下标
struct indivial //定义个体数据结构
{
double chrom[CHROMLENGTH+1]; //染色体
double value; //函数值
double fitness; //适应度
};
struct indivial
BestIndivial; //当代最佳个体
struct indivial
WorstIndivial;
struct indivial
Group[150]; //种群
double Random(double Low, double High)//本函数实现随机产生Low-High之间的实数 .意思：随机
{
return((double)rand()/RAND_MAX)*(High-Low)+Low;
}
double Max(double a, double b)
{
if(a>=b) return a;
else return b;
}
void GenerateInitialPopulation()//种群初始化，二进制编码初始化其中'1'表示路径顶点在最短路径中,'0'则反之
{
int i,j;
for(i = 0; i < PopSize; i++)
{
for(j = 1; j < CHROMLENGTH-2; j++)
{
Group[i].chrom[j] = (int)(Random(1,10)<6)?'\0':'\1';
}
Group[i].chrom[CHROMLENGTH-1] = '\1';
Group[i].chrom[0] = '\1';
}
}
void CalculateObjectValue() //计算个体值
{
int i,j,l;
int a[15][15]=
{{0, 3, 5, MAXNUM,MAXNUM,MAXNUM,MAXNUM,4, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,0, MAXNUM,9, 5, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,4, MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,0, 4, 3, MAXNUM,MAXNUM,MAXNUM,5, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,1, 5, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,2, MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, 8, 4, MAXNUM,MAXNUM,6, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,2, MAXNUM,4, MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,MAXNUM,MAXNUM,MAXNUM,9, MAXNUM,6, MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,1, MAXNUM,MAXNUM,0, 7, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,4, 4, MAXNUM,0, 2, MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,5, MAXNUM,7, MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,1 ,MAXNUM,MAXNUM},
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, MAXNUM,MAXNUM,2 },
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0 ,2, 3 },
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0, 1 },
{MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,MAXNUM,0 },};
for(i=0; i < PopSize; i++)
{
for(l=0; l<CHROMLENGTH; l++)
{ if(Group[i].chrom[l]!=0)
{
d[i][l]=a[0][l];
s[i][l]=0;
}
}
d[i][0]=0;
s[i][0]=1;
}
for(i=0; i < PopSize; i++)
{
for(l=0; l<CHROMLENGTH-1; l++)
{
int u=0; //
for(j=0; j<CHROMLENGTH; j++)
{
if(!s[i][j]&&Group[i].chrom[j]=='\1')
{
u=j;
}
s[i][u]=1;
for(int w=0; w<CHROMLENGTH; w++)
if(!s[i][w]&&Group[i].chrom[w]=='\1')
{
d[i][w]=d[i][u]+a[u][w];
}
}
}
Group[i].value = d[i][14];
}
}
void CalculateFitnessValue()//根据优化函数值计算出个体适应度
{
int i;
double temp;
for(i=0; i<PopSize; i++)
{
if(FunctionMode==MAX) //求最大值情况
{
if((Group[i].value + Cmin) > 0.0)
{
temp=Cmin + Group[i].value;
}
else
{
temp=0.0;
}
}
else if(FunctionMode==MIN) //求最小值情况
{
if(Group[i].value<Cmax)
{
temp=Cmax-Group[i].value;
}
else
{
temp=0.0;
}
}
Group[i].fitness=temp;
}
}
void FindBestAndWorstIndivial()//从当前群体中找出适应度最好和最差个体
{
int i;
double sum = 0.0;
Best_Index = 0;
Worst_Index = 0;
BestIndivial = Group[0];
WorstIndivial = Group[0];
for(i = 1; i < PopSize; i++)
{
if(Group[i].fitness > BestIndivial.fitness) //适应度高为更优秀个体
{
BestIndivial = Group[i];
Best_Index = i;
}
else if(Group[i].fitness < WorstIndivial.fitness)
{
WorstIndivial = Group[i];
Worst_Index = i;
}
sum += Group[i].fitness;
}
}
void SelectionOperator()//采用比例选择算子产生新群体
{
int i, index;
double p,sum = 0.0;
struct indivial *NewGroup = new struct indivial[PopSize];
double *cfitness = new double[PopSize]; //存每个个体的概率
for(i = 0; i < PopSize; i++)
{
sum += Group[i].fitness ;
}
for(i = 0; i < PopSize; i++)
{
cfitness[i] = Group[i].fitness/sum;
}
for(i = 1; i < PopSize; i++) //计算累计概率
{
cfitness[i] = cfitness[i-1] + cfitness[i];
}
int temp=0;
for(i = 1; i < PopSize; i++)
{
if(cfitness[temp] > cfitness[i])
temp = i;
}
for(i = 0; i < PopSize; i++) //轮盘赌选择
{
p = (double)(rand()%1000)/1000.0;
index = 0;
while(p > cfitness[index])
{
index++;
}
if(index >= 10)
{
NewGroup[i] = Group[temp];
}
else
{
NewGroup[i] = Group[index];
}
}
//将最好个体复制下来,不参与进化
Group[Best_Index] = Group[Best_Index];
for(i = 0; i < PopSize; i++)
{
if(i != Best_Index)
Group[i] = NewGroup[i];
}
delete []cfitness;
delete []NewGroup;
}
void CrossoverOperator()//采用单点交叉方法产生新群体
{
int i,j;
int index;
int point, temp;
double p;
char ch;
for(i=0; i<PopSize; i++)
{
index=i;
}
for(i=0; i<PopSize; i++)
{
point = (int)Random(0,PopSize-i);
temp=index;
index = point+i;
index = temp;
} //对当前个体进行随机排序
for(i=0; i<PopSize-1; i+=2)
{
p=rand()%1000/1000.0;
if(p < m_fPc)
{
point = (int)Random(0,CHROMLENGTH-1)+1;
for(j = point; j<CHROMLENGTH; j++)
{
if(Group[index].value<MAXNUM&&Group[index+1].value<MAXNUM)
{
ch = (int)Group[index].chrom[j];
Group[index].chrom[j]=Group[index+1].chrom[j];
Group[index+1].chrom[j] = ch;
}
}
}
}
}
void MutationOperator()//随机产生变异位，进行染色体基因位的变异
{
int i,j;
double p;
for(i = 0; i < PopSize; i++)
{
if(i != Best_Index) //保证当前最优个体不参与进化
{
for(j = 0;j < CHROMLENGTH; j++)
{
p = rand()%1000/1000.0;
if(p < m_fPm)
{
if(Group[i].value<MAXNUM)
{
Group[i].chrom[j] = (Group[i].chrom[j]==0)?1:0;
}
}
}
}
}
}
void PerformEvolution()//用当前最好个体代替最差个体
{
Group[Worst_Index] = BestIndivial;
}
void OutPut()//输出计算结果
{
cout<<"所有路径顶点:";
for(int k=0;k<CHROMLENGTH;k++)
{
cout<<setw(3)<<k;
}
cout<<endl;
cout<<"-------------------------------------------------------------------------------"<<endl;
cout<<"最短路径顶点:";
for(int j=0; j<CHROMLENGTH; j++)
{
cout<<setw(3)<<BestIndivial.chrom[j];
}
cout<<endl;
cout<<"最短路径长度:";
cout<<setw(3)<<BestIndivial.value;
cout<<endl;
}
void main(void)
{
generation = 0; //意思：一代，代
GenerateInitialPopulation(); //二进制编码初始化'1'表示路径顶点在最短路径中。意思：最初的群体
CalculateObjectValue(); //计算优化函数值. 意思：计算个体值
CalculateFitnessValue(); //根据优化函数值计算出个体适应度
FindBestAndWorstIndivial(); //从当前群体中找出适应度最好和最差个体
while(generation < MaxGeneration)
{
generation++;
SelectionOperator(); //采用比例选择算子产生新群体。意思：选择
CrossoverOperator(); //采用单点交叉方法产生新群体。意思：交叉
MutationOperator(); //随机产生变异位，进行染色体基因位的变异。意思：突变操作
CalculateObjectValue(); //计算个体值。意思：计算个体值
CalculateFitnessValue(); //根据优化函数值计算出个体适应度。意思：适应度
FindBestAndWorstIndivial(); //从当前群体中找出适应度最好和最差个体。意思：个体
PerformEvolution(); //用当前最好个体代替最差个体。意思：实行进化
}
OutPut(); //输出计算结果
}
6. 没学过matlab,下面是遗传算法解决车辆路径算法，请解释一下选择，和交叉，谢谢！！！
[x,lumda]=eig(A);
这句是得到A的特征值和相应的特征向量.
会发现x是特征向量，是N*N的矩阵(N是A的大小），即3*3
而lumda也是一个3*3的矩阵，不过它只是对角线上有值。
只要找到对角线上绝对值最大的列。然后输出x相应的列就是最大特征根对应的特征值。
r=abs(sum(lumda))，先对lumda进行列求和。然后求绝对值，实际上就是求对角线元素的绝对值。
n=find(r==max(r))，首先先求出r中最大的值，然后再找到哪一列是最大的值。最后得到的n是最大特征值对应的列。
于是最大特征值为lumda中第n行第n列(lumda是方阵，其实就是求它的第n个对角元)
相应的特征向量，就是x中第n列。
7. 基于遗传算法路径优化C++编程
[cpp]
bool CAStar::Search(int X, int Y, std::list<POINT> &lResult, double dbGapBreak)
{
if(X < 0 || Y < 0
|| X > m_dwMapWidth || Y > m_dwMapWidth ||
m_dwDestinationX < 0 || m_dwDestinationX < 0 ||
m_dwDestinationX > m_dwMapWidth || m_dwDestinationY > m_dwMapHeight)
{
//_outf("坐标或地图参数错误！");
return false;
}
LPAPOINT p = new APOINT;
p->x = X;
p->y = Y;
p->parent = NULL;
p->dbGap = _p2g(X, Y, m_dwDestinationX, m_dwDestinationY);
m_lOpen.push_front(p);//起始节点加入到开启列表
m_lSafe.push_back(p);//加入到公共容器，任何新分配的节点，都要加入到这里，便于算法执行完后清理
std::list<LPAPOINT>::iterator it;
DWORD dwTime = clock();
while(!m_lOpen.empty())
{
//这里就是反复遍历开启列表选择距离最小的节点
it = GetMingapNode();
if((*it)->dbGap <= dbGapBreak)
break;
p = *it;
GenerateSuccessors(it);
}
if(!m_lOpen.empty())
{
//如果列表不为空，从最后一个节点开始拷贝路径到返回值中
//_outf("最终寻路到：%X, %X", p->x, p->y);
POINT point;
while(p)
{
point.x = p->x;
point.y = p->y;
lResult.push_front(point);
p = p->parent;
}
}
for(it = m_lSafe.begin(); it != m_lSafe.end(); ++it)
{
//清理内存
if(*it != NULL)
{
m_pMap[(*it)->y][(*it)->x] = 1;//会被添加到m_lSafe的节点，一定是最初为1的节点，所以可以在这里恢复地图数据
delete (*it);
*it = NULL;
}
}
m_lSafe.clear();//清空容器
//_outf("耗时：%d 毫秒", clock() - dwTime);
if(m_lOpen.empty())
{
//_outf("寻路失败");
return false;
}
m_lOpen.clear();//清空开启列表
//_outf("寻路成功，节点数：%d", lResult.size());
return true;
}
bool CAStar::Search(int X, int Y, std::list<POINT> &lResult, double dbGapBreak)
{
if(X < 0 || Y < 0
|| X > m_dwMapWidth || Y > m_dwMapWidth ||
m_dwDestinationX < 0 || m_dwDestinationX < 0 ||
m_dwDestinationX > m_dwMapWidth || m_dwDestinationY > m_dwMapHeight)
{
//_outf("坐标或地图参数错误！");
return false;
}
LPAPOINT p = new APOINT;
p->x = X;
p->y = Y;
p->parent = NULL;
p->dbGap = _p2g(X, Y, m_dwDestinationX, m_dwDestinationY);
m_lOpen.push_front(p);//起始节点加入到开启列表
m_lSafe.push_back(p);//加入到公共容器，任何新分配的节点，都要加入到这里，便于算法执行完后清理
std::list<LPAPOINT>::iterator it;
DWORD dwTime = clock();
while(!m_lOpen.empty())
{
//这里就是反复遍历开启列表选择距离最小的节点
it = GetMingapNode();
if((*it)->dbGap <= dbGapBreak)
break;
p = *it;
GenerateSuccessors(it);
}
if(!m_lOpen.empty())
{
//如果列表不为空，从最后一个节点开始拷贝路径到返回值中
//_outf("最终寻路到：%X, %X", p->x, p->y);
POINT point;
while(p)
{
point.x = p->x;
point.y = p->y;
lResult.push_front(point);
p = p->parent;
}
}
for(it = m_lSafe.begin(); it != m_lSafe.end(); ++it)
{
//清理内存
if(*it != NULL)
{
m_pMap[(*it)->y][(*it)->x] = 1;//会被添加到m_lSafe的节点，一定是最初为1的节点，所以可以在这里恢复地图数据
delete (*it);
*it = NULL;
}
}
m_lSafe.clear();//清空容器
//_outf("耗时：%d 毫秒", clock() - dwTime);
if(m_lOpen.empty())
{
//_outf("寻路失败");
return false;
}
m_lOpen.clear();//清空开启列表
//_outf("寻路成功，节点数：%d", lResult.size());
return true;
}
新增的SearchEx源代码如下：
nBeginSift 参数为循环初始值，nEndSift为循环结束值，其实就是一个for循环的起始值与结束值。
这个循环的引用计数，最终会被 乘于 10 来作为距离分段选择路径进行路线优化
nBeginSift 与 nEndSift的间距越大，并不表示最终路径就越好，最终优化出来的路径，还是会和地形有关。
其实最好路径优化算法是按照角度的变化来选择路径优化，但是预计开销会比较大，有了这个优化方式作为基础，你可以自己去写根据角度变化来优化的算法。
[cpp]
bool CAStar::SearchEx(int X, int Y, std::list<POINT> &lResult, double dbGapBreak, int nBeginSift, int nEndSift)
{
DWORD dwTime = clock();
if(!Search(X, Y, lResult, dbGapBreak))
return false;
std::list<POINT>::iterator it = lResult.begin();
std::list<POINT>::iterator it2 = it;
std::list<POINT> l2;
for(int i = nBeginSift; i < nEndSift; i++)
{
it = lResult.begin();
it2 = it;
for(;it != lResult.end(); ++it)
{
if(_p2g(it2->x, it2->y, it->x, it->y) > (double)(i * 10))
{
SetDestinationPos(it->x, it->y);
l2.clear();
if(Search(it2->x, it2->y, l2, 0.0))
{
it = lResult.erase(it2, it);
lResult.insert(it, (l2.begin()), (l2.end()));
}
it2 = it;
}
}
}
_outf("耗时：%d 毫秒", clock() - dwTime);
return true;
}
bool CAStar::SearchEx(int X, int Y, std::list<POINT> &lResult, double dbGapBreak, int nBeginSift, int nEndSift)
{
DWORD dwTime = clock();
if(!Search(X, Y, lResult, dbGapBreak))
return false;
std::list<POINT>::iterator it = lResult.begin();
std::list<POINT>::iterator it2 = it;
std::list<POINT> l2;
for(int i = nBeginSift; i < nEndSift; i++)
{
it = lResult.begin();
it2 = it;
for(;it != lResult.end(); ++it)
{
if(_p2g(it2->x, it2->y, it->x, it->y) > (double)(i * 10))
{
SetDestinationPos(it->x, it->y);
l2.clear();
if(Search(it2->x, it2->y, l2, 0.0))
{
it = lResult.erase(it2, it);
lResult.insert(it, (l2.begin()), (l2.end()));
}
it2 = it;
}
}
}
_outf("耗时：%d 毫秒", clock() - dwTime);
return true;
}
8. 遗传算法求数组结构的图最短路径时染色体怎么编码
#include "stdafx.h"
#include "stdio.h" //标准输入输出库
#include "stdlib.h" //标准函数库
#include "time.h"
#include "iostream.h"
#include "iomanip.h"
#include "math.h" //数学函数库
#define MAX 1 //设定求最大适应值
#define MIN 2
#define CHROMLENGTH 15 //染色体长度,注意编码变化时,要随时修改
#define MAXNUM 1000
#define Cmax 30 //估计最大值
#define Cmin 0 //估计最小值
int PopSize = 150; //每代最大个体数
int FunctionMode = MIN;
double m_fPc = 0.9; //交叉概率
double m_fPm = 0.009; //变异概率