3

我想使用 GA 来确定从 A 到 B 的最佳路径，满足某些条件（长度、匝数等）

路径的示例是：上 4、左 8、下 3、右 3、下 1、左 10、上 4、左 1、上 3

问题是，我真的不知道一种很好的方式来表示这样的信息，以便在 GA 中使用，特别是因为路径的长度是可变的。

有谁知道如何做这样的事情？

4

5 回答 5

2

我不确定你的表示问题到底是什么，所以我怀疑你有这个问题是因为误解了 GA 的染色体字符串。从理论上讲，如果您采取额外的步骤来划分您的单个基因，则不必在整数边界上明确重组染色体串，这将允许您在逐个基因的基础上进行重组。这解决了可变长度基因的问题，例如您的“路径”。重组可变长度基因只是在突变方法中添加另一个变体，特别是“使用这个元素或核对这个元素”，除了标准的“使用来自 A 的元素或来自 B 的元素”，如果你的基因可以分解成离散的元素，就像你的路径一样。

于 2009-04-13T17:59:50.573 回答
2

听起来您真的很想使用A* 优化算法之类的东西，它通常（效果很好）用于寻路。您可以指定任何您喜欢的启发式函数以获得适当的解决方案。

于 2009-05-25T22:22:57.723 回答
1

我会使用 U、D、L、R....

所以“上 4，左 8，下 3，右 3，下 1，左 10，上 4，左 1，上 3”将是：

UUUULLLLLLLLDDDRRRDLLLLLLLLLLLUUUULUUU

像这样繁殖字符串会容易得多。

对于 A（15 个字符）和 B（3 个字符），我在 A 和 B 之间的育种功能是：

  • 在 1 和 MAX(LEN(A), LEN(B)) {介于 1 和 15} 之间选择一个随机所需的长度 (len)
  • 在 1 和 len 之间选择一个随机分割点。
  • 选择您是否希望 A 或 B 随机先行。
  • 从一个中取出第一个 s 字符，然后从另一个中取出最后一个（len-s）个字符。
于 2009-05-25T22:18:01.977 回答
1

GA 可以处理可变长度的染色体。实际个体可能非常复杂。例如，它可以包含一些固定长度的位、字符串（没有固定长度），可能还有一些共轭复数对。此外，共轭复数对必须始终保留一些条件。可以做到，但个体越复杂，遗传操作就越复杂（例如交叉、突变）。可能健身功能需要更多的代码行。但这仍然是可能的。

也许正如建议的那样，您可以选择数字编码的路径表示，但仍然可以使用您的示例编码为Osama ALASSIRY建议： UUUULLLLLLLLDDDRRRDLLLLLLLLLLLUUUULUUU。
对于交叉：

  • 让变异操作符读取给定个体的当前长度1，
  • 生成两个随机数 x1,y1，x1,y1 =< lenght1 和 x1 != y1（这是您对个人 1 的切割点），
  • 对个人 2 做同样的事情，现在你有两对 (x1,y1) 和 (x2,y2)，
  • 从个体 1 复制 x1 和 y1 之间的内容，并将其插入到值 x2 和 y2 之间的个体 2 中。新版本的 Individual 2 可能会改变其长度，因为 x1y1 和 x2y2 之间的基因数量可能不同，但没关系，
  • x2y2 之间的个人 2 的原始版本中的内容应该插入 x1y1 之间的个人 1 的新版本中（它的长度也会改变），

为了清楚起见：
父 A：UUUULLLLLLLLDDDRRRDLLLLLLLLLUUUULUUU
父 B：DRRRRLULUDDDR
你生成随机对pairA（4,18），pairB（0,5）假设你从0开始计算基因你交换以下字符串：
UUUU LLLLLLLLDDDRRRD LLLLLLLLLLUUUULUUU
DRRRRL ULUDDDR
所以交叉后你得到
UUUU DRRRRL LLLLLLLLLLUUUULUUU
LLLLLLLLDDDRRRD ULUDDDR
现在你刚刚跨越。您也可以使用一个切割点或多个点。

至于突变：

  • 生成介于 0 和个体长度之间的数字，
  • 生成 1-4 之间的数字并更新该基因。（如果生成 1，则将其更改为 U、2-D、3-L、4-R）

你刚刚做了突变。您还可以突变多个基因。

但正如我所说，还有其他可能性。

于 2009-11-04T20:44:51.660 回答
0

对我来说，这听起来与旅行推销员问题非常相似，该页面是否包含一些有用的信息？

于 2009-04-13T22:02:11.537 回答