Вот тут эта бяка: 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.86602 ... .0472/0.5/ В динамике: Тут я меняю 2 из 4х углов на +0.05 (второй на -0.05) радиан. Изменяя немножко угол получаем совершенно другой фрактал. Отлично. Углы будут у нас генами. Чтобы не искать их вручную - прикрутим генетический алгоритм. Прикрутим? Для начала создадим популяцию. 100 особей, скажем (вообще, хватит и 20 особей. Чем меньше популяция - тем меньше отбор надо производить, но вместе с тем теряется разнообразие). Код (PHP): for($i=0;$i<$populationSize;$i++){ for($j=0;$j<rand(3,15);$j++){ $population[$i][$j][0]=rand(-32766, 1)*M_PI/32767; $population[$i][$j][1]=cos($population[$i][$j][0]); } $population[$i]["fitness"]=0; } Делаем популяцию размером $populationSize особей. У каждой особи есть от 4-х до 16 генов (зачем нам ограничиваться статическим количеством углов? Пущай оно все будет в динамике))). Каждый ген - это пара угол/косинус. Ключ "fitness" - коэффициент приспособленности отдельно взятой особи, с помощью которого мы будет решать, уничтожить особь (если коэффициент слишком низкий) или размножить (если коэффициент выше, чем у других особей). Отбор будем производить следующим образом. Пользователю выдается два рандомных фрактала и дальше пользователь решает, какой фрактал ему больше нравится (аяксом отправляем номер фрактала на сервер, там делаем array[fitness]++ и отдаем пользователю другие два рандомных фрактала). Выглядит это вот так: Когда начинают появляться одни и те же фракталы, можно нажать "Запустить механизм отбора". Происходит следующее. Код (PHP): $by = 'fitness'; usort($population, function($first, $second) use($by){ if ($first[$by]>$second[$by]) {return 1;} elseif ($first[$by]<$second[$by]) {return -1;} return 0; }); Берем наш массив с популяцией, сортируем по ключу "fitness" (не приспособленных в начало массива, приспособленных - в конец). Далее делим массив пополам: Код (PHP): $bestpopulation=array_slice($population, $hsize); shuffle($bestpopulation); Дальше, как я тут ни старался сделать аккуратно, в итоге все равно наговнокодил. Поэтому, как есть: Код (PHP): $hsize=(int)$populationSize/2; $hhsize=(int)$populationSize/4; for($i=0; $i<$hhsize; $i++){ $i1=$i; $i2=$i+$hhsize; $len1=count($bestpopulation[$i1]); $len2=count($bestpopulation[$i2]); if($len1==$len2){ foreach($bestpopulation[$i1] as $key=>$value){ if(rand(0,1)==1){ $population[$i1][$key]=$value; $population[$i2][$key]=$bestpopulation[$i2][$key]; }else{ $population[$i2][$key]=$value; $population[$i1][$key]=$bestpopulation[$i2][$key]; } } }else{ $population[$i1]=$bestpopulation[$i1]; $population[$i2]=$bestpopulation[$i2]; } } Берем двух предков из лучшей популяции ($bestpopulation), проверяем совпадает ли количество генов (чтобы не скрещивать собаку с обезьяной). Если количество генов совпадает - берем рандомные гены у одного предка и рандомные гены у второго предка. Формируем двух потомков. В итоге получаем новую популяцию, которая наполовину состоит из приспособленных предков и наполовину из потомков этих предков. Далее новая популяция у нас будет мутировать. Код (PHP): for($i=0;$i<$populationSize;$i++){ unset($population[$i]['fitness']); $mutate=rand(0, 19); if($mutate==0){ $key=rand(0, count($population[$i])-1); $population[$i][$key][0]=rand(-32766, 1)*M_PI/32767; $population[$i][$key][1]=cos($population[$i][$key][0]); } if($mutate==1){ $add=rand(0,1); if($add==1){ if(count($population[$i])<16){ $ploidy[0]=rand(-32766, 1)*M_PI/32767; $ploidy[1]=cos($ploidy[0]); array_push($population[$i], $ploidy); } }else{ if(count($population[$i])>3){ array_pop($population[$i]); } } } $population[$i]['fitness']=0; } Очищаем fitness. У каждой особи в новой популяции, с вероятностью 5%, может измениться один ген (if(rand(0, 19)==0){заменяем один из генов рандомным значением}). Кроме того (и вот тут у нас самый яркий момент), с вероятность опять же 5%, у особи может измениться количество генов. Вообще, код выше - только чтобы объяснить принцип. Выглядит это более лаконично: Код (PHP): for($i=0;$i<$populationSize;$i++){ unset($population[$i]['fitness']); $mutate=rand(0, 9); if($mutate==0){ $ploidy[0][0]=rand(-32766, 1)*M_PI/32767; $ploidy[0][1]=cos($ploidy[0][0]); array_splice($population[$i], rand(0, count($population[$i])), rand(0,2), $ploidy); } $population[$i]['fitness']=0; } Собственно вот и всё. В реализации этого алгоритма можно работать как с общей популяцией, так и создать для себя отдельную популяцию (тогда массив с популяцией будет записываться в сессию). Пока писал это сообщение, немножко переделал алгоритм: Увеличил размер популяции ($populationSize) до 200 особей. Перед скрещиванием сделал сортировку приспособленных особей ($bestpopulation) по количеству генов - чтобы они повеселее скрещивались. Количество мутаций сделал 20%. Вообще, из-за разного количества генов у особей, приходится искать некий компромисс. Особи очень неохотно скрещиваются между собой - количество генов может изменяться в довольно широких пределах. Ну, например, одна из особей имеет очень неплохой фенотип, но количество генов не совпадает с количеством генов у других особей. Во время отбора эта особь ни с кем не скрещивается, а просто делает свою копию - размножается почкованием)). Тут варианта два: Оставить небольшой процент мутаций. 2-3 особи через какое-то время заполняют собой всю популяцию. Мутанты погибают, поскольку не проходят отбор (качественные мутации очень редки, а с низким процентом - еще реже). Приходится производить очень утомительный отбор, пока не появится качественная мутация (может вообще показаться, что отбор не работает, а алгоритм выдает одни и те же фракталы) Увеличить процент мутаций. Получаем больше разнообразия, но вместе с тем некоторые яркие особи могут быстро мутировать и выродиться (собственно, что и происходит. Но зато получается очень бодренько ). Для тех, кто дочитал эту херню - немножко фракталов на закуску: