ارائه الگوریتمی ابتکاری برای حل مسئله ترتیب خطی
محل انتشار: چهارمین کنفرانس بین المللی محاسبات نرم
سال انتشار: 1400
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 207
فایل این مقاله در 7 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
CSCG04_034
تاریخ نمایه سازی: 23 اسفند 1400
چکیده مقاله:
در این مقاله ، الگوریتمی ابتکاری ارائه می شود که با آن بتوان یک جواب برای مساله ترتیب خطی در زمان مناسب بدست آورد. ابتدا مساله به صورت یک مساله برنامه ریزی صحیح مدلسازی می شود. سپس با حذف محدودیت صحیح بودن متغیر ها ، مدل به صورت یک مدل خطی ساده می نشود. جواب بهینه برای مدل خطی را می توان در زمان چند جمله ای بدست آورد. این جواب بهینه مدل خطی به عنوان یک جواب اولیه برای مساله اصلی در نظر گرفته می شود. الگوریتم ارائه شده در این مقاله به این صورت عمل می کند که از روی این جواب اولیه بخشی از راس های مساله با نام S را به دو زیر بخش به نام های S۱,S۲ تقسیم بندی می کند به گونه ای که اختلاف بین مجموع وزن یال های بین S۲,S۱ با مجموع وزن یال های بین S۱,S۲ ماکسیمم شود. سپس فرض می شود که همه رئوس در S۱ قبل از همه رئوس در S۲ هستند و بدین ترتیب مساله اصلی را به دو زیر مساله با اندازه کوچکتر تجزیه می شود یعنی یافتن ترتیب خطی در زیر مجموعه های S۲,S۱ این کار را به صورت بازگشتی تا زمانی که زیر مساله ها با استفاده از روش های حل دقیق مسایل صحیح در زمانی مطلوب قابل حل باشند ادامه پیدا می کند . در نهایت جواب مساله اصلی، با ترکیب راه حل های زیر مسایل ساخته می شود. همچنین یک استراتژی انتخاب گره جایگزین بر اساس راه حل های ابتکار ی ارائه داده کی شود که در آن گره را با بهترین راه حل ابتکاری انتخاب خواهد شد. در نهایت نتایج اجرای الگوریتم بر روی داده های شبیه سازی شده ارائه می شود. در اجرای الگوریتم بر روی نمونه های ایجاد شده از مساله مشاهده می شود الگوریتم می تواند جواب های مناسبی تولید کند که اختلاف زیادی با جواب بهینه نداشته باشد.
کلیدواژه ها:
نویسندگان
امین اسکندری
دانشکده مهارت و کار آفرینی،واحد شیراز،دانشگاه آزاد اسلامی،شیراز، ایران