elainefairy / ga-based-tsp Goto Github PK

算法描述

swig -c++ -python traveller.i
python setup.py install

Python Test:

cd test
python test.py

C++ Test:

gcc -std=c++11 -fPIC -lm -lstdc++ -pthread DPoint.cpp CityMap.cpp test.cpp -o test -g
./test city_num time_out

Execute

• 设置城市数500，将随机生成 经度~(30.0, 40.0)，纬度~(110.0, 130.0)之间的城市

  • 城市距离没有使用球面模型计算，而是如下简化的计算方法：
    • 南北方向AM = 地球半径 * 纬度差 * Math.PI/180.0；
    • 东西方向BM = 地球半径 * 经度差 * Cos<当地纬度数 * Math.PI/180.0>
    • 距离 = sqrt(AM*AM + BM*BM)
  • reference: http://tech.meituan.com/lucene-distance.html

• 遗传算法参数:

  • 种群数：种群数越大，遗传基因多样性越丰富
  • 子女数：每个种群遗传产生下一代的子女数
  • 最大转移数：变异时两个基因产生交叉的序列长度，该数值越大，变异性越大
  • 灾变：灾变初始值，灾变倍增值
    • 灾变的概念：这里设定当最优个体在连续多代遗传时都保持不变，就启动灾变倒计时。 当倒计时为0时表示当前种群陷入局部最优，将种群基因重置，类似于物种灭绝并产生新物种

• 设置程序运行时间20秒，设置调试模式为true

• Result of Execution：

    [work@localhost test]$ python analysis.py 
    time_out: 2000 , state:  500个城市 第2776代 最优产生于第2763代 分数0.186737 里程34096140.417267 灾变倒计数0788 灾变计数000 群体平均分0.143186 用时2000(ms)
    time_out: 4000 , state:  500个城市 第5695代 最优产生于第5682代 分数0.237647 里程26791815.559546 灾变倒计数0788 灾变计数000 群体平均分0.173504 用时4000(ms)
    time_out: 6000 , state:  500个城市 第8691代 最优产生于第8618代 分数0.258155 里程24663463.804994 灾变倒计数0728 灾变计数000 群体平均分0.196991 用时6010(ms)
    time_out: 8000 , state:  500个城市 第11644代 最优产生于第11640代 分数0.280567 里程22693316.459644 灾变倒计数0797 灾变计数000 群体平均分0.216620 用时8010(ms)
    time_out: 10000 , state:  500个城市 第14671代 最优产生于第14565代 分数0.291937 里程21809472.816275 灾变倒计数0695 灾变计数000 群体平均分0.188085 用时10010(ms)
  

• ERROR：traveller_wrap.cxx:2843:13: 错误：‘ptrdiff_t’不是一个类型名 virtual ptrdiff_t distance(const SwigPyIterator &/x/) const\
  • Solution：类型ptrdiff_t在<stddef.h>中定义，在swig生成的traveller_wrap.cxx文件头部添加：#include<stddef.h>