Bat Algorithm Research Based On Hybrid Strategy

Bat algorithm (BA) is one of novel metaheuristic algorithms introduced by Yang Xin-She, who is a professor in Cambridge University, in 2010. Yang proposed this algorithm inspired by predation and echolocation behavior of micro-bat. Not only the BA has a simple structure, less parameter, robustness, but also it is easy to understand and program implement. In recently, more and more researchers are interested in the algorithm, which has made it gradually be one of popular research branches of swarm intelligence and intelligent optimization algorithms. It is a fresh algorithm, after all, it may has more or less defects, such as, easily trapped into local optimal solution, low convergence speed, etc. Largely, they limit the application of the algorithm. So aiming at the shortcoming, some improved strategies will be proposed in this thesis, so as to increase optimization efficiency.0-1 Knapsack Problem (0-1 KP) is classic combinatorial optimization problem. It is widely used in many fields in actual life, such as, budget control, loading problem, project selection, investment problem, etc. It is also study as sub-problem. From foregone literatures, the method of solving 0-1KP is divided into accurate algorithm and heuristic algorithm. Because of computing complexity, the large-scale problem cannot be solved with accurate algorithm. In that case, the heuristic algorithm gains better result.In this thesis, the main research work is as follow:(1)Aiming at the problems of easily relapsing into local extremum and low convergence speed of basic BA, this paper proposes an improved hybrid BA, through introducing genetic operation of Genetic Algorithm (GA). This algorithm combines advantage of BA and GA. It includes updating rules of standard velocity and position, and ideas of selection, crossover and mutation of GA. In the process of algorithm fusion, a new crossover operator, based on velocity vector of BA, has been proposed. It can dynamically adjust the population, and avoid premature convergence. Test result shows that this way not only increases the population diversity, individuals jump out of local optimal solution and avoid premature convergence; but also achieves good effect of increasing the speed of population converges the global optimal solution.(2)In view of inertia weight influence on algorithm search ability, this paper introduces the concept of inertia weight into BA. Through researching Bak-Sneppen Model (BS Model) of Self-Organized Criticality (SOC), I propose a novel BA based on BS model and strategy of changing inertia weight. The experimental test shows that the new algorithm model greatly improves the searching ability, the convergence speed and precision of the original algorithm.(3)The improved BA is applied to solving 0-1 KP. According to the characteristics of this kind of problem, the basic BA transforms the binary edition one. In addition, by modifying the bat individuals' position updating formula, the optimization process of improved BAs is better for solving 0-1 KP. Finally, by the MATLAB simulation test platform, it gains optimal target value.