【遗传算法求解TSP问题】

ygxdxm

2696人浏览 · 2024-02-23 11:27:51

ygxdxm · 2024-02-23 11:27:51 发布

遗传算法在组合优化中的应用

遗传算法由美国Holland教授最先提出的，其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法，模拟自然界生物的繁殖、交叉、变异现象，每一代经过自然选择会保留相对优秀的个体。算法本身主要依赖遗传算子（选择、交叉和变异）对种群中的个体进行组合，产生新的个体，并按照某种指标筛选个体，不断地重复该过程，直到满足某种收敛指标为止。

在前面的文章中已经提到了遗传算法的几个组成部分。它的理论研究主要包含：

编码格式

编码格式表征了染色体的形式，不同的编码格式对算法的性能有重要的影响。常见的编码格式有：
- 二进制编码
- 格雷码编码，它能够克服二进制编码在连续函数离散化时存在的不足。
- 实数编码，该方法适合于遗传算法中表示范围较大的数使遗传算法更接近问题空间避免了编码和解码的过程。
- 多参数级联编码，即对含有多个变量的个体进行编码，通常可以先分别对每个变量分别进行编码，之后再将它们的编码按照一定的顺序排列起来
- 非数值编码，染色体编码串中的基因值取一个仅有代码含义而无数值含义的符号集。优点是在遗传算法中可以利用所求问题的专门知识及相关算法
适应度函数

适应度函数用来评价个体的适应程度。通常可利用目标函数转化成适应度函数，将目标函数转换成适应度函数一般应遵循两个原则：适应度必须非负；优化过程中目标函数的变化方向应与群体进化过程中适应度函数变化方向一致。针对最大化、最小化问题对目标函数作出不同的变换。

在遗传进化的初期通常会产生一些竞争力极强的超常个体，它们控制了选择过程，影响了算法的全局优化性能。因此在进化初期必须避免某一个个体适应度过大。通过对适应度进行尺度变换改变原适应值的比例关系。常用的尺度变换方法有线性变换法、幂函数变换法和指数变换法。
遗传算子
- 选择算子：选择操作通过适应度选择优质个体而抛弃劣质个体，其目的是把优质个体或解直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。常见的选择方法有：
  - 轮盘赌选择：每个个体按照适应值的占比依概率选择个体。
  - 排序选择：将个体的适应值从高到低排序，依照适应值顺序选取一定数量的个体。
  - 最优个体保存：父代群体中的最优个体直接进入子代群体中。
  - 锦标赛选择：每次选取Ｎ个个体中适应度最高的个体，重复该过程M次。
- 交叉算子：交叉是指对两个父代染色体按某种方式相互交换其部分基因从而形成两个新的个体，它在遗传算法中起核心作用，决定了遗传算法的全局搜索能力。常见的交叉方法有：
  - 单点交叉：在染色体中随机设置一个交叉点，随后在该点相互交换两个配对染色体的基因。
  - 两点交叉：在染色体中随机设置两个交叉点，随后在这两个交叉点相互交换两个配对染色体的基因。
  - 均匀交叉：两个交叉染色体的每一位基因都以相同的概率进行交换，形成两个新个体。
  - 算术交叉：由两个个体的线性组合而产生出新的个体。
- 变异算子：变异是指染色体的某些基因座上的基因值用该基因座的其他等位基因来替换从而形成一个新的染色体，它决定了遗传算法的局部搜索能力，能够维持种群的多样性，可以防止出现早熟现象。常见的变异操作有：
  - 基本位变异，对染色体以变异概率Ｐ随机指定某一位或某几位基因进行变异操作。
  - 均匀变异，分别用符合某一范围内均匀分布的随机数‚以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。
  - 逆转算子，变异算子的一种特殊形式。在染色体上随机选择两个逆转点，然后将逆转点之间的基因逆向排序。
  - 自适应变异算子，与基本位变异操作类似，唯一不同的是变异概率是随种群中个体的多样性程度而自适应调整的。
参数选择：在遗传算法运行过程中，存在着对其性能产生重大影响的一组参数，主要包括染色体长度、群体规模、收敛判据、交叉概率及变异概率。参数选择关系到遗传算法的精度、可靠性和计算时间等诸多因素并且影响到结果的质量和系统性能。
收敛性分析：遗传算法的收敛性通常是指遗传算法所生成的迭代种群收敛到某一稳定状态或其适应值函数的最大或平均值随迭代趋于优化问题的最优值。

遗传算法求解旅行商问题

问题描述

