بخشی از مقاله

ژنتیک

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


مختصراً گفته مي شود که الگوريتم ژنتيک (يا 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)
fit(A)=3 , fit(B)=1 , fit(C)=2
معمولاً الگوريتم هاي ژنتيک يک عدد احتمال اتصال دارد که بين 0.6 و1 است که احتمال به وجود آمدن فرزند را نشان مي دهد.ارگانيسم ها با اين احتمال دوباره با هم ترکيب مي شوند.اتصال 2 کروموزوم فرزند ايجاد مي کند،که به نسل بعدي اضافه مي شوند.اين کارها انجام مي شوند تا اين که کانديدهاي مناسبي براي جواب،در نسل بعدي پيدا شوند. مرحله بعدي تغيير دادن فرزندان جديد است. الگوريتم هاي ژنتيک يک احتمال تغيير کوچک وثابت دارند که معمولاً درجه اي در حدود 0.01 يا کمتر دارد. بر اساس اين احتمال ،کروموزوم هاي فرزند به طور تصادفي تغيير مي کنند يا جهش مي يابند.مخصوصاً با جهش بيتها در کروموزوم ساختمان داده يمان.


اين فرآيند باعث به وجود آمدن نسل جديدي از کروموزوم ها يي مي شود، که با نسل قبلي متفاوت است.کل فرآيند براي نسل بعدي هم تکرار مي شود،جفتها براي ترکيب انتخاب مي شوند،جمعيت نسل سوم به وجود مي آيندو... .
پس به صورت خلاصه مراحل به ترتيب زير مي باشد:
1. selectتعداد(1-r)p فرضیه از میان P انتخاب و به Ps اضافه کنید. احتمال انتخاب یک فرضیه hi از میانP عبارت است از:
P(hi) = Fitness (hi) / Σj Fitness (hj)


2. : Crossoverبا استفاده از احتمال بدست آمده توسط رابطه فوق، تعداد(rp)/2 زوج فرضیه از میان P انتخاب و با استفاده از اپراتورCrossover دو فرزند از آنان ایجاد کنید. فرزندان را به Ps اضافه کنید.
3. : Mutateتعداد m درصد از اعضا Ps را با احتمال یکنواخت انتخاب و یک بیت از هر یک آنها را بصورت تصادفی معکوس کنید
4. Pß Ps :Update
5. برای هر فرضیه h در P مقدار تابع Fitness را محاسبه کنید
ايده اصلي:


در دهه هفتاد ميلادي دانشمندي از دانشگاه ميشيگان به نام جان هلند ايده استفاده از الگوريتم ژنتيك را در بهينه‌سازي‌هاي مهندسي مطرح كرد. ايده اساسي اين الگوريتم انتقال خصوصيات موروثي توسط ژن‌هاست. فرض كنيد مجموعه خصوصيات انسان توسط كروموزوم‌هاي او به نسل بعدي منتقل مي‌شوند. هر ژن در اين كروموزوم‌ها نماينده يك خصوصيت است. بعنوان مثال ژن 1 مي‌تواند رنگ چشم باشد ، ژن 2 طول قد، ژن 3 رنگ مو و الي آخر. حال اگر اين كروموزوم به تمامي، به نسل بعد انتقال يابد، تمامي خصوصيات نسل بعدي شبيه به خصوصيات نسل قبل خواهد بود. بديهيست كه در عمل چنين اتفاقي رخ نمي‌دهد. در واقع بصورت همزمان دو اتفاق براي كروموزوم‌ها مي‌افتد. اتفاق اول موتاسيون (Mutation) است.

موتاسيون به اين صورت است كه بعضي ژن‌ها بصورت كاملا تصادفي تغيير مي‌كنند. البته تعداد اين گونه ژن‌ها بسيار كم مي‌باشد اما در هر حال اين تغيير تصادفي همانگونه كه پيشتر ديديم بسيار مهم است. مثلا ژن رنگ چشم مي‌تواند بصورت تصادفي باعث شود تا در نسل بعدي يك نفر داراي چشمان سبز باشد. در حالي كه تمامي نسل قبل داراي چشم قهوه‌اي بوده‌اند. علاوه بر موتاسيون اتفاق ديگري كه مي‌افتد و البته اين اتفاق به تعداد بسيار بيشتري نسبت به موتاسيون رخ مي‌دهد چسبيدن ابتداي يك كروموزوم به انتهاي يك كروموزوم ديگر است. اين مساله با نام Crossover شناخته مي‌شود. اين همان چيزيست كه مثلا باعث مي‌شود تا فرزند تعدادي از خصوصيات پدر و تعدادي از خصوصيات مادر را با هم به ارث ببرد و از شبيه شدن تام فرزند به تنها يكي از والدين جلوگيري مي‌كند. براي عمل تركيب ويژگي هاي والد مي توان به صورت زير عمل كرد:


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


0 0 0 0 0 0 0 0 0 0 0 0 0
والدین
1 1 1 1 1 1 1 1 1 1 1 1 1


1 1 1 1 1 1 1 1 1 0 0 0 0
فرزند
0 0 0 0 0 0 0 0 0 1 1 1 1

نحوه انجام عملیات بازترکیبی
روش کار به صورت زیر است:
• بصورت تصادفی یک نقطه از کروموزوم را انتخاب می-کنیم
• ژنهای مابعد آن نقطه از کروموزوم¬ها را جابجا می-کنیم


شایان ذکر است که عمل بازترکیبی را می¬توان هم از نقاط آغازین ژن¬ها انجام داد و هم اینکه می¬توان بدون توجه به محل شروع ژن، عمل بازترکیبی را انجام داد.
همچنین اگر مانند مثال فوق عملیات بازترکیبی را در یک نقطه انجام دهیم به آن بازترکیبی تک نقطه¬ای (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 تبديل شده .
جهش:


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


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


والد 0 0 0 0 0 0 0 0 0 0 0 0 0


فرزند 0 0 1 1 0 0 0 1 0 0 1 0 0


نحوه انجام عملیات جهش

جهش، برای بازنمائی¬هایی که از مقادیر حقیقی استفاده کرده-اند، به این صورت پیاده سازی می¬شود که یک عدد حقیقی بصورت تصادفی در یک محدوده خاص تعیین و جایگزین عدد قبلی گردد و یا اینکه عدد اصلی با یک مقدار خاص جمع گردد و ....
برای سایر ارائه¬ها نیز انواع خاصی از جهش پیشنهاد شده است.
با توجه به اینکه هدف از جهش بهتر شدن کروموزوم¬ها و یا اینکه پیدا شدن یک راه حل جدید است، می¬توانیم به جای تغییر تصادفی کروموزوم¬ها، تغییرات کروموزوم¬ها را هدفمند کنیم. برای اینکار، بسته به نوع مساله، بر روی کروموزوم انتخاب شده یکی از روشهای کلاسیک حل مساله را اعمال کرده، و جواب حاصل را بعنوان کروموزوم جدید جایگزین می¬کنند. استفاده از این روش که از آن با عنوان جهش ابتکاری (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 را توليد،تغيير وانتخاب را اعمال مي کنيم.الگوريتم وقتي پايان مي يابد که به معيارمان برسيم.

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