我想使用 GA 来确定从 A 到 B 的最佳路径,满足某些条件(长度、匝数等)
路径的示例是:上 4、左 8、下 3、右 3、下 1、左 10、上 4、左 1、上 3
问题是,我真的不知道一种很好的方式来表示这样的信息,以便在 GA 中使用,特别是因为路径的长度是可变的。
有谁知道如何做这样的事情?
我想使用 GA 来确定从 A 到 B 的最佳路径,满足某些条件(长度、匝数等)
路径的示例是:上 4、左 8、下 3、右 3、下 1、左 10、上 4、左 1、上 3
问题是,我真的不知道一种很好的方式来表示这样的信息,以便在 GA 中使用,特别是因为路径的长度是可变的。
有谁知道如何做这样的事情?
我不确定你的表示问题到底是什么,所以我怀疑你有这个问题是因为误解了 GA 的染色体字符串。从理论上讲,如果您采取额外的步骤来划分您的单个基因,则不必在整数边界上明确重组染色体串,这将允许您在逐个基因的基础上进行重组。这解决了可变长度基因的问题,例如您的“路径”。重组可变长度基因只是在突变方法中添加另一个变体,特别是“使用这个元素或核对这个元素”,除了标准的“使用来自 A 的元素或来自 B 的元素”,如果你的基因可以分解成离散的元素,就像你的路径一样。
听起来您真的很想使用A* 优化算法之类的东西,它通常(效果很好)用于寻路。您可以指定任何您喜欢的启发式函数以获得适当的解决方案。
我会使用 U、D、L、R....
所以“上 4,左 8,下 3,右 3,下 1,左 10,上 4,左 1,上 3”将是:
UUUULLLLLLLLDDDRRRDLLLLLLLLLLLUUUULUUU
像这样繁殖字符串会容易得多。
对于 A(15 个字符)和 B(3 个字符),我在 A 和 B 之间的育种功能是:
GA 可以处理可变长度的染色体。实际个体可能非常复杂。例如,它可以包含一些固定长度的位、字符串(没有固定长度),可能还有一些共轭复数对。此外,共轭复数对必须始终保留一些条件。可以做到,但个体越复杂,遗传操作就越复杂(例如交叉、突变)。可能健身功能需要更多的代码行。但这仍然是可能的。
也许正如建议的那样,您可以选择数字编码的路径表示,但仍然可以使用您的示例编码为Osama ALASSIRY建议: UUUULLLLLLLLDDDRRRDLLLLLLLLLLLUUUULUUU。
对于交叉:
为了清楚起见:
父 A:UUUULLLLLLLLDDDRRRDLLLLLLLLLUUUULUUU
父 B:DRRRRLULUDDDR
你生成随机对pairA(4,18),pairB(0,5)假设你从0开始计算基因你交换以下字符串:
UUUU LLLLLLLLDDDRRRD LLLLLLLLLLUUUULUUU
DRRRRL ULUDDDR
所以交叉后你得到
UUUU DRRRRL LLLLLLLLLLUUUULUUU
LLLLLLLLDDDRRRD ULUDDDR
现在你刚刚跨越。您也可以使用一个切割点或多个点。
至于突变:
你刚刚做了突变。您还可以突变多个基因。
但正如我所说,还有其他可能性。
对我来说,这听起来与旅行推销员问题非常相似,该页面是否包含一些有用的信息?