کروموزوم (الگوریتم ژنتیک)

الگوریتم ژنتیک

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

طراحی کروموزوم ویرایش

طراحی یک کروموزوم و پارامترهای آن به نیازهای خاص مسئله‌ای که باید حل شود بستگی دارد. به عنوان مثال فرض کنید مسئله ما پیدا کردن عدد یک صحیح بین 0 تا 255 می‌باشد به‌طوری‌که مقدار تابع f(x) = x * x بیشینه (ماکزیمم) گردد. (معمولاً این نوع مسایل توسط الگوریتم ژنتیک حل نشده و توسط روش‌های عددی حل می‌شوند. این تنها یک مثال ساده می‌باشد.) راه حل‌های ما اعدادی بین 0 تا 255 می‌باشند به‌طوری‌که هر یک از این راه حل‌ها را می‌توان با یک رشته 8 بیتی نمایش داد. بنابراین ما باید از یک رشته 8 بیتی به عنوان کروموزوم استفاده نماییم. حال اگر یک کروموزوم در جمعیت نمایش دهنده مقدار 155 باشد، آن کروموزوم باید به شکل 10011011 باشد. یک مسئله واقعی در این مورد می‌تواند مسئله فروشنده دوره گرد باشد. در این مسئله به دنبال ترتیبی از سفر به شهرهای مختلف می‌گردیم به‌طوری‌که فروشنده کوتاه‌ترین مسیر را طی نماید. فرض کنید شش شهر A, B, C, D, E و F وجود دارند. یک روش مناسب برای طراحی کروموزوم مسئله فوق ترتیبی است که شهرها ملاقات می‌شوند. به عنوان مثال ترتیبی که یک کروموزوم می‌تواند در این جمعیت داشته باشد می‌تواند شبیه DFABEC باشد.

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

جستارهای وابسته ویرایش

الگوریتم ژنتیک