TSP算法小软件要考虑的问题很多

释永思

% V$ o5 [, h1 T: T( P# k+ C
  Q) E1 T$ x+ `* eTSP算法小软件要考虑的问题很多。
选择遗传算法，蚁群算法，动态规划算法三种算法，
如何让这三种算法有公共的参数，如顶点数，顶点坐标，用户自定义坐标，随机生成坐标。
又如何三种算法有各自不同的参数，如遗传次数，蚁群蚂蚁数。。。
& L: \9 E" C  h; E( `; }9 X显示的顶点与坐标，如果超出屏幕如何滚动，顶点如何标号，如何显示最后路径标号。。。
; l# T! U+ K; ~0 m0 L; S这三种算法，要如何显示动态求解过程，而不是仅仅显示一个结果。。。
最后决定，不作为压力任务，有空时搞下，没空时算了，不理了。。。

TSPv20.rar (222.11 KB, 下载次数: 1)

2016-5-10 14:12 上传

点击文件名下载附件
下载积分: 体力 -2 点

& s6 L- n6 V" ]* e

: I0 D/ w' J2 O9 N, L! n
1 y: d3 z% f0 i: P
0 r+ ^9 K. ?: g0 l8 ?* ~( u


/ [/ v" f+ g3 R




" [+ N1 z* z8 A0 p
+ U& C; I& k' }9 L


0 S; D  ]" W# W8 X/ }
8 F- a  w# X0 m; ?! o5 O3 f! Y


  Z( w3 d- I& l7 H, a( j, v$ y
& b' A; b2 V( S5 l: H( G, M4 X9 V

释永思

我开发的TSP算法小软件（未完成），暂时如此，下载网址：http://pan.baidu.com/s/1geZdh2F

释永思

我开发的TSP算法小软件（未完成），暂时如此，下载网址：
http://pan.baidu.com/s/1o8y7sbK
比刚才的改正了一些BUG。基本上DELPHI的遗传算法与蚁群算法都可行的了。
现在周末放松下先，下周开始专攻DELPHI的TSP的动态规划算法代码了。
小软件，玩下而已，不必太过认真，兴趣玩下。
; F; |4 }4 [' D  Z3 K

释永思

首先解决TSP的DP的数据存储问题，所以称为状态压缩法。也就是用二进制字符串表示子集的方法

。一个TStringList，一行代表一列，即一行本是这样的：   01011101001,P1,P2,,,Pn，
3 X3 ~+ q, f/ j* U  P这样用TStringList来做是可能正确的方法。
由于不可能太大量，所以不用TStringList来做，改用数组来做，这样一样用二进制字串代表表示
" g* G5 j0 Q& P- J1 D! P
/ Q8 ]. ?" \7 v" \' q子集的方法，就成为方向了。
  h2 d& O  I( f/ S4 ?4 ~" M

释永思

: \& F) F0 R1 d" P9 g' ~经过一段时间的辛苦研究开发，TSP问题算法小软件V1.0终于开发完成了，先发出来让大家使用下
" n+ o; v6 d  @0 T0 z0 Z4 F先，有什么BUG以后再理了。有遗传算法，蚁群算法，动态规划算法，三种算法同时求解，GUI图
4 h& I+ y( l( O% E! w形路径显示，方便大家学习研究。
$ }) T) p7 d  p下载网址：http://pan.baidu.com/s/1nveqIV3

释永思

我现在开始学习思考，遗传算法，蚁群算法，动态规划，在求连续函数的极值中的应用。
# }/ P/ s% Y- e, u5 p8 @! t在TSP中的应用我已经知了，在连续函数中求极值，又要学习一番了。
" A: ?8 e$ m: v4 A; m; o

释永思

自思自悟：
蚁群求极值：
5 e1 D/ U. {% X$ F. c一开始M个蚂蚁，平均取值，得到M个适应值。
% @9 A; q! u, B; E( g! P; d由M个适应值，按比例比重调整信息素，
下次产生随机点时，不是平均产生，是按信息素产生，
6 ]- M# _( ^( ?/ A" j9 L- T: J就是这么简单。
0 O, t& x( ?. H% `0 y! z3 r不理什么路径。蚁群在求函数极值时路径对应什么，实在想不出来。
& l( {5 R; j8 ~8 ]. f
遗传算法求极值：
  {. a8 [% ~6 ]- B, }8 D$ `一开始M个种群，平均取值，得到M个适应值。
- \. `& v" ^( P4 e: a交叉变异，又得N个适应值，排序筛选种群。重复。
如何交叉变异，这是数字游戏。
8 g/ p. P6 g$ K4 O; r
, p, \7 o1 m1 P2 B$ d5 y0 N

释永思

5 P- m4 R' ?9 y3 A& [8 _8 F
关于思考一个数字与一条路径的对应关系，又令我一个午睡没法睡着。
# N: o: V8 U6 _' \9 X7 R+ k; f( n我这样想，一个数字，假定是固定的N位数，则每位数是十进制，就是N重循环，每重循环取十个数字。
这如同一个图，有N个点，每个点十条边，穷举历遍所有路径，就是N位数字的全部数字。这样，就可以和蚁群中的路径对应上了，就可以用蚁群中的节点信息素来运用到函数求极值上来了。这样，不用一个蚁点一个信息素，而是一位数字一个信息素，与TSP路径可以对应上了。为思考此，我又一个午睡没有睡着了。
' g% F! Q7 ]6 q$ }

% p7 w9 Q! Q2 ?. @