随机组合择优算法

zopey · 发表于 2019-11-3 23:43

工作表1有49列数据，从中任选12列，从第1行开始，如果该行有一个数字则继续往下查找，
直至某行N与所选12列交叉单元格的内容皆空，停止查找并记录最大行数 N-1。

题目就是寻找49选12所有组合中，可能满足最大的N。本例只有114行数据，故N 理论最大值为114。
海量组合穷举法耗时太长，故选用随机组合算法，主要参考了遗传算法的交叉算子。有待优化。

无标题.jpg

随机组合择优算法.rar (28.73 KB, 下载次数: 47)

zopey · 发表于 2019-11-4 12:54

49选12 组合：
1、个体编码为一个字符串，长度49代表所有列，数字1代表选中列，数字0代表未选中，数字1累计为12个。
   穷举法一次生成所有组合，普通随机一次生成一个组合判断，遗传算法一次生成一个若干个组合的族群。
2、遗传算法本例中一次生成 50个组合（初始族群），每迭代一次又是50个新的组合（完整步骤是：选择+交叉+变异），加快了筛选。

a、当选出两个个体rg1、rg2 ，要交叉部分的数字1 累计个数相等才可以交叉操作，否则新产生的个体不符组合要求。
   1010 和 0011    可以交叉置换
   1010 和 0001    不可以交叉
b、变异操作也要设计为 1与 0 交换。

zopey · 发表于 2019-12-23 15:34

题目见 http://club.excelhome.net/thread-1513250-1-1.html
关于搬石头的解答（随机组合），撞不出最优解564，太难了。

搬石头.zip (20.21 KB, 下载次数: 19)

yjh_27 · 发表于 2019-12-23 16:12

zopey 发表于 2019-12-23 15:34
题目见 http://club.excelhome.net/thread-1513250-1-1.html
关于搬石头的解答（随机组合），撞不出最优 ...

17人去搬9块石头，有10^17种搬法，只有163种最大564的搬法。
确实大海捞针

zopey · 发表于 2019-12-23 16:56

yjh_27 发表于 2019-12-23 16:12
17人去搬9块石头，有10^17种搬法，只有163种最大564的搬法。
确实大海捞针

人不怕多，应是 9^17 搬法。

yjh_27 · 发表于 2019-12-23 17:43

zopey 发表于 2019-12-23 16:56
人不怕多，应是 9^17 搬法。

是的，不计不出力的，就减为9^17

按我原帖16L的算法，求出163个最佳，也就5秒

zopey · 发表于 2020-3-15 10:00

题目：
http://club.excelhome.net/thread-1525690-1-1.html

说有两个答案：
39,15,46,25,23,30,03
39,15,46,25,23,30,06
答题器，随机多试几次，运气好出来一个答案

迭代表2.rar (33.11 KB, 下载次数: 8)

micch · 发表于 2020-3-15 10:49

丢丢老师这个题目，来自于论坛一个求助，之前我推荐他倒代码版求助了，但是老师们都没答，估计是因为求助的太随意了。

感觉应该有某个算法适合解决，但是不懂，用数组排列组合运算量又大，只能用排除法选最多，然后排除选次多，一个一个选，但是随机数据测试的时候，这样排除不合理。并列数字选择的时候，只能随机选，对结果有影响。

一把小刀闯天下 · 发表于 2020-3-15 11:23

zopey 发表于 2020-3-15 10:00
题目：
http://club.excelhome.net/thread-1525690-1-1.html

这个问题确实也没有什么好的想法，如果局部最优都为一个估计直接就能得出全局最优。但实际情况会有很多个，如果按组合来算计算量太大了，所以先随机再取第一个局部最优去匹配，随机次数100可能就能得到全局最优的。当然它可能会有很多个最优解，只是不能确定这种方法是否一定能得到全局最优解，，，

http://club.excelhome.net/forum. ... ;page=2#pid10264106

zopey · 发表于 2020-3-15 11:54

一把小刀闯天下发表于 2020-3-15 11:23
这个问题确实也没有什么好的想法，如果局部最优都为一个估计直接就能得出全局最优。但实际情况会有很多个 ...

遗传算法族群繁衍有3个步骤：1、选择，2 交叉，3、变异。

目前只有交叉运算，初始的生成族群（要多试几次）对后面迭代结果影响较大；考虑增加变异运算，使程序更有效率。

'交叉位置
'tempb = Int(1 + Rnd() * k1)
For i = 1 To k1
If Mid(rg1, i, 1) <> Mid(rg2, i, 1) Then Exit For '交叉起始位 i
Next
t1 = 0: t2 = 0
For j = i To k1
If Mid(rg1, j, 1) = 1 Then t1 = t1 + 1
If Mid(rg2, j, 1) = 1 Then t2 = t2 + 1
If t1 = t2 Then Exit For '交叉结束位 j
Next

复制代码

		自动登录	找回密码
密码			免费注册

[分享] 随机组合择优算法

评分

评分

最新热点 /1