الگوریتمهای ترکیبی (آتوماتاهای یادگیر + الگوریتمهای ژنتیکی) برای حل مسئله مینیمم کردن پهنای باندگراف

در این مقاله، سه الگوریتم تقریبی برای حل مسئله مینیمم کردن پهنای باند در گرافها بکار گرفته شده است که بوسیله تغییر دادن ترتیب سطرها و ستونهای ماتریس مجاورت، باعث کاهش پهنای باند میگردند. الگوریتم اول مبتنی بر آتوماتاهاییادگیر مهاجرت اشیا می باشد. دومین الگوریتم، یک الگوریتم ترکیبی میباشد که از ترکیب آتوماتای یادگیر مهاجرت اشیا و ژنتیک حاصل شده است. الگوریتم سوم نیز از ترکیب آتوماتای یادگیر ساختار متغیر و ژنتیک حاصل شده است. الگوریتمها بر روی 113نمونه از مسئلههای واقعی ارزیابی شدهاند و نتایج آن با تعدادی از الگوریتمهای مشهور مقایسه شده است که نتایج بهبود یافتهاینسبت به چندین مورد از بهترین الگوریتمها دیده میشود. نشان داده شده است که با استفاده همزمان از الگوریتمهای ژنتیکی و آتوماتای یادگیر در فرایند جستجو، سرعت رسیدن به جواب افزایش مییابد و همچنین از بدام افتادن الگوریتم در بهینههای محلی جلوگیری میشود. یکی دیگر از نکات مثبت الگوریتمهای جدید ارایه شده این است که بحث سرعت اجرایی و کیفیت نتایج را در حالت متعادل نگه میدارند یعنی این الگوریتمها قادر هستند که در مدت زمان کم، جوابهای معقول بدست آورند

کلیدواژه ها:

آتوماتای یادگیر مهاجرت اشیا ، الگوریتم ژنتیکی ، پهنای باند گراف ، الگوریتم ترکیبی