10, <=2000) if(isset($_GET['anz'])) { $anz=min(2000,max(11, floor($_GET['anz']))); } else { $anz=200; } # Anzahl der Durchläufe des genetischen Algorithmus (> 3; <=200) if(isset($_GET['n'])) { $n=min(200,max(4, floor($_GET['n']))); } else { $n=20; } # Anzahl der Mutanten-Eltern (<=$anz) if(isset($_GET['m'])) { $m=min($anz,max(2, floor($_GET['m']))); } else { $m=5; } # Wieviele Punkten hinzukommen? (zwischen 1 und $anz) if(isset($_GET['dazu'])) { $dazu=min($anz,max(1, floor($_GET['dazu']))); } else { $dazu=min($anz,max(1,floor(0.1*$anz))); } # Gewicht eines Mutationsbeitrages auswählen # 1: nach Abstand 1/(1+d) # 2: Mischung Abstand und Zufall # sonst: Zufall if(isset($_GET['gew'])) { $gew=floor($_GET['gew']); } else { $gew=0; } # Laufparameter bei Mutanten zufällig leicht variieren? # 0 nein, sonst ja if(isset($_GET['uvar'])) { $uvar=floor($_GET['uvar']); } else { $uvar=0; } # Option welche Kurve, siehe unten if(isset($_GET['opt'])) { $opt=floor($_GET['opt']); } else { $opt=1; } if ($opt==1) { #Punkte der Kurve zufällig: for ($j = 0; $j <= 3; $j++) { $px[$j]=mt_rand(50,950); $py[$j]=mt_rand(50,950); } } else if ($opt==2) { # Problem Symmetrie mit zwei Punkten als Ergebnis, # gegebenenfalls falsches Ergebnis in der Mitte! $px[0]=100; $py[0]=100; $px[3]=100; $py[3]=900; $px[1]=1284.18; $py[1]=-400; $px[2]=1284.18; $py[2]=1400; } else if ($opt==3) { # Ähnliche Kurve mit Symmetrie: $px[0]=100; $py[0]=100; $px[3]=900; $py[3]=100; $px[1]=1600; $py[1]=804.89; $px[2]=-600; $py[2]=804.89; } else if ($opt==4) { # Ähnliche Kurve mit Symmetrie: $px[0]=400; $py[0]=400; $px[3]=600; $py[3]=400; $px[1]=400; $py[1]=1000; $px[2]=600; $py[2]=1000; } else { $px[0]=100; $py[0]=100; $px[3]=900; $py[3]=900; $px[1]=800; $py[1]=950; $px[2]=50; $py[2]=200; } # Schlußfolgerung: Problem immer so zerlegen, daß keine symmetrischen Kurven # untersucht werden, spart Rechenzeit und vermeidet Probleme. # einzelner Punkt, zu dem der Abstand bestimmt werden soll: $px[4]=500; $py[4]=500; # Darstellung Pfad und Punkt $pfad=" \n"; $punkt=" \n"; # Verteilungsfunktionen 0 setzen for ($i = -1; $i <= $n; $i++) { for ($j = 0; $j <= 500; $j++) { $dv[$j][$i] =0; $uv[$j][$i] =0; } } $dtext=''; # Abstände entlang der Kurve bestimmen for ($j = 0; $j <= $anz; $j++) { # Parametrisierung c(u) durchlaufen lassen $u=$j/$anz; # Hilfsgröße, mit welcher später verhindert wird, # daß der Pfadparameter u Einfluß auf das Sortieren hat. $ai[$j]=$j; $u0=(1 - $u); $u1=$u0*$u0*$u0; $u2=3*$u*$u0*$u0; $u3=3*$u*$u*$u0; $u4=$u*$u*$u; $cx=$u1*$px[0]+$u2*$px[1]+$u3*$px[2]+$u4*$px[3]; $cy=$u1*$py[0]+$u2*$py[1]+$u3*$py[2]+$u4*$py[3]; # merken, welcher Punkt $ul[$j]=$u; # Abstand berechnen $ax=$cx-$px[4]; $ay=$cy-$py[4]; # Abstand merken $d[$j]=sqrt($ax*$ax+$ay*$ay); # Gewicht als Hilfsgröße merken $ds[$j]=1/(1+$d[$j]); # Verteilungsfunktionen $vi=min(500,floor($d[$j])); $dv[$vi][-1]=$dv[$vi][-1]+1; $vi=floor($ul[$j]*500); $uv[$vi][-1]=$uv[$vi][-1]+1; } # Hilfsgröße ai zufällig mischen, # so ist bei nächsten Sortierschritt gewährleistet, # daß gleichweit entfernte Punkte in verschiedenen # Umläufen nicht immer in der gleichen Reihenfolge stehen. shuffle($ai); # Sortieren, Punkte mit kleinsten Abstand nach vorne, # hinten kann dann einfach aussortiert werden. array_multisort($d, $ai, $ul); # statistik for ($j = 0; $j <= 9; $j++) { $std[$j][-1]=$d[$j]; $stu[$j][-1]=$ul[$j]; } # Ab hier wird optimiert, es werden jeweils die Punkte # mit den größten Abständen durch solche ersetzt, welche # mit verschiedenen Algorithmen aus Punkten mit kleineren # Abständen geraten wurden. # Zeichenkette Ausgabe beste Punkte pro Durchlauf $pmin=''; # Anfangsradius für Malpunkt $cr=1; $cfak=pow(0.1,1/$n); for ($i = 0; $i <= $n; $i++) { # Größenänderung des Malpunktes pro Generation $cr=$cr*$cfak; # Farbe des Malpunktes pro Generation $fib=100*(1-0.5*$i/$n); $fig=100*(1-$i/$n); $fir=100*($i/$n); $rgb="$fir%,$fig%,$fib%"; # die zehn besten Punkte ausgeben $cj=1; for ($j = 0; $j <= 9; $j++) { $cj=$cj*1.05; $cc=$cj*$cr; $u=$ul[$j]; $u0=(1 - $u); $u1=$u0*$u0*$u0; $u2=3*$u*$u0*$u0; $u3=3*$u*$u*$u0; $u4=$u*$u*$u; $cx=$u1*$px[0]+$u2*$px[1]+$u3*$px[2]+$u4*$px[3]; $cy=$u1*$py[0]+$u2*$py[1]+$u3*$py[2]+$u4*$py[3]; $pmin.=" \n"; } # Mit zufälligen Rekombinationen und Mutationen ergänzen: $ja=$anz +1; $jo=$anz +$dazu; # Array machen: for ($j = 0; $j <= $anz; $j++) { $ia[$j]=$j; } for ($j = $ja; $j <= $jo; $j++) { $ai[$j]=$j; do { # m Pfadpunkte zufällig auswählen $is = array_rand($ia, $m); $gs=0; for ($k = 0; $k < $m; $k++) { if ($gew==1) { # Gewicht nach Abstand $ik=$is[$k]; $g[$k]=$ds[$ik]; } else if ($gew==2) { # Gewicht nach Abstand und Zufall $ik=$is[$k]; $g[$k]=$ds[$ik]*mt_rand(10,1000)/1000; } else { # Gewicht zufällig $g[$k]=mt_rand(10,1000)/1000; } $gs=$gs+$g[$k]; } $uls=0; for ($k = 0; $k < $m; $k++) { $ik=$is[$k]; $uls=$uls+$g[$k]*$ul[$ik]; } $ulm=$uls/$gs; # Mutation if ($uvar!=0) { $u=$ulm; $u0=(1 - $u); $u1=$u0*$u0*$u0; $u2=3*$u*$u0*$u0; $u3=3*$u*$u*$u0; $u4=$u*$u*$u; $cx=$u1*$px[0]+$u2*$px[1]+$u3*$px[2]+$u4*$px[3]; $cy=$u1*$py[0]+$u2*$py[1]+$u3*$py[2]+$u4*$py[3]; $ax=$cx-$px[4]; $ay=$cy-$py[4]; $dulm=sqrt($ax*$ax+$ay*$ay); # Größe der Mutation abhängig vom Abstand zum bisherigen kleinsten Wert. $vari=(abs($dulm-$d[0])+0.001*$d[0])*$ds[0]; $ulm=max(0,min(1,$ulm+$vari*mt_rand(-10000,10000)/10000)); } # vermeiden, daß Werte doppelt vorkommen $ok = in_array($ulm, $ul); } while ($ok); $ul[$j]= $ulm; } $anz=$jo; # Mittelwert von jeweils drei guten Punkten hinten eintragen $ul[$anz+1]=($ul[0] + $ul[1] + $ul[2])/3; $ul[$anz+2]=($ul[1] + $ul[2] + $ul[3])/3; $ul[$anz+3]=($ul[0] + $ul[2] + $ul[3])/3; $ul[$anz+4]=($ul[0] + $ul[1] + $ul[3])/3; $ai[$anz+1]=$anz+1; $ai[$anz+2]=$anz+2; $ai[$anz+3]=$anz+3; $ai[$anz+4]=$anz+4; $ai[$anz+5]=$anz+5; $ai[$anz+6]=$anz+6; # und zufällig gewichtetes Mittel über die 10 besten Punkte: $gs=0; $ug=0; for ($j = 0; $j <= 9; $j++) { $gz=mt_rand(10,1000); $gs=$gs+$gz; $ug=$ug+$gz*$ul[$j]; } $ul[$anz+5]=$ug/$gs; # Größe der Mutation abhängig vom Abstand zum bisherigen kleinsten Wert. $ulm=($u[0]*$ds[0]+$u[1]*$ds[1]+$u[2]*$ds[2])/($ds[0]+$ds[1]+$ds[2]); $u=$ulm; $u0=(1 - $u); $u1=$u0*$u0*$u0; $u2=3*$u*$u0*$u0; $u3=3*$u*$u*$u0; $u4=$u*$u*$u; $cx=$u1*$px[0]+$u2*$px[1]+$u3*$px[2]+$u4*$px[3]; $cy=$u1*$py[0]+$u2*$py[1]+$u3*$py[2]+$u4*$py[3]; $ax=$cx-$px[4]; $ay=$cy-$py[4]; $dulm=sqrt($ax*$ax+$ay*$ay); $vari=(abs($dulm-$d[0])+0.001*$d[0])*$ds[0]; $ulm=max(0,min(1,$ulm+$vari*mt_rand(-10000,10000)/10000)); $ul[$anz+6]=$ulm; $anz=$anz+6; # Für die Punkte Abstände und Verteilungsfunktion bestimmen: for ($j = 0; $j <= $anz; $j++) { $u=$ul[$j]; $u0=(1 - $u); $u1=$u0*$u0*$u0; $u2=3*$u*$u0*$u0; $u3=3*$u*$u*$u0; $u4=$u*$u*$u; $cx=$u1*$px[0]+$u2*$px[1]+$u3*$px[2]+$u4*$px[3]; $cy=$u1*$py[0]+$u2*$py[1]+$u3*$py[2]+$u4*$py[3]; $ax=$cx-$px[4]; $ay=$cy-$py[4]; $d[$j]=sqrt($ax*$ax+$ay*$ay); $ds[$j]=1/(1+$d[$j]); if ($j>=$ja) { # Verteilungsfunktionen $vi=min(500,floor($d[$j])); $dv[$vi][$i]=$dv[$vi][$i]+1; $vi=floor($ul[$j]*500); $uv[$vi][$i]=$uv[$vi][$i]+1; } } $dtext.="$i: A 0: $d[0] u: $ul[0] |"; $dtext.=" A 1: $d[1] u: $ul[1] |"; $dtext.=" A 2: $d[2] u: $ul[2] |"; $dtext.=" A 3: $d[3] u: $ul[3] |"; $dtext.=" A 4: $d[4] u: $ul[4] |"; $dtext.=" A 5: $d[5] u: $ul[5] \n"; # Und wieder so sortieren, daß die Punkte mit kleinsten Abständen vorne stehen: shuffle($ai); array_multisort($d, $ai, $ul); # statistik for ($j = 0; $j <= 9; $j++) { $std[$j][$i]=$d[$j]; $stu[$j][$i]=$ul[$j]; } } # Die besten finalen Punkte ausgeben for ($j = 0; $j <= 9; $j++) { $u=$ul[$j]; $u0=(1 - $u); $u1=$u0*$u0*$u0; $u2=3*$u*$u0*$u0; $u3=3*$u*$u*$u0; $u4=$u*$u*$u; $cx=$u1*$px[0]+$u2*$px[1]+$u3*$px[2]+$u4*$px[3]; $cy=$u1*$py[0]+$u2*$py[1]+$u3*$py[2]+$u4*$py[3]; $ax=$cx-$px[4]; $ay=$cy-$py[4]; $dj=sqrt($ax*$ax+$ay*$ay); $pmin.=" \n"; } $pmin.="Abstand: $d[0]; Position: $ul[0] "; # Der erste Punkt der Liste muß der mit dem kleinsten gefundenen Abstand sein, # dieser wird als Ergebnis nochmal extra gekennzeichnet. $u=$ul[0]; $u0=(1 - $u); $u1=$u0*$u0*$u0; $u2=3*$u*$u0*$u0; $u3=3*$u*$u*$u0; $u4=$u*$u*$u; $cx=$u1*$px[0]+$u2*$px[1]+$u3*$px[2]+$u4*$px[3]; $cy=$u1*$py[0]+$u2*$py[1]+$u3*$py[2]+$u4*$py[3]; $pmin.="\n"; $pmin.="\n"; $pmin.=" \n"; # viewBox berechnen, damit man per Klick auf den Ergebnispunkt vergrößern kann: $vx= round($cx) - 5; $vy= round($cy) - 5; $viewBox="$vx $vy 10 10"; # eine zehnfach größere viewBox: $vx= round($cx) - 50; $vy= round($cy) - 50; $viewBox2="$vx $vy 100 100"; # Verteilungsfunktionen $hmax=100; $humax=100; $xmin=10000; $xmax=0; $vf=' '; $vu=' '; for ($i = -1; $i <= $n; $i++) { $fr=round(255*($i+1)/($n+2)); $fb=round(255*(1-($i+1)/($n+2))); $fi="rgb($fr,$fb,0)"; $fo=round(1-0.8*($i+1)/($n+2),3); $vf.="\n"; $vu.="\n"; for ($j = 0; $j <= 500; $j++) { $x=2*$j; $h=$dv[$j][$i]; $hu=$uv[$j][$i]; $hmax=max($hmax, $h); $humax=max($humax, $hu); if ($h>0) { $vf.="\n"; $xmin=min($xmin, $x); $xmax=max($xmax, $x); } if ($hu>0) { $vu.="\n"; } } $vf.="\n"; $vu.="\n"; } $hmax=$hmax+100; $humax=$humax+100; $xmin=max(0,$xmin-100); $xdiff=$xmax-$xmin+100; $xk=$xmin+20; $pd=''; $pu=''; for ($j = 0; $j <= 9; $j++) { $fr=round(50*($j/9)+150); $pd.="\n"; $pu.="' />\n"; } $vf.="$pd \n"; $vu.="$pu \n"; # Ausgabe raushauen: # svg-header senden: $content="Content-type: image/svg+xml"; header($content); # xml-Zeile ausgeben echo ""; # und jetzt das Dokument ?>