Prolog中的网络模块化优化

Question

我正在研究prolog中的网络模块化优化。

我想最大化Q，其中Q是每个模块的模块分数之和。模块得分是模块中的边数(Lm)除以网络中的边数(L)减去模块中节点的度数之和(Dm)除以网络中的边数平方的两倍。

Modscore = (Lm/L) - (Dm/2L)^2

Q= sum(Modscores)

因此，每个节点都被随机分配了一个模块，然后我想输出一个节点到模块的最优分配。其中最多可以有n个模块。如果边的两个节点都在同一模块中，则该边在模块中。

在prolog中有没有简单的库或方法来优化这样的值？我看过：http://www.swi-prolog.org/man/clpfd.html，但这似乎并不合适，因为我希望优化的值不是整数(但模块的节点分配是..)。这是对的还是我错了？

这个任务真的不适合prolog吗？我用python编写了一个遗传算法来解决这个问题，我知道还有一些其他语言的优化算法和工具箱。但我感兴趣的是在prolog中做这件事有多容易或多难。

%Modularity in prolog
%Undirected & unweighted
%not a multigraph


number_of_edges(L):-
    findall(Edge_Id, edge(Edge_Id, X, Y), Edge_Ids), length(Edge_Ids, L).

edge_in_module(Edge_Id, Module):-
    edge(Edge_Id, X, Y),
    node_in_module(X, Module),
    node_in_module(Y, Module).

edges_in_module(Edge_Ids, Module):-
    bagof(Edge_Id, edge_in_module(Edge_Id,Module), Edge_Ids).

degree_of_node(Node, Degree):-
    findall(Connected_Node,edge(_, Node, Connected_Node), Connected_Nodes),               length(Connected_Nodes, OutDegree),
    findall(Connected_Node2,edge(_, Connected_Node2, Node), Connected_Nodes2), length(Connected_Nodes2,InDegree),
    Degree is InDegree + OutDegree.

degree_of_node_in_module(Node,Module,Degree):-
    node_in_module(Node, Module),
    degree_of_node(Node,Degree).

list_sum([Item], Item).
list_sum([Item1,Item2 | Tail], Total) :-
    list_sum([Item1+Item2|Tail], Total).

mod_score(Module, Mod_score):-
    findall(Degree, degree_of_node_in_module(Node,Module,Degree), Degrees),
    list_sum(Degrees, Dm),
    edges_in_module(Edges, Module),
    length(Edges, Lm),
    number_of_edges(L),
    LmOverL is Lm / L,
    DmOver2L is Dm / (2*L),
    SecondTerm is DmOver2L*DmOver2L,
    Mod_score is LmOverL- SecondTerm.

%空手道图形%

