Кіріспе
Эволюциялық есептеудің кіші жиыны
Есептеу интеллектісінде (CI) эволюциялық алгоритм (EA) – эволюциялық есептеудің кіші жиыны, жалпы халыққа негізделген метаэвристикалық оңтайландыру алгоритмі. EA биологиялық эволюциядан шабыттанған механизмдерді қолданады, мысалы, көбею, мутация, рекомбинация және таңдау. Оптимизациялау мәселесінің мүмкін болатын шешімдері популяциядағы жеке тұлғалардың рөлін атқарады, ал жарамдылық функциясы шешімдердің сапасын анықтайды (сондай-ақ жоғалту функциясын қараңыз). Популяцияның эволюциясы жоғарыда аталған операторларды қайталап қолданғаннан кейін жүзеге асады. Эволюциялық алгоритмдер әртүрлі проблемаларға жақын шешімдер табуда өте жақсы нәтижелер көрсетеді, себебі олар негізгі жарамдылық ландшафты туралы ешқандай болжам жасамайды. Биологиялық эволюцияны модельдеуге қолданылатын эволюциялық алгоритмдерден алынған әдістер көбінесе микроэволюциялық процестерді зерттеумен және жасушалық процестерге негізделген жоспарлау модельдерімен шектеледі. EA-ның көптеген нақты қолданылуларында есептеу күрделілігі шектеуші фактор болып табылады. Шындығында, бұл есептеу күрделілігі жарамдылық функциясын бағалауға байланысты. Жарамдылықты жуықтау осы қиындықты жеңудің бір жолы болып табылады. Дегенмен, сырттай қарағанда қарапайым EA жиі күрделі мәселелерді шеше алады; сондықтан алгоритмнің күрделілігі мен проблеманың күрделілігі арасында тікелей байланыс болуы мүмкін емес. Эволюциялық алгоритмдерді Монте-Карло әдісінің бір түрі деп қарастыруға болады.
Түрлері
Ұқсас әдістер генетикалық бейнелеу және басқа да іске асыру егжей-тегжейлерімен, сондай-ақ қолданылатын нақты мәселенің сипатымен ерекшеленеді. Генетикалық алгоритм – Бұл ЭА-ның ең танымал түрі. Ол мәселені сандар тізбегі түрінде шешуді іздейді (әдетте екілік, бірақ ең жақсы бейнелеулер көбінесе шешіліп жатқан мәселе туралы ақпаратты көрсетеді). Дифференциалдық эволюция – Векторлық айырмашылықтарға негізделген, сондықтан ол негізінен сандық оңтайландыру мәселелеріне жарайды. Бірлескен эволюциялық алгоритм – Генетикалық алгоритмдер мен эволюциялық стратегияларға ұқсас, бірақ жасалған шешімдер басқа шешімдермен өзара әрекеттесу нәтижелері негізінде салыстырылады. Іздеу процесінде шешімдер бәсекелесе де, ынтымақтаса да жұмыс істей алады. Бірлескен эволюциялық алгоритмдер көбінесе фитнес ландшафты динамикалық, күрделі немесе бәсекелестік өзара әрекеттесуді қамтитын жағдайларда қолданылады. Нейроэволюция – Генетикалық бағдарламалауға ұқсас, бірақ геномдар құрылым мен байланыс салмақтарын сипаттау арқылы жасанды нейрондық желілерді көрсетеді. Геномдық кодтау тікелей немесе жанама болуы мүмкін. Оқу жіктегіш жүйесі – Мұнда шешім – жіктегіштердің жиынтығы (ережелер немесе шарттар). Мичиган LCS жеке жіктегіштер деңгейінде эволюциялайды, ал Питтсбург LCS жіктегіш жиынтықтарының популяцияларын пайдаланады. Бастапқыда жіктегіштер тек екілік болды, бірақ қазір нақты, нейрондық желі немесе S-өрнек типтерін де қамтиды. Фитнес әдетте күш немесе дәлдік негізінде күшейту оқытуы немесе қадағалаумен оқыту арқылы анықталады. Сапа-Түрлілік алгоритмдері – QD алгоритмдері бір мезгілде жоғары сапалы және әртүрлі шешімдерге қол жеткізуге бағытталған. Мәселеге ең жақсы шешімді табуға ғана бағытталған дәстүрлі оңтайландыру алгоритмдерінен айырмашылығы, QD алгоритмдері мәселе кеңістігінде әртүрлі шешімдерді зерттейді және жоғары өнімділікпен ғана емес, сонымен қатар әртүрлі және бірегей шешімдерді сақтайды.
Differential evolution – Based on vector differences and is therefore primarily suited for numerical optimization problems. Coevolutionary algorithm – Similar to genetic algorithms and evolution strategies, but the created solutions are compared on the basis of their outcomes from interactions with other solutions. Solutions can either compete or cooperate during the search process. Coevolutionary algorithms are often used in scenarios where the fitness landscape is dynamic, complex, or involves competitive interactions. Neuroevolution – Similar to genetic programming but the genomes represent artificial neural networks by describing structure and connection weights. The genome encoding can be direct or indirect. Learning classifier system – Here the solution is a set of classifiers (rules or conditions). A Michigan LCS evolves at the level of individual classifiers whereas a Pittsburgh LCS uses populations of classifier sets. Initially, classifiers were only binary, but now include real, neural net, or S expression types. Fitness is typically determined with either a strength or accuracy based reinforcement learning or supervised learning approach. Quality–Diversity algorithms – QD algorithms simultaneously aim for high quality and diverse solutions. Unlike traditional optimization algorithms that solely focus on finding the best solution to a problem, QD algorithms explore a wide variety of solutions across a problem space and keep those that are not just high performing, but also diverse and unique.
Теориялық негіздер
Келесі теориялық қағидалар барлық немесе дерлік барлық ЭА-ға қолданылады.
Тегін түскі ас теоремасы жоқ
Оптимизацияның "тегін түскі ас" теоремасы барлық оптимизациялық стратегиялардың барлық оптимизациялық проблемалар жиынтығы қарастырылғанда бірдей тиімді екенін көрсетеді. Осыған сәйкес, эволюциялық алгоритмдердің біреуі екіншісінен түбірлі жақсырақ болмайды. Бұл жағдай тек барлық проблемалар жиынтығы шектелгенде ғана мүмкін. Бірақ іс жүзінде осылай жасалады. Сондықтан, эволюциялық алгоритмді (ЭА) жақсарту үшін, ол проблема туралы білімді қандай да бір формада пайдалануы керек (мысалы, белгілі бір мутация күшін таңдау арқылы немесе проблемаға бейімделген кодтауды қолдану арқылы). Егер екі ЭА салыстырылатын болса, онда осы шектеу ескеріледі. Сонымен қатар, ЭА проблемаға қатысты білімді қолдана алады, мысалы, бастапқы популяцияны толығымен кездейсоқ түрде емес, эвристикалық әдістер немесе басқа процедуралар арқылы құру арқылы. ЭА-ны нақты проблемалық аймаққа бейімдеудің тағы бір жолы – ұрпақ құру процесіне тиісті эвристикалық әдістерді, жергілікті іздеу процедураларын немесе проблемамен байланысты басқа процедураларды қосу. ЭА-ның осы кеңейтілген түрі меметикалық алгоритм деп аталады. Екі кеңейтім де практикалық қолдануларда маңызды рөл атқарады, себебі олар іздеу процесін жылдамдатуға және оны сенімдірек етуге мүмкіндік береді.
Ынтымақтастық
Ұрпақтан басқа, келесі ұрпақты қалыптастыру үшін ата-ана ұрпағының ең жақсы жеке тұлғасы да пайдаланылатын ЭА-лар үшін (элиталық ЭА деп аталады), егер оптимум болса, конвергенцияның жалпы дәлелі бар. Дәлелдеу үшін, ең көп іздеу қарастырылады: Элиталық ұрпақты қабылдау қасиеті мен оптимумның болуынан, әр ұрпақта сәйкес ең жақсы жеке тұлғаның жарамдылығының жақсаруы белгілі бір ықтималдықпен болады. Яғни, жарамдылық мәндері монотонды түрде өспейтін тізбек құрайды, бұл тізбек оптимумның болуына байланысты шектеулі. Осыдан тізбектің оптимумға қарай конвергенциясы шығады. Дәлелдеме конвергенция жылдамдығы туралы ешқандай мәлімдеме жасамағандықтан, ЭА-ның практикалық қолданылуында көмегі аз. Бірақ ол элиталық ЭА-ны қолдану туралы ұсынысты негіздейді. Дегенмен, әдеттегі панмиктикалық популяциялық модельді қолданғанда, элиталық ЭА-лар элиталық емес ЭА-лардан гөрі ертерек конвергенцияға бейім. Панмиктикалық популяциялық модельде жұптасу таңдауы (іске асыру туралы бөлімнің 2-қадамы) популяциядағы кез келген жеке тұлғаның жұптасуға қабілетті болуын қамтамасыз етеді. Панмиктикалық емес популяцияларда таңдау тиісті түрде шектеледі, соның салдарынан жақсы жеке тұлғалардың таралу жылдамдығы панмиктикалықтарға қарағанда төмендейді. Осылайша, элиталық ЭА-ның ертерек конвергенциясының жалпы тәуекелі жұптасу таңдауын шектейтін тиісті популяциялық модельдер арқылы айтарлықтай азайтылуы мүмкін.
From the property of elitist offspring acceptance and the existence of the optimum it follows that per generation an improvement of the fitness of the respective best individual will occur with a probability Thus:
I. e., the fitness values represent a monotonically non decreasing sequence, which is bounded due to the existence of the optimum. From this follows the convergence of the sequence against the optimum. Since the proof makes no statement about the speed of convergence, it is of little help in practical applications of EAs. But it does justify the recommendation to use elitist EAs. However, when using the usual panmictic population model, elitist EAs tend to converge prematurely more than non elitist ones. In a panmictic population model, mate selection (step 2 of the section about implementation) is such that every individual in the entire population is eligible as a mate. In non panmictic populations, selection is suitably restricted, so that the dispersal speed of better individuals is reduced compared to panmictic ones. Thus, the general risk of premature convergence of elitist EAs can be significantly reduced by suitable population models that restrict mate selection.
Виртуалды әліпбилер
Виртуалды әліпбилер теориясымен Дэвид Э. Голдберг 1990 жылы нақты сандарды қолдану арқылы, классикалық рекомбинация операторларын (мысалы, біркелкі немесе n-нүктелік кроссовер) пайдаланатын эволюциялық алгоритмнің (ЭА) іздеу кеңістігінің белгілі бір аймақтарына жете алмайтынын көрсетті, бұл екілік сандармен кодтаудан өзгеше. Осыдан нақты сандармен бейнеленетін ЭА үшін рекомбинацияда арифметикалық операторларды (мысалы, арифметикалық орташа немесе аралық рекомбинация) қолдану ұсынылады. Тиісті операторларды пайдаланғанда, нақты мәнді бейнелеулер екілік бейнелеулерге қарағанда тиімдірек болып шығады, бұл бұрынғы пікірге қайшы келеді.
Биологиялық процестермен салыстыру
Көптеген эволюциялық алгоритмдердің кемшілігі – генотип пен фенотип арасындағы нақты айырманың болмауы. Табиғатта ұрықтанған жұмыртқа жасушасы эмбриогенез деп аталатын күрделі процестен өтіп, жетілген фенотипке айналады. Осы тікелей емес кодтау генетикалық іздеуді сенімдірек етеді деп саналады (яғни, қатаң мутациялардың болу ықтималдығын азайтады) және организмнің эволюцияға бейімделуін жақсарта алады. Мұндай тікелей емес (генеративті немесе дамушы деп те аталады) кодтаулар эволюцияға ортадағы үлгілерді пайдалануға мүмкіндік береді. Жасанды эмбриогенез немесе жасанды даму жүйелері саласындағы жаңа зерттеулер осы мәселелерді шешуге бағытталған. Гендік экспрессия бағдарламалау генотип-фенотип жүйесін табысты зерттейді, онда генотип – белгілі бір ұзындықтағы сызықтық көпгендік хромосомалардан, ал фенотип – әртүрлі өлшемдер мен пішіндердегі бірнеше экспрессиялық ағаштардан немесе компьютерлік бағдарламалардан тұрады.
Қолданбалар
Эволюциялық алгоритмдер іс жүзінде қолданылатын салалар – инженерлік, күрделі жоспарлау, ауыл шаруашылығы, роботтардың қозғалысын жоспарлау, сондай-ақ қаржы, зерттеу және өнер салаларында шексіз көп. Эволюциялық алгоритмді қолдану тәжірибесіз пайдаланушыдан ойлау жүйесін өзгертуді талап етеді, себебі ЭА арқылы міндетке жақындасу тәсілі дәстүрлі нақты әдістерден өзгеше, және мұндай әдістер инженерлердің немесе басқа мамандықтардың оқу бағдарламаларында көбінесе қарастырылмайды. Мысалы, жарамдылықты бағалау тек мақсатты ғана емес, сонымен қатар оған қатысты эволюциялық іздеу процесін де қолдауы керек, мысалы, бастапқы сапа критерийлерін жақсартуға әкелмейтін жақсартуларды марапаттау арқылы. Мысалы, егер жоспарлау міндетінде персоналды орналастыру немесе энергияны тұтыну сияқты ресурстардың ең жоғары деңгейін болдырмау қажет болса, тек ең жоғары деңгейді бағалау жеткіліксіз. Керісінше, әлі де қабылданатын деңгейден асып кетулердің саны мен ұзақтығы да тіркелуі керек, осылайша нақты ең жоғары деңгейден төмендетуге ынталандыру жасалады. Сондықтан, бастаушыларға арналған және жаңадан бастаушылардың қателіктерін болдырмауға көмектесетін, сондай-ақ қолданбалы жобаны сәтті аяқтауға бағытталған бірнеше жарияланымдар бар. Бұл мәселені шешу үшін ЭА-ны қашан қолдану керек және қашан қолданбаған жөн деген негізгі сұраққа жауап беруді қамтиды.
Мысалдар
2020 жылы Google компаниясы өздерінің AutoML Zero жүйесі нейрондық желілер концепциясы сияқты классикалық алгоритмдерді сәтті қайта ашуға қабілетті екенін мәлімдеді. Tierra және Avida компьютерлік симуляциялары макроэволюциялық динамиканы модельдеуге ұмтылады.