BuringStraw

BuringStraw

首頁封存

遺傳算法實現旅行商問題

#数据科学34
AI 翻譯
這篇文章透過AI由簡體中文翻譯成繁體中文。查看原文
AI 生成的摘要
標題：遺傳算法實現旅行商問題 日期：2022-05-16 12:29:00 標籤：數據科學 本文介紹了使用遺傳算法解決旅行商問題的具體實現。旅行商問題要求在給定城市及其間距的情況下，找到一條最短路徑，使旅行商能夠訪問每個城市一次並返回起始城市。 首先，為每個城市設定坐標以計算距離，並可使用Floyd算法獲得最短路徑。文章中定義了一些全局常量和變量，包括種群大小、全局最優解等。接著，提供了隨機浮點數生成和計算兩點距離的工具函數。 主要過程中，通過隨機生成染色體、選擇優秀個體、交叉操作等步驟來進行遺傳算法的實現。交叉操作使用順序交叉方法，從兩個個體中隨機選取基因片段進行組合。 完整代碼和具體實現細節也在文中提供。

我們選擇遺傳算法的經典案例 —— 旅行商問題來介紹遺傳算法的具體實現。

旅行商問題#

給定一系列城市和每對城市之間的距離，求解訪問每一座城市一次並回到起始城市的最短回路。

我們將給每個城市設定一個坐標，以此來求得每對城市之間的距離。對於圖上問題，可使用 Floyd 算法對圖進行處理，以獲得每對城市之間的最短路。

全局常量、變量定義#

const int SIZE = 1000, CNT = 1000;//種群大小和最大代數
using Pos = pair<double, double>;//坐標類型
using Rst = vector<int>;//染色體類型
vector<Pos> a;//城市坐標數組
double ans = 1e9;//全局最優解，初始化為一個不可能達到的大的長度
Rst ans_rst;//該解對應的染色體
double notans = 1e9;//當前種群最優解，（所以不是答案）
double geneSum = 0;//當前種群的參與二元錦標賽的所有解的和
int geneCnt = 0;//當前種群參與二元錦標賽的個體數量，好像不會變
//以上兩行用來求種群平均解，用來觀察種群變化

工具函數#

//取隨機浮點數，0~1
double randf() {
    return static_cast<float>(rand()) / static_cast<float>(RAND_MAX);
}
//兩點距離
double getDis(Pos p1, Pos p2) {
    return sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2));
}

主要過程#

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        double tx, ty;
        scanf("%lf%lf", &tx, &ty);
        a.push_back(make_pair(tx, ty));
    }
    //以上為數據輸入部分
    //整個種群
    vector<Rst> pool; 
    //生成隨機染色體
    for (int i = 1; i <= SIZE; ++i)
        pool.push_back(randGene(n));
    //進行CNT代繁衍
    for (int i = 1; i <= CNT; ++i) {
        //初始化本輪統計數據
        notans = 1e9;
        geneSum = 0;
        geneCnt = 0;
        printf("%d ", i);
        //適應度數組
        vector<double> score;
        //新的種群
        vector<Rst> new_pool;
        for (int i = 1; i <= CNT / 2; ++i) {
            //選擇兩個親代
            auto win1 = choose(pool);
            auto win2 = choose(pool);
            //20%的概率進行交叉
            if (randf() < 0.2) {
                auto children = oxCross(win1, win2);
                win1 = children.first;
                win2 = children.second;
            }
            //嘗試變異，1%的概率變異
            bianYi(win1);
            bianYi(win2);
            //插入新的種群
            new_pool.push_back(win1);
            new_pool.push_back(win2);
        }
        //輸出本輪結果
        printf("%lf %lf %lf\n", ans, notans, geneSum / geneCnt);
        //種群改變
        pool = new_pool;
    }
    //輸出最優解的染色體
    for (int v : ans_rst)
        printf("%d ", v);
    return 0;
}

