4. Искусственная жизнь.

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

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

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

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

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

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

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

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

2. Произвести эволюцию популяции следующими способами:

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

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

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

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

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

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

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

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

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

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

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

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

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

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