Путешествие на шахматном коне - это проблема, которую веками изучали как шахматисты, так и математики. Предлагается маршрут лошади с характерным прыжком таким образом, чтобы он проходил через все квадраты на доске (64 квадрата, 8 × 8), касаясь каждого из них только один раз.
Первые данные по этой проблеме были найдены в арабской рукописи 840 года (Мюррей, 1913), где были подробно описаны два маршрута. Первый математический анализ был представлен Леонардом Эйлером в Берлине (1759 г.). Другими известными математиками, которые занимались этим, были Тейлор, де Мойр и Лагранж.
Ближе к нашему времени Маккей и Мордеки использовали мощные мэйнфреймы в поисках наиболее возможных маршрутов на доске 8 × 8. Маккей рассчитал общее количество закрытых маршрутов (когда лошадь завершает круг, следующий прыжок приводит его к стартовой клетке) в
13,267,364,410,532, а Мордецкий нашел
1305 × 10 35 открытых маршрутов.
Что касается поисковых систем, то они варьируются от чисто эвристических систем (Warnsdorff 1823), поиска в глубину и обратного отслеживания, нейронных сетей, генетических алгоритмов, алгоритмов муравьиных колоний и т. Д.
Для разрешения этой работы, генетический алгоритм, основанный на разработанном
Чу-Бизли
Генетические алгоритмы
Генетические алгоритмы (AG) - это методы, используемые для решения задач поиска и оптимизации. Они основаны на эволюции популяций в природе, в соответствии с принципами естественного отбора и выживания наиболее приспособленных, постулированных Чарльзом Дарвином (1859).
Подражая этим адаптивным процессам, AG могут генерировать решения для реальных проблем. Путем адекватного кодирования начальной популяции ГА и правильной реализации эволюционных методов можно достичь оптимальных решений.
Основные принципы ГА были установлены Голландией в 1975 году, но эта техника стала популярной только в середине 1980-х годов, особенно благодаря работе Гольдберга (1989).
В природе люди борются за ресурсы выживания, а также за воспроизводство. Те, кто имеет наилучшие условия для выживания и привлечения партнеров, имеют больше шансов родить потомков. Наоборот, у наименее одаренных будет мало шансов на размножение. Характеристики наиболее адаптированных унаследованы их детьми, которые получают комбинацию лучших генов от своих родителей и, таким образом, развиваются, достигая большей адаптации к среде, в которой они живут.
AG работают аналогично естественной системе. У них есть совокупность людей, где каждый является потенциальным решением данной проблемы. Каждый из этих людей будет обладать способностью или адаптационной ценностью, связанной с тем, насколько близко или далеко он находится от достижения такого решения.
Аналогично природе, эти люди смогут скрещиваться и создавать потомков, которые получат лучших из своих предков, и, таким образом, по мере того, как будут проходить поколения, они будут стремиться к оптимальному решению проблемы.
Типичный GA использует упрощенные понятия отбора, кроссовера, мутации и выживания наиболее приспособленных, так что, имея относительно мало знаний о методах решения проблемы, вы также можете найти решение.
В тех областях, где существуют конкретные методы для конкретных решений, они всегда будут работать лучше, чем AG. Идея использования этих алгоритмов заключается в поиске в полях без ограниченного решения, или, если это решение существует, его можно улучшить, комбинируя его с использованием AG.
AG используются в самых разных областях, таких как: численная и комбинаторная оптимизация, машинное обучение, автоматическое программирование, экономика, иммунные системы, экология, эволюция и обучение, социальные системы и т. Д.
Структура и функционирование генетического алгоритма
Simple AG (например, созданный Голландией и один из наиболее часто используемых) состоит из группы индивидуумов, также называемых хромосомами. Каждая хромосома представляет возможное решение предложенной проблемы и состоит из ряда значений, которые могут быть {0,1}, целые числа, вещественные числа и т. Д. Эти значения соответствуют каждому из генов, которые составляют хромосому. Возможное графическое представление следующее:
У AG также есть генетические операторы, которые осуществляют процессы отбора, скрещивания и мутации. Поскольку эти три оператора являются наиболее распространенными и базовыми, в некоторые специализированные AG включаются операторы улучшения осуществимости, повышения оптимальности и т. Д.
Генетический алгоритм Чу-Бизли
Как указывалось выше, Чу-Бизли GA был использован для этой работы. Наиболее важные отличия от простых AG:
- В популяции не может быть равных хромосом. В простых ГА все или почти все население заменяется в каждом поколении. В Chu-Beasley заменяется только один человек, при условии, что у нового есть желаемые характеристики разнообразия, осуществимости и т. Д. Он включает в себя оператора улучшения оптимальности.
Адаптация ГА к проблеме шахматного коня
В зависимости от квадрата, в котором она находится, лошадь может иметь от двух до восьми законных ходов, которые можно кодировать различными способами. В этой работе была решена кодировка с целыми числами:
Таким образом, неполный заезд может быть представлен целочисленной полосой, подобной этой:
4 - 6 - 0 - 0 - 2 - 4…
Если мы возьмем начальную точку, такую как e4 (центр доски), и представим этот путь в алгебраической записи, мы получим:
(e4) - f6 - h5 - g3 - f1 - d2 - e4
Обратите внимание, что последнее движение переносит нас в ранее посещенное место (e4), делая этот маршрут незаконным. Поэтому можно сказать, что этот маршрут имеет действительную длину в пять прыжков. Это количество прыжков - это то, что мы называем фитнес-функцией человека. Для этой проблемы пригодная функция из 63 легальных прыжков является правильным решением. Возвращаясь к сходству с природой, индивид или хромосома более или менее уместны в зависимости от того, больше или меньше число их фитнес-функций. Чем больше функция способностей, тем ближе вы будете к решению проблемы: завершите путешествие лошади по шахматной доске.
Реализация генетического алгоритма
Было решено создать начальную популяцию из 64 особей или хромосом (последующие тесты подтвердили, что это наиболее подходящее число). Каждый из генов в этих хромосомах был дополнен случайным числом от 0 до 7. Единственное начальное ограничение, которое было принято было то, что прыжок с квадрата х не снял лошадь с доски.
С созданием начальной популяции начинается цикл или поколение, которое можно упростить следующим образом:
- Выбор предшественника Скрещивание предшественника и генерация детской мутации ребенка Улучшение адаптивности включения ребенка (возможно) в популяцию ребенка
Выбор родителей
Есть несколько способов выбора родителей, которые будут генерировать потомков населения. Наиболее используемыми являются:
- Элитная рулетка или рейтинг турниров Монте-Карло
В этой работе были проведены эксперименты по выбору Торнео, Элитисты и Монте-Карло, которые, как мы увидим позже, дали самые лучшие результаты.
Выбор по турниру
Две пары кандидатов в прародители (хромосомы) выбираются случайным образом из популяции. Из каждой пары выбирается хромосома, которая имеет наилучшую фитнес-функцию, и крест получается из двух выбранных.
Элитарный Выбор
Две лучшие хромосомы всегда берутся из популяции, и между ними происходит скрещивание, чтобы родить ребенка.
Монте-Карло или рулетка
С этим методом вероятность, что человек должен воспроизвести, пропорциональна разнице между его способностями и способностями его конкурентов. Это может быть представлено как игра в рулетку, где каждый игрок получает секцию или часть рулетки, но наиболее подходящие получают большие секции, чем наименее подходящие. Затем рулетка вращается (число выбирается случайным образом), и каждый раз выбирается тот, у кого есть секция, в которой останавливается рулетка.
Запустив рулетку дважды, два родителя выбираются для пересечения.
Родительский переход
Генное скрещивание происходит с двумя отобранными хромосомами, из которых будут рождены два ребенка. Только самые приспособленные из этих детей могут войти в население.
Так же, как существуют различные методы выбора, это также происходит с пересечением. В этой работе были проверены операторы пересечения по одной точке и двум точкам, в результате чего пересечение с одной точкой было наиболее успешным. Его реализация заключается в следующем:
Как только два родителя были выбраны, их хромосомы обрезаются в случайно выбранной точке. При этом в каждой хромосоме генерируются два разных сегмента: голова и хвост. Затем гены хвостов обмениваются между каждым человеком, и таким образом создаются два ребенка, которые наследуют характеристики от обоих родителей. Наконец, только ребенок с наилучшей функцией способностей будет иметь возможность попасть в группу.
Мутация Сына
Мутация сына приводит к тому, что некоторые из его генов, обычно только один, изменяют свою ценность случайным образом. Таким образом, поведение, которое происходит в природе, имитируется, поскольку, когда рождаются потомки, обычно происходит некоторый тип ошибки, обычно без существенного значения, при передаче генетической нагрузки от родителей к детям. Обычно вероятность мутации очень низкая, менее 1%. Тем не менее, тесты в этой работе имели лучшие результаты с мутацией, близкой к 85%.
Наиболее широко используемые операторы генетической мутации - это случайная замена и замена двух генов в хромосоме.
В настоящей работе есть вероятность, что любой из двух операторов может быть применен в мутации.
Улучшение адаптируемости детей
Этот момент более чем важен в AG. Испытания, проведенные несколькими авторами (а также в настоящей работе) с простыми ГА, не дали результатов при поиске действительных маршрутов для шахматной лошади. Чтобы улучшить функционирование AGs, были реализованы различные методы, которые частично специализируют процесс. Эта идея адаптивности была исследована Уитли (1994)
Гордон и Слокум (2004) представили методику ремонта, которая будет объяснена ниже. Другой специализацией были Al-Gharaibeh, Qqwagneh и Al-zahawi (2007), которые улучшили адаптивность потомства с помощью эвристики.
Идея Гордона и Слокума заключалась в следующем: для каждой хромосомы в популяции, в точке, где прыжок недопустим (то есть, он снимает лошадь с доски или на ранее посещенный квадрат), применяется ремонт. Этот ход рассматривается, и делается попытка заменить его другим действительным ходом, который позволяет продолжить путешествие. Если нет достоверного скачка, оценка этой хромосомы прекращается. В случае допустимого прыжка недействительный ген модифицируется этим прыжком и передается гену, который следует справа. Это продолжается до тех пор, пока не появится квадрат без возможных прыжков или пока не будет найдено решение пути лошади. Эвристика или возврат не применяются, как с другими методами.
В представленном выше примере оценка хромосомы закончилась, когда лошадь отскочила назад к клетке e4. То есть цепочка генов:
4 - 6 - 0 - 0 - 2 - 4…
(e4) - f6 - h5 - g3 - f1 - d2 - e4, где последнее значение (4) недействительно.
Процесс восстановления пытается найти правильное значение для этого гена, скажем, значение 7, которое уберет нас с поля. Затем мы ищем другое значение, например 3, которое приведет нас к c4, который является блоком, еще не посещенным. Тогда генная цепь останется
4 - 6 - 0 - 0 - 2 - 3…
(e4) - f6 - h5 - g3 - f1 - d2 - c4
и мы поступим таким же образом со следующим геном справа от цепи.
Разница между настоящей работой и работой Гордона и Слокума заключается в том, что они применяют репарацию ко всему населению, тогда как в нашей Chu-Beasley AG мы работаем только над вновь созданным сыном.
Включение Сына в Население
Как только ребенок получен и улучшен, вычисляется его фитнес-функция, то есть сколько действительных скачков имеет его генная цепь. Эта функция сравнивается с каждым из членов текущего населения. Если физическая функция лучше, чем у худшего члена населения, этот человек исключается и заменяется нынешним ребенком. Всегда уважая разнообразие: что ребенок не равен ни одному из членов, присутствующих в популяции.
Если в популяции уже существует хромосома с теми же генами, что и у текущего ребенка, или если этот ребенок не лучше худшего из индивидов, то ее отбрасывают, и предполагается, что в этом поколении не было потомства.
Полученные результаты
Для работы использовался язык C # вместе с платформой A-Forge.Net, отличным бесплатным продуктом с открытым исходным кодом, ориентированным на искусственный интеллект и позволяющим сократить время разработки.
Мы попытались провести процесс тестирования, аналогичный предыдущим исследованиям, но поскольку Chu-Beasley - это другой AG, одни и те же параметры использовать нельзя. Наконец, была создана начальная популяция из 64 хромосом, и для каждого квадрата на доске было сделано 1 000 000 поколений. Процесс был повторен пять раз для каждой коробки, чтобы получить средние значения, сопоставимые с другими предложениями. Результаты можно увидеть в следующей таблице:
Три метода отбора позволили найти хотя бы один раз поездку в первом поколении. Это благодаря механизму ремонта.
Примечательно, что в то время как AG Гордона и Slocum обнаружили наибольшее количество прогонов в отдельном квадрате (642 против 529), наш AG признал более высокое среднее значение почти в каждом квадрате на доске.
С другой стороны, не было тестов, дающих отрицательный результат, то есть GA всегда находил действительные маршруты в каждом тесте.
Средние значения в пяти тестах.
Ссылки:
- Мюррей HJR (1913) История шахмат Б.Д. Маккей, «Рыцарские туры по шахматной доске 8 × 8», канд. диссертация, факультет компьютерных наук, Австралийский национальный университет, 1997 год. Мордеки, «О количестве экскурсий рыцаря», в Prepublicaciones de Matematica de la Republica, Уругвай, 2001/57, 2001. Бисли, JE E CHU, PC A Генетический алгоритм для обобщенной задачи присваивания. Компьютерные исследования операций, 24 (1), стр. 17-23, 1997. Холланд Дж. Адаптация в естественных и искусственных системах, 1-е изд., Университет Мичигана, 1975. 2-е изд. 1992 г., издательство MIT Press, Голдберг Д., Генетические алгоритмы в поиске, оптимизации и машинном обучении. Аддисон-Уэсли, 1989 г. Уитли Д., Гордон В.С. и Матиас К. Эволюция Ламаркина, эффект Болдуина и оптимизация функций. Параллельное пробное решение с натуры 3, Израиль, с. 6-15, 1994
- Гордон В.С. и Слокум Т.Дж. (2004) Рыцарский тур - Эволюционный против Поиск в глубину. В трудах Конгресса эволюционных вычислений 2004 (CEC'04), Портленд, штат Орегон, с. 1435-1440
- Al-Gharaibeh, Z. Qawagneh и H. Al-zahawi, «Генетические алгоритмы с эвристикой - проблема путешествия Найта», в Proc. Международной конференции по генетическим и эволюционным методам, 2007, с. 177-81.A-Forge.Net
