گوگل پلاس انجمن مکاریتم پایان نامه وبلاگ الگوریتم ژنتیک مزایا و معایب
  • کارشناس مهندسی
  • 6819 بازدید
  • 1 نظر
  • آموزش

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

تاریخچه ی الگوریتم

پیشینه الگوریتم ژنتیک به سال های حدود 1960 برمی گردد. در دهه های 50 و 60، تحقیقات متعددی برای استفاده از نظریه تکامل در بهینه سازی مسائل مهندسی به طور مستقل صورت گرفت. ایده اصلی در همه این سیستم ها، رشد یک جمعیت از پاسخ های اولیه یک مساله به سمت پاسخ بهینه با الهام گیری از عملگرهای انتخاب و تغییر ژنتیک طبیعی بود. در سال های 1965 تا 1973 رکنبرگ[1] کتاب خود را به نام  " تکنیک های تکامل" در زمینه محاسبات تکاملی منتشر کرد و در سال های بعد نظریه او توسط محققین دیگر توسعه یافت. الگوریتم ژنتیک نخستین بار توسط  جان هلند[2]مطرح و به وسیله خود او و دانشجویان و همکارانش گسترش یافت. تلاش های او و اطرافیانش در این زمینه در نهایت به نشر کتاب سازگاری در طبیعت و سیستم های مصنوعی[3] انجامید. پس از آن تحقیقات گسترده ای توسط افراد مختلف در این زمینه انجام شد به عنوان مثال در سال 1992 جان کزا[4] الگوریتم ژنتیک را به صورت عملیاتی در برنامه نویسی به کار برد و برنامه نویسی ژنتیک را به عنوان روش خود مطرح ساخت و الگوریتم ژنتیک به صورت امروزی خود رسید.

اصطلاحات زیستی

در راستای فهم کامل الگوریتم ژنتیک، ابتدا بهتر است با برخی از اصطلاحات زیستی به کار رفته در تئوری این الگوریتم آشنا شویم. همه موجودات زنده از واحدهای کوچکی به نام سلول تشکیل شده اند. هر سلول نیز به نوبه خود از مجموعه ای از یک یا چند کروموزوم[5] تشکیل شده است. کروموزوم ها رشته هایی از مولکول DNA می باشند که در حقیقت برنامه کاری موجود زنده را در خود ذخیره می کنند. هر کروموزوم شامل چندین ژن[6] می باشد، که هر ژن بلوکی از مولکول DNA می باشد که پروتئین خاصی را کدگذاری می کند. به طور کلی می توان گفت که هر ژن یک خصیصه[7] از موجود زنده (مانند رنگ چشم) را کد گذاری می کند. حالت های ممکن برای یک خصیصه را حالت[8] می گویند. هر ژن موقعیت مخصوص خود را در کروموزوم دارد که به آن موقعیت[9] می گویند. بسیاری از موجودات زنده در هر سلول چندین کروموزوم دارند. مجموعه کامل مواد ژنتیکی در سلول (مجموعه همه کروموزوم ها) (genome) نامیده می شوند. اصطلاح (genotype) به مجموعه خاصی از کروموزوم های موجود در genome اطلاق می شود. Genotype ها در پی تحولات و تغییر، به phenotypeها- خصوصیات فیزیکی و ذهنی موجود زنده (مانند رنگ چشم، بلندی، اندازه مغز و یا میزان هوش)- تبدیل می شوند.


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


در طی تولید مثل جنسی[10]، در اثر الحاق[11] ژن ها از کروموزوم های والدین[12] با یکدیگر ترکیب شده تا کروموزوم کامل جدیدی را تشکیل دهند. در طی این تغییرات، ممکن است تغییرات کوچکی در برخی از بخش های DNA  ژن های فرزند، بوجود آمده و فرزند دچار جهش[13]  گردد. در نهایت تناسب[14] یک موجود زنده با توجه به احتمال زیستن آن برای تکثیر(زیست پذیری[15]) یا برحسب تابعی از تعداد فرزندان آن گونه (باروری[16]) تعیین می گردد.


معرفی الگوریتم

 

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


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


در الگوریتم ژنتیک هر کروموزوم نشان دهنده پاسخی از مساله مورد نظر می باشد. این پاسخ بسته به نوع کدسازی مساله مورد نظر که  با توجه به خصوصیات مساله تعیین می شود، می تواند به صورت ماتریسی  از اعداد حقیقی (کدسازی حقیقی)، یک رشته از بیت های 0و1 ای (کدسازی باینری) و ... مطرح شود. بنابراین هر کدام از "ژن ها" که اجزاء کروموزوم ها می باشند، می توانند نشانگر یک عدد حقیقی، یک بیت و ... باشند. در مورد روش های معمول در کدسازی، در قسمت های بعد بحث خواهیم کرد.

ساز و کار الگوریتم

اصول كار الگوريتم ژنتيك به صورت روند زير ارائه مي گردد:

گام 1 – كد گذاري

گام 2 – انتخاب تصادفي جمعيت اوليه از مجموعه پاسخ ها

گام 3 – محاسبه ميزان سازگاري گروه پاسخ با تابع هدف ( Fitness )

گام 4 – ايجاد جمعيت جديد با استفاده از عملگر هاي ژنتيك (تكثير تركيب و جهش)

گام 5 – تكرار مراحل سوم و چهارم تا هنگامي كه جواب نهايي همگرا گردد

 

