采用交叉熵算法求解0-1背包问题

mahuan1279

当数据量变大时，容易陷入局部最值，跟蚁群算法的鲁棒性有些相似。如何避免一开始就“误入歧途”是个值得考虑的问题。

mahuan1279

(defun tt()
(setq w_tol 7718  
      clst '(597     596     593     586    581    568     567  560     549     548    547    529    529    527    520     491     482    478    475    475    466     462    459    458    454    451    449    443    442    421    410    409     395    394     390    377    375    366  361    347    334    322    315    313    311    309  296     295      294    289    285    279    277    276    272    248    246    245    238    237     232     231    230    225     192     184     183     176     174    171    169    165    165     154    153     150     149     147     143     140     138     134     132     127    124    123     114     111     104     89     74    63      62    58    55    48    27     22    12    6    220    208    198     192     180    180     165     162     160     158     155     130    125    122    120     118     115     110     105     101     100     100     98     96     95     90    88     82    80    77    75     73     72     70  69      66     65    63      60     58    56     50    30    20    15    10    8    5    3    1)   
      wlst '(54     183  106  82     30    58    71  166  117     190     90     191 205     128     110     89    63    6     140     86    30    91    156    31     70    199     142     98     178     16     140    31    24    197     101    73     169    73    92     159     71     102     144     151    27     131     209     164     177     177     129    146     17    53     164     146     43     170     180     171     130     183    5     113    207    57    13     163    20     63    12    24    9     42    6     109     170     108     46     69    43  175    81    5    34     146     148     114     160     174     156     82     47     126     102    83    58    34    21    14     80    82    85    70    72    70     66     50     55    25    50    55    40    48    50    32    22    60        30    32    40    38     35    32    25    28    30    22    25    30    45    30    60    50    20    65    20    25     30     10    20     25     15     10     10    10    4    4    2    1))
(setq n (length wlst) m 1000  r 0.9 pflst nil pslst nil)
(repeat n
  (setq pflst (cons 0.5 pflst))
  (setq pslst (cons 1.0 pslst))
)
(defun rnd ()
  (*(rem (getvar "cputicks") 1e4) 1e-4)
)
(defun xfun(lst)
  (mapcar '(lambda (x) (if (< (rnd) x) 1 0)) lst)
)
(defun check(lst)
  (setq s 0 c 0)
  (mapcar '(lambda (x y) (if (<= (setq s (+ s (* x y))) w_tol) (progn (setq c s) y)(progn (setq s c) 0))) wlst lst)
)
(setq valst '(0 0))
(while (> (apply 'max (mapcar '(lambda (x y) (abs (- y x))) pflst pslst)) 0.001)
(setq xlst nil)
(repeat m
  (setq xlst (cons (xfun pflst) xlst))
)
(setq xlst (mapcar 'check xlst))
(setq vlst (mapcar '(lambda (x) (apply '+ (mapcar '* x clst))) xlst))
(setq pt (nth (fix (* r m))
              (mapcar 'cadr (vl-sort (mapcar '(lambda (x) (list (float x) x)) vlst) '(lambda (ea eb) (< (car ea) (car eb)))))
          )
)
(setq evlst (mapcar '(lambda (y) (if (>= y pt) 1 0)) vlst) en (float (apply '+ evlst)))
(setq pslst (mapcar '(lambda (k) (/ k en)) (mapcar '(lambda (z) (apply '+ (mapcar '* z evlst)))  (apply 'mapcar (cons 'list xlst)))))
(setq pflst (mapcar '(lambda (x y z) (+ (* 0.9 x) (* 0.075 y) (* 0.025 z))) pslst pflst ylst))
(setq ylst (car (vl-remove nil (mapcar '(lambda (x) (if (= (apply 'max vlst) (apply '+ (mapcar '*  x clst))) x nil)) xlst))))
(setq vblst (list (apply '+ (mapcar '* clst ylst))
                  (apply '+ (mapcar '* wlst ylst))
                   ylst
                         )
)
(if (> (car vblst) (car valst))
    (setq valst vblst)
)
)
valst
)

_$ (repeat 5 (progn (princ (tt)) (princ " ")))
(29631 7718 (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0)) (29589 7717 (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0)) (29283 7710 (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0)) (29531 7715 (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0)) (29220 7718 (1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0)) " "
_$