TSP（traveling salesman problem）问题是典型的NP完全问题，可描述为：已知n个城市相互之间的距离，某一旅行商从某个城市出发访问每个城市一次且仅一次，最后回到出发城市，如何安排才使其所走路线最短。该问题可描述为搜索自然子集 $X={1,2,3,...,n}X=\left \{ 1,2,3,...,n \right \}$ (其中每个元素表示城市的编号)的一个排列 $ρ(X)={V1,V2,...,Vn}\rho (X)=\left \{ V_{1},V_{2},...,V_{n} \right \}$ ，使得
$T_{d} =\sum_{i=1}^{n-1}d(V_{i},V_{i+1})+ d(V_{n},V_{1})$
取最小值，其中 $d(V_{i},V_{i+1})$ 表示城市 $V_{i}$ 到城市 $V_{i+1}$ 的距离。现提供14个城市的位置坐标如下。

城市编号	X坐标	Y坐标	城市编号	X坐标	Y坐标
1	16.47	96.10	8	17.20	96.29
2	16.47	94.44	9	16.30	97.38
3	20.09	92.54	10	14.05	98.12
4	22.39	93.37	11	16.53	97.38
5	25.23	97.24	12	21.52	95.59
6	22.00	96.05	13	19.41	97.13
7	20.47	97.02	14	20.09	92.55

遗传算法实现

（1）编码

采用整数排列编码，对于n个城市的TSP问题，将染色体分为n段，每一段代表城市的编号，旅行商将按照这个排列顺序访问城市。如对于5个城市的TSP问题，|2|5|3|1|4|就符合规则。

（2）种群初始化

该步骤涉及到种群规模的设定，一般依照经验选取。随机生成多个初始解。

（3）适应度函数

城市的之间的距离非负，此处为最小化问题，适应度函数可取目标函数的倒数。

（4）选择操作

选择操作依照适应值大小选择个体，适应值高的个体可以直接进入种群或者进行交叉产生子代。后文程序将对前面提到的选择方法进行测试。

（5）交叉操作

采用部分映射杂交，具体步骤为：首先随机选择两个交叉点，然后对两个交叉点中间的基因全部交换。可逐个交换基因，假设存在两个染色体A，B,交换时出现A(i) = a,A(j) = b(i≠j)，B(i)=b，现需要交换第i个交叉点的基因。设交换后A变为A1,由于染色体A1的i，j位置都为b，发生了冲突，需要替换A1(j)=A(i)=a。以10个城市的交叉过程为例：

①假设两个交叉点的位置分别为4和7，部分映射交叉后，两个染色体变为下图，交换期间出现了重复基因
在这里插入图片描述
②对于冲突的基因采用前面提到的方式处理，结果为

（6）变异操作

基本位变异：在染色体上随机选取两个变异点，然后交换两个位置的基因即可。仍以10个城市的TSP为例，假设两个变异点分别为4和7，则变异过程如下：
逆转算子：为了提高GA的局部搜索能力，引入逆转算子，具体操作为在染色体上随机选取两个位置，然后逆向排序两个位置的基因即可，需要注意的是经过逆转后的染色体，只有适应度提高的才保存，否则逆转无效。仍以10个城市的TSP为例，假设两个变异点分别为4和7，则进化逆转过程如下：

主要代码实现及运行结果

GATSP类

GATSP类中设计了两个结构体，用于保存城市坐标和个体信息。通过读取14个城市的坐标信息，计算出两两的距离。私有数据成员保存了遗传算法需要的常用参数，如种群规模、染色体大小、交叉概率、变异概率。在初始化种群后，通过遗传算子对种群不断更迭，最终计算出当前参数配置下的最优解，当然这里的最优解不一定是真实的最优解。

#ifndef GATSP_H
#define GATSP_H

#include <iostream>
#include <string>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <random>
#include <ctime>

using namespace std;
using uint = unsigned int;
const double eps = 1e-20;

struct CityPos{
    double x; // x坐标
    double y; // y坐标
};

struct Individual{
    // 当前个体的染色体
    vector<uint> chrom;
    // 个体的适应值
    double fitness;
};

class GATSP
{
private:
    // 私有成员数据
    vector<vector<double>> distance_info;
    // 迭代次数
    uint maxgen;
    // 种群规模
    uint sizepop;
    // 交叉概率
    double pcross;
    // 变异概率
    double pmutation;
    // 染色体长度，这里表示城市的个数
    uint lenchrom;
    // 代沟率
    double ggap;

    // 子种群数量
    uint selNum;

