Денис Романюк. 

Введение в генетические алгоритмы. Простые примеры на Java.



Генетические алгоритмы (ГА) - это упрощенное моделирование процесса эволюции для решения програмистских задач.

Классический ГА реализуется следующим образом. Предположим, мы ищем решение некоторой задачи, представимое в двоичном виде (в виде последовательности нулей и единиц). Создается структура - "хромосома", состоящая из "генов".

"Хромосома" - это решение задачи. Например, 00010101010101010100000101011111100111
"Ген" - это атомарный кусочек хромосомы. В нашем случае - ноль или единица в определенной позиции.

Далее программируются операторы кроссовера и мутации.

Кроссовер (скрещивание) - это когда две хромосомы смешиваются и порождают третью хромосому, которая содержит в себе черты обеих родительских хромосом. Например, пусть мы имеем хромосомы 111111 и 000000. Выбираем случайную точку в хромосомах - допустим, между вторым и третьим геном. Тогда после кроссовера мы получим хромосому-потомка 110000 или 001111.

Мутация - это когда после кроссовера потомок в случайном порядке изменяется. Задается некоторая константа P - вероятность мутации гена . Допустим, после кроссовера мы получили хромосому 1100000. Применяя оператор мутации к каждому гену, мы с вероятностью Р меняем его на противоположный - ноль на единицу и единицу на ноль. Если, например, мы "попали" в заданную вероятность для 4-го гена, то после оператора мутации мы получим хромосому 110100.

Далее программируется фитнесс-функция. Она определяет "успешность" данной особи (хромосомы), т.е., близость ее к искомому ответу. Для сложных задач задание фитнесс-функции - наиболее непростая часть во всем генетическом алгоритме.

Кроме того, программируются методы селекции. Это отбор особей для скрещивания. Этот отбор должен происходить таким образом, чтобы с большей вероятностью скрещивались более успешные особи, т.е., особи, имеющие большее значение фитнесс-функции. Однако менее удачные особи также должны иметь шанс пройти кроссовер, ибо в их генах может быть что-то полезное.

Наиболее изученными являются пропорциональный(или рулеточный) отбор и турнирный отбор. Турнирный отбор работает быстрее, поэтому рассмотрим его. В случае турнирного отбора, для выбора особи отбираются N случайных особей. Затем из них отбирается особь с наибольшим значением фитнесс-функции. О пропорциональном отборе читать здесь: http://algolist.manual.ru/ai/ga/dioph.php

Дальше можно приступить к склеиванию всех этих кусочков и созданию самого ГА.

Вот шаги работы ГА:

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

Алгоритм может заканчиваться при достижении самых разных условий, например:

Вот простенькие примеры реализации ГА на языке Java (все они легко могут быть переведены на другой язык):


1. Решение Диофантова Уравнения.

Нахождение целых решений уравнения a + 2*b + 3*c + 4*d = 30
Для селекции используется "пропорциональный отбор" (или "рулеточный" - Roulette Wheel Selection)
Файлы:
Chromosome.java - класс инкапсулирует хромосому и все, что с ней связано.
Diofant.java - все остальное. Запускать этот файл.

Исходный код программы, демонстрирует работу алгоритма - скачать (5.26 Кб)


2. Нахождение максимума функиции.

Нахождение максимума функиции x + Math.abs(Math.sin(32 * x)) на отрезке от нуля до Pi.
Для селекции используется "пропорциональный отбор".
Файлы:
Chromosome.java - класс инкапсулирует хромосому и все, что с ней связано.
Maximum.java - все остальное. Запускать этот файл.

Исходный код программы, демонстрирует работу алгоритма -  скачать (5.63 Кб)


3. Решение "задачи о рюкзаке" (knapsack problem).

Описание задачи по-английски можно найти здесь - http://en.wikipedia.org/wiki/Knapsack_problem
На русском - http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D1%80%D0%B0%D0%BD%D1%86%D0%B5
Для селекции используется "турнирный отбор" (Tournament Selection).
Представление хромосомы - в двоичном виде. "1" значит "берем предмет", "0" - "не берем"
Из-за своей упрощенности алгоритм находит "неплохое", но не всегда лучшее решение.
В интернете есть масса инфы, как его можно улучшить.
Файлы:
Chromosome.java - класс инкапсулирует хромосому и все, что с ней связано.
Knapsack.java - все остальное. Запускать этот файл.
Item.java - примитивный Java класс, представляющий собой предмет с весом и стоимостью.

Исходный код программы, демонстрирует работу алгоритма -  скачать(5.03 Кб)



На главную