java遺傳算法排課如何性能優化？
問題描述
如圖所示，在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這組數據。
