الگوریتم ژنتیک: ساده و جادویی

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

• الگوریتم ژنتیک
• استراتژیهای تکاملی
• برنامه ریزی تکاملی

الگوریتم ژنتیک
الگوریتم ژنتیک یکی از الگوریتمهای تکاملی است که اگرچه به شکلهای مختلفی ارائه شده است اما پایه تمام این شکلها چهار فرایند است که در ادامه به آنها پرداخته می شود. الگوریتم ژنتیک یک بهینه سازی غیر جبری است که مناسب برای توابعی است که بهینه سازی آنها با روشهای جبری کاری طاقت فرسا است. الگوریتم ژنتیک برای مسایلNP-Hard بسیار مناسب می باشد. همچنین این الگوریتمها قادر به حل مسایلی هستند که در فضای حلشان ناپیوستگی وجود دارد. یکی دیگر از مزایای این روش، توانایی اعمال آن به مسایلی است که دارای متغیرهای زیاد می باشند.
از طرف دیگر، الگوریتم ژنتیک ضعفهایی نیز دارد. این روش غیر جبری است بنابراین پاسخ دقیق مساله را نمی یابد و حتی ممکن است برای یک مساله مشخص با هر بار بکارگیری پاسخی متفاوت ارائه دهد. اگرچه تمامی این پاسخها می توانند پاسخهایی باشند که دقت مورد نیاز را برآورده کنند. الگوریتمهای ژنتیک قابل اعمال به تمام مسایل بهینه سازی هستند اما در مسایلی این روشها نسبت به سایر روشها بسیار کندتر عمل می کنند. بنابراین ژنتیک، روشی عمومی برای تمام جستجوها نمی باشد.
با این وجود این الگوریتم (و سایر الگوریتمهای تکاملی) فضای پاسخ را به صورت موازی و خوشه به خوشه و نه به صورت عضو به عضو می کاوند به همین دلیل امکان رخ دادن اپتیمم های محلی از بین می رود. این روشها نیازی به اطلاعات مربوط به مشتقات تابع هدف ندارند. تنها شکل اصلی تابع مورد نیاز می باشد.
چهار فرایند اصلی در الگوریتم ژنتیک عبارتند از

• ایجاد جمعیت کروموزومها (تبدیل مجموعه ای از پاسخهای ممکن به شکل کروموزوم و ژن)
• انتخاب (جفت یابی) (Selection)
• ترکیب (CrossOver)
• جهش (Mutation)

در شکل (ضمیمه ها، Pic1) چگونگی مراحل الگوریتم ژنتیک، نشان داده شده است.
قبل از ادامه بحث لازم است قسمتی بسیار مهم از الگوریتم ژنتیک، تابع تطابق (تابع هدف) (Fitness function - Objective function) را معرفی کنیم. این تابع شاید قلب الگوریتم ژنتیک باشد. انتخاب اعضاء بهتر یا به عبارتی زنده ماندن ژنهای بهتر با این تابع کنترل می شود. در ادامه به صورت مفصل درباره تابع تطابق صحبت خواهد شد.

عناصر الگوریتم ژنتیک
الگوریتمهای ژنتیک اگرچه در شکلهای مختلفی وجود دارند اما حداقل شامل چهار قسمت زیر می باشند:

• جمعیتی از جوابهای ممکن که به کروموزوم و ژن تبدیل شده اند.
• عملگر انتخاب
• عملگر ترکیب
• عملگر جهش

طراحی یک الگوریتم ژنتیک برای مساله ای خاص دارای سه مرحله است:

• طراحی شیوه کدگذاری
• طراحی تابع تطابق
• طراحی عملگرهای ژنتیک

در ادامه هر کدام از این عناصر مورد بررسی قرار می گیرد.

