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

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

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

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

مختصراً گفته می شود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می کند.

مسئله ای که باید حل شود ورودی است و راه حل ها طبق یک الگو کد گذاری می شود ومتریک که تابع fitness هم نام دارد هر راه حل کاندید را ارزیابی می کندکه اکثر آنها به صورت تصادفی انتخاب می شوند.

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

کلاً این الگوریتم ها از بخش های زیر تشکیل می شوند : انتخاب مجدد selection ترکیب combination جهش ژنی mutation که در ادامه آنها را توضیح خواهیم داد.

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

مثلا فرض کنید گونه خاصی از افراد هوش بسیار بیشتری از بقیه افراد یک جامعه یا کولونی دارند.

در شرایط کاملا طبیعی این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتا بالاتری خواهند داشت و این رفاه خود باعث طول عمر بیشتر و باروری بهتر خواهد بود(توجه کنید شرایط طبیعی است نه در یک جامعه سطح بالا با ملاحظات امروزی یعنی طول عمر بیشتر در این جامعه نمونه با زاد و ولد بیشتر همراه است).

حال اگر این خصوصیت(هوش)ارثی باشد به طبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشتر این‌گونه افراد بیشتر خواهد بود.

اگر همین روند را ادامه دهید خواهید دید که در طی نسل‌های متوالی دائما جامعه نمونه ما باهوش و باهوش‌تر می‌شود.

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

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

در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مساله یاری کند مفهومیست به نام : تصادف یا جهش.

هدف اصلی روش‌های هوشمند به کار گرفته شده در هوش مصنوعی یافتن پاسخ بهینه مسائل مهندسی است.

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

در مورد نکته دوم باید بگوییم که روش‌های ریاضی بهینه‌سازی اغلب منجر به یک فرمول یا دستورالعمل خاص برای حل هر مسئله می‌شوند.

در حالی که روش‌های هوشمند دستورالعمل‌هایی هستند که به صورت کلی می‌توانند در حل هر مسئله‌ای به کار گرفته شوند.

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

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

برای اینکه جواب سوال را دریابیم، ابتدا باید فرآیند تولید مثل موجودات را بررسی کنیم.

در جریان تولید مثل یک موجود کروموزوم­های والدین موجود با یکدیگر ترکیب می­شوند و سلول تخم را تشکیل می دهند.

تکثیر این سلول تخم منجر به تشکیل یک فرزند تقریباً مشابه والدینش می­شود.

این موجود ترکیبی از خصوصیات والدین خود را به همراه خواهد داشت.

این روند باعث تکامل یک موجود می­شود.

اما تا اینجای کار اتفاق خاصی که باعث ایجاد یک موجود جدید گردد به وقوع نپیوسته است.

نکته کار اینجاست که در حین تشکیل سلول تخم تغییرات ناخواسته­ای درون کروموزوم(های) سلول بوجود می­آید.

این تغییرات اگر کوچک باشند، در حین تکثیر سلول تخم و تشکیل موجود اصلی اصلاح می­شوند.

اما تغییرات بزرگ اصلاح نمی­شوند و منجر به تشکیل یک موجود جدید می­شوند.

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

با توجه به اینکه این فرزندان نیز در تقابل با محیط موفق­تر هستند، امکان تولید مثل پیدا می­کنند.

با توجه به مطالب فوق متوجه می­شوید که سه فاکتور اصلی مبنای نظریه داروین را تشکیل می­دهند، این سه فاکتور عبارتند از: · تنوع: ترکیب شدن مشخصات والدین متفاوت باعث می­شود که خصوصیات خوب آنها ترکیب شود و یک موجود بهتر بوجود آید.

· تصادف: عامل ایجاد تغییرات در موجودات فرزند · انتخاب: که توسط محیط انجام می­شود، به این معنی که موجودات با شایستگی پائین احتمال ادامه حیات و تولید مثل کمتری دارند.

