Photo Photo Photo Photo Photo Photo

Print
E-mail
Computer Science: Harmony-Scatter Search to Solve Travelling Salesman Problem

 

Harmony-Scatter Search to Solve Travelling Salesman Problem

Ahmed T. Sadiq Al-Obaidi*

Department of Computer Science, University of Technology, Baghdad, Iraq.

Abstract

This paper presents a hybrid metaheuristic algorithm which is Harmony-Scatter Search (HSS). The HSS provides Scatter Search (SS) with random exploration for search space of problem and more of diversity and intensification for promising solutions. The SS and HSS have been tested on Traveling Salesman Problem. A computational experiment with benchmark instances is reported. The results demonstrate that the HSS algorithm produce better performance than original Scatter Search algorithm. The HSS in the value of average fitness is 27.6% comparing with original SS. In other hand the elapsed time of HSS is larger than the original SS by small value. The developed algorithm has been compared with other algorithms for the same problem, and the result was competitive with some algorithm and insufficient with another.

البحث الايقاعي المنتشر لحل مشكلة البائع المتجول

أحمد طارق صادق*

قسم علوم الحاسوب، الجامعة التكنولوجية، بغداد، العراق.

الخلاصة:

يقدم هذا البحث خوارزمية مهجنة تنقيبية (وصفية) هي خوارزمية البحث الايقاعي  المنتشر. توفر هذه الخوارزمية للبحث المنتشر استكشاف عشوائي لمجال بحث المشكلة ومزيداً من التنوع والتكثيف لايجاد مختلف الحلول. تم اختبار الخوارزمية المقترحة لحل مشكلة البائع المتجول. أظهرت النتائج ان خوارزمية البحث الايقاعي المنتشر أعطت نتائج أفضل من الخوارزمية الاصلية للبحث المنتشر وزادت نسبة دالة الكفاءة بنسبة 27.6% عن الخوارزمية الاصلية. ومن جانب آخر فأن وقت التنفيذ للخوارزمية المقترحة كان أكبر بقليل من الخوارزمية الاصلية. وقد تم مقارنة الخوارزمية المقترحة مع خوارزوميات آخرى لنفس المشكلة المعنية وكانت النتيجة بأن خوارزمية البحث الايقاعي المنتشر أفضل من بعض الخوارزميات وعدم أفضليتها على البعض الاخر.


alt

 

S5 Box

Login



Register

*
*
*
*
*

Fields marked with an asterisk (*) are required.