「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 遺傳算法
遺傳算法(Genetic Algorithm,簡稱GA)起源于對生物系統所進行的計算機模擬研究,是一種隨機全局搜索優化方法,它模擬了自然選擇和遺傳中發生的復制、交叉和變異等現象,從任一初始種群出發,通過隨機選擇、交叉和變異操作,產生一群更適合環境的個體,使群體進化到搜索空間中越來越好的區域,這樣一代一代不斷繁衍進化,最后收斂到一群最適應環境的個體(Individual),從而求得問題的優質解[1]。
3.2 構思
3.2.1 核心定義的類
在C++中,內置的數據類型無法很好地滿足我們的特殊需求,雖然STL容器擁有很強大且完備的功能,但是有些信息還是定義為類比較好處理,比如記錄景點信息、路線信息、遺傳信息等。需要定義幾個主要的類:
- scenicSpot類用于記錄一個景點的信息(景點名、開放時間、關閉時間、價格、坐標等);
- Chrom類用于記錄條路線的信息(路線、路線評價、路線價格、路線路程等);
- Evolve類用于記錄種群,并實現種群的進化方法。
3.2.2 常用類和方法
除此之外,還有一些數據類型和功能被反復用到,處理成單獨的類和函數比較方便管理和計算:
- coordinate類,記錄坐標,并實現坐標的計算功能;
- mytime類,記錄時間,只記錄時、分、秒,方便時間的運算;
- selector_sort函數,選擇排序。
- find_vector函數,在vector中查找元素并返回下標。
- vector容器存儲路線節點,方便變化長度,作為輔助作用
3.2.3 遺傳算法的策略
- 精英遺傳,當前一代的最優解之間相互雜交;
- 劣等淘汰,每一代最差的結果被淘汰;
- 優質選擇,淘汰掉本代最差的結果后,從子代中選擇最好的一批結果補充,以保持種群規模;
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 Chrom類
// 染色體
class Chrom
{
private:
vector<scenicSpot> geneorder; // 基因序列,路線
double chromstar; // 路線評價
double chromdistance; // 路線路程
double chromprice; // 路線票價
mytime chromendtime; // 路線游玩時間
double chromscore; // 這條染色體的適應度
public:
Chrom();
Chrom(scenicSpot *gene);
Chrom(vector<scenicSpot> gene);
~Chrom(){};
// 計算參數‘
void calculate();
// 輸出信息
vector<scenicSpot> gene() const { return this->geneorder; }
int size() const { return this->geneorder.size(); }
double score() const { return this->chromscore; } // 返回得分
double star() const { return this->chromstar; } // 返回路線評價
double distance() const { return this->chromdistance; } // 返回路線路程
double price() const { return this->chromprice; } // 返回路線票價
mytime endtime() const { return this->chromendtime; } // 返回路線游玩時間
coordinate end() const { return this->geneorder.back().coord(); } // 返回最后一站的坐標
string route() const; // 輸出路線
// 其他操作
void append(scenicSpot s); // 增加路線長度
vector<scenicSpot> getblock(int start, int end); // 獲取片段
vector<scenicSpot> swapnodeAbarr(); // 交換節點變異
vector<scenicSpot> swapEpisodeAbarr(); // 片段易位變異
vector<scenicSpot> inverseEpisodeAbarr(); // 片段逆序變異
void adjust(double budget, double maxtrip); // 調整(如果超預算,刪除尾部節點,以保證子代的有效性)
Chrom onesideCross(vector<scenicSpot> cross, int start); // 雜交時的一邊變換
double calcscore(double budget, double maxtrip); // 計算線路得分
// 重載算符
friend ostream &operator<<(ostream &out, const Chrom &c);
Chrom &operator=(const Chrom s);
bool operator<(const Chrom s);
bool operator<=(const Chrom s);
bool operator>(const Chrom s);
bool operator>=(const Chrom s);
bool operator!=(const Chrom s);
bool operator==(const Chrom s);
};
4.7 Evolve類
// 遺傳算法
class Evolve
{
private:
vector<Chrom> parents; // 父代
vector<Chrom> children; // 子代
vector<scenicSpot> scenicmap; // 景點地圖(坐標)
vector<vector<double>> distance_map; // 記錄景點間的距離
double maxtrip; // 路線的最大路程
double budget; // 預算
int maxgen; // 最大迭代次數
int populat_scale; // 群體規模
double cross_prob; // 交叉概率
double abarr_prob; // 變異概率
double select_prob; // 選擇概率
int children_scale; // 子代的選取個數
public:
Evolve(int maxgen = 100, int pop_scale = 200, double crossp = 0.8, double abarrp = 0.0125, double slectp = 0.5, string path = "./map.csv");
~Evolve(){};
bool importMap(string path); // 從文件導入景點地圖
bool calcdistMap(); // 計算路徑
void randomParents(); // 隨機生成第一父代
void Cross(); // 雜交
void Aberrant(); // 變異(基因點交換、基因片段倒序、基因增長)
void select(); // 選擇子代插入父代
bool evolveNow(); // 開始演化
};
4.8 main函數
int main()
{
Evolve evolution;
evolution.evolveNow();
return 0;
}
浙公網安備 33010602011771號