Лекция #17. GA (Генетические Алгоритмы + addon). [Лектор - xmvlad]

Автор: Vladislav Gusev

Полный лог лекции: http://www.everfall.com/paste/id.php?rrl0azjec5us
В лекции были мало затронуты  вопросы практического применения скорее всего 09.03.2006 20:00 (MSK) будет аддон (я надеюсь).

<xmvlad> ладно начнем потихоньку :)
<xmvlad> Disclaimer to kas: лектор предупреждает, что информация полученная в результате прослушивания это лекции, может не иметь прямого отношения к геймдеву, хотя лектор постарается привести жизненные примеры. :)
<xmvlad> Что такое ГА? В общем случаи это эволюционный метод оптимизации, проще говоря умный "поиск".
<xmvlad> В ГА все сводится к одному -  оптимизации некоторой целевой функции
<xmvlad> обычна эта целевая функция называется фитнес-функцией
<xmvlad> Таким образом предположим что у нас есть вектор V - какие-то аргументы(параметры) функции, и непосредственно сама функция F(V) - фитнес-функция. V - это некоторая особь нашей популяции. Фитнес-функция для каждой особи V определяет насколько оптимальна - хуже или лучше других. То есть присваивает особи некоторые "очки" - скалярную величину.
<xmvlad> теперь перейдем непосредственно к описанию "стандартного" алгоритма ГА
<xmvlad> 1. Задаем фитнес функцию F(V)
<xmvlad> 2. Задаем способ преобразования предметной области в набор параметров(кодирование). Например если это интегер, то кодированием будет является его бинарное представление
<xmvlad> Вектор V и его кодирование обычно называют хромосомой, элементы хромосомы генами, то есть в примере с интом, инт - это хромосома, бит - это ген
<xmvlad> Особь это по сути чаще всего и есть хромосома.
<xmvlad> Набор Особей образует популюцию.
<xmvlad> и так целевая функция и способ кодирования у нас уже есть.
<xmvlad> 3. Создаем популяцию. Популяция - это набор, множество особей(хромосом), в случае с интом это просто набор интов int Osob1, Osob2 :)
<xmvlad> на этом этапе параметр который мы можем изменять это - Размер популяции.
<xmvlad> Чем больше популяция тем дольше она обрабатывается, чем меньше тем хуже "покрытие" ландшафта функции, то есть ГА может пропустить какой ни буть "резкий" минимиу, застрять в локальном етк
<xmvlad> Однозначаных рекомендация для определения размера популяции не существует. Необходимо пробовать, и исходить из разумности :) то есть выбирать такой размер, что бы за разумное(необходимое) время происходило достаточное количестов генераций новых популяций
<xmvlad> 4. Инициализируем популяци. Наиболее распространненыц способ - присваиваем рэндомные значения нашим особям, например: vector<int> osobi(100, 1); vector - это популяция int особь
<xmvlad> 5. Для каждой особи расчитываем значение фитнес-функции F(V), их можно рассматривать как некоторые "очки" которые определяют какая особь лучше какая хуже.
<xmvlad> главное, это к вопросу о выборе фитнес-функции она ДОЛЖНА иметь рельеф, то есть для двух пусть даже очень похожих особей фитнес-функция должна возращать разные значения: одна особь лучше, другая хуже и никак иначе. (по крайней мере очень желательно)
<xmvlad> возвращаясь к примеру, vector<float> fitnes_value; int i; for (i = 0; i < osobi.size(); ++i)  fitnes_value = FITNES(osobi);
<xmvlad> 6. Теперь мы знаем какие особи у нас хуже, а какие лучше (ближи к оптимуму). Необходимо решить следующую задачу: решить какие особи родят детей, и дети перейдут в следующую популяцию а какие умрут :)
<xmvlad> При этом мы должны руководствоватся тем что лучшие(с более минимальным/максимальным) значение фитнес функции должны переходить в следующую популяцию, а неудачники подыхать :)
<xmvlad> Для этого существуют различные методы:
<xmvlad> 1. Элитарный. (эмперика 20/80). Сортируем особей по значению фитнес функции, выбираем 20% первых лучших особей(элиту :). Они будут размножатся и перейдут в следующую популяцию
<xmvlad> можно не 20 процентов, больше меньше, но обычно советует брать окого 20%
<xmvlad> 2. Пропорциональный стохастичесхий. Этот метод можно представить как колесо рулетки, чем лучше значение фитнес функции особи, тем больше сектор который она занимает на "круге" рулетки, теперь бросаем шарик(рэндом) и выбираем особь. Очевидно что особи с большим значением фитнес функции будут "выпадать" чаще а значит и размножатся переходся в следующую популяцию
<xmvlad> в общем это два основных метода, есть и другие извращения но про них не будем :) интересующимся искать в гугле GA selection operator
<xmvlad> 7. Теперь в случаи Элитарной селекции у нас есть набор - 20% лучших особей. Нам необходим их скрестить и породить от них детей. Для этого необходимо выбрать ДВЕ особи.
<xmvlad> Можно перебрать все пары, можно использовать рэндом для этих 20% процентов пока не заполнится новая популяция.
<xmvlad> В случае пропорционального стохастического, бросаем шарик первый раз - первый родитель, второй раз - второй родитель, и так пока не заполнится новая популяция.
<xmvlad> 8. Мы перешли к самой отвтественной части - порождения новых особей. :) на этом этапе у нас уже есть две особи.
<xmvlad> Необходимо провести "перемешивание"(обмен, "перекрест") их хромосом, данная операция называется кроссинговером. У нас есть два родителя необходим получить одного ребенка.
<xmvlad> Существует несколько способов:
<xmvlad> а) Наиболее распространенный и эффективный - двух точечный кроссинговер
<xmvlad> Представим хромосому наших особей как строку состоящую из генов, для инта это будет строк 0..31, где каждый ген будет являтся одним битом.
<xmvlad> и так у нас есть две строки parent1[0..31] и parent2[0..31],
<xmvlad> суть двухточечного кроссинговера состоиит в том что мы выбираем случайно две "точки" на этих строках. например 5, 20
<xmvlad> и таких образом получаем разбиение хромосомы на несколько отрезков [0..5][6..20][21..31]
<xmvlad> теперь одну часть берем у первого родителя, другую у другого, то есть
<xmvlad> child[0..31] = parent1[0..5], parent2[6..20], parent1[21..31]
<xmvlad> то есть делим строки парентов на две части (концы врапаются) и берем для ребенка одну часть у первого родителя, вторую часть у второго
<xmvlad> это был двухточечный кроссинговер, наиболее эффективный метод.
<xmvlad> б) Юниформный кроссинговер
<xmvlad> для каждой позиции в хромосоме ребенка кидаем монетку, если 0 берем ген у первого родителя, если 1 у второго.
<xmvlad> После кроссинговера мы _почти_ уже получили ребенка :)
<xmvlad> <aloha_hawaii> сколько должно быть детей от каждой пары родителей?
<xmvlad> один обычно так
<xmvlad> но может и большь
<xmvlad> рекомендуют одного

9 марта 2006