home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Monster Media 1993 #2
/
Image.iso
/
text
/
9305nni.zip
/
930503.BIB
< prev
next >
Wrap
Text File
|
1993-05-03
|
4KB
|
114 lines
Article 8960 of comp.ai.neural-nets:
Newsgroups: comp.ai.neural-nets
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
From: george@hilbert.coe.northeastern.edu (George Kechriotis)
Subject: summary of responses to minimum cover question
Message-ID: <1993May3.225754.8004@lynx.dac.northeastern.edu>
Sender: usenet@lynx.dac.northeastern.edu (usenet dummy)
Organization: CDSP Computing Lab, Northeastern University
Date: Mon, 3 May 1993 22:57:54 GMT
Lines: 100
Thanks to everybody who responded to my minimum
cover/Hopfield Neural Net question. Although I
didn't had time yet to search all the bibliography
and to try out the proposed methods, it seems that
a good algorithm can be found.
Here are some of the responses that I received:
================================================================
Hi,
You may want to look up the following paper:
P.P. Chu, "Using a semi-asynchronous Hopfield Network to
Obtain Optimal Coverage in Logic Minimization," in Proc.
Intl. Joint Conf. on Neural Networks, IEEE Press, New York,
NY, pp. 141-146, 1991.
================================================================
You can try by moving the constraints up in the original objective with
some log barrier function, for instance. (Have a look in the bibliography
of the interior point methods and barrier functions). That way you
change your original problem from a costrainted optimization to an
unconstrained one.
================================================================
There are two aspects to constructing a Hopfield Net to solve such
problems. The first is the representational issue, which you discussed
in your posting (summarized above), and which I refer to as the
"statics" issue. The second issue is network "dynamics". Most
representations give poor performance, because they result in poor
dynamics. For instance, the N*N permutation matrix representation, used
by Hopfield and Tank for the TSP, leads to poor dynamics. My guess is
that the minimum cover representation that you proposed will not lead to
satisfactory network dynamics.
The work of Sorkin (1990) indicates that the network dynamics should
implement a fractal energy landscape. I explored that issue in a recent
paper:
Lister, R (1993), "Annealing Networks and Fractal Landscapes",
IEEE International Conference on Neural Networks,
San Francisco, March 1993, Vol. I, pp 257-262.
================================================================
I just read Lister's reply to your message in comp.ai.neural-nets. Perhaps you
have all the information you need by now; I thought I'd reply in any case.
By "minimum cover" I suppose you mean "minimum vertex cover". (Your formulation
as I saw it in Lister's reply suggested that).
The following describes two Hopfield net formulations of minimum vertex cover
(and reviews several earlier Hopfield net formulations of it).
@inproceedings{Jag92f,
author = "Jagota, A.",
title = "Optimization by Reduction to Maximum Clique",
booktitle = "International Conference on Neural Networks",
organization = "San Francisco",
publisher = "IEEE",
address = "New York",
note = "Submitted To",
month= "March",
year = 1993
}
If you do not have easy access to the proceedings, you may retrieve the Latex
source by:
ftp ftp.cs.buffalo.edu (or 128.205.32.9 subject-to-change)
Name : anonymous
> cd users/jagota
> get ICNN93.tex
> quit
================================================================
Hi,
I have being paid my attention to your question presented in
the newsgroup about how to solve the minmum covering problem
by employing the Hopfield network.In my work, I encountered a
problem which is equivalent to the subgraph isomorphism problem.
I want to solve it by using the Hopfield network. I'd like to know
whether or not both problems are equivalent. By the way, there
seem to be a lot of responses about your question in the newsgroup.
I would appreciate it if you can forward these responses to me.
================================================================
thanks again to every body who responded. It was a great help!
george
george@hilbert.coe.northeastern.edu