Откопал такую задачку:
Искусственный муравей (Artificial Ant). Представляет чрезвычайно сложную задачу15
для
генетического программирования. В данной задаче необходимо найти простой алгоритм
управления роботом-муравьем, который находит и съедает наибольшее количество пищи за
400 тактов модельного времени16
. Муравей может двигаться вперед, поворачивать налево и
направо. Если во время движения он проходит через ячейку с пищей, то он съедает ее.
Муравей также может «почуять», есть ли в клетке перед ним пища. Решетка с миром, в
котором живет искусственный муравей показана на рис. 69. След ячеек с пищей известен как
«След Санта Фе». Мир тороидальный: выход за границы приводит к появлению муравья с
противоположной стороны.
Особь искусственного муравья состоит из одного дерева. Оценка приспособленности
производится следующим образом. Муравей начинает путь с левого верхнего угла и
повернут направо. Затем начинается исполнение дерева: при активации узла движения или
сенсора, муравей соответственно двигается или чувствует. Когда исполнение дерева
заканчивается, оно начинает исполняться с самого начала. Каждое движение занимает 1 такт
времени. Оценка заканчивается, когда муравей съел всю пищу в мире, либо когда
закончилось 400 шагов. Приспособленность равна количеству съеденной пищи.
Задача искусственного муравья отличается от задачи символьной регрессии и булевских
задач тем, что сами значения на выходах узлов дерева игнорируются. Единственно важным
является то, как влияет действие узла на сам мир, т.е. побочный эффект от активации узла:
движение муравья, поворот и т.д. Это означает, что для искусственного муравья порядок
исполнения узлов определяет действия особи, в то время как для предыдущих задач
очередность исполнения узлов дерева не играла особой роли. Пример решения (очень
компактного) для задачи искусственного муравья: (progn3 (if-food-ahead move
(progn2 left (progn2 (progn3 right right right) (if-food-ahead
move right)))) move right).
Простой
