混合遗传模拟退火算法求解背包问题
- 格式：pdf
- 大小：212.41 KB
- 文档页数：4
关键词 ： 包问题 ； 背 遗传算 法； 拟退火 模
中 图分 类 号 ： ２ １４ ０ ２ ． 文 献标 志码 ： Ａ 文 章 编 号 ：６ ４— ３ Ｘ ２ １ ） ３— ０ ６— ４ １７ ３ ０ （ ０ ２ ０ ０ ６ ０
背 包 问题是 运筹 学 中一个著 名 的问题 ， 它是指 从 ｎ个不 同价值 和 重量 的物 品集 合 中选 择若 干 个 物 品装
入指定容量 ｃ的背包 ， 使得被选物品的总重量不超过背包容量且价值总和最大． 假设第 ｉ 个物品的价值和重 量分别为ｐ 和 Ｗ ， 引入 向量 ∈ ｛ ， ｝， ０ １ 当物品 ｉ 被选择放入背包时， ＝１否则 ＝０ 背包问题可以建模 ； ．
为 如下 的整数 规划 模型 ：
法 操作 简单 实用 ， 受到 了学 者们 的广泛 关 注 ． 而 ， 然 每种 算 法都 有 其 自身 的 优势 和缺 陷 ． 传 算 法 是 一 种 遗 基 于 自然选 择 和 自然 遗传 学机 制上 的随机 搜索算 法 ， 具有 较强 的全局 搜索性 能 ， 但是 遗传 算法 在搜 索过 程 中 容 易 出现早 熟 现象 ． 拟退 火算 法模 拟 固体退火 的过 程 ， 模 不仅 能 够 向 目标 函数优 化 的方 向迭 代 ， 而且 通 过 引 入 接 受准则 ， 能够 以一 定 概 率 接 受 较 差 的解 ， 而 避 免 陷 入 局 部 最 优 解 ， 当 问题 规 模 较 大 时 ， 敛 速 度 从 但 收
Ｘ为初 始解 ， ｘ Ｎ（ ）为 Ｘ的某个 邻域 结构 ， Ｔ＞０为 Ｓ Ｌ 法 的参数 ， Ｓ Ｌ Ａ Ｓ算 则 Ａ Ｓ算法 可描 述为 ： （ ） 始 化 ， ｏ ｎ ＝０， ＝Ｘ １初 ｄｗ Ｘ ．
（） ２ 计算 Ｎ ｘ （ ）中所有解的适应度 函数值 ， 假设 Ｙ是 Ｎ ｘ （ ）中适应度函数值最大的解 ， 令 ＝ｆＹ （ ）一
ｍｘ （。 …， ａｇｘ， ）＝∑Ｐ ，
ｉ ｌ ＝
（ Ｆ） Ｋ
ｓ． ∑ Ｗ ． ｔ ｉ ≤Ｃ ，
∈ ｛ ，｝ｉ＝１２ ｉ ，ｉ ０并且∑ ｉ ． ＞Ｃ
＝１
背包 问题属 于带 约束 的 Ｎ Ｐ困难 问题 ］在 现实 生活 中有着 广泛 的应用 背景 ， ， 比如 货物 装 载 、 工厂 下 料 、
电子商务和软硬件划分等心 ． ｊ并且背包 问题往往作为子问题出现在许多复杂的组合优化问题 中， 以研究 所 背包问题的有效求解算法具有重要的理论和实际意义． 常见的求解背包问题的算法有精确算法和智能优化算法 Ｉ ． ６ 精确算法具有指数时间的算法复杂度 ， Ｊ 难
以应用 于求解 大规 模 问题 ． 能优 化算 法能 够较 快地求 得精 度较 高 的近似解 ， 智 特别 是遗 传算 法 和模拟 退火 算
收 稿 日期 ：０ ２— ２—２ ２１ ０ ３ 基金项 目： 福建省教育厅科研 资助项 目（Ａ １０ ） Ｊ １ ２ １ 作者简介 ： 林耿 （９ １ ， 福建莆田人 ， 师， 士， １８ 一） 男， 讲 博 主要从事组合优化和智能计 算方面的研究
第 ３期
林 耿 ： 混合遗传模 拟退火算法求解背 包问题
・６ ７・
ｌ 混合遗传模 拟退火算法
遗 传算 法具 有很 强 的全局 搜 索能力 ， 但是局 部 搜索 能力 较 差 ， 容易 陷人 局 部最 优解 ． 拟退 火 算 法具 有 模 较 强 的局部 搜索 能力 ， 但搜 索 速度 较慢 ． 本研 究将 这 两个算 法 结合起 来 ， 出混 合 的遗传 模拟 退火 算法 ， 提 随机
构造种群 ， 采用模拟退火对种群 中的解进行局部搜索 ， 引入新的种群更新策略 ， 保持种群的多样性 ， 避免早熟
现象 发 生．
１ １ 适应 度 函数 ．
背包 问题是 一个带 约束 的极大 化问题 ． 适应度 函数 的建立是有效解决 背包 问题 的关 键 ． 本研 究采 用惩罚 函 数 方法 构造 适应 度 函数 ， 即对 不在约 束集 内的解 ， 在其 目标 函数值 上加上 一个惩 罚项 ， 而使得 算法 在惩罚 项 从
第２ ４卷 第 ３期
２ ２年 ９月 ０１
河南工程 学院学报 （自然科学版）
Ｊ ＲＮＡＬ Ｏ ＮＡＮ Ｉ Ｓ Ｉ ＵＴ Ｆ ＥＮＧ ＮＥ ＯＵ Ｆ ＨＥ Ｎ ＴＴ Ｅ Ｏ Ｉ ＥＲＩ ＮＧ
Ｖｏ． １２４， ． Ｎｏ ３ Ｓｅ ｔ ２ ２ ｐ ． ０１
混合 遗传 模 拟 退 火算 法 求解 背 包 问题
林 耿
（ 闽江 学院 数 学 系 ， 福建 福 州 ３００ ） ５ １８
摘 要 ： 出了一种混合遗传模拟退 火算 法求解 背包 问题 ， 提 该算 法应用改进 的模拟 退 火算法作为局 部搜 索， 高算 法的 提
搜索效率 ， 采用同时考虑解的质量和种群 多样性 的种群 更新 策略 ， 保持 种群 的 多样性 ， 仿真 实验结果表 明该算 法是有效 的．
的 作用下找到问题的最优解． 定义适应度函 ）＝ｇ 一 ａ｛ ｉ — ，ｔ 数为 （） ｍｘ ∑Ｗ ｃｏ ， 其中ｋ 惩罚参数． 为
１＝ ｌ
１２ 改进 的模 拟退 火局 部搜 索算 法 ．
传统模拟退火算法能够有效避免陷入局部最优解 ， 但当问题的规模较大时 ， 模拟退火算法的收敛速度较 慢． 本研究基于模拟退火的思想， 提出了一个改进模拟退火局部搜索算法 Ｓ Ｌ ， Ａ Ｓ 加快 了局部搜索 的速度． 设
较慢．
本研究将模拟退火算法有效地融入遗传算法 ， 结合遗传算法和模拟退火算法的优点 ， 提出了一种求解背
包 问题 的混合 遗传模 拟 退火算 法 ， 有效 地避 免陷入 局部 最 优解 ． 单纯 的遗传 算 法 比较 ， 验 结果 表 明 了该 与 实 混 合算 法求解 背包 问题 的有 效性 和适 用性 ．
中 图分 类 号 ： ２ １４ ０ ２ ． 文 献标 志码 ： Ａ 文 章 编 号 ：６ ４— ３ Ｘ ２ １ ） ３— ０ ６— ４ １７ ３ ０ （ ０ ２ ０ ０ ６ ０
背 包 问题是 运筹 学 中一个著 名 的问题 ， 它是指 从 ｎ个不 同价值 和 重量 的物 品集 合 中选 择若 干 个 物 品装
入指定容量 ｃ的背包 ， 使得被选物品的总重量不超过背包容量且价值总和最大． 假设第 ｉ 个物品的价值和重 量分别为ｐ 和 Ｗ ， 引入 向量 ∈ ｛ ， ｝， ０ １ 当物品 ｉ 被选择放入背包时， ＝１否则 ＝０ 背包问题可以建模 ； ．
为 如下 的整数 规划 模型 ：
法 操作 简单 实用 ， 受到 了学 者们 的广泛 关 注 ． 而 ， 然 每种 算 法都 有 其 自身 的 优势 和缺 陷 ． 传 算 法 是 一 种 遗 基 于 自然选 择 和 自然 遗传 学机 制上 的随机 搜索算 法 ， 具有 较强 的全局 搜索性 能 ， 但是 遗传 算法 在搜 索过 程 中 容 易 出现早 熟 现象 ． 拟退 火算 法模 拟 固体退火 的过 程 ， 模 不仅 能 够 向 目标 函数优 化 的方 向迭 代 ， 而且 通 过 引 入 接 受准则 ， 能够 以一 定 概 率 接 受 较 差 的解 ， 而 避 免 陷 入 局 部 最 优 解 ， 当 问题 规 模 较 大 时 ， 敛 速 度 从 但 收
Ｘ为初 始解 ， ｘ Ｎ（ ）为 Ｘ的某个 邻域 结构 ， Ｔ＞０为 Ｓ Ｌ 法 的参数 ， Ｓ Ｌ Ａ Ｓ算 则 Ａ Ｓ算法 可描 述为 ： （ ） 始 化 ， ｏ ｎ ＝０， ＝Ｘ １初 ｄｗ Ｘ ．
（） ２ 计算 Ｎ ｘ （ ）中所有解的适应度 函数值 ， 假设 Ｙ是 Ｎ ｘ （ ）中适应度函数值最大的解 ， 令 ＝ｆＹ （ ）一
ｍｘ （。 …， ａｇｘ， ）＝∑Ｐ ，
ｉ ｌ ＝
（ Ｆ） Ｋ
ｓ． ∑ Ｗ ． ｔ ｉ ≤Ｃ ，
∈ ｛ ，｝ｉ＝１２ ｉ ，ｉ ０并且∑ ｉ ． ＞Ｃ
＝１
背包 问题属 于带 约束 的 Ｎ Ｐ困难 问题 ］在 现实 生活 中有着 广泛 的应用 背景 ， ， 比如 货物 装 载 、 工厂 下 料 、
电子商务和软硬件划分等心 ． ｊ并且背包 问题往往作为子问题出现在许多复杂的组合优化问题 中， 以研究 所 背包问题的有效求解算法具有重要的理论和实际意义． 常见的求解背包问题的算法有精确算法和智能优化算法 Ｉ ． ６ 精确算法具有指数时间的算法复杂度 ， Ｊ 难
以应用 于求解 大规 模 问题 ． 能优 化算 法能 够较 快地求 得精 度较 高 的近似解 ， 智 特别 是遗 传算 法 和模拟 退火 算
收 稿 日期 ：０ ２— ２—２ ２１ ０ ３ 基金项 目： 福建省教育厅科研 资助项 目（Ａ １０ ） Ｊ １ ２ １ 作者简介 ： 林耿 （９ １ ， 福建莆田人 ， 师， 士， １８ 一） 男， 讲 博 主要从事组合优化和智能计 算方面的研究
第 ３期
林 耿 ： 混合遗传模 拟退火算法求解背 包问题
・６ ７・
ｌ 混合遗传模 拟退火算法
遗 传算 法具 有很 强 的全局 搜 索能力 ， 但是局 部 搜索 能力 较 差 ， 容易 陷人 局 部最 优解 ． 拟退 火 算 法具 有 模 较 强 的局部 搜索 能力 ， 但搜 索 速度 较慢 ． 本研 究将 这 两个算 法 结合起 来 ， 出混 合 的遗传 模拟 退火 算法 ， 提 随机
构造种群 ， 采用模拟退火对种群 中的解进行局部搜索 ， 引入新的种群更新策略 ， 保持种群的多样性 ， 避免早熟
现象 发 生．
１ １ 适应 度 函数 ．
背包 问题是 一个带 约束 的极大 化问题 ． 适应度 函数 的建立是有效解决 背包 问题 的关 键 ． 本研 究采 用惩罚 函 数 方法 构造 适应 度 函数 ， 即对 不在约 束集 内的解 ， 在其 目标 函数值 上加上 一个惩 罚项 ， 而使得 算法 在惩罚 项 从
第２ ４卷 第 ３期
２ ２年 ９月 ０１
河南工程 学院学报 （自然科学版）
Ｊ ＲＮＡＬ Ｏ ＮＡＮ Ｉ Ｓ Ｉ ＵＴ Ｆ ＥＮＧ ＮＥ ＯＵ Ｆ ＨＥ Ｎ ＴＴ Ｅ Ｏ Ｉ ＥＲＩ ＮＧ
Ｖｏ． １２４， ． Ｎｏ ３ Ｓｅ ｔ ２ ２ ｐ ． ０１
混合 遗传 模 拟 退 火算 法 求解 背 包 问题
林 耿
（ 闽江 学院 数 学 系 ， 福建 福 州 ３００ ） ５ １８
摘 要 ： 出了一种混合遗传模拟退 火算 法求解 背包 问题 ， 提 该算 法应用改进 的模拟 退 火算法作为局 部搜 索， 高算 法的 提
搜索效率 ， 采用同时考虑解的质量和种群 多样性 的种群 更新 策略 ， 保持 种群 的 多样性 ， 仿真 实验结果表 明该算 法是有效 的．
的 作用下找到问题的最优解． 定义适应度函 ）＝ｇ 一 ａ｛ ｉ — ，ｔ 数为 （） ｍｘ ∑Ｗ ｃｏ ， 其中ｋ 惩罚参数． 为
１＝ ｌ
１２ 改进 的模 拟退 火局 部搜 索算 法 ．
传统模拟退火算法能够有效避免陷入局部最优解 ， 但当问题的规模较大时 ， 模拟退火算法的收敛速度较 慢． 本研究基于模拟退火的思想， 提出了一个改进模拟退火局部搜索算法 Ｓ Ｌ ， Ａ Ｓ 加快 了局部搜索 的速度． 设
较慢．
本研究将模拟退火算法有效地融入遗传算法 ， 结合遗传算法和模拟退火算法的优点 ， 提出了一种求解背
包 问题 的混合 遗传模 拟 退火算 法 ， 有效 地避 免陷入 局部 最 优解 ． 单纯 的遗传 算 法 比较 ， 验 结果 表 明 了该 与 实 混 合算 法求解 背包 问题 的有 效性 和适 用性 ．
