問(wèn)題描述
如圖所示，在X軸上有5個(gè)點(diǎn)，分別為x1,x2,x3,x4,x5。這5個(gè)點(diǎn)的實(shí)際間距已知為L(zhǎng)，但實(shí)際中由于測(cè)量誤差的存在，每個(gè)點(diǎn)x1,x2,x3,x4,x5會(huì)有一系列如圖中黑色圈內(nèi)所示的測(cè)量點(diǎn)。那么如何在實(shí)際測(cè)量點(diǎn)中取值可以使得相鄰位置的間距最接近L，問(wèn)題可以描述為如下數(shù)學(xué)公式：
F=min∑|xi+1?xi?L|,1≤i≤4
F=min∑|xi+1?xi?L|,1≤i≤4
解決思路
通過(guò)查詢資料發(fā)現(xiàn)，我要解決的問(wèn)題和TSP問(wèn)題（旅行商問(wèn)題）很像。TSP問(wèn)題中是預(yù)先給定數(shù)量已知位置固定的點(diǎn)，然后求得是旅行商人從任意一個(gè)點(diǎn)出發(fā)遍歷所有的點(diǎn)（中間每個(gè)點(diǎn)只能經(jīng)過(guò)一次）最后回到這個(gè)點(diǎn)時(shí)路徑最短，具體可以參考維基百科旅行商問(wèn)題。
我要解決問(wèn)題的特點(diǎn)是點(diǎn)之間的間距固定，但每個(gè)點(diǎn)的位置上有n個(gè)測(cè)量點(diǎn)，我的最終目的是選擇最優(yōu)的測(cè)量點(diǎn)使得路徑距離和4L之間的偏差最小，換言之也是使得路徑的最短（只不過(guò)是與4L做差值之后最短），這就與TSP問(wèn)題不謀而合了。雖然每個(gè)位置上有個(gè)n個(gè)測(cè)量點(diǎn)，但每次只從每個(gè)位置上取出一個(gè)測(cè)量點(diǎn)，這樣就形成一條線路，然后計(jì)算路徑間距，最后通過(guò)比較即可選擇出最優(yōu)的路徑，這就和TSP問(wèn)題求解的思路是一樣的了。
但是如果遍歷每個(gè)位置上的點(diǎn)來(lái)求所有的路線，這樣當(dāng)測(cè)量點(diǎn)數(shù)n比較大時(shí)計(jì)算量就相對(duì)很大了，所以就想到了用啟發(fā)式搜索算法的方式來(lái)搜索最優(yōu)解，最后使用遺傳算法來(lái)解決這個(gè)問(wèn)題。
遺傳算法
遺傳算法，顧名思義，可以聯(lián)想到自然界種群繁衍、基因遺傳的過(guò)程，實(shí)際上它也是借鑒進(jìn)化生物學(xué)中的一些現(xiàn)象發(fā)展起來(lái)的（交叉，變異，選擇以及遺傳等等）維基百科遺傳算法，是一種通過(guò)模擬生物進(jìn)化過(guò)程搜索最優(yōu)解的啟發(fā)式搜索算法。
遺傳算法的本質(zhì)就是模仿自然界優(yōu)勝劣汰、適者生存的過(guò)程。它往往從實(shí)際問(wèn)題的解集出發(fā)通過(guò)一定的編碼方式形成問(wèn)題域中“基因”、“染色體”和“個(gè)體”的概念，進(jìn)而確定初始種群（由一定數(shù)量的個(gè)體組成），然后根據(jù)問(wèn)題域中的適應(yīng)度函數(shù)（FitnessFunction），通過(guò)一代代的選擇（Selection）、交叉（Crossover）和變異（Mutation）等方式模擬這個(gè)種群的進(jìn)化過(guò)程，最后逐漸進(jìn)化出較好的個(gè)體（也就是解集中近似的最優(yōu)解）。將遺傳算法應(yīng)用到實(shí)際問(wèn)題的流程大致如下：
1.對(duì)實(shí)際問(wèn)題的解集進(jìn)行編碼，使其可以對(duì)應(yīng)生物遺傳過(guò)程中“基因”、“染色體”和“個(gè)體”的概念。比如本題中，解集就是每個(gè)位置上的隨機(jī)選一個(gè)測(cè)量點(diǎn)連起來(lái)的路徑，這樣我可以對(duì)測(cè)量點(diǎn)進(jìn)行編號(hào)，使得每個(gè)測(cè)量點(diǎn)就代表了一個(gè)“基因”，然后一條路勁就代表了一條“染色體”，進(jìn)而形成一個(gè)個(gè)體（每個(gè)個(gè)體只有一條“染色體”）。具體如下圖所示：
2.確定問(wèn)題域中的適應(yīng)度函數(shù)（FitnessFunction）。這個(gè)一般實(shí)際問(wèn)題都會(huì)已經(jīng)給出，比如本題中的適應(yīng)度函數(shù)就是前面所述的數(shù)學(xué)公式：
F=min∑|xi+1?xi?L|,1≤i≤4
F=min∑|xi+1?xi?L|,1≤i≤4
3.確定初始種群（population）。這個(gè)可以用random的方式隨機(jī)生成，如果為了比較快的收斂到較優(yōu)解，也可以一開(kāi)始就生成一些表現(xiàn)優(yōu)良的“個(gè)體”。
4.然后根據(jù)適應(yīng)度函數(shù)進(jìn)行選擇（Selection）、交叉（Crossover）和變異（Mutation），通過(guò)一定代數(shù)的遺傳即可選出近似的最優(yōu)解。
以上就是我查閱資料后對(duì)遺傳算法的一個(gè)基本的理解，下面我將具體介紹每個(gè)步驟中使用的方法（包括編碼的方式，個(gè)體的選擇，交叉的方式等）并展示相應(yīng)的代碼。（如果還想對(duì)遺傳算法有更深入的了解，可以看這里知乎如何通俗易懂的理解遺傳算法）
解題過(guò)程
1.編碼方式
對(duì)問(wèn)題域的解集進(jìn)行編碼，獲得相應(yīng)的“基因”、“染色體”等，常用的編碼方式有兩種：
1)實(shí)數(shù)編碼：使用實(shí)數(shù)進(jìn)行編碼（比如0，1，2等等）。
2)二進(jìn)制編碼：這個(gè)編碼方式就是使用二進(jìn)制0、1來(lái)表示問(wèn)題域中解集。
對(duì)于本題中，每個(gè)位置上有n個(gè)測(cè)量點(diǎn)，顯然用二進(jìn)制編碼方式不太合適，而如果用實(shí)數(shù)編碼的方式則可以很好的表示每個(gè)位置上的測(cè)量點(diǎn)。因此，我使用實(shí)數(shù)（0~n-1）對(duì)每個(gè)位置上的測(cè)量點(diǎn)進(jìn)行編號(hào)，這樣我只要新建一個(gè)二維數(shù)組即可表示每個(gè)位置上的所有測(cè)量點(diǎn)。同時(shí)，使用random的方式隨機(jī)生成測(cè)量點(diǎn)，即可將測(cè)量點(diǎn)的坐標(biāo)值保存在數(shù)組中對(duì)應(yīng)的位置。其代碼如下：
//pointNum是位置數(shù)（本題中是5），realPointNum是每個(gè)位置上實(shí)際的測(cè)量點(diǎn)數(shù)
classGARandom{
privateintpointNum,realPointNum;
publicGARandom(intpointNum,intrealPointNum){
this.pointNum=pointNum;
this.realPointNum=realPointNum;
}
publicdouble[][]randomInitPopulation(){
double[][]x=newdouble[pointNum][realPointNum];
for(inti=0;i<x.length;i++){
for(intj=0;j<x[0].length;j++){
if(i==j){
x[i][j]=i*10;//將一組收斂值放入其中，用以后面測(cè)試算法的性能
}else{
x[i][j]=i*10+(i+1)*Math.random();
}
}
}
returnx;
}
}
2.確定適應(yīng)度函數(shù)
本題的適應(yīng)度函數(shù)就是要使得相鄰位置的間距最接近L，即前面所描述的數(shù)學(xué)公式：
F=min∑|xi+1?xi?L|,1≤i≤4
F=min∑|xi+1?xi?L|,1≤i≤4
題目中有5個(gè)位置，也就是要選出使每?jī)蓚€(gè)相鄰的位置最接近固定間距L的測(cè)量點(diǎn)。所以可以像TSP問(wèn)題一樣事先計(jì)算出相鄰位置測(cè)量點(diǎn)之間的距離并將其保存在數(shù)組中，然后在種群進(jìn)化的過(guò)程中，根據(jù)種群的“染色體”（也就是路徑）計(jì)算出總的偏差，以此來(lái)判斷其適應(yīng)度的好壞（這里是距離越小適應(yīng)度越好）。計(jì)算相鄰位置測(cè)量點(diǎn)距離的代碼如下：
//求得每?jī)蓚€(gè)位置，所有點(diǎn)之間的距離
distance=newdouble[pointNum-1][realPointNum][realPointNum];
for(inti=0;i<pointNum-1;i++){
for(intj=0;j<realPointNum;j++){
for(intk=0;k<realPointNum;k++){
distance[i][j][k]=Math.abs(x[i+1][k]-x[i][j]-L);
}
}
}
評(píng)價(jià)個(gè)體適應(yīng)度的代碼如下：
//根據(jù)先驗(yàn)條件求得個(gè)體適應(yīng)度，并根據(jù)適應(yīng)度求得單個(gè)個(gè)體的概率以及個(gè)體的累積概率
//以便選擇階段使用
privatevoidevaluate(int[][]chromosome){
intk=0;
doublelen=0;
doublesumFitness=0;
double[]tempFitness=newdouble[scale];
//根據(jù)距離數(shù)組求得每條路徑的適應(yīng)度，也就是和固定距離L的偏差的和
while(k<chromosome.length){
for(inti=0;i<chromosome[k].length-1;i++){
len+=distance[i][chromosome[k][i]][chromosome[k][i+1]];
}
fitness[k]=len;
len=0;
k++;
}
//求總的適應(yīng)度
for(inti=0;i<scale;i++){
tempFitness[i]=10.0/(fitness[i]+1);//計(jì)算適應(yīng)度，這里距離越小適應(yīng)度越大，因此采用倒數(shù)的方式表示
sumFitness+=tempFitness[i];
}
//根據(jù)適應(yīng)度，轉(zhuǎn)化成相應(yīng)的單個(gè)個(gè)體概率和個(gè)體的累積概率，用于后面的輪盤(pán)賭選擇策略
doubletempP=0;
for(inti=0;i<scale;i++){
ps[i]=tempFitness[i]/sumFitness;//單個(gè)個(gè)體概率
tempP+=ps[i];
pc[i]=tempP;//個(gè)體累積概率
}
}
3.確定初始種群
這里我采用了隨機(jī)生成的方式，但是為了使初始種群中能覆蓋所有經(jīng)過(guò)實(shí)數(shù)編號(hào)的測(cè)量點(diǎn)（0~n-1），所以我讓前n個(gè)體的“染色體”如下所示：
這種方式使得初始種群的前n個(gè)個(gè)體的“染色體”排列是全0，全1直到全n-1，這樣盡可能將所有的測(cè)量點(diǎn)都覆蓋進(jìn)去，避免隨機(jī)生成的時(shí)候漏掉一些測(cè)量點(diǎn)。其代碼如下：
//生成父代種群的“染色體”，也就是隨機(jī)選取每個(gè)位置上的點(diǎn)組成一個(gè)網(wǎng)絡(luò)
//scale是種群規(guī)模，pointNum是位置數(shù)（x1-x5）
oldPopulation=newint[scale][pointNum];
for(inti=0;i<scale;i++){
for(intj=0;j<pointNum;j++){
if(i<realPointNum){
oldPopulation[i][j]=i;
}else{
oldPopulation[i][j]=rand.nextInt(realPointNum);
}
}
}
4.選擇（Selection）
確定初始種群后，就根據(jù)適應(yīng)度函數(shù)計(jì)算出初代最優(yōu)的個(gè)體，并將其直接遺傳給子代。這里這么做的原因是，保存表現(xiàn)最優(yōu)良的個(gè)體，讓其余個(gè)體進(jìn)行交叉或變異（當(dāng)然還有其他的方式，這個(gè)由你自己決定），這種方式也叫做精英選擇。然后通過(guò)輪盤(pán)賭選擇方式，隨機(jī)選擇個(gè)體放到子代中去。這個(gè)輪盤(pán)賭選擇方式是根據(jù)每個(gè)個(gè)體適應(yīng)度占總適應(yīng)度的概率進(jìn)行選擇的，想詳細(xì)了解的可以看這篇博文輪盤(pán)賭策略。選擇階段的代碼如下：
//精英選擇（選擇上一代中fitness最好的個(gè)體，然后直接保存到下一代中）
privatevoidselectMaxFitness(){
intmaxId=0;
doubletempFitness=fitness[0];
//
for(inti=1;i<scale;i++){
if(tempFitness>fitness[i]){
tempFitness=fitness[i];
maxId=i;
}
}
if(bestLength>tempFitness){
bestLength=tempFitness;
bestGen=t;
System.arraycopy(oldPopulation[maxId],0,bestChoice,0,pointNum);
}
copyPopulation(0,maxId);
}
//輪盤(pán)賭選擇策略
privatevoidselect(){
intj,selectId;
doubler;
selectMaxFitness();//精英選擇，保留上一代fitness最好的個(gè)體
for(inti=1;i<scale;i++){
r=rand.nextDouble();
for(j=0;j<scale;j++){
if(r<=pc[j]){
break;
}
}
if(j<scale){
selectId=j;
copyPopulation(i,selectId);
}
}
}
5.交叉（Crossover）
選擇完之后，就要對(duì)這些個(gè)體進(jìn)行“染色體”交叉，用以產(chǎn)生子代。交叉的方式有很多，我這里選擇了最簡(jiǎn)單的單點(diǎn)交叉，即通過(guò)random.nextDouble()隨機(jī)生成一個(gè)數(shù)，當(dāng)它小于交叉概率時(shí)，即表明可以進(jìn)行“染色體”的交叉，然后隨機(jī)生成一個(gè)索引值，然后將相鄰的“染色體”位于索引值后的部分進(jìn)行交叉。其代碼如下：
//單點(diǎn)交叉
privatevoidcrossover(){
for(intk=1;k<scale/2;k+=2){
doublepCrossoverTemp=rand.nextDouble();
//小于交叉概率時(shí)進(jìn)行“染色體”交叉,將交叉索引(包括交叉索引處的元素)后的元素進(jìn)行互換
if(pCrossoverTemp<=pCrossover){
inttempCrossover;
intindexCrossover=1+rand.nextInt(pointNum-1);//排除索引值為0的情況，整體交換沒(méi)有意義
for(inti=indexCrossover;i<pointNum;i++){
tempCrossover=newPopulation[k][i];
newPopulation[k][i]=newPopulation[k+1][i];
newPopulation[k+1][i]=tempCrossover;
}
}
}
}
當(dāng)然這是最最簡(jiǎn)單的交叉算子，如果想使用表現(xiàn)更好的算子，可以看這篇博文遺傳算法中幾種交叉算子。
6.變異（Mutation）
變異這個(gè)部分，我沒(méi)有查閱很多資料，直接用了最簡(jiǎn)單的單點(diǎn)變異。其代碼如下：
privatevoidmutation(){
for(inti=1;i<scale;i++){
doublepMutationTemp=rand.nextDouble();
if(pMutationTemp<pMutation){
//隨機(jī)選擇變異位置
intmutationIndex=rand.nextInt(pointNum);
//將變異位置的值保存下來(lái)
inttemp=newPopulation[i][mutationIndex];
//獲得變異值
intmutationTemp=rand.nextInt(realPointNum);
//確保變異值和之前的值不一樣
while(mutationTemp==temp){
mutationTemp=rand.nextInt(realPointNum);
}
newPopulation[i][mutationIndex]=mutationTemp;
}
}
}
7.重復(fù)操作
從確定初代種群開(kāi)始到經(jīng)過(guò)第一次的選擇、交叉和變異這就產(chǎn)生了第一個(gè)子代。然后重復(fù)4、5、6這三個(gè)步驟，整個(gè)遺傳算法就有如自然界進(jìn)化一般，在適應(yīng)度函數(shù)的制約下，自動(dòng)朝著最優(yōu)解的方向“進(jìn)化”而去，當(dāng)然遺傳算法一般得到只是最優(yōu)解的近似解。
代碼測(cè)試
測(cè)試輸入
初始種群的大小設(shè)定為30，即初始種群包含30個(gè)個(gè)體;每個(gè)位置實(shí)際測(cè)量點(diǎn)的數(shù)量設(shè)定為10個(gè);“進(jìn)化”的代數(shù)設(shè)定為2000，即算法要?dú)v經(jīng)2000代的“遺傳進(jìn)化”;相鄰位置的固定間距設(shè)定為10;交叉概率定為0.8;變異概率定為0.1。
測(cè)試結(jié)果
由上圖可以看出經(jīng)過(guò)2000次的選擇、交叉和變異，在固定間距是10的情況下，算法在第355代找到了最佳的路徑01234，也就是我事先輸入到數(shù)組的0，10，20，30，40這組數(shù)據(jù)。