(بقای شایسته­ترین) روند فوق و مخصوصاً سه فاکتور فوق مبنای کار دانشمندان رشته کامپیوتر قرار گرفت و در نتیجه الگوریتم­های ژنتیک بوجود آمدند.

این روش در سال 1970 توسط John Holland معرفی گردید این روشها با نام Evolutionary Algorithms نیز خوانده میشوند.

پیشرفت این الگوریتم­ها باعث شد که کلاً مجموعه روشهای حل مساله با نام پردازش تکاملی بوجود بیاید.

پردازش تکاملی از شاخه­های زیر تشکیل شده­ است: 1.

الگوریتم­های ژنتیک (Genetic Algorithms) 2.

برنامه نویسی ژنتیک (Genetic Programming) 3.

استراتژی های تکاملی (Evolutionary Strategies) 4.

برنامه نویسی تکاملی (Evolutionary Programming) نحوه ارائه مطالب به این صورت است که در ابتدا قسمتهای مختلف یک الگوریتم ژنتیک را بیان کرده و هریک را به اختصار تشریح می­کنیم.

سپس بیان می­کنیم که یک الگوریتم ژنتیک چه خصوصیاتی باید داشته باشد، بخش اول : الگوریتم ژنتیک الگوریتم ژنتیک چیست؟

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

این الگوریتم­ها با الهام از روند تکاملی طبیعت، مسائل را حل می­کنند.

به این معنی که مانند طبیعت یک جمعیت از موجودات تشکیل می­دهند و درون این موجودات اقدام به انجام اعمالی چون انتخاب والدین، تولید مثل، جهش و ...

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

این الگوریتم­ها با توجه به خصوصیات خاصی که دارند، به خوبی از عهده حل مسائلی که نیاز به بهینه­سازی دارند و یا پارامترهای زیادی در آنها دخیل است، برمی­آیند.

در این قسمت به معرفی این الگوریتم­ها می­پردازیم.

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

مدلسازی مساله یا بازنمائی 2.

تشکیل جمعیت اولیه 3.

ارزیابی جمعیت 4.

انتخاب والدین 5.

بازترکیبی 6.

جهش 7.

انتخاب فرزندان 8.

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

موتور الگوریتم ژنتیک یک جمعیت آغازین از فرمول ایجاد می کند.هر فرد در برابر مجموعه ای از داده های مورد آزمایش قرار می گیرد و مناسبترین آنها انتخاب می شود که شاید 10 درصد از مناسبترین ها باقی بمانند و بقیه کنار گذاشته می شوند.

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

الگوریتم ژنتیک GA یک تکنیک جستجو در علم کامپیوتربرای یافتن راه حل بهینه ومسائل جستجو است.الگوریتم های ژنتیک یکی از انواع الگوریتم های تکاملی اند که از علم زیست شناسی مثل وراثت، جهش،انتخاب ناگهانی ، انتخاب طبیعی و ترکیب الهام گرفته شده اند.

عموماً راه حلها به صورت 2 تایی 0 و1 نشان داده می شوند ولی روشهای نمایش دیگری هم وجود دارد.تکامل از یک مجموعه کاملاً تصادفی از موجودیت ها شروع می شود و در نسلهای بعدی تکرار می شود.در هر نسل،مناسبترین ها انتخاب می شوند نه بهترین ها.

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

کروموزوم ها عموماً به صورت یک رشته ساده از داده ها نمایش داده می شوند،البته انواع ساختمان داده های دیگر هم می توانند مورد استفاده قرار گیرند: 1.

اعداد صحیح 2.

رشته­­های بیتی 3.

اعداد حقیقی در فرم نقطه شناور 4.

اعداد حقیقی به فرم رشته های بیتی 5.

یک مجموعه از اعداد حقیقی یا صحیح 6.

ماشینهای حالت محدود 7.

هر فرم دیگری که بتوانیم عملگرهای ژنتیک را بر روی آنها تعریف کنیم در ابتدا چندین مشخصه به صورت تصادفی برای ایجاد نسل اول تولید می شوند.

