چکیده 

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

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

کلاً این الگوریتم ها از بخش های زیر تشکیل می شوند :

تابع برازش  - نمایش – انتخاب – تغییر

که در ادامه آنها را توضیح خواهیم داد.

مقدمه

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

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

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

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

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

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

   اما آیا می‌توان گفت اختراع هواپیما نتیجه همین تلاش بوده است؟ یا فرضا می‌توان گفت فضا پیماها حاصل بهینه‌سازی طرح اولیه هواپیماها بوده‌اند؟

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

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

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

 در واقع می‌توان تکامل طبیعی را به این‌صورت خلاصه کرد: جست‌وجوی کورکورانه(تصادف یا Blind Search)+ بقای قوی‌تر.

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

   روش‌های کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روش‌ها نقطه بهینه محلی(Local Optima) را بعنوان نقطه بهینه کلی در نظر می‌گیرند و نیز هر یک از این روش‌ها تنها برای مساله خاصی کاربرد دارند. این دو نکته را با مثال‌های ساده‌ای روشن می‌کنیم.

     به شکل زیر توجه کنید. این منحنی دارای دو نقطه ماکزیمم می‌باشد. که یکی از آنها تنها ماکزیمم محلی است. حال اگر از روش‌های بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک مقدار ماکزیمم تابع را بیابیم. مثلا از نقطه 1 شروع کنیم و تابع را ماکزیمم کنیم. بدیهی است اگر از نقطه 1 شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از آن متوقف خواهد شد. اما در روش‌های هوشمند خاصه الگوریتم ژنتیک بدلیل خصلت تصادفی آنها حتی اگر هم از نقطه 1 شروع کنیم باز ممکن است در میان راه نقطه A به صورت تصادفی انتخاب شود که در این صورت ما شانس دست‌یابی به نقطه بهینه کلی (Global Optima) را خواهیم داشت.

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

 

الگوریتم ژنتیک چیست؟

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

    برای مثال اگر بخواهیم نوسانات قیمت نفت را با استفاده از عوامل خارجی وارزش رگرسیون خطی ساده مدل کنیم،این فرمول را تولید خواهیم کرد:قیمت نفت در زمان t=ضریب 1 نرخ بهره در زمان t+ضریب 2 نرخ بیکاری در زمان t+ثابت 1 . سپس از یک معیار برای پیدا کردن بهترین مجموعه ضرایب و ثابت ها جهت مدل کردن قیمت نفت استفاده خواهیم کرد.در این روش 2 نکته اساسی وجود دارد.اول این روش خطی است و مسئله دوم این است که ما به جای اینکه در میان "فضای پارامترها"جستجو کنیم ،پارامترهای مورد استفاده را مشخص کرده ایم.

   با استفاده از الگوریتم های ژنتیک ما یک ابر فرمول یا طرح تنظیم می کنیم که چیزی شبیه"قیمت نفت در زمان t تابعی از حداکثر 4 متغیر است"را بیان می کند. سپس داده هایی برای گروهی از متغیرهای مختلف،شاید در حدود 20 متغیر فراهم خواهیم کرد.سپس الگوریتم ژنتیک اجرا خواهد شد که بهترین تابع و متغیرها را مورد جستجو قرار می دهد.روش کار الگوریتم ژنتیک به طور فریبنده ای ساده،خیلی قابل درک وبه طور قابل ملاحظه ای روشی است که ما معتقدیم حیوانات آنگونه تکامل یافته اند.هر فرمولی که از طرح داده شده بالا تبعیت کند فردی از جمعیت فرمول های ممکن تلقی می شود خیلی شبیه به این که بگوییم جرج بوش فردی از جمعیت انسان های ممکن است.

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

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

     مختصراً گفته می شود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می کند.مسئله ای که باید حل شود ورودی است و راه حلها طبق یک الگو کد گذاری می شودومتریک که تابع fitness هم نام دارد هر راه حل کاندید را ارزیابی می کندکه اکثر آنها به صورت تصادفی انتخاب می شوند.[3]

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

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

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

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

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

    معمولاً الگوریتم های ژنتیک یک عدد احتمال اتصال دارد که بین 0.6و1 است که احتمال به وجود آمدن فرزند را نشان می دهد.ارگانیسم ها با این احتمال با هم دوباره با هم ترکیب می شوند.اتصال 2 کروموزوم فرزند ایجاد می کند،که به نسل بعدی اضافه می شوند.این کارها انجام می شوند تا این که کاندیدهای مناسبی برای جواب،در نسل بعدی پیدا شوند. مرحله بعدی تغییر دادن فرزندان جدید است.الگوریتم های ژنتیک یک احتمال تغییر کوچک وثابت دارند که معمولاً درجه ای در حدود 0.01 یا کمتر دارد. بر اساس این احتمال ،کروموزوم های فرزند به طور تصادفی تغییر می کنند یا جهش می یابند.مخصوصاً با جهش بیتها در کروموزوم ساختمان داده مان.

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

این فرآیند تکرار می شود تا این که به آخرین مرحله برسیم.

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

