logo

SCIENTIA SINICA Informationis, Volume 50 , Issue 10 : 1501(2020) https://doi.org/10.1360/N112018-00260

A warning propagation algorithm to solve the double-objective minimum spanning tree

More info
  • ReceivedJan 16, 2019
  • AcceptedAug 13, 2019
  • PublishedOct 12, 2020

Abstract


Funded by

国家重点研发计划(2017YFE0117500)

国家自然科学基金(61462001,61762019,61862051)

北方民族大学重点科研项目(2017KJ24,2017KJ25)

北方民族大学重大专项(ZDZX201901)

计算机应用技术自治区重点学科项目

自治区优势特色学科项目

2018宁夏回族自治区重点研发计划项目(2018BEE03019)

宁夏高等学校一流学科建设(电子科学与技术学科)(NXYLXK2017A07)

宁夏自然科学基金项目(2019AAC03120)


References

[1] Yan W M, Wu W M. Data Structure. 2nd ed. Beijing: Tsinghua University Press, 1992. 168--174. Google Scholar

[2] Zhou G, Gen M. Genetic algorithm approach on multi-criteria minimum spanning tree problem. Eur J Operational Res, 1999, 114: 141-152 CrossRef Google Scholar

[3] Chen G L, Guo W Z, Tu X Z. An Improved Algorithm to Solve the Multi-Criteria Minimum Spanning Tree Problem. J Software, 2006, 17: 364-370 CrossRef Google Scholar

[4] Guo W Z, Chen G L. An effective discrete particle swarm optimization algorithm for solving multi-objective minimum spanning tree problem. Pattern recognition and artificial intelligence, 2009, 22(04):597-604. Google Scholar

[5] Dyer M, Frieze A, Molloy M. A probabilistic analysis of randomly generated binary constraint satisfaction problems. Theor Comput Sci, 2003, 290: 1815-1828 CrossRef Google Scholar

[6] Martin O C, Monasson R, Zecchina R. Statistical mechanics methods and phase transitions in optimization. Theory Computer Science, 2001, 265: 3-67. Google Scholar

[7] Friedgut E, Bourgain J. J Amer Math Soc, 1999, 12: 1017-1055 CrossRef Google Scholar

[8] Kaporis A C, Kirousis L M, Lalas E G. The probabilistic analysis of a greedy satisfiability algorithm. Random Struct Alg, 2006, 28: 444-480 CrossRef Google Scholar

[9] Dubois O, Boufkhad Y, Mandler J. Typical random 3-sat formulae and the satisfiability threshold. Electronic Colloquium on Computational Complexity, 2003, 10(007): 1-2. Google Scholar

[10] Mézard M, Parisi G. J Statistical Phys, 2003, 111: 1-34 CrossRef Google Scholar

[11] Mézard M, Zecchina R. Random K-satisfiability problem: From an analytic solution to an efficient algorithm. Phys Rev E, 2002, 66: 056126 CrossRef PubMed ADS Google Scholar

[12] Maneva E, Mossel E, Wainwright M J. A new look at survey propagation and its generalizations. J ACM, 2007, 54: 17-es CrossRef Google Scholar

[13] Braunstein A, Mézard M, Zecchina R. Survey propagation: An algorithm for satisfiability. Random Struct Alg, 2005, 27: 201-226 CrossRef Google Scholar

[14] Yedidia J S, Freeman W T, Weiss Y. Understanding belief propagation and its generalizations. Artif Intell, 2003, 8: 239--269. Google Scholar

[15] Aurell E, Gordon U, Kirkkpatrick S. Comparing beliefs, surveys, and random walks. In: Proceedings of Advances in Neural Information Processing Systems, 2004. 17: 1--8. Google Scholar

[16] Kroc L, Sabharwal A, Selman B. Survey propagation revisited. In: Proceedings of the 23rd Conference on Uncertainty in Artificial Intelligence, Corvallis, 2007. 217--226. Google Scholar

