Эволюциялық алгоритмдер: бұл не және олар не үшін қажет

Мазмұны:

Эволюциялық алгоритмдер: бұл не және олар не үшін қажет
Эволюциялық алгоритмдер: бұл не және олар не үшін қажет
Anonim

Жасанды интеллект саласында эволюциялық алгоритм (EA) метаэвристикалық оңтайландыруға негізделген жалпы популяциялық есептеулердің ішкі жиыны болып табылады. EA көбею, мутация, рекомбинация және іріктеу сияқты биологиялық дамудан туындаған механизмдерді пайдаланады. Эволюциялық оңтайландыру алгоритмдері мәселесінде кандидаттық шешім популяциядағы жеке тұлғалардың рөлін атқарады. Сондай-ақ фитнес функциясы жауаптардың сапасын анықтайды.

Эволюциялық алгоритмдер көбінесе есептердің барлық түрлеріне жақсы жақындайды. Өйткені олар негізгі фитнес ландшафтына қатысты ешқандай болжам жасамайды. Эволюциялық модельдеу және генетикалық алгоритмдер үшін қолданылатын әдістер әдетте микроэволюциялық процестерді зерттеумен және жасушалық кезеңдерге негізделген модельдерді жоспарлаумен шектеледі. Нақты EA қолданбаларының көпшілігінде есептеу күрделілігі тыйым салатын фактор болып табылады.

Шынындабұл мәселе фитнес функциясын бағалауға қатысты. Фитнес жуықтау - бұл қиындықты жеңудің бір шешімі. Дегенмен, қарапайым көрінетін EA жиі күрделі мәселелерді шеше алады. Сондықтан реттілік пен есептің күрделілігі арасында тікелей байланыс болуы мүмкін емес. Толығырақ ақпаратты "Эволюциялық алгоритмдер" кітаптарынан табуға болады.

Орындау

эволюциялық модельдеу және алгоритмдер
эволюциялық модельдеу және алгоритмдер

Бірінші қадам – кездейсоқ жеке адамдардың бастапқы популяциясын жасау.

Екінші қадам - бұл топтағы әрбір адамның жарамдылығын бағалау (уақыт шегі, жеткілікті дайындық және т.б.).

Үшінші қадам - аяқтау үшін келесі регенерация қадамдарын қайталаңыз:

  1. Өсіру үшін ең қолайлы адамдарды таңдаңыз (ата-ана).
  2. Ұрпақ алу үшін кроссовер және мутация арқылы эволюциялық алгоритмнен өткен жаңа тұлғаларды әкеліңіз.
  3. Жаңа адамдардың жеке жарамдылығын бағалаңыз.
  4. Ең аз қолайлы топты олармен ауыстырыңыз.

Түрлері

Генетикалық алгоритм – эволюциялық реттілік, сарапшы кеңесшісінің ең танымал түрі. Есептің шешімі рекомбинация және мутация (кейде біреу, кейбір жағдайларда екеуі де) сияқты операторларды қолдану арқылы сандар тізбегі түрінде (дәстүрлі екілік, дегенмен ең жақсы көріністер әдетте шешілетін мәселеде көбірек бейнеленетін) ізделеді.). Сарапшы кеңесшісінің бұл түрі оңтайландыру мәселелерінде жиі қолданылады. Мұның тағы бір атауы fetura (латын тілінен аударғанда «туу»):

  1. Генетикалық бағдарламалау. Ол шешімдерді компьютерлік кодтар ретінде ұсынады және олардың жарамдылығы есептеу тапсырмаларын орындау қабілетімен анықталады.
  2. Эволюциялық бағдарламалау. Эволюциялық генетикалық алгоритмге ұқсас, бірақ құрылымы бекітілген және оның сандық параметрлері өзгеруі мүмкін.
  3. Ген экспрессиясын бағдарламалау. Компьютерлік қолданбаларды әзірлейді, бірақ әртүрлі өлшемдегі жобалар бекітілген ұзындықтағы сызықтық хромосомаларда кодталған генотип-фенотип жүйесін зерттейді.
  4. Стратегия. Шешімдердің көрінісі ретінде нақты сандар векторларымен жұмыс істейді. Әдетте өздігінен бейімделетін эволюциялық мутация жылдамдығы алгоритмдерін пайдаланады.
  5. Дифференциалды даму. Векторлық айырмашылықтарға негізделген, сондықтан ең алдымен сандық оңтайландыру мәселелеріне жарамды.
  6. Нейроэволюция. Эволюциялық бағдарламалау және генетикалық алгоритмдерге ұқсас. Бірақ соңғысы қосылымдардың құрылымы мен салмағын сипаттайтын жасанды нейрондық желілер. Геномды кодтау тікелей немесе жанама болуы мүмкін.