    // 子种群
    vector<Individual> select_individuals;

    // 目标函数的最优值
    double best_obj_val;
    // 种群
    vector<Individual> individuals;

    // 辅助函数

    vector<CityPos> readCityPosFromFile(string filename);

    double cal_distance(const CityPos& c1, const CityPos& c2){
        return sqrt(pow(c1.x - c2.x, 2) + pow(c1.y - c2.y,2));
    }

    double sumFitness();

public:
    GATSP();
    GATSP(uint maxgen_, uint sizepop_, double pcross_, double pmutation_, uint lenchrom_, double ggap_);

    // 初始化城市的距离信息
    void initDistanceInfo(string filename);

    // 初始化种群
    void initIndividuals();

    // 计算目标函数值
    double objectFun(const vector<uint>& chrom,const uint lenChrom);

    // 个体的适应值为目标函数值的倒数，直接计算
    double calFitnessVal(const vector<uint>& chrom,const uint lenChrom){return 1.0/objectFun(chrom,lenChrom);}

    // 选择优良个体的函数
    void select();

    // 交叉
    void cross();

    void intcross(Individual& p1, Individual& p2);

    void resolve_conflicts(vector<uint>& chrom, vector<uint>& chrom_pre, uint pos, uint val);

    // 变异
    void mutate();

    // 引入逆转算子
    void reverse_chrom();

    // 将子种群重插入到父种群
    void reins();

    // 遗传算法主流程
    void ga();

    // 输出最优结果
    void output_result();
};
#endif // GATSP_H

初始化种群

在C++中可以借助random_shuffle方法对一个基本的序列，多次重新洗牌，生成多个个体。

void GATSP::initIndividuals()
{
    // 创建一个基本的染色体
    vector<uint> chrom_example;
    for(uint i = 1; i <= lenchrom; ++i)
    {
        chrom_example.push_back(i);
    }


    Individual individual;
    // 创建个体，并利用函数的重新洗牌功能让基本染色体不断变化
    for(uint i = 0; i < sizepop; ++i)
    {
        // 注意这里不能传常迭代器
        // 利用基本的染色体，结合random_shuffle函数的功能，产生随机个体
        random_shuffle(chrom_example.begin(),chrom_example.end());
        individual.chrom = chrom_example;
        individual.fitness = calFitnessVal(chrom_example,lenchrom);

        // 添加个体
        individuals.push_back(individual);
    }
}

适应值的计算

前面提到，这里的目标函数值实际就是路径的距离，它是非负的。由于求路径最小，这里适应度函数就去目标函数的倒数。具体实现如下：

目标函数值计算：

// 个体目标函数值计算
double GATSP::objectFun(const vector<uint>& chrom, const uint lenChrom)
{
    double objVal = 0.0;
    for(uint i = 0; i < lenChrom - 1; ++i)
    {
        // curIndex取值范围为[1,lenChrom]
        uint preIndex = chrom.at(i);
        uint nextIndex = chrom.at(i+1);
        // 注意染色体编号从1开始编码，而存储距离信息时从下标0开始存储的
        objVal += distance_info.at(preIndex - 1).at(nextIndex - 1);
    }

    // 终点到起点的距离
    uint startIndex = chrom.at(0);
    uint lastIndex = chrom.at(lenChrom - 1);
    return objVal + distance_info.at(lastIndex-1).at(startIndex - 1);
}

个体适应值计算：

// 个体的适应值为目标函数值的倒数，直接计算
double calFitnessVal(const vector<uint>& chrom,const uint lenChrom)
{return 1.0/objectFun(chrom,lenChrom);}

选择操作

这一步是从父种群中选取一定数量组成子种群。这里对排序选择、轮盘赌、最优个体保存都进行了实现。

