我手头有一个分配问题，我想知道应用局部搜索技术来达到理想的解决方案是否合适(搜索空间相当大)。
我有一个有向图(流程图)，我想在二维平面上以一种非常清晰，易懂且易于人眼阅读的方式进行可视化。因此;我将给每个顶点分配(x,y)个位置。我正在考虑用模拟退火、遗传算法或任何你能建议的方法来解决这个问题
输入: A graph G = (V,E)输出:一组赋值，
{(xi, yi) for each vi in V}。换句话说，每个顶点将被分配一个位置(x, y)，其中坐标均为整数且>= 0。
这些是我用来判断解决方案的标准(我欢迎任何建议):
- 相交边的数量应该是最小的，
- 所有边沿一个方向流动(即从左到右)，
- 高角度分辨率(两条边形成的最小角度) 面积小-最不重要。
此外;我有一个初始配置(分配位置到顶点)，手工制作。这是非常混乱的，这就是为什么我试图自动化的过程。
我的问题是，
使用本地搜索技术有多明智?可能性有多大它会产生一个理想的结果吗?
我应该从什么开始呢?模拟退火，遗传算法还是别的什么?
我应该在开始时随机播种还是使用初始的从配置开始?
或者，如果你已经知道一个类似的实现/伪代码/东西，请告诉我它
任何帮助都将非常感激。谢谢。
EDIT:它不需要很快-不是实时的。此外;|V|=~200，每个顶点平均有1.5条向外的边。图中没有断开的组件。它确实涉及到周期。
我建议您查看http://www.graphviz.org/Theory.php，因为graphviz是领先的开源图形可视化工具之一。
取决于任务是什么，也许使用graphviz进行可视化是有意义的。
这篇论文很好地概述了各种方法。Roberto Tomassia的书也是一个不错的选择。
http://oreilly.com/catalog/9780596529321 -在这本书中，你可能会发现用于2D图形精细可视化的遗传算法的实现。
在类似的情况下，我更喜欢使用遗传算法。您也可以从随机初始化人口开始—根据我的经验，经过几次迭代后，您将找到相当好的(但也不是最好的)解决方案。
同样，使用java你可以并行这个算法(孤岛策略)——这是相当有效的改进。
我还想建议你差分进化算法。从我的经验来看，它比遗传优化更快地找到解决方案。
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]);
}
}
函数操作可以翻转字符串的一些位或多个位或编码顶点x和y的部分，或者可能生成完全新的遗传字符串或尝试解决其中的问题(直接一条边)。
回答你的第一个问题，我必须说这要视情况而定。这取决于许多不同的因素，例如:
- 需要多快(需要实时完成吗?)
- 有多少个顶点
- 与顶点数量相比，有多少条边(即它是密集的还是稀疏的图?)
如果需要实时完成，那么本地搜索技术将不是最好的，因为它们可能需要一段时间才能得到一个好的结果。只有当图的大小很小时，它们才足够快。如果一开始就很小，你就不应该使用本地搜索。
已经有了你所描述的渲染图的算法。问题是，什么时候问题会变得太大，他们无法发挥作用?我不知道那个问题的答案，但我相信你可以做一些调查来找出答案。
现在继续你关于本地搜索实现的问题。
从我个人的经验来看，模拟退火比遗传算法更容易实现。然而，我认为这个问题可以很好地转化为两种情况。我想从SA开始。
对于模拟退火，您将从随机配置开始。然后，您可以通过将一个或多个顶点移动一段随机距离来随机打乱配置。我相信你能完成算法的细节。
对于遗传算法方法，您也可以从随机总体开始(每个图的顶点具有随机坐标)。突变可以像我描述的SA算法中的扰动一样。重组可以简单地从父图中随机取顶点，并在子图中使用它们。再一次，我相信你可以填补空白。
总结:只有当你的图形足够大，并且你不需要超级快(比如不到几秒钟)的时候，才使用本地搜索。否则请使用不同的算法。
编辑:根据你的图形参数，我认为你可以使用最容易编码的算法。当V=200时，即使是O(V^3)算法也足够了。我个人认为模拟退火是最简单和最好的方法。