人工智能 -- 模擬退火演算法解決TSP問題（JAVA版）

模擬退火演算法：由兩規則三函陣列成，

兩規則指：外層回圈結束規則、內層回圈結束規則，

三函式指：溫度更新函式（控制溫度的變化）、狀態產生函式（用于產生鄰結點）、狀態接收函式（用于判斷鄰結點是否應該被接受）

本代碼中退火演算法介紹：

外層回圈結束規則為：溫度小于某個指定的最低溫度

內層回圈結束規則為：溫度步長小于指定值，即每一個溫度執行的狀態選擇次數

狀態產生函式為：bulider_neighbor(Node node),根據傳入的結點，回傳該結點的鄰結點ArrayList集合，然后在該集合中隨機選取一個結點neighbor，作為新的結點

狀態接收函式：接受條件為 neighbor的距離代價value 小于 當前結點(cur_node)的距離代價value或者根據e^-(neighbor.value-cur_node.value)/T （T指當前溫度值 Temperature） 計算出一個概率值 P ，若P大于Random[0,1]之間的數，則接受，將新結點neighbor作為當前節點，若不滿足上述兩個條件，則拒絕接受，

溫度更新函式：此處偷懶，選擇最簡單的Temperature=Temperatrue*a；a的值為小于1的小數即可，保證Temperature的值下降，

package com.AI.Experiment4;

import java.util.ArrayList;
import java.util.Random;

/**
 * 模擬退火演算法，解決TSP（旅行商）問題
 */

class Node{
    public int[] sol;  //存放路徑
    public int value;  //存放該路徑的距離代價

    public Node(int num){
        sol=new int[num];
        value=Integer.MAX_VALUE;
    }
}

public class SA {
    private int[][] Dist;   //距離矩陣
    private float Temperature;//初始溫度
    private int City_num;   //城市數目
    private Node cur_node;  //初始化結點
    private Node best_neighbor; //最優鄰結點
    private float a;        //降溫系數

    /**
     * 傳入初始化引數：
     *      1.距離矩陣
     *      2.初始溫度
     *    
     *      注：可以為該演算法設定更多的初始化引數，例如：溫度步長、最低溫度等
     * @param dist
     * @param temperature
     */
    public SA(int[][] dist, int temperature,float a) {
        Dist = dist;
        Temperature = temperature;
        this.a=a;
        City_num=dist.length;

    }

    /**
     * 將node2的內容復制到node1中
     * @param node1
     * @param node2
     */
    public void CopyNode(Node node1,Node node2){
        for(int i=0;i<City_num;i++){
            node1.sol[i]=node2.sol[i];
        }
        node1.value=node2.value;
    }

    /**
     * 模擬退火演算法，主函式
     * @return
     */
    public Node SA_mian(){
        //先初始化各個引數
        init();

        Random random=new Random(); //用于生成亂數

        //外層回圈退出條件，溫度小于0.005（最低溫度）
        while(Temperature>0.005){
            int step=0; //溫度步長，內層回圈，每一個溫度執行200次計算
            while(step<200){

                  //下面是狀態產生函式部分    
        
                //隨機獲取當前結點的鄰結點
                ArrayList<Node> neighbors = builder_neighbors(cur_node);//獲取當前結點的鄰居結點的集合
                int index= random.nextInt(neighbors.size());   //隨機鄰結點在集合中的下標

                Node neighbor=neighbors.get(index); //獲取隨機鄰結點

                //下面是 狀態接受函式部分
                 
                //判斷隨機鄰結點的距離代價和當前結點的距離代價
                if(neighbor.value<cur_node.value){
                    //符合，則接受該鄰居結點作為當前結點
                    CopyNode(cur_node,neighbor);
                    CopyNode(best_neighbor,neighbor);
                }
                else{
                    if(Math.pow(Math.E,-(neighbor.value-cur_node.value)/Temperature)>random.nextDouble()){
                        CopyNode(cur_node,neighbor);
                    }
                }

                step++;
            }

            Temperature=Temperature*a;    //此處為溫度更新函式
        }

        return best_neighbor;    //回傳最優解
    }

    /**
     * 生成傳入結點的鄰結點集合
     * @param node
     * @return
     */
    public ArrayList<Node> builder_neighbors(Node node){
        ArrayList<Node> neighbors=new ArrayList<>();
        Node neighbor;//臨時變數存放鄰居結點
        int temp;   //臨時變數存放城市編號
        for(int i=1;i<City_num-1;i++){
            for (int j=2;j<City_num;j++){
                neighbor=new Node(City_num);
                
                //將當前結點復制給；鄰居結點
                CopyNode(neighbor,node);
                
                //交換第i個城市和第j個城市的位置
                temp=neighbor.sol[i];
                neighbor.sol[i]=neighbor.sol[j];
                neighbor.sol[j]=temp;

                //計算鄰居結點的距離代價
                neighbor.value=evaluate(neighbor);

                //將該鄰居結點加入集合
                neighbors.add(neighbor);
            }
        }

        return neighbors;
    }
    
    //初始化結點
    private void init(){
        cur_node=new Node(City_num);
        best_neighbor=new Node(City_num);

        for(int i=0;i<City_num;i++){
            cur_node.sol[i]=i;
        }

        //計算初始化結點的距離代價
        cur_node.value=evaluate(cur_node);

        //將初始化結點作為最優解結點
        CopyNode(best_neighbor,cur_node);
    }

    /**
     * 計算傳入結點的距離代價
     * @param node
     */
    public int evaluate(Node node){
        int distance=0;
        for(int i=1;i<City_num;i++){
            distance=distance+Dist[node.sol[i-1]][node.sol[i]];
        }

        distance=distance+Dist[node.sol[City_num-1]][node.sol[0]];

        return distance;
    }

    public static void main(String[] args) {
        int max=6555;
        
        //距離矩陣
        int[][] Dist={{max,3,2,3,max},{3,max,max,6,4},{2,max,max,1,5},{3,6,1,max,7},{max,4,5,7,max}};
        int temperature=100;
        float a=0.98f;
        SA sa=new SA(Dist,temperature,a);
        Node node = sa.SA_mian();

        for (int i=0;i<Dist.length;i++){
            System.out.print(node.sol[i]+"\t");
        }

        System.out.println("最優解的距離代價："+node.value);
    }
}

若演算法有不足或對演算法有不理解的地方，歡迎評論！