Фракталы

«Если долго всматриваться в бездну — бездна начнёт всматриваться в тебя» © Ницше

Previous Entry Share Next Entry
Геометрические фракталы и немножко генетики :)
xcontcom
Вот тут эта бяка: http://fractal.facegenetic.com/

фрактал

Не забываем нажать сюда

Под катом много картинок и непонятного текста :)



В двух словах.

Есть один такой чудный алгоритм, который мне впервые попался в августе 2005-го года. Очень мне тогда понравился этот алгоритм, на нем и начал изучать программирование, делая реализации этого алгоритма в Visual Basic. Тут вот на днях нашел дамп своего старого сайта со всеми реализациями геометрических фракталов и решил вспомнить детство. Тем более, фракталы - отличный материал для генетических алгоритмов.

Фик его знает, кто первый тот алгоритм придумал. Вероятно шведский математик Кох. Его фрактал - "Снежинка Коха", но нас она сейчас мало интересует. Рассмотрим реализацию алгоритма на примере другого замечательного фрактала - "Кривой Леви".

Алгоритм прост до неприличия. Есть у нас две точки - A и B. Находим третью точку C, так чтобы угол (альфа) CAB был 45°, а угол ACB - 90° (ну или AC=AB*cos(альфа)).

фрактал

Теперь у нас есть три точки - A, C и B, для которых находим следующие точки D и E

фрактал

Вот так это выглядит после 18 итераций:

фрактал
http://fractal.facegenetic.com/0.785398/0.707106
(Точки линиями не соединял - пользовал context.fillRect(x,y,1,1). Точки и без того расположены плотно. Для другого угла (альфа) те линии только мешают.)

Другой пример фрактала, который можно нарисовать тем же алгоритмом - Дракон Хартера-Хейтуэя (придуманный тремя умными дядьками из NASA). Собственно, это та-же кривая Леви, только начиная со второй итерации (на первой у нас только один угол) чередуем углы - 45° и -45°

фрактал

Следующая итерация:

фрактал

18 итераций:

фрактал
http://fractal.facegenetic.com/0.785398/0.707106/-0.785398/0.707106
(ЧПУ: угол/косинус угла/следующий угол/косинус следующего угла. На серваке строка парсится, формируются два массива - один с углами, другой с коэффициентами и передаются обратно в браузер, где клиентская часть на JS рисует фрактал. Клиентская часть реализована так, что в функцию можно передать любое количество углов.)

1-2 угла - это скучно и не интересно. Есть вот, например, старая реализация алгоритма (2010 год), на Action Script. Делал очень не аккуратно, без рекурсий и с непонятной логикой (взял старый исходник на VB и переписал на AS), но зато можно менять угол с помощью мышки:

http://fractal.facegenetic.com/levi.swf - Кривая Леви
http://fractal.facegenetic.com/harter.swf - Дракон Хартера-Хейтуэя
Исходники здесь: http://fractal.facegenetic.com/frac.txt

Что еще можно сделать? Можно добавить больше углов. Например, 120, 30, -60, 60 - получаем вот такой вот "корешок":

фрактал
http://fractal.facegenetic.com/2.0944/-0.5/0.523599/0.866025/-1.0472/0.5/1.0472/0.5/

В динамике:
фрактал
Тут я меняю 2 из 4х углов на +0.05 (второй на -0.05) радиан.
Изменяя немножко угол получаем совершенно другой фрактал. Отлично. Углы будут у нас генами. Чтобы не искать их вручную - прикрутим генетический алгоритм. Прикрутим?

Для начала создадим популяцию. 100 особей, скажем (вообще, хватит и 20 особей. Чем меньше популяция - тем меньше отбор надо производить, но вместе с тем теряется разнообразие).

исходники генетических алгоритмов

Делаем популяцию размером $populationSize особей. У каждой особи есть от 4-х до 16 генов (зачем нам ограничиваться статическим количеством углов? Пущай оно все будет в динамике))). Каждый ген - это пара угол/косинус.
Ключ "fitness" - коэффициент приспособленности отдельно взятой особи, с помощью которого мы будет решать, уничтожить особь (если коэффициент слишком низкий) или размножить (если коэффициент выше, чем у других особей).


