一维下料（线材排样）软件

三坛老窖

aoe1981 发表于 2018-2-8 22:50
我的做法顶多是模仿。我把您的软件的参数一通胡乱设置，尤其调到极端值，比如都为0或很大，但效率依旧很 ...

“在参数的背后肯定更有创新性的算法”
别说的这么玄乎，自认为这个程序最大的亮点在于整个求解思路，即9楼的那张流程图，其他都是一些小技巧的组合，说出来谁都会，参数背后不存在什么创新性的算法，你琢磨琢磨马上可以看穿其中的原由，说不定能找到比我那个评价方法更为有效的方法。

PS：28楼的评价方法已订正，订正前的方法是我以前用过的，订正的方法是现在发布的程序中使用的。

aoe1981

三坛老窖 发表于 2018-2-8 22:07
看你贴出的结果，应该说这两天你的代码进步大大的。

我上面提到的那个斯洛伐克（不是捷克）的软件，是 ...

　　试了一下，是１５０５——１７模式，图如下：
　　

　　

　　

　　英文差，不太会用。没您的牛！有国际视野，更牛！！！

　　感觉一个软件的包装部分的工程量真的比核心算法的工程量还要大得多！

aoe1981

　　

　　您发表的这个评价指标公式与我的理解一致了：
　　“指标=方式的有效长度 / 棒料长度+系数1×方式最大可重复次数+系数2 x（方式中可包含的最大零件数 - 方式中包含的零件个数 ）
　　方式中可包含的最大零件数 = 最长棒料长度 / 最短零件长度”

　　这里我所说的“一致”不是说具体使用方法上的完全吻合，而是概括的认识、思想的暗合。
　　设对于某一根给定规格的原料：A1，其可开料的零件的集合是：A1={a,a,……b,……c,……d,……,e……}，则任一可行下料组合都是该集合的一个子集。假设这样的子集一共有m个（或者干脆就是下料组合数m个），对于一个可接受的原料利用率 i ，假设为98%，其对应的子集数为 ni 个，则这 ni 个子集应当是我们重点考察的对象。
　　如何筛选出这个子集 ni 是一件困难的事，且不说一次性的筛选，实际下料过程中，即使同一规格的原料A2、A3、……其对应可用零件的全集也是处于递减变化过程中的。用遍历组合去筛选想想都是恐怖的，而且这个事先给定的可接受原料利用率也不见得就是恰当的。好在这些特点吧与随机筛选倒是吻合。只要尝试组合次数足够，找到一组或者更多组达到 i 的下料组合不在话下，甚至可以模糊 i 的要求，在控制尝试组合的循环次数后，极大可能得到比如：95%，96%，97%，98%，99%，……的下料组合。但是，我们还是想排除那些低效的组合，比如：20%，30%，60%，……怎么排除，当然不是确定的排除，而只是将其入选可能性大大降低，哪怕不幸入选，也会用一定的评价标准将其淘汰。
　　但为什么一定要将原料可接受利用率抬高呢？这一方面是生活常识，一方面也来源于数据观察。那些优异的整体下料方案，尤其最优结果，其方案组成的每一个下料组合的原料利用率都是极高的，极“贪婪”的。如果组成整体下料方案的多个下料组合的原料利用率是低效的、糟糕的，则整体方案必不优秀或至少不是最优。因此，我们可以大致划定：整体优异方案必然建立在单个下料组合的足够“贪婪”的基础之上。
　　但是，同时也应注意：局部极致地“贪婪”未必会营造出整体的优异。怎么处理？就是不要因为有了99%，就拦截了所有其他的比如：98%，97%，……让他们也参与进来，加入到组成最终方案的队伍当中，在更广阔的基础上进行对比择优。这正如大神“三坛老窖”所描述的“抖动”一样，筛东西要筛得好，筛得快，就要把“筛子”抖动起来。
　　怎样让这些组合都参与进来？就要研究他们的特点。每个 i 附近的下料组合其利用率可视为无太大差别，而此时能反映他们特点的便是：可最大开料数x（或曰：某个 Ai 的 ni 个优异子集中的重复个数）、组合零件数y。这两个参数可以成为辨识他们除了利用率 i 之外的两个重要标识。
　　如何利用这3个标识，大神“三坛老窖”给出了极优异的方法。我没有更好的方法，但做法的核心思想是和最新这个方法一致的。一个高利用率的下料组合其可最大开料数x又极大，这种组合对整体优异方案的贡献极大。我不能给出更多正面说明，但反面来看，一个低效组合如果x很大的话，整体方案一定很糟。这就告诉我们：迫不得已时，把低效组合的x降低；反之，就是对于 i 左右的下料组合，我们取x较大者优先。
　　至于组合零件数y，老窖同志一开始给出的评价标准倾向于y较大的优先，我一直不明所以。因为我一开始是倾向于y值小的优先，但当时也找不出理由来说明。现在想了一些，可以说说，也不见得就对。如果让组合零件数y大的优先，则整体上会出现小零件优先而剩余大零件可能性较大的局面。依前所述，可开料零件集合 Ai 是递减的，越到后面，原料所对应零件的开料组合选择空间越是逼仄。如果此时，留下的零件中，小零件居多的话，其组合空间稍大，方案尾部利用率进一步提高的可能性也较大。好在，从上面的评价方法来看，想到一块了，开心啊！！！