در طول هر نسل ،هر مشخصه ارزیابی می شود وارزش تناسب(fitness) توسط تابع تناسب اندازه گیری می شود.

سپس باید نسل اولیه را مشخص کنیم.

بعد از اینکه شکل کروموزومها را تعریف نمودیم، بایستی جمعیتی را تشکیل دهیم، که می­خواهیم عناصر آنرا تکامل دهیم.

تعداد عناصر موجود در این جمعیت معمولاً ثابت است.

به این معنی که هنگامی که تعدادی عنصر در جریان تولید مثل به این جمعیت اضافه می­کنیم، بایستی به همین تعداد عنصر نیز از جمعیت قبلی حذف کنیم.

قبل از اینکه الگوریتم بتواند آغاز به کار کند، بایستی یک جمعیت اولیه از کروموزوم­ها تشکیل بدهیم.

در اکثر الگوریتم­ها این جمعیت اولیه به صورت تصادفی تشکیل می­شود.

به این معنی که به اندازه طول جمعیت، کروموزوم تصادفی ایجاد می­کنیم و آنها را به جمعیت اولیه اضافه می­کنیم.

البته برای اینکه الگوریتم سریعتر به جواب برسد، می­توانیم بوسیله یکی از الگوریتم­های کم هزینه تعدادی از جوابهای تقریباً بهینه را محاسبه کرده و از آنها بعنوان جمعیت اولیه استفاده می­کنیم.

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

البته نباید فراموش کنیم که انجام این عمل در مواردی باعث می شود، الگوریتم در مینیمم­های محلی ناشی از جمعیت آغازی گیر افتاده و نتواند جوابهای بهتری را پیدا کند.

برای جلوگیری از این مشکل علاوه بر جوابهای بهینه پیدا شده، تعدادی عنصر نیز به صورت تصادفی به جمعیت اضافه می­کنیم.

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

برای هر فرد ،یک جفت والد انتخاب می شود.در هر نسل تعدادی از عناصر جمعیت این فرصت را پیدا می­کنند که تولید مثل کنند.

به این عناصر که از میان جمعیت انتخاب می­شوند، والدین می­گویند.

روشهای مختلفی برای انتخاب والدین وجود دارند.

در زیر به چند مورد از این روشها اشاره می­کنیم: 1.

انتخاب تمام جمعیت به عنوان والدین: در واقع هیچگونه انتخابی انجام نمی­دهیم.

2.

انتخاب تصادفی: بصورت تصادفی تعدادی از موجودات جمعیت را به عنوان والدین انتخاب می­کنیم، این انتخاب می­تواند با جایگذاری یا بدون جایگذاری باشد.

3.

روشهای مبتنی بر شایستگی: در این روشها عناصر با شایستگی بیشتر شانس بیشتری برای انتخاب شدن به عنوان والدین را دارند.

4.

سایر روشها: این روشها با استفاده از تکنیکهایی سعی می­کنند که انتخابهایی را ارائه دهند، که هم رسیدن به جواب نهایی را تسریع کنند و هم اینکه کمک می­کنند که جواب بهینه­تری پیدا شود.

انتخابها به گونه ای اند که مناسبترین عناصر انتخاب شوند تا حتی ضعیفترین عناصر هم شانس انتخاب داشته باشند تا از نزدیک شدن به جواب محلی جلوگیری شود.سایر الگوهای انتخاب عبارتند از: چرخ منگنه دار(رولت)،انتخاب مسابقه ای (Tournament) ،...

.

به عنوان نمونه اگر بخواهیم رولت را بررسی کنیم باید به مسائل زیر توجه شود: در روش معرفی شده در الگوریتم ساده GA احتمال انتخاب یک فرضیه برای استفاده در جمعیت بعدی بستگی به نسبت fitness آن به fitness بقیه اعضا دارد.

این روش Roulette Wheel selectionنامیده میشود.

