「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 遺傳算法

遺傳算法（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;
}

posted @ 2023-04-01 16:48 是陸柒閱讀(245) 評論(0) 收藏舉報來源

刷新頁面返回頂部