人工智能|套裁问题之踩坑记蚁群算法|Python

前些天一个老哥要我做个板材套裁的东东，我看了下觉得很简单，结果一脚就踩了个大坑。
套裁就是在板材加工之前如何裁板，就是从指定规格的原材中如何最小消耗的裁出需要数量的各种板材。我一想，这不就是个背包问题吗，结果做起来才发现想得太简单了，在第一步就晕了：如何找出所有可用的背包（即如何放置待切割板材）。
套裁问题和背包问题最大的区别就是面积之和上能放下的未必就能符合放入的矩形不能重合的约束，所以套裁需要对放置进来的矩形进行定位。也就是说，将要切割的矩形放到原材中时，是需要确定放到哪里才可以的。而通常的背包问题则只要简单的算下数量之和就可以了，也就是说，套裁其实是在通常的背包问题上还要满足特定放置点的约束。
这些特定放置点其实就是原材和已经放入的矩形的四个顶点，每个顶点可以有四个方位、横竖两个方向进行尝试放置，算法思路很简单，用迭代就ok了，但问题在于，每放一个矩形就可能多了三个顶点，而当待放入的目标矩形和大板大小差得比较多时，这就演变成了一个比指数增长还可怕的计算问题。
我一开始理解错了一个板的切割问题时，加入了一个远小于原材的小矩形时，等了二十分钟，发现怎么还在算？！我有些奇怪，就打了个debug，看到的情况是：

27个顶点（重合的点会被吸收掉，放到其它边上而且已经没有了可放置方位的点也会被吸收掉）
迭代深度达到了24（即已经放入了23个矩形，现在正在尝试放入第24个）

