Главная >> Диссертации - все темы

Pages: |

| 2 |

«Использование генетических алгоритмов для генерации конечных автоматов ...»

-- [ Страница 1 ] --

Санкт-Петербургский государственный университет информационных технологий

механики и оптики

На правах рукописи

Лобанов Павел Геннадьевич

Использование генетических алгоритмов для генерации

конечных автоматов

Специальность 05.13.11 – Математическое и программное обеспечение

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

Научный руководитель – доктор технических наук, профессор Шалыто А. А.

Санкт-Петербург

ВВЕДЕНИЕ

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

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

Генетические алгоритмы [5] применяются при решении широкого круга задач.

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

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

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

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

Основные задачи

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

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

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

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

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

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

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

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

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

Результаты диссертации получены в ходе работ по государственному контракту «Технология генетического программирования для генерации автоматов управления системами со сложным поведением» (шифр «2007-4-14-18-01-033»), проводимых СПбГУ ИТМО в 2007 – 2008 гг. в рамках Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научнотехнологического комплекса России» на 2007 – 2012 гг.

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

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

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

Апробация диссертации. Основные положения диссертационной работы докладывались на 4-й Всероссийской научной конференции «Управление и информационные технологии» СПбГЭТУ «ЛЭТИ» (2006), XXXVI научной и учебнометодической конференции профессорско-преподавательского и научного состава СПбГУ ИТМО (2007), IV межвузовской конференции молодых ученых СПбГУ ИТМО (2007), XIV Всероссийской научно-методической конференции «Телематика-2007»

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

Публикации. По теме диссертации опубликовано шесть печатных работ, в том числе три в изданиях из перечня ВАК («Известия РАН. Теория и системы управления»

и «Научно-технический вестник СПбГУ ИТМО»).

Структура диссертации. Диссертация изложена на 114 страницах и состоит из введения, четырех глав и заключения. Список литературы содержит 32 наименования.

Работа содержит 42 рисунков и 15 таблиц.

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

ГЛАВА 1. ОБЗОР ЗАДАЧ, В КОТОРЫХ ГЕНЕРАЦИЯ КОНЕЧНЫХ

АВТОМАТОВ ОСУЩЕСТВЛЯЕТСЯ С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ

АЛГОРИТМОВ

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

Подобные идеи возникали у ряда исследователей. В 1962 г. Л. Фогель начал моделировать интеллектуальное поведение индивида и его развитие в процессе эволюции [6]. При этом поведение индивида задавалось конечным автоматом.

Продолжая эти исследования, Л. Фогель, А. Оуэнс и М. Уолш предложили в 1966 г.

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

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

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

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

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

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

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

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

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

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

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

• Пропорциональный отбор подразумевает, что сначала подсчитывается промежуточная популяция, причем вероятность попадания особи в эту популяцию определятся соотношением. Например, если дробь равна 2.36, то особь будет добавлена в промежуточную популяцию два раза. С вероятностью 0.36 она будет добавлена третий раз. Особи для скрещивания выбираются из промежуточной популяции случайным равновероятным • Элитизм подразумевает, что несколько лучших родительских особей добавляются в новое поколение. Использование элитизма позволяет не потерять хорошее промежуточное решение, но в тоже время из-за него алгоритм может застрять в локальном экстремуме.

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

Мутация – случайное изменение одной или нескольких позиций в хромосоме.

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

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

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

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

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

Термины «генетические алгоритмы» и «генетическое программирование»

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

Один из создателей эволюционного программирования Л.Фогель рассматривал интеллектуальное поведение индивида, как способность успешно предсказывать поведение среды, в которой он находится, и в соответствии с этим действовать. В 60-x годах прошлого века Л. Фогель поставил ряд экспериментов [3] по созданию искусственных систем, способных адаптироваться к первоначально не известной им среде.

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

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

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

Получившийся в результате мутаций автомат добавлялся в популяцию. При этом были допустимы следующие мутации автомата:

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

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

• замена начального состояния (в случае, если число состояний больше • замена действия на переходе.

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

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

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

В работе [12] предлагается подход, позволяющий свести задачу оптимизации функций к задаче управления. При этом процесс нахождения глобального максимума сводится к перемещению по дискретизированному пространству поиска. Для управления перемещением вводится автомат Мили. Сформулируем рассматриваемую задачу: задано некоторое множество R 2, и на нем определена функция : R +. Перемещение объекта управления по пространству описывается f : R + R + {x | xt + x } – стратегия перемещения. Таким образом, перемещение на текущем шаге (в текущий момент времени) зависит от значений функции, исследованных на прошлом и позапрошлом шагах. Пусть T N, T > 1 – перемещения f. Таким образом, производится поиск стратегий, которые, с одной стороны, должны искать глобальный максимум (этому требованию соответствует второе слагаемое в сумме), а, с другой стороны, к окончанию поиска текущее положение xT должно быть «недалеко» от максимального из исследованных (этому требованию соответствует первое слагаемое). Константа в числителе первого слагаемого устанавливает приоритет между первым и вторым требованиями.

перемещения f реализуется, как показано на рис. 2.

Sensor device (преобразователь) переводит непрерывные значения xt), xt 1) из R + во множество X дискретных входных воздействий автомата Мили A, реализуя функцию : R 2 X. Данная функция наряду с автоматом A выводится генетическим алгоритмом.

Finite state machine Mealy (автомат Мили) A задается множеством входных воздействий X, действий Y, состояний S, начальным состоянием s1 S, функцией переходов автомата : X S S и функцией выходов автомата : X S Y.

Actor device (устройство перемещения) переводит выходные воздействия автомата в команду по перемещению объекта управления по двумерной сетке, дискретизирующей. Устройство перемещения хранит информацию о текущем и предыдущем положениях устройства управления xt и xt 1, а также вектор перемещения dt, который определяет как направление перемещения, так и величину шага, которая может быть равна шагу сетки, либо удвоенному шагу сетки. В зависимости от выходных воздействий автомата устройство перемещения оставляет устройство управления на месте xt +1 = xt, либо перемещает его в одно из четырех ортогональных направлений. При этом шаг перемещения может остаться неизменным, либо удвоиться, либо уменьшиться вдвое. Определяется множество возможных перемещению вперед, назад, влево, вправо, вперед с удвоением шага, вперед с уменьшением шага вдвое.

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

Дерево параметризуется константами A, B, которые при вычислении заменяются на значения xt), xt 1). Корнем дерева является cond-выражение. Пример дерева выражений приведен на рис. 3.

Для наглядности иллюстрации в данном дереве не отображена функция.

Результатом вычисления выражения приведенного вида после подстановки значений xt) и xt 1) являются конечное множество переходов (,) и конечное множество выходных воздействий (,), которые определяют функции,. Если в множестве переходов (выходных воздействий) присутствуют два различных перехода (два различных выходных воздействия) из одного состояния, то выбирается самый левый из них (в приведенном примере переход (0,)).

Генетические операции (скрещивание, мутация) определены таким образом, чтобы при их выполнении порождались корректные деревья. Используются три дополнительные генетические операции над вершинами, являющимися списком инструкций (данные вершины обозначены символом {} на рис. 3): удаление поддерева, добавление поддерева, изменение порядка на поддеревьях.

Эксперименты проводились на трех различных функциях :

Параметр n принимал значение равное двум, v = 10, T = 50, а константы µi были выбраны таким образом, чтобы i [0,]. Пространством поиска являлось множество := [0, 10]. Автоматы содержали по 10 состояний. Популяция состояла из 10 автоматов, для каждого из которых случайным образом выбиралось x 0 – положение объекта управления в начальный момент времени.

Графики первой и третьей функций приведены на рис. 4.

