Abstract:
The artificial bee colony (ABC) algorithm is widely applied in many fields, but it suffers from slow convergence, so its solutions perform well in exploration but poorly in exploitation. Researchers from Kanazawa University and the University of Toyama proposed a scale-free mechanism to guide the search of the ABC algorithm. They verified that scale-free networks improve the algorithm's optimization performance and enhance the search ability of other metaheuristic algorithms.
Kanazawa – Honey bees are not only vitally important pollinators of food crops, their hunt for rich food sources has also proved to be an excellent model for optimizing numerical problems. Now, researchers from Kanazawa University and the University of Toyama have used the intelligent behavior of bees to improve optimization performance in real-world problems.
Inspired by the foraging behavior of a honey bee colony, the artificial bee colony (ABC) algorithm is a relatively new population-based algorithm for solving complex optimization problems. In the algorithm, employed bees look for food sources and share the information with onlooker bees, who then choose a food source to exploit. Scout bees conduct random searches to discover new food. The positions of food sources represent possible solutions to an optimization problem. The ABC algorithm has fewer control parameters, a simpler structure, and more convincing performance than other methods, so it has been widely applied in fields such as data mining and vehicle routing. "However, it takes many iterations to obtain a solution," explains Yuki Todo from the Faculty of Electrical and Computer Engineering at Kanazawa University, "thus, it performs well in exploration but poorly in exploitation."
Therefore, the researchers developed a novel scale-free mechanism to guide the search of the ABC algorithm and verified its performance using real-world problems. They analyzed how the network properties of a scale-free network, namely, the power law distribution and low degree-degree correlation coefficient, influence the optimization process. In each iteration, employed bees (or onlooker bees) were placed onto the nodes of the scale-free network according to the quality of their food sources. Employed bees with high-quality food sources were relocated to high-degree nodes and employed bees with relatively low-quality food sources were relocated to low-degree nodes. Using these rules, the power law distribution property made low-quality employed bees more likely to connect with high-quality employed bees.
The scale-free mechanism enables each employed bee to learn more effective information from its neighbors, which improves the exploitation ability of the ABC algorithm. Because the low degree-degree correlation coefficient property can control the information exchange among high-quality employed bees, it stops the information of these bees from taking over the whole population quickly. This helps to maintain population diversity and avoids the problem of the population converging too early. "During the optimization process, the scale-free ABC algorithm obtains a better balance between exploration and exploitation," says Junkai Ji from the Faculty of Engineering at the University of Toyama, "and also enhances the search ability of other iterative approaches, such as the flower pollination algorithm."
Figure.
Schematic diagram of SFABC. The scale-free artificial bee colony algorithm (SFABC) in which the search is guided by a scale-free network is proposed. The mechanism enables the SFABC search to follow two rules. First, the bad food sources can learn more information from the good sources of their neighbors. Second, the information exchange among good food sources is relatively rare. The employed bees are ranked based on the qualities of their food sources and labeled by the ranking values.
Article
An artificial bee colony algorithm search guided by scale-free networks
Journal: Information Sciences
Authors: Junkai Ji, Shuangbao Song, Cheng Tang, Shangce Gao, Zheng Tang, Yuki Todo
DOI: 10.1016/j.ins.2018.09.034
PAGE TOP