مرحله 1 : كد گذاري

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

·       کدگذاری باینری

·       کدگذاری جایگشتی

·       کدگذاری مقداری

·       کدگذاری درختی

 

مرحله 2 : انتخاب تصادفي جمعيت اوليه از مجموعه پاسخ ها

در اين مرحله موتور الگوريتم ژنتيک يک جمعيت اوليه از مجموعه پاسخ ها ايجاد مي کند. اين انتخاب مي تواند به يكي از اين روشها انجام شود :

·       انتخاب تصادفي از بين مجموعه جواب هاي ممكن

·       انتخاب از بين يك جمعيت قبلي نگهداري شده

·       يك مجموعه از راه حل ارائه شده توسط فرد خبره

·       يك مجموعه راه حل ارائه شده توسط يك الگوريتم خلاق ديگر

مرحله 3 : محاسبه ميزان سازگاري گروه پاسخ با تابع هدف ( برازش يا  Fitness )

هر فرد از گروه در برابر مجموعه اي از داده ها ي مورد آزمايش قرار مي گيرد و مناسبترين آنها شايد 10 درصد از مناسبترين ها باقي مي مانند.بقيه کنار گذاشته مي شوند.

راه حل خوب ، به خوب بودن تابع ارزيابي بستگي دارد ( معمولاً سخت ترين قسمت است) عملگر ارزيابي يك كروموزوم را رمزگشايي مي كند و يك مقدار برازندگي به آن نسبت مي دهد . الگوريتم ورودي هايي که به جواب بهينه نزديک ترند را نگه داشته و از بقيه صرف نظر مي کند.

مرحله 4 : ايجاد جمعيت جديد با استفاده از عملگر هاي ژنتيك (تكثير تركيب و جهش)

وقتي با روش هاي انتخاب کروموزوم ها انتخاب شدند، بايد به طور تصادفي براي افزايش تناسبشان اصلاح شوند. 2 راه حل اساسي براي اين کار وجود دارد :

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

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

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


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


 

گام مهم ديگر درالگوريتم ، تولد است که در هر دوره يکبار اتفاق مي افتد. محتويات دو کروموزومي که در فرآيند توليد شرکت مي کنند با هم ترکيب ميشوند تا 2 کروموزوم جديد که ما آنها را فرزند مي ناميم  ايجاد کنند.

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

·       
گلچین (Elite)
آموزش الگوریتم ژنتیک - Elite


در این عمل یک یا چند فرد نخبه (elite) از جمعیت فعلی به طور مستقیم به نسل بعدی منتقل می شوند

 

 

مرحله 5 : تكرار مراحل دوم تا چهارم تا هنگامي كه جواب نهايي همگرا گردد

معيارهاي زير به‌عنوان معيار توقف در الگوريتم ژنتيك شمرده مي‌شوند :

·       زمان اجراي الگوريتم

·       تعداد نسلهايي که ايجاد مي‌شوند

·       يک راه حل راضي کننده بدست آمده باشد.

·       بعد از انجام تعداد معين توليد نسل هيچ پيشرفتي در کيفيت راه حلها بوجود نيايد (همگرايي معيار خطا )

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

·       ترکيبي از معيارهاي بالا.

 

طرح کلی الگوریتم

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

در زیر چند نمونه از اصلی ترین نمونه های این طرح را می بینمیم:


 
برتری و ضعف های الگوریتم ژنتیک نسبت به دیگر الگوریتم ها


برتری ها و ضعف های الگوریتم

 

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

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

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

·       این روش برای بهینه سازی مسائلی که با کمیت های گسسته سر و کار دارد بسیار مناسب است.

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

 

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

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

·       اگر تابع هدف مساله، تابع خوش رفتار و نسبتا یکنواختی باشد، روش هایی مانند CG(Conjugate Gradiant) گزینه بهتری می باشند.

·       در مواردی که رفتار تابع fitness به طور کلی مشخص است، می توان روش های مناسب تری برای بهینه کردن مساله طراحی کرد.

·       يک مشکل چگونگي نوشتن عملگر fitness است که منجر به بهترين راه حل براي مسئله شود.اگر اين کارکرد برازش به خوبي و قوي انتخاب نشود ممکن است باعث شود که راه حلي براي مسئله پيدا نکنيم يا مسئله اي ديگر را به اشتباه حل کنيم.

 

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

 

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

·       توپولوژي هاي شبکه هاي کامپيوتري توزيع شده

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

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

·       مهندسي نرم افزار

·       بازي هاي کامپيوتري

·       مهندسي مواد

·       مهندسي سيستم

·       رباتيک (Robotics)

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

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

·       ياددهي رفتار به رباتها با GA

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

·       درك زبان محاوره اي و يا خواندن متون

انجام پایان نامه با الگوریتم ژنتیک

می خواهید بدانید معیارهای مطمئن ترین و بهترین موسسه انجام پایان نامه ارشد چیست؟ کلیک نمائید

نظرات کاربران
  1. avatar
    جمعه 11 دی 1394 پاسخ

    خوب است

نظر خود را درباره این مطلب ارسال کنید
 
 
 
 





فیسبوک موسسه انجام پایان نامه مکاریتم View Association of Mecharithm's LinkedIn profile لینکدین موسسه انجام پایان نامه مکاریتم View Mecharithm Associatoion's LinkedIn profile موسسه انجام پایان نامه و رساله دکتری Instagram Instagram