php - 我的 GAHelloWorld 实现逻辑有什么问题？

Question

我有一个计划生成任务，根据this question , 可以借助遗传算法求解。

我通过谷歌搜索找到了许多非常有用的文献和两个“Hello World!”例子。到目前为止，我已经尝试将它们翻译成 php，并重新封装以使代码可重用于我 future 的任务。

这里是关于 C++ 的示例链接和 Java (抱歉，最后一个是俄语，但那里的代码仍然有用)。

这是我的实现:

<?php    
abstract class Creature
    {
        protected $fitness;

        public function __construct()
            {
                $this->fitness = 0;
            }

        public function getFitness()
            {
                return $this->fitness;
            }

        abstract public function calculateFitness();

        public function compareTo($creature)
            {
                return $this->fitness - $creature->fitness;
            }

        abstract public function mateWith($creature);

        abstract public function mutate();
    }

abstract class Population
    {
        protected $creatures;
        protected $generation;

        public function __construct()
            {
                $this->creatures    = array();
                $this->generation   = 1;

                $this->populate();
            }

        public function __destruct()
            {
                unset($this->creatures);
            }

        public function get($index)
            {
                return isset($this->creatures[$index]) ? $this->creatures[$index] : null;
            }

        public function getCount()
            {
                return count($this->creatures);
            }

        public function getGeneration()
            {
                return $this->generation;
            }

        abstract protected function populate();

        public function sort($order = SORT_ASC)
            {
                switch($order)
                    {
                        case SORT_ASC:
                            $fn = function($c1, $c2){ return $c1->compareTo($c2); };
                        break;

                        case SORT_DESC:
                            $fn = function($c1, $c2){ return $c2->compareTo($c1); };
                        break;

                        default: return false;
                    }

                return usort($this->creatures, $fn);
            }

        public function select(array $params)
            {
                $result = false;

                if(isset($params['top']))
                    {
                        $length = round(abs($this->getCount() * $params['top']) / 100);

                        $this->creatures = array_slice($this->creatures, 0, $length);

                        $result = true;
                    }

                if(isset($params['fn']) && is_callable($params['fn']))
                    {
                        $this->creatures = array_filter($this->creatures, $params['fn']);

                        $result = true;
                    }

                return $result;
            }

        public function breed()
            {
                $candidates = $this->creatures;

                shuffle($candidates);

                $candidates = array_chunk($candidates, 2);
                $result     = 0;

                foreach($candidates as &$pair)
                    {
                        if(count($pair) < 2)continue;

                        list($mother, $father) = $pair;

                        $children = $mother->mateWith($father);

                        $result += count($children);

                        $this->creatures = array_merge($this->creatures, $children);
                    }

                $this->generation++;

                return $result;
            }
    }

class HWCreature extends Creature
    {
        protected $string;

        protected function randChar()
            {
                return chr(rand(0, 255));
            }

        protected function fill()
            {
                $length = strlen(Algorithm::TARGET);

                for($i = 0; $i < $length; $i++)
                    {
                        $this->string .= $this->randChar();
                    }
            }

        public function __construct($fill = true)
            {
                parent::__construct();

                $this->string = '';

                if(!$fill)return;

                $this->fill();
                $this->calculateFitness();
            }

        public function __toString()
            {
                return $this->string;
            }

        public function calculateFitness()
            {
                $length = strlen($this->string);
                $target = Algorithm::TARGET;

                for($i = 0; $i < $length; $i++)
                    {
                        $this->fitness += abs(ord($this->string[$i]) - ord($target[$i]));
                    }
            }

        public function mateWith($creature)
            {
                $length = strlen(Algorithm::TARGET) - 1;
                $place  = rand(0, $length);

                $child1 = new self(false);
                $child1->string = substr($this->string, 0, $place) . substr($creature->string, $place);
                $child1->mutate();
                $child1->calculateFitness();

                $child2 = new self(false);
                $child2->string = substr($creature->string, 0, $place) . substr($this->string, $place);
                $child2->mutate();
                $child2->calculateFitness();

                return array($child1, $child2);
            }

        public function mutate()
            {
                if(rand(1, 100) > Algorithm::MUTATION_RATE)return;

                $char   = $this->randChar();
                $length = strlen(Algorithm::TARGET);
                $place  = rand(0, $length - 1);

                $this->string = substr_replace($this->string, $char, $place, 1);
            }
    }

