Tursunova durdonaxonning

FARG’ONA DAVLAT UNIVERSITETI

AMALIY MATEMATIKA YO’NALISHI

K.20.122-GURUH TALABASI
TURSUNOVA DURDONAXONNING

SUN’IY INTELEKT VA NEYRON TO’RLI TEXNOLOGIYALAR FANIDAN

MUSTAQIL ISHI

Genetik algoritmni amalga oshirish.

Reja:

1. 
   Genetik algoritm.
   
2. 
   Optimallashtirish muammolari.
   
3. 
   Genetik algoritmni amalga oshirish.
   

Yilda kompyuter fanlari va operatsiyalarni tadqiq qilish,a genetik algoritm (GA) a metaheuristik jarayonidan ilhomlangan tabiiy selektsiya ning katta sinfiga tegishli evolyutsion algoritmlar (EA). Genetik algoritmlar odatda yuqori sifatli echimlarni yaratish uchun ishlatiladi optimallashtirish va qidirish kabi biologik ilhomlangan operatorlarga tayanibmuammolar mutatsiya, krossover va tanlov. GA dasturlarining ayrim misollariga optimallashtirish kiradi qaror daraxtlari yaxshiroq ishlash uchun hal qilish sudoku jumboqlari, giperparametrni optimallashtirish va boshqalar.
Genetik algoritmda optimallashtirish muammosiga nomzod echimlari populyatsiyasi (shaxslar, mavjudotlar, organizmlar yoki fenotiplar deb ataladi) yaxshiroq echimlar tomon rivojlanadi. Har bir nomzod echimi mutatsiyaga uchragan va o'zgartirilishi mumkin bo'lgan xususiyatlar to'plamiga (uning xromosomalari yoki genotipi) ega; an'anaviy ravishda echimlar ikkilik 0 va 1 satrlari sifatida, ammo boshqa kodlashlar ham mumkin.
Evolyutsiya odatda tasodifiy hosil bo'lgan shaxslar populyatsiyasidan boshlanadi va iterativ jarayon bo'lib, har bir iteratsiyadagi populyatsiya avlod deb ataladi. Har bir avlodda populyatsiyadagi har bir shaxsning jismoniy tayyorgarligi baholanadi; fitnes odatda hal qilinayotgan optimallashtirish muammosidagi ob'ektiv funktsiyaning qiymati hisoblanadi. Hozirgi populyatsiyadan ko'proq mos keladigan shaxslar stoxastik ravishda tanlanadi va har bir shaxsning genomi o'zgartiriladi (Rekombinatsiyalangan va ehtimol tasodifiy mutatsiyaga uchragan) yangi avlodni shakllantirish uchun. Nomzod echimlarining yangi avlodi keyinchalik algoritmning keyingi iteratsiyasida qo'llaniladi. Odatda, algoritm maksimal avlodlar soni ishlab chiqarilganda yoki aholi uchun qoniqarli fitness darajasiga erishilganda tugaydi.
Odatda genetik algoritm talab qiladi:

1. 
   eritma domenining genetik tasviri,
   
2. 
   yechim sohasini baholash uchun fitnes funktsiyasi.
   

