3 августа 2009 в 23:19

Генетические алгоритмы, распознавание изображений

Генетические алгоритмы достаточно широко используются в задачах оптимизации и обучения нейросетей.
Сами алгоритмы являются итеративными, и, дают лишь приближенноезначение, что, однако, с лихвой компенсируется областью их применения.
Разберем устройство одного из таких алгоритмов на примере распознавания простейшего изображения.
Оперировать мы будем популяциями хромосом (особей), так как алгоритм является итеративным, номер текущей итерации назовем текущей эпохой.
Перед составлением алгоритма определим, что же будет являться нашей задачей, и что будет являться её решением:
Рассмотрим пример нахождения коэффициентов, в уравнении параболы, исходя из нарисованного от руки изображения. В этом случае задача – найти такие коэффициенты, при которых парабола будет максимально точно совпадать с рисунком, решение задачи – набор из трех коэффициентов в уравнении параболы.

Алгоритм предусматривает популяцию неких объектов (хромосом), которые будут бороться за выживание.
Итак, Хромосома – это возможное решение нашей задачи, не важно какое, правильное или нет.
Ген – элементарная частичка информации, в рамках данной задачи, у нас будет три гена – соответственно по одному на каждый коэффициент.
Популяция – набор хромосом текущей эпохи.
Первоначально мы создаём популяцию (желательно из нескольких тысяч хромосом), и заполняем гены произвольной информацией, которая не противоречит условию задачи.
Как и в реальном мире, наши хромосомы будут размножаться и подвергаться различным мутациям. За эти действия отвечают операторы скрещивания (кроссовер) и мутации.

Кроссовер отвечает за передачу признаков родителей своим потомкам, в самой простой реализации он создаёт новую хромосому из генов двух родителей, «донор» очередного гена выбирается произвольным образом.
Оператор мутации призван внести разнообразия в наш островок цифровой жизни, под его действием у хромосомы изменяется произвольный ген.
Fitness-функция: Как и в жизни – не приспособленные виды должны погибать, «чистить» нашу популяцию будет последняя функция, называемая функцией приспособления, или Fitness-функцией.
Для каждой хромосомы эта функция возвращает число, обратно пропорциональное «приспособленности» этой хромосомы, на нее накладываются условия:
Значение Fitness от идеального решения = 0
Это основное условие, но все же желательно подобрать функцию так, чтобы ее значение росло, по мере удаления решения от идеального. Иными словами – чтобы она имела только один минимум.

Теперь можно сформулировать вариант алгоритма
1. Обозначить номер эпохи = 0, создать популяцию хромосом, в генах которых будет произвольная, не противоречащая задаче, информация
2. Посчитать приспособленность популяции
3. Выбрать из популяции особь А
4. С вероятностью P(скрещивания) выбрать особь B и применить оператор кроссовера, результирующую особь занести в новую популяцию.
5. С вероятностью P(мутации) выполнить мутацию произвольной особи, результирующую особь занести в новую популяцию
6. Выполнить операции 3,4,5 n раз, где n >= размера популяции
7. Создать новую популяцию из лучших особей существующей и только что сформированной популяции
8. Увеличить номер текущей эпохи
9. Если результат работы удовлетворителен – остановка алгоритма, иначе – переход к шагу 2.

Генетический алгоритм не является строго детерминированным, например, мы можем сначала выполнить скрещивание всех особей, а потом мутацию (в рамках данной задачи именно этот подход оказался более эффективным). Итак, попробуем, на основе описанного, решить поставленную задачу. Сначала нам понадобится определить хромосому, которая и будет хранилищем информации о генах.
  1. public class Chromosome : IComparable
  2. {
  3.     public double[] gens;
  4.     static Random random = new Random();
  5.  
  6.     public Chromosome()
  7.     {
  8.         this.gens = new double[3];
  9.  
  10.         for (int i = 0; i < 3; i++)
  11.         {
  12.             this.gens[i] = random.NextDouble() * 100;
  13.         }
  14.         this.fit = fitness(this);
  15.     }
  16.     public int CompareTo(object obj)
  17. }
