遗传算法绘制图形？位置分配问题

Question

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

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

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

以下是我将用来评判解决方案的标准（我欢迎任何建议）：

1.交叉边的数量应该最小； 2.所有的边都从左到右流动； 3.高角分辨率（由两条边形成的最小角度，这些边都与同一个顶点相交）； 4.小区域-最不重要的。

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

我的问题是，

1.选择使用局部搜索技术是否明智？它有多大可能产生期望的结果？ 2.我应该从哪里开始？模拟退火、遗传算法还是其他什么？ 3.我应该在开始时随机种子还是使用初始配置？ 4.或者，如果你已经知道类似的实现/伪代码/东西，请指引我。

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

编辑：它不需要快速-不是实时的。此外；|V|=~200，每个顶点平均有1.5个出边。图形没有断开的组件。它包含循环。

- Murat Derya Özen

---

主要任务是绘制图形吗？关于图形绘制已经有很多研究了，你应该先阅读相关资料……如果这不是你的主要任务，那么就使用一些现有的库来完成图形绘制部分。 - Szabolcs

你是否找到了一种解决方案，如何在基因中存储坐标和边缘，以创建不那么复杂的遗传算法？我的意思是，你决定将其存储为具有1,0值的字符串，还是你已经找到了一种存储坐标和边缘的解决方案？ - kuldarim

Answer 1

我建议查看http://www.graphviz.org/Theory.php，因为graphviz是领先的开源图形可视化工具之一。根据任务的不同，也许使用graphviz进行可视化是有意义的。

- Leonard Brünings

Answer 2

这篇论文是对各种方法的相当不错的概述。罗伯托·托马西亚的书也是一个不错的选择。

- MPG

---

谢谢MPG。这篇论文真的很好，但它没有指向一个坚实的算法。它只是一个概述。此外，书评说它大多充满理论，但没有实际实现。 - Murat Derya Özen

Answer 3

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;

编写一个函数double evaluate(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]);
    }
}

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

- Sherif elKhatib

---

在许多问题中，从数字向量到位向量的转换是不必要的。但如果您想这样做，我建议使用格雷码。 - stemm

Answer 4

http://oreilly.com/catalog/9780596529321 - 这本书中可能会有关于二维图形优化的遗传算法实现。

在类似的情况下，我更喜欢使用遗传算法。此外，您可以从随机初始化种群开始 - 根据我的经验，在几次迭代后，您会找到相当不错（但也不是最好的）的解决方案。

此外，使用Java，您可以并行运行此算法（孤立岛策略）- 这是相当有效的改进。

另外，我想向您推荐差分进化算法。根据我的经验 - 它比遗传优化更快地找到解决方案。

- stemm

---

我在那本书中没有找到任何用于精细可视化二维图形的遗传算法实现。 - Dang Manh Truong

Answer 5

回答你的第一个问题，我必须说这取决于许多不同的因素，例如：

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

如果需要实时完成，则本地搜索技术不是最佳选择，因为在获得良好结果之前可能需要运行一段时间。只有当图的大小很小时，它们才足够快。如果一开始就很小，那么你不应该使用本地搜索。

已经有算法可以呈现你描述的图形了。问题是，在什么时候问题变得太大，以至于它们无法有效解决？我不知道这个问题的答案，但我相信你可以进行一些研究来找出答案。

现在转到关于实现本地搜索的问题。

从我的个人经验来看，模拟退火比遗传算法更容易实现。但是，我认为这个问题在两种情况下都可以很好地解决。不过，我会先从SA开始。

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

对于遗传算法方法，您也可以从随机种群开始（每个图形都具有顶点的随机坐标）。突变可以像我描述的SA算法中的扰动一样。重组可以简单地从父母中选择随机顶点并在子图中使用它们。同样，我相信您可以填补空白。

总之：仅当您的图形足够大且不需要快速完成（例如少于几秒钟）时，才使用局部搜索。否则，请使用其他算法。

编辑：根据您的图形参数，我认为您可以只使用最容易编码的算法。对于V=200，即使是O（V ^ 3）算法也足够了。就个人而言，我觉得模拟退火算法最容易且最佳。

- tskuzzy

---

感谢tskuzzy的回答。我通过编辑原帖回答了你的问题。它不需要快速 - 不是实时的。此外; |V|= ~200，每个顶点平均有1.5个出边。我会尝试其他现有的方法来看看它们需要多长时间... - Murat Derya Özen

已根据要求修改了我的回答。 - tskuzzy