Искусственный интеллект

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

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

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

В биологии каждая особь состоит из клеток, содержащих в себе набор молекул ДНК. При размножении происходит взаимодействие ДНК особей, в результате чего образуется ДНК потомка. Существует три основных способа взаимодействия:

Кроссовер (или скрещивание) - операция, при которой две хромосомы обмениваются частями.

Мутация - случайное изменение хромосомы (изменение состояния одного из генов на противоположное).

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

В ГА чаще используются первые два способа взаимодействия хромосом.

Последовательность действий ГА выглядит следующим образом:

Шаг 1. создание начальной популяции, т.е. присвоение аргументам целевой функции случайных значений;

Шаг 2. вычисление значения целевой функции, в соответствии со значениями аргументов, заданных на первом шаге;

Шаг 3. преобразование аргументов функции в двоичный формат;

Шаг. 4 применение операций скрещивания и мутации для всего набора хромосом (популяции). На этом шаге количество особей в популяции возрастает;

Шаг 5. селекция популяции - формирование новой популяции из старой, путем отбора новых хромосом и удаления старых, после чего старая популяция вымирает;

Шаг. 6. обратное преобразование аргументов функции в десятеричный формат;

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

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

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

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

Более подробный обзор систем ИИ можно найти в работах С. Бобровского (Бобровский (2001)), а одна из самых больших подборок материалов по этой теме находится здесь: http://dir.vahoo.com/science/computer science/artificial intelligence.

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

1. The Journal of Artificial Societies and Social Simulation (JASSS,

http://iasss.soc.surrev.ac.uk);

2. American Association for Artificial Intelligence (AAAI,

www.aaai.org);

3. International Society of Artificial Life (ISAL, www.alifc.org);