找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1319|回复: 18

[研讨] 采用遗传算法求解最短路径问题(已知起终点并经其他所有点)

[复制链接]

已领礼包: 1857个

财富等级: 堆金积玉

发表于 2020-2-4 01:10:52 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

×
已知点集,指定其中的起点和终点,求起点到终点的最短路径(线路经过其他所有点并只经过一次)。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2020-2-4 02:05:30 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-2-4 02:36 编辑

;;;24个点(含起始点和终点),程序运行约2分钟。若想得到 更优解,适当调大N_d值,当然运行时间会更长些。
(defun c:tt()
(defun rnd ()
  (*(rem (getvar "cputicks") 1e4) 1e-4)
)
(defun rnd_n (n)
  (fix (* n (rnd)))
)
(defun pick (lst i j)
   (setq count (length lst) nc 0 picklst nil)
   (while (<= nc j)
       (if (<= i nc)
           (setq picklst (cons (nth nc lst) picklst))
       )
      (setq nc (+ nc 1))
   )   
   (reverse picklst)
)
(defun xipai (n)
  (setq i 1 j 0 klst nil)
  (while (<= i n)
      (setq klst (cons i klst))
      (setq i (+ 1 i))
   )
   (while (<= j 20)
         (setq i_pot (rnd_n n))
         (setq j_pot (rnd_n n))
         (setq nmin (min i_pot j_pot))
         (setq nmax (max i_pot j_pot))
         (setq klst (append (pick klst  (+ 1 nmax) (- n 1)) (pick klst (+ 1 nmin) nmax) (pick klst 0 nmin)))
         (setq j (+ j 1))
   )
   (mapcar '1- klst)
)
(defun fitfun (ptlst)
  (apply '+ (mapcar 'distance ptlst (append (cdr ptlst) (list (car ptlst)))))
)
;;;取点函数
(defun fp ()
    (setq sn (ssget ":N" '((0 . "point"))))
    (setq i 0 n (sslength sn) pts nil)
    (while (< i n)
        (setq pts (cons (cons i (cdr (assoc 10 (entget (ssname sn i))))) pts))
        (setq i (+ i 1))
    )
    (reverse pts)
)
(setq pts (fp))
(setq pt_sta (getpoint "请选择起始点:" ))
(setq pt_end (getpoint "请选择终点:" ))
(setq poplst nil)
(repeat 100
  (setq plst (xipai (length pts)))
  (setq poplst (cons plst poplst))
)
(defun n-pt (nlst)
(mapcar '(lambda (x) (cdr (nth x pts))) nlst)
)
(defun fitfun (ptlst)
  (apply '+ (mapcar 'distance (cons pt_sta ptlst) (reverse (cons pt_end (reverse ptlst)))))
)
(setq p_best  (car (vl-sort (mapcar '(lambda (x y) (cons (fitfun (n-pt x)) y))
                                      poplst
                                      poplst
                                                          )  
                              '(lambda (e1 e2)  (< (car e1) (car e2)) )
                      )                          
                )
)
(setq p_chane 0.02  N_d 3000 ii 0)
(while (< ii N_d)
   (setq vlst nil)
   (foreach en poplst
       (setq nt (length en))
       (setq  ens en pc1 (nth (rnd_n nt) ens) flag t clst (list pc1))
       (while flag
            (setq r_rnd (rnd))
            (if (< r_rnd p_chane)
                            (setq pc2 (nth (rnd_n (- nt 1)) (vl-remove pc1 ens)))
                (progn
                    (setq en_rnd (nth (rnd_n nt) poplst))
                                        (if (= pc1 (last en_rnd))
                                            (setq pc2 (car en_rnd))
                                            (setq pc2 (cadr (member pc1 en_rnd)) )
                                        )   
                                 )
                          )
                         (if (or (= pc2 (cadr (member pc1 ens))) (= pc1 (cadr (member pc2 ens))) )
                             (setq flag nil)
                 (progn
                    (if (member pc2 (member pc1 ens))
                        (setq ens (append (reverse (member pc1 (reverse ens))) (member pc2 (reverse (cdr (member pc1 ens)))) (cdr (member pc2 ens)) ))
                          (setq ens (append (reverse (member pc2 (reverse ens))) (member pc1 (reverse (cdr (member pc2 ens)))) (cdr (member pc1 ens)) ))
                     )
                     (setq pc1 pc2)
                                         (setq clst (cons pc1 clst))
                                         (if (= (length clst) (- nt 1))
                                             (setq flag nil)
                                          )
                                 )
                         )
           )
      (if (< (fitfun (n-pt ens)) (fitfun (n-pt en)))
                  (setq vlst (cons ens vlst))
              (setq vlst (cons en  vlst))
           )
        )
   (setq ii (+ 1 ii))
   (setq poplst vlst)
   (setq p_bestnew  (car (vl-sort (mapcar '(lambda (x y) (cons (fitfun (n-pt x)) y)) poplst poplst)  
                                             '(lambda (e1 e2)  (< (car e1) (car e2)) )
                                    )
                                )
                 )
  (if (< (car p_bestnew) (car p_best) )
      (setq  p_best p_bestnew)
   )
)
(apply 'command (cons "pline" (reverse  (cons "" (reverse (n-pt (cdr p_best)))))))
)

cc.png

点评

选中的点有显示就更好了。  详情 回复 发表于 2020-2-4 13:18
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 5295个

财富等级: 富甲天下

发表于 2020-2-4 10:14:19 | 显示全部楼层
遗传算法不容易理解,有好的教材吗?

点评

网上关于遗传算法的内容很多,可以下载看看。  详情 回复 发表于 2020-2-4 10:47
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2020-2-4 10:47:35 | 显示全部楼层
tzfcn 发表于 2020-2-4 10:14
遗传算法不容易理解,有好的教材吗?

网上关于遗传算法的内容很多,可以下载看看。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 5295个

财富等级: 富甲天下

发表于 2020-2-4 11:01:27 | 显示全部楼层
遗传算法是在20世纪六七十年代由美国密歇根大学的 Holland教授创立。60年代初,Holland在设计人工自适应系统时提出应借鉴遗传学基本原理模拟生物自然进化的方法。1975年, Holland出版了第一本系统阐述遗传算法基本理论和方法的专著,其中提出了遗传算法理论研究和发展中最重要的模式理论( schemata theory)。因此,一般认为1975年是遗传算法的诞生年。同年, de jong完成了大量基于遗传算法思想的纯数值函数优化计算实验的博士论文,为遗传算法及其应用打下了坚实的基础。1989年, Goldberg的著作对遗传算法做了全面系统的总结和论述,奠定了现代遗传算法的基础。
遗传算法是一种基于“适者生存”的高度并行、随机和自适应的优化算法,通过复制、交叉、变异将问题解编码表示的“染色体”群一代代不断进化,最终收敛到最适应的群体,从而求得问题的最优解或满意解。其优点是原理和操作简单、通用性强、不受限制条件的约束,且具有隐含并行性和全局解搜索能力,在组合优化问题中得到广泛应用。最早将遗传算法应用于jb-shop调度问题的是 Davis遗传算法求解job-shop调度问题时较少应用邻域知识,更适合应用于实际。如何利用遗传算法高效求解job-shop调度问题,一直被认为是个具有挑战意义的难题,并成为研究的热点。
遗传算法中交叉算子是最重要的算子,决定着遗传算法的全局收敛性。交叉算子设计最重要的标准是子代继承父代优良特征和子代的可行性。邵新宇等人在深入分析job-shop调度问题的基础上,提出了一种基于工序编码的POX方法,将其与其他基于工序编码的交叉进行比较,证明了该交叉方法解决job-shop调度问题的有效性。同时,为解决传统遗传算法在求解jb-shop调度问题的早熟收敛,邵新宇等人还设计了一种改进的子代交替模式遗传算法,明显加快了遗传算法收敛的速度,此原理同样适用于其他组合优化问题。邵新宇等人所提出的遗传算法的变异不同于传统遗传算法中的变异操作(为保持群体的多样性),是通过局部范围内搜索改善子代的性能
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 5295个

财富等级: 富甲天下

发表于 2020-2-4 11:24:35 | 显示全部楼层
代码运行良好。
散点串联.gif

点评

运行这么快?是你的电脑配置高还是N_d设置的小?我的电脑上50以内的点数,N_d设置为3000,也要运行3~5分钟。当然点数不多的时候,N_d设置小也可接受,加快运行速度。  详情 回复 发表于 2020-2-4 11:49
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2020-2-4 11:49:44 | 显示全部楼层
tzfcn 发表于 2020-2-4 11:24
代码运行良好。

运行这么快?是你的电脑配置高还是N_d设置的小?我的电脑上50以内的点数,N_d设置为3000,也要运行3~5分钟。当然点数不多的时候,N_d设置小也可接受,加快运行速度。

点评

玩电脑的都没有好电脑,我不玩电脑,所以电脑用好的  详情 回复 发表于 2020-2-4 12:17
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 5295个

财富等级: 富甲天下

发表于 2020-2-4 12:17:35 | 显示全部楼层
aimisiyou 发表于 2020-2-4 11:49
运行这么快?是你的电脑配置高还是N_d设置的小?我的电脑上50以内的点数,N_d设置为3000,也要运行3~5分 ...


玩电脑的都没有好电脑,我不玩电脑,所以电脑用好的
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 5295个

财富等级: 富甲天下

发表于 2020-2-4 13:18:37 | 显示全部楼层
aimisiyou 发表于 2020-2-4 02:05
;;;24个点(含起始点和终点),程序运行约2分钟。若想得到 更优解,适当调大N_d值,当然运行时间会更长些。 ...

选中的点有显示就更好了。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2020-2-4 13:24:33 | 显示全部楼层
可以将N_d设置成点数n的函数,如N_d=3*n^2,这样就可以动态决定循环次数,当点数少时运行加快。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 5295个

财富等级: 富甲天下

发表于 2020-2-6 09:58:05 | 显示全部楼层
点多时运行时间是比较长,应该可以优化算法地

点评

优化肯定是可以的,见LKH算法(之前是想实现的,但中途搁浅了),该算法就是在一开始就构造个体都是较好解的种群,所以收敛很快。本程序一开始生成的种群中个体是随机的,所以运行时间长。  详情 回复 发表于 2020-2-6 10:21
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2020-2-6 10:21:27 | 显示全部楼层
tzfcn 发表于 2020-2-6 09:58
点多时运行时间是比较长,应该可以优化算法地

优化肯定是可以的,见LKH算法(之前是想实现的,但中途搁浅了),该算法就是在一开始就构造个体都是较好解的种群,所以收敛很快。本程序一开始生成的种群中个体是随机的,所以运行时间长。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2020-2-6 14:05:00 | 显示全部楼层
用迪杰斯特拉吧,速度很快的
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

发表于 2020-2-6 14:06:21 | 显示全部楼层
http://bbs.xdcad.net/thread-725178-1-1.html
迪杰斯特拉专门计算最短路径的

点评

两者有区别,迪杰斯特拉计算的两点间最短路径不需要经过其他所有点。那个可以用弗洛伊德算法实现,复杂度O(n^3),没迪杰斯特拉算法快,但很容易实现且代码简单。  详情 回复 发表于 2020-2-6 14:35
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

已领礼包: 1857个

财富等级: 堆金积玉

 楼主| 发表于 2020-2-6 14:35:54 | 显示全部楼层
本帖最后由 aimisiyou 于 2020-2-6 14:38 编辑

两者有区别,迪杰斯特拉计算的两点间最短路径不需要经过其他所有点。那个可以用弗洛伊德十字法实现,复杂度O(n^3),没迪杰斯特拉算法快,但很容易实现且代码简单。复杂度小的可以用A*算法。

点评

迪杰斯特拉穷举一万条路径,只需要一秒钟  详情 回复 发表于 2020-2-6 15:06
整体最短路径,其实就是单个的两点最短,是不是?如果两点不是最短,那么整体也不是最短,你这个可以求出好几个整体最短,然后排序取第一个  详情 回复 发表于 2020-2-6 15:04
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )

GMT+8, 2024-3-29 15:28 , Processed in 0.434432 second(s), 59 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表