453 صفحه
مقدمه ای بر الگوریتم ژنتیک
Introduction to Genetic Algorithms, Springer, 2008
Chapters
Evolutionary Computing
Genetic Algorithms
Terminologies and operators of genetic algorithm
Advanced operators and techniques in genetic algorithm
Classification of genetic algorithm
Genetic programming
Genetic algorithm optimization problems
Genetic algorithm implementation using MATLAB
++Genetic algorithm optimization in C/C
Applications of genetic algorithms
Introduction to particle swarm optimization and ant colony optimization
فرمت فایل : word(قابل ویرایش)
تعداد صفحات:19
فهرست مطالب:
چکیده موضوع ………………………………………………………………………
مقدمه……………………………………………………
الگوریتم ژنتیک چیست؟…………………………………… ……………………………………
ایده اصلی …………………………………………………………………………………
الگوریتم ژنتیک ……………………………………………………………………….
سود و کد الگوریتم………………………………………………………..
روش های نمایش ………………………………………………………….
روش های انتخاب ………………………………………………………..
روش های تغییر ……………………………………………………………..
نقاط قوت الگوریتم های ژنتیک... ……………………………………
نقاط ضعف الگوریتم های ژنتیک. ……………………………………
نمونه هایی از کاربردهای الگوریتم های ژنتیک در دنیای امروز……………………………………..
یک مثال ساده با جزئیات …………………………………….
هایپر هیوریستیک ...................
منابع
چکیده:
الگوریتم های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش بینی یا تطبیق الگو استفاده می کنند.الگوریتم های ژنتیک اغلب گزینه خوبی برای تکنیک های پیش بینی بر مبنای رگرسیون هستند.همان طور ساده،خطی وپارامتری یک گفته می شود،به الگوریتم های ژنتیک می توان غیر پارامتریک گفت.
مختصراً گفته می شود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل نمسئله استفاده می کند.مسئله ای که باید حل شود ورودی است و راه حلها طبق یک الگو کد گذاری می شودومتریک که تابع fitness هم نام دارد هر راه حل کاندید را ارزیابی می کندکه اکثر آنها به صورت تصادفی انتخاب می شوند.
کلاً این الگوریتم ها از بخش های زیر تشکیل می شوند :
تابع برازش - نمایش – انتخاب – تغییر
که در ادامه آنها را توضیح خواهیم داد.
مقدمه
هنگامی که لغت تنازع بقا به کار میرود اغلب بار ارزشی منفی آن به ذهن میآید. شاید همزمان قانون جنگل به ذهن برسد و حکم بقای قویتر!
البته برای آنکه خیالتان راحت شود میتوانید فکر کنید که همیشه هم قویترینها برنده نبودهاند. مثلا دایناسورها با وجود جثه عظیم و قویتر بودن در طی روندی کاملا طبیعی بازی بقا و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیفتر از آنها حیات خویش را ادامه دادند. ظاهرا طبیعت بهترینها را تنها بر اساس هیکل انتخاب نمیکند! در واقع درستتر آنست که بگوییم طبیعت مناسب ترینها (Fittest) را انتخاب میکند نه بهترینها.
قانون انتخاب طبیعی بدین صورت است که تنها گونههایی از یک جمعیت ادامه نسل میدهند که بهترین خصوصیات را داشته باشند و آنهایی که این خصوصیات را نداشته باشند به تدریج و در طی زمان از بین میروند.
مثلا فرض کنید گونه خاصی از افراد، هوش بسیار بیشتری از بقیه افراد یک جامعه یا کولونی دارند. در شرایط کاملا طبیعی این افراد پیشرفت بهتری خواهند کرد و رفاه نسبتا بالاتری خواهند داشت و این رفاه خود باعث طول عمر بیشتر و باروری بهتر خواهد بود(توجه کنید شرایط طبیعیست نه در یک جامعه سطح بالا با ملاحظات امروزی یعنی طول عمر بیشتر در این جامعه نمونه با زاد و ولد بیشتر همراه است). حال اگر این خصوصیت(هوش)ارثی باشد به طبع در نسل بعدی همان جامعه تعداد افراد باهوش به دلیل زاد و ولد بیشتر اینگونه افراد بیشتر خواهد بود. اگر همین روند را ادامه دهید خواهید دید که در طی نسلهای متوالی دائما جامعه نمونه ما باهوش و باهوشتر میشود. بدین ترتیب یک مکانیزم ساده طبیعی توانسته است در طی چند نسل عملا افراد کم هوش را از جامعه حذف کند علاوه بر اینکه میزان هوش متوسط جامعه نیز دائما در حال افزایش است(البته امکان داشت اگر داروین بیعرضگی افراد باهوش امروزی را میدید کمی در تئوری خود تجدید نظر میکرد اما این مسئله دیگریست!).
بدین ترتیب میتوان دید که طبیعت با بهرهگیری از یک روش بسیار ساده(حذف تدریجی گونههای نامناسب و در عین حال تکثیر بالاتر گونههای بهینه) توانسته است دائما هر نسل را از لحاظ خصوصیات مختلف ارتقا بخشد.
البته آنچه در بالا ذکر شد به تنهایی توصیف کننده آنچه واقعا در قالب تکامل در طبیعت اتفاق میافتد نیست. بهینهسازی و تکامل تدریجی به خودی خود نمیتواند طبیعت را در دسترسی به بهترین نمونهها یاری دهد. اجازه دهید تا این مساله را با یک مثال شرح دهیم.
پس از اختراع اتومبیل به تدریج و در طی سالها اتومبیلهای بهتری با سرعتهای بالاتر و قابلیتهای بیشتر نسبت به نمونههای اولیه تولید شدند. طبیعیست که این نمونههای متاخر حاصل تلاش مهندسان طراح جهت بهینهسازی طراحیهای قبلی بوده اند. اما دقت کنید که بهینهسازی یک اتومبیل تنها یک "اتومبیل بهتر" را نتیجه میدهد.
اما آیا میتوان گفت اختراع هواپیما نتیجه همین تلاش بوده است؟ یا فرضا میتوان گفت فضا پیماها حاصل بهینهسازی طرح اولیه هواپیماها بودهاند؟
پاسخ اینست که گرچه اختراع هواپیما قطعا تحت تاثیر دستاورهای صنعت اتومبیل بوده است اما بههیچ وجه نمیتوان گفت که هواپیما صرفا حاصل بهینهسازی اتومبیل و یا فضا پیما حاصل بهینهسازی هواپیماست. در طبیعت هم عینا همین روند حکمفرماست. گونههای متکاملتری وجود دارند که نمیتوان گفت صرفا حاصل تکامل تدریجی گونه قبلی هستند.
در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مساله یاری کند مفهومیست به نام : تصادف یا جهش.
به عبارتی طرح هواپیما نسبت به طرح اتومبیل یک جهش بود و نه یک حرکت تدریجی. در طبیعت نیز به همین گونهاست. در هر نسل جدید بعضی از خصوصیات به صورتی کاملا تصادفی تغییر مییابند سپس بر اثر تکامل تدریجی که پیشتر توضیح دادیم در صورتی که این خصوصیت تصادفی شرایط طبیعت را ارضا کند حفظ میشود در غیر اینصورت به شکل اتوماتیک از چرخه طبیعت حذف میگردد.
در واقع میتوان تکامل طبیعی را به اینصورت خلاصه کرد: جستوجوی کورکورانه(تصادف یا Blind Search)+ بقای قویتر.
حال ببینیم که رابطه تکامل طبیعی با روشهای هوش مصنوعی چیست .هدف اصلی روشهای هوشمند به کار گرفته شده در هوش مصنوعی یافتن پاسخ بهینه مسائل مهندسی ست. بعنوان مثال اینکه چگونه یک موتور را طراحی کنیم تا بهترین بازدهی را داشته باشد یا چگونه بازوهای یک ربات را محرک کنیم تا کوتاهترین مسیر را تا مقصد طی کند(دقت کنید که در صورت وجود مانع یافتن کوتاهترین مسیر دیگر به سادگی کشیدن یک خط راست بین مبدا و مقصد نیست) همگی مسائل بهینهسازی هستند.
روشهای کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روشها نقطه بهینه محلی(Local Optima) را بعنوان نقطه بهینه کلی در نظر میگیرند و نیز هر یک از این روشها تنها برای مساله خاصی کاربرد دارند. این دو نکته را با مثالهای سادهای روشن میکنیم.
فرمت فایل : word(قابل ویرایش)
تعداد صفحات:32 صفحه ,19 اسلاید
فهرست مطالب:
چکیده.................................................................................................................4
مقدمه..................................................................................................................5
فصل اول
1-1)الگوریتم ژنتیک چیست؟...................................................................................9
2-1)ایده اصلی....................................................................................................13
3-1)الگوریتم .....................................................................................................15
3-1-1)روش های نمایش ......................................................................................17
3-1-2)روش های انتخاب .....................................................................................18
3-1-3)روش های تغییر .......................................................................................19
فصل دوم
1-2)نقاط قوت الگوریتم های ژنتیک.........................................................................21
2-2)محدودیتهای الگوریتم ژنتیک............................................................................22
3-2)کاربردهای الگوریتم های ژنتیک.......................................................................24
4-2)یک مثال ساده...............................................................................................25
نتیجه گیری........................................................................................................31
منابع................................................................................................................32
چکیده:
الگوریتم های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش بینی یا تطبیق الگو استفاده می کنند.الگوریتم های ژنتیک اغلب گزینه خوبی برای تکنیک های پیش بینی بر مبنای رگرسیون هستند.همان طور ساده،خطی وپارامتری یک گفته می شود،به الگوریتم های ژنتیک می توان غیر پارامتریک گفت.
مختصراً گفته می شود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل نمسئله استفاده می کند.مسئله ای که باید حل شود ورودی است و راه حلها طبق یک الگو کد گذاری می شودومتریک که تابع fitness هم نام دارد هر راه حل کاندید را ارزیابی می کندکه اکثر آنها به صورت تصادفی انتخاب می شوند.
کلاً این الگوریتم ها از بخش های زیر تشکیل می شوند :
تابع برازش - نمایش – انتخاب – تغییر
که در ادامه آنها را توضیح خواهیم داد.