Mavzu: Genetik algoritimlar Reja: kirish 1. Optimallashtirish muammolari 2. Genetik operatorlar , evristika , tugatish 3. Qurilish bloklari gipotezasi 4. Cheklovlar va variantlar Adabiyotlar

Kirish Optimallashtirish muammolari Genetik algoritmda a aholi ning nomzod echimlari (shaxslar, jonzotlar yoki deyiladi fenotiplar ) optimallashtirish muammosi yanada yaxshi echimlarga yo'naltirilgan. Har bir nomzodning echimi bir qator xususiyatlarga ega (uning xromosomalar yoki genotip ) o'zgarishi va o'zgarishi mumkin bo'lgan; an'anaviy ravishda echimlar ikkilikda 0s va 1s qatorlari sifatida ifodalanadi, ammo boshqa kodlashlar ham mumkin. [2] Evolyutsiya odatda tasodifiy hosil bo'lgan shaxslar populyatsiyasidan boshlanadi va an takroriy jarayon , populyatsiya har bir iteratsiyada a deb nomlanadi avlod. Har bir avlodda fitness aholining har bir shaxsiga baho beriladi; fitnes odatda ning qiymati hisoblanadi ob'ektiv funktsiya optimallashtirish muammosida hal qilinmoqda. Shaxslar qanchalik mos bo'lsa stoxastik ravishda mavjud populyatsiya orasidan tanlangan va har bir kishining genomi o'zgartirilgan ( birlashtirilgan va ehtimol tasodifiy mutatsiyaga uchragan) yangi avlodni shakllantirish uchun. Nomzod echimlarining yangi avlodi keyinchalik algoritm . Odatda, algoritm maksimal avlodlar soni ishlab chiqarilganda yoki aholi uchun qoniqarli darajaga erishilganda tugaydi. Oddiy genetik algoritm quyidagilarni talab qiladi. a genetik vakillik eritma domeni, a fitness funktsiyasi echim maydonini baholash. Har bir nomzod echimining standart vakili bitlar qatori . [2] Boshqa turdagi va tuzilmalar massivlaridan ham xuddi shu tarzda foydalanish mumkin. Ushbu genetik vakilliklarni qulaylashtiradigan asosiy xususiyat shundaki, ularning qismlari aniq o'lchamlari tufayli osongina tekislanadi, bu oddiylikni osonlashtiradi krossover operatsiyalar. O'zgaruvchan uzunlik ko'rsatkichlari ham ishlatilishi mumkin, ammo krossoverni amalga oshirish bu holda ancha murakkab. Daraxtga o'xshash vakolatxonalar o'rganiladi genetik dasturlash va grafik shaklidagi tasvirlar o'rganiladi evolyutsion dasturlash ; ikkala chiziqli xromosomalar va daraxtlarning aralashmasi o'rganiladi gen ekspressionini

dasturlash . Genetik vakillik va fitnes funktsiyasi aniqlangandan so'ng, GA eritmalar populyatsiyasini boshlashga, so'ngra mutatsion, krossover, inversiya va selektsiya operatorlarini takroriy qo'llash orqali yaxshilashga kirishadi. Boshlash Aholining soni muammoning mohiyatiga bog'liq, ammo odatda bir necha yuz yoki minglab mumkin bo'lgan echimlarni o'z ichiga oladi. Ko'pincha, boshlang'ich populyatsiya tasodifiy ravishda hosil bo'lib, barcha mumkin bo'lgan echimlarni taklif qiladi ( qidirish maydoni ). Ba'zan, echimlar optimal echimlar topilishi mumkin bo'lgan joylarda "urug '" bo'lishi mumkin. Tanlash Asosiy maqola: Tanlash (genetik algoritm) Har bir keyingi avlod davomida mavjud aholining bir qismi tanlangan yangi avlodni etishtirish. Shaxsiy echimlar a orqali tanlanadi fitnesga asoslangan jarayon, qaerda montajchi echimlar (a bilan o'lchanganidek fitness funktsiyasi ) odatda ko'proq tanlanadi. Muayyan tanlov usullari har bir echimning mosligini baholaydi va eng yaxshi echimlarni afzal ko'radi. Boshqa usullar faqat aholining tasodifiy tanloviga baho beradi, chunki avvalgi jarayon juda ko'p vaqt talab qilishi mumkin. Fitnes funktsiyasi genetik vakillik bo'yicha aniqlanadi va o'lchanadi sifat taqdim etilgan echim. Fitness funktsiyasi har doim muammoga bog'liq. Masalan, xalta muammosi biron bir sobit quvvatga ega bo'lgan sumkachaga qo'yilishi mumkin bo'lgan ob'ektlarning umumiy qiymatini maksimal darajada oshirishni xohlaydi. Yechimning namoyishi bitlar qatori bo'lishi mumkin, bu erda har bir bit turli xil ob'ektni aks ettiradi va bitning qiymati (0 yoki 1) ob'ektning sumkada yoki yo'qligini anglatadi. Har bir bunday tasvir to'g'ri emas, chunki ob'ektlarning kattaligi sumkachaning imkoniyatlaridan oshib ketishi mumkin. The fitness yechim - bu vakolatxona to'g'ri bo'lsa, aks holda 0, sumkachadagi barcha ob'ektlarning qiymatlari yig'indisi. Ba'zi muammolarda fitnes ifodasini aniqlash qiyin yoki hatto imkonsiz; bu holatlarda, a simulyatsiya a-ning fitness funktsiyasi qiymatini aniqlash uchun

