Семинары по АМ – Занятие 3 и Генетические Алгоритмы


Автор:

В прошлую субботу состоялось третье, срединное, занятие из цикла открытых семинаров по агентному моделированию. Поскольку некоторые из участников не были на 2м занятии, мы решили сделать домашнее задание совместно (доработать модель развития социальных сетей). Также мы поговорили о генетических алгоритмах и их месте в будущем программирования. Именно об этом и пойдет речь в этом посте.

Генетические алгоритмы

Что же такое генетические алгоритмы? Напомню, что алгоритм – это последовательность шагов для преобразования входного параметра в выходной. К примеру, если нам нужно написать программу для робота, который собирает мусор с территории вокруг дома, то мы должны описать как робот будет принимать решение о том или ином действии (выходной параметр),  к примеру поднять мусор или двигаться дальше, на основе информации о состоянии внешней среды (входной параметр), к примеру есть ли на данном участке территории мусор. То есть мы должны сесть и придумать для робота оптимальную стратегию уборки территории!

Но люди ленивы по своей природе и решили, что можно заставить компьютер найти оптимальную стратегию для робота. Вы просто пишете программу, которая ищет оптимальный алгоритм. То есть вы поднимаетесь на уровень абстракции выше:  программируете не оптимальный алгоритм, а алгоритм нахождения оптимального алгоритма! Вот оно как!

Как же написать такой алгоритм? Для этого вы используете принципы биологической эволюции, а именно:

  • отбор – выживает та популяция особей (в нашем случае, алгоритмов), которая лучше других приспособлена к окружающей среде;
  • размножение – выжившие популяции размножаются и передают свои отличительные особенности потомкам;
  • мутация – в редких случаях происходит мутация в потомстве и потомство приобретает характеристики, отличные от характеристик родителей.

Описание генетического алгоритма уборки территории

Допустим, что у нас есть робот, который должен убирать территорию,  представленную в виде квадрата из 100 клеток (10×10). По всей территории случайным образом разбросан мусор. Давайте опишем генетический алгоритм поиска оптимальной стратегии уборки территории для нашего робота.

picture-2

Что в нашем случае есть стратегия (алгоритм) уборки? Стратегия – это набор правил, согласно которым робот должен принимать решения в ответ на состояние окружающей среды.

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

Какие действия может принять робот в ответ на состояние окружающей среды? У него есть 7 возможных действий: сделать шаг вверх, вниз, налево, направо, пойти “куда глаза глядят” (random), а также поднять мусор или не поднимать ничего. Таким образом получается, что стратегия – это набор правил о том, какое из 7 действий совершить в зависимости от того или иного состояния внешней среды. Схематически представим одно из правил в следующем виде:

Сверху Снизу Слева Справа Текущая клетка Действие
Стена Пусто Стена Пусто Пусто Шаг вправо

Сколько может быть таких правил в стратегии? Очевидно, что нужно перебрать все возможные комбинации окружающей среды: 243 правила (3 в пятой степени). И каждой возможной комбинации нужно однозначно сопоставить одно из 7 возможных действий.

Вот последовательность шагов для нахождения оптимального алгоритма:

  1. Создать изначальную популяцию возможных алгоритмов (стратегий) уборки территории – возьмем 200 алгоритмов. Самый простой способ: выбрать случайным образом (random) действия в ответ на каждое состояние среды.
  2. Прогнать каждый алгоритм для 100 возможных конфигураций расположения мусора на территории.
  3. Подсчитать приспособленность (fitness) каждого алгоритма. В нашем случае алгоритм является тем более приспособленным, чем быстрее робот сможет убрать территорию, используя данный алгоритм. Правила такие: если робот поднял мусор то +5 очков, если ударился в стенку, то -1 очко. Таким образом, присопособленность стратегии равна среднему количеству очков, заработанных роботом при использовании данного алгоритма за 100 сессий уборки.
  4. Выбрать определенное количество наиболее присопособленных алгоритмов, которые станут родителями нового поколения алгоритмов.
  5. Скрестить родителей. Каждая пара алгоритмов создает потомка, путем скрещивания. В нашем случае, один из 2 потомков будет наследовать часть правил от отца, а вторую часть – от матери.  Второй потомок – наоборот: вторую часть от отца, и первую – от матери.
  6. Мутация – с малой вероятностью нужно мутировать некоторые правила из стратегии потомка. Например, заменить действие “Шаг вправо” на “Шаг влево” для одного из правил.
  7. 1000 раз повторить процесс с шага 2.

