سال انتشار: ۱۳۸۵

محل انتشار: دوازدهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۶

نویسنده(ها):

امیر شاهرودی – استادیار دانشگاه صنعتی شریف
حمید بیگی – عضو هیات علمی دانشگاه صنعتی شریف

چکیده:

دراینمقاله ، راه حل جدیدی برای حل مساله ی کوتاخ ترین مسیر تصادفی (کوتاه ترین مسیر در گراف های تصادفی) ارایه شده است. این روش، بااستفاده از یک الگوریتم ژنتیکی، مسیر بهینه را در گراف های تصادفی جستجو مینماید.در این الگوریتم هر عضو جمعیت دربر دارنده ی یک مسیر از گره ی مبدا به گره ی مقصد (یک راه حل کاندید) می باشد. محیط نیز در این الگوریتم، نقش محاسبه ی کننده تابع برازندگی را ایفا مینماید. الگوریتم، با ارایه ی مسیر کد شده توسط هر عضو جمعیت به محیط و دریافت هینه ی محاسبه شده توسط گراف تصادفی (که خود یک مقدار تصادفی است)، میزان برازندگی هر عضو را ارزیابی می نماید. با ملاحظه ی میزان برازندگی محاسبه شده بازای هر عضو جمعیت، افراد مناسب برای تولید نسل بعدی از طریق عملگرهای ترکیب و جهش انتخاب می شوند. نتایج عملی حاصل شده از این الگوریتم ژنتیکی، بیانگر همگرایی سریع (در کمتر از ۵۰۰ نسل) به جواب بهینه می باشند.