0

我有一个时间表生成任务，根据这个问题，可以借助遗传算法来解决。

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

这是示例的链接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

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

请任何人解释一下，为什么会发生这种情况？另外，我只与精英基因/生物群交配是不是做错了什么？

任何帮助将不胜感激。

4

1 回答 1

1

至少对于调试/测试，您可能需要长时间运行算法，因此您应该增加max_execution_timephp.ini 中的值（或使用该set_time_limit函数）。

您的代码中的术语似乎有些混乱。乍一看，您似乎没有实施精英主义。您似乎拥有的是truncation selection。这样选父母有错吗？好吧，它通常不是最理想的，因为它完全丢弃了较弱的候选者，虽然它们本身不可行，但可能包含可能有助于最终解决方案的遗传物质。在这个简单的示例中，这可能无关紧要，但总的来说，您可能会发现适应度成比例的选择策略（例如轮盘赌选择）更有效。这种策略有利于较强壮的个体，但允许较弱的候选人被选为父母。

如果要实施精英主义，则应将未修改的精英候选人复制到下一代中，然后通过从整个当前一代（包括精英个体）中选择父母来繁殖该一代的其余部分。通过精英主义保留的候选人百分比应该在 5% 左右（您可以尝试找到最佳比例）。

其他一些观察：

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