Har bir nomzod echimining standart namoyishi bitlar qatori (shuningdek, deyiladi bit to'plami yoki bit qatori). boshqa turdagi va tuzilmalarning massivlari xuddi shu tarzda ishlatilishi mumkin. Ushbu genetik tasavvurlarni qulay qiladigan asosiy xususiyat shundaki, ularning qismlari sobit o'lchamlari tufayli osongina hizalanadi, bu esa oddiy krossover operatsiyalarini osonlashtiradi.
O'zgaruvchan uzunlikdagi tasvirlardan ham foydalanish mumkin, ammo bu holda krossoverni amalga oshirish ancha murakkab. Daraxtga o'xshash vakolatxonalar genetik dasturlashda o'rganiladi va grafik shaklidagi tasvirlar o'rganiladi evolyutsion dasturlash; ikkala chiziqli xromosomalar va daraxtlarning aralashmasi o'rganiladi gen ekspression dasturlash.
Genetik vakillik va fitnes funktsiyasi aniqlangandan so'ng, GA echimlar populyatsiyasini ishga tushiradi va keyin mutatsiya, krossover, inversiya va selektsiya operatorlarini takroriy qo'llash orqali uni yaxshilaydi.
Aholi soni muammoning xususiyatiga bog'liq, lekin odatda bir necha yuzlab yoki minglab mumkin bo'lgan echimlarni o'z ichiga oladi. Ko'pincha, dastlabki populyatsiya tasodifiy ravishda hosil bo'lib, mumkin bo'lgan echimlarning butun doirasini (qidiruv maydoni) ta'minlaydi. Ba'zan, echimlar optimal echimlarni topish mumkin bo'lgan joylarda "urug'langan" bo'lishi mumkin.
Genetik operatorlar.
Krossover (genetik algoritm) va mutatsiya (genetik algoritm).
Keyingi qadam genetik operatorlarning kombinatsiyasi orqali tanlangan echimlarning ikkinchi avlod populyatsiyasini yaratishdir:krossover (rekombinatsiya deb ham ataladi) va mutatsiya.
Ishlab chiqariladigan har bir yangi echim uchun ilgari tanlangan hovuzdan ko'paytirish uchun bir juft "ota-ona" echimlari tanlanadi. Yuqoridagi krossover va mutatsiya usullaridan foydalangan holda "bola" echimini ishlab chiqarish orqali odatda "ota-onasi"ning ko'plab xususiyatlarini baham ko'radigan yangi echim yaratiladi. Har bir yangi bola uchun yangi ota-onalar tanlanadi va jarayon tegishli o'lchamdagi echimlarning yangi populyatsiyasi paydo bo'lguncha davom etadi. Ikki ota-onadan foydalanishga asoslangan ko'payish usullari ko'proq "biologiya ilhomlangan" bo'lsa-da, ba'zi tadqiqotlar ortiq ikki "ota-onalar" yuqori sifatli xromosoma ishlab, deb taklif qiladi.Ushbu jarayonlar oxir-oqibat xromosomalarning keyingi avlod populyatsiyasiga olib keladi, bu dastlabki avloddan farq qiladi. Odatda, aholi uchun ushbu protsedura bilan o'rtacha jismoniy tayyorgarlik oshadi, chunki naslchilik uchun faqat birinchi avlodning eng yaxshi organizmlari tanlanadi va kamroq mos keladigan echimlarning ozgina qismi tanlanadi. Ushbu kamroq mos echimlar ota-onalarning genetik hovuzida genetik xilma-xillikni ta'minlaydi va shuning uchun keyingi avlod bolalarining genetik xilma-xilligini ta'minlaydi. Ushbu jarayonlar oxir-oqibat xromosomalarning keyingi avlod populyatsiyasiga olib keladi, bu dastlabki avloddan farq qiladi. Odatda, aholi uchun ushbu protsedura bilan o'rtacha jismoniy tayyorgarlik oshadi, chunki naslchilik uchun faqat birinchi avlodning eng yaxshi organizmlari tanlanadi va kamroq mos keladigan echimlarning ozgina qismi tanlanadi. Ushbu kamroq mos echimlar ota-onalarning genetik hovuzida genetik xilma-xillikni ta'minlaydi va shuning uchun keyingi avlod bolalarining genetik xilma-xilligini ta'minlaydi.Mutatsiyaga qarshi krossoverning ahamiyati bo'yicha fikr ikkiga bo'lingan. Fogel (2006) da mutatsiyaga asoslangan qidiruvning ahamiyatini qo'llab-quvvatlovchi ko'plab havolalar mavjud.Krossover va mutatsiya asosiy genetik operatorlar sifatida tanilgan bo'lsa-da, genetik algoritmlarda qayta guruhlash, kolonizatsiya-yo'q bo'lib ketish yoki migratsiya kabi boshqa operatorlardan foydalanish mumkin.
Kabi parametrlarni sozlashga arziydi mutatsiya ehtimoli, krossover ehtimoli va aholi soni ustida ishlanayotgan muammo sinfi uchun oqilona sozlamalarni topish. Juda kichik mutatsiya darajasi genetik driftga olib kelishi mumkin (bu ergodik bo'lmagan tabiatda). Rekombinatsiya darajasi juda yuqori bo'lib, genetik algoritmning erta yaqinlashishiga olib kelishi mumkin. Mutatsiya darajasi juda yuqori, agar elitist tanlov qo'llanilmasa, yaxshi echimlarning yo'qolishiga olib kelishi mumkin. Aholining etarli miqdori mavjud muammo uchun etarli genetik xilma-xillikni ta'minlaydi, ammo talab qilinganidan kattaroq qiymatga o'rnatilsa, hisoblash resurslarining isrof bo'lishiga olib kelishi mumkin.
Genetik algoritmlarni amalga oshirish oddiy, ammo ularning xatti- harakatlarini tushunish qiyin. Xususan, nima uchun ushbu algoritmlar amaliy muammolarga tatbiq etilganda tez-tez yuqori darajadagi echimlarni yaratishda muvaffaqiyat qozonishini tushunish qiyin. Genetik algoritmlarning Parallel tatbiq etilishi ikkita ta'mga ega. Dag'al donali parallel genetik algoritmlar kompyuter tugunlarining har birida populyatsiyani va tugunlar orasida shaxslarning migratsiyasini o'z ichiga oladi. Nozik taneli parallel genetik algoritmlar har bir protsessor tugunida tanlash va ko'paytirish uchun qo'shni shaxslar bilan ishlaydigan shaxsni qabul qiladi. Onlayn optimallashtirish muammolari uchun genetik algoritmlar kabi boshqa variantlar fitnes funktsiyasida vaqtga bog'liqlik yoki shovqinni keltirib chiqaradi. 1980-yillarning oxirida General Electric dunyodagi birinchi genetik algoritm mahsulotini sotishni boshladi, a asosiy ramka-sanoat jarayonlari uchun mo'ljallangan asboblar to'plam yilda 1989, Axcelis, Inc. ozod Evolver, ish stoli kompyuterlar uchun dunyodagi birinchi tijorat GA mahsulot. The Nyu- York Tayms texnologiya yozuvchisi jon Markoff yozgan 1990 yilda Evolver haqida va u 1995 yilgacha yagona interaktiv tijorat genetik algoritmi bo'lib qoldi. Evolver 1997 yilda Palisade-ga sotilgan, bir nechta tillarga tarjima qilingan va hozirda uning 6-versiyasida. 1990 yildan boshlab, MATLAB uchta lotinsiz optimallashtirish evristik algoritmlarini (simulyatsiya qilingan tavlanish, zarralar to'dasini optimallashtirish, genetik algoritm) va ikkita to'g'ridan-to'g'ri qidirish algoritmlarini (simpleks qidirish, naqshlarni qidirish) qurdi.
Genetik algoritmni guruhlash (GGA) ning evolyutsiyasi GA bu erda fokus klassik gazdagi kabi alohida narsalardan elementlarning guruhlariga yoki kichik to'plamiga o'tkaziladi. Genetik algoritmlar tomonidan hal qilingan muammolarga quyidagilar kiradi: quyosh nurlarini quyosh kollektoriga o'tkazish uchun mo'ljallangan nometall, kosmosdagi radio signallarni qabul qilish uchun mo'ljallangan antennalar, kompyuter raqamlari uchun yurish usullari, murakkab oqim maydonlarida aerodinamik jismlarning optimal dizayni.