УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»



Главная

Новости
 Новости науки
 Важное
 Почетные доктора
 Инновации
 Культура
 Люди
 Разное
 Скартел-Yota
 Стрим
 Смольный
Учебный процесс
 Образование
 Дипломы
 Курсовые проекты
 Лабораторные работы
 Учебные курсы
 Визуализаторы
 Unimod-проекты
 Семинары
 Стипендии
Наука
 События и факты
 Госконтракты
 Статьи
 Диссертации
 Книги
 Презентации
 Свидетельства
 Сотрудничество
Исследования
 Автоматы
 Верификация
 Геном
 Искусственный интеллект
 Генетические алгоритмы
 Движение
 UniMod
 Роботы и агенты
 Нейронные сети
 ФЦП ИТМО-Аалто
 Разное

О нас
 Премии
 Сертификаты и дипломы
 Соревнования по программированию
 Прорыв
 Автографы
 Рецензии

Беллетристика
 Мотивация
 Мысли
Медиа
 Видео
 Фотографии
 Аудио
 Интервью

English
 Home

 Articles
 Posters
 Automata-Based Programming
 Initiatives
 Projects
 Presentations
 UniMod
 UniMod Projects
 Visualizers


Поиск по сайту

Яndex



   Главная / Статьи / Использование генетических алгоритмов для автоматического построения конечного автомата в задаче о «флибах» (версия для печати)


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



П.Г. Лобанов, А.А. Шалыто (СПбГУ ИТМО, Санкт-Петербург)

Статья в формате PDF
Исполняемая программа
Исходные тексты

Аннотация

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

В работе Воронина  О., Дьюдни  А. Дарвинизм в программировании //Мой компьютер. 2004. № 35 для решения указанной задачи используется один из генетических алгоритмов. При этом построенный автомат правильно предсказывает относительно небольшое число символов. Это во многом связано с подходом, используемым при построении следующего поколения (худший предсказатель в поколении заменяется на результат скрещивания лучшего предсказателя со случайно выбранным флибом). Цель настоящей работы — разработка подхода, устраняющего указанный недостаток. Для этого авторами применяется другой метод генерации нового поколения. Он основан на турнирном отборе и принципе элитизма. Дополнительная оптимизация достигается благодаря применению алгоритма восстановления связей между состояниями автомата.

Используемый в работе подход позволяет построить при одинаковом числе поколений лучший предсказатель, чем известный метод. Так, например, лучший флиб, полученный известным методом, после 400 поколений (при размере одного поколения 200), в среднем правильно предсказывает 81 символ из 100 для среды, изменения которой задаются битовой маской, представленной в виде: 1111010010111101001. При аналогичных условиях, лучший флиб, полученный в настоящей работе, в среднем правильно предсказывает 94 символа из 100.




© 2002—2017 По техническим вопросам сайта: vl.ulyantsev@gmail.com