ИСКУССТВЕННАЯ ЖИЗНЬ.

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

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

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

а) адаптироваться к меняющимся условиям внешней среды и конкурировать за ресурсы;

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

в) мутировать под влиянием определенных воздействий или случайно.

Этапы генетического алгоритма:

1. Создать начальную случайную популяцию, состоящую из множества решений(особи или хромосомы). Т.е. популяция – это множество векторов P = {} = … , где n – размер популяции, – особь. Каждая из позиций вектора хромосомы называется геном. Получить оценку качества Z_i для каждой особи.
2. Произвести эволюцию популяции следующими способами:

1.

2.

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

2.2. Размножение: в соответствии с определенным качеством особи она имеет вероятность размножения тем большую, чем точка удачнее.

Примеры законов размножения:

- деление: исходная особь разделяется на две (или несколько) близлежащих точки: и , где векторы и определяют­ся алгоритмом;

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

Виды кроссинговера:

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

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

в) равномерный кроссинговер. Каждый ген первого родителя наследуется первым потомком с вероятностью, определенной на шаге 2.1, в противном случае этот ген передается второму потомку. И наоборот.

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

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

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

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

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

4.2. Клеточные автоматы.

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

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

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

Свойства клеточных автоматов:

- изменения значений всех клеток происходят одновременно после вычисления нового состояния каждой клетки решетки;

- решетка автомата однородна: невозможно отличить какие-либо две области решетки по ландшафту;

- взаимодействия локальны, т.е. на каждую клетку влияют лишь клетки окрестности (как правило, соседние);

- множество состояний клетки конечно.

Типы клеточных автоматов:

- с клетками с памятью, когда новое состояние клетки зависит от её текущего состояния и с клетками без памяти – когда не зависит;

- статичные, у которых положение клетки во время эволюции остается постоянным и подвижные, у которых возможно изменение положения клетки в решетке;

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

- одномерные, двумерные и автоматы больших размерностей;

- локальные и автоматы с глобальным параметром.

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

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