PHPで遺伝的アルゴリズム

はじめに

前回のPythonで遺伝的アルゴリズムのコードをPHP7で実装してみたのでメモ書き程度に書いておきます。

パラメータ

PHPは定数が使えるのでconstで定義していきます。

const GENE_LENGTH = 10;
const INDIVIDUAL_LENGTH = 100;
const GENERATION = 20;
const MUTATE_RATE = 0.1;
const ELITE_RATE = 0.2;

初期個体群生成

/**
 * @return array
 */
function get_population(): array 
{
    $population = [];
    for ($i=0; $i<INDIVIDUAL_LENGTH; $i++) {
        $individual = [];
        for ($j=0; $j<GENE_LENGTH; $j++) {
            array_push($individual, rand(0, 1));
        }
        array_push($population, $individual);
    }
    return $population;
}

適応度と評価

/**
 * @param array $pop
 * @return int
 */
function fitness(array $pop): int 
{
    return array_sum($pop);
}

/**
 * @param array $pop
 * @return array
 */
function evaluate(array $pop): array 
{
    $sort = [];
    for ($i=0; $i<INDIVIDUAL_LENGTH; $i++) {
        array_push($sort, $pop[$i][0]);
    }
    array_multisort($sort, SORT_DESC, $pop);
    return $pop;
}

交叉と突然変異

前回は二点交叉で交叉を実装しましたが、PHPでやったときにうまく動かず修正するのがめんどくさかったので一点交叉で実装しました。

/**
 * @param array $parent1
 * @param array $parent2
 * @return array
 */
function crossover(array $parent1, array $parent2): array
{
    $r = rand(0, GENE_LENGTH-1);
    $child1 = array_slice($parent1, 0, $r, true);
    $child2 = array_slice($parent2, $r, null, true);
    $child = array_merge($child1, $child2);
    return $child;
}

/**
 * @param array $parent
 * @return array
 */
function mutate(array $parent): array
{
    $r = rand(0, GENE_LENGTH-1);
    $child = $parent;
    $child[$r] = $child[$r]==0 ? 1 : 0;
    return $child;
}

コード全体

<?php

const GENE_LENGTH = 10;
const INDIVIDUAL_LENGTH = 100;
const GENERATION = 20;
const MUTATE_RATE = 0.1;
const ELITE_RATE = 0.2;

/**
 * @return array
 */
function get_population(): array 
{
    $population = [];
    for ($i=0; $i<INDIVIDUAL_LENGTH; $i++) {
        $individual = [];
        for ($j=0; $j<GENE_LENGTH; $j++) {
            array_push($individual, rand(0, 1));
        }
        array_push($population, $individual);
    }
    return $population;
}

/**
 * @param array $pop
 * @return int
 */
function fitness(array $pop): int 
{
    return array_sum($pop);
}

/**
 * @param array $pop
 * @return array
 */
function evaluate(array $pop): array 
{
    $sort = [];
    for ($i=0; $i<INDIVIDUAL_LENGTH; $i++) {
        array_push($sort, $pop[$i][0]);
    }
    array_multisort($sort, SORT_DESC, $pop);
    return $pop;
}

/**
 * @param array $parent1
 * @param array $parent2
 * @return array
 */
function crossover(array $parent1, array $parent2): array
{
    $r = rand(0, GENE_LENGTH-1);
    $child1 = array_slice($parent1, 0, $r, true);
    $child2 = array_slice($parent2, $r, null, true);
    $child = array_merge($child1, $child2);
    return $child;
}

/**
 * @param array $parent
 * @return array
 */
function mutate(array $parent): array
{
    $r = rand(0, GENE_LENGTH-1);
    $child = $parent;
    $child[$r] = $child[$r]==0 ? 1 : 0;
    return $child;
}


// 初期個体群生成
$first_population = get_population();
$pop = [];
foreach ($first_population as $key => $population) {
    array_push($pop, [fitness($population), $population]);
}
$pop = evaluate($pop);
echo "Generation: 0\n";
echo "Min : {$pop[INDIVIDUAL_LENGTH-1][0]}\n";
echo "Max : {$pop[0][0]}\n";
echo "--------------------------\n";


for ($g=1; $g<=GENERATION; $g++) {
    echo "Generation: $g\n";

    // エリートを選択
    $eva = evaluate($pop);
    $elites = array_slice($eva, 0, (int)(count($pop)*ELITE_RATE));

    // 突然変異、交叉
    $pop = $elites;
    for ($i=0; count($pop)<INDIVIDUAL_LENGTH; $i++) {
        if (lcg_value() < MUTATE_RATE) {
            $m = rand(0, count($elites)-1);
            $child = mutate($elites[$m][1]);
        } else {
            $m1 = rand(0, count($elites)-1);
            $m2 = rand(0, count($elites)-1);
            $child = crossover($elites[$m1][1], $elites[$m2][1]);
        }
        array_push($pop, [fitness($child), $child]);
    }

    // 評価
    $eva = evaluate($pop);
    $pop = $eva;

    echo "Min : {$pop[INDIVIDUAL_LENGTH-1][0]}\n";
    echo "Max : {$pop[0][0]}\n";
    echo "--------------------------\n";
}

print_r($pop[0]);

実行結果

Generation: 0
Min : 2
Max : 10
--------------------------
Generation: 1
Min : 5
Max : 10
--------------------------
Generation: 2
Min : 8
Max : 10
--------------------------
Generation: 3
Min : 9
Max : 10
--------------------------
.
.
.
.
Generation: 16
Min : 9
Max : 10
--------------------------
Generation: 17
Min : 9
Max : 10
--------------------------
Generation: 18
Min : 9
Max : 10
--------------------------
Generation: 19
Min : 9
Max : 10
--------------------------
Generation: 20
Min : 9
Max : 10
--------------------------
Array
(
    [0] => 10
    [1] => Array
        (
            [0] => 1
            [1] => 1
            [2] => 1
            [3] => 1
            [4] => 1
            [5] => 1
            [6] => 1
            [7] => 1
            [8] => 1
            [9] => 1
        )

)

ちなみに実行速度比較してみました。パラメータはPHPのほうと同じにしています。
まずPython

$ time python ga.py
.
.
.
python ga.py  0.13s user 0.08s system 74% cpu 0.287 total

次にPHP

$ time php ga.php
.
.
.
php ga.php  0.03s user 0.02s system 60% cpu 0.081 total

PHP7.2.2で実行したんですがPHP7が正直こんなに速いとは思ってもいませんでした。恐るべし…