遗传算法画图？职位分配问题

Question

我手头有一个分配问题，想知道应用本地搜索技术来达到理想的解决方案是否合适（搜索空间相当大）。

我有一个有向图（流程图），我希望以一种非常清晰、易于理解且易于人眼阅读的方式在二维平面上可视化。所以;我将为每个顶点分配 (x,y) 位置。我正在考虑使用模拟退火、遗传算法或您建议的任何此类方法来解决这个问题

输入：图 G = (V,E)
输出：一组分配，{(xi, yi) for every vi in V}。换句话说，每个顶点将被分配一个位置（x，y），其中坐标都是整数并且> = 0。

这些是我将用来判断解决方案的标准（我欢迎任何建议）：

• 相交的数量边缘应该是最小的，
• 所有边缘都沿一个方向流动（即从左到右），
• 高角度分辨率（两条边缘形成的最小角度 事件发生在同一顶点），
• 小区域 - 最不重要。

此外;我有一个手工制作的初始配置（将位置分配给顶点）。它非常混乱，这就是为什么我试图使这个过程自动化。

我的问题是，

• 采用本地搜索技术有多明智？有多大可能 它会产生预期的结果吗？

• 我应该从什么开始？模拟退火、遗传算法 或者其他什么？

• 我应该在开始时随机播种还是使用初始 配置开始？

• 或者，如果您已经知道类似的实现/伪代码/事物，请指出我。

任何帮助将不胜感激。谢谢。

编辑：它不需要很快 - 不是实时的。此外; |V|=~200 并且每个顶点平均有大约 1.5 条出边。该图没有断开连接的组件。它确实涉及循环。

Answer 1

我建议查看 http://www.graphviz.org/Theory.php 因为 graphviz 是领先的开源图形可视化工具之一。

根据任务的具体内容，也许完全使用 graphviz 进行可视化是有意义的。

Answer 2

这篇论文是一个很好的概述的各种方法。 Roberto Tomassia 的书也是一个不错的选择。

Answer 3

http://oreilly.com/catalog/9780596529321 - 在本书中，您可能会找到遗传算法的实现二维图的精细可视化。

在类似的情况下，我更喜欢使用遗传算法。另外，您可能会从随机初始化的群体开始 - 根据我的经验，经过几次迭代后，您会发现非常好的（但也不是最好的）解决方案。

另外，使用java你可以并行这个算法（孤岛策略）——这是相当有效的改进。

另外我想建议你差分进化算法。根据我的经验 - 它比遗传优化更快地找到解决方案。

Answer 4

function String generateGenetic()
String genetic = "";
for each vertex in your graph
    Generate random x and y;
    String xy = Transform x and y to a fixed-length bit string;
    genetic + = xy;
endfor
return genetic;

编写一个函数 doublevaluate(String Genetic) 这会给你带来一定程度的满意。 （可能基于有多少条边相交和边方向。

您的程序：

int population = 1000;
int max_iterations = 1000;
double satisfaction = 0;
String[] genetics = new String[population]; //this is ur population;
while((satisfaction<0.8)&&(count<max_iterations)){
    for (int i=0;i<population;i++){
        if(evaluate(genetics[i])>satisfaction)
            satisfaction = evaluate(genetics[i]);
        else
            manipulate(genetics[i]);
    }
}

函数操作可以翻转字符串的某些位或多个位或编码顶点的 x 和 y 的部分，或者可能完全生成一个新的遗传字符串或尝试解决其中的问题（直接边缘）。

Answer 5

为了回答你的第一个问题，我必须说这要看情况。这取决于许多不同的因素，例如：

• 需要多快（是否需要实时完成？）
• 有多少个顶点
• 与顶点数量相比，有多少条边（即是密集图还是稀疏图？）

如果需要实时完成，那么本地搜索技术将不是最好的，因为它们可能需要一段时间才能获得良好的结果。只有当图表尺寸很小时，它们才会足够快。如果一开始就很小，那么您不必一开始就使用本地搜索。

正如您所描述的，已经有用于渲染图形的算法。问题是，到什么时候问题会变得太大以至于他们无法发挥作用？我不知道这个问题的答案，但我相信你可以做一些研究来找出答案。

现在继续回答有关实施本地搜索的问题。

从我个人的经验来看，模拟退火比遗传算法更容易实现。不过我认为这个问题可以很好地转化为两种设置。不过我会从 SA 开始。

对于模拟退火，您将从随机配置开始。然后，您可以通过将一个或多个顶点移动一段随机距离来随机扰动配置。我相信你可以完成算法的细节。

对于遗传算法方法，您还可以从随机群体开始（每个图都有随机的顶点坐标）。突变可以像我描述的 SA 算法中的扰动一样。重组可以简单地从父母那里获取随机顶点并在子图中使用它们。再次强调，我相信你可以填空。

总结：仅当您的图表足够大且不需要快速完成（例如不到几秒）时，才使用本地搜索。否则使用不同的算法。

编辑：根据您的图形参数，我认为您可以只使用最容易编码的算法。当 V=200 时，即使 O(V^3) 算法也足够了。我个人认为模拟退火是最简单也是最好的途径。