The Improved Binary Bees Algorithm And Its Application In Combinatorial Optimization Problems

This paper proposes the study on―the Improved Binary Bees Algorithm and itsapplication in combinatorial optimization problems‖, involving the contents ofalgorithm development and problems solving.The study on combinatorial optimization problem (COP) has importanttheoretical and practical values. As an important branch of Operations Research,COP research is widely applied in the fields of transport planning, logisticsmanagement, information science, engineering, etc. As COP essentially belongs toan NP-complete problem, and especially with respect to high-dimensional andlarge-scaled COPs whose variable space and solution space are usually in complexshapes, their exact solutions can hardly be solved in a limited computing time bydeterministic algorithms. On the contrary, with the rapid development of computertechnology, heuristics provide an effective method for the solving of feasiblesolutions (or suboptimal solutions) for COPs. Especially, swarm intelligencealgorithms, as a subset of heuristics, have a significant advantage due to theirfeatures of clear concepts, strong robustness and distributed computing.A novel swarm intelligence algorithm, named―Improved Binary BeesAlgorithm (IBBA)‖is proposed in this paper, with its application in tworepresentative COPs. Specifically, the study covers the following contents.Firstly, we introduce a series of basic concepts of COP and its solving, as wellas, two typical COPs (traveling salesman problem and flowshop schedulingproblem). We further summarize common-used multi-objective handling techniquesand constraint handing techniques in solving multi-objective multi-constraint COPs.Then, the IBBA is proposed. It, on the one hand, inherits the commoncharacteristics of the bees algorithm family as functional partitioning and parallelimplementation of global search and local search, and on the other hand, adjusts theelite selection strategy and local search mechanism to further improve algorithmperformance. The effectiveness of the IBBA is initially proved by its application in single-objective and multi-objective traveling salesman problems (TSPs).Next, a multi-objective multi-constraint four-dimensional COP is extractedfrom our study on elderly and disabled assistant service robotics, named―missionplanning for a team of modular and reconfigurable service robots‖. This problem isintroduced, analyzed and modeled in the perspectives of engineering backgroundintroduction, problem analyzing, definition of a solution, optimization objectivemodeling and constraint modeling.Finally, the above COP is solved by the proposed IBBA. In comparativeexperiments, the IBBA’s effectiveness and its advantage over the prototype areexhibited in the indices of solution quality, computational efficiency, single-objectiveoptimization and robustness to problem scale.This paper has two innovations. First, it develops the novel algorithm IBBA andintegrates the methods of combinatorial scheme expression and evolution,multi-objective handling and constraint handing into the basic algorithm frameworkto solve COPs. Second, it extends the field of research of modular andreconfigurable robot (MRR) by extending, and then solving, the―configurationdesign‖problem of a MRR team to a comprehensive problem integrating missionassignment and configuration design.