BeWithYou

胡搞的技术博客

  1. 首页
  2. 数据结构/实用算法/知识
  3. 遗传算法求解TSP问题

遗传算法求解TSP问题


大学时候人工智能课的题目,偶尔翻到了,重新整理一下记下来。


一、TSP问题

TSP问题就是经常听到的旅行商问题(Travelling Salesman Problem),呵呵P本身就是“问题”的缩写。假设有个人要拜访n个城市,限制每个城市只能去一次,最后回到出发的城市。怎样求出总路程最短的路径?

他已被证明为一个NP完全问题。


二、遗传算法

遗传算法从生物遗传学中的自然选择机制中发展而来,是一种概率搜索算法。遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定;具有内在的隐并行性和更好的全局寻优能力;采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则。遗传算法的这些性质,已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。

求解TSP问题,我们一般使用在搜索过程中自动获取和积累有关搜索空间的知识并自适应的控制搜索过程从而得到最优解的通用搜索方法。对于中小规模的TSP问题,遗传算法可以求得最优解,对于大规模的TSP问题,则可以求接触近似最优解。

遗传算法的基本运算过程如下:

a)初始化:设置进化代数计数器t=0,设置最大进化代数T,随机生成M个个体作为初始群体P(0)

b)个体评价:计算群体P(t)中各个个体的适应度。

c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。

d)交叉运算:将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。

e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。

f)终止条件判断:若t=T,则以进化过程中所得到的具有最大适应度个体作为最优解输出,终止计算。

而在求解问题的实际过程中,可以针对所求问题的具体情况,合理的将以上步骤重新搭配。


三、遗传算法应用于求解TSP问题

注意,同标题一样这里是“求解”,而不是解决。遗传算法应用于TSP问题,只能大概率的求解出最优解或近似最优解,而不能保证解答出最完美的答案。通过模拟生物进化,这样一种不确定性的求解方法,确实是很具有美感的啊!

为了使流程更加清晰,下面附上一张遗传算法求解TSP的图。

blob.png

其中的几个概念:

地图信息:就是一些点和其位置。

算法参数包括:种群大小,精英保留率,杂交率,变异率,最大代数,停止参数。

个体:访问完所有城市的一种路径。

种群:若干个个体组成的群体。

距离:个体所表示的访问路径的总长度。

适应度:种群里所有个体的最大距离-当前个体的距离。这里适应度越大表示越好。

总适应度:种群里每个个体的适应度之和。

杂交率、变异率:杂交和变异的概率。

杂交:把几个个体的信息进行一定规则的交换。

变异:把个体的信息在个体内部按照一定规则进行略微的变化。


其中的关键算法:

1、初始化个体

即随机排列点,染色体就是排列的点序列。(比如01背包就是0和1的序列)

this.get_random_path = function (city_num) {
    this.path = [];
    var tmp = [];
    for (var i = 0; i < city_num; i++) {
        tmp.push(i);
    }
    var index;
    for (var i = city_num - 1; i >= 0; i--) {
        index = Math.floor(Math.random() * tmp.length);
        this.path.push(tmp[index]);
        tmp.splice(index, 1);
    }
};

2、计算个体总路径长度

即连续两点(另加头尾)求距离和。

this.get_total_length = function (route) {
    var total_length = 0;
    for (var i = 0; i < route.length - 1; i++) {
        total_length += this.get_distance(this.city_position[route[i]], this.city_position[route[i + 1]]);
    }
    total_length += this.get_distance(this.city_position[route[route.length - 1]], this.city_position[route[0]]);
    return total_length;
};

3、轮盘赌选择父代

每次繁衍下一代的时候,先从父代中根据保留率选择排名前几位的精英直接放入下一代。之后需要选取3个父代个体进行杂交。如何选取这3个父代个体呢?直接随机不太好,又不能直接选择排名前几位的。此时就用到轮盘赌算法。

其实也挺简单,个体的适应度越大越有可能被选中。

this.wheel_select = function () {
    var slice = Math.random() * this.total_fitness;
    var total = 0.0;
    var result = 0;
    for (var i = 0; i < this.defines.UNIT_NUM; i++) {
        total += this.group[i].fitness;
        if (total > slice) {
            result = i;
            break;
        }
    }
    return result;
};

slice根据种群的总适应度随机出一个了门槛,个体适应度越高越有机会被选中。由于total不断累加,最后总有个体会被选中。

4、三交换启发交叉杂交

选用3个父代进行杂交!不是两个父代哦。当然首先还是要根据杂交率决定是否需要杂交。

先从选中的第一个父代个体中随机选择一个节点,下标记做index,内容记做ps。然后把三个父亲的第一个点都调整为ps。比如三个父亲本来为123,132,231,选中了2号城市。则依次调整为:231,211,231。然后子代第一个点设为ps。

之后从index=1开始,每次从三个父代中取index点,选择到子代index-1处距离最小的点,放进到子代里,再调整到相应位置。最终完成杂交。

