05.02.2014

Как заставить муравьев решать шахматные задачи

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

Можете ли вы сделать 63 правильных хода так, чтобы единожды посетить каждую клетку на доске? Напомним, что конь ходит так: две клетки, поворот на 90 градусов и еще одна клетка. Это может показаться сложной задачей, но на самом деле последовательность передвижений под названием "ход конем" можно совершить несметным количеством вариантов.

Если вам удастся сделать 63 хода и закончить на той клетке, с которой вы можете совершить последний — 64 — правильный ход и оказаться на исходном месте, то вы пройдете так называемый замкнутый маршрут. Остальные варианты называются открытые маршруты.

Математики задумались над тем, сколько существует замкнутых маршрутов, и в итоге они получили поразительную цифру: 26 триллионов. А открытых маршрутов есть столько, что точное количество мы даже и не знаем.

Исследователь Филип Хингстон настолько заинтересовался задачей хода коня, что взялся за поиски альтернативного решения. И стимул он обнаружил в природе, а именно: среди муравьев.

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

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

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

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

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

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

Используя алгоритм, удалось найти почти полмиллиона маршрутов. Это оказалось значительным шагом вперед в сравнении с ранней работой, основывавшейся на генетическом алгоритме. Он имитирует дарвиновский принцип естественного отбора – выживают сильнейшие. Более приспособленные особи (которые лучше справляются с поставленной задачей) из симулированной популяции выживают, тогда как более слабые вымирают.

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

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

Источники:

1. facepla.net