Генетичен алгоритъм

Какво е това

Естествената еволюция може да се моделира като игра, в която наградите за организъм, който играе добре играта на живот, са предаването на генетичния му материал на наследниците му и продължаване на оцеляването му.^[2] В естествената еволюция това колко добре се представя даден индивид зависи от това с кого работи и с кого се конкурира, както и от околната среда. Генетичните алгоритми са симулация на естествения подбор върху популация от кандидат-решения на оптимизационен проблем (хромозоми, индивиди, същества или фенотипове).

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

Програмиране на това на компютър

Псевдокодът е следният:

1. Иницииране: Създават се някои възможни решения; много често те имат случайни стойности.
2. Оценка: Функцията за пригодност оценява всяко решение; оценката е число, което показва колко добре това решение решава проблема.
3. Следващите стъпки се изпълняват, докато се изпълни изискването за спиране:
1. Подбор: Избор на решенията/индивидите за следващата итерация
2. Рекомбинация: Комбинирайте избраните решения
3. Мутация: Случайно променяйте новосъздадените решения
4. Оценка: Приложете функцията за пригодност, вж. стъпка 2.
5. Ако изискването за спиране не е изпълнено, започнете отново със стъпката за избор.

Пример:

Горното описание е абстрактно. Конкретен пример помага.

Приложения

По принцип

Генетичните алгоритми са добри в решаването на проблеми, които включват съставяне на разписания и графици. Те са прилагани и в инженерството. Често се използват за решаване на глобални оптимизационни проблеми.

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

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

В своето Ръководство за проектиране на алгоритми Скина съветва да не се използват генетични алгоритми за каквито и да било задачи: "Съвсем неестествено е да се моделират приложения в термините на генетични оператори като мутация и кръстосване на битови низове. Псевдобиологията добавя още едно ниво на сложност между вас и вашия проблем. Второ, генетичните алгоритми отнемат много дълго време за нетривиални проблеми. [...] Аналогията с еволюцията - при която значителният напредък изисква [sic] милиони години - може да бъде доста подходяща. [...] Никога не съм се сблъсквал с проблем, при който генетичните алгоритми да ми се струват правилният начин да го атакувам. Освен това никога не съм виждал изчислителни резултати, докладвани с помощта на генетични алгоритми, които да са ме впечатлили положително. Придържайте се към симулираното отгряване за вашите евристични нужди от търсене на вуду."

Настолни игри

Настолните игри са много важна част от областта на генетичните алгоритми, прилагани към проблемите на теорията на игрите. Голяма част от ранната работа в областта на изчислителния интелект и игрите беше насочена към класическите настолни игри, като например тик-так-тоу,^[3] шах и дама.^[4] Сега в повечето случаи настолните игри могат да бъдат изиграни от компютър на по-високо ниво от най-добрите хора, дори с техники за сляпо изчерпателно търсене. Играта Го е известно изключение от тази тенденция и досега е устоявала на машинните атаки. Най-добрите компютърни играчи на Го сега играят на нивото на добър начинаещ.^[5][6] Твърди се, че стратегията на Го разчита в голяма степен на разпознаване на модели, а не само на логически анализ, както е при шаха и други по-независими от фигурата игри. Огромният ефективен коефициент на разклонение, необходим за намирането на висококачествени решения, силно ограничава възможността за използване на изпреварващ поглед в рамките на търсенето на последователност от ходове.

Компютърни игри

Генетичният алгоритъм може да се използва в компютърните игри за създаване на изкуствен интелект (компютърът играе срещу вас). Това дава възможност за по-реалистично изживяване в игрите; ако един човешки играч може да намери последователност от стъпки, които винаги водят до успех, дори когато се повтарят в различни игри, не може да остане предизвикателство. И обратното, ако техника за учене, като например генетичен алгоритъм за стратег, може да избегне повтарянето на минали грешки, играта ще има повече възможности за игра.

Генетичните алгоритми се състоят от следните части:

• Метод за представяне на предизвикателството от гледна точка на решението (напр. насочване на войници при атака в стратегическа игра)
• Функция за пригодност или оценка, за да се определи качеството на даден пример (например измерване на щетите, нанесени на противника при такава атака).

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

Ограничения

Използването на генетичен алгоритъм има някои ограничения в сравнение с алтернативни алгоритми за оптимизация:

• Повтарящата се оценка на функцията за годност за сложни проблеми често е най-ограничаващият сегмент на изкуствените еволюционни алгоритми. Намирането на оптимално решение на сложни проблеми често изисква много скъпи оценки на функцията за годност. При реални проблеми, като например проблеми за структурна оптимизация, една оценка на функцията може да изисква от няколко часа до няколко дни пълна симулация. Типичните методи за оптимизация не могат да се справят с такъв тип проблеми. Често се налага да се използва приближение, тъй като изчисляването на точното решение отнема твърде много време. Генетичните алгоритми понякога комбинират различни модели на апроксимация, за да решат сложни проблеми от реалния живот.
• Генетичните алгоритми не се мащабират добре. Това означава, че когато броят на елементите, които са подложени на мутация, е голям, често се наблюдава експоненциално нарастване на размера на пространството за търсене. Това прави изключително трудно използването на техниката при проблеми като проектиране на двигател, къща или самолет. За да се използват генетичните алгоритми при такива проблеми, те трябва да бъдат разбити на възможно най-просто представяне. По тази причина виждаме еволюционни алгоритми, кодиращи проекти за лопатки на вентилатори вместо за двигатели, форми на сгради вместо подробни строителни планове и аероплани вместо проекти на цели самолети. Вторият проблем, свързан със сложността, е въпросът как да се защитят частите, които са еволюирали, за да представят добри решения, от по-нататъшни разрушителни мутации, особено когато оценката на тяхната годност изисква те да се комбинират добре с други части.
• "По-доброто" решение е само в сравнение с други решения. В резултат на това критерият за спиране не е ясен при всеки проблем.
• При много проблеми генетичните алгоритми са склонни да се насочват към локални оптимуми или дори към произволни точки, а не към глобалния оптимум на проблема. Това означава, че алгоритъмът не "знае как" да жертва краткосрочната годност, за да получи по-дългосрочна годност. Вероятността това да се случи зависи от формата на фитнес функцията: някои проблеми улесняват намирането на глобалния оптимум, други може да улеснят функцията да намери локалните оптимуми. Този проблем може да бъде намален чрез използване на различна фитнес функция, увеличаване на степента на мутация или чрез използване на техники за подбор, които поддържат разнообразна популация от решения. Често срещана техника за поддържане на разнообразието е използването на "наказание за ниша": към всяка група индивиди с достатъчно сходство (радиус на нишата) се добавя наказание, което ще намали представителството на тази група в следващите поколения, позволявайки на други (по-малко сходни) индивиди да бъдат запазени в популацията. Този трик обаче може да не е ефективен, в зависимост от пейзажа на проблема. Друга възможна техника би била просто да се замени част от популацията със случайно генерирани индивиди, когато по-голямата част от популацията е твърде сходна помежду си. Разнообразието е важно при генетичните алгоритми (и генетичното програмиране), тъй като кръстосването на хомогенна популация не дава нови решения. При еволюционните стратегии и еволюционното програмиране разнообразието не е от съществено значение поради по-голямата зависимост от мутацията.
• Работата с динамични набори от данни е трудна, тъй като геномите започват да се сближават в началото към решения, които може да не са валидни за по-късните данни. Предложени са няколко метода за решаване на този проблем чрез увеличаване на генетичното разнообразие и предотвратяване на ранната конвергенция - чрез увеличаване на вероятността за мутация, когато качеството на решението спадне (т.нар. задействана хипермутация), или чрез периодично въвеждане на изцяло нови, случайно генерирани елементи в генофонда (т.нар. случайни имигранти). Отново, еволюционните стратегии и еволюционното програмиране могат да бъдат реализирани с така наречената "стратегия на запетайката", при която родителите не се поддържат, а новите родители се избират само от потомците. Това може да бъде по-ефективно при динамични проблеми.
• Генетичните алгоритми не могат ефективно да решават проблеми, при които единствената мярка за пригодност е една единствена мярка за правилно/неправилно решение (като например проблеми за вземане на решения), тъй като няма начин за сходимост към решението (няма хълм за изкачване). В тези случаи случайното търсене може да намери решение толкова бързо, колкото и ГА. Ако обаче ситуацията позволява повторение на опита за успех/неуспех, което дава (евентуално) различни резултати, тогава съотношението между успехите и неуспехите представлява подходяща мярка за годност.
• За специфични оптимизационни проблеми и случаи на проблеми други оптимизационни алгоритми могат да бъдат по-ефективни от генетичните алгоритми по отношение на скоростта на сходимост. Алтернативните и допълващи алгоритми включват стратегии за еволюция, еволюционно програмиране, симулирано отгряване, гаусова адаптация, изкачване по хълмове и интелигентност на рояци (например: оптимизация на колонии от мравки, оптимизация на рояци от частици) и методи, базирани на целочислено линейно програмиране. Пригодността на генетичните алгоритми зависи от обема на знанията за проблема; добре познатите проблеми често имат по-добри, по-специализирани подходи.