Отбор будем производить следующим образом. Пользователю выдается два рандомных фрактала и дальше пользователь решает, какой фрактал ему больше нравится (аяксом отправляем номер фрактала на сервер, там делаем array[fitness]++ и отдаем пользователю другие два рандомных фрактала). Выглядит это вот так:

фрактал

Когда начинают появляться одни и те же фракталы, можно нажать "Запустить механизм отбора". Происходит следующее.

исходники генетических алгоритмов

Берем наш массив с популяцией, сортируем по ключу "fitness" (не приспособленных в начало массива, приспособленных - в конец). Далее делим массив пополам:

исходники генетических алгоритмов

Дальше, как я тут ни старался сделать аккуратно, в итоге все равно наговнокодил. Поэтому, как есть:

исходники генетических алгоритмов

Берем двух предков из лучшей популяции ($bestpopulation), проверяем совпадает ли количество генов (чтобы не скрещивать собаку с обезьяной). Если количество генов совпадает - берем рандомные гены у одного предка и рандомные гены у второго предка. Формируем двух потомков. В итоге получаем новую популяцию, которая наполовину состоит из приспособленных предков и наполовину из потомков этих предков.

Далее новая популяция у нас будет мутировать.

исходники генетических алгоритмов

Очищаем fitness. У каждой особи в новой популяции, с вероятностью 5%, может измениться один ген (if(rand(0, 19)==0){заменяем один из генов рандомным значением}).
Кроме того (и вот тут у нас самый яркий момент), с вероятность опять же 5%, у особи может измениться количество генов. Вообще, код выше - только чтобы объяснить принцип. Выглядит это более лаконично:

исходники генетических алгоритмов

Собственно вот и всё. В реализации этого алгоритма можно работать как с общей популяцией, так и создать для себя отдельную популяцию (тогда массив с популяцией будет записываться в сессию).

Пока писал это сообщение, немножко переделал алгоритм:
Увеличил размер популяции ($populationSize) до 200 особей.
Перед скрещиванием сделал сортировку приспособленных особей ($bestpopulation) по количеству генов - чтобы они повеселее скрещивались.
Количество мутаций сделал 20%.
Вообще, из-за разного количества генов у особей, приходится искать некий компромисс. Особи очень неохотно скрещиваются между собой - количество генов может изменяться в довольно широких пределах. Ну, например, одна из особей имеет очень неплохой фенотип, но количество генов не совпадает с количеством генов у других особей. Во время отбора эта особь ни с кем не скрещивается, а просто делает свою копию - размножается почкованием)). Тут варианта два:
Оставить небольшой процент мутаций. 2-3 особи через какое-то время заполняют собой всю популяцию. Мутанты погибают, поскольку не проходят отбор (качественные мутации очень редки, а с низким процентом - еще реже). Приходится производить очень утомительный отбор, пока не появится качественная мутация (может вообще показаться, что отбор не работает, а алгоритм выдает одни и те же фракталы)
Увеличить процент мутаций. Получаем больше разнообразия, но вместе с тем некоторые яркие особи могут быстро мутировать и выродиться (собственно, что и происходит. Но зато получается очень бодренько :)).

Для тех, кто дочитал эту херню - немножко фракталов на закуску:

фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал фрактал

фрактал




Здравствуйте! Ваша запись попала в топ-25 популярных записей LiveJournal для Украины. Подробнее о рейтинге читайте в Справке.

На последней динозаврика не увидел, но там есть корова, У неё на голове щенок сидит, обезьянки есть, тигрёнок

Районы, фракталы, жилые массивы...))))

Лепота!
А ещё цвет в атрибуты прикрутить - вообще арт получится :)

Какие красивые! А Вас давно не было.

О_О. Картинка, которая шевелиться, прикольная. Все остальное для меня, словно на сюмбюльском.

О!!!! Теперь я понимаю, что не жила...
Сколько впереди интересного может быть, а может и не быть

Доброе утро!

Интересная мысль! В динамике очень интересно смотрится!

Не для средних умов...

Обалдеть! Правда, немного сложновато для моего мозга:)

Вывих мозга.

Я это еще с девятого класса знаю)

Да, действительно много непонятного текста. Но, считаю, что это очень интересно.

?

Log in

No account? Create an account