在遗传算法中使用二进制编码是必要的吗



我正在做一个项目,探索遗传算法在建筑中的应用,我们使用进化方法在三维中创建Voronoi镶嵌。这是使用openFrameworks(c++)的ofxVoro++来完成的。

我们的基因组染色体是一个三维点的矢量(列表)。我们已经实现了单点和两点交叉以及变异,它以一定的概率随机化这些点。在我见过的大多数例子中,基因组是二进制编码的,我认为这会导致突变和交叉产生不同的作用。

所以我的问题是:二进制编码(除了速度)还有其他好处吗?你将如何在c++中处理这样的编码/解码?从二进制到三维点列表。

谨致问候,Fred

我在物流和财务问题上使用了不同的GA。我经常不使用二进制表示。我能给你的第一个例子是TSP问题:

https://en.wikipedia.org/wiki/Travelling_salesman_problem

这里我使用了标准表示:染色体是一个整数数组,每个值代表城市。

因此,这取决于你试图解决的问题类型,如果你能找到一种在没有二进制表示的情况下实现GA的方法,你就不需要任何调整。此外,我更喜欢自然表示,因为在调试代码时,如果GA按您的意愿工作,它更容易理解。

您也可以使用真正的编码,但在这种情况下,使用什么交叉和突变很重要。如果你的交叉只是(p1+p2)/2或p1*a+p2*(1-a),你不会得到好的结果。

K.Deb在1995年提出了一种用于实数编码的良好的交叉算子。这是论文:http://www.complex-systems.com/pdf/09-2-2.pdf

交叉和突变是不同的运算符。交叉使用现有的基因。突变将新的遗传物质引入种群。在不知道更多关于算法的信息的情况下,随机化点听起来像是突变。突变通常在非常低的时间百分比(可能是1%)进行,而交叉可能相当高(50%)。

所以对于你的算法,我不会为了交叉而"修改"任何东西。相反,对于交叉,我会尝试重新定位材料,或者简单地从父母那里获取点的不同部分。

对于突变,在点上加或减一个小数字,从而修改点(突变)可能是有意义的。

在不了解更多算法和染色体表示的情况下,很难提出建议。

最新更新