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

مشخص نشده
مشخص نشده
19
مشخص نشده
216 KB
25555
قیمت قدیم:۶,۰۰۰ تومان
قیمت: ۵,۰۰۰ تومان
دانلود مقاله
  • خلاصه
  • فهرست و منابع
  • خلاصه تحقیق مقاله الگوریتم های ژنتیک

         چکیده 

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

         مختصراً گفته می شود که الگوریتم ژنتیک (یا 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]

  • فهرست و منابع تحقیق مقاله الگوریتم های ژنتیک

    فهرست:

    چکیده موضوع ………………………………………………………………………

    مقدمه……………………………………………………

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

    ایده اصلی …………………………………………………………………………………

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

    سود و کد الگوریتم………………………………………………………..

    روش های نمایش ………………………………………………………….

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

    روش های تغییر ……………………………………………………………..

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

    نقاط ضعف الگوریتم های ژنتیک. ……………………………………

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

    یک مثال ساده با جزئیات …………………………………….

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

    منبع:

    ] مجله علم و کامپیوتر 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

کلمات کلیدی:  N/A
تحقیق در مورد تحقیق مقاله الگوریتم های ژنتیک, مقاله در مورد تحقیق مقاله الگوریتم های ژنتیک, تحقیق دانشجویی در مورد تحقیق مقاله الگوریتم های ژنتیک, مقاله دانشجویی در مورد تحقیق مقاله الگوریتم های ژنتیک, تحقیق درباره تحقیق مقاله الگوریتم های ژنتیک, مقاله درباره تحقیق مقاله الگوریتم های ژنتیک, تحقیقات دانش آموزی در مورد تحقیق مقاله الگوریتم های ژنتیک, مقالات دانش آموزی در مورد تحقیق مقاله الگوریتم های ژنتیک

دریافت لینک دانلود به صورت خودکار بلافاصله پس از پرداخت

امکان پرداخت آنلاین از طریق کلیه کارت های عضو شتاب

ثبت سفارش
تعداد
عنوان محصول