چینش های جدید برای اتوماتای سلولی ژنتیکی

مدل اتوماتای سلولی ژنتیکی ترکیبی است از الگوریتم های ژنتیکی و مدل اتوماتای سلولی. در مدل اتوماتای سلولی ژنتیکی میان رشته ها (کروموزوم) در جمعیت ژنتیکی و سلولها در اتوماتای سلولی تناظری برقرار می شود. نتیجه این خواهد بود که هر سلول دارای تعدادی ژن در قالب رشته های بیتی است که نمایش دهنده یک جواب ممکن برای مساله مورد مطالعه می باشد. ژن ها معرف حالت سلول در اتوماتای سلولی هستند. حالت بعدی اتوماتای سلولی (نسل بعدی در این جمعیت) با کمک قوانین اتوماتا که در واقع قوانین زاد و ولد میباشند تولید می گردد. عمل چینش، در اتوماتای سلولی ژنتیکی عملی است که نحوه قرار گیری سلولها در فضای جمعیت را تغییر می دهد. عمل چینش سبب از میان رفتن همسایگان قدیمی یک سلول و ایجاد همسایگان جدید برای آن سلول می گردد و از این طریق ، رشته ای که در صدد انتخاب یک رشته و ترکیب با آن برای ایجاد فرزندان جدید است، دارای محدودیت دسترسی و انتخاب می باشد و فقط از یک سری رشته محدود در همسایگان خود حق انتخاب دارد. این محدودیت، در حل بعضی از مسائل نه تنها باعث کاهش کارایی الگوریتم نمی شود، بلکه کارایی آن را بهبود می بخشد. چند روش چینش که در [ 5]مطرح و کارایی آنها مورد آزمایش قرار گرفته عبارتند از : چینش سطری، چینش قطری، چینش حداکثر فاصله، چینش تصادفی و چینش مرکزی. در این مقاله چینش های جدیدی معرفی شده است و بر روی مسایل متنوعی از جمله مساله کوله پشتی و مساله رنگ آمیزی گراف آزمایش و مورد ارزیابی قرار گرفته است و با چینشهای گزارش شده در [ 5] مقایسه گردیده است

کلیدواژه ها:

الگوریتمهای ژنتیکی ، اتوماتای سلولی ، اتوماتای سلولی ژنتیکی ، چینش