الگوریتم ژنتیک دودویی و پاسخ به پنج سوال مهم درباره آن

قدرت انتخاب و تصمیم‌گیری مختص انسان است؛ اما من در عجبم که طبیعت به چه خوبی و بهتر از هر کسی دیگری در این عالم، از عهده آن برمی‌آید.

احمدرضا پاکرایی

مقدمه

طی سه پست آتی به توضیح الگوریتم ژنتیک دودویی پرداخته، به پنج سوال مهم در خصوص آن پاسخ می‌دهیم؛ یعنی

چه موضوع مهمی وجود دارد که الگوریتم ژنتیک دودویی را به دردسر می‌اندازد؟

دو دلیل مهم استفاده از عملگر جهش در الگوریتم ژنتیک دودویی چیست؟

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

نخبه‌گرایی در الگوریتم ژنتیک دودویی، به چه موضوع مهمی اشاره دارد؟

نکات کلیدی در به‌کارگیری روش‌های مختلف انتخاب، در الگوریتم ژنتیک دودویی کدامند؟ 

و در آینده نزدیک به کمک این مطالب الگوریتم ژنتیک دودویی را در متلب پیاده سازی خواهیم کرد. با ما در ادامه همراه باشید.

الگوریتم ژنتیک: انتخاب طبیعی بر روی کامپیوتر

دو تیپ از الگوریتم‌ ژنتیک اجرایی شده است که هر دوی آن‌ها صورت مشابهی از مدل‌سازی یعنی ترکیب ژنتیک و انتخاب طبیعی را دنبال می‌کنند. یکی، متغیر‌ها را به صورت یک رشته‌ی دودویی کد شده نمایش می‌دهد؛ و با رشته‌های دودویی کار می‌کند در حالیکه دیگری با متغیر‌های پیوسته کار می‌کند.

نمایش دودویی متغیر‌ها 

در مقایسه با تکامل بیولوژیک، الگوریتم ژنتیک دودویی نیز با یک جمعیت اولیه از اعضای تصادفی شروع به کار می‌کند. هر رشته باینری(کروموزوم)، ویژگی‌های انتخاب شده‌ی(Selected Characteristics) یکی از اعضای جمعیت را نشان می‌دهد. می‌توان دو رشته‌ای را که به تصادف انتخاب شد‌ه‌اند، با یکدیگر ترکیب کرد در این صورت دو رشته جدید به وجود می‌آیند که ترکیبی از ویژگی‌های دو رشته دیگر هستند؛ پس هر رشته‌ باینری جدید، بخش‌های از رشته‌های باینری والدین خود را شامل می‌شود.  

اجزای الگوریتم ژنتیک دودویی

الگوریتم ژنتیک همانند هر الگوریتم بهینه‌سازی دیگر با تعریف متغیر‌های بهینه‌سازی، تابع هزینه(Cost Function) و هزینه(Cost) شروع می‌شود و مانند سایر الگوریتم‌های بهینه‌سازی با آزمایش همگرایی(Convergence) به پایان می‌رسد. سلسه مراتب اجرای الگوریتم ژنتیک دودویی به صورت یک فلوچارت ساده، در شکل1 نشان داده شده است.

نقطه قوت الگوریتم ژنتیک این است که بر خلاف بسیاری از روش‌ها، هیچ مشکلی برای کار با داده‌های گسسته ندارد.

تابع هزینه و انتخاب متغیرها 

تابع هزینه(f) خروجی را بر حسب مجموعه‌ای از متغیر‌های ورودی(کروموزوم) تولید می‌کند. هدف این است که خروجی را با برخی از روش‌های مطلوب، با پیدا کردن مقادیر مناسب برای متغیر‌های ورودی، تغییر دهیم. خواهیم دید که تعریف یک تابع هزینه‌یِ مناسب و تصمیم برای تعیین متغیرهایی که باید استفاده شوند، کاملا مرتب هستند.

نکته: در ادبیات مربوط به الگوریتم ژنتیک اصطلاح برازندگی به طور گسترده برای اشاره به خروجی تابع هزینه استفاده می‌شود؛ ولی از آن‌جای‌که بیشتر مسائل بهینه‌سازی از نوع کمینه‌سازی هستند ما در اینجا از اصطلاح هزینه استفاده کرده‌ایم.

الگوریتم ژنتیک به وسیله تعریف یک کروموزوم یا آرایه‌ای از مقادیر متغیرها برای بهینه‌سازی شروع می‌شود. اگر یک کروموزوم $$N_{var}$$ متغیر داشته باشد که توسط$$P_{1},P_{2},P_{3},...,P_{N_{var}}$$   داده شده باشند؛ سپس کروموزوم به صورت یک بردار ردیفی $$N_{var}$$  عنصری نوشته می‌شود.

$$Chromosome=[P_{1},P_{2},P_{3},...,P_{N_{var}}]$$

   هر کروموزوم هزینه‌ای دارد که با ارزیابی تابع هزینه در $$P_{1},P_{2},P_{3},...,P_{N_{var}}$$   تعیین می‌شود.

  $$Cost=f(chromosome)=f(P_{1},P_{2},P_{3},...,P_{N_{var}})$$

اغلب تابع هزینه بسیار پیچیده است. کاربر بایستی تصمیم بگیرد کدام متغیر‌های مسئله مهم‌تر هستند. متغیر‌هایِ بیش از حد، الگوریتم ژنتیک را به دردسر می‌اندازند. برخی اوقات، تعداد صحیح و انتخاب متغیر‌ها از تجربه یا اجراهای بهینه‌سازی آزمایشی  به دست می‌آیند؛ اوقات دیگر، یک تابع هزینه تحلیلی برای این کار وجود دارد. بیشتر مسائل بهینه‌سازی نیاز به محدودیت‌ها یا مرزهای برای متغیر دارند.

به زودی در پست بعدی به ادامه مطلب خواهیم پرداخت با ما همراه باشید.