基因編碼與產生#

我們以旅行商走過的順序作為基因的編碼，染色體是長度為城市數量的 10 進制序列。

//隨機生成染色體
Rst randGene(int n) {
    Rst ret;
    unordered_map<int, bool> mp;
    for (int i = 1; i <= n; ++i) {
        int newr = rand() % n;
        while (mp[newr])
            newr = rand() % n;
        ret.push_back(newr);
        mp[newr] = true;
    }
return ret;
}

適應度評價#

取總路程的倒數作為適應度。該方法產生的適應度總和不為 1.

//走的總路程
double getValue(Rst &g) {
    int len = g.size();
    double s = 0;
    for (int i = 1; i < len; ++i)
        s += getDis(a[g[i - 1]], a[g[i]]);
    s += getDis(a[g[0]], a[g[len - 1]]);
    if (s < ans) {
        ans = s;
        ans_rst = g;
    }
    if (s < notans)
        notans = s;
    geneSum += s;
    geneCnt++;
    return s;
}

//適應度
double getShiYingDu(Rst &g) { return 1.0 / getValue(g); }

選擇#

我們採用二元錦標賽的方式進行選擇，即每次隨機抽出兩個個體，保留適應度更高的。相應地，選擇多個個體進行比較的方法即為 n 元錦標賽。

//選擇，二元錦標賽
Rst &choose(vector<Rst> &pool) {
    int len = pool.size();
    int i = rand() % len;
    int j = rand() % len;
    int big = getShiYingDu(pool[i]) > getShiYingDu(pool[j]) ? i : j;
    return pool[big];
}

交叉#

我們使用的交叉方式是一種順序交叉。從個體 2 中隨機選取一段放在個體 1 前面，並將其之後的重複基因去掉。再使用另一個個體中的同一段做同樣的操作。

例如 1 5 4 3 2 和 5 3 2 1 4 隨機選擇第 1 到 3 位得到的子代是 2 1 3 5 4 和 5 4 3 2 1

//順序交叉(Order Crossover)
pair<Rst, Rst> oxCross(Rst &r1, Rst &r2) {
    int len = r1.size();
    int i = rand() % len, j = i + rand() % (len - i);
    Rst s1, s2;
    unordered_map<int, bool> mp1, mp2;
    for (int p = i; p <= j; ++p) {
        s1.push_back(r2[p]);
        mp1[r2[p]] = 1;
        s2.push_back(r1[p]);
        mp2[r1[p]] = 1;
    }
    for (int p = 0; p < len; ++p) {
        if (!mp1[r1[p]]) {
            s1.push_back(r1[p]);
            mp1[r1[p]] = 1;
        }
        if (!mp2[r2[p]]) {
            s2.push_back(r2[p]);
            mp2[r2[p]] = 1;
        }
    }
    return {s1, s2};
}

變異#

一定概率隨機選兩個基因進行交換。

//變異
void bianYi(Rst &r) {
    double rd = randf();
    if (rd < 0.01) {
        int len = r.size();
        int i = rand() % len;
        int j = rand() % len;
        int t = r[i];
        r[i] = r[j];
        r[j] = t;
    }
}

運行測試#

我們隨機生成了一組測試數據，包含 174 個城市坐標。下圖是進行了 1000 次繁衍後的最優解（紅）和種群平均解（綠）。
數據：https://gist.github.com/zhufengning/3a617fc3f3765cd192d42fb27ee374d0

img

完整代碼#

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

const int SIZE = 1000, CNT = 1000;
using Pos = pair<double, double>;
using Rst = vector<int>;

vector<Pos> a;
double ans = 1e9;
double notans = 1e9;
double geneSum = 0;
int geneCnt = 0;
Rst ans_rst;

//取隨機浮點數，0~1
double randf() {
    return static_cast<float>(rand()) / static_cast<float>(RAND_MAX);
}

