数学建模社区-数学中国

标题: TSP算法小软件要考虑的问题很多 [打印本页]

---

作者: 释永思    时间: 2016-5-4 15:13
标题: TSP算法小软件要考虑的问题很多

" B$ r5 Y5 @+ E
  T; p0 a7 }: G. d8 R5 Z7 ~5 oTSP算法小软件要考虑的问题很多。
- G. j# `. `3 y5 J6 t) g6 u选择遗传算法，蚁群算法，动态规划算法三种算法，
如何让这三种算法有公共的参数，如顶点数，顶点坐标，用户自定义坐标，随机生成坐标。
又如何三种算法有各自不同的参数，如遗传次数，蚁群蚂蚁数。。。
! x7 q6 D2 [6 g6 b& M: E显示的顶点与坐标，如果超出屏幕如何滚动，顶点如何标号，如何显示最后路径标号。。。
这三种算法，要如何显示动态求解过程，而不是仅仅显示一个结果。。。
% z1 p" z0 k$ ^最后决定，不作为压力任务，有空时搞下，没空时算了，不理了。。。

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

2016-5-10 14:12 上传

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

% e; g; `" f5 s. @& C8 A9 ^
8 [% D/ }  R3 s9 g3 t

" i/ U( {& T! O; G


6 _) w5 l4 `' I- S6 i+ _

  ]/ [! `8 N  Z0 Y3 b; o3 x
8 r, L% y2 N% e3 k$ l5 T# m! ^

5 z/ p, W% Q5 b7 ~) Q& b( \' F" W

1 g4 ?! m; A; ]/ s. O
- D) H8 e& H2 Y. _7 q% ?4 l% x
* h# P' G* Q) \" ^  D6 r; n

. `& E/ A/ u1 U* s$ \- b. ~


" W1 l- G& ~5 B6 N. Z7 X& X  X# R

7 i# E4 W* z7 k

---

作者: 释永思    时间: 2016-5-7 11:31
我开发的TSP算法小软件（未完成），暂时如此，下载网址：http://pan.baidu.com/s/1geZdh2F
/ N9 x( L$ d, X% d9 V2 G# [- T$ u. y

---

作者: 释永思    时间: 2016-5-7 15:09
我开发的TSP算法小软件（未完成），暂时如此，下载网址：
4 O7 ~  |9 K  m5 |: U: G. ihttp://pan.baidu.com/s/1o8y7sbK
# `+ x, q+ ]8 O2 e' |' S! p% B比刚才的改正了一些BUG。基本上DELPHI的遗传算法与蚁群算法都可行的了。
" h1 `9 Z' w* [0 Z) `( r现在周末放松下先，下周开始专攻DELPHI的TSP的动态规划算法代码了。
/ j: t3 z( L" _/ u" l: A小软件，玩下而已，不必太过认真，兴趣玩下。
2 k  j6 D  a. G; K7 u

---

作者: 释永思    时间: 2016-5-9 15:37
首先解决TSP的DP的数据存储问题，所以称为状态压缩法。也就是用二进制字符串表示子集的方法

5 ^- W2 e5 W1 h* r) s3 ~" U9 _。一个TStringList，一行代表一列，即一行本是这样的：   01011101001,P1,P2,,,Pn，
这样用TStringList来做是可能正确的方法。
* I& [. N. |+ U7 O; {* t由于不可能太大量，所以不用TStringList来做，改用数组来做，这样一样用二进制字串代表表示

: V% f% |) W6 o# G3 |2 h7 _! @子集的方法，就成为方向了。

---

作者: 释永思    时间: 2016-5-10 10:17

! @' Q; P0 ^! g: z) c
经过一段时间的辛苦研究开发，TSP问题算法小软件V1.0终于开发完成了，先发出来让大家使用下
先，有什么BUG以后再理了。有遗传算法，蚁群算法，动态规划算法，三种算法同时求解，GUI图
1 j" R( m' P  A4 `形路径显示，方便大家学习研究。
/ {, {; b5 p2 p- r( T% f% r下载网址：http://pan.baidu.com/s/1nveqIV3

---

作者: 释永思    时间: 2016-5-11 14:36
我现在开始学习思考，遗传算法，蚁群算法，动态规划，在求连续函数的极值中的应用。
5 y5 w8 J5 n" P/ |. j0 E2 ]. i" V在TSP中的应用我已经知了，在连续函数中求极值，又要学习一番了。

---

作者: 释永思    时间: 2016-5-12 10:49
自思自悟：
蚁群求极值：
7 O1 z0 M1 I: V) D0 v) j6 |一开始M个蚂蚁，平均取值，得到M个适应值。
1 _* I- [8 \8 [- W- q由M个适应值，按比例比重调整信息素，
+ W, T* j: O" y0 g. M( {* _! }& R下次产生随机点时，不是平均产生，是按信息素产生，
就是这么简单。
" O5 w! {/ E, u0 D不理什么路径。蚁群在求函数极值时路径对应什么，实在想不出来。
. v, s9 X4 i, k% a
( R4 V6 f0 F$ b/ C9 U, ?$ C遗传算法求极值：
# k8 P, u& t# ?+ V一开始M个种群，平均取值，得到M个适应值。
( i- z$ d9 @) f4 X3 m交叉变异，又得N个适应值，排序筛选种群。重复。
9 o3 w1 b. U4 p! W- U; w& {如何交叉变异，这是数字游戏。
: I1 a$ o3 l( N) {# l5 b7 ^) B0 C
9 g2 r) P) [& J. B# ^

---

作者: 释永思    时间: 2016-5-12 13:37


关于思考一个数字与一条路径的对应关系，又令我一个午睡没法睡着。
6 G" P4 F; Y  ]% a7 A+ C* e我这样想，一个数字，假定是固定的N位数，则每位数是十进制，就是N重循环，每重循环取十个数字。
这如同一个图，有N个点，每个点十条边，穷举历遍所有路径，就是N位数字的全部数字。这样，就可以和蚁群中的路径对应上了，就可以用蚁群中的节点信息素来运用到函数求极值上来了。这样，不用一个蚁点一个信息素，而是一位数字一个信息素，与TSP路径可以对应上了。为思考此，我又一个午睡没有睡着了。

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5