Java利用遺傳算法求解最短路徑問題

Posted on 2022-06-07 by WalkonNet

遺傳算法（Genetic Algorithm，GA）最早是由美國的John holland於20世紀70年代提出,該算法是根據大自然中生物體進化規律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。

1、問題描述

圖1所示為一個最短路徑問題，每條邊代表一條可以通行的弧，邊上的數值表示這條弧的長度，多條弧相互連接形成路徑，目標是尋找一條從節點0出發到節點5的最短路徑。

2、編碼

從表現型到基因型的映射稱為編碼。圖1中每條路徑的每個節點對應一個基因，通過對節點的有序組合可以將每條路徑映射為一個向量。每個向量長度為6，起始和結束位置的數值分別為0和5，代表從節點0出發，到節點5終止，圖1中節點間邊的長度代表節點間的距離，若兩節點間無邊相連，則這兩個節點間的距離為一個極大的數M。由於向量長度固定為6，而解中可能並不包含所有的節點，個體中可能會存在多個相鄰且重復出現的節點，因此設置節點到其本身的距離為0。

3、個體類

每個個體包含路徑Path和適應度length（即路徑長度）兩個屬性，每個個體路徑屬性中的起點為0，結束點為5，其餘位置數值隨機生成（0-5范圍內的整數），向量長度固定為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）數據的初始化（2）定義初始種群（3）循環依次調用選擇、交叉和變異算子（4）輸出迭代後的結果。以鄰接矩陣的形式表達圖1中各節點間的距離，建立一個集合表示種群，隨機產生10個個體並添加到初始種群完成種群的初始化，設置迭代次數並依次調用三個算子更新種群，最終輸出結果。詳細代碼如下：

    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個較優的個體
            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、適應度

該問題中適應度即為每個個體所代表的路徑長度，適應度函數如下：

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個個體的種群。

在經過選擇算子後生成的包含5個個體的種群中隨機選擇兩個不同的個體，選擇一個不是首也不是尾的基因，將所選擇的兩個個體對應的基因進行交叉，並將新產生的個體添加到種群中去，返回新的種群。代碼如下：

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));
 
        //輸出交叉產生的個體
        System.out.println("交叉產生的個體為：" + 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個個體的種群。

隨機選擇一個個體，將這個個體的隨機一個不為首或尾的基因進行變異，隨機產生一個[0,5]中的數值代替該基因處的數值，將變異後產生的新的個體添加到種群中。重復以上步驟三次，共計產生三個新的個體。這裡需要註意的是，由於每次選擇要變異的個體都是隨機的，可能存在兩次甚至三次選擇同一個個體進行變異的情況，這也符合自然界中生物遺傳的思想。代碼如下：

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));
            //輸出交叉產生的個體
            System.out.println("第"+ (i+1) +"次變異產生的個體為：" + 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、總結

本文解決的問題復雜度較低，適合代碼或者遺傳算法的初學者嘗試解決。另外在解決該問題時，本文所采用的編碼方式較為簡單，雖可以很好的解決此類簡單問題，但在求解更復雜的問題時可能會存在計算結果為不可行解的情況，因此在采用遺傳算法解決更復雜的問題時，非常有必要對編碼方式進行進一步的加工，使其更適合問題特性且計算結果更優。完整的代碼如下：

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個較優的個體
            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個個體，返回兩個所選的適應度最好的個體
    //輸入：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;
    }
 
    //交叉產生兩個新的個體
    //輸入：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));
 
        //輸出交叉產生的個體
        System.out.println("交叉產生的個體為：" + 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));
            //輸出交叉產生的個體
            System.out.println("第"+ (i+1) +"次變異產生的個體為：" + 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次左右就已經求得最優解，為保證結果的最優性，本文對進行瞭2000次迭代，迭代結果與上一篇文章中通過Dijkstra方法求得的最優解一致。

在進行代碼的編寫時也遇到瞭一些比較經典的問題，總結如下：

1.初始版本的選擇算子中，先將每個個體的適應度屬性存儲到一個新建的數組中進行排序，此方法舍近求遠，因此對其進行改進，采用Collections.sort（）對種群中的個體進行排序。

2.初始版本的選擇算子中，采用for循環和while循環的方式刪除適應度大的個體，此種方式導致程序運行時出現死循環且不能很好的實現刪除5個適應度大的個體的目的，for循環中每次刪除個體後種群數量發生變化，程序運行會出現異常，因此對其進行改進，采用迭代器對個體進行刪除。

3.在交叉和變異算子中需要對集合進行復制，由於集合名代表的是集合存儲的地址，直接賦值仍然會修改原集合中的數據，因此在對集合進行深層次的復制，新建個體並將原集合中的個體屬性值分別賦給新個體後添加到復制集合中去。

到此這篇關於Java利用遺傳算法求解最短路徑問題的文章就介紹到這瞭,更多相關Java求最短路徑內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

Java利用遺傳算法求解最短路徑問題

目錄

1、問題描述

2、編碼

3、個體類

4、遺傳算法解決最短路徑問題主方法

5、適應度

6、選擇算子

7、交叉算子

8、變異算子

9、總結

推薦閱讀：

發佈留言取消回覆

近期文章

目錄

1、問題描述

2、編碼

3、個體類

4、遺傳算法解決最短路徑問題主方法

5、適應度

6、選擇算子

7、交叉算子

8、變異算子

9、總結

推薦閱讀：

發佈留言 取消回覆

近期文章

標籤

發佈留言取消回覆