如何创建我的遗传算法的人口？

Question

一个问题给出我应该发现从开始的5条最好的路径与目标遗传算法。操场上的图像如下所示：

1

游乐场有一个起点，一个目标，而一些障碍。答案不应该有障碍冲突。我将使用Python的3.x的为我实现。

我想我的操场转换为2D numpy的阵列。 1分的为瓦片，我们不能去那里，因为他们是障碍，0的是，我们可以去的瓷砖。

grid = np.array([
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

start = (12,0)
goal = (0,10)

现在我不知道如何创建我的初始种群与其他GA operators如交叉和变异工作。

我想我应该有一些功能，使路径从起点到目标与认识的局限性，并将它们保存为我的人民。

Answer 1

正如你已经知道你的搜索空间的大小（它是方形的大小，你的身材），你可以使用此信息的整数均匀分布初始化你的人口。

我不知道这个广场的瓷砖大小，但是让我们假设它的[15,15]。你的人口的每一个人都将是2D，对不对？因此，当你正在使用python，并考虑到人口规模等于10，你应该这样做：

import numpy as np
pop = np.random.randint(0,15,[10,2])

因此，每个单独的将发生在正方形的位置。现在，你不必担心，如果个人在一个禁地。你应该把它处理你的选择阶段的约束。

而且可以肯定，你需要制定你的健身功能，以惩罚那些谁是禁止的地方的人。但你不使用它来启动你的人口，你用它来选择最佳的个体，你明白了吗？

有一些技术来处理的制约，我建议你在this paper或者只是看到了code example读取其中的一些。

Answer 2

在遗传算法，人口是候选方案，它的迭代过程中演变的集合。初始群体通常是随机生成的。 （link to source）

例如一种溶液（或初始种群的一个候选）可以是这样的：

([
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, *, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, *, *, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, *, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, *, *, 0, 0],
[0, 0, 0, 1, 1, 1, 1, 1, 0, 0, *, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, *, 1, 1, 1, 0, 0],
[0, *, *, *, *, *, *, *, *, *, *, 1, 1, 1, 0, 0],
[0, *, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, *, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[*, *, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])

其中的*的一个线索是从（12，0）到（0，10）的路径。

所以，现在你需要找出一种方法来随机生成其开始在start月底在end *'s的路径。天真的方法是使用左，右，上，下随机的方向。如果该方向是由一个边界或1个封锁的，选择不同的方向。继续，直到你到达终点。

此外，一个路径可以具有*的彼此相邻的，如上面所看到的。 （3，11），（3，12）包含*的但不是连续的线索的一部分。对于这种使用不同的数字来表示的方向或我建议使用Unicode为箭头，例如\u2190是左箭头。

希望这可以帮助。