class HWPopulation extends Population
    {
        protected function populate()
            {
                for($i = 0; $i < Algorithm::POPULATION_SIZE; $i++)
                    {
                        $this->creatures[] = new HWCreature();
                    }
            }
    }

class Algorithm
    {
        const POPULATION_SIZE   = 100; // 1000 in my original test
        const ELITE_RATE        = 50; // %
        const MUTATION_RATE     = 25; // %
        const MAX_GENERATIONS   = 1000;

        const TARGET    = 'Hello World!';

        protected $population;

        public function __construct()
            {
                $this->population = new HWPopulation();
            }

        public function __destruct()
            {
                unset($this->population);
            }

        public function __invoke()
            {
                do
                    {
                        $generation = $this->population->getGeneration();
                        $representer    = $this->population->get(0);

                        echo sprintf(
                                'gen %d > %s',
                                $generation, $representer
                            ),
                            '<br>',
                            PHP_EOL;

                        if($representer == self::TARGET)break;

                        $selector = array('top' => self::ELITE_RATE);

                        $this->population->sort();
                        $this->population->select($selector);
                        $this->population->breed();
                    }
                while($generation < self::MAX_GENERATIONS);
            }
    }

$algorithm = new Algorithm();
$algorithm();
unset($algorithm);
?>

但是，我在配备 i7 @ 2.4 GHz CPU 的 16Gb RAM 机器上的结果是:

...
gen 739 > HfkkoWotlc!
gen 740 > HfkkoWotlc!
gen 741 > HfkkoWotlc!
gen 742 > HfkkoWotlc!
gen 743 > HfkkoWotlc!
gen 744 > HfkkoWotlc!
gen 745 > HfkkoWotlc!

Fatal error: Maximum execution time of 30 seconds exceeded in {script} on line 126

所以，看起来效率极低。我相信，这个问题可能出在选择或育种策略上……而我完全迷失在那里。

谁能解释一下，为什么会这样？另外，我只与精英基因/生物群交配是不是做错了什么？

我们将不胜感激。

Answer 1

至少为了调试/测试，您可能需要长时间运行算法，因此您应该增加 php.ini 中的 max_execution_time 的值(或使用 set_time_limit 函数)。

您的代码中的术语似乎有些困惑。从非常简短的一瞥来看，您似乎没有实现精英主义。你似乎拥有的是 truncation selection .这样选 parent 有错吗？好吧，它通常是次优的，因为它完全丢弃了较弱的候选者，这些候选者虽然本身不​​可行，但可能包含有助于最终解决方案的遗传物质。在这个简单的示例中，它可能无关紧要，但通常您会发现 fitness-proportionate selection strategy ，如轮盘赌选择，更有效。这种策略有利于强者，但也允许弱者被选为 parent 。

如果要实现精英主义，则应将精英候选者不加修改地复制到下一代中，然后通过从整个当前世代(包括精英个体)中选择 parent 来培育那一代的其余成员。通过精英主义保留的候选人的比例应该在5%左右(你可以通过实验找到最佳比例)。

一些其他观察:

1. 如果降低突变概率，您也可能会获得更好的结果。过多的突变会毁掉优秀的个体。
2. 您的适应度函数似乎关心每个字母的接近程度(即，如果第一个字母是“G”，则得分为 1，但“M”得分为 5)。但是，您的变异函数不太复杂，只是随机替换字母，所以它们有多接近并不重要(“X”被“H”替换的机会与“G”一样多)。将每个字母记为 1(错误)或 0(正确)可能更简单、更有效，除非您要更改突变以将字母更改为字母表中相邻的字母。