void GATSP::select()
{
    // 选择方法一：排序选择,按适应值从大到小排序
//    sort(individuals.begin(), individuals.end(), [](const Individual& p1, const Individual& p2){
//        return p1.fitness > p2.fitness;
//    });

//    for(uint i = 0; i < selNum; ++i)
//    {
//        select_individuals.at(i) = individuals.at(i);
//    }


    // 选择方法二：只用轮盘赌，测试效果相对较好

    // 使用系统时间作为种子
//    std::time_t now = std::time(nullptr);
//    std::tm* cur_tm = std::localtime(&now);
//    int seed = cur_tm->tm_hour * 3600 + cur_tm->tm_min * 60 + cur_tm->tm_sec;

//    // 默认引擎
//    std::default_random_engine dre(seed);

//    // 默认生成0到1之间的数
//    std::uniform_real_distribution<double> ure;

//    // 生成[0,sizepop-1]的数，选择种群的一员
//    std::uniform_int_distribution<uint> ure_pos(0,sizepop-1);

//    // 采用轮盘赌的方法，从父代中选取selNum个个体出来
//    double avgFitness = sumFitness() / sizepop;
//    for(uint i = 0; i < selNum; ++i)
//    {
//        // 产生一个0~1的随机数
//        double pickPro = ure(dre);
//        while(pickPro < eps)
//        {
//            pickPro = ure(dre);
//        }
//        pickPro *= avgFitness;

//        uint pickPos = ure_pos(dre);

//        while(individuals.at(pickPos).fitness < pickPro)
//        {
//            pickPos = ure_pos(dre);
//        }
//        select_individuals.at(i) = individuals.at(pickPos);
//    }

    // 选择方法三：最优个体保存 + 轮盘赌
    // 使用系统时间作为种子
    std::time_t now = std::time(nullptr);
    std::tm* cur_tm = std::localtime(&now);
    int seed = cur_tm->tm_hour * 3600 + cur_tm->tm_min * 60 + cur_tm->tm_sec;

    // 默认引擎
    std::default_random_engine dre(seed);

    // 默认生成0到1之间的数
    std::uniform_real_distribution<double> ure;

    // 生成[0,sizepop-1]的数，选择种群的一员
    std::uniform_int_distribution<uint> ure_pos(0,sizepop-1);

    // 找出最优个体
    vector<Individual>::const_iterator it = max_element(individuals.cbegin(), individuals.cend(),
               [](const Individual& p1, const Individual& p2){
                  return p1.fitness < p2.fitness;
    });

    // 第一个位置默认保存最优个体
    select_individuals.at(0) = (*it);

    // 采用轮盘赌的方法，从父代中选取selNum个个体出来
    double avgFitness = sumFitness() / sizepop;
    for(uint i = 1; i < selNum; ++i)
    {
        // 产生一个0~1的随机数
        double pickPro = ure(dre);
        while(pickPro < eps)
        {
            pickPro = ure(dre);
        }
        pickPro *= avgFitness;

        uint pickPos = ure_pos(dre);

        while(individuals.at(pickPos).fitness < pickPro)
        {
            pickPos = ure_pos(dre);
        }
        select_individuals.at(i) = individuals.at(pickPos);
    }
}

交叉操作

选出来的子种群将作为交叉父代的候选者，利用部分映射杂交的方法完成交叉操作。

cross函数：交叉操作的主入口

void GATSP::cross()
{
    // 使用系统时间作为种子
    std::time_t now = std::time(nullptr);
    std::tm* cur_tm = std::localtime(&now);
    int seed = cur_tm->tm_hour * 3600 + cur_tm->tm_min * 60 + cur_tm->tm_sec;

    // 默认引擎
    std::default_random_engine dre(seed);

    // 默认生成0到1之间的数，用于和交叉概率作比较
    std::uniform_real_distribution<double> ure;

    uint cross_end = selNum - selNum % 2;

    // 1.从子种群中选择两个要交叉的个体,直接选择 i和i+1作为交叉的父代
    for(uint i = 0; i < cross_end; i += 2)
    {
        double pickPro = ure(dre);

        // 2.生成(0~1)随机数，判断是否小于交叉概率，小于则交叉
        if(pickPro > pcross)
        {
            continue;
        }
        // 两个父代进行交叉映射，交叉后的父代将被覆盖
        intcross(select_individuals.at(i), select_individuals.at(i+1));
    }
}

intcross函数：完成实际的交叉操作，主要是随机选择两个不同的交叉点，随后交换该区间的基因片段，但需要解决交换后的基因冲突。