1       به تعداد ثابتی از نسل ها برسیم .

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

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

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

5       بازرسی دستی.

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

ایده اصلی

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

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

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

    یک گام مهم دیگر درالگوریتم،تولد است که در هر دوره یکبار اتفاق می افتد. محتویات دو کروموزومی که در فرآیند تولید شرکت می کنند با هم ترکیب میشوند تا 2 کروموزوم جدید که ما انها را فرزند می نامیم  ایجاد کنند.این هیوریستیک به ما اجازه می دهد تا 2 تا از بهترین ها را برای ایجاد یکی بهتر از آنها با هم ترکیب کنیم.(evolution) به علاوه در طول هر دوره،یک سری از کروموزوم ها ممکن است جهش یابند[6](Mutation) .

الگوریتم

    هر ورودی x در یک عدد برداری X=(x₁|x₂|..|x_n) قرار دارد .برای اجرای الگوریتم ژنتیک مان باید هر ورودی را به یک کروموزوم تبدیل کنیم.می توانیم این را با داشتن log(n) بیت برای هر عنصرو تبدیل ارزش Xi انجام دهیم مثل شکل زیر .

                       0111111                   ...                         1010111    1111011

 

 

 

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

 

 

 

 

[6]

   سود و کد :

 

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

[2]

 

[5]

روش های نمایش

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

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

    خاصیت هر 3تای این روشها این است که آنها تعریف سازنده ایی را که تغییرات تصادفی در آنها ایجاد می کنند را آسان می کنند:0را به 1 وبرعکس،اضافه یا کم کردن ارزش یک عدد یا تبدیل یک حرف به حرف دیگر.

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

 

روش های انتخاب

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

انتخاب 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 تبدیل شده .

تقاط قوت الگوریتم های ژنتیک

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

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

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

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

محدودیتهای GAها

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

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

چند نمونه از کاربرد های الگوریتم های ژنتیک

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

توپولوژی های شبکه های کامپیوتی توزیع شده.

بهینه سازی ساختار ملکولی شِمیایی (شیمی)

مهندسی برق برای ساخت آنتنهای Crooked-Wire Genetic Antenna

مهندسی نرم افزار

بازی های کامپیوتری

مهندسی مواد

مهندسی سیستم

رباتیک(Robotics)

تشخیص الگوو استخراج داده(Data mining)

حل مسئله فروشنده دوره گرد

آموزش شبکه های عصبی مصنوعی

یاددهی رفتار به رباتها با GA .

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

برای کسب اطلاعات بیشتر و کامل تر به مرجع شماره 3 مراجعه شود.
یک مثال ساده:

 ما یک مربع 3*3 داریم که می خواهیم اعدادی بین 1تا15 را در این مربع قرار دهیم به طوری که جمع

اعداد در هر سطرو ستون برابر 24 شود.

 

 

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

نسل اول

اولین گام ایجاد کردن یک نسل ابتدایی برای شروع کار است که شامل تعدادی ژنوم تصادفی است.این ژنوم ها به صورت باینری(0و1) نشان داده می شوند. حالا مثال مان:

اول یکسری عدد به صورت تصادفی تولید می شوند. هر ژنوم یا کروموزوم  شامل اطلاعاتی برای هر 9 جای خالی است .چون این اعداد مقادیر بین 0تا15 دارند می توان آنها را با 4 بیت یا ژن داده نمایش داد. پس هر ژنوم شامل 36 بیت است.

یک نمونه ژنوم می تواند به شکل زیر باشد:

Bits (Genes)    0110    1100    1111    1011    0100    1010    0111    0101   1110

Values(Traits)    6      12     15      11       4       10       7       5     14

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

 

 

          

مقادیر معادل عبارتند از 33و25و26و24و21و39.واضح است که این مقادیر مسئله را حل نمی کنند.پس باید مقادیر تناسب را برای این ژنوم محاسبه کرد.برای این کار ابتدا فاصله هرمجموع را از24 محاسبه کرده،سپس معکوس مجموع تفاصل آنها را محاسبه می کنیم .

بنابراین درجه تناسب برای این ژنوم تقریباً برابر 0.033 است.هرچقدر که اعداد ما به جواب نزدیکتر باشند عدد تناسب بزرگتر خواهد شد.اما اگر مخرج ما برابر 0شود چه اتفاقی می افتد؟ دراین صورت همه اعداد ما برابر 24 شده اند وما به جواب رسیده ایم.

نسل بعدی

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

انتخاب

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

بهترین روش برای تابع انتخاب(Fitness) در این مسئله روشی به نام رولت(Roulette) است.اول یک عدد تصادفی بین 0 وعدد تناسب نسل قبلی انتخاب می شود. تابع انتخاب به صورت زیر خواهد بود:

RouletteSelection()

{

    float ball  = rand_float_between(0.0| total_fitness);

    float slice = 0.0;

 

    for each genome in population

    {

        slice += genome. fitness;

   

        if ball < slice

            return genome;

    }

}

