一种求解0-1背包问题的混合粒子群算法.pdf

维普资讯 第2l卷第4期 长 沙 电 力 学 院 学 报 ( 自 然 科 学 版 ) V01．2l No．4 2006年11月 JOURNALOFCHANGSHAUNIVERSITYOFELECTRICPOWER(NATURALSCIENCE) N0v．20 06 一 种求解 O一1背包问题的混合粒子群算法 叶永春 ，车林仙 ，何兵 (1．泸州职业技术学院 电子与信息工程系，四川 泸州 646005；2．泸州职业技术学院 机电工程系，四川泸州 646005； 3．泸州职业技术学院机电工程研究所，四川 泸州 646005) 摘 要：H-z~0—1背包问题，提出一种具有修复策略的、贪心算法与二进制粒子群算法相结合的混合智能算法． 数值试验结果表明，该方法能在一定程度上克服早熟现象，且收敛速度较快．因此，应用该混合智能算法求解0—1 背包问题是比较有效的． 关 键 词 ：0—1背包问题；粒子群算法；混合智能算法 中图分类号：022；TP14 文献标识码 ：A 文章编号：1006—7140(2006)04—0087—04 A KindofHyb~dParticleSwarm OptimizationAlgorithm for Solving0—-1KnapsackProblems YEYong—chun ，CHE Lin—xian ．-，HE Bing’ (1．DepartmentofElectronic＆InformationEngineering，LuzhouVocational＆TcehnicalCollege，Luzhou646005，China； 2．DepartmentofMcehatronicEngineering，LuzhnuVocational＆TechnicalCollege，Luzhou646005，China； 3．InstituteofMcehatronicEngineering，LuzhouVocational＆TcehnicalCollege，Luzhou646005，China) Abstract：Aimedatthe0—1knapsackproblems，htearticleproposesakindofhybridintelligencealgo— rihtmcombiningwihthteadjustingstrategy，htegreedyalgorihtmandhtebinaryparticleswarmoptimiza— tionalgorihtm．Resultsofnumerical tests show htathtealgorihtm Cna avoidprecociousphenomenatoa certain extentna dithashigherrateofconvergence．Therefore，htehybridintelligencealgorihtm iseffec— tivetosolve0一Iknapsackproblems． Keywords：0—-1knapsackproblem；particleswarm optimization；hybridintelligencealgorihtm 背包问题 (Knapsackproblem)是一个典型的 NP．hard完全问题，其本质是 0—1整数规划问 收稿 日期；2006—09—10 基金项 目：泸州市科技计划项 目(200610) 作者简介：叶永春 (1972一)，女，讲师，硕士，主要从事计算智能及算法设计与分析方面的研究