论文部分内容阅读
摘 要：针对二维矩形装箱问题，在现有IFFA算法的基础上加以改进，提出了IFFA2算法，并将它与单亲遗传算法进行结合构成混合单亲遗传算法来解决二维单箱装箱问题。在算法中，提出了新的的编码方案，并设计了相应的适应度函数和遗传操作，解码时引入了IFFA2算法，将启发式算法与遗传算法进行了有效的结合。
关键词：二维装箱问题；IFFA2算法；碎片；单亲遗传算法
1 引言
装箱问题是指将一些给定的不同尺寸的物品按照要求摆放入有一定容积的容器中，以获得某种最佳的效益。该问题是一个典型的组合优化问题，属于NP-hard问题[1]。可以从不同的角度对装箱问题进行分类，从装箱物体所属空间进行分类，可分为一维、二维及三维装箱问题。
本文研究的是二维装箱问题中的一种。该问题可描述为[2]：给定n个矩形物品集合 和一个宽度为有限值W，高度无限的箱子，其中第 个物品的宽度为 ，高度为 ， 。要求将所有的物品装入箱子中而使所占箱子高度为最小。生产生活中很多实际问题可归结为该类装箱问题，如裁剪、装载、印刷排版、玻璃和木材的切割等等。
早在二十世纪七十年代，人们就开始了对装箱问题的探讨和研究[3]。到目前，提出了大量的解决方法。其中常见的主要有启发式算法和遗传算法等。2006年9月大連海事大学的汤岩等人提出了一种IFFA算法，并将该算法与遗传算法相结合实现了二维装箱问题的求解。
IFFA2算法是一种启发式算法，它是在IFFA算法的基础上进一步做了改进，考虑了碎片利用的一种算法。又将该算法与单亲遗传算法相结合实现了对二维装箱问题的求解。
2 IFFA2算法
2.1 IFFA算法思想及存在的不足
IFFA 算法是汤岩[4]等人提出的一种启发式算法，该算法的主要思想是：每个物品在装箱时寻找高度最小的合适区间装入，当同时有多个高度相等的合适区间时，优先使用造成浪费面积（碎片）最小的方案，在高度和浪费面积都相等的情况下，优先使用最左边的区间。
IFFA算法虽然是一种较优秀的算法，但没有考虑已有碎片的利用，仍会产生较多的浪费空间。
2.2 IFFA2算法的提出
为了得到更合理的布局，本文在IFFA算法的基础上考虑了碎片的利用，提出了IFFA2算法。该算法的主要思想是在将每个物品装箱时，先从目前的碎片中查找看有没有可以装入该物品的碎片，如果有，则将其装入碎片空间中；如果找不到这样的碎片，则按照IFFA算法进行装箱。
在该算法中，首先以箱子的左下角为坐标原点，以箱子所在平面为xoy面建立直角坐标系。由于区间和碎片存在频繁的删除和插入，所以采用了链表的形式来定义区间及碎片，区间按照从左到右的顺序连接在一起。碎片按照宽度由大到小（宽度相同的按高度由大到小）的顺序链接在一起。具体结构如下：
定义碎片结点：
point1 = ^sp；
sp = record
xsp： integer； / /碎片左下角横坐标
ysp： integer； / /碎片左下角纵坐标
wsp： integer； / /碎片宽度
hsp： integer； / /碎片高度
next： point1； / /向前的指针
end；
定义区间结点：
point2 = ^qj；
qj = record
xqj： integer； / /区间左下角横坐标
yqj： integer； / /区间左下角纵坐标（即为该区间的高度）
wqj： integer； / /区间的宽度
next： point2； / /向前的指针
end；
3 基于IFFA2算法的混合单亲遗传算法在二维装箱问题中的实现
遗传算法是模拟生物界优胜劣汰、适者生存的一种自适应搜索算法。在传统遗传算法中，对于顺序编码来说常规的交叉算子往往会出现非法解，为了避免非法解，就得采用一些特殊的交叉算子，同时执行交叉操作后常会使一些较优秀的基因块被破坏，为了避免以上这些问题的产生，本文采用了单亲遗传算法[5]，将其与IFFA2算法相结合来求解二维装箱问题，具体实现如下：
3.1编码
假设所有物品在装箱时都可以进行90°旋转，采用以下的编码方式：先将所有要装箱的物品进行统一编号，一个物品的编号与染色体中一个基因的编码对应，基因的编码可以为正或者为负，且规定，若基因编码为正则表示其对应的物品是直接装入，若编码为负则表示其对应的物品的是旋转90°后再装入。假设有 个要装箱的物品，则在 个物品编号前加上正负号就构成了一条染色体，染色体中每个基因编码与相应物品的编号以及该物品的装箱方式相对应。例如：有6个要装箱的矩形物品，则（-2，6， 5， 3，-1，-4）就是一条染色体，它表示物品的装箱顺序为265314，其中3号、5号和6号物品直接装箱，1号、2号和4号物品旋转90°后再装箱。
3.2解码
个体解码方法：染色体中的基因码与装箱物品编号之间是一一对应的，即染色体中第 个基因码对应的就是第 个要装箱物品的编号，基因码的正负决定该物品的装箱方式。具体装箱过程按照IFFA2算法进行。算法步骤如下：
第1步：把第一个要装箱的物品放入箱子的左下角；
第2步：对于当前要装箱的物品，首先搜索碎片链表，找可容得下该物品的最小碎片将其放入，并修改碎片链表，转向第4步，若找不到则执行第3步；
第3步：找到最低可放置区间将当前物品装箱，并相应修改区间链表，如果需要合并区间，那么在装入物品后将会产生新的碎片，这时还需将新的碎片插入到碎片链表中，转向第4步； 第4步：将当前物品左下角的坐标值放入到事先建立好的位置数组中，转第5步。
说明：在算法执行前要建立一个 的二维数组，用以记录当前种群中各个个体对应的装箱模式下 个物品装箱后其左下角的坐标值，其中： 是装箱物品的个数， 是种群中个体数目。
第5步：若所有物品已装完，则结束；否则转第2步。
3.3 初始种群的产生
在遗传算法中，初始种群的好坏直接影响到算法的求解质量及收敛速度。在生活中有这样的例子：要将一定数量的小米和大豆同装入一个容器中，为了节省空间，在装的时候可以把大豆先装入，然后将小米插入到大豆形成的缝隙中。这里参照上述的例子，先将矩形按照面积从大到小的顺序排列，再将其按已有顺序分成若干组，其中第一组的矩形面积大于第二组的矩形面积，第二组的面积大于第三组的面积，依次类推。然后再采用随机键的方式分别在各个矩形组中随机产生一个矩形排放的先后顺序，最后再将它们按照第一组、第二组等的顺序排列，这样就确定出矩形排放的一个完整的先后顺序。
矩形的放置方式通过产生随机数的方式确定，对于每个矩形，都随机生成一个[0，1]之间的随机数，若随机数大于等于0.5，则该矩形直接放入，若随机数小于0.5，则旋转90°后再放入。
3.4适应度函数
文中装箱问题的装箱目的是装完所有物品后，要使物品的总计高度最小，当几个方案高度相同时，要采用浪费面积最小的方案。选取适应度函数如下：
其中，M是一个足够大的正数，它使得 >0， 为按照某一方案装箱后的高度， 为要装箱的所有矩形面积之和，它是一个常数， vs为当前装箱方案产生的碎片面积之和，A是一个大于0的常数，用作调整参数。
3.5 选择算子
在選择过程中采用轮盘赌选择法和最优个体保存法。
3.6 变异算子
变异可以增加群体多样性，为了保持一定水平的变异率，增大产生新的基因块的概率，从而加快收敛速度，这里对于每个经过选择的个体全部进行变异操作。
采用了以下四种变异算子，在变异时，对于每个个体，随机产生[1，4]之间的整数 ，根据 取值的不同，执行不同的变异操作，具体操作如下（假设装箱物品的个数为n）：
（1）单点基因倒位
随机选取[1，n]上的两个整数确定变异点，然后将位于变异点之间的子串中的基因按照逆序排列。
（2）单点基因移位
随机选取[1，n]上的两个整数确定变异点，然后将位于变异点之间的子串中的基因依次后移，并且把该子串中最后一位基因移到最前面。
（3）多点基因换位
对于一个染色体，先确定一个正整数m，再取[1，m]上的随机数i，然后随机交换i对位置的基因值。
（4）多点基因突变
对于一条染色体，先确定一个正整数t，再取[1，t]上的随机数i，然后随机地改变i个基因的值，即如果原来的值为正，则将其变为负；如果原来的值为负，则将其变为正。
对于一个个体，通过前三种变异可随机改变某些物品的装箱顺序，通过多点基因突变，可随机的改变某些物品的放置方式。
3.7终止条件
本文采用的终止条件是出现早熟情况或达到遗传代数时终止迭代。
4 结束语
装箱问题在现实生产和生活中普遍存在，成功的解决该问题，将对生产生活有重要的指导作用。本文对现有的算法进行了总结分析，进一步提出了新算法，并采用该算法实现了对二维装箱问题的求解，在算法中，设计了相应的编码、种群初始化方法、适应度函数及遗传操作。由于一些客观原因，没有对该算法进行算例试算，下一步将继续研究并编制程序通过算例来验证其有效性。
参考文献
[1] 邢文训，谢金星.现代优化计算方法[M].北京：清华大学出版社，2005：1-47，113-148.
[2]赵素芬.几何布局问题及其应用（一）[J].呼和浩特科技，1993（2）：19-21.
[3]陈胜达.基于遗传与递归的装箱算法研究[D].厦门大学，2006：1-34.
[4]汤岩，胡俊敏，武立丰.一种改进的二维装箱问题的混合遗传算法[J].集美大学学报（自然科学版），2006，11（3）：258-262.
[5]王珍和.用单亲遗传算法解决影片递送问题[D].内蒙古大学，2003：19-26.
作者简介：李玉贤（1982年6月—），女，内蒙古呼和浩特市人，讲师，理学硕士，从事高等数学的教学。
关键词：二维装箱问题；IFFA2算法；碎片；单亲遗传算法
1 引言
装箱问题是指将一些给定的不同尺寸的物品按照要求摆放入有一定容积的容器中，以获得某种最佳的效益。该问题是一个典型的组合优化问题，属于NP-hard问题[1]。可以从不同的角度对装箱问题进行分类，从装箱物体所属空间进行分类，可分为一维、二维及三维装箱问题。
本文研究的是二维装箱问题中的一种。该问题可描述为[2]：给定n个矩形物品集合 和一个宽度为有限值W，高度无限的箱子，其中第 个物品的宽度为 ，高度为 ， 。要求将所有的物品装入箱子中而使所占箱子高度为最小。生产生活中很多实际问题可归结为该类装箱问题，如裁剪、装载、印刷排版、玻璃和木材的切割等等。
早在二十世纪七十年代，人们就开始了对装箱问题的探讨和研究[3]。到目前，提出了大量的解决方法。其中常见的主要有启发式算法和遗传算法等。2006年9月大連海事大学的汤岩等人提出了一种IFFA算法，并将该算法与遗传算法相结合实现了二维装箱问题的求解。
IFFA2算法是一种启发式算法，它是在IFFA算法的基础上进一步做了改进，考虑了碎片利用的一种算法。又将该算法与单亲遗传算法相结合实现了对二维装箱问题的求解。
2 IFFA2算法
2.1 IFFA算法思想及存在的不足
IFFA 算法是汤岩[4]等人提出的一种启发式算法，该算法的主要思想是：每个物品在装箱时寻找高度最小的合适区间装入，当同时有多个高度相等的合适区间时，优先使用造成浪费面积（碎片）最小的方案，在高度和浪费面积都相等的情况下，优先使用最左边的区间。
IFFA算法虽然是一种较优秀的算法，但没有考虑已有碎片的利用，仍会产生较多的浪费空间。
2.2 IFFA2算法的提出
为了得到更合理的布局，本文在IFFA算法的基础上考虑了碎片的利用，提出了IFFA2算法。该算法的主要思想是在将每个物品装箱时，先从目前的碎片中查找看有没有可以装入该物品的碎片，如果有，则将其装入碎片空间中；如果找不到这样的碎片，则按照IFFA算法进行装箱。
在该算法中，首先以箱子的左下角为坐标原点，以箱子所在平面为xoy面建立直角坐标系。由于区间和碎片存在频繁的删除和插入，所以采用了链表的形式来定义区间及碎片，区间按照从左到右的顺序连接在一起。碎片按照宽度由大到小（宽度相同的按高度由大到小）的顺序链接在一起。具体结构如下：
定义碎片结点：
point1 = ^sp；
sp = record
xsp： integer； / /碎片左下角横坐标
ysp： integer； / /碎片左下角纵坐标
wsp： integer； / /碎片宽度
hsp： integer； / /碎片高度
next： point1； / /向前的指针
end；
定义区间结点：
point2 = ^qj；
qj = record
xqj： integer； / /区间左下角横坐标
yqj： integer； / /区间左下角纵坐标（即为该区间的高度）
wqj： integer； / /区间的宽度
next： point2； / /向前的指针
end；
3 基于IFFA2算法的混合单亲遗传算法在二维装箱问题中的实现
遗传算法是模拟生物界优胜劣汰、适者生存的一种自适应搜索算法。在传统遗传算法中，对于顺序编码来说常规的交叉算子往往会出现非法解，为了避免非法解，就得采用一些特殊的交叉算子，同时执行交叉操作后常会使一些较优秀的基因块被破坏，为了避免以上这些问题的产生，本文采用了单亲遗传算法[5]，将其与IFFA2算法相结合来求解二维装箱问题，具体实现如下：
3.1编码
假设所有物品在装箱时都可以进行90°旋转，采用以下的编码方式：先将所有要装箱的物品进行统一编号，一个物品的编号与染色体中一个基因的编码对应，基因的编码可以为正或者为负，且规定，若基因编码为正则表示其对应的物品是直接装入，若编码为负则表示其对应的物品的是旋转90°后再装入。假设有 个要装箱的物品，则在 个物品编号前加上正负号就构成了一条染色体，染色体中每个基因编码与相应物品的编号以及该物品的装箱方式相对应。例如：有6个要装箱的矩形物品，则（-2，6， 5， 3，-1，-4）就是一条染色体，它表示物品的装箱顺序为265314，其中3号、5号和6号物品直接装箱，1号、2号和4号物品旋转90°后再装箱。
3.2解码
个体解码方法：染色体中的基因码与装箱物品编号之间是一一对应的，即染色体中第 个基因码对应的就是第 个要装箱物品的编号，基因码的正负决定该物品的装箱方式。具体装箱过程按照IFFA2算法进行。算法步骤如下：
第1步：把第一个要装箱的物品放入箱子的左下角；
第2步：对于当前要装箱的物品，首先搜索碎片链表，找可容得下该物品的最小碎片将其放入，并修改碎片链表，转向第4步，若找不到则执行第3步；
第3步：找到最低可放置区间将当前物品装箱，并相应修改区间链表，如果需要合并区间，那么在装入物品后将会产生新的碎片，这时还需将新的碎片插入到碎片链表中，转向第4步； 第4步：将当前物品左下角的坐标值放入到事先建立好的位置数组中，转第5步。
说明：在算法执行前要建立一个 的二维数组，用以记录当前种群中各个个体对应的装箱模式下 个物品装箱后其左下角的坐标值，其中： 是装箱物品的个数， 是种群中个体数目。
第5步：若所有物品已装完，则结束；否则转第2步。
3.3 初始种群的产生
在遗传算法中，初始种群的好坏直接影响到算法的求解质量及收敛速度。在生活中有这样的例子：要将一定数量的小米和大豆同装入一个容器中，为了节省空间，在装的时候可以把大豆先装入，然后将小米插入到大豆形成的缝隙中。这里参照上述的例子，先将矩形按照面积从大到小的顺序排列，再将其按已有顺序分成若干组，其中第一组的矩形面积大于第二组的矩形面积，第二组的面积大于第三组的面积，依次类推。然后再采用随机键的方式分别在各个矩形组中随机产生一个矩形排放的先后顺序，最后再将它们按照第一组、第二组等的顺序排列，这样就确定出矩形排放的一个完整的先后顺序。
矩形的放置方式通过产生随机数的方式确定，对于每个矩形，都随机生成一个[0，1]之间的随机数，若随机数大于等于0.5，则该矩形直接放入，若随机数小于0.5，则旋转90°后再放入。
3.4适应度函数
文中装箱问题的装箱目的是装完所有物品后，要使物品的总计高度最小，当几个方案高度相同时，要采用浪费面积最小的方案。选取适应度函数如下：
其中，M是一个足够大的正数，它使得 >0， 为按照某一方案装箱后的高度， 为要装箱的所有矩形面积之和，它是一个常数， vs为当前装箱方案产生的碎片面积之和，A是一个大于0的常数，用作调整参数。
3.5 选择算子
在選择过程中采用轮盘赌选择法和最优个体保存法。
3.6 变异算子
变异可以增加群体多样性，为了保持一定水平的变异率，增大产生新的基因块的概率，从而加快收敛速度，这里对于每个经过选择的个体全部进行变异操作。
采用了以下四种变异算子，在变异时，对于每个个体，随机产生[1，4]之间的整数 ，根据 取值的不同，执行不同的变异操作，具体操作如下（假设装箱物品的个数为n）：
（1）单点基因倒位
随机选取[1，n]上的两个整数确定变异点，然后将位于变异点之间的子串中的基因按照逆序排列。
（2）单点基因移位
随机选取[1，n]上的两个整数确定变异点，然后将位于变异点之间的子串中的基因依次后移，并且把该子串中最后一位基因移到最前面。
（3）多点基因换位
对于一个染色体，先确定一个正整数m，再取[1，m]上的随机数i，然后随机交换i对位置的基因值。
（4）多点基因突变
对于一条染色体，先确定一个正整数t，再取[1，t]上的随机数i，然后随机地改变i个基因的值，即如果原来的值为正，则将其变为负；如果原来的值为负，则将其变为正。
对于一个个体，通过前三种变异可随机改变某些物品的装箱顺序，通过多点基因突变，可随机的改变某些物品的放置方式。
3.7终止条件
本文采用的终止条件是出现早熟情况或达到遗传代数时终止迭代。
4 结束语
装箱问题在现实生产和生活中普遍存在，成功的解决该问题，将对生产生活有重要的指导作用。本文对现有的算法进行了总结分析，进一步提出了新算法，并采用该算法实现了对二维装箱问题的求解，在算法中，设计了相应的编码、种群初始化方法、适应度函数及遗传操作。由于一些客观原因，没有对该算法进行算例试算，下一步将继续研究并编制程序通过算例来验证其有效性。
参考文献
[1] 邢文训，谢金星.现代优化计算方法[M].北京：清华大学出版社，2005：1-47，113-148.
[2]赵素芬.几何布局问题及其应用（一）[J].呼和浩特科技，1993（2）：19-21.
[3]陈胜达.基于遗传与递归的装箱算法研究[D].厦门大学，2006：1-34.
[4]汤岩，胡俊敏，武立丰.一种改进的二维装箱问题的混合遗传算法[J].集美大学学报（自然科学版），2006，11（3）：258-262.
[5]王珍和.用单亲遗传算法解决影片递送问题[D].内蒙古大学，2003：19-26.
作者简介：李玉贤（1982年6月—），女，内蒙古呼和浩特市人，讲师，理学硕士，从事高等数学的教学。