1

我正在研究能够使用基因编程进行食物觅食行为的进化蚂蚁，正如 Koza在这里所描述的那样。每个时间步，我遍历每只蚂蚁，执行它的计算机程序（同一个程序被蚁群中的所有蚂蚁使用）。目前，我已经定义了简单的指令，如MOVE-ONE-STEP、TURN-LEFT、TURN-RIGHT等。但我也有一个PROGN按顺序执行参数的函数。我遇到的问题是，因为PROGN可以按顺序执行指令，这意味着蚂蚁可以在一个时间步内执行多个操作。与自然不同，我不能并行运行蚂蚁，这意味着一只蚂蚁可能会去执行几个动作，操纵环境，而所有其他蚂蚁都在等待轮到他们。

我只是想知道，这是通常的做法，还是有更好的方法？Koza 似乎没有提及任何关于它的事情。问题是，我想扩展场景以拥有其他代理（例如敌人），这可能依赖于在单个时间步中仅发生一次的事情。

4

3 回答 3

2

我不熟悉 Koza 的工作，但我认为一个合理的方法是给每只 ant 自己的指令队列，该队列跨时间步长持续存在。通过这样做，您可以让蚂蚁在PROGN每个时间步执行一条指令。例如，蚂蚁时间步长的高级逻辑可以是：

Do-Time-Step(ant):
1. if ant.Q is empty:  // then put the next instruction(s) into the queue
2.     instructions <- ant.Get-Next-Instructions()
3.     for instruction in instructions:
4.         ant.Q.enqueue(instruction)
5.     end for
6. end if
7. instruction <- ant.Q.dequeue()  // get the next instruction in the queue
8. ant.execute(instruction)        // have that ant do its job
于 2011-10-03T06:35:19.167 回答
0

对指令进行排队的另一种类似方法是对指令集进行预处理，并将 PROGN 的实例扩展为组件指令集。如果您允许 PROGN 调用其他 PROGN，则必须递归完成。这样做的缺点是候选程序有点臃肿，但这只是在运行时。另一方面，它很容易、快速并且很容易调试。

示例：说 PROGN1 = {inst-p1 inst-p2}

然后候选程序将以 {inst1 PROGN1 inst2} 开始，并在准备好在模拟中进行评估时扩展为 {inst1 inst-p1 inst-p2 inst2}。

于 2011-10-05T13:07:37.080 回答
0

这完全取决于您的特定 GP 实施。

在我的 GP 中，内核程序要么被重复评估，要么被并行评估——作为一个整体，即这种情况下的“原子”操作是单个程序评估。因此，在评估下一个程序之前，种群中的所有个体都按顺序重复 n 次，或者所有个体只执行一次，然后再执行 n 次。

使用这种并发级别的虚拟代理我取得了相当不错的结果。绝对有可能将其分解得更多，但是此时您将降低算法的可扩展性：

虽然很容易将程序的评估分布在多个 CPU 或内核之间，但由于所有程序之间需要同步的数量，对每个节点的评估做同样的事情几乎毫无价值。

鉴于现代系统（甚至智能手机）中 CPU/内核数量的迅速增加以及 GP 的“CPU 饥渴”，您可能需要重新考虑您的方法——您真的想在程序中包含移动/转向指令吗？

为什么不重新设计它以使用在程序评估期间将方向和速度参数存储在某些寄存器/变量中的原语？然后，模拟步骤根据程序存储的指令使用这些参数来实际移动/转动您的代理。

  1. 评估程序（并行）
  2. 执行模拟
  3. 重复n次
  4. 评估适合度，选择，...

干杯，杰伊

于 2011-12-11T12:35:38.383 回答