Весь фокус в том, что в процессе такой эволюции за 1000 поколений получается алгоритм, который почти оптимален! И от вас не требуется почти никакой работы! Вот вся сила и простота генетических алгоритмов. Я считаю, что будущее программирования именно за ними, программист еще выше поднимается по иерархии абстракций и начинает программировать алгоритмы нахождения оптимальных алгоритмов.  Следует заметить, что генетические алгоритмы, несмотря на их относительную новизну, уже активно используются для решения реальных задач: от General Electric (автоматизация проектирования комплектующих к самолетам) до John Deere (планирование работы сборочных конвейеров).

Оптимальная стратегия уборки

Оптимальная стратегия уборки во многом напоминает оптимальную игру в змейку на телефонах Nokia: в случае отсутствия мусора в ближайших клетках робот двигается кругообразно (до упора вправо, потом до упора наверх, и против часовой стрелки) пока не найдет мусор.

picture-3

Но замечено еще необычное поведение: в случае если робот находит 3 последовательно лежащие кучки мусора, то он сначала находит самую левую из кучек мусора, и потом двигаясь направо собирает все три. Мы бы навряд ли сами догадались до такого поведения: с высокой вероятностью мы бы запрограммировали поведение, что если в текущей клетке есть мусор, то следует его поднять. Более того, даже в начале работы генетического алгоритма “выживали” бы стратегии, которые именно так и поступали. Но что нам помогло? Именно! Мутация! Мутация помогла сгенерировать правило, которое ЛОКАЛЬНО неоптимально, но ГЛОБАЛЬНО ведет к оптимальному результату. Вот вам и теория ограничений :) ))

picture-4

Вот, собственно и все,  что я хотел рассказать о генетических алгоритмах. На семинаре мы еще поговорили о том, для решения каких задач можно применить генетические алгоритмы и придумали пару идей: от task management-а до управления светофорами. Есть еще идеи?

Для более подробного изучения генетических алгоритмов рекомендую книгу Джона Холланда “Адаптация в естественных и искусственных системах”, а сам я почерпнул этот материал из книги Melanie Mitchell “Complexity: a guided tour”.

Кстати, кто-нибудь нашел ошибку в расчетах количества возможных ситуаций (243)? :) Пишите в комментариях (кроме тех, кто был на семинаре).

Схожие посты:

Семинары по агентному моделированию – Занятие 1

Семинары по агентному моделированию – Занятие 2


10 отзывов

  • By simulyant, June 29, 2009 @ 8:45 am

    Похожая задача решалась на ICFPC-2008 (International Conference on Functional Programming Contest) http://habrahabr.ru/blogs/icfpc/29104/. Там ставилась задача управления марсоходом для оптимальной доставки его в требуемую точку и избегания препятствий и марсиан.

    Ответить

    Bayram Annakov Ответ:

    Здорово! Спасибо за ссылку!

    Ответить

  • By Иван Парфенов, June 30, 2009 @ 8:46 am

    Я (профан в программировании) вспомнил о том, что существуют алгоритмы обучения, применяемые в нейронных сетях. Можно как-то сравнить эти 2 подхода и определить, какой метод лучше, дешевле, проще?

    Ответить

    Bayram Annakov Ответ:

    Быстрое сканирование статьи о нейронных сетях на википедиа создало впечатление, что обучающиеся нейронные сети используется для выявления скрытых зависимостей… но может мое сканирование слишком быстрое, надо бы углубиться в этот вопрос…

    Ответить

  • By daltonik, October 20, 2009 @ 4:02 pm

    мне кажется 162 (=3*3*3*3*2)

    Ответить

  • By Bayram Annakov, October 20, 2009 @ 4:09 pm

    daltonik, прежде чем я отвечу о правильности, поясните как вы эту цифру получили? Почему 3*3*3*3*2?

    Ответить

  • By daltonik, October 20, 2009 @ 4:17 pm

    Текущая клетка может иметь только два состояния либо в ней пусто либо фиксируется наличие мусора,а остальные клетки(правая,левая,вверхняя,нижняя) по три состояния(добавляется стена).значит 2*3*3*3*3

    Ответить

  • By Bayram Annakov, October 20, 2009 @ 10:10 pm

    daltonik, вы правы! но забыли еще какие-то “невозможные ситуации”…

    Ответить

  • By вжалил, January 7, 2011 @ 10:06 am

    здравствуй
    МЕНЕ НУЖЕН ЭЛЕКТРОНАЯ КНИГА Генетические алгоритмы

    Ответить

Ссылки на эту статью

  1. Empatika Open – Встреча 3 | Empatika — April 27, 2010 @ 12:06 am

Оставить отзыв

WordPress Themes