精英交叉二进制蝙蝠算法求解0-1背包问题*

针对基本蝙蝠算法收敛速度慢,易早熟的问题,提出了一种精英交叉二进制蝙蝠算法。该算法借鉴精英策略和遗传算法中的交叉机制,按照一定比例选择蝙蝠群中的精英个体进行交叉,将得到子蝙蝠群和父蝙蝠群进行混合择优,保证蝙蝠群的多样性和优秀性,提高了全局搜索能力；为提高局部搜索能力,算法在对每个个体计算适应度值时加入贪心策略；另外,通过对蝙蝠群最优解进行动态监测,适时对种群进行柯西变异,使算法具有跳出局部极值的能力。通过对5个实例的仿真计算比较表明,该算法与改进贪心遗传算法,贪心二进制蝙蝠算法和病毒协同蝙蝠算法相比,无论是收敛速度还是寻优能力都表现优异,为求解0-1背包问题提供了一个实用的算法。

Elite cross binary bat algorithm for solving 0-1 knapsack problem

To solve the problem of being slow convergence and prone to premature in the classical bat algorithm,in this paper ,an elitist individuals cross binary bat algorithm (ECBBA) is proposed. Elite strategy and the cross-fertilize are carried out in this algorithm ,which selects some elite bats in the group to make cross firstly,and then choose the bats with higher fitness from the offspring and parents as the new generation bats.The means can keep multiformity and superiority of the group and improve the ability of getting the best solution in global .To improve ability of the local searching ,the greedy strategy is applied in computing the fitness of every bat.On the other hand,through monitoring the change of the global best bat,the algorithm will make Cauchy mutation in some bats which can help the algorithm to jump the local optima.Simulation experiment on 5 0-1kp shows that the proposed algorithm ECBBA has faster convergence rate,higher precision and stronger capability of searching global optimal solution than the GMOGAS,GBBA and VEBA algorithms .