混合遗传算法在有色装箱问题中的应用

1、混合遗传算法在有色装箱问题中的应用邱玉良,刘志忠河海大学应用数学 (系 ,南京 (210098E-mail :摘 要 :有色装箱问题是经典装箱问题的推广,它在多处理器实时计算机系统的任务调度等 实际问题中有着很强的应用背景。为了更好的解决这个问题,本文将 C-BF (有色最佳适应算 法 与改进的遗传算法相结合, 给出了一种新的混合遗传算法, 用随机产生实例的方法对本文 的算法和文献中的近似算法做了比较,结果表明用本文的算法求解有色装箱问题效果比较好。 关键词 :装箱问题;有色装箱;混合遗传算法;有色最佳适应算法1. 引言经典装箱问题是把一定数量的物品放入容积 相同的一些箱子中,要求每个箱子中物

2、品体 积之和不超过箱子的容积并且所用的箱子数 目最少。有色装箱问题是经典装箱问题的推 广,它最初是在支持容错的多处理器实时计 算机系统的任务调度中被提出来的 1,在计 算机科学和工业领域中,有着广泛的应用背 景,包括多处理器任务调度、内存管理、资 源分配、运输计划等,因此对其求解具有广 泛的应用价值。从计算复杂性来讲,装箱问题是一个经典的 NP 完全问题 2,很难精确求解,由于目前 NP 完全问题不存在有效时间内求得精确解 的算法,因此就出现了各种求解装箱问题的 近似算法如:下次适应 (NF、首次适应 (FF、 降序适应 (FD、 降序下次适应 (NFD、 最佳适 应 (BF等 3, 文献 4

3、5已经表明有色装箱问 题也是 NP 完全问题,与经典装箱问题一样, 出现了一些求解此问题的近似算法。这些近 似算法比较容易实现,运算速度快,各自有 其自身的优点与不足,但它们都不具有通用 性,并且在某些情况下的结果也不理想。为 了更好地求解有色装箱问题笔者提出了一种 启发式混合遗传算法。遗传算法 (GA(其详 述参见 7作为一种有效的全局并行搜索工 具,具有简单、通用、鲁棒性强的特点,且 无需过多的专业知识。近年来其在求解最优 化问题中得到了越来越广泛的应用,它的基 本思想是将某种编码技术作用于被称为个体 的二进制串 (也可以采用其它方式 , 然后模 拟有这些串组成的群体的进化过程,对这些 群

4、体进行选择操作、交叉操作、变异操作, 通过寻求群体进化中的最优个体,得到所求 问题的最优解。它的主要特点是擅长全局搜 索, 而局部搜索不足, 且容易出现早熟现象, 研究表明, GA 可以用极快的速度达到最优解 的 90%, 但要达到真正的最优解要花费相当 长的时间,解决这一问题的方法可考虑对简 单 GA 进行适当的改进,目前最为活跃的研 究领域是考虑 GA 与其它方法集成,即混合 遗传算法。在这里, 笔者将 GA 与 C-BF 算法相结合, 构 成一种启发式混合遗传算法(G-CBF 对有 色装箱问题进行了求解。C-BF 算法(有色最佳适应算法 :在对有色 物品进行装箱时,把待装物品装入这样的已

5、 打开的箱子里(把已经装过物品的箱子称为 已打开的箱子 (1待装物品的颜色与箱子中 所有物品的颜色都不相同; (2箱子所剩容积 大于物品体积,且与物品体积最接近;如果 没有这样的已打开的箱子则把待装物品装入 一个新箱子;直到所有物品都被装入箱子为 止。2. 有色装箱问题及其算法2.1 问题描述有色装箱问题:给定 n 个物品的一个序列 12, , , n nL a a a=L,物品(1 ia i n 的大小( (0,1i v a ,颜色 (1 i C i k ,其中物品 的 颜 色 数 目 为 (, K K N K 是常数 ,21, , B B L为一个由单位容积的箱子组成的无限序列。要求:每一

6、物品只能装入到唯一的箱子中, 每一个箱子中物品大小之和不能超过 1,同 一个箱子中物品的颜色互不相同,如何使用 最少的单位容积的箱子,装下所有的物品?2.2 数学模型令12, , , n n L a a a =L 为任意给定的 n个物品的一个序列, 物品 (1 i a i n 的大小( (0,1i v a ,颜色 (1 i C i k ,其中物品的颜色数目不超过 (, K K N K 是常数 , 若 设所用的箱子数为 m , 将这 m 个箱子按被用 的 先 后 顺 序 分 别 记 为12, , , m B B B L , 记(1, 2, , j B j m =L 号箱子中所装物品的下标集为jI

7、 ,对于jI 内的任意两个元素 p 、 q , 必须满足p q C C ;令(j f B 表示装入箱子jB 中的所有物品的体积之和。因此有:min m121211( 1, , , 1, 2, , . ( (, 1,2, , ( ( jj k j k k k I j k k I m nj i j i v a k k I C C j m s t f B v a j m f B v a =K K 、2.3 已有的算法KC-A 算法 4:首先把箱子分成 K 类, 物品 序列中第 i 个具有这种颜色的物品只能装在 第 i 类箱子中, 从而保证相同颜色的物品不会 出现在同一类箱子中,然后在任何一类箱子 类

8、内部,物品的放置采用近似策略 A ,我们称这样的算法为以 A 为基础的 K - 分类算 法,记为 KC -A 算法,相应的,当算法采 用 FF 算法时,则得到 KC -FF 算法。 JCBP 算法 5:首先把待装物品以大小为标准 降序排列,从左端把第一个物品装入第一个 箱子 , 然后从右往左依次查看物品, 如果所 查看的物品满足:物品颜色与当前箱(把正在往里面装物品的 箱子称为当前箱内所装物品的颜色都不相 同;物品的体积不大于当前箱的剩余容积; 则把这个物品装入当前箱,并检查下一个物 品,直到没有可以装箱的物品为止,然后打 开一个新箱子,把左端的第一个物品装入, 再从右端开始查找满足条件 (1

9、(2物品并装 箱;如此操作直到所有物品都被装箱为止。 SCPF-A 算法 6:首先把物品按颜色种类分 类,将相同颜色的物品分成一类,放置时按 照相同颜色的物品首先放置的原则,即把具 有颜色1C 的所有物品先分别放在不同的箱子里,然后再处理具有颜色2C 的所有物品,直到把所有颜色的物品都放置完毕,在放置的过程中,相同颜色的物品不能放在相同的 箱子中,每个箱子中物品体积之和不能超过箱子的体积。如果每类物品都采用经典装箱 问题的近似算法 A 放置,则记为 SCPF -A;例如:当算法 A 选取的是 FF 算法时,则得 到 SCPF -FF 算法。3. 基于混合遗传算法求解 3.1 混合遗传算法的实现

10、本文用每条染色体所用的箱子数 m 作为 目标函数,即 ( f X m =。适应度函数设为( ( F X M f X =,其中 ( M f X >。遗传算法中的交叉操作有多种方式,比 如:单点交叉、两点交叉、多点交叉、部分 匹配交叉等。本文采用两点交叉算子,具体 操作如下:一对染色体 A 、 B 进行交配,交 配后,把 A 的交配区域加到 B 的前面得到' B , 把 B 的交配区域加到 A 的前面得到 ' A ;然后在 ' A 中自交配区域后依次删除与交配 区域中的基因相同的基因,得到新的染色体1A ,对 ' B 采用同样的处理方法得到新的染色体 1B ,

11、 这样就得到了两条新的染色体 1A 、1B 。本文应用了两点对换变异算子,其操作过程是:以较小的概率 m p 产生变异基因 g ,然后Step1 初 始 化 设 置 进 化 代 数 计 数 器0t =, 设置最大进化代数 T ,设置群体规模 M , 随机生成 M 个从 1到 n 的全排列作为第一代染色体 (0p ,设置交叉概率 c p ,设置变异概率m p 。Step6 群体 ( p t 经过选择、 交叉、 变异操 作后得到下一代群体 (1 p t +,终止条件判 断,若 t T ,则 1t t =+,转到 Step2;若t T >, 则以进化过程中所得到的具有最大适应度的个体作为最优装

12、箱顺序输出,并输出 所用箱子数 ( M F X (同时可以输出装 箱方案 。4. 算例及与其它算法的比较4.1 算例设L = 0.3(A,0.3(C,0.8(B,0.4(C,0.2(A, 0.5(C,0.7(C,0.3(B,0.7(B,0.9(A,0.5(B, 0.6(B,0.8(B,0.6(A,0.4(C,0.7(A,0.3(C, 0.1(A,0.1(B,0.2(B为给定的物品序列,其中 A , B , C 表示三种 不同的颜色,应用本文的算法,设置 5T =,10M =, 0.5c p =, 0.02m p =,计算结果为:10m =,为最优解。应用 JCBP 算法和 SCPF-A 算法,

13、分别得 12m =和 11m =。4.2 与其它算法的比较笔者应用随机产生实例的方法对本文的算法 和 JCBP算法、 SCPF-A 算法进行了比较, 实验证明本文的算法比起它算法具有更好的 装箱效果,它们的比较结果如表 1所示:表 1 混合遗传算法与其它近似算法的比较物 品 个 数 N 颜色数KSCPF-FFD(箱子数JCBP(箱子数G-CBF (箱 子 数 12 19 51 49 124 156 246 298 405 401 479 473附注:由于文献 56已经验证了 JCBP 算法、 SCPF-A 算法比 KC-A 算法装箱效果好,所 以本文没与 KC-A 算法进行比较。5. 结论通过

14、试验数据可以看出,用混合遗传算法求 解色装箱问题所得到的结果要比用近似算法 得到的结果好。但当物品数量比较大时,问 题变的比较复杂,不好验证本文算法所求得 的解是否为最优解,并且用混合遗传算法求 解的时间开销有点大,这两点有待于做进一 步的研究。 .参考文献1 C L Liu, J Layland. Scheduling algorithms for multi programming in a hard real-timeenvioronmentJ. Journal ofACM.1973,10(1:174-189.2 M R Garey, D S Johnson. Computers and

15、 Intractability: Aguild to the Theory of NP-CompletenessM. New York: W H Freeman and Company ,1978.3 Coffman E G,Garey M R,Johnson D S. Approximation algorithms for bin packing: A surveyA. Hochnaum Ded. Approximation Algorithms for NP-Hard ProblemsC. Boston :PWS Publishing, 1996.46-93.4 顾晓东, 许胤龙, 陈国

16、良, 顾钧 . 有色装箱问题的 在 线 近 似 算 法 J. 计 算 机 研 究 与 发 展 .2002, 39(3:335-340.5 刘春霞,于洪霞 . 有色装箱问题的一种新的近似 算法 J. 佳木斯大学学报 .2005, 23(4:606-609.6 董一鸿,赵杰 . 带约束的一维装箱问题近似算法 的研究 J.计算机工程与应用 .2003, 18:41-44.7 雷英杰,张善文,李续武,周创明 MATLAB 遗 传算法工具箱及应用A Hybrid Genetic Algorithm for Coloring Bin-packing ProblemQiu Yuliang, Liu Zhiz

17、hong2. Dept. of Science, Hohai University, Nanjing (210098AbstractAs one of the constrained bin packing problem(BPP,coloring BPP has many important applications such as multi-processor real-time scheduling, ect. In order to solve this problem better, the paper proposes a new hybrid genetic algorithm, which is combined with C-BF(Coloring-Best Fitand improved genetic algorithm. The results of coloring BPP problems which are randomly produced w