Природа всегда поражала человека своим многообразием и красотой. Животные и растения удивляют своей способностью быстро приспосабливаться к окружающей среде. Многое из того, что мы видим, можно объяснить теорией эволюции.

Теория эволюции Чарльза Дарвина была представлена в работе «Происхождение Видов» в 1859 году. Основные положения теории — это наследственность, изменчивость и естественный отбор. Однако, долгое время было неизвестно, каким образом реализуется наследственность, пока не была открыта ДНК.
В 70-х годах прошлого века ученые, занимавшиеся компьютерными исследованиями, обратились к теории эволюции. Казалось привлекательным создать программы или механизмы, осуществляющие решение задач способами, почерпнутыми из природы.

Эволюционные исследования велись во многих направлениях, одним из которых являются генетические алгоритмы. «Отцом» генетических алгоритмов считается Дж.Холланд (Holland). Его книга «Адаптация в естественных и искусственных системах» («Adaptation in Natural and Artifical Systems», 1975) стала классикой.

Теория

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

Обычно имеется некоторая функция от нескольких переменных (целевая функция). Задача состоит в том, чтобы найти ее максимум или минимум.
Параметры функции — это генетический материал — гены. Совокупность генов составляет хромосому. Каждая особь обладает своей хромосомой, то есть, своим набором параметров-генов. Подставив параметры в целевую функцию, можно получить какое-то значение.

Генетические алгоритмы работают с популяцией, состоящей из некоторого количества особей, заданных при помощи данного способа. Затем популяция оценивается, то есть оценивается каждая особь при помощи оценивающей функции, значение которой — приспособленность. Чем выше приспособленность, тем лучше особь. Вот здесь и начинается самое интересное. Особи «скрещиваются» между собой с помощью генетических операторов, часть потомков заменяют представителей более старого поколения в соответствии со стратегией отбора. Выбор особей для скрещивания проводится согласно селективной стратегии. Заново сформированная популяция снова оценивается, затем выбираются наиболее достойные для скрещивания особи, которые скрещиваются, получаются потомки, занимают место старых особей и т.д.

Весь процесс продолжается до тех пор пока не найдется особь, гены которой представляют собой оптимальный набор параметров, при которых значение целевой функции близко к максимуму или минимуму, либо равно ему. Останов работы ГА может произойти также в случае вырождения популяции, то есть практического отсутствия разнообразия в генах разных особей популяции. Вырождение популяции называют преждевременной сходимостью.

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

Генетические операторы.

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

Оператор скрещивания (кроссинговер или кроссовер)

С помощью этого оператора происходит комбинирование генетической информации родителей и передача ее потомкам.

У обоих родителей есть свои хромосомы. Случайным образом выбирается точка кроссовера, в которой хромосомы делятся на 2 части и обмениваются ими, как показано на рисунке:

кроссовер

Получается 2 потомка.
Такой тип кроссовера называется одноточечным. Существует еще 2-точечный (который мы рассмотрим в примере) и N-точечный кроссовер.

Оператор мутации

Мутация в генетических алгоритмах имеет полную аналогию в природе, когда происходит замена одного гена другим в ДНК под воздействием, например, радиоактивности. Считается, что мутация — это причина скачкообразности эволюции, и благодаря ей появляются новые виды.

В генетических алгоритмах мутация способствует защите от преждевременной сходимости. Реализуется она путем выбора случайного гена или группы генов и их изменения по определенным правилам (например, инверсия).

Стратегии отбора

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

Стратегии формирования нового поколения

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

Принцип элитизма

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

Размер популяции

Следует выбирать размер популяции не слишком маленьким (до 10 особей) и не слишком большим (свыше 1000 особей). Малый размер популяции способствует вырождению, а большой — неоправданно увеличивает количество вычислений в алгоритме. Размер обычно выбирают 20-300 особей, все зависит от решаемой алгоритмом задачи.

Применения генетических алгоритмов

Если пространство поиска не очень сложно и уже имеются другие эффективные методы, то лучше их и использовать, так как генетические алгоритмы обычно требуют бо’льших (по сравнению со стандартными методами) вычислительных затрат.

Применять генетические алгоритмы лучше для задач, для которых эффективных алгоритмов решения не существует (например, задачи перебора, которые не решаются за приемлемое время, скажем «задача о коммивояжере»).

Области применения генетических алгоритмов:

  • Экстремальные задачи (нахождение точек минимума и минимума);
  • Задачи о кратчайшем пути;
  • Составление расписаний;
  • Аппроксимация функций;
  • Настройка нейронных сетей;
  • Моделирование искусственной жизни;
  • и др.

Практика

Перейдем от теории к практике.
Представьте себе пробирку, в которой плавают живые организмы, называемые флибами (от англ. finite living blobs — конечные живые капельки). Каждый флиб (см.рисунок)

флиб

снабжен аппаратом принятия решений и одной единственной хромосомой. Флиб — по сути — биологический эквивалент конечного автомата. Хромосома определяет поведение этого автомата. Флибы живут в цифровой среде, выжить в которой и есть их задачей.

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

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

диаграмма состояний

