Общая характеристика работы

Актуальность проблемы. В последнее время все шире применяется автоматное программирование, в рамках которого поведение программ описывается с помощью конечных детерминированных автоматов (в дальнейшем автоматов [1]).

Для многих задач автоматы удается строить эвристически, однако существуют задачи, для которых такое построение затруднительно или невозможно. Известны задачи (например, итерированная дилемма узников [2] и задача о «флибах» [3, 4]), в которых применение генетических алгоритмов (направленного перебора) позволяет генерировать автоматы. Это повышает уровень автоматизации автоматных программ и является одним из первых шагов к автоматическому построению программ.

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

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

Основные задачи исследования состоят в следующем:

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

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

3. Разработка модификаций генетических алгоритмов при построении автоматов для ряда задач.

4.Исследование эффективности генетических алгоритмов при построении двух разнотипных автоматов для одной из рассмотренных задач.

Методы исследования. В работе использовались методы теории автоматов, программирования и генетические алгоритмы.

Научная новизна. В работе получены новые научные результаты, которые выносятся на защиту:

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

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

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

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

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

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

Внедрение результатов работы. Результаты, полученные в диссертации, используются на практике в компании Транзас (Санкт-Петербург) при разработке тренажера вертолета, а также в учебном процессе на кафедре «Компьютерные технологии» СПбГУ ИТМО по курсу «Теория автоматов в программировании».

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

Для различных биологических объектов характерна оптимальность, а также согласованность и эффективностью их работы. Многих исследователей давно интересовал «философский» вопрос - возможно ли эффективное построение значимых и полезных для человека систем на основе принципов биологической эволюции?

Подобные идеи возникали у ряда исследователей. В 1962 г. Л. Фогель начал моделировать интеллектуальное поведение индивида и его развитие в процессе эволюции [6]. При этом поведение индивида задавалось конечным автоматом. Продолжая эти исследования, Л. Фогель, А. Оуэнс и М. Уолш предложили в 1966 г. схему эволюции конечных автоматов, решающих задачи предсказания [3]. Примерно в это же время (в середине 60-х годов) Дж. Холланд разработал новый метод поиска оптимальных решений - генетические алгоритмы. Результатом его исследований стала книга [7], вышедшая в 1975 г. Эти работы заложили основы эволюционных вычислений.

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

Популяция - это совокупность особей на рассматриваемой стадии эволюции.

Индивид (особь) - единичный представитель популяции.

Хромосома - структура, содержащая генетический код индивида.

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

Функция приспособленности (fitness-функция, приспособленность) - определяет, как близка особь к решению задачи.

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

Стратегия отбора определяет каким образом формируется новое поколение особей. Известны различные стратегии отбора, например, отбор отсечением [8], турнирный отбор [9], элитизм [9] и пропорциональный отбор [8]. Кратко опишем особенности каждой из этих стратегий:

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

Турнирный отбор работает следующим образом: из популяции случайным образом выбирается Ь особей. Наиболее приспособленная из этих особей допускается к скрещиванию (между особями проводится турнир).

Пропорциональный отбор подразумевает, что сначала подсчитывается приспособленность каждой особи ±₁ и вычисляется средняя приспособленность особей в популяции :Е_ср=1_1. После этого строится промежуточная популяция, причем вероятность попадания особи в эту популяцию определятся соотношением. Например, если дробь равна 2.36, то особь будет добавлена в промежуточную популяцию два раза. С вероятностью 0.36 она будет добавлена третий раз. Особи для скрещивания выбираются из промежуточной популяции случайным равновероятным образом.

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

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

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

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

Для генетических алгоритмов характерна относительно простая структура особей. 3. Koza [10] предложил задавать особи в виде деревьев решений. Генетические алгоритмы, основанные на таких структурах, получили название генетическое программирование.

Термины «генетические алгоритмы» и «генетическое программирование» понимаются в широком смысле - для обозначения эволюционных вычислений. Для обозначения генетических алгоритмов, оперирующих с битовыми строками фиксированной длины (описанных, например, в работе [2]), используется термин «традиционные генетические алгоритмы».

Эксперименты Фогеля (регрессия)

Один из создателей эволюционного программирования Л.Фогель рассматривал интеллектуальное поведение индивида, как способность успешно предсказывать поведение среды, в которой он находится, и в соответствии с этим действовать. В 60-х в проведенных экспериментах Л. Фогель моделировал поведение простейшего живого существа, названного «флиб», которое способно предсказывать изменения параметра среды, обладающего периодичностью. Это существо моделировалось конечным автоматом с действиями на переходах - автоматом Мили [11]. В качестве среды выступала последовательность символов над двоичным алфавитом, например, (1111010010). На вход автомата в каждый момент времени подавалась битовое значение параметра окружающей среды. Автомат формировал значение выходной переменной - возможное значение рассматриваемого параметра в следующий момент времени. На рис. 1 приведен один из возможных автоматов, который построен для распознавания, указанной выше последовательности.<.p>

В начале эксперимента [3] задавалась периодическая последовательность символов над двоичным алфавитом, например (101110011101) и выбирался префикс данной последовательности малой длины. После этого создавалась популяция автоматов с небольшим числом состояний (например, пять). Затем каждый из автоматов путем одной из описанных ниже пяти мутаций (выбираемой случайным образом равномерно) производил потомка. Далее над потомком подобным образом производилось еще несколько мутаций (их число определялось случайным образом). Получившийся в результате мутаций автомат добавлялся в популяцию. При этом были допустимы следующие мутации автомата:

добавление состояния;

удаление состояния (в случае, если число состояний больше единицы);

замена начального состояния (в случае, если число состояний больше единицы);

замена действия на переходе.

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

Задача оптимизации функций

В работе [12] предлагается подход, позволяющий свести задачу оптимизации функций к задаче управления. При этом процесс нахождения глобального максимума сводится к перемещению по дискретизированному пространству поиска. Для управления перемещением вводится автомат Мили. Сформулируем рассматриваемую задачу: задано некоторое множество: Q с R +. Перемещение объекта управления по пространству Q описывается следующим образом:

x_t+₁= x_t + f^(x_t), где x_t с Q, функция f+х R —{x|x_t + xeQ}- стратегия перемещения.

Таким образом, перемещение на текущем шаге (в текущий момент времени) зависит от значений функции , исследованных на прошлом и позапрошлом шагах. Пусть T с N,T > 1 - время, отведенное на перемещение по пространству Q. Задачей является _1Tf/r, и (Ф^_т) + 1) - максимизация функционала.

Таким образом, производится поиск стратегий, которые, с одной стороны, должны искать глобальный максимум (этому требованию соответствует второе слагаемое в сумме), а, с другой стороны, к окончанию поиска текущее положение x_T должно быть «недалеко» от максимального из исследованных (этому требованию соответствует первое слагаемое). Константа и в числителе первого слагаемого устанавливает приоритет между первым и вторым требованиями.

Функция (f,T)является функцией приспособленности. Стратегия перемещения f реализуется.

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

Для кодирования графов переходов автоматов используется три класса: StateMachine, State и Branch. В качестве главного класса автомата применяется класс StateMachine. Классы State и Branch реализуют его состояния и переходы соответственно.

Массив states в классе StateMachine содержит состояния автомата автопилота. Поле currentStateIndex используется для хранения номера текущего состояния автомата. В массив brunches класса State включены переходы из данного состояния. /

Поле stateIndex в классе Branch содержит номер состояния, в которое переходит автомат. В массиве outputs хранятся значения выходных переменных, генерируемых при переходе.

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