کنفرانس بین المللی محاسبات نرم

صفحه اصلی / چهارمین کنفرانس بین المللی محاسبات نرم

ارائه الگوریتمی ابتکاری برای حل مسئله ترتیب خطی

نویسندگان :

امین اسکندری¹

1- دانشگاه شیراز

کلمات کلیدی :

ترتیب خطی، برنامه ریزی صحیح، الگوریتم های ابتکاری

چکیده :

در این مقاله ، الگوریتمی ابتکاری ارائه می دهیم که با آن بتوان یک جواب برای مساله ترتیب خطی در زمان مناسب بدست آورد. ابتدا مساله را به صورت یک مساله برنامه ریزی صحیح مدلسازی می کنیم. سپس با حذف محدودیت صحیح بودن متغیر ها آن را به صورت یک مدل خطی ساده می نماییم. جواب بهینه برای مدل خطی را می توان در زمان چند جمله ای بدست آورد. این جواب بهینه مدل خطی به عنوان یک جواب اولیه برای مساله اصلی در نظر گرفته می شود الگوریتم ارائه شده در این مقاله به این صورت عمل می کند که از روی این جواب اولیه بخشی از راسهای مساله با نام S را به دو زیر بخش به نام های {S_1,S_2} تقسیم بندی می کند به گونه ای که اختلاف بین مجموع وزن یال های بین S_1 و S_2 با مجموع وزن یال های بین S_2 و S_1 ماکسیمم شود. سپس فرض می شود که همه رئوس در S_1 قبل از همه رئوس در S_2 هستند و بدین ترتیب مساله اصلی را به دو زیر مساله با اندازه کوچکتر تجزیه می شود یعنی یافتن ترتیب خطی در زیر مجموعه های S_1 و S_2. این کار را به صورت بازگشتی تا زمانی که زیر مساله ها با استفاده از روشهای حل دقیق مسایل صحیح در زمانی مطلوب قابل حل باشند ادامه پیدا می کند. در نهایت جواب مساله اصلی، با ترکیب راه حل های زیر مسایل ساخته می شود. همچنین یک استراتژی انتخاب گره جایگزین بر اساس راه حل های ابتکاری ارائه می دهیم که در آن گره را با بهترین راه حل ابتکاری انتخاب می کنیم . در نهایت نتایج اجرای الگوریتم بر روی داده های شبیه سازی شده را ارائه می دهیم. در اجرای الگوریتم بر روی نمونه های ایجاد شده از مساله مشاهده می شود الگوریتم می تواند جواب های مناسبی تولید کند که اختلاف زیادی با جواب بهینه نداشته باشد.