P(hi) = Fitness (hi) / Σj Fitness (hj) A C 1/6 = 17% 3/6 = 50% B 2/6 = 33% fit(A)=3 , fit(B)=1 , fit(C)=2 معمولاً الگوریتم های ژنتیک یک عدد احتمال اتصال دارد که بین 0.6 و1 است که احتمال به وجود آمدن فرزند را نشان می دهد.ارگانیسم ها با این احتمال دوباره با هم ترکیب می شوند.اتصال 2 کروموزوم فرزند ایجاد می کند،که به نسل بعدی اضافه می شوند.این کارها انجام می شوند تا این که کاندیدهای مناسبی برای جواب،در نسل بعدی پیدا شوند.

مرحله بعدی تغییر دادن فرزندان جدید است.

الگوریتم های ژنتیک یک احتمال تغییر کوچک وثابت دارند که معمولاً درجه ای در حدود 0.01 یا کمتر دارد.

بر اساس این احتمال ،کروموزوم های فرزند به طور تصادفی تغییر می کنند یا جهش می یابند.مخصوصاً با جهش بیتها در کروموزوم ساختمان داده یمان.

این فرآیند باعث به وجود آمدن نسل جدیدی از کروموزوم ها یی می شود، که با نسل قبلی متفاوت است.کل فرآیند برای نسل بعدی هم تکرار می شود،جفتها برای ترکیب انتخاب می شوند،جمعیت نسل سوم به وجود می آیندو...

پس به صورت خلاصه مراحل به ترتیب زیر می باشد: selectتعداد(1-r)p فرضیه از میان P انتخاب و به Ps اضافه کنید.

احتمال انتخاب یک فرضیه hi از میانP عبارت است از:P(hi) = Fitness (hi) / Σj Fitness (hj) : Crossoverبا استفاده از احتمال بدست آمده توسط رابطه فوق، تعداد(rp)/2 زوج فرضیه از میان P انتخاب و با استفاده از اپراتورCrossover دو فرزند از آنان ایجاد کنید.

فرزندان را به Ps اضافه کنید.: Mutateتعداد m درصد از اعضا Ps را با احتمال یکنواخت انتخاب و یک بیت از هر یک آنها را بصورت تصادفی معکوس کنیدPß Ps :Updateبرای هر فرضیه h در P مقدار تابع Fitness را محاسبه کنیدایده اصلی: در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه‌سازی‌های مهندسی مطرح کرد.

ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست.

فرض کنید مجموعه خصوصیات انسان توسط کروموزوم‌های او به نسل بعدی منتقل می‌شوند.

هر ژن در این کروموزوم‌ها نماینده یک خصوصیت است.

بعنوان مثال ژن 1 می‌تواند رنگ چشم باشد ، ژن 2 طول قد، ژن 3 رنگ مو و الی آخر.

حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود.

بدیهیست که در عمل چنین اتفاقی رخ نمی‌دهد.

در واقع بصورت همزمان دو اتفاق برای کروموزوم‌ها می‌افتد.

اتفاق اول موتاسیون (Mutation) است.

موتاسیون به این صورت است که بعضی ژن‌ها بصورت کاملا تصادفی تغییر می‌کنند.

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

مثلا ژن رنگ چشم می‌تواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد.

در حالی که تمامی نسل قبل دارای چشم قهوه‌ای بوده‌اند.

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

این مساله با نام Crossover شناخته می‌شود.

این همان چیزیست که مثلا باعث می‌شود تا فرزند تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن تام فرزند به تنها یکی از والدین جلوگیری می‌کند.

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

این موضوع باعث می­شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند.

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

این موضوع باعث میشود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند.

ما نیز این موضوع را در الگوریتم ژنتیک خود شبیه سازی می کنیم، به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.

