在Python前瞻算法 [英] lookahead algorithm in Python

问题描述

予具有50顶点和边70的网络（图形）。予反复通过添加两个顶点的量一个新的边缘最提高给定的适宜度量之间的边缘生长此网络。这工作得很好放眼望去只有一步，但我想看看，如果我得到更好的结果放眼望去n步。

I have a network (a graph) of 50 vertices and 70 edges. I grow this network iteratively by adding an edge between the two vertices for which a new edge improves a given fitness metric the most. This works quite well looking ahead just one step, but I'd like to see if I get better results looking ahead n steps.

所以...我想，以发现网络上最好的反复变化组合，通过超前n步进入期货来实现搜索算法。

So... I am trying to implement a search algorithm in order to find the network's best combination of iterative changes by looking ahead n steps into the futures.

这个算法应该评估网络之间的迭代t和健身差异网络在反复T + N，挑选带来最佳的健身改善道路的第一步，并再次期待n步向前，重复，直到我到了一个足够好的网络整体健康。

This algorithm should evaluate the fitness difference between the network at iteration t and the network at iteration t+n, pick the first step of the path that leads to the best fitness improvement, and once again look n steps ahead, repeat until I reach a good enough overall network fitness.

唉，我有很多困难包我的头解决此问题。我想，我设法硬℃的算法，展望只需两步$ C $，但它没有看起来很不错，绝对不会轻易扩展到其他步骤我想试试。这是不好的，但应该足以使我的问题更加清晰。

Alas, I'm having a lot of difficulties wrapping my head around this problem. I think I managed to hard-code an algorithm that looks ahead just two steps, but it's not looking good and is definitely not easily scalable to other steps I'd like to try. It's bad, but it should be enough to make my question clearer.

下面是我的code，和我的问题：

Here's my code, and my question:

from igraph import *

def comp_delta(ER,ER_old): # evaluates the graph

n_modu = ER.modularity(ER.community_multilevel(return_levels=False),weights=None)
o_modu = ER_old.modularity(ER_old.community_multilevel(return_levels=False),weights=None)

return float(n_modu - o_modu) / float(o_modu)


graph = Graph.Erdos_Renyi(30, .1, directed=False, loops=False) # create a random root graph of density 0.1
rootGraph = graph

score = []

# STEP 1
for n1 in range(30):
    for n2 in range(n1,30):
        if graph.are_connected(graph.vs[n1],graph.vs[n2]) == False and n1 != n2:
            graphOld = graph.as_undirected()
            graph.add_edge(rootGraph.vs[n1],rootGraph.vs[n2])
            graphStep1 = graph

            # STEP 2
            for d1_1 in range(30):
                for d1_2 in range(d1_1,30):
                    if graph.are_connected(graph.vs[d1_1],graph.vs[d1_2]) == False and d1_1 != d1_2:
                        graphOld.add_edge(rootGraph.vs[d1_1],rootGraph.vs[d1_2])
                        score.append([n1,n2,d1_1,d1_2,comp_delta(graphOld,rootGraph)])
                        graphOld = graphStep1.as_undirected()

            graph = graphStep1.as_undirected()

print score # array that can be sorted to retrieve both the best score and its path.

如何改变这种code，所以我可以1）看n步走向未来，并检索导致了指标的最佳改进？

How to change this code so I can 1) look n steps into the future, and retrieve the path that led to the best improvement of the metric?

请让我知道，如果我没有说清楚，我会因此更新消息。非常感谢！

Please let me know if I'm not being clear, I'll update the message consequently. Thanks a lot!

推荐答案

如果您无法包裹你的头部周围的问题，你需要它分解成更小的步骤。

If you're having trouble wrapping your head around the problem, you need to break it into smaller steps.

想想你正在试图获得了这幅什么：

Think about what you're trying to acheive:

我想，以发现网络上最好的反复变化组合，通过超前n步进入期货来实现搜索算法

I am trying to implement a search algorithm in order to find the network's best combination of iterative changes by looking ahead n steps into the futures