//隨機生成解
Rst randGene(int n) {
    Rst ret;
    unordered_map<int, bool> mp;
    for (int i = 1; i <= n; ++i) {
        int newr = rand() % n;
        while (mp[newr])
            newr = rand() % n;
        ret.push_back(newr);
        mp[newr] = true;
    }
    return ret;
}

//兩點距離
double getDis(Pos p1, Pos p2) {
    return sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2));
}

//走的總路程
double getValue(Rst &g) {
    int len = g.size();
    double s = 0;
    for (int i = 1; i < len; ++i) {
        s += getDis(a[g[i - 1]], a[g[i]]);
    }
    s += getDis(a[g[0]], a[g[len - 1]]);
    if (s < ans) {
        ans = s;
        ans_rst = g;
    }

    if (s < notans)
        notans = s;

    geneSum += s;
    geneCnt++;
    return s;
}

//適應度
double getShiYingDu(Rst &g) { return 1.0 / getValue(g); }

//選擇，二元錦標賽
Rst &choose(vector<Rst> &pool) {
    int len = pool.size();
    int i = rand() % len;
    int j = rand() % len;
    int big = getShiYingDu(pool[i]) > getShiYingDu(pool[j]) ? i : j;
    return pool[big];
}

//順序交叉(Order Crossover)
pair<Rst, Rst> oxCross(Rst &r1, Rst &r2) {
    int len = r1.size();
    int i = rand() % len, j = i + rand() % (len - i);
    Rst s1, s2;
    unordered_map<int, bool> mp1, mp2;
    for (int p = i; p <= j; ++p) {
        s1.push_back(r2[p]);
        mp1[r2[p]] = 1;
        s2.push_back(r1[p]);
        mp2[r1[p]] = 1;
    }
    for (int p = 0; p < len; ++p) {
        if (!mp1[r1[p]]) {
            s1.push_back(r1[p]);
            mp1[r1[p]] = 1;
        }
        if (!mp2[r2[p]]) {
            s2.push_back(r2[p]);
            mp2[r2[p]] = 1;
        }
    }
    return {s1, s2};
}

//變異
void bianYi(Rst &r) {
    double rd = randf();
    if (rd < 0.01) {
        int len = r.size();
        int i = rand() % len;
        int j = rand() % len;
        int t = r[i];
        r[i] = r[j];
        r[j] = t;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        double tx, ty;
        scanf("%lf%lf", &tx, &ty);
        a.push_back(make_pair(tx, ty));
    }
    //以上為數據輸入部分
    //整個種群
    vector<Rst> pool; 
    //生成隨機染色體
    for (int i = 1; i <= SIZE; ++i)
        pool.push_back(randGene(n));
    //進行CNT代繁衍
    for (int i = 1; i <= CNT; ++i) {
        //初始化本輪統計數據
        notans = 1e9;
        geneSum = 0;
        geneCnt = 0;
        printf("%d ", i);
        //適應度數組
        vector<double> score;
        //新的種群
        vector<Rst> new_pool;
        for (int i = 1; i <= CNT / 2; ++i) {
            //選擇兩個親代
            auto win1 = choose(pool);
            auto win2 = choose(pool);
            //20%的概率進行交叉
            if (randf() < 0.2) {
                auto children = oxCross(win1, win2);
                win1 = children.first;
                win2 = children.second;
            }
            //嘗試變異，1%的概率變異
            bianYi(win1);
            bianYi(win2);
            //插入新的種群
            new_pool.push_back(win1);
            new_pool.push_back(win2);
        }
        //輸出本輪結果
        printf("%lf %lf %lf\n", ans, notans, geneSum / geneCnt);
        //種群改變
        pool = new_pool;
    }
    //輸出最優解的染色體
    for (int v : ans_rst)
        printf("%d ", v);
    return 0;
}
載入中......
此文章數據所有權由區塊鏈加密技術和智能合約保障僅歸創作者所有。