روش کار در شکل زیر نشان داده شده است: نحوه انجام عملیات بازترکیبی روش کار به صورت زیر است: · بصورت تصادفی یک نقطه از کروموزوم را انتخاب میکنیم · ژنهای مابعد آن نقطه از کروموزومها را جابجا میکنیم شایان ذکر است که عمل بازترکیبی را میتوان هم از نقاط آغازین ژنها انجام داد و هم اینکه میتوان بدون توجه به محل شروع ژن، عمل بازترکیبی را انجام داد.

همچنین اگر مانند مثال فوق عملیات بازترکیبی را در یک نقطه انجام دهیم به آن بازترکیبی تک نقطهای (Single Point Crossover) میگویند.

اما میتوانیم این عملیات را در چند نقطه انجام دهیم، که به آن بازترکیبی چند نقطهای (Multipoint Crossover) میگویند، و در پایان اگر تمام نقاط کروموزوم را بعنوان نقاط بازترکیبی انتخاب کنیم به آن بازترکیبی جامع (Uniform Crossover) میگوئیم.

لازم به ذکر است که عملیات بازترکیبی موجودات جدیدی تولید نمیکند و تنها باعث میشود که موجودات موجود بهتر شوند.

در صورتی که برای بازنمائی کروموزومها از روشهایی غیر از اعداد صحیح و یا رشتههای عددی استفاده کرده باشیم، عملیات بازترکیبی را به روشهای دیگری پیاده سازی میکنیم.

به عنوان مثال اگر از اعداد حقیقی برای ارائه استفاده کرده باشیم، یک روش اینست که قسمت حقیقی و مانتیس دو عدد را جابجا کنیم.

برای سایر بازنمائیها نیز روشهای مختلفی برای بازترکیبی ارائه شده است که از حوصله این بحث خارج است.

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

انتخاب Elitist : مناسبترین عضو هر اجتماع انتخاب می شود.

انتخاب Roulette : یک روش انتخاب است که در آن عنصری که عدد برازش(تناسب)بیشتری داشته باشد،انتخاب می شود.

انتخاب Scaling : به موازات افزایش متوسط عدد برازش جامعه،سنگینی انتخاب هم بیشتر می شود وجزئی تر.این روش وقتی کاربرد دارد که مجموعه دارای عناصری باشد که عدد برازش بزرگی دارند و فقط تفاوت های کوچکی آنها را از هم تفکیک می کند.

انتخاب Tournament : یک زیر مجموعه از صفات یک جامعه انتخاب می شوندواعضای آن مجموعه با هم رقابت می کنندو سرانجام فقط یک صفت از هر زیر گروه برای تولید انتخاب می شوند.

بعضی از روشهای دیگر عبارتند از:Rank Selection, Generational Selection, Steady-State Selection .Hierarchical Selection روش های تغییر: وقتی با روش های انتخاب کروموزوم ها انتخاب شدند،باید به طور تصادفی برای افزایش تناسبشان اصلاح شوند.2 راه حل اساسی برای این کار وجود دارد.

اولین و ساده ترین جهش (Mutation) نامیده می شود.درست مثل جهش در موجودات زنده که عبارت است از تغییر یک ژن به دیگری، در الگوریتم ژنتیک جهش تغییر کوچکی در یک نقطه از کد خصوصیات ایجاد می کند.

دومین روش Crossover نام دارد و 2 کروموزوم برای معاوضه سگمنتهای کدشان انتخاب می شوند.این فرآیند بر اساس فرآیند ترکیب کروموزوم ها در طول تولید مثل در موجودات زنده شبیه سازی شده.

اغلب روش های معمول Crossover شامل Single-point Crossover هستند ، که نقطه تعویض در جایی تصادفی بین ژنوم ها است.بخش اول قبل از نقطه ،و بخش دوم سگمنت بعد از آن ادامه پیدا می کند،که هر قسمت برگرفته از یک والد است،که 50/50 انتخاب شده.

شکل های بالا تاثیر هر یک از عملگر های ژنتیک را روی کروموزوم های 8 بیتی نشان می دهد.

