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

Использование принципов дарвинизма для автоматизированного решения проблем началось в 1950-х. К 1960-му году три различные интерпретации этой идеи разрабатывались в трех разных местах. Эволюционное программирование было введено Лоуренсом Дж. Фогелем в США, в то время как Джон Генри Холланд назвал свой метод генетическим алгоритмом. В Германии Инго Rechenberg и Ханс-Пол Schwefel представили подход эволюционной стратегии. Эти области разрабатывались отдельно в течение примерно 15 лет. С начала девяностых годов они были унифицированы как «диалекты» одной технологии, называемой эволюционные вычисления. Кроме того, в начале девяностых годов появился четвертый поток — генетическое программирование. С 1990-х эволюционные вычисления во многом стали связаны с идеей роевого интеллекта и вдохновленные природой алгоритмы становятся все более значительной частью этого направления.

Таким образом, термины «эволюционное программирование», «эволюционные стратегии», «генетические алгоритмы» и «генетическое программирование» рассматриваются как частные случаи общего термина «эволюционные вычисления» или «эволюционное моделирование».

Моделирование эволюции с использованием идей эволюционных алгоритмов и искусственной жизни началось с работы Нильса Aall Barricelli в 1960-х, и было продлено Алексом Фрейзером, который опубликовал ряд работ по моделированию искусственного отбора.[1] Эволюционные алгоритмы стали общепризнанным методом оптимизации в результате работ Инго Rechenberg в 1960-х и начале 1970-х, который использовал их для решения сложных инженерных задач.[2] Генетические алгоритмы стали особенно популярны благодаря работам Джона Холланда.[3] Вместе с ростом академического интереса, резкое увеличение мощности компьютеров позволило практические применения, в том числе автоматическую эволюцию компьютерных программ.[4] Эволюционные алгоритмы в настоящее время используются для решения многомерных задач более эффективно, чем программное обеспечение, разрабатываемое человеком.[5]

Схема работы генетического алгоритма

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

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

Мутации и скрещивания

Функция, представленная в древовидной форме

Мутация — это случайное изменение «генотипа». В ГА и ЭС оператор мутации может быть реализован простым добавлением нормально распределенной случайной величины к каждой компоненте вектора. В ГП и ЭП эта операция сильно зависит от способа кодирования выращиваемых программ. Например, при древовидном кодировании (см. рисунок) она может быть осуществлена случайным изменением информации в узле или добавлением, удалением узла или целого поддерева.

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

В начале 70-х годов лауреат Нобелевской премии М.Эйген совершил впечатляющую попытку построения моделей возникновения в ранней биосфере Земли молекулярно генетических систем обработки информации[6]. Наиболее известная из них — модель «квазивидов», описывающая простую эволюцию полинуклеотидных (информационных) последовательностей. Вслед за Эйгеном в 1980 г. новосибирскими учеными В.Ратнером и В.Шаминым была предложена модель «сайзеров»[7].

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

Модель сайзера в простейшем случае рассматривает систему из трех типов макромолекул: полинуклеотидной матрицы и ферментов трансляции и репликации, кодированных этой матрицей. Полинуклеотидная матрица — это как бы запоминающее устройство, в котором хранится информация о функциональных единицах сайзера — ферментах. Фермент трансляции обеспечивает «изготовление» произвольного фермента по записанной в матрице информации. Фермент репликации обеспечивает копирование полинуклеотидной матрицы. Сайзеры достаточны для самовоспроизведения. Включая в схему сайзера дополнительные ферменты, кодируемые полинуклеотидной матрицей, можно обеспечить сайзер любыми свойствами, например свойством регулирования синтеза определенных ферментов и адаптации к изменениям внешней среды.[8]

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

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

Роевой интеллект (англ. Swarm intelligence) описывает коллективное поведение децентрализованной самоорганизующейся системы. Рассматривается в теории искусственного интеллекта как метод оптимизации. Термин был введен Херардо Бени и Ван Цзином в 1989 году, в контексте системы клеточных роботов[9]. Системы роевого интеллекта, как правило, состоят из множества агентов (Многоагентная система) локально взаимодействующих между собой и с окружающей средой. Сами агенты обычно довольно просты, но все вместе, локально взаимодействуя, создают так называемый роевой интеллект. Примером в природе может служить колония муравьёв, рой пчёл, стая птиц, рыб…

Коллективный интеллект — термин, который появился в середине 1980-х годов в социологии при изучении процесса коллективного принятия решений. Исследователи из NJIT определили коллективный интеллект как способность группы находить решения задач более эффективные, чем лучшее индивидуальное решение в этой группе.

Социологическое направление — поскольку человеческое общество представляет собой реальный, к тому же хорошо поддающийся наблюдению и задокументировнный (в отличие от человеческого мозга), инструмент обработки информации, социологические метафоры и реминисценции присутствуют в работах по кибернетике и смежным направлениям с самого их возникновения. Если роевой интеллект ориентирован на получение сложного поведения в системе из простых элементов, этот подход, наоборот, исследует построение простых и специальных объектов на базе сложных и универсальных: «государство глупее, чем большинство его членов»[10]. Для этого направления характерно стремление дать социологическим понятиям определения из области информатики. Так в[11] элита определяется как носитель определенной частной модели реального мира, а базис (то есть народ) играет роль арбитра между элитами. Эволюционный процесс заключается в порождении и гибели элит. Базис не в состоянии разобраться в сути идей и моделей, представляемых элитами, и не ставит перед собой такой задачи. Однако, именно в силу своей невовлеченности сохраняет способность к ясной эмоциональной оценке, позволяющей ему легко отличать харизматические элиты от загнивающих, пытающихся сохранить свои привилегии, понимая, что их идея или модель не подтвердилась.

• International Conference on Evolutionary Computation Theory and Applications (ECTA, 20-22.09.2013 Vilamoura, Portugal)[12]
• IEEE Congress on Evolutionary Computation (CEC)
• Genetic and Evolutionary Computation Conference (GECCO)[13]
• International Conference on Parallel Problem Solving From Nature (PPSN)[14]

• Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М.: Физматлит, 2003. — 432 с. — ISBN 5-9221-0337-7.
• Курейчик В. М., Лебедев Б. К., Лебедев О. К. Поисковая адаптация: теория и практика. — М.: Физматлит, 2006. — 272 с. — ISBN 5-9221-0749-6.
• Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы: Учебное пособие. — 2-е изд.. — М.: Физматлит, 2006. — 320 с. — ISBN 5-9221-0510-8.
• Гладков Л. А., Курейчик В. В, Курейчик В. М. и др. Биоинспирированные методы в оптимизации: монография. — М.: Физматлит, 2009. — 384 с. — ISBN 978-5-9221-1101-0.
• Рутковский Л. Методы и технологии искусственного интеллекта. — М.: Горячая линия-Телеком, 2010. — 520 с. — ISBN 5-9912-0105-6.
• Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. — 2-е изд.. — М.: Горячая линия-Телеком, 2008. — 452 с. — ISBN 5-93517-103-1.