Genetik algoritmlar

Genetik algoritmlar
Tabiiy tanlanishga o'xshab "rivojlanayotgan" kompyuter dasturlari hatto ularni yaratuvchilar to'liq tushunmasa ham, murakkab muammolarni hal qila oladi.
Jon H. Holland
Tirik organizmlar muammoni mukammal hal qiluvchilardir. Ular eng yaxshi kompyuter dasturlarini sharmanda qiladigan ko'p qirralilikni namoyish etadilar. Bu kuzatish, ayniqsa, algoritm ustida bir necha oylar yoki yillar davomida intellektual kuch sarflashi mumkin bo'lgan kompyuter olimlarini hayratda qoldiradi, organizmlar esa o'z qobiliyatlari bilan evolyutsiya va tabiiy tanlanishning aniq yo'naltirilmagan mexanizmi orqali paydo bo'ladi.
Pragmatik tadqiqotchilar evolyutsiyaning ajoyib kuchini hasad qilishdan ko'ra taqlid qilinadigan narsa deb bilishadi. Tabiiy tanlanish dasturiy ta'minotni loyihalashdagi eng katta to'siqlardan birini yo'q qiladi: muammoning barcha xususiyatlarini va ularni hal qilish uchun dastur bajarishi kerak bo'lgan harakatlarni oldindan belgilash. Evolyutsiya mexanizmlaridan foydalangan holda, tadqiqotchilar hech kim ularning tuzilishini to'liq tushuna olmasa ham, muammolarni hal qiladigan dasturlarni "ko'paytirish" mumkin. Darhaqiqat, bu genetik algoritmlar reaktiv dvigatellar kabi murakkab tizimlarni loyihalashda yutuqlarga erishish qobiliyatini allaqachon namoyish etgan.
Genetik algoritmlar muammoning potentsial yechimlarini an'anaviy dasturlarga qaraganda ko'proq o'rganishga imkon beradi. Bundan tashqari, tadqiqotchilar yaxshi tushunilgan sharoitlarda dasturlarning tabiiy tanlanishini o'rganar ekan, ular erishgan amaliy natijalar tabiat dunyosida hayot va aqlning qanday rivojlanishi tafsilotlari haqida ma'lumot berishi mumkin.
Ko'pgina organizmlar ikkita asosiy jarayon orqali rivojlanadi: tabiiy tanlanish va jinsiy ko'payish. Birinchisi, populyatsiyaning qaysi a'zolari omon qolishi va ko'payishini aniqlaydi, ikkinchisi esa ularning avlodlari genlari o'rtasida aralashish va rekombinatsiyani ta'minlaydi. Spermatozoidlar va tuxumdonlar birlashganda, mos keladigan xromosomalar bir-biriga to'g'ri keladi va keyin ularning uzunligi bo'ylab kesib o'tadi va shu bilan genetik material almashadi. Bunday aralashtirish jonzotlarning tez rivojlanishiga imkon beradi, agar har bir nasl oddiygina bitta ota-onaning genlarining nusxasini o'z ichiga olgan bo'lsa, vaqti-vaqti bilan mutatsiya bilan o'zgartirilgan. (Garchi bir hujayrali organizmlar juftlashish bilan shug'ullanmasalar ham, odamlar bu haqda o'ylashni yaxshi ko'radilar, lekin ular genetik material almashadilar va ularning evolyutsiyasini o'xshash shartlar bilan tasvirlash mumkin.)
Tanlash oddiy: agar organizm yirtqichni tanib, qochib ketish kabi ba'zi bir fitnes sinovlaridan o'ta olmasa, u o'ladi. Shunga o'xshab, kompyuter olimlari yomon ishlaydigan algoritmlarni yo'q qilishda unchalik qiyin emas. Agar dastur raqamlarni o'sish tartibida tartiblashi kerak bo'lsa, masalan, dastur chiqishidagi har bir yozuv oldingisidan kattaroq yoki yo'qligini tekshirish kerak.
Odamlar ming yillar davomida yaxshiroq ekinlar, poyga otlari yoki manzarali atirgullar etishtirish uchun chatishtirish va seleksiyadan foydalanganlar. Biroq, bu tartiblarni kompyuter dasturlarida ishlatish uchun tarjima qilish unchalik oson emas. Asosiy muammo - DNK inson yoki sichqonchaning tuzilishini aks ettirganidek, turli xil dasturlarning tuzilishini aks ettira oladigan "genetik kod" ni yaratishdir. Masalan, FORTRAN dasturining matnini birlashtirish yoki mutatsiyaga solish, ko'p hollarda FORTRAN dasturini yaxshiroq yoki yomonroq hosil qiladi, lekin umuman dastur bo'lmaydi.
1950-yillarning oxiri va 1960-yillarning boshlarida kompyuter fanlari va evolyutsiyani birlashtirishga qaratilgan birinchi urinishlar muvaffaqiyatsiz yakunlandi, chunki ular oʻsha davrdagi biologik matnlardagi urgʻuga amal qilgan va yangi gen birikmalarini yaratish uchun juftlashish oʻrniga mutatsiyaga tayangan. Keyin 1960-yillarning boshida Berklidagi Kaliforniya universitetidan Hans J. Bremermann juftlashishning bir turini qo'shdi: naslning xususiyatlari ikkita ota-onadagi tegishli genlarni yig'ish orqali aniqlandi. Biroq, bu juftlashtirish jarayoni cheklangan edi, chunki u faqat mazmunli tarzda qo'shilishi mumkin bo'lgan xususiyatlarga nisbatan qo'llanilishi mumkin edi.
Shu vaqt ichida men moslashuvning matematik tahlillarini o'rganib chiqdim va genlar guruhlarining juftlash orqali rekombinatsiyasi evolyutsiyaning muhim qismi ekanligiga amin bo'ldim. 1960-yillarning oʻrtalariga kelib men juftlashish va mutatsiya orqali evolyutsiyaga juda mos keladigan genetik algoritmni ishlab chiqdim. Keyingi o'n yil ichida men har qanday kompyuter dasturining tuzilishini aks ettira oladigan genetik kodni yaratish orqali genetik algoritmlar ko'lamini kengaytirish ustida ishladim.
Natijada qoidalar to'plamidan iborat tasniflagich tizimi paydo bo'ldi, ularning har biri har safar o'z shartlari ma'lum bir ma'lumot bilan qondirilganda ma'lum harakatlarni bajaradi. Shartlar va harakatlar qoidalarni kiritish va chiqarishda o'ziga xos xususiyatlarning mavjudligi yoki yo'qligiga mos keladigan bit satrlari bilan ifodalanadi. Mavjud bo'lgan har bir xususiyat uchun satr tegishli pozitsiyada 1 ni o'z ichiga oladi va yo'q bo'lgan har bir xususiyat uchun u 0 ni o'z ichiga oladi. Misol uchun, tan olingan itlar uchun klassifikator qoidasi 1 ni o'z ichiga olgan qator sifatida kodlanishi mumkin. "sochli", "slobbers", "barks", "sodiq" va "chases tayoq" so'zlariga mos keladigan bitlar va "metall", "urdu tilida gapiradi" va "kredit kartalariga ega" so'zlariga mos keladigan bitlar uchun 0. Aniqroq aytganda, dasturchi eng oddiy, eng ibtidoiy xususiyatlarni tanlashi kerak, shunda ular 20 ta savol o'yinidagi kabi birlashtirilishi mumkin. ob'ektlar va vaziyatlarning keng doirasini tasniflash uchun.
Garchi ular tan olishda ustun bo'lsa-da, bu qoidalar, shuningdek, ularning chiqishidagi bitlarni tegishli xatti-harakatlarga bog'lash orqali harakatlarni boshlash uchun ham amalga oshirilishi mumkin [69-betdagi rasmga qarang]. FORTRAN LISP kabi standart dasturlash tilida yozilishi mumkin bo'lgan har qanday dastur tasniflagich tizimi sifatida qayta yozilishi mumkin.

