История эволюционного моделирования

Большая Энциклопедия Нефти и Газа

Cтраница 1

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

Эволюционное моделирование ( ЭМ) представляет собой одно из быстро развивающихся направлений математического моделирования, объединяющее компьютерные методы моделирования эволюционных процессов в естественных ( ЕС) и искусственных системах, такие как генетические алгоритмы, эволюционные стратегии, эволюционное программирование и другие эвристические методы.

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

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

Обратите внимание

Однако биологические системы обладают свойствами воспроизводства, адаптации, самоисправления, устойчивости, гибкости и многими другими, которые лишь фрагментарно присутствуют в искусственных системах.  [2]

Базовая структура ГА с учетом блока эволюционной адаптации.  [3]

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

Эволюционное моделирование знаковых систем ( знаков-фреймов) может рассматриваться как многообещающий вариант использования неодарвинизма в теоретической и прикладной семиотике. Здесь главная идея состоит в применении методов имитации эволюции к семиотически.  [5]

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

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

Другим важным фактором эволюционного моделирования является моделирование процессов селекции, размножения и наследования.

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

Суть стратегии эволюционного моделирования состоит в реализации целенаправленного процесса размножения-гибели, при котором размножению соответствует появление новых объектов, а гибели – удаление объектов в соответствии с определенными критериями естественного и искусственного отбора.  [7]
Важно

Перечислите основные направленияэволюционного моделирования и приведите основные факторы, определяющие неизбежность эволюции.  [8]

Считается, что историяэволюционного моделирования или эволюционных вычислений началась с работ Дж. Растригина и других исследователей.  [9]

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

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

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

Комплексы из трех равноправных объектов, находящихся в заданных отношениях, существовали давно: цель-план-стратегия; точность-локальность-простота; индукция-дедукция-абдукция; изменчивость-наследственность-отбор и др. В триаде пара элементов находится в отношении дополнительности, а третий элемент задает отношение ( меру) совместимости. Общей для разных интеллектуальных объектов характеристикой является структура или архитектура интеллектуальной ИС. Она характеризуется многоуровневостью, единством и непротиворечивостью.  [10]

Крупнейшее хранилище информации в областиэволюционного моделирования, это специализированная сеть, объединяющая FTP-серверы ведущих научно-исследовательских организаций и высших учебных заведений, известных своими разработками в области генетических алгоритмов и искусственных нейронных сетей.  [11]

Крупнейшим хранилищем информации в областиэволюционного моделирования является ENCORE ( The EvolutioNary Computation REpository network) – специализированная сеть, объединяющая FTP-серверы ведущих научно-исследовательских организаций и высших учебных заведений, известных своими достижениями в области ГА и ИНС. Одновременно ENCORE выступает дистрибьютором научных материалов тех учреждений, которые не имеют собственных FTP-серверов.  [12]

Взаимодейтсвие автоматов со средой.  [13]

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

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

Репликация реализует итеративный характер биологического упорядочения.  [14]

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

Совет

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

Как примеры гибридных систем с эволюцией приводятся моделирование развития популяции простейших автоматов и многомодельные системы.  [15]

Страницы:      1    2    3    4

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

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

Так было с нейронными сетями, с моделированием рассуждений, с компьютерной лингвистикой и т.д. Многие значимые теории науки были так или иначе рассмотрены через призму искусственного интеллекта. Теория Ч. Дарвина (1859 г.

) стала отправной точкой для еще одного направления исследований – эволюционного моделирования.

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

· наследственность (потомки сохраняют свойства родителей);

· изменчивость (потомки почти всегда не идентичны);

· естественный отбор (выживают наиболее приспособленные).

К методам эволюционного моделирования относятся

· метод группового учета аргументов

1) берется самый последний слой классификаторов;

2) генерируется из них по определенным правилам новый слой классификаторов, которые теперь сами становятся последним слоем;

3) отбирается из них F лучших, где F – ширина отбора (селекции);

4) если не выполняется условие прекращения селекции (наступление вырождения), переход на п. 1, иначе лучший классификатор объявляется искомым решением задачи идентификации;

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

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

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

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

Генетические алгоритмы – адаптивные методы поиска, которые используются для решения задач функциональной оптимизации.