Биологиялық процестермен салыстыру

Көптеген эволюциялық алгоритмдердің мүмкін шектеуі генотип пен фенотиптің нақты айырмашылығының болмауы болып табылады. Табиғатта ұрықтанған жұмыртқа жетілу үшін эмбриогенез деп аталатын күрделі процестен өтеді. Бұл жанама кодтау генетикалық іздеулерді сенімдірек етеді (яғни, өлімге әкелетін мутацияларды тудыруы ықтималдығы аз) және ағзаның даму қабілетін жақсартуы мүмкін. Мұндай жанама (басқаша айтқанда,генеративті немесе дамытушы) кодтаулар эволюцияға қоршаған ортадағы заңдылықты пайдалануға мүмкіндік береді.

Жасанды эмбриогенез немесе даму жүйелеріндегі соңғы жұмыстар осы мәселелерді шешуге тырысады. Ген экспрессиясын бағдарламалау кезінде генотип-фенотип аймағы сәтті зерттеледі, мұнда біріншісі бекітілген ұзындықтағы сызықтық мультигенді хромосомалардан, ал екіншісі көптеген экспрессиялық ағаштардан немесе әртүрлі өлшемдер мен пішіндегі компьютерлік бағдарламалардан тұрады.

Қатысты әдістер

эволюциялық алгоритмдер
эволюциялық алгоритмдер

Алгоритмдерге мыналар кіреді:

  1. Құмырсқалар колониясын оңтайландыру. Бұл жәндіктер феромондармен байланысып, жолдар түзе отырып, қорек іздейді деген идеяға негізделген. Негізінен комбинаторлық оңтайландыру және графикалық есептер үшін қолайлы.
  2. Түбірлік жүгірткі алгоритмі. Авторды өсімдік тамырларының табиғаттағы қызметі шабыттандырған.
  3. Жасанды аралар колонияларына арналған алгоритм. Бал араларының мінез-құлқына негізделген. Ол ең алдымен сандық оңтайландыру үшін ұсынылған және комбинаторлық, шектелген және көп мақсатты есептерді шешу үшін кеңейтілген. Ара алгоритмі жәндіктердің жем іздеу әрекетіне негізделген. Ол маршруттау және жоспарлау сияқты көптеген қолданбаларда қолданылған.
  4. Бөлшектер тобын оңтайландыру – жануарлар табынының мінез-құлық идеяларына негізделген. Сондай-ақ, ең алдымен, сандық процесс тапсырмалары үшін қолайлы.

Басқа танымал метаэвристикалық әдістер

  1. Аңшылық іздеу. Белгілі бір жануарларды, мысалы, қасқырларды топпен ұстауға негізделген әдісолжаны қоршау үшін өз міндеттерін таратады. Эволюциялық алгоритм мүшелерінің әрқайсысы басқалармен қандай да бір түрде байланысты. Бұл әсіресе басшыға қатысты. Бұл комбинаторлық процесс әдісі ретінде бейімделген үздіксіз оңтайландыру әдісі.
  2. Өлшемдер бойынша іздеу. Табиғатқа негізделген метаэвристикалық әдістерден айырмашылығы, бейімделу процесінің алгоритмі метафораны негізгі принцип ретінде пайдаланбайды. Керісінше, ол әрбір иерацияда іздеу өлшемінің қатынасы параметрін жаңартуға негізделген қарапайым өнімділікке бағытталған әдісті пайдаланады. Firefly алгоритмі оттықтардың бір-бірін жыпылықтайтын жарығымен қалай тартатынынан шабыттандырады. Бұл әсіресе мультимодальды оңтайландыру үшін пайдалы.
  3. Үйлесімді іздеңіз. Музыканттардың мінез-құлқы туралы идеяларға негізделген. Бұл жағдайда эволюциялық алгоритмдер комбинаторлық оңтайландырудың жолы болып табылады.
  4. Гаусс бейімделуі. Ақпараттық теорияға негізделген. Өнімділік пен орташа қолжетімділікті арттыру үшін пайдаланылады. Бұл жағдайдағы эволюциялық алгоритмдердің мысалы: термодинамикадағы энтропия және ақпарат теориясы.

Memetic

эволюциялық модельдеу
эволюциялық модельдеу