* This source code was highlighted with Source Code Highlighter.


Значение 100 выбрано для примера, это не ограничит общности, даже если искомая парабола будет иметь кофээфициенты >100
Отметим метод CompareTo, позволяющий нам сортировать списки объектов Chromosome.

  1. public class Population
  2. {
  3.     Random random = new Random();
  4.     public List<Chromosome> population;
  5.     public int count;
  6.     public double crossProbability;
  7.     public double MutationProbability;
  8.     public int age;
  9.  
  10.     public Population()
  11.     {
  12.         for (int i = 0; i < 5000; i++)
  13.         {
  14.             this.population.Add(new Chromosome());
  15.         }
  16.     }
  17.      
  18.     public void GoToNextGeneration()
  19.     {
  20.         Chromosome chromosome;
  21.         for (int i = 0; i < count; i++)
  22.         {
  23.             chromosome = population[i];
  24.  
  25.             if (random.NextDouble() < crossProbability)
  26.             {
  27.                 population.Add(Cross(chromosome,population[random.Next(count)]));
  28.             }
  29.         }
  30.  
  31.         for (int i = 0; i < population.Count; i++)
  32.         {
  33.             if (random.NextDouble() < MutationProbability)
  34.             {
  35.                 population.Add(Mutate(population[i]));
  36.             }
  37.         }
  38.  
  39.         population.Sort();
  40.         population.RemoveRange(count,population.Count-count);
  41.  
  42.         age++;
  43.     }
  44.  
  45.     Chromosome Cross(Chromosome a, Chromosome b)
  46.     Chromosome Mutate(Chromosome a)
  47.     double Fitness(Chromosome a)
  48. }
* This source code was highlighted with Source Code Highlighter.


Вот она, эволюция в двадцати строчках! Это и будет сердцем нашей программы.
В первой части мы получаем потомство от уже существующей популяции, и добавляем его в конец списка, т.е. все «дети» будут находится подномерами большими чем count.
Второй шаг – мутация, было бы логично мутировать саму хромосому, а не добавлять мутировавший клон, но в этом случае мы теряем содержащееся в исходной хромосоме решение, а оно может быть лучшим в популяции.
Наконец, в конце мы сортируем всю нашу получившуюся популяцию по возрастанию Fitness функции, (следовательно – по убыванию правильности решения) удаляем наименее «приспособленные» хромосомы, и увеличиваем номер текущей эпохи.

Давайте рассмотрим, что же представляют собой три последние функции, производящии операции над нашими хромосомами?
  1. Chromosome Cross(Chromosome a, Chromosome b)
  2. {
  3.     double[] pair = new double[3];
  4.  
  5.     for (int i = 0; i < 3; i++)
  6.     {
  7.         if ((random.Next() % 2) == 0)
  8.         {
  9.             pair[i] = a.Gens[i] + (b.Gens[i] - a.Gens[i]) * 0.1;
  10.         }
  11.         else
  12.         {
  13.             pair[i] = b.Gens[i] - (b.Gens[i] - a.Gens[i]) * 0.1;
  14.         }
  15.     }
  16.  
  17.     Chromosome result = new Chromosome(pair);
  18.     return result;
  19. }
* This source code was highlighted with Source Code Highlighter.


Реализация оператора кроссовера может быть достаточно разнообразной, и, обычно, подбирается под конкретную задачу. Здесь, с вероятностью 0.5, для каждого гена, потомок получит его от первого родителя или, с такой же вероятностью, от второго родителя.
Поправка (b.Gens[i] — a.Gens[i]) * 0.1 сделана чтобы както разнообразить популяцию новыми генотипом.
  1. Chromosome Mutate(Chromosome a)
  2. {
  3.     double[] pair = (double[])a.Gens.Clone();
  4.     int geneNum = random.Next(3);
  5.     pair[geneNum] = random.NextDouble() * 100;
  6.     return new Chromosome(pair, a.chromosomeSettings);
  7. }
