A new global best guided artificial bee colony algorithm with application in robot path planning

https://doi.org/10.1016/j.asoc.2019.106037Get rights and content

Abstract

Artificial bee colony has received much attention in recent years as a competitive population-based optimization algorithm. However, its slow convergence speed and one-dimensional search strategy limit it from demonstrating advantage in separable functions. To address these concerning issues, this paper introduces a coevolution framework into ABC and designs a global best leading artificial bee colony algorithm with an improved strategy to accelerate its convergence and conquer the dependency of dimension separately. A set of classical and Congress on Evolutionary Computation 2015 benchmark functions are adopted for validating the efficiency of our algorithm. In addition, in order to show the practicality of our algorithm, a robot path-planning problem is tested, and our algorithm still achieves superior results.

Introduction

Karaboga [1] first proposed artificial bee colony (ABC) algorithm in 2005. Now it is one of the promising evolutionary algorithms (EAs), which simulates honeybees’ foraging behavior. Due to its few controlling parameters and easy implementation, ABC has been successfully applied to various practical problems, for example, pattern recognition [2], [3], magnetics [4], [5], neural network controlling [6], [7], and others [8], [9], [10], [11], [12], [13].

Although the ABC algorithm works well, there still is huge potential for further enhancing ABC’s performance, especially for the dimension-dependent problems. Since the framework in [14], [15] could successfully discriminate the dependent and independent dimensions groups, our paper proposes a coevolution framework to tackle the dimension-independent and dimension-dependent parts of a given optimization problem.

Our paper employs global best leading artificial bee colony dimension-independent (GLABC) and global best leading artificial bee colony dimension-dependent (GLABC-d) algorithms to deal with dimension-independent part and dimension-dependent part of problems, respectively. In GLABC, by comparing the search ability between the differential evolution (DE) and ABC, the updating equation of DE is introduced to the employed bee phase of ABC for enhancing its convergence rate and two Gaussian operators are proposed for balancing the global and local searches. In GLABC-d, a crossover strategy is adopted in onlooker bees to tackle the dimensions with relationship. A new strategy is also presented to enable onlooker bees to get more valuable information in potential solution space. A global best leading strategy is thoroughly employed in the onlooker bees of both GLABC and GLABC-d for accelerating their convergence rate, which is the reason we call our algorithm as global best leading ABC. We combine GLABC and GLABC-d into a coevolution framework called Co-GLABC. In the coevolution framework, we first discriminate the mutually dependent and mutually independent variables of a given problem, which inherits the differential grouping technique [16] to divide the total dimensions into several subsets. Then, the GLABC or the GLABC-d is selected for optimizing the separated subsets. Tested on the benchmark functions and the Congress on Evolutionary Computation 2015 (CEC2015) functions, the Co-GLABC proposed in this paper has a better performance.

In order to verify the practicality of Co-GLABC, we apply the algorithm to a robot path-planning problem. We compare the Co-GLABC algorithm with other EAs on this problem. The experimental results show that the Co-GLABC can find a more accurate path.

Although ABC exhibits a strong global search ability, researchers reveal that it still faces a challenge of slow convergence speed [17]. Therefore, plenty of works have been presented [4], [18], [19], [20], [21], [22], [23], [24], [25], [26], [27], [28], [29], [30], [31], [32] in recent years. X. Li and G. Yang [26] recoded the successful neighbor and successful controlling magnitude for each variable of each food source. Then they used this successful information to guide bees’ search. M.S. Kiran et al. [24] proposed several search equations and let bees to select one of them to update in an adaptive manner on the condition of considering many kinds of benchmarks’ characteristics. M.S. Kıran and O. Fındık [23] recorded the update orientation of individuals. If the individual is successfully updated, the recorded update orientation will be utilized in the next generation; I. Babaoglu [18] proposed a new search equation to conquer the stagnation phenomenon especially in the later stage of optimization; Zhu and Kwong [27] introduced a global best information for ABC to promote its exploitation ability and obtained a higher accuracy of solution. Gao et al. [19] divided the whole population into several subpopulations and proposed two communication mechanism among them to facilitate the optimization performance. Gao and Liu [21] eliminated the concept of employed bees and onlooker bees in traditional ABC which are replaced by two proposed strategies for global and local searches respectively. Akay and Karaboga [4] present a new frequency perturbation strategy to avoid getting stuck in local minima. For a better balance between coarse and precise search abilities of ABC, Gao proposed a new update equation by utilizing two random selected food sources and employed an orthogonal learning strategy in [20]. Karaboga and Gorkemli [22] proposed a new definition of the best solution among the current food source’s neighbors to precisely search on onlooker bee phase. Kuang et al. [25] introduced a chaotic distribution into scout bees to strengthen their global search ability. Gao et al. [28] defined a new search direction mechanism to overcome the oscillation phenomenon in the employed bees, and proposed an intelligent learning mechanism to accelerate the convergence speed of the worst employed bee. The proposed ABC algorithm (ABC-QAP) and its parallel version (PABC-QAP) in [29] incorporate the ABC meta-heuristic with Tabu search to optimize QAP. Zhou and Yao et al. [30] proposed a novel multi-colony algorithm, which divides the colony into three parts according to the individual fitness value. In [31], the gravity model was introduced into the ABC algorithm to select the better neighbors of the current individual and improve the exploitation ability.

The paper is organized as follows. Section 2 describes the standard artificial bee colony; Section 3 elaborates the motivation and details of the two GLABC algorithm, as well as the coevolution framework; In Section 4, comparison experiments among other ABC variants on some classical and CEC 2015 benchmarks are conducted, effectiveness evaluation of each part of the proposed Co-GLABC algorithm. In Section 5, the problem of robot path planning is introduced, and the experimental results of our algorithm applied to this problem are given. An integrate conclusion is presented in Section 6.