和你的输入到系统中有：

And what your inputs to the system are:

• 在初始图
• 重复次数 N （可以说，我们选择3）
• 在排名函数，它确定一个图的健身（或者相对改善超过previous图）

• initial graph
• number of iterations n (lets say we choose 3)
• ranking function that determines fitness of a graph (or perhaps relative improvement over a previous graph)

因此​​，我们需要编写一个函数，它接受这些投入，并返回最佳的边缘一个新的图形补充说。

So we need to write a function that takes these inputs and returns a new graph with the optimal edge added.

def add_optimal_edge(graph, rank, n=1): # you don't need to pass in the rank function necessarily
    ...

现在是什么功能呢？那么每个下一代它必须遍历每一个可能的新优势，创造这个边缘增加了一个新的图形和新的图形比较旧的（基本上是你已经做的）。

Now what does this function do? Well for each future generation it has to iterate over every possible new edge, create a new graph with this edge added and compare the new graph to the old one (basically what you're already doing).

但它是如何确定哪些优势是最优的？那么对于每一个新的边缘有看新图，并遍历所有可能的新的优势，并为这些新的图形，然后遍历所有可能出现的新的边缘，新图的的这些的..等等。 。。而随后每一最终图形比较原始 - 选择所述最佳的第一步骤，基于所述原始图的最终生成的排名。 唷的

But how does it determine which edge is optimal? Well for each new edge it has to look at the new graph and iterate over all possible new edges and create new graphs for those and then iterate over all possible new edges and new graphs for those .. etc .. .and then compare each final graph to the original - selecting the optimal first step, based on the ranking of the original graph to the final generation. phew

我们需要一些code，它确实是这样的：

We want some code that does something like:

for generation in range(n):
    new_graphs = (graph.add_edge(e) for e in graph.possible_new_edges())

不过，后代将需要这样做在图列表（没有一个），所以也许从那里清单和工作开始了：

But subsequent generations will need to do this over a list of graphs (not a single one), so perhaps start out with a list and work from there:

graphs = [graph] # start off with just one graph
for generation in range(n):
    graphs = (graph.add_edge(e) for graph in graphs for e in graph.possible_new_edges())

本使用发电机COM prehensions使内存的使用情况并不气球失控，它不断改写图，使每个后续一代遍历一个大集。每个图再对比原来的，并找到最好的：

This uses generator comprehensions so that memory usage doesn't balloon out of control, and it keeps overwriting graphs so that each subsequent generation is iterating over a larger set. Then compare each graph to the original and find the best:

best = max(graphs, key=lambda g: rank(graph, g)) # select best graph by ranking it against original

好了，我们已经找到了最好的，但我们需要知道的第一代是带领我们到那里。做到这一点的一种方法是，我们去而不只是最新的图形跟踪previous图的路径，所以我们遍历项目，现在图的列表（路径）

Okay, we've found the best, but we need to know what the first generation was that led us to get there. One way to do that would be to track the path of previous graphs as we go instead of just the latest graph, so the items we're iterating over are now lists of graphs (a path)

def add_optimal_edge(graph, rank, n=1):
    paths = [[graph]] # start off with just one graph path, which contains a single graph
    for generation in range(n):
        # path[-1] is the latest graph for each generation
        paths = (path + path[-1].add_edge(e) for path in paths for e in path[-1].possible_new_edges())
    # select best path by comparison of final generation against original graph
    best = max(paths, lambda path: rank(graph, path[-1])) 
    return best[1] # returns the first generation graph

最后的结果是简洁的，但内在生成COM prehension有点长篇大论 - 你很可能重构了这一点，以生成函数，使其更具可读性。如果您在填写详细的我已经添加了额外的功能，你应该用自己的方式来解决。

The final result is concise, but the inner generator comprehension is a little long winded - you could probably refactor this out to a generator function to make it more readable. If you fill in the details for the extra functions I've added, you should be well on your way to a solution.

这篇关于在Python前瞻算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！