ishlatilishi mumkin fenotip (masalan, suyuqlikning hisoblash dinamikasi shakli fenotip sifatida kodlangan transport vositasining havo qarshiligini aniqlash uchun ishlatiladi), yoki hatto interaktiv genetik algoritmlar ishlatiladi. Genetik operatorlar Asosiy maqolalar: Krossover (genetik algoritm) va Mutatsiya (genetik algoritm) Keyingi qadam, kombinatsiyalash orqali tanlanganlardan ikkinchi avlod populyatsiyasini yaratishdir genetik operatorlar : krossover (shuningdek, rekombinatsiya deb ham ataladi) va mutatsiya . Ishlab chiqariladigan har bir yangi eritma uchun avval tanlangan hovuzdan naslchilik uchun bir juft "ota-ona" eritmasi tanlanadi. Yuqoridagi krossover va mutatsiya usullaridan foydalangan holda "bola" yechimini ishlab chiqarish orqali, odatda, "ota-onalari" ning ko'plab xususiyatlariga ega bo'lgan yangi echim yaratiladi. Har bir yangi tug'ilgan bola uchun yangi ota-onalar tanlanadi va bu jarayon tegishli hajmdagi eritmalarning yangi populyatsiyasi paydo bo'lguncha davom etadi. Ikki ota-onadan foydalanishga asoslangan ko'paytirish usullari ko'proq "biologiyadan ilhomlangan" bo'lsa ham, ba'zi tadqiqotlar [3] [4] ikkitadan ortiq "ota-onalar" yuqori sifatli xromosomalarni yaratishini taklif qiladi. Ushbu jarayonlar oxir-oqibat xromosomalarning keyingi avlod populyatsiyasini keltirib chiqaradi, ular boshlang'ich avloddan farq qiladi. Umuman olganda, aholi uchun ushbu protsedura o'rtacha jismoniy tayyorgarlikni oshiradi, chunki naslchilik uchun faqat birinchi avloddan eng yaxshi organizmlar tanlanadi va unchalik yaroqsiz bo'lgan eritmalar. Ushbu mos bo'lmagan echimlar ota-onalarning genetik havzasida genetik xilma-xillikni ta'minlaydi va shuning uchun keyingi avlod bolalarining genetik xilma-xilligini ta'minlaydi. Mutatsiyaga qarshi krossoverning ahamiyati to'g'risida fikrlar ikkiga bo'lingan. Ichida ko'plab havolalar mavjud Fogel (2006) mutatsiyaga asoslangan qidiruvning ahamiyatini qo'llab-quvvatlaydi. Krossover va mutatsiya asosiy genetik operatorlar sifatida tanilgan bo'lsa-da, genetik algoritmlarda qayta guruhlash, mustamlaka-yo'q qilish yoki migratsiya kabi boshqa operatorlardan foydalanish mumkin.[ iqtibos kerak ]

Kabi parametrlarni sozlash kerak mutatsiya ehtimollik, krossover muammo sinfi uchun oqilona sozlamalarni topish uchun ehtimollik va populyatsiya hajmi. Mutatsiya darajasi juda kichik bo'lishi mumkin genetik drift (bu bo'lmagan ergodik tabiatda). Rekombinatsiya darajasi juda yuqori bo'lsa, genetik algoritmning barvaqt yaqinlashishiga olib kelishi mumkin. Mutatsiya darajasi juda yuqori bo'lsa, yaxshi echimlarni yo'qotishiga olib kelishi mumkin elita tanlovi ish bilan ta'minlangan. Aholining etarlicha kattaligi mavjud muammo uchun etarlicha genetik xilma-xillikni ta'minlaydi, ammo talab qilinadigan qiymatdan kattaroq bo'lsa, hisoblash resurslarining isrof bo'lishiga olib kelishi mumkin. Evristika Yuqoridagi asosiy operatorlardan tashqari, boshqalar evristika hisobni tezroq yoki ishonchli qilish uchun ishlatilishi mumkin. The spetsifikatsiya evristik bir-biriga juda o'xshash nomzodlar echimlari orasidagi krossoverni jazolaydi; bu aholining xilma-xilligini rag'batlantiradi va muddatidan oldin oldini olishga yordam beradi yaqinlashish kamroq maqbul echimga. [5] [6] Tugatish Ushbu avlod jarayoni tugatish shartiga kelguniga qadar takrorlanadi. Tugatishning umumiy shartlari: Minimal mezonlarga javob beradigan echim topildi Belgilangan avlodlar soni Ajratilgan byudjetga (hisoblash vaqti / pul) yetdi Eng yuqori darajadagi echimning pog'onasi platoga etib bormoqda yoki unga erishilganki, ketma-ket takrorlashlar endi yaxshi natijalarni bermaydi Qo'lda tekshirish Yuqoridagi kombinatsiyalar Qurilish bloklari gipotezasi Genetik algoritmlarni amalga oshirish oddiy, ammo ularning xatti-harakatlarini tushunish qiyin. Xususan, ushbu algoritmlarning amaliy muammolarga nisbatan yuqori malakali echimlarni ishlab chiqarishda nima uchun tez-tez muvaffaqiyat qozonishini tushunish qiyin. Qurilish bloklari gipotezasi (BBH) quyidagilardan