设为首页收藏本站转
发帖领奖家园QQ群申请版主版主评价切换到宽版

 找回密码
 立即注册

QQ登录

只需一步，快速开始

扫一扫，访问微社区

晓东CAD家园-论坛»论坛 › ╃CAD编程开发 › 算法与数据结构 › 采用交叉熵算法求解0-1背包问题
12
返回列表 发新帖
楼主: aimisiyou

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

[复制链接]
aimisiyou

已领礼包: 1861个

财富等级: 堆金积玉
 楼主| 发表于 2020-12-25 08:32:08 | 显示全部楼层
(defun tt()
(setq w_tol 3820  
      wlst '(54 95 36 18  4 71 83 16 27 84 88 45 94 64 14 80  4 23 75 36
             90 20 77 32 58  6 14 86 84 59 71 21 30 22 96 49 81 48 37 28
              6 84 19 55 88 38 51 52 79 55 70 53 64 99 61 86  1 64 32 60
             42 45 34 22 49 37 33  1 78 43 85 24 96 32 99 57 23  8 10 74
             59 89 95 40 46 65  6 89 84 83  6 19 45 59 26 13  8 26  5  9)     ;;;各物品重量
      clst '(297 295 293 292 291 289 284 284 283 283 281 280 279 277 276 275 273 264 260 257  
             250 236 236 235 235 233 232 232 228 218 217 214 211 208 205 204 203 201 196 194
             193 193 192 191 190 187 187 184 184 184 181 179 176 173 172 171 160 128 123 114
             113 107 105 101 100 100  99  98  97  94  94  93  91  80  74  73  72  63  63  62
              61  60  56  53  52  50  48  46  40  40  35  28  22  22  18  15  12  11   6   5))  ;;;各物品价值
(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 (car (tt))) (princ " ")))
TT
15128 15128 15128 15150 15128 " "
_$
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能，那里可能会有你要找的答案；
如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子标题加上【已解决】；
如何回报帮助你解决问题的坛友，一个好办法就是给对方加【D豆】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
回复 支持 反对

使用道具 举报

aimisiyou

已领礼包: 1861个

财富等级: 堆金积玉
 楼主| 发表于 2020-12-25 11:45:36 | 显示全部楼层
_$  (defun tt()
(setq w_tol 3820  
      wlst '(54 95 36 18  4 71 83 16 27 84 88 45 94 64 14 80  4 23 75 36
             90 20 77 32 58  6 14 86 84 59 71 21 30 22 96 49 81 48 37 28
              6 84 19 55 88 38 51 52 79 55 70 53 64 99 61 86  1 64 32 60
             42 45 34 22 49 37 33  1 78 43 85 24 96 32 99 57 23  8 10 74
             59 89 95 40 46 65  6 89 84 83  6 19 45 59 26 13  8 26  5  9)     ;;;各物品重量
      clst '(297 295 293 292 291 289 284 284 283 283 281 280 279 277 276 275 273 264 260 257  
             250 236 236 235 235 233 232 232 228 218 217 214 211 208 205 204 203 201 196 194
             193 193 192 191 190 187 187 184 184 184 181 179 176 173 172 171 160 128 123 114
             113 107 105 101 100 100  99  98  97  94  94  93  91  80  74  73  72  63  63  62
              61  60  56  53  52  50  48  46  40  40  35  28  22  22  18  15  12  11   6   5))  ;;;各物品价值
(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.75 x) (* 0.15 y) (* 0.1 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 10 (progn (princ (car (tt))) (princ " ")))
TT
15163 15163 15163 15163 15163 15163 15163 15163 15163 15163 " "
_$
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能，那里可能会有你要找的答案；
如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子标题加上【已解决】；
如何回报帮助你解决问题的坛友，一个好办法就是给对方加【D豆】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
回复 支持 反对

使用道具 举报

aimisiyou

已领礼包: 1861个

财富等级: 堆金积玉
 楼主| 发表于 2020-12-27 23:44:48 | 显示全部楼层
本帖最后由 aimisiyou 于 2021-4-15 14:37 编辑

_$ (defun tt()
(setq w_tol 3820  
      wlst '(54 95 36 18  4 71 83 16 27 84 88 45 94 64 14 80  4 23 75 36
             90 20 77 32 58  6 14 86 84 59 71 21 30 22 96 49 81 48 37 28
              6 84 19 55 88 38 51 52 79 55 70 53 64 99 61 86  1 64 32 60
             42 45 34 22 49 37 33  1 78 43 85 24 96 32 99 57 23  8 10 74
             59 89 95 40 46 65  6 89 84 83  6 19 45 59 26 13  8 26  5  9)     ;;;各物品重量
      clst '(297 295 293 292 291 289 284 284 283 283 281 280 279 277 276 275 273 264 260 257  
             250 236 236 235 235 233 232 232 228 218 217 214 211 208 205 204 203 201 196 194
             193 193 192 191 190 187 187 184 184 184 181 179 176 173 172 171 160 128 123 114
             113 107 105 101 100 100  99  98  97  94  94  93  91  80  74  73  72  63  63  62
              61  60  56  53  52  50  48  46  40  40  35  28  22  22  18  15  12  11   6   5))  ;;;各物品价值
(setq n (length wlst) m 200  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.85 x) (* 0.125 y) (* 0.025 z))) pflst pslst 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 10 (progn (princ (car (tt))) (princ " ")))
TT
15163 15163 15163 15163 15163 15163 15163 15163 15163 15163 " "
_$
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能，那里可能会有你要找的答案；
如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子标题加上【已解决】；
如何回报帮助你解决问题的坛友，一个好办法就是给对方加【D豆】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
回复 支持 反对

使用道具 举报

aimisiyou

已领礼包: 1861个

财富等级: 堆金积玉
 楼主| 发表于 2021-1-7 09:54:07 | 显示全部楼层
本帖最后由 aimisiyou 于 2021-1-7 10:00 编辑

当数据量变大时，容易陷入局部最值，跟蚁群算法的鲁棒性有些相似。如何避免一开始就“误入歧途”是个值得考虑的问题。
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能，那里可能会有你要找的答案；
如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子标题加上【已解决】；
如何回报帮助你解决问题的坛友，一个好办法就是给对方加【D豆】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
回复 支持 反对

使用道具 举报

aimisiyou

已领礼包: 1861个

财富等级: 堆金积玉
 楼主| 发表于 2021-1-7 11:41:41 | 显示全部楼层
本帖最后由 aimisiyou 于 2021-1-7 11:50 编辑

(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)) " "
_$
m12.png
m13.png
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能，那里可能会有你要找的答案；
如果你在论坛求助问题，并且已经从坛友或者管理的回复中解决了问题，请把帖子标题加上【已解决】；
如何回报帮助你解决问题的坛友，一个好办法就是给对方加【D豆】，加分不会扣除自己的积分，做一个热心并受欢迎的人！
回复 支持 反对

使用道具 举报

12
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2024-4-25 02:45 , Processed in 0.175595 second(s), 36 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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