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