人工生命Bug模型二元蚁群算法求解多0/1背包问题-《计算机技术与发展》

文章信息/Info

Title:: Binary Ant Colony Algorithm Based on Bug Artifical Life for 0/1 Knapsack Problem

Keywords:: Bug artifical life model; binary ant colony algorithm; cellular automata(CA); 0/1Knapsack problem

摘要:: 从一维有趣的Bug人工生命模型出发,并对该模型进行扩展,将蚂蚁对信息素的大小进行选择的概率函数作为细胞的转换函数,对二元蚁群算法从人工生命的角度重新进行描述,同时引入更多的随机因素有效防止二元蚁群算法易陷入局部最优的缺陷,然后通过增加细胞状态集合元素数目的方式对Bug模型二元蚁群算法进行扩展,应用于多0/1背包问题的求解.仿真实验表明,运用文中算法不仅能快速有效地完成多0/1背包问题的求解过程,而且在一定程度上体现了计算的本质

Abstract:: Starting with the one dimension Bug artificial life model,then expanded,the ants on the size of the pheromone choice probabili-ty function as cell transformation function. Ant colony algorithm for binary is described from the view of the artificial life. At the same time introduce more random factors to effectively prevent binary ant colony algorithm is easy to fall into local optimum of the defect. Through increasing the number of the cell,the binary ant colony algorithm of Bug model is extended,then the algorithm is used to solved the typical multiple 0/1 Knapsack problem. Experimental results show that this model not only has a good convergence,but also reflects the essence of the computation