Цель данного тренажера — облегчить изучение алгоритмов и обозначений поворотов в кубике Рубика путём моделирования оных и просмотра в виртуальной анимированной модели кубика. Моделирование позволяет делать и отменять ходы, облегчая понимание того, что при этом происходит с кубиком. В тренажёре возможны 3 режима использования с соответствующими вкладками:
- Processing Algorithm — «Обработка Алгоритма «,
- Manual Commands — «Ручные Команды» и
- Edit Base — «Редактировать Основу «.
Во всех вкладках, помимо средств управления и функций, куб показан в двух изображениях. Большое (слева) это – вид спереди, маленькое (справа) – вид сзади, что позволяет видеть куб целиком без необходимости его вращения. Там же, чуть ниже в центре, находится маленький куб, показывающий положение осей X, Y, и Z (это поможет не запутаться при вращении куба мышкой и вернуть его в исходное положение).
Положение куба может быть изменено, то есть, его можно вращать, используя мышь. Нажатие на рисунок куба и удерживание нажатой левой кнопки позволяет вращать куб относительно осей X и Y. С нажатой правой кнопкой мыши удобно вращать кубик относительно осей Y и Z. Во всех трёх вкладках есть кнопка «Default Orientation» , которая возвращает положение кубика Рубика в пространстве к начальному состоянию.
КАК СОБРАТЬ КУБИК РУБИКА 3×3 БЕЗ ФОРМУЛ с помощью телефона/Программа для сборки кубика рубика
Этот симулятор работает с двумя наборами команд (обозначений вращения кубика), стандартным набором и набором WCA (World Cube Association – всемирная ассоциация кубика).
1. Вкладка Processing Algorithm
На вкладке Processing Algorithm можно моделировать алгоритм, введённый в поле «Algorithm». После воспроизведения алгоритма его можно проанализировать шаг за шагом, добавить в «список» алгоритмов и впоследствии сохранить в файл. После полной вставки (написания) алгоритма, нажимаете на «Play», и программа в окне просмотра исполнит весь алгоритм, чтобы Вы могли видеть, как, когда и какие грани вращаются. В поле для ввода алгоритма команды должны быть написаны через пробел между каждой командой. Программа «воспринимает» символы ТОЛЬКО из «стандартного набора» и набора команд по правилам WCA.
Описание функций:
1- Окно просмотра.
2 — Standard Cube: приводит куб к стандартному состоянию (то есть, после нажатия этой кнопки Вы увидите в окне просмотра собранный кубик со стандартным набором и расположением цветов и сориентированным, как показано на рисунке — это дефолтное состояние при открытии окна программы).
3 — Cube To Cmd Man: отправляет текущий куб на вкладку Manual Commands в окно просмотра.
4 — Cube To Edit Base: отправляет текущий куб на вкладку Edit Base в окно просмотра.
5 — Get Cube From Manual Cmd: импортирует куб из вкладки Manual Commands в окно просмотра текущей вкладки.
6 — Get Cube From Edit Base: импортирует куб из вкладки Edit Base в окно просмотра текущей вкладки.
7 — Default Orientation: возвращает положение кубика в пространстве к начальному состоянию.
8 — Play Animation: кнопка, типа, включает/отключает анимацию. По факту: не снимайте эту галочку, так как после запуска алгоритма исполняется только одна команда, а все кнопки вкладки становятся неактивными. Лечится этот глюк только перезапуском программы с обязательной постановкой галочки в этом чекбоксе.
9 — Animation Speed: скорость вращения граней кубика.
10 — непосредственно поле для ввода алгоритма, который Вы хотите воспроизвести.
11 — Play: кнопка для запуска и просмотра «в действии» введённого алгоритма.
12 — Кнопка » » : продвигает на 1 шаг вперёд изучаемый алгоритм.
Поле Algorithm list
15 — Auto Play When Selecting: отсутствие /присутствие галочки в этом чекбоксе определяет, будет ли выбранный из списка алгоритм воспроизведён автоматически.
16 — Clear: удаляет все алгоритмы из выпадающего списка алгоритмов.
17 — Remove: удаляет алгоритм, выбранный в настоящее время в списке алгоритмов.
18 — Add/Update: добавляет новый алгоритм, который введён в поле «Algorithm», к списку алгоритмов, или обновляет выбранный из списка и отредактированный алгоритм (в этом случае программа спросит Вас, действительно ли Вы хотите изменить существующий алгоритм).
19 –Выпадающий список: список алгоритмов, созданных или загруженных из файла.
20 — поле Algorithm Name: область добавления названия нового алгоритма, а так же поле отображения названия алгоритма, выбранного из списка.
21 — Open: открывает файл со списком алгоритмов.
22 — Save: сохраняет список алгоритмов в файл.
Теперь о некоторых особенностях работы со списком алгоритмов. Для того, чтобы создать новый список, Вам нужно сначала открыть любой существующий ))), он есть в папке с установленной программой и называется ExemploAlgos.ALG, кнопкой Clear очистить его и добавить новые алгоритмы, затем нажать кнопку Add/Update и сохранить его под новым именем с помощью кнопки Save.
Для редактирования существующего списка алгоритмов выберите нужный с помощью кнопки Open. После редактирования списка алгоритмов (добавления новых и удаления/редактирования существующих ) необходимо нажать кнопку Add/Update, а затем кнопку Save и сохранить список. Если Вы сохраняете файл под старым именем с заменой существующего, то все изменения будут внесены, но удалённые алгоритмы останутся в этом списке. Если Вы хотите сохранить изменённый список без удалённых алгоритмов, то нужно сохранить файл с НОВЫМ именем, тогда он сохранится именно в том виде, в котором находится в программе в данный момент.
2. Вкладка Manual Commands.
На вкладке Manual Commands можно запустить и просмотреть команды по одной, по мере необходимости, с помощью соответствующих кнопок или горячих клавиш. Эти команды можно автоматически записать и в дальнейшем отправить на вкладку Processing Algorithm для моделирования алгоритма или его части. Каждая выбранная команда сразу показывает его результат в окне предварительного просмотра.
1 — Окно просмотра.
2 — Выбор набора команд: Установкой радиокнопки выбираем между набором стандартных команд и набором команд WCA.
3 — Кнопки команд: выполняют команды согласно тексту кнопки.
4 — Индикатор обратной команды: при нажатии клавиши «Shift» на клавиатуре или выборе этого чекбокса мышкой, на всех кнопках команд появится штрих для выполнения обратного поворота.
5 — Индикатор команды двойного слоя: при нажатии клавиши «Ctrl» на клавиатуре или выборе этого чекбокса мышкой, соответствующие кнопки команд изменятся волшебным образом на команды для осуществления поворота грани с прилегающим слоем.
6 — Индикатор поворота на 180 градусов: при нажатии клавиши «Alt » на клавиатуре или выборе этого чекбокса мышкой, выбранная команда будет проделана дважды, то есть, выбранный слой (или 2 слоя, или весь кубик) повернётся на 180 градусов.
7 — Command Animation: включение анимации движения кубика. Эта функция, как и на первой вкладке, работает с глюком, но другим. Если снять или поставить галочку, то изменений при нажатии на кнопку Play не произойдет, а вот если после простановки или снятия той галочки посетить вкладку Edit Base и вернуться назад, то анимация отключится или включится, в зависимости от наличия галочки в этом чекбоксе.
8 — Speed: скорость вращения граней кубика.
9 — Rec Cmd: автоматическая запись выполненных команд в поле 16.
10 — Del Cmd: отменяет и стирает из записи последнюю записанную команду.
11 — Add To Proc Algo: отправляет набор записанных команд из строки на вкладку Processing Algorithm в поле для ввода алгоритма. Если там уже присутствует запись какого-то алгоритма, то отправляемые команды добавятся в конце существующего алгоритма.
12 — Cube to Proc Algo: отправляет текущий куб на вкладку Processing Algorithm в окно просмотра.
13 — Cube To Edit Base: отправляет текущий куб на вкладку Edit Base в окно просмотра.
14 — Standard Cube — Стандартный Куб: приводит куб к стандартному состоянию (см. п. 2 для вкладки Manual Commands).
15 — Default Orientation: возвращает положение кубика в пространстве к начальному состоянию.
16 — Поле, в которое выводятся записываемые команды алгоритма при выборе Rec Cmd.
3. Вкладка Edit Base.
На вкладке Edit Base можно скопировать текущее состояние реального кубика Рубика в симулятор. Это позволяет, имея реальный куб в стадии решения, проверить алгоритмы и команды в программе, как если бы они были сделаны в реальном кубе, чтобы получить гарантированный результат в реальном кубике Рубика.
Описание функций:
1- Окно просмотра.
2 — Pecas de Canto disponiveis: Доступные угловые элементы, которые вставляются в позицию, выбранную в пункте 3. На рисунке ниже показано содержимое выпадающего списка угловых элементов, когда ни одна угловая часть не определена в кубе:
3 — Posicoes de Canto disponiveis: возможные операции для выбранного углового элемента в этой позиции, то есть, Set: установить (пункт 4), Clear: очищает (пункт 6) или Spin: повернуть (пункт 5).
4 — Set: устанавливает в текущее положение (пункт 3), выделенный элемент (пункт 2).
5 — Spin: выполняет вращение в отобранном положении (пункт 3).
6 — Clear: очищает выбранную позицию (пункт 3), выложив элемент обратно в список доступных угловых элементов (в пункте 2).
7 — Auto Next Set Pos: автоматически Выбирает новое положение (пункт 3) для следующего углового элемента. Если позиция уже занята, программа выдаст окно предупреждения с указанием номера данной позиции и номера установленного в ней углового элемента. На рисунке ниже, например, говорится о том, что на 18-ой позиции стоит 8-ой элемент.
8 — Pecas de Centro disponiveis: Доступные центральные элементы, которые вставляются в позицию, выбранную в пункте 9. На рисунке ниже показано содержимое выпадающего списка центральных элементов, когда ни один центральный элемент не установлен в кубе:
9 — Posicoes de Centro disponiveis: возможные операции для выбранного центрального элемента в этой позиции, то есть, Set: установить (пункт 10), Clear: очищает (пункт 11)
10 — Set: устанавливает в текущее положение (пункт 9) выделенный фрагмент (пункт 8).
11 — Clear: очищает выбранную позицию (пункт 9), выложив центральный элемент оттуда обратно в список (в пункте 8).
12 — Auto Next Set Pos: автоматически Выбирает новое положение (пункт 9) для следующего центрального элемента. Если позиция уже занята, программа выдаст окно предупреждения с указанием номера установленного в ней элемента.
13 — Pecas Laterais disponiveis: Доступные реберные (боковые) элементы, которые вставляются в позицию, выбранную в пункте 14. На рисунке ниже показано содержимое выпадающего списка реберных элементов, когда ни один реберный элемент не установлен в кубе:
14 — Posicoes de Canto disponiveis: возможные операции для выбранного реберного элемента в этой позиции, то есть, Set: установить (пункт 15), Clear: очищает (пункт 17) или Spin: повернуть (пункт 16).
15 — Set: устанавливает в текущее положение (пункт 14), выбранный боковой элемент (пункт 13).
16 — Spin: вращает боковой элемент, установленный в выбранную позицию (пункт 14).
17 — Clear: очищает выбранную позицию (пункт 14), выложив боковой элемент обратно в список доступных для установки (в пункте 13).
18 — Auto Next Set Pos: автоматически выбирает новое положение (пункт 14)для следующего бокового элемента. Если позиция уже занята, программа выдаст окно предупреждения с указанием номера установленного в ней элемента.
19 –Base Lists: список конфигураций кубика Рубика для вывода в окно просмотра.
20 — Load Base: выводит в окно просмотра выбранную комбинацию.
21 — Add/Update: добавляет новую или перезаписывает выбранную из списка комбинацию на ту, в которой в настоящий момент находится кубик Рубика в окне просмотра. Для добавления новой, ей нужно присвоить новое имя.
22 — Remove: удаляет из списка выбранную в настоящий момент комбинацию.
23 — Open: открывает файл со списком комбинаций кубика.
24 — Save: Сохраняет текущий список комбинаций в файл.
25 – Name Add: Название добавляемой или перезаписываемой комбинации на кубике (основы /базы) для добавления в список комбинаций и сохранения в файл.
26 — Random Animation: Включение анимации при нажатии кнопки перемешивания (Random Cube) кубика Рубика.
27 — Speed: Скорость вращения граней кубика при перемешивании.
28 — Standard Cube — Стандартный Куб: Приводит куб к стандартному (см. выше) состоянию.
29 — Clean Cube: Полностью очищает кубик Рубика от цветных элементов, оставляя только их нумерацию для дальнейшей работы.
30 — Random Cube: Перемешивает (запутывает) кубик Рубика при полностью расставленных элементах (хоть по стандартным местам, хоть по любым другим, но куб перед этим должен быть полностью заполнен цветными элементами, иначе кнопка не будет активной). При перемешивании кубика программа выдаёт окно, в котором показывает по какому алгоритму она замесила куб и спрашивает что сделать с этой последовательностью команд (Set it — записать в строку проигрывания на вкладку Processing Algorithm с перезаписью того, что там было записано, Append it — дописать эту последовательность к тому, что там записано, или Cancel — ничего не делать.)
31 — Default Orientation: возвращает положение кубика в пространстве к начальному состоянию.
32 — Cube To Cmd Man: Отправляет текущий куб на вкладку Manual Commands в окно просмотра (если все элементы расставлены по нужным местам).
33 — Cube to Proc Algo: Отправляет текущий куб на вкладку Processing Algorithm в окно просмотра (если все элементы расставлены по нужным местам).
На четвёртой вкладке «About справка по данной программе на португальском языке. А эта страница сайта является близким к тексту пересказом того, что там написано, за исключением языка вращений кубика (он есть на другой странице сайта) и слов благодарности консультанту разработчика этой программы. Так что, можете считать сей опус русским онлайн хелпом к ней.
Операционные системы: Windows XP, 7, 8
Поддерживаемые языки: португальский
Версия: 1.3.0
Лицензия: freeware (бесплатная )
Источник: dedfoma.ru
CubeX — Rubik’s Cube Solver
При обновлении версии приложения вы получите уведомление на E-mail.
Уже подписались: 1
Скриншоты Видео Инструкции
CubeX — Rubik’s Cube Solver — это приложение, которое поможет вам собрать Кубик Рубика максимально быстрым путём из возможных благодаря двум специальным механизмам.
Сфотографируйте свой куб при помощи камеры и на основе полученных по снимку цветовых данных CubeX подберёт пошаговую помощь в сборе кубика.
Источник: androidvip.net
Сборка Кубика Рубика генетическим алгоритмом online без смс
В то время пока я собирался на ланч, мой ко-воркер Дейв окликнул меня: «Хэй, Алекс, а ты не хочешь заниматься улучшениями навыков своего программирования?». Я задумался. Это было интересное предложение, но я склонялся ответить отказом: «Сейчас я занимаюсь развитем навыков говорения на языках, дружище!». Ладно, шучу.
Утро началось с того, что я добрался до почты и заполучил в руки копеечный китайский Кубик, случайно заказанный на али. К обеду я проштудировал мануал сборки и обновил мышечную память, а к вечеру пришло осознание, что я наигрался. Будущее кубика было ясным: он будет пылиться на полке, раз или два в неделю может быть я буду его собирать, чтобы привести мысли в порядок или отвлечься, но не более того. Соревнование в механической скорости сборки? Non merci, уж лучше скворечники делать…
Ситуацию, как всегда, спасли мысли об автоматизации. После недолгого изучения я узнал рекогнисцировку. Для начала, число Бога уже давно найдено и равно 20. Правда задача сборки от этого не упрощается, т.к. использовать граф кратчайших путей для всех возможных конфигураций кубика не очень спортивно и немножко накладно по ресурсам.
Алгоритм Бога предполагает под собой некое разумное количество использованной памяти, и в то же время обязан обеспечить минимально возможное число модификаций. Так вот, такого алгоритма еще нет.
Есть ряд алгоритмов, позволяющих заметно ускорить сборку по сравнению с традиционными шаблонными методоми, но повторять кем-то уже проложенный (математически) путь мне показалось скучным. Если кому интересно, вот хороший анализ Далее есть традиционные шаблонные методы. Идея здесь в послойной сборке снизу вверх с использованием формул.
Формула — последовательность модификаций Кубика, приводящая к таким-то целевым модификациям, и таким-то побочным. Соответственно, побочные модификации почти всегда падают на еще не собранные слои. Различаются шаблонные методы уровнем детализации шаблонов. Всякого рода спидкуберы знают все мыслимые шаблоны для большого количества частных случаев, что позволяет отыграть лишнюю 0.1 секунду с каждой модификации на соревнованиях. Пример, на что еще можно потратить жизнь.
Итак, я постепенно формировал для себя задачу. В итоге, формулируется она так: за кратчайшее реальное время необходимо написать решалку для Кубика Рубика.
Что мы знаем о Кубике? Число его состояний описывается как
(8! × 3^7) × (12! × 2^11)/2 = 43 252 003 274 489 856 000
Именно это число накладывает ограничения на использование графа кратчайших путей. Что мы знаем о его правилах? То что каждый конкретный элемент (боковой или угловой) должен стоять точно на своём месте. Что является точным местом? Для бокового элемента — это соотстветствие обоих его цветов цветам центральных элементов, для углового элемента — соответствие трёх центральных элементов трём цветам этого углового элемента.
Таким образом мы можем в любой момент времени просто ответить на вопрос — «стоит ли данный элемент на своём месте?». Второй аспект, который мы знаем — Кубик может быть собран послойно, при чём каждый слой собирается постепенно. А это значит… па-пара-парам! Нужна градиентная эвристика. Осталось лишь выбрать метод реализации.
Алгебраические методы я не стал рассматривать, т.к. мне хотелось получить некое решение, легко обобщаемое на подобый класс задач. (То что получилось я могу не слишком сложно обобщить до 11*11*11, к примеру) Еще был вариант: подробно забить маски шаблонов и формулы к ним, просто автоматизировав любую из статей в гугле «сборка Кубика Рубика». Но по понятным причинам, кроме тоски этот вариант не навевал ничего.
Оставался перебор. Несмотря на полное возможное число состояний, перебор представлялся мне самым простым решением. Оставалось выяснить детали реализации. Интуиция подсказывала мне, что потребуется некая конкурентная среда возможных вариантов, чтобы из представленных вариантов было быстрее найти переход на следующий уровень сборки. В общем-то вариант генетического алгоритма начал доминировать сам собой.
Средой исполнения я решил выбрать обычный современный браузер, т.к. эта штука идеально выполняла требование скоростной реализации. Я поделился идеей с приятелем, занимавшимся в этот момент выпасом гусей в Белоруссии, или чем-то в этом роде. Дима подхватил предложение, мы начали смотреть способы параллельного объединения усилий. Довольно быстро нашёлся collabedit.com, позволявший писать JavaScript код нескольким людям одновременно. Я закинул html на хостинг с инклюдами
И мы приступили. Хранить кубик как описание физического объекта нам показалось бессмысленным и гораздо более сложным процессом, чем хранение и связка отдельных 6-ти плоскостей, состоящих из массивов по 9 элементов. Я сел за написание UI и рендеринг кубика, Дима сел за описание объекта куба и его модификаций. Для того чтобы выполнить над кубиком абсолютно любой набор действий, требуется уметь выполнять 3 операции:
1. Вращение куба влево
2. Вращение куба вверх
3. Вращение фронтальной плоскости по часовой стрелке
Я думаю нет смысла доказывать утверждение, оно вполне интуитивно понятно.
При вращении куба, например, вверх, необходимо циклично поменять местами 4 массива плоскостей, вращать левую и правую стороны против и по- часовой стрелке соответсвенно, а так же отразить по горизонтальной оси заднюю плоскость. На следующее утро я убил практически 2 часа времени на осознание последнего факта, получая после вращений виртуального и реального кубиков расхождение в симметрии.
Кубик научился поддерживать через метод .modify (symbol) команды из стандартной формульной записи (Right, Left, Upper, Down, Front), а так же их против-часовые модификации с апострофом. Далее я написал функцию runSequence позволяющую выполнять формулу целиком над заданным кубиком. Часть подготовки интерпретатора была почти завершена. Последним штрихом я сделал функцию shuffle с выводом новой случайной формулы тасования кубика, и на всякий случай сверил результат интерпретатора и реального кубика. Теперь всё, рутинная часть позади.
Общество Кубов, в котором нет цветовой дифференциации, лишено цели.
подумалось мне. Каждый член Популяции Кубов, каждый маленький Кубик, должен представлять на сколько он близок, как личность, к Высшему Кубу. В противном случае данная социальная группа очевидно повязнет в хаосе и модификационных излишествах. Первым делом, я сел за описание фитнесс-функции.
Было очевидно, что просто считать количество одинаковых цветов на каждой из плоскостей, возводить их, скажем, в квадрат и складывать — хочется, но нельзя. В противном случае из ближайшего локального максимума популяция Кубов никогда не выберется. Луч надежды должен быть более узконаправленным. Я описал функцию в соотстветсвии с классическими методами сборки — послойно. При чем каждый следующий слой, и каждый следующий элемент текущего слоя давал ощутимый прирост фитнесса, что позволяло более приспособленным только что появившимся Кубособям быстро доминировать в популяции.
function calcTargetStickers (cube, side, cells) < var target = cube.get(side, 4); cells = cells || [0, 1, 2, 3, 4, 5, 6, 7, 8]; var count = 0; for (i = 0; i < cells.length; i++) < count += cube.get(side, cells[i]) == target ? 1 : 0; >return count; > . var crossCoincidence = 0; /* [side1, cell_side1, front_cell] */ $.map([[1, 5, 3], [0, 7, 1], [3, 3, 5], [4, 1, 7]], function (el, i) < var p = calcTargetStickers(cube, el[0], [el[1]]); if (p calcTargetStickers(cube, 2, [el[2]])) < crossCoincidence++; >>); points += crossCoincidence * crossCoincidence * 50; var anglesCoincidence = 0; /* [side1, cell_side1, side2, cell_side2, front_cell] */ if (crossCoincidence == 4) $.map([[1, 2, 0, 6, 0], [0, 8, 3, 0, 2], [3, 6, 4, 2, 8], [4, 0, 1, 8, 6]], function (el, i) < if (calcTargetStickers(cube, el[0], [el[1]]) calcTargetStickers(cube, el[2], [el[3]]) calcTargetStickers(cube, 2, [el[4]])) < anglesCoincidence++; >>); points += anglesCoincidence * anglesCoincidence * 100; var layer2Coincidence = 0; /* [side1, cell_side1, side2, cell_side2] */ if (anglesCoincidence == 4 crossCoincidence == 4) $.map([[1, 1, 0, 3], [0, 5, 3, 1], [3, 7, 4, 5], [4, 3, 1, 7]], function (el, i) < if (calcTargetStickers(cube, el[0], [el[1]]) calcTargetStickers(cube, el[2], [el[3]])) < layer2Coincidence ++; >>); points += layer2Coincidence * layer2Coincidence * 200; var layer3Coincidence = 0; /* [side1, cell_side1] */ if (layer2Coincidence == 4) $.map([[1, 3], [0, 1], [3, 5], [4, 7]], function (el, i) < if (calcTargetStickers(cube, el[0], [el[1]])) < layer3Coincidence ++; >>); points += layer3Coincidence * layer3Coincidence * 300; var layer3Angles = 0; /* [side1, cell_side1, side2, cell_side2] */ if (layer3Coincidence == 4) $.map([[1, 0, 0, 0], [0, 2, 3, 2], [3, 8, 4, 8], [4, 6, 1, 6]], function (el, i) < if (calcTargetStickers(cube, el[0], [el[1]]) calcTargetStickers(cube, el[2], [el[3]])) < layer3Angles ++; >>); points += layer3Angles * layer3Angles * 400; if (layer3Angles == 4) solved = true;
Каждый уровень содержит в себе проверку четырёх элементов, боковых или же угловых, стоят ли эти элементы на своих местах. Если все 4 элемента стоят на своих местах, мы можем переходить к следующему уровню. Это обеспечивает плавную сегрегацию всей популяции.
Далее, предстоял сам генетический алгоритм. Очевидно, геном является некая шаблонная модификация Куба. Геномом — весь набор модификаций, который привел к текущему состоянию. Что же является результатом скрещиванием Кубов? Ничего, они все однополые и размножаются почкованием.
В каждом раунде эволюции происходит мутация всех геномов путем добавления генов к уже существующему геному. Еще одним параметром мутации является значение geneMaxAppendCount — максимальное возможное число генов, которые будут добавлены во время следующей мутации. Это важное число, которое регулирует, на сколько сложную модификацию Куб сможет сгенерировать за один раз. После мутации Куба считается его фитнесс, а затем и всех остальных кубов. Затем считается средняя температура по больнице, и на основании неё — насколько широко генотип конкретного Куба распространится теперь в популяции:
var poluttionCount = Math.floor((1) * (curFitness / averageTemperature — 1) ); poluttionCount *= poluttionCount; poluttionCount—;
Далее этот более сильный Куб вымещает собой несколько более слабых Кубов популяции, и начинается следующий виток эволюции.
Ура! Оно работает.
Основная проблема с которой я столкнулся, заключалась в самом последнем этапе сборки: полностью собраны 2 уровня, на 3-м уровне верно стоят боковины, и даже на своих местах расположены углы — осталось лишь повернуть по- или против часовой стрелки несколько уголков и вот он полностью готовый Куб… Но, этот этап хранит в себе хитрость: во время финального поворота углов, а их всегда либо 0, либо 2 и более — разрушаются все два нижних слоя куба до тех пор, пока не будут повернуты в правильное положение все верхние углы, да еще и так, что все модификации должны производиться с одной и той же плоскости, а в конце вдобавок нужно правильно совместить по горизонтальным плоскостям все 3 полностью собранных слоя Кубика. И несмотря на то, что с самым последним действием интуитивно справится даже двухлетний ребёнок, мне не хотелось закладыавть в фитнесс-функцию каких-то частных случаев. Задача эволюционного алгоритма любыми способами перескочить яму, которая необходима для промежуточной сборки финальной части. Для этого я сделал две вещи:
1. В набор формул я добавил формулы поворота угла в повторении 2х и 4х, для того чтобы угол поворачивался против или по часовой стрелке за 1 ген соответственно. Это увеличивает вероятность выполнить большую часть операцию за одну мутацию.
2. Ввел значение geneMaxAppendCount и включил его в фитнесс-функцию: points += cube.geneMaxAppendCount * 30;. Дело в том, что обычно Кубы стартую с максимального значения в 4 или 5. В самом начале, когда улучшение Куба сделать легко, оно происходит за 1 или 2 гена, в популяции начинают доминировать Кубы с короткими генетическими переходами. На самом последнем этапе подобная стратегия уже не проходит, и мы должны поощрять особей, которые пытаются найти более сложные решения, но так, чтобы рост geneMaxAppendCount не стал самоцелью популяции.
Два этих ухищрения позволили гарантированно решать любой Кубик Рубика в среднем за 300 операций (исключая операции вращения всего Куба). Иногда процесс затягивается на последнем этапе, до тех пор, пока случайная мутация не переживет яму, временно разрушающую Куб. Вручную, по самому примитивному алгоритму я собираю Кубик в среднем за 170 операций. Но я считаю для переборного алгоритма это вполне разумное число, к тому же перед популяцией вполне можно поставить задачу сокращения длины генотипа, что резко снизит требуемое число операций.
Далее, о более низкоуровневом решении.
Как возможные гены, программа использует набор формул, которые я скопировал из случайной статьи в интернете.
var formulHigh = [ «U», «D», «», «v», «», «v», «R’ D’ R D», «U’ L’ U L U F U’ F'», «F R U R’ U’ F'», «R U R’ U R U U R'», «U R U’ L’ U R’ U’ L», «U’ L’ U R U’ L U R'», «R’ D’ R D R’ D’ R D», «R’ D’ R D R’ D’ R D R’ D’ R D R’ D’ R D» ];
Я задумался, возможно решить задачу совсем чисто, на использовании лишь операторов вращения и базовых модификаций?
var formulLow = [ «U», «F», «», «v», «R», «L», «D», «R’ D’ R D R’ D’ R D», «R’ D’ R D R’ D’ R D R’ D’ R D R’ D’ R D» ];
Формулы поворота углов мне показались однозначно необходимыми, в противном случае предфинальная яма представляется мне непреодолимой за разумный промежуток времени.
Я столкнулся со следующей проблемой: даже небольшие ямки уже преодолевались с трудом. Из-за усложнения на порядок пути до полезой модификации, Кубы очень трудно переживали периоды временного разрушения. Нужно было каким-то образом обеспечить протекцию некоторых смелых Кубов, ушедших в поисках лучшей формы. Я решил ввести политику Льготного Кредитования Популяции.
В случае, когда за последние 100 раундов эволюции не происходило значимых улучшений фитнесса, случайные Кубы безпроцентно кредитовались на 30 раундов дополнительным фитнессом. Но они не могли использовать свой кредит, чтобы только за счет него возвыситься над всей популяцией и расплодиться. Они получали временную протекцию от более приспособленных в данный момент Кубов, для того чтобы иметь больше шансов выйти на следующую выйгрышную конфигурацию.
Идея, на мой взгляд, неплохая, но видимо я недокрутил настройки, поэтому сильной прибавки эффективности я не получил.
Вероятно, на «чистое» решение требуется на несколько порядков большая популяция, в которой пространство доступных вариантов резко расширится. Кстати, в Хроме код работает заметно быстрее моего ФФ.
Какой итог я могу подвести. Это первое моё применение генетического алгоритма, и, к счастью, успешное. Поставленная цель достигнута, при чём путём наименьшего сопротивления. Передаю эстафетную палочку тебе, хабровчанин, возможно у тебя получится заставить популяцию придти к решению «чисто».
- кубик рубика
- генетические алгоритмы
- javascript
Источник: habr.com