* This source code was highlighted with Source Code Highlighter.


Как и обещано, оператор мутации изменяет один произвольный ген.
Взглянем на самое интересное, как же мы будем определять, насколько близка наша хромосома к идеальному решению?
  1. double GetFitness(Chromosome a)
  2. {
  3.     double result = 0;
  4.     double temp;
  5.     for (int i = 0; i < funcLength; i++)
  6.     {
  7.         temp = Math.Abs(Func(i, a.Gens) - funcArray[i]);
  8.         result += temp;
  9.     }
  10.  
  11.     return result;
  12. }
  13.  
  14. double Func(double x, double[] gens)
  15. {
  16.     double result = 0;
  17.     for (int i =2; i >= 0; i--)
  18.     {
  19.         result += gens[2-i] * Math.Pow(x, i);
  20.     }
  21.     return result;
  22. }
* This source code was highlighted with Source Code Highlighter.


Массив funcArray получается сканированием картинки снизу вверх по столбцам, каждый столбец – индекс массива, высота первой найденной черной точки в столбце – значение.
Функция Func – возвращает значение уравнения 2й степени в точке x, с коэффициентами из массива gens
Получается Fitness – это сумма «погрешностей», для каждой точки нашей параболы, которая есть на рисунке. Такая функция не имеет единственный минимум, но, тем не менее, обеспечивает достаточную сходимость алгоритма.

Результат:

Результат
При количестве хромосом в популяции = 5000, на 25ом поколении мы получаем достаточно близкое сходство.
Данный алгоритм можно расширить на кривые любого порядка =)

Исходники: slil.ru/27874467
UPD: Перенес в искусственный интеллект
+72
5315
135

Комментарии (51)

–76
Niketas, #
Долго же Вы ждали, чтобы написать этот топик (судя по времени регистрации и отсутствию комментариев).
0
n1tra, #
К чему бы это?
+25
Error_403_Forbidden, #
Долго ж ты ждал, чтобы написать эту хуйню
–2
Niketas, #
Хабранарод, вы чего?
Я ничего отрицательного под этим комментарием не подразумевал. Просто наблюдение.
0
ksn, #
Возможно Вы написали бесполезный комментарий.
0
TKing, #
Возможно на Вас отразился эффект первого комментария?
0
Niketas, #
Похоже :-(
Был неправ. Исправлюсь.
+2
Danov, #
Из пушки по воробям ;-) Вы про МНК знаете? На сколько порядков он будет быстрее?
Интересно было бы рассмотреть более сложные примеры, которые другими методами, либо не решаются, либо решаются очень сложно.
+2
Dark_Unique, #
Я с вами полностью согласен, но даже решение задачи коммивояжера пришлось заняло бы почти в 2 раза больше текста, и было бы труднее для понимания.
0
Danov, #
Если цель статьи краткое изложение ГА тогда тут еще короче.
+2
Dark_Unique, #
Я не претендую на идеальную реализацию, но по вашей ссылке ГА подаётся как вполне детерминированный алгоритм, думаю для начального знакомства она была бы тяжелее.
+15
YoungSkipper, #
Да, ладно вам. Хороший материал в общем объясняющий метода. Как hello world. Мне например лет шесть назад не хватало такого.

Я «выводил» команду футболистов таким образом.

Футболист содержал в себе набор из порядка 30 генов — ген стремления бежать к чужим воротам c мячем или без, ген желания отдать пас, ген стремления находиться у своих ворот, ген отвечающий за стремление обежать противника, ген позиции, ген стремления находиться у своей позиции и т.п.

У команды было соответсвено 11 хромосом. Защитники, нападающие, полузащитники и вратарь.

Был симулятор матчей.

Отыгрывались матчи у примерно 100 команд. После этого брались лучше 50 и из них создавались еще 50 команд — путем кроссовера и мутации между нужными типами хромосом.

И так далее.

Итераций не помню сколько было — в среднем отводил компу подумать час времени.

