溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇“Java如何利用遺傳算法求解最短路徑”文章的知識(shí)點(diǎn)大部分人都不太理解，所以小編給大家總結(jié)了以下內(nèi)容，內(nèi)容詳細(xì)，步驟清晰，具有一定的借鑒價(jià)值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“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所示為一個(gè)最短路徑問題，每條邊代表一條可以通行的弧，邊上的數(shù)值表示這條弧的長度，多條弧相互連接形成路徑，目標(biāo)是尋找一條從節(jié)點(diǎn)0出發(fā)到節(jié)點(diǎn)5的最短路徑。
從表現(xiàn)型到基因型的映射稱為編碼。圖1中每條路徑的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)一個(gè)基因，通過對(duì)節(jié)點(diǎn)的有序組合可以將每條路徑映射為一個(gè)向量。每個(gè)向量長度為6，起始和結(jié)束位置的數(shù)值分別為0和5，代表從節(jié)點(diǎn)0出發(fā)，到節(jié)點(diǎn)5終止，圖1中節(jié)點(diǎn)間邊的長度代表節(jié)點(diǎn)間的距離，若兩節(jié)點(diǎn)間無邊相連，則這兩個(gè)節(jié)點(diǎn)間的距離為一個(gè)極大的數(shù)M。由于向量長度固定為6，而解中可能并不包含所有的節(jié)點(diǎn)，個(gè)體中可能會(huì)存在多個(gè)相鄰且重復(fù)出現(xiàn)的節(jié)點(diǎn)，因此設(shè)置節(jié)點(diǎn)到其本身的距離為0。
每個(gè)個(gè)體包含路徑Path和適應(yīng)度length（即路徑長度）兩個(gè)屬性，每個(gè)個(gè)體路徑屬性中的起點(diǎn)為0，結(jié)束點(diǎn)為5，其余位置數(shù)值隨機(jī)生成（0-5范圍內(nèi)的整數(shù)），向量長度固定為6。個(gè)體類中定義的compareTo方法是為了用于在選擇算子中采用迭代器進(jìn)行個(gè)體的刪除。
public class Individual implements Comparable<Individual>{
int[] Path = new int[6]; //存儲(chǔ)路徑
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;
}
}
}主方法包括（1）數(shù)據(jù)的初始化（2）定義初始種群（3）循環(huán)依次調(diào)用選擇、交叉和變異算子（4）輸出迭代后的結(jié)果。以鄰接矩陣的形式表達(dá)圖1中各節(jié)點(diǎn)間的距離， 建立一個(gè)集合表示種群，隨機(jī)產(chǎn)生10個(gè)個(gè)體并添加到初始種群完成種群的初始化，設(shè)置迭代次數(shù)并依次調(diào)用三個(gè)算子更新種群，最終輸出結(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ī)生成十個(gè)個(gè)體添加到初始種群列表
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個(gè)較優(yōu)的個(gè)體
List<Individual> NewSelPopu = Selection(Population);
//交叉
List<Individual> NewCroPopu = Crossover(NewSelPopu);
//變異
Population = Variation(NewCroPopu);
System.out.println("第"+ (i+1) + "次迭代完成！");
}
//輸出迭代后的種群
System.out.print("2000次迭代后集合中個(gè)體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//對(duì)集合中的個(gè)體排序
Collections.sort(Population);
//輸出排序后的集合中個(gè)體的長度
System.out.print("\n" +"2000次迭代后所有個(gè)體的最短路徑長度為:" + Population.get(9).length);
System.out.println("\n"+"最短路徑為：" + Arrays.toString(Population.get(9).Path));
}該問題中適應(yīng)度即為每個(gè)個(gè)體所代表的路徑長度，適應(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]];
}輸入：包含10個(gè)個(gè)體的種群。
輸出：包含5個(gè)個(gè)體的種群。
計(jì)算所輸入的種群的所有個(gè)體的適應(yīng)度，并按照適應(yīng)度將這些個(gè)體進(jìn)行升序排列，刪除掉其中適應(yīng)度較大的五個(gè)個(gè)體，并返回剩余的種群。代碼如下：
static List<Individual> Selection(List<Individual> Population){
System.out.print("排序前集合中個(gè)體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//對(duì)集合中的個(gè)體排序
Collections.sort(Population);
//輸出排序后的集合中個(gè)體的長度
System.out.print("\n" +"排序后集合中個(gè)體的長度:");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//使用迭代器刪除個(gè)體
Iterator<Individual> iterator = Population.iterator();
while(iterator.hasNext() && Population.size()>5){
Individual next = iterator.next();
if(next != null)
iterator.remove();
}
//輸出刪除后的個(gè)體的長度
System.out.print("\n" + "選擇后的個(gè)體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
System.out.println("\n" + "選擇完成!");
return Population;
}輸入：包含5個(gè)個(gè)體的種群。
輸出：包含7個(gè)個(gè)體的種群。
在經(jīng)過選擇算子后生成的包含5個(gè)個(gè)體的種群中隨機(jī)選擇兩個(gè)不同的個(gè)體，選擇一個(gè)不是首也不是尾的基因，將所選擇的兩個(gè)個(gè)體對(duì)應(yīng)的基因進(jìn)行交叉，并將新產(chǎn)生的個(gè)體添加到種群中去，返回新的種群。代碼如下：
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ī)選擇兩個(gè)不同的個(gè)體
int i = rand.nextInt(5);
int j = rand.nextInt(5);
while(i == j){
j = rand.nextInt(5);
}
//隨機(jī)選擇一個(gè)不是首尾的基因進(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)生的個(gè)體
System.out.println("交叉產(chǎn)生的個(gè)體為：" + Arrays.toString(CroPopu.get(i).Path) + "和" + Arrays.toString(CroPopu.get(j).Path));
//輸出交叉后的個(gè)體適應(yīng)度
System.out.print("交叉后的個(gè)體的長度：");
for(Individual a : NewSelPopu){
System.out.print(a.length +" ");
}
System.out.println("\n"+"交叉完成！");
return NewSelPopu;
}輸入：包含7個(gè)個(gè)體的種群。
輸出：包含10個(gè)個(gè)體的種群。
隨機(jī)選擇一個(gè)個(gè)體，將這個(gè)個(gè)體的隨機(jī)一個(gè)不為首或尾的基因進(jìn)行變異，隨機(jī)產(chǎn)生一個(gè)[0,5]中的數(shù)值代替該基因處的數(shù)值，將變異后產(chǎn)生的新的個(gè)體添加到種群中。重復(fù)以上步驟三次，共計(jì)產(chǎn)生三個(gè)新的個(gè)體。這里需要注意的是，由于每次選擇要變異的個(gè)體都是隨機(jī)的，可能存在兩次甚至三次選擇同一個(gè)個(gè)體進(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ī)選擇一個(gè)個(gè)體的一個(gè)基因進(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)生的個(gè)體
System.out.println("第"+ (i+1) +"次變異產(chǎn)生的個(gè)體為：" + Arrays.toString(VarPopu.get(i).Path));
}
//輸出變異后的個(gè)體適應(yīng)度
System.out.print("變異后的個(gè)體的長度：");
for(Individual a : NewCroPopu){
System.out.print(a.length +" ");
}
System.out.println("\n"+"變異完成！");
return NewCroPopu;
}本文解決的問題復(fù)雜度較低，適合代碼或者遺傳算法的初學(xué)者嘗試解決。另外在解決該問題時(shí)，本文所采用的編碼方式較為簡單，雖可以很好的解決此類簡單問題，但在求解更復(fù)雜的問題時(shí)可能會(huì)存在計(jì)算結(jié)果為不可行解的情況，因此在采用遺傳算法解決更復(fù)雜的問題時(shí)，非常有必要對(duì)編碼方式進(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ī)生成十個(gè)個(gè)體添加到初始種群列表
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) + "個(gè)個(gè)體為：");
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個(gè)較優(yōu)的個(gè)體
List<Individual> NewSelPopu = Selection(Population);
//交叉
List<Individual> NewCroPopu = Crossover(NewSelPopu);
//變異
Population = Variation(NewCroPopu);
System.out.println("第"+ (i+1) + "次迭代完成！");
}
//輸出迭代后的種群
System.out.print("2000次迭代后集合中個(gè)體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//對(duì)集合中的個(gè)體排序
Collections.sort(Population);
//輸出排序后的集合中個(gè)體的長度
System.out.print("\n" +"2000次迭代后所有個(gè)體的最短路徑長度為:" + Population.get(9).length);
System.out.println("\n"+"最短路徑為：" + Arrays.toString(Population.get(9).Path));
}
//選擇函數(shù),刪除種群中較大的5個(gè)個(gè)體，返回兩個(gè)所選的適應(yīng)度最好的個(gè)體
//輸入：10個(gè)個(gè)體的種群
//輸出：5個(gè)個(gè)體的種群
static List<Individual> Selection(List<Individual> Population){
System.out.print("排序前集合中個(gè)體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//對(duì)集合中的個(gè)體排序
Collections.sort(Population);
//輸出排序后的集合中個(gè)體的長度
System.out.print("\n" +"排序后集合中個(gè)體的長度:");
for(Individual a : Population){
System.out.print(a.length +" ");
}
//使用迭代器刪除個(gè)體
Iterator<Individual> iterator = Population.iterator();
while(iterator.hasNext() && Population.size()>5){
Individual next = iterator.next();
if(next != null)
iterator.remove();
}
//輸出刪除后的個(gè)體的長度
System.out.print("\n" + "選擇后的個(gè)體的長度：");
for(Individual a : Population){
System.out.print(a.length +" ");
}
System.out.println("\n" + "選擇完成!");
return Population;
}
//交叉產(chǎn)生兩個(gè)新的個(gè)體
//輸入：5個(gè)個(gè)體的種群
//輸出：7個(gè)個(gè)體的種群
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ī)選擇兩個(gè)不同的個(gè)體
int i = rand.nextInt(5);
int j = rand.nextInt(5);
while(i == j){
j = rand.nextInt(5);
}
//隨機(jī)選擇一個(gè)不是首尾的基因進(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)生的個(gè)體
System.out.println("交叉產(chǎn)生的個(gè)體為：" + Arrays.toString(CroPopu.get(i).Path) + "和" + Arrays.toString(CroPopu.get(j).Path));
//輸出交叉后的個(gè)體適應(yīng)度
System.out.print("交叉后的個(gè)體的長度：");
for(Individual a : NewSelPopu){
System.out.print(a.length +" ");
}
System.out.println("\n"+"交叉完成！");
return NewSelPopu;
}
//變異兩個(gè)個(gè)體
//輸入：7個(gè)個(gè)體的種群
//輸出：10個(gè)個(gè)體的種群
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ī)選擇一個(gè)個(gè)體的一個(gè)基因進(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)生的個(gè)體
System.out.println("第"+ (i+1) +"次變異產(chǎn)生的個(gè)體為：" + Arrays.toString(VarPopu.get(i).Path));
}
//輸出變異后的個(gè)體適應(yīng)度
System.out.print("變異后的個(gè)體的長度：");
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]; //存儲(chǔ)路徑
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次迭代后集合中個(gè)體的長度：9 9 9 9 9 9 9 9 9 10003
2000次迭代后所有個(gè)體的最短路徑長度為:9
最短路徑為：[0, 2, 2, 2, 3, 5]
由于問題比較簡單，一般迭代100次左右就已經(jīng)求得最優(yōu)解，為保證結(jié)果的最優(yōu)性，本文對(duì)進(jìn)行了2000次迭代，迭代結(jié)果與上一篇文章中通過Dijkstra方法求得的最優(yōu)解一致。
在進(jìn)行代碼的編寫時(shí)也遇到了一些比較經(jīng)典的問題，總結(jié)如下：
1.初始版本的選擇算子中，先將每個(gè)個(gè)體的適應(yīng)度屬性存儲(chǔ)到一個(gè)新建的數(shù)組中進(jìn)行排序，此方法舍近求遠(yuǎn)，因此對(duì)其進(jìn)行改進(jìn)，采用Collections.sort（）對(duì)種群中的個(gè)體進(jìn)行排序。
2.初始版本的選擇算子中，采用for循環(huán)和while循環(huán)的方式刪除適應(yīng)度大的個(gè)體，此種方式導(dǎo)致程序運(yùn)行時(shí)出現(xiàn)死循環(huán)且不能很好的實(shí)現(xiàn)刪除5個(gè)適應(yīng)度大的個(gè)體的目的，for循環(huán)中每次刪除個(gè)體后種群數(shù)量發(fā)生變化，程序運(yùn)行會(huì)出現(xiàn)異常，因此對(duì)其進(jìn)行改進(jìn)，采用迭代器對(duì)個(gè)體進(jìn)行刪除。
3.在交叉和變異算子中需要對(duì)集合進(jìn)行復(fù)制，由于集合名代表的是集合存儲(chǔ)的地址，直接賦值仍然會(huì)修改原集合中的數(shù)據(jù)，因此在對(duì)集合進(jìn)行深層次的復(fù)制，新建個(gè)體并將原集合中的個(gè)體屬性值分別賦給新個(gè)體后添加到復(fù)制集合中去。
以上就是關(guān)于“Java如何利用遺傳算法求解最短路徑”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對(duì)大家有幫助，若想了解更多相關(guān)的知識(shí)內(nèi)容，請(qǐng)關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