「C++」蟻群算法求解最佳路徑問題（一日游規劃）

1 題目描述

為游客提供行程規劃服務，在滿足時間、資金約束下，使得行程的總體質量較高、路程較短。

某地有一組旅游景點，景點具有名稱、營業時間、門票價格、評分、游玩時長、**地理位置(經緯度坐標)**等信息。
該程序要根據游客的資金預算，自動生成一條合理的旅游路線。

上次采用遺傳算法實現了這個功能，這次采用蟻群算法。

2 題目要求

“一日游”的時間從早上八點到晚上七點；
生成的線路應盡量用完以上的游玩時間，但不能超時；
不需要考慮出發點和結束點，即可以從任意景點出發、在任意景點結束；
以線路中所有景點的評分的均值作為該線路的評價得分；
以所有景點的門票價格之和作為該線路的價格；
以各景點間的距離之和作為線路的路程長度；
線路的質量優劣，按以下公式計算：
$Q = 0.4 ? n or ma l (評價得分) + 0.4 ? n or ma l (價格) + 0.2 ? n or ma l (路程長度)$
其中， $\frac{評價得分}{景點數量}; 0\le評價得分\le5$
$normal(價格)=\frac{預算-價格}{預算}; 0≤價格\le預算$
$normal(路程長度)=\frac{最大長度-路程長度}{最大路程}; 0\le路程長度\le最大長度$

輸入:

200，50//說明:200為游客的預算，則生成的線路的價格不能超過該預算;50為游客一天最遠的行程，則線路的路程長度不能超過該最遠行程。

輸出:

//如果可行，則輸出一條較優的線路:
景點1、景點3、景點8、景點4 (0.82、4.2、180、50)//說明:先按順序輸出景點名稱，括號內分別為線路的質量得分、評價得分、價格、路程長度。
//如果不可行，如輸入的預算為0且無免費景點，則輸出:
error

3 解決方案

3.1 蟻群算法

3.1.1 算法簡介

蟻群算法（Ant Clony Optimization， ACO）是一種群智能算法，它是由一群無智能或有輕微智能的個體（Agent）通過相互協作而表現出智能行為，從而為求解復雜問題提供了一個新的可能性。蟻群算法最早是由意大利學者Colorni A., Dorigo M. 等于1991年提出。經過20多年的發展，蟻群算法在理論以及應用研究上已經得到巨大的進步。

蟻群算法是一種仿生學算法，是由自然界中螞蟻覓食的行為而啟發的。在自然界中，螞蟻覓食過程中，蟻群總能夠按照尋找到一條從蟻巢和食物源的最優路徑。[1]

3.1.2 算法邏輯

放一只螞蟻在一個起點處，由螞蟻來決定下一步走哪一個節點；
螞蟻經過一條路線，會留下信息素（Flomone），為后來的螞蟻提供選擇的依據；
信息素隨時間衰減；
每一只螞蟻經過這條路線都會帶來信息素，以減緩信息素的衰減效果；
每一次迭代中的螞蟻都會完成走完一條路線，一次迭代結束后根據螞蟻走過路線的情況更新信息素，再進行下一次迭代；

3.1.3 螞蟻的策略

在其他情況相同的情況下，螞蟻傾向于選擇路程更短的節點；
在路程相同的情況下，螞蟻傾向于選擇信息素濃度更高的路線；
螞蟻通過輪盤賭的方式選擇下一個節點，選擇一個節點的概率為：
$P_{ij}=\frac{\tau^\alpha_{ij}\eta^\beta_{ij}}{\Sigma_{z}\tau^\alpha_{iz}\eta^\beta_{iz}}$

其中，z是所有剩余的可選擇的節點， $\tau_{ij}$ 為第 $i$ 個節點到第 $j$ 個節點的路徑上的信息素， $\eta_{ij}$ 為第 $i$ 個節點到第 $j$ 個節點的“能見度”（路程的倒數）， $\alpha和\beta$ 分別為信息素和“能見度”的重要系數；

$\alpha$ 和 $\beta$ 影響蟻群的策略，需要一個適當的比例；

alpha=0時，無視 flomone，螞蟻完全根據能見度(上一次路線得分)做判斷，容易陷入局部最優解；
beta=0時，無視上次路線得分，螞蟻完全根據flomone做判斷，收斂速度快，但很難達到最優解；

