Фомин Максим Александрович

Государственный университет информатики и искусственного интеллекта

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

 

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

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

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

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

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

{,,,, … ,}, где m – количество состояний в автомате. Переменная  показывает, по какому входному параметру будет осуществлен переход из состояния L в состояние К. Переменная Y - результат перехода. Геном хромосомы может быть любое состояние, которое может принять окружающая среда.

Мутация будет представлена в виде обмена местами двух пар ХY исходящих из одного состояния. Будет использоваться N-точечный кроссинговер.

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

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

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

3.                  Текущий переход заменяется на переход, ведущий в недоступное состояние.

На вход автомата будет подаваться ряд:

{x₁,x₂,…x_n}, где n – разрядность входного ряда. На выходе мы получим ряд с разрядностью n-1. Фитнес функция формируется путем парного сравнения элементов выходного ряда и части элементов входного (начиная со 2-го элемента). При совпадении  элементов наращивается счетчик. Значение счетчика должно стремиться к n-1.

Новизна данного метода:

-       измененный вид хромосомы занимает меньшее количество памяти и позволит уменьшить количество операций при расчетах;

-       предложен новый алгоритм восстановления недоступного состояния.

Выводы: в рамках работы был оптимизирован генетический алгоритм для генерации конечного автомата Мили. Были предложены нововведения наличие которых обеспечит лучшее качество работы алгоритма.

 

Используемые источники:

1. http://is.ifmo.ru/disser/lobanov_autoref.pdf

2. http://ru.wikipedia.org/wiki/Генетический_алгоритм

3. http://ru.wikipedia.org/wiki/Конечный_автомат

4. http://www.studcode.ru/archiv/ponyatie-o-geneticheskix-algoritmax/