Muayyan muammoni hal qiladigan klassifikator qoidalarini ishlab chiqish uchun bitta oddiy 1 va 0 dan iborat tasodifiy qatorlar populyatsiyasidan boshlanadi va har bir qatorni natija sifatiga qarab baholaydi. Muammoga qarab, fitnes o'lchovi biznesning rentabelligi, o'yinning foydasi, xatolik darajasi yoki boshqa mezonlar bo'lishi mumkin. Yuqori sifatli simlar mate; sifatsizlari nobud bo'ladi. Avlodlar o'tishi bilan takomillashtirilgan echimlar bilan bog'liq satrlar ustunlik qiladi. Bundan tashqari, juftlashish jarayoni bu qatorlarni doimiy ravishda yangi usullar bilan birlashtirib, yanada murakkab echimlarni yaratadi. Texnikaga olib keladigan muammolar turlari o'yin nazariyasida yangi strategiyalarni ishlab chiqishdan tortib murakkab mexanik tizimlarni loyihalashgacha bo'lgan turli xil muammolarni o'z ichiga oladi.

Genetik algoritmlar tilida qayta ko'rib chiqish, muammoning yaxshi echimini izlash - bu alohida ikkilik satrlarni qidirish. Barcha mumkin bo'lgan satrlar olamini xayoliy manzara deb hisoblash mumkin; vodiylar yomon echimlarni kodlaydigan satrlarning joylashishini belgilaydi va landshaftning eng yuqori nuqtasi mumkin bo'lgan eng yaxshi satrga mos keladi.

Yechim maydonidagi mintaqalarni, shuningdek, belgilangan joylarda 1 va 0 ga ega bo'lgan satrlarga qarab aniqlash mumkin, bu xarita koordinatalarining ikkilik ekvivalenti. Masalan, 1 bilan boshlanadigan barcha satrlar to'plami imkoniyatlar to'plamida mintaqani tashkil qiladi. Shunday qilib, 0 bilan boshlanadigan yoki to'rtinchi pozitsiyada 1, beshinchi pozitsiyada 0 va oltinchi pozitsiyada 1 va hokazo bo'lgan barcha satrlarni bajaring.

Bunday landshaftni o'rganishning an'anaviy usullaridan biri toqqa chiqishdir: tasodifiy nuqtadan boshlang va agar ozgina o'zgartirish sizning yechimingiz sifatini yaxshilasa, shu yo'nalishda davom eting; aks holda, fo qarama-qarshi yo'nalishda. Murakkab muammolar, ammo ko'plab yuqori nuqtalarga ega landshaftlarni yaratadi. Muammoli makonning o'lchamlari soni ortib borayotganligi sababli, qishloq tunnellar, ko'priklar va undan ham murakkab topologik xususiyatlarni o'z ichiga olishi mumkin. To'g'ri bolani topish yoki hatto qaysi yo'ldan borishni aniqlash tobora qiyinlashib bormoqda. Bundan tashqari, bunday qidiruv joylari odatda juda katta. Agar og'riqlar o'yinidagi har bir harakat, masalan, o'rtacha 10 ta alternativga ega bo'lsa va odatdagi o'yin har tomondan 30 ta harakatdan iborat bo'lsa, unda shaxmat o'ynash uchun 1060 ga yaqin strategiya mavjud (ularning aksariyati yomon).
O’zgarish haqiqiy organizmlar va genetik algoritmlar uchun o’zgarishning asosiy mexanizmi bo’ladi.
Xromasomalar bir qatorda tiziladi va o’zgarish nuqtasidan tashqarida o’zlarining genetik kodlarini almashishadi.

