1. Tabiatdagi tabiiy tanlanish

Evolyutsion nazariya deb da'vo qiladi hamma biologik turlar maqsadga muvofiq ravishda rivojlanadi va o'zgaradi eng yaxshi yo'l moslashish muhit. Evolyutsiya jarayonida hasharotlar va baliqlarning ko'plab turlari himoya ranglariga ega bo'ldi, kirpi ignalar tufayli daxlsiz bo'ldi, odam eng murakkab narsaning egasiga aylandi. asab tizimi. Aytishimiz mumkinki, evolyutsiya barcha tirik organizmlarni optimallashtirish jarayonidir. Keling, ushbu optimallashtirish muammosini tabiat qanday hal qilishini ko'rib chiqaylik.

Evolyutsiyaning asosiy mexanizmi tabiiy tanlanishdir.

Uning mohiyati shundaki, ko'proq moslashgan shaxslar mavjud ko'proq imkoniyatlar yashash va ko'payish uchun va shuning uchun yomon moslashgan shaxslarga qaraganda ko'proq nasl beradi. Bundan tashqari, genetik ma'lumotlarning uzatilishi tufayli ( genetik meros) avlodlar ota-onalaridan asosiy fazilatlarni meros qilib oladilar. Shunday qilib, kuchli shaxslarning avlodlari ham nisbatan yaxshi moslashgan va ularning ulushi bo'ladi umumiy massa shaxslar ortadi. Bir necha o'nlab yoki yuzlab avlodlar o'zgargandan so'ng, ma'lum bir turning o'rtacha jismoniy tayyorgarligi sezilarli darajada oshadi.

Genetik algoritmlarning ishlash tamoyillarini aniqroq qilish uchun tabiatdagi irsiy meros mexanizmlari qanday ishlashini ham tushuntiramiz. Har qanday hayvonning har bir hujayrasi hammasini o'z ichiga oladi genetik ma'lumot bu shaxs. Bu ma'lumot juda uzun DNK (Dezoksiribonuklein kislotasi) molekulalari to'plami shaklida yozilgan. Har bir DNK molekulasi molekulalardan tashkil topgan zanjirdir nukleotidlar A, T, C va G deb atalgan to'rtta tur. Aslida ma'lumotlar DNKdagi nukleotidlar tartibi bo'yicha olib boriladi. Shunday qilib, genetik kod individual - bu faqat 4 ta harfdan iborat juda uzun belgilar qatori. Hayvon hujayrasida har bir DNK molekulasi membrana bilan o'ralgan - bu shakllanish deyiladi xromosoma.

Har bir insonning tug'ma sifati (ko'z rangi, irsiy kasalliklar, soch turi va boshqalar) deb ataladigan xromosomaning ma'lum bir qismi tomonidan kodlangan genom bu mulk. Misol uchun, ko'z rangi geni kodlaydigan ma'lumotni o'z ichiga oladi o'ziga xos rang ko'z. Turli ma'nolar gen deyiladi allellar.

Hayvonlar ko'payganda, ikkita ota-ona jinsiy hujayralari birlashadi va ularning DNKsi o'zaro ta'sirlanib, naslning DNKsini hosil qiladi. O'zaro ta'sirning asosiy usuli krossover (kesishish, kesishish). Krossoverda ajdodlarning DNKsi ikki qismga bo'linadi, so'ngra ularning yarmi almashinadi.

Meros paytida, radioaktivlik yoki boshqa ta'sirlar tufayli mutatsiyalar mumkin, buning natijasida ota-onalardan birining jinsiy hujayralarida ba'zi genlar o'zgarishi mumkin. O'zgartirilgan genlar naslga o'tadi va unga yangi xususiyatlar beradi. Agar bular yangi bo'lsa xossalari foydalidir, ular katta ehtimol bilan bu shaklda saqlanib qoladi - bu holda, turning yaroqliligining keskin o'sishi bo'ladi.

2. Genetik algoritm nima

Ba'zi bir murakkab funksiya bo'lsin ( maqsad funktsiyasi), bir nechta o'zgaruvchilarga bog'liq va funktsiya qiymati maksimal bo'lgan o'zgaruvchilarning shunday qiymatlarini topish talab qilinadi. Bunday muammolar deyiladi optimallashtirish muammolari va amaliyotda juda tez-tez uchraydi.

Eng biri illyustrativ misollar- yuqorida tavsiflangan investitsiyalarni taqsimlash muammosi. Ushbu muammoda o'zgaruvchilar har bir loyihaga kiritilgan investitsiya hajmi (10 ta o'zgaruvchi) va maksimal darajada oshirish kerak bo'lgan funktsiya investorning umumiy daromadidir. Har bir loyihaga investitsiyalarning minimal va maksimal hajmining qiymatlari ham berilgan, ular har bir o'zgaruvchi uchun o'zgarish maydonini aniqlaydi.

