「C++」蟻群算法求解最佳路徑問題(一日游規劃)
「C++」蟻群算法求解最佳路徑問題(一日游規劃)
1 題目描述
為游客提供行程規劃服務,在滿足時間、資金約束下,使得行程的總體質量較高、路程較短。
- 某地有一組旅游景點,景點具有名稱、營業時間、門票價格、評分、游玩時長、**地理位置(經緯度坐標)**等信息。
- 該程序要根據游客的資金預算,自動生成一條合理的旅游路線。
上次采用遺傳算法實現了這個功能,這次采用蟻群算法。
2 題目要求
-
“一日游”的時間從早上八點到晚上七點;
-
生成的線路應盡量用完以上的游玩時間,但不能超時;
-
不需要考慮出發點和結束點,即可以從任意景點出發、在任意景點結束;
-
以線路中所有景點的評分的均值作為該線路的評價得分;
-
以所有景點的門票價格之和作為該線路的價格;
-
以各景點間的距離之和作為線路的路程長度;
-
線路的質量優劣,按以下公式計算:
Q = 0.4 ? n o r m a l ( 評價得分 ) + 0.4 ? n o r m a l ( 價格 ) + 0.2 ? n o r m a l ( 路程長度 ) Q=0.4 * normal(評價得分) + 0.4 * normal(價格)+0.2 * normal(路程長度) Q=0.4?normal(評價得分)+0.4?normal(價格)+0.2?normal(路程長度)
其中, n o r m a l ( 評價得分 ) = 評價得分 景點數量 ; 0 ≤ 評價得分 ≤ 5 normal(評價得分) = \frac{評價得分}{景點數量}; 0\le評價得分\le5 normal(評價得分)=景點數量評價得分?;0≤評價得分≤5
n o r m a l ( 價格 ) = 預算 ? 價格 預算 ; 0 ≤ 價格 ≤ 預算 normal(價格)=\frac{預算-價格}{預算}; 0≤價格\le預算 normal(價格)=預算預算?價格?;0≤價格≤預算
n o r m a l ( 路程長度 ) = 最大長度 ? 路程長度 最大路程 ; 0 ≤ 路程長度 ≤ 最大長度 normal(路程長度)=\frac{最大長度-路程長度}{最大路程}; 0\le路程長度\le最大長度 normal(路程長度)=最大路程最大長度?路程長度?;0≤路程長度≤最大長度 -
輸入:
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 i j = τ i j α η i j β Σ z τ i z α η i z β P_{ij}=\frac{\tau^\alpha_{ij}\eta^\beta_{ij}}{\Sigma_{z}\tau^\alpha_{iz}\eta^\beta_{iz}} Pij?=Σz?τizα?ηizβ?τijα?ηijβ??
其中,z是所有剩余的可選擇的節點, τ i j \tau_{ij} τij?為第 i i i個節點到第 j j j個節點的路徑上的信息素, η i j \eta_{ij} ηij?為第 i i i個節點到第 j j j個節點的“能見度”(路程的倒數), α 和 β \alpha和\beta α和β分別為信息素和“能見度”的重要系數;
α \alpha α和 β \beta β影響蟻群的策略,需要一個適當的比例;
- alpha=0時,無視 flomone,螞蟻完全根據能見度(上一次路線得分)做判斷,容易陷入局部最優解;
- beta=0時,無視上次路線得分,螞蟻完全根據flomone做判斷,收斂速度快,但很難達到最優解;
公式解釋: 從當前節點 i i i到節點 j j j的概率為這兩個節點間的信息素與能見度的乘積,占當前節點到所有可選擇節點的比例。
- 信息素的更新由下面的公式決定:
τ i j ′ = ρ τ i j + Δ τ \tau_{ij}'=\rho\tau_{ij}+\Delta\tau τij′?=ρτij?+Δτ
其中, ρ \rho ρ為信息素的衰減系數, Δ τ \Delta\tau Δτ為一輪迭代后螞蟻帶來的信息素變化。
Δ τ = Q L \Delta\tau=\frac{Q}{L} Δτ=LQ?
Q Q Q為一個常量,可取1; L L L為這一只螞蟻選擇的路線的路程;每一只螞蟻都會帶來信息素的變化,則 Δ τ \Delta\tau Δτ應是所有變化的總和。
3.1.4 蟻群算法在本例中的應用
- 初始信息素濃度都為1;
- 由于本問題不是求解最短路徑,而是有評分作為指標找出最優的路線,所以能見度定義為 η = 0.4 ? n o r m a l ( 評價得分 ) + 0.4 ? n o r m a l ( 價格 ) + 0.2 ? n o r m a l ( 路程長度 ) \eta=0.4 * normal(評價得分) + 0.4 * normal(價格)+0.2 * normal(路程長度) η=0.4?normal(評價得分)+0.4?normal(價格)+0.2?normal(路程長度);
- 將信息素的變化量也相應改為 Δ τ = η Q \Delta\tau=\eta Q Δτ=η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++」遺傳算法求解最佳路徑問題——“一日游”行程規劃程序
浙公網安備 33010602011771號