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;//現在の集団に参加する二元トーナメントの個体数、変わらないようです
//上記の2行は集団の平均解を求めるために使用され、集団の変化を観察します

ツール関数#

//ランダムな浮動小数点数を取得、0~1
double randf() {
    return static_cast<float>(rand()) / static_cast<float>(RAND_MAX);
}
//2点間の距離
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) {
            //2つの親を選択
            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); }

選択#

私たちは二元トーナメント方式で選択を行います。つまり、毎回ランダムに 2 つの個体を抽出し、適応度が高い方を保持します。対応して、複数の個体を比較する方法は 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};
}

変異#

一定の確率でランダムに 2 つの遺伝子を選択して交換します。

//変異
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;
}

//2点間の距離
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) {
            //2つの親を選択
            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;
}
読み込み中...
文章は、創作者によって署名され、ブロックチェーンに安全に保存されています。