Представляют собой своего рода модели машинного исследования поискового пространства, построенное на эволюционной метафоре.

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

Обратите внимание

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

Генетические алгоритмы применяются для решения следующих задач:

· оптимизация функций;

· разнообразные задачи на графах (задача коммивояжера, раскраска и т.д.);

· настройка и обучение искусственной нейронной сети;

· задачи компоновки;

· составление расписаний;

· игровые стратегии;

· аппроксимация функций;

· искусственная жизнь;

· биоинформатика.

Оценка особей популяции

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

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

Отбор (селекция)

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

Скрещивание

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

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

Этот оператор определяет передачу признаков родителей потомкам, к ним применяется вероятностный оператор скрещивания, который строит на их основе новые (1 или 2) решения-потомка

Мутация

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

История эволюционного моделирования

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

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

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

Основы современных генетических алгоритмов были заложены в книге Холланда, использовавшего в них принципы дарвинизма. Правда генетическими они стали называться позднее, а в 1975 году автор назвал их репродуктивными планами и рассматривал, прежде всего, как алгоритмы адаптации.

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

Важно

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

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

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

В 1986 году появилось новое направление эволюционного моделирования — искусственные иммунные системы.

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

В середине 1990-х годов эти принципы активно развивались в исследованиях Форреста, Тимминса, Нила и других исследователей. Суть метода заключается в проведении эволюционного процесса клеток искусственной иммунной системы по принципам и механизмам, протекающим в естественных иммунных системах.

В 1995 году в США Сторном и Прайсом разработан метод дифференциальной эволюции. Он работает напрямую с вещественными числами любой точности и подходит для оптимизации многомерных функций, в том числе не дифференцируемых, с большим количеством локальных оптимумов. Метод прост в реализации и легко распараллеливается.

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

Совет

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

эволюционные методы искусственный интеллект генетические алгоритмы искусственные иммунные системы

Как изучать жизненный цикл: дедукция и индукция

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

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

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

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

Несмотря на то, что слова “математическое моделирование” обычно пугают ученых с биологическим образованием, а слова “эволюция и жизненный цикл” отваживают математиков как нечто трудно описываемое значками и потому негодное для “настоящей ” науки, тем не менее и тем и другим должно быть понятно, что речь идет о таких насущных проблемах, как причины и сущность старения, прогнозирование демографических явлений. Так что ученые из МГУ предложили исключительно актуальную тему для раздумий и в компактном виде суммировали достижения исследований последних двух-трех веков. Начавшись в конце 18-го века историческими трудами Эйлера и Мальтуса, на сегодняшний день число ученых, вовлеченных в работу по данной теме, составляет тысячи. Более того, если Эйлер и Мальтус опирались не столько на эксперементальные данные, сколько на собственный здравый смысл, то сегодняшние ученые имеют в своем распроряжении точные данные о биологических и демографических характеристиках многих групп животных и растений, уже опубликовано более полутора десятков тысяч статей, содержащих и анализирующих эти данные. Наибольшее внимание уделяется растениям, птицам, насекомым и рыбам. Для проверки и параметризации любой мыслимой модели этого более чем достаточно. Так что дело за самими моделями и конкретизацией задач, которые должны этими моделями решаться. Вернее, следует поменять порядок – сначала задачи, а уж потом методы.

Задачи, которые на сегодняшний день считаются актуальными для исследователей эволюции жизненного цикла, были определены еще в середине 70-х годов прошлого века Стернсом (Stearns, 1976. Life-history tactics: a review of the ideas). Вот эти задачи, сформулированные в виде вопросов:

Почему организмы бывают большими и маленькими?

Почему одни созревают позже, другие раньше?

Почему у одних плодовитость высокая, а у других – низкая?

Почему у одних жизнь короткая, а у других – долгая?

Почему организмы стареют и умирают?

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

Обратите внимание

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

Итак, конкуренция за ресурсы и естественный отбор, приводящий к максимизации и стабилизации демографических показателей – вот базовые установки для моделирования.

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

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

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

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

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

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

Максимизировать этот показатель, называемый «жизненным репродуктивным успехом», можно и за счет увеличения плодовитости, и за счет увеличения выживаемости.

Важно

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

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

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

