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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

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

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

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

مطالب مرتبط[ویرایش]

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