الگوریتم ژنتیک آگاه از بهترین عضو با کاربرد در رنگ آمیزی و بعد متریک گراف

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

کلیدواژه ها:

الگوریتم ژنتیک ، الگوریتم های فراابتکاری ، بعدمتریک گراف ، رنگ آمیزی گراف