求解多维0_1背包问题的二元粒子群算法

第 21 卷第 18 期 系 系 统统 仿仿 真真 学学 报报 Vol. 21 No. 18 2009 年 9 月 Journal of System Simulation Sep., 2009 5735 求解多维求解多维0/1背包问题的二元粒子群算法背包问题的二元粒子群算法 程美英，熊伟清，严 彬，叶 青 (宁波大学计算机科学与技术研究所，宁波 315211) 摘摘 要要：从一维细胞自动机模型入手，设计了一种求解二元离散优化问题的二元粒子群算法细胞 自动机模型 从一维细胞自动机模型入手，设计了一种求解二元离散优化问题的二元粒子群算法细胞 自动机模型(BPSO-CA)。粒子从起始细胞出发，根据本身携带的信息并感知存储在细胞中的全局 最优粒子位置的信息随机选择状态(0 或 1)，从而实现复杂智能的“涌现” 。然后将其用来求解多维 0/1 背包问题，同时引入贪心算法对不符合约束条件的非法个体进行修正。通过对 Zuse Institute Berlin 公布的测试集进行实验，表明该模型能在多项式时间内完成求解过程，且实验结果优于测试 集记录的结果。 关键词关键词：二元粒子群算法(BPSO)；细胞自动机(CA)；贪心算法；多维 0/1 背包问题；NPC 问题 中图分类号中图分类号：TP301.6 文献标识码文献标识码：A 文章编号：文章编号：1004-731X (2009) 18-5735-05 Binary PSO Algorithm for Multiple 0/1 Knapsack Problem CHENG Mei-ying, XIONG Wei-qing, YAN Bin, YE Qing (Institute of Computer Science and Technology, Ningbo University, Ningbo 315211, China) Abstract: Starting with the one dimension cellular automata model, a kind of binary PSO cellular automata model used to solve the binary discrete optimization problem was designed. In this model, the particle started from the first cell, randomly chose the state (0 or 1) according to its own information and the globe optimal information stored in the cell, then the complex intelligent emergences. The model was involved to solve the Multiple 0/1 Knapsack Problem, and the greedy algorithm was introduced to revise the illegal individuals that did not conform to the restrictions. By testing the test sets of the knapsack problem which were announced by the Zuse Institute Berlin, the solving process could be completed in polynomial time and all the results are superior to the given test results. Key words: binary PSO (BPSO); cellular automata (CA); greedy algorithm (GA); Multiple 0/1 Knapsack Problem (MKP); NPC problem 引引 言言1 近年来， 复杂系统一直是众多学者研究的热点之一， 如： 单只蚂蚁的能力极其有限， 但却能聪明的找到把食物搬运回 家的最短路程，并还能形成等级森严的社会体系；一群行为 盲目的蜂群能造出精美的蜂窝； 鸟群在没有集中控制的情况 下时聚时散，表现出非常优美和谐的动态1, 我们人类通 常的思维习惯是把自然界的某种智慧的行为归功于比这种 行为更聪明的造物者的设计。实际上，近年来的复杂性科学 2研究指出：诸如人脑、生态系统、细胞、蚁群、鸟群以及 人类社会中的政党和组织等都是由并行的、 相互作用的智能 体组成的网络， 只要对自然界中的智能体设置几条简单的规 则，复杂的智能是可以通过简单的交互作用“涌现”的。粒 子群算法(PSO)3作为复杂自适应系统中的一种，用无质量、 无体积的微粒作为个体，每个个体都有一定的感知能力，能 够感知周围局部最好位置的个体和整个群体的全局最好位 置个体的存在，并根据当前情况，适当调整自己下一步的行 为，从而使整个群体涌现出一定的智能性。 收稿日期：收稿日期：2008-04-17 修回日期：修回日期：2008-09-14 基金项目：基金项目：国家自然科学基金 (60472099)；浙江省自然科学基金 (Y106080)；宁波市自然科学基金 (2007A610051) 作者简介：程美英作者简介：程美英(1983-), 女, 安徽黄山人, 硕士生, 研究方为智能计 算；熊伟清熊伟清(1965-), 男, 浙江丽水人, 教授, 研究方向为进化计算, 软件 工程；严彬严彬(1981-), 男, 浙江杭州人, 硕士生, 研究方向为智能计算； 叶青叶青(1982-), 男, 湖北武汉人, 研究方向为智能计算。 PSO 在连续型优化问题求解方面取得很好的效果， 为了 处理二元离散优化问题4，1997 年，Kennedy 和 Eberhart 提 出了二进制 PSO 算法(BPSO)5。在用 BPSO 求解二元离散 优化问题时，一个维数为 n 的 0、1 序列代表问题的解。90 年代提出的 M 理论6(超弦理论的一种)指出宇宙是 11 维，但 我们人眼最多只能感受三维的空间， 对于四维或四维以上的 高维空间我们甚至很难通过想象的方式来描绘粒子之间的复 杂运动，这就对问题研究带来不便。如何更好、更直观地描 述高维空间粒子在求解二元离散优化问题时的复杂动态行 为呢?细胞自动机模型给我们提供了一个很好的工具。20 世 纪 80 年代，美国科学家沃弗拉姆(Stephen Wolfram)曾指出 7：细胞自动机是一个真实的复杂系统，我们可以舍弃严格 的复杂方程式，把细胞自动机一类简单程序作为分析工具， 这种简单但可演变出复杂样式的程序能更精确、 更轻易地模 拟出各种复杂现象，诸如从雪花的增长到宇宙的演化等等。 本文从一维细胞自动机模型入手， 对高维空间粒子在求 解二元离散优化问题所表现出的复杂动态行为进行描述， 提 出基于二元粒子群算法的细胞自动机模型(BPSO-CA)， 然后 将其用来求解单 0/1 背包问题和多维 0/1 背包问题。通过时 间复杂度和空间复杂度的分析， 得出该模型能够在多项式时 间内完成求解过程， 并且所得到的解均优于测试集记录的最 好解。 第 21 卷第 18 期 Vol. 21 No. 18 2009 年 9 月 系 统 仿 真 学 报 Sep., 2009 5736 1 二元粒子群算法细胞自动机模型二元粒子群算法细胞自动机模型(BPSO-CA) 1.1 二元粒子群算法细胞自动机模型二元粒子群算法细胞自动机模型(BPSO-CA)描述描述 一维细胞自动机是一个三元有序组，用 CA=Q，F， M表示，式中： Q 所有细胞状态的集合； F 细胞的转换函数； M 细胞的阵列模式(或细胞空间)； 不同于一般的动力学模型， 细胞自动机是一类模型的总 称， 其最大的特点就是复杂的现象可以由一些简单的局部规 则产生，它的这种“自下而上”的研究思路与粒子群算法的 “自下而上”的“涌现”现象不谋而合，因此从细胞自动机 的角度对算法进行描述，具有更直观的效果。 图 1 一维随机二值二邻居 BPSO-CA 模型 这里认为采用固定的输入， 假设在一条直线上均匀的分 布着 n 个细胞(见图 1)，第 i 个细胞对应第 i 维的空间，将 n 维空间中全局最优粒子的位置 g p存储到图 1 所处的细胞 内。 任意时刻每个细胞可取 k 个(0 或 1)整数值中的一个。 某 个细胞下一时刻的取值由粒子自身携带的信息并感知存储 在细胞中的信息根据 1 和 0 的概率分布来决定。 细胞之间的 作用是邻近的局域作用, 包括(1)粒子从左到右进行搜索； (2) 从右到左对存储全局最优粒子位置的细胞进行更新。 我们称 为一维随机二值二邻居细胞自动机。 初始化种群规模popsize,及种群中每个粒子的自身信息 (包括粒子的速度 maxmax ( ) , ij v tvv 、位置( ) ij x tmaxmax,xx (maxx为粒子位置坐标的上界， maxx为粒子位置坐标的下界) 及粒子本身最优位置( ) ij p t，1,2,1,2,.ipopsize jn=)。每 个携带自身信息的粒子，从起点出发，在每个细胞处按公式 (1)(2)根据自身在该细胞处的信息( ),( ),( ) ijijij v t x tp t)及通过感 知存储在细胞处的全局最优位置( ) g pt,修改得到粒子在该维 的当前速度(1) ij v t +并得到粒子在该维的当前位置(1) ij xt +， 然后根据粒子的位置概率分布来决定细胞取 0 或 1，转移概 率公式如(3)8，随后粒子转移到下一个细胞处。 1 12 2 (1)( )( )( )( )( ) ijijijijgij v tv tcr p tx tc r p tx t+=+ (1) (1)( )(1) ijijij xtxtvt+=+ (2) 0(1)0.5 (1) 1(1)0.5 ij ij ij sign x t X t sign x t + += + (3) 其中，( ) 1/(1) x sign xe=+为模糊函数，c1,c2为加速常数，r1,r2 为两个相互独立的随机函数。随着时间的推移，所有粒子完 成对细胞队列的遍历之后， 更新存储在细胞中的全局最优粒 子的位置得到(1) g p t +及种群中粒子的个体最优位置(1) ij p t+。 所有细胞都按给定的规则同步更新， 任意时刻 CA 的构 形(configuration)C 表示全体细胞的当前状态， 是一个有限或 无限的状态符号序列( 12 ,., n X XX)，0,1 i X ，也即问题的 一个解。由此可以看出一维的细胞自动机模型虽然结构简 单，但却能很好表现出高维粒子复杂的动态行为。 1.2 二元粒子群算法细胞自动机模型二元粒子群算法细胞自动机模型(BPSO-CA)收 敛性分析 收 敛性分析 因本文 BPSO-CA 模型采用全局最优更新策略，即一旦 找到一个全局最优，该最优解个体将一直生存下去。因此只 要证明如下定理 1， 即可保证本文的 BPSO-CA 模型值收敛。 定理定理1设 *( ) p t为t次迭代内BPSO-CA模型首次发现最 优解 * c的概率， 则对于任意小的0 和充分大的迭代次数 t， 有 *( ) 1 p t ，且 * lim( )1 t p t =。 证明：任意时刻，每个携带自身信息( ),( ),( ) ijijij v t x tp t)的 粒子通过感知存储在细胞中的全局最优位置( ) g p t，得到粒 子的当前位置(1) ij xt +，且粒子在构造解的过程中，通过模 糊函数(1) ij sign x t +作为自己的状态转移概率。 因( ) ijx t maxmax,xx 且,( )(0,1)xR sign x 并单调递增， 所以在粒子构造解的过程中， 粒子每一步状态转移概率的可 行选择为 min 0p，且有： max minmin ()0ppsign x=。从而，对 于任意解 c(包括任意最优解 * cC)均以 min ()0 n pp的概 率产生，其中 n 为细胞阵列的长度。假定只要能有一个粒子 搜索到最优解即可满足要求，由此， *( ) p t的一个下界为： * ( )1 (1)tp tp= ，对于任意小的0 ，当 t 足够大时，有 *( ) 1p t ，从而，当t时，有： * lim( )1p t =。证毕 2 二元粒子群算法细胞自动机二元粒子群算法细胞自动机(BPSO-CA) 模型解模型解 0/1 背包问题算法设计背包问题算法设计 2.1 0/1 背包问题数学模型描述背包问题数学模型描述9 0/1 背包问题(0/1knapsack problem，简称 KP)给出一套 实体及它们的价值和尺寸，选择一个或多个互不相干的子 集，使每个子集的尺寸不超过给定边界，而被选择的价值总 和最大。具体给定边界，给定 m 种资源(如空间、容积、载 量等)各种资源的最大提供量是,1,2,., ici m=， 现将 n 种物品 装入背包， 第j项物品占用第i种资源的数量是,1,2,., ij ajn=， 受益量是 j p，求一个二进制的向量 12 ( ,.,) n Xx xx=，使总受 益最大。本质上，这是一个整数规划问题： 1 1 max() .,1,2,., 0,1,1,2,., . n jj j n jiji j j f Xxp stxac im xjn = = = = = (4) 当2m时，称为多维 0/1 背包问题。多维 0/1 背包问 题也是一个典型的 NP-hard 问题， 在确定一个物品只能放入 一个背包并满足约束条件下，其空间复杂度为2n mO （） ，其 中，n为物品的个数，m为背包的个数。若采用穷举搜索 法求解，其时间复杂度也为2n mO （） ，随着规模的增大，其 时间和空间复杂度均成指数级增长，显然穷举法不可取。 2 n 1 0 1 0 1 0 1 第 21 卷第 18 期 Vol. 21 No. 18 2009 年 9 月 程美英, 等： 求解多维 0/1 背包问题的二元粒子群算法 Sep., 2009 5737 2.2 BPSO-CA 模型解单模型解单 0/1 背包问题背包问题 从上述 0/1 背包问题的数学模型可以看出： (1) 对于一个物品而言，它只有两种可能的状态：一是 放入背包的状态；二是没有放入背包的状态； (2) 对于背包而言，无论物品如何放置，都不能超过它 的容量限制； 二进制编码是最有效和最经济的数据表示法， 自然界中 最容易模拟和实现的二值逻辑。 仔细观察图 1 的一维 CA 模 型可以看出，由于采用二进制编码，任意时刻，粒子只需根 据自身携带的信息及感知当前细胞最优粒子位置的信息从0和 1 中进行选择，而 1 和 0 恰好可以对应着 0/1 背包问题中物品 的“放入”和“不放入”，这就对粒子的智能行为要求非常底， 因而特别适合求解离散 0/1 背包问题。算法设计步骤如下： 1) 每个细胞代表一个等待装入背包的物品(见图 2)。假 设有 n 个物品等待装入背包中，也即 CA 的长度为 n； 2) 假设种群规模为popsize，初始化粒子自身信息(速 度、位置及个体最优位置)； 3) 根据公式(12)得到粒子的当前位置，并按公式(3)决 定细胞的取值 0 或 1，1 表示该物品被放入背包中，0 表示 该物品没有被放入背包中； 4) 对任意一个粒子而言，将其所对应的 0/1 状态序列 ( 12 ,., n XXX ),0,1 i X 按公式(4)计算背包的价值和重量， 且它对物品的选择要不和背包的限制条件相冲突； 5) 更新个体最优位置及存储在细胞内的全局最优粒子 的位置； 6) 重复步骤 35，满足结束条件则输出结果；不满足， 继续。 图 2 粒子遍历单 0/1 背包问题的 CA 模型 2.2.1 BPSO-CA模型求解单模型求解单0/1背包问题时间复杂度分析背包问题时间复杂度分析 从上述 BPSO-CA 模型求解单 0/1 背包问题的设计步骤 可以得出：因种群规模为popsize，物品数目为 n(即 CA 的 长度为 n)，初始化粒子自身信息(位置、速度及个体最优)各 需(popsize n)次，即时间复杂度 O(3 popsize n)；其他参 数的初始化需要常数次，故时间复杂度为 O(popsize)；对 每个粒子在细胞处按位置概率分布决定取 0 或 1，时间复杂 度为 O(popsize n)；计算每个粒子对应背包问题的解的时 间复杂度为 O(popsize n)；修改粒子个体最优位置时间复 杂度为 O(popsize n)；比较得到全局最优时间复杂度分别 为 O(popsize)；修改存储在细胞处的全局最优粒子位置时 间复杂度为( )O n；输出结果时间复杂度为 O(1)。 故一次循环后整个计算过程的时间复杂度为： (3)()() ()()()( )(1) () Opopsize nO popsizeO popsize n O popsize nO popsize nO popsizeO nO O popsize n =+ + = 显然， 经过N次循环之后的时间复杂度为： O(N popsize n)。 由此可以得出：利用 BPSO-CA 模型可以在多项式时间内求 解单 0/1 背包问题，这是传统算法不可能得到的。 2.2.2 BPSO-CA模型求解单模型求解单0/1背包问题空间复杂度分析背包问题空间复杂度分析 在实际应用中， 通常把算法执行时间内所占的存储单元 定义为算法的空间复杂度。 在用 BPSO-CA 模型求解拥有 n 个物品的单 0/1 背包问 题时，每个粒子遍历长度为 n 的 CA，第 i 个细胞对应第 i 个物品，存储每个粒子自身信息所需空间3 popsize n；每 个细胞存储全局最优粒子位置，故所需的空间为 n；记录每 个粒子在细胞处按位置概率分布取 0 或 1，需要存储空间为 popsize n；记录全局最优解的空间为 n；故可得到整个计 算过程的空间复杂度： 3()Sn popsizenn popsizenO n popsize=+= popsize为种群的规模，n 为物品的个数。 2.3 BPSO-CA 模型求解多维模型求解多维 0/1 背包问题背包问题 在用 BPSO-CA 模型求解多维 0/1 背包问题时，可以参 照其解决单 0/1 背包问题的过程。在 BPSO-CA 模型中，任 意一个细胞都有自己的状态，完成独立的运算，即可以被看 作是一个独立的自动机。因此，我们完全可以通过拉长细胞 自动机的长度来解决多维 0/1 背包问题(见图 3)。算法设计 步骤如下： (1) 在用 BPSO-CA 模型求解多维 0/1 背包问题时， 设有 n个物品等待装入m个背包中则令细胞自动机的长度 dn m=，也即让图 2 中的一条直线上均匀分布着dn m= 个细胞。为了方便说明问题，我们把图 2 中的细胞按背包的 数目排成几行，得到图 3，但图 3 中的每一列仍然代表同一 个物品； (2) 粒子的搜索过程同单 0/1 背包问题的求解过程。细 图 3 粒子遍历多维 0/1 背包问题的 CA 模型 2 n 1 0 1 0 1 0 物品 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 背 包 1 背 包 2 背 包 m 2 n 物品 1 第 21 卷第 18 期 Vol. 21 No. 18 2009 年 9 月 系 统 仿 真 学 报 Sep., 2009 5738 胞下一时刻的取值1或0仍然代表该物品被放入背包中或没 有被放入背包中； (3) 对每个粒子遍历完所有细胞之后所对应的 0/1 序列 进行解码，取出(1,., ,.,2 ,.,) d x dnnm n=，0,1 d x，其中 1dn=表示第 1 个背包的装载情况，(1)2dnn=+为第 2 个背包的装载情况， 依次类推，(1)dmn m n= 为第m个背 包的装载情况； (4) 用一个m n的矩阵存储每个粒子所对应问题的一 个解，为了保证同一个物品只能放入一个背包中，可以通过 随机函数让矩阵中每一列只能允许出现一个1(即只允许图3 中每一列细胞中的一个取 1)； (5) 按公式(4)计算背包的价值和重量，即背包问题中个 体的适应度函数由个体解确定的所有背包中物品的总价值 来决定； (6) 重复步骤 25， 满足结束条件输出结果； 不满足继续。 同理可以得出用 BPSO-CA 模型求解多维 0/1 背包问题 的 时 间 复 杂 度()O N popsize n m, 空 间 复 杂 度 为 ()O popsize n m， 其中 N 为循环次数，popsize为种群的规 模， n 为物品的个数,m 为背包的个数。 由此可以得出： BPSO- CA 模型同样可以在多项式时间内求解多维 0/1 背包问题。 分析过程同单 0/1 背包问题。 2.4 非法个体修正非法个体修正 粒子在完成一趟遍历之后， 不可避免的会产生一些非法 的解(如粒子选择的物品超过背包的容量限制)，我们称这样 的个体为“非法个体”。为了保持种群中个体的合法性，就 需要对非法个体进行修正。对此增加一步修正过程，该过程 同样发生在粒子对所有物品的遍历之后， 主要思想是多退少 补的贪心算法，即先退出多余的占有物，再对没有放入的物 品进行尝试。 1) 先从种群中找出与背包限制条件相冲突的粒子； 2) 对粒子i的第t个背包进行多退操作：将粒子i的第 t个背包中的物品价值进行从小到大排列，找出价值最小的 物品k，将其从背包t中取出，细胞自动机中的相应细胞取 值置 0； 3) 如果还是发生冲突，再进行多退操作； 4) 进行少补操作：将没有放入任何一个背包的物品放 入队列中，队列中物品的价值从大到小排列，将价值最大的 物品放入背包t中，并将相应细胞的取值由 0 置 1； 5) 继续进行少补操作，直至与约束冲突； 本文设计的算法是以 BPSO-CA 模型为主体，但是粒子 群算法较好的全局搜索能力及局部搜索能力弱的缺陷仍然 存在该模型中，所以在处理局部最优解的邻域时，引入传统 的贪心算法进行修正，从而逼近局部最优，以弥补粒子群算 法的不足。 3 参数选取说明参数选取说明 参数的选取对算法的性能和效率的影响很关键。 在本算 法中共有 6 个主要的参数：群体规模popsize、加速常数 12 ,c c，粒子速度( ) ij v t、粒子位置坐标( ) ij x t。其中群体的规 模将直接影响到算法的时间性能以及粒子对空间的遍历细 度； 加速常数直接影响到粒子向自身最好位置和全局最好位 置的偏向程度； 同样粒子的位置坐标和速度对寻找全局最优 解也会产生影响。 在实验仿真中， 群体规模popsize的选取一般与背包问 题的规模成正比； 为了保证算法在初期具有较强的全局收敛 能力，而晚期具有较强的局部收敛能力，我们可以引入惯性 因子w，并将w看作迭代次数的函数，即( )0.9w t = 0.5/ maxtnumber，其中maxnumber为最大截止代数； 加速常数 12 1.8cc=；粒子速度 5,5 ijv ，粒子位置 7.5,7.5 ijx ，个体最优位置 7.5,7.5 ijp 。各个参数对 于具体的背包问题也可以做适当的调整。 4 仿真实验仿真实验 实验测试数据采用http:/elib.zib.de/pub/Packages/mp- testdata/ip/sac94-suite/index.html上记载的55个测试集，实 验结果见表1所示，全部优于测试集记录的结果。下面选择 其中的format.dat和weish04.dat进行说明， 并具体给出粒子 的遍历路径序列及进化曲线图。 测试数据测试数据1 format.dat: /2 个背包 28 个物品 2 28 /物品各自的价值 189844022507270 14148 3100 465030800 615497511604225510 11880 479 440 490330110 560 24355 2885 117484550 7503720195010500 表表 1 测试数据测试数据 测试数据名称目前公布的最好解 本文 BPSO-CA 的解 flei.dat21394021 hp1.dat 3418 5123 hp2.dat 3186 6450 pb1.dat 3090 4795 pb2.dat 3186 5325 pb4.dat 95168 136567 pb5.dat 2139 4021 pb6.dat 776 2252 pb7.dat 1035 1696 pet2.dat 87061 125894 pet3.dat 4015 5165 pet4.dat 6120 8655 pet5.dat 12400 15495 pet7.dat 16537 22497 sent01.dat 7772 9460 sent02.dat 8722 9460 weing1.dat 141278 164045 weing2.dat 130883 164045 weing3.dat 95677 146288 weing4.dat 119337 164045 weing5.dat 98796 160666 weing6.dat 130623 164045 weing7.dat 1095445 1118047 第 21 卷第 18 期 Vol. 21 No. 18 2009 年 9 月 程美英, 等： 求解多维0/1背包问题的二元粒子群算法 Sep., 2009 5739 续表续表 1 测试数据测试数据 测试数据名称 目前公布的最好解 本文 BPSO-CA 的解的 weing8.dat 624319 703976 format 141278 164045 weish01.dat 4554 5829 weish02.dat 4536 5829 weish03.dat 4115 5829 weish04.dat 4561 5829 weish05.dat 4514 5829 weish06.dat 5557 6974 weish07.dat 5567 6974 weish08.dat 5605 6974 weish09.dat 5246 6974 weish10.dat 6339 8604 weish11.dat 5643 8604 weish12.dat 6339 8604 weish13.dat 6159 8604 weish14.dat 6954 9624 weish15.dat 7486 9624 weish16.dat 7289 9624 weish17.dat 8633 9624 weish18.dat 9850 11525 weish19.dat 7689 11525 weish20.dat 9450 11525 weish21.dat 9074 11525 weish22.dat 8947 12331 weish23.dat 8344 12331 weish24.dat 10220 12331 weish25.dat 9939 12331 weish26.dat 9584 13417 weish27.dat 9819 13417 weish28.dat 9492 13417 weish29.dat 9410 13417 weish30.dat 11191 13417 由表 1 可以得出：本文 BPSO-CA 模型与贪心算法相结合得到的 解均优于测试集记录的结果。 /背包的容量限制 600 600 /第 1 个背包中物品重量限制，0 为不可放入 45 0 85 150 65 95 30 0 1700 40 25 20 0 0 25 0 0 25 0 165 0 85 0 0 0 0 100 /第 2 个背包中物品重量限制，0 为不可放入 30 20 125 5 80 25 35 73 12 15 15 40 5 10 10 12 10 9 0 20 60 40 50 36 49 40 19 150 实验采用20个粒子，经过25代的运行之后，能得到稳 定的结果：164045。 46603 /贪心算法的解 141278 /测试集公布的结果 下面是运用BPSO-CA模型求解2背包28物品的多维 0/1背包问题的0/1序列，我们按背包数目分别给出： /第 1 个背包对应的 0/1 序列 0 0 1 0 0 1 0 00 0 0 0 10 0 0 0 0 1 0 1 01 0 0 0 01 /第 2 个背包对应的 0/1 序列 1 1 0 1 1 0 1 11 1 1 1 01 1 1 1 1 0 1 0 10 1 1 1 10 对最优粒子序列进行验证： 得到第1个背包的重量为575， 第2个背包的重量为580，均没有超过背包的容量限制，所以 合法。并且与上述贪心算法的解和公布的测试集结果进行比 较，发现BPSO-CA与贪心算法相结合得到的结果明显较优。 图4是本文BPSO-CA与贪心算法相结合求解format.dat 时群体最佳适应度随进化代数变化的进化曲线图， 种群规模 popsize=20。可以看出，该模型能迅速收敛到全局最优解 164045。这也就更进一步说明具有全局搜索性能的BPSO- CA与具有良好局部搜索性能的贪心算法相结合，能很快收 敛到全局最优解。 图 4 BPSO-CA 在 format.dat 上的进化曲线图 测试数据测试数据2 weish04.dat /5 个背包 30 个物品 5 30 /背包的容量限制 540 270 500 500 750 具体各物品的价值和重量可参考http:/elib.zib.de/pub/ Packages/mp-testdata/ip/sac94-suite/index.html-weish04.dat 5829 /本文BPSO-CA模型的解 1647 /贪心算法的解 4561 /测试集公布的结果 下面是BPSO-CA模型求解5背包30物品的多维0/1背 包问题的0/1序列，我们同样按背包数目分别给出： /第 1 个背包对应的 0/1 序列 00010000 0 0 1 1 011 01000000 1 1 0 0 001 /第 2 个背包对应的 0/1 序列 00000100 0 0 0 0 000 00001000 0 0 0 0 010 /第 3 个背包对应的 0/1 序列 00101000 1 0 0 0 100 10000010 0 0 0 0 000 /第 4 个背包对应的 0/1 序列 00000010 0 0 0 0 000 00110000 0 0 1 0 100 /第 5 个背包对应的 0/1 序列 11000001 0 1 0 0 000 00000101 0 0 0 1 000 通过对最优粒子序列进行验证，得到各个背包的重量 为：295、186、263、213、395，均没有超出背包的容量限 制，并且结果均优于贪心算法的解和公布的测试结果。 135000 140000 145000 150000 155000 160000 165000 170000 010203040 Iterations Output （下转第5743页） 第 21 卷第 18 期 Vol. 21 No. 18 2009 年 9 月 刘叶青， 等： 自训练多项式光滑的半监督支持向量机 Sep., 2009 5743 表表 1 算法算法 1 和算法和算法 3 的平均精度比较的平均精度比较 Data set 算法 1 的分类精度（%） mn 算法 3 的分类精度（%） =2 =4 =10 breast 95.227 95.134 95.325 42810 94.272 94.647 94.286 diabetes 73.103 73.469 72.279 7669 72.703 72.109 71.988 heart 80.377 82.625 82.716 27014 78.868 78.378 79.012 Monks 66.422 67.638 70.817 4297 65.931 67.638 68.872 5 结论结论 对小部分标记样本和大部分无标记样本的学习， 本文采 用了自训练半监督支持向量机的循环算法，若循环中采用 SVM的一般解法即求解一个二次规划问题，则当训练样本 的个数只有几百时，效率就已经很低。为了解决这个问题， 采用直接求解支持向量机的原始优化问题， 由此得到一个不 光滑的无约束优化问题。将正号函数展开为无穷多项式级 数，由此得到了一族光滑函数，用多项式光滑函数对无约束 优化问题进行逼近，并用共轭梯度算法求解模型。在人工数 据和UCI数据集上的实验结果显示，给出的算法效率高， 能保证标记样本很少时的分类精度并且不因标记样本的增 多而明显提高分类精度。 参考文献参考文献: 1 Burges C. A tutorial on support vector machines for pattern recognition J. Data Mining and Knowledge Discovery (S1384-5810), 1998, 2(2): 127-167. 2 吴强，贾传荧，张爱锋, 等. 球结构支持向量机的改进算法及仿真 研究J. 系统仿真学报，2008，20(1)：345-348. (WU Qiang, JIA Chuan-ying, ZHANG Ai-feng, et al. Improved algorithm based on sphere structure svms and simulation J. Journal of System Simulation (S1004-731X), 2008, 20(1): 345-348.) 3 Chapelle V Sindhwani, S S Keerthi. Optimization techniques for semi-supervised support vector machines J. Journal of Machine Learning Research (S1532-4435), 2008, 9(1): 203-233. 4 Chapelle V Sindhwani, S Keerthi. Branch and bound for semi- supervised support vector machines C/ In Advances in Neural Information Processing Systems. 19, Cambridge, MA, USA: MIT Press, 2007: 217-224. 5 Astorino A Fuduli. Nonsmooth optimization techniques for semi- supervised classification J. IEEE Transactions on Pattern Analysis and Machine Intelligence (S0162-8828), 2007, 29(12): 2135-2142. 6 V Sindhwani, S Keerthi, O Chapelle. Deterministic annealing for semi-supervised kernel machines C/ Proceedings of the 23rd International Conference on Machine Learning, New York, USA: ACM Press, 2006: 841-848. 7 Chapelle M Chi, A Zien. A continuation method for semi-supervised SVMs C/ Proceedings of the 23rd International Conference on Machine Learning, New York. USA: ACM Press, 2006: 185-192. 8 Chapelle A Zien. Semi-supervised classification by low density separation C/ Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics. Savannah, Barbados, USA: Pascal Press, 2005: 57-64. 9 Lee Y J, Mangasarian O L. SSVM: A smooth support vector machine for classification J. Computational Optimization and Applications (S0926-6003), 2001, 22(1): 5-21. 10 袁玉波, 严杰, 徐成贤. 多项式光滑的支撑向量机J. 计算机学报, 2005, 28(1): 9-17. 11 熊金志，胡金莲，袁华强, 等. 一类光滑支持向量机新