Ryokuchaneko’s gists

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;

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.5

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.4

Created July 15, 2013 13:05

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

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

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

Created July 14, 2013 04:24

コスト関数の定義。運賃総額と空港での待ち時間、レンタカーの追加料金を含めたコストを旅程ごとに算出する関数を定義する。

	function schedulecost($sol, $origin, $people, $flights, $destination) {
	$totalprice = 0;
	$latestarrival = 0;
	$earliestdep = 24*60;
	$d = count($sol)/2;
	for ($i = 0; $i < $d; $i++) {
	$origin = $people[$i][1];
	$outbound = $flights[$origin][$destination][$sol[$i*2]];
	$returnf = $flights[$destination][$origin][$sol[$i*2+1]];

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

Created July 14, 2013 04:21

誰がどの便でLGAにやってくるかを$sで表現する。各数字はその日の何便目に乗るか。そして、Seymourの行き・帰り・Frannyの行き・帰り・・・の順に並んでいる。この数列から各人の旅程の情報を出力する関数を定義する（printschedule）

	$s = array(1,4,3,2,7,3,6,3,2,4,5,3);

	function printschedule($r, $people, $flights, $destination) {
	$d = count($r)/2;
	for($i = 0; $i < $d; $i++){
	$name = $people[$i][0];
	$origin = $people[$i][1];
	$out = $flights[$origin][$destination][$r[($i*2)]];
	$ret = $flights[$destination][$origin][$r[($i*2+1)]];
	echo sprintf("%10s%10s %5s-%5s $%3s %5s-%5s $%3s" . PHP_EOL, $name, $origin, $out[0], $out[1], $out[2], $ret[0], $ret[1], $ret[2]);

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

Last active December 19, 2015 17:39

グループ旅行問題を特にあたり$peopleのarrayに人名と出発地を入れる。そして、全ての人達の目的地としてLGAを設定する。サンプルのフライトデータとしてhttp://kiwitobes.com/optimize/schedule.txtが用意されているのでダウンロードして同じディレクトリに入れておく。そして、schedule.txtからoriginとdestをキーとしたフライトリストを作る。さらに、HH:MMの形式で表された時間を午前０時０分から何分経ったかに変換するgetminutes関数を定義する

	$people = array(array('Symour', 'BOS'), array('Franny', 'DAL'), array('Zooey', 'CAK'), array('Walt', 'MIA'), array('Buddy', 'ORD'), array('Les', 'OMA'));
	$destination = 'LGA';
	$flights = array();
	$fp = fopen("schedule.txt", "r");
	while($line = fgets($fp)) {
	$line = rtrim($line);
	$explode_line = explode(",",$line);
	$origin = $explode_line[0];
	$dest = $explode_line[1];
	$depart = $explode_line[2];

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

Created July 14, 2013 00:11

MovieLensのデータ・セットを使って商品の推薦を行います。まず、loadMovieLens関数でMovieLensのデータをロードします。そして、getRecommendations関数を使ってユーザーベースの推薦を行い、calculateSimilarItems関数を使ってアイテム間の相関を計算し、getRecommendedItems関数でアイテムベースの推薦を行います。

	function loadMovieLens($path) {
	$movies = array();
	$fp = fopen($path . "/u.item", "r");
	while($line = fgets($fp)){
	$line_explode = explode("\|", $line);
	$movies[$line_explode[0]] = $line_explode[1];
	}
	fclose($fp);
	$prefs = array();
	$fp = fopen($path . "/u.data", "r");

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

Created July 12, 2013 16:54

transformPrefsでスコアのディクショナリをアイテムごとのディクショナリに変換してアイテムごとにループを回して各アイテムに似ているアイテムをランキングでとってくる各ユーザーの評価で映画のタイトルのスコアに重みづけをしてアイテムベースでユーザーにオススメをする

	function calculateSimilarItems($critics, $n) {
	$result = array();
	$itemPrefs = transformPrefs($critics);
	$c = 0;
	foreach($itemPrefs as $item => $v) {
	$c++;
	if( $c%100 == 0){
	echo sprintf("%d / %d", $c, count($itemPrefs));
	}
	$scores = topMatches($itemPrefs, $item, $n, 'distance');

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

Last active December 19, 2015 16:29

今まで用いてきた評価者ごとの映画の評価配列を映画ごとの評価配列に変換する以前に定義したtopMatches関数を使って、似た属性をもつ映画をランキング形式で表示できる。また、映画が誰に見られるべきかをgetRecommendationsを使って表示することができる

	function transformPrefs($critics) {
	$result = array();
	foreach ($critics as $key => $person) {
	foreach ($person as $item => $value) {
	if(!isset($result[$item])){
	$resutl[$item] = array();
	}
	$result[$item][$key] = $value;
	}
	}