تجزيه و تحليل فضاي برازندگي جواب‌هاي مسئله طولاني ترين مسير ساده در گراف ها

مسئله طولاني ترين مسير روي گراف ها يكي از مهم ترين مسائل در تئوري گراف بوده و عبارت است از يافتن مسيري ساده با بيشترين تعداد رئوس بين دو راس معين يا ماكزيمم مجموع طول هاي يال ها بين بين دو راس معين در گراف. اين مسئله كاربرد هاي مختلفي در حوزهاي گوناگون دارد، كه از مهم ترين آن-ها مي‌توان به يافتن مسير بحراني در سيستم VLSI و بدست آوردن طولاني ترين مسير در شبكه صف اشاره كرد. از آن جايي كه تعداد بسيار معدودي الگوريتم حل در زمان چند جمله اي براي كلاس ها (انواع) خاصي از گراف ها براي اين مسئله توسعه داده شده است، در مقاله حاضر براي نخستين بار، تجزيه و تحليل فضاي برازندگي جواب هاي مسئله بر اساس شاخص هاي آماري مستخرج از اجراي 1000 مرتبه جستجوي محلي ساده انجام شده كه در نتيجه آن تخمين زده شد بهينه‌هاي محلي اين مسئله در چندين نقطه فضا تجمع يافته اند و لذا روش‌هاي حل مبتني بر جمعيت به جواب هاي بهتري براي مسئله مذكور در گراف‌هاي مختلف دست خواهند يافت. اين فرضيه با حل چند مسئله طولاني‌ترين مسير توسط الگوريتم‌هاي فراابتكاري مبتني بر تك جواب (شبيه‌سازي تبريد) و مبتني بر چند جواب (الگوريتم ژنتيك) مورد آزمون قرار گرفت، و با توجه به برتري جواب‌هاي توليدي الگوريتم ژنتيك، مورد پذيرش قرار گرفت. نتايج اين تحليل نشان مي دهد كه ميانگين اختلاف نتايج الگوريتم ژنتيك پيشنهادي براي يك مسئله بهينه، 0.024363 است.