edge(edge1,node10,node3).
edge(edge2,node11,node1).
edge(edge3,node11,node5).
edge(edge4,node11,node6).
edge(edge5,node12,node1).
edge(edge6,node13,node1).
edge(edge7,node13,node4).
edge(edge8,node14,node1).
edge(edge9,node14,node2).
edge(edge10,node14,node3).
edge(edge11,node14,node4).
edge(edge12,node17,node6).
edge(edge13,node17,node7).
edge(edge14,node18,node1).
edge(edge15,node18,node2).
edge(edge16,node2,node1).
edge(edge17,node20,node1).
edge(edge18,node20,node2).
edge(edge19,node22,node1).
edge(edge20,node22,node2).
edge(edge21,node26,node24).
edge(edge22,node26,node25).
edge(edge23,node28,node24).
edge(edge24,node28,node25).
edge(edge25,node28,node3).
edge(edge26,node29,node3).
edge(edge27,node3,node1).
edge(edge28,node3,node2).
edge(edge29,node30,node24).
edge(edge30,node30,node27).
edge(edge31,node31,node2).
edge(edge32,node31,node9).
edge(edge33,node32,node1).
edge(edge34,node32,node25).
edge(edge35,node32,node26).
edge(edge36,node32,node29).
edge(edge37,node33,node15).
edge(edge38,node33,node16).
edge(edge39,node33,node19).
edge(edge40,node33,node21).
edge(edge41,node33,node23).
edge(edge42,node33,node24).
edge(edge43,node33,node3).
edge(edge44,node33,node30).
edge(edge45,node33,node31).
edge(edge46,node33,node32).
edge(edge47,node33,node9).
edge(edge48,node34,node10).
edge(edge49,node34,node14).
edge(edge50,node34,node15).
edge(edge51,node34,node16).
edge(edge52,node34,node19).
edge(edge53,node34,node20).
edge(edge54,node34,node21).
edge(edge55,node34,node23).
edge(edge56,node34,node24).
edge(edge57,node34,node27).
edge(edge58,node34,node28).
edge(edge59,node34,node29).
edge(edge60,node34,node30).
edge(edge61,node34,node31).
edge(edge62,node34,node32).
edge(edge63,node34,node33).
edge(edge64,node34,node9).
edge(edge65,node4,node1).
edge(edge66,node4,node2).
edge(edge67,node4,node3).
edge(edge68,node5,node1).
edge(edge69,node6,node1).
edge(edge70,node7,node1).
edge(edge71,node7,node5).
edge(edge72,node7,node6).
edge(edge73,node8,node1).
edge(edge74,node8,node2).
edge(edge75,node8,node3).
edge(edge76,node8,node4).
edge(edge77,node9,node1).
edge(edge78,node9,node3).

%随机分配给两个模块%

node_in_module(node1,1).
node_in_module(node2,1).
node_in_module(node3,2).
node_in_module(node4,1).
node_in_module(node5,1).
node_in_module(node6,1).
node_in_module(node7,2).
node_in_module(node8,2).
node_in_module(node9,1).
node_in_module(node10,2).
node_in_module(node11,2).
node_in_module(node12,2).
node_in_module(node13,2).
node_in_module(node14,2).
node_in_module(node15,2).
node_in_module(node16,1).
node_in_module(node17,1).
node_in_module(node18,1).
node_in_module(node19,2).
node_in_module(node20,1).
node_in_module(node21,1).
node_in_module(node22,1).
node_in_module(node23,1).
node_in_module(node24,1).
node_in_module(node25,1).
node_in_module(node26,2).
node_in_module(node27,2).
node_in_module(node28,2).
node_in_module(node29,2).
node_in_module(node30,1).
node_in_module(node31,2).
node_in_module(node32,1).
node_in_module(node33,2).
node_in_module(node34,1).

Answer 1

非常非常难。

您说得对，CLP不能用来解决这个问题，因为没有合适的域。每个CLP求解器都使用目标域的知识进行了大量的调优，并且没有一个可以在图上模拟任意属性。自从我上一次使用SWI或Ciao用于CLP以来，已经过去了大约五年，但如果在您尝试在图的顶点的powerset上求解方程时，这种情况发生了变化，我会感到非常惊讶。

Raw Prolog真的很糟糕，大量使用findall对于确定图结构上的传递属性是必要的，但几乎打破了指称语义。Prolog最擅长表达像列表或树这样复杂的结构之间的声明性映射。图要稍微复杂一点，因为一旦它们包含循环，它们就不能用无引用的表示法来表示。

Prolog的另一个问题是，它没有指定解决方案策略，而不是蛮力。如果你想要更复杂的东西，那么你需要写一个元解释器。一旦你走上了这条路，如果你的解决方案策略包括任何类型的随机化，那么你必须询问你将如何在你的域中生成对象的随机实例。尽管将模块实例视为整数允许简单生成，但搜索偏差非常弱，这导致了一个问题:您将如何改进随机盲搜索？另一方面，如果你想编码更强的搜索偏差，那么你如何生成对象的随机实例呢？除非它们有一个到整数的规范映射，否则这将变得非常困难。