[17] Feige U, Mossel E, Vilenchik D. Theor Comput, 2013, 9: 617-651 CrossRef Google Scholar

[18] Creignou N, Daudé H. The SAT-UNSAT transition for random constraint satisfaction problems. Discrete Math, 2009, 309: 2085-2099 CrossRef Google Scholar

[19] Xu K, Li W. Exact Phase Transitions in Random Constraint Satisfaction Problems. jair, 2000, 12: 93-103 CrossRef Google Scholar

[20] Braunstein A, Zecchina R. Survey and belief propagation on random k-SAT. In: Proceedings of International Conference on Theory and Applications of Satisfiability Testing, 2004. 2919: 519--528. Google Scholar

[21] Kschischang F R, Frey B J, Loeliger H A. Factor graphs and the sum-product algorithm. IEEE Trans Inform Theor, 2001, 47: 498-519 CrossRef Google Scholar

[22] Weiss Y. Correctness of Local Probability Propagation in Graphical Models with Loops. Neural Computation, 2000, 12: 1-41 CrossRef Google Scholar

[23] Weiss Y, Freeman W T. Correctness of belief propagation in Gaussian graphical models of arbitrary topology.. Neural Computation, 2001, 13: 2173-2200 CrossRef PubMed Google Scholar

  • Figure 1

    An instance of factor graph

  • Figure 2

    A model transformation instance of RBM

  • Figure 3

    Schematic diagram of transformation principle

  • Table 1   Parameters of 6 groups of random undirected graphs with different numbers of nodes
    $n$ $m$ $\alpha$ $d$
    100 4950 49.5 3.475
    150 11175 74.5 3.475
    200 19900 99.5 3.475
    300 44850 149.5 3.475
    350 61075 174.5 3.475
    400 79800 199.5 3.475
  •   

    Algorithm 1 Factor graph transformation algorithm

    Require:Random bigraph instance $G$;

    Output:Factor graph $F$;

    A random bigraph instance is selected;

    Select the initial point randomly $v\in~V$ as the starting point of transformation;

    while $v~\le~V$ do

    if $v$ is not the isolated point then

    The bigraph edge $e\in~E$ is mapped to a clause node of the factor graph;

    Two sets of weights on the edge of a bigraph are mapped to two nodes of a factor graph;

    else

    Draw auxiliary edges to connect outliers;

    $v=v+1$;

    end if

    end while

    Add a binary tag bit to each edge and map it to the third argument node;

  •   

    Algorithm 2 Warning propagation algorithm for solving double objective minimum spanning tree

    Require:Factor graph $F$; Maximum number of iterations $t_{\rm~max}$; a requested precision $\varepsilon$;

    Output:The number of nodes in the minimum spanning tree $\eta~_{a\rightarrow~i}^{*}$;

    Get the factor graph by Algorithm 1;

    A node is randomly selected as the initial iteration node $n_{i}\in~V$;

    At time $t\leftarrow~0$, for every edge of the factor graph init the warning messages $W_{a\rightarrow~i}\in\left~\{~0,~1~\right~\}$;

    Let us do a random permutation of the edges in $G$;

    Using 2 to update the warning information until the algorithm converges;

    while $t~\le~t_{\rm~max}$ do

    Sweep the set of edges in the factor graph and update the warning information;

    if $\left~|\eta~_{a\rightarrow~i}(t)-\eta~_{a\rightarrow~i}(t-1)~~\right~|<~\varepsilon~$ then

    Takes the convergent nodes to form the nodes of the double-objective minimum spanning tree;

    else

    Continue;

    end if

    Break;

    end while

    The sum of the weights of two variable nodes representing weights in the factor graph is calculated respectively;

    Get part of the assignment;

  • Table 2   Comparison of the running time of MACS algorithm and WP algorithm (s)
    The number of node Enumeration MACS WP
    20 3360 552. 6 20. 423
    30 8700 681 30. 697
    40 20580 847. 2 40. 537
    50 45900 1095. 6 51. 018