基于免疫遗传算法的装箱问题求解.pdf

　第 2 1 卷 第 4 期 小 型 微 型 计 算 机 系 统 V o l2 1 N o 4　 　　2000 年 4 月 - 　 2000　　 M IN I M ICRO SY ST EM A p r 文 章 编 号:(2000) 04036 103 基于免疫遗传算法的装箱问题求解 曹先彬　刘克胜　王煦法 ( 中国科学技术大学 计算机科学技术系　合肥 230026) 摘　要: 装箱是一类典型的N P 完全问题. 本文用一种免疫遗传算法来研究装箱问题的求解. 免疫遗传算法在传统遗 传算法的全局随机搜索基础上, 借鉴生物免疫机制中抗体的多样性保持策略, 大大提高了算法的群体多样性. 实验表 明, 免疫遗传算法具有很好的全局收敛性, 能有效解决装箱问题. 关 键 词: 装箱问题; 遗传算法; 多样性; 免疫机制 分 类 号: T P 18　　　　　文献标识码: A 1　引　言 散布性. 这对应于 GA 中的群体多样性, 借鉴这一特点可以提 高算法的全局收敛性. 装箱是一典型的组合优化问题. 由于需要考虑维数、形 ( 2) 自我调节能力 免疫系统通过对抗体的相互促进与 状、约束、目标等不同因素, 装箱问题虽然广泛存在于许多领 抑制反应, 能自我调节适当数量的必要抗体. 这对应于 GA 中 〔1〕 域, 但它却远比一般的N P 问题更复杂 . 到 目前为止, 人们 个体基于浓度的协作, 利用这一功能可以提高算法的局部收 〔2, 3 〕 对装箱问题提出了许多算法 , 但都有明显不足: 穷举法在 敛能力. 1 借鉴免疫系统的这些特点, 我们将待求解问题对应 箱子数 目稍大时就存在 组合爆炸; 启发式搜索法引入的启 ( ) 为抗原, 问题的候选解对应为抗体 即待进化个体 , 在 GA 的 发信息依赖于个人经验, 并且同样存在 组合爆炸; 神经网络 基础上引入生物免疫机制, 提出了如图 1 所示的一种免疫遗 方法在解决装箱问题时效果明显, 但它收敛速度慢, 易陷入局 传算法 IGA , 并用来求解装箱问题. 部极优. 遗传算法(GA ) 作为一种随机化搜索算法, 具有很强的全 局搜索能力, 特别适合求出问题的近似最优解, 用 GA 解决装 〔4, 7 〕 箱问题是一可行思路 . 但 GA 本身还存在许多不足, 尤其 在解群分布不均匀时易于出现未成熟收敛, 陷入局部极优. 目 前对基本遗传算法有很多改进的工作, 但为避免未成熟收敛, 〔4, 5 〕 提高群体多样性应是主要改进方法之一 . 对装箱问题而言, 如果能有一种算法, 它以 GA