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

از روش های مرسوم برای حل مسایل غیرچندجمله ای در دنیای واقعی، می توان به الگوریتم های تکاملی اشاره کرد. این الگوریتم ها به دلیل اینکه از چندین نقطه شروع اولیه جهت پیدا کردن جواب نهایی استفاده می کنند، با احتمال بسیار پایین در نقاط بهینه محلی به دام می افتند و در مدت زمان کوتاه جواب بهینه یا جواب های نزدیک به بهینه را می یابند. دو نمونه از الگوریتم های تکاملی معروف، الگوریتم ژنتیک (Genetic Algorithm) و الگوریتم ترکیب باکتری (Bacterial Conjugation) می باشد. در الگوریتم ژنتیک (GA) پس از تولید کروموزوم های اولیه با استفاده از روش های متداول مانند روش انتخاب چرخ رولت (RWS) و روش انتخاب رقابتی بولتزمن دودویی (BBTS)، تعدادی کروموزوم جهت تولید فرزند طی سایر مراحل الگوریتم ژنتیک انتخاب می شوند. در الگوریتم ترکیب باکتری (BC) هم تابعی به نام تابع ترکیب باکتری (BCF) وظیفه تولید باکتری را بر عهده دارد. در این مقاله، به طراحی الگوریتم ژنتیک بهبود یافته ای می پردازیم که به جای استفاده از روش های متداول انتخاب مانند RWS و ،BBTS، از تابع ترکیب باکتری جهت انتخاب کروموزوم ها از میان جمعیت اولیه استفاده می کند. از این رو، الگوریتم پیشنهادی را الگوریتم ژنتیک مبتنی بر تابع ترکیب باکتری (GA-BCF) می نامیم. برای نشان دادن درستی عملکرد الگوریتم پیشنهادی، این الگوریتم برای حل مسیله کوله پشتی دودویی به کار گرفته شده و نتایج حاصل با نتایج بدست آمده از الگوریتم ژنتیک (GA) و الگوریتم ترکیب باکتری (BC) مقایسه و ارزیابی می شوند. نتایج ارزیابی ها نشان می دهند که الگوریتم پیشنهادی در مدت زمان کمتر جواب بهتری پیدا می کند.

کلیدواژه ها:

الگوریتم های تکاملی ، الگوریتم ژنتیک ، تابع ترکیب باکتری ، مسایل غیرچندجمله ای ، مسیله کوله پشتی دودویی