امین نجارپور - گروه کامپیوتر، واحد علوم و تحقیقات خوزستان، دانشگاه آزاد اسلامی، اهواز، ایران
مهدی صادق زاده - گروه کامپیوتر، واحد علوم و تحقیقات خوزستان، دانشگاه آزاد اسلامی، اهواز، ایران

مسئله کوتاهترین مسیر یکی از مسائل کلاسیک در تئوری گرافهاست که کاربرد وسیعی در زمینه های مختلف مثل حمل و نقل، ارتباطات، الکترونیک و ... دارد. این مسئله انواع گوناگونی دارد و الگوریتم های مختلفی برای حل آنها پیشنهاد شده است. در این تحقیق نوعی مسئله چند هدفه به نام کوتاهترین مسیرهای ناهمپوشان مطرح می شود که در آن، هدف یافتن n مسیر مجزا از مجموعه ای از مبدأها به مجموعه ای از مقصدها (بصورت جفت های مبدأ- مقصد)، با رعایت سه شرط است: 1) کلیه مسیرها باید مسیرهایی ساده باشند، 2) مسیرها نباید هیچ گونه اشتراک و همپوشانی با یکدیگر داشته باشند، 3) کوتاهترین مسیر ممکن بین هر جفت مبدأ - مقصد پیدا شود. الگوریتم ژنتیک مرتب سازی نامغلوب 2 (NSGA-II) از الگوریتم های چند هدفه ای است که در بسیاری از مسائل بهینه سازی چند هدفه استفاده شده است. در این تحقیق یک الگوریتم NSGA-II پیشنهادی برای مسئله کوتاهترین مسیرهای ناهمپوشان مطرح شده و عملکرد آن با یک الگوریتم دیگر به نام الگوریتم ژنتیک حاصل جمع توابع هزینه ی وزن دهی شده (SWCF) مقایسه می گردد. نتایج بدست آمده حاکی از این است که الگوریتم NSGA-II پیشنهادی، چه از لحاظ کیفی و چه کمی، عملکرد بهتری نسبت به الگوریتم ژنتیک SWCF دارد.

کوتاهترین مسیرهای ناهمپوشان، الگوریتم NSGA-II، مرتب سازی نامغلوب، بهینه سازی چند هدفه