Генетические алгоритмы или как биологи помогают математикам
Генетические алгоритмы уже используются для решения реальных бизнес-задач: от General Electric (автоматизация проектирования комплектующих к самолетам) до John Deere (планирование работы сборочных конвейеров)
В последнее время набирает популярность идея заимствования теорий и концепций из одной области науки в другую. Математика и программирование не отстают от других и успешно адаптируют принципы биологической эволюции и достижения нейробиологии для решения задач оптимизации.
Поговорим об одном из таких примеров – генетических алгоритмах.
ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ
Напомню, что алгоритм – это последовательность шагов для преобразования входного параметра в выходной. Если нам нужно написать программу для робота, который собирает мусор с территории вокруг дома, то мы должны описать, как робот будет принимать решение о том или ином действии (выходной параметр): к примеру, поднять мусор или двигаться дальше; на основе информации о состоянии внешней среды (входной параметр): к примеру, есть ли на данном участке территории мусор. То есть мы должны сесть и придумать для робота оптимальную стратегию уборки территории.
Но люди ленивы по своей природе и решили, что можно заставить компьютер найти оптимальную стратегию для робота. Вы просто пишете программу, которая ищет оптимальный алгоритм. То есть вы поднимаетесь на уровень абстракции выше: программируете не оптимальный алгоритм, а алгоритм нахождения оптимального алгоритма! Вот оно как!
Как же написать такой алгоритм? Для этого вы используете принципы биологической эволюции, а именно:
отбор – выживает та популяция особей (в нашем случае, алгоритмов), которая лучше других приспособлена к окружающей среде;
размножение – выжившие популяции размножаются и передают свои отличительные особенности потомкам;
мутация – в редких случаях происходит мутация в потомстве, и потомство приобретает характеристики, отличные от характеристик родителей.
ОПИСАНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА УБОРКИ ТЕРРИТОРИИ
Допустим, что у нас есть робот, который должен убирать территорию, представленную в виде квадрата из 100 клеток (10×10). По всей территории случайным образом разбросан мусор. Давайте опишем генетический алгоритм поиска оптимальной стратегии уборки территории для нашего робота.
Что в нашем случае есть стратегия (алгоритм) уборки? Стратегия – это набор правил, согласно которым робот должен принимать решения в ответ на состояние окружающей среды.
Как робот узнает о состоянии окружающей среды? Наш робот может видеть всего на одну клетку вверх, влево, вправо, и вниз, и, разумеется, на клетку, в которой он находится сейчас. Так робот сканирует окружающую среду. Какие могут быть состояния окружающей среды? В клетке может быть мусор, она может быть пуста или эта клетка может быть стеной (например, если робот находятся в клетке 1.1, то на севере и западе у него стена).
Какие действия может принять робот в ответ на состояние окружающей среды? У него есть 7 возможных действий: сделать шаг вверх, вниз, налево, направо, пойти «куда глаза глядят» (random), а также поднять мусор или не поднимать ничего. Таким образом, получается, что стратегия – это набор правил о том, какое из 7 действий совершить в зависимости от того или иного состояния внешней среды. Схематически представим одно из правил в следующем виде:
Сверху
Снизу
Слева
Справа
Текущая клетка
Действие
Стена
Пусто
Стена
Пусто
Пусто
Шаг вправо
Сколько может быть таких правил в стратегии? Очевидно, что нужно перебрать все возможные комбинации окружающей среды: 243 правила (3 в пятой степени). И каждой возможной комбинации нужно однозначно сопоставить одно из 7 возможных действий.
Вот последовательность шагов для нахождения оптимального алгоритма:
Создать изначальную популяцию возможных алгоритмов (стратегий) уборки территории – возьмем 200 алгоритмов. Самый простой способ: выбрать случайным образом (random) действия в ответ на каждое состояние среды.
Прогнать каждый алгоритм для 100 возможных конфигураций расположения мусора на территории.
Подсчитать приспособленность (fitness) каждого алгоритма. В нашем случае алгоритм является тем более приспособленным, чем быстрее робот сможет убрать территорию, используя данный алгоритм. Правила такие: если робот поднял мусор, то +5 очков, если ударился в стенку, то -1 очко. Таким образом, присопособленность стратегии равна среднему количеству очков, заработанных роботом при использовании данного алгоритма за 100 сессий уборки.
Выбрать определенное количество наиболее присопособленных алгоритмов, которые станут родителями нового поколения алгоритмов.
Скрестить родителей. Каждая пара алгоритмов создает потомка путем скрещивания. В нашем случае, один из 2 потомков будет наследовать часть правил от отца, а вторую часть – от матери. Второй потомок – наоборот: вторую часть от отца, и первую – от матери.
Мутация – с малой вероятностью нужно мутировать некоторые правила из стратегии потомка. Например, заменить действие «Шаг вправо» на «Шаг влево» для одного из правил.
1 000 раз повторить процесс с шага 2.
Весь фокус в том, что в процессе такой эволюции за 1 000 поколений получается алгоритм, который почти оптимален! И от вас не требуется почти никакой работы. Вот вся сила и простота генетических алгоритмов. Я считаю, что будущее программирования именно за ними, программист еще выше поднимается по иерархии абстракций и начинает программировать алгоритмы нахождения оптимальных алгоритмов. Следует заметить, что генетические алгоритмы, несмотря на их относительную новизну, уже активно используются для решения реальных бизнес-задач: от General Electric (автоматизация проектирования комплектующих к самолетам) до John Deere (планирование работы сборочных конвейеров).
ОПТИМАЛЬНАЯ СТРАТЕГИЯ УБОРКИ
Оптимальная стратегия уборки во многом напоминает оптимальную игру в змейку на телефонах Nokia: в случае отсутствия мусора в ближайших клетках робот двигается кругообразно (до упора вправо, потом до упора наверх, и против часовой стрелки), пока не найдет мусор.
Но замечено еще необычное поведение: в случае, если робот находит 3 последовательно лежащие кучки мусора, то он сначала находит самую левую из кучек мусора, и потом двигаясь направо собирает все три. Мы бы навряд ли сами догадались до такого поведения: с высокой вероятностью мы бы запрограммировали поведение, что если в текущей клетке есть мусор, то следует его поднять. Более того, даже в начале работы генетического алгоритма «выживали» бы стратегии, которые именно так и поступали. Но что нам помогло? Именно! Мутация! Мутация помогла сгенерировать правило, которое ЛОКАЛЬНО неоптимально, но ГЛОБАЛЬНО ведет к оптимальному результату.
Для более подробного изучения генетических алгоритмов рекомендую книгу Джона Холланда «Адаптация в естественных и искусственных системах».
Следите за обновлениями Slon.ru в вашей социальной сети:
ВКонтакте или
Facebook.
RSS
0
экспорт в блог
В последнее время набирает популярность идея заимствования теорий и концепций из одной области науки в другую. Математика и программирование не отстают от других и успешно адаптируют принципы биологической эволюции и достижения нейробиологии для решения задач оптимизации.
Следите за обновлениями Slon.ru в вашей социальной сети:
