Genetik algoritmlar reja

2.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.