В результате получил набор значений который потом использовались для ручного формирования набора комманд против которого играл игрок.

Целью такого изврата было экономия времени геймдизайнера на создание начального набора параметров для комманд.

+6
Danov, #
Очень хорошая для ГА задача. Напишите об этом статью.
+2
sse, #
В Quake 3 таким образом создавали (вернее, досоздавали) ботов. В этом документе в том числе указаны постановка задачи и условия отбора решения, предлагаемого «ботовому» ГА.
+1
FloppyFormator, #
И пусть наши футболисты потом по ней учатся :)
+1
DjoNIK, #
Только у меня проблемы с просмотром результата работы?
0
Ferroman, #
нашейпараболы
единственныйминимум
0
Ferroman, #
Там такого много.
Короче говоря, перечитали бы текст ещё раз.
0
Alexlexandr, #
Давно настроен решить одну техническую задачу.
Спроектировать промышленный сортировщик продукции основанный на системе технического зрения.
Если у кого-то есть настроение посотрудничать по этой тематике и уверенность в своих силах, можно пообщаться в личке.
0
Iskin, #
Спасибо за статью, но пример не такой показательный. От себя добавлю, что круто когда мы оптимизируем числа, а что если у нас не числа, а граф? Как тут смешивать и мутировать? ;)
0
Dark_Unique, #
Пример выбирал максимально простой, чтобы не погружать в технические тонкости.
По поводу мутирования — например в задаче коммивояжера оператором мутации может выступать перетасовка пути. Главное, чтобы эти операторы создавали реальные решения в рамках данной задачи, а быть они по сути могут любыми (с поправкой на оптимизацию).
0
Sharpy, #
Будет интересна статья по распознаванию рукописного чегобытонибыло с помощью метода обратного распространения ошибки?
0
Indalo, #
В смысле с помощью НС?
0
Sharpy, #
да
0
Indalo, #
Будет, если это нечто большее, чем пример применения готовой библиотеки :)
0
mechmind, #
Метод обратного распространения ошибки — это только способ обучения. Типов нейросетей для решения задачи можно подобрать несколько :)
0
Sharpy, #
трёхслойный перцептрон
0
ksn, #
Достаточно интересно по крайней мере мне :)
0
culvert, #
Некоторое применение ГА бывает в торговых роботов (автоматические системы торговли на биржах).
С помощью ГА пытаются предсказать движение на рынке, есть ли какие-нибудь идеи как это делается?
если есть, было бы интересно почитать.
+1
marazm, #
Собирают популяцию трейдеров первой эпохи, валят тех кто неправильно предсказал…
0
TheShade, #
Популяция в 5000 хромосом — это слишком круто. Вы получили 5000*25 = 75000 тысяч вычислений на такой простой функции? Если она будет сложнее, вы потеряете кучу времени просто на оценку решения.

Я взял свой фреймворк, записал там задачу, подобную вашей и получил для исходной параболы с параметрами A=1.0, B=2.0, C=3.0 решение всего за 2000 вычислений при размере популяции в 20 хромосом:

