Research On The Bees Algorithm And Its Application

Swarm intelligence stems from the problem-solving ability of social species that have been evolved for hundreds of thousands of years in nature on the earth.Many of the problems encountered by those species are considered to be of great complexity by human beings.Swarm-based intelligent optimization methods are inspired by the metaphor from behaviors of varied species with predominantly socializing characteristics in ecosystem.They function with analogous biological mechanism.The development of these methods has been perceived as an effective facilitator for handling NP-hard problems that are impossible to solve by traditional optimizers.The Bees Algorithm was one of the swarm intelligent algorithms,invented by Professor Pham in 2005 in the UK.The algorithm takes inspirations from foraging behaviors of honeybees.It is primarily imitates how a colony discovers,selects and eventually collects superior nectar.It is featured by a direct combination of neighborhood search for exploitation and global search for exploration,and this is embodied by role division of scout bees in colony.It is therefore easy for manipulation.It has been successfully applied to solve engineering problems.However,the theoretical investigation of this algorithm has far from being mature.The convergence features of individual scout and scout population in an optimization process need to be analyzed vigorously with mathematical methods.The researches carried out in this thesis try to cope with these deficiencies.Furthermore,the thesis also aims to improve the algorithm by introducing several strategies and apply it to solve service composition problem in a Cloud Manufacturing environments.The primary work in this thesis involves:(1)Modeling the Bees Algorithm with Markov chain for theoretical analysis.The establishment is realized from modeling individual scout bee and scout population.The Markov property of the states of a scout bee and scout population in optimization process is mathematically formulated with rigorousness.The scout state transfer probability is calculated and presented,which underpins the Markov property of scout population.The scout population state is further categorized into groups according to fitness.This move simplifies the calculation and analysis of the algorithm's asymptotic property.The convergent characteristics of the algorithm,as well as the influences of the neighbourhood shrinking and site abandonment strategies,are analyzed based on the established model.(2)Improving the algorithm with a labor adjustment strategy.The honeybee colony of the algorithm consists of several divisions of bees,which determines the optimizing performance.The quantities of the divisions are predefined as parameters and specified in the initialization step.The determination of these parameters is usually set empirically so that the algorithm could perform efficiently.The proposed strategy attempts to tune the number of bees playing different roles according to fitness sample by current scout population while keeping the entire colony unchanged.It allows the algorithm a degree of adaptability so as to make the algorithm less reliant on prior knowledge.(3)Extending the Bees Algorithm to multi-modal optimization.The intrinsic characters like parallel computation,direct combination of neighborhood and global search and so on make the algorithm advantageous for multi-model optimization.Several new concepts and strategies are integrated into the Bees Algorithm,making it competent for handling multi-modal optimization problems.The colony size of the proposed algorithm can be tuned based on the number of optima detected.This prevents the algorithm from being inefficient or yielding low accuracy due to the inadequate colony size predefined.(4)Introducing a balanced neighborhood search strategy to the Bees Algorithm.This strategy combines random search and pseudo gradient search and utilizes their respective advantages.It takes into account the latest search experiences and then specifies the distribution of foragers in a patch for neighborhood search.If a neighborhood search does not produce any improvement to a solution,or the distribution of foragers that sampled improve fitness in consecutive iteration varies too much,randomness will gradually take dominancy within a neighborhood range.On the contrary,if foragers obtain improved fitness upon similar distribution in consecutive iteration,it is reasonable to believe foragers following the same distribution will get higher fitness in the nest iteration.The balance search strategy does not require much computational costs but enhances the search efficiency of the Bees Algorithm.(5)Applying the Bees Algorithm to resource service composition in Cloud Manufacturing.The multi-user resource service composition in Cloud Manufacturing is an NP-hard problem,and is included as an exemplification for the investigation on how the Bees Algorithm can be applied.Also,the thesis details how the algorithm is implemented to deal with this multi-objective combinatorial optimization problem with constraints.A seeded initial service is adopted by the algorithm in the initialization step.This initial service is constructed with the integration of users' historical experiences about candidate services or feedbacks recorded in cloud platforms.The search based on seeded initial service is demonstrated to have higher success rate and search efficiency.