یک الگوریتم ژنتیک بهبودیافته با گوناگونی و جستجوی محلی برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی
هدف: هدف این مقاله ارائه یک الگوریتم ژنتیک بهبودیافته برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی است. روشهای پیشین حل مسئله کمتر به گوناگونی جوابها در جمعیت توجه داشتهاند و به دلیل عدم تنوع کافی در عملگرهای جهش تنها در برخی اجراها عملکرد مطلوبی دارند و در سایر اجراها در بهینه محلی گرفتار...
Main Authors: | , , |
---|---|
Format: | Article |
Language: | fas |
Published: |
Ayandegan Institute of Higher Education, Tonekabon,
2022-02-01
|
Series: | تصمیم گیری و تحقیق در عملیات |
Subjects: | |
Online Access: | http://www.journal-dmor.ir/article_133626_a7932ff7c58985254e3f84fca3275f43.pdf |
_version_ | 1797905109504491520 |
---|---|
author | منا علیزاده فیروزی وحید کیانی حسین کریمی |
author_facet | منا علیزاده فیروزی وحید کیانی حسین کریمی |
author_sort | منا علیزاده فیروزی |
collection | DOAJ |
description | هدف: هدف این مقاله ارائه یک الگوریتم ژنتیک بهبودیافته برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی است. روشهای پیشین حل مسئله کمتر به گوناگونی جوابها در جمعیت توجه داشتهاند و به دلیل عدم تنوع کافی در عملگرهای جهش تنها در برخی اجراها عملکرد مطلوبی دارند و در سایر اجراها در بهینه محلی گرفتار میشوند.روششناسی پژوهش: روش پیشنهادی از عملگرهای ژنتیک مناسب برای افزایش گوناگونی جمعیت و از جستجوی همسایگی محلی در اطراف بهترین جواب برای افزایش سرعت همگرایی استفاده میکند. استفاده از عملگرهای جهش هاب در کنار عملگرهای جهش تخصیص در الگوریتم پیشنهادی باعث کاوش بهتر فضای جستجو، افزایش کارایی و دستیابی به جواب بهینه در اکثر اجراها در مسائل با اندازه بزرگ شد. همچنین، جستجوی همسایگی محلی در اطراف بهترین جواب، باعث همگرایی سریعتر روش پیشنهادی شد و زمان حل مسئله را درمجموع برای مسائل بزرگ کاهش داد.یافتهها: ارزیابی روش پیشنهادی و الگوریتم پایه روی مجموعه داده پست استرالیا (AP) نشان داد که بهبودهای انجامشده ضمن حفظ سرعت اجرا، کارایی الگوریتم ژنتیک را در دستیابی به جواب بهینه برای مسائلی به بزرگی 200 گره از %2 به بیش از %85 افزایش میدهد.اصالت/ارزش افزوده علمی: این مطالعه نشان داد که الگوریتمهای فرا ابتکاری و نسخههای بهبودیافته آنها میتوانند روشهای مناسبی برای حل انواع مسائل مکانیابی هاب در زمان کوتاه و محدود باشند |
first_indexed | 2024-04-10T10:00:58Z |
format | Article |
id | doaj.art-3a634a19dfb94d53a5e98d804bfdb621 |
institution | Directory Open Access Journal |
issn | 2538-5097 2676-6159 |
language | fas |
last_indexed | 2024-04-10T10:00:58Z |
publishDate | 2022-02-01 |
publisher | Ayandegan Institute of Higher Education, Tonekabon, |
record_format | Article |
series | تصمیم گیری و تحقیق در عملیات |
spelling | doaj.art-3a634a19dfb94d53a5e98d804bfdb6212023-02-16T08:45:52ZfasAyandegan Institute of Higher Education, Tonekabon,تصمیم گیری و تحقیق در عملیات2538-50972676-61592022-02-016453655210.22105/dmor.2021.272989.1325133626یک الگوریتم ژنتیک بهبودیافته با گوناگونی و جستجوی محلی برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکیمنا علیزاده فیروزی0وحید کیانی1حسین کریمی2گروه مهندسی صنایع، دانشگاه بجنورد، بجنورد، ایران.گروه مهندسی کامپیوتر، دانشگاه بجنورد، بجنورد، ایران.گروه مهندسی صنایع، دانشگاه بجنورد، بجنورد، ایران.هدف: هدف این مقاله ارائه یک الگوریتم ژنتیک بهبودیافته برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی است. روشهای پیشین حل مسئله کمتر به گوناگونی جوابها در جمعیت توجه داشتهاند و به دلیل عدم تنوع کافی در عملگرهای جهش تنها در برخی اجراها عملکرد مطلوبی دارند و در سایر اجراها در بهینه محلی گرفتار میشوند.روششناسی پژوهش: روش پیشنهادی از عملگرهای ژنتیک مناسب برای افزایش گوناگونی جمعیت و از جستجوی همسایگی محلی در اطراف بهترین جواب برای افزایش سرعت همگرایی استفاده میکند. استفاده از عملگرهای جهش هاب در کنار عملگرهای جهش تخصیص در الگوریتم پیشنهادی باعث کاوش بهتر فضای جستجو، افزایش کارایی و دستیابی به جواب بهینه در اکثر اجراها در مسائل با اندازه بزرگ شد. همچنین، جستجوی همسایگی محلی در اطراف بهترین جواب، باعث همگرایی سریعتر روش پیشنهادی شد و زمان حل مسئله را درمجموع برای مسائل بزرگ کاهش داد.یافتهها: ارزیابی روش پیشنهادی و الگوریتم پایه روی مجموعه داده پست استرالیا (AP) نشان داد که بهبودهای انجامشده ضمن حفظ سرعت اجرا، کارایی الگوریتم ژنتیک را در دستیابی به جواب بهینه برای مسائلی به بزرگی 200 گره از %2 به بیش از %85 افزایش میدهد.اصالت/ارزش افزوده علمی: این مطالعه نشان داد که الگوریتمهای فرا ابتکاری و نسخههای بهبودیافته آنها میتوانند روشهای مناسبی برای حل انواع مسائل مکانیابی هاب در زمان کوتاه و محدود باشندhttp://www.journal-dmor.ir/article_133626_a7932ff7c58985254e3f84fca3275f43.pdfالگوریتم ژنتیکالگوریتمهای فرا ابتکاریجستجوی محلیمکانیابی هاب |
spellingShingle | منا علیزاده فیروزی وحید کیانی حسین کریمی یک الگوریتم ژنتیک بهبودیافته با گوناگونی و جستجوی محلی برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی تصمیم گیری و تحقیق در عملیات الگوریتم ژنتیک الگوریتمهای فرا ابتکاری جستجوی محلی مکانیابی هاب |
title | یک الگوریتم ژنتیک بهبودیافته با گوناگونی و جستجوی محلی برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی |
title_full | یک الگوریتم ژنتیک بهبودیافته با گوناگونی و جستجوی محلی برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی |
title_fullStr | یک الگوریتم ژنتیک بهبودیافته با گوناگونی و جستجوی محلی برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی |
title_full_unstemmed | یک الگوریتم ژنتیک بهبودیافته با گوناگونی و جستجوی محلی برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی |
title_short | یک الگوریتم ژنتیک بهبودیافته با گوناگونی و جستجوی محلی برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی |
title_sort | یک الگوریتم ژنتیک بهبودیافته با گوناگونی و جستجوی محلی برای حل مسئله مکانیابی بدون ظرفیت هاب با تخصیص تکی |
topic | الگوریتم ژنتیک الگوریتمهای فرا ابتکاری جستجوی محلی مکانیابی هاب |
url | http://www.journal-dmor.ir/article_133626_a7932ff7c58985254e3f84fca3275f43.pdf |
work_keys_str_mv | AT mnạʿlyzạdhfyrwzy yḵạlgwrytmzẖntyḵbhbwdyạfthbạgwnạgwnywjstjwymḥlybrạyḥlmsỷlhmḵạnyạbybdwnẓrfythạbbạtkẖṣyṣtḵy AT wḥydḵyạny yḵạlgwrytmzẖntyḵbhbwdyạfthbạgwnạgwnywjstjwymḥlybrạyḥlmsỷlhmḵạnyạbybdwnẓrfythạbbạtkẖṣyṣtḵy AT ḥsynḵrymy yḵạlgwrytmzẖntyḵbhbwdyạfthbạgwnạgwnywjstjwymḥlybrạyḥlmsỷlhmḵạnyạbybdwnẓrfythạbbạtkẖṣyṣtḵy |