公式解釋： 從當前節點 $i$ 到節點 $j$ 的概率為這兩個節點間的信息素與能見度的乘積，占當前節點到所有可選擇節點的比例。

信息素的更新由下面的公式決定：
$\tau_{ij}'=\rho\tau_{ij}+\Delta\tau$
其中， $\rho$ 為信息素的衰減系數， $\Delta\tau$ 為一輪迭代后螞蟻帶來的信息素變化。
$\Delta\tau=\frac{Q}{L}$
$Q$ 為一個常量，可取1； $L$ 為這一只螞蟻選擇的路線的路程；每一只螞蟻都會帶來信息素的變化，則 $\Delta\tau$ 應是所有變化的總和。

3.1.4 蟻群算法在本例中的應用

初始信息素濃度都為1；
由于本問題不是求解最短路徑，而是有評分作為指標找出最優的路線，所以能見度定義為 $\eta=0.4 * normal(評價得分) + 0.4 * normal(價格)+0.2 * normal(路程長度)$ ；
將信息素的變化量也相應改為 $\Delta\tau=\eta Q$ ；

3.2 構思

本質上需要用到的信息與《「C++」遺傳算法求解最佳路徑問題——“一日游”行程規劃程序》相似，所以大部分內容不需要修改。主要的差異在于實現算法的邏輯。

3.2.1 核心定義的類

需要定義幾個主要的類：

scenicSpot類用于記錄一個景點的信息（景點名、開放時間、關閉時間、價格、坐標等）；
Ant類用于記錄條路線的信息（路線、路線評價、路線價格、路線路程等）；
antColony類用于記錄蟻群和信息素等信息。

3.2.2 常用類和方法

除此之外，還有一些數據類型和功能被反復用到，處理成單獨的類和函數比較方便管理和計算：

coordinate類，記錄坐標，并實現坐標的計算功能；
mytime類，記錄時間，只記錄時、分、秒，方便時間的運算；
selector_sort函數，選擇排序；
find_vector函數，在vector中查找元素并返回下標；
vector容器存儲路線節點，方便變化長度，作為輔助作用；
除此之外還可重載矩陣的四則運算符，方便做矩陣的計算；

4 代碼概覽

4.1 mytime類

class mytime
{
private:
    int hour;
    int min;
    int sec;

public:
    mytime() { this->hour = this->min = this->sec = 0; }
    mytime(int h, int m = 0, int s = 0);
    mytime(string t);
    mytime(double t);
    ~mytime(){};
    int H() const { return this->hour; }//返回小時
    int M() const { return this->min; }//返回分鐘
    int S() const { return this->sec; }//返回秒
    void H(int h) { this->hour = h; }//修改小時
    void M(int m) { this->min = m; }//修改分鐘
    void S(int s) { this->sec = s; }//修改秒
    int to_sec() const;//時間轉為整數
    mytime &operator=(const mytime &m);//重載賦值運算符
    mytime &operator+=(const mytime &y);//重載自增運算符
    friend mytime toMytime(int sec);//整型轉為時間
    friend ostream &operator<<(ostream &out, const mytime m);//重載輸出運算符
    //重載四則運算
    friend mytime operator+(const mytime &m, const mytime &y);
    friend mytime operator-(const mytime &m, const mytime &y);
    friend double operator/(const mytime &m, const mytime &y);
    friend double operator*(const int &m, const mytime &y);
    //重載邏輯運算
    friend bool operator>(const mytime &m, const mytime &y);
    friend bool operator<(const mytime &m, const mytime &y);
    friend bool operator>=(const mytime &m, const mytime &y);
    friend bool operator<=(const mytime &m, const mytime &y);
    friend bool operator==(const mytime &m, const mytime &y);
    friend bool operator!=(const mytime &m, const mytime &y);
};

4.2 coordinate類

class coordinate
{
private:
    float abscissa; // 橫坐標
    float ordinate; // 縱坐標
public:
    coordinate() {}
    coordinate(float x, float y);
    coordinate(int x, int y);
    coordinate(double x, double y);
    float x() const { return abscissa; }//返回橫坐標
    float y() const { return ordinate; }//返回縱坐標
    // 賦值
    coordinate &operator=(const coordinate &coord);
    // 計算距離
    float distance(coordinate c);
    friend ostream &operator<<(ostream &out, const coordinate c);
};

4.3 選擇排序

