صفحه 1:
صفحه 2:
a
الگوریتم های ژنتیک
Instructor : Saeed Shiry
& Mitchell Ch. 9
صفحه 3:
.الگوریتم ژنتیک روش یادگیری بر پایه تکامل بیولوژیک است ۰
۳
eae ال ل ۱
صفحه 4:
ک مسئله مجموعه بسیار بزرگی از راه حلهای ممکن را تولید میکند /3) یک
د از اين راه حلها با استفاده از يك “ تابع تناسب” مورد ارزيابى قرار ميكيرد
هترين راه حلها باعث توليد راه حلهاى جديدى ميشوند. كه اينكار باعث تكامل
.راه حلها ميكردد
ترتیب فضای جستجو در جهتی تکامل پیدا میکند که به راه حل مطلوب برسد
ا ل ل ال ل ل ا ل فشك
صفحه 5:
5۱۳ و یا 506616 606۲۵۱-0و الگوریتم ژنتیک بجای جستجوی فرضیه های ۰
Sea ie ee nce و Soy
و
.جمعيت فعلى با فرزندانی که از بهترین فرضیه های موجود حاصل شده اند بدست ميآيد
صفحه 6:
0 ee 3 Ie SS TES ee eee Se ere ree
ا ل ل ل ل تم fe 9 WP re- hmmar
ا ل ا ةزه
Ee رك
'را ميتوان براحتى بصورت موازى اجرا نمود از اينرو ميتوان كامييوترهاى
.ارزان قيمت ترى را بصورت موازى مورد استفاده قرار داد
ا ل ل 0
ا ل ل
0 ا ا te an
صفحه 7:
PARALLELIZATION C
PRO
* CS 5 (999 Js »» Genetic Programming Inc.
Ee een ا Eee eed ye
350 1/112 براى يياده سازى روش هاى زنتيك را مورد استفاده قرار
صفحه 8:
کاربرد الگوریتم های ژنتیک بسیار زیاد میباشد
optimization,
automatic programming,
machine learning,
economics,
operations research,
ecology,
studies of evolution and learning, and
social systems
صفحه 9:
:به دو نوع مرتبط به هم ولی مجزا دسته بندی میشوند ۴۸ روش های
Genetic Algorithms (GAs) .1
Rupp OE ete ete BMS -T0 Ne" ل TS oe
2. Genetic Programming (GP)
پردازد 50| که در زبانهای برنامه نویسی مثل ۳665 660۲655/01 اين روش به تولید
,بدین ترتیب میتوان برنامه هانی ساخت که قابل اجرا باشند
صفحه 10:
tenttee Si SE Stes OD rer oe Toy ل ين
eee Mma eC meE ل ين
,جدیدی جایگزین میگردد
65 در هر بار تكرارتمامى فرضيه ها با استفاده از يك تابع تناسب يا *
eey Wore nis nee ا ل ل ا 2295057
.جدید را تشکیل میدهند
به های انتخاب شده به همان صورت مورد استفاده واقع شده و مابقی با استفاده »
ان بكار ميروند36101آنا!/! و 0105501761 از ايراتورهاى زنتيكى نظير
صفحه 11:
:داراى يارامترهاى زير است .64 يك الكوريتم
GA(Fitness,Fitness_threshold,p,r,m)
پابیی کف رضیه که مقداریعددویه هو فرضیه نسبتمیدهد۳[]0655 : ۰
مقدار آستانه که شرط پایانرا معینمیکند 0۲۳650۱0 _کوع(]ز۲ : ۰
تعداد فرضیه هنیکه باید در جمعیتدر نظر گرفته شوند 0 : ۰
۲۳ در صدواز جمعیتکه در هر مرحله توسط اللگرریتم ۲: ۰
*:m ¢ mutation
صفحه 12:
.فرضيه بطور تصادفومقدار دهىاوليه كنيد م جمعيتوا رت ۱۱۱۵۱۱۰
ل Sa SAVIO ee eo Oe a)
عيت جديد ايجاد كنيد b[max, Fitness(h)] < Fitness threshold ).45
.است را بركردانيد 180655] فرضيه اى كه داراى بيشترين مقدار
صفحه 13:
عیت جدید
eee Eee De
ple (Co Cres be ea eect eer لضافه کنید. لحتما
:عبارتلستاز از میان«افرضیه
سر طلست
P(hi) = Fitness (hi) / 2j Fitness (hj)
VPM CSN -10 eT ا ا اا 0) 7B)
Ce eee = 8 er es bn Der net Ol cool! gees eae
ل فرزندانرا بسه
۳ eae ا wits ieas)
|۳0 pel Ul
4 ۳ كن I
©. هيضرف براى هر ١ ارا محاسبه كنيد 17655 مقدار تابع 6 در
صفحه 14:
نمایش فرضیه ها
۱0 ا fr Ecos Pee OOe ber ote e SP opr ser
۱
* : .به مقادير يا رلم حلهاوولقعمك فتء ميشود ©م/556001
000 0 ا ا reece ce Pm cl We)
,میگیرند
| eet e Tee rene ee Te ees
spore ee eee aaa ORO سس
ات و سم و ت)]
صفحه 15:
:1111-| مثال: نمايش قوانين
,/10101ن5 كه داراى سه مقدار 01061001 براى نمايش مقادير يك ويزكى نظير ٠
Ree erent = Ip TP rCCe i Poeem) 00
= Overcast * Rain
100 -> Outlook = Sunny
011-> Outlook
0 le nies
را میتوان با پشت سر هم قرار دلدن بیت های قسمت ۲6۳ -
9
Wind
011
همين ترتيب كل يك2إوا
00
Baal ل الل BAN ل ذال
= bit string: 111100
Wind
10
(elitr lye) a
PlayTennis
111
صفحه 16:
Oe
ها: ملاحظات
ركيب بعضى از بيت ها منجر به فرضیه های بی معنی گردد. برای پرهیز از چنین وضعیتی
.ميتوان از روش انكدينك ديكرى استفاده نمود ٠
و 0
ا ار ا ل ل كن
صفحه 17:
005 ايراتورهاى زنتيكى
تفاده از دو رشته والد دو رشته فرزند بوجود ميآورد ]0105501 ايراتور ٠
.براى اينكار قسمتى از بيتهاى والدين در بيتهاى فرزندان كيى ميشود ٠
هائی که باید از هر یک از والدین کپی شوند به روشهای مختلف انجام میشود *
single-point crossover *
* Two-point crossover
+ Uniform crossover
1/1 ا wD lems Sen Sele hO I wet تك
صفحه 18:
SINGLE-POINT CR¢
.یک نقطه تصادفی در طول رشته انتخاب میشود ۰
0
م ا لل ا ا ا ا 0
لعف 0 سوه
صفحه 19:
6 روشهای دیگر
* Two-point crossover
000000000000000 ص0 مس
و 3
ی
ی ره 4 :حاجب (1) جرد( سس
[0 oge Eee een Pe ee spp
صفحه 20:
لاالاا ايراتورهاى زنتيكى
Tes. ۱
.میکند. اینکار با انجام تغییرات کوچکی در رشته اولیه بوقوع میپیوندد
CPSs ee eos Crm En ا ا ا ا ل 0
.مقدار آن تغییر پیدا میکند
.اعمال Ysexe mutation lel 5! ae crossover 2 pt *
eel لت
صفحه 21:
CROSSOVER OR MI
See pers) enh a SU Por
كداميك بهتر است؟ كداميك لازم است؟ كداميك اصلى است؟
| t cess Isc Tee SCE Peony
* بستگی به صورت مسئله دارد
[۳ ا
See Ee ee ees
8 ستفاده کند ولی الگوریتمی که فقط از ۲۳۱13170۳ میتوان الگوریتمی داشت 5
نخواهد كرد
صفحه 22:
CROSSOVER OR MI
* Crossover Ly 5 4i_Ssaimatuols explorative Sy jastet
ree IDES ear Se ose Seer oon
لنجام تغییرلتک وچک 6۱0۱0111۷6 خاصیتگسترشیو یا۲زا۱/۷]۵ ۰
.تصادفییه نولحیک شفشده وسعتب بخشد
ل لات لت 0۱ لي
۱
زم است 1710311017 براى رسيدن به يك ياسخ بهينه يك خوش شانسى در ٠
صفحه 23:
ارضیه هاست که کمک میکند تا فرضیه های برتر برای نسل بعدی جمعیت 0655 تابع ء
She Eero ل ا ا ees re es
CS Soe wee ee لت نل
syne
صفحه 24:
Roulette Wheel selection
ee SES EW ee Sere SPI AC) Wee)
انتخاب يك فرضيه براى استفاده در جمعيت بعدى
2# ا ل
اععالالا عغ6عان0ظ8 اعضا دارد. اين روش
ac (CD Ree 5ع|6 .ناميده ميشودم 0ع
8 )0(- P(hi) = Fitness (hi) / 2j Fitness (hj)
< (0)سسس۳
* روشهای دیگر:
۴ ایو امه
و وا
صفحه 25:
es
ر فضای فرضیه
:با روشهای دیگر مثل شبکه های عصبی تفاوت دارد :3۸۵) روش جستجوی
eT eye renee Eel e-(el (“hme (-Se-1g a See eee Ss Lene ree
CE eer) Wier ey OLE SO SS ESPS SS SAREE ES merc
.در 1 داشته باشد.از اینرو احتمال گیر افتادن
1 See wo aera ل
صفحه 26:
0٩
, عضویکه سازگارب سیاربیشتریاز بقیه لفراد جمعیتدارد بطور مرتبو0۲۵۷/0[۲ ۰
ا 111[ 1 1 1[ 1 1[ 1 111111
.را كم ميكند .548) اينكار باعث كاهش يراكندكى جمعيت شده و سرعت ٠
F(X)
صفحه 27:
سس
8 راه حل رفع مشکل
nc Ts erie eek Sere s Lo ke ere Rc الت ا رن
.مقدار این برتری نشان داده نخواهد شد
كاه اعضا مشابهىدر جمعيتوجود دلشته باشند 10©55] مقدار 5131159 5180655 : ٠
.كاشمويايد
صفحه 28:
۸ چرا
رای تازه واردین به روشهای ژنتیکی ایجاد شود اين است که آیا این روش واقعا میتواند کار
200000
صفحه 29:
ارزيابى جمعيت و قضيه
آيا ميتوان تكامل در جمعيت در طى زمان را بصورت رياضى مدل نمود؟ ٠
.را بيان نمايد 4 ميتواند مشخصه يديده تكامل در 56161073 قضيه ٠
6 مجموعه اى از رشته بيت ها را توصيف ميكند.يك 5017613 يك ٠
.است ©6031 00176 از © واكو* است. مثل (000*0 كه * حالت
ل ار ا ا لت رفن
*,000*)00,**** : 3مماع 5 دارند. مثلا 0000000 را ميتوان نماينده )©
وغيره
صفحه 30:
۳
Seen Este git eee eee eter vo racial lait S Se ae gen toe
د برابر با 5 مثل 50116173 تعداد نمونه هائى كه نماينده يك + فرض كنيد كه در لحظه
.را مشخص ميكند (1+-70)5,5 قضيه مقدار مورد انتظار
1 ا ا
P(h,) = Fitness (h,) / 2, Fitness (h;)
:اين مقدار احتمال را ميتوان بصورت زير نيز نشان داد
6م /لرط) ؟ د رطام )6(
صفحه 31:
Oe
۳
© stile pine cyl ASG! Sein op GG! Cures cul tig pene 615 U Cul os aa
Cap SONS ITC CA] (Ho meee ا ا
ماصل خواهند شد برابر است (] كه از 5 از اينرو مقدار «مورد انتظار براى نمونه هائى از *
:با
صفحه 32:
012212100020
0
میانگین 1 +1 های مورد انتظار در لحظه 56۳6۳03 رابطه فوق به اين معناست که تعداد ۰
.سایر اعضا نسبت عکس دارد ۶0655 بوده و با مقدار (],5)دا
رابطه فوق فقط اثر مرحله انتخاب نمونه ها در نظر گرفته شده است. با در نظر گرفتن اثر ۰
[icles eh Ee نموه
صفحه 33:
SCHEMA T
eo ل
See ed
۳ en aed
7 > ل ل رادار
Pe = treble oP wanimmn umes
1 Se ee ee محجمه
Pe ee Le eal
۱ ee
ee oe a ed علا
صفحه 34:
اطلاعات مفيد و اميد بخش موجود در جمعيت را كد 5016103 يك ٠
PRES vee REEDS ECM e RSIS Pree rel)
ها 561761773 انتخاب شدن دارندء بتدريج مثالهاى بيشترى به بهترين
.اختصاص مى يابند
ا Tee SE برت انرق ٠. Jee
ل رو ۳
هاى با طول كوتاه كمثر تغيير 56176173 نخواهد داد.در حالت كلى
3 در حالت كلى باعث تغييرات موثر در 10531017] عمل ٠
8 دد
صفحه 35:
ای جستجو 65۸) تفاوت
بجاوكد كردزيارامترها مجموعه لنها را كد ميكند .6 ٠
.بجاوجستجو برلويكنقطه بدنبا لجمعيتىاز نقاط ميكردد 68 ٠
٠ 6 دريكيم ر مشتقو يا ساير لطلاعاتكمكومستقيما ازلطلاعا.تموجود در نتيجه بهره
ae) eter shee at paver Gee se Cnr Peeen
صفحه 36:
a
ال ا 1
2020
———
_ ~~z=m™
صفحه 37:
ا ل ees os See ees Tee ۱
,فارسی درگیر هستند, بسیار مفید خواهد بود
۱ Te BIOS oa
شهای حروف فارسی بر روی صفحهکلید جستجو کرده و چینش بهینه را بدست
.آورد
میتواند با توجه به یک
۳9
صفحه 38:
SST OO سس
ی حروف فارسی بر روی a
صفحه 39:
ید ثابت است و ما میخواهیم که تعداد ۳۳ نشانه که متشکل از ۳۲ حرف الفبای فارسی بعلاوه حرف همزه *
۰ است را بر روی سه ردیف صفحه کلید که به ترتیب دارای ۱۱,۱۲,و ۱ کلید هستند, قرار دهیم
ا ا ااا ا ااا |
صفحه کلید بای تایپ حرروف فارسی, احساس راحتی بیشتری نسبت به کار با
۳-9
صفحه 40:
6 ISCAS TST IESE ren
BSe penne Ap Yee IOS) ES on ea ا
د در این الگوریتم
گرهای ژنتیکی بر روی جمعیت موجود كد جينشهاى مختلفي از حروف فارسي بر روى .
میشوند و جامع هسستی سوق داده 0 ى اعضاى آن به
مقدار وج بر سید
Ere DeNC Le SSIES ere TOeT CS eer os) 0
تناسب ب متتی که از مطالب چند سایت خبمری فارسی زبان تهیه شده است, به دست میاید
صفحه 41:
اعضای جمعیت جایگشتهای مختلف حروف فارسی روی صفحه کلید هستند. هر عضو *
i Tae eS eS SSS et eter ister
آن متتاظر با یک کلید از صفحه کلید است
i
أ
SEY ل ااا eee So
ee Sis here St Seer rE a
ES eee eT Cao POLE Sse ca eos ern bik te oye
.زده شده است
صفحه 42:
ختی کار کردن با چینش حروف بر روی صفحهکلید یک مساله پیچیده ارگونومیک است
ا ا ا ل ا Se rs eee Lee Tt
ا ل ا ee
بيشترين تايب حروف به صورت متناوب با دو دست؟؛
كمترين تكرار تايب دو حرف متوالى با يك انكشت؛ و
.بیشترین تایپ حروف بر روی کلیدهای پایهای (کلیدهای ردیف وسط)
كن
صفحه 43:
er et wr pan 0 و ل ان
هزينه مربوط به لستفادم از Pl OS SOO ee crt Seer
,پشتسر هم
:برای هدف سوم, فاکتور اندازهگیری زیر معرفی میشود ۰
ال ا ل ار ا Fee ee ی
,حرفپشتسر هم
هزينه مربوط به تايبكردزنيكحرفهبا تسوجك بسك :. ...وي *
.موقعيتآنحرفبر روىصفحاءك ليد
صفحه 44:
.وموزوم از مجموع اين سه فاكتور براى تمامى حروفى كه در متن مورد استفاده براى *
: آزمایش وجود دارند, بدست میآید
مجموعه تمامىكلماتموجود در متنمورد استفاده برلىآزمايش لسك /الا
ا ا ف
لست ,1 لم از 0
صفحه 45:
ا ا ا ان
۱ ا ا ا ل CORNET Oe
.كردن دو كروموزوم والد هزينة زمانى بالايى دارد
بو صورت برای اعضای مختلف جامعه به کار میبریم. در این مساله یک ۰
مىكنيم كه اعضاى آسن تراز اول جمعيت از ديد تابع تناسب را تشكيل
3-00
ا ا ا ا ل ا ل ال 0
ند. در حاليكه براى افراد عادى جامعه اين تعداد به ©) جابهجايى افزايش
.مییابد
صفحه 46:
:الكوريتم ذنتيك با يا رامترهاى زيس اجا كرديم
تعداد اعضای جمعیت ۱۰۰ کرروموزوم که در نسل اول به صورت تصادفی تولید شدهاند؛
3
| eee Ee eel SE
.و تعداد كل نسلها 6٠© نسل
صفحه 47:
|
ماس
9 end درطى perl erate CS ey
الا بهپایین, متوسط مقادیر تناسپ همه اعضبای جامعه, متوسط مقادیر تتاسب جامعه نخبگا
«بهترين تناسب هستند
صفحه 48:
۳ TAS aren)
كنونى حروف فارسى است .
ین الگوریتم ژنتیک بررای حرروف فارسی اراثه داد, هزینهاش با توجه به
امماهد | مس[ من
det | end ام
صفحه 49:
| Se OSE et SES Se
:نسل های مختلف یک نمونه در طول زمان سازگاری های مختلفی را کسب میکنند
۰ :سوال
م ل ان Teele,
صفحه 50:
LAMARCKIAN EV
. فرضیه لیارائه کرده که طبقآنت جربیاتیکموجود زندم در ترکیب1۵708۲61 ۰
,ژنتیکیف رزندانآنت-اثیر میگارد
| See OSS S Eevee STUDS SMS Te S006 Es eS Terie hn See
.مينمايد تا آنها ديكر مجبور به يادكيرى اين يديده نباشند
:اما شواهد تجربی این نظر را تائید نمیکنند »
صفحه 51:
BALDWII
BS tp to ere See eyes Stee SLES SES ee Eee A
MMe kerr ren
ESS Ste Ie Se EE Sab ee ES 5 clots cy ected
,شرایط را داشته باشند شانس بیشتری برای بقا دارند
Pepe CORP ep EC ate ye cers BIBS CE CE AEE Te eee TEED)
Pera pytee i peg tE Pn PoP ge LIE TES Ro Cee Pern mich pK etree
5-93
صفحه 52:
a ee
الگوریتم های ژنتیک
لگوریتم های ژنتیک از قابلیت خوبی برای پیاده سازی بصورت موازی برخوردارد هستند
زج 0
Teno ل كت
.اجرا ميشود ©0617 بر روى .6/8 در هر كره يك الكوريتم استاندارد
اال 00
صفحه 53:
EVOLVING NEURAL NE
بعمل آمده است.از جمله : وزنهاء \| emer Cone ie a) هاى مختلف ./6 از
.ساختارو تابع يادكيرى
ی یک شبکه عصبی میتواند بسیار سریعتر از روش استاندارد 66/۸ استفاده از ٠
back propagation xs Uc.
ر شبكه عصبى مشكلتر ميباشد. براى شبكه هاى كوجك با .02 استفاده از ٠
ene ا ا ا ا ال
ريس به زن هاى الكوريتم زنتيك تبديل و تركيبات مختلف آن بررسى ميكردد
اى بدست آوردن تابع يادكيرى يك شبكه عصبى راه حلهائى نظير استفاده از ٠
,قرار گرفته اما عموما این روشها بسیار کند عمل کرده اند
صفحه 54:
ا ا م يل
۰ 6۵
صمة ها ی ۱۳۱۱۹
September 1993.
[3] Peter Klausler, www.visi.com/~pmk/evovied.html, September 2005.
CUR یر ات
Peete ا ا ele a
[5] P. S. Deshwall and K. Deb, Design of an Optimal Hindi Keyboard for Convenient
ععممت امع ieee re MP EM US Rma NA
EW ene U DMM is teen eee aa re
1983۰
ات۱۸۱۲
eter ener rele eeu eee ake
.2005
صفحه 55:
GENETIC PROGF
Sie] Jac ene ee end OSC EO pe ocr perce)
2 ete ey eres aE sete
.باشند
* 6۳ روشیاز ال ا ل ا جمعیتیک
.برنامه كامييوترولست
* برنامه ها اغلب بتوسط يك درخت نمايش داده شده و اجراى برنامه برابر
.كردبه درخت 0305 است با ۱
we F = sin(x) + sqrt(x*2 + y)
2 sqrt
صفحه 56:
ا Sante Pee el
۵ ,- ,+ ,]50۲ ,5 ,510 میبایست توابع پایه ای که در آن زمینه مورد نیاز هستند نظیر ۰
شوند
همجنين ترمينالها نظير متغيرها و ثوابت نیز ید مشخص شوند *
زرك برنامه هائى كه توسط اين مقادير اوليه قابل بيان هستند يك عمل 66 آنكاه الكوريتم *
,جستجوی تکاملی را انجام خوهد داد
صفحه 57:
97-۳0۵0
aoe Ie ees Fe eee Cec ee Wee)
دیگر بطور
sove اپراتور
بطور تصادفی عوض میشوند
+ +
sin ~ 8 sin ۳
2 + سم 0
0 ae
۹ 2 4
a — a ee Ms
2 sqrt Sin sqrt
5 \
صفحه 58:
| الكوريتمى ياد كرفته ميشود كه بتواذ
إيتمى ياد كرفته ميشود كه بتواند بلوكى ها را در يك ستون 023)! در كتاب مثا
2 ار كتاب مثالى از ٠
ss
۲ 5 Tr
aes FEB ame pee Cae ge Lerner SDT ا
PASC ا Wee) 1
۱
صفحه 59:
۱ Sone erode ees ene eee e nose
:عبارتند از
Parco ل لل Se ket
۰ .یک بلوک را از میز به انتهای ستون منتقل نمود
٠ :توابع اوليه
ا ا ا ل ا رتل تي بن
آوجود ندارد
۰ ۲8 )۲00 60۳۲661 0۱061 له همرلم با بلوکهایزیرینشترتیبصحیح مورد
500250 Sap) a
٠ ليرد تاترتيب18 نام بلوكوكه بيد در با لفى(/5531عع76 غلاع0) لآلا
,درستدربیاید
صفحه 60:
:ساير توابع اوليه ٠
* (MS x) move block x to stackSsls SI 0
9 eed ete Sean
د لینلپراتور بلوکبا اهر لگر بلوکت۲۵۱ 10 ۱۵61۷ ۱۵۷6 (۲۲۲۷) .۰
,برمیگردلند] ستونرا به میز منتقلمیکند. درغر لینصورتقدار
(EQ x y) returns true if x = y.
+ (NOT x) returns the complement of x
+ DU(x y) do x until expression y is true
صفحه 61:
655 مقدار تابع
عداد ©0©9 مثال كه هر يك در بركيرنده آرايش اوليه متفاوتى براى بلوك ها ٠
Kno ee ا 0
BY ا ا ا 0 تت كن
ليه اى برابر با0000© برنامه تصادفى شروع بكار نموده و يس از توليد 00 *
:نسل قادر ميشود تا برنامه اى بيدا نمايد كه تمامى ©03 مثال را حل نمايد
(EQ (DU (MT CS)(NOT CS)) (DU (MS NN)(NOT NN))
صفحه 62:
aa
فیلتر
۳۳ 0 ETO Dey Rreerey Ee CD rg) Wn evEy ا ا
:توابع اوليه ٠
ا 20 قطعات و سيم بندى های مدار ۰
تابعى براى حذف كردن قطعات و سيم بندى هاى مدار ٠
eSE ا ا ا الت 0
Be Pee rere ever SIC e Dit ae aE Siete
فت
: جمعيت اوليه (020000000© ٠
درصد6۲0550۷6۲ : نرخ ©© ٠
mutation +=» : نرخ 0 ٠»
صفحه 63:
فیلتر
ع eS EST ES Sales ET nse ۱
ای که بصورت تصادفی ایجاد شدند در 000 مواقع حتی امکان شبیه سازی وجود نداشت ۰
ECE TOS eee yenek ((o EES eee n ۱