История

През 1950 г. Алън Тюринг предлага "обучаваща се машина", която да работи паралелно с принципите на еволюцията. Компютърното симулиране на еволюцията започва още през 1954 г. с работата на Нилс Аал Баричели, който използва компютър в Института за напреднали изследвания в Принстън, Ню Джърси. Неговата публикация от 1954 г. не е широко забелязана. От 1957 г. австралийският количествен генетик Алекс Фрейзър публикува поредица от статии за симулиране на изкуствен подбор на организми с множество локуси, контролиращи измерим признак. От това начало компютърното симулиране на еволюцията от биолозите става по-разпространено в началото на 60-те години, а методите са описани в книгите на Фрейзър и Бърнел (1970 г.) и Кросби (1973 г.). Симулациите на Фрейзър включват всички съществени елементи на съвременните генетични алгоритми. Освен това през 60-те години Ханс-Йоахим Бремерман публикува поредица от статии, в които също се приема популация от решения на оптимизационни задачи, подложена на рекомбинация, мутация и селекция. Изследванията на Бремерман също включват елементите на съвременните генетични алгоритми. Сред другите забележителни ранни пионери са Ричард Фридберг, Джордж Фридман и Майкъл Конрад. Много от ранните статии са препечатани от Fogel (1998).

Въпреки че в работата си, докладвана през 1963 г., Баричели симулира еволюцията на способността да се играе проста игра, изкуствената еволюция става широко признат метод за оптимизация в резултат на работата на Инго Рехенберг и Ханс-Пол Швефел през 60-те и началото на 70-те години на миналия век - групата на Рехенберг успява да реши сложни инженерни проблеми чрез стратегии за еволюция. Друг подход е техниката на еволюционното програмиране на Лорънс Й. Фогел, която е предложена за генериране на изкуствен интелект. Еволюционното програмиране първоначално използваше машини с крайни състояния за прогнозиране на средата и използваше вариации и селекция за оптимизиране на прогнозиращите логики. Генетичните алгоритми в частност станаха популярни благодарение на работата на Джон Холанд в началото на 70-те години на миналия век, и по-специално на книгата му "Адаптация в естествените и изкуствените системи" (1975 г.). Неговата работа води началото си от изследванията на клетъчните автомати, проведени от Холанд и неговите студенти в Мичиганския университет. Холанд въвежда формализирана рамка за прогнозиране на качеството на следващото поколение, известна като теорема за схемата на Холанд. Изследванията в областта на ГА остават предимно теоретични до средата на 80-те години, когато в Питсбърг, Пенсилвания, се провежда Първата международна конференция по генетични алгоритми.