Section snippets

ABC framework

Artificial bee colony is a popular swarm optimization algorithm that motivated by the intelligence of foraging behavior in the honeybee colony. It was firstly proposed by Karaboga [1] in 2005 and had attracted much attention in recent years. In the colony, three different types of bees cooperate with each other to find the global optimum which has the minimum fitness value on an evaluation function. They have different division of works. Employed bees work to forage food sources which are

Coevolution global-best artificial bee colony algorithm (Co-GLABC)

Except for some basic benchmarks [17], [33], which are mutually dimension independent, some optimization problems are partially mutually dimension independent and partially mutually dimension dependent, or totally dimension dependent. To make ABCs suitable for solving these problems, this paper utilizes a coevolution framework and a global best leading strategy to address the dimension-dependent problem and accelerate the convergence rate of ABC, respectively.

Experimental and results

In this section, we conduct an integrated evaluation to estimate the achievements of our algorithms. Section 4.1 presents the explanation of testing benchmarks of this paper, including fourteen classical benchmarks and fifteen CEC2015 learning-based benchmarks; Comparison experiments and results among several state-of-the-art algorithms are conducted and presented in 4.2. In Section 4.3, each part of the GLABCs is tested separately for further evaluating their effectiveness.

Robot path planning

At present, with the rapid development of artificial intelligence, robots have been widely used in various fields. Mobile robots replace humans in many harsh environments, such as battlefields and disaster scenes. For mobile robots, path planning is one of the core research directions [32], [42]. Path planning is an important issue as it allows a mobile robot to get from point A to point B. The feasibility of motion planning is dependent on threatening areas, terrain, fuel, and time constraint.

Conclusion

This paper constructs a coevolution global best leading ABC algorithm to handle the optimization problems with dimension-independent and dimension-dependent parts. For the dimension-independent part, we introduce the search equation of DE into ABC’s employed bees’ phase to accelerate its convergence speed and bring the global best position to guide onlooker bees’ search. For the dimension-dependent parts, we bring a crossover strategy as well as the global best position to ABC’s onlooker bees’

CRediT authorship contribution statement

Feiyi Xu: Investigation, Software, Writing - original draft. Haolun Li: Writing - original draft, Software, Investigation. Chi-Man Pun: Methodology. Yujie Li: Data curation, Formal analysis. Yurong Song: Resources, Writing - review & editing. Hao Gao: Project administration, Supervision, Funding acquisition.

Declaration of Competing Interest

No author associated with this paper has disclosed any potential or pertinent conflicts which may be perceived to have impending conflict with this work. For full disclosure statements refer to https://doi.org/10.1016/j.asoc.2019.106037.

Acknowledgments

The authors acknowledge support from National Key R&D Program of China (2018YFA0702200), National Nature Science Foundation of China (No. 61571236, 61931012), the Science and Technology on Space Intelligent Control Laboratory, China (KGJZDSYS-2018-02, 6142208180302), the Research Committee of University of Macau, China (MYRG2019-00086-FST, MYRG2018-00035-FST), the Science and Technology Development Fund of Macau SAR, China under Grant 041-2017-A1, and Postgraduate Research & Practice Innovation

References (48)

  • KıranM.S. et al.

    A directed artificial bee colony algorithm

    Appl. Soft Comput.

    (2015)
  • KiranM.S. et al.

    Artificial bee colony algorithm with variable search strategy for continuous optimization

    Inform. Sci.

    (2015)
  • LiX. et al.

    Artificial bee colony algorithm with memory

    Appl. Soft Comput.

    (2016)
  • ZhuG. et al.

    Gbest-guided artificial bee colony algorithm for numerical function optimization

    Appl. Math. Comput.

    (2010)
  • DokerogluT. et al.

    Artificial bee colony optimization for the quadratic assignment problem

    Appl. Soft Comput.

    (2019)
  • ZhouJ. et al.

    An individual dependent multi-colony artificial bee colony algorithm

    Inform. Sci.

    (2019)
  • XiangW. et al.

    An improved artificial bee colony algorithm based on the gravity model

    Inform. Sci.

    (2018)
  • ShiY. et al.

    An improved artificial bee colony and its application

    Knowl.-Based Syst.

    (2016)
  • GaoH. et al.

    Particle swarm optimization based on intermediate disturbance strategy algorithm and its application in multi-threshold image segmentation

    Inform. Sci.

    (2013)
  • AkayB. et al.

    A modified artificial bee colony algorithm for real-parameter optimization

    Inform. Sci.

    (2012)
  • HossainM.A. et al.

    Ferdous autonomous robot path planning in dynamic environment using a new optimization technique inspired by bacterial foraging technique

    Robot. Auton. Syst.

    (2015)
  • LiangJun-Hao et al.

    Efficient collision-free path-planning of multiple mobile robots system using efficient artificial bee colony algorithm

    Adv. Eng. Softw.

    (2015)
  • KarabogaD.

    An Idea Based on Honey Bee Swarm for Numerical OptimizationTech. Rep.-tr06

    (2005)
  • ZhangX. et al.

    A modification of artificial bee colony algorithm applied to loudspeaker design problem

    IEEE Trans. Magn.

    (2014)
  • Cited by (76)

    • Multi-robot path planning using learning-based Artificial Bee Colony algorithm

      2024, Engineering Applications of Artificial Intelligence
    View all citing articles on Scopus
    1

    These authors contributed to the work equally and should be regarded as co-first authors.

    View full text