Еволюционни алгоритми: какво представляват и защо са необходими

В региона изкуствен интелект еволюционният алгоритъм (ЕА) е подмножество на изчисленията на общата популация, базирано на метаевристична оптимизация. EA използваше механизми, вдъхновени от биологичното развитие, като възпроизвеждане, мутация, рекомбинация и подбор. Кандидат-решението в проблема на еволюционните оптимизационни алгоритми играе ролята на индивиди в популация. А функцията за пригодност определя качеството на отговорите.

Еволюционните алгоритми често приближават добре решенията на всички видове проблеми. Тъй като в идеалния случай те не правят никакви предположения за основния пейзаж на фитнес. Методите, използвани за еволюционно моделиране и генетични алгоритми, обикновено се ограничават до изследвания на микроеволюционни процеси и модели за планиране, базирани на клетъчни етапи. В повечето реални приложения на ЕА изчислителната сложност е непосилен фактор.

Всъщност този проблем е свързан с оценката на функцията за годност. Приближаването на фитнес е едно от решенията за преодоляване на тази трудност. Въпреки това, на пръв поглед простата ЕА може да реши често сложни проблеми. Следователно не може да има пряка връзка между сложността на последователността и проблема. Можете да прочетете повече в книгите "Еволюционни алгоритми".

Изпълнение

Първата стъпка е да се създаде първоначална популация от индивиди в случаен ред.

Втората стъпка е да се оцени пригодността на всяко лице в тази група (времеви ограничения, адекватност на обучението и т.н.). д.).

Третата стъпка е да повторите следните стъпки за регенериране до завършване:

1. Избор на най-подходящите индивиди за размножаване (родители).
2. Развъждане на нови индивиди, които са преминали през еволюционен алгоритъм с помощта на кръстосване и мутация, за да се получи потомство.
3. Оценка на индивидуалната пригодност на новите индивиди.
4. Заместете с тях най-малко подходящото население.

Видове

Генетичният алгоритъм е еволюционна последователност, най-популярният тип съветник. В търсене на решение на проблема в като низове числа (традиционно двоични, въпреки че най-добрите представяния обикновено са тези, които отразяват по-голямото от двете числа в решавания проблем) чрез прилагане на оператори като рекомбинация и мутация (понякога един, а в някои случаи и двата). Този тип съветникът често се използва в задачи за оптимизация. Другото наименование на този процес е fetura (от латински - "раждане"):

1. Генетично програмиране. В него решенията се представят като компютърни кодове и тяхната пригодност се определя от способността им да изпълняват изчислителни задачи.
2. Еволюционно програмиране. Подобно на еволюционен генетичен алгоритъм, но структурата е фиксирана, а числените параметри могат да се променят.
3. Програмиране на генната експресия. Разработва изчислителни приложения, но изследва система генотип-фенотип, при която проекти с различни размери са кодирани в линейни хромозоми с фиксирана дължина.
4. Стратегия. Работа с вектори от реални числа като представяне на решения. Обикновено се използват самоадаптивни еволюционни алгоритми със скорост на мутация.
5. Диференцирано развитие. Създаден е на базата на векторни разлики и следователно е подходящ предимно за числени проблеми на оптимизацията.
6. Невроеволюция. Подобно на еволюционното програмиране и генетичните алгоритми. Но последните са изкуствени невронни мрежи, които описват структурата и теглото на връзките. Кодирането на генома може да бъде пряко или непряко.

Сравнение с биологични процеси

Възможно ограничение на много еволюционни алгоритми е липсата на ясно разграничение между генотип и фенотип. В природата оплодената яйцеклетка преминава през сложен процес, известен като ембриогенеза, за да узрее. Смята се, че това непряко кодиране прави генетичните търсения по-надеждни (т.е. намалява вероятността от фатални мутации) и може също така да подобри способността на организма да еволюира. Подобно непряко (с други думи, генеративно или развиващо) кодиране също така позволява на еволюцията да използва закономерностите в на околната среда.

Последните разработки в областта на изкуствения ембриогенезис или системите за развитие се стремят да решат тези проблеми. Програмирането на генната експресия успешно изследва областта генотип-фенотип, където първото се състои от линейни многогенни хромозоми с фиксирана дължина, а второто - от множество експресионни дървета или компютърни програми с различни размери и форми.

Свързани техники

Алгоритмите включват:

1. Оптимизация с колония от мравки. Той се основава на идеите за търсене на храна от насекоми, които използват феромонови връзки за формиране на пътища. Подходящ предимно за комбинаторна оптимизация и графови проблеми.
2. Алгоритъмът runner-root. Създателят е вдъхновен от функцията на корените на растенията в природата.
3. Алгоритъмът на изкуственото пчелно семейство. Въз основа на поведението на медоносните пчели. Първоначално е предложена за числено оптимизиране и е разширена за решаване на комбинаторни, ограничени и многоцелеви проблеми. Алгоритъм на пчелите, базиран на хранителното поведение на насекомите. Прилага се в много приложения като маршрутизиране и планиране.
4. Оптимизация с рояк частици - въз основа на идеи за поведението на стадата животни. Той е подходящ и за решаване на числени задачи, свързани с процеси.

Други популационни метаевристики

1. Търсене на лов. Метод, основан на груповото улавяне на някои животни, например вълци, които разделят плячката си. Всеки член на еволюционния алгоритъм е свързан с другия по някакъв начин. Това важи с особена сила за водача. Това е метод за непрекъсната оптимизация, адаптиран като метод на комбинаторни процеси.
2. Търсене в измеренията. За разлика от метаевристичните методи, базирани на природата, алгоритъмът на адаптивния процес не използва метафора като основен принцип. Вместо това се прилага прост метод, ориентиран към производителността, който се основава на актуализиране на параметъра на съотношението на измеренията на търсенето на всяка итерация. Алгоритъмът Firefly е вдъхновен от поведението на светулките, които се привличат една друга чрез мигане. Това е особено полезно за мултимодална оптимизация.
3. Търсене на хармония. Въз основа на идеи за поведението на музиканта. В този случай еволюционните алгоритми са метод, който е подходящ за комбинаторна оптимизация.
4. Адаптиране на Гаус. Въз основа на теорията на информацията. Използва се за постигане на максимална производителност и средна пригодност. Пример за еволюционни алгоритми в тази ситуация: ентропията в термодинамиката и теорията на информацията.

Меметичен

Хибриден метод, основан на идеята на Ричард Докинс за мем. Обикновено той е под формата на алгоритъм, базиран на агрегиране, съчетан с индивидуални процедури за обучение, които могат да извършват локални уточнения. Подчертава използването на знания за конкретния проблем и се опитва да организира прецизно и глобално търсене по синергичен начин.

Еволюционните алгоритми представляват евристичен подход към проблеми, които не могат лесно да бъдат решени за полиномиално време, като например класически NP-сложни проблеми и всички други, които биха отнели твърде много време за изчерпателна обработка. Когато се използват самостоятелно, те обикновено се прилагат за комбинаторни проблеми. Генетичните алгоритми обаче често се използват заедно с други методи, като служат за бърз начин за намиране на няколко оптимални начални места да работите с.

Предпоставката за еволюционен алгоритъм (известен като ЕА) е доста проста, ако сте запознати с процеса на естествен подбор. Той съдържа четири основни стъпки:

• инициализация;
• избор;
• генетични оператори;
• прекратяване.

Всяка от тези стъпки съответства приблизително на определен аспект на естествения подбор и осигурява прости начини за модулно прилагане на тази категория алгоритми. Просто казано, в ЕА по-приспособените членове ще оцелеят и ще се възпроизвеждат, докато неприспособените членове ще умрат и няма да допринесат за генофонда на бъдещите поколения.

Иницииране

За да стартирате алгоритъм, първо трябва да създадете набор от решения. Популацията ще съдържа произволен брой възможни решения на проблема, често наричани членове. Те често се създават на случаен принцип (в рамките на ограниченията на задачата) или, ако са известни някакви предварителни знания, условно се концентрират около считания за идеален вариант. Важно е популацията да обхваща широк спектър от решения, тъй като по същество тя е генофонд. Следователно, ако искаме да изследваме много различни възможности в рамките на алгоритъма, трябва да се стремим към много различни гени.

Избор на

След като популацията е създадена, нейните членове трябва да бъдат оценени според функцията за пригодност. Фитнес функцията взема характеристиките на члена и дава цифрово изражение на неговата жизнеспособност. Създаването им често може да бъде много трудно. Важно е да се намери добра система, която точно да представя данните. Това е много специфично за проблема. Сега е необходимо да се изчисли годността на всички членове и да се избере част от най-добрите членове.

Няколко целеви функции