Genetik algoritmlar bu manzara ustidan to'r tashlaydi. Rivojlanayotgan populyatsiyadagi qatorlarning ko'pligi uni bir vaqtning o'zida ko'plab mintaqalarda namuna oladi. Shunisi e'tiborga loyiqki, genetik algoritmning turli hududlardan namuna olish tezligi to'g'ridan-to'g'ri hududlarning o'rtacha "balandligi" ga to'g'ri keladi - ya'ni o'sha yaqin joyda yaxshi yechim topish ehtimoli.

Genetik algoritmlarning e'tiborini yechim maydonining eng istiqbolli qismlariga qaratishning ajoyib qobiliyati ularning qisman yechimlarni o'z ichiga olgan qatorlarni birlashtirish qobiliyatining bevosita natijasidir. Birinchidan, kodlangan strategiyaning ishlashini aniqlash uchun populyatsiyadagi har bir qator baholanadi. Ikkinchidan, yuqori darajali satrlar juftlashadi. Ikki satr bir qatorda, torlar bo'ylab nuqta tasodifiy tanlanadi va shu nuqtaning chap tomonidagi qismlar ikkita nasl hosil qilish uchun almashtiriladi: biri o'zaro faoliyat nuqtasigacha birinchi qatorning belgilarini va undan keyingi ikkinchisinikini o'z ichiga oladi. , ikkinchisi esa to'ldiruvchi xochni o'z ichiga oladi. Ikki gameta zigota hosil qilish uchun uchrashganda biologik xromosomalar bir-birini kesib o'tadi va shuning uchun genetik algoritmlardagi kesishish jarayoni aslida uning biologik modelini taqlid qiladi. Nasl ota-ona satrlarini almashtirmaydi; Buning o'rniga ular har bir avlodda tashlab yuboriladigan past yaroqli satrlarni almashtiradilar, shunda umumiy populyatsiya bir xil darajada qoladi.
Uchinchidan, mutatsiyalar satrlarning kichik qismini o'zgartiradi: taxminan har 10 000 belgidan bittasi 0 dan 1 gacha yoki aksincha. Mutatsiyaning o'zi odatda yechim izlashni ilgari surmaydi, lekin keyingi evolyutsiyaga qodir bo'lmagan yagona populyatsiyaning rivojlanishidan sug'urta qiladi.
Genetik algoritm yechim maydonining yuqori daromadli yoki "maqsadli" mintaqalaridan foydalanadi, chunki ko'payish va kesishishning ketma-ket avlodlari bu hududlarda ko'payib borayotgan qatorlarni hosil qiladi. Algoritm ota-onalar sifatida eng mos satrlarni qo'llab-quvvatlaydi va shuning uchun o'rtachadan yuqori satrlar (maqsadli hududlarga to'g'ri keladi) keyingi avlodda ko'proq naslga ega bo'ladi.
Darhaqiqat, ma'lum bir mintaqadagi qatorlar soni ushbu mintaqaning yaroqliligining statistik bahosiga mutanosib ravishda oshadi. Har bir mintaqaning o'rtacha yaroqliligini baholash uchun statistik minglab yoki millionlab mintaqalardan o'nlab namunalarni baholashi kerak. Genetik algoritm bir xil natijaga ancha kamroq qatorlar va deyarli hech qanday hisoblash bilan erisha oladi.
Bu hayratlanarli xatti-harakatning kaliti shundaki, bitta satr uning bitlari paydo bo'lgan barcha hududlarga tegishlidir. Masalan, 11011001 qatori 11****** (bu yerda * bit qiymati aniqlanmaganligini bildiradi), 1******1, **0**00* va boshqalarning aʼzosi hisoblanadi. . Eng katta mintaqalar - ko'plab noma'lum bitlarni o'z ichiga olganlar - odatda populyatsiyadagi barcha qatorlarning katta qismi tomonidan tanlanadi. Shunday qilib, bir necha ming qatorli populyatsiyani boshqaradigan genetik algoritm aslida juda ko'p sonli hududlarni tanlaydi. Bu yashirin parallellik genetik algoritmga boshqa muammolarni hal qilish jarayonlaridan markaziy ustunlikni beradi.

Krossover yashirin parallelizm ta'sirini murakkablashtiradi. Genetik algoritmdagi satrlarni kesib o'tishning maqsadi bir qatorni ketma-ket avlodlarda qayta-qayta sinab ko'rishdan ko'ra maqsadli hududlarning yangi qismlarini sinab ko'rishdir. Ammo bu jarayon naslni bir mintaqadan boshqasiga “ko‘chirishi” ham mumkin, bu esa turli hududlarning tanlab olish tezligining qat’iy mutanosiblikdan o‘rtacha fitnesga qarab ketishiga olib keladi. Bu ketish evolyutsiya tezligini sekinlashtiradi.

