home *** CD-ROM | disk | FTP | other *** search
/ Monster Media 1993 #2 / Image.iso / text / 9305nni.zip / 930503.BIB < prev    next >
Text File  |  1993-05-03  |  4KB  |  114 lines
  1. Article 8960 of comp.ai.neural-nets:
  2. Newsgroups: comp.ai.neural-nets
  3. Path: serval!netnews.nwnet.net!usenet.coe.montana.edu!saimiri.primate.wisc.edu!zaphod.mps.ohio-state.edu!howland.reston.ans.net!noc.near.net!lynx!hilbert!george
  4. From: george@hilbert.coe.northeastern.edu (George Kechriotis)
  5. Subject: summary of responses to minimum cover question
  6. Message-ID: <1993May3.225754.8004@lynx.dac.northeastern.edu>
  7. Sender: usenet@lynx.dac.northeastern.edu (usenet dummy)
  8. Organization: CDSP Computing Lab, Northeastern University
  9. Date: Mon, 3 May 1993 22:57:54 GMT
  10. Lines: 100
  11.  
  12.  
  13.  
  14. Thanks to everybody who responded to my minimum
  15. cover/Hopfield Neural Net question. Although I 
  16. didn't had time yet to search all the bibliography
  17. and to try out the proposed methods, it seems that 
  18. a good algorithm can be found.
  19.  
  20. Here are some of the responses that I received:
  21.  
  22. ================================================================
  23. Hi,
  24.  
  25. You may want to look up the following paper:
  26.  
  27. P.P. Chu, "Using a semi-asynchronous Hopfield Network to
  28. Obtain Optimal Coverage in Logic Minimization," in Proc.
  29. Intl. Joint Conf. on Neural Networks, IEEE Press, New York,
  30. NY, pp. 141-146, 1991.
  31. ================================================================
  32. You can try by moving the constraints up in the original objective with
  33. some log barrier function, for instance. (Have a look in the bibliography
  34. of the interior point methods and barrier functions). That way you
  35. change your original problem from a costrainted optimization to an
  36. unconstrained one.
  37. ================================================================
  38. There are two aspects to constructing a Hopfield Net to solve such
  39. problems.  The first is the representational issue, which you discussed
  40. in your posting (summarized above), and which I refer to as the
  41. "statics" issue.  The second issue is network "dynamics".  Most
  42. representations give poor performance, because they result in poor
  43. dynamics.  For instance, the N*N permutation matrix representation, used
  44. by Hopfield and Tank for the TSP, leads to poor dynamics.  My guess is
  45. that the minimum cover representation that you proposed will not lead to
  46. satisfactory network dynamics.
  47.  
  48. The work of Sorkin (1990) indicates that the network dynamics should
  49. implement a fractal energy landscape.  I explored that issue in a recent
  50. paper:
  51.  
  52. Lister, R (1993), "Annealing Networks and Fractal Landscapes",
  53.                   IEEE International Conference on Neural Networks,
  54.                   San Francisco, March 1993, Vol. I, pp 257-262.
  55. ================================================================
  56. I just read Lister's reply to your message in comp.ai.neural-nets. Perhaps you
  57. have all the information you need by now; I thought I'd reply in any case.
  58.  
  59. By "minimum cover" I suppose you mean "minimum vertex cover". (Your formulation
  60. as I saw it in Lister's reply suggested that).
  61.  
  62. The following describes two Hopfield net formulations of minimum vertex cover
  63. (and reviews several earlier Hopfield net formulations of it).
  64.  
  65. @inproceedings{Jag92f,
  66.        author = "Jagota, A.",
  67.         title = "Optimization by Reduction to Maximum Clique",
  68.     booktitle =  "International Conference on Neural Networks",
  69.  organization = "San Francisco",
  70.     publisher = "IEEE",
  71.       address = "New York",
  72.        note = "Submitted To",
  73.        month= "March",
  74.          year =  1993
  75.   }
  76.  
  77. If you do not have easy access to the proceedings, you may retrieve the Latex
  78. source by:
  79.  
  80. ftp ftp.cs.buffalo.edu (or 128.205.32.9 subject-to-change)
  81. Name : anonymous
  82. > cd users/jagota
  83. > get ICNN93.tex
  84. > quit
  85. ================================================================
  86. Hi,
  87.  
  88. I have being paid my attention to your question presented in
  89. the newsgroup about how to solve the minmum covering problem
  90. by employing the Hopfield network.In my work, I encountered a
  91. problem which is equivalent to the subgraph isomorphism problem.
  92. I want to solve it by using the Hopfield network. I'd like to know
  93. whether or not both problems are equivalent. By the way, there
  94. seem to be a lot of responses about your question in the newsgroup.
  95. I would appreciate it if you can forward these responses to me.
  96.  
  97. ================================================================
  98.  
  99.  
  100.  
  101. thanks again to every body who responded. It was a great help!
  102.  
  103.  
  104. george
  105.  
  106. george@hilbert.coe.northeastern.edu
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.