A new global best guided artificial bee colony algorithm with application in robot path planning
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)
- et al.
An image watermarking scheme in wavelet domain with optimized compensation of singular value decomposition via artificial bee colony
Inform. Sci.
(2015) - et al.
An efficient image segmentation method based on a hybrid particle swarm algorithm with learning strategy
Inform. Sci.
(2016) - et al.
Forecasting stock markets using wavelet transforms and recurrent neural networks: An integrated system based on artificial bee colony algorithm
Appl. Soft Comput.
(2011) - et al.
Optimal filter design using an improved artificial bee colony algorithm
Inform. Sci.
(2014) - et al.
Self-generated fuzzy systems design using artificial bee colony optimization
Inform. Sci.
(2015) - et al.
Solving the large-scale hybrid flow shop scheduling problem with limited buffers by a hybrid artificial bee colony algorithm
Inform. Sci.
(2015) - et al.
An adaptive artificial bee colony algorithm for long-term economic dispatch in cascaded hydropower systems
Int. J. Electr. Power Energy Syst.
(2012) Artificial bee colony algorithm with distribution-based update rule
Appl. Soft Comput.
(2015)- et al.
A modified artificial bee colony algorithm
Comput. Oper. Res.
(2012) - et al.
A quick artificial bee colony (qABC) algorithm and its performance on optimization problems
Appl. Soft Comput.
(2014)
A directed artificial bee colony algorithm
Appl. Soft Comput.
Artificial bee colony algorithm with variable search strategy for continuous optimization
Inform. Sci.
Artificial bee colony algorithm with memory
Appl. Soft Comput.
Gbest-guided artificial bee colony algorithm for numerical function optimization
Appl. Math. Comput.
Artificial bee colony optimization for the quadratic assignment problem
Appl. Soft Comput.
An individual dependent multi-colony artificial bee colony algorithm
Inform. Sci.
An improved artificial bee colony algorithm based on the gravity model
Inform. Sci.
An improved artificial bee colony and its application
Knowl.-Based Syst.
Particle swarm optimization based on intermediate disturbance strategy algorithm and its application in multi-threshold image segmentation
Inform. Sci.
A modified artificial bee colony algorithm for real-parameter optimization
Inform. Sci.
Ferdous autonomous robot path planning in dynamic environment using a new optimization technique inspired by bacterial foraging technique
Robot. Auton. Syst.
Efficient collision-free path-planning of multiple mobile robots system using efficient artificial bee colony algorithm
Adv. Eng. Softw.
An Idea Based on Honey Bee Swarm for Numerical OptimizationTech. Rep.-tr06
A modification of artificial bee colony algorithm applied to loudspeaker design problem
IEEE Trans. Magn.
Cited by (76)
Path planning algorithms in the autonomous driving system: A comprehensive review
2024, Robotics and Autonomous SystemsMulti-robot path planning using learning-based Artificial Bee Colony algorithm
2024, Engineering Applications of Artificial IntelligenceA Q-learning based multi-strategy integrated artificial bee colony algorithm with application in unmanned vehicle path planning
2024, Expert Systems with ApplicationsA mixing algorithm of ACO and ABC for solving path planning of mobile robot
2023, Applied Soft Computing
- 1
These authors contributed to the work equally and should be regarded as co-first authors.