Ikki qatorning naslining ota-onasi hududini tark etishi ehtimoli mintaqani belgilaydigan 1 va 0 orasidagi masofaga bog'liq. Misol uchun, 10**** ni tanlaydigan qatorning avlodi, agar krossover satrning ikkinchi pozitsiyasidan boshlangan bo'lsa, u mintaqadan tashqarida bo'lishi mumkin - oltita genni o'z ichiga olgan qator uchun beshdan bir imkoniyat. (Agar bir xil qurilish bloki 1000 gendan iborat bo'lsa, 999 tadan bittasi xavfini tug'diradi.) 1****1 mintaqasidan namuna olgan olti genli qatorning avlodi ota-onasi hududini tark etish xavfini tug'diradi. krossover qayerda sodir bo'lishidan qat'iy nazar.

Hududni belgilaydigan yaqin qo'shni 1 yoki 0 lar ixcham qurilish bloklari deb ataladi. Ular krossover buzilmagan holda omon qolishlari mumkin va shuning uchun ularni olib yuradigan torlarning o'rtacha yaroqliligiga mutanosib ravishda kelajak avlodlarga ko'payadi. Krossoverni o'z ichiga olgan ko'paytirish mexanizmi barcha hududlarni ularning yaroqliligiga mutanosib tezlikda tanlay olmasa ham, ixcham qurilish bloklari bilan belgilangan barcha hududlar uchun buni amalga oshirishda muvaffaqiyat qozonadi. Satrlar populyatsiyasidagi ixcham aniqlangan qurilish bloklari soni hanuzgacha satrlar sonidan ancha oshadi va shuning uchun genetik algoritm hali ham yashirin parallellikni namoyish etadi.

Qizig'i shundaki, tabiiy genetikada inversiya deb ataladigan operatsiya vaqti-vaqti bilan genlarni qayta tartibga soladi, shunda ota-onalarda bir-biridan uzoqda bo'lganlar avlodda bir-biriga yaqin joylashadi. Bu qurilish blokini yanada ixcham bo'lishi va krossover tomonidan kamroq parchalanishi uchun qayta belgilashni anglatadi. Agar qurilish bloki o'rtacha moslik darajasi yuqori bo'lgan hududni ko'rsatsa, u holda ixchamroq versiya avtomatik ravishda kamroq ixcham versiyani almashtiradi, chunki u nusxa ko'chirish xatosi tufayli bir nechta naslni yo'qotadi. Natijada, inversiyadan foydalanadigan moslashuvchan tizim foydali qurilish bloklarining ixcham versiyalarini topishi va afzal ko'rishi mumkin.

Genetik algoritmning yashirin parallelligi unga nisbatan bir nechta satrlarni manipulyatsiya qilishda qidiruv maydonida ko'p sonli hududlarni sinab ko'rish va ulardan foydalanish imkonini beradi. Yashirin parallelizm, shuningdek, genetik algoritmlarga chiziqli bo'lmagan muammolarni hal qilishga yordam beradi - ikkita alohida qurilish blokini o'z ichiga olgan qatorning mosligi har bir qurilish blokiga tegishli bo'lgan fitnes yig'indisidan ancha katta (yoki ancha kichik) bo'lishi mumkin.

Chiziqli muammolar qidiruv maydonini qisqartiradi, chunki satrning bir pozitsiyasida 1 yoki 0 mavjudligi boshqa joyda 1 yoki 0 mavjudligi bilan bog'liq bo'lgan muvofiqlikka ta'sir qilmaydi. Masalan, 1000 ta raqamli satrlar maydoni 31000 dan ortiq imkoniyatlarni o'z ichiga oladi, lekin agar muammo chiziqli bo'lsa, algoritm faqat har bir pozitsiyada 1 yoki 0 ni o'z ichiga olgan satrlarni, jami atigi 2000 ta imkoniyatni o'rganishi kerak.

Muammo chiziqli bo'lmaganda, qiyinchilik keskin ortadi. Masalan, *0*** va **1*** bilan bogʻliq boʻlgan fitnes aholi oʻrtacha koʻrsatkichidan past boʻlsa-da, masalan, *01** mintaqasidagi simlarning oʻrtacha yaroqliligi aholi sonidan yuqori boʻlishi mumkin. Nonlineerlik bitta 1 yoki 0 dan iborat foydali qurilish bloklari etarli bo'lmaydi degani emas. Bu xususiyat, o'z navbatida, imkoniyatlar portlashiga olib keladi: uzunligi 20 bit bo'lgan barcha satrlar to'plami uch milliarddan ortiq qurilish bloklarini o'z ichiga oladi. Yaxshiyamki, yashirin parallelizmdan hali ham foydalanish mumkin. Bir necha ming qatorli populyatsiyada ko'plab ixcham qurilish bloklari 100 yoki undan ortiq satrlarda paydo bo'ladi, bu yaxshi statistik namunani taqdim etish uchun etarli. O'rtachadan yuqori ko'rsatkichlarga erishish uchun nochiziqlilikdan foydalanadigan qurilish bloklari kelgusi avlodlarda avtomatik ravishda tez-tez ishlatiladi.