شکل بالاتر 2 ژنوم را نشان می دهد که نقطه تعویض بین 5امین و 6امین مکان در ژنوم قرار گرفته،ایجاد یک ژنوم جدید از پیوند این 2 والد بدست می آیند.شکل 2وم ژنومی را نشان می دهد که دچار جهش شده و 0 در آن مکان به 1 تبدیل شده .

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

بعنوان مثال در مینیمم سازی یک تابع، عملیات بازترکیبی ما را به مینیممهای محلی که عناصر اولیه در نزدیکی آنها قرار داشتهاند هدایت میکند، و نمیتواند ما را به مینیممهای کلی و یا حتی مینیممهای محلی دیگر هدایت کند.

برای حل کردن این مشکل به این صورت عمل میکنیم که با تغییرات تصادفی در ژنها، کروموزومها را به نقاط ناشناخته پرتاب میکنیم، به این امید که احتمالاً این نقطه جدید ما را به مینیمم کلی هدایت کند.

برای انجام جهش به این صورت عمل میکنیم: · بصورت تصادفی تعدادی از کروموزومهای فرزند را انتخاب میکنیم · به صورت تصادفی مقادیر یک یا چند ژن وی را تغییر میدهیم.

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

برای سایر ارائهها نیز انواع خاصی از جهش پیشنهاد شده است.

با توجه به اینکه هدف از جهش بهتر شدن کروموزومها و یا اینکه پیدا شدن یک راه حل جدید است، میتوانیم به جای تغییر تصادفی کروموزومها، تغییرات کروموزومها را هدفمند کنیم.

برای اینکار، بسته به نوع مساله، بر روی کروموزوم انتخاب شده یکی از روشهای کلاسیک حل مساله را اعمال کرده، و جواب حاصل را بعنوان کروموزوم جدید جایگزین میکنند.

استفاده از این روش که از آن با عنوان جهش ابتکاری (Heuristic) یاد میشود، بسته به نوع مساله ممکن است دستیابی به راه حل نهایی را سریعتر کنند.

البته در این موارد بایستی از روشهای ابتکاری سریع استفاده کنیم و یا اینکه با الگوریتمهای کم هزینه تنها به بهتر کردن کروموزوم بپردازیم.

نکته آخری که به آن اشاره کنیم این است که جهش باعث ایجاد تغییرات ناخواسته در جمعیت شده، و باعث بوجود آمدن موجودات جدید میشود.

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

نتیجهای که از این مطلب بدست میآید اینست که در صورتی که فقط از جهش استفاده کنیم، ممکن است که بتوانیم جواب بهینه را پیدا کنیم، اما استفاده از بازترکیبی به تنهایی پیدا شدن جواب بهینه تضمین نمیشود.

یک نکته ای که می توان به آن پرداخت پاسخ به سؤال زیر است: Mutation or Crossover?

این سوال ها سالها مطرح بوده است: کدامیک بهتر است؟

کدامیک لازم است؟

کدامیک اصلی است؟

پاسخی که تاکنون بیشتر از بقیه پاسخها مورد قبول بوده: بستگی به صورت مسئله دارد در حالت کلی بهتر است از هر دو استفاده شود هر کدام نقش مخصوص خود را دارد میتوان الگوریتمی داشت که فقط از mutation استفاده کند ولی الگوریتمی که فقط ازcrossover استفاده کند کار نخواهد کرد.

Crossover خاصیت جستجوگرانه و یا explorative دارد.

میتواندبا انجام پرشهای بزرگ به محل هائی دربین والدین رفته و نواحی جدیدی را کشف نماید.

Mutationخاصیت گسترشی و یا exploitive دارد.

میتواند با انجام تغییرات کوچک تصادفی به نواحی کشف شده وسعت ببخشد.

Crossoveاطلاعات والدین را ترکیب میکند درحالیکه mutation میتواند اطلاعات جدیدی اضافه نماید.

برای رسیدن به یک پاسخ بهینه یک خوش شانسی در mutation لازم است.

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

