Java利用遺傳算法求解最短路徑問題
更新時間：2022年06月07日 16:02:21 作者：Xing_LG
遺傳算法（Genetic Algorithm，GA）最早是由美國的John holland于20世紀70年代提出,該算法是根據(jù)大自然中生物體進化規(guī)律而設計提出的。本文將利用遺傳算法求解最短路徑問題，需要的可以參考一下
遺傳算法（Genetic Algorithm，GA）最早是由美國的John holland于20世紀70年代提出,該算法是根據(jù)大自然中生物體進化規(guī)律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優(yōu)解的方法。
1、問題描述
圖1所示為一個最短路徑問題，每條邊代表一條可以通行的弧，邊上的數(shù)值表示這條弧的長度，多條弧相互連接形成路徑，目標是尋找一條從節(jié)點0出發(fā)到節(jié)點5的最短路徑。
2、編碼
從表現(xiàn)型到基因型的映射稱為編碼。圖1中每條路徑的每個節(jié)點對應一個基因，通過對節(jié)點的有序組合可以將每條路徑映射為一個向量。每個向量長度為6，起始和結束位置的數(shù)值分別為0和5，代表從節(jié)點0出發(fā)，到節(jié)點5終止，圖1中節(jié)點間邊的長度代表節(jié)點間的距離，若兩節(jié)點間無邊相連，則這兩個節(jié)點間的距離為一個極大的數(shù)M。由于向量長度固定為6，而解中可能并不包含所有的節(jié)點，個體中可能會存在多個相鄰且重復出現(xiàn)的節(jié)點，因此設置節(jié)點到其本身的距離為0。
3、個體類
每個個體包含路徑Path和適應度length（即路徑長度）兩個屬性，每個個體路徑屬性中的起點為0，結束點為5，其余位置數(shù)值隨機生成（0-5范圍內的整數(shù)），向量長度固定為6。個體類中定義的compareTo方法是為了用于在選擇算子中采用迭代器進行個體的刪除。
public class Individual implements Comparable<Individual>{
int[] Path = new int[6]; //存儲路徑
int length; //表示適應度
public int[] getPath() {
return Path;
}
public void setPath(int[] path) {
Path = path;
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
public int compareTo(Individual o) {
if(this.getLength() > o.getLength())
{
return -1;
}
else if(this.getLength()<o.getLength())
{
return 1;
}
else
{
return 0;
}
}
}4、遺傳算法解決最短路徑問題主方法
主方法包括（1）數(shù)據(jù)的初始化（2）定義初始種群（3）循環(huán)依次調用選擇、交叉和變異算子（4）輸出迭代后的結果。以鄰接矩陣的形式表達圖1中各節(jié)點間的距離， 建立一個集合表示種群，隨機產(chǎn)生10個個體并添加到初始種群完成種群的初始化，設置迭代次數(shù)并依次調用三個算子更新種群，最終輸出結果。詳細代碼如下：
static int[][] matrix = new int[6][6];
final static int M = 10000;
static Random rand = new Random();
public static void main(String[] args) {
//鄰接矩陣
matrix[0] = new int[]{0, 6, 3, M, M, M};/*1*/
matrix[1] = new int[]{6, 0, 2, 5, M, M};/*2*/
matrix[2] = new int[]{3, 2, 0, 3, 4, M};/*3*/
matrix[3] = new int[]{M, 5, 3, 0, 2, 3};/*4*/
matrix[4] = new int[]{M, M, 4, 2, 0, 5};/*5*/
matrix[5] = new int[]{M, M, M, 3, 5, 0};/*6*/
//定義初始種群
Math.random();
List<Individual> Population = new ArrayList<>();
for (int i = 0; i < 10; i++) {
//隨機生成十個個體添加到初始種群列表
Individual Popu = new Individual();
Popu.Path[0] = 0;
Popu.Path[1] = rand.nextInt(5);
Popu.Path[2] = rand.nextInt(5);
Popu.Path[3] = rand.nextInt(5);
Popu.Path[4] = rand.nextInt(5);
Popu.Path[5] = 5;
Popu.length = M;
Population.add(Popu);
}
for(int i = 0; i<2000; i++){
System.out.println("第"+(i+1)+"次迭代開始！");
//初始種群中選擇出5個較優(yōu)的個體
List<Individual> NewSelPopu = Selection(Population);
//交叉
List<Individual> NewCroPopu = Crossover(NewSelPopu);
//變異
Population = Variation(NewCroPopu);
System.out.println("第"+ (i+1) + "次迭代完成！");
}
//輸出迭代后的種群
System.out.print("2000次迭代后集合中個體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//對集合中的個體排序
Collections.sort(Population);
//輸出排序后的集合中個體的長度
System.out.print("\n" +"2000次迭代后所有個體的最短路徑長度為:" + Population.get(9).length);
System.out.println("\n"+"最短路徑為：" + Arrays.toString(Population.get(9).Path));
}5、適應度
該問題中適應度即為每個個體所代表的路徑長度，適應度函數(shù)如下：
static void Fitness(Individual in){
//計算路徑長度
in.length = matrix[in.Path[0]][in.Path[1]] + matrix[in.Path[1]][in.Path[2]] +
matrix[in.Path[2]][in.Path[3]] + matrix[in.Path[3]][in.Path[4]] + matrix[in.Path[4]][in.Path[5]];
}
6、選擇算子
輸入：包含10個個體的種群。
輸出：包含5個個體的種群。
計算所輸入的種群的所有個體的適應度，并按照適應度將這些個體進行升序排列，刪除掉其中適應度較大的五個個體，并返回剩余的種群。代碼如下：
static List<Individual> Selection(List<Individual> Population){
System.out.print("排序前集合中個體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//對集合中的個體排序
Collections.sort(Population);
//輸出排序后的集合中個體的長度
System.out.print("\n" +"排序后集合中個體的長度:");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//使用迭代器刪除個體
Iterator<Individual> iterator = Population.iterator();
while(iterator.hasNext() && Population.size()>5){
Individual next = iterator.next();
if(next != null)
iterator.remove();
}
//輸出刪除后的個體的長度
System.out.print("\n" + "選擇后的個體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
System.out.println("\n" + "選擇完成!");
return Population;
}7、交叉算子
輸入：包含5個個體的種群。
輸出：包含7個個體的種群。
在經(jīng)過選擇算子后生成的包含5個個體的種群中隨機選擇兩個不同的個體，選擇一個不是首也不是尾的基因，將所選擇的兩個個體對應的基因進行交叉，并將新產(chǎn)生的個體添加到種群中去，返回新的種群。代碼如下：
static List<Individual> Crossover(List<Individual> NewSelPopu){
//復制集合
List<Individual> CroPopu = new ArrayList<>();
for (int i = 0; i < 5; i++) {
Individual ind = new Individual();
System.arraycopy(NewSelPopu.get(i).Path, 0, ind.Path, 0, 6);
ind.length = NewSelPopu.get(i).length;
CroPopu.add(ind);
}
//隨機選擇兩個不同的個體
int i = rand.nextInt(5);
int j = rand.nextInt(5);
while(i == j){
j = rand.nextInt(5);
}
//隨機選擇一個不是首尾的基因進行交叉
int k = rand.nextInt(4) + 1;
int l = CroPopu.get(i).Path[k];
CroPopu.get(i).Path[k] = CroPopu.get(j).Path[k];
CroPopu.get(j).Path[k] = l;
//更新length并添加到集合中
Fitness(CroPopu.get(i));
Fitness(CroPopu.get(j));
NewSelPopu.add(CroPopu.get(i));
NewSelPopu.add(CroPopu.get(j));
//輸出交叉產(chǎn)生的個體
System.out.println("交叉產(chǎn)生的個體為：" + Arrays.toString(CroPopu.get(i).Path) + "和" + Arrays.toString(CroPopu.get(j).Path));
//輸出交叉后的個體適應度
System.out.print("交叉后的個體的長度：");
for(Individual a : NewSelPopu){
System.out.print(a.length +" ");
}
System.out.println("\n"+"交叉完成！");
return NewSelPopu;
}8、變異算子
輸入：包含7個個體的種群。
輸出：包含10個個體的種群。
隨機選擇一個個體，將這個個體的隨機一個不為首或尾的基因進行變異，隨機產(chǎn)生一個[0,5]中的數(shù)值代替該基因處的數(shù)值，將變異后產(chǎn)生的新的個體添加到種群中。重復以上步驟三次，共計產(chǎn)生三個新的個體。這里需要注意的是，由于每次選擇要變異的個體都是隨機的，可能存在兩次甚至三次選擇同一個個體進行變異的情況，這也符合自然界中生物遺傳的思想。代碼如下：
static List<Individual> Variation(List<Individual> NewCroPopu){
//復制集合
List<Individual> VarPopu = new ArrayList<>();
for (int i = 0; i < 7; i++) {
Individual ind = new Individual();
System.arraycopy(NewCroPopu.get(i).Path, 0, ind.Path, 0, 6);
ind.length = NewCroPopu.get(i).length;
VarPopu.add(ind);
}
//變異三次
for (int i = 0; i < 3; i++) {
//隨機選擇一個個體的一個基因進行變異
int j = rand.nextInt(7);
VarPopu.get(j).Path[(rand.nextInt(4) + 1)] = rand.nextInt(5);
//更新length并添加到集合中
Fitness(VarPopu.get(j));
NewCroPopu.add(VarPopu.get(j));
//輸出交叉產(chǎn)生的個體
System.out.println("第"+ (i+1) +"次變異產(chǎn)生的個體為：" + Arrays.toString(VarPopu.get(i).Path));
}
//輸出變異后的個體適應度
System.out.print("變異后的個體的長度：");
for(Individual a : NewCroPopu){
System.out.print(a.length +" ");
}
System.out.println("\n"+"變異完成！");
return NewCroPopu;
}9、總結
本文解決的問題復雜度較低，適合代碼或者遺傳算法的初學者嘗試解決。另外在解決該問題時，本文所采用的編碼方式較為簡單，雖可以很好的解決此類簡單問題，但在求解更復雜的問題時可能會存在計算結果為不可行解的情況，因此在采用遺傳算法解決更復雜的問題時，非常有必要對編碼方式進行進一步的加工，使其更適合問題特性且計算結果更優(yōu)。完整的代碼如下：
import java.util.*;
public class GeneticAlgorithm {
static int[][] matrix = new int[6][6];
final static int M = 10000;
static Random rand = new Random();
public static void main(String[] args) {
//鄰接矩陣
matrix[0] = new int[]{0, 6, 3, M, M, M};/*1*/
matrix[1] = new int[]{6, 0, 2, 5, M, M};/*2*/
matrix[2] = new int[]{3, 2, 0, 3, 4, M};/*3*/
matrix[3] = new int[]{M, 5, 3, 0, 2, 3};/*4*/
matrix[4] = new int[]{M, M, 4, 2, 0, 5};/*5*/
matrix[5] = new int[]{M, M, M, 3, 5, 0};/*6*/
//定義初始種群
Math.random();
List<Individual> Population = new ArrayList<>();
for (int i = 0; i < 10; i++) {
//隨機生成十個個體添加到初始種群列表
Individual Popu = new Individual();
Popu.Path[0] = 0;
Popu.Path[1] = rand.nextInt(5);
Popu.Path[2] = rand.nextInt(5);
Popu.Path[3] = rand.nextInt(5);
Popu.Path[4] = rand.nextInt(5);
Popu.Path[5] = 5;
Popu.length = M;
Population.add(Popu);
}
//輸出初始種群
for (int i = 0; i < 10; i++) {
System.out.println("初始種群中第" + (i+1) + "個個體為：");
for (int j = 0; j < 6; j++) {
System.out.print(Population.get(i).Path[j]);
}
//更新length
for (int j = 0; j < 10; j++) {
Fitness(Population.get(j));
}
System.out.println("\n" +"適應度為：" +Population.get(i).length);
System.out.println();
}
for(int i = 0; i<2000; i++){
System.out.println("第"+(i+1)+"次迭代開始！");
//初始種群中選擇出5個較優(yōu)的個體
List<Individual> NewSelPopu = Selection(Population);
//交叉
List<Individual> NewCroPopu = Crossover(NewSelPopu);
//變異
Population = Variation(NewCroPopu);
System.out.println("第"+ (i+1) + "次迭代完成！");
}
//輸出迭代后的種群
System.out.print("2000次迭代后集合中個體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//對集合中的個體排序
Collections.sort(Population);
//輸出排序后的集合中個體的長度
System.out.print("\n" +"2000次迭代后所有個體的最短路徑長度為:" + Population.get(9).length);
System.out.println("\n"+"最短路徑為：" + Arrays.toString(Population.get(9).Path));
}
//選擇函數(shù),刪除種群中較大的5個個體，返回兩個所選的適應度最好的個體
//輸入：10個個體的種群
//輸出：5個個體的種群
static List<Individual> Selection(List<Individual> Population){
System.out.print("排序前集合中個體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//對集合中的個體排序
Collections.sort(Population);
//輸出排序后的集合中個體的長度
System.out.print("\n" +"排序后集合中個體的長度:");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//使用迭代器刪除個體
Iterator<Individual> iterator = Population.iterator();
while(iterator.hasNext() && Population.size()>5){
Individual next = iterator.next();
if(next != null)
iterator.remove();
}
//輸出刪除后的個體的長度
System.out.print("\n" + "選擇后的個體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
System.out.println("\n" + "選擇完成!");
return Population;
}
//交叉產(chǎn)生兩個新的個體
//輸入：5個個體的種群
//輸出：7個個體的種群
static List<Individual> Crossover(List<Individual> NewSelPopu){
//復制集合
List<Individual> CroPopu = new ArrayList<>();
for (int i = 0; i < 5; i++) {
Individual ind = new Individual();
System.arraycopy(NewSelPopu.get(i).Path, 0, ind.Path, 0, 6);
ind.length = NewSelPopu.get(i).length;
CroPopu.add(ind);
}
//隨機選擇兩個不同的個體
int i = rand.nextInt(5);
int j = rand.nextInt(5);
while(i == j){
j = rand.nextInt(5);
}
//隨機選擇一個不是首尾的基因進行交叉
int k = rand.nextInt(4) + 1;
int l = CroPopu.get(i).Path[k];
CroPopu.get(i).Path[k] = CroPopu.get(j).Path[k];
CroPopu.get(j).Path[k] = l;
//更新length并添加到集合中
Fitness(CroPopu.get(i));
Fitness(CroPopu.get(j));
NewSelPopu.add(CroPopu.get(i));
NewSelPopu.add(CroPopu.get(j));
//輸出交叉產(chǎn)生的個體
System.out.println("交叉產(chǎn)生的個體為：" + Arrays.toString(CroPopu.get(i).Path) + "和" + Arrays.toString(CroPopu.get(j).Path));
//輸出交叉后的個體適應度
System.out.print("交叉后的個體的長度：");
for(Individual a : NewSelPopu){
System.out.print(a.length +" ");
}
System.out.println("\n"+"交叉完成！");
return NewSelPopu;
}
//變異兩個個體
//輸入：7個個體的種群
//輸出：10個個體的種群
static List<Individual> Variation(List<Individual> NewCroPopu){
//復制集合
List<Individual> VarPopu = new ArrayList<>();
for (int i = 0; i < 7; i++) {
Individual ind = new Individual();
System.arraycopy(NewCroPopu.get(i).Path, 0, ind.Path, 0, 6);
ind.length = NewCroPopu.get(i).length;
VarPopu.add(ind);
}
//變異三次
for (int i = 0; i < 3; i++) {
//隨機選擇一個個體的一個基因進行變異
int j = rand.nextInt(7);
VarPopu.get(j).Path[(rand.nextInt(4) + 1)] = rand.nextInt(5);
//更新length并添加到集合中
Fitness(VarPopu.get(j));
NewCroPopu.add(VarPopu.get(j));
//輸出交叉產(chǎn)生的個體
System.out.println("第"+ (i+1) +"次變異產(chǎn)生的個體為：" + Arrays.toString(VarPopu.get(i).Path));
}
//輸出變異后的個體適應度
System.out.print("變異后的個體的長度：");
for(Individual a : NewCroPopu){
System.out.print(a.length +" ");
}
System.out.println("\n"+"變異完成！");
return NewCroPopu;
}
//更新適應度
static void Fitness(Individual in){
//計算路徑長度
in.length = matrix[in.Path[0]][in.Path[1]] + matrix[in.Path[1]][in.Path[2]] +
matrix[in.Path[2]][in.Path[3]] + matrix[in.Path[3]][in.Path[4]] + matrix[in.Path[4]][in.Path[5]];
}
}public class Individual implements Comparable<Individual>{
int[] Path = new int[6]; //存儲路徑
int length; //表示適應度
public int[] getPath() {
return Path;
}
public void setPath(int[] path) {
Path = path;
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
public int compareTo(Individual o) {
if(this.getLength() > o.getLength())
{
return -1;
}
else if(this.getLength()<o.getLength())
{
return 1;
}
else
{
return 0;
}
}
}運行結果如下：
第2000次迭代完成！
2000次迭代后集合中個體的長度：9 9 9 9 9 9 9 9 9 10003
2000次迭代后所有個體的最短路徑長度為:9
最短路徑為：[0, 2, 2, 2, 3, 5]
由于問題比較簡單，一般迭代100次左右就已經(jīng)求得最優(yōu)解，為保證結果的最優(yōu)性，本文對進行了2000次迭代，迭代結果與上一篇文章中通過Dijkstra方法求得的最優(yōu)解一致。
在進行代碼的編寫時也遇到了一些比較經(jīng)典的問題，總結如下：
1.初始版本的選擇算子中，先將每個個體的適應度屬性存儲到一個新建的數(shù)組中進行排序，此方法舍近求遠，因此對其進行改進，采用Collections.sort（）對種群中的個體進行排序。
2.初始版本的選擇算子中，采用for循環(huán)和while循環(huán)的方式刪除適應度大的個體，此種方式導致程序運行時出現(xiàn)死循環(huán)且不能很好的實現(xiàn)刪除5個適應度大的個體的目的，for循環(huán)中每次刪除個體后種群數(shù)量發(fā)生變化，程序運行會出現(xiàn)異常，因此對其進行改進，采用迭代器對個體進行刪除。
3.在交叉和變異算子中需要對集合進行復制，由于集合名代表的是集合存儲的地址，直接賦值仍然會修改原集合中的數(shù)據(jù)，因此在對集合進行深層次的復制，新建個體并將原集合中的個體屬性值分別賦給新個體后添加到復制集合中去。
到此這篇關于Java利用遺傳算法求解最短路徑問題的文章就介紹到這了,更多相關Java求最短路徑內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
本文給大家分享Jenkins集成SonarQube遇到的報錯問題及解決方法，本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友參考下吧2021-07-07
SSH框架網(wǎng)上商城項目第25戰(zhàn)之使用java email給用戶發(fā)送郵件
這篇文章主要為大家詳細介紹了SSH框架網(wǎng)上商城項目第25戰(zhàn)之使用java email給用戶發(fā)送郵件，感興趣的小伙伴們可以參考一下2016-06-06
詳解JAVA中implement和extends的區(qū)別
這篇文章主要介紹了詳解JAVA中implement和extends的區(qū)別的相關資料,extends是繼承接口，implement是一個類實現(xiàn)一個接口的關鍵字，需要的朋友可以參考下2017-08-08
這篇文章主要為大家詳細介紹了Java?IO流的三個應用案例：點名器、集合到文件和文件到集合，文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下2022-09-09
這篇文章主要為大家介紹了線上Spring CPU 高負載解決思路詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-09-09
這篇文章主要介紹了Java常用線程池原理及使用方法解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-07-07
java編程創(chuàng)建型設計模式單例模式的七種示例
這篇文章主要為大家介紹了java編程中創(chuàng)建型設計模式之單例模式的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助2022-02-02
這篇文章主要介紹了IDEA中java斷言assert語法詳解,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
門面模式又叫外觀模式（Facade Pattern），主要用于隱藏系統(tǒng)的復雜性，并向客戶端提供了一個客戶端可以訪問系統(tǒng)的接口，本文通過實例代碼給大家介紹下java門面模式的相關知識，感興趣的朋友一起看看吧2023-02-02
這篇文章主要介紹了基于重定向RedirectAttributes的用法，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12