Keling, ma'lum bo'lganlardan foydalanib, bu muammoni hal qilishga harakat qilaylik tabiiy yo'llar optimallashtirish. Biz har bir investitsiya variantini (o'zgaruvchan qiymatlar to'plami) individual sifatida va ushbu variantning rentabelligini ushbu shaxsning yaroqliligi sifatida ko'rib chiqamiz. Keyin, evolyutsiya jarayonida (agar biz uni tartibga solishga muvaffaq bo'lsak), jismoniy shaxslarning jismoniy tayyorgarligi oshadi, ya'ni ko'proq va ko'proq foydali investitsiya variantlari paydo bo'ladi. Bir nuqtada evolyutsiyani to'xtatib, eng yaxshi shaxsni tanlab, biz etarli miqdorda olamiz yaxshi qaror vazifalar.

Genetik algoritm oddiy model kompyuter dasturi shaklida amalga oshirilgan tabiatdagi evolyutsiya. U genetik meros mexanizmining analogidan ham, tabiiy tanlanishning analogidan ham foydalanadi. Shu bilan birga, biologik terminologiya soddalashtirilgan shaklda saqlanadi.

Genetik meros shunday modellashtirilgan

Evolyutsiya jarayonini taqlid qilish uchun biz birinchi navbatda tasodifiy populyatsiyani hosil qilamiz - tasodifiy xromosomalar to'plamiga (raqamli vektorlar) ega bo'lgan bir nechta shaxslar. Genetik algoritm bu populyatsiyaning evolyutsiyasini shaxslarni kesib o'tish va avlodlarni o'zgartirishning tsiklik jarayoni sifatida simulyatsiya qiladi.

Populyatsiyaning hayot aylanishi bir nechta tasodifiy kesishish (krossover orqali) va mutatsiyalardan iborat bo'lib, buning natijasida populyatsiyaga ma'lum miqdordagi yangi individlar qo'shiladi. Genetik algoritmda tanlash eski populyatsiyadan yangi populyatsiyani shakllantirish jarayoni bo'lib, undan keyin eski populyatsiya nobud bo'ladi. Tanlashdan so'ng, yangi populyatsiyaga krossover va mutatsiya operatsiyalari yana qo'llaniladi, keyin yana tanlash sodir bo'ladi va hokazo.

Genetik algoritmdagi tanlash tabiatdagi tabiiy tanlanish tamoyillari bilan quyidagicha chambarchas bog'liq:

Shunday qilib, tanlov modeli keyingi avlod populyatsiyasini qanday qurish kerakligini belgilaydi. Qoidaga ko'ra, bir kishining xochda qatnashish ehtimoli uning yaroqliligiga mutanosib ravishda qabul qilinadi. Ko'pincha elitizm deb ataladigan strategiya qo'llaniladi, unda bir nechta eng yaxshi shaxslar o'zgarishsiz, krossover va tanlovda ishtirok etmasdan keyingi avlodga o'tadi. Har holda, har bir keyingi avlod, o'rtacha, avvalgisidan yaxshiroq bo'ladi. Jismoniy shaxslarning jismoniy tayyorgarligi sezilarli darajada o'sishni to'xtatganda, jarayon to'xtatiladi va optimallashtirish muammosini hal qilish uchun topilgan shaxslarning eng yaxshisi olinadi.

Investitsiyalarni optimal taqsimlash muammosiga qaytsak, bu holda genetik algoritmni amalga oshirish xususiyatlarini tushuntiramiz.

• Individual = masala yechimi = 10 ta xromosomalar to'plami X j
• X xromosoma j = loyihaga investitsiya hajmi j = bu raqamning 16-bitli yozuvi
• Investitsiyalar hajmi cheklanganligi sababli, barcha xromosoma qiymatlari haqiqiy emas. Bu populyatsiyalarni yaratishda hisobga olinadi.
• Investitsiyalarning umumiy miqdori qat'iy belgilanganligi sababli, faqat 9 ta xromosoma o'zgaradi va 10-chi xromosoma ulardan yagona tarzda aniqlanadi.

Quyida K umumiy investitsiya hajmining uch xil qiymati uchun genetik algoritm natijalari keltirilgan.

Foyda grafigidagi rangli kvadratlar genetik algoritm tomonidan ma'lum bir loyihaga qancha investitsiya tavsiya etilganligini ko'rsatadi.     Ko'rinib turibdiki, K ning kichik qiymati bilan faqat minimal investitsiyalar bilan foydali bo'lgan loyihalar kiritiladi.

Agar siz investitsiyalarning umumiy hajmini oshirsangiz, qimmatroq loyihalarga sarmoya kiritish foydali bo'ladi.

K ning yanada oshishi bilan foydali loyihalarga maksimal sarmoya kiritish chegarasiga erishiladi va past rentabelli loyihalarga sarmoya kiritish yana mantiqiy bo'ladi.

3. Genetik algoritmlarning xususiyatlari

Genetik algoritm eng yangi, ammo optimallashtirish muammolarini hal qilishning yagona usuli emas. Uzoq vaqt davomida bunday muammolarni hal qilishning ikkita asosiy usuli ma'lum - to'liq qidiruv va mahalliy gradient. Ushbu usullarning o'ziga xos afzalliklari va kamchiliklari bor va har bir alohida holatda qaysi birini tanlash haqida o'ylashingiz kerak.

Keling, standart va ning afzalliklari va kamchiliklarini ko'rib chiqaylik genetik usullar klassik sayohatchi sotuvchi muammosi (TSP) misolidan foydalanish. Muammoning mohiyati ularning koordinatalari bilan berilgan bir nechta shaharlar atrofida eng qisqa yopiq yo'lni topishdir. Ma'lum bo'lishicha, allaqachon 30 ta shahar uchun eng maqbul yo'lni qidirish qiyin vazifa, bu turli xil yangi usullarni (jumladan, neyron tarmoqlar va genetik algoritmlarni) ishlab chiqishga turtki bo'ldi.

Yechimning har bir varianti (30 ta shahar uchun) raqamlar qatoridir, bunda j-o'rinda aylanib o'tish tartibida j-shaharning raqami. Shunday qilib, ushbu muammoda 30 ta parametr mavjud va barcha qiymatlar kombinatsiyasi haqiqiy emas. Tabiiyki, birinchi g'oya barcha vaqtinchalik echimlarni to'liq qidirishdir.

To'liq usul tabiatan eng sodda va dasturlashda ahamiyatsiz. Qidiruv uchun optimal yechim(maqsad funktsiyasining maksimal nuqtalari) barcha mumkin bo'lgan nuqtalarda maqsad funktsiyasining qiymatlarini ketma-ket hisoblash, ularning maksimalini eslab qolish talab qilinadi. Ushbu usulning kamchiliklari yuqori hisoblash narxidir. Xususan, sayohatchi sotuvchi muammosida 10 30 dan ortiq yo'l variantlari uzunligini hisoblash kerak bo'ladi, bu mutlaqo haqiqiy emas. Biroq, agar barcha variantlarni o'rtacha vaqt ichida qidirish mumkin bo'lsa, topilgan yechim haqiqatan ham maqbul ekanligiga amin bo'lishingiz mumkin.

Ikkinchi mashhur usul gradient tushish usuliga asoslangan. Bu holda, birinchi navbatda, ba'zi tasodifiy parametr qiymatlari, va keyin bu qiymatlar asta-sekin o'zgartirilib, maqsad funktsiyasining eng yuqori o'sish tezligiga erishiladi. Mahalliy maksimalga erishgandan so'ng, bunday algoritm to'xtaydi, shuning uchun global optimalni topish uchun qo'shimcha harakatlar talab etiladi. Gradient usullari juda tez ishlaydi, ammo topilgan yechimning optimalligiga kafolat bermaydi.

Ular so'zda foydalanish uchun ideal unimodal maqsad funksiyasi bitta mahalliy maksimalga ega bo'lgan muammolar (shuningdek, global deb ham ataladi). Sayohatchi sotuvchi muammosi yagona emasligini tushunish oson.

Odatda amaliy muammo odatda multimodal  va ko'p o'lchovli, ya'ni u juda ko'p parametrlarni o'z ichiga oladi. Bunday vazifalar uchun yo'q universal usul, bu esa mutlaqo aniq yechimni tezda topish imkonini beradi.

Biroq, to'liq va gradient usullarini birlashtirib, hech bo'lmaganda taxminiy yechimni olishga umid qilish mumkin, uning aniqligi hisoblash vaqtining oshishi bilan ortadi.

Genetik algoritm aynan shunday birlashgan usuldir. Kesish va mutatsiya mexanizmlari ma'lum ma'noda usulning qidiruv qismini va tanlashni amalga oshiradi eng yaxshi yechimlar- gradient tushishi. Rasm shuni ko'rsatadiki, bu kombinatsiya barcha turdagi muammolar uchun doimiy ravishda yaxshi genetik qidiruv ko'rsatkichlariga imkon beradi.

Demak, agar ma'lum bir to'plamda bir nechta o'zgaruvchilardan iborat kompleks funktsiya berilgan bo'lsa, genetik algoritm bu funktsiyaning qiymati maksimal mumkin bo'lgan qiymatga etarlicha yaqin bo'lgan nuqtani oqilona vaqt ichida topadigan dasturdir. Qabul qilinadigan hisoblash vaqtini tanlab, biz odatda shu vaqt ichida olinishi mumkin bo'lgan eng yaxshi echimlardan birini olamiz.

Ward Systems Group genetik algoritm yordamida sayohatchi sotuvchi muammosini hal qilishning aniq misolini tayyorladi. Shu maqsadda GeneHunter mahsulot funksiyalari kutubxonasidan foydalanilgan.

Genetik algoritmning o'ziga xos xususiyati - bu "o'tish" operatoridan foydalanishga e'tibor qaratish bo'lib, u nomzod yechimlarning rekombinatsiya operatsiyasini bajaradi, uning roli tirik tabiatdagi kesishish roliga o'xshaydi.

Entsiklopedik YouTube

1 / 5

? Genetik algoritm

? 20: Genetik algoritmlarga kirish (1 / 2)

? C# - Dengiz jangi- Eng yaxshi AI algoritmi

? 15/09/2018 “Optimal tuzilmalarni izlashning genetik algoritmlari” ma’ruzasi Ulyantsev V.I.

? Genetik algoritm. Grafikni o'lchagichga joylashtirish

Subtitrlar

Hikoya

Evolyutsiyani simulyatsiya qilish bo'yicha birinchi ish 1954 yilda Nils Baricelli tomonidan Prinston universitetida o'rnatilgan kompyuterda amalga oshirilgan. Uning o‘sha yili nashr etilgan asari keng jamoatchilik e’tiborini tortdi. 1957 yildan beri avstraliyalik genetik Aleks Freyzer o'lchanadigan xususiyatlar bo'yicha bir nechta nazoratga ega bo'lgan organizmlar o'rtasida sun'iy tanlanishni simulyatsiya qilish bo'yicha bir qator maqolalarni nashr etdi. Ushbu rivojlanish evolyutsion jarayonlarning kompyuter simulyatsiyasi va Freyzer va Barnel (1970) va Krosbi (1973) kitoblarida tasvirlangan usullar 1960-yillardan boshlab biologlar orasida keng tarqalgan faoliyatga aylanishiga imkon berdi. Freyzerning simulyatsiyalari hamma narsani o'z ichiga olgan muhim elementlar zamonaviy genetik algoritmlar. Bunga qo'shimcha ravishda, Xans-Yoaxim Bremermann 1960-yillarda rekombinatsiya, mutatsiya va tanlovga duchor bo'lgan eritma populyatsiyasini optimallashtirish muammolarida qo'llash yondashuvini qabul qilgan bir qator maqolalarni nashr etdi. Bremermanning tadqiqotlari zamonaviy genetik algoritmlarning elementlarini ham o'z ichiga olgan. Boshqa kashshoflar orasida Richard Fridberg, Jorj Fridman va Maykl Konrad bor. Bir guruh dastlabki asarlar David B. Vogel (1998) tomonidan qayta nashr etilgan.

Garchi Baricelli 1963 yilgi ishida mashinaning o'ynash qobiliyatini simulyatsiya qilgan oddiy o'yin Sun'iy evolyutsiya XX asrning 1960-yillari va 1970-yillari boshlarida Ingo Rechenberg va Xans-Pol Shvefelning ishlaridan so'ng umume'tirof etilgan optimallashtirish usuliga aylandi - Rechensberg guruhi evolyutsion strategiyalarga muvofiq murakkab muhandislik muammolarini hal qila oldi. Yana bir yondashuv Lorens J. Vogelning evolyutsion dasturlash texnikasi bo'lib, uni yaratish taklif qilingan sun'iy intellekt. Evolyutsion dasturlash dastlab vaziyatlarni bashorat qilish uchun cheklangan holat mashinalaridan foydalangan va bashoratli mantiqni optimallashtirish uchun xilma-xillik va tanlovdan foydalangan. Genetik algoritmlar, ayniqsa, Jon Gollandning 70-yillar boshidagi ishi va uning "Tabiiy muhitda moslashish" kitobi tufayli mashhur bo'ldi. sun'iy tizimlar"(1975). Uning tadqiqoti Golland tomonidan o'tkazilgan uyali avtomatlar bilan tajribalar va Michigan universitetidagi yozuvlariga asoslangan. Gollandiya elektron teorema deb nomlanuvchi keyingi avlod sifatini bashorat qilish uchun rasmiylashtirilgan yondashuvni taqdim etdi. Genetik algoritmlar sohasidagi tadqiqotlar asosan 1980-yillarning o'rtalariga qadar, ya'ni Pitsburgda (AQSh, Pensilvaniya) Genetik algoritmlar bo'yicha Birinchi Xalqaro konferentsiya bo'lib o'tgunga qadar, asosan nazariy bo'lib qoldi.

Tadqiqotga bo'lgan qiziqishning o'sishi bilan ish stoli kompyuterlarining hisoblash quvvati ham sezilarli darajada oshdi, bu yangi hisoblash texnologiyasini amalda qo'llash imkonini berdi. 1980-yillarning oxirida General Electric dunyodagi birinchi genetik algoritm mahsulotini sotishni boshladi. Bu sanoat hisoblash asboblari to'plamiga aylandi. 1989 yilda yana bir kompaniya Axcelis, Inc. ish stoli kompyuterlari uchun dunyodagi birinchi tijorat genetik algoritm mahsuloti Evolverni chiqardi. New York Times texnologiya jurnalisti Jon Markoff 1990 yilda Evolver haqida yozgan.

Algoritmning tavsifi

Muammo shunday rasmiylashtirilganki, uning yechimi genlarning vektori (“genotip”) sifatida kodlanishi mumkin, bunda har bir gen bit, raqam yoki boshqa ob’ekt bo‘lishi mumkin. Genetik algoritmning (GA) klassik tatbiqlari genotipning qat'iy uzunligi borligini taxmin qiladi. Biroq, ushbu cheklovdan ozod bo'lgan GA o'zgarishlari mavjud.

Ba'zi, odatda tasodifiy, boshlang'ich populyatsiyaning ko'plab genotiplari yaratiladi. Ular "fitness funktsiyasi" yordamida baholanadi, bunda har bir genotip o'ziga xos qiymat ("fitness") bilan bog'liq bo'lib, u tasvirlagan fenotip muammoni qanchalik yaxshi hal qilishini aniqlaydi.

Genetik algoritmlarni qo'llash

Genetik algoritmlar quyidagi muammolarni hal qilish uchun ishlatiladi:

1. Funktsiyani optimallashtirish
2. Grafiklardagi turli muammolar (sayohatchi sotuvchi muammosi, rang berish, mosliklarni topish)
3. Sun'iy neyron tarmog'ini o'rnatish va o'rgatish
4. Joylashtirish vazifalari
5. O'yin strategiyalari
6. Bioinformatika (oqsillarni yig'ish)
7. Cheklangan holat mashinalarining sintezi
8. PID kontrollerlarini sozlash

C++ da oddiy amalga oshirishga misol

Bir o'lchovli fazoda, kesishmasdan qidirish.

#o'z ichiga oladi #o'z ichiga oladi #o'z ichiga oladi #o'z ichiga oladi #o'z ichiga oladi int main () ( srand ((insigned int ) time (NULL )); const size_t N = 1000 ; int a [ N ] = ( 0 ); uchun ( ; ; ) ( //har bir elementning tasodifiy yo'nalishidagi mutatsiya: uchun (size_t i = 0; i< N ; ++ i ) a [ i ] += ((rand () % 2 == 1 ) ? 1 : - 1 ); //endi eng yaxshilarini tanlang, o'sish tartibida tartiblang std::sort(a, a + N); // va keyin eng yaxshilari massivning ikkinchi yarmida bo'ladi. //eng yaxshilarini birinchi yarmiga ko'chiring, ular nasl qoldirgan va birinchilari vafot etgan: std :: nusxa (a + N / 2, a + N, a); //endi aholining o'rtacha holatini ko'rib chiqamiz. Ko'rib turganingizdek, u tobora yaxshilanmoqda. std :: cout<< std :: accumulate (a , a + N , 0 ) / N << std :: endl ; } }

Delphida oddiy amalga oshirishga misol

Bir o'lchovli fazoda omon qolish ehtimoli bilan, kesishmasdan qidiring. (Delphi XE da sinovdan o'tgan)

dastur Program1 ; ($APPTYPE CONSOLE) ($R *.res) System dan foydalanadi. Umumiy. Standart, tizim. Umumiy. To'plamlar, tizim. SysUtils; const N = 1000; Nh = N div 2 ; MaxPopulation = Yuqori (Integer); var A: massiv [1 .. N] of Integer; I, R, C, Ballar, Tug'ilish darajasi: Butun son; Iptr: ^ Integer; tasodifiylashtirishni boshlash; // Qisman aholi uchun I := 1 dan N do A [I] := Tasodifiy (2); takrorlash // I uchun mutatsiya := 1 dan Nga A [ I ] := A [ I ] + (- Tasodifiy (2) yoki 1); // Tanlov, oxirida eng yaxshisi TArray. Saralash< Integer >(A, TComparer< Integer >. Standart); // Oldindan o'rnatilgan Iptr := Adr (A [ Nh + 1 ]); Ballar:= 0; Tug'ilish darajasi:= 0; // Natijalarni kesib o'tish for I := 1 to Nh do begin Inc (Points , Iptr ^ ); // Tasodifiy o'tish muvaffaqiyati R := Tasodifiy(2); Inc (Tug'ilish darajasi, R); A[I]:=Iptr^*R; Iptr ^ := 0 ; Inc(Iptr, 1); oxiri ; // oraliq jami Inc(C); qadar (Points / N >= 1 ) yoki (C >= MaxPopulation ) ; Yozma(Format( "Aholisi %d (stavka:%f) ball:%f", [C, Tug'ilishRate / Nh, Ballar / N])); oxiri.

Madaniyatda

• 1995-yilda suratga olingan “Virtuosity” filmida asosiy yovuz odamning miyasi xotira va xotiralar yordamida genetik algoritm yordamida o‘stiriladi. xulq-atvor xususiyatlari jinoyatchilar.

Ushbu bo'lim turli xil optimallashtirish muammolarini hal qilishga qaratilgan oddiy genetik algoritm (GA) tushunchasini tavsiflaydi. GA nazariyasi va qo'llanilishida qo'llaniladigan tushunchalar kiritiladi va mazmunli tavsiflanadi. GA ning asosiy teoremasi va GA ning nazariy asosini tashkil etuvchi sxemalar nazariyasi keltiriladi. GA ning afzalliklari va kamchiliklariga oid kontseptual masalalar muhokama qilinadi.

1.1. Oddiy genetik algoritm

Genetik algoritmlar nazariyasi asoslari J. G. Golland tomonidan o'zining muhim ishida shakllantirilgan va keyinchalik bir qator boshqa tadqiqotchilar tomonidan ishlab chiqilgan. D.Goldbergning eng mashhur va tez-tez tilga olingan monografiyasi, unda asosiy natijalar va yo'nalishlar muntazam ravishda taqdim etilgan. amaliy qo'llash GA.

GA genetika biologik fanidan olingan printsiplar va atamalardan foydalanadi. GAda har bir shaxs qandaydir muammoning potentsial yechimini ifodalaydi. Klassik GAda individ ikkilik belgilar qatori - xromosoma bilan kodlanadi, ularning har bir biti gen deb ataladi. Shaxslar to'plami - potentsial echimlar - populyatsiyani tashkil qiladi. Muammoning optimal yoki suboptimal yechimini izlash populyatsiya evolyutsiyasi jarayonida amalga oshiriladi, ya'ni. ko'payish, krossing-over va mutatsiyaning genetik operatorlari yordamida bir cheklangan eritmalar to'plamini boshqasiga ketma-ket o'zgartirish. EVs quyidagi printsiplarga asoslangan tabiiy evolyutsiya mexanizmlaridan foydalanadi:

1. Birinchi tamoyil Darvinga ko'ra eng kuchli va tabiiy tanlanishning omon qolishi kontseptsiyasiga asoslangan bo'lib, u 1859 yilda "Tabiiy tanlanish yo'li bilan turlarning kelib chiqishi" kitobida ishlab chiqqan. Darvinning fikriga ko'ra, o'z muhitidagi muammolarni yaxshiroq hal qila oladigan shaxslar omon qolish va ko'payish (ko'payish) ehtimoli ko'proq. Genetik algoritmlarda har bir shaxs qandaydir muammoning yechimini ifodalaydi. Ushbu tamoyilga o'xshab, shaxslar eng yaxshi qadriyatlar maqsadli (fitness) funktsiyalarning omon qolish va ko'payish imkoniyati yuqori. Ushbu tamoyilni rasmiylashtirish, keyinroq ko'rib chiqamiz, ko'paytirish operatori tomonidan amalga oshiriladi.
2. Ikkinchi tamoyil nasl xromosomasi ota-ona xromosomalaridan olingan qismlardan iborat ekanligidan kelib chiqadi. Bu tamoyil 1865 yilda G. Mendel tomonidan kashf etilgan. Uning rasmiylashtirilishi o'tish operatori uchun asos bo'lib xizmat qiladi.
3. Uchinchi tamoyil 1900 yilda de Vres tomonidan kashf etilgan mutatsiya tushunchasiga asoslanadi. Dastlab, bu atama nasllarning xususiyatlaridagi sezilarli (o'tkir) o'zgarishlarni va ularning ota-onalarida mavjud bo'lmagan xususiyatlarni olishlarini tavsiflash uchun ishlatilgan. Ushbu printsipga o'xshab, genetik algoritmlar avlodlarning xususiyatlarini keskin o'zgartirish uchun shunga o'xshash mexanizmdan foydalanadi va shu bilan populyatsiyadagi individlarning xilma-xilligini (o'zgaruvchanligini) oshiradi (echimlar to'plami).

Ushbu uchta tamoyil EV ning asosini tashkil qiladi. Ulardan foydalanib, aholi (ma'lum bir muammoning ko'plab echimlari) avloddan-avlodga o'tadi.

Sun'iy populyatsiyaning evolyutsiyasi - ma'lum bir muammoning bir nechta echimlarini izlash - 1.1-rasmda keltirilgan algoritm shaklida rasmiy ravishda tavsiflanishi mumkin.

GA optimallashtirish masalasining parametrlari to'plamini oladi va ularni qandaydir chekli alifboda chekli uzunlikdagi ketma-ketlikda kodlaydi (eng oddiy holatda ikkilik alifboda "0" va "1").

Oldindan oddiy GA tasodifiy ravishda xromosomalarning (torlarning) boshlang'ich populyatsiyasini hosil qiladi. Keyin algoritm quyidagi uchta asosiydan foydalanib, keyingi avlodni (aholi) hosil qiladi genetik operatorlar:

1. reproduktsiya operatori (OR);
2. o'tish operatori (krossover, OK);
3. mutatsiya operatori (OM).

Genetik algoritmlar shunchaki tasodifiy qidiruv emas, ular evolyutsiya jarayonida to'plangan ma'lumotlardan samarali foydalanadi.

Yechimni izlash jarayonida hozirgi vaqtda olingan eng yaxshi echimlardan "foydalanish" va qidiruv maydonini kengaytirish o'rtasidagi muvozanatni saqlash kerak. Har xil usullar qidiruv tizimlari bu muammoni turli yo'llar bilan hal qiladi.

Misol uchun, gradient usullari amalda faqat eng yaxshi joriy echimlardan foydalanishga asoslangan bo'lib, bu bir tomondan konvergentsiya tezligini oshiradi, lekin boshqa tomondan mahalliy ekstremal muammoni keltirib chiqaradi. Polar yondashuvda tasodifiy qidirish usullari hamma tomonidan qo'llaniladi

IN Yaqinda Neyron tarmoqlar va genetik algoritmlar kabi yangi paydo bo'lgan algoritmlar haqida tobora ko'proq gapirilmoqda. Bugun men genetik algoritmlar haqida gapiraman, ammo bu safar mavhum ta'riflar va murakkab atamalardan qochishga harakat qilaylik.
Buyuk olimlardan biri aytganidek: "Agar siz o'z nazariyangizni xotiningizga tushuntira olmasangiz, sizning nazariyangiz befoyda!" Shunday qilib, keling, hamma narsani tartibda aniqlashga harakat qilaylik.

Bir chimdim tarix

Vikipediyada aytilganidek: "Genetik algoritmlarning asoschisi 1975 yilda genetikadan o'z maqsadlari uchun foydalanish g'oyasini ilgari surgan Jon Holland edi." Ma'lumot uchun, Altair 8800 o'sha yili paydo bo'lgan va yo'q, bu terrorchi emas, balki birinchi Shaxsiy kompyuter. O'sha paytda Jon allaqachon 46 yoshda edi.

U qayerda ishlatiladi?

Algoritm o'z-o'zidan o'rganilganligi sababli, ilovalar doirasi juda keng:

• Grafik muammolar
• Joylashtirish vazifalari
• Rejalashtirish
• "Sun'iy intellekt" ni yaratish

Ishlash printsipi

Genetik algoritm, birinchi navbatda, evolyutsion algoritmdir, boshqacha aytganda, algoritmning asosiy xususiyati kesishish (birlashtirish) hisoblanadi. Siz taxmin qilganingizdek, algoritm g'oyasi shafqatsizlarcha tabiatdan olingan, xayriyatki, u buning uchun sudga da'vo qilmaydi. Shunday qilib, sanab o'tish va eng muhimi, tanlash orqali to'g'ri "kombinatsiya" olinadi.
Algoritm uch bosqichga bo'lingan:

• chatishtirish
• Naslchilik (seleksiya)
• Yangi avlodning shakllanishi

Natija bizga mos kelmasa, natija bizni qoniqtirmaguncha yoki quyidagi shartlardan biri yuzaga kelguncha ushbu amallar takrorlanadi:

• Avlodlar (tsikllar) soni oldindan tanlangan maksimal darajaga etadi
• Mutatsiya uchun vaqt tugadi

Bosqichlar haqida batafsil ma'lumot

Yangi aholining shakllanishi. Ushbu bosqichda boshlang'ich populyatsiya yaratiladi, bu kosher bo'lmasligi mumkin, ammo algoritm bu muammoni hal qilish ehtimoli katta. Asosiysi, ular "format" ga mos keladi va "ko'paytirish uchun moslashtirilgan".
Ko'paytirish. Xo'sh, bu erda hamma narsa odamlarga o'xshaydi, avlod olish uchun ikkita ota-ona talab qilinadi. Asosiysi, avlod (bola) o'z xususiyatlarini ota-onasidan meros qilib olishi mumkin. Bunday holda, nafaqat omon qolganlar ham ko'payadi (bu ibora ayniqsa bema'ni, lekin bizda hamma narsa sharsimon vakuumda bo'lganligi sababli, hamma narsa mumkin), aks holda bitta alfa erkak ajralib turadi, uning genlari boshqalarga to'g'ri keladi va Bu biz uchun tubdan qabul qilinishi mumkin emas.
Mutatsiyalar. Mutatsiyalar ko'payishga o'xshaydi, mutantlardan ma'lum miqdordagi shaxslar tanlanadi va oldindan belgilangan operatsiyalarga muvofiq o'zgartiriladi.
Tanlash. Bu erda eng shirin qismi boshlanadi, biz aholi orasidan "oldinga ketadiganlar" ulushini tanlashni boshlaymiz. Shu bilan birga, biz tanlaganimizdan keyin "omon qolganlar" ulushini parametr sifatida ko'rsatib, qo'lda oldindan aniqlaymiz. Afsuski, qolgan odamlar o'lishi kerak.

Amaliyot

Siz mo''jizaviy algoritm haqidagi "ertak" ni muvaffaqiyatli tingladingiz va ehtimol uni ishlatishni boshlashimizni kutgandirsiz, men sizni xursand qilmoqchiman, vaqt keldi.
Keling, mening sevimli Diofant tenglamalari misolini ko'rib chiqaylik (butun ildizli tenglamalar).
Bizning tenglamamiz: a+2b+3c+4d=30
Ehtimol, siz ushbu tenglamaning ildizlari segmentda joylashganligiga shubha qilgandirsiz, shuning uchun biz 5 ni olamiz
tasodifiy a,b,c,d qiymatlari. (30 chegarasi vazifani soddalashtirish uchun maxsus olingan)
Shunday qilib, bizda birinchi avlod bor:

1. (1,28,15,3)
2. (14,9,2,4)
3. (13,5,7,3)
4. (23,8,16,19)
5. (9,13,5,2)

Omon qolish darajasini hisoblash uchun biz har bir yechimni ifodaga almashtiramiz. Olingan qiymatdan 30 gacha bo'lgan masofa bo'ladi kerakli qiymat.

1. |114-30|=84
2. |54-30|=24
3. |56-30|=26
4. |163-30|=133
5. |58-30|=28

Pastroq qiymatlar 30 ga yaqinroq, ya'ni ular ko'proq ma'qul. Ma'lum bo'ladiki katta qiymatlar omon qolish darajasi past bo'ladi. Tizimni yaratish uchun har bir (xromosoma) ni tanlash ehtimolini hisoblaylik. Ammo yechim koeffitsientlarning o'zaro qiymatlari yig'indisini olish va shundan foizlarni hisoblashdir. ( P.S. 0,135266 - teskari koeffitsientlar yig'indisi)

1. (1/84)/0.135266 = 8.80%
2. (1/24)/0.135266 = 30.8%
3. (1/26)/0.135266 = 28.4%
4. (1/133)/0.135266 = 5.56%
5. (1/28)/0.135266 = 26.4%

Keyinchalik, har birida bittadan farzandli bo'lgan besh juft ota-onani tanlaymiz. Biz roppa-rosa besh marta imkoniyat beramiz, har safar ota-ona bo'lish imkoniyati bir xil bo'ladi va omon qolish imkoniyatiga teng bo'ladi.
3-1, 5-2, 3-5, 2-5, 5-3
Yuqorida aytib o'tilganidek, nasl ota va onaning genlari haqida ma'lumotni o'z ichiga oladi. Buni ta'minlash mumkin turli yo'llar bilan, lekin bu holda "krossover" ishlatiladi. (| = ajratuvchi chiziq)

• H.-otasi: a1 | b1,c1,d1 H.-ona: a2 | b2,c2,d2 X.-avlod: a1,b2,c2,d2 yoki a2,b1,c1,d1
• H.-otasi: a1,b1 | c1,d1 H.-ona: a2,b2 | c2,d2 X.-avlod: a1,b1,c2,d2 yoki a2,b2,c1,d1
• H.-otasi: a1,b1,c1 | d1 H.-ona: a2,b2,c2 | d2 X.-avlod: a1,b1,c1,d2 yoki a2,b2,c2,d1

Ma'lumotni avlodga uzatishning ko'plab usullari mavjud va o'zaro faoliyat ko'p usullardan faqat bittasi. Ajratuvchining joylashuvi mutlaqo o'zboshimchalik bilan bo'lishi mumkin, shuningdek, ota yoki onaning chiziqning chap tomonida bo'ladimi.
Keling, avlodlar bilan ham shunday qilaylik:

• H.-otasi: (13 | 5,7,3) H.-ona:(1 | 28,15,3) X.-avlod: (13,28,15,3)
• H.-otasi: (9,13 | 5,2) H.-ona: (14,9 | 2,4) X.-avlod: (9,13,2,4)
• H.-otasi: (13,5,7 | 3) H.-ona: (9,13,5 | 2) X.-avlod: (13,5,7,2)
• H.-otasi: (14 | 9,2,4) H.-ona: (9 | 13,5,2) X.-avlod: (14,13,5,2)
• H.-otasi: (13,5 | 7, 3) H.-ona: (9,13 | 5, 2) X.-avlod: (13,5,5,2)

Keling, avlodlarning omon qolish darajasini hisoblaylik.

• (13,28,15,3) - |126-30|=96(9,13,2,4) - |57-30|=27
  (13,5,7,2) - |57-30|=22
  (14,13,5,2) - |63-30|=33
  (13,5,5,2) - |46-30|=16

  Bu juda achinarli, chunki naslning o'rtacha jismoniy tayyorgarligi 38,8, ota-onalar uchun esa bu koeffitsient 59,4 ni tashkil etdi. Ayni paytda buning uchun mutatsiyadan foydalanish tavsiya etiladi, biz bir yoki bir nechta qiymatlarni 1 dan 30 gacha tasodifiy raqam bilan almashtiramiz;
  Algoritm omon qolish darajasi nolga teng bo'lguncha ishlaydi. Bular. tenglamaning yechimi bo‘ladi.
  Aholisi ko'proq bo'lgan tizimlar (masalan, 5 o'rniga 50) kerakli darajaga (0) tezroq va barqaror ravishda yaqinlashadi.

  Kod

  Bu erda soddalik tugaydi va ajoyib C++ boshlanadi...
  C++ sinfi ishga tushirilganda 5 ta qiymatni talab qiladi: 4 koeffitsient va natija. Yuqoridagi misol uchun u quyidagicha ko'rinadi: CDiophantine dp(1,2,3,4,30);

  Keyin tenglamani yechish uchun yechimni o'z ichiga olgan allelni qaytaradigan Solve() funksiyasini chaqiring. Genni olish uchun GetGene() ga qo'ng'iroq qiling to'g'ri qiymatlar a B C D. Ushbu sinfdan foydalanadigan standart main.cpp protsedurasi quyidagicha ko'rinishi mumkin:

  #o'z ichiga oladi " " #include "diophantine.h" void main() ( CDiophantine dp(1,2,3,4,30); int ans; ans = dp.Solve(); if (ans == -1) ( cout<< "No solution found." << endl; } else { gene gn = dp.GetGene(ans); cout << "The solution set to a+2b+3c+4d=30 is:\n"; cout << "a = " << gn.alleles << "." << endl; cout << "b = " << gn.alleles << "." << endl; cout << "c = " << gn.alleles << "." << endl; cout << "d = " << gn.alleles << "." << endl; } }

  CDiophantine sinfining o'zi:

  #o'z ichiga oladi #o'z ichiga oladi #define MAXPOP 25 struktur genini ( int allellar; int fitnes; float ehtimoli; // Tenglik uchun test. operator==(gen gn) (uchun (int i=0;i)<4;i++) { if (gn.alleles[i] != alleles[i]) return false; } return true; } }; class CDiophantine { public: CDiophantine(int, int, int, int, int);// Constructor with coefficients for a,b,c,d. int Solve();// Solve the equation. // Returns a given gene. gene GetGene(int i) { return population[i];} protected: int ca,cb,cc,cd;// The coefficients. int result; gene population;// Population. int Fitness(gene &);// Fitness function. void GenerateLikelihoods(); // Generate likelihoods. float MultInv();// Creates the multiplicative inverse. int CreateFitnesses(); void CreateNewPopulation(); int GetIndex(float val); gene Breed(int p1, int p2); }; CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {} int CDiophantine::Solve() { int fitness = -1; // Generate initial population. srand((unsigned)time(NULL)); for(int i=0;i25) sindirish; ) temppop[i] = Zot (ota-ona1, ota-ona2);// Bola yarating. ) uchun (i=0;i

  Maqola Vikipediya va veb-sayt materiallariga asoslangan