我们简单估算下：27个顶点，每个顶点有8个放置方案，每个放置方案要测试24个矩形，即一趟需探测：27*8*24=5184（当然有很多重复，但这不重要），是不是很小意思啦，然后，请24次方！！也就是2的快300次方了，而现在的cpu才只有64位啊！
我这才意识到自己把问题想简单了，虽然这种估算是用最后一次迭代的数据来估之前的情况，会大大的放大计算量，但计算量到了这个地步，这种估算的误差已经可以不必太计较了。
因为已经答应了老哥，总不能食言啊，只好暂时放过这个问题，在用尽了洪荒之力终于暂时控制住了这个问题的复杂度之后，才发现这个小板竟然是开在另一个板子上的，我根本不需要管的，当时真是有一口血喷在屏幕上的感觉啊:(
这个第一步其实就相当于背包问题中找出各种背包的过程，所以在暂时控制住了包包的复杂度之后，问题就回到了背包问题的正轨。这就简单了，我之前介绍过用蚁群算法来解决这类问题，所以蹭蹭蹭就写好了算法，可执行结果依然让我吐血：我头一次见到在这样复杂的问题上，计算机竟然输给了人！！
老哥给了我一个类似软件的计算结果，是96张原材，可他们自己手算的结果是94张原材，还只需要3种切割图案就可以了，可我算了一两天最好的结果都要用到104张原材！想了半天不得要领，甚至把老哥他们的手算结果自己都算了好几次，最后还是得回来检查自己的算法。
开始的时候，我是按将石头往背包里放（即将每个需要切割的板材向原材中放）的思路，这种方法看来有些不对头，所以干脆调整成拿着背包找石头（即在每张原材中放板材，放不下了则换张新的原材），一通昏天暗地的调整之后，嗯，结果很明显啊，我也终于算出96张了！！
真是被打败了，在计算机这么擅长的的问题上计算机竟然会输给了人？！
然后就是开始调整算法的各种参数，可调了一天，就只能算到96张，这怎么可能呢？！对于这样存在着相当大数量最优解的问题，蚁群算法是一定可以找出来的啊？！我思来想去，最后只好跟踪算法是如何一步步添加矩形的，才终于发现了问题。在之前讨论蚁群算法的文章里，我说过蚂蚁在挑选自己的下一步时要依靠两种信息：

【人工智能|套裁问题之踩坑记】整个蚁群对于最优解的综合意见，即各边上遗留下来的信息素
问题自身的启发性知识所给出的优化方向

这里的问题就在于这个启发性知识。一般来说，蚁群算法作为一种高效的元算法，其对启发性知识并不是很依赖，一般只需要提供一个优化方向就可以了，毕竟蚁群算法是依靠成群的蚂蚁组团血拼，即是以规模用量（尽可能多的探索）来降低对质（领域知识上的深刻）上的要求，这也是其可以作为一种应用广泛的元算法的原因所在。但在套裁问题上，显然出了点问题。
本来，我认为这个启发性知识就是尽量提高原材的利用率就可以了，但看过各个矩形的添加顺序后发现，由于小矩形的组合比较有利于提高利用率，所以这种启发性知识的设置导致了小矩形会被优先挑选走，而在大量的小矩形被挑走后，再增加大矩形，就没有合适的小矩形可以和大矩形进行配对了。
找到原因就好办了，我调整了启发性知识的计算方法，即在每个原材增加第一个矩形时优先挑选大矩形。当我满怀信心的再次运行算法后，咦？！怎么竟然会没有效果呢？！再仔细一研究，原来，先挑大矩形会导致第二大的矩形一直得不到挑选，直到最大的矩形挑完后，终于可以开始挑次大矩形的时候，小矩形也都被挑的七七八八了。意识到这个问题后，自然就明白了这个启发性知识就是在挑第一个矩形时既要尽量先挑大的，还要尽量先挑剩余数量多的。
然后再试，哦，95张了，我是该笑呢，还是该哭呢:(
不过，有了每张原材是如何挑第一个矩形的经验，我自然也就看到了解决问题的曙光：问题肯定出在了后继矩形该怎么挑上了。
后继矩形的挑选其实就是尽量先挑可以提高原材利用率的，还要尽量先挑剩余数量多的。
按这个思路重新调整了启发性知识后，ok，终于，终于，终于，我也算出了94张啦:)
反思下本次踩坑的经验教训：

套裁问题和背包问题最大的区别就在于，背包问题只有一个约束：即包的重量。而套裁问题其实是一个多约束的问题，即存在：各矩形数量限制、总利用率和原材规格限制。对于这样的多约束问题，就需要对启发性知识加以深化，以避免过于偏向某一个方向进行优化，而导致陷入其它约束中产生反作用
一开始将矩形往原材中放置时效果很差，其原因乃在于蚁群算法建立的应是事物间的直接联系，如背包问题中的包和石头、之前斗地主挑牌型时的牌手和牌力，但我开始在费了很大气力挑出了所有如何在原材中放置各个矩形的切割图案之后就将注意力集中在这个矩形放置的切割图案上了，也就是说，我虽然开始似乎是在将矩形放到原材中，其实是在将矩形向各个切割图案里放，矩形和原材之间增加了一个切割图案的匹配，导致这两者之间变成了间接关系。而后来的调整其实就是恢复了矩形和原材之间的直接关系，而切割图案则只是在寻找矩形时的一种建议和约束而已。这才能看到这一调整后，算法在效果上产生了明显的提升

总的来说，套裁问题其实是一个多约束问题，而多约束问题的解决显然需要对各约束的平衡进行小心的权衡与调整，这就需要反复的运算以寻找到合适的平衡点。
最后，对比人配置的结果，程序还有一个很明显的缺陷，即人可以只用3种切割图案就完成这个最优的套裁方案，而我即便是放出了500只蚂蚁，反复计算了500次，最好的也不过是17种切割图案。难道，人还真能在这个问题上打败计算机吗？！
我仔细研究了老哥所给的板材规格的数据，发现这是一组经过精心设计的特定规格，也就是说这些板材规格和原材规格之间有着非常明显的匹配关系，人进行配置其实就是按照这种匹配关系直接套就可以了。这就使得人所配置出来的方案，其实存在着一种更强的约束。而当一次需要套裁出的成品数量上升时，可以产生最优套裁方案的切割图案会指数性上升，想在成千上万种可行的切割图案中找到这么独特的切割图案是极小概率的运气，除非加入这种特定约束，否则是根本不可能的。
而如果打破这种匹配关系，显然人就不行了。当我逐步缩小原材规格，使得人的这种特定匹配关系不再成立时，得到了一个有趣的结果：

原材规格原本为2500*1300，这时的原材利用率约为90%
当我将原材规格调整为2300*1300，我所计算出的原材利用率达到了95%多一点

也就是说，人的这种配置方案，其实是用原材的冗余或说浪费为代价来实现的，而这种代价的成本显然是非常高昂的，导致成本起码提高了5%啊:(
====================================================================================================
关注我的公众号及时获取推送的最新文章