بودجه اختصاص داده شده تمام شود(زمان محاسبه/پول).

یک فرد(فرزند تولید شده) پیدا شود که مینیمم (کمترین)ملاک را برآورده کند.

بیشترین درجه برازش فرزندان حاصل شود یا دیگر نتایج بهتری حاصل نشود.

بازرسی دستی.

ترکیبهای بالا.

اگر در حالت عملی بخواهیم این موضوع را نشان دهیم به طریق زیر عمل می کنیم: در ابتدا تعداد مشخصی از ورودی ها،X1,X2,…,Xn که متعلق به فضای نمونه X هستند را انتخاب می کنیم و آنها را در یک عدد بردای X=(x1,x2,…xn) نمایش می دهیم.در مهندسی نرم افزار اصطلاحاً به آنها ارگانیسم یا کروموزوم گفته می شود.به گروه کروموزوم ها Colony یا جمعیت می گوییم.در هر دوره Colony رشد می کند و بر اساس قوانین مشخصی که حاکی از تکامل زیستی است تکامل می یابند.

برای هر کروموزوم Xi ،ما یک ارزش تناسب(Fitness) داریم که آن را f(Xi) هم می نامیم.عناصر قویتر یا کروموزوم هایی که ارزش تناسب آنها به بهینه Colony نزدیکتر است شانس بیشتری برای زنده ماندن در طول دوره های دیگر و دوباره تولید شدن را دارند و ضعیفترها محکوم به نابودی اند.

به عبارت دیگر الگوریتم ورودی هایی که به جواب بهینه نزدیکترند را نگه داشته واز بقیه صرف نظر می کند.

یک گام مهم دیگر درالگوریتم،تولد است که در هر دوره یکبار اتفاق می افتد.

محتویات دو کروموزومی که در فرآیند تولید شرکت می کنند با هم ترکیب میشوند تا 2 کروموزوم جدید که ما انها را فرزند می نامیم ایجاد کنند.

این هیوریستیک به ما اجازه می دهد تا 2 تا از بهترین ها را برای ایجاد یکی بهتر از آنها با هم ترکیب کنیم.(evolution) به علاوه در طول هر دوره،یک سری از کروموزوم ها ممکن است جهش یابند.

الگوریتم: هر ورودی x در یک عدد برداری X=(x1,x2,..,xn) قرار دارد .برای اجرای الگوریتم ژنتیک مان باید هر ورودی را به یک کروموزوم تبدیل کنیم.می توانیم این را با داشتن log(n) بیت برای هر عنصرو تبدیل ارزش Xi انجام دهیم مثل شکل زیر .

0111111 ...

1010111 1111011 می توانیم از هر روش کد کردن برای اعداد استفاده کنیم.در دوره 0، یک دسته از ورودی های X را به صورت تصادفی انتخاب می کنیم.بعد برای هر دوره iام ما ارزش مقدار Fitness را تولید،تغییر وانتخاب را اعمال می کنیم.الگوریتم وقتی پایان می یابد که به معیارمان برسیم.

سود و کد : Choose initial population Repeat Evaluate the individual fit nesses of a certain proportion of the population Select pairs of best-ranking individuals to reproduce Apply crossover operator Apply mutation operator Until terminating condition برای درک بهتر نحوه کار را به صورت یک فلوچارت به صورت زیر نمایش می دهیم : یک روشی که بسیار کاربرد دارد استفاده از درخت می باشد.

به عنوان مثال اگر بخواهیم برای نمایش از ساختار درختی استفاده کنیم به این صورت نمایش می دهیم.

این روش توسط John Koza توسعه یافت،که برنامه نویسی ژنتیک (Genetic programming)است و برنامه ها را به عنوان شاخه های داده در ساختار درخت نشان می دهد.در این روش تغییرات تصادفی می توانند با عوض کردن عملگرها یا تغییر دادن ارزش یک گره داده شده در درخت،یا عوض کردن یک زیر درخت با دیگری به وجود آیند.

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

