Геометрические фракталы и немножко генетики :)
Вот тут эта бяка: 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 особи через какое-то время заполняют собой всю популяцию. Мутанты погибают, поскольку не проходят отбор (качественные мутации очень редки, а с низким процентом - еще реже). Приходится производить очень утомительный отбор, пока не появится качественная мутация (может вообще показаться, что отбор не работает, а алгоритм выдает одни и те же фракталы)
Увеличить процент мутаций. Получаем больше разнообразия, но вместе с тем некоторые яркие особи могут быстро мутировать и выродиться (собственно, что и происходит. Но зато получается очень бодренько :)).
Для тех, кто дочитал эту херню - немножко фракталов на закуску:
Не забываем нажать сюда
Под катом много картинок и непонятного текста :)
В двух словах.
Есть один такой чудный алгоритм, который мне впервые попался в августе 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 особи через какое-то время заполняют собой всю популяцию. Мутанты погибают, поскольку не проходят отбор (качественные мутации очень редки, а с низким процентом - еще реже). Приходится производить очень утомительный отбор, пока не появится качественная мутация (может вообще показаться, что отбор не работает, а алгоритм выдает одни и те же фракталы)
Увеличить процент мутаций. Получаем больше разнообразия, но вместе с тем некоторые яркие особи могут быстро мутировать и выродиться (собственно, что и происходит. Но зато получается очень бодренько :)).
Для тех, кто дочитал эту херню - немножко фракталов на закуску:
