切割库存问题（优化钢筋或其他材料的切割）遗传算法

admin1

(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 2 0) 12.0 nil)
=> ((0 2 0 2 0) (0 2 0 1 0) (0 2 0 0 0) (0 1 0 2 0) (0 1 0 1 0) (0 1 0 0 0))
(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 0 2) 12.0 nil)
=> ((0 2 0 0 2) (0 2 0 0 1) (0 2 0 0 0) (0 1 0 0 2) (0 1 0 0 1) (0 1 0 0 0))
(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 2 0) 12.0 T)
=> ((0 2 0 2 0) (0 2 0 1 0) (0 2 0 0 0) (0 1 0 2 0) (0 1 0 1 0) (0 1 0 0 0) (0 0 0 2 0) (0 0 0 1 0))
(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 0 2) 12.0 T)
=> ((0 2 0 0 2) (0 2 0 0 1) (0 2 0 0 0) (0 1 0 0 2) (0 1 0 0 1) (0 1 0 0 0) (0 0 0 0 2) (0 0 0 0 1))[code];; 20150929: Fixed by Roy.

‎;;参数：lenLst List，按降序排列的所需长度。;‎
‎;;demLst 列表，相应要求长度的数目。;‎
‎;;股票真实，标准股票的长度。;‎
‎;;allPatP 布尔值，如果为 true，则生成所有可行模式。;‎
‎;;如果为 false，则仅生成模式集 ;‎
‎;;对于第一个需求> 0。 ;‎
;; 20150918: Very minor changes by Roy.
;; GenPat                    (By Ymg)                                         ;
;;                                                                            ;
;; http://www.theswamp.org/index.php?topic=48889.0                            ;
;;                                                                            ;
;; Procedure for Generating the Efficient Feasible Cutting Patterns           ;
;; http://www.cs.bham.ac.uk/~wbl/biblio/gecco2006/docs/p1675.pdf              ;
;; Appendix 1                                                                 ;
;; Part of "Cutting Stock Waste Reduction Using Genetic Algorithms"           ;
;;              by Y. Khalifa, O. Salem and A. Shahin                         ;
;;                                                                            ;
;; Argument: lenLst     List, Demanded Lengths in Descending Order.           ;
;;           demLst     List, Number of Corresponding Demanded Length.        ;
;;           stockLen   Real, Length of Standard Stock.                       ;
;;           allPatP    Boolean, if true,  Generate all Feasible Patterns.    ;
;;                               if false, Generate only the Set of Patterns  ;
;;                                         for the First Demand > 0.          ;
(defun GenPat (lenLst demLst stockLen allPatP / i j cntLst maxIdx patLst usedLen)
  (setq maxIdx (length lenLst))
  (setq i 0)
  (while (zerop (nth i demLst)) (setq i (1+ i)))
  (while
    (or
      (not cntLst)
      (if allPatP
        (> (apply '+ cntLst) 0)
        (> (nth i (reverse cntLst)) 0)
      )
    )
    (cond
      (cntLst
        (while (zerop (car cntLst)) (setq cntLst (cdr cntLst))) ; Last item in cntLst is for the first item (= longest) in lenLst.
        (setq cntLst (cons (1- (car cntLst)) (cdr cntLst)))
        (setq j (length cntLst))
        (setq usedLen
          (apply
            '+
            (mapcar
              '(lambda (cnt len) (* cnt len))
              (reverse cntLst)
              lenLst
            )
          )
        )
      )
      (T
        (setq j 0)
        (setq usedLen 0.0)
      )
    )
    (while (< j maxIdx)
      (setq cntLst
        (cons
          (min
            (fix (/ (- stockLen usedLen) (nth j lenLst)))
            (nth j demLst)
          )
          cntLst
        )
      )
      (setq usedLen (+ usedLen (* (car cntLst) (nth j lenLst))))
      (setq j (1+ j))
    )
    (setq patLst (cons (reverse cntLst) patLst))
  )
  (reverse (cdr patLst)) ; Remove 'zero pattern'.
)[/code]