采用遗传算法求解最短路径问题（已知起终点并经其他所有点）

aimisiyou

已知点集，指定其中的起点和终点，求起点到终点的最短路径（线路经过其他所有点并只经过一次）。

aimisiyou

;;;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)))))))
)

tzfcn

遗传算法不容易理解，有好的教材吗？

aimisiyou

tzfcn 发表于 2020-2-4 10:14
遗传算法不容易理解，有好的教材吗？

网上关于遗传算法的内容很多，可以下载看看。

tzfcn

遗传算法是在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调度问题的早熟收敛,邵新宇等人还设计了一种改进的子代交替模式遗传算法,明显加快了遗传算法收敛的速度,此原理同样适用于其他组合优化问题。邵新宇等人所提出的遗传算法的变异不同于传统遗传算法中的变异操作(为保持群体的多样性),是通过局部范围内搜索改善子代的性能

tzfcn

代码运行良好。

aimisiyou

tzfcn 发表于 2020-2-4 11:24
代码运行良好。

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

tzfcn

aimisiyou 发表于 2020-2-4 11:49
运行这么快？是你的电脑配置高还是N_d设置的小？我的电脑上50以内的点数，N_d设置为3000，也要运行3～5分 ...

玩电脑的都没有好电脑，我不玩电脑，所以电脑用好的

tzfcn

aimisiyou 发表于 2020-2-4 02:05
;;;24个点（含起始点和终点），程序运行约2分钟。若想得到 更优解，适当调大N_d值，当然运行时间会更长些。 ...

选中的点有显示就更好了。

aimisiyou

可以将N_d设置成点数n的函数，如N_d=3*n^2，这样就可以动态决定循环次数，当点数少时运行加快。

tzfcn

点多时运行时间是比较长，应该可以优化算法地

aimisiyou

tzfcn 发表于 2020-2-6 09:58
点多时运行时间是比较长，应该可以优化算法地

优化肯定是可以的，见LKH算法（之前是想实现的，但中途搁浅了），该算法就是在一开始就构造个体都是较好解的种群，所以收敛很快。本程序一开始生成的种群中个体是随机的，所以运行时间长。

dcl1214

用迪杰斯特拉吧，速度很快的

dcl1214

http://bbs.xdcad.net/thread-725178-1-1.html
迪杰斯特拉专门计算最短路径的

aimisiyou

dcl1214 发表于 2020-2-6 14:06
http://bbs.xdcad.net/thread-725178-1-1.html
迪杰斯特拉专门计算最短路径的

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