Amaliy matematika” yo‘nalishi 21. 08-guruh talabasi Mamasodiqova Mubina Sattorali qizining

Genetik algoritmlar

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.