Chiziqli bo'lmaganlik bilan kurashishdan tashqari, genetik algoritm muammoni hal qilishning an'anaviy usullarini uzoq vaqt davomida to'xtatib qo'ygan jumboqni hal qilishga yordam beradi: tadqiqot va ekspluatatsiya o'rtasidagi muvozanatni saqlash. Shaxmat o'ynash uchun yaxshi strategiya topilsa, masalan, ushbu strategiyadan foydalanishga e'tibor qaratish mumkin. Ammo uning tanlovi yashirin xarajatlarga olib keladi, chunki ekspluatatsiya chinakam yangi strategiyalarni kashf qilishni qiyinlashtiradi. Yaxshilanishlar yangi, xavfli narsalarni bog'lashdan kelib chiqadi. Ko'pgina xatarlar muvaffaqiyatsizlikka uchraganligi sababli, qidiruv hozirgi zamonni kelajak uchun garovga qo'yish kerak bo'lgan darajada degradatsiyani o'z ichiga oladi, bu moslashadigan va o'rganadigan barcha tizimlar uchun klassik muammodir.

Genetik algoritmning to'siqga yondashuvi krossoverga aylanadi. Krossover qurilish blokini parchalash orqali foydalanishga xalaqit berishi mumkin bo'lsa-da, rekombinatsiya jarayoni qurilish bloklarini yangi kombinatsiyalar va yangi kontekstlarda sinovdan o'tkazadi. Krossover o'rtachadan yuqori bo'lgan hududlarning yangi namunalarini yaratadi, bu avvalgi namunalar tomonidan ishlab chiqarilgan taxminlarni tasdiqlaydi yoki rad etadi. Bundan tashqari, krossover qurilish blokini parchalab tashlaganida, u genetik algoritmga ilgari tanlanmagan hududlarni sinab ko'rish imkonini beradigan yangi blokni ishlab chiqaradi.

"Mahbusning dilemmasi" deb nomlanuvchi o'yin genetik algoritmning ekspluatatsiyaga qarshi kashfiyotni muvozanatlash qobiliyatini ko'rsatadi. Uzoq vaqt davomida o'rganilgan ushbu o'yin o'zining ikki o'yinchisiga "hamkorlik" va "qo'zg'alish" o'rtasidagi tanlovni taqdim etadi: agar ikkala o'yinchi ham hamkorlik qilsa, ikkalasi ham foyda oladi; agar bitta o'yinchi nuqsoni bo'lsa, defektor yuqori to'lov oladi va kooperator hech narsa olmaydi; agar ikkalasi ham nuqsonli bo'lsa, ikkalasi ham minimal foyda oladi [71-betdagi jadvalga qarang]. Misol uchun, agar A o'yinchisi hamkorlik qilsa va B o'yinchisi nuqsonli bo'lsa, A o'yinchisi hech qanday to'lovni olmaydi va B o'yinchisi besh balldan to'lov oladi.

Siyosatshunoslar va sotsiologlar “Mahbusning dilemmasi”ni o‘rganishdi, chunki u hamkorlikdagi qiyinchiliklarning oddiy, aniq misolini keltiradi. O'yin nazariyasi har bir o'yinchi boshqa o'yinchi keltirishi mumkin bo'lgan maksimal zararni minimallashtirishi kerakligini taxmin qiladi: ya'ni ikkala o'yinchi ham nuqsoni bo'lishi kerak. Shunga qaramay, ikki kishi birgalikda o'yinni qayta-qayta o'ynaganda, ular umumiy daromadlarini oshirish uchun bir-biri bilan hamkorlik qilishni o'rganadilar. Mahbusning dilemmasi uchun ma'lum bo'lgan eng samarali strategiyalardan biri bu "tat uchun tit" bo'lib, u hamkorlik qilishdan boshlanadi, ammo keyin boshqa o'yinchining oxirgi o'yiniga taqlid qiladi. Ya'ni, u keyingi safar buzilish bilan "jazolanadi", keyingi safar hamkorlik qilish orqali hamkorlikni mukofotlaydi.
Michigan universitetidan Robert Axlerod, Stefani Forest bilan hozir Nyu-Meksiko universitetida ishlagan holda, genetik algoritm tit-for-tat strategiyasini kashf qila oladimi yoki yo'qligini aniqlashga qaror qildi. Genetik algoritmni qo'llash birinchi navbatda mumkin bo'lgan strategiyalarni satrlarga tarjima qilishni talab qiladi. Oddiy usullardan biri keyingi javobni oxirgi uchta o'yin natijasiga asoslashdir. Har bir iteratsiya to'rtta mumkin bo'lgan natijaga ega va shuning uchun uchta o'yin ketma-ketligi 64 ta imkoniyatni beradi. 64-bitli qatorda har biri uchun bitta gen (yoki bit pozitsiyasi) mavjud. Birinchi gen, masalan, ketma-ket uchta o'zaro buzilish holatlariga ajratiladi. Har bir genning qiymati 1 yoki 0 ga teng bo'ladi, bu uning tegishli tarixiga afzal qilingan javob defektsiyaning hamkorlik ekanligiga bog'liq. Misol uchun, barcha 0 dan iborat 64 bitli satr barcha holatlarda nuqsonli strategiyani belgilaydi. Bunday oddiy o'yin uchun ham 264 (taxminan 16 kvadrillion) turli strategiyalar mavjud.