Если бы это правило было общим, то преимущество неизменно получали бы неспециализированные формы, а высокоэффективные потребители ресурсов всегда бы проигрывали и не появлялись на эволюционной арене. Было бы чрезвычайно полезно рассмотреть соотношение результатов моделирования для микро- и макроэволюции.

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

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

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

Именно здесь и кроется основная трудность моделиста: какой из показателей оптимизировать? Можно оптимизировать разницу между рождаемостью и смертностью (мальтузианский параметр) или их отношение, или используемую емкость среды…

Совет

Сразу все три параметра (а на самом деле их больше) в модели оптимизировать не получается. Кроме того, в подобных моделях редко обосновывается выбор того или иного параметра для оптимизации.

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

Совершенно особый класс моделей, который касется эволюции демографических характеристик, назван в статье адаптивно-динамическим моделированием. Модели этого класса опираются на теорию игр.

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

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

Авторы указывают, что среди важных заслуг этого подхода – объяснение механизма симпатрического видообразования. Дивергенция может происходить просто вследствие внутренней динамики разнородных частей одной популяции (о моделировании механизмов симатрического видообразования см. Женская привередливость способствует видообразованию. «Элементы», 25.12.09).

Эволюционное моделирование. Проблемы формы и содержания

В.Э. Карпов

НИИ Информационных технологий, г.Москва

Эволюционное моделирование. Проблемы формы и содержания Новости искусственного интеллекта №5, 2003
Сложно сказать точно, когда впервые возникла простая идея, заключающаяся в том, что вместо моделирования сложного объекта в уже готовом виде следует заниматься моделированием эволюции некоторого простого объекта. Действительно, запустить эволюционный процесс и ждать, когда с течением времени появится требуемый ответ – это достаточно естественный и привлекательный путь решения сложно формализуемых задач.

История развития этого направления, называемого эволюционным моделированием, весьма характерна и показательна. Не успев оформиться в некоторую строгую и формальную теорию, эволюционное моделирование (ЭМ) на некоторое время уходит с арены активно разрабатываемых методов искусственного интеллекта.

Затем, то ли по причине кризиса идей в ИИ, то ли по непреложному закону переоткрытия уже известного, но термин ЭМ спустя много лет возникает вновь.

Правда, уже как новое направление ИИ, объединяющее в себе множество методов и моделей со своей классификацией и всеми вытекающими из узкой специализации последствиями.

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

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

История вопроса

Впервые, пожалуй, идея ЭМ была явно сформулирована еще в 60-х гг. Л.Фогелем в работе «Искусственный интеллект и эволюционное моделирование» ([Fogel, 1966] или в русском переводе [Фогель Л. и др., 1969]), которую можно было бы назвать классической, если б она не была, фактически, предана незаслуженному забвению. Причин тому можно выделить несколько.

Начнем с того, что работы Фогеля появились в крайне неудачное для них время. То было время бурного расцвета ИИ, когда одна за другой появлялись новые концепции создания интеллектуальных систем, когда казалось, что вот-вот появится некая панацея, и искусственный интеллект, как синоним искусственного разума, будет создан.

Поэтому идея эволюционного моделирования была лишь одной в ряду многих.

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

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

Можно сказать, что процесс эволюции как таковой полностью выпал из рассмотрения.

Самое интересное, что параллельно, практически одновременно с работами Фогеля создавались разнообразные модели, которые могли бы стать основой для эволюции. Например, исследования М.Л.Цетлина по теории автоматов ([Цетлин, 1969]) должны бы дать эволюционному моделированию замечательную модель объекта эволюции.

Обратите внимание

С другой стороны, интенсивно развивались и формализовывались модели эволюции как таковой ([Шмальгаузен, 1968]).

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

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

Ознаменовалось это прежде всего появлением такого явления, как генетические алгоритмы. Предложенные Холландом [Holland, 1975] генетические алгоритмы (ГА), как водится, изначально претендовали на революционный метод решения интеллектуальных поисковых задач.

Приверженцы этого направления утверждают, что ГА основываются на теории эволюции Дарвина (а именно, на идее естественного отбора). О проблемах ГА мы поговорим позже.

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