Ричард Доукинстің мем идеясына негізделген гибридті әдіс. Ол әдетте жергілікті нақтылауларды орындауға қабілетті жеке оқыту процедураларымен біріктірілген популяцияға негізделген алгоритм нысанын алады. Мәселеге қатысты білімді пайдалануды және синергетикалық жолмен егжей-тегжейлі және жаһандық іздеулерді ұйымдастыруға тырысады.

Эволюциялықалгоритмдер классикалық NP қиын есептер және толық өңдеуге тым ұзақ уақыт алатын кез келген басқа нәрсе сияқты полиномдық уақытта оңай шешілмейтін есептерге эвристикалық тәсіл болып табылады. Тәуелсіз пайдаланған кезде олар әдетте комбинаторлық есептер үшін қолданылады. Дегенмен, генетикалық алгоритмдер жиі басқа әдістермен бірге пайдаланылады, олар жұмыс істеу үшін бірнеше оңтайлы бастапқы орындарды табудың жылдам жолы ретінде әрекет етеді.

Эволюциялық алгоритмнің алғышарттары (кеңесші ретінде белгілі) сіз табиғи сұрыптау процесімен таныс болсаңыз, өте қарапайым. Ол төрт негізгі қадамнан тұрады:

  • инициализация;
  • таңдау;
  • генетикалық операторлар;
  • соңы.

Осы қадамдардың әрқайсысы шамамен табиғи сұрыпталудың белгілі бір аспектісіне сәйкес келеді және алгоритмдердің сол санатын модульдеудің оңай жолдарын қамтамасыз етеді. Қарапайым тілмен айтқанда, EA-да ең жарамды мүшелер аман қалады және көбейеді, ал жарамсыз мүшелер өледі және келесі ұрпақтың гендік қорына үлес қоспайды.

Инициализация

Алгоритмді бастау үшін алдымен шешімдер жинағын жасау керек. Бастапқыда жиі мүшелер деп аталатын ықтимал проблемалық мәлімдемелердің ерікті саны болады. Олар жиі кездейсоқ түрде жасалады (тапсырманың шектеулері шегінде) немесе, егер кейбір алдыңғы білімдер белгілі болса, идеалды деп есептелетін нәрсеге алдын ала шоғырланған. Халықтың шешімдердің кең ауқымын қамтуы маңызды,өйткені ол негізінен генофонд болып табылады. Сондықтан, егер адам алгоритмнің көптеген әртүрлі мүмкіндіктерін зерттегісі келсе, көптеген әртүрлі гендерге ие болуға ұмтылу керек.

Таңдау

генетикалық кодтар
генетикалық кодтар

Популяция жасалғаннан кейін оның мүшелері енді фитнес функциясына сәйкес бағалануы керек. Фитнес функциясы мүшенің сипаттамаларын алады және мүшенің қаншалықты сәйкес келетінін сандық түрде көрсетеді. Оларды жасау көбінесе өте қиын болуы мүмкін. Деректерді дәл көрсететін жақсы жүйені табу маңызды. Бұл мәселеге өте тән. Енді барлық қатысушылардың жарамдылығын есептеп, ең жақсы мүшелерді таңдау керек.

Бірнеше мақсат функциялары

ЕА-ларды да осы жүйелерді пайдалану үшін кеңейтуге болады. Бұл процесті біршама қиындатады, өйткені оларды пайдалану кезінде бір оңтайлы нүктені анықтаудың орнына жиынтық алынады. Шешімдер жинағы Парето шекарасы деп аталады және олардың ешқайсысы басқа біреуге үстемдік етпейтіні үшін бірдей қолайлы элементтерді қамтиды.

Генетикалық операторлар

Бұл қадам екі ішкі қадамды қамтиды: кроссовер және мутация. Ең жақсы терминдерді таңдағаннан кейін (әдетте бірінші 2, бірақ бұл сан әртүрлі болуы мүмкін), олар енді алгоритмде келесі ұрпақты құру үшін пайдаланылады. Таңдалған ата-ананың сипаттамаларын қолдану арқылы қасиеттердің қоспасы болып табылатын жаңа балалар жасалады. Бұл көбінесе деректер түріне байланысты қиын болуы мүмкін, бірақ әдетте комбинаторлық есептержарамды комбинацияларды араластыру және шығару әбден мүмкін.