В результате экспериментов генетическое программирование сгенерировало стратегии перемещения f, для которых значение функции приспособленности близко к максимальному (единице). Кроме того, найденные стратегии являются устойчивыми как к изменению позиции x 0 объекта управления в начальный момент времени, так и к замене функции приспособленности на другую, которая обладает аналогичными свойствами.

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

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

В работе [13] для выражения стратегий переговорщиков применены конечные автоматы. Входными и выходными воздействиями являются возможные предложения.

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

Приведем описание используемой операции скрещивания. Операция принимает на вход два автомата и выдает один. Для этого множество состояний каждого автомата разбивается на два подмножества. После этого подмножество первого автомата, содержащее указанную вершину, объединяется с подмножеством второго автомата, которое не содержит начальную вершину. Заметим, что некоторые ребра теперь ведут наружу или исходят из вершин, не представленных в полученном автомате. Эти ребра изменяются для корректности автомата. Предложенный метод напоминает скрещивание абстрактных графов, используемое в работе [14].

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

1.5. РАСПОЗНАВАНИЕ НЕРЕГУЛЯРНЫХ ЯЗЫКОВ

На практике языки, которые необходимо классифицировать, редко являются регулярными [15]. Поэтому предпринимались попытки автоматизировать процесс построения распознавателей нерегулярных языков. Простейшим обобщением автомата на более широкий класс языков является автомат с магазинной памятью. Такой автомат отличается от конечного автомата тем, что может использовать в процессе работы стек: по комбинации текущего состояния, входного символа и символа на вершине стека автомат выбирает следующее состояние и, возможно, символ для записи в магазин. Может быть показано, что для любого контекстно-свободного языка можно построить недетерминированный автомат с магазинной памятью, распознающий требуемый язык. Построение же детерминированного автомата с магазинной памятью возможно не всегда. Классическим примером такого языка является язык палиндромов [15].

В работе [16] рассматривается задача построения недетерминированного автомата с магазинной памятью по множеству примеров с помощью генетических алгоритмов. При этом используется построение автоматов, допускающих вход по пустому стеку. В автоматах запрещены -переходы. Может быть показано, что определенные таким образом недетерминированные автоматы с магазинной памятью по-прежнему способны распознавать любые контекстно-свободные языки.

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

F M, S+, S ) = (cor M, S+ )/ 3 + pref M, S+ )/ 3 + stack M, S+ )/ 3) cor M, S ).

Здесь S+ - множество примеров цепочек, принадлежащих языку, S - множество примеров, которые не принадлежат языку цепочек, а cor M, S) - доля верно распознанных автоматом M слов из множества S.

Приведем описание функции pref M, S), смысл которой заключается в том, чтобы премировать автоматы, принимающие как можно более длинные префиксы слов, принадлежащих языку. Пусть при этом pref*(M, w) = max, где v является префиксом w и принимается автоматом;

Функция stack M, S+) премирует автоматы, имеющие меньшее число символов в стеке в конце разбора цепочек из множества примеров S. При этом stack*(M, w) = Автоматы представляются с помощью строк. Для того чтобы избежать экспоненциального роста длины строки, в работе [16] введено ограничение на число переходов автомата. Автомат записывается в виде строки следующим образом: для каждого перехода выписываются начальное состояние, конечное состояние, входной символ, символ на вершине стека, следующее состояние и набор символов, которые размещаются в стеке. Максимальное число символов, которые можно положить в стек фиксируется. Поэтому все строки имеют одинаковую длину. В работе [16] в качестве оператора скрещивания используется двухточечное скрещивание строк, а качестве мутации – мутация над строками. Возможна запись, как в двоичную строку, так и в строку над числами.

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

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

В работе используется специфическое представление автомата с магазинной памятью, названное диаграммой псевдосостояний. Представление аналогично диаграмме переходов конечного автомата Мура [11], но его состояния разделены на различные классы:

• READ-состояния - осуществляют чтение символа из входного потока.

После этого в зависимости от прочитанного символа автомат переходит в следующее состояние.

• POP-состояния - осуществляют чтение символа с вершины стека. Переход выполняется в зависимости от прочитанного символа.

• PUSH-состояния - помещают в стек определенный символ. Они имеют единственный переход.

• ACCEPT-состояния - допускающие состояния автомата. Они не имеют • REJECT-состояния - отвергающие состояния автомата. Они также не Пример диаграммы псевдосостояний приведен на рис. 5.

Диаграммы переходов получаются в результате вычисления выражений на специальном макроязыке APDAL. Выражения, соответствующие искомому автомату, выводятся с использованием генетического программирования. Для простоты входной алфавит автомата полагается равным {a, b}. Стековый алфавит совпадает с входным.

Автор работы [17] вводит следующие инструкции:

• READ - создать новое READ-состояние.

• PUSHA - создать новое PUSH-состояние, помещающее в стек символ a.

• PUSHB - создать новое PUSH-состояние, помещающее в стек символ b.

• POP - создать новое POP-состояние.

• REJECT - создать новое отвергающее состояние.

• ACCEPT - создать новое допускающее состояние.

В качестве аргументов инструкциям передаются состояния, в которые должны вести переходы, исходящие из вершины. Таким образом, инструкции READ и POP имеют два аргумента, инструкции PUSHA и PUSHB - один аргумент, а инструкции REJECT и ACCEPT не имеют аргументов.

Вершины автомата создаются и нумеруются в порядке вычисления выражения. В процессе исполнения поддерживается специальная переменная LASTSTATE, соответствующая номеру последнего созданного состояния. Значение переменной может быть передано в инструкции языка с помощью макроса TOLAST. Макрос DEC уменьшает значение переменной LASTSTATE на единицу.

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

1.6. ПРОЕКТИРОВАНИЕ ЛОГИЧЕСКИХ СХЕМ ДЛЯ АВТОМАТОВ МИЛИ

При аппаратной реализации автоматов Мили возникает задача построения логической схемы, которая реализует данный автомат [18]. Эта задача обычно разбивается на ряд подзадач:

• минимизация число состояний автомата;

• кодирование состояний – сопоставление битовой строки, как номера, • минимизация логической схемы;

• физическая реализация спроектированной схемы.

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

Табл. 1 задает некоторый автомат Мили.

Таблица 1. Таблица, задающая автомат Мили Текущее состояние Следующее состояние Выходное воздействие Если произвести кодирование состояний автомата следующим образом:

{ 0 = 00,s1 = 11 s2 = 01,s3 = 10}, то будет построена схема, приведенная на рис. 6. Она содержит три элемента INV, пять элементов AND, три элемента OR и два Dтриггера.

