Генетические алгоритмы (ГА) - это упрощенное моделирование процесса эволюции для
решения програмистских задач.
Классический ГА реализуется следующим образом. Предположим, мы ищем решение
некоторой задачи, представимое в двоичном виде (в виде последовательности нулей и единиц).
Создается структура - "хромосома", состоящая из "генов".
"Хромосома" - это решение задачи. Например, 00010101010101010100000101011111100111
"Ген" - это атомарный кусочек хромосомы. В нашем случае - ноль или единица в определенной позиции.
Далее программируются операторы кроссовера и мутации.
Кроссовер (скрещивание) - это когда две хромосомы смешиваются и порождают третью хромосому,
которая содержит в себе черты обеих родительских хромосом. Например, пусть мы имеем хромосомы 111111 и 000000.
Выбираем случайную точку в хромосомах - допустим, между вторым и третьим геном. Тогда после
кроссовера мы получим хромосому-потомка 110000 или 001111.
Мутация - это когда после кроссовера потомок в случайном порядке изменяется. Задается
некоторая константа P - вероятность мутации гена . Допустим, после кроссовера мы получили
хромосому 1100000. Применяя оператор мутации к каждому гену, мы с вероятностью Р меняем
его на противоположный - ноль на единицу и единицу на ноль. Если, например, мы "попали" в
заданную вероятность для 4-го гена, то после оператора мутации мы получим хромосому 110100.
Далее программируется фитнесс-функция. Она определяет "успешность" данной особи
(хромосомы), т.е., близость ее к искомому ответу. Для сложных задач задание фитнесс-функции
- наиболее непростая часть во всем генетическом алгоритме.
Кроме того, программируются методы селекции. Это отбор особей для скрещивания.
Этот отбор должен происходить таким образом, чтобы с большей вероятностью скрещивались
более успешные особи, т.е., особи, имеющие большее значение фитнесс-функции. Однако
менее удачные особи также должны иметь шанс пройти кроссовер, ибо в их генах может быть
что-то полезное.
Наиболее изученными являются пропорциональный(или рулеточный) отбор и турнирный отбор.
Турнирный отбор работает быстрее, поэтому рассмотрим его. В случае турнирного отбора,
для выбора особи отбираются N случайных особей. Затем из них отбирается особь с наибольшим
значением фитнесс-функции. О пропорциональном отборе читать здесь:
http://algolist.manual.ru/ai/ga/dioph.php
Дальше можно приступить к склеиванию всех этих кусочков и созданию самого ГА.
Вот шаги работы ГА:
- Случайным образом создается исходная популяция. Как правило, задается в виде
массива. Каждая особь(хромосома) в популяции - это случайный набор нулей и
единиц заданной длины.
- Каждая особь в популяции оценивается на успешность. Для этого применяется
фитнесс-функция. Если искомое решение найдено, то алгоритм заканчивается (разумеется,
при первой итерации вероятность этого очень мала).
- Отбираются особи для кроссовера. Повторюсь: этот отбор должен происходить
таким образом, чтобы с большей вероятностью скрещивались более успешные особи,
т.е., особи, имеющие большее значение фитнесс-функции.
- Отобранные особи скрещиваются, каждый потомок подвергается мутации с заданной
вероятностью.
- Из потомков формируется новая популяция, которая заменяет старую.
- Возвращаемся к шагу 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://www.mgopu.ru/PVU/2.1/Recurs/BacketTm/CnReturn/task_ruc.htm
Для селекции используется "турнирный отбор" (Tournament Selection).
Представление хромосомы - в двоичном виде. "1" значит "берем предмет", "0" - "не берем"
Из-за своей упрощенности алгоритм находит "неплохое", но не всегда лучшее решение.
В интернете есть масса инфы, как его можно улучшить.
Файлы:
Chromosome.java - класс инкапсулирует хромосому и все, что с ней связано.
Knapsack.java - все остальное. Запускать этот файл.
Item.java - обычный Java bean, представляющий собой предмет с весом и стоимостью.
Исходный код программы, демонстрирует работу алгоритма -
(5.03 Кб)
|