Подходят ли генетические алгоритмы для решения таких задач, как проблема Кнута?
Все мы знаем, что генетические алгоритмы могут дать оптимальное или почти оптимальное решение. Таким образом, в некоторых задачах, таких как NP-сложные, с компромиссом между временем и оптимальным решением, почти оптимальное решение является достаточно хорошим.
Поскольку нет гарантии нахождения оптимального решения, считается ли GA хорошим выбором для решения проблемы Кнута?
Согласно «Искусственный интеллект: современный подход» (третье издание), раздел 3.2 (стр. 73):
Кнут предположил, что, начиная с числа 4, последовательность операций факториала, извлечения квадратного корня и минимума приведет к любому желаемому положительному целому числу.
Например, 5 можно набрать из 4:
этаж (sqrt (sqrt (sqrt (sqrt (sqrt ((4!)!))))))
Итак, если у нас есть число (5), и мы хотим знать последовательность операций трех упомянутых, чтобы достичь заданного числа, каждый ген хромосомы будет числом, которое представляет определенную операцию с дополнительным числом для (нет операции), а функция приспособленности будет абсолютной разницей между заданным числом и числом, которое мы получаем в результате применения операций в определенном порядке для каждой хромосомы (до min). Предположим, что количество итераций (поколений) выполнено без оптимального решения, а ближайшее число, которое у нас есть, равно 4 (с пригодностью 1), проблема в том, что мы можем получить 4, не применяя никаких операций к 4, в то время как для 5 нам нужно много операций, поэтому почти оптимальное решение даже близко не к этому решению.
Итак, не подходит ли GA для такого рода задач? Или предполагаемое представление хромосом и функция приспособленности недостаточно хороши?
Ответы
Прежде чем попытаться ответить на ваш вопрос более прямо, позвольте мне кое-что прояснить.
Люди часто используют термин генетические алгоритмы (ГА), но во многих случаях на самом деле они имеют в виду эволюционные алгоритмы (ЭА), которые представляют собой совокупность популяционных (т. Е. Несколько решений поддерживаются одновременно) алгоритмов оптимизации и подходы, вдохновленные дарвинизмом и выживанием сильнейших . ГА - один из таких подходов, при котором хромосомы бинарны, и у вас есть как мутация, так и операция кроссинговера. Есть и другие подходы, такие как стратегии эволюции или генетическое программирование .
Как вы также заметили, советники - это метаэвристики, и, хотя есть некоторые исследования их свойств сходимости [ 1 ], на практике они могут не сходиться. Однако, когда любой другой потенциальный подход не работает, советники могут быть определенно полезны.
В вашем случае проблема действительно заключается в том, чтобы найти замкнутое (или аналитическое ) выражение функции, которое состоит из других более мелких функций. Именно для этого и было создано генетическое программирование (в частности, древовидный ГП). Фактически, проблема Кнута является частным случаем проблемы символической регрессии , которая является типичной проблемой, к которой применяется GP. Итак, GP - это, вероятно, первый подход, который вам стоит попробовать.
Тем временем я реализовал в DEAP простую программу, которая пытается решить проблему Кнута. Проверить это здесь . Пригодность лучшего решения, которое он нашел до сих пор (с некоторым начальным значением), составляет 4, а решение floor(sqrt(float(sqrt(4))))(здесь floatпросто преобразует ввод в число с плавающей запятой, чтобы обеспечить безопасность типа). Я использовал разницу как функцию пригодности и запустил алгоритм GP для 100 поколений по 100 человек для каждого поколения (что не так уж много!). Я не особо настраивал гиперпараметры, так что, возможно, с правильным начальным значением и гиперпараметрами вы сможете найти правильное решение.
Чтобы решить ваши проблемы, в принципе, вы можете использовать эту кодировку, но, как вы заметили, GA действительно может вернуть $4$ как лучшее решение (что на самом деле не так уж далеко от $5$), и вы могли бы избежать моего убийства в каждом поколении любых людей, обладающих именно такой ценностью.
Я не тратил слишком много времени на свою реализацию и обдумывал эту проблему, но, как я сказал выше, даже при генетическом программировании и использовании только операций Кнута это могло застрять в локальных оптимумах. Вы можете попробовать дополнить мою (или вашу) реализацию другими операциями, такими как умножение и сложение, и посмотреть, улучшится ли что-то.