装箱问题的数学模型如下 :
n
∑ min Z ( y) = yi i =1 n
∑ s . t . j =1 Wjxij ≤ Cyi , i ∈ N
n
∑xij = 1 , j ∈ N
i =1
yi = 0 或 1 , i ∈N xij = 0 或 1 , i , j ∈ N 其中 , yi = 1 表示箱子 i 中被装入物品 ,反之 yi = 0 表示箱子空着 。 xij = 1 表示物品 j 装入箱子 i 中 ,反之 xij = 0 表 示物品未装入箱子 i 中 。 装箱问题是许多具有重要意义的实际优化问题 的基础 , 在管理决策中有重要应用 , 它属于 N P hard 问题 ,目前还没有在多项式时间内求得最优解 的算法 。
基于此考虑 , 将常规遗传算法的染色体编码串 中各基因座位置 (表示箱子) 及相应基因值 (箱子中 的物品) 组成一个二元组 , 把此二元组按一定顺序 排列起来 ,就形成了一种变长度染色体编码方案 。
举例说 ,比如从 1 到 6 对物品进行编码 , 染色体 物品部分可写成 142352 ,这表示 :第 1 个物品放入箱 子 1 ,第 2 个物品放入箱子 4 ,第 3 个和第 6 个物品放 入箱子 2 ,第 4 个物品放入箱子 3 ,第 5 个物品放入箱 子 5 ;而染色体的群体部分仅表示箱子 , 用字母来表 示箱子 (这样 ,上面染色体就可以表示为 ADB CEB ) 。
heuristic algorithm
3 结论
遗传算法不是一种单纯的优化算法 ,而是一种
55
以进化思想为基础的全新的一般方法论 ,是解决优 化等复杂问题的有利工具 。随着遗传算法理论研究 的不断深入 ,其自身的发展将得到进一步完善 ,它的 应用范围将得到进一步扩大 。
参考文献
[1 ] Falkenauer E. A new representation and operators for genetic algorithms applied to grouping problems [ J ] . Evolutionary Computation ,1994 ,2(02) .
2. 2 染色体编码设计 在遗传算法中如何描述问题的可行解 , 即把一
个问题的可行解从其解空间转换到遗传算法所能处 理的搜索空间的转化方法 ,就称为编码 。
由于装箱问题的适应值函数依赖于箱子中物体 的群体 ,因此此问题中好的编码应该包含 2 个部分 : 一部分提供关于哪个物品属于哪个箱子 ( 群体) 的 信息 ,另一部分对使用的箱子编码 。
的隐并行性 、应用的鲁棒性 、操作的简明性 , 成为一
种具有良好普适性和可规模化的优化方法 。
基于遗传算法的装箱问题求解过程主要包括染
色体编码结构及各种遗传算子的设计 。
2. 1 适应值函数
确定适应值函数的原则是 :最小化使用的箱子
数量同时 , 尽量装满所有使用的箱子 。具体函数如
下:
fB PP =
to solve the bin2packing problem
YANG Dian2sheng
( Office of The Dean of Studies , Ezhou University , Ezhou 436000 , China)
Abstract :To solve the bin2packing problem , this paper presented an improved inheritance algorithm of a kind of chromosomes with changeable length and analyzed the concrete methods and steps to realize it . Key words :bin2packing problem ; inheritance algorithm ;
ISSN 100928984
长春工程学院学报 (自然科学版) 2004 年 第 5 卷 第 2 期
CN 22 21 32 3/ N J . C ha ng ch un In st. Te ch . (Nat. Sci. Edi. ) ,2004 ,Vol. 5 ,No. 2
17/ 23 53 25 5
第 1 步 :随机选择 2 个交叉位置 ,对每个父代选 定交叉部分 。
第 2 步 :将第 1 个父代交叉部分的内容插入到第 2 个父代第 1 个交叉位置之前 。由于交叉对染色体的 部分群体进行操作 , 这就意味着从第 1 个父代插入 一些群体 (箱子) 到第 2 个父代中 。
第 3 步 :从产生的后代中原有的箱子中去掉所 有重复出现的物品 , 使得这些物品原先的从属关系 让位于“新”插入的箱子 。因此产生的后代中的某些 群体发生了改变 ,他们不再包含与原先相同的物品 。
收稿日期 :2004 - 04 - 01 作者简介 :杨殿生 (1963 ,8 - ) ,男 (汉) ,安徽明光 ,讲师
主要研究工程数学 , (0711) 3853327 。
针对该问题提出了一些启发式算法 , 他们基本 上都是以贪心法为出发点 , 加上某些简单规则得到 的 ,比如次优配合启发式方法 ( next - f it heuristic) 、 优先配合启发式方法 ( f irst - f it heuristic) 或最佳配 合启发式方法 ( best - f it heuristic) 等 ,但这些启发式 算法都不能实现全局最优 ,只能找到局部最优解 。
交叉指按一定的概率 Pc 选择参与交叉的父代 , 把 2 个父代个体中的部分结构加以替换重组而生成 新个体的操作 ,它是遗传算法区别于其他进化算法 的重要特征 ,在遗传算法中起着关键作用 ,是产生新 个体的主要方法 。
由于染色体编码包含 2 部分 :箱子和物品的群 体 ,因此交叉需处理可变长度的染色体 ,具体步骤如 下:
从群体中选择优胜的个体 , 淘汰劣质个体的操
作称为选择 ,其目的是把优化的个体直接遗传到下 一代或通过配对交叉产生新的个体遗传到下一代 , 它是建立在群体中个体的适应值评估基础上的 。
这里采用联赛选择算子 。其基本方法是 ,从群体 中随机选择 k 个个体 , 其中适应值最高的个体保存 到下一代 ,这一过程反复执行 ,直到保存到下一代的 个体数达到预先设定的数目为止 。其中 ,参数 k 称为 竞赛规模 ,常取 k = 2 。 2. 3. 2 交叉算子
n
∑( Fi/ C)
j =1
N
式中 : N ———解中使用的箱子数量 ;
Fi ——— i 个箱子中所有物品的重量之和 , 即箱
子的填充程度 ;
54
长春工程学院学报 (自然科学版)
2004 ,5 (2)
C ———箱子的重量限制 , k 是常数 ( k > 0) 表 示对装满箱子的重视程度 , k 越大 , 装 得满的箱子比一般填充的箱子受到的 重视就越大 ,这里取 k = 2 。
所谓变异运算 ,就是将个体染色体编码中的某 些基因座上的基因值用该基因座的其他等位基因来 替换 ,从而形成一个新个体 。
与前类似 ,装箱问题的变异算子必须针对群体 (箱子) 而不是物品进行操作 ,至于变异过程 ,算子的 实现细节依赖于现有的特定群体问题 ,但可指出两 条一般性策略 :或启用一个新的箱子 ,或消除一个已 经使用的箱子 。如果变异后解中缺少某些物品 ,可 以采用 FF 或 FFD 启发算法来按照随机的顺序将其 重新放入箱子 。
从遗传算法过程中产生新个体的能力方面来 说 ,交叉运算是产生新个体的主要方法 ,它决定遗传 算法的全局搜索能力 ,而变异运算只是产生新个体 的辅助方法 ,但也是必不可少的一个运算步骤 ,因为 它决定了遗传算法的局部搜索能力 。交叉算子和变 异算子的相互配合 ,共同完成对搜索空间的全局和 局部搜索 ,从而使得遗传算法能够以良好的性能完 成最优化问题的寻优过程 。 2. 4 基于遗传算法的装箱问题算法描述
质特征在于群体搜索策略和简单的遗传算子 , 群体
搜索使遗传算法突破领域搜索的限制 , 可以实现整
个解空间上的分布式信息搜索 、采集和继承 ;遗传算
子仅仅利用适应值度量作为运算指标进行染色体的
随机操作 ,降低了一般启发式算法在搜索过程中对
人机交互的依赖 , 这样就使得遗传算法获得了强大
的全局最优解搜索能力 ,问题域的独立性 、信息处理
通过查询物品部分 , 可以清楚群体名称所代表 的含义 ,即 :
B = { 3 ,6} , E = { 5} , C = { 4} , D = { 2} , A = { 1}
因此 , 包括 2 个部分的染色体的集成可由下图 来表示 :
图 1 染色体集成图
这种表示的原理是 :对于装箱问题来说 ,群体是 有意义的积木块 ,也就是最小的解片断 ,这些片断可 以按照对其所属的解所期望的质量来转运信息 。
而这种表示的关键之处就是遗传算子对于染色 体的群体部分进行操作 , 其物品部分仅用于判定由 哪些物品形成该群体 。 2. 3 遗传操作设计
遗传操作包括以下 3 个基本遗传算子 :选择 、交 叉 、变异 。选择和交叉基本完成了遗传算法的大部分 搜索功能 ,变异增加了遗传算法找到接近最优解的 能力 。 2. 3. 1 选择算子
1 装箱问题及数学模型
装箱问题 ( bin - packing problem) 就是要将重量 分别为 w1 , w2 …, wn 的 n 个物品装入许多个箱子 (最 多 n 个) ,且箱子有重量限制 , 每个箱子所装物品的 总重量不超过 C ( C > 0) 。问题是寻找最优的将物品 分配到箱子的方案 , 使每个箱子中物品的重量之和 不超过其限制 ,而使用的箱子数量最少 。
求解装箱问题的一种变长度染色体遗传算法
杨殿生
(鄂州大学 ,湖北鄂州 436000)
摘 要 :针对装箱问题提出了一种变长度染色体的