template <typename T>
void selection_sort(std::vector<T> &arr)
{
    for (int i = 0; i < arr.size() - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < arr.size(); j++)
            if (arr[j] < arr[min])
                min = j;
        std::swap(arr[i], arr[min]);
    }
}

4.4 查找vector元素

// 查找
template <typename T>
int find_vector(vector<T> tlist, T t)
{
    for (int i = 0; i < tlist.size(); i++)
    {
        if (tlist[i] == t)
        {
            return i;
        }
    }
    return -1;
}

4.5 scenicSpot類

class scenicSpot
{
private:
    string scenicname;      // 景點名稱
    mytime busi_hour;       // 營業時間
    mytime clos_hour;       // 歇業時間
    float scenicprice;      // 門票價格
    float scenicscore;      // 評分
    mytime scenicduration;  // 游玩時長
    coordinate sceniccoord; // 景點坐標
public:
    scenicSpot() {}
    scenicSpot(string name, mytime busi = mytime(8), mytime clos = mytime(19), float price = 100, float score = 0, mytime duration = mytime(1), coordinate coord = coordinate(0, 0));
    ~scenicSpot(){};
    // 返回各項成員
    string name() const { return this->scenicname; }
    mytime businesshour() const { return this->busi_hour; }
    mytime closerhour() const { return this->clos_hour; }
    float price() const { return this->scenicprice; }
    float score() const { return this->scenicscore; }
    mytime duration() const { return this->scenicduration; }
    coordinate coord() const { return this->sceniccoord; }
    // 重載運算符
    scenicSpot &operator=(const scenicSpot s);
    bool operator==(const scenicSpot &s);
    friend ostream &operator<<(ostream &out, const scenicSpot &s);
};

4.6 class Ant核心函數

class Ant
{
private:
    vector<scenicSpot> nodes; // 基因序列，路線
    double Antstar;           // 路線評價
    double Antdistance;       // 路線路程
    double Antprice;          // 路線票價
    mytime Antendtime;        // 路線游玩時間
    double Antscore;          // 路線得分
public:
	//略去不重要的函數
    // 計算評分、路程等參數
    void calculate();
    // 其他操作
    vector<vector<double>> deltaTau(); // 返回這只螞蟻帶來的flomone變化
    bool isExist(scenicSpot spot) const;// 判斷路線是否已經存在該景點
    bool append();// 增加路線長度
    double calcscore(double budget, double maxtrip);// 計算線路得分
    // 重載算符
    friend ostream &operator<<(ostream &out, const Ant &c);
    Ant &operator=(const Ant s);
};

4.7 class antColony核心函數

class antColony
{
private:
    /* data */
    vector<Ant> ants;                // 螞蟻
    vector<Ant> best_ant;            // 存儲迭代中的最佳路徑，防止好的結果被刷新掉（取20個）
    vector<vector<double>> flomone;  // 弗洛蒙濃度（信息素）
    vector<scenicSpot> spots;        // 景點信息
    vector<vector<double>> spotsmap; // 景點地圖(路程信息)
    double bugdet;                   // 預算
    double maxtrip;                  // 最大路程
    int maxgen;                      // 最大迭代次數
    ofstream fout;                   // 把過程寫入文件方便查看
public:
    //略去其他不重要的成員函數
    int roulette();                   // 輪盤賭
    bool import(string path); // 從文件導入景點信息
    bool calcDist();// 計算景點間距離
    bool initFlomone(); // 初始化flomone
    bool initAnt();// 初始化螞蟻
    bool updateFlomone(); // 更新Flomone
    void Run();// 開始運行
};

4.8 一些參數

#define Q 0.1     // 系統常數（取值任意）
#define rho 0.3   // 揮發系數
#define alpha 0.5 // flomone 重要程度系數
#define beta 1.5  // 能見度重要程度系數（此處能見度定義為路線得分）
#define tau 1     // flomone濃度初始值
#define ants_num 10// 一個起點放置的螞蟻數量

4.9 main

#include "antColony.hpp"
int main(int argc, char *argv[])
{
    antColony antcolony;
    antcolony.Run();
    return 0;
}

5 參考

[1] 蟻群算法（Ant Colony Optimization）
[2] 【數之道 04】解決最優路徑問題的妙招-蟻群ACO算法
[3] 「C++」遺傳算法求解最佳路徑問題——“一日游”行程規劃程序

posted @ 2023-04-16 15:09 是陸柒閱讀(208) 評論(0) 收藏舉報來源

刷新頁面返回頂部