　　也没有多少新鲜有用的东西，表达下来，诌了这么多……

三坛老窖

aoe1981 发表于 2018-2-9 10:26
　　试了一下，是１５０５——１７模式，图如下：
　　

从你贴上来的图片看，CutLogic 1D升级过了（界面颜色不一样了），看来我的记忆没有错，我用的版本当时是只能找到1506的，797的能找到798，1870能找到1879的结果，你用797和1870这两组数据试试，看现在能找到什么样的结果？

彼此彼此，我是“雅蠛蝶·系列的，英文是我心头永远的痛。至今没有出过伟光正的管控区域，距离”国际视野“，没有十万八千里，也得有八千十万里。托时代进步的福，所用的浏览器有自动翻译功能，虽然翻译的不够地道，但连猜带蒙也能看个八九不离十。

三坛老窖

aoe1981 发表于 2018-2-9 11:48
　　

　　您发表的这个评价指标公式与我的理解一致了：

你这一帖太精彩了，反复看了几遍，这正是我想说又表述不出来的思想，呵呵，缘分呐……
我这贴的算法思路，有了你的这个补充，可谓是完美无缺了！谢谢啊……

EH中研究算法的真正大神是灰袍法师，可惜法师已淡出EH多年，正应了那句话：哥已退隐江湖多年，但是江湖还有哥的传说。

你用”大神“或”您“来称谓老窖，老窖愧不敢当啊，我们还是以你、我平等相称为好。

aoe1981

三坛老窖 发表于 2018-2-9 14:20
从你贴上来的图片看，CutLogic 1D升级过了（界面颜色不一样了），看来我的记忆没有错，我用的版本当时是 ...

　　一般吧，１８７０跑了３次，依次是１８７９、１８９０、１８９０，耗时感觉较长，３分钟左右吧，我也没准确计时。图如下：
　　

　　

　　

　　

　　

　　

　　哦，原来那个图的横轴就是时间吧，那就不到２分钟。

aoe1981

　　那款国外的软件还是很牛的，跑了几次，平均１６０秒就能得到７９８的结果。比我的强！但与您的存在差距，首先是时间上。

　　

　　

　　

　　
　　至于我的嘛，跑死了得到一个７９９，共对比１００００个方案，总耗时９２０秒……泪崩啊……

　　我的程序当循环次数大了以后效率严重低下，不过多少欣慰的是１０００个方案易得８００的方案。图如下：

　　
　　５００个方案也可以得到８００的

　　

aoe1981

说了这么多，也做了这么多，但其实我一直没有将可最大开料数x引入到下料组合的评价当中，我是坚持用我一开始提到的思路在做：即余料小、组合零件数少的优先，随机循环次数控制贪婪程度。而将可最大开料数只运用于开料环节。

为什么如此因守？一是想看看能走到什么程度，一是由于我写程序的思路如果将x引入评价，必将其从某层循环外嵌入循环内，程序效率会更低更低。唯愿能提高搜索的效率以有所补偿。

我向来是不善于优化程序的，我只是一个半路出家的业余选手，很多问题我首先想到的是自己能不能用VBA做出来，这是我最大的满足。至于优化，呵呵，我不太会刻意在意的。

有功夫了再盗版一下三坛老窖的评价思路。哈哈……

我这个思路中对循环次数的恰当设置依赖性还真是大，下图在２０００个方案中得到了７９９：

三坛老窖

aoe1981 发表于 2018-2-9 17:15
　　一般吧，１８７０跑了３次，依次是１８７９、１８９０、１８９０，耗时感觉较长，３分钟左右吧，我也 ...

这个有些奇怪，跑3次，结果是1879，1880，1880，可以理解，何以会1879，一下蹦到1890？那道是其输出过程中的一个bug？想不通。

三坛老窖

aoe1981 发表于 2018-2-9 19:19
说了这么多，也做了这么多，但其实我一直没有将可最大开料数x引入到下料组合的评价当中，我是坚持用我一开 ...

当切口宽度=0时，余料长度与有效长度（模式中零件长度之和）是一回事，但当切口宽度不等于0时，用余料长度与用有效长度来参与评价模式，差别就大了，尤其是像797这组数据，每1mm上就包含着成千上万个不同的模式。