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

2022-06-07 22:03:39

遺傳演演算法（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求最短路徑內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！