遺傳演算法路徑
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; //變異概率