В областта на изкуствения интелект, еволюционният алгоритъм (EA) е подмножество от изчисления на общата популация, базирани на метаевристична оптимизация. EA използва механизми, вдъхновени от биологичното развитие, като репродукция, мутация, рекомбинация и селекция. Кандидатното решение в задачата за еволюционни оптимизационни алгоритми играе ролята на индивиди в популацията. Освен това функцията за фитнес определя качеството на отговорите.
Еволюционните алгоритми често приближават добре решенията на всички видове проблеми. Защото в идеалния случай те не правят никакви предположения относно основния фитнес пейзаж. Методите, използвани за еволюционно моделиране и генетични алгоритми, обикновено са ограничени до изследвания на микроеволюционни процеси и модели за планиране, базирани на клетъчни етапи. В повечето реални приложения на EA изчислителната сложност е прекомерен фактор.
Всъщносттози проблем е свързан с оценката на фитнес функцията. Апроксимацията на фитнес е едно от решенията за преодоляване на тази трудност. Въпреки това, един привидно прост EA може да реши често сложни проблеми. Следователно не може да има пряка връзка между сложността на последователността и проблема. Повече подробности можете да намерите в книгите "Еволюционни алгоритми".
Внедряване
Първа стъпка е да създадете първоначална популация от индивиди на случаен принцип.
Втора стъпка е да се оцени пригодността на всеки индивид в тази група (времево ограничение, достатъчна готовност и т.н.).
Трета стъпка - повторете следните стъпки за регенериране до завършване:
- Изберете най-подходящите хора за отглеждане (родители).
- Доведете нови индивиди, които са преминали еволюционния алгоритъм, използвайки кръстосване и мутация, за да получите потомство.
- Оценете индивидуалната годност на новите хора.
- Заменете най-малко подходящата популация с тях.
Видове
Генетичният алгоритъм е еволюционна последователност, най-популярният тип експертен съветник. Решение на проблема се търси под формата на низове от числа (традиционно двоични, въпреки че най-добрите представяния обикновено са тези, които отразяват повече в решавания проблем) чрез прилагане на оператори като рекомбинация и мутация (понякога една, в някои случаи и двете). Този тип експертен съветник често се използва при оптимизационни проблеми. Друго име за това е fetura (от латински за "раждане"):
- Генетично програмиране. Той представя решенията като компютърни кодове и тяхната пригодност се определя от способността им да изпълняват изчислителни задачи.
- Еволюционно програмиране. Подобно на еволюционния генетичен алгоритъм, но структурата е фиксирана и нейните числени параметри могат да се променят.
- Програмиране на генна експресия. Разработва компютърни приложения, но изследва системата генотип-фенотип, където проекти с различни размери са кодирани върху линейни хромозоми с фиксирана дължина.
- Стратегия. Работи с вектори на реални числа като представяне на решения. Обикновено използва самоадаптивни алгоритми за еволюционна скорост на мутация.
- Диференциално развитие. Базиран на векторни разлики и следователно основно подходящ за проблеми с числената оптимизация.
- Невроеволюция. Подобно на еволюционното програмиране и генетичните алгоритми. Но последните са изкуствени невронни мрежи, описващи структурата и тежестта на връзките. Геномното кодиране може да бъде директно или индиректно.
Сравнение с биологични процеси
Възможно ограничение на много еволюционни алгоритми е липсата на ясно разграничение между генотип и фенотип. В природата оплодената яйцеклетка преминава през сложен процес, известен като ембриогенеза, за да стане зряла. Смята се, че това непряко кодиране прави генетичните търсения по-надеждни (т.е. по-малко вероятно да причиняват фатални мутации) и може също да подобри способността на организма да се развива. Такива косвени (с други думи,генеративни или развиващи) кодировки също позволяват на еволюцията да използва редовността в околната среда.
Последната работа в областта на изкуствената ембриогенеза или системите за развитие се стреми да отговори на тези проблеми. При програмиране на генна експресия, областта на генотип-фенотип се изследва успешно, където първата се състои от линейни мултигенни хромозоми с фиксирана дължина, а втората от много експресионни дървета или компютърни програми с различни размери и форми.
Свързани техники
Алгоритмите включват:
- Оптимизация на колонии от мравки. Тя се основава на идеята, че насекомите търсят храна, като се свързват с феромони, за да образуват пътеки. Основно подходящ за комбинирана оптимизация и проблеми с графики.
- Алгоритъм за коренен плъзгач. Създателят е вдъхновен от функцията на корените на растенията в природата.
- Алгоритъм за изкуствени пчелни семейства. Въз основа на поведението на медоносните пчели. Основно се предлага за числена оптимизация и е разширен за решаване на комбинаторни, ограничени и многоцелеви задачи. Алгоритъмът на пчелите се основава на поведението на насекомите за хранене. Прилага се в много приложения като маршрутизиране и планиране.
- Оптимизация на рояка от частици - базирана на идеи за поведение на стадото на животните. И също така предимно подходящ за задачи с числени процеси.
Други популярни метаевристични методи
- Търсене на лов. Метод, базиран на групов улов на определени животни, като например вълци, коиторазпределят задълженията си да обграждат плячката. Всеки от членовете на еволюционния алгоритъм е свързан с останалите по някакъв начин. Това важи особено за лидера. Това е метод за непрекъсната оптимизация, адаптиран като метод на комбинаторен процес.
- Търсене по измервания. За разлика от естествените метаевристични методи, алгоритъмът на адаптивния процес не използва метафората като основен принцип. По-скоро той използва прост метод, ориентиран към производителността, базиран на актуализиране на параметъра на съотношението на търсенето при всяка итерация. Алгоритъмът на Firefly е вдъхновен от това как светулките се привличат взаимно с мигащата си светлина. Това е особено полезно за мултимодална оптимизация.
- Търсете хармония. Въз основа на идеите за поведението на музикантите. В този случай еволюционните алгоритми са начинът за комбинаторна оптимизация.
- Гаусова адаптация. Въз основа на теорията на информацията. Използва се за постигане на максимална производителност и средна наличност. Пример за еволюционни алгоритми в тази ситуация: ентропия в термодинамиката и теория на информацията.
Memetic
Хибриден метод, базиран на идеята на Ричард Докинс за мем. Обикновено е под формата на алгоритъм, базиран на населението, комбиниран с индивидуални учебни процедури, способни да извършват локални усъвършенствания. Набляга на използването на специфични за проблема знания и се опитва да организира фини и глобални търсения по синергичен начин.
ЕволюционноАлгоритмите са евристичен подход към проблеми, които не могат лесно да бъдат решени за полиномиално време, като класически NP-трудни проблеми и всичко друго, което би отнело твърде много време за изчерпателна обработка. Когато се използват самостоятелно, те обикновено се използват за комбинаторни задачи. Въпреки това, генетичните алгоритми често се използват в тандем с други методи, действайки като бърз начин за намиране на множество оптимални начални места за работа.
Предпоставката на еволюционния алгоритъм (известен като съветник) е доста проста, като се има предвид, че сте запознати с процеса на естествения подбор. Той съдържа четири основни стъпки:
- инициализация;
- избор;
- генетични оператори;
- край.
Всяка от тези стъпки приблизително съответства на определен аспект на естествения подбор и предоставя лесни начини за модулиране на тази категория алгоритми. Просто казано, в EA най-подходящите членове ще оцелеят и ще се възпроизвеждат, докато негодни членове ще умрат и няма да допринасят за генофонда на следващото поколение.
Инициализация
За да стартирате алгоритъма, първо трябва да създадете набор от решения. Популацията ще съдържа произволен брой възможни формулировки на проблема, често наричани членове. Те често се генерират на случаен принцип (в рамките на ограниченията на задачата) или, ако са известни някои предварителни знания, ориентирано около това, което се счита за идеално. Важно е населението да покрива широк спектър от решения,защото по същество това е генофонд. Следователно, ако някой иска да изследва много различни възможности в рамките на един алгоритъм, трябва да се стреми да има много различни гени.
Избор
След като популацията е създадена, нейните членове вече трябва да бъдат оценени според фитнес функцията. Функцията за фитнес приема характеристиките на члена и дава числово представяне на това колко годен е членът. Създаването им често може да бъде много трудно. Важно е да се намери добра система, която да представя точно данните. Това е много специфично за проблема. Сега е необходимо да се изчисли пригодността на всички участници и да се изберат някои от най-добрите членове.
Многоцелеви функции
EA също могат да бъдат разширени, за да използват тези системи. Това донякъде усложнява процеса, тъй като вместо да се идентифицира една оптимална точка, при използването им се получава набор. Множеството от решения се нарича граница на Парето и съдържа елементи, които са еднакво подходящи в смисъл, че нито едно от тях не доминира над друг.
Генетични оператори
Тази стъпка включва две подстъпки: кръстосване и мутация. След избиране на най-добрите термини (обикновено първите 2, но този брой може да варира), сега те се използват за създаване на следващото поколение в алгоритъма. Чрез прилагане на характеристиките на избраните родители се създават нови деца, които са смесица от качества. Това често може да бъде трудно в зависимост от вида на данните, но обикновено при комбинаторни проблеминапълно възможно е да се смесват и извеждат валидни комбинации.
Сега е необходимо да се въведе нов генетичен материал в поколението. Ако тази важна стъпка не бъде предприета, ученият много бързо ще се забие в местни крайности и няма да получи оптимални резултати. Тази стъпка е мутация и се прави съвсем просто, променяйки малка част от децата по такъв начин, че те предимно да не отразяват подгрупи от гените на родителите. Мутацията обикновено се случва вероятностно, тъй като вероятността детето да я получи, както и нейната тежест, се определя от разпределението.
Прекратяване
В крайна сметка алгоритъмът трябва да приключи. Това обикновено се случва в два случая: или е достигнало някакво максимално време за изпълнение, или е достигнало праг на производителност. В този момент се избира и връща окончателното решение.
Пример за еволюционни алгоритми
Сега, за да илюстрирате резултата от този процес, трябва да видите съветника в действие. За да направим това, можем да си припомним как няколко поколения динозаври се научиха да ходят (постепенно овладявайки земята), оптимизирайки структурата на тялото си и прилагайки мускулна сила. Въпреки че влечугите от ранното поколение не можеха да ходят, съветникът успя да ги развие с течение на времето чрез мутация и кръстосване във форма, която може да ходи.
Тези алгоритми стават все по-актуални в съвременния свят, тъй като решенията, базирани на тях, се използват все по-често в индустрии като дигитален маркетинг, финанси издравеопазване.
Къде се използват EA?
По-широко, еволюционните алгоритми се използват в голямо разнообразие от приложения като обработка на изображения, маршрутизиране на превозни средства, оптимизиране на мобилните комуникации, разработка на софтуер и дори обучение на изкуствена невронна мрежа. Тези инструменти са в основата на много от приложенията и уебсайтовете, които хората използват ежедневно, включително Google Maps и дори игри като The Sims. В допълнение, медицинската област използва EA, за да помогне при вземането на клинични решения относно лечението на рак. Всъщност еволюционните алгоритми са толкова стабилни, че могат да се използват за решаване на почти всеки проблем с оптимизация.
Законът на Мур
Нарастващото разпространение на EO се дължи на два основни фактора: налична изчислителна мощност и натрупване на големи масиви от данни. Първият може да бъде описан със закона на Мур, който по същество гласи, че количеството изчислителна мощност в компютъра се удвоява приблизително на всеки две години. Това предсказание се изпълнява от десетилетия. Вторият фактор е свързан с нарастващата зависимост от технологиите, което позволява на институциите да събират невероятно голямо количество данни, което им позволява да анализират тенденциите и да оптимизират продуктите.
Как могат еволюционните алгоритми да помогнат на търговците?
Пазарните условия се променят бързо и са много конкурентни. Това принуди маркетинг мениджърите да се състезават за по-добро вземане на решения. Увеличаване на наличнитеизчислителната мощност накара работниците да използват EA за решаване на проблеми.
Оптимизация на реализациите
Една от основните цели е да се увеличи броят на посетителите на сайта. Този проблем се свежда до оптимизиране на броя на потребителите, които правят това, което маркетологът иска. Например, ако една компания продава лаптопи, идеалното е да увеличите броя на посетителите на сайта, които в крайна сметка купуват продукта. Това е същността на оптимизирането на обменния курс.
Един от изненадващо важните аспекти е изборът на потребителски интерфейс. Ако уеб дизайнът не е много удобен за потребителя, има такива, които в крайна сметка не купуват продукта по една или друга причина. Тогава целта е да се намали броят на потребителите, които в крайна сметка не осъществят реализация, което увеличава общата печалба.