или таблицей состояний:

0 1
A 1,B 1,C
B 0,C 0,B
C 1,A 0,A

В таблице и на диаграмме изображен один и тот же конечный автомат с тремя состояниями.

В таблице состояний для каждого состояния и входного символа есть два элемента. Первый — выходной символ, который должен породить автомат, второй — состояние, в которое он должен перейти. Например, если автомат находится в состоянии А и воспринимает символ «1», то в следующий момент времени он перейдет в состояние С и выдаст символ «1».

На диаграмме состояний в кружках записываются все состояния автомата, а переходы между состояниями изображаются стрелками. Причем, символ у начала стрелки обозначает входной сигнал, а символ у конца стрелки — выходной сигнал. Конечный автомат начинает свою работу с исходного состояния (обычно А). С каждым тактом воображаемых часов автомат получает входной сигнал, генерирует выходной и переходит в следующее состояние.
Автоматы, на которых построены флибы, получают и выдают двоичные сигналы — 0 и 1.

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

Как мы говорили, для флиба способность к выживанию определяется тем, как он предсказывает изменения в окружающей среде, которая для него представляется символами 0 и 1. Конечно, нельзя требовать от флиба предсказания непериодических изменений в среде, однако в средах с некоторой периодичностью флибы могут предсказывать среду со 100% вероятностью.

Существует множество флибов с тремя состояниями, но только некоторые из них могут предсказать среду безошибочно. В этом и состоит задача нашего генетического алгоритма — найти такие конечные автоматы, которые безошибочно предсказывают определенную периодическую последовательность нулей и единиц. Честно говоря, как сделать это с помощью какого-нибудь другого алгоритма (кроме, конечно, прямого перебора), мы не знаем.

Флибы периодически размножаются, механизм их размножения до сих пор неизвестен. Однако исследования флибов показывают, что хромосома флиба состоит из строк таблицы переходов, склеенных в кольцо (для нашего примера — 1B1C0C0B1A0A). Хромосома потомка двух флибов — родителей получается в результате двухточечного кроссовера их хромосом (см.Теорию и рисунок:).
двухточечный кроссовер

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

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

скриншот

Создание программы

Создадим такие массивы:

  • chrom(i,j) — двумерный массив, содержащий значение j-го гена в хромосоме i-го флиба
  • state(i) — текущее состояние i-го флиба
  • count(i) — количество правильно предсказанных символов среды у i-го флиба
  • env(i) — сами символы среды

Закодируем состояния флиба цифрами: A-0, B-1, C-2 и так далее.

Сама программа будет состоять из четырех частей, повторяющихся в цикле:

  1. Подсчет количества правильно предсказанных символов среды.
    Генерируется некоторое количество символов среды (у меня — 1000), при этом значение в массиве count для каждого флиба увеличивается на 1, если тот правильно предсказал следующий символ.
    Здесь можно использовать такой способ: изменяем переменную j — индекс текущего символа среды от 0 до 999. Тогда сам символ вычисляется как env(j mod Period), где Period — период среды (например для повторяющихся символов 11010 период равен 5), а следующий символ — как env((j+1) mod Period).
    Определить следующее состояние флиба просто. Сначала вычислим
    1
    l:=4*state(i)+2*symb

    где symb — это текущий символ среды. Тогда следующее состояние флиба определится как chrom(l+1), а выдаваемый им символ — chrom(l).
  2. Вычисление наилучшего и наихудшего предсказателя среды
    Здесь используется стандартный прием для нахождения минимального и максимального значений в массиве count. Думаю, объяснять его не надо.
  3. Кроссовер
    Флиб — наилучший предсказатель спаривается со случайно выбранным флибом из популяции. Один из их потомков заменяет наихудшего предсказателя.
    Самое сложное здесь — это правильно перекрестить хромосомы. Так как длина хромосомы равна m:=4*(Количество состояний флиба), выберем два числа c1 и c2 случайным образом от 0 до m-1. Если с1 больше с2, следует поменять их местами. Затем нужно организовать три цикла от 0 до с1, от с1 до с2 и от с2 до m-1, в которых в хромосому потомка будут копироваться соответствующие гены предков.
  4. Мутация
    Здесь все просто. Выбираем случайный флиб и случайный ген в его хромосоме. Если номер гена четный — значит в нем хранится выдаваемый флибом символ (0,1), тогда значение этого гена определяется как ((ген+1) mod 2). Если же номер гена нечетный, значит в нем хранится номер состояния флиба, и тогда вычисляем так: ((ген+1) mod (К-во состояний флиба)). То есть ген циклически изменяется.

Осталось рассмотреть начало и конец программы.

В начале популяция флибов населяется случайным образом (то есть создаются случайные хромосомы).
Основной цикл программы повторяется до тех пор, пока один из флибов не достигнет показателя предсказаний — 100%, или пока программу не остановит пользователь.

Заключение

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

Счастливого программирования!
Как всегда, ленивые могут скачать уже готовую программу.

Флибы
Флибы
flibs0.1.exe
Version: 0.1
214.5 KiB
406 Downloads
Детали

О.Воронин, А.К.Дьюдни