Комментарии 14
Спасибо за статью, сам собирал кубик и также разочаровался. Теперь поподробнее изучу генетические алгоритмы — тут у меня яма.
Топовый пример занятия для прожига времени — называется Speed Stacking.
Топовый пример занятия для прожига времени — называется Speed Stacking.
Крутая статья, очень просто и на пальцах объясняет, зачем и для чего нужны генетические алгоритмы. Надо бы самому что-то такое намутить.
A* должен катить. Только опять же все будет зависеть от хорошей «допустимой эвристической оценки» (admissible/consistent heuristics). Не всякая функция оценки катит для поиска! Но если поэкспериментировать и найти хорошую, то может очень сильно ускорить. Вот в курсе по AI на edX. В этом же курсе есть еще несколько «атак» на «сложные переборные поиски»
Так ведь результат эволюции у вас получается просто набор команд для решения одного кубика. Это вовсе не то для чего существуют металгоритмы в стиле генетического. Вы должны были бы поставить задачу вот так: генетическим способом найти функцию которая собирает любой кубик. Результатом работы метаалгоритма является алгоритм а не одиночное решение.
На самом деле вы просто сделали алгоритм А*-поиска.
На самом деле вы просто сделали алгоритм А*-поиска.
Мне было интересно применить генетический алгоритм в данной задаче — и я его применил. Это первично )
По поводу метаалгоритмов и генетического в частности — я нигде не видел доселе подобного суждения о предназначении, вы не могли бы показать соус? Напрмер, когда ставится задача оптимизации лопасти турбины — эта задача решается очевидно под конкретный диаметр, и под конкретную рабочую скорость. Я не верю что какой-то алгоритм обязан выдасть формулу или функцию описывающую все формы лопастей под все скорости и все размеры.
По поводу метаалгоритмов и генетического в частности — я нигде не видел доселе подобного суждения о предназначении, вы не могли бы показать соус? Напрмер, когда ставится задача оптимизации лопасти турбины — эта задача решается очевидно под конкретный диаметр, и под конкретную рабочую скорость. Я не верю что какой-то алгоритм обязан выдасть формулу или функцию описывающую все формы лопастей под все скорости и все размеры.
Например когда вы используете другую метаалгоритмическую систему — нейронные сети, какая у вас цель? Ну например создать сеть которая умеет распознавать лица, или капчу. Вы же не одну конкретную картинку распознать хотите.
На самом деле задача которую вы поставили и ее решение ( особенно включая факт что у вас нет перекрестных мутаций) фактически сводится к хрестоматийной задаче: 8 Puzzle . Можно конечно сказать что генетический подход можно использовать для решения А*-задач. Но как перекрестные мутации и являются главной фишкой подхода которая в теории позволять получить результат быстрее.
Кстати если вы таки попробуете сделать подход с скрещиванием то отпишитесь, интересно заработает быстрее или нет.
На самом деле задача которую вы поставили и ее решение ( особенно включая факт что у вас нет перекрестных мутаций) фактически сводится к хрестоматийной задаче: 8 Puzzle . Можно конечно сказать что генетический подход можно использовать для решения А*-задач. Но как перекрестные мутации и являются главной фишкой подхода которая в теории позволять получить результат быстрее.
Кстати если вы таки попробуете сделать подход с скрещиванием то отпишитесь, интересно заработает быстрее или нет.
Я понял. Вы говорите о том, что логичнее было бы построить систему, оперирующую скажем шаблонами и их применением, а не конкретными случайными модификациями кубика? Т.е. на выходе самая живущая особь получила бы в генотипе все возможные шаблоны действий в тех или иных случаях? Должен признаться, мне это в голову не приходило, довольно интересная задумка… Ну что ж, будет чем заняться в следующий раз, если энтузиазм накатит, спасибо. А по текущему решению… нечего скрещивать тут, я не вижу что.
Ну почему нечего. Вот например есть у вас 10 наборов команд и их фитнес-значения. Берем например топ 2 набора, режем их пополам и склеиваем половинки, получаем в итоге еще 4 набора для которых тоже считаем фитнес-функцию и добавляем в пул. Таким образом в пуле уже 14 наборов. Выбрасываем нижние 4 и у нас снова 10. Но проблема в том что таким образом очень трудно случайно попасть на решение. А это имхо уже проблема больше того что генетический подход больше подходит для статистических задач в которых нет однозначного решения.
Генетическим алгоритмом интересно создавать ботов для игр типа Цивилизации. Например для начала в пул ставим ботов которые один мирный, второй форсит науку, третий вступает в войны и тд. Фитнес-функция для них будет например количество ресурсов после 1000 ходов в игре. В конце итерации путем скрещивания ( подкручивания разных коэффициентов в настройках ботов) получаем первые мутации. То есть если боты выстроились по фитнесу в таком порядке: наука > война > мир > экономика, то создаем мутацию которая фокусируется на науке на 40%, на войне 30%, 20% мире и 10% экономике и например еще несколько ( переставив мир и экономику местами ) и снова прогоняем.
Идея в том что подбирать коэффициенты способом мутаций быстрее чем брутфорс перебором, так как вероятность что мутация будет не хуже чем родитель больше сем если просто менять перебором.
В варианте с кубиком конечно труднее так как результат должен быть не статистический а конкретный. Это как если пробовать написать полностью идеального бота — долго, мучительно и требует множества итераций
Генетическим алгоритмом интересно создавать ботов для игр типа Цивилизации. Например для начала в пул ставим ботов которые один мирный, второй форсит науку, третий вступает в войны и тд. Фитнес-функция для них будет например количество ресурсов после 1000 ходов в игре. В конце итерации путем скрещивания ( подкручивания разных коэффициентов в настройках ботов) получаем первые мутации. То есть если боты выстроились по фитнесу в таком порядке: наука > война > мир > экономика, то создаем мутацию которая фокусируется на науке на 40%, на войне 30%, 20% мире и 10% экономике и например еще несколько ( переставив мир и экономику местами ) и снова прогоняем.
Идея в том что подбирать коэффициенты способом мутаций быстрее чем брутфорс перебором, так как вероятность что мутация будет не хуже чем родитель больше сем если просто менять перебором.
В варианте с кубиком конечно труднее так как результат должен быть не статистический а конкретный. Это как если пробовать написать полностью идеального бота — долго, мучительно и требует множества итераций
Это вовсе неправда, что «метаалгоритмы», как вы их называте, должны находить функцию, которая будет собирать любой кубик. Что насчет nP проблем, которые можно (насколько известно) решить только перебором? Для них ведь нет функции. А генетические алгоритмы — это направленный перебор, чтобы прийти к решению быстрее, чем случайный поиск.
Идея очень интересная! Я сначала не понял, как работает Ваш алгоритм, и зачем geneMaxAppendCount, но потом разобрался, что каждый ген — это изменение Куба, и соответсвенно иногда невозможно найти резултьтат за 5 ходов, поэтому мы добавляем гены. Но можно было задать определнное постоянное значение, например 50 генов, за которое решение должно быть найдено и посмотреть, сколько раундов понадобиться, если проблему вообще можно решить при этом количестве генов.
И почему вы не используете скрещивание?! Со скрещиванием, вы сможете решать проблемув разы быстрее, я уверен! Как написал выше, без скрещивание получается случайный поиск, когда выбираются лучшие значения для следующих случайных модификаций. Вся сила генетических алгоритмов в кросс-оверах совмещенных с мутациями, потому что скажем вначале оптимально поворачивать куб, а в конце крутить, поэтому если скрестить два фенотипа, которые делают именно это, но по отдельности, получится оптимальное решение!
К тому же, Вы можете попробовать sequential и generational подходы: первый, когда новый Куб создается и сразу же помещается в популяцию, после чего в следующем раунде он будет уже доступен для генерации детей, второй, когда создаются скажем все 50 Кубов, которые вместе заменяют всю популяцию, и процесс повторяется заново. Если честно, не помню плюси и минусы каждого подхода, но они связаны со скоростью нахождения решения и риском того, что все Кубы в попляции будут более-менее однородны и соответственно не будет прогресса.
Я большой фанат генетических алгоритмов, если будет время попробую тоже что-то сделать с кубиками! Спасибо за идею и за описание самой проблемы и метода modify! Классный получился топик, нравится гифка!
P.S. Я думал, что можно было бы закодировать кубик как gggggggggyyyyyyyyyooooooooorrrrrrrrrbbbbbbbbb, например, где каждый ген — это меленький квадратик, но тогда очень много компьютаций понадобиться, чтобы вычислять возможные изменения, потому что поворот — это изменение 3*5 генов, и по определнному правилу, т.е. если один квадратик стал желтым, то соответсвенно определенный другой должен стать синим при повороте. Можно было бы делать мутацию/скрещивание и проверять, возможна ли она, но это очень много ресурсов, нежели делать как Вы — кодировать именно изменения.
И почему вы не используете скрещивание?! Со скрещиванием, вы сможете решать проблемув разы быстрее, я уверен! Как написал выше, без скрещивание получается случайный поиск, когда выбираются лучшие значения для следующих случайных модификаций. Вся сила генетических алгоритмов в кросс-оверах совмещенных с мутациями, потому что скажем вначале оптимально поворачивать куб, а в конце крутить, поэтому если скрестить два фенотипа, которые делают именно это, но по отдельности, получится оптимальное решение!
К тому же, Вы можете попробовать sequential и generational подходы: первый, когда новый Куб создается и сразу же помещается в популяцию, после чего в следующем раунде он будет уже доступен для генерации детей, второй, когда создаются скажем все 50 Кубов, которые вместе заменяют всю популяцию, и процесс повторяется заново. Если честно, не помню плюси и минусы каждого подхода, но они связаны со скоростью нахождения решения и риском того, что все Кубы в попляции будут более-менее однородны и соответственно не будет прогресса.
Я большой фанат генетических алгоритмов, если будет время попробую тоже что-то сделать с кубиками! Спасибо за идею и за описание самой проблемы и метода modify! Классный получился топик, нравится гифка!
P.S. Я думал, что можно было бы закодировать кубик как gggggggggyyyyyyyyyooooooooorrrrrrrrrbbbbbbbbb, например, где каждый ген — это меленький квадратик, но тогда очень много компьютаций понадобиться, чтобы вычислять возможные изменения, потому что поворот — это изменение 3*5 генов, и по определнному правилу, т.е. если один квадратик стал желтым, то соответсвенно определенный другой должен стать синим при повороте. Можно было бы делать мутацию/скрещивание и проверять, возможна ли она, но это очень много ресурсов, нежели делать как Вы — кодировать именно изменения.
И он все еще считает…
Похоже что-то тут не так.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сборка Кубика Рубика генетическим алгоритмом online без смс