<?php

/*
SYNOPSIS:
 evola.php [ausgluehen|zufall|schwellenwert] maxDurchlaeufe [Starttemp|Schwellenwert]
*/

$modus   = $argv[1];          // ausgluehen, zufall oder schwellenwert
$T       = intval($argv[3]);  // Starttemperatur (für $modus=ausgluehen)
$PHI     = intval($argv[3]);  // Schwellenwert
$maxRuns = intval($argv[2]);  // maximale Generationen

$strecken = array(
	'1_2' => 5,
	'1_3' => 8,
	'1_4' => 11,
	'1_5' => 3,
	'1_6' => 7,
	'2_3' => 10,
	'2_4' => 4,
	'2_5' => 9,
	'2_6' => 12,
	'3_4' => 6,
	'3_5' => 17,
	'3_6' => 8,
	'4_5' => 6,
	'4_6' => 5,
	'5_6' => 11,
);

$kandidatA = array(6,4,1,5,3,2);
shuffle($kandidatA);

$loesungen   = array();
$loesungen[] = $kandidatA;
$maxDiff     = -20000; // Merkvariable für Ausglühen

for ($runs = 0; $runs < $maxRuns; ++$runs) {
	$fittnessA = bewerte(end($loesungen)); // A(t-1).F
	$kandidatB = mutation(end($loesungen));
	$fittnessB = bewerte($kandidatB); // B.F
	
	if (akzeptanz($fittnessA, $fittnessB, count($loesungen))) {
		$loesungen[] = $kandidatB;
	}
	else {
		$loesungen[] = end($loesungen); // A(t-1)
	}
	
	$T *= 0.95; // für Ausglühen
	if ($runs % 10 == 0 && $runs > 0) $PHI--; // für Schwellenwert
	
	// Ausgabe
	$f = bewerte(end($loesungen));
	print abs($f).": ".str_repeat("#", -$f)."\n";
}

print implode(',', end($loesungen)); // Letzte Lösung ausgeben





function bewerte($kandidat) {
	global $strecken;
	$summe = 0;
	for ($i = 0; $i < 6; ++$i) {
		$von  = $kandidat[$i]; // 0..5
		$nach = $kandidat[($i + 1) % 6]; // 1..0
		
		if ($von>$nach) { $t = $von; $von = $nach; $nach = $t; }
		$summe += $strecken[$von.'_'.$nach];
	}
	return -$summe;
}

function mutation($kandidat) {
	$z1 = rand(0,5);
	$z2 = rand(0,5);
	while ($z1 == $z2) $z2 = rand(0,5);
	$t = $kandidat[$z1];
	$kandidat[$z1] = $kandidat[$z2];
	$kandidat[$z2] = $t;
	return $kandidat;
}

function akzeptanz($a,$b,$t) {
	global $modus, $maxDiff;
	
	switch ($modus) {
		case 'ausgluehen':
			
			global $T;
			
			if ($b-$a > $maxDiff) $maxDiff = $b-$a;
			
			if ($b > $a) return true;
			$u = rand(0,100000) / 100000; // [0..1]
			$k = $maxDiff;
			if ($u <= exp(-(($a-$b) / ($T*$k)))) return true;
			else return false;
			
		case 'schwellenwert':
		
			global $PHI;
			return (($b > $a) || ($a-$b < $PHI));
		
		case 'zufall':
			
			return $b > $a;
	}
}

?>