IV. Генетичен Алгоритъм

Основно Описание

Генетичните алгоритми са вдъхновени от Дарвиновата теория за еволюцията. Решенията на проблем с генетични алгоритми е еволюционно.

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

Това се повтаря докато някакво условие (примерно броя популации или доказване на най-доброто решение) е удовлетворено.

Пример
Както вече се знае от главата за пространството на търсене, разрешаването на проблема често може да бъде изразено като търсене за екстремум на функция. Точно това е което представя проблема тук. Някаква функция е дадена и GA опитва да намери минимума на функцията.
Може да опитате стартиране на генетичен алгоритъм в следващия аплет чрез натискане на бутона Start. Графиката представлява пространство на търсене и вертикалните линии представляват решения (точки в пространството на търсене). Червената линия е най-доброто решение, зелените линии са другите.
Бутона Start стартира алгоритъма, Step извършва една стъпка (т.е. формира едно ново поколение), Stop спира алгоритъма и Reset разбърква популацията.

Тук има аплет, но вашия browser не поддържа Java. Ако желаете да видите аплета, моля проверете изисквания за browser.

Скициране на Основния Генетичен Алгоритъм

[Старт] Генериране на случайна популация от n хромозоми (подходящи решения на проблема)
[Жизнеспособност] Изчисляване жизнеспособността f(x) на всеки хромозом n в популацията
[Нова популация] Създаване на нова популация чрез повтаряне на следните стъпки докато новата популация бъде завършена
1. [Селекция] Избиране на два родителски хромозома от популацията съобразно тяхната жизнеспособност (по-добра жизнеспособност, по добри шансове за селекция)
2. [Кръстосване] С кръстосването вероятностно се кръстосват родителите за да формират новото поколение (деца). Ако не бъде извършено кръстосване, поколението е точно копие на родителите.
3. [Мутация] С мутацията вероятностно се мутира новото поколение на някое място (позиция в хромозомата).
4. [Приемане] Поставяне на новото поколение в новата популация
[Заместване] Използване ново-генерираната популация за по-нататъшни изпълнение на алгоритъма
[Проверка] Ако крайното условие е удовлетворено, спиране, и връщане на най-доброто решение в настоящата популация
[Цикъл] Отиди на стъпка 2

Някои Коментари

Както може да се забележи, скицирането на Основния GA е много общо. Има много неща които могат да бъдат описани различно в различни проблеми.

Първият въпрос е как да се създават хромозомите, какъв тип кодиране да се избере. С това е свързано кръстосването и мутацията, двете основни операции на GA. Кодирането, кръстосването и мутацията са представени в следващите глави.

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

Някои от засегнатите въпроси ще бъдат дискутирани по-късно.

Може би има учудване, защо генетичните алгоритми работят. Може да бъде обяснено частично от Schema теорема (Holland), обаче, тази теорема е била критикувана в доста пъти. Ако имате желание да научите повече, преоверете други ресурси.