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

今回は学生寮の最適化問題をPHPで書いてみます。
まずは$dormsと$prefで学生寮のリストと各学生の希望のリストを作ります

$dorms = array('Zeus', 'Athena', 'Hercules', 'Bacchus', 'Plute');
$prefs = array(array('Toby', array('Bacchus', 'Hercules')), array('Steve', array('Zeus', 'Plute')), array('Andrea', array('Athena', 'Zeus')),array('Sarah', array('Zeus', 'Plute')), array('Dave', array('Athena', 'Baccus')), array('Jeff', array('Hercules', 'Plute')), array('Fred',  array('Hercules', 'Plute')), array('Suzie', array('Bacchus', 'Hercules')), array('Laura', array('Bacchus', 'Hercules')), array('Neil', array('Hercules', 'Athena')));

学生に寮を割り当てるたびに寮の候補が減っていくので
今回の$domainは順番に範囲が狭くなるように設定しています

$domain = array();
var_dump($prefs);
for ($i = 0; $i <count($dorms) * 2; $i++) {
    $domain[] = array(0, count($dorms)*2 -1 - $i);
}

各生徒への寮の割り当て配列$vecが与えられた時に寮の割り当て表を出力する関数を定義します。

function printsolution($vec, $dorms, $prefs) {
    $slots = array();
    for ( $i = 0; $i<count($dorms); $i++) {
        $slots[] = $i;
        $slots[] = $i;
    }

    for($i = 0; $i < count($vec); $i++) {
        $x = $vec[$i];
        $dorm = $dorms[$slots[$x]];
        echo $prefs[$i][0] . ',' . $dorm . '<br>';
        array_slice($slots, $x, 1);
    }
}
$vec = array(0,0,0,0,0,0,0,0,0,0);
var_dump(printsolution($vec, $dorms, $prefs));

寮の割り当てに対するコスト関数の定義を行います。

function dormcost($vec, $dorms, $prefs){
    $cost = 0;
    $slots = array(0,0,1,1,2,2,3,3,4,4);

    for($i = 0; $i < count($vec); $i++) {
        $x = $vec[$i];
        $dorm = $dorms[$slots[$x]];
        $pref = $prefs[$i][1];
        if($pref[0] == $dorm) {
            $cost = $cost + 0;
        } elseif($pref[1] == $dorm) {
            $cost = $cost + 1;
        } else {
            $cost = $cost + 3;
        }
        array_slice($slots, $x, 1);
    }
    return $cost;
}

ランダムオプティマイゼーションで寮の割り当て問題の最適化をしてみます。

function dormcostrandomoptimize($domain, $dorms, $prefs) {
    $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 = dormcost($r, $dorms, $prefs);

        if ($cost < $best) {
            $best = $cost;
            $bestr = $r;
        }
    }
    return $bestr;
}

$s = dormcostrandomoptimize($domain, $dorms, $prefs);
var_dump(dormcost($s, $dorms, $prefs));
var_dump(printsolution($s, $dorms, $prefs));

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

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

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

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

遺伝アルゴリズムを用いた最適化関数。
ここでは旅程問題の最小コストの最適化を試みていますが、他の問題にも応用できます。
かなり強力なアルゴリズムなのでオススメです。
肌感としては、世代数を増やすよりも人口（ポピュレーション）を増やしたほうが良い解に辿り着ける可能性が高い気がします。
遺伝的アルゴリズムはpythonコードをphp化するのに苦労しました。
もとのpythonコードにミスがあったので苦戦していたのですが、<『集合知プログラミング』 解体新書/a>が非常に参考になりました。

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

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

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

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