Если же закодировать состояния иначе: { 0 = 00, s1 = 10, s2 = 01,s3 = 11, то возможна более экономичная реализация автомата (рис. 7), содержащая всего два элемента INV, пять элементов AND, два элемента OR и два D-триггера.

Рис. 7. Более экономичная реализация автомата Мили при втором варианте Наивным решением задачи кодирования состояний является перебор всех возможных способов кодирования, построение минимальной схемы при заданном способе кодирования, выбор способа кодирования, при котором достигается экспоненциальную сложность по числу состояний, в силу того, что такой сложностью обладает перебор всех возможных нумераций. Более того, установлено, что задача нумерации состояний (State Assignment Problem) является NP-полной.

В рассматриваемой работе применяется генетический алгоритм для решения задачи кодирования состояний. Особь генетического алгоритма, задающая решение задачи, кодировалась в хромосому в виде строки длины N над целыми числами из диапазона [0..2 K 1. Пример кодирования особи указанным образом для автомата с шестью состояниями приведен в табл. 2.

Для скрещивания использовалась одноточечная, двухточечная и однородная рекомбинация строк. Мутация осуществлялась путем замены номера некоторого состояния (в позиции от 0 до N 1 ) на другой допустимый номер. Как в случае мутации, так и в случае скрещивания могла получиться хромосома, определяющая некорректный способ кодирования, когда два состояния кодировались одним числом, в то время как некоторому состоянию не был сопоставлен никакой номер. В этом случае особь «штрафовалась», что препятствовало осуществлению недопустимых операций в дальнейшем.

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

Данная эвристика формулируется следующим образом:

• два состояния a, b, для каждого из которых существует переход в состояние c, должны быть закодированы «близкими» значениями;

• два состояния a, b, в каждое из которых существует переход из состояния c, должны быть закодированы «близкими» значениями;

• у первого из указанных правил имеет приоритет над вторым.

«Близость» номеров состояний определяется расстоянием Хемминга между битовыми строками, задающими эти номера: номера, битовые строки которых отличаются не более чем в одной позиции, считаются «близкими», иначе не считаются таковыми. Например, номера 0101 и 1101 являются «близкими», в то время как приспособленности подсчитывалось число случаев x, противоречащих первому требованию, и число случаев y, противоречащих второму требованию. Если при этом хромосома соответствовала недопустимому способу кодирования (по описанным выше причинам), то ей назначался «штраф» – некоторое натуральное число z. При этом функция приспособленности принималась равной f = 2x + y + z.

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

В результате проведенных экспериментов авторам рассматриваемой работы удалось на некоторых известных контрольных задачах (benchmark) получить значения функции приспособленности меньшие, чем те, что были получены известными ранее методами. В табл. 3 в столбце, обозначенном Our GA, приведены полученные результаты. В строках таблицы приведены сравнительные результаты по benchmark.

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

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

Таким образом, в указанной работе решалась задача построения схемы, которая:

• соответствует автомату Мили;

• имеет минимальную площадь;

• имеет ограниченное время обработки сигнала.

Хромосома, кодирующая схему, задавалась матрицей ячеек. Каждая из ячеек содержала два или три (для элемента MUX) входных сигнала, логический элемент и выходной сигнал. Выходные сигналы ячеек предыдущего уровня являлись входными для ячеек следующего уровня. В соответствии с описанной структурой, ячейка кодировалась вектором целых чисел, соответствующих входным сигналам, логическому элементу и выходному сигналу. Пример хромосомы и соответствующей ей логической схемы приведен на рис. 8.

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

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

1.7. ОБЗОР МЕТОДОВ ГЕНЕРАЦИИ АВТОМАТОВ С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ

АЛГОРИТМОВ

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

• Эволюционные алгоритмы (по Л. Фогелю) [3] предполагают, что новые особи появляются только за счет операторов мутации. Алгоритмы данного класса не требуют много памяти для выполнения, однако работают они довольно медленно и легко могут «застрять» в локальном экстремуме.

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

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

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

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

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

Это не сложно сделать, если включить в функцию приспособленности размер структуры, использующейся для кодирования особи. Пусть fi определяет на сколько хорошо i особь решает поставленную задачу и lengthi – размер структуры, использующейся для кодирования i особи. В качестве функции приспособленности можно использовать такую функцию Fi, что 2. Fi < Fj для любых i и j, при которых fi = fj и lengthi < lengthj ;

3. Fi = Fj для любых i и j, при которых fi = fj и lengthi = lengthj.

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

ВЫВОДЫ ПО ГЛАВЕ

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

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

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

4. Выполненный обзор показал:

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

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

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

ГЛАВА 2. ГЕНЕРАЦИЯ АВТОМАТОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ О

ФЛИБАХ

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

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

Одна из важнейших способностей живых существ – предсказание изменений окружающей среды. В качестве простейшей модели живого существа можно использовать конечный автомат. В работе [20] такие конечноавтоматные модели названы флибами (сокращение от finite living blobs – конечные живые капельки).

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

Флиб изменяет свое состояние и формирует значение выходной переменной. Это значение соответствует возможному состоянию среды в следующий момент времени.

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

2.2. СХЕМЫ РАБОТЫ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В ЗАДАЧЕ О ФЛИБАХ

Приведем схемы работы известного и предлагаемого алгоритмов.

Для поиска оптимального предсказателя в работе [20] предлагается использовать следующий генетический алгоритм.

1. Создается поколение случайных флибов.

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

3. Определяются худший и лучший предсказатели в поколении.

4. Лучший предсказатель скрещивается с флибом, выбранным случайным образом.

5. Случайным образом определяется, необходимость применения к полученному флибу оператора мутации. Если это необходимо, то указанный оператор 6. Худший предсказатель в поколении заменяется флибом, полученный в результате скрещивания. После выполненной замены считается, что новое поколение сгенерировано.

7. Если один из флибов достиг уровня предсказания равного 100% или пользователь остановил программу, то алгоритм прекращает работу. В противном случае переходим к пункту 2.

одноточечного скрещивания и мутации, будут подробно рассмотрены в разд. 2.3, 2.6, 2.7.

2.2.2. Предлагаемая модификация алгоритма В настоящей работе предлагается применять метод генерации нового поколения, отличающийся от метода, описанного в разд. 2.2.1. Предлагаемый метод использует турнирный отбор [21] и принцип элитизма (в новое поколение добавляется одна или несколько лучших особей из предыдущего поколения) [22].

Число флибов в поколении будем называть размером поколения.

Предлагаемая модификация алгоритма имеет следующий вид.

1. Создается текущее поколение случайных флибов.

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

3. Строится новое поколение флибов:

a. Создается пустое новое поколение, и в него добавляется лучший предсказатель из текущего поколения.

b. Случайным образом из текущего поколения выбираются две пары флибов.

c. Из каждой пары флибов выбирается лучший предсказатель.

d. Лучшие предсказатели из указанных пар скрещиваются.

e. Случайным образом определяется необходимость применения оператора мутации к полученному флибу. Если это необходимо, то указанный оператор применяется к флибу.

f. К флибу применяется новый оператор мутации – «восстановление связей между состояниями автомата».

g. Флиб добавляется в новое поколение.

h. Переходим к пункту b, если размер нового поколения меньше размера 4. Текущее поколение флибов заменяется новым.

5. Если число поколений меньше заданного пользователем, то переходим к Опишем известный и предлагаемый методы реализации флиба.

Поведение флиба описывается с помощью таблицы переходов и выходов. В табл. 5 в качестве примера приведен флиб с тремя состояниями A, B и C.

Таблица 5. Таблица переходов и выходов для флиба с тремя состояниями Представим эту таблицу в виде строки: 1B0A0C0A1A0B (такое представление используется в работе [20]). Отметим, что число элементов в приведенной строке в четыре раза больше числа состояний флиба. Пронумеруем состояния флиба и элементы строки, задающей его. Первому состоянию и первому элементу строки присвоим номер ноль. Если флиб находится в состоянии с номером s и текущее состояний среды i, то состояние, в которое флиб перейдет, содержится в элементе строки, задающей флиб. Этот элемент имеет номер 4s + 2i + 1. Значение выходной переменной, генерируемой флибом, содержится в элементе с номером 4s + 2i.

Для создания случайного флиба требуется задать значения элементов строки случайным образом.

Приведем алгоритм создания случайного флиба, заданного строкой.

1. Цикл по всем элементам строки, задающей флиб.

a. Если номер элемента четный, то элементу присваивается одно из возможных состояний среды, выбранное случайным образом.

b. Если номер элемента нечетный, то элементу присваивается одно из возможных состояний флиба, выбранное случайным образом.

В настоящей работе предлагается использовать другой способ кодирования флиба – автомат, заданный с помощью графа переходов, который реализуется с помощью трех классов – Flib, State и Branch, которые приведены в Приложении (Листинг 1).

В качестве главного класса при реализации флиба применяется класс Flib.

Классы State и Branch реализуют его состояния и переходы соответственно. В каждом из этих классов имеется метод Clone, предназначенный для создания копий объектов.

_curStateIndex используется для хранения номера текущего состояния флиба в массиве _states. Число правильно предсказанных входных символов размещается в поле _guessCount. Метод Step переводит флиб в новое состояние и, при необходимости, изменяет число правильно предсказанных символов. Метод Nulling возвращает флиб в начальное состояние, и обнуляет число правильно предсказанных символов.

В массиве _branches класса State содержатся дуги переходов из данного состояния. Номер элемента в массиве соответствует входной переменной.

Переменные _stateIndex и _output класса Branch содержат номер состояния, в которое переходит флиб по этой дуге, и значение выходной переменной.

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

Опишем работу алгоритма создания случайного флиба.

1. Создаются объекты, соответствующие состояниям флиба.

2. Для каждого объекта выполняется следующее:

o для состояния формируются переходы из него.

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

2.4. ГЕНЕРАТОР ЗНАЧЕНИЙ ВХОДНОЙ ПЕРЕМЕННОЙ

В качестве значений входной переменной для флибов (как и в работе [20]) используется повторяющаяся последовательность битов (битовая маска), задающая изменения состояний среды. Эта маска в программе зациклена. Код класса для генерации входного сигнала приведен в Приложении (Листинг 2).

Массив символов, соответствующий битовой строке, передается в конструктор класса SimpleSignalSource. Свойства Input и InputNext возвращают входной символ для текущего и следующего моментов времени соответственно. Для перехода к следующему символу используется метод DoStep. Этот метод необходимо вызвать перед началом использования генератора входного сигнала. Метод Nulling сбрасывает генератор входного сигнала в начальное состояние.

Лучшим предсказателем является тот флиб, который наиболее точно предсказывает входной сигнал. В качестве функции приспособленности используется число правильно угаданных символов (поле _guessCount в классе Flib). После формирования нового поколения все флибы в нем устанавливаются в начальное состояние с помощью метода Nulling. Затем для определения приспособленности флибов, каждому из них подается на вход несколько входных символов (по умолчанию их число равно 100). После этого можно строить новое поколение решений, используя в качестве приспособленности флиба значение поля _guessCount, содержащее число правильно предсказанных символов.

2.6. ОПЕРАТОР ОДНОТОЧЕЧНОГО СКРЕЩИВАНИЯ

Опишем известный и предлагаемый алгоритмы работы оператора одноточечного скрещивания.

В работе [20] формирование нового флибов из двух существующих родительских выполняется с помощью оператора одноточечного скрещивания. Приведем описание алгоритма работы этого оператора для флиба, закодированного строкой длины m.

1. Выбирается случайное число j в интервале от 0 до m - 1.

2. Элементы с номерами меньшими либо равными j из строки, задающей первый родительский флиб, копируются в строку, задающую новый флиб.

3. Элементы с номерами большими j из строки, задающей второй родительский флиб, копируются в строку, задающую новый флиб.

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

1. Случайным образом выбирается номер одного из состояний нового флиба.

2. В этот флиб добавляются состояния из первого родителя, номера которых меньше выбранного номера, и состояния из второго родителя, номера которых больше выбранного номера.

3. Формируется и добавляется новое состояние, образованное из состояний первого и второго родителей, которые соответствуют выбранному номеру.

Алгоритм формирования состояния аналогичен алгоритму работы оператора одноточечного скрещивания, который описан в разд. 2.6. Реализация изложенного алгоритма приведена в Приложении (Листинг 3).

Опишем известный и предлагаемый алгоритмы работы оператора мутации.

Алгоритм работы оператора мутации для флиба, заданного битовой строкой, который используется в работе [20], имеет следующий вид.

1. Случайным образом выбирается элемент в строке, задающей флиб.

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

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

1. Случайным образом выбирается состояние флиба.

2. Случайным образом выбирается дуга из выбранного состояния флиба.

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

переменной, то ей присваивается значение состояния среды, b. Если было определено, что изменяется номер состояния, то номеру состояния, в которое переходит флиб, присваивается номер случайно Класс, реализующий данный оператор мутации, приведен в Приложении (Листинг 4).

2.8. АЛГОРИТМ ВОССТАНОВЛЕНИЯ СВЯЗЕЙ МЕЖДУ СОСТОЯНИЯМИ

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

Рассмотрим работу оператора восстановления связей между состояниями на восстановления связей между состояниями, приведен в Приложении (Листинг 5).

Опишем алгоритм реализации предлагаемого оператора мутации.

1. Формируется список доступных состояний (метод InitIndexesList).

Для этого можно, например, использовать функцию рекурсивного обхода 2. Выполняется цикл по всем состояниям. Если текущее состояние не входит в число доступных состояний, то для него выполняются следующие a. Случайным образом выбирается состояние из списка доступных b. Выбирается случайным образом один переход из выбранного c. В текущем состоянии заменяется один переход из этого состояния на переход, который ведет в то же состояние, что и переход, выбранный d. Выбранный в пункте b переход заменяется переходом, который ведет e. Обновляется список доступных состояний. В него добавляется текущее состояние и все состояния, в которые можно попасть из Рассмотрим работу описанного выше алгоритма на примере. На рис. 9 изображен граф переходов для флиба полученного в результате работы генетического алгоритма.

Начальное состояние автомата – A.

Рис. 9. Граф переходов для флиба полученного в результате работы генетического алгоритма Для автомата, граф переходов которого изображен на рис. 9, состояния A и B являются доступными состояниями, в то время как состояния C и D – недоступные. На рис. 10 доступные состояния закрашены светло-серым цветом. Недоступные состояния изображены темно-серыми.

Рис. 10. Доступные (светло-серые) и недоступные (темно-серые) состояния автомата недоступные состояния. Первым идет состояние C. Случайным образом выбирается состояние из списка доступных состояний (например, состояние B). Выбирается случайным образом переход из состояния B. В качестве примера выберем переход, который соответствует единичному значению входной переменной и ведет в состояние A. Он заменяется на переход, соответствующий такому же значению выходной переменной, и ведет в состояние C. Один из переходов, который ведет из состояния C (для примера возьмем переход, соответствующий единичному значению входной переменной), заменяется аналогичным переходом, ведущим в состояние A.

На рис. 11 показан результат добавления состояния C в список доступных состояний. Серым пунктиром показаны переходы, которые были удалены в результате этой операции. Черным пунктиром обозначены новые переходы. В состояние C автомат попадет из начального состояния A, если на его вход, например, будет подана последовательность значений входной переменной вида 01.

Рис. 11. Добавление состояние C в список доступных состояний После замены переходов состояние C стало доступным. В состояние D можно попасть из состояния C. Следовательно, состояние D также стало доступным.

Действительно, в состояние D можно перейти из начального состояния A, если подать, например, последовательность значений входной переменной вида 0011.

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

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

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

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

2.8.1. Программа для проведения экспериментов на флибах По рассмотренным алгоритмам (известному и предлагаемому) написана программа, окно пользовательского интерфейса которой приведено на рис. 13.

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

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

Приведенные в приложении листинги составляют ядро разработанной программы для предлагаемого подхода.

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

При формировании нового поколения применялся турнирный отбор [21] и элитизм (в новое поколение добавляется одна или несколько лучших особей из предыдущего поколения) [22]. Для формирования новой особи использовался одноточечный оператор скрещивания. Все эксперименты проводились при размере поколения 100 и вероятности применения одноточечного оператора мутации 0,03. Число воздействий среды на флиб выбрано равным 100. Поэтому число правильно предсказанных символов по величине равно точности предсказания символов в процентах. В таблицах с результатами экспериментов, которые приведены ниже, указаны минимальные, максимальные и средние точности предсказания автоматически построенных флибов.

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

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

Эксперимент производился для 400 поколений. Битовая маска, задающая среду, имеет вид – 1111010010111101001. Число состояний флиба – 20.

Графики для первого эксперимента приведены на рис. 14.

Рис. 14. Графики усредненных результатов для первого эксперимента по применению оператора мутации «восстановления связей между состояниями» (пунктир используется Из приведенных графиков видно, что использование алгоритма восстановления связей между состояниями позволяет повысить среднюю эффективность генетического алгоритма.

Результаты первого эксперимента приведены в табл. 6.

Таблица 6. Результаты первого эксперимента по применению оператора мутации «восстановления связей между состояниями»

Эксперимент производился для 400 поколений. Битовая маска, задающая среду, имеет вид – 111101001011110. Число состояний флиба – 10. Отметим, что битовая маска в этом эксперименте короче, чем в предыдущем.

Графики для второго эксперимента приведены на рис. 15.

Рис. 15. Графики усредненных результатов для второго эксперимента по применению оператора мутации «восстановления связей между состояниями» (пунктир используется Результаты второго эксперимента приведены в табл. 7.

Таблица 7. Результаты второго эксперимента по применению алгоритма оператора мутации «восстановления связей между состояниями»

Значения, приведенные в столбце "Усредненный результат", соответствуют крайним правым точкам графиков на рис. 15.

Эксперимент производился для 1600 поколений. Битовая маска, задающая среду, имеет вид – 1010111101100011110111110011001. Число состояний флиба – 30.

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

Графики для третьего эксперимента приведены на рис. 16.

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

Таблица 8. Результаты второго эксперимента по применению оператора мутации «восстановления связей между состояниями»

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

2.9. ИСПОЛЬЗОВАНИЕ АВТОМАТОВ С ФЛАГАМИ

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

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

На рис. 17 изображена структурная схема для автомата без флагов.

Флаговые переменные вместе с входными переменными и текущим состоянием автомата определяют в какое состояние перейдет автомат в следующий момент времени и какие выходные переменные он сформирует. На рис. 18 изображена структурная схема для автомата c флагами.

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

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

На рис. 19 изображен граф переходов для флиба, таблица переходов и выходов для которого приведена в табл. 5.

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

Пусть x и F = (f1, K, fn) – состояние среды и вектор флаговых переменных в текущий момент времени соответственно. Тогда вектор флаговых переменных для F = (f1 = x, f2 = f1, K, fn = fn 1). При программной реализации флаговые переменные можно хранить в массиве. В этом случае переход от F к F осуществляется с помощью удаления последнего элемента массива и вставки в начало массива текущего состояния среды x.

Введение каждой флаговой переменной увеличивает число переходов из каждого состояния флиба вдвое. При n флаговых переменных число переходов из каждого состояния флиба будет равно 2n +1. Номер перехода, который должен использоваться в записанным в двоичном виде числом fn K f2f1x.

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

Таблица 9. Таблица переходов и выходов для флиба с тремя состояниями и одной флаговой переменной Состояние Значение входной переменной s и флаговой переменной f На рис. 20 изображен граф переходов для флиба, таблица переходов которого приведена в табл. 9.

Рис. 20. Граф переходов для флиба с тремя состояниями и одной флаговой переменой В общем случае, входная переменная может принимать произвольное число значений. Пусть существует допустимых комбинации значений входных переменных, и все эти комбинации пронумерованы от 0 до m 1. Тогда при n флаговых переменных число переходов из каждого состояния автомата будет равно mn +1. Номер перехода, который должен использоваться в текущий момент времени, можно вычислить по формуле x + m1f1 + m 2f2 + K + m nfn, где x – номер текущей комбинации значений входных переменных, а F = (f1, K, fn) – вектор флаговых переменных.

Флаговые переменные позволяют существенно уменьшить число состояний в автомате. Рассмотрим эту особенность на простом примере. Пусть требуется построить флиб для простейшей среды, заданной с помощью повторяющейся битовой маски 11100. При использовании обычного автомата потребуются, по крайней мере, три состояния, для того чтобы флиб смог предсказывать изменения среды со сто процентной точностью. Пример такого флиба приведен на рис. 21.

Рис. 21. Граф переходов флиба с одной входной переменной для среды заданной битовой Начальное состояние автомата A. Отметим, что для рассматриваемой маски среды один из переходов в состоянии C не определен.

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

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

При n флаговых переменных число переходов из каждого состояния автомата будет равно m n + 1, где m – число допустимых комбинации значений входных пропорционален числу переходов из каждого состояния. Создание новой особи из двух родительских также выполняется за время пропорциональное числу переходов из каждого состояния автомата. Для того чтобы генетический алгоритм перебирал решения для автоматов с флагами со скоростью не меньшей, чем для автоматов без максимальное число состояний для автомата без флагов.

2.9.1. Эксперименты по использованию автоматов с флагами Эксперименты, описываемые в этом разделе, проводились с помощью генетического алгоритма, решающего задачу о флибах. При формировании нового поколения применялся турнирный отбор [21] и элитизм [22]. Для формирования новой особи использовался одноточечный оператор скрещивания. Все эксперименты проводились при размере поколения 100 и вероятности применения одноточечного оператора мутации 0,03. Число воздействий среды на флиб выбрано равным 100.

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

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

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

Таблица 10. Результаты экспериментов над флибами без флагов с разным числом состояний Число состояний Худший результат Усредненный результат Лучший результат Как видно из таблицы, увеличение числа состояний действительно несколько улучшает точность найденного предсказателя.

Графики для экспериментов над флибами с разным числом состояний приведены на рис. 23. Точками изображен график для результатов эксперимента над флибами с состояниями. Штрихпунктирная линия используется для флибов с 20 состояниями, а пунктирная линия для флибов с 40 состояниями. График для результатов эксперимента над флибами, имеющими 80 состояний, изображен сплошной линией.

Рис. 23. Графики усредненных результатов для экспериментов над флибами без флагов с Основным недостатком увеличения числа состояний является рост объема вычислений и, как следствие, увеличение времени, необходимого для построения предсказателя.

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

Таблица 11. Результаты экспериментов над флибами с разным числом состояний и флагов Графики для экспериментов над флибами с разным числом состояний и флагов приведены на рис. 24. Точками изображен график для результатов эксперимента над флибами с 80 состояниями без флагов. Штрихпунктирная линия используется для флибов с 40 состояниями и одним флагом, а пунктирная линия – флибы с состояниями и двумя флагами. График результатов эксперимента над флибами с состояниями и тремя флагами изображен сплошной линией.

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

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

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

ВЫВОДЫ ПО ГЛАВЕ

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

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

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

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

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

ГЛАВА 3. ГЕНЕРАЦИЯ АВТОМАТОВ ДЛЯ ЗАДАЧИ ОБ УМНОМ МУРАВЬЕ

На тороидальном поле размером 32 на 32 вдоль определенной ломаной линии («тропы») расположено 89 ячеек с едой. Расположение ячеек с едой на «тропе»

фиксировано. На рис. 25 приведено пример «тропы», называемый в литературе «тропой Джона Мьюра» (John Muir Trail) [24], которая образована черными и серыми ячейками. При этом каждая черная ячейка содержит одну единицу еды.

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

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

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

Пример автомата с четырьмя состояниями, моделирующего поведение муравья, построенный в работе [10] эвристически, приведен на рис. 26. Однако муравей с таким поведением задачу не решает, так как за 200 ходов съедает только 42 единицы еды.

Рис. 26. Автомат с четырьмя состояниями, моделирующий поведение умного муравья

3.2. ИЗВЕСТНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ

Конечный автомат, моделирующий поведение муравья, является решением задачи об умном муравье. Чем больше еды съедает муравей за 200 ходов, тем лучше решение (в качестве значения функции приспособленности [10, 24] используется число единиц еды, съеденной муравьем). Автомат задается набором состояний, пронумерованных от нуля. Из каждого состояния выходит две дуги, так как возможно два входных воздействия – ноль и единица. Дуга определяет номер состояния, в которое перейдет автомат, и значение выходной переменной, генерируемой им при переходе (вперед, налево или направо).

Как и в классическом алгоритме из работы [10], в диссертации используется стратегия отбора особей для следующего поколения – отбор отсечением. При использовании такого отбора родительские решения выбираются из группы лучших решений текущего поколения. Размер этой группы решений (порог отсечения) составляет 20% от размера поколения. Все решения из группы лучших решений имеют одинаковые шансы быть выбранными в качестве родительских решений.

Приведем описание предлагаемого генетического алгоритма, использующего отбор отсечением:

1. Текущее поколение решений заполняется случайными решениями.

2. Из текущего поколения решений отбирается группа лучших решений.

3. Формируется новое поколение решений:

a. Создается пустое новое поколение решений.

b. Из группы лучших решений случайным образом выбирается пара c. Формируется новое решение с помощью применения n-точечного оператора скрещивания [24] к двум выбранным решениям.

(n-точечный оператор мутации и новые операторы мутации).

e. Новое решение добавляется в новое поколение решений.

f. Если размер нового поколения меньше размера текущего поколения, 4. Новое поколение становится текущим.

5. Если число созданных поколений меньше заданного пользователем, то переходим к пункту 2.

В данной работе, как и в работе [10], используется n–точечный оператор скрещивания. Приведем описание алгоритма работы этого оператора:

1. В качестве нового решения берется копия первого из выбранных решений.

2. Осуществляется цикл по всем состояниям нового решения. Для каждого a. Выполняется цикл по всем дугам состояния. Для каждой дуги:

i. Случайным образом определяется, требуется ли изменить ii. Случайным образом определяется, требуется ли изменить значение выходной переменной, генерируемое при переходе Для n–точечного оператора скрещивания задается вероятность его применения к каждому элементу автомата.

В данной работе, как и в работе [10], используется n–точечный оператор мутации. Приведем описание алгоритма этого оператора:

1. Осуществляется цикл по всем состояниям автомата:

a. Выполняется цикл по всем дугам переходов в состоянии:

i. Случайным образом определяется необходимость изменение ii. Если требуется изменить индекс состояния, то он изменяется iii. Случайным образом определятся необходимость изменения значения выходной переменной, генерируемой автоматом при iv. Если требуется изменить значение выходной переменной, то Для n–точечного оператора мутации задается вероятность его применения к элементу автомата. В отличие от обычного оператора мутации, такой оператор может изменить сразу несколько элементов в автомате.

3.3. ПРЕДЛОЖЕННЫЕ МОДИФИКАЦИИ АЛГОРИТМА

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

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

Приведем алгоритм реализации нового оператора мутации – сортировка состояний в порядке использования:

1. Создается пустой словарь пар номеров: [«старый номер состояния» – «новый номер состояния»].

2. Моделируется работа автомата. Перед каждым переходом выполняем следующее: если в словаре нет пары, в которой первый элемент равен текущему номеру состояния, то в него добавляется пара [текущий номер состояния – число пар в словаре].

3. Выполняется цикл по всем состояниям автомата. Для каждого состояния:

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

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

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

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

Рис. 27. Граф переходов флиба полученного в процессе работы генетического алгоритма Состояния флиба пронумерованы цифрами от нуля до трех. Начальное состояние нулевое.

Создается пустой словарь пар [«старый номер состояния» – «новый номер состояния»].

Начинается моделирование работы флиба. На вход автомату подается единица.

Автомат переходит в состояние 2 и в словарь добавляется пара [0, 0]. На следующем шаге моделирования автомат переходит в состояние 1, а в словарь добавляется пара [2, 1]. Далее автомат переходит в состояние 2 и в словарь добавляется пара [1, 2]. При переходе из состояния 2 в состояние 0 в словарь ничего не добавляется, так как для состояний 2 в словаре уже есть пара.

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

После моделирования работы флиба словарь пар номеров будет иметь следующий вид:

Осуществляется цикл по всем состояниям. Так как в словаре нет пары только для состояния 3, то в него добавляется пара [3, 3]. Теперь словарь принимает следующий вид:

Осталось изменить порядок состояний и номера состояний в переходах согласно словарю. Состояния 1 и 2 меняются местами и номерами. Граф переходов для флиба, получившегося в результате работы алгоритма, приведен на рис. 28.

Рис. 28. Граф переходов флиба после применения оператора мутации «сортировки состояний в порядке использования» (среда заданна битовой маской 11100) После применения алгоритма сортировки состояний можно построить автомат, имеющий такое же поведение, как и автомат, найденный с помощью классического генетического алгоритма [10], но имеющий меньшее число состояний. Для этого в автомате, состояния которого отсортированы в порядке использования, достаточно удалить все неиспользуемые состояния и заменить переходы в них переходами в начальное состояние.

В нашем случае одно неиспользуемое состояние – 3. В состояние 3 ведет только один переход из состояния 2. Удалим состояние 3 и заменим переход в него на переход в состояние 0. Результат изображен на рис. 29.

Рис. 29. Граф переходов флиба после удаления неиспользуемых состояний (среда заданна Так как при моделировании работы автомата переход из состояния 2, соответствующий значению входной переменной 0, ни разу не выполнялся, то поведение автомата не изменилось.

Оператор мутации «сортировка состояний в порядке использования» приводит к одному виду автоматы с одинаковым поведением, но разной пометкой вершин.

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

Таким образом, использование оператора мутации «сортировка состояний автомата в порядке использования» позволяет сократить пространство поиска, в котором генетический алгоритм перебирает решения.

3.3.2. Оператор мутации «всегда вперед, если впереди еда»

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

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

используемых состояний.

приспособленными будут те муравьи, которые съедают больше еды за 200 ходов.

Однако, если количество съеденной еды одинаково, то предпочтение будет отдаваться автоматам с меньшим числом используемых состояний.

3.4. ОПИСАНИЕ ПРОГРАММЫ ДЛЯ СРАВНЕНИЯ ЭФФЕКТИВНОСТИ ГЕНЕТИЧЕСКИХ

АЛГОРИТМОВ, РЕШАЮЩИХ ЗАДАЧУ ОБ УМНОМ МУРАВЬЕ

В программе, написанной на языке C#, автоматы реализуются с помощью трех классов: StateMachine, State и Branch, которые приведены на диаграмме классов (рис. 31).

В качестве главного класса при реализации автомата применяется класс StateMachine. Классы State и Branch реализуют его состояния и переходы соответственно. В каждом из этих классов имеется метод Clone, предназначенный для создания копий объектов.

Массив States в классе StateMachine содержит состояния автомата.

Свойство CurStateIndex используется для хранения номера текущего состояния автомата в массиве States. Доступ к значению функции приспособленности можно получить с помощью свойства Fitness. Словарь пар номеров [«старый номер состояния» – «новый номер состояния»] (далее словарь используемых состояний) доступен через свойство UsefulStates.

Метод DoStep переводит автомат в новое состояние, изменяет словарь используемых состояний и возвращает значение выходной переменной, генерируемой автоматом. Метод Nulling возвращает автомат в начальное состояние.

В массиве Branches класса State содержатся дуги переходов из данного состояния. Номер элемента в массиве соответствует значению входной переменной.

Переменные StateIndex и Output класса Branch свойства номер состояния, в которое переходит флиб по этой дуге, и значение выходной переменной.

Для реализации стратегий отбора используются классы, изображенные на рис. 32. Эти классы реализуют интерфейс ISelection.

Рис. 32. Диаграмма классов для реализации стратегий отбора В метод Init передаются автоматы текущего поколения, и происходит родительскую особь для скрещивания. Класс TournamentSelection (Листинг 6) реализует турнирный отбор [25], а класс TruncationSelection – стратегия отбора отсечением [24] (Листинг 7).

Для реализации операторов скрещивания используются классы, изображенные на рис. 33. Эти классы реализуют интерфейс ICrossover.

Рис. 33. Диаграмма классов для реализации операторов скрещивания Метод CreateChild создает новый автомата из двух родительских автоматов.

Классы OnePointCrossover и TwoPointCrossover реализуют одноточечный и двухточечный операторы скрещивания. Класс NPointCrossover реализует n– точечный оператор скрещивания (Листинг 8).

Для реализации операторов мутации используются классы, изображенные на рис. 34. Эти классы реализуют интерфейс IMutation.

Рис. 34. Диаграмма классов для реализации операторов мутации Метод Mutate выполняет операцию мутации над переданным в него автоматом.

Классы SimpleMutation и NPointMutation реализуют стандартный и n– точечный операторы мутации [24] (Листинг 9) соответственно.

Для реализации оператора мутации «восстановление связей между состояниями»

используется класс BranchRestorer. Класс StaterSorter реализует оператор мутации «сортировка состояний в порядке использования».

применяется класс ComplexMutation.

Классы, реализующие вычисление значения функции приспособленности, изображены на рис. 35. Эти классы реализуют интерфейс IFitness.

Рис. 35. Диаграмма классов для реализации вычисления значения функции Метод CalculateFitness вычисляет значение функции приспособленности для переданного в него автомата. Класс AntProblem моделирует поведение умного муравья и определяет значение функции приспособленности для него. Класс FlibProblem выполняет ту же функцию для флибов без флагов. Класс FlibWithFlagsProblem реализованных автоматами с флагами.

Основной класс GAEngine, реализующий работу генетического алгоритма, изображен на рис. 36.

Рис. 36. Диаграмма классов для реализации генетического алгоритма Класс GAEngine не зависит от того, какие именно операторы скрещивания, мутации, стратегии отбора и функции приспособленности используются. Такой подход позволяет легко модифицировать генетический алгоритм.

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

Эксперименты проводились на компьютере с процессором AMD Athlon 3800+.

Pages: |

| 2 |

Главная >> Диссертации - все темы

[ СКАЧАТЬ ОРИГИНАЛ ДОКУМЕНТА .pdf ]

Похожие работы:

«vy vy из ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Водопьянова, Лилия Николаевна 1. Управленческий учет валютных операций 1.1. Российская государственная библиотека diss.rsl.ru 2002 Водопьянова, Лилия Николаевна Управленческий учет валютных операций [Электронный ресурс]: Дис.. канд. зкон. наук : 08.00.12 М.: РГБ, 2002 (Из фондов Российской Государственной Библиотеки) Бухгалтерский учет, контроль и анализ хозяйственной деятельности Полный текст: http://diss.rsl.ru/diss/02/0000/020000262.pdf...»

«МАРЫЧЕВ Владимир Владимирович НАУЧНАЯ КАРТИНА МИРА В КУЛЬТУРЕ СОВРЕМЕННОГО ОБЩЕСТВА Диссертация на соискание ученой степени кандидата философских наук Специальность 09.00.13 – Религиоведение, философская антропология, философия культуры Научный руководитель : доктор философских наук, профессор НОВИКОВА О.С. Ставрополь – СОДЕРЖАНИЕ ВВЕДЕНИЕ.. ГЛАВА I. ТЕОРЕТИЧЕСКИЕ И...»

«Сафиуллина Регина Ринатовна ЦИАНОБАКТЕРИАЛЬНО-ВОДОРОСЛЕВЫЕ ЦЕНОЗЫ ЧЕРНОЗЕМА ОБЫКНОВЕННОГО ПОД РАСТЕНИЯМИ-ФИТОМЕЛИОРАНТАМИ В ЗАУРАЛЬЕ РЕСПУБЛИКИ БАШКОРТОСТАН 03.02.13 – Почвоведение 03.02.01 – Ботаника Диссертация на соискание ученой степени кандидата биологических наук Научные...»

«Гусельников Николай Николаевич МОДЕЛИ И МЕТОДЫ УПРАВЛЕНИЯ ИНФРАСТРУКТУРОЙ ПРОМЫШЛЕННОГО ПРЕДПРИЯТИЯ Специальность 08.00.05 – Экономика и управление народным хозяйством: экономика, организация и управление предприятиями, отраслями, комплексами (промышленность)...»

«ХРАМЕНКОВА Анна Владимировна ПОЛУЧЕНИЕ КОМПОЗИЦИОННЫХ И ПОЛИМЕРИММОБИЛИЗОВАННЫХ КАТАЛИТИЧЕСКИ АКТИВНЫХ ОКСИДНЫХ ПОКРЫТИЙ МЕТОДОМ НЕСТАЦИОНАРНОГО ЭЛЕКТРОЛИЗА 05.17.03 – Технология электрохимических процессов и защита от коррозии...»

«КОРОБЕЙНИКОВ АЛЕКСАНДР АЛЕКСАНДРОВИЧ УГОЛОВНАЯ ОТВЕТСТВЕННОСТЬ ЗА ВОСПРЕПЯТСТВОВАНИЕ ОСУЩЕСТВЛЕНИЮ ПРАВОСУДИЯ И ПРОИЗВОДСТВУ ПРЕДВАРИТЕЛЬНОГО РАССЛЕДОВАНИЯ специальность 12.00.08 (уголовное право и криминология; уголовно-исполнительное право) Диссертация на соискание ученой степени кандидата юридических наук Научный руководитель – доктор юридических наук, доцент Р.Э. Оганян Ставрополь-...»

«Соловьева Татьяна Михайловна ИССЛЕДОВАНИЕ И РАЗРАБОТКА ЭФФЕКТИВНЫХ МЕТОДИК ИЗМЕРИТЕЛЬНОГО КОНТРОЛЯ МЕТОДОМ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ 05.11.15 – Метрология и метрологическое обеспечение Диссертация на соискание ученой степени кандидата технических наук...»

«Денисова Марина Николаевна РАЗРАБОТКА ГИДРОТРОПНОГО СПОСОБА ПОЛУЧЕНИЯ ЦЕЛЛЮЛОЗЫ ИЗ НЕДРЕВЕСНОГО РАСТИТЕЛЬНОГО СЫРЬЯ Специальность 05.21.03 – Технология и оборудование химической переработки биомассы дерева; химия древесины Диссертация на соискание ученой степени кандидата технических наук НАУЧНЫЙ РУКОВОДИТЕЛЬ, кандидат...»

«Мозговой Максим Владимирович Машинный семантический анализ русского языка и его применения Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Диссертация на соискание ученой степени кандидата физико-математических наук Научный руководитель — доктор физико-математических наук, профессор Тузов В.А. Санкт-Петербург – 2006 2 Оглавление ОГЛАВЛЕНИЕ ВВЕДЕНИЕ О...»

«Жердев Павел Александрович ПЕРВОНАЧАЛЬНЫЙ ЭТАП РАССЛЕДОВАНИЯ ПРЕСТУПЛЕНИЙ, СВЯЗАННЫХ С ПОДДЕЛКОЙ ИЛИ УНИЧТОЖЕНИЕМ ИДЕНТИФИКАЦИОННОГО НОМЕРА ТРАНСПОРТНОГО СРЕДСТВА В ЦЕЛЯХ ЭКСПЛУАТАЦИИ ИЛИ СБЫТА Специальность 12.00.12 – криминалистика; судебно-экспертная деятельность; оперативно-розыскная деятельность Диссертация на соискание...»

«Самородова Альбина Илдаровна ПОИСК НОВЫХ ПРОИЗВОДНЫХ 1-ЭТИЛКСАНТИНА, ВЛИЯЮЩИХ НА СИСТЕМУ ГЕМОСТАЗА 14.03.06 – Фармакология, клиническая фармакология Диссертация на соискание ученой степени кандидата медицинских наук Научный руководитель : Камилов Феликс Хусаинович Заслуженный деятель...»

«Землянухин Юрий Петрович ЭЛЕКТРОМАГНИТНЫЕ ХАРАКТЕРИСТИКИ КОМПОЗИЦИОННЫХ РАДИОМАТЕРИАЛОВ, АКТИВНО ВЗАИМОДЕЙСТВУЮЩИХ С ЭЛЕКТРОМАГНИТНЫМ ИЗЛУЧЕНИЕМ МИЛЛИМЕТРОВОГО ДИАПАЗОНА 01.04.03 – Радиофизика Диссертация на соискание ученой степени кандидата технических наук Научный руководитель кандидат физ.мат. наук,...»

«ТАВТИЛОВА Наталья Николаевна ПСИХОДИНАМИКА ЛИЧНОСТНОГО РОСТА СОТРУДНИКОВ УГОЛОВНО-ИСПОЛНИТЕЛЬНОЙ СИСТЕМЫ, СОСТОЯЩИХ В РЕЗЕРВЕ КАДРОВ НА ВЫДВИЖЕНИЕ Специальность 19.00.06 – юридическая психология ДИССЕРТАЦИЯ на соискание ученой степени кандидата психологических наук Научный руководитель : доктор психологических наук, профессор Сочивко Дмитрий Владиславович Рязань – ОГЛАВЛЕНИЕ Введение.. Глава 1....»

«Моторина Наталья Валерьевна Лингвокультурные скрипты традиционного коммуникативного поведения в России и Англии 10.02.20 – сравнительно-историческое, типологическое и сопоставительное языкознание Диссертация на соискание ученой степени кандидата филологических наук Научный руководитель : доктор филологических...»

«ИЗ ФОНДОВ РОССИЙСКОЙ ГОСУДАРСТВЕННОЙ БИБЛИОТЕКИ Горюнова, Екатерина Александровна Метод контроля загрязнения придорожных сельскохозяйственных земель отработавшими газами двигателей внутреннего сгорания Москва Российская государственная библиотека diss.rsl.ru 2006 Горюнова, Екатерина Александровна Метод контроля загрязнения придорожных сельскохозяйственных земель отработавшими газами двигателей внутреннего сгорания : [Электронный ресурс] : На примере Брянской области : Дис. . канд. техн. наук :...»

«Цыплакова Елена Германовна ПРИБОРЫ И МЕТОДЫ КОНТРОЛЯ И МОНИТОРИНГА ВОЗДЕЙСТВИЯ АВТОТРАНСПОРТА НА АТМОСФЕРНЫЙ ВОЗДУХ СЕВЕРНЫХ ГОРОДОВ Специальность 05.11.13 – Приборы и методы контроля природной среды, веществ, материалов и изделий Диссертация на соискание ученой степени...»

« ГРАНОВСКАЯ АНТОНИНА ВАСИЛЬЕВНА РАЗВИТИЕ КОММУНИКАТИВНОЙ КОМПЕТЕНТНОСТИ РУКОВОДИТЕЛЕЙ САМОДЕЯТЕЛЬ НЫ Х ТВОРЧЕСКИХ ОБ ЪЕДИНЕНИЙ В УЧРЕЖДЕНИЯХ КУЛЬ ТУРЫ 13.00.05 теория методика и организация социальнокультурной деятельности ДИССЕРТАЦИЯ на соискание ученой степени кандидата педагогических наук Научный руководитель: кандидат педагогических наук, профессор Мацукевич О.Ю. Москва 2 СОДЕРЖАНИЕ ...»

«Горбунов Сергей Андреевич ОБОСНОВАНИЕ ПАРАМЕТРОВ И РАЗРАБОТКА ВЫСОКОНАГРУЖЕННЫХ, АДАПТИВНЫХ, РАДИАЛЬНОВИХРЕВЫХ ПРЯМОТОЧНЫХ ВЕНТИЛЯТОРОВ МЕСТНОГО ПРОВЕТРИВАНИЯ Специальность 05.05.06 – Горные машины Диссертация на соискание учёной степени кандидата технических наук Научный руководитель – доктор технических наук Макаров Владимир Николаевич Екатеринбург – 2014 2 СОДЕРЖАНИЕ ВВЕДЕНИЕ.. 1. Анализ состояния, проблемы и критерии...»

«Фи Хонг Тхинь ОЦЕНКА И ПРОГНОЗ ОСЕДАНИЯ ЗЕМНОЙ ПОВЕРХНОСТИ В РЕЗУЛЬТАТЕ ИЗВЛЕЧЕНИЯ ПОДЗЕМНЫХ ВОД НА ТЕРРИТОРИИ Г. ХАНОЙ (ВЬЕТНАМ) 25.00.08 – Инженерная геология, мерзлотоведение и грунтоведение Диссертация на соискание ученой степени кандидата геолого-минералогических наук Научный руководитель : доктор...»

«УСТИЧ Дмитрий Петрович ФОРМИРОВАНИЕ СИСТЕМЫ МОНИТОРИНГА ИННОВАЦИОННОЙ АКТИВНОСТИ НА КРУПНЫХ РОССИЙСКИХ ПРЕДПРИЯТИЯХ Специальность: 08.00.05 – Экономика и управление народным хозяйством (управление инновациями) Диссертация на соискание ученой степени кандидата...»

наверх

<< ГЛАВНАЯ | КОНТАКТЫ

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА (Авторефераты, диссертации, методички, учебные программы, монографии)

«Использование генетических алгоритмов для генерации конечных автоматов ...»

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ОБЗОР ЗАДАЧ, В КОТОРЫХ ГЕНЕРАЦИЯ КОНЕЧНЫХ

АВТОМАТОВ ОСУЩЕСТВЛЯЕТСЯ С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ

АЛГОРИТМОВ

1.5. РАСПОЗНАВАНИЕ НЕРЕГУЛЯРНЫХ ЯЗЫКОВ

1.6. ПРОЕКТИРОВАНИЕ ЛОГИЧЕСКИХ СХЕМ ДЛЯ АВТОМАТОВ МИЛИ

1.7. ОБЗОР МЕТОДОВ ГЕНЕРАЦИИ АВТОМАТОВ С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ

АЛГОРИТМОВ

ВЫВОДЫ ПО ГЛАВЕ

ГЛАВА 2. ГЕНЕРАЦИЯ АВТОМАТОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ О

ФЛИБАХ

2.2. СХЕМЫ РАБОТЫ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ В ЗАДАЧЕ О ФЛИБАХ

2.4. ГЕНЕРАТОР ЗНАЧЕНИЙ ВХОДНОЙ ПЕРЕМЕННОЙ

2.6. ОПЕРАТОР ОДНОТОЧЕЧНОГО СКРЕЩИВАНИЯ

2.8. АЛГОРИТМ ВОССТАНОВЛЕНИЯ СВЯЗЕЙ МЕЖДУ СОСТОЯНИЯМИ

2.9. ИСПОЛЬЗОВАНИЕ АВТОМАТОВ С ФЛАГАМИ

ВЫВОДЫ ПО ГЛАВЕ

ГЛАВА 3. ГЕНЕРАЦИЯ АВТОМАТОВ ДЛЯ ЗАДАЧИ ОБ УМНОМ МУРАВЬЕ

3.2. ИЗВЕСТНЫЙ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ

3.3. ПРЕДЛОЖЕННЫЕ МОДИФИКАЦИИ АЛГОРИТМА

3.4. ОПИСАНИЕ ПРОГРАММЫ ДЛЯ СРАВНЕНИЯ ЭФФЕКТИВНОСТИ ГЕНЕТИЧЕСКИХ

АЛГОРИТМОВ, РЕШАЮЩИХ ЗАДАЧУ ОБ УМНОМ МУРАВЬЕ

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)