⑴ 求貨郎擔問題的matlab演算法
貨郎擔問題有很多解法,模擬退火,遺傳演算法,動態規劃等。
基於matlab TSP問題遺傳演算法的實現
%TSP問題(又名:旅行商問題,貨郎擔問題)遺傳演算法通用matlab程序
%D是距離矩陣,n為種群個數,建議取為城市個數的1~2倍,
%C為停止代數,遺傳到第 C代時程序停止,C的具體取值視問題的規模和耗費的時間而定
%m為適應值歸一化淘汰加速指數 ,最好取為1,2,3,4 ,不宜太大
%alpha為淘汰保護指數,可取為0~1之間任意小數,取1時關閉保護功能,最好取為0.8~1.0
%R為最短路徑,Rlength為路徑長度
function [R,Rlength]=geneticTSP(D,n,C,m,alpha)
[N,NN]=size(D);
farm=zeros(n,N);%用於存儲種群
for i=1:n
farm(i,:)=randperm(N);%隨機生成初始種群
end
R=farm(1,:);%存儲最優種群
len=zeros(n,1);%存儲路徑長度
fitness=zeros(n,1);%存儲歸一化適應值
counter=0;
while counter<c
for i=1:n
len(i,1)=myLength(D,farm(i,:));%計算路徑長度
end
maxlen=max(len);
minlen=min(len);
fitness=fit(len,m,maxlen,minlen);%計算歸一化適應值
rr=find(len==minlen);
R=farm(rr(1,1),:);%更新最短路徑
FARM=farm;%優勝劣汰,nn記錄了復制的個數
nn=0;
for i=1:n
if fitness(i,1)>=alpha*rand
nn=nn+1;
FARM(nn,:)=farm(i,:);
end
end
FARM=FARM(1:nn,:);
[aa,bb]=size(FARM);%交叉和變異
while aa<n
if nn<=2
nnper=randperm(2);
else
nnper=randperm(nn);
end
A=FARM(nnper(1),:);
B=FARM(nnper(2),:);
[A,B]=intercross(A,B);
FARM=[FARM;A;B];
[aa,bb]=size(FARM);
end
if aa>n
FARM=FARM(1:n,:);%保持種群規模為n
end
farm=FARM;
clear FARM
counter=counter+1
end
Rlength=myLength(D,R);
function [a,b]=intercross(a,b)
L=length(a);
if L<=10%確定交叉寬度
W=1;
elseif ((L/10)-floor(L/10))>=rand&&L>10
W=ceil(L/10);
else
W
http://blog.renren.com/share/231644124/531791903
⑵ 做數學建模用到的遺傳演算法,難不難,要怎麼學要不要用專門的工具箱
要看你用遺傳演算法解決什麼問題,一般情況下,有兩個方向使用遺傳演算法,一是自己編寫遺傳演算法代碼解決問題,二是用Matlab遺傳演算法工具箱。前者可以學習王小平的《遺傳演算法——理論、應用與軟體實現》這本書,後者可以學習 雷英傑的《MATLAB遺傳演算法工具箱及應用》這本書,網上都可以找到電子版。
你要是用遺傳演算法解決旅行商問題這樣的組合優化問題,建議你自己編碼實現吧,網上可以找到很多代碼參考。
⑶ 遺傳演算法解決旅行商問題(TSP)一:初始化和適應值
旅行商問題(Travelling salesman problem, TSP)是這樣一個問題:給定一系列城市和每對城市之間的距離,求解訪問每一座城市一次並回到起始城市的最短迴路。
設有n個城市,城市i和城市j之間的距離是 。設
那麼TSP問題使下面的目標最小:
首先,設置一下參數:
這里假設有10個城市,其坐標定義於pos變數,第一行是各個城市的x坐標,第二行是各個城市的y坐標,比如第一個城市的坐標為(1,1),第三個城市的坐標為(2,2)。之後計算處各個城市之間的距離。
種群中每個個體,都表示著一個訪問城市的路徑,這意味著每個個體都要覆蓋所有城市,但是只能經過一個城市一次。
根據種群中每個個體中城市的順序,可以求出這個個體所代表的距離,距離越大,適應度越小,因此用距離的倒數作為個體的適應度值。
⑷ tSp Concorder演算法原理
tsp問題遺傳演算法將多目標按照線性加權的方式轉化為單目標,然後應用傳統遺傳演算法求解
其中w_i表示第i個目標的權重,f_k表示歸一化之後的第i個目標值。我們很容易知道,這類方法的關鍵是怎麼設計權重。比如,Random Weight Genetic Algorithm (RWGA) 採用隨機權重的方式,每次計算適應度都對所有個體隨機地產生不同目標的權重,然後進行選擇操作。Vector-Evaluated Genetic Algorithm (VEGA) 也是基於線性加權的多目標遺傳演算法。如果有K個目標,VEGA 會隨機地將種群分為K個同等大小子種群,在不同的子種群按照不同的目標函數設定目標值,然後再進行選擇操作。VEGA 實質上是基於線性加權的多目標遺傳演算法。VEGA 是第一個多目標遺傳演算法,開啟了十幾年的研究潮流。
1.TSP問題是指假設有一個旅行商人要拜訪n個城市,他必須選擇所要走的路徑,路徑的限制是每個城市只能拜訪一次,而且最後要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。本文使用遺傳演算法解決att30問題,即30個城市的旅行商問題。旅行商問題是一個經典的組合優化問題。一個經典的旅行商問題可以描述為:一個商品推銷員要去若干個城市推銷商品,該推銷員從一個城市出發,需要經過所有城市後,回到出發地。應如何選擇行進路線,以使總的行程最短。從圖論的角度來看,該問題實質是在一個帶權完全無向圖中,找一個權值最小的Hamilton迴路。由於該問題的可行解是所有頂點的全排列,隨著頂點數的增加,會產生組合爆炸,它是一個NP完全問題。TSP問題可以分為對稱和不對稱。在對稱TSP問題中,兩座城市之間來回的距離是相等的,形成一個無向圖,而不對稱TSP則形成有向圖。對稱性TSP問題可以將解的數量減少了一半。所以本次實驗的TSP問題使用att48數據,可在tsplib中下載數據包。演化演算法是一類模擬自然界遺傳進化規律的仿生學演算法,它不是一個具體的演算法,而是一個演算法簇。遺傳演算法是演化演算法的一個分支,由於遺傳演算法的整體搜索策略和優化計算是不依賴梯度信息,所以它的應用比較廣泛。我們本次實驗同樣用到了遺傳演算法(用MATLAB編寫)來解決TSP問題。