В то же время предпринимались попытки возобновления исследований в области ЭМ. Речь идет прежде всего о работах И.Л.Букатовой ([Букатова, 1975]). Однако даже в одной из наиболее значительных работ ([Букатова и др.

, 1991]) факторы эволюции лишь декларируются. Фактически речь идет о повторении исследований Фогеля на несколько более высоком качественном уровне с улучшенной методологической (декларативно) проработкой.

Даже основной объект эволюции остался на том же уровне, что и у основателей ЭМ.

Заканчивая предысторию вопроса, можно сделать еще пару замечаний. Не исключено, что само мышление человека (по крайне мере та часть, которая относится к понятию инсайта – озарения) является эволюционным процессом. Речь идет о переборе на подсознательном уровне вариантов решения задачи [Тихомиров, 1966].

Важно

Раз перебор – значит, необходим механизм эффективного решения этой комбинаторной задачи. А это и есть предмет ЭМ. Кроме того, принятый в ЭМ подход достаточно хорошо сходится и с представлениями биологов относительно того, что отличает живые организмы высокого уровня развития от примитивных. Например, Р.

Фокс в [Фокс, 1992] пишет: «биологическое преимущество развитой нервной системы состоит в способности к предсказанию нелинейных событий на основе быстрого моделирования».

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

открытая библиотека учебной информации

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

В начале 70-х годов лауреат Нобелœевской премии М.Эйген предпринял впечатляющую попытку построения моделœей возникновения в ранней биосфере Земли молекулярно-генетических систем обработки информации.

Наиболее известная из них – модель “квазивидов”, описывающая простую эволюцию полинуклеотидных (информационных) последовательностей. Вслед за Эйгеном в 1980-м новосибирскими учеными В.Ратнером и В.

Шаминым была предложена модель “сайзеров”.

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

Модельно заданы приспособленности “особей” как функции векторов.

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

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

Фермент трансляции обеспечивает “изготовление” произвольного фермента по записанной в матрице информации. Фермент репликации обеспечивает копирование полинуклеотидной матрицы. Сайзер достаточен для самовоспроизведения.

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

Совет

К началу 50-х годов в науке сформировалась синтетическая теория эволюции, основанная на объединœении генетики и дарвиновского учения о естественном отборе.

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

При этом в последующие десятилетия появились модели, исследующие молекулярно-генетические аспекты эволюции.

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

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

Полученная оценка указывает на то, что случайное формирование белка было вполне вероятно в процессе эволюции.

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

Отдельный автомат можно рассматривать как модель молекулярно-генетической системы управления живой клетки, причем каждый логический элемент интерпретируется как регулятор синтеза определœенного фермента. Модели Кауфмана позволяют сделать ряд предсказаний относительно “программ” жизнедеятельности клетки.

Обратите внимание

В частности, продемонстрировано, что для одновременного обеспечения устойчивости и гибкости программы число входов логических элементов должно быть ограничено определœенным интервалом, а именно составлять величину примерно равную 2-3.

Согласованность и эффективность работы элементов биологических организмов наводит на мысль: а можно ли использовать принципы биологической эволюции для оптимизации практически важных для человека систем? Одна из первых схем эволюционной оптимизации была предложена в 60-е годы П.Фогелœем, А.Оуэнсом и М.

Уолшем; эффективность этой схемы на практике была продемонстрирована И.Букатовой из Москвы. Также в последнее время проявляется большой интерес к исследованию и использованию генетического алгоритма, предложенного Дж.Холландом из Мичиганского университета.

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

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

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

Читайте также

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

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

– Лекция: Эволюционное моделирование и генетические алгоритмы

Темы научных исследований и рефератов, интернет-листов Математическое моделирование: история, личности, будущее. Компьютерное моделирование и его особенности. Роль математического моделирования в современном мире. Рассматриваются основные понятия и принципы… [читать подробенее]

– ЭВОЛЮЦИОННОЕ МОДЕЛИРОВАНИЕ

БИОКОМПЬЮТЕР Если оглянуться и окинуть непредвзятым взглядом историю мирового компьютинга, неминуемо обнаруживаешь: огромный корабль компьютерного приборостроения находится в движении. Он медленно, но верно разворачивается от чисто счетной техники, через… [читать подробенее]

Космики: моделирование эволюции многоклеточных организмов

Здравствуй, Хабр!

Несколько лет назад в прикладных целях я реализовал обычный Force-based визуализатор графов.

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

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

shift+click, shift+drag, alt+click.

потрогать лучше всего получится в Chrome или Safari по причине V8 javascript.

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

Эксперименты выросли в желание обеспечить взаимодействие множества таких объектов по некоторым принципам, так, чтобы за этим было интересно наблюдать:

• объект считаем моделью тела многоклеточного организма, кодовое название «космик»
• космики состоят из клеток (cell) и склеек (stick)
• клетки имеют собственную энергию, с ростом энергии меняется размер и цвет
• склейки имеют энергию, определяющую её упругость, равную минимальной из энергий склеенных клеток
• клетки космика отталкиваются друг от друга с силой, пропорциональной энергии клеток
• склейки клеток препятствуют процессу отталкивания клеток с силой, пропорциональной энергии склеек
• головной клеткой космика считается клетка с наибольшей энергией
• космики стремятся поглотить (присоединить к себе) других космиков
• космик поглощает другого космика, приблизившись к его головной клетке любой собственной клеткой, обладающей большей энергией, чем головная клетка поглощаемого космика
• космики стремятся уклониться от поглощения другими космиками
• ускорение космика формируется суммой ускорений его клеток
• каждая клетка ускоряется в направлении всех клеток, которые она способна поглотить, с силой, пропорциональной её собственной энергии
• каждая клетка ускоряется в направлении от всех клеток, которые способны её поглотить, с силой, пропорциональной её собственной энергии

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

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

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

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

Важно

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

Перенос модели на GPU дал возможность использовать 8-16K частиц вместо 250 в браузерном прототипе.

Это то, что есть на сегодняшний момент. Имеющие CUDA 2.

0 совместимые устройства, могут потрогать модельку лично: потрогать.

В архиве, кроме прочего, ссылка на SDK для Win7 x64, который нужно установить перед запуском exe (UPD: добавил в архив ещё один dll, теперь должен и без SDK стартовать). На XP 32bit тоже работает, ссылку можно взять здесь: Cuda SDK.

p — снять с паузы s — показать slidebar'ы r — смена режима отображения h — пометить головные клетки f — fullscreen Немного о дальнейших планах: Конечно, хочется больше клеток. После оптимизации GTX 580 считает 16K клеток на частоте 30 FPS, в видео участвуют 8K клеток на частоте 120FPS. Сказывается квадратичная сложность алгоритма, так как все клетки влияют на все клетки. Применение алгоритма оптимизации Barnes-Hut'а на CUDA, судя по прочитанным научным статьям от тех, кто это уже переносил на GPU, даёт эффект только за пределами порога в 50K частиц, что вне realtime порога ? Впрочем, мне это всё ещё кажется сомнительным. Кроме того, порядок межклеточных взаимодействий значительно сложнее гравитационного. Теоретически есть возможность считать одновременно 256K частиц на тех же 30FPS независимыми «галактиками» по 1K частиц (отображать на экране как сетку 16×16). С точки зрения эволюции, 256K частиц, пусть и сегментированных в независимые галактики, может оказаться значительно более полезным, чем непосредственное взаимодействие 16K клеток в пределах одной галактики. Обмен особями можно устраивать по раундам, обеспечивая межгалактический mortal kombat ? По тому же принципу можно реализовать распределённую версию модели, например, в виде симпатичного screensaver'а. Начислять энтузиастам очки за время, которое их железо крутило космос, показывая им процесс в виде заставки. Очки можно будет тратить в конструкторе особей, которые будут вбрасываться в распределённый космос, мутировать и эволюционировать — «демиург» сможет отслеживать успехи своей популяции и количество материи, подконтрольной его особям на просторах глобального космоса. Ключевую роль в дальнейшем развитии проекта должен сыграть морфогенетический алгоритм, который при столь скромных топологических возможностях (количества клеток / особь) сумеет обеспечить видовое многообразие особей. Надеюсь, удастся его реализовать. Пока всё, спасибо за внимание! P.S. Энтузиасты, автономно запустившие модель — просьба написать — что за железо и какой FPS в консоли (консоль на заднем плане вторым окном)

UPD: dropbox убрал возможность размещать материалы по открытой ссылке, дублирую ссылку на материалы из статьи — Ya.disk

UPD: демо движка космиков 2013, с soft-body физикой