我正在尝试开发一种遗传算法，该算法将找到在指定位置连接给定数量节点的最有效方法。
网络上的所有节点都必须能够连接到服务器节点，并且网络内必须没有循环。它基本上是一棵树。
我有一个可以测量任何给定网络布局的“适合度”的功能。阻止我的是，我想不出一个交叉函数需要 2 个网络结构（父母）并以某种方式混合它们来创建满足上述条件的后代。
有任何想法吗？
澄清：每个节点都有一个固定的 x,y 坐标位置。只能更改它们之间的路线。
问问题
1772 次
7 回答
3
Amir-我认为这个想法是每个生成的树都将包含相同的节点集，以不同的顺序排列。
也许与其使用基于交叉的遗传算法，不如使用受生物学启发较少的爬山算法？定义一组交换（例如，在节点之间交换子节点）以充当可能的突变，然后迭代地突变并检查您的适应度函数。与所有此类搜索一样，您很容易陷入局部最大值，因此从不同的起始位置进行多次运行是个好主意。
于 2009-12-30T20:39:35.570 回答
1
让我先用一个问题回答你的问题：
如果您创建的网络布局违反了“无循环”规则和“连接到服务器”规则，适应度函数会如何表现？
如果它只是通过较差的适应度分数来惩罚给定的网络布局，你不需要做任何特别的事情，除了取两个网络布局并将它们交叉，布局 A 的 1/2，布局 B 的 1/2。这是一个非常基本的交叉功能，它应该可以工作。
但是，如果您负责构建一个有效的布局并且不能依赖于简单地清除无效布局，那么您将需要做更多的工作。
于 2009-12-30T20:33:19.593 回答
1
遗传算法中交叉的目的是潜在地将来自一个父母的良好部分解决方案与另一个父母的解决方案混合。在这种情况下考虑部分解决方案的一种方法可能是紧密连接节点的子树。如果您的适应度函数在整个树的局部部分的微小变化方面相当平滑，那么这可能是考虑交叉的有用方法。
鉴于此，一种可能的交叉形式如下：
从两个父树P1和P2开始。随机选择两个节点（可能对节点之间的最小距离进行某种强制），N1和N2。
在逐个节点的基础上，根据P1中的链接从N1向外“生长”一棵树C1，同时从P2开始从N2向外生长另一棵树。不要将相同的节点添加到两棵树 - 保持节点集完全不相交。继续，直到所有节点都已添加到C1或C2。这为我们提供了来自每个父母的“特征”以保证是无环的形式进行重组。
重组是通过添加一个额外的链接来完成的，从C1到C2，以创建新的子C。至于选择哪个链接，可以随机选择（均匀地或根据某种分布），也可以通过贪心算法（基于某种启发式，或新树C的整体适应度）来选择。
于 2009-12-31T10:00:38.230 回答
1
您可以检查交叉运算符，以确保子染色体中没有重复节点。这些交叉算子中有几个是阶交叉（OX）和边缘交叉算子。这种交叉算子也有助于使用 GA 求解 TSP。
之后，您将不得不检查是否有任何周期。如果是，则生成一对新的染色体。这当然是蛮力。
于 2009-12-31T10:27:12.530 回答
0
一个尝试的想法：在度量空间（例如 3 维欧几里得空间）中编码节点的位置。没有“不正确”的分配，因此交叉永远不会具有破坏性。从这样的分配中，您总是可以构建最近邻树、最小生成树或类似树。
这只是一个更一般的想法的示例：不要直接对树进行编码，而是对一些始终可以构建树的信息进行编码。棘手的部分是这样做的方式是让子树保留父母的重要属性。
于 2009-12-30T22:42:34.110 回答
0
在早期的一个会议上，有一篇论文为旅行推销员提出了以下算法，我已经成功地对几个图问题进行了调整：
在整个 POPULATION 中，按连接数降序计算并排序节点（也就是说，如果 N0 在某些个体中连接到 N1、N2、N3，它有 3 个连接，如果 N1 总是连接到 N4，它只有1）。
最初，取计数最高的节点。将此称为 current_gene_node。（比如说，N0）
循环：将 current_gene_node 添加到您的后代。
从连接列表中删除该节点。（没有循环，因此不再考虑 N0。）
如果 current_gene_node 在种群中没有连接，则在种群中随机选择一个未选择的节点（突变）
否则，从该节点的连接列表中，根据整个人口中连接的流行程度进行抽签选择（如果 current_gene_node = N0，并且连接 N0 是，例如，N1 = 50%，N2 = 30%，N3 = 20 % -- N1 有 50% 的机会成为下一个 current_gene_node)。
转到 LOOP 直到所有节点都连接
从直接从两个父母那里选择的意义上说，这并不是真正的遗传，但它遵循基于人口流行率选择的相同数学压力。所以它对我来说“足够遗传”，对我来说效果很好:-)
于 2010-01-25T19:14:27.320 回答