Эволюционное моделирование

Идея имитации эволюционных процессов для решения задач возникла ещё до появления компьютеров. В частности, Алан Тьюринг предложил метод генетического поиска в 1948 году^[1]. Разработанные им машины типа B походили на примитивные нейронные сети, в которых связи между нейронами обучались по принципу, напоминающему генетический алгоритм. Машины типа P у Тьюринга напоминали подходы к обучению с подкреплением, где сигналы удовольствия и наказания управляли обучением определённого поведения. Однако его статья была опубликована только в 1968 году, а сам Тьюринг погиб в 1954 году, поэтому его работы практически не повлияли на развитие эволюционных методов^[2].

Эволюционное моделирование как самостоятельная область активно развивалось с 1950-х—1960-х годов^[1]. В этот период в разных странах независимо появились три подхода: эволюционные стратегии, эволюционное программирование и генетические алгоритмы. Позднее, в начале 1990-х, появилось генетическое программирование. Эти классы различались по методам отбора, способам мутаций и способу представления генетических данных. К 1990-м границы между направлениями размылись, и в 1991 году был введён общий термин «эволюционное моделирование», охватывающий все четыре парадигмы^[3].

В 1962 году Лоренс Дж. Фогель начал исследование эволюционного программирования в США как направления искусственного интеллекта. В этой системе конечные автоматы подвергались мутациям (добавление/удаление состояний, изменение переходов), а наиболее успешные варианты подвергались дальнейшей эволюции. Итоговый автомат применяли для решения задач предсказания, идентификации систем и автоматического управления. Метод впоследствии был расширен для работы с временными рядами и в эволюции игровых стратегий.

В 1964 году Ингo Рехенберг и Ганс-Пауль Швефель предложили в Германии концепцию эволюционных стратегий. Так как классические градиентные методы часто застревали в локальных минимумах, Рехенберг и Швефель предложили использовать случайные мутации всех параметров вектора решения для движения к глобальному экстремуму. Детские решения эволюционировали из родительских, а для следующих поколений выбирались наиболее успешные варианты. Первые эксперименты были проведены без использования компьютеров с помощью кубиков, а с 1965 года вычисления полностью автоматизировали^[4].

Джон Хенри Холланд разработал генетические алгоритмы в 1960-х, а в 1970-х они были дополнительно развиты в Университете Мичигана^[5]. В отличие от других подходов, Холланд изначально преследовал исследование механизмов адаптации. Популяции кодировались битовыми строками, подвергались искусственному отбору, мутациям и рекомбинациям. В то время как другие методы отслеживали одну оптимальную особь (дети конкурировали с родителями), генетические алгоритмы Холланда работали с большими популяциями, в которых конкуренция шла в каждом поколении по всей выборке.

В 1990-х появился новый подход — генетическое программирование, активно развиваемый Джоном Козой^[1]. Здесь объекты эволюции — программы на языке высокого уровня (часто на Lisp), представленные в виде древовидных S-выражений, что позволяло эффективно перестраивать их структуру (например, посредством обмена поддеревьями). Программы оценивались по качеству решения задачи, а эта оценка использовалась для искусственного отбора. Генетическое программирование успешно применялось в распознавании образов, индукции последовательностей и автоматическом планировании.

Среди других исследователей, повлиявших на развитие эволюционных методов, был Нильс Олл Барричелли, выполнивший первые вычислительные эксперименты с искусственной эволюцией в 1953 году и опубликовавший результаты в 1954 году^[6]. Ещё одним пионером был Алекс Фрейзер, который опубликовал ряд работ по симуляции искусственного отбора^[7]. По мере роста интереса и увеличения вычислительных мощностей стали появляться практические применения, например, автоматическая эволюция программ^[8]. Сегодня эволюционные алгоритмы решают задачи высокой размерности эффективнее традиционных методов и применяются для оптимизации сложных систем^[9].

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

• Агентное моделирование
  • Муравьиные алгоритмы оптимизации
  • Оптимизация роя частиц
  • Роевая интеллигенция
• Искусственные иммунные системы
• Искусственная жизнь
  • Цифровой организм