void GATSP::intcross(Individual &p1, Individual &p2)
{

    // 使用系统时间作为种子
    std::time_t now = std::time(nullptr);
    std::tm* cur_tm = std::localtime(&now);
    int seed = cur_tm->tm_hour * 3600 + cur_tm->tm_min * 60 + cur_tm->tm_sec;

    // 默认引擎
    std::default_random_engine dre(seed);

    // 生成[0,lenchrom)之间的两个不同的随机整数，作为两个交叉点
    std::uniform_int_distribution<uint> chrom_pos(0,lenchrom-1);

    uint pos1 = chrom_pos(dre);
    uint pos2 = chrom_pos(dre);
    // 确保两个交叉点位置不同
    while(pos1 == pos2)
    {
        pos2 = chrom_pos(dre);
    }

    uint start_pos = (pos1 < pos2)? pos1 : pos2;
    uint end_pos = (pos1 < pos2)? pos2 : pos1;

    // 取出父代的两条染色体
    vector<uint> chrom1 = p1.chrom;
    vector<uint> chrom2 = p2.chrom;

    // 备份最初的染色体
    vector<uint> chrom1_src = chrom1;
    vector<uint> chrom2_src = chrom2;


    // 逐个交换start_pos到end_pos的元素，并解决可能出现的基因冲突
    for(uint i = start_pos; i <= end_pos; ++i)
    {
        // 交叉一次后的染色体变化
        vector<uint> chrom1_pre = chrom1;
        vector<uint> chrom2_pre = chrom2;

        // 使用最初的染色体的值
        uint v1 = chrom1_src.at(i);
        uint v2 = chrom2_src.at(i);

        // 先交换，再解决冲突基因
        chrom1.at(i) = v2;
        chrom2.at(i) = v1;

        // 采用部分映射杂交，同时进行交叉后基因片段的冲突问题（基因不允许重复）
        resolve_conflicts(chrom1, chrom1_pre, i, v2);
        resolve_conflicts(chrom2, chrom2_pre, i, v1);
    }

    // 更新交叉后的染色体和适应值
    p1.chrom = chrom1;
    p1.fitness = calFitnessVal(chrom1, lenchrom);

    p2.chrom = chrom2;
    p2.fitness = calFitnessVal(chrom2, lenchrom);
}

resolve_conflicts函数：用于解决交换后，产生的重复基因冲突。

void GATSP::resolve_conflicts(vector<uint> &chrom, vector<uint> &chrom_pre, uint pos, uint val)
{
    // 查找v1在交换后chrom1中的位置，判断是否可能出现冲突
    vector<uint>::iterator find_val_pos = find(chrom.begin(),chrom.end(),val);

    // 从起点处寻找，该位置一定
    uint find_val_d1 = static_cast<uint>(distance(chrom.begin(),find_val_pos));
    // 说明冲突基因位于第pos个位置前面
    if(find_val_d1 != pos)
    {
        chrom.at(find_val_d1) = chrom_pre.at(pos);
    }
    // 从后面继续查找
    else{
        find_val_pos = find(++find_val_pos, chrom.end(), val);
        // 如果在后面查找到了冲突基因
        if(find_val_pos != chrom.end())
        {
            find_val_d1 = static_cast<uint>(distance(chrom.begin(),find_val_pos));
            chrom.at(find_val_d1) = chrom_pre.at(pos);
        }
    }
}

变异操作

变异过程比较简单，主要是随机产生两个不同的变异点，随后交换这两个位置的元素即可。

void GATSP::mutate()
{
    // 使用系统时间作为种子
    std::time_t now = std::time(nullptr);
    std::tm* cur_tm = std::localtime(&now);
    int seed = cur_tm->tm_hour * 3600 + cur_tm->tm_min * 60 + cur_tm->tm_sec;

    // 默认引擎
    std::default_random_engine dre(seed);

    // 生成0~1的随机数，用于和变异概率比较
    std::uniform_real_distribution<double> urd;

    // 用于生成两个交叉点
    std::uniform_int_distribution<uint> chrom_pos(0,lenchrom-1);

    for(uint i = 0; i < selNum; ++i)
    {
        // 1.随机生成一个0~1的随机数，看是否小于变异概率。小于则变异
        double pickPro = urd(dre);
        if(pickPro > pmutation)
        {
            continue;
        }

        // 2.从[0,lenchrom)随机生成两个不同的数，作为两个变异点
        uint pos1 = chrom_pos(dre);
        uint pos2 = chrom_pos(dre);
        while(pos1 == pos2)
        {
            pos2 = chrom_pos(dre);
        }

        // 交换变异点位置的元素
        uint val1 =  select_individuals.at(i).chrom.at(pos1);
        select_individuals.at(i).chrom.at(pos1) = select_individuals.at(i).chrom.at(pos2);
        select_individuals.at(i).chrom.at(pos2) = val1;
    }
}

逆转变异算子

同样是产生两个不同的变异点，随后逆序两个区间的元素即可。但需要注意的是，只有逆转能够提高个体适应值的，才会保存逆转变异个体。

