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; } # Kombination von guten Werten zusätzlich anhängen? # 0 nein, sonst ja if(isset($_GET['an'])) { $an=floor($_GET['an']); } else { $an=0; } # Option welche Kurve, siehe unten if(isset($_GET['opt'])) { $opt=floor($_GET['opt']); } else { $opt=1; } if ($opt==1) { #Punkte der Kurven zufällig: $px[0]=mt_rand(50,950); $py[0]=mt_rand(50,300); $px[3]=mt_rand(50,950); $py[3]=mt_rand(50,300); $px[1]=mt_rand(50,950); $py[1]=mt_rand(50,1000); $px[2]=mt_rand(50,950); $py[2]=mt_rand(50,1000); $px[4]=mt_rand(50,950); $py[4]=mt_rand(700,950); $px[7]=mt_rand(50,950); $py[7]=mt_rand(700,950); $px[5]=mt_rand(50,950); $py[5]=mt_rand(0,950); $px[6]=mt_rand(50,950); $py[6]=mt_rand(0,950); } else if ($opt==2) { # Problem Symmetrie mit zwei Ergebnissen, # gegebenenfalls falsches Ergebnis in der Mitte! $px[0]=100; $py[0]=100; $px[3]=100; $py[3]=900; $px[1]=1000; $py[1]=-200; $px[2]=1000; $py[2]=1200; $px[4]=100; $py[4]=300; $px[7]=100; $py[7]=700; $px[5]=855; $py[5]=-200; $px[6]=855; $py[6]=1200; } else if ($opt==3) { # Ähnliche Kurven 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; $px[4]=490; $py[4]=420; $px[7]=510; $py[7]=420; $px[5]=200; $py[5]=623; $px[6]=800; $py[6]=623; } else if ($opt==4) { # Ähnliche Kurven mit Symmetrie: $px[0]=300; $py[0]=400; $px[3]=700; $py[3]=400; $px[1]=400; $py[1]=1000; $px[2]=600; $py[2]=1000; $px[4]=490; $py[4]=420; $px[7]=510; $py[7]=420; $px[5]=200; $py[5]=623; $px[6]=800; $py[6]=623; } else if ($opt==5) { # Kurven mit zwei Schnittpunkten: $px[0]=100; $py[0]=100; $px[3]=900; $py[3]=100; $px[1]=300; $py[1]=1000; $px[2]=500; $py[2]=1000; $px[4]=100; $py[4]=900; $px[7]=900; $py[7]=900; $px[5]=500; $py[5]=0; $px[6]=700; $py[6]=0; } else if ($opt==6) { # Kurven mit zwei Schnittpunkten: $px[0]=50; $py[0]=70; $px[3]=800; $py[3]=100; $px[1]=1000; $py[1]=1000; $px[2]=1000; $py[2]=1000; $px[4]=200; $py[4]=900; $px[7]=950; $py[7]=930; $px[5]=0; $py[5]=0; $px[6]=0; $py[6]=0; } else if ($opt==7) { $px[0]=100; $py[0]=100; $px[3]=900; $py[3]=900; $px[1]=800; $py[1]=950; $px[2]=50; $py[2]=200; $px[4]=51; $py[4]=150; $px[7]=850; $py[7]=949; $px[5]=500; $py[5]=750; $px[6]=250; $py[6]=500; } 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; $px[4]=150; $py[4]=100; $px[7]=900; $py[7]=850; $px[5]=600; $py[5]=700; $px[6]=300; $py[6]=400; } # Schlußfolgerung: Problem immer so zerlegen, daß keine symmetrischen Kurven # untersucht werden, spart Rechenzeit und vermeidet Probleme. # Darstellung der Pfade $pfad=" \n"; # Verteilungsfunktionen 0 setzen for ($i = -1; $i <= $n; $i++) { for ($j = 0; $j <= 900; $j++) { $dv[$j][$i] =0; $uv[$j][$i] =0; $vv[$j][$i] =0; } } $dtext=''; $jk=-1; # Abstände entlang der Kurven bestimmen # Anzahl auf beide Kurven aufteilen: $anz=ceil(sqrt($anz)); for ($j = 0; $j <= $anz; $j++) { $u=$j/$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]; for ($k = 0; $k <= $anz; $k++) { # Parametrisierung c(u) durchlaufen lassen $jk=$jk+1; # Hilfsgröße, mit welcher später verhindert wird, # daß der Pfadparameter u Einfluß auf das Sortieren hat. $ai[$jk]=$jk; $v=$k/$anz; $v0=(1 - $v); $v1=$v0*$v0*$v0; $v2=3*$v*$v0*$v0; $v3=3*$v*$v*$v0; $v4=$v*$v*$v; $bx=$v1*$px[4]+$v2*$px[5]+$v3*$px[6]+$v4*$px[7]; $by=$v1*$py[4]+$v2*$py[5]+$v3*$py[6]+$v4*$py[7]; # merken, welche Punkte $ul[$jk]=$u; $vl[$jk]=$v; # Abstand berechnen $ax=$cx-$bx; $ay=$cy-$by; # Abstand merken $d[$jk]=sqrt($ax*$ax+$ay*$ay); # Gewicht als Hilfsgröße merken $ds[$jk]=1/(1+$d[$jk]); # Verteilungsfunktionen $vi=min(900,floor($d[$jk])); $dv[$vi][-1]=$dv[$vi][-1]+1; $vi=floor($ul[$jk]*500); $uv[$vi][-1]=$uv[$vi][-1]+1; $vi=floor($vl[$jk]*500); $vv[$vi][-1]=$vv[$vi][-1]+1; } } $anz=$jk; # 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, $vl); # statistik for ($j = 0; $j <= 9; $j++) { $std[$j][-1]=$d[$j]; $stu[$j][-1]=$ul[$j]; $stv[$j][-1]=$vl[$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]; $v=$vl[$j]; $v0=(1 - $v); $v1=$v0*$v0*$v0; $v2=3*$v*$v0*$v0; $v3=3*$v*$v*$v0; $v4=$v*$v*$v; $bx=$v1*$px[4]+$v2*$px[5]+$v3*$px[6]+$v4*$px[7]; $by=$v1*$py[4]+$v2*$py[5]+$v3*$py[6]+$v4*$py[7]; $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; $vls=0; for ($k = 0; $k < $m; $k++) { $ik=$is[$k]; $uls=$uls+$g[$k]*$ul[$ik]; $vls=$vls+$g[$k]*$vl[$ik]; } $ulm=$uls/$gs; $vlm=$vls/$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]; $v=$vlm; $v0=(1 - $v); $v1=$v0*$v0*$v0; $v2=3*$v*$v0*$v0; $v3=3*$v*$v*$v0; $v4=$v*$v*$v; $bx=$v1*$px[4]+$v2*$px[5]+$v3*$px[6]+$v4*$px[7]; $by=$v1*$py[4]+$v2*$py[5]+$v3*$py[6]+$v4*$py[7]; $ax=$cx-$bx; $ay=$cy-$by; $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)); $vlm=max(0,min(1,$vlm+$vari*mt_rand(-10000,10000)/10000)); } # vermeiden, daß Werte doppelt vorkommen $ok = in_array($ulm, $ul); $oj = in_array($vlm, $vl); } while ($ok AND $oj); $ul[$j]= $ulm; $vl[$j]= $vlm; } $anz=$jo; if ($an!=0) { # 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; $vl[$anz+1]=($vl[0] + $vl[1] + $vl[2])/3; $vl[$anz+2]=($vl[1] + $vl[2] + $vl[3])/3; $vl[$anz+3]=($vl[0] + $vl[2] + $vl[3])/3; $vl[$anz+4]=($vl[0] + $vl[1] + $vl[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; $vg=0; for ($j = 0; $j <= 9; $j++) { $gz=mt_rand(10,1000); $gs=$gs+$gz; $ug=$ug+$gz*$ul[$j]; $vg=$vg+$gz*$vl[$j]; } $ul[$anz+5]=$ug/$gs; $vl[$anz+5]=$vg/$gs; # Größe der Mutation abhängig vom Abstand zum bisherigen kleinsten Wert. $ulm=($ul[0]*$ds[0]+$ul[1]*$ds[1]+$ul[2]*$ds[2])/($ds[0]+$ds[1]+$ds[2]); $vlm=($vl[0]*$ds[0]+$vl[1]*$ds[1]+$vl[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]; $v=$vlm; $v0=(1 - $v); $v1=$v0*$v0*$v0; $v2=3*$v*$v0*$v0; $v3=3*$v*$v*$v0; $v4=$v*$v*$v; $bx=$v1*$px[4]+$v2*$px[5]+$v3*$px[6]+$v4*$px[7]; $by=$v1*$py[4]+$v2*$py[5]+$v3*$py[6]+$v4*$py[7]; $ax=$cx-$bx; $ay=$cy-$by; $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)); $vlm=max(0,min(1,$vlm+$vari*mt_rand(-10000,10000)/10000)); $ul[$anz+6]=$ulm; $vl[$anz+6]=$vlm; $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]; $v=$vl[$j]; $v0=(1 - $v); $v1=$v0*$v0*$v0; $v2=3*$v*$v0*$v0; $v3=3*$v*$v*$v0; $v4=$v*$v*$v; $bx=$v1*$px[4]+$v2*$px[5]+$v3*$px[6]+$v4*$px[7]; $by=$v1*$py[4]+$v2*$py[5]+$v3*$py[6]+$v4*$py[7]; $ax=$cx-$bx; $ay=$cy-$by; $d[$j]=sqrt($ax*$ax+$ay*$ay); $ds[$j]=1/(1+$d[$j]); if ($j>=$ja) { # Verteilungsfunktionen $vi=min(900,floor($d[$j])); $dv[$vi][$i]=$dv[$vi][$i]+1; $vi=floor($ul[$j]*500); $uv[$vi][$i]=$uv[$vi][$i]+1; $vi=floor($vl[$j]*500); $vv[$vi][$i]=$vv[$vi][$i]+1; } } $dtext.="$i: A 0: $d[0] u: $ul[0] v: $vl[0] |"; $dtext.=" A 1: $d[1] u: $ul[1] v: $vl[0] |"; $dtext.=" A 2: $d[2] u: $ul[2] v: $vl[0] | \n"; # Und wieder so sortieren, daß die Punkte mit kleinsten Abständen vorne stehen: shuffle($ai); array_multisort($d, $ai, $ul, $vl); # statistik for ($j = 0; $j <= 9; $j++) { $std[$j][$i]=$d[$j]; $stu[$j][$i]=$ul[$j]; $stv[$j][$i]=$vl[$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]; $v=$vl[$j]; $v0=(1 - $v); $v1=$v0*$v0*$v0; $v2=3*$v*$v0*$v0; $v3=3*$v*$v*$v0; $v4=$v*$v*$v; $bx=$v1*$px[4]+$v2*$px[5]+$v3*$px[6]+$v4*$px[7]; $by=$v1*$py[4]+$v2*$py[5]+$v3*$py[6]+$v4*$py[7]; $ax=$cx-$bx; $ay=$cy-$by; $dj=sqrt($ax*$ax+$ay*$ay); $pmin.=" \n"; } $pmin.="Abstand: $d[0]; Position: $ul[0], $vl[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]; $v=$vl[0]; $v0=(1 - $v); $v1=$v0*$v0*$v0; $v2=3*$v*$v0*$v0; $v3=3*$v*$v*$v0; $v4=$v*$v*$v; $bx=$v1*$px[4]+$v2*$px[5]+$v3*$px[6]+$v4*$px[7]; $by=$v1*$py[4]+$v2*$py[5]+$v3*$py[6]+$v4*$py[7]; $pmin.=" "; # viewBox berechnen, damit man per Klick auf den Ergebnispunkt vergrößern kann: # Mitte $ax=($bx+$cx)/2; $ay=($by+$cy)/2; #$pmin.=""; # Abstand $dx=($bx-$cx); $dy=($by-$cy); $dd=ceil(sqrt($dx*$dx+$dy*$dy)+5/2); $ddd=2*$dd; $vx= round($ax) - $dd; $vy= round($ay) - $dd; $viewBox="$vx $vy $ddd $ddd"; # viewBox Kurve 1: $vx= round($cx) - 5; $vy= round($cy) - 5; $viewBox1="$vx $vy 10 10"; # viewBox Kurve 2: $vx= round($bx) - 5; $vy= round($by) - 5; $viewBox2="$vx $vy 10 10"; # Verteilungsfunktionen $hmax=100; $humax=100; $hvmax=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); $vu.="\n"; for ($j = 0; $j <= 500; $j++) { $x=2*$j; $hu=5*$uv[$j][$i]; $hv=5*$vv[$j][$i]; $humax=max($humax, $hu); $hvmax=max($hvmax, $hv); if ($hu>0) { $vu.="\n"; } if ($hv>0) { $vu.="\n"; } } $vu.="\n"; $vf.="\n"; for ($j = 0; $j <= 900; $j++) { $x=$j; $h=$dv[$j][$i]; $hmax=max($hmax, $h); if ($h>0) { $vf.="\n"; $xmin=min($xmin, $x); $xmax=max($xmax, $x); } } $vf.="\n"; } $hmax=$hmax+100; $humax=$humax+100; $hvmax=$hvmax+100; $huvm=$humax+$hvmax; $xmin=max(0,$xmin-100); $xdiff=$xmax-$xmin+100; $xk=$xmin+20; $pd=''; $pu=''; $pv=''; for ($j = 0; $j <= 9; $j++) { $fr=round(50*($j/9)+150); $pd.="\n"; $pu.="' />\n"; $pv.="' />\n"; } $vf.="$pd \n"; $vu.="$pu $pv \n"; # Ausgabe raushauen: # svg-header senden: $content="Content-type: image/svg+xml"; header($content); # xml-Zeile ausgeben echo ""; # und jetzt das Dokument ?>