Axelrod va Forrest genetik algoritmni strategiyalarni ifodalovchi kichik tasodifiy qatorlar to'plami bilan ta'minladilar. Har bir torning yaroqliligi uning strategiyasining takroriy o'yinda olgan to'lovlarining o'rtacha ko'rsatkichi edi. Bu torlarning barchasi past fitnesga ega edi, chunki Mahbusning dilemmasini o'ynashning ko'pgina strategiyalari unchalik yaxshi emas. Tezda genetik algoritm tat uchun ekspluatatsiya qilingan titni topdi, ammo keyingi evolyutsiya qo'shimcha yaxshilanishlarni kiritdi. Genetik algoritm allaqachon yuqori darajada o'ynagan paytda kashf etilgan yangi strategiya "blef" bo'lishi mumkin bo'lgan o'yinchilarni ekspluatatsiya qildi - qochqinlarga qarshi qayta-qayta hamkorlik qilishga jalb qilindi. Ammo tarixda o'yinchini blöf qilish mumkin emasligi ko'rsatilganida, u "tit for tat" ga qaytdi.

Biologik evolyutsiya, albatta, bitta superindividni hosil qilish uchun emas, balki bir-biriga yaxshi moslashgan o'zaro ta'sir qiluvchi turlarni yaratish uchun ishlaydi. (Haqiqatan ham, biologik sohada eng yaxshi individ degan narsa yo'q.) Xuddi shunday, genetik algoritmdan o'zgartirishlar bilan nafaqat individual qoidalar yoki strategiyalar, balki quyidagilardan tashkil topgan klassifikator-tizim "organizmlar" evolyutsiyasini boshqarish uchun foydalanish mumkin. ko'p qoidalar. Yakka holda eng mos qoidalarni tanlash o'rniga, raqobatbardosh bosim qobiliyatlari ularni tashkil etuvchi qatorlarda kodlangan kattaroq tizimlarning evolyutsiyasiga olib kelishi mumkin.

Ushbu yuqori darajadagi evolyutsiyani qayta yaratish uchun asl genetik algoritmga bir nechta o'zgartirishlar kiritish kerak. Satrlar hali ham shart-harakat qoidalarini ifodalaydi va shartlari bajarilgan har bir qoida avvalgidek harakat hosil qiladi. Har bir qoidani ishlab chiqaradigan to'g'ri harakatlar soni bo'yicha baholash foydali o'zaro ta'sir qiluvchi qoidalar klasterlarini topish o'rniga individual "ustun qoidalar" evolyutsiyasiga yordam beradi. Qidiruvni o'zaro ta'sir qiluvchi qoidalarga yo'naltirish uchun tartib qoidalarni tizim harakatlarini nazorat qilish uchun raqobatlashishga majburlash orqali o'zgartiriladi. Shartlari bajarilgan har bir qoida, shartlari bajarilgan barcha boshqa qoidalar bilan raqobatlashadi va eng kuchli qoidalar tizim ushbu vaziyatda nima qilishini aniqlaydi.

Tizimning harakatlari muvaffaqiyatli natijaga olib keladigan bo'lsa, barcha g'alaba qozonish qoidalari mustahkamlanadi; aks holda ular zaiflashadi.

Ushbu usulni ko'rib chiqishning yana bir usuli - har bir qoida qatorini tasniflagich dunyosi haqidagi gipoteza sifatida ko'rib chiqish. Qoida faqat joriy vaziyatga mos kelishini "da'vo qilsa" raqobatga kiradi. Uning raqobatbardoshlik qobiliyati shu kabi muammolarni hal qilishda qanchalik hissa qo'shganiga bog'liq. Genetik algoritm davom etar ekan, kuchli qoidalar birlashadi va ota-onalarning qurilish bloklarini birlashtirgan avlod qoidalarini shakllantiradi. Eng zaif qoidalar o'rnini bosadigan bu nasllar ishonchli, ammo sinab ko'rilmagan gipotezani tashkil qiladi.

Qoidalar o'rtasidagi raqobat tizimni doimiy yangilik bilan ishlashning oqlangan usuli bilan ta'minlaydi. Agar tizim muayyan vaziyatga javob beradigan kuchli qoidalarga ega bo'lsa, bu uning ma'lum bir yaxshi tasdiqlangan gipotezaga ega ekanligini aytish bilan tengdir. Hayotni ota-onalariga qaraganda zaifroq boshlaydigan nasl qoidalari raqobatda g'alaba qozonishi va shart-sharoitlarni qondiradigan kuchli qoidalar bo'lmagan taqdirdagina tizimning xatti-harakatlariga ta'sir qilishi mumkin - boshqacha qilib aytganda, tizim nima qilishni bilmaydi. Agar ularning harakatlari yordam bersa, omon qoladi; bo'lmasa, ular tez orada almashtiriladi. Shunday qilib, nasl yaxshi amaliyotda qo'llaniladigan vaziyatlarda tizimning harakatlariga aralashmaydi, balki yangi sharoitlarda nima qilish kerakligi haqida gipoteza sifatida qanotlarda muloyimlik bilan kutishadi.

Raqobatni shu tarzda qo'shish klassifikator tizimining evolyutsiyasiga kuchli ta'sir qiladi. Tizim ishlay boshlaganidan ko'p o'tmay, u oddiy shartlarga ega qoidalarni rivojlantiradi - keng ko'lamli vaziyatlarni xuddi ular bir xildek ko'rib chiqadi. Tizim batafsil ma'lumot bo'lmaganda nima qilish kerakligini ko'rsatuvchi standart kabi qoidalardan foydalanadi. Standart qoidalar faqat qo'pol kamsitishlarni keltirib chiqarganligi sababli, ular ko'pincha noto'g'ri va shuning uchun kuchga ega emas. Tizim tajriba orttirgan sari, ko'payish va kesishish yanada murakkab, o'ziga xos qoidalarni ishlab chiqishga olib keladi, ular tezda muayyan holatlarda xatti-harakatlarni belgilash uchun etarlicha kuchli bo'ladi.

Oxir-oqibat, tizim ierarxiyani rivojlantiradi: quyi darajadagi istisno qoidalari qatlamlari ko'p holatlarni hal qiladi, ammo ierarxiyaning yuqori darajasidagi standart qoidalar batafsil qoidalarning hech biri uning shartlarini qondirish uchun etarli ma'lumotga ega bo'lmaganda kuchga kiradi. Bunday standart ierarxiyalar tizimni haddan tashqari batafsil variantlarda qolib ketishining oldini olish bilan birga, yangi vaziyatlarda tegishli tajribani keltirib chiqaradi.

Rivojlanayotgan klassifikator tizimlarini doimiy yangilik bilan ishlashga mohir qiladigan bir xil xususiyatlar, shuningdek, ma'lum bir harakat uchun to'lov faqat harakat qilinganidan keyin ko'p vaqt o'tishi mumkin bo'lgan vaziyatlarni hal qilishda yaxshi ishlaydi. Masalan, shaxmat o'yinining dastlabki harakatlari mag'lubiyatning keyingi g'alabasi uchun zamin yaratishi mumkin.

Bunday uzoq muddatli maqsadlar uchun klassifikator tizimini o'rgatish uchun dasturchi har safar vazifani bajarganida tizimga to'lov beradi. Muvaffaqiyat uchun kredit (yoki muvaffaqiyatsizlik uchun ayb) ierarxiya bo'ylab individual qoidalarni mustahkamlash (yoki zaiflashtirish) uchun tarqalishi mumkin, hatto ularning harakatlari natijaga faqat uzoqdan ta'sir qilgan bo'lsa ham. Ko'p avlodlar davomida tizim keyinchalik to'lovlar uchun zamin yaratish uchun ilgari amal qiladigan qoidalarni ishlab chiqadi. Shuning uchun u o'z harakatlarining oqibatlarini oldindan bilish qobiliyatiga ega bo'ladi.

Genetik algoritmlar endi turli xil kontekstlarda sinovdan o'tkazildi. Misol uchun, Illinoys universitetidan Devid E. Goldberg janubi-g'arbdan shimoli-sharqqa tabiiy gazni olib o'tuvchiga asoslangan gaz quvurlari tizimini boshqarishni o'rganadigan algoritmlarni ishlab chiqdi. Quvurlar majmuasi ko'plab tarmoqlardan iborat bo'lib, ularning barchasi turli hajmdagi gazni tashiydi; mavjud bo'lgan yagona boshqaruv - bu quvur liniyasining ma'lum bir tarmog'idagi bosimni oshiradigan kompressorlar va saqlash tanklariga va undan gaz oqimini tartibga solish uchun klapanlar. Manipulyatsiya qiluvchi klapanlar yoki kompressorlar va liniyalardagi haqiqiy bosim o'zgarishi o'rtasidagi katta kechikish tufayli muammoning analitik yechimi yo'q va inson boshqaruvchilari, xuddi Goldberg algoritmi kabi, shogirdlik orqali o'rganishlari kerak.

Goldberg tizimi nafaqat gazga bo'lgan talabni amalda erishilgan xarajatlar bilan taqqoslabgina qolmay, balki quvurda teshilgan teshiklarga to'g'ri javob berishga qodir bo'lgan standart qoidalar ierarxiyasini ham ishlab chiqdi (ko'pincha noto'g'ri buldozer pichog'ida sodir bo'ladi). ). Kembrijdagi Tica Associates kompaniyasidan Lourens Devis aloqa tarmoqlarini loyihalashda shunga o'xshash usullardan foydalangan; uning dasturiy ta'minotining maqsadi - uzatish liniyalari va ularni o'zaro bog'laydigan kalitlarning minimal soni bilan maksimal mumkin bo'lgan ma'lumotlarni tashishdir.

General Electric va Rensselaer politexnika institutining bir guruh tadqiqotchilari yaqinda genetik algoritmdan tijoriy avialaynerlar kabi yuqori o'tishli reaktiv dvigatel turbinalarini loyihalashda yaxshi foydalanishdi. Taxminan silindrsimon kanalga o'ralgan statsionar va aylanuvchi pichoq qatorlarining ko'p bosqichlaridan iborat bunday turbinalar besh yil yoki undan ko'proq davom etadigan dvigatelni rivojlantirish loyihalari markazida bo'lib, ular 2 milliard dollargacha sarflaydi.

Prisoner‘s dilemmada har bir o’yinchi yoki birgalikda o’yinchi yoki birgalikda o’ynay oladi yoki tark eta oladi va boshqalarning tanloviga asoslangan holda jarima ( yoki mukofot ) qabul qiladi. Agar misol uchun ikkalasi ham birlashsa ikkalasiyam 3 ball oladi. Ikkala o’yinchining ham tashlab ketishi eng xavfsiz strategiya lekin takrorlanuvchi o’yin ko’pincha hamkorlikga olib keladi.

Turbinaning dizayni kamida 100 ta o'zgaruvchini o'z ichiga oladi, ularning har biri turli qiymatlarni qabul qilishi mumkin. Olingan qidiruv maydoni 10387 dan ortiq nuqtani o'z ichiga oladi. Turbinaning "yaroqliligi" uning ichki va tashqi devorlarining silliq shakli yoki silindr ichidagi turli nuqtalarda oqimning bosimi, tezligi va turbulentligi kabi bir qator 50 ga yaqin cheklovlarni qanchalik qondirishiga bog'liq. Bitta dizaynni baholash odatdagi muhandislik ish stantsiyasida taxminan 30 soniya davom etadigan dvigatel simulyatsiyasini ishga tushirishni talab qiladi.

Oddiy bir holatda, yolg'iz ishlaydigan muhandis qoniqarli dizaynga erishish uchun taxminan sakkiz hafta davom etdi. Bir yoki ikkita o'zgaruvchining o'zgarishi oqibatlarini bashorat qilish uchun tajribaga asoslangan xulosa chiqarish qoidalaridan foydalanadigan ekspert tizimlari deb ataladigan tizimlar dizaynerga foydali o'zgarishlarni izlashda yordam berishi mumkin. Bunday ekspert tizimidan foydalangan muhandis sakkiz haftalik qo'lda dizayndan ikki baravar yaxshilangan dvigatelni loyihalash uchun bir kundan kam vaqt oldi.

Biroq, bunday ekspert tizimlari tez orada bir vaqtning o'zida ko'plab o'zgaruvchilarni o'zgartirish orqali keyingi takomillashtirishni amalga oshirish mumkin bo'lgan nuqtalarda qolib ketadi. Ushbu o'lik nuqtalar yuzaga keladi, chunki turli xil ko'p o'zgarishlar bilan bog'liq barcha effektlarni saralash amalda imkonsizdir, hatto oldingi tajriba o'z kuchini saqlab qolgan dizayn maydonining hududlarini belgilash ham mumkin emas.

Bunday nuqtadan uzoqlashish uchun dizayner yechim uchun yangi qurilish bloklarini topishi kerak. Bu erda genetik algoritm o'ynaydi. Algoritmni ekspert tizimi tomonidan ishlab chiqarilgan dizaynlar bilan ekish, muhandis qo'lda versiyasidan uch baravar yaxshilangan dizaynni topish uchun bor-yo'g'i ikki kunni oldi (va faqat ekspert tizimidan foydalanishning yana yarmi).

Ushbu misol oddiy genetik algoritmlarning ham kuchli, ham cheklovini ko'rsatadi: ular murakkab landshaftlarni o'rganishda yaxshi imkoniyatlarga ega bo'lgan hududlarni topishda eng yaxshisidir. Ammo agar qisman yechimni bir nechta o'zgaruvchilarga o'zgartirishlar kiritish orqali yanada yaxshilash mumkin bo'lsa, genetik algoritmni boshqa, standartroq usullar bilan to'ldirish yaxshidir.

Garchi genetik algoritmlar tabiiy tanlanish ta'sirini taqlid qilsa-da, hozirgacha ular biologik evolyutsiyaga qaraganda ancha kichikroq miqyosda ishlagan. Mening hamkasblarim va men 8000 ga yaqin qoidalarni o'z ichiga olgan klassifikator tizimlarini ishga tushirdik, ammo bu o'lcham tabiiy populyatsiyalar uchun yashovchanlik chegarasida. Yo'qolib ketish xavfi ostida bo'lmagan yirik hayvonlar millionlab, hasharotlar populyatsiyasi trillionlab va bakteriyalar kvintillion yoki undan ko'p bo'lishi mumkin. Bu katta raqamlar yashirin parallelizmning afzalliklarini sezilarli darajada oshiradi.
Massiv parallel kompyuterlar keng tarqalgan bo'lib, o'lchamlari tabiiy turlarga yaqinroq bo'lgan dasturiy ta'minot populyatsiyalarini rivojlantirish mumkin bo'ladi. Darhaqiqat, genetik algoritm bunday mashinalarga juda mos keladi. Har bir protsessor bitta satrga bag'ishlanishi mumkin, chunki algoritm operatsiyalari krossover paytida bitta satrlarga yoki ko'pi bilan bir juft qatorga qaratilgan. Natijada, butun aholi parallel ravishda qayta ishlanishi mumkin.

Bizda klassifikator tizimlari haqida hali ko'p o'rganishimiz kerak, ammo hozirgacha bajarilgan ishlar shuni ko'rsatadiki, ular ajoyib murakkab xatti-harakatlarga qodir. Michigan universitetidan Rik L. Riolo allaqachon "yashirin o'rganish" ni ko'rsatadigan genetik algoritmlarni kuzatgan (kalamush kabi hayvon mukofotsiz labirintni o'rganadi va keyinchalik labirintga joylashtirilgan ovqatni tezroq topishi mumkin). ).

Santa-Fe institutida Forrest, U. Brayan Artur, Jon X. Miller, Richard G. Palmer va men cheklangan ratsionallikdagi iqtisodiy agentlarni simulyatsiya qilish uchun tasniflash tizimlaridan foydalanganmiz. Ushbu agentlar oddiy tovar bozoridagi tendentsiyalar bo'yicha harakat qilish darajasiga qadar rivojlanib, spekulyativ pufakchalar va halokatlarni keltirib chiqaradi.

Ushbu agentlar yashaydigan taqlid qilingan dunyolar tabiiy ekotizimlarga juda ko'p o'xshashliklarni ko'rsatadi: ular simbioz, parazitizm, biologik "qurol poygalari", mimikr, nisha shakllanishi va turlanish kabi hodisalarga o'xshashlarni ko'rsatadi. Genetik algoritmlar bilan boshqa ishlar evolyutsiya jinsiy yoki jinsiy reproduktsiyani qo'llab-quvvatlaydigan sharoitlarga oydinlik kiritdi.