void GATSP::reverse_chrom()
{

    // 使用系统时间作为种子
    std::time_t now = std::time(nullptr);
    std::tm* cur_tm = std::localtime(&now);
    int seed = cur_tm->tm_hour * 3600 + cur_tm->tm_min * 60 + cur_tm->tm_sec;

    // 默认引擎
    std::default_random_engine dre(seed);

    // 用于生成两个逆转位置
    std::uniform_int_distribution<uint> chrom_pos(0,lenchrom-1);

    for(uint i = 0; i < selNum; ++i)
    {
        vector<uint> r_chrom = select_individuals.at(i).chrom;

        // 1.从[0,lenchrom)随机生成两个不同的数，作为两个变异点
        uint pos1 = chrom_pos(dre);
        uint pos2 = chrom_pos(dre);
        while(pos1 == pos2)
        {
            pos2 = chrom_pos(dre);
        }

        uint start_pos = (pos1 < pos2)? pos1 : pos2;
        uint end_pos = (pos1 < pos2)? pos2 : pos1;

        // 将start_pos和end_pos中的元素逆序
        // vector支持随机访问迭代器,[0,lenchrom-1]取值
        reverse(r_chrom.begin() + static_cast<int>(start_pos),
                r_chrom.begin() + static_cast<int>(end_pos + 1));

        // 检验进化逆序操作后，适应值是否提高
        double r_fitness = calFitnessVal(r_chrom, lenchrom);
        if(select_individuals.at(i).fitness >= r_fitness)
        {
            continue;
        }

        // 进化逆转有提升的染色体，保存
        select_individuals.at(i).chrom = r_chrom;
        select_individuals.at(i).fitness = r_fitness;
    }
}

程序运行结果

主函数：

#include"gatsp.h"
int main()
{
	// 自行填写文件路径
    string filename{"xxx//city_pos_data.dat"};
    // 迭代次数
    unsigned int maxgen = 200;
    // 种群规模
    unsigned int sizepop = 250;
    // 交叉概率
    double pcross = 0.9;
    // 变异概率，如果容易出现早熟，适当调高变异概率
    double pmutation = 0.3;
    // 染色体长度，这里表示城市的个数
    uint lenchrom = 14;
    // 代沟率
    double ggap = 0.9;

    GATSP tsp{maxgen,sizepop,pcross,pmutation,lenchrom,ggap};

    tsp.initDistanceInfo(filename);

    tsp.ga();
    
    return 0;
}

程序某次运行结果如下：

种群大小为250,迭代次数为200的情况下，遗传算法搜索结果为:
最大适应值为:0.0340826
最优路径为:12->7->13->8->11->9->10->1->2->14->3->4->5->6->12
14个城市TSP问题的最短路径搜索结果为:29.3405

通过运行《MATLAB智能算法30个案例分析（第2版）》的示例代码进行比对：

matlab代码输出结果：

最优解:
1—>2—>14—>3—>4—>5—>6—>12—>7—>13—>8—>11—>9—>10—>1
总距离：29.3405

通过对比两者的运行结果可知，当前条件下，最优路径的距离为29.3405，由于出发点可以浮动，而且出发方向可以顺逆变动，实际上最优路径的解是由多个的，但是最短路径的距离是固定的。

参考文献

[1]马永杰,云文霞.遗传算法研究进展[J].计算机应用研究,2012,29(04):1201-1206+1210.

[2]葛继科,邱玉辉,吴春明等.遗传算法研究综述[J].计算机应用研究,2008,(10):2911-2916.

[3]王银年.遗传算法的研究与应用[D].江南大学,2009.

[4]史峰.MATLAB智能算法30个案例分析[M].北京航空航天大学出版社,2011.

乐奇 Rokid 开放社区

更多推荐

TestStar | 接入 AIUI 测试 30 天后，别拿别人的数算自己的账

乐奇 Rokid 开放社区

SQL 必知必会：手把手教你掌握 MySQL 开窗函数的 4 大核心场景（附代码）

乐奇 Rokid 开放社区

用 AIUI 打造「免手出行助手」——一篇能跟着做完的智能体实战教程

乐奇 Rokid 开放社区

所有评论(0)

查看更多评论

ygxdxm

@ygxdxm

已为社区贡献2条内容

【遗传算法求解TSP问题】

ygxdxm

遗传算法在组合优化中的应用

遗传算法求解旅行商问题

问题描述

遗传算法实现

主要代码实现及运行结果

GATSP类

初始化种群

适应值的计算

选择操作

交叉操作

变异操作

逆转变异算子

程序运行结果

参考文献

所有评论(0)

温馨提示：您尚未绑定手机号

ygxdxm