حل مساله ی کوتاه ترین مسیر تصادفی با استفاده از یک الگوریتم ژنتیکی

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

Keywords:

مساله ی کوتاه ترین مسیر تصادفی , گراف های تصادفی , الگوریتم های ژنتیکی , یادگیری کمکی