Експертните оценки също могат да бъдат разширени, за да използват тези системи. Това донякъде усложнява процеса, тъй като вместо да се определи една единствена оптимална точка, се получава набор от тях. Множеството от решения се нарича граница на Парето и съдържа елементи, които са еднакво подходящи в смисъл, че нито едно от тях не доминира над друго.

Генетични оператори

Тази стъпка включва две подстъпки: кръстосване и мутация. След като изберете най-добрите членове (обикновено първите 2, но броят им може да варира), те се използват за създаване на следващото поколение в алгоритъма. Чрез прилагане на характеристиките на избраните родители се създават нови деца, които са смесица от качества. Това често може да бъде трудно в зависимост от вида на данните, но обикновено е напълно възможно при комбинаторни проблеми да се смесват и съчетават валидни комбинации от.

Сега е необходимо да се въведе нов генетичен материал в поколението. Ако човек не направи този важен стъпка, тогава ученият много бързо ще затъне в локални екстремуми и няма да получи оптимални резултати. Тази стъпка е мутация и се извършва съвсем просто чрез промяна на малка част от децата, така че те да не отразяват предимно подгрупи от гените на родителите. Мутацията обикновено се проявява вероятностно, тъй като вероятността детето да я получи, както и нейната тежест, се определят от разпределение.

Прекратяване

В крайна сметка алгоритъмът трябва да приключи. Обикновено това се случва в два случая: или е достигнато някакво максимално време за изпълнение, или е достигнат праг на производителност. На този етап се избира окончателното решение и се връща.

Пример за еволюционни алгоритми

Сега, за да илюстрираме резултата от този процес, трябва да разгледаме ЕА в действие. Можем да си представим няколко поколения динозаври, които се научават да ходят (постепенно овладяват земята), като оптимизират структурата на тялото си и упражняват мускулна сила. Въпреки че ранните влечуги не са можели да ходят, ЕА е успял да ги развие с течение на времето чрез мутации и кръстосване до форма, способна да ходи.

Тези алгоритми стават все по-актуални в съвременния свят, тъй като решенията, базирани на тях, се използват все по-често в индустрии като цифровия маркетинг, финансите и здравеопазването.

Къде се използват оценките на въздействието?

В по-широк смисъл еволюционните алгоритми се прилагат в от всички видове Приложения като обработка на изображения, маршрутизиране на превозни средства, мобилна оптимизация, разработване на софтуер и дори обучение на изкуствени невронни мрежи. Тези инструменти са в основата на много от приложенията и уебсайтовете, които хората използват всеки ден, включително Google Maps и дори игри като The Sims. Освен това в медицината се използват ИО за подпомагане на вземането на клинични решения относно лечението на рак. Всъщност еволюционните алгоритми са толкова надеждни, че могат да се използват за решаване на почти всеки оптимизационен проблем.

Законът на Мур

Нарастващото разпространение на оценките на въздействието се дължи на два основни фактора: наличната изчислителна мощност и натрупването на големи масиви от данни. Първият може да се опише със закона на Мур, който по същество гласи, че изчислителната мощ на компютъра се удвоява приблизително на всеки две години. Тази прогноза е валидна от десетилетия. Вторият фактор е свързан с нарастващата зависимост от технологиите, които позволяват на институциите да събират невероятно количество данни, за да анализират тенденциите и да оптимизират продуктите.

Как еволюционните алгоритми могат да помогнат на търговците?

Пазарните условия се променят бързо и са много конкурентни. Това кара маркетинг мениджърите да се конкурират за най-добрите вземане на решения. Увеличаване на наличната изчислителна мощност ръководени служители да използват СУ за решаване на проблеми.

оптимизация на реализациите

Една от основните цели е да се увеличи броят на посетителите на уебсайта. Предизвикателството се свежда до оптимизиране на броя на потребителите, които правят това, което маркетологът иска от тях. Например, ако дадена компания продава лаптопи, в идеалния случай тя трябва да увеличи броя на посетителите на сайта, които в крайна сметка купуват продукта. Това е същността на оптимизацията на коефициента на преобразуване.

Един изненадващо важен аспект е изборът на потребителски интерфейс. Ако уеб дизайнът не е много удобен за потребителя, има хора, които в крайна сметка не купуват продукта по една или друга причина. Целта е да се намали броят на потребителите, които в крайна сметка не се конвертират, като по този начин се увеличи общата печалба.