用遗传算法解决TSP问题

大小: 877KB

文件类型: .rar

金币: 1

下载: 0 次

发布日期: 2021-05-13
语言: 其他
标签: 遗传算法 TSP问题

高速下载

资源简介

本压缩文档包含三个文件：用遗传算法解决TSP问题可执行源代码，word文档报告，实验测试数据

资源截图

小图大图

代码片段和文件信息

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
using namespace std;
typedef long long LL;
const int maxn = 1e2 + 7;
const int INF = 0x7fffffff;
const double PI = acos（-1）;
struct Point { //点类
    string name;
    double x y;
    int i; //编号
};
vector p;
double d[maxn][maxn]; //距离矩阵
int n;
double sum = 0; //当前最短路径长度

double dist（Point a Point b） { //计算两点距离
    return sqrt（（a.x - b.x） * （a.x - b.x） + （a.y - b.y） * （a.y - b.y））;
}

double get_sum（vector a） { //返回路径长度
    double sum = 0;
    for （int i = 1; i < a.size（）; i++） {
        sum += d[a[i].i][a[i - 1].i];
    }
    sum += d[a[0].i][a[a.size（）-1].i];
    return sum;
}

void init（） {                    //初始化
    srand（（unsigned）time（NULL））; //设置随机数种子
    cin >> n;
    p.clear（）;
    for （int i = 0; i < n; i++） {
        Point t;
        cin >> t.name >> t.x >> t.y;
        t.i = i;
        p.push_back（t）;
    }
    for （int i = 0; i < n; i++） {
        for （int j = i + 1; j < n; j++） {
            d[i][j] = d[j][i] = dist（p[i] p[j]）;
        }
    }
    sum = get_sum（p）;
}

void show（） { //显示当前结果
    cout << “路径长度: “ << sum << endl;
    cout << “路径:“;
    for （int i = 0; i < n; i++）
        cout << ‘ ‘ << p[i].name;
    puts（““）;
}

int w = 100;                  //限定种群只能活100个个体
vector >group;//种群，也就是染色体列表

void Improve_Circle（） { //改良圈法得到初始序列
    vector cur = p;
    for （int t = 0; t < w; t++） {     //重复50次
        for （int i = 0; i < n; i++） { //构造随机顺序
            int j = rand（） % n;
            swap（cur[i] cur[j]）;
        }
        int flag = 1;
        while （flag） {
            flag = 0;
            //不断选取uv子串，尝试倒置uv子串的顺序后解是否更优，如果更优则变更
            for （int u = 1; u < n - 2; u++） {
                for （int v = u + 1; v < n - 1; v++） {
                    if （d[cur[u].i][cur[v + 1].i] + d[cur[u - 1].i][cur[v].i] <
                        d[cur[u].i][cur[u - 1].i] + d[cur[v].i][cur[v + 1].i]） {
                        for （int k = u; k <= （u + v） / 2; k++） {
                            swap（cur[k] cur[v - （k - u）]）;
                            flag = 1;
                        }
                    }
                }
            }
        }
        group.push_back（cur）;
        double cur_sum = get_sum（cur）;
        if （cur_sum < sum） {
            sum = cur_sum;
            p = cur;
        }
    }
}

vector get_randPerm（int n） { //返回一个随机序列
    vector c;
    for （int i = 0; i < n; i++） {
        c.push_back（i）;
    }
    for （int i = 0; i < n; i++） {
        swap（c[i] c[rand（） % n]）;
    }
    return c;
}

//排序时用到的比较函数
bool cmp（vector a vector b） { return get_sum（a） < get_sum（b）; }

int dai = 200; //一共进行200代的进化选择
int c[maxn];
dou

属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     512707  2018-06-30 18:41  15计2-2015551239-王维-用遗传算法解TSP问题\15计2-2015551239-王维-遗传算法解TSP问题.docx

     文件       6457  2018-06-30 17:00  15计2-2015551239-王维-用遗传算法解TSP问题\GA.cpp

     文件    2091626  2018-06-30 17:39  15计2-2015551239-王维-用遗传算法解TSP问题\GA.exe

     文件        266  2018-06-30 17:04  15计2-2015551239-王维-用遗传算法解TSP问题\in.txt

     目录          0  2018-07-01 19:05  15计2-2015551239-王维-用遗传算法解TSP问题

----------- ---------  ---------- -----  ----

              2611056                    5

共有条评论

用遗传算法解决TSP问题

资源简介

资源截图

代码片段和文件信息

评论

相关资源