جمعیت
مفهوم جمعیت در الگوریتم ژنتیک شبیه به چیزی است که در زندگی طبیعی وجود دارد. برای مساله گزاره هایی وجود دارند که می توانند به عنوان پاسخ، چه درست، چه غلط در نظرگرفته شوند. به این گزاره ها پاسخهای ممکن یا شدنی می گوییم. مثلا اگر مساله یافتن ماکزیمم یک تابع در مجموعه اعداد صحیح باشد، تمام اعداد صحیح می توانند به عنوان پاسخ شدنی مساله در نظر گرفته شوند.
در الگوریتم ژنتیک به عنوان اولین مرحله لازم است مجموعه ای از جوابهای شدنی به عنوان جمعیت اولیه ایجاد شود. اعضای این مجموعه معمولا به صورت تصادفی انتخاب می شوند اما در الگوریتمهای بهینه، از قیدهایی استفاده می شود تا جمعیت پراکندگی بیش از حد نداشته باشد. تعداد اعضای جمعیت به نوع مساله بستگی دارد. در واقع تعداد اعضا، پارامتری است که با تغییر آن می توان دقت جوابها و سرعت همگرایی جستجو را بهبود بخشید. در برخی مسایل یک جمعیت 8 عضوی کاملا مناسب است در حالی که در برخی یک جمعیت 100 عضوی نیز کافی نیست. بر اساس تجربه بهتر است تعداد اعضای جمعیت عددی بین 10 تا 160 باشد.
بعد از انتخاب جمعیت، لازم است اعضای آن به شکل کروموزوم درآیند. هر کروموزوم آرایشی از چند ژن است. در مرحله تبدیل (کدگذاری) (Encoding) ، جوابها به ژنها تبدیل می شوند. روشهای مختلفی برای کدگذاری وجود دارد. انتخاب روش وابسته به نوع مساله ای است که به آن پرداخته می شود. نکته قابل ذکر در تبدیل جوابها به کروموزوم ها این است که طول کروموزوم ها باید برابر و ثابت باشد یعنی اگر یک جواب از مجموعه به کروموزومی با n ژن تبدیل شد، طول تمام کروموزومهای دیگر نیز باید n باشد. طول کروموزومها را نوع کدگذاری، جنس پاسخها و محدوده پاسخها تعیین می کند. کروموزومها در الگوریتم ژنتیک باید به گونه ای باشند که دقیقا تمام مشخصات پاسخ را در خود ذخیره کنند. مثلا اگر مساله با اعداد حقیقی کار می کند، کروموزوم باید شامل اطلاعات مربوط به علامت عدد، تعداد رقمهای اعشاری، محدوده عدد و ... باشد. مهمترین نوع کدگذاری، کدگذاری باینری است.

جمعیت
ادامه در فایل ضمیمه

انتخاب در الگوریتم ژنتیک

انتخاب چرخ رولت

انتخاب ترتیبی، بولتزمن، حالت پایدار و رقابتی

ترکیب و انواع آن در GAs

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

با توجه به مطالب گفته شده، الگوریتم ژنتیک را می توان مانند آنچه در فایل ضمیمه است، بیان کرد.

استدلال همگرایی الگوریتم ژنتیک

فایلی در فرمت pdf اما... به انگلیسی! خیلی شرمندم!

کمی ریاضی.

مقاله ای دیگر

سلام با تشکر از مطالب مفیدتون . من این ترم باید یک پروژه به زبان #C با الگوریتم ژنتیک انجام بدم ودنبال یک موضوع ساده هستم .اگر ممکنه یک موضوع معرفی کنید که پیاده سازی اش با الگوریتم ژنتیک آسون باشه ممنون.

زمانبندی چند پردازنده ای کدش اماده پیدا میشه

با تشکر از راهنمایی و کمک شما عزیزان

سلام
مسئله کاشی کاری را هم می شود با الگوریتم ژنتیک حل و پیاده سازی کرد؟
آیا یه همچین سورسی موجود است؟

من دو تا سئوال در مورد این الگوریتم دارم که ممنون می شم راهنماییم کنین:
1.نخبه گرایی در این الگوریتم یعنی چی؟
2.توضیح مطلب زیر:
شما[1]فرض كنيد كه كرو موزومهاي مساله داراي طول lباشند مدل شماتيك مساله به شكل زير نشان داده مي‌شود:(a1, a2, ..., ai, ..., al), ai Î {0, 1, #}.

كه در آن # نشاندهنده تمامي <حالتهاي ممكن و مجاز[2] > براي يك <موقعيت بيتي خاص[3]> ميباشد.
يعني در حالت كلي (01#0#1)بيانگر
{(010001), (010011), (011001), (011011)}.مي
باشد.
براي رشته‌اي به طول l كد در هر موقعيت مكاني آن k حالت مختلف مجاز مي‌باشد تعداد kl حالت در مجموعه اوليه جوابها وجود دارد.

براي رشته‌اي به طول l كد در هر موقعيت مكاني آن k حالت مختلف مجاز مي‌باشد تعداد(K+1)lحالت در مجموعه شماتيك وجود دارد.

[1] Schemata

[2] Allel

[3] Locus

جناب Sherlukholmz،
با سلام خدمت حضرتعالی،

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

http://www.barnamenevis.org/sh...d.php?t=109086

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

اگر از خود شما نیست می خواستم از جنابعالی درخواست مطالبی در ایزمینه را داشته باشم. اگر لطف بفرمایید جواب بنده را بدهید ممنون می شوم.

با تشکر.

با توجه به مقالات مفید مهندس مقدم نمونه سورسی در سایت قرار دادم که علاقه مندان میتونند استفاده کنند.

سورس حل معمای 8 وزیر توسط الگوریتم ژنتیک به زبان Vb.Net

موفق باشید