• Культурные алгоритмы
• Дифференциальная эволюция
• Эволюция в два этапа
• Алгоритмы оценки распределения
• Эволюционный алгоритм
  • Генетический алгоритм
  • Эволюционное программирование
  • Генетическое программирование
    • Генное выражение программирования
    • Грамматическая эволюция
  • Эволюционная стратегия
• Обучаемая эволюционная модель
• Система классификаторов с обучением
• Меметические алгоритмы
• Нейроэволюция
• Самоорганизация, например, самоорганизующиеся карты, конкурентное обучение

В последние годы появилось множество сомнительных алгоритмов, зачастую являющихся лишь повторениями существующих методов (например, оптимизации роя частиц) с изменёнными метафорами, но без новых идей. Подробный каталог таких алгоритмов опубликован в Evolutionary Computation Bestiary^[10]. Важно отметить, что новый метод не обязательно означает строго новую эволюционную идею; многие из «новых» алгоритмов имеют слабую экспериментальную проверку^[11].

Эволюционные алгоритмы — это подмножество эволюционного моделирования, реализующее механизмы, вдохновлённые биологической эволюцией: воспроизведение, мутации, рекомбинации и естественный отбор. Каждый кандидат-решение играет роль особи в популяции, а функция затрат определяет «окружение», в котором они выживают (см. также Функция приспособленности). Эволюция популяции происходит при повторном применении этих операторов.

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

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

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

Тем не менее, применение вычислительных и информационных концепций, особенно из теории вычислимости, важно и для понимания самой эволюции. Сильной стороной этого подхода является признание децентрализованной природы биологического развития: организмы формируются в результате локальных взаимодействий между клетками. Наиболее продуктивные параллели между развитием программ и организмов проводят между внутриклеточными процессами и работой современных компьютеров^[12]. Поэтому биологические системы ближе к вычислительным машинам, которые обрабатывают входную информацию и рассчитывают следующее состояние, чем, например, к традиционной динамической системе^[13].

Далее, согласно теории вычислимости, микропроцессы в организме могут быть принципиально неразрешимыми и неполными, что усиливает аналогичность между компьютерами и клетками с биологической точки зрения^[14].

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

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

Список ведущих специалистов области постоянно обновляется. Анализ сети научного сообщества по эволюционному моделированию был опубликован в 2007 году^[16].

• Кальянмой Деб
• Кеннет А. Де Йонг
• Питер Дж. Флеминг
• Дэвид Б. Фогель
• Стефани Форрест
• Дэвид Э. Голдберг
• Джон Хенри Холланд
• Тео Янсен
• Джон Коза
• Збигнев Михалевич
• Мелани Митчелл
• Питер Нордин
• Риккардо Поли
• Инго Рехенберг
• Ганс-Пауль Швефель

Существуют научные журналы, посвящённые эволюционному моделированию:

• Evolutionary Computation (основан в 1993, MIT Press)
• Artificial Life (основан в 1993, MIT Press)
• IEEE Transactions on Evolutionary Computation (основан в 1997, IEEE)
• Genetic Programming and Evolvable Machines (основан в 2000, Springer Nature)
• Swarm Intelligence (основан в 2007, Springer Nature)
• Evolutionary Intelligence (основан в 2008, Springer Nature)
• Journal of Artificial Evolution and Applications (2008—2010, Hindawi)
• Memetic Computing (основан в 2009, Springer Nature)
• International Journal of Applied Evolutionary Computation (основан в 2010, IGI Global)
• Swarm and Evolutionary Computation (основан в 2011, Elsevier)
• International Journal of Swarm Intelligence and Evolutionary Computation (основан в 2012, Walsh Medical Media)

Ключевые конференции по эволюционному моделированию:

• Генетическая и эволюционная конференция по вычислениям (GECCO, ACM)
• Конгресс IEEE по эволюционным вычислениям (CEC)
• EvoStar — объединяет четыре конференции: EuroGP, EvoApplications, EvoCOP и EvoMUSART
• Параллельное решение задач природы (PPSN)