Genetik algoritmlar Reja
Download 69.23 Kb. Pdf ko'rish
|
Genetik algoritmlar
Genetik algoritmlar Reja: Genetik algoritmning hayoti va faoliyati Dasturiy ta'minotni ulash san'ati Dunyo va Apokalipsisning yaratilishi Muammoning yechimini shaxs shaklida qanday ifodalash Fitnes funktsiyasi Algoritm haqida qisqacha Global optimallashtirish Biologik talqin Genetik algoritmning hayoti va faoliyati Keling, uzoqdan boshlaylik. Muayyan muammolarni hal qilish kerak. Bizning maqsadimiz o'zgarishi mumkin bo'lgan harakatlarni topishdir Berilgan(muammolarning dastlabki shartlari) ichida Javob(maqsadli holat). Vaziyat oddiy bo'lsa va bunday muammoning yechimini mana shu matanlaringiz yordamida sharoitdan aniq hisoblash mumkin bo'lsa, yaxshi, bu erda bizning hiyla-nayranglarimiz bo'lmasa ham, hamma narsa yaxshi, biz sikildik, hammamiz tarqaldik. Masalan, kvadrat tenglamani yechishda javob (x1, x2 qiymatlari) biz hammamiz maktabda o'rgangan formulani qo'llash orqali boshlang'ich shartdan (a, b, c koeffitsientlari) olinadi. Va darslikda kerakli formula bo'lmasa, yanada qayg'uli holatda nima qilish kerak? Muammolardan birini hal qilish uchun aqliy hujumni sinab ko'rishingiz mumkin. Analitik tarzda. Raqamli usullar. Funktsiyalarni umidsiz sanab o'tish kuchi bilan. Bir muncha vaqt o'tgach, siz "o'z-o'zidan hal bo'lsa" orzusidagi talabani eshitasiz. . Atrof-muhitga ko'proq moslashgan (muammoni hal qilishga yaqinlashgan) alfa erkakka aylanadi, omon qoladi va kuchli avlod beradi. Butun umrini onlayn o'yinlar o'ynab o'tkazgan va muammoni hal qilishda muvaffaqiyat qozonishni bilmagan yutqazgan odamning nasl berish imkoniyati juda kichik. Genofond bu pimply o'rtoqlarning hissasidan tozalanadi va butun dasturlar jamiyati hal qilingan muammo uchun yorqin kelajak sari harakat qiladi. Xo'sh, umumiy ma'noda allaqachon tushunarli, endi siz nuances bilan shug'ullanishingiz kerak: birinchi navbatda, juftlik dasturlarini qanday tasavvur qilasiz? ikkinchidan, dasturlarning birinchi avlodini qayerdan olamiz? uchinchidan, biz jismoniy shaxslarning jismoniy tayyorgarligini qanday asosda aniqlaymiz va bu o'tishga qanday ta'sir qiladi? to'rtinchidan, algoritmni tugatish shartlari, bu orgiyani qachon to'xtatish kerakligi haqida qaror qabul qilish kerak Dasturiy ta'minotni ulash san'ati Dasturlarni kesib o'tish masalasi unchalik oddiy emas. Funktsiyalar, satrlar yoki o'zgaruvchilarning tasodifiy almashinuvi sizga yangi dastur emas, balki kompilyator / tarjimon tomonidan yuborilgan qo'rqinchli so'zlarning yog' oqimiga olib keladi. Ya'ni, dasturlarni kesib o'tish yo'lini topish kerak to'g'ri. Aqlli amakilar chiqish yo‘lini topdilar. Kompilyatorlarning tuzilishini o'rgangan aqlli o'g'il-qizlar ham allaqachon taxmin qilishgan. Ha, ha, bu sintaksis daraxti. Men zudlik bilan ishtiyoqimni pasaytiraman: soqolimiz hali unchalik qalin emas, shuning uchun biz eng oddiy dasturlardan foydalanamiz. Xohlaganlar dasturlashning mislsiz boyligi vodiysiga borishlari mumkin, ammo biz uchun hamma narsa oddiy - dastur ifodalardan iborat bo'lib, ular o'z navbatida ba'zi arit, o'zgaruvchilar va konstantalarga ega oddiy funktsiyalardan iborat. Har bir ifoda dastur tomonidan qaytarilgan qiymatlardan birini hisoblaydi. Masalan: kvadrat tenglamani yechishga urinayotgan (juda muvaffaqiyatli emas) ikkita ifodadan iborat individual dastur kvadrati: funktsiya kvadrati(a, b, c)( x1 = min(sin(b)*(a+1), 0); x2 = 3 + exp(log(b*a)); qaytish (x1, x2); ) Biz taqdimotga qaror qildik, endi saqlash bilan shug'ullanishimiz kerak. Aynan shu dasturlar atrofida hali ham ko'plab raqslar mavjud bo'lgani uchun, shu jumladan ularni tizimning bir qismidan ikkinchisiga o'tkazish (umuman olganda, bu mening holatimda, odatda, turli tillarda yozilgan), bizning shaxsimizni daraxt shaklida saqlash. unchalik qulay emas. Uni qulayroq ko'rsatish uchun (ideal holda, ba'zi chekli alifbolar ustidagi satrlar to'plami) bizning individual-daraxtlar to'plami kodlash / dekodlashni o'rganishi kerak. Bu daraxtga o'xshaydi, lekin unday emas Shunday qilib, biz daraxtni satr sifatida ko'rsatishimiz kerak. Bu erda bizga karva daraxtlarining kuchi yordam beradi. Boshlash uchun daraxtda topilishi mumkin bo'lgan funktsiyalar, o'zgaruvchilar va konstantalar to'plami haqida qaror qabul qilish kerak. O'zgaruvchilar va konstantalar daraxt barglariga mos keladi va terminallar deb ataladi, funktsiyalar - daraxtning qolgan (ichki) tugunlariga terminal bo'lmaganlar deyiladi. Funktsiyalar turli xil argumentlarga ega bo'lishi mumkinligiga ham e'tibor qaratish lozim, shuning uchun bizga bunday bilim kerak bo'ladi ("arnost", - bu so'z mutaxassislar og'zidan jimgina yugurdi). Natijada kodlash jadvali, masalan, bu: Bu yerda n, +, *, agar funksiyalar; 2 - doimiy; a va b o'zgaruvchilardir. Haqiqiy masalalarda jadval og'irroq, bunday to'plam bilan va kvadrat tenglamani yechish mumkin emas. Shuni ham yodda tutish kerakki, nolga bo'linmaslik va apokalipsisning boshqa stsenariylariga yo'l qo'ymaslik uchun barcha funktsiyalar haqiqiy raqamlarning butun to'plamida aniqlanishi kerak (yaxshi yoki vazifada qanday to'plamdan foydalansangiz). Aks holda, siz qorovulda o'tirishingiz, noldan logarifmlarni ushlashingiz va keyin u bilan nima qilishni aniqlab olishingiz kerak bo'ladi. Biz mag'rur odamlar emasmiz, bunday variantlarni hisobga olmaganda, biz oson yo'ldan boramiz. Biz eng issiq joyga - o'tish joyiga qaytamiz. Dasturni kesib o'tish operatsiyalari uchun quyidagi shartlarni qo'yamiz: birinchidan, ikkita kesishuvchi individlar ikkita nasl beradi (ya'ni populyatsiya soni doimiy); ikkinchidan, kesib o'tish natijasida avlodlar, ma'lum darajada, ikkala ota-onaning xususiyatlariga ega bo'lishi kerak (ya'ni, olma olma daraxtidan juda uzoqqa aylanmasligi kerak). Endi biz dastur qanday taqdim etilishini bilib oldik - bu satrlar yoki daraxtlar to'plamimi. Shunga ko'ra, ularni iplar yoki daraxtlar sifatida kesib o'tish mumkin. Daraxtlarni kesib o'tish - tasodifiy tanlangan novdalar almashinuvi. String kesishish bir necha usullar bilan amalga oshirilishi mumkin: bir nuqtali rekombinatsiya (bo'lak-bo'lak yopishtirish), ikki nuqtali rekombinatsiya, elementlarni elementlar almashinuvi va boshqalar. Ularni qo'shimchali iboralar bilan uzun murakkab jumlalar bilan tasvirlash mumkin, lekin diagrammaga bir qarash. nima ekanligini tushunish uchun etarli: Shuni ta'kidlash kerakki, rekombinatsiyada yopishtirish joylari tasodifiy tanlanadi, xuddi elementlarni elementlarning kesishishida bo'lgani kabi, almashinuv ma'lum bir ehtimollik bilan amalga oshiriladi. Daraxtlarni irsiyat nuqtai nazaridan kesib o'tish yanada istiqbolli ko'rinadi, ammo uni amalga oshirish qiyinroq. Keling, bir juft shaxslar o'rtasidagi munosabatlardan ijtimoiy asoslarga o'tamiz. Shaxslar avlodlarga bo'linadi. Yangi avlod oldingi avlod farzandlaridan iborat. Ma’lum bo‘lishicha, hozirgi o‘g‘il-qiz avlodi, ota va ona avlodi, bobo-buvi, buvilar va hokazolar, nol avlodgacha – barcha g‘ururli insonlarning avlodlari bor ekan. Yangi avlodning har bir shaxsi tug'ilgandan keyin muammoni hal qilishga harakat qiladi, uning harakatlari qandaydir ilohiy fitnes funktsiyasi bilan baholanadi va o'spirinning faoliyatini baholashga qarab, shaxs nasl berish, ya'ni nasl berish uchun ba'zi imkoniyatlarga ega bo'ladi. nasl berish uchun tanlangan avlodning eng yaxshi vakillari sinfi. Bizning dunyomiz shafqatsiz va shafqatsizdir va distopiyaning barcha qonunlariga ko'ra (yoki Fyurerning g'oyalariga ko'ra, siz xohlaganingizcha) befoyda nafaqaxo'r ota-onalar farzand ko'rish missiyasini tugatgandan so'ng, gaz vagonida sayohatga chiqishadi. , er-xotin farzandlari uchun yashash joyini bo'shatish. Bolalar ota-onalari izidan boradilar, shuning uchun avloddan-avlodga. Juftlashtirish kvotalari bilan bog'liq bo'lgan bir xil fitnes funktsiyasi (yoki fitnes funktsiyasi) shaxsning muammoni hal qilish qobiliyatini adekvat baholashi va ushbu moslikning raqamli ifodasini berishi kerak (qiymat qanchalik katta bo'lsa, moslik shunchalik yaxshi bo'ladi). Masalan, bir xil kvadrat tenglama bo'lsa, bu individual dastur tomonidan hisoblangan x1, x2 almashtirilgan qiymatlar bilan tenglamaning chap tomonining qiymati nolga qanchalik yaqinligini o'lchovi bo'lishi mumkin. Juftlashtirish kvotalari bilan bog'liq bo'lgan bir xil fitnes funktsiyasi (yoki fitnes funktsiyasi) shaxsning muammoni hal qilish qobiliyatini adekvat baholashi va ushbu moslikning raqamli ifodasini berishi kerak (qiymat qanchalik katta bo'lsa, moslik shunchalik yaxshi bo'ladi). Masalan, bir xil kvadrat tenglama bo'lsa, bu individual dastur tomonidan hisoblangan x1, x2 almashtirilgan qiymatlar bilan tenglamaning chap tomonining qiymati nolga qanchalik yaqinligini o'lchovi bo'lishi mumkin. Fitnes funktsiyasi avlodning har bir shaxsiga uning foydaliligini, yaroqliligini ko'rsatadigan ma'lum bir raqamni beradi. Bu qiymat tanlash (tanlash) protsedurasiga ta'sir qiladi: bu qiymat shaxs uchun qanchalik katta bo'lsa, kesishish uchun juftlikni (va hatto bir nechtasini) topish ehtimoli shunchalik yuqori bo'ladi. Amalda, avlodning barcha shaxslari uchun yaroqlilikni hisoblab chiqqandan so'ng, biz ushbu qiymatlarni normallashtiramiz (shunday qilib, jismoniy shaxslarning yaroqlilik yig'indisi 1 ga teng bo'ladi) va har bir o'pish joylari uchun juda ko'p (tasodifiy raqam) tashlanadi. 0 dan 1 gacha), bu omadlini aniqlaydi. Alfa erkak bir nechta o'rindiqlarga ega bo'lishi mumkin, yutqazgan hech narsa olmaydi va Pamela bilan 1994 yildagi eskirgan kalendar bilan yolg'iz qoladi. Ushbu tanlov usuli "ruletni tanlash" deb ataladi va sxematik tarzda u quyidagicha ko'rinadi: Tanlashning boshqa usullari ham mavjud, ammo ularning barchasi umumiy qoidaga amal qiladi: odam qanchalik ko'p jismoniy tayyorgarlikka ega bo'lsa, u kesib o'tishda shunchalik ko'p ishtirok etishi kerak. Shuningdek, jarayon elitizm variantini ham o'z ichiga olishi mumkin, bunda avlodning eng yaxshi vakili Vatan oldidagi xizmatlari uchun qo'shimcha hayot yillari ko'rinishidagi mukofot oladi: u o'zgarmasdan keyingi avlodga o'tadi, garchi u bolalarni bolalarga aylantira oladi. parallel. Bu bizga juda yaxshi yechimni yo'qotmaslikka imkon beradi, bu o'tish vaqtida yo'q qilinishi mumkin. Bu erda biz mutatsiyani ham eslatib o'tamiz. Ushbu operatsiya tasodifiy ravishda kichik bir ehtimollik bilan shaxsning bir qismini o'zgartiradi, bu genofondni diversifikatsiya qilish imkonini beradi. Foydali narsa, to'satdan bunday mutatsiya laktoza parchalanishiga yordam beradi! Va agar yo'q bo'lsa va yana bir qo'l ortiqcha bo'lsa, unda kunlaringiz oxirigacha u bilan azob cheking, nasl berish hali ham etarli imkoniyat emas Dunyo va Apokalipsisning yaratilishi Biz nasldan naslga qanday o'tishni bilib oldik, endi keyingi savol "asosiy sabab nima edi, hammasi qanday boshlandi?". Sizning bu dunyongizdan farqli o'laroq, biz bunday narsalarni tushuntirish uchun "katta portlash" yoki "7 kun" kabi hiyla-nayranglarni o'ylab topishimiz shart emas. Bu erda javob juda aniq - barchasi tasodifiy yaratilgan nol avloddan boshlangan. Ha, ha, biz tasodifiy ravishda satrlarni/daraxtlarni yaratamiz. Yagona talab - bu shaxsning to'g'riligi va uning qanchalik nuqsonli ekanligi hech kimni qiziqtirmaydi, tanlov o'z ishini qiladi. Bizning dunyomiz bizga kerak bo'lgan vaqtgacha mavjud. Biz yoki bizni qoniqtiradigan fitnes uchun barni o'rnatamiz va etarlicha salqin shaxs paydo bo'lganda, biz jarayonni to'xtatamiz yoki avlod shaxslari bir-biridan qanchalik farq qilishini tekshiramiz. Agar butun avlod bir xil egizaklardan iborat bo'lsa, unda keyingi juftlashish qo'zg'alishlari genofondga hech qanday yangilik bermaydi va bitta mutatsiyaga umid qilish soddalikdir. Vaqt chegarasini ham belgilashingiz mumkin. Keling, ushbu ajoyib so'zda to'xtab, orqaga qaraymiz (yaxshi, yuqoriga). Xulosa qilib aytganda, genetik algoritm quyidagicha ko'rinadi: Biz muammoning yechimini genetik algoritm misolida ko'rsatishni o'rganamiz - ba'zi alifbolar bo'yicha belgilangan uzunlik ro'yxati. Shundan so'ng, biz jismoniy shaxslarni baholay oladigan va tasodifiy nol avlodni yaratadigan fitnes funksiyasini tanlaymiz. Bu erda erkin sevgining aylanishi boshlanadi: avlod shaxslarining jismoniy tayyorgarligi hisoblab chiqiladi, bu ma'lumotlarga ko'ra juftliklar hosil bo'ladi (yutqazganlar tashqariga chiqariladi va alfa erkaklar bir juft bilan cheklanmaydi), qolgan juftlik tug'iladi. bir juft bola (mutatsiya ularga ham tegishli) va qo'llarini o'zlariga qo'yishadi. Bu tanlangan kishi topilmaguncha yoki o'zgarishlar bizni xursand qilishni to'xtatmaguncha yoki biz hamma narsadan charchamaguncha davom etadi. Xo'sh, sxemasiz qanday qilishim mumkin: Qo‘yilgan biror masalani EHMda yechish uchun, avval uning matematik modelini, keyin algoritmini va programmasini tuzish kerak bo‘ladi. Bu uchlikda algoritm bloki muhim ahamiyatga ega. Algoritm bu oldimizga qo‘yilgan masalani yechish zarur bo‘lgan amallar ketma-ketligidir. Algoritm so‘zi va tushunchasi IX asrda yashab ijod etgan buyuk alloma Muhammad al-Xorazmiy nomi bilan uzviy bog‘liq. Algoritm so‘zi Al-Xorazmiy nomini Yevropa olimlari tomonidan buzib talaffuz qilinishidan yuzaga kelgan. Al- Xorazmiy birinchi bo‘lib o‘nlik sanoq sistemasining tamoyillarini va undagi to‘rtta amallarni bajarish qoidalarini asoslab bergan. Genetik algoritmlar evolyutsion algoritmlarning eng taniqli variantlaridir. Ular eng avvalo turli kombinatsiyali va optimizatsiyali masalalarni yechish vositalaridir. Data Mining ning standart instrumental yig`malariga xam kiradi. Genetik algoritmlarni tuzish asosiy bazasi bo`lib biologik evolyutsiya modeli va tasodifiy izlash metodlari xisoblanadi; irsiylik, o`zgaruvchanlik va tirik tabiatda tabiiy tanlash mexanizmlari imitatsiyasi amalga oshiriladi. Genetik algoritmlar yechilayotgan masalaning maxsus kodlangan ma`lumotlari, elementar logik genlardan tarkib topgan xramasomalar bilan ishlaydi. Bu kombinatsiyalar ko`pchiligi xromosomalar populyatsiyalari deb ataladi. Optimal yechimni izlash uchun xromosomalar qarama-qarshiligi usuli, sifat ko`rsatkichini xromosomalar qatori qimmatini belgilovchi xayotchanlik funksiyasi kiritiladi. Genetik algoritm hamma ish masalaning yechimi bo`luvchi, maksimal xayotchan qatorlarni topishga yo`naltirilgan. Populyatsiya reproduktsiya, o`zgaruvchanlik va genetik kompozitsiya muolajalari yordamida qayta ishlanadi. Bular ichidagi muolaja individual xromosomalarda tasodifiy mutatsiyalar, xromosomalar orasidagi genlar bilan almashinish, ota-ona xromosomalari genetik materiali rekombinatsiyasi. Mutatsiya shundan iboratki, unda tasodifiy tanlangan xromosomada bir yoki bir nechta genlar o`zgaradi, natijada xromosomaning xamma xususiyatlari o`zgaradi. Tanlash keyingi chatishish uchun ota-onalar juftini tanlashdan iborat bo`ladi. Muolaja bajarilish vaqtida evolyutsiyaning xar bir bosqichida yanada mukammallashgan individuallar populyatsiyasi paydo bo`ladi, berilgan sharoitlar bajarilmaguncha. Algoritmning asosiy xossalari Algoritmning 5-ta asosiy xossasi bor: Diskretlilik (Cheklilik). Tushunarlilik. Aniqlik. Ommaviylik. Natijaviylik. Diskretlilik (Cheklilik). Bu xossaning mazmuni algoritmlarni doimo chekli qadamlardan iborat qilib bo‘laklash imkoniyati mavjudligida. Ya’ni uni chekli sondagi oddiy ko‘rsatmalar ketma-ketligi shaklida ifodalash mumkin. Agar kuzatilayotgan jarayonni chekli qadamlardan iborat qilib qo‘llay olmasak, uni algoritm deb bo‘lmaydi. Tushunarlilik. Har bir ijrochining bajarishi mumkin bo‘lgan ko‘rsatmalar yoki buyruqlar majmuasi mavjud, u ijrochining ko‘rsatmalar tizimi (sistemasi) deyiladi. Demak, ijrochi uchun berilayotgan har bir ko‘rsatma ijrochining ko‘rsatmalar tizimiga mansub bo‘lishi lozim. Ko‘rsatmalarni ijrochining ko‘rsatmalar tizimiga tegishli bo‘ladigan qilib ifodalay bilishimiz muhim ahamiyatga ega. Masalan, quyi sinfning a’lochi o‘quvchisi "son kvadratga oshirilsin" degan ko‘rsatmani tushinmasligi natijasida bajara olmaydi, lekin "son o‘zini o‘ziga ko‘paytirilsin" shaklidagi ko‘rsatmani bemalol bajaradi, chunki u ko‘rsatma mazmunidan ko‘paytirish amalini bajarish kerakligini anglaydi. Natijaviylik. Har bir algoritm chekli sondagi qadamlardan so‘ng albatta natija berishi shart. Bajariladigan amallar ko‘p bo‘lsa ham baribir natijaga olib kelishi kerak. Chekli qadamdan so‘ng qo‘yilgan masala yechimga ega emasligini aniqlash ham natija hisoblanadi. Agar ko‘rilayotgan jarayon cheksiz davom etib natija bermasa, uni algoritm deb atay olmaymiz. Chegaralangan ko`p to`plam algoritmlari. 1960-yil o`rtalarida M.M. Bongard ma`lumotlarda logik qonuniyatlarni izlashda chegaralangan to`plam algoritmini tavsiya qildi. Shundan beri metod turli soxalardagi ko`plab masalalarni yechishda o`z samarasini ko`rsatdi. Bu algoritmlar ma`lumotlar guruxchalarida oddiy logik xolatlar kombinatsiyasi chastotasini xisoblaydi. Chegaralangan to`plamli realizatsiyalovchi yondoshish vakili bo`lib, WizSoft muassasasi WizWhy sistemasi xisoblanadi. Sistema ishlab chiqaruvchilari uning quyidagi xususiyatlarini ajratadilar: hamma if-then qonunlarini aniqlash, xar bir qonun uchun xatolik darajasini aniqlash; o`zgaruvchi sonli segmentatsiya eng yaxshisini aniqlash; xar bir belgining prognostik kuchini xisoblab chiqish; natijalarda odatdan tashqaridagi fenomerlarni aniqlash; olingan qonuniyatlarni bashoratlashda ishlatish; relevant qonunlar ro`yxatida bashoratni belgilash; bashorat xatosini aniqlash; xatolar qiymatini xisobga olib bashoratlash. Xulosa Sistemaning qo`shimcha xususiyati quyidagi: sistema prognnoziga subyektiv sabablar ta`sir qilmaydi; sistemani ishlatuvchilar amaliy statistika soxasidagi maxsus bilimlarga ega bo`lishlari shart emas, Data Mining boshqa usullaridan farqli xisoblashlar juda aniq va tez olinadi, boshlang`ich belgilarning qaysi intervallari qidirilayotgan if-then qonun uchun eng yaxshi bo`lishini avvaldan aniqlab bo`lmaydi. Yuqori natijaga da`vogar algoritm ishi birinchi qadami boshlang`ich belgilarni intervallarga bo`lishi maksimal kichikroq bo`lishi kerak. Bu albatta, asosan miqdoriy belgilarga taalluqlidir. If-then qonuniyatni qidirganda xar qanday sistemaning samaradorligi ma`lumotlar bazasini xar birini yozish qonuniyatining yaxshi vaqtini topish xususiyati bilan belgilanadi. Ba`zi olimlar fikricha bu xususiyat olingan ma`lumotlar sistemasini baxolashda asosiy kriteriy xisoblanadi. Foydalanilgan adabiyotlar www.genetikalgoritm.com www.algoritm.com www.ncbi.nlm.nih.gov Download 69.23 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling