Теоритическая часть

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

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

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

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

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

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

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

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

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

 f(x1, x2, x3, :, xN)

Для того чтобы заработал ГА, нам необходимо представить независимые переменные в виде хромосом.

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


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

  1. В первом поколении все хромосомы генерируются случайно.
  2. Применяют генетические операторы (кроссовер, мутация, инверсия)
  3. Производиться отбор решений в зависимости от целевой функции
  4. Отбрасываются наихудшие варианты и на их место ставят наилучшие
  5. Если найденные решения не являются оптимальными, то переходим к этапу 2

Существуют следующие генетические операторы

  1. кроссовер
  2. мутация
  3. инверсия

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

001100101110010|11000   -------->   00110010111001011100
110101101101000|11100		

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

00110010111001011000   -------->   00110010111001111000

3. Инверсия инвертирует (изменяет) порядок бит в хромосоме путем циклической перестановки (случайное количество раз). Многие модификации ГА обходятся без данного генетического оператора.

00110010111001011000   -------->   11000001100101110010

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

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


Практика. Применение ГА в компьютерных вирусах.

Вот, как нам представляется возможным претворить ГА в жизнь. Пройдёмся по "этам работы генетического алгоритма": Сгенерировать случайные хромосомы (код) мы не можем, т.к. его работоспособность будет нулевая (почти наверное:). Поэтому за начальный код берем наше рабочее тело вируса. В качестве подобия генетических операторов будет выступать пермутация, т.е. реализуем только мутацию и инверсию, которые мы понимаем в следующем смысле: мутация - изменение отдельно взятой команды на ее возможный эквивалент из списка; инверсия - меняем команды или блоки команд местами. Целевой функцией, в коей вся сложность и заключается, на наш взгляд должна быть функция наименьшей похожести кода потомка от предка (конечно есть и другие варианты: быстрота, размер, ... ) Параметрами мы предлагаем считать наборы вероятностей пермутациии (такие как "вероятностть мутации команды MOV" или "вероятность перестановки двух соседних команд"). Дело обстоит так, потому что во-первых, код нельзя считать параметром, а функция зависит именно от кода, во-вторых, необходимо в любом случае сохранять случайность изменений, отловив в этом закономерность, а это - теория вероятностей.:) Т.о. вирус генерирует N потомков, с помощью целевой функции выбирает наилучший и именно им заражает жертву.

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

Вряд ли, конечно, в ближайшем будущем кто-нибудь реализует что-то подобное, но факт остаётся фактом - это весьма перспективное направление... Вперёд, друзья! :)

04.06.02