资源描述：
《基于蚁群算法的多维0_1背包问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、742007,43(30)ComputerEngineeringandApplications计算机工程与应用基于蚁群算法的多维0-1背包问题的研究汪采萍1,213,胡学钢,王会颖1,213WANGCai-ping,HUXue-gang,WANGHui-ying1.合肥工业大学计算机与信息学院,合肥2300092.安徽职业技术学院,合肥2300513.安徽大学计算机学院,合肥2300391.SchoolofComputerScienceandInformation,HefeiUniversityofTechnol
2、ogy,Heifei230009,China2.AnhuiVocationalandTechnicalCollege,Heifei230051,China3.SchoolofComputerScience,AnhuiUniversity,Hefei230039,ChinaE-mail:wangcp70@163.comWANGCai-ping,HUXue-gang,WANGHui-ying.Onmulti-dimension0-1knapsackproblembasedonantcolonyalgorithm.Co
3、mputerEngineeringandApplications,2007,43(30):74-76.Abstract:Antcolonyalgorithmisanalyzedandoptimizedinthisarticle.Anewsolving0-1knapsackproblemalgorithm,Multi-dimension0-1KnapsackProblemAntColonyAlgorithm(MKPACA),isputforward.Itgreatlyreducesthesearchingtimeo
4、fantcolonyalgorithm.Italsoeffectivelyamelioratesthedisadvantageofeasilyfallinginlocalbestofantcolonyalgorithm.Thesimulationresultsshowthatthealgorithmismoreefficient.Keywords:multi-dimension0-1knapsackproblem;antcolonyalgorithm;Multi-dimension0-1KnapsackProbl
5、emAntColonyAlgorithm(MKPACA)摘要:系统地阐述了蚁群算法,并对它进行改进、优化。将蚁群算法应用于求解多维0-1背包问题,提出一种求解多维0-1背包问题的算法——多维0-1背包问题蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷。仿真实验取得了较好的结果。关键词:多维0-1背包问题;蚁群算法;多维0-1背包问题蚁群算法文章编号:1002-8331(2007)30-0074-03文献标识码:A中图分类号:TP3911引言统,具有分布式的计算特性,具有
6、很强的通用性、顽健性、鲁棒背包问题是运筹学中一个典型的优化难题[8],是一个NP-性,易于与其它优化算法融合,是基于总体优化的方法,是解决完全问题。对该问题求解方法的研究无论是在理论上,还是在NP问题的有效工具。实践中都具有一定的意义,如资源分配、投资决策、装载问题、本文提出一种基于蚁群算法求解多维0-1背包问题的算网络资源分配等均可建模为背包问题[1]。求解背包问题的方法法,多维0-1背包问题蚁群算法。该算法对常规的蚁群算法进主要有回溯算法、贪婪算法、遗传算法、禁忌搜索算法、模拟退行改进。它大大减少了蚁群算法的
7、搜索时间,有效改善了蚁群火算法等。算法易于过早地收敛于非最优解的缺陷。仿真实验取得了较好蚂蚁算法(AntColonyAlgorithm,ACA)是一种源于大自然的效果。的新型仿生类进化算法,源于对蚂蚁觅食模型的研究。它是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能优化2常规蚁群算法(AS)算法。它由意大利学者DorigoM.等[7]首先提出,在离散型组合蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的优化问题中表现突出,成功地应用于求解TSP、二次分配、图着最短路径,并且能随环境的变化,适应性地搜索新的路
8、径,产生色、车辆调度、集成电路设计及通信网络负载等问题。蚂蚁算法新的选择。根本原因是蚂蚁在寻找食物源时,能在其走过的路的基本思想是模仿蚂蚁依赖信息素(pheromone)进行通信而显上释放一种特殊的分泌物--信息素(pheromone),随着时间的示出的社会性行为,在智能体(agent)定义的基础上,由一个贪推移该物质会逐渐挥发,后来的蚂蚁选择该路径的概率与当时心法指导下
