Ryokuchaneko’s gists

Created July 15, 2013 13:07

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

	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));

Ryokuchaneko / PHPで学ぶ集合知プログラミング5.6

Created July 15, 2013 13:10

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

	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;

Ryokuchaneko / PHPで学ぶ集合知プログラミング5.7

Created July 15, 2013 13:14

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

	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;