بخشی از مقاله
چکیده
مسئله طولانیترین مسیر روی گراف ھا یکی از مهمترین مسائل در تئوری گراف بوده و عبارت است از یافتن مسیری ساده با بیشترین تعداد رئوس بین دو راس معین یا ماکزیمم مجموع طولھای یالھا بین بین دو راس معین در گراف. این مسئله کاربردھای مختلفی در حوزھای گوناگون دارد، که از مهمترین آنھا میتوان به یافتن مسیر بحرانی در سیستم VLSI و بدست آوردن طولانیترین مسیر در شبکه صف اشاره کرد. از آنجایی که تعداد بسیار معدودی الگوریتم حل در زمان چند جملهای برای کلاسھا - انواع - خاصی از گرافھا برای این مسئله توسعه داده شده است، در مقاله حاضر برای نخستین بار، تجزیه و تحلیل فضای برازندگی جوابھای مسئله بر اساس شاخصھای آماری مستخرج از اجرای ١٠٠٠ مرتبه جستجوی محلی ساده انجام شده که در نتیجه آن تخمین زده شد بهینهھای محلی این مسئله در چندین نقطه فضا تجمع یافتهاند و لذا روشھای حل مبتنی بر جمعیت به جوابھای بهتری برای مسئله مذکور در گرافھای مختلف دست خواھند یافت. این فرضیه با حل چند مسئله طولانیترین مسیر توسط الگوریتمھای فراابتکاری مبتنی بر تک جواب - شبیهسازی تبرید - و مبتنی بر چند جواب - الگوریتم ژنتیک - مورد آزمون قرار گرفت، و با توجه به برتری جوابھای تولیدی الگوریتم ژنتیک، مورد پذیرش قرار گرفت. نتایج این تحلیل نشان میدھد که میانگین اختلاف نتایج الگوریتم ژنتیک پیشنهادی برای یک مسئله بهینه، ٣۶٣۴٠٫٠٢ است.
١. تعریف مسئله
مسئله طولانیترین مسیر سادهa در تئوری گراف، مسئله یافتن یک مسیر ساده با حداکثر طول در یک گراف خاص است. به عبارت دیگر در میان تمام مسیرھای ساده ممکن در گراف معین، ھدف مسئله پیدا کردن طولانیترین مسیر است. یک مسیر زمانی ساده نامیده میشود که دارای رئوس تکراری نباشد. بر خلاف مسئله کوتاهترین مسیر که کوتاهترین مسیر بین دو راس را به ما میدھد و در زمان چند جملهای حل میشود، برای مسئله طولانیترین مسیر زمان چند جملهای وجود ندارد و این مسئله جزء مسائل - NP-complete - است. به عبارت دیگر در زمان چند جملهای نمیتوان برای این مسئله به جواب دست یافت مگر اینکه P=NP باشد. مسئله مسیر ھمیلتونی نیز یک مسئله NP-complete مشهور است، که ھدف این مسئله تصمیمگیری در مورد اینکه آیا مسیری ساده بین دو راس معین از گراف وجود دارد که ھر راس را دقیقا یکبار ملاقات کند، حالت خاصی از مسئله طولانیترین مسیر است. مسئله طولانیترین مسیر کاربردھای مختلفی در حوزھای گوناگون دارد که عبارتند از: بدست آوردن طولانیترین مسیر در شبکه صف، پیدا کردن مسیر بحرانی در یک مدار دیجیتال یکپارچه - - IC، یافتن مسیر بحرانی در سیستم VLSI، تجزیه و تحلیل زمانبندی استاتیک - - STA و انواع آن-ھا، شامل تجزیه و تحلیل آماری زمانبندی استاتیک - - SSTA ، طراحی اتوماسیون الکترونیکی، توصیف زمینه گشت زنی چندین ربات، بازیابی اطلاعات و طراحی برد مداری که در آن نیاز به پیدا کردن طولانیترین مسیر بین دو راس مشخص در مسیریابی شبکه مستطیل است.
مسئله یافتن طولانیترین مسیر را میتوان به مسئله یافتن کوتاھترین مسیرکاھشb داد. - گرچه ممکن است این گراف دارای دور با وزن منفی باشد - اگر گراف ورودی برای مسئله طولانیترین مسیر G باشد، کوتاھترین مسیر ساده بر روی گراف ھمیلتونیخواھد بود که دقیقاً مشابه G است، اما وزنھای لبه منفی میشود، و طولانیترین مسیر بر روی G است. ھر چند ھر یک از دورھا با وزن مثبت در گراف اصلی G منتهی به دورھایی با وزن منفی در گراف ھمیلتونی خواھد شد. بنابراین یافتن کوتاهترین مسیر ساده بر روی یک گراف با دورھایی با وزن منفی، نیز NP-complete است. اگر G حاوی ھیچ دوری نباشد، پس ھمیلتونی ھیچ دوری با وزن منفی نخواھد داشت و ھر یک از الگوریتمھای یافتن کوتاهترین مسیر اکنون میتواند بر روی ھمیلتونی اجرا شوند تا مسئله اصلی در زمان چند جملهای حل شود. بنابراین مسئله طولانیترین مسیر بر روی گرافھای بدون دور ساده تعریف میشود. ھمانطور که بیان شد، مسئله یافتن طولانیترین مسیر بر روی گرافھای بدون دور را میتوان در زمان چند جملهای و از طریق منفی کردن وزن یالھا و اجرای الگوریتم کوتاهترین مسیر حل کرد. بنابراین طولانیترین مسیر در گرافھای بدون دور از طریق معکوس کردن وزن یالھا و اجرای الگوریتمھای پیدا کردن کوتاهترین مسیر در زمان چند جملهای میتوان حل کرد ]٢،١.[
٢. مرور ادبیات
درختھا اولین کلاس از گرافھا ھستند که الگوریتم زمان چند جملهای برای طولانیترین مسیر آنها - یعنی یافتن قطر درخت بدون وزن - پیدا شده است. در ابتدا، این الگوریتم توسط دایجستراc در سال ٠۶١٩ پیشنهاد شد. اما بالترمن و ھمکارانش اثباتی برای آن فراھم کردند که بعدھا توسط یوھارا و ھمکارانش برای درختھای وزندار بهبود داده شد. آنها ھمچنین مسئله را برای گرافھای بلوکی در زمان خطی حل کردند . ھمچنین از طریق تعمیم الگوریتم دایجسترا، الگوریتم چند جملهای برای مسئله طولانیترین مسیر در جایگشت دو قسمتی و نمودارھای Ptolemaic با پیچیدگی زمانی O - n - و O - n5 - حل کرده اند. علاوه بر این، آنها گرافھای دو محدب بازهای به عنوان زیر گراف بازهای معرفی کردند و مسئله برای آن در زمان O - n3 - m+nlogn - - حل شده است، جایی که n نمایانگر تعداد رئوس و m نمایانگر تعداد یالھای گراف معین میباشد. و ھمچنین به عنوان یک نتیجه فرعی آنھا نشان داد که طولانیترین مسیر در نمودار آستانه را میتوان در زمان و فضا O - n+m - بدست آورد . ھمچنین الگوریتمی با زمان O - n3 - برای مسئله گراف -m بخشی کامل توسط گیوتینd پیشنهاد شده است. اخیرا، لونیدو و ھمکارانش، بوسیله الگوریتم پیشنهاد شده برای مسئله طولانیترین مسیر نشان دادهاند که، یک جواب چند جملهای در نمودار فاصله در زمان O - n4 - اجرا میشود، ولی ھمچنان پاسخ دادن به سوال »پیچیدگی مسئله در نمودار فاصله« ھمچنان باز مانده است.
وانگ و ھمکارانش مسئله طولانیترین مسیر در گراف را، در زمینه بازیابی اطلاعات در شبکهھای نظیر به نظیر جایی که وزنھا با رئوس مرتبط ھستند، بیان کردند. ھمچنین آنھا برای حل این مسئله یک الگوریتم ژنتیک ارائه کردند]١١.[ اشمیت و ھمکارانش از مسئله طولانی مسیر برای ارزیابی بدترین تاخیر بسته از سوئیچ اترنتe استفاده کردند. اترنت، سوئیچ داده شده است را به یک مدل محاسبه تاخیر تبدیل کرده که توسط یک گراف جهتدار ارائه شده است. در این گراف بدون دور جهت دار خاص، طولانیترین مسیر را میتوان با استفاده از برنامه نویسی پویا محاسبه کرد]٧.[ مسئله طولانیترین مسیر ھمچنین در حوزه طراحی بورد مدار با عملکرد چاپ بالا نمایش داده میشود که در آن یکی از نیازھا بدست آوردن طولانیترین مسیر بین دو راس خاص در یک شبکه مسیریابی مستطیلی است]٩.[ در آن مقاله، نویسندگان یک مدل برنامهیزی خطی عدد صحیح مختلط برای حل مسئله طولانیترین مسیر در یک گراف خاص پیشنهاد دادند. در ]٦[، نویسندگان مسئله طولانیترین مسیر را در زمینه گشت زنی چند ربات توصیف و در]٥[ یک الگوریتم ژنتیک برای حل طولانیترین مسیر ارائه شده است. در ]٤[، الگوریتمھای تقریبی برای مسئله طولانی ترین مسیر - گراف بدون وزن - در نظر گرفته شد. نویسندگان نشان دادند که ھیچ الگوریتم چندجملهای نمیتواند یک تقریب ضریب ثابت برای مسئله طولانیترین مسیر بدست آورد، مگر اینکه . P = NP در ]٣[، یک الگوریتم ابتکاری برای مسئله طولانیترین مسیر، بر اساس مولفه به شدت وابسته به گراف ارائه شده است.
٣. تجزیه و تحلیل فضای برازش جواب ھا
نکته اساسی و مهم در حوزه بهینهسازی تنها طراحی بهترین الگوریتم برای مسائل بهینهسازی نیست، بلکه جستجو برای یافتن الگوریتمی که بیشترین تطابق با یک کلاس از مسائل دارد، بسیار قابل اھمیت است. این ادعا که الگوریتم بهینه سازی A برای تمام مسائل بهینهسازی کاملا بهتر از الگوریتم بهینهسازی B است، اساسا بیمعنی است. قضیه fNFL ثابت کرده است که، تحت مفروضات خاص ھیچ الگوریتم بهینهسازی برتری تسبت به دیگر الگوریتمھا درتمامی حالتھای مسائل بهینهسازی ندارد. اگر الگوریتم A برای مسئله داده شده بهتر از الگوریتم B انجام شود، ھمیشه مسئله دیگری وجود دارد که در آن عملکرد الگوریتم B بهتر از الگوریتم A است . بنابراین ھیچ الگوریتم فراابتکاری نمیتواند بطور یکنواخت بهتر از سایر الگوریتم ھای فراابتکاری در تمامی مسائل باشد. سوالی که در خصوص برتری الگوریتم بیان شده است، تنها نشاندھنده برتری الگوریتم در یک کلاس خاص از مسائل و/ یا نمونهھا است]١٠ .[ بسیاری از مطالعات در تجزیه و تحلیل فضای جواب برای مسائل بهینهسازی مختلف نشان داده شده است که نه تنها مشکلات مختلف به ساختارھای مختلف مطابقت دارد، بلکه ھمچنین نمونه ھای گوناگون مسئله مشابه به ساختارھای مختلف مطابقت دارد. در واقع، ھیچ الگوریتم فراابتکاری ایدهآل، به عنوان یک جعبه سیاه ، طراحی نشده است .
تجزیه و تحلیل برازش برای مسائل بهینهسازی یکی از جنبهھای مهم طراحی الگوریتم فراابتکاری است. اثربخشی الگوریتم فراابتکاری بستگی به ویژگیھای برازش مرتبط با نمونهھا دارد. مطالعه فضای جواب مسئله بهینهسازی یک راه بررسی طبیعت ذاتی و مشکلات نمونهھای آن برای ادغام این دانش در مورد ساختار مسئله در طراحی الگوریتم فراابتکاری فراھم میکند. تابع ھدف و ھمسایهھا به شیوهی کاملی فضای جواب را تعریف می-کنند و بهرهوری جستجوی یک فراابتکاری را تحت تاثیر قرار میدھند. بنابراین تجزیه و تحلیل برازندگی فضای جواب در طراحی بهتر ھمسایهھا و نمایش جوابھا تابع ھدف کمک خواھد کرد. علاوه بر این تجزیه و تحلیل فضای جواب درک بهتری از رفتار الگوریتم فراابتکاری و یا ھر یک از اجزای جستجو یک الگوریتم فراابتکاری فراھم میکند. ھمچنین علت عملکرد قوی یا ضعیف الگوریتم فراابتکاری برای مسئله و/یا نمونه داده شده را توضیح میدھد. مفهوم فضای جواب برای اولین بار توسط رایتg در سال ١٩٣٢ در زیستشناسی توصیف شده است . برازندگی فضای جواب برای مطالعه سیستمھای بیولوژیکی - تکامل یافته - و درک فرآیند تکاملی که از عملیات خاص جهشh و تقاطعi بدست میآید، استفاده شده است . پس از آن، این مفهوم در تجزیه و تحلیل مسئلهھای بهینهسازی مورد استفاده قرار شده است .
٣-١.معیارھای پراکندگی
ھدف از بیان معیارھای پراکندگی، تجزیه و تحلیل پراکندگی جوابھای بهینه محلی در فضای جواب برای ھر فضای جستجو G و برای فضای ھدف Fاست. اقدامات مشترک مورد استفاده عبارتند از:
٣-١-١.پراکندگی در جستجوی فصلی
برای جمعیت P میانگین فاصله dmm - p - و میانگین فاصله نرمالیز شده Dmm - p - از طریق فرمولھای زیر بدست میآید]٨.[
٣-١-٢.پراکندگی در فضای تابع ھدف
بسیاری شاخصھا برای تجزیه و تحلیل پراکندگی جوابھا در فضای ھدف مورد استفاده قرار گرفته است . به عنوان مثال Amp - p - ، برای جوابھا از جمعیت اختیاری p مرتبط است با تفاوت بین بهترین و بدترین کیفیت از جمعیت p که از طبق فرمول زیر قالب محاسبه است.
ارتباط بین جمعیت تصادفی آغازین U و جمعیت نهایی O از طریق فرمول زیر بدست میآید. بنابراین با توجه به توضیحات ارائه شده درباره اھمیت برازندگی فضای جواب و ھمچنین فرمولھای بیان شده، برنامهای جهت انجام برازندگی فضای جواب در متلب کد نویسی شده است که ضمن نمایش چگونگی پراکندگی در فضای جواب G، در شناسایی الگوریتمی است که بیشترین اقتباس با مسئله دارد، کمک کند.
