Sun'iy intellekt sohasida evolyutsion algoritm (EA) metaevristik optimallashtirishga asoslangan umumiy populyatsiya hisoblarining kichik to'plamidir. EA ko'payish, mutatsiya, rekombinatsiya va tanlash kabi biologik rivojlanishdan ilhomlangan mexanizmlardan foydalanadi. Evolyutsion optimallashtirish algoritmlari muammosidagi nomzod yechimi populyatsiyadagi individlar rolini o'ynaydi. Shuningdek, fitnes funksiyasi javoblar sifatini belgilaydi.
Evolyutsion algoritmlar ko'pincha barcha turdagi muammolarning yechimlarini yaxshi taxmin qiladi. Chunki ideal holda ular asosiy fitnes landshafti haqida hech qanday taxminlar qilmaydi. Evolyutsion modellashtirish va genetik algoritmlar uchun qo'llaniladigan usullar odatda mikroevolyutsion jarayonlarni o'rganish va hujayra bosqichlariga asoslangan rejalashtirish modellari bilan chegaralanadi. Aksariyat haqiqiy EA ilovalarida hisoblash murakkabligi taqiqlovchi omil hisoblanadi.
Aslidabu masala fitnes funktsiyasini baholash bilan bog'liq. Fitnesga yaqinlashish bu qiyinchilikni yengishning bir yechimidir. Biroq, oddiy ko'rinadigan EA ko'pincha murakkab muammolarni hal qilishi mumkin. Shuning uchun ketma-ketlikning murakkabligi va muammo o'rtasida bevosita bog'liqlik bo'lishi mumkin emas. Batafsil ma'lumotni "Evolyutsiya algoritmlari" kitoblarida topishingiz mumkin.
Amalga keltirish
Birinchi qadam tasodifiy shaxslarning dastlabki populyatsiyasini yaratishdir.
Ikkinchi bosqich - bu guruhdagi har bir shaxsning mosligini baholash (vaqt chegarasi, yetarli tayyorgarlik va h.k.).
Uchinchi qadam - tugatish uchun quyidagi regeneratsiya bosqichlarini takrorlang:
- Koʻpaytirish uchun eng mos odamlarni tanlang (ota-onalar).
- Nasl olish uchun krossover va mutatsiya yordamida evolyutsiya algoritmidan oʻtgan yangi shaxslarni keltiring.
- Yangi odamlarning individual tayyorgarligini baholang.
- Eng kam mos keladigan aholini ular bilan almashtiring.
Turlar
Genetik algoritm evolyutsion ketma-ketlik boʻlib, Ekspert maslahatchisining eng mashhur turi. Muammoning yechimi rekombinatsiya va mutatsiya (ba'zan bitta, ba'zi hollarda ikkalasi) kabi operatorlarni qo'llash orqali raqamlar qatorlari ko'rinishida (an'anaviy ravishda ikkilik, lekin eng yaxshi tasvirlar odatda hal qilinayotgan masalada ko'proq aks ettirilgan bo'lsa-da) izlanadi.). Ushbu turdagi Ekspert maslahatchisi ko'pincha optimallashtirish muammolarida qo'llaniladi. Buning boshqa nomi fetura (lotincha "tug'ilish" degan ma'noni anglatadi):
- Genetik dasturlash. U yechimlarni kompyuter kodlari sifatida taqdim etadi va ularning muvofiqligi hisoblash vazifalarini bajarish qobiliyati bilan belgilanadi.
- Evolyutsion dasturlash. Evolyutsion genetik algoritmga o'xshash, ammo strukturasi o'zgarmas va uning raqamli parametrlari o'zgarishi mumkin.
- Gen ifodasini dasturlash. Kompyuter ilovalarini ishlab chiqadi, lekin genotip-fenotip tizimini o'rganadi, bu erda turli o'lchamdagi loyihalar belgilangan uzunlikdagi chiziqli xromosomalarda kodlanadi.
- Strategiya. Haqiqiy sonlar vektorlari bilan yechimlar tasviri sifatida ishlaydi. Odatda oʻz-oʻzidan moslashuvchi evolyutsion mutatsiya tezligi algoritmlaridan foydalanadi.
- Differentsial rivojlanish. Vektor farqlariga asoslangan va shuning uchun birinchi navbatda raqamli optimallashtirish muammolari uchun javob beradi.
- Neyroevolyutsiya. Evolyutsion dasturlash va genetik algoritmlarga o'xshash. Ammo ikkinchisi sun'iy neyron tarmoqlar bo'lib, ulanishlarning tuzilishi va og'irligini tavsiflaydi. Genom kodlash to'g'ridan-to'g'ri yoki bilvosita bo'lishi mumkin.
Biologik jarayonlar bilan solishtirish
Koʻpgina evolyutsion algoritmlarning mumkin boʻlgan cheklovi genotip va fenotip oʻrtasidagi aniq farqning yoʻqligidir. Tabiatda urug'lantirilgan tuxum etuk bo'lish uchun embriogenez deb ataladigan murakkab jarayondan o'tadi. Ushbu bilvosita kodlash genetik qidiruvlarni yanada ishonchli qiladi (ya'ni, halokatli mutatsiyalarni keltirib chiqarish ehtimoli kamroq) va organizmning rivojlanish qobiliyatini yaxshilashi mumkin. Bunday bilvosita (boshqacha aytganda,generativ yoki rivojlanish) kodlashlar evolyutsiyaga atrof-muhitdagi muntazamlikdan foydalanishga ham imkon beradi.
Sun'iy embriogenez yoki rivojlanish tizimlari bo'yicha so'nggi ishlar ushbu muammolarni hal qilishga intiladi. Gen ifodasini dasturlashda genotip-fenotip hududi muvaffaqiyatli o'rganiladi, bunda birinchisi belgilangan uzunlikdagi chiziqli multigen xromosomalardan, ikkinchisi esa turli o'lcham va shakldagi ko'plab ifodali daraxtlar yoki kompyuter dasturlaridan iborat.
Tegishli texnikalar
Algoritmlarga quyidagilar kiradi:
- chumolilar koloniyasini optimallashtirish. Bu hasharotlar feromonlar bilan bog'lanib, yo'llar hosil qilish orqali oziq-ovqat izlaydi, degan g'oyaga asoslanadi. Asosan kombinatoriy optimallashtirish va grafik muammolari uchun javob beradi.
- Ildiz slayder algoritmi. Ijodkor o‘simlik ildizlarining tabiatdagi funksiyasidan ilhomlangan.
- Sun'iy asalarilar koloniyalari uchun algoritm. Asal asalarilarning xulq-atvoriga asoslanadi. U birinchi navbatda sonli optimallashtirish uchun taklif qilingan va kombinatsion, chegaralangan va ko'p maqsadli muammolarni hal qilish uchun kengaytirilgan. Asalarichilik algoritmi hasharotlarning ozuqa qidirish xatti-harakatlariga asoslangan. U marshrutlash va rejalashtirish kabi koʻplab ilovalarda qoʻllanilgan.
- Zarrachalar toʻdasini optimallashtirish - hayvonlarning podasining xatti-harakati gʻoyalariga asoslangan. Shuningdek, birinchi navbatda raqamli jarayon vazifalari uchun javob beradi.
Boshqa mashhur metaevristik usullar
- Ov qidiruvi. Ba'zi hayvonlarni, masalan, bo'rilarni guruhli ovlashga asoslangan usulo'ljani o'rab olish uchun o'z vazifalarini taqsimlaydi. Evolyutsiya algoritmining har bir a'zosi boshqalar bilan qandaydir tarzda bog'lanadi. Bu, ayniqsa, rahbar uchun to'g'ri keladi. Bu kombinatsion jarayon usuli sifatida moslashtirilgan uzluksiz optimallashtirish usuli.
- Oʻlchovlar boʻyicha qidirish. Tabiatga asoslangan metaevristik usullardan farqli o'laroq, adaptiv jarayon algoritmi o'zining asosiy printsipi sifatida metaforadan foydalanmaydi. Aksincha, u har bir iteratsiyada qidiruv o'lchovi nisbati parametrini yangilashga asoslangan oddiy ishlashga yo'n altirilgan usuldan foydalanadi. Firefly algoritmi o't chirog'ining miltillovchi nuri bilan bir-birini qanday jalb qilishidan ilhomlangan. Bu, ayniqsa, multimodal optimallashtirish uchun foydalidir.
- Uyg’unlikni qidiring. Musiqachilarning xulq-atvori g'oyalari asosida. Bunday holda, evolyutsion algoritmlar kombinatoriy optimallashtirishning yo'lidir.
- Gauss moslashuvi. Axborot nazariyasiga asoslanadi. Ishlash va o'rtacha mavjudligini maksimal darajada oshirish uchun foydalaniladi. Bu vaziyatdagi evolyutsion algoritmlarga misol: termodinamika va axborot nazariyasidagi entropiya.
Memetic
Richard Dokinsning mem haqidagi g'oyasiga asoslangan gibrid usul. Odatda u mahalliy takomillashtirishni amalga oshirishga qodir bo'lgan individual o'rganish protseduralari bilan birlashtirilgan populyatsiyaga asoslangan algoritm shaklini oladi. Muammoga oid bilimlardan foydalanishga urgʻu beradi va nozik va global qidiruvlarni sinergetik tarzda tashkil etishga urinadi.
EvolyutsionAlgoritmlar polinom vaqtida osonlikcha yechilmaydigan muammolarga, masalan, klassik NP-qiyin masalalarga va toʻliq ishlov berish uchun juda uzoq vaqt talab qiladigan boshqa masalalarga evristik yondashuvdir. Mustaqil ravishda foydalanilganda, ular odatda kombinatsion muammolar uchun ishlatiladi. Biroq, genetik algoritmlar ko'pincha boshqa usullar bilan birgalikda qo'llaniladi va ular bilan ishlash uchun bir nechta optimal boshlang'ich joylarni topishning tezkor usuli sifatida ishlaydi.
Evolyutsiya algoritmining asosi (maslahatchi sifatida tanilgan) siz tabiiy tanlanish jarayoni bilan tanish ekansiz, juda oddiy. U to'rtta asosiy qadamni o'z ichiga oladi:
- boshlash;
- tanlov;
- genetik operatorlar;
- end.
Ushbu bosqichlarning har biri taxminan tabiiy tanlanishning ma'lum bir jihatiga mos keladi va ushbu toifadagi algoritmlarni modullashtirishning oson usullarini taqdim etadi. Oddiy qilib aytganda, EAda eng kuchli a'zolar omon qoladi va ko'payadi, noloyiq a'zolar esa o'lib, keyingi avlod genofondiga hissa qo'shmaydi.
Initializatsiya
Algoritmni boshlash uchun avvalo yechimlar toʻplamini yaratishingiz kerak. Populyatsiyada ko'pincha a'zolar deb ataladigan mumkin bo'lgan muammoli bayonotlarning o'zboshimchalik soni bo'ladi. Ular ko'pincha tasodifiy (topshiriq cheklovlari doirasida) hosil bo'ladi yoki, agar ba'zi oldingi bilimlar ma'lum bo'lsa, taxminiy ravishda ideal deb hisoblangan narsalar atrofida markazlashtiriladi. Aholi keng ko'lamli echimlarni qamrab olishi muhim,chunki u mohiyatan genofonddir. Shuning uchun, agar kimdir algoritm ichida turli xil imkoniyatlarni o'rganmoqchi bo'lsa, ko'p turli genlarga ega bo'lishga intilishi kerak.
Tanlash
Aholisi yaratilgandan soʻng, endi uning aʼzolari fitnes funksiyasiga koʻra baholanishi kerak. Fitness funktsiyasi a'zoning xususiyatlarini oladi va a'zo qanchalik mos ekanligini raqamli tasvirni beradi. Ularni yaratish ko'pincha juda qiyin bo'lishi mumkin. Ma'lumotlarni to'g'ri ko'rsatadigan yaxshi tizimni topish muhimdir. Bu muammoga juda xosdir. Endi barcha ishtirokchilarning mosligini hisoblash va eng yaxshi aʼzolarni tanlash kerak.
Bir nechta maqsadli funksiyalar
EA'larni ushbu tizimlardan foydalanish uchun ham kengaytirish mumkin. Bu jarayonni biroz murakkablashtiradi, chunki ulardan foydalanishda bitta optimal nuqtani aniqlash o'rniga, to'plam olinadi. Yechimlar to'plami Pareto chegarasi deb ataladi va ularning hech biri boshqasiga ustunlik qilmasligi ma'nosida bir xil darajada mos elementlarni o'z ichiga oladi.
Genetik operatorlar
Bu bosqich ikkita kichik bosqichni o'z ichiga oladi: krossover va mutatsiya. Eng yaxshi atamalarni tanlagandan so'ng (odatda eng yaxshi 2, lekin bu raqam farq qilishi mumkin), ular endi algoritmda keyingi avlodni yaratish uchun ishlatiladi. Tanlangan ota-onalarning xususiyatlarini qo'llash orqali sifatlar aralashmasi bo'lgan yangi bolalar yaratiladi. Bu ko'pincha ma'lumotlar turiga qarab qiyin bo'lishi mumkin, lekin odatda kombinatsion muammolardayaroqli kombinatsiyalarni aralashtirish va chiqarish mumkin.
Endi avlodga yangi genetik materialni kiritish kerak. Agar bu muhim qadam qo'yilmasa, olim juda tez mahalliy ekstremallarga yopishib qoladi va optimal natijalarga erisha olmaydi. Ushbu qadam mutatsiya bo'lib, u juda oddiy tarzda amalga oshiriladi, bolalarning kichik bir qismini, asosan, ota-onalarning genlarining pastki qismlarini aks ettirmaydigan tarzda o'zgartiradi. Mutatsiya odatda ehtimollik asosida sodir bo'ladi, chunki bolaning uni olish ehtimoli va uning og'irligi taqsimot bilan belgilanadi.
Toʻxtatish
Oxir-oqibat, algoritm tugashi kerak. Bu odatda ikkita holatda sodir bo'ladi: yoki u maksimal bajarish vaqtiga yetdi yoki ishlash chegarasiga yetdi. Bu vaqtda yakuniy yechim tanlanadi va qaytariladi.
Evolyutsion algoritmlarga misol
Endi, bu jarayonning natijasini ko'rsatish uchun maslahatchining harakatini ko'rishingiz kerak. Buning uchun biz dinozavrlarning bir necha avlodlari yurishni (erni asta-sekin o'zlashtirish), tana tuzilishini optimallashtirish va mushaklar kuchini qo'llashni qanday o'rganganligini eslashimiz mumkin. Ilk avlod sudralib yuruvchilar yura olmasa ham, maslahatchi vaqt o'tishi bilan mutatsiya va krossover orqali ularni yura oladigan shaklga aylantira oldi.
Bu algoritmlar zamonaviy dunyoda tobora dolzarb boʻlib bormoqda, chunki ularga asoslangan yechimlar raqamli marketing, moliya va boshqa sohalarda tobora koʻproq foydalanilmoqda.sog'liqni saqlash.
EA qayerda ishlatiladi?
Kengroq aytganda, evolyutsion algoritmlar tasvirni qayta ishlash, transport vositalarini marshrutlash, mobil aloqani optimallashtirish, dasturiy taʼminotni ishlab chiqish va hattoki sunʼiy neyron tarmoqlarni oʻrgatish kabi turli xil ilovalarda qoʻllaniladi. Ushbu vositalar odamlar kundalik foydalanadigan ko'plab ilova va veb-saytlar, jumladan Google Xaritalar va hatto The Sims kabi o'yinlarning markazida. Bundan tashqari, tibbiyot sohasi saraton kasalligini davolash bo'yicha klinik qarorlar qabul qilishda yordam berish uchun EA dan foydalanadi. Aslida evolyutsion algoritmlar shunchalik mustahkamki, ulardan deyarli har qanday optimallashtirish muammosini hal qilishda foydalanish mumkin.
Mur qonuni
EO tarqalishining ortib borishi ikkita asosiy omil bilan bog'liq: mavjud hisoblash quvvati va katta ma'lumotlar to'plamining to'planishi. Birinchisini Mur qonuni bilan ta'riflash mumkin, bu asosan kompyuterdagi hisoblash quvvati miqdori har ikki yilda ikki baravar ko'payadi. Bu bashorat o'nlab yillar davomida saqlanib qolgan. Ikkinchi omil texnologiyaga tobora ortib borayotgan ishonch bilan bog'liq bo'lib, bu institutlarga nihoyatda katta hajmdagi ma'lumotlarni to'plash imkonini beradi, bu ularga tendentsiyalarni tahlil qilish va mahsulotlarni optimallashtirish imkonini beradi.
Evolyutsion algoritmlar marketologlarga qanday yordam beradi?
Bozor sharoitlari tez oʻzgarmoqda va juda raqobatbardosh. Bu marketing menejerlarini yaxshiroq qaror qabul qilish uchun raqobatlashishga majbur qildi. Mavjudlikni oshirishhisoblash quvvati ishchilarni muammolarni hal qilish uchun EA dan foydalanishga olib keldi.
Konversiyani optimallashtirish
Asosiy maqsadlardan biri saytga tashrif buyuruvchilar darajasini oshirishdir. Bu muammo sotuvchi xohlagan narsani qiladigan foydalanuvchilar sonini optimallashtirish bilan bog'liq. Misol uchun, agar kompaniya noutbuklarni sotadigan bo'lsa, ideal mahsulot sotib olish bilan yakunlangan saytga tashrif buyuruvchilar sonini ko'paytirishdir. Bu konversiya tezligini optimallashtirishning mohiyati.
Ajablanarlisi muhim jihatlardan biri bu foydalanuvchi interfeysini tanlashdir. Agar veb-dizayn foydalanuvchilarga juda qulay bo'lmasa, u yoki bu sababga ko'ra mahsulotni sotib olmaydiganlar bor. Maqsad konvertatsiya qilmaydigan foydalanuvchilar sonini kamaytirishdir, bu esa umumiy foydani oshiradi.
