多目标0-1规划的元胞竞争决策算法.pdfVIP

上 海理 工大学学报 第33卷 第2期 J．UniversityofShanghaiforScienceandTechnology Vo1．33 No．2 2011 文章编号：1007—6735(2011)02—0163—05 多目标 0．1规划的元胞竞争决策算法 熊小华 ， 马 良 ， 宁爱兵 (1．上海理工大学 管理学院，上海 200093；2．上海第X．业大学 计算机与信息学院，上海 201209) 摘要：将元胞演化规则与竞争决策算法相结合 ，提 出了一种求解多 目标0．1规划问题的元胞竞争 决策算法．大量数据测试和验证表明，该算法能有效提高非劣解的分布性和多样性． 关键词：竞争决策算法；元胞 自动机；多目标；O一1规划 中图分类号：0223 文献标志码：A Cellularcompetitivedecisionalgorithm for multi·objective0-1programmingproblem XIONGXiao-hua．-． MALiang ． NINGAi．bing (1．BusinessSchool，UniversityofShanghaiforScienceandTechnology，Shanghai200093，China； 2．CollegeofComputerandInformation，ShanghaiSecondPolytechnicUniversity，Shanghai201209，China) Abstract：Combiningtheconceptsofcellularautomata、vi山 ocmpetitivedecisionalgorithm，acellular ocmpetitivedceisionalgorithmformulti-objectives0—1progmmn~gproblemwaspresented．Thealgorithm wasthenusedtosolvemanyinstancesofmulti-objectives0-1programmingandtheocmpuattionalresults show itcanimproveeffcetivelythediversityanddistributionofParetooptimalset． Keywords：competitivedecisionalgorithm；cellularautomata；multi—objectives；0—1pro— gramming 多 目标 0．1规划是以一维背包问题的0-1整数 解往往并不存在，一般所要求的都是一组相互之间 规划为原型发展起来的多个约束、多个 目标的最优 无法区分优劣的非劣解 (non-dominatedsolution)， 化问题，在投资决策、经济预算以及资源分配等问题 也称有效解或Pareto解．多 目标优化问题的Pareto 中有着广泛的应用．这种具有多个约束、多个 目标的 解只是一个可以接受的非劣解，并且大多数的Pare— 组合优化问题，统称为多 目标优化问题(MOP)_1-2]． to解的个数很多，甚至是无穷大[2]． 针对多个彼此冲突的目标 ，如何获取这些问题的最 0-1整数规划属于NP(非确定多项式)完备问 优解，一直都是科学界和工程界关注的焦点问题．由 题类，是否存在有效算法尚不可知，已有的精确算法 于多 目标意义下，使得所有 目标都达到最佳的最优 仅能解决小规模问题，而启发式算法又不能保证得 收稿 日期：2011—02—25 项 目基金：国家 自然科学基金资助项 目；上海市重点学科建设资助项 目($30504)． 作者简介：熊小华(1978一)，女，博士研究生．研究方向：算法设计、系统工程．E—mail：xiong_xiao_hua@163．com； 马 良(联系人)，男，教授．研究方向：算法设计 、系统工程．