обработка данных

Нажмите сюда, если долго загружается,
либо "ESC" - отмена
 
Заказ обратного звонка
Заказать звонок
Наш специалист свяжется с Вами и ответит на все вопросы
Обработка данных
Наш специалист свяжется с Вами и ответит на все вопросы.
OK

Эволюция фрактальных монстров

Источник: https://habrahabr.ru
Время чтения: ~8 мин
Эволюция фрактальных монстров
Статьи
674
Изображение носит иллюстрационный характер
Сегодня будем рисовать геометрические фракталы, которым уделяют незаслуженно мало внимания. А между тем, тут каждый фрактал — маленький шедевр, поражающий воображение!
Эволюция фрактальных монстров
Источник: habrahabr.ru
Дальше много картинок и кода, но прежде посмотрите на картинку выше и скажите, что на ней нарисовано?
Алгоритм
Рассмотрим один любопытный алгоритм на примере известного фрактала — кривой Леви.
Есть у нас две точки A1 и A2. Найдем такую точку A3, для которой угол A1 = 45°, а угол A3 = 90°.
Эволюция фрактальных монстров
Источник: habrahabr.ru
Проделаем ту же операцию для точек A1, A3 и A3, A2.
Эволюция фрактальных монстров
Источник: habrahabr.ru
И дальше рекурсивно для каждой пары точек.

Третья итерация:
Эволюция фрактальных монстров
Источник: habrahabr.ru
На 14 итерации эта кривая выглядит вот так:
Эволюция фрактальных монстров
Источник: habrahabr.ru
Более наглядно на JavaScript:
CODE
Немного модифицировав приведенный выше код, можем нарисовать другую известную фрактальную кривую — Дракон Хартера-Хейтуэя. Для этого, начиная со второй итерации, будем чередовать углы 45° и -45°.
Эволюция фрактальных монстров
Источник: habrahabr.ru
Третья итерация:
Эволюция фрактальных монстров
Источник: habrahabr.ru
На 14 итерации эта кривая выглядит вот так:
Эволюция фрактальных монстров
Источник: habrahabr.ru
Модифицированный фрагмент исходника:
CODE
Мы самую малость изменили нашу функцию, добавив в нее еще один угол, а фрактал изменился до неузнаваемости! В динамике (изменяем второй угол с шагом в 5°):
Эволюция фрактальных монстров
Источник: habrahabr.ru
И вот тут наш пытливый ум начинает задавать вопросы. А что, если попробовать использовать другие значения углов, вместо [45,-45]? Скажем, [30,-60]. Или [30,-30,-60,60]. Перепишем нашу функцию, чтобы она принимала массив с углами, в качестве одного из аргументов.

Массив position хранит номер угла из массива arr для текущей глубины рекурсии (n). Окончательный вариант функции:
CODE
С этого момента будем рисовать только точки, не соединяя их линиями… чисто из эстетических соображений. Фрактал [30,-30,-60,60] нарисованный линиями и точками:
Эволюция фрактальных монстров
Источник: habrahabr.ru
Особое внимание следует обратить на то, что все точки A3 лежат на окружности с диаметром A1A2:
Эволюция фрактальных монстров
Источник: habrahabr.ru
Если точки находятся внутри (или снаружи) окружности — фрактал получается слишком сжатым (или наоборот — выходит за пределы области отрисовки). Наглядно:
Эволюция фрактальных монстров
Источник: habrahabr.ru
Вот этим косинусом мы выравниваем точки по окружности:
CODE
Не трудно заметить, что используя угол 120° мы получим ту же точку, что и с углом -60°. Поэтому все углы лежат в диапазоне (-90°,90°).

Попробуем ввести в наш скрипт разные комбинации углов.
«Маленькие шедевры»
Несколько рандомных фракталов с углами -45°/45°:
Эволюция фрактальных монстров
Источник: habrahabr.ru
С углами -30°/30°/-60°/60°:
Эволюция фрактальных монстров
Источник: habrahabr.ru
С углами -15°/15°/-30°/30°/-45°/45°/-60°/60°/-75/75°:
Эволюция фрактальных монстров
Источник: habrahabr.ru
… Так можно продолжать очень долго. Если использовать углы 15°/30°/45°/60°/75° (положительные и отрицательные) и, скажем, рисовать «восьмиугольные» фракталы — сколько всего фракталов мы сможем нарисовать? Примерно 10^8 = 100 000 000 штук. Кроме того, множество «восьмиугольных» фракталов не имеет пересечений с множеством, скажем, «девятиугольных» фракталов (за исключением фракталов, у которых все углы одинаковые). В общем, очень немало фракталов можно нарисовать этим алгоритмом.

Искать вручную что-то среди этого множества, при этом не зная, как это «что-то» должно выглядеть — немного затруднительно. Что мешает нам прикрутить сюда генетический алгоритм? Ничего. Прикрутим!
Эволюция
Генетический алгоритм — эвристический алгоритм поиска, использующий механизмы биологической эволюции. Алгоритм прост, интуитивно понятен и вместе с тем довольно эффективен.

Делится на несколько этапов:

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

