目錄
一、引言
1.1 目的
1.2 意義
二、遺傳算法介紹
2.1 遺傳算法的基本思想
2.2 遺傳算法與其他算法的主要區(qū)別
2.3 基于Java的遺傳算法設(shè)計思想
三、遺傳算法的具體實現(xiàn)
3.1?系統(tǒng)功能模塊圖和說明
3.2 代碼和說明
3.2.1 初始化
3.2.2 選擇運算
3.2.3 交叉運算
3.2.4 變異運算
3.2.5 主函數(shù)
四、系統(tǒng)測試
4.1 測試環(huán)境
4.2 測試步驟?
4.3 系統(tǒng)運行結(jié)果
五、遺傳算法總結(jié)
一、引言
????????一個程序員一生中可能會邂逅各種各樣的算法，但總有那么幾種，是作為一個程序員一定會遇見且大概率需要掌握的算法。今天就來聊聊這些十分重要的“必抓！”算法吧~，就比如說遺傳算法啊
1.1 目的
主要用java語言實現(xiàn)了遺傳算法，求x12 + x22的最大值。主要對于以往的參數(shù)范圍是比較固定，因此打算做一個可以自定義設(shè)定參數(shù)范圍，可以自主設(shè)置每一代群體的數(shù)量，一樣可以設(shè)置迭代次數(shù)。
1.2 意義
可以探究遺傳算法求最大值時參數(shù)范圍及迭代次數(shù)和群體數(shù)量對于求最大值時造成影響的關(guān)系大小。
???
二、遺傳算法介紹
2.1 遺傳算法的基本思想
遺傳算法（Genetic Algorithms, GA）是模擬達(dá)爾文生物進(jìn)化論的自然選擇，遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。
一個種群則由經(jīng)過基因（gene）編碼（coding）的一定數(shù)目的個體（individual）組成。
遺傳算法是從代表問題可能潛在解集的一個種群（population）開始的。
人類細(xì)胞有23對染色體（22對常染色體和一對性染色體），即每個細(xì)胞共有46個染色單體。
染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合
染色體其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個體形狀的外部表現(xiàn)
如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的
初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代(generation）演化產(chǎn)生出越來越好的近似解。
在每一代，根據(jù)問題域中個體的適應(yīng)度大小挑選個體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。
這個過程將導(dǎo)致種群像自然進(jìn)化一樣的后代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼，可以作為問題近似最優(yōu)解。 ??????
2.2 遺傳算法與其他算法的主要區(qū)別
- 自組織、自適應(yīng)和自學(xué)習(xí)性（智能性）
- 應(yīng)用遺傳算法求解問題時，在編碼方案、適應(yīng)度函數(shù)及遺傳算子確定后，算法將利用進(jìn)化過程中獲得的信息自行組織搜索。由于基于自然的選擇策略為“適者生存，不適應(yīng)者被淘汰”，因而適應(yīng)度大的個體具有較高的生存概率。適應(yīng)度大的個體具有更適應(yīng)環(huán)境的基因結(jié)構(gòu)，再通過基因重組和基因突變等遺傳操作，就可能產(chǎn)生更適應(yīng)環(huán)境的后代。
- 遺傳算法的本質(zhì)并行性，遺傳算法按并行方式搜索一個種群數(shù)目的點，而不是單點。它的并行性表現(xiàn)在兩個方面：
一是遺傳算法是內(nèi)在并行的，即遺傳算法本身非常適合大規(guī)模并行。最簡單的并行方式是讓幾百甚至數(shù)千臺計算機(jī)各自進(jìn)行獨立種群的演化計算，運行過程中甚至不進(jìn)行任何通信，等到運算結(jié)束時才通信比較，選取最佳個體。
二是遺傳算法的內(nèi)含并行性。由于遺傳算法采用種群的方式組織搜索，因而可同時搜索解空間內(nèi)的多個區(qū)域，并相互交流信息。
使用這種搜索方式，雖然每次只執(zhí)行與種群規(guī)模n成比例的計算。但實質(zhì)上已進(jìn)行了大約O（n3）次有效搜索，這就使遺傳算法能以較少的計算獲得較大的收益。
遺傳算法不需要求導(dǎo)或其他輔助知識，而只需要影響搜索方向的目標(biāo)函數(shù)和相應(yīng)的適應(yīng)度函數(shù)。
- 遺傳算法強調(diào)概率轉(zhuǎn)換規(guī)則，而不是確定的轉(zhuǎn)換規(guī)則。
- 遺傳算法可以更加直接地應(yīng)用。
- 遺傳算法對給定問題，可以產(chǎn)生許多的潛在解，最終選擇可以由使用者確定
- 在某些特殊情況下，如多目標(biāo)優(yōu)化問題不止一個解存在，有一組最優(yōu)解。
2.3 基于Java的遺傳算法設(shè)計思想
首先應(yīng)當(dāng)分為兩個類，一個類包含遺傳算法所需的各種變量，比如說，x1，x2兩個參數(shù)、迭代次數(shù)、群體數(shù)組、選擇次數(shù)、所求出的最大解、群體適應(yīng)度及其占比、參數(shù)群體的二進(jìn)制字符串等等，這些都是在實現(xiàn)遺傳算法時所需要用到的變量，因此我們應(yīng)當(dāng)把這些變量單獨放出一個類中，當(dāng)需要用到時，直接調(diào)用即可。
第二個類就是遺傳算法的實現(xiàn)類，該類應(yīng)當(dāng)包含整個遺傳算法所需要的各種方法。比如說，參數(shù)初始化函數(shù)，主要用來進(jìn)行輸入，確定參數(shù)的取值范圍和迭代次數(shù)和群體數(shù)量這些都是需要我們?nèi)プ远x輸入的，還包括了計算適應(yīng)度函數(shù)，計算每一個個體對應(yīng)的適應(yīng)度是多少，還有選擇運算，根據(jù)每個個體的適應(yīng)度進(jìn)行選擇，這里可以采取輪盤賭的方法去進(jìn)行選擇。還應(yīng)當(dāng)包括交叉算法，對選擇后的個體進(jìn)行交配，這里也應(yīng)當(dāng)是隨機(jī)兩兩交配，更能體現(xiàn)達(dá)爾文的自然選擇理論，交叉點也應(yīng)當(dāng)隨機(jī)生成。最后變異算法必不可少，隨機(jī)選擇變異點進(jìn)行變異，當(dāng)然這里也應(yīng)該存在不變異的情況，假設(shè)不變異的情況下變異點應(yīng)當(dāng)為-1。還應(yīng)包括一下其他輔助方法，比如說十進(jìn)制轉(zhuǎn)化為二進(jìn)制函數(shù)，二進(jìn)制轉(zhuǎn)化為十進(jìn)制函數(shù)，選擇運算結(jié)束之后需要進(jìn)行重新布局的重新布局函數(shù)，打印群體及其二進(jìn)制顯示函數(shù)，判斷是否找到最優(yōu)解函數(shù)。
三、遺傳算法的具體實現(xiàn)
3.1?系統(tǒng)功能模塊圖和說明
下圖1是該算法的主要流程圖。
圖 1?算法流程圖
從算法流程圖我們應(yīng)該可以知道首先初始化參數(shù)，初始化參數(shù)完成之后，再根據(jù)輸入的參數(shù)初始化群體，然后進(jìn)行選擇運算，對群體進(jìn)行選擇，然后進(jìn)行交叉運算，隨機(jī)生成交叉點，根據(jù)交叉點將個體兩兩隨機(jī)分配進(jìn)行交叉整合。最后再進(jìn)行變異運算決定子代個體。如果沒有找到最優(yōu)解并且在迭代次數(shù)在設(shè)定的范圍之內(nèi)則重新進(jìn)行選擇，交叉，變異運算。
3.2 代碼和說明
接下來詳細(xì)解析系統(tǒng)流程圖的每一個流程。
3.2.1 初始化
初始化分為兩個初始化參數(shù)，下代碼2很直觀地顯示了初始化的參數(shù)有，每一代的群體數(shù)量，兩個參數(shù)的取值范圍，還有迭代次數(shù)。
// 初始化參數(shù)最大值,群體
public static void xScan(){
// 輸入?yún)?shù)范圍
System.out.print("請輸入每代的群體數(shù)量：");
xSize = scan.nextInt();
System.out.print("請輸入X1的最大值：");
maxX1 = scan.nextInt();
System.out.print("請輸入X2的最大值：");
maxX2 = scan.nextInt();
System.out.print("請輸入迭代次數(shù)：");
iterations = scan.nextInt();
// 初始化群體
xx = new int[xSize][2];
strXX = new String[xSize];
}代碼 2?參數(shù)初始化
代碼3是群體初始化，群體初始化，這里我選擇了十進(jìn)制初始化，然后再計算每一個參數(shù)的二進(jìn)制字符串的位數(shù)，這里主要是為了方便我控制臺輸出樣式，與算法并無太大的關(guān)系。然后將群體轉(zhuǎn)化成二進(jìn)制字符串。
// 群體初始化
public static void initXX(){
System.out.println("-----隨機(jī)初始化群體----");
for (int i=0;i<xSize;i++){
xx[i][0] = (int) (Math.random()*maxX1);
xx[i][1] = (int) (Math.random()*maxX2);
}
// 最大值的二進(jìn)制字符串位數(shù)
countStrXSize();
// 群體二進(jìn)制
strXXToBin();
// 打印群體
printXX();
}代碼 3?群體初始化
3.2.2 選擇運算
代碼4是選擇運算的主要代碼，進(jìn)行選擇運算首先進(jìn)行個體適應(yīng)度計算及其占比情況，在每次進(jìn)行選擇之前都要重置個體被選擇次數(shù)的數(shù)組，如果這里不重新創(chuàng)建的話，就會保留上一次的值，造成數(shù)據(jù)紊亂。這里我是根據(jù)輪盤賭法選擇，比如說第一個個體占比30%，第二個個體占比70%，那么生成一個隨機(jī)數(shù)，隨機(jī)數(shù)小于或等于0.3的時候則第一個個體被選擇，如果隨機(jī)數(shù)的范圍是大于0.3的話，則選擇第二個個體。以此類推則完成了基于輪盤賭法的選擇運算。
// 選擇運算
public static void selectXX(){
System.out.println("----------進(jìn)行選擇運算----------");
// 先進(jìn)行計算適應(yīng)度及其占比情況
countSuitNum();
// 每次選擇都要重置選擇次數(shù)數(shù)組
selectTimes = new int[xSize];
// 輪盤賭法
for (int i=0;i<xSize;i++){
double per = Math.random();
for (int j=0;j<xSize;j++){
if(per<=xxSuitPoss[j]){
selectTimes[j] += 1;
break;
}
}
}
for (int i=0;i<selectTimes.length;i++){
xxSelectMap.put(i,selectTimes[i]);
System.out.println("個體編號："+(i+1)+", ("+xx[i][0]+", "+xx[i][1]+")"+"\t適應(yīng)度："+xxSuitList.get(i)
+"\t占總數(shù)的百分比："+String.format("%.2f",xxSuitMap.get(i).doubleValue())+"\t選擇次數(shù): "+xxSelectMap.get(i));
}
// 根據(jù)選擇結(jié)果重新布局
refreshXX();
// 選擇完更新二進(jìn)制群體得十進(jìn)制數(shù)
refreshXXTen();
}代碼 4?選擇運算
3.2.3 交叉運算
交叉算法的主要邏輯就是從個體數(shù)組索引隨機(jī)生成一個不重復(fù)的數(shù)組，然后根據(jù)這個不重復(fù)數(shù)組首尾兩兩交配，達(dá)成一個偽隨機(jī)兩兩交配的思想。然后將交配后的個體重新賦值回群體數(shù)組，這時候群體數(shù)組已經(jīng)打亂，因此我們需要刷新十進(jìn)制的群體數(shù)組。
// 交叉算法
public static void cross(){
System.out.println("---------進(jìn)行交叉運算---------");
int ranArr[] = new int[xSize];
int arr[] = new int[xSize];
for(int i=0;i<xSize;i++){
arr[i] = i;
}
Random random = new Random();
for (int i=0;i<xSize;i++){
// 得到一個位置
int j = random.nextInt(xSize-i);
// 得到位置的數(shù)值
ranArr[i] = arr[j];
// 將最后一個未用的數(shù)字放到這里
arr[j] = arr[xSize-1-i];
}
for(int i=0;i<xSize/2;i++){
// 隨機(jī)確定交叉點
int cross_x = (int) (Math.random()*(x1BinStrSize+x2BinStrSize));
System.out.print("配對情況：配對前："+(ranArr[i]+1)+" = "+strXX[ranArr[i]]+" 和 "+(ranArr[xSize-1-i]+1)
+" = " + strXX[ranArr[xSize-1-i]]+"進(jìn)行配對，交叉點："+(cross_x+1)+"\t");
strXX[ranArr[i]] = strXX[ranArr[i]].replace("|","");
strXX[ranArr[xSize-1-i]] = strXX[ranArr[xSize-1-i]].replace("|","");
String str1 = strXX[ranArr[i]];
String str2 = strXX[ranArr[xSize-1-i]];
String str1_1,str1_2;
str1_1 = str1.substring(0,cross_x)+str2.substring(cross_x);
str1_2 = str2.substring(0,cross_x)+str1.substring(cross_x);
str1_1 = str1_1.substring(0,x1BinStrSize)+"|"+str1_1.substring(x1BinStrSize);
str1_2 = str1_2.substring(0,x1BinStrSize)+"|"+str1_2.substring(x1BinStrSize);
System.out.println("配對后："+(ranArr[i]+1)+" = "+str1_1+", "+(ranArr[xSize-1-i]+1)+" = "+str1_2);
strXX[ranArr[i]] = str1_1;
strXX[ranArr[xSize-1-i]] = str1_2;
}
// 刷新十進(jìn)制群體
refreshXXTen();
System.out.println("交叉后個體");
printXX();
}
代碼 5?交叉算法
3.2.4 變異運算
代碼6主要描述了變異運算的邏輯代碼，首先對循環(huán)對每一個個體進(jìn)行變異，至于變異，書上的是都會選擇變異，而我這里仔細(xì)研讀了達(dá)爾文的自然選擇理論之后，認(rèn)為是否變異也應(yīng)當(dāng)是隨機(jī)的，不應(yīng)該每一個子代都會發(fā)生變異。因此有0.5的概率不發(fā)生變異，變異點應(yīng)當(dāng)置-1。這里的邏輯是隨機(jī)生成一個隨機(jī)數(shù)，該隨機(jī)數(shù)的范圍是二進(jìn)制顯示個體字符串的長度的兩倍，如果隨機(jī)數(shù)小于個體二進(jìn)制字符串長度的話，則在該隨機(jī)數(shù)的點位上進(jìn)行變異，也就是取反操作。0變1，1變0。如果隨機(jī)數(shù)的數(shù)值大于個體二進(jìn)制字符串的長度則不進(jìn)行變異，變異點置-1。然后將得到的字符串重新賦值到群體二進(jìn)制字符串?dāng)?shù)組里。因為群體二進(jìn)制字符串?dāng)?shù)組發(fā)生改變，這里我們應(yīng)當(dāng)還要進(jìn)行更新十進(jìn)制數(shù)組。并且變異運算結(jié)束后，說明一代變異算法結(jié)束，代數(shù)+1。下圖6則是變異算法的邏輯代碼
// 變異算法
public static void variation(){
System.out.println("---------進(jìn)行變異運算---------");
for (int i=0;i<xSize;i++){
// 隨機(jī)選擇變異點,當(dāng)大于字符串范圍時不進(jìn)行變異
int var = (int) (Math.random()*(2*(x1BinStrSize+x2BinStrSize-1)))+1;
System.out.print("個體編號："+(i+1)+"\t"+strXX[i]);
strXX[i] = strXX[i].replace("|","");
char [] strX = strXX[i].toCharArray();
if(var < strX.length) {
if (strX[var - 1] == '0') {
strX[var - 1] = '1';
} else {
strX[var - 1] = '0';
}
}
else{
var = -1;
}
strXX[i] = new String(strX);
strXX[i] = strXX[i].substring(0,x1BinStrSize)+"|"+strXX[i].substring(x1BinStrSize);
System.out.println("\t變異點："+var+"\t變異結(jié)果："+strXX[i]);
}
times++;
// 更新群體十進(jìn)制數(shù)組
refreshXXTen();
System.out.println("\n---------------------第"+times+"代群體情況---------------------");
printXX();
}
代碼 6?變異算法
3.2.5 主函數(shù)
根據(jù)上面的運算，及系統(tǒng)流程圖，我們應(yīng)該可以了解了遺傳算法的一整個運算流程，首先初始化參數(shù)，然后初始化群體，然后進(jìn)入選擇運算，交叉運算，變異運算，最后判斷是否找到最優(yōu)解及是否大于設(shè)定的迭代范圍，如果都沒有，則重新進(jìn)入選擇運算，以此類推，主函數(shù)邏輯代碼實現(xiàn)如下d代碼7
public static void main(String[] args) {
// 初始化參數(shù)
xScan();
System.out.println("---------------------第"+times+"代群體情況---------------------");
// 初始化群體
initXX();
do {
// 選擇運算
selectXX();
// 交叉運算
cross();
// 變異運算
variation();
}
while (!checkResult() && times<iterations);
}代碼 7?主函數(shù)
四、系統(tǒng)測試
4.1 測試環(huán)境
Dell Inspiron 5509 Win10電腦，IntelliJ IDEA 2021.1 x64編譯器。
4.2 測試步驟?
首先來確定測試用例，測試用例應(yīng)當(dāng)包括，群體數(shù)量，參數(shù)取值范圍，迭代次數(shù)。測試用例表如下：
表 1?測試用例
| 名稱 |
群體數(shù)量 |
x1的最大值 |
x2的最大值 |
迭代次數(shù) |
應(yīng)當(dāng)獲得最優(yōu)解 |
| 測試用例1 |
10 |
127 |
63 |
100 |
20098 |
| 測試用例2 |
10 |
127 |
63 |
200 |
20098 |
| 測試用例3 |
20 |
127 |
63 |
100 |
20098 |
| 測試用例4 |
50 |
127 |
63 |
100 |
20098 |
| 測試用例5 |
10 |
127 |
127 |
100 |
32258 |
| 測試用例6 |
10 |
63 |
127 |
100 |
20098 |
| 測試用例7 |
10 |
127 |
127 |
100 |
32258 |
| 測試用例8 |
10 |
127 |
63 |
100 |
20098 |
測試用例1和2是用來測試迭代次數(shù)對獲得最優(yōu)解的影響
測試用例3和4是用來測試群體對獲得最優(yōu)解的影響
測試用例5和6是用來測試參數(shù)x1對獲得最優(yōu)解的影響
測試用例7和8是用來測試參數(shù)x2對獲得最優(yōu)解的影響
4.3 系統(tǒng)運行結(jié)果
測試結(jié)果應(yīng)當(dāng)包含獲得的最優(yōu)解，實際最優(yōu)解，是否提前獲得最優(yōu)解，獲得最優(yōu)解的代數(shù)
表 2?測試結(jié)果
| 測試用例結(jié)果 |
獲得的最優(yōu)解 |
實際最優(yōu)解 |
是否提前獲得最優(yōu)解 |
獲得最優(yōu)解的代數(shù) |
| 測試用例1 |
19729 |
20098 |
否 |
100 |
| 測試用例2 |
19973 |
20098 |
否 |
200 |
| 測試用例3 |
20098 |
20098 |
是 |
30 |
| 測試用例4 |
20098 |
20098 |
是 |
5 |
| 測試用例5 |
32005 |
32258 |
否 |
100 |
| 測試用例6 |
20098 |
20098 |
是 |
31 |
| 測試用例7 |
32005 |
32258 |
否 |
100 |
| 測試用例8 |
20098 |
20098 |
是 |
51 |
根據(jù)根據(jù)測試用例1和2的運行結(jié)果結(jié)果我們可以知道迭代次數(shù)多的時候，得到的最優(yōu)解會更接近實際最優(yōu)解；根據(jù)測試用例3和4的運行結(jié)果我們可以知道當(dāng)群體數(shù)量更多的時候，可以更早獲得最優(yōu)解；綜合測試用例5和6和測試用例7和8的運行結(jié)果我們可以知道當(dāng)參數(shù)范圍比較小的時候更容易獲得最優(yōu)解。
五、遺傳算法總結(jié)
遺傳算法是一種基于生物進(jìn)化原理的優(yōu)化算法，通過模擬生物進(jìn)化過程中的遺傳、變異和選擇等機(jī)制，尋找最優(yōu)解。它被廣泛應(yīng)用于各個領(lǐng)域的問題求解，如工程設(shè)計、組合優(yōu)化、機(jī)器學(xué)習(xí)等。
遺傳算法的應(yīng)用場景包括但不限于：
優(yōu)化問題：遺傳算法能夠有效地解決復(fù)雜的優(yōu)化問題，如旅行商問題、背包問題等。它能夠在搜索空間中進(jìn)行全局搜索，找到近似最優(yōu)解。
設(shè)計問題：遺傳算法可以用于設(shè)計優(yōu)化，如電路設(shè)計、結(jié)構(gòu)設(shè)計等。通過對設(shè)計參數(shù)進(jìn)行編碼和演化，可以得到滿足要求的設(shè)計方案。
機(jī)器學(xué)習(xí)：遺傳算法可以作為一種優(yōu)化方法用于機(jī)器學(xué)習(xí)算法的參數(shù)優(yōu)化，如神經(jīng)網(wǎng)絡(luò)的權(quán)重優(yōu)化、支持向量機(jī)的參數(shù)選擇等。
調(diào)度問題：遺傳算法可以用于調(diào)度問題的求解，如任務(wù)調(diào)度、車輛路徑規(guī)劃等。通過對調(diào)度方案進(jìn)行編碼和演化，可以得到最優(yōu)的調(diào)度策略。
掌握遺傳算法的種類和知識點對程序員來說至關(guān)重要。以下是一些程序員需要掌握的關(guān)鍵知識點：
遺傳算法的基本原理：了解遺傳算法的基本概念和運行原理，包括編碼方式、適應(yīng)度函數(shù)、選擇、交叉和變異等操作。
編碼方式：了解如何將問題的解空間映射到遺傳算法的編碼空間，選擇合適的編碼方式對問題進(jìn)行建模。
適應(yīng)度函數(shù)：設(shè)計適應(yīng)度函數(shù)來評估個體的優(yōu)劣程度，以指導(dǎo)遺傳算法的搜索過程。
選擇算子：了解不同的選擇算子，如輪盤賭選擇、錦標(biāo)賽選擇等，以及它們之間的優(yōu)缺點。
交叉算子：學(xué)習(xí)如何通過交叉操作來生成新的個體，以增加種群的多樣性和搜索空間的覆蓋度。
變異算子：了解如何通過變異操作來引入新的基因信息，以避免陷入局部最優(yōu)解。
參數(shù)設(shè)置和調(diào)優(yōu)：掌握如何設(shè)置遺傳算法的參數(shù)，并通過實驗和調(diào)優(yōu)找到合適的參數(shù)值，以提高算法的性能。
并行與分布式遺傳算法：了解如何利用并行和分布式計算的方法來加速遺傳算法的執(zhí)行效率。文章來源：http://www.zghlxwxcb.cn/news/detail-558311.html
鼓勵程序員積極學(xué)習(xí)和深入研究遺傳算法領(lǐng)域。遺傳算法作為一種強大的優(yōu)化工具，在實際問題中發(fā)揮著重要的作用。通過學(xué)習(xí)和研究，程序員可以將遺傳算法應(yīng)用到自己的工作中，提高問題求解的效率和質(zhì)量。此外，深入研究遺傳算法還可以探索其改進(jìn)和擴(kuò)展，為解決更加復(fù)雜的問題提供新的思路和方法。文章來源地址http://www.zghlxwxcb.cn/news/detail-558311.html
到了這里，關(guān)于作為一個程序員一定要掌握的算法之遺傳算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
