استفاده از الگوریتم کلونی زنبور مصنوعی برای مشکل فروشنده سیار
ترجمه نشده

استفاده از الگوریتم کلونی زنبور مصنوعی برای مشکل فروشنده سیار

عنوان فارسی مقاله: یک الگوریتم کلونی زنبور مصنوعی با یک تابع انتخاب اصلاح شده برای مشکل فروشنده سیار
عنوان انگلیسی مقاله: An artificial bee colony algorithm with a Modified Choice Function for the traveling salesman problem
مجله/کنفرانس: ازدحام و محاسبات تکاملی - Swarm And Evolutionary Computation
رشته های تحصیلی مرتبط: کامپیوتر
گرایش های تحصیلی مرتبط: مهندسی الگوریتم ها و محاسبات، هوش مصنوعی، محاسبات ابری
کلمات کلیدی فارسی: ماوراء-اکتشافی، فراابتکاری، الگوریتم زنبور، مشکل بهینه سازی ترکیبی، جستجوی محله، Lin-Kernighan
کلمات کلیدی انگلیسی: Hyper-heuristic، Metaheuristic، Bee algorithm، Combinatorial optimisation problem، Neighbourhood search، Lin-Kernighan
نوع نگارش مقاله: مقاله پژوهشی (Research Article)
نمایه: Scopus - Master Journals List - JCR
شناسه دیجیتال (DOI): https://doi.org/10.1016/j.swevo.2018.08.004
دانشگاه: School of Computer Sciences, Universiti Sains Malaysia, Malaysia
صفحات مقاله انگلیسی: 14
ناشر: الزویر - Elsevier
نوع ارائه مقاله: ژورنال
نوع مقاله: ISI
سال انتشار مقاله: 2019
ایمپکت فاکتور: 7/893 در سال 2018
شاخص H_index: 43 در سال 2019
شاخص SJR: 1/278 در سال 2018
شناسه ISSN: 2210-6502
شاخص Quartile (چارک): Q1 در سال 2018
فرمت مقاله انگلیسی: PDF
وضعیت ترجمه: ترجمه نشده است
قیمت مقاله انگلیسی: رایگان
آیا این مقاله بیس است: بله
آیا این مقاله مدل مفهومی دارد: دارد
آیا این مقاله پرسشنامه دارد: ندارد
آیا این مقاله متغیر دارد: ندارد
کد محصول: E13121
رفرنس: دارای رفرنس در داخل متن و انتهای مقاله
فهرست مطالب (انگلیسی)

Abstract

1- Introduction

2- Related work

3- The proposed model

4- Results and discussion

5- Conclusions

References

بخشی از مقاله (انگلیسی)

Abstract

The Artificial Bee Colony (ABC) algorithm is a swarm intelligence approach which has initially been proposed to solve optimisation of mathematical test functions with a unique neighbourhood search mechanism. This neighbourhood search mechanism could not be directly applied to combinatorial discrete optimisation problems. In order to tackle combinatorial discrete optimisation problems, the employed and onlooker bees need to be equipped with problem-specific perturbative heuristics. However, a large variety of problem-specific heuristics are available, and it is not an easy task to select an appropriate heuristic for a specific problem. In this paper, a hyper-heuristic method, namely a Modified Choice Function (MCF), is applied such that it can regulate the selection of the neighbourhood search heuristics adopted by the employed and onlooker bees automatically. The Lin-Kernighan (LK) local search strategy is integrated to improve the performance of the proposed model. To demonstrate the effectiveness of the proposed model, 64 Traveling Salesman Problem (TSP) instances available in TSPLIB are evaluated. On average, the proposed model solves the 64 instances to 0.055% from the known optimum within approximately 2.7 min. A performance comparison with other state-of-the-art algorithms further indicates the effectiveness of the proposed model.

Introduction

A computational optimisation methodology involves finding feasible solutions from a finite set of solutions, and identifying only the optimal solution(s). Swarm intelligence algorithms constitute a sub-class of computational optimisation methodology [1]. Swarm intelligence algorithms are developed based on emergence of collective behaviours pertaining to a population of interacting individuals in adapting to the local and/or global environments. Examples of swarm intelligence algorithms include Particle Swarm Optimisation (PSO) [2], Ant Colony Optimisation (ACO) [3], Bat Algorithm (BA) [4], Firefly Algorithm (FA) [5], Cuckoo Search Algorithm (CSA) [6], and bee-inspired algorithms [7–9]. Bees are highly organised social insects. Their survival relies on assigning an important task to each bee in a cooperative mode. The tasks include reproduction, foraging, and constructing hive. Within these tasks, foraging is one of the most important tasks, because the bee colony must ensure an undisrupted supply of food to survive. The food foraging behaviours of bees can be computationally realised as algorithmic tools to solve various optimisation problems. The Artificial Bee Colony (ABC) algorithm is one of the popular beeinspired algorithms. Proposed by Karaboga [7], it is inspired by the foraging behaviours of honey bees in a colony. In the ABC algorithm, a food source represents a possible solution to the optimisation problem in the search space, and the nectar amount of the food source represents the fitness of that solution. The ABC algorithm defines three types of bees: employed bees, onlooker bees, and scout bees. An employed bee looks for new food sources around the neighbourhood of the food source that it has previously visited. An onlooker bee observes dances and selects a food source to visit. It tends to select good food sources from those found by the employed bees. A scout bee searches for new food sources randomly. The mechanism of the ABC algorithm is as follows. The employed bees first perform a neighbourhood search nearby the food source in their memory (i.e. solution). Then, they go back to the hive and perform dances. The dances inform the onlooker bees about the fitness of each solution. Each onlooker bee observes and selects a food source to perform another neighbourhood search based on a probability proportional to the food source fitness (i.e. a roulette wheel selection). The onlooker bees tend to select good food sources from those found by the employed bees. The employed and onlooker bees perform neighbourhood search by perturbing an existing solution to produce a new solution.