求解动态背包问题的多智能体进化算法  

Multiagent-Based Evolutionary Algorithm for Dynamic Knapsack Problem

作　　者：闫杨[1] 汪定伟[1] 王大志[1] 王洪峰[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110004

出　　处：《东北大学学报（自然科学版）》2009年第7期948-951,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金重点资助项目(70431003);国家自然科学基金创新群体项目(60521003);国家科技支撑计划项目(2006BAH02A09)

摘　　要：针对动态背包问题,提出了一种基于多智能体的进化算法(MAEA).通过智能体相互合作地模拟生物机制特征来寻求最优解.智能体生存于网格环境中,为了增加自身能量,智能体可以与其邻域展开竞争,并依据统计信息来获得知识进行学习.为了保持种群的多样性,在算法中引入了随机移民机制.通过对一系列动态背包问题的仿真实验可以看出,在离线性能指标下,这种引入了随机移民机制的基于多智能体的动态进化算法相比几类遗传算法可以获得更好的性能.A multiagent-based evolutionary algorithm （MAEA） is proposed to solve the dynamic knapsack problem, where the agents are co-evolving to simulate living organism features so as to find optimum solution. Existing in a grid-like environment, all agents shall compete with their neighborhood to enhance their energy and acquire knowledge through learning in according to statistical data. And the random immigration scheme is introduced into the algorithm to maintain the diversity of the population. Simulation results showed that the MAEA solution with random immigration scheme to dynamic knapsack problem can obtain a better performance than several other similiar genetic algorithms in according to the average-of-generation fitness taken as evaluation indices.

关 键 词：背包问题 多智能体 动态进化算法 随机移民 多样性 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]