2. На следующем этапе происходит селекция. Для каждой особи считаем коэффициент приспособленности (fitness). Чем лучше особь — тем выше коэффициент. Сортируем популяцию по этому коэффициенту. Делим популяцию пополам — из наиболее приспособленных будем формировать следующую популяцию. (Как делить и что выбирать для следующей популяции — тема, на которую можно долго спорить).

3. Следующий этап — скрещивание. Из наиболее приспособленных выбираем (случайным образом) две особи — родителей. Делаем двух потомков: берем случайным образом часть генов одного родителя и часть генов другого, заполняем ими генотип одного из потомков. Оставшиеся гены уходят второму потомку. Берем следующих двух родителей. Проделываем ту же операцию. Так пока не закончатся родители. Из родителей и потомков формируем новую популяцию.
Эволюция фрактальных монстров
Источник: habrahabr.ru
4. Заключительный этап — мутации. Берем некоторый процент особей из новой популяции, для каждой из них (особей) выбираем случайным образом ген и заменяем его на случайное значение. Таким образом мы добавляем в наш генофонд гены, которых не было в начальной популяции и которые, в перспективе, могут сформировать наилучшие результаты. Кроме того, повышая процент мутаций, можно в какой-то степени решить проблему сходимости к локальному оптимуму.

Каждый этап более наглядно на JavaScript.
Начальная популяция
CODE
Функция randomangl вызывается с тремя аргументами: минимальный угол, максимальный угол и шаг. Удобно, если мы хотим заполнить начальную популяцию определенными углами. Например, можно вызвать функцию с следующими аргументами:

randomangl(-45, 45, 90) — сгенерирует углы -45°/45°
randomangl(-60, 60, 30) — сгенерирует углы -60°/-30°/30°/60°
randomangl(-75, 75, 15) — сгенерирует углы -75°/-60°/-45°/-30°/-15°/15°/30°/45°/60°/75°

Углы 0° не используем. Фрактал [45°,0°] выглядел бы вот так:
Эволюция фрактальных монстров
Источник: habrahabr.ru
Получаем тот же фрактал [45°], только в том месте, где пытаемся нарисовать 0° — точки сливаются (вся дальнейшая рекурсия в этом месте становится бессмысленной). По этой же причине, нет смысла генерировать фракталы с использованием 90°. Для начальной популяции лучше всего вызвать функцию randomangl(-75, 75, 15). Для мутаций — randomangl(-89, 89, 1).

Создаем начальную популяцию:
CODE
Создаем сразу несколько популяций с разным количеством углов (anglemin, anglemax). Инициализируем отдельный массив с коэффициентам приспособленности. Первый ген у каждой особи принудительно делаем положительным — фракталы [45°,-45°] и [-45°,45°] симметричны.
Селекция
Вообще, приспособленность каждой особи, в классических генетических алгоритмах, определяется специальной fitness-функцией. Функция оценивает, насколько каждая из особей решает поставленную задачу. В нашем случае, четко сформулировать задачу не представляется возможным (не знаем, как это «что-то» должно выглядеть), поэтому в качестве fitness-функции прикрутим к алгоритму пользователя.

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

Интерфейс:
Эволюция фрактальных монстров
Источник: habrahabr.ru
На страничке два канваса: myCanvas1 и myCanvas2. И две кнопочки: onclick=«selecter(1);» и onclick=«selecter(2);»

Вызываем функцию, которая рисует два случайных фрактала:
CODE
В функции get2fractals выбираем случайную популяцию.
В функции drawcanvas проверяем if(n==1) — чтобы не рисовать два одинаковых фрактала. Номер популяции и номера двух фракталов храним в глобальных переменных (PopulationNumber и FractalNumber[]).

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

Будем считать, что пользователь оказался добросовестным и произвел выборов не меньше, чем количество особей в популяции, прежде чем запустить механизм эволюции.
Скрещивание и мутации
CODE
Берем поочередно каждую популяцию. Пишем всех особей во временный массив, туда же пишем их коэффициенты приспособленности fitness. Сортируем временный массив по этим коэффициентам. Отрезаем половинку (самых приспособленных). Старые два массива обнуляем, чтобы там ничего лишнего не осталось. Дергаем из временного массива двух предков, формируем двух потомков. Заполняем популяцию предками и потомками.

Производим мутации. Небольшое замечание. Вместо процента мутаций во всей популяции, используем вероятность мутации отдельно взятой особи.

Доступна опция exchange. С помощью этой опции реализована модель миграции особей между популяциями.

Модель миграции:
CODE
Если флажок Exchanges установлен, поочередно для каждой популяции, одна случайная особь с вероятность 50% может обменяться генами со случайной особью из следующей популяции (популяция n+1). Генов в генотипах следующей популяции больше, обмен производим следующим образом. Выбираем случайный ген у особи в популяции n+1, вставляем его на ту же позицию в генотип у особи из популяции n. Меняем особи местами:
Эволюция фрактальных монстров
Источник: habrahabr.ru
Осталось добавить свистелок (css-кнопочки, сохранение всего процесса в localStorage, отображение Parents Tree...).
Поделиться
Поделиться
Поделиться
Поделиться
Поделиться
Поделиться
Поделиться
Подписка на новости. Получайте важное первым
ПОДПИСАТЬСЯ