$ java  -Devaluator.name=Parabola -jar ananke.jar
step = 103, result = -45.88803332499999, scorings = 1874 (cache hits: 0), acceptabilities = 1854 (cache hits: 0)
Best solution: [A=1.0, B=2.0, C=1.82]
0
Danov, #
У Вас, скорее всего, операторы кроссовера и мутации правильные :)
В данном примере они с потолка взяты. Впрочем, тоже показательно, т.к. алгоритм все же сходится.
0
TheShade, #
Примечательно то, что задача определения «правильных» (т.е. сводящих популяцию к минимуму) операторов и их параметров сама по себе является задачей оптимизации. И это — настоящая проблема :) Мета-ГА пытаются решить это оборачиванием ещё одним ГА :)
0
Danov, #
Это и есть основная задача при применении ГА: разработка операторов кроссовера и мутации. Прежде всего, кроссовера. Эффективно использовать типовые операторы получается крайне редко. Если типовой подходит по контексту задачи, тогда, чаще всего, можно подыскать более эффективные итерационные алгоритмы. Или скомбинировать метод случайного поиска с одним из методов направленного поиска.
0
TheShade, #
Да-да, здравствуйте меметические алгоритмы :)
0
objMihail, #
А может просто добавить параметры ГА в хромосому наряду с другими данными? Мне кажется в природе так и было.
+1
VenomBlood, #
Насколько я понимаю, у вас фитнесс функция даёт разницу с идеальной параболой, а в топике рассматривается рисунок от руки. Безусловно, можно было сделать более оптимальный пример, но он был бы не таким прозрачным.
0
ksn, #
А что Вы можете сказать о производительности генетических алгоритмов? У меня на Core2Duo P7350 @ 2.00GHz относительно долго идет расчет до 25ого поколения. Возможно это потому, что не реализована мультипоточность?
+2
Danov, #
Не автор, но отвечу :)
ГА – это сравнительно универсальный метод поиска с помощью грубой вычислительной силы. Он очень требователен к вычислительным ресурсам. Его эффективность можно повысить, но для этого требуются неплохой математик, который, в принципе, может найти решение и другими менее затратными методами, чаще всего специализированными.
Применение Мета-ГА, который оптимизирует основной ГА, практически не имеет смысла, т.к. время на поиск тонкой настройки на быстрое решение основной задачи может превышать время решения основной задачи ненастроенным ГА.
Самое печальное, что найденная тонкая настройка будет пригодной только для ограниченного набора исходных условий основной задачи.
+1
Danov, #
Получилось чрезмерно категорично ;-)
Мета-ГА (nGA) имеет право на существование для сложных задач.
0
ksn, #
Можете привести примеры таких задач?
0
Danov, #
Конкретную задачу не назову. А смысл идеи следующий. К каждой особи цепляется некоторая история применимых к ней (и ее предкам) операторов и/или некоторый код (эволюционирующий вместе с хромосомой), определяющий правило выбора применяемых в будущем операторов, исходя из истории, текущей скорости сходимости и прочих текущих характеристик работы ГА.
0
Danov, #
Предполагается, что есть набор операторов кроссовера и мутации из которого можно выбирать предположительно оптимальные для текущей ситуации операторы.
0
Danov, #
Еще можно менять не сами операторы, а их параметры, например, вероятность применения мутации. Самый простой способ выйти из локального экстремума — существенно повысить вероятность применения оператора мутации.
+1
TheShade, #
Но есть класс задач, для которых найти аналитическое решение или даже построить правдоподобную специальную эвристику не представляется простой задачей. Тогда встаёт выбор между поиском грубой силой и случайным поиском с общими эвристиками (коим, например, может быть ГА), второй вариант в этом случае явно побеждает.

Есть ещё забавная No Free Lunch Theorem.
0
ksn, #
А что Вы можете сказать о производительности генетических алгоритмов? У меня на Core2Duo P7350 @ 2.00GHz относительно долго идет расчет до 25ого поколения. Возможно это потому, что не реализована мультипоточность?
0
ksn, #
Извиняюсь, из-за лагов интернета дав раза запостилось.
0
ivanrt, #
Интересно. С точки зрения алгоритма, я бы сделал мутации методом умножения на случайное число от 0.5 до 2 а то не совсем понятно как гены-коэффициенты могут вырасти больше 100.
0
VadimKotov, #
Уважаемый автор, если Вы интересуетесь оптимизацией, возможно Вам будет интересно узнать об алгоритме клональной селекции (clonal selection algorithm), относящемуся к классу эволюционных алгоритмов. Он немного проще и быстрее генетических алгоритмов. Хотя возможно, Вы уже давно с ними знакомы.
А статья у Вас потрясающая =)
0
jcdenton_dx, #
Огромное спасибо за хороший пример на пальцах. Уже копипастю.
0
yarema, #
перезалейте файлик с исходниками пожалуйста)

Только зарегистрированные пользователи могут оставлять комментарии.
Войдите, пожалуйста.