一维下料问题--遗传算法求解

Aug. 23th, 2016


遗传算法 下料问题 数模

最近搞数模又用到了之前写的一篇论文里用的遗传算法,但是因为问题差别还是比较大,所以基本又重新实现了一遍,因为时间比较紧,基本没有考虑复杂度的问题,所以还有很大改进的余地,这里把基本的思想阐述一下。

问题简述

“下料问题(cutting stock problem)”是把相同形状的一些原材料分割加工成若干个不同规格大小的零件的问题。

现考虑单一原材料下料问题. 设这种原材料呈长方形,长度为$L$,宽度为$W$,现在需要将一批这种长方形原料分割成$m$种规格的零件, 所有零件的厚度均与原材料一致,但长度和宽度分别为$(l_1,w_1),\dots ,(l_m,w_m)$,其中$w_i<l_i<L,w_i<W,i=1,2,\dots ,m$。$m$种零件的需求量分别为$n_1,\dots ,n_m$。下料时,零件的边必须分别和原材料的边平行。这类问题在工程上通常简称为二维下料问题。特别当所有零件的宽度均与原材料相等,即$w_i=W,i=1,\dots ,m$,则问题称为一维下料问题。

考虑用材料既少,下料方式又少的下料方案。这里简化为考虑所用材料最少的模型及增加一种下料方式大致相当于使原材料总损耗增加$0.08\%$情况下的最佳方案。

具体数据:原材料长度为$L=3000mm$,完成有$53$种不同长度的零件的下料任务,需求零件长度和数量为$l_i,n_i,i=1,\dots ,53$,每次切割产生$5mm$的损耗。

遗传算法实现

编码方式

经过计算,整个生产过程共生产$3970$个零件,这里把$n$个长度为$l$的一种零件看作是长度均为$l$的$n$种零件,每种只有一个,也就是将需要生产的所有零件都平铺开来,就变成了要生产$3970$个长度可同可异的零件。接下来定义这样的编码:

一条染色体上共有$3970$个基因,位与第$i$个位置上的基因的值$k$表示生产第$i$个零件的原材料的编号为$k,k\le 3970$。

如下图所示: 共需生产$5$个零件,使用了$2$块原材料,每块原材料对应一种切割方式。

初始种群的生成

初始种群采用FFD(first fit decrease)的方法生成,相当于有若干原材料闲置备用,遍历所有待生产零件的长度,一旦发现原材料$k$剩余的长度可以生产零件$i$,就将生产零件$i$的原材料设为$k$,反应在染色体上就是第$i$个基因的值为$k$。 如图所示: 从图中可以明显看出来,遍历零件的顺序对于结果有很大的影响,特别是零件数目很大时,一个合适的遍历顺序就可以减少原材料的使用(同时满足BFD best fit decrease),也就达到了降低损耗的目的。 而在程序实现时,不同的遍历顺序就体现为改变不同长度的零件的编号,这里采用同种长度的零件在遍历时放在一起的策略,主要是考虑到切割方式数目也作为优化的目标之一。具体做法为:

假设保存每种零件长度的数组为L,保存每种零件要生产的零件数目的数组为N,其中长度为L[i]的零件要生产N[i]个。 接下来生成$53$个在区间$[0,52]$内的互异的随机整数,保存在数组T中,令

newN[i]=N[t[i]]
newL[i]=L[t[i]]

那么在遍历的过程中根据数组N中每种零件要生产的数目从左到右遍历,就可以达到不同长度的零件放置在原材料上的顺序不同的目的。经过这样的操作,每一种排列都对应一条染色体,就可以产生许多代表不同下料方案的染色体,作为初始种群。

解码方式(适应度值计算)

根据问题描述,假设零件生产完后所有原材料的剩余长度为$R$,原材料切割方式为$t$种,那么需要优化的目标为:

$$ min\quad R+R\centerdot t\centerdot 0.08\% $$

接下来的工作就是根据染色体上的信息推算出$R$和$t$的值。 首先,一种生产方案所使用的原材料的数量$m$为一条染色体上所有基因的值中的最大值。那么$\quad R=3000\centerdot m-零件总长度\quad$ 接下来,对于$[1,m]$中的每一个值,都遍历整个染色体,可以得到每个原材料加工了哪些长度的零件。对每一个原材料生产的零件都进行排序,再过滤掉进行相同加工方式的其余的原材料,就可以得到加工的方式数$t$。进而就可以求得每条染色体的适应度值。还要注意一点,适应度值越大的个体越容易存活下来,而上述的目标函数值越小越好,这里可以采用取倒数等方法是目标函数变为越大越好。

交叉变异过程

交叉过程和变异过程本身并没有太大的难度。交叉即是取两个染色体,将其中的某段基因互换,对于本问题来说,只要保证交换的长度相同(长度不同会导致染色体长度改变,也就是生产零件的数目改变,有悖题意)即可;变异要求相同,这里采用的是选取染色体中的一段,然后对调其间的所有基因的值。

关键在于经历过交叉和变异之后产生的新染色体不一定具有合理的意义,因为原材料的长度是有限制的。比如$i$号基因(第$i$个零件)的值为$k$(由第$k$个原材料生产),但是交换之后$k$变成了$j$,可能出现第$j$号原材料已经没有足够的剩余长度用来生产零件$i$的情况,因此要对新染色体进行调整。

调整过程如图所示: 得到新的染色体后,先找出所有原材料生产了哪些零件(包括零件的长度$l$和零件的编号$i$,也就是在染色体中的位置),对于生产的零件超出长度限制的原材料,逐个将零件移出原材料,直到剩余长度非负为止。而对于移出的原材料,保存其长度$l$和位置$i$先放置在一边。对所有原材料都经过上述步骤之后,将所有移出的零件再以与初始化种群时相同的方式(FFD)遍历所有原材料,并放置在合适的原材料$k$上进行加工(即将第$i$个基因的值改为$k$)。

选择过程

这里采取精英保留策略和轮盘赌策略结合的方式。首先计算出所有染色体的适应度值,然后计算出平均值,将适应度值超出平均值1.2倍(经验数值)的个体选出来作为下一代的初始种群,余下的一部分按照适应度值的大小设置被选中的概率,然后为每个个体设置一个在区间$[0,1]$内的子区间,之后产生$[0,1]$之间的随机数,落在哪个范围内,就将对应的个体选出来。

算法存在的问题

  1. 初始种群时随机的程度不够。在遍历的过程中,总是将某种长度的零件“生产”完后再考虑下一种,这限制了一部分切割方式,以至于算法很难达到最优解。曾经尝试使用$[0,3969]$之间的随机数进行重排,也就是每一个零件都作为一种单独的类别,但计算出的结果中的下料方式数特别多,而且算法迭代上百代后依旧很难收敛,因此也舍弃掉了。这一部分还有待提高。
  2. 在计算下料方式数时,去除重复的下料方式采用了遍历的方法,也就是对每个原材料的分割方式,都遍历所有其他原材料的分割方式,看是否相同,如果重复,则打上‘重复’的标记。这种算法复杂度比较高,应该先对所有原材料的下料方式进行排序(先按所生产的长度最小的零件排序,若相同,按次小的零件排序...),之后只要遍历一遍所有原材料即可得到下料方式数。
  3. 在生成遍历顺序的过程中(产生$53$个随机数确定遍历顺序),每一个染色体(程序中作为一个数组chro)都有自己对应的L数组和N数组,造成了空间利用上的浪费。可以考虑在对每个零件遍历原材料时更改原材料的编号而不是零件的编号,用到的空间会少一些。

$The\ \ end\ !$