صفحه 1:
صفحه 2:
ایا
تم » يردازش تصوير وأ
5 New ees
7
صفحه 3:
صفحه 4:
صفحه 5:
aff A\
9 sah ور NL LG yp cg
را به صورت کد شده در قال.رشته ای,از اعدله,صکیح با ب Pay AS
a Ag 2 ۳۳
د o 5
۱ ۳2
3 سس
| 1011018101 101101) 100
1100101101 ||
۸
یبد
صفحه 6:
صفحه 7:
صفحه 8:
صفحه 9:
۰۰۰9
Meta i6 2p Sauk ba ۲ خش لياس دارد که
eee 2 كلوفي. مويلأجكان »الكوريتم يتيك ۶/2
أدا
صفحه 10:
صفحه 11:
صفحه 12:
صفحه 13:
صفحه 14:
صفحه 15:
صفحه 16:
Create Taal Randa
Population for Bun
Desig
[Result for Rim
Taek One Ind و
[Select Twe Indiv ida rerform Insert Offspring
Based on Fituess cossover ata New,
اه
Tae
صفحه 17:
صفحه 18:
صفحه 19:
Genetik algoritm
الگوریتم ژنتیک چیست ؟
SOFT COMPITINGیکی از زیر شاخه های •
است که تکامل طبیعی موجودات را GAالگوریتم ژنتیک
الگو قرار می دهد.ؤنتیک الگوریتم از جمله روشهایی
به کار می روند .آنها NPهستند که برای حل مسایل
الگوریتم های تصادفی هستند که بر اساس پدیده طبیعی
.وراثت ژنتیک عمل می کنند
الگوریتم مبتنی بر تکرار است و اصول اولیه آن از عم •
ژنتیک اقتباس گردیده است.در مسایل متنوعی نظیر بهینه
سازی ،شناسایی و کنترل سیستم ،پردازش تصویر و
.مسایل ترکیبی و آزمایش شبکه عصبی به کار می رود
ساختار الگوریتم
.اCیناCCلگوریتم CبCCCا رشته CبCCCیتیکCCCار میکCCCند 1-
.در هر تCCCکرار چند نCCقطه Cاز فCCCضایجستجو را در نCCظر میگCCCیرد 2-
•
:نکات مهم
•
.شرایط جمعیت در رسیدن به جواب بسیار تأثیر گذار است
با توجه به پارامترهای تصادفی حتی در صورت استفاده جمعیت اولیه
.یکسان ممکن است جوابها یکسان نباشد
•
.تابع ارزش در این الگوریتم اهمیت زیادی دارد
•
فناوری الگوریتم
این الگوریتم روش قدرتمندی را برای توسعه اکتشافی مسائل بهینه سازی
ترکیبی مقیاس بزرگ فراهم آورده است .الگوریتم ژنتیک مسئله را به
صورت مجموعه ای از رشته ها که شامل ذرات ریز هستند کدگذاری می
کند ،پس برای تحریک فرایند تکامل تدریجی تغییراتی را بر روی رشته
.ها اعمال می دارد
الگوریتم ژنتیک در دنیای کامپیوتر
جهت استفاده در برنامه ها ابتدا باید راه حل بیابید تا حاالت جواب مسئله خود •
را به صورت کد شده در قالب رشته ای از اعداد صحیح یا به صورت رشته
ای از بیت ها نشان دهید مثل 0111011001
:مثال •
شرایط خاتمه الگوریتم
به تعداد ثابتی از نسل ها برسیم
.بودجه اختصاصی (پول/زمان) تمام شود •
.یک فرCد (فرCزند پیدا شود که کمترین مالک رCا برCآورده کند •
.نتایج بهتری حاصل شود •
•
نتایج
مختصرا گفته می شود که الگوریتم ژنتیک ( )GAیک تکنیک
برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی
حل مسئله استفاده می کند .مسئله ای که باید حل شود دودویی
است و راه حل ها طبق یم الگو کد گذاری می شوند .این الگوریتم
یک تکنیک جستجو در علم رایانه برای یفتن راه حل بهینه و
مسائل جستجو است.
نمونه ای از کاربرد الگوریتم ژنتیک
چکیده :مساله فروشنده دوره گرداز مسایل کالسیک تحقیق در عملیات می •
باشد.بسیاری از فعالیت های علمی را می توان به صورت مسئله فروشنده دوره
.گرد در آورد .و سپس حل نمود
شهر تشکیل شده که بین هر دو شهر آن یک مسیر می تواند وجود nمسئله :از •
داشته باشد.هر یک از این مسیر ها فاصله و هزینه مشخص دارند.این مسئله
.کوتاهترین مسیر را تعیین می کند
الگوریتم های ژنتیک با مجموعه اولیه ای از راه حل های تصدفی که جمعیت •
اولیه نامیده می شود ،شروع می شوند .هر عضو (جواب) یک کروموزوم
.نامیده می شنوند
همان گونه که در شکل پیداست این الگوریتم سه بخش اساسی دارد که
عبارتند از الگوریتم کلونی مورچگان ،الگوریتم ژنتیک و قسمت
.تبادل جوابها
تبادل جوابها
ساختار الگوریتم ترکیبی به گونه ای طراحی شده است که هر دو الگوریتم به •
نشان داده loopصورت موازی به حل مسئله می پردازد تا به شرط توقف که با
مورچه و mشده است ،برسند .در این زمان الگوریتم مورچگان به تعداد
از EC%جواب اولیه ایجاد کرده اند و به مقدار Mالگوریتم ژنتیک به تعدا
.جوابها بین دو الگوریتم مبادله می شوند
پس از مبادله جوابها عمل تطبیق جوابها در دو الگوریتم صورت می گیرد• ،
بدین صورت که جوابهای الگوریتم مورچگان وارد نسل جاری جمعیت
الگوریتم ژنتیک شده و جوابهای الگوریتم ژنتیک وارد مرحله قبل از فرومون
.ریزی کلی می شوند
پس از این مرحله الگوریتم مجددا حل مسئله فروشنده دوره گرد را ادامه می •
.دهد تا به شرط توقف برسد
نمایی کلی از روش GA
همان طور که دیدید در هر نسل به تعداد نسل قبل ما فرزند خواهیم داشت.
این فرزندان از طریق روش Over Crossایجاد می شوند.در این روش مکان
مورد نظر به طور randomانتخاب می شود.ولی تعداد Chromosome
هایی که در cross overشرکت می کنند بر اساس یک احتمال(Cross
0.6<Pc<0.7 )Over Rateانتخاب می شوند.
در اینجا چند روش معروف Cross Overرا نشان میدهیم:
– روش ادغام تک نقطه ای()Single-Sight Cross Over
– روش ادغام دو نقطه ای()Two-point Cross Over
– روش ادغام چند نقطه ای()Multi-point Cross Over
روش ادغام تک نقطه ای()Single-Sight Cross Over
در این روش یک مکان تصادفی در طول رشته انتخاب می شود و geneها
از این مکان به بعد جابجا میشوند.
رCوش ادغام دو نقطه ای((Two-point Cross Over
در این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این
دو نقطه را جابجا می کنیم.
روش ادغام چند نقطه ای()Multi-point Cross Over
شبه کد
آخرین نکات!
.1این نکته بسیار مهم است که همیشه مقدار میانگین Fitnessاز نسلی به نسل بعد یا
ثابت می ماند یا افزایش میابد و نهایت به یک عدد همگرا می شود و حول آن عدد با
میزان واریانس کمی نوسان می کند!
.2توجه به فاکتورهای اساسی که در پیاده سازی GAمهم است:
نحوه نمایش.
اندازه ی جمعیت و نرخ جهش.
روشهای انتخاب و حذف.
عملگرهای ادغام و جهش.
.3شرط خاتمه.
مزایای GA
.1
.2
.3
.4
.5
.6
.7
.8
.9
فهم آسان.
مجزا بودن.
پشتیبانی از بهینه سازی چند تابعی.
مناسب برای محیط های نویزی.
همیشه یک جواب داریم که با گذشت زمان بهتر می شود.
امکان استفاده به صورت موازی.
روشهای مختلفی برای افزایش سرعت و پیشرفت الگوریتم وجود دارد.
بهره برداری ساده از جواب قبلی.
انعطاف پذیر برای کاریرد های ترکیبی.
پایان