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

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

Keywords:

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