PHPで学ぶ「集合知プログラミング」〜最適化〜 2

ランダムサーチによる最小コストの旅程を求める関数。
コスト関数を入れ替えれば旅程以外の問題でも最小、最大をランダムサーチによって求めることができる。

	function randomoptimize($domain, $origin, $people, $flights, $destination) {
	$best = 999999999;
	$bestr = 'null';
	for($i = 0; $i < 10000; $i++) {
	$r = array();
	for($s = 0; $s < count($domain); $s++) {
	$r[] = rand($domain[$s][0], $domain[$s][1]);
	}
	$cost = schedulecost($r, $origin, $people, $flights, $destination);
	if ($cost < $best) {
	$best = $cost;
	$bestr = $r;
	}
	}
	return $bestr;
	}
	$domain = array();
	for ($i = 0; $i < count($people)*2; $i++) {
	$domain[] = array(0, 9);
	}
	$result = randomoptimize($domain, $origin, $people, $flights, $destination);
	$schedule = printschedule($result, $people, $flights, $destination);

view raw PHPで学ぶ集合知プログラミング5.4 hosted with ❤ by GitHub

ヒルクライムによる最小コストを求める関数。
コスト関数を入れ替えれば、他の問題においても最小、最大値を求めることができる。

	function hillclimb($domain, $origin, $people, $flights, $destination) {
	$r = array();
	for($s = 0; $s < count($domain); $s++) {
	$r[] = rand($domain[$s][0], $domain[$s][1]);
	}
	while(1){
	$neighbors = array();
	for ($k = 0; $k < count($domain); $k++) {
	if($r[$k] > $domain[$k][0]) {
	$neighbors[] = array_replace($r, array($k => $r[$k]-1));
	}
	if($r[$k] < $domain[$k][1]) {
	$neighbors[] = array_replace($r, array($k => $r[$k]+1));
	}
	}
	$current = schedulecost($r, $origin, $people, $flights, $destination);
	$best = $current;
	for ($p = 0; $p < count($neighbors); $p++) {
	$cost = schedulecost($neighbors[$p], $origin, $people, $flights, $destination);
	if ( $cost < $best ) {
	$best = $cost;
	$r = $neighbors[$p];
	}
	}
	if( $best == $current ) {
	break;
	}
	}
	return $r;
	}
	$result = hillclimb($domain, $origin, $people, $flights, $destination);
	var_dump($result);
	$cost = schedulecost($result, $origin, $people, $flights, $destination);
	var_dump($cost);
	$schedule = printschedule($result, $people, $flights, $destination);

view raw PHPで学ぶ集合知プログラミング5.5 hosted with ❤ by GitHub

擬似アニーリングによる最適化関数。
ここでは、旅程のコストの最適値を求めているが、コスト関数を入れ替えれば他の問題にも適用できます。

	function annealingoptimize($domain, $origin, $people, $flights, $destination, $T=10000.0, $cool=0.95, $step=1) {
	$vec = array();
	for($s = 0; $s < count($domain); $s++) {
	$vec[] = rand($domain[$s][0], $domain[$s][1]);
	}
	while ( $T > 0.1 ) {
	$i = rand(0, (count($domain) - 1) );
	$dir = rand( -$step, $step);
	$vecb = $vec;
	$vecb[$i] += $dir;
	if($vecb[$i] < $domain[$i][0]){
	$vecb[$i] = $domain[$i][0];
	} elseif ($vecb[$i] > $domain[$i][1]) {
	$vecb[$i] = $domain[$i][1];
	}
	$ea = schedulecost($vec, $origin, $people, $flights, $destination);
	$eb = schedulecost($vecb, $origin, $people, $flights, $destination);
	$p = exp(-abs($eb-$ea)/$T);
	$rand = rand(1,10000)/10000;
	if (($eb < $ea) || ($rand < $p)) {
	var_dump('A');
	$vec = $vecb;
	}
	$T = $T*$cool;
	}
	return $vec;
	}
	$result = annealingoptimize($domain, $origin, $people, $flights, $destination, $T=10000.0, $cool=0.95, $step=1);
	var_dump($result);
	$cost = schedulecost($result, $origin, $people, $flights, $destination);
	var_dump($cost);
	$schedule = printschedule($result, $people, $flights, $destination);

view raw PHPで学ぶ集合知プログラミング5.6 hosted with ❤ by GitHub

遺伝アルゴリズムを用いた最適化関数。
ここでは旅程問題の最小コストの最適化を試みていますが、他の問題にも応用できます。
かなり強力なアルゴリズムなのでオススメです。
肌感としては、世代数を増やすよりも人口（ポピュレーション）を増やしたほうが良い解に辿り着ける可能性が高い気がします。

	function geneticoptimize($domain, $origin, $people, $flights, $destination, $popsize = 50, $step=1, $mutprob=0.2, $elite=0.2, $maxiter = 100) {
	function mutate($vec, $domain, $step) {
	$i = rand(0, (count($domain) - 1));
	$rand = rand(1,10000)/10000;
	if(($rand < 0.5) && ($vec[$i] > $domain[$i][0])) {
	$vec[$i] = $vec[$i] - $step;
	return $vec;
	} elseif($vec[$i] < $domain[$i][1]) {
	$vec[$i] = $vec[$i] + $step;
	return $vec;
	}
	}
	function crossover($r1, $r2, $domain) {
	$i = rand(1, (count($domain) - 2));
	for($k = 0; $k < $i; $k++){
	$r2[$k] = $r1[$k];
	}
	return $r2;
	}
	$pop = array();
	for($y = 0; $y < $popsize; $y++){
	$vec = array();
	for($s = 0; $s < count($domain); $s++) {
	$vec[] = rand($domain[$s][0], $domain[$s][1]);
	}
	$pop[] = $vec;
	}
	$topelite = floor($elite*$popsize);
	for($g=0; $g<$maxiter; $g++){
	$scores = array();
	foreach($pop as $key => $v){
	if(!empty($v)){
	$scores[]=array(schedulecost($v, $origin, $people, $flights, $destination), $v);
	}
	}
	sort($scores);
	$pop = $ranked = array();
	foreach($scores as $key => $v) {
	$ranked[] = $v[1];
	}
	foreach($ranked as $v){
	$pop[] = $v;
	if(count($pop) == $topelite) {
	break;
	}
	}
	while(count($pop) <= $popsize) {
	$randrand = rand(1,10000)/10000;
	if($randrand < $mutprob){
	$c = rand(0, $topelite);
	$pop[] = mutate($ranked[$c], $domain, $step);
	}else{
	$c1 = rand(0, $topelite);
	$c2 = rand(0, $topelite);
	$pop[] = crossover($ranked[$c1], $ranked[$c2], $domain);
	}
	}
	print $scores[0][0] . '<br />';
	}
	return $scores[0][1];
	}
	$result = geneticoptimize($domain, $origin, $people, $flights, $destination, $popsize = 50, $step=1, $mutprob=0.2, $elite=0.2, $maxiter = 100);
	var_dump($result);
	die();
	$cost = schedulecost($result, $origin, $people, $flights, $destination);
	var_dump($cost);
	$schedule = printschedule($result, $people, $flights, $destination);
	var_dump($schedule);

view raw PHPで学ぶ集合知プログラミング5.7 hosted with ❤ by GitHub

遺伝的アルゴリズムはpythonコードをphp化するのに苦労しました。
もとのpythonコードにミスがあったので苦戦していたのですが、<『集合知プログラミング』 解体新書/a>が非常に参考になりました。