遺傳演算法最短路徑
❶ 數學建模中，給出非常多的節點，求這些節點的最短路徑（類似一條線的路徑），應該用什麼演算法好
下面是我自己編寫的一段代碼，用來求過包含兩千多個點的最短路，速度很快，比遺傳、蟻群快而且最短路更短。你可以試試看，有問題再問我。
function [S,len]=short(P)
% 此程序用來求相同類型點間的最短路
% P表示某一類型的點的坐標矩陣
% p是最短路徑
% d是路徑權值和
%建立權值矩陣
n=length(P);%求該類型點的數量
W=zeros(n,n);
for i=1:n %計算權值並填充權值矩陣,由於各點聯通，此權值矩陣就是該圖的最短路矩陣
for j=(i+1):n
W(i,j)=sqrt((P(i,1)-P(j,1))^2+(P(i,2)-P(j,2))^2);
end
end
for i=2:n
for j=1:(i-1)
W(i,j)=W(j,i);
end
end
%求通過所有點的最短路
%先求從i點至j點，必須通過指定其他n-2個點的最短路,選出其中的的最短路
S=zeros(1,n);
S(1)=1; %先插入1,2點，以此為基準，每次插進一個新點
S(2)=2;
d1=2*W(1,2);
for i=3:n %新加入的點的標號
d1i=zeros(1,i); %插入第i個點，有i中可能的距離,其中最小值將為該輪的d1
for j=1:i %新加入點的位置，插入第i個點是有i個空位可供選擇
if j==1 %在第一個空位插入
d1i(j)=d1+W(i,S(1))+W(i,S(i-1))-W(S(1),S(i-1)); %插入點在首端時，距離為原距離與第i點與上一次插入後的第1位置的點之間距離之和
end
if j>1 & j<i %在中間的空位插入
d1i(j)=d1+W(S(j-1),i)+W(i,S(j))-W(S(j-1),S(j));
end
if j==i
d1i(j)=d1+W(S(i-1),i)+W(S(1),i)-W(S(1),S(i-1));
end
end
[d1,I]=min(d1i);
S((I+1):i)=S(I:(i-1)); %將第I位後面的點後移一位
S(I)=i;%將第i點插入在I位置
end
len=d1;
下面這段代碼是我用來把上面的結果保存到txt文件中的代碼，如果你需要，可以用用。代碼是我上次用過的沒有改，你自己按照需要自己改吧。
clear
close all
clc
loaddata
X=[C;E;I;J];
[S,len]=short(X);
DrawPath(S,X);
print(1,'-dpng','cmeiju3.png');
% 將結果保存至txt文件
fid=fopen('cmeijulujin.txt','wt'); %創建alunjin.txt文件
fprintf(fid,'c號刀具\n');
fprintf(fid,'%d %d\n',X(S));
save('cmeijus','S');
save('cmeijulen','len');
❷ 怎麼在matlab中運用遺傳演算法求解車輛最短路徑問題
建議先在論壇裡面搜一下吧，之前很多帖子都有就這個問題進行討論的，有不少帖子寫的很好的:)
❸ 遺傳演算法tsp問題求解~80高分求解還會繼續加分
遺傳演算法GA
遺傳演算法：
旅行商問題(traveling saleman problem,簡稱tsp)：
已知n個城市之間的相互距離，現有一個推銷員必須遍訪這n個城市，並且每個城市只能訪問一次，最後又必須返回出發城市。如何安排他對這些城市的訪問次序，可使其旅行路線的總長度最短？
用圖論的術語來說，假設有一個圖 g=(v,e)，其中v是頂點集，e是邊集，設d=(dij)是由頂點i和頂點j之間的距離所組成的距離矩陣，旅行商問題就是求出一條通過所有頂點且每個頂點只通過一次的具有最短距離的迴路。
這個問題可分為對稱旅行商問題(dij=dji,,任意i,j=1,2,3，…,n)和非對稱旅行商問題(dij≠dji,,任意i,j=1,2,3，…,n)。
若對於城市v={v1,v2,v3,…,vn}的一個訪問順序為t=(t1,t2,t3,…,ti,…,tn),其中ti∈v(i=1,2,3,…,n)，且記tn+1= t1，則旅行商問題的數學模型為：
min l=σd(t(i),t(i+1)) （i=1,…,n）
旅行商問題是一個典型的組合優化問題，並且是一個np難問題，其可能的路徑數目與城市數目n是成指數型增長的，所以一般很難精確地求出其最優解，本文採用遺傳演算法求其近似解。
遺傳演算法：
初始化過程：用v1,v2,v3,…,vn代表所選n個城市。定義整數pop-size作為染色體的個數，並且隨機產生pop-size個初始染色體，每個染色體為1到18的整數組成的隨機序列。
適應度f的計算：對種群中的每個染色體vi，計算其適應度，f=σd(t(i),t(i+1)).
評價函數eval(vi)：用來對種群中的每個染色體vi設定一個概率，以使該染色體被選中的可能性與其種群中其它染色體的適應性成比例，既通過輪盤賭，適應性強的染色體被選擇產生後台的機會要大，設alpha∈(0,1)，本文定義基於序的評價函數為eval(vi)=alpha*(1-alpha).^(i-1) 。[隨機規劃與模糊規劃]
選擇過程：選擇過程是以旋轉賭輪pop-size次為基礎，每次旋轉都為新的種群選擇一個染色體。賭輪是按每個染色體的適應度進行選擇染色體的。
step1 、對每個染色體vi,計算累計概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1,…pop-size.
step2、從區間(0,pop-size)中產生一個隨機數r；
step3、若qi-1<r<qi,則選擇第i個染色體 ；
step4、重復step2和step3共pop-size次，這樣可以得到pop-size個復制的染色體。
grefenstette編碼：由於常規的交叉運算和變異運算會使種群中產生一些無實際意義的染色體，本文採用grefenstette編碼《遺傳演算法原理及應用》可以避免這種情況的出現。所謂的grefenstette編碼就是用所選隊員在未選（不含淘汰）隊員中的位置，如：
8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1
對應：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。
交叉過程：本文採用常規單點交叉。為確定交叉操作的父代，從 到pop-size重復以下過程：從[0，1]中產生一個隨機數r，如果r<pc ，則選擇vi作為一個父代。
將所選的父代兩兩組隊，隨機產生一個位置進行交叉，如：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1
交叉後為：
8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1
6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1
變異過程：本文採用均勻多點變異。類似交叉操作中選擇父代的過程，在r<pm 的標准下選擇多個染色體vi作為父代。對每一個選擇的父代，隨機選擇多個位置，使其在每位置按均勻變異（該變異點xk的取值范圍為[ukmin,ukmax],產生一個[0，1]中隨機數r，該點變異為x'k=ukmin+r(ukmax-ukmin)）操作。如：
8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1
變異後：
8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1
反grefenstette編碼：交叉和變異都是在grefenstette編碼之後進行的，為了循環操作和返回最終結果，必須逆grefenstette編碼過程，將編碼恢復到自然編碼。
循環操作：判斷是否滿足設定的帶數xzome，否，則跳入適應度f的計算；是，結束遺傳操作，跳出。
//c++的程序
#include<iostream.h>
#include<stdlib.h>
template<class T>
class Graph
{
public:
Graph(int vertices=10)
{
n=vertices;
e=0;
}
~Graph(){}
virtual bool Add(int u,int v,const T& w)=0;
virtual bool Delete(int u,int v)=0;
virtual bool Exist(int u,int v)const=0;
int Vertices()const{return n;}
int Edges()const{return e;}
protected:
int n;
int e;
};
template<class T>
class MGraph:public Graph<T>
{
public:
MGraph(int Vertices=10,T noEdge=0);
~MGraph();
bool Add(int u,int v,const T& w);
bool Delete(int u,int v);
bool Exist(int u,int v)const;
void Floyd(T**& d,int**& path);
void print(int Vertices);
private:
T NoEdge;
T** a;
};
template<class T>
MGraph<T>::MGraph(int Vertices,T noEdge)
{
n=Vertices;
NoEdge=noEdge;
a=new T* [n];
for(int i=0;i<n;i++){
a[i]=new T[n];
a[i][i]=0;
for(int j=0;j<n;j++)if(i!=j)a[i][j]=NoEdge;
}
}
template<class T>
MGraph<T>::~MGraph()
{
for(int i=0;i<n;i++)delete[]a[i];
delete[]a;
}
template<class T>
bool MGraph<T>::Exist(int u,int v)const
{
if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge)return false;
return true;
}
template<class T>
bool MGraph<T>::Add(int u,int v,const T& w)
{
if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]!=NoEdge){
cerr<<"BadInput!"<<endl;
return false;
}
a[u][v]=w;
e++;
return true;
}
template<class T>
bool MGraph<T>:delete(int u,int v)
{
if(u<0||v<0||u>n-1||v>n-1||u==v||a[u][v]==NoEdge){
cerr<<"BadInput!"<<endl;
return false;
}
a[u][v]=NoEdge;
e--;
return true;
}
template<class T>
void MGraph<T>::Floyd(T**& d,int**& path)
{
d=new T* [n];
path=new int* [n];
for(int i=0;i<n;i++){
d[i]=new T[n];
path[i]=new int[n];
for(int j=0;j<n;j++){
d[i][j]=a[i][j];
if(i!=j&&a[i][j]<NoEdge)path[i][j]=i;
else path[i][j]=-1;
}
}
for(int k=0;k<n;k++){
for(i=0;i<n;i++)
for(int j=0;j<n;j++)
if(d[i][k]+d[k][j]<d[i][j]){
d[i][j]=d[i][k]+d[k][j];
path[i][j]=path[k][j];
}
}
}
template<class T>
void MGraph<T>::print(int Vertices)
{
for(int i=0;i<Vertices;i++)
for(int j=0;j<Vertices;j++)
{
cout<<a[i][j]<<' ';if(j==Vertices-1)cout<<endl;
}
}
#define noEdge 10000
#include<iostream.h>
void main()
{
cout<<"請輸入該圖的節點數："<<endl;
int vertices;
cin>>vertices;
MGraph<float> b(vertices,noEdge);
cout<<"請輸入u,v,w:"<<endl;
int u,v;
float w;
cin>>u>>v>>w;
while(w!=noEdge){
//u=u-1;
b.Add(u-1,v-1,w);
b.Add(v-1,u-1,w);
cout<<"請輸入u,v,w:"<<endl;
cin>>u>>v>>w;
}
b.print(vertices);
int** Path;
int**& path=Path;
float** D;
float**& d=D;
b.Floyd(d,path);
for(int i=0;i<vertices;i++){
for(int j=0;j<vertices;j++){
cout<<Path[i][j]<<' ';
if(j==vertices-1)cout<<endl;
}
}
int *V;
V=new int[vertices+1];
cout<<"請輸入任意一個初始H-圈："<<endl;
for(int n=0;n<=vertices;n++){
cin>>V[n];
}
for(n=0;n<55;n++){
for(i=0;i<n-1;i++){
for(int j=0;j<n-1;j++)
{
if(i+1>0&&j>i+1&&j<n-1){
if(D[V[i]][V[j]]+D[V[i+1]][V[j+1]]<D[V[i]][V[i+1]]+D[V[j]][V[j+1]]){
int l;
l=V[i+1];V[i+1]=V[j];V[j]=l;
}
}
}
}
}
float total=0;
cout<<"最小迴路："<<endl;
for(i=0;i<=vertices;i++){
cout<<V[i]+1<<' ';
}
cout<<endl;
for(i=0;i<vertices;i++)
total+=D[V[i]][V[i+1]];
cout<<"最短路徑長度："<<endl;
cout<<total;
}
這個你 看得懂么？
❹ 遺傳演算法求最短路徑
#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;
}
❺ 利用遺傳演算法求解TSP問題 從北京出發 四個城市
作為一種模擬生物自然遺傳與進化過程的優化方法,遺傳演算法(GA)因其具有隱並行性、不需目標函數可微等特點,常被用於解決一些傳統優化方法難以解決的問題。旅行商問題(TSP)是典型的NP難題組合優化問題之一,且被廣泛應用於許多領域,所以研究遺傳演算法求解TSP具有重要的理論意義和應用價值。具有量子計算諸多特點的量子遺傳演算法(OGA)作為—新的概率進化演算法,在解決實際問題時,其高度並行性能極大地提高計算效率,因而研究OGA求解TSP同樣有重要的價值;而將具有遍歷性和隨機性的「混沌」概念引入量子遺傳演算法求解較復雜的組合優化問題又為求解優化問題開拓了一個新的思路。
❻ 遺傳演算法求解最短路徑問題
#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(); //輸出計算結果
}
❼ 遺傳演算法求最短路徑的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;
❽ 如何使用 Grasshopper 生成若干點之間的最短路徑
用galapagos遺傳演算法模塊計算
通過模擬退火演算法和遺傳演算法結合，無限接近最優解
❾ 過n個點的最短路徑怎麼求
用遺傳演算法，模擬退火演算法，這有可能得出次優解。 或者用每次從一個點遍歷所有點，找到與它距離最短的點，連接，然後以下一個點為起點，找一個沒有連接過的點並且是離它距離最短的點，連接，依次下去，知道找到最後的點。 這是有數學證明的 絕對是最短的 少年
❿ 節約里程法求解最短路問題
你只要記住2點之間直線最短。
節約里程法是用來解決運輸車輛數目不確定的問題的最有名的啟發式演算法。
1、節約里程法優化過程分為並行方式和串列方式兩種。核心思想是依次將運輸問題中的兩個迴路合並為一個迴路，每次使合並後的總運輸距離減小的幅度最大，直到達到一輛車的裝載限制時，再進行下一輛車的優化。
2、節約里程法最短路徑是兩點之間直線最短。最短路徑是典型的最短路徑路由演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。
3、在路徑優化問題還包括節約里程法，遺傳演算法，神經網路這幾種演算法。其中遺傳演算法相對簡便，由於遺傳演算法不能直接處理問題空間的參數,因此必須通過編碼將要求解的問題表示成遺傳空間的染色體或者個體。這一轉換操作就叫做編碼。