تغییر از یک نسل به نسل بعدی(Cross over)  

  حالا دو ژنوم بخشی از ژنهایشان را برای ایجاد نسل بعدی اهدا می کنند. اگر آنها تغییر پیدا نکنند همانطور بی تغییر به نسل بعدی منتقل خواهند شد.درجه Crossover نشان دهنده این است که هر چند وقت یکبار ژنوم ها تغییر پیدا خواهند کرد و این عدد باید در حدود 65-85% باشد.

عملگر تغییر در ژنوم های باینری مثال ما با انتخاب یک مکان تصادفی در ژنوم برای تغییر آغاز می شود. بخش اول ژنهای پدر و بخش دوم ژنهای مادر با هم ترکیب می شوند(و بالعکس) تا2 فرزند تولید شوند. در زیریک عمل تغییر را می بینیم.

Before Crossing

Father 011110010011 001011011000111011010000

Mother 010100111110 010101111101000100010010

After Crossing

Child1 011110010011 010101111101000100010010

Child2 010100111110 001011011000111011010000

جهش(Mutation)

قبل از این که ژنوم ها در نسل بعدی قرار بگیرند،احتمال دارد دچار جهش یا تغییر ناگهانی شوند شوند.جهش یک تغییر ناگهانی در ژن است.در ژنهای باینری این تغییر به معنای تغییر یک بیت از 0به 1 یا از 1 به 0 است. درجه جهش نشان دهنده احتمال بروز جهش در یک ژن است و تغریباً بین 1-5% برای ژنهای باینری و 5-20%برای ژنهای عددی است.

 نمونه برنامه این مسئله به زبان C++ همراه این تحقیق آورده شده است.[4]

هایپر هیوریستیک

 

      مثال های بسیاری وجود دارد که برای حل ان ها از الگوریتم ژنتیک استفاده شده است از جمله Traveling salesman& bin packing&scheduling   .مسئله ی جدول زمانی پرسنل وکارکنان با استفاده از الگوریتم ژنتیک به صورت موفقیت امیزی حل شده است .aickelin& dowslamd از الگوریتم ژنتیک لیست کار پرستاران در یکی از بیمارستان های بزرگ انگلستان به کا ر برده شد eston & mansour از الگوریتم ژنتیک برای حل مسئله ی جدول زمان بندی کار استفاده کردند .در واقع برای حل این مسئله از الگوریم ژنتیک توزیع شده که به صورت موازی روی شبکه ی محل کار وجود داشت دست یافتند.آنچه از این تحقیق بدست آمد سه دسته ی متفاوت زمان بندی برای مجموعه ای از کارهای متفاوت بود. این محققین مسائلی را که با هیوریستیک و متا هیوریستیک کار میکرند با هم مقایسه کردند و نتیجه ان بود که الگوریتم ژنتیک بهتر از همه ی آنها کار می کرد در نتیجه الگوریتم های ژنتیک با کروموزوم های مستقیم و کروموزوم های غیر مستقیم به صورت گسترده ای مورد مطالعه قرار گرفت . به عنوان مثال hart & ross& nelson از الگوریتم ژنتیک با کروموزوم های مستقیم برای حل مسئله ی زمان بندی امتحانات طراحی شد. انه استراتژی های به عنوان پارامتر در ده خانه ای ارایه ایجاد کردند. بنابراین کروموزوم ها ساختار جدول زمان بندی را ایجاد می کنند نه خود جدول زمان بندی. کروموزوم های غیر مستقیم برای رفع محدودیت های کروموزوم های مستقیم مورد استفاده قرار می گیرند. که این محدودیت همان شکست هماهنگ بین قسمت های مختلف حل مسئله وجود داشت.

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

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

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

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

 

[1] مجله علم و کامپیوتر www.ccwmagazine.com

[2]   www.wikipedia.com

 [3]  www.talkorigins.org

 [4]   www.gpwiki.org

[5] پاورپوینت Koza 

www.smi.stanford.edu/people/koza

[6]  دانشکده کامپیوتر دانشگاه McGill کانادا

 www.cgm.cs.mcgill.ca   

 [7]www.sharifthinktank.com 

[8] www.itna.com

  Guided operators for a hipper-heuristic Genetic Algorithm [9]

www.cs.nott.ac.ukIT university of Nottingham

 

 

 

 

 

 

تجمیع شناسنامه کامپیوتر جمع آوری خودکار فروش کاشی مساجد ایجاد شناسنامه تجهیزات کاشی مسجدی هلپ دسک سازمانی هلپ دسک IT Help Desk کاشی سنتی ایرانی مدیریت تجهیزات IT مدیریت تجهیزات آی تی کارتابل درخواست ها کارتابل درخواست های IT جمع آوری خودکار نرم افزارها جمع آوری سیستم های شرکت جمع آوری سیستم های سازمان تجمیع اطلاعات تجمیع اطلاعات IT تجمیع کامپیوترها مدیریت IT سیستم جمع آوری شناسنامه کامپیوتر سیستم مدیریت کلان IT سیستم مدیریت فنآوری اطلاعات ابزار مدیران IT ابزار مدیران فنآوری اطلاعات سامانه تجمیع خودکار شناسنامه جمع آوری سیستم کامپیوتر