在执行GAHelloWorld时，逻辑有什么问题？

Question

我有一个时间表生成任务，根据this question，可以在遗传算法的帮助下解决。

我已经通过谷歌搜索，发现了许多非常有用的文献和两个“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); 
?> 

然而，我的16GB内存的机器上的结果与酷睿i7 @ 2.4GHz的CPU是：

... 
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。以这种方式选择父母是否是错误的？那么它往往是次优的，因为它完全抛弃了较弱的候选者，尽管这些候选者本身不可行，但可能包含可能有助于最终解决方案的遗传材料。在这个简单的例子中，它可能并不重要，但总的来说，您可能会发现一个fitness-proportionate selection strategy（如轮盘选择轮盘）更有效。这样的策略有利于较强的个人，但允许选择较弱的候选人作为父母的可能性。

如果您想实施精英主义，您应该将未修改的精英候选人复制到下一代，然后通过选择当前整个一代（包括精英个人）的父母，培育其余的那一代。通过精英主义保留的候选人的比例应该是5％左右（您可以尝试找到最佳比例）。

其他一些意见：

1. 您还可以得到更好的结果，如果你减少变异概率。太多的突变会破坏好人。
2. 你的健身功能似乎关心每个字母的接近程度（即如果第一个字母是'G'，那么得分为1，但'M'得分为5）。然而，你的变异函数不太复杂，只是随机替换字母，所以它们有多接近并不重要（'X'有'G'代替'H'的可能性）。除非要改变突变以将字母改为字母中相邻的字母，否则将每个字母评分为1（错误）或0（正确）可能更简单也更有效。