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

1、第 24卷第 4期 2005年 12月延安大学学报 (自然科学版 Journal of Yanan U niversity (N atural Science Editi on V o l . 24 N o. 4 D ec . 2005利用遗传算法求解装箱问题 李大可 1, 杨花娥 2(1. 西安建筑科技大学 理学院 , 陕西 西安 710054; 2. 西安文理学院 数学系 , 陕西 西安 710063摘要 :遗传算法通过编码技术 , 运用繁殖 、 , , 进 行适应度分析 , 构成优胜劣汰 、 ,化 , 最终求得适合问题的最优解 .关键词 :遗传算法 ;:T . :A 文章编号 :1004

2、2602X (2005 04200322021 遗传算法遗传算法是一种模仿生物遗传与进化过程而得 出的一种随机优化方法 , 它是 “仿生学” 在数学领域 中的直接引用 . 它利用简单的编码技术和进化繁殖 机制来表现复杂的现象 , 进而提供了一种求解复杂 系统优化问题的通用框架 . 由于它不依赖问题的具 体领域 , 不受搜索空间的限制性假设的约束 , 不要求 一定具有目标函数的解析表达式 , 因此 , 遗传算法应 用的领域十分广泛 . 遗传算法的主要过程如下 . 1 对研究的变量或对象进行编码形成染色体 , 并随机地建立一个初始群体 .2 计算群体中诸染色体的适应度 .3 执行遗传算子操作 .

3、包括 :繁殖 , 将适应度高 的染色体进行繁殖 , 添入到群体中 , 删除适应度低的 染色体 ; 杂交 , 随机选出染色体对 , 基基因进行片段 交叉换位 , 产生新的染色体对 ; 突变 , 随机改变某染 色体的某个基因 , 得到新染色体 .4 根据某种条件判断计算过程是否可以结束 , 如果不满足结束条件 , 则返回到步骤 2, 直到满足结 束条件为止 .装 箱问题也称背包问题 , 它可以表述为一个单 约束的纯整数规划问题 . 设有一个箱子的总容积为 W , 另有 n 个不同的物品 , 其体积分别 w 1, w 2, , w n , 其价值分别为 p 1, p 2, , p n , 问题是在不

4、超过箱 子总容积条件下 , 如何使装入装子物体的总价值最 大 . 这里 w i 、 p i 和 W 都是正整数 , i =1, 2, , n . 问题的一个可行解可以用如下二进制字符串表 示 :X =(x 1, x 2, , x n , x i 为如下 021变量 :x i =1, 表示物品 i 被装箱 ; x i =0表示物品 i 未被装箱 , i = 1, 2, , n . 从而向量 X 就是一个装箱方案 .装箱问题可以用如下数学模型表述 :m ax ni =1p i ×x is . t . ni =1w i x i W , x i 0,1,i =1, 2, , n . 2 应用

5、举例下面我们通过一个经济活动中常见的实际问 题 , 介绍如何利用遗传算法解决装箱问题 , 这是遗传 算法最简单 、 最基本的应用模式 .例 现有 100万元资金打算在 5个不同的地方 修建某种工厂 , 由于条件不同 , 所需投资分别为 :w 1 =56, w 2=20, w 3=54, w 4=42, w 5=15(单位 :万 元 , 工厂建成后 , 每年能得到的利润分别为 :p 1= 7, p 2=5, p 3=9, p 4=6, p 5=3(单元 :万元 . 问如 何确定投资地点 , 使总投资不超过 100万元 , 且使建 成后每年所获总利润最多 ?此 问题可以看成是一种装箱问题 . 其中

6、装箱数 学模型中的参数分别为 :x i 表示在第 i 个地方是否收稿日期 :20050710作者简介 :李大可 (1958 , 男 , 陕西西安市人 , 西安建筑科技大学副教授 .修建工厂 (i =1, 2, , 5 , W =100, n =5, w 1=56, w 2=20, w 3=54, w 4=42, w 5=15, p 1=7, p 2=5, p 3=9, p 4=6, p 5=3, 目标函数 :m ax f (X =7x 1 +5x 2+9x 3+6x 4+3x 5, 约束条件 :g (X =56x 1 +20x 2+54x 3+42x 4+42x 4+15x 5 100. 编

7、码是应用遗传算法首先要解决的问题 , 在遗 传算法的实际应用中 , 根据所研究对象的不同性质 , 将问题的可行解设计成染色体 . 遗传基因也可以取 不同的表示形式 , 在下面的讨论中 , 遗传基因用 0 1码表示 , 这是一种最常用的编码形式 . 遗传算法操作 的对象是用遗传基因表示的染色体 ,.利用 A 1,5, q 0, 015时 , 当该数 q 015, 1时 , 产生一 个基因 1, 这样得到一个由 4个染色体组成的第一代 初始群体 , 不妨设为 :x (1 1=1; 0; 1; 1; 0;x (1 2=0; 1; 1; 0; 0;x (1 3=0; 1; 0; 1; 1;x (1 4

8、=0; 1; 0; 0; 1. 在 遗传算法中 , 适应度是描述群体中染色体优 劣性的尺度 , 在优化问题中 , 适应度是可行解的目标 函数值 . 称 f (x (m i 值为第 m 代染色体 x (m i (i =1, 2, , n 的适应度 . 在本问题中 , 适应度为 :f (X = 7x 1+5x 2+9x 3+6x 4+3x 5.在第一代初始染色体中经过计算可得 :f (x (1 1 =22, f (x (1 2 =14, f (x (1 3 =14, f (x (1 4 =8, 而 g (x (1 1 =152, g (x (1 2 =74, g (x (1 3 =77, g (x

9、 (1 4 =35. 因此 , 染色体 x (1 1不满足题中的约束条件 , 不 是可行解 . 为了解决不可行性 , 需要对不可行解进行 改造 , 使之成为可行解 , 下面利用解码法将不可行解 转化成可行解 .设 X =(x 1, x 2, , x n 是某代种群中的染色 体 , 若 X 的分量 x i =1, 说明该装箱含有物品 i , 其价值和体积分别为 p i 和 w i , Q i =w i为物品 i 的价值与 体积比 . 在本问题中 , 这个比值的经济意义是投资 1万元在第 i 地建厂所能获得的利润 . 根据问题的要 求 , 希望投资的总利润最大 . 如果染色体 X 是不可 行的 ,

10、 则将 X 中所有 x i =1的分量取出 , 将对应的建 厂地区按比例值进行降序排列 . 若 Q i >Q j , 则说明 第 i 地区在设计过程中优先于第 j 地区 . 于是按染色 体 X 中原定方案的适合程度从大到小依次重新确 定建厂地区 , 直到不能再增加 (总金额小于或等于 W 为止 , 这样得到第一代的染色体 X , 并用 X 取 代 X .利用解码法对第一代染色体中的不可行解 x (1 1进行改造 , 使其转化成可行解 x (2 1=1; 0; 0; 0; 0, f (x (1 1=7, 而 g (x (1 1 =56. (其中 1; 0; 1; 0; 0还是 不可行解 需

11、 要说明的是对种群实施各种遗传运算后 , 都 要 检验解 X 的可行性 , 凡是不可行的 , 都可按上述 解码法转化成可行解 .在. x (m 1x (m 2, , x (m n , (i(m k =1f (x (m k , m 代染色体 x (m i 的生存概率 i =1, 2, , n . 它反映了群体中染色体之间的 相对优劣性 . 本问题各染色体的生存概率分别为 :(1 1=22 58=013793, (1 2=14 58=012414, (1 3 =012414, (1 4=8 58=011379. 对这 4个染色进行 4次有放回的随机抽取 , 产生 4个新的染色体 , 显然 , 生存

12、概率大的染色有更大的机会被抽中 . 在对染色 体的抽样方案中 , 总体的随机抽样可以保证优良染 色体被选择的机会增大 , 同时也给劣质染色体一定 生存的机会 . 随机抽样的一种可能性最大的结果是 : x (2 1=x (1 1=1; 0; 1; 1; 0,x (2 2=x (1 2=0; 1; 1; 0; 0,x (2 3=x (1 3=0; 1; 0; 1; 1,x (2 4=x (1 1=1; 0; 1; 1; 0. 这样 , 第二代染色体的适应度比第一代染色体 的适应度有所提高 .在群体中产生新染色体是寻优的必须途径 . 为产 生出新染色体 , 遗传算法还模仿基因突变 , 将染色体 某位

13、基因进行突变 (1变为 0, 0变为 1 , 例如 , 将第二 代染色体 x (2 2=0; 1; 1; 0; 0的第五位基因进行突 变 , 则突变后的新染色体为 :x (3 2=0; 1; 1; 0; 1. 杂 交运算是将群体的染色随机组合成两组 , 在 本例中可选两个染色体为一组 , 不妨设 x (3 1=x (2 1与 x (3 3=x (2 3为一组 , x (3 2与 x (3 4=x (2 4为一组 . 对每一 组再进行一次随机抽样 , 以等概率从 1, 2, 3, 4, 5中 选取一个数 t . 假设随机抽取得 t =2, 那么将同组的 染色体从最低位开始的后 3位互换 , 得到

14、新的染色 体 . 结果是 :x (4 1=1; 0; 1; 0; 0,x (4 2=0; 1; 1; 1; 0,x (4 3=0; 1; 1; 1; 0,x (4 4=1; 0; 1; 0; 0. 如 果将上述的繁殖 、 杂交和突变等遗传运算不 断循环执行下去 , 最终可逼近最优解 (事实上 , 此例 中已得到最优解 f (x (3 2 =17 . 因此 , 该问题的最终 方法为 :在第 2、 第 3和第 5个地方修 (下转第 38页 33第 4期李大可 , 杨花娥 :利用遗传算法求解装箱问题In ternet 环境的自主式学习平台 , 在该平台下 , 教师 提供多种网上教学资源 , 学习者通

15、过网络采用多种 方式 (在线 离线 进行交互学习 。 网络的发展为教育 提供了新的途径 , 为远程教育和终身教育的开展提 供了技术保障 , 进行合理的课程设计 , 为不同类型的 学习者提供个性化的学习支持将是每个教育者神圣 又艰巨的任务 , 相信随着网络技术的不断发展 , 在国 家大力提倡高等教育大众化的鼓舞下 , 会有越来越 多的网络课程出线在我们面前 。参考文献 :1何克抗 . CA I 的理论基础和以学为中心的课件设计 EB OL . h ttp : www . k 12. com . cn .2祝智庭 . CA I 的教学策略设计 EB OL . h ttp : www . k 12.

16、 com . cn .3潘懋德 . 关于辅助教学软件开发方向的思考 EB OL . h ttp : www . U 2. . cn .4黄荣怀 . 网络课程认证标准与优秀课程点评 2003年 . . h i 2edufo rum . com . cn .5张震 . 基于 W eb J . , 3:64. 责任编辑 贺小林 D i ng m ode and i m plem en ti ng m ethods of web -based course L I U Yan 2bao , HAO J i 2sheng(Co llege of M athem atics and Com p u ter

17、 Science , Yanan U n iversity , Yanan 716000, Ch ina Abstract :In ternet m edia in tegrates the characteristics of o ther m edias , w ho se po ssesses are of great in ter 2 acti on . T he designati on and i m p lem en tati on of the w eb 2based cou rses have becom e the focu s of educati on . B ased

18、 on the characteristics and the i m p lem en ting p rinci p les of w eb 2based cou rse , th is p ap er w ill discu ss in detail the design ing m odel and i m p lem en ting m ethods of w eb 2based cou rse , and give the functi onal m odel of learn ing th rough In ternet .Key words :w eb 2based cou rse ; design ing m ode ; i m p lem en ting m ethods ; in teracti on ; co llabo rative learn 2 ing ; learn ing by self 2determ inati on(上接第 33页 建工厂 ; 总费用 89万元 ; 最大利润 17万元 .