Построение управляющих автоматов с помощью генетических алгоритмов (лабораторная работа)

Введение
1. Постановка задачи
1.1. Задача об "умном муравье"
В задаче рассматривается фиксированное поле 32 на 32 клетки (рис.1), расположенное на поверхности тора. Большая часть клеток пуста, остальные 89 содержат пищу. Имеется агент-муравей, способный видеть, есть ли перед ним пища. Он начинает движение с клетки, помеченной как старт и может совершать следующие действия:
- повернуть налево
- повернуть направо
- сделать шаг вперед, и если в новой клетке есть пища, съесть ее
- ничего не делать
Максимальное число ходов - 200.
Муравей должен съесть как можно больше пищи, совершив при этом как можно меньше ходов.
В данной лабораторной работе эта задача решается путем построения с помощью генетических алгоритмов конечного автомата, управляющего действиями муравья. При этом желательно минимизировать число состояний этого автомата.
1.2. Конечный автомат Мура
2. Реализация
2.1. Функция приспособленности
2.2. Метод мутации
2.3. Метод скрещивания
2.4. Генарация нового поколения
3. Резусльтаты работы
3.1. Граф переходов
3.2. Графики максимального и среднего значения функции приспособленности
Заключение
Источники

12 страниц PDF

Предварительный просмотр