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

          در سالهای اخیر استفاده از روش‌های تکامل تدریجی برای حل مسائل بهینه‌سازی روند رو به رشدی داشته است. الگوریتم‌های تکاملی، روش‌های جستجو و بهینه‌سازی هستند که بر اساس تکامل تدریجی شکل گرفته‌اند. الگوریتم ژنتیک به عنوان محبوبترین الگوریتم تکامل تدریجی در فضای جستجوی نامعین کاربرد وسیعی پیدا کرده است. الگوریتم ژنتیک، به عنوان یک الگوریتم محاسباتی بهینه‌سازی، با در نظر گرفتن مجموعه‌ای از نقاط فضای جواب در هر تکرار محاسباتی، به نحو مؤثری نواحی مختلف فضای جواب را جستجو می‌کند. الگوریتم‌ ژنتیک‌ ویژگی‌هایی‌ دارد که‌ آن‌ را در مقایسه‌ با دیگر الگوریتم‌های‌ بهینه‌یابی‌، متفاوت ‌می‌سازد. این‌ ویژگی‌ها و تمایزات‌ را می‌توان‌ به‌ صورت‌ زیر برشمرد ]۸ و ۱۳.[

          ۱- الگوریتم‌ ژنتیک‌ به‌ جای‌ به‌ کارگیری‌ خود متغیرها از به‌ رمز درآمده‌ی‌ آنها، یعنی‌ کروموزوم‌ها، استفاده‌ می‌کند. در نتیجه‌ ارتباط‌ و وابستگی‌ کمی‌ به‌ خود مسئله‌ دارد. بنابراین‌ می‌توان‌ حدس‌ زد که‌ این‌ الگوریتم‌ می‌تواند پاسخ‌ گستره‌ی‌ وسیعی‌ از مسائل‌ را بیابد.

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

          ۳- این‌ الگوریتم‌ به‌ سادگی‌ برای‌ حل‌ مسائلی‌ که‌ شمار زیادی‌ متغیر دارند به‌ کار گرفته‌ می‌شود.

          ۴- الگوریتم‌ ژنتیک‌، ساده‌ است‌ و به‌ اطلاعات‌ کمکی‌ مانند مشتق‌های‌ تابع‌ هدف‌ نیازی‌ ندارد. در نتیجه‌ برای‌ بهینه‌سازی‌ روی‌ یک‌ تابع‌ هدف‌ بسیار پیچیده‌، ناپیوسته‌ یا بی‌مشتق‌، و یا سیستم‌هایی‌که‌ تعریف‌ ریاضی‌ مشخصی‌ ندارند و با شبیه‌سازی‌ یا اعمال‌ مستقیم‌ پارامترها به‌ سیستم‌ واقعی ‌آزموده‌ می‌شوند. بسیار مناسب‌ است‌.

          ۵- الگوریتم‌ ژنتیک‌ در پایان‌ می‌تواند به‌ جای‌ یک‌ پاسخ‌، مجموعه‌ای‌ از پاسخ‌های‌ بهینه‌ را ارائه‌کند. این‌ ویژگی‌ در پاسخ‌یابی‌ مسائل‌ بهینه‌یابی‌ چند هدفی[۱]‌ اهمیت‌ دارد.

اصطلاحات و مفاهیم پایه ای:

حال که می خواهیم از روش های بیولوژیکی برای حل مسئله استفاده کنیم، لذا باید برای بیان یک مسئله به زبان الگوریتم ژنتیک، نام گذاری هائی مشابه داشته باشیم و از مفاهیم بیولوژیکی نیز استفاده کنیم، لذا آشنائی با این نام ها و مفاهیم ضروری به نظر می رسد.

ژن( Gen ) : پایه‌ای ترین و بنیادی‌ترین المان‌های سازنده یک ساختار وراثتی ژن (GEN) است. ژن ها عناصر پایه سازنده ویژگی های یک ساختار ارگانیک می باشند که هر ژن منتقل کننده و بیان کننده ویژگی‌های خاصی است که بصورت بالقوه در نسل حامل این ژن وجود دارد و ممکن است بصورت بالفعل در نسل ظاهر شود و یا به دلیل مسائل محیطی و وراثتی هیچ‌گاه ظاهر نشود.

کروموزوم(Chromosome ) : با انتخاب نوع ژن ها و نحوه و ترتیب چینش این ژن ها در کنار یکدیگر ویژگی های خاصی برای هر ساختار تولید خواهد شد. به این انتخاب و نوع چینش ژن ها در کنار یکدیگر یا همان رشته های ژنی ، کروموزوم (chromosome )  گفته می شود.

نژادمانه(Genotype ): در واقع مشخص کننده نژاد و مشخصات وراثتی یک ساختار ارگانیک است که بصورت بالقوه وجود دارد و ممکن است هیچ گاه به مرثه ظهور هم نرسد، اما می تواند به نسل های بعدی منتقل شود و در نسل های بعدی ظاهر شود.

رخ مانه(Phenotype ): رخ مانه یا همان Phenotype ، همان مشخصات بالفعل ساختار ارگانیک می باشد که بیانگر وجود و ساختار واقعی ساختار است. رخ مانه بخشی از ویژگی های وراثتی است که با توجه به شرایط محیطی توانسته اند ظاهر شوند.

حال که با مفاهیم و نام های بیولوژیکی آشنا شدیم بایستی متغیرها و مفاهیم مسائل را نیز بر اساس این مفاهیم نام گذاری و بیان کنیم.

ژن : در یک مسئله ژن ها همان پارامترهائی هستند که هر متغیر مسئله می تواند اختیار کند، به عبارت دیگر ژن ها در مسئله ریاضی راه حل های ممکن را ارائه می کنند که شاید حتی
راه حل واقعی نباشند.

کروموزوم: مفهوم بعدی که می بایستی در یک مسئله ریاضی و الگوریتم ژنتیک یکسان سازی شود، کروموزوم است، کروموزوم در یک مسئله مانند ساختار ارگانیک همان رشته ژنی است، یعنی مجموعه ای از پارامترهای مورد نظر که یک جواب کامل را برای مسئله تعیین می کنند، که بدلیل نوع ژن ها و توضیحات بالا ممکن است جواب واقعی و یا حتی جواب غیرقابل قبولی برای مسئله باشد.

جمعیت اولیه: مجموعه جواب های اولیه است که برای حل مسئله فرض می شوند. این جمعیت مجموعه از کروموزوم ها می باشد.

تابع تطبیق: معیاری است برای بررسی میزان نزدیکی و سازگاری جواب های تولید شده در هر نسل با شرایط موردنظر. در هر مرحله، برای تولید نسل بعد والدینی از نسل فعلی که به شرایط تابع تطبیق نزدیک شانس بیشتری برای انتخاب دارند.

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

 

 

 

 

 

 

 

 

 

 

 

 

 


۱- Multi-Objective Optimization