MEMORY, LEARNING & OPTIMIZATION - comments and preprint -

[BATTITI@itnvax.science.unitn.it]

		MEMORY, LEARNING & OPTIMIZATION
		Are Monte Carlo techniques appropriate?	

A research stream in Neural Networks proposes to use NN for Combinatorial
Optimization (CO), with mixed results. Other streams consider state of the art
optimization techniques and apply them to machine learning and NN tasks.
    In reality the areas of optimization and learning are deeply interrelated.
    In particular, recent CO algorithms use MEMORY and LEARNING to generate 
    efficient search trajectories from a set of local moves.
Unfortunately Markov Chain Monte Carlo methods are memory-less (by definition,
the distribution of the random variable X(t+1) in a Markov chain is mediated
entirely by the value of X(t)). The past history does NOT influence the 
current move.
    Is the importance assigned to Markov chain sampling methods in the area of 
    optimization and learning justified by the theoretical results (whose 
    practical interest is dubious, see the clear discussion about sa in [1]) 
    or by the results obtained on significant tasks? We doubt it.

===========================================================================
Now we describe a homework that we made after reading the interesting paper
placed in the neuroprose archive by M. Mitchell [2] about a week ago.
(to spare e-mail bytes we assume knowledge of [2])

On the "Royal Road" function R1 (Table 1 in the cited reference), GA
converges in 61,334 function evaluations (mean), RMHC (a zero-temperature
Monte Carlo method used by Forrest and Mitchell) in 6,179.

In RMHC, a given string is mutated at a randomly chosen single locus.
If the mutation leads to an equal or higher fitness, the new string replaces
the old string.

Now, if the last mutation increased the fitness, it is reasonable that it is 
NOT considered again in the next step (otherwise the successful mutation can
be undone). Similarly, if the last mutation was not accepted because the fitness
would have decreased, it is pointless to consider it again in the next step.

Let us generalize and modify RMHC: if mutation (i) at iteration (t) either
decreases or increases the fitness, (i) is prohibited for the next T iterations
(the corresponding bit in the string is "frozen"). Nothing happens if the fit-
ness remains unchanged.

Here are the homework results as a function of T (100 runs for each value):
T	mean f.evals	st. dev.
0	6,450		(289)  ----(confirms results of [2])
50 	3,728 		(148)
100 	3,122 		(104)
200 	2,805 		(94)
300 	2,575 		(88)
400 	2,364 		(83)
500 	2,605 		(79)

The use of this simple form of memory can accelerate the convergence (about
 1/3 function evaluations are sufficient when T=400).

Bye the way, we would not be surprised if some biological mechanism could be
used for the same purpose (the above modification of RMHC resembles a sort of 
"refractory period": if a mutation "fires" it does not fire again for T steps).
No doubt there is noise in our biological neurons..., but is our gray matter
generating Markov chains? Comments are welcome.


Roberto Battiti					Giampietro Tecchiolli
Dip. di Matematica Univ. di Trento		IRST
38050 Povo (Trento) - ITALY			38050 Povo (Trento) - ITALY
e-mail: battiti at itnvax.science.unitn.it		e-mail: tec at irst.it

*****************************************************************************
A preprint with a benchmark of the Reactive Tabu Scheme and other popular
techniques (including GAs) is available by ftp from our local archive 
("Local Search with Memory: Benchmarking RTS", R. Battiti and G. Tecchiolli)

To get a copy:
unix> ftp volterra.science.unitn.it    (130.186.34.16)
Name: anonymous
Password: (type your email address)
ftp> cd pub/rts-neuro
ftp> binary
ftp> get rts-benchmark.ps.Z
ftp> quit
unix>uncompress rts-benchmark.ps.Z
unix> lpr rts-benchmark.ps (34 pages)
A limited number of hardcopies are available if printing is impossible. 

Additional background references are abstracted in the file:
pub/rts-neuro/ABSTRACTS-TN  of the above archive.

*****************************************************************************
ftp references cited:

[1] "Probabilistic inference using Markov chain Monte Carlo methods"
R. M. Neal, posted 23 Nov 1993.
ftp: ftp.cs.toronto.edu 
file: pub/radford/review.ps.Z).

[2] " When Will a Genetic Algorithm Outperform Hill Climbing?"
Melanie Mitchell, John H. Holland, Stephanie Forrest, posted  23 Jan 1994.
ftp: archive.cis.ohio-state.edu
file: pub/neuroprose/mitchell.ga-hillclimb.ps.Z).