問題描述
如圖所示，在X軸上有5個點，分別為x1, x2, x3, x4, x5。這5個點的實際間距已知為L，但實際中由於測量誤差的存在，每個點x1, x2, x3, x4, x5會有一系列如圖中黑色圈內所示的測量點。那麼如何在實際測量點中取值可以使得相鄰位置的間距最接近L，問題可以描述為如下數學公式：
F=min∑|xi+1−xi−L|,1≤i≤4
解決思路
透過查詢資料發現，我要解決的問題和TSP問題（旅行商問題）很像。TSP問題中是預先給定數量已知位置固定的點，然後求得是旅行商人從任意一個點出發遍歷所有的點（中間每個點只能經過一次）最後回到這個點時路徑最短，具體可以參考維基百科旅行商問題。
我要解決問題的特點是點之間的間距固定，但每個點的位置上有n個測量點，我的最終目的是選擇最優的測量點使得路徑距離和4L之間的偏差最小，換言之也是使得路徑的最短（只不過是與4L做差值之後最短），這就與TSP問題不謀而合了。雖然每個位置上有個n個測量點，但每次只從每個位置上取出一個測量點，這樣就形成一條線路，然後計算路徑間距，最後透過比較即可選擇出最優的路徑，這就和TSP問題求解的思路是一樣的了。
但是如果遍歷每個位置上的點來求所有的路線，這樣當測量點數n比較大時計算量就相對很大了，所以就想到了用啟發式搜尋演算法的方式來搜尋最優解，最後使用遺傳演算法來解決這個問題。
遺傳演算法
遺傳演算法，顧名思義，可以聯想到自然界種群繁衍、基因遺傳的過程，實際上它也是借鑑進化生物學中的一些現象發展起來的（交叉，變異，選擇以及遺傳等等）維基百科遺傳演算法，是一種透過模擬生物進化過程搜尋最優解的啟發式搜尋演算法。
遺傳演算法的本質就是模仿自然界優勝劣汰、適者生存的過程。它往往從實際問題的解集出發透過一定的編碼方式形成問題域中“基因”、“染色體”和“個體”的概念，進而確定初始種群（由一定數量的個體組成），然後根據問題域中的適應度函式（Fitness Function），透過一代代的選擇（Selection）、交叉（Crossover）和變異（Mutation）等方式模擬這個種群的進化過程，最後逐漸進化出較好的個體（也就是解集中近似的最優解）。將遺傳演算法應用到實際問題的流程大致如下：
1. 對實際問題的解集進行編碼，使其可以對應生物遺傳過程中“基因”、“染色體”和“個體”的概念。比如本題中，解集就是每個位置上的隨機選一個測量點連起來的路徑，這樣我可以對測量點進行編號，使得每個測量點就代表了一個“基因”，然後一條路勁就代表了一條“染色體”，進而形成一個個體（每個個體只有一條“染色體”）。具體如下圖所示：
2. 確定問題域中的適應度函式（Fitness Function）。這個一般實際問題都會已經給出，比如本題中的適應度函式就是前面所述的數學公式：
3. 確定初始種群（population）。這個可以用random的方式隨機生成，如果為了比較快的收斂到較優解，也可以一開始就生成一些表現優良的“個體”。
4. 然後根據適應度函式進行選擇（Selection）、交叉（Crossover）和變異（Mutation），透過一定代數的遺傳即可選出近似的最優解。
以上就是我查閱資料後對遺傳演算法的一個基本的理解，下面我將具體介紹每個步驟中使用的方法（包括編碼的方式，個體的選擇，交叉的方式等）並展示相應的程式碼。（如果還想對遺傳演算法有更深入的瞭解，可以看這裡知乎如何通俗易懂的理解遺傳演算法）
解題過程
1. 編碼方式
對問題域的解集進行編碼，獲得相應的“基因”、“染色體”等，常用的編碼方式有兩種：
1) 實數編碼：使用實數進行編碼（比如0，1，2等等）。
2) 二進位制編碼：這個編碼方式就是使用二進位制0、1來表示問題域中解集。
對於本題中，每個位置上有n個測量點，顯然用二進位制編碼方式不太合適，而如果用實數編碼的方式則可以很好的表示每個位置上的測量點。因此，我使用實數（0 ~ n-1）對每個位置上的測量點進行編號，這樣我只要新建一個二維陣列即可表示每個位置上的所有測量點。同時，使用random的方式隨機生成測量點，即可將測量點的座標值儲存在陣列中對應的位置。其程式碼如下：
//pointNum是位置數（本題中是5），realPointNum是每個位置上實際的測量點數
class GARandom {
private int pointNum,realPointNum;
public GARandom(int pointNum,int realPointNum) {
this.pointNum = pointNum;
this.realPointNum = realPointNum;
}
public double[][] randomInitPopulation(){
double[][] x = new double[pointNum][realPointNum];
for (int i = 0; i < x.length; i++) {
for (int j = 0; j < x[0].length; j++) {
if(i == j){
x[i][j] = i * 10;//將一組收斂值放入其中，用以後面測試演算法的效能
}else{
x[i][j] = i * 10 + (i + 1)*Math.random();
return x;
2. 確定適應度函式
本題的適應度函式就是要使得相鄰位置的間距最接近L，即前面所描述的數學公式：
題目中有5個位置，也就是要選出使每兩個相鄰的位置最接近固定間距L的測量點。所以可以像TSP問題一樣事先計算出相鄰位置測量點之間的距離並將其儲存在陣列中，然後在種群進化的過程中，根據種群的“染色體”（也就是路徑）計算出總的偏差，以此來判斷其適應度的好壞（這裡是距離越小適應度越好）。計算相鄰位置測量點距離的程式碼如下：
//求得每兩個位置，所有點之間的距離
distance = new double[pointNum - 1][realPointNum][realPointNum];
for (int i = 0; i < pointNum - 1; i++) {
for (int j = 0; j < realPointNum; j++) {
for (int k = 0; k < realPointNum; k++) {
distance[i][j][k] = Math.abs(x[i + 1][k] - x[i][j] - L);
評價個體適應度的程式碼如下：
//根據先驗條件求得個體適應度，並根據適應度求得單個個體的機率以及個體的累積機率
//以便選擇階段使用
private void evaluate(int[][] chromosome) {
int k = 0;
double len = 0;
double sumFitness = 0;
double[] tempFitness = new double[scale];
//根據距離陣列求得每條路徑的適應度，也就是和固定距離L的偏差的和
while (k < chromosome.length) {
for (int i = 0; i < chromosome[k].length - 1; i++) {
len += distance[i][chromosome[k][i]][chromosome[k][i + 1]];
fitness[k] = len;
len = 0;
k++;
//求總的適應度
for (int i = 0; i < scale; i++) {
tempFitness[i] = 10.0 / (fitness[i] + 1);//計算適應度，這裡距離越小適應度越大，因此採用倒數的方式表示
sumFitness += tempFitness[i];
//根據適應度，轉化成相應的單個個體機率和個體的累積機率，用於後面的輪盤賭選擇策略
double tempP = 0;
ps[i] = tempFitness[i] / sumFitness;//單個個體機率
tempP += ps[i];
pc[i] = tempP;//個體累積機率
3. 確定初始種群
這裡我採用了隨機生成的方式，但是為了使初始種群中能覆蓋所有經過實數編號的測量點（0 ~ n-1），所以我讓前n個體的“染色體”如下所示：
這種方式使得初始種群的前n個個體的“染色體”排列是全0，全1直到全n-1，這樣儘可能將所有的測量點都覆蓋進去，避免隨機生成的時候漏掉一些測量點。其程式碼如下：
//生成父代種群的“染色體”，也就是隨機選取每個位置上的點組成一個網路
//scale是種群規模，pointNum是位置數（x1-x5）
oldPopulation = new int[scale][pointNum];
for (int j = 0; j < pointNum; j++) {
if (i < realPointNum){
oldPopulation[i][j] = i;
oldPopulation[i][j] = rand.nextInt(realPointNum);
4. 選擇（Selection）
確定初始種群後，就根據適應度函式計算出初代最優的個體，並將其直接遺傳給子代。這裡這麼做的原因是，儲存表現最優良的個體，讓其餘個體進行交叉或變異（當然還有其他的方式，這個由你自己決定），這種方式也叫做精英選擇。然後透過輪盤賭選擇方式，隨機選擇個體放到子代中去。這個輪盤賭選擇方式是根據每個個體適應度佔總適應度的機率進行選擇的，想詳細瞭解的可以看這篇博文輪盤賭策略。選擇階段的程式碼如下：
//精英選擇（選擇上一代中fitness最好的個體，然後直接儲存到下一代中）
private void selectMaxFitness() {
int maxId = 0;
double tempFitness = fitness[0];
//
for (int i = 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);
//輪盤賭選擇策略
private void select() {
int j, selectId;
double r;
selectMaxFitness();//精英選擇，保留上一代fitness最好的個體
r = rand.nextDouble();
for (j = 0; j < scale; j++) {
if (r <= pc[j]) {
break;
if (j < scale) {
selectId = j;
copyPopulation(i, selectId);
5. 交叉（Crossover）
選擇完之後，就要對這些個體進行“染色體”交叉，用以產生子代。交叉的方式有很多，我這裡選擇了最簡單的單點交叉，即透過random.nextDouble()隨機生成一個數，當它小於交叉機率時，即表明可以進行“染色體”的交叉，然後隨機生成一個索引值，然後將相鄰的“染色體”位於索引值後的部分進行交叉。其程式碼如下：
//單點交叉
private void crossover() {
for (int k = 1; k < scale/2; k += 2) {
double pCrossoverTemp = rand.nextDouble();
//小於交叉機率時進行“染色體”交叉,將交叉索引(包括交叉索引處的元素)後的元素進行互換
if (pCrossoverTemp <= pCrossover) {
int tempCrossover;
int indexCrossover = 1 + rand.nextInt(pointNum - 1);//排除索引值為0的情況，整體交換沒有意義
for (int i = indexCrossover; i < pointNum; i++) {
tempCrossover = newPopulation[k][i];
newPopulation[k][i] = newPopulation[k + 1][i];
newPopulation[k + 1][i] = tempCrossover;
當然這是最最簡單的交叉運算元，如果想使用表現更好的運算元，可以看這篇博文遺傳演算法中幾種交叉運算元。
6. 變異（Mutation）
變異這個部分，我沒有查閱很多資料，直接用了最簡單的單點變異。其程式碼如下：
private void mutation() {
double pMutationTemp = rand.nextDouble();
if (pMutationTemp < pMutation) {
//隨機選擇變異位置
int mutationIndex = rand.nextInt(pointNum);
//將變異位置的值儲存下來
int temp = newPopulation[i][mutationIndex];
//獲得變異值
int mutationTemp = rand.nextInt(realPointNum);
//確保變異值和之前的值不一樣
while (mutationTemp == temp) {
mutationTemp = rand.nextInt(realPointNum);
newPopulation[i][mutationIndex] = mutationTemp;
7. 重複操作
從確定初代種群開始到經過第一次的選擇、交叉和變異這就產生了第一個子代。然後重複4、5、6這三個步驟，整個遺傳演算法就有如自然界進化一般，在適應度函式的制約下，自動朝著最優解的方向“進化”而去，當然遺傳演算法一般得到只是最優解的近似解。
程式碼測試
測試輸入
初始種群的大小設定為30，即初始種群包含30個個體;每個位置實際測量點的數量設定為10個;“進化”的代數設定為2000，即演算法要歷經2000代的“遺傳進化”;相鄰位置的固定間距設定為10;交叉機率定為0.8;變異機率定為0.1。
測試結果
由上圖可以看出經過2000次的選擇、交叉和變異，在固定間距是10的情況下，演算法在第355代找到了最佳的路徑01234，也就是我事先輸入到陣列的0，10，20，30，40這組資料。
問題描述
如圖所示，在X軸上有5個點，分別為x1, x2, x3, x4, x5。這5個點的實際間距已知為L，但實際中由於測量誤差的存在，每個點x1, x2, x3, x4, x5會有一系列如圖中黑色圈內所示的測量點。那麼如何在實際測量點中取值可以使得相鄰位置的間距最接近L，問題可以描述為如下數學公式：
F=min∑|xi+1−xi−L|,1≤i≤4
F=min∑|xi+1−xi−L|,1≤i≤4
解決思路
透過查詢資料發現，我要解決的問題和TSP問題（旅行商問題）很像。TSP問題中是預先給定數量已知位置固定的點，然後求得是旅行商人從任意一個點出發遍歷所有的點（中間每個點只能經過一次）最後回到這個點時路徑最短，具體可以參考維基百科旅行商問題。
我要解決問題的特點是點之間的間距固定，但每個點的位置上有n個測量點，我的最終目的是選擇最優的測量點使得路徑距離和4L之間的偏差最小，換言之也是使得路徑的最短（只不過是與4L做差值之後最短），這就與TSP問題不謀而合了。雖然每個位置上有個n個測量點，但每次只從每個位置上取出一個測量點，這樣就形成一條線路，然後計算路徑間距，最後透過比較即可選擇出最優的路徑，這就和TSP問題求解的思路是一樣的了。
但是如果遍歷每個位置上的點來求所有的路線，這樣當測量點數n比較大時計算量就相對很大了，所以就想到了用啟發式搜尋演算法的方式來搜尋最優解，最後使用遺傳演算法來解決這個問題。
遺傳演算法
遺傳演算法，顧名思義，可以聯想到自然界種群繁衍、基因遺傳的過程，實際上它也是借鑑進化生物學中的一些現象發展起來的（交叉，變異，選擇以及遺傳等等）維基百科遺傳演算法，是一種透過模擬生物進化過程搜尋最優解的啟發式搜尋演算法。
遺傳演算法的本質就是模仿自然界優勝劣汰、適者生存的過程。它往往從實際問題的解集出發透過一定的編碼方式形成問題域中“基因”、“染色體”和“個體”的概念，進而確定初始種群（由一定數量的個體組成），然後根據問題域中的適應度函式（Fitness Function），透過一代代的選擇（Selection）、交叉（Crossover）和變異（Mutation）等方式模擬這個種群的進化過程，最後逐漸進化出較好的個體（也就是解集中近似的最優解）。將遺傳演算法應用到實際問題的流程大致如下：
1. 對實際問題的解集進行編碼，使其可以對應生物遺傳過程中“基因”、“染色體”和“個體”的概念。比如本題中，解集就是每個位置上的隨機選一個測量點連起來的路徑，這樣我可以對測量點進行編號，使得每個測量點就代表了一個“基因”，然後一條路勁就代表了一條“染色體”，進而形成一個個體（每個個體只有一條“染色體”）。具體如下圖所示：
2. 確定問題域中的適應度函式（Fitness Function）。這個一般實際問題都會已經給出，比如本題中的適應度函式就是前面所述的數學公式：
F=min∑|xi+1−xi−L|,1≤i≤4
F=min∑|xi+1−xi−L|,1≤i≤4
3. 確定初始種群（population）。這個可以用random的方式隨機生成，如果為了比較快的收斂到較優解，也可以一開始就生成一些表現優良的“個體”。
4. 然後根據適應度函式進行選擇（Selection）、交叉（Crossover）和變異（Mutation），透過一定代數的遺傳即可選出近似的最優解。
以上就是我查閱資料後對遺傳演算法的一個基本的理解，下面我將具體介紹每個步驟中使用的方法（包括編碼的方式，個體的選擇，交叉的方式等）並展示相應的程式碼。（如果還想對遺傳演算法有更深入的瞭解，可以看這裡知乎如何通俗易懂的理解遺傳演算法）
解題過程
1. 編碼方式
對問題域的解集進行編碼，獲得相應的“基因”、“染色體”等，常用的編碼方式有兩種：
1) 實數編碼：使用實數進行編碼（比如0，1，2等等）。
2) 二進位制編碼：這個編碼方式就是使用二進位制0、1來表示問題域中解集。
對於本題中，每個位置上有n個測量點，顯然用二進位制編碼方式不太合適，而如果用實數編碼的方式則可以很好的表示每個位置上的測量點。因此，我使用實數（0 ~ n-1）對每個位置上的測量點進行編號，這樣我只要新建一個二維陣列即可表示每個位置上的所有測量點。同時，使用random的方式隨機生成測量點，即可將測量點的座標值儲存在陣列中對應的位置。其程式碼如下：
//pointNum是位置數（本題中是5），realPointNum是每個位置上實際的測量點數
class GARandom {
private int pointNum,realPointNum;
public GARandom(int pointNum,int realPointNum) {
this.pointNum = pointNum;
this.realPointNum = realPointNum;
}
public double[][] randomInitPopulation(){
double[][] x = new double[pointNum][realPointNum];
for (int i = 0; i < x.length; i++) {
for (int j = 0; j < x[0].length; j++) {
if(i == j){
x[i][j] = i * 10;//將一組收斂值放入其中，用以後面測試演算法的效能
}else{
x[i][j] = i * 10 + (i + 1)*Math.random();
}
}
}
return x;
}
}
2. 確定適應度函式
本題的適應度函式就是要使得相鄰位置的間距最接近L，即前面所描述的數學公式：
F=min∑|xi+1−xi−L|,1≤i≤4
F=min∑|xi+1−xi−L|,1≤i≤4
題目中有5個位置，也就是要選出使每兩個相鄰的位置最接近固定間距L的測量點。所以可以像TSP問題一樣事先計算出相鄰位置測量點之間的距離並將其儲存在陣列中，然後在種群進化的過程中，根據種群的“染色體”（也就是路徑）計算出總的偏差，以此來判斷其適應度的好壞（這裡是距離越小適應度越好）。計算相鄰位置測量點距離的程式碼如下：
//求得每兩個位置，所有點之間的距離
distance = new double[pointNum - 1][realPointNum][realPointNum];
for (int i = 0; i < pointNum - 1; i++) {
for (int j = 0; j < realPointNum; j++) {
for (int k = 0; k < realPointNum; k++) {
distance[i][j][k] = Math.abs(x[i + 1][k] - x[i][j] - L);
}
}
}
評價個體適應度的程式碼如下：
//根據先驗條件求得個體適應度，並根據適應度求得單個個體的機率以及個體的累積機率
//以便選擇階段使用
private void evaluate(int[][] chromosome) {
int k = 0;
double len = 0;
double sumFitness = 0;
double[] tempFitness = new double[scale];
//根據距離陣列求得每條路徑的適應度，也就是和固定距離L的偏差的和
while (k < chromosome.length) {
for (int i = 0; i < chromosome[k].length - 1; i++) {
len += distance[i][chromosome[k][i]][chromosome[k][i + 1]];
}
fitness[k] = len;
len = 0;
k++;
}
//求總的適應度
for (int i = 0; i < scale; i++) {
tempFitness[i] = 10.0 / (fitness[i] + 1);//計算適應度，這裡距離越小適應度越大，因此採用倒數的方式表示
sumFitness += tempFitness[i];
}
//根據適應度，轉化成相應的單個個體機率和個體的累積機率，用於後面的輪盤賭選擇策略
double tempP = 0;
for (int i = 0; i < scale; i++) {
ps[i] = tempFitness[i] / sumFitness;//單個個體機率
tempP += ps[i];
pc[i] = tempP;//個體累積機率
}
}
3. 確定初始種群
這裡我採用了隨機生成的方式，但是為了使初始種群中能覆蓋所有經過實數編號的測量點（0 ~ n-1），所以我讓前n個體的“染色體”如下所示：
這種方式使得初始種群的前n個個體的“染色體”排列是全0，全1直到全n-1，這樣儘可能將所有的測量點都覆蓋進去，避免隨機生成的時候漏掉一些測量點。其程式碼如下：
//生成父代種群的“染色體”，也就是隨機選取每個位置上的點組成一個網路
//scale是種群規模，pointNum是位置數（x1-x5）
oldPopulation = new int[scale][pointNum];
for (int i = 0; i < scale; i++) {
for (int j = 0; j < pointNum; j++) {
if (i < realPointNum){
oldPopulation[i][j] = i;
}else{
oldPopulation[i][j] = rand.nextInt(realPointNum);
}
}
}
4. 選擇（Selection）
確定初始種群後，就根據適應度函式計算出初代最優的個體，並將其直接遺傳給子代。這裡這麼做的原因是，儲存表現最優良的個體，讓其餘個體進行交叉或變異（當然還有其他的方式，這個由你自己決定），這種方式也叫做精英選擇。然後透過輪盤賭選擇方式，隨機選擇個體放到子代中去。這個輪盤賭選擇方式是根據每個個體適應度佔總適應度的機率進行選擇的，想詳細瞭解的可以看這篇博文輪盤賭策略。選擇階段的程式碼如下：
//精英選擇（選擇上一代中fitness最好的個體，然後直接儲存到下一代中）
private void selectMaxFitness() {
int maxId = 0;
double tempFitness = fitness[0];
//
for (int i = 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);
}
//輪盤賭選擇策略
private void select() {
int j, selectId;
double r;
selectMaxFitness();//精英選擇，保留上一代fitness最好的個體
for (int i = 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）
選擇完之後，就要對這些個體進行“染色體”交叉，用以產生子代。交叉的方式有很多，我這裡選擇了最簡單的單點交叉，即透過random.nextDouble()隨機生成一個數，當它小於交叉機率時，即表明可以進行“染色體”的交叉，然後隨機生成一個索引值，然後將相鄰的“染色體”位於索引值後的部分進行交叉。其程式碼如下：
//單點交叉
private void crossover() {
for (int k = 1; k < scale/2; k += 2) {
double pCrossoverTemp = rand.nextDouble();
//小於交叉機率時進行“染色體”交叉,將交叉索引(包括交叉索引處的元素)後的元素進行互換
if (pCrossoverTemp <= pCrossover) {
int tempCrossover;
int indexCrossover = 1 + rand.nextInt(pointNum - 1);//排除索引值為0的情況，整體交換沒有意義
for (int i = indexCrossover; i < pointNum; i++) {
tempCrossover = newPopulation[k][i];
newPopulation[k][i] = newPopulation[k + 1][i];
newPopulation[k + 1][i] = tempCrossover;
}
}
}
}
當然這是最最簡單的交叉運算元，如果想使用表現更好的運算元，可以看這篇博文遺傳演算法中幾種交叉運算元。
6. 變異（Mutation）
變異這個部分，我沒有查閱很多資料，直接用了最簡單的單點變異。其程式碼如下：
private void mutation() {
for (int i = 1; i < scale; i++) {
double pMutationTemp = rand.nextDouble();
if (pMutationTemp < pMutation) {
//隨機選擇變異位置
int mutationIndex = rand.nextInt(pointNum);
//將變異位置的值儲存下來
int temp = newPopulation[i][mutationIndex];
//獲得變異值
int mutationTemp = rand.nextInt(realPointNum);
//確保變異值和之前的值不一樣
while (mutationTemp == temp) {
mutationTemp = rand.nextInt(realPointNum);
}
newPopulation[i][mutationIndex] = mutationTemp;
}
}
}
7. 重複操作
從確定初代種群開始到經過第一次的選擇、交叉和變異這就產生了第一個子代。然後重複4、5、6這三個步驟，整個遺傳演算法就有如自然界進化一般，在適應度函式的制約下，自動朝著最優解的方向“進化”而去，當然遺傳演算法一般得到只是最優解的近似解。
程式碼測試
測試輸入
初始種群的大小設定為30，即初始種群包含30個個體;每個位置實際測量點的數量設定為10個;“進化”的代數設定為2000，即演算法要歷經2000代的“遺傳進化”;相鄰位置的固定間距設定為10;交叉機率定為0.8;變異機率定為0.1。
測試結果
由上圖可以看出經過2000次的選擇、交叉和變異，在固定間距是10的情況下，演算法在第355代找到了最佳的路徑01234，也就是我事先輸入到陣列的0，10，20，30，40這組資料。