صفحه 1:
OD.
sore
عنوان:
استفاده از الگوریتم های
تکاملی برای حل مسئله
(اوزير
استاد راهنما:
استاد مهناز ميرزايى
تنهيه شده توسط:
الهه جوادى
صفحه 2:
الگوریتم تکاملی دراستخراج ترکیب
الگوریتم تکاملی درانتخاب ترکیب
الگوریتم تکاملی درطبقه بندی
سامانه های مبتنی بر قانون
درخت تصمیم گیری و الگوریتم های تکاملی
الگوریتم های تکاملی در دسته بندی
الگوریتمهای ژنتیک
انتخاب طبیعی
مقايسة الگوریتم ژنتیک با سیستمهای طبیعی
صفحه 3:
۲ ۲ ۰ تاملی عبارت است از سامانههای حل مساله ای که مدل های
محاسباتی فرایندهای حل مساله را به عنوان عنصر اصلی در طراحی و اجرا
به کار میبرند . تعدادی از مدل های محاسباتی تکاملی توسعه یافته عبارتند
از : الگوریتمهای LLG الگوریتم های ژنتیک . برنامه ریزی تکاملی
استراتزی تکامل ۰ وحیات مصنوعی
صفحه 4:
الگوریتم تکاملی(0)0)الگوریتمی است که جنبه های انتخاب طبیعی و تداوم
هماهنگی را ترکیب می کند. الگوریتم تکاملی از جمعیت ساختارهای
قوانین انتخاب ترکیب بندی مجدد. تغییر و بقاء حفاظت می کند.
این ساختارها مبتنی بر اپراتورهای ژنتیکی هستند .در این روش,محیط
خود تعیینکننده هماهنگی یا عملکرد هر یک از افراد جمعیت است و ازافراد
هماهنگ تر مى .
صفحه 5:
۴ تعریف افراد
* ارزیابی ( تابعهاهنگی تابع )
* انتخاب جمعیت
* مکانیزم انتخاب والد
* اپراتورهای متفیر» ترکیب مجدد و جهش
؟ ساز و کار انتخاب بازمانده (جانشینی)
هر کدام از این اجزا باید با توجه به یک الگوریتم تکاملی تعیین شوند.
صفحه 6:
راهبرد تکامل که برای اولین بار توسط اینگو ریچن برگ و هانس - پاتول
شوقول در سال ۱۹۶۳در دانشگاه بر لین اراكه شد.الگوریتمی است که افرآد
(راه حل های بالقوه) با توجه بهمجموعه ای از متغیرهای مشاهده ای با ارزش
واقعی کد گزاری ميشوند. برای هر متغیر هدف . هر فرد راهبردی متغیر دارد
که این راهبردها درجه تغییر متفیرهای مربوطراتعیین می کنند. متفیرهای
Gopal, با توجه به نرخ تغییر متفیرهای هدف خود. تغفییر میکنند .ویژگی های
یک راهیرد تکامل یه وسیله اندازه جمعیتو می تعداد زاد و ولد در هر مرحله
تست سود
صفحه 7:
فرایند استخراج ترکیب داده که مربوط بهمسأله است در داده کاوی امری
است بسیار مشکل و وابسته به داده در بعضی از انواعداده» ترکیب به آساتی
قابل تشخیصاست . از جمله در داد مربوط به متن که داده همان متن
کلمات هستند. اما زمانیکه بعضی از انواع داده توجه خود راصرفا معطوف به
استخراج میکنند این وظیفه دشوار خواهدبود .به ویثه در جایی که
استخراج ترکیب داده بیش از اندازه چالش برانگیز باشد. درگذشته دادة
تصوير تنها محدود به رشته هایی مانند ستاره شناسی بود . با این حال
امروزه این نوع داده درزمینههای مختلفیبه کار میرود. مانند تصویربرداری
پزشکی . تصاویر چند رسانه در شبکه و تصویر های ویدیوئی.
صفحه 8:
معمولا به دنبال استخراج داده. مجموعه ای از ترکیبات نیزتعیین میشوند . در
بسیاری از موقعیت ها شناخت اولویت مربوط بودن شکل استخراج شده
از داده بهمسأله.امری دشواراست.ترکیبهای نامربوط نه تنها پیچیدگی زمانی
الگوریتم ها را زیاد میکنند . زمان مورد نیاز استخراج خود ترکیب را نیز
افزایش می دهند.اغلب روش تکاملی به کار رفته برای انتخاب
ترکیبها توسط الگوریتم یادگیری صورت میگیرد. در اين روشهنگام ارزیابی
الگوریتم یادگیری با توجه به محاسبات الگوریتمی» زبرمجموعه
و اهتگی ترکیب ها نیز می بدست آید.
صفحه 9:
آلکوریتمهای تکاملی با الگوریتم های طبقه بندی مانند سامانه های eee
و وی ر درخت تصمیم گیری ارتباط مستفیم دارند.
صفحه 10:
سامانه های مبتنی بر قانون
در یادگیری ماشینی مفاهیمی مانند مجموعه قوانین بسیار متداول است .زیرا
در مان سایر روش هاء قوانین به سادگی ارائه می شوند و انسان نیز می
توائد به آسانى آنها را تفسیر کند.در الگوریتم های تکاملی دو شیوه اصلی برای
ارائه مجموعه های قوانین وجود دارد «میشیگان در روش هر فرد جمعیت
ارائه کننده قانونی ثابت است و جمعیت کل . دربردارنده مفهوم هدفاست.
حلقه اصلی در یک سامانه طبقه بندی .سامانه ای است که با ورودیهایی از
محیط آغاز به کار میکند و خروجیها به صورت پیام پیام هایی به ليست
هاى قبلیاضافه و شروع به می کار کنند و قوی ترین قانون هماهنگ با پیام ها
cle می شود.سامانه های طبقه بندی در جایی که دانش کافی یا
تخصصی برای کنترل مرسوم جود نداشته باشد به مثابه سامانه های
pees رای محیط های نا امن استفاده میشوئد
صفحه 11:
درخت تصمیم گیری روشی مرسوم در طبقه بندی است . زیرا به آسانی
توسط چندین گره. می ساخته شود و متخصصان به راحتی می توانند آنها
را تفسیر کنند .گرههای داخلی بیانگرآزمون هایی بر اساس ت رکیبهاهستند
eae 0 داده میپردازند. گره هایبرگ ها بیانگر عنوان مایقه ها ۰ ۲
مسیر گره ريشه به یکی از برگها بیانگر پیوستگی آزمون ها است.
صفحه 12:
در این رابطه می توان بین دو روش اصلی استفاده از الگوریتم های تکاملی در
مسائل دسته بندی وجه تمایز قایل شد . در روش Sal هر موقعیت در
کروموزوم ها .آیتمی را در مجموعه آموزش ارائه میکند .اگر شماره دسته ها
(66)اولویت در نظر گرفته شوند هر موقعیت در کروموزوم ها . می تواند
ارزشی به صورت [1,1)]داشته باشد.این روش مشابه کد گذاری مستقیم
شبکه های طبیعی است . این روش در اجرا ساده است زیرا نیازی به اپراتور
تکاملی با تخصص ویژه نیست اما مشکلاتی نیز وجود دارد .از جمله این که
اندازه افراد دقیقا اندازه مجموعه آموزش است و برای م شکلات بزرگ این
تاربردی نیست.
صفحه 13:
معرفی الگوریتمهای ژنتیک
۳ هاى (نتيك مذلى از يادكيرى ماشين است كه نحوه رفتار آنا
تمثيلى از فرآيندهاى تكاملى موجود در عالم طبيعت است.
الكوريتمهاى زنتيك يكى از قويترين روشهاى بركرفته ازطبيعت است كه با
الهام از ژنتیک وانتخاب طبیعی, یکی از بهترين اشكال بهينه سازى عددى
در مسائل علوم و مهندسی را ارائه میکند.با جستجوی تصادفی و البته
هوشمندانه مناسب ترین رشتهها از میان اطلاعات کد شده بدست خواهد
آمد.
صفحه 14:
عمل حذف در شرایط طبیعی باعث نابودی افرادی که سازگاری کمتری با
محیط دارند میشود؛ به عبارت سادهتر نتيجه مبارزه بین جانداران باقى ماندن
افراد سازگارتر میباشد. داروین معتقد بود که رقابت در میان افراد گونه های
مختلف صورت گرفته و تنها آن عده که دارای صفات ممتازتری هستند قادر به
ادامه زندگی خواهند بود و افرادی که نسبت به شرایط محیطی سازش ندارند از
بین میروند. از این رو انتخاب طبیعی صورت گرفته و صفات نامطلوب افراد
نامناسب به واسطه عدم امکان تولید مثل از بین میرود. این عمل در نسلهای
متمادی صورت پذیرفته که نتيجة آن پیدایش نسلهایی است که قادرند خود را
بهتر با محیط زندگی هماهنگ سازند.
صفحه 15:
مقایسة الگوریتم ژنتیک با سیستمهای طبیعی \
کروموزوم بسته های ژنی پاسخ های ممکن مسئله به
هستند که اطلاعات ورائتی را از صورت رشته های عددی
نسلى به نسل ديكر SULT Lae رمزگذاری شده است.
تابع برازش (۴1۲۳۴655)
محيط مساله به صورت يك ابطة ریاضی درآمده
شرایط محیطی را که جمعیت در آن قرار درد صرح ا
ce on
اهر رشتة جبعيت رايه عنوان متغير تابع
برازش در نظركرفته و مقدار تابع برازش
هر رشته محاسبه میشود. متناسب با
جمعیت
تقاطع (Crossover) تقاطع
La فقس ۱ رشته هاى جمعيت به صورت دو به دو
در نتيجه تقاطع يا تبادل قسمتى از 9
كروموزومها مبادله زنهاى بيوسته صورت مزدوج ميشوند. زوج رشتهها از يك نقعله
ميكيرد.
د. نیم بخشهای بین دو رشته
تعویض میشوند.
صفحه 16:
همانطور که قبلاً هم اشاره شد. الگوریتمهای ژنتیک, تکنیکهای جستجو بر
٩ سم تسل شناسی طبیعی و انتحاب طبیعی ی نم ۱
ژنتیک از مقایسه بین نمایش یک ساختار پیچیده با کمک یک برداراز مولفه
ها ازايدة ساختار ژنتیکی یک کروموزوم سرچشمه میگیرد.ئدر مورد ساختار
کلی الگوریتم ژنتیک قبل از هر چیز باید مکانیسمی برای نمایش هر جواب
مساله به صورت یک کروموزوم تعریف نمود. سپس مجموعهای از کروموزومها
را که در حقیقت بیانگر یک مجموعه ازجوابهای مساله هستند به عنوان
جمعیت اولیه در نظر گرفت. اندازه جمعیت ادلخواه بوده و توسط کاربر
تعیین ميشود. بعد از این مرحله باید با بکارگیری اعمال ژنتیک اقدام به تولید
کروموزومهای جدید. موسوم به نوزادنمود. پس از تولید تعدادی کروموزوم
جدید بايد به انتخاب برازنده ترین کروموزومها پرداخت به طوری که تعداد
کروموزومهای منتخب برابر با اندازه جمعیت اولیه باشد. فرایند انتخاب مبتنی
بر مقدار برازندگی هر رشته بوده که اغلب تابع برازش را برابر با همان تابع
هدف مساله بهینه سازی در نظر میگیرند . تاکنون یک تکرار یا یک نسل از
الگوریتم طی شده است. الگوریتم بعد از طى جندين نسل به تدريج به سمت
جواب بهينه همكرا ميشود.
صفحه 17:
ساختار کلی الگوربتم هایژنتیکی :
فضای جستجو:
برای فضاهای کوچک. روشهای کلاسیک جستجو و بهینه سازی خوب و کافی
هستند اما برای فضاهای بزرگ و مسائل مشکل نیازمند به تکنیکهای دیگری
همچون روشهای ذیل هستیم:
Lil ان
Dobu Gear
الم Borer
rear kyoto
صفحه 18:
الگوریتم ژنتیک به جای این که بر روی پارامترها یا متغیرهای مساله کار کند.
يا شكل كد شده آنها سروکار دارد. یکی از روشهای کد کردن؛ << کدکردن
دودویی > می باشد که در آن هدف تبدیل جواب مساله به رشتهای از
اعدادباینری (در مبنای ۲) است.
صفحه 19:
پس از تعیین سیستم کدینگ و مشخص شدن روش تبدیل هر جواب به
کروموزوم. باید یک جمعیت اولیه از کروموزومها تولید نمود. در اکثر موارد.
جمعیت اولیه به صورت تصادفی تولید میشود. اما گاهی اوقات برای بآلا
بردن سرعت و کیفیت الگوریتم از روشهای ابتکاری نیز برای تولید جمعیت
اولیه استفاده میگردد. در هر صورت عمومیترین و راحتترین روش استفاه
ادنك رويكرت تصادفی می باشد..
اندازه جمعیت اولیه معمولا به سایز رشته کدشده وابسته است. به عنوان
ار کروموزومهادریک مساله ۳۲ بیتی هستند قطعا بايد جد -
انتخابی اولیه بیشتر از حالتی باشد که کروموزوم هابه عنوان مثال ۱۶بیتی
هستند.
صفحه 20:
کروموزومها به نحوی باید حاوی اطلاعات جوابی باشند که نمایانگر آن هستند.
روشی که اغلب بکار برده میشود. نمایش دودوتی است. شبیه کروموزومهای
Se)
0000000000100 0 جومم و0
1000000000000 9 «مسومسمسبن
روشهای دیگری نیز برای نمایش کروموزومها وجود دارد که وابسته به مسئله
مورد حل می باشد.
صفحه 21:
۳ ای که یک با چند نقطه از دو یا چند جواب را انتخاب ۲۰۵۰
آنها را تعویض میکنند. اين عملگرها. یک جواب را در نظر گرفته و
محلهایی از جواب را با جوابهای دیگر معاوضه کرده و جوابهای جدید را به
وجود ميآورند. به اين نوع عملكرهاءعملكر برشى كفته ميشود.
مثال :
Chrownsnwe 000000 |] 0000000000000
وموم و0 00000000000
بممجان 4 1000۵
OPP sprice 2 IdDdd|OOIDOadOadD.
صفحه 22:
عملگرهایی که یک یا چند ژن از یک کروموزوم را انتخاب و مقادیر آنها را
تغییر میدهند. در اين عملگرهادیک یا چند محل از یک رشته کاراکتری با
طول خاص, در نظر گرفته شده و مقادیر کاراکترها در آن محلها تفییر
مییابد.
مثال :
IIDddddOOOOAdddO بیان امیس
Dutated pPPsprice 00000000
صفحه 23:
مواردی که در این نوع مهم است. عبارتند از:
۱-تعداد محلهایی که قرار است تغییر یابند.
۲-نحوة انتخاب محلها
۳-نحوة عملیات تفییر
صفحه 24:
۱ للگوریتمهای ژنتیک بهطور ذاتی دارای ماهیت تصادفی میباشند. یعنی از راههای مختلف به
جوابهای مختلف خولهیم رسید. اين کارکرد بدلیل نحوه عملکرد الگوریتم است که حدس اولیه
که شامل جمعیتی از افراد است تصادفی انتخاب ميشود.
۲-الگوریتمهای ژنتیک برای مسائل دشوار استفاده ميشود. مسائلی که فضای جستجو در ان بسیا
وسیعتر از آن است که بخواهيم جستجوی کلاسیک و منطقی انجام بدهیم.
۳-متفاوت از بسیاری از الگوریتمهای حل مسائل عددی که فقط یک با چند جواب خاص را
بهدست میدهند, الگوریتمهای ژنتیک یک جمعیت از راهحلها را بهدست خواهد آورد که دارای
بهترین برازش هستند و تابع هدف را بيشینه ميكنند.
۴-راه حل ها به شکل کروموزوم (فرد) دستهبندی و رمزبندی میشوند. که هر کروموزوم دارای
مجموعهاى از زنها است که خواص مختلفى رابيان ميكنند.
-۵اصل بقای اصلح (تنازع بقا) درست مانند جهان واقعیت و عالم طبیعت. پیادهسازی ميشود.
یی آفردی از استخر ژنی یا جمعیت اولیه که شرایط تایع برازش را ارضاه نمیکنند. بهطو قلح
١ هی بمدی حضور نخواهند داشت و محکوم به فنا هستندا
صفحه 25:
کتاب الگوریتم ژنتیک نوشته مصطفی عباس کیا
کتاب مقدمه ای بر الگوریتمهای ژنتیک نوشته مهدی علیرضا
سایت ویکیپدیا
صفحه 26: