4 解 0 -1 整数问题的混合粒子群算法
首先把原约束方程作为罚函数项加入到原目
标中, 变成无约束的优化问题, 即
min T = f ( x 1 , x 2 , ,, x n ) +
m
E M
mi n ( 0, gi ( x 1 , x 2 , ,, x n ) 2 ( 4)
i= 1
其中 M 为一充分大的正数。
化, 神经网络训练, 模糊系统控制以及其他遗传算 法的应用 领域。目 前已提出 了多种 P SO 改进算 法[ 6~ 9] , 如自适应 P SO 算法、杂交 P SO 算法、协同 PSO 算法。笔者提出基于遗传算法思想的一种新 的 PSO 算法来解决 0- 1 整数规划问题。P SO 是 模拟鸟群的捕食行为, 设想这样一个场景: 一群鸟 在随机搜索食物。在 这个区域里只 有一块食物。
2 0- 1 整数规划问题数学模型
0- 1 整数规划问题的数学模型为 min f ( x 1 , x 2 , ,, x n ) ,
收稿日期: 2011- 02- 22
基金项目: / 青蓝工程0 资助( 苏教师( 2010) 27 号) ; 江苏省高校自然科学基础研究课题( 08K JB520003) 作者简 介: 薛 峰( 1957 ) ) , 男, 四川 人, 高 级 实验 师, 研 究方 向: 计 算 机网 络系 统集 成( E - mail: gao_ shang @ h otm ail. com ) ; 陈 刚
x k ) 项可以看作遗传算法的交叉操作, 让当前解与 个体极值和全局极值分别作交叉操作, 产生的解为 新的位置。交叉方法可以采用以下两种方法
1) 交叉策略 A :
( 1) 两串 old1和 old2 交叉, 在第二个串 o ld2 中 随机选择一个交叉区域;
( 2) 将 o ld1 的相应的交叉区域由 old2 交叉区
XUE F eng , CH EN Gang , GAO Shang
( Schoo l of Co mputer Science and Eng ineering , Jiangsu U niver sity o f Science and T echno lo gy , Zhenjiang 212003, China)
所有的鸟都不知道食物在那里。但是他们知道当
前的位置离食物还有多远, 那么找到食物的最优策 略是什么呢? 最简单有效的就是搜寻目前离食物 最近的鸟的周围区域。P SO 从这种模型中得到启 示并用于解决优化问 题。PSO 中, 每个优化问题 的解都是搜索空间中的一只鸟, 称为/ 粒子0。所有 的例子都有一个由被优化的函数决定的适应值, 每 个粒子还有一个速度决定他们飞翔的方向和距离, 然后粒子们就追随当前的最优粒子在解空间中搜
88
计算技术与自动化
2011 年 3 月
如原来解为 1 0 0 1 0 1 1 11 0 01 , 随机产生区 域为 1 1 0 0, 则变异操作后的解为
1 0 0 1 0 1 1 0 0 1 1 1。 2) 变异策略 B: ( 1) 在解空间( x 1 , x 2 , ,, x n ) T 中随机选择 一块区域, 如( x i , x i+ 1 , ,, x j ) T ; ( 2) . ( x i , x i+ 1 , ,, x j ) T 取随机值。 3) 变异策略 C: ( 1) 在解空间( x 1 , x 2 , ,, x n ) T 中随机选择 一个 1 到 n 的整数 j ; ( 2) x j ¬ x j 。 如原来解为 1 0 0 1 0 1 1 1 1 0 0 1, 随机产生 整数为 4, 则变异操作后的解为 1 0 0 0 0 1 1 1 1 0 0 1。 解 0 - 1 整数规划问题的混合粒子群算法 hy br id _PSO 如下: 1) 设定粒子数 np , 规定迭代次数 nmax , 随机产 生 np 个初始解 X 0 ; 2) 根据当前位置根据式( 4) 计算适应值 l 0, 设 置当前适应值为个体极值 plbest , 当前位置为个体 极值 位 置 px best , 根 据 各 个 粒 子 的 个 体 极 值 plbest , 找 出 全 局 极 值 glbest 和 全 局 极 值 位 置 gx best; 3) While ( 迭代次数 < 规定迭代次数 nmax ) do 4) for j = 1: np 5) 第 j 个粒子位置 X 0( j ) 与 g xbest 交叉得到 X 1 ¢(j ) ; 6) X 1 ¢(j ) 与 px best 交叉得到 X 1( j ) ; 7) 对 X 1( j ) 进行变异操作; 8) 根据当前位置计算适应值 l1; 9) 如果 l 1( j ) < p lbest ( j ) , 则 px best ( j ) =
薛 峰, 陈 刚, 高 尚
( 江苏科技大学 计算机科学与工程学院, 江苏 镇江 212003)
摘 要: 经典的粒子群是一个有效的寻找连续函数 极值的方 法, 结合 遗传算法 的思想提 出的混 合粒子
群算法来 解决 0- 1 整数规划问题, 经过比较测试, 6 种 混合粒子群算法的效果都比较好, 特别交叉策略 A 和
子的邻居, 那么在所有邻居中的极值就是局部 极值。
在找到这 2 个最优值时, 每个粒子根据如下 的公式来更新自己的速度和新的位置:
v k + 1 = c0 v k + c1 ( p best k -x k ) + c2 ( g best k -x k )
( 2)
xk+ 1= xk+ vk+ 1
( 3)
( 1967 ) ) , 江苏镇江人, 工程师, 研究方向: 计算机应用。
第 30 卷第 1 期
薛 峰等: 求解 0 - 1 整数规划的混合粒子群优化算法
87
s. t . gi ( x 1 , x 2 , ,, x n ) \0( i = 1, 2, ,, m) ( 1) x i = 0, 1( i = 0, 1, ,, n)
索。PSO 初始化为一群随机粒子( 随机解) , 然后 通过迭代找到最优解。在每一次迭代中, 粒子通过 跟踪两个极值来更新自己。一个是粒子本身所找
到的最优解, 称为个体极值 pbest; 另一个极值是整 个种群目前找到的最优解, 称为全局极值 g best, 另 外也可以不用整个种群而只是用其中一部分为粒
法[ 2] 、遗传算 法[ 2] 、遗传退 火进化 算法[ 3] 、蚁群 算 法[ 4, 5] ) 。精确方法虽然可以得到 准确解, 但 时间 复杂性与物品数目成指数关系。近似算法和智能 优化算法虽然不一定得到准确解, 但可得到比较有 效解, 并且时间复杂性比较低。笔者尝试采用粒子 群优化算法解决此问题。
变异策略 C 的混合粒子群算法是最好的且简单有效的算法。对于目前还没有好 的解法的 组合优化问 题, 很
容易地修 改此算法就可解决。
关键 词: 粒子群算法; 0- 1 整数规划问题; 背包问题; 遗传算法; 变 异
中图 分类号: T P 301. 6
文献标识码: A
Solving 0- 1 Integer Programming Problem by Hybrid Particle Swarm Optimization Algorithm
3 基本粒子群优化算法
粒子群优化 ( PSO, part icle sw arm o pt imizat ion) 算法是一种进化计算技术, 最早是由 Kennedy 与 Eberhart 于 1995 年提出的[ 6] 。源于对鸟群 捕食的行为研究的 P SO 同遗传算法类似, 是一种 基于迭代的优化工具。系统初始化为一组随机解, 通过迭代搜寻最优值。目前已广泛应用于函数优
其中: v k 是粒子的速度向量; x k 是当前粒子的
位置; p best k 粒 子 本身 所 找 到的 最 优 解 的位 置; gbestk 整个种群目前找到的最优解的位置; c0 , c1 , c2表示群体认知系数, c0 一般取介于( 0, 1) 之间的
随机数, c1 , c2 取( 0, 2) 之间的随机数。vk + 1 是 vk , p best k -x k 和 gbest k -x k 矢量的和。在每一维粒子的 速度都会被限制在一个最大速度 v max ( vmax > 0) , 如 果某一维更新后的速度超过用户设定的 vmax , 那么 这一维的速度就被限定为 v max , 即若 v k > v max 时, v k = v max 或 v k < -v max 时, v k = -v max 。
域代替。
例如两父串为
old1 = 1 0 0 1 0 1 1 1 1 0 0 1,
old2 = 0 1 1 0 1 0 1 0 1 1 0 0。
交叉区域为 0 1 0 1 1, 交叉后为
new 1 = 1 0 0 1 0 0 1 0 1 1 0 1。 2) 交叉策略 B:
( 1) 随机产生 kຫໍສະໝຸດ 个 1 到 n 的整数 j1 , j2 , ,, jk ;
Key words: par ticle sw arm algo rithm; 0- 1 integer pr og ramming pr oblem; knapsack pro blem; g enetic algo rithm; mutation
1引言
0- 1 整数规划问题是运筹学中一个典型的组 合优化难题, 有着广泛的应用背景, 如货物装载问 题, 选址问题等。由于此问题比较简单典型, 因此 评价算法优劣常常以此问题作为的测试对象进行 研究。0- 1 整数规划问题属于 NP 问题, 目前求 解的方法有精确方法( 如动态 规划、递 归法、回溯 法、分支限界法等[ 1] ) , 近似算法( 如贪心法[ 1] , L ag rang e 法等) 以及 智能优 化算 法( 如 模拟 退火算