this.hybridization = function (p1, p2, p3, c) {
    //随即继承一个父亲
    switch (Math.floor(Math.random() * 3)) {
        case 0:
            c.path = p1.path.clone();
            break;
        case 1:
            c.path = p2.path.clone();
            break;
        case 2:
            c.path = p3.path.clone();
            break;
    }
    //根据杂交率决定是否杂交
    if ((Math.random() > this.defines.HYBRIDIZATION_RATE)) {
        return;
    }
    //清空子代基因
    c.path = [];
    var index = Math.floor(Math.random() * (this.city_num));//在[0,length-1]中选择一个位置
    //把三个父亲的第一个点调整成为p1.path[index]
    var s = p1.path[index];
    var pt1 = p1.path.slice(index, this.city_num + 1).concat(p1.path.slice(0, index));
    index = p2.path.indexOf(s);
    var pt2 = p2.path.slice(index, this.city_num + 1).concat(p2.path.slice(0, index));
    index = p3.path.indexOf(s);
    var pt3 = p3.path.slice(index, this.city_num + 1).concat(p3.path.slice(0, index));
    c.path.push(s);
    for (index = 1; index < this.city_num; index++) {//每次取index-1到index距离最小的点,放进去子代,再调整到相应位置
        var l1 = this.map.get_distance(this.map.city_position[s], this.map.city_position[pt1[index]]);
        var l2 = this.map.get_distance(this.map.city_position[s], this.map.city_position[pt2[index]]);
        var l3 = this.map.get_distance(this.map.city_position[s], this.map.city_position[pt3[index]]);
        if (l1 <= l2 && l1 <= l3) {//p1
            c.path.push(pt1[index]);
            s = pt1[index];
        } else if (l2 <= l1 && l2 <= l3) {//p2
            c.path.push(pt2[index]);
            s = pt2[index];
        } else if (l3 <= l1 && l3 <= l2) {//p3
            c.path.push(pt3[index]);
            s = pt3[index];
        }
        var tmp = pt1.indexOf(s);
        pt1 = pt1.slice(0, index).concat(pt1.slice(tmp, this.city_num)).concat(pt1.slice(index, tmp));
        tmp = pt2.indexOf(s);
        pt2 = pt2.slice(0, index).concat(pt2.slice(tmp, this.city_num)).concat(pt2.slice(index, tmp));
        tmp = pt3.indexOf(s);
        pt3 = pt3.slice(0, index).concat(pt3.slice(tmp, this.city_num)).concat(pt3.slice(index, tmp));
    }
};

这里的path.clone(),是事先为Array添加了clone方法,原生js中没有这个东西。

5、变异

就是很简单的交换两个点。这里不允许同一个位置自己交换自己,因为都已经有变异率决定是否需要变异了,在搞一个概率性不变异就没什么意思了。不过实现的方式太糙了。。先这样用吧。

this.variation = function (unit) {
    //根据突变率决定是否要变异
    if (Math.random() > this.defines.VARIATION_RATE) {
        return;
    }
    var position1 = Math.floor(Math.random() * (unit.path.length));//在[0,length-1]中选择一个位置
    var position2;
    do {
        position2 = Math.floor(Math.random() * (unit.path.length));//在[0,length-1]中选择一个位置
    } while (position2 == position1);
    //交换他们的位置
    unit.path.swap(position1, position2);
};

6、判断停止繁衍

用连续适应度判别。每次更新下一代后,判断子代适应度是否不大于父代。累计不大于父代的次数达到设定值的时候(也就是我们说的一代不如一代),就可以停止繁衍了。此时输出结果,座位近似最优解。


四、界面的实现方式

看到上面的Js代码,很容易的就想到会用canvas来画了。具体就不多说了。


五、一些数据结论性的东西

其实没什么意义,不过东西做出来总得有个结论吧。我们来找一找合适的参数设定,可以多快好省的求解问题。

一个测试用例:50个点以半径200排列成为一个圆。首先使用自带的测试用例进行实际测试。点击载入测试用例按钮,画布上显示出50个城市位置,如图。

blob.png

保持默认的参数不变,即种群大小50,精英保留率20%,杂交率85%,变异率10%,最大代数无限制,停止参数5代,以及默认的图像显示效果。点击开始按钮,开始以0.5秒一代的速度演算。演算中途截取第2代的效果如图。

blob.png

为了加快演示速度,将滑动条拖到最快的位置,以1ms每代的速度繁衍。最终在131代停止繁衍,最终效果如图。

blob.png

经过多次测试,此测试用例最终的最优解为1255.81,近似于圆的周长2*200*3.14=1256。并且路径即为绕园一周。但是每次测试时停止的代数相差较大。有30代以内的,也有大于1000代才产生最终结果的。

再给几个测试用图:

blob.png

呵呵请原谅博主的恶趣味。

由图可知,简单图形以及边界轮廓较为清晰的情况下可以直接由肉眼判断系统给出的解决方案是否符合最有情况,本系统最终可以实现近似最优解的求解,准确度较为精准。

还有一个数据,修改算法参数得到的最终效果。在Ueditor里不知道表格怎么居中,算了就这样吧。


种群大小

精英保留率

杂交率

变异率

停止参数

繁衍代数

最短路径

50

20%

85%

10%

5

80

1255.81

10

20%

85%

10%

5

76

2149.71

50

1%

85%

10%

5

1880

1255.81

50

20%

10%

10%

5

874

1255.81

50

20%

85%

1%

5

12

1305.84

50

20%

85

10

2

4

2840.85


由表中的数据直观的经验可以粗略的得出结论:

1)种群大小过小时由于个体数量不足无法产生足够不同的解决方案,从而导致无法求出令人满意的近似最优解。

2)父代精英保留率过低可能可以产生合理的近似最优解,但是需要繁衍的代数会增加。

3)杂交率过低也会耗费更多的繁衍次数产生需要的结果。

4)变异率过低降低了优化个体产生的几率,可能产生不了满意的近似最优解。

5)停止参数过低对繁衍代数影响非常巨大,过低时会达不到合理结果就停止繁衍,过高时导致太长时间无法停止。


最后附上DEMO的地址:

遗传算法求解TSP问题(H5实现)


回到顶部