Енді ұрпаққа жаңа генетикалық материал енгізу қажет. Егер бұл маңызды қадам жасалмаса, ғалым өте тез жергілікті шектен шығып, оңтайлы нәтижелерге қол жеткізе алмайды. Бұл қадам мутация болып табылады және ол балалардың кішкене бөлігін негізінен ата-ана гендерінің ішкі жиынын көрсетпейтіндей етіп өзгерте отырып, өте қарапайым орындалады. Мутация әдетте ықтималдықпен болады, өйткені баланың оны алу ықтималдығы, сондай-ақ оның ауырлығы таралу арқылы анықталады.

Тоқтату

модельдеу және алгоритмдер
модельдеу және алгоритмдер

Соңында алгоритм аяқталуы керек. Бұл әдетте екі жағдайда орын алады: не ол қандай да бір максималды орындау уақытына жетті немесе өнімділік шегіне жетті. Осы кезде соңғы шешім таңдалады және қайтарылады.

Эволюциялық алгоритмдер мысалы

Енді бұл процестің нәтижесін көрсету үшін сізге кеңесшінің әрекетін көру керек. Ол үшін динозаврлардың бірнеше ұрпағы жүруді (бірте-бірте жерді меңгеру), денесінің құрылымын оңтайландыру және бұлшықет күшін қолдануды қалай үйренгенін еске түсіре аламыз. Бауырымен жорғалаушылардың ерте ұрпақтары жүре алмаса да, кеңесші оларды мутация және кроссовер арқылы уақыт өте келе жүре алатын пішінге айналдыра алды.

Бұл алгоритмдер қазіргі әлемде өзекті бола түсуде, өйткені оларға негізделген шешімдер цифрлық маркетинг, қаржы жәнеденсаулық сақтау.

EA қай жерде қолданылады?

Кеңірек айтқанда, эволюциялық алгоритмдер кескіндерді өңдеу, көлікті бағыттау, мобильді байланысты оңтайландыру, бағдарламалық жасақтаманы әзірлеу және тіпті жасанды нейрондық желіні оқыту сияқты көптеген қолданбаларда қолданылады. Бұл құралдар адамдар күнделікті қолданатын көптеген қолданбалар мен веб-сайттардың, соның ішінде Google Maps және тіпті The Sims сияқты ойындардың негізі болып табылады. Сонымен қатар, медицина саласы қатерлі ісік ауруын емдеуге қатысты клиникалық шешімдер қабылдауға көмектесу үшін EA пайдаланады. Шын мәнінде, эволюциялық алгоритмдердің сенімділігі сонша, оларды кез келген дерлік оңтайландыру мәселесін шешуге пайдалануға болады.

Мур заңы

ЭО-ның өсіп келе жатқан таралуы екі негізгі факторға байланысты: қол жетімді есептеу қуаты және үлкен деректер жинақтарының жинақталуы. Біріншісін Мур заңымен сипаттауға болады, ол негізінен компьютердегі есептеу қуатының мөлшері шамамен екі жыл сайын екі есе өсетінін айтады. Бұл болжам ондаған жылдар бойы орындалды. Екінші фактор технологияларға өсіп келе жатқан тәуелділікке қатысты, бұл мекемелерге трендтерді талдауға және өнімдерді оңтайландыруға мүмкіндік беретін керемет үлкен көлемдегі деректер жинауға мүмкіндік береді.

Эволюциялық алгоритмдер маркетологтарға қалай көмектеседі?

генетикалық модельдеу
генетикалық модельдеу

Нарық жағдайлары тез өзгеруде және өте бәсекеге қабілетті. Бұл маркетинг менеджерлерін жақсырақ шешім қабылдау үшін бәсекелесуге мәжбүр етті. Қол жетімділікті арттыруЕсептеу қуаты жұмысшыларды мәселелерді шешу үшін EA қолдануға итермеледі.

Түрлендіруді оңтайландыру

модельдеу және генетикалық алгоритмдер
модельдеу және генетикалық алгоритмдер

Басты мақсаттардың бірі – сайтқа келушілер санын арттыру. Бұл мәселе маркетологтың қалағанын жасайтын пайдаланушылар санын оңтайландыруға байланысты. Мысалы, егер компания ноутбук сататын болса, бұл өнімді сатып алатын сайтқа кірушілердің санын көбейту. Бұл конверсия жылдамдығын оңтайландырудың мәні.

Таңқаларлық маңызды аспектілердің бірі - пайдаланушы интерфейсін таңдау. Егер веб-дизайн қолданушыға өте ыңғайлы болмаса, өнімді бір немесе басқа себептермен сатып алмайтындар бар. Мұндағы мақсат – конверсия жасамайтын пайдаланушылар санын азайту, бұл жалпы табысты арттырады.

Ұсынылған: