songw@csri.toronto.edu (Wenyi Song) (02/07/89)
In article <1233@usfvax2.EDU> pollock@usfvax2.UUCP (Wayne Pollock) writes: >In article <1637@cps3xx.UUCP> artzi@cpsvax.cps.msu.edu (Ytshak Artzi) writes: > >Funny you should ask; we spent an entire lecture today discussing this >very problem in my Parallel Processing and Distributed Computing class. >The short answer is for M cities, an M X M neural network can find very >close to optimal solutions in a very short time. In AT&T Bell Labs, I've >heard that they have designed hardware, had it manufactured, and used it >to find the solution for a large problem. The whole time used (including ^^^^^^^^^^^^^^^^^^^^^^^^^^ >manufaturing the chip) was less than the time it took using traditional ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ >methods on a Cray-1! (I am assuming that if the story is true, the ^^^^^^^^^^^^^^^^^^^^ >Cray-1 method found an optimal solution; even so, this is impressive!) >Hopfield and Tank[1985] describe a case involving over 100 cities in which ^^^^^^^^^^ >a neural network computes a solution which is only a fraction of 1% longer >than the optimal solution, in only a few milliseconds of computation. They >remark that it would have taken weeks to have found an optimal solution >even using a Cray. > I gather what you referred to is J. J. Hopfield and D. W. Tank, "Neural" Computation of Decisions in Optimization Problems, Biological Cybernetics, 52, 141-152, 1985 If that's the case, then ... They showed simulation results of the 10-city problem. It needs 100 neurons. They also showed some simulation results of the 30-city problem, which requires 900 neurons. But nothing about the 100 city problem. Not only the simulation of the 100-city problem is difficult, in terms of computing time cost, but also the hardware implementation of their orginal model. This is because it needs 10,000 neurons. If they are fully inter- connected, then you have to put another (100,000,000 - 10,000) synapses into the chip. For comparison, DRAM is probably just reaching the density of 64 Mbits in a chip. So how about the comparison in terms of speed? Let's look at the well known Lin-Kernighan algorithm. S. Lin and B. W. Kernighan, An Effective Heuristic Algorithm for the Traveling- Salesman Problem, Operations Research, 21, 498-516, 1973 As reported, a typical 100-city problem requires about three minutes on their GE635 computer to obtain the optimum with above 95% confidence. Note they didn't use a Cray-1. Note we should conduct a fair comparison. If one insists on using Gray to enumerate all possible paths for the TSP problem, then ...
billh@madnix.UUCP (Bill Humphries) (02/09/89)
I've been facinated by the references to the solution of the 'Traveling Salesman' problem using neural nets on this sig. I was wondering if there were any papers or texts on the use of neural networks to solve other optimization problems through 'pattern matching' and other techniques. A caveat, however, I know nothing about neural nets and hit the math wall at Ito integrals. Please respond by mail unless you have a reference you'd like to share with everyone. Thanks in advance, Bill Humphries.
andrew@nsc.nsc.com (andrew) (02/11/89)
A recently addressed "solution" by supercomputer to a long-standing maths
conjecture - that of the finite projective plane - now exists for planes up
to order 10 (Science News, Dec 24 & 31, 1988), whereby 1000's of hours
of Cray time was needed! This looks like a nice place for a net and a Cray
to do battle... the constraints are simply expressed:
- for order k, construct a square matrix with k**2 + k + 1 rows/columns
- fill the matrix with 0's and 1's, such that:
- every row contains exactly k + 1 1's
- every possible pair of rows has exactly one column in which
both have a '1'
I have successfully solved this for low orders using the linear "schema"
cs (constraint satisfaction) program from "Explorations...PDP".
Boltzmann is lousy, but I haven't tried Harmony yet.
The net scales as order O(k**4) in # nodes and O(k**4 - k**6) (to be
resolved) in # weights. For order 10, one needs about 12K neurons and
about 2M weights. Out there exists hardware (which I don't have) to
get over 1M cps, so it's obviously in range of current virtual net
simulators.
Interested parties contact me at:
Andrew Palfreyman, MS D3969 PHONE: 408-721-4788 work
National Semiconductor 408-247-0145 home
2900 Semiconductor Dr. there's many a slip
P.O. Box 58090 'twixt cup and lip
Santa Clara, CA 95052-8090
DOMAIN: andrew@logic.sc.nsc.com
ARPA: nsc!logic!andrew@sun.com
USENET: ...{amdahl,decwrl,hplabs,pyramid,sun}!nsc!logic!andrew