اگر یکی به نتیجه نرسید سایر راه ها ادامه می یابند و منابع بیشتری را در اختیار شان قرار می گیرد.

در سال 1999 شرکت Genetic Programming Inc.

یک کامپیوتر موازی با 1000 گره هر یک شامل کامپیوتر های P2, 350 MHZ برای پیاده سازی روش های ژنتیک را مورد استفاده قرار داد.

در نظر بگیرید: همه 8 عدد رشته باینری یک فضای جستجو را تشکیل می دهند،که می تواند به صورت ******** نشان داده شود.رشته 01101010 یکی از اعضای این فضاست.همچنین عضوی از فضاهای *******0و******01و0 ******0و*1*1*1*0و 0**01*01 والی آخر باشد.

به دلیل موازی بودن واین که چندین رشته در یک لحظه مورد ارزیابی قرار می گیرند GA ها برای مسائلی که فضای راه حل بزرگی دارند بسیار مفید است .اکثر مسائلی که این گونه اند به عنوان "غیر خطی" شناخته شده اند.در یک مسئله خطی،Fitness هر عنصر مستقل است،پس هر تغییری در یک قسمت بر تغییر وپیشرفت کل سیستم تاثیر مستقیم دارد.می دانیم که تعداد کمی از مسائل دنیای واقعی به صورت خطی اند.در مسائل غیر خطی تغییر در یک قسمت ممکن است تاثیری ناهماهنگ بر کل سیستم ویا تغییر در چند عنصر تاثیر فراوانی بر سیستم بگذارد.

خوشبختانه موازی بودن GA باعث حل این مسئله می شود ودر مدت کمی مشکل حل می شود.مثلاً برای حل یک مسئله خطی 1000 رقمی 2000 امکان حل وجود دارد ولی برای یک غیر خطی 1000 رقمی 21000 امکان .

یکی از نقاط قوت الگوریتم های ژنتیک که در ابتدا یک کمبود به نظر می رسد این است که :GA ها هیچ چیزی در مورد مسائلی که حل می کنند نمی دانندو اصطلاحاً به آنهاBlind Watchmakers می گوییم .

آنها تغییرات تصادفی را در راه حل های کاندیدشان می دهند وسپس از تابع برازش برای سنجش این که آیا آن تغییرات پیشرفتی ایجاد کرده اند یا نه، استفاده می کنند.مزیت این تکنیک این است که به GA اجازه می دهند یا با ذهنی باز شروع به حل کنند.از آنجایی که تصمیمات آن اساساً تصادفی است،بر اساس تئوری همه راه حلهای ممکن به روی مسئله باز است،ولی مسائلی که محدود به اطلاعات هستند باید از راه قیاس تصمیم بگیرند ودر این صورت بسیاری از راه حلهای نو وجدید را از دست می دهند.

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

محدودیتهای GAها : یک مشکل چگونگی نوشتن عملگر Fitness است که منجر به بهترین راه حل برای مسئله شود.اگر این کارکرد برازش به خوبی و قوی انتخاب نشود ممکن است باعث شود که راه حلی برای مسئله پیدا نکنیم یا مسئله ای دیگر را به اشتباه حل کنیم.

به علاوه برای انتخاب تابع مناسب برای Fitness ،پارامترهای دیگری مثل اندازه جمعیت،نرخ جهش وCrossover ،قدرت ونوع انتخاب هم باید مورد توجه قرار گیرند.

مشکل دیگر،که آن را نارس می نامیم این است که اگر یک ژنوم که فاصله اش با سایر ژنوم های نسل اش زیاد باشد(خیلی بهتر از بقیه باشد)و خیلی زود دیده شود(ایجاد شود)ممکن است محدودیت ایجاد کند و راه حل را به سوی جواب بهینه محلی سوق دهد.این اتفاق معمولاً در جمعیت های کم اتفاق می افتد.روش های Rank ,Scaling tournament selection بر این مشکل غلبه می کنند.