利用遗传算法求解装箱问题.pdfVIP

( ) 第 24 卷　第 4 期 延安大学学报 自然科学版 V o l. 24　N o. 4 ( ) 2005 年 12 月 Journal of Yanan U niversity N atural Science Edition D ec. 2005 利用遗传算法求解装箱问题 1 2 李大可 , 杨花娥 ( 1. 西安建筑科技大学 理学院, 陕西 西安 710054; 2. 西安文理学院 数学系, 陕西 西安 710063 ) 摘　要: 遗传算法通过编码技术, 运用繁殖、杂交和突变等遗传算子, 对染色体组成的初始种群, 进 行适应度分析, 构成优胜劣汰、适者生存的自然环境, 产生出新的更加优良的种群. 经过若干代的进 化, 最终求得适合问题的最优解. 关键词: 遗传算法; 装箱问题; 遗传算子 中图分类号: T P 301. 6　　　文献标识码: A 　　　文章编号: 1004602X (2005) 1　遗传算法 子总容积条件下, 如何使装入装子物体的总价值最 大. 这里w i、p i 和W 都是正整数, i = 1, 2, …, n. 遗传算法是一种模仿生物遗传与进化过程而得 问题的一个可行解可以用如下二进制字符串表 出的一种随机优化方法, 它是“仿生学”在数学领域 示: X = (x 1 , x 2 , …, x n ) , x i 为如下 01 变量: x i = 1, 中的直接引用. 它利用简单的编码技术和进化繁殖 表示物品 i 被装箱; x i = 0 表示物品 i 未被装箱, i = 机制来表现复杂的现象, 进而提供了一种求解复杂 1, 2, …, n. 从而向量X 就是一个装箱方案. 系统优化问题的通用框架. 由于它不依赖问题的具 装箱问题可以用如下数学模型表述: n 体领域, 不受有哪些信誉好的足球投注网站空间的限制性假设的约束, 不要求 m ax p i ×x i ∑ 一定具有目标函数的解析表达式, 因此, 遗传算法应 i= 1 n 用的领域十分广泛. 遗传算法的主要过程如下. s. t. 　 w ix i ≤W , x i ∈ {0, 1}, i = 1, 2, …, n. ∑ 1) 对研究的变量或对象进行编码形成染色体, i= 1 并随机地建立一个