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; <=100) if(isset($_GET['n'])) { $n=min(100,max(4, floor($_GET['n']))); } else { $n=20; } # Wieviele Punkten hinten sollen weg? (zwischen 1 und $anz -10) if(isset($_GET['weg'])) { $weg=min($anz-10,max(1, floor($_GET['weg']))); } else { $weg=min($anz-10,max(1,floor(0.25*$anz))); } 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.14; $py[1]=-400; $px[2]=1284.14; $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=" Pfad, Anklickern: Vergrößern des Ergebnisses \n"; $punkt=" Punkt, Knopf zum Anklickern: Vergrößern des Ergebnisses \n"; # Verteilungsfunktionen 0 setzen for ($i = -1; $i <= $n; $i++) { for ($j = 0; $j <= 500; $j++) { $dv[$j][$i] =0; $uv[$j][$i] =0; } } # Abstände entlang der Kurve bestimmen for ($j = 0; $j <= $anz; $j++) { # Parametrisierung c(u) durchlaufen lassen $u=$j/$anz; $ai[$j]=mt_rand(-100*$anz,100*$anz); $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; } # Sortieren, Punkte mit kleinsten Abstand nach vorne, # hinten kann dann einfach aussortiert werden. array_multisort($d, $ai, $ul); # 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; for ($i = 0; $i <= $n; $i++) { # Größenänderung des Malpunktes pro Generation $cr=$cr*0.9; # 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 $tausch=9; $cj=1; for ($j = 0; $j <= $tausch; $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.=" Abstand $d[$j] \n"; } # Mit zufälligen Mutationen auffüllen: $ja=$anz-$weg; $jo=$ja-1; # Array machen: for ($j = 0; $j <= $jo; $j++) { $ia[$j]=$j; } for ($j = $ja; $j <= $anz; $j++) { # 5 Pfadpunkte zufällig auswählen $is = array_rand($ia, 2); $i0=$is[0]; $i1=$is[1]; $g0=mt_rand(100,1000); $g1=mt_rand(100,1000); $ul[$j]=($g0*$ul[$i0] + $g1*$ul[$i1])/($g1+$g0); } # Für die Punkte Abstände und Verteilungsfunktion bestimmen: for ($j = 0; $j <= $anz; $j++) { $ai[$j]=mt_rand(-100*$anz,100*$anz); $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]); # 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; } # Und wieder so sortieren, daß die Punkte mit kleinsten Abständen vorne stehen: array_multisort($d, $ai, $ul); } # Die besten finalen Punkte ausgeben for ($j = 0; $j <= $tausch; $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); $pmin.=" Abstand $d[$j] \n"; } # 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.=" Abstand $d[0]; Knopf zum Einblenden der Kurve \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"; } $vf.="\n"; $vu.="\n"; $hmax=$hmax+100; $humax=$humax+100; $xmin=max(0,$xmin-100); $xdiff=$xmax-$xmin+100; $xk=$xmin+20; # Ausgabe raushauen: # svg-header senden: $content="Content-type: image/svg+xml"; header($content); # xml-Zeile ausgeben echo ""; # und jetzt das Dokument ?> Minimaler Abstand Kurve - Punkt Mit einem genetischen oder evolutionären Algorithmus wird bestimmt, welcher Punkt der blauen Kurve dem roten Punkt am nächsten kommt. Eine Verteilungsfunktion des Abstandes kann eingeblendet werden, indem der kleine grüne Knopf gedrückt wird. Entsprechend gibt es eine Verteilungsfunktion für den Laufparameter mit dem kleinen gelben Knopf. Bei einem breiten Bildschirm ist die aber ohnehin zu sehen. Zurück geht es jeweils mit dem hellblauen Knopf. Pro Durchlauf gibt es jeweils eine Verteilung. Diese werden übereinandergelegt. Jeder Durchlauf bekommt eine andere Farbe und Teiltransparenz, der erste Durchlauf hellgrün und nicht transparent, der letzte rot und halbtransparent. Bei der Verteilungsfunktion für den Laufparameter sollte der Algorithmus gut funktionieren, wenn es einen deutlichen roten Häufungspunkt gibt. Bei der Verteilungsfunktion für den Abstand sollte es einen sehr schmalen und hohen Ausschlag links geben und rechts davon kein rot mehr. Die grünen Verteilungen sind hingegen recht breit zu erwarten. Eine Vergrößerung des Bereiches rund um das Ergebnis kann erreicht werden, indem der rote Punkt angeklickert wird. Noch größer geht es, wenn die blaue Kurve angeklickert wird. Zurück geht es, wenn der schwarz gerandete Ergebnispunkt auf der Kurve angeklickert wird. GET-Parameter: anz - Anzahl der Testpunkte (> 10, <2001) n - Anzahl der Generationen (> 3, <101) weg - Anzahl der ersetzten Testpunkte (zwischen 1 und anz -10) opt - Welche Kurve - 0 zufällig, sonst Kurven mit mehr als einem Maximum, die problematisch für den Algorithmus sind " begin="vf.click" /> Knopf zum Einblenden der Verteilungsfunktion des Abstandes Knopf zum Einblenden der Verteilungsfunktion des Laufparameters Knopf zum Einblenden der Kurve Knopf zum Einblenden der Kurve