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