From: wlfong@logos.waterloo.edu (Philip W. L. Fong)
Subject: Randomization, GA and SA in CSP
Keywords: Randomization, Genetic Algorithms, Simulated Annealing, CSP
Organization: University of Waterloo
Date: Wed, 8 Apr 1992 15:37:12 GMT


Recently I posted news to ask for how Randomization, Genetic Algorithms,
and Simulated Annealing could be applied to solve Constraint Satisfaction
Problems.  Here is a summary of the replies I got.  Thank you for all
who provided these valuable input.  I would be grateful if you would
keep me posted when you come across any new information.  Thank you
very much.

Philip Fong
wlfong@logos.waterloo.edu

========================================================================

Date: Fri, 3 Apr 1992 21:07:14 -0500
From: Kimball Collins <kpc@ptolemy.arc.nasa.gov>

i'm using simulated annealing in constraint-based scheduling.

========================================================================

Date: Fri, 3 Apr 1992 21:38:17 -0500
From: Kimball Collins <kpc@ptolemy.arc.nasa.gov>

sure.  i am modifying the space shuttle ground operations scheduler to
schedule wind tunnels.  it is an interval-based, constraint-based
scheduler that starts with cpm and iteratively improves the schedule
by doing random moves or picking violated constraints to fix.
violated constraints can include ones that will never be satisfied.
im my case, electrical power is an example.  i want to reduce power
usage.  the space shuttel code was written by monte zweben et al. here
at ames.  he has published in aaai in the past few years.  mark fox at
cmu and david biefeld at jpl are other possibilities.  biefeld has
worked on a similar scheduler.  i don't know whether fox uses
randomness much.

another maybe possibility is steve minton here, who has also published
in aaai and possibly sigart bulletin in recent years.  he has worked
on million queens etc. and is famous for a min-conflicts criterion.  i
don't know how much randomness he uses; i'll ask sometime.

another possibility is peter cheeseman here but he hasn't published on
the topic.  he is big on probabilistic techniques.  wait a minute, no;
read his paper in ijcai-90 on where the hard problems are.  great
stuff imho.

==========================================================================

Date: Sat, 4 Apr 1992 15:28:26 -0500
From: davidmc@cpsc.ucalgary.ca (David Mcfadzean)

> I am investigating the possibility of using randomized algorithm to
> solve Constraint Satisfaction Problems.  If anyone out there know what
> has been done in the past with this approach, please let me know.  I
> am also interested in the application of Genetic Algorithm in solving
> CSP.  (Actually I know nothing about GA and whether it can be applied to
> solving CSP.)

I reviewed a paper that discussed applying a GA to the TSP,
included here for your illumination and edification. We also 
discussed the issue in my machine learning class, and decided
that GAs were not that useful for solving NP-complete problems.
The GA comes up with good solutions in polynomial time,
but doesn't solve it, which is usually what you want for an
NP-complete problem. GAs don't work very well because NP-complete problems
are usually characterized by a flat search space, so gradient-descent
(hill climbing) algorithms get lost.

Hope this helps,
--
David McFadzean (davidmc@cpsc.ucalgary.ca)
Knowledge Science Institute
University of Calgary

p.s. Feel free to post this to the net if you think others
would find it useful.

[... Latex listing of the article deleted.  Available directly from 
     sender of this message ...]

@book{Goldberg89,
  author = 	"Goldberg, D. E.",
  title = 	"Genetic Algorithms in Search, Optimization, and
		 Machine Learning",
  publisher = 	"Addison-Wesley",
  address = 	"Reading, Mass.",
  year = 	1989,
}

============================================================================

Date: Sat, 4 Apr 1992 16:20:38 -0500
From: davidmc@cpsc.ucalgary.ca (David Mcfadzean)

Yes, that's [Goldberg89] the best reference I've come across.

 > Actually, do you know of any good book specialized in simulated annealing?
 > I want a book that deals with both the theoretical and practical aspect
 > of simulated annealing.  Please let me know if you have any thing like
 > that.

Sorry, I don't have any refs for SA but they sometimes talk about
it the GA mailing list. Here's the latest issue:

Genetic Algorithms Digest   Monday, March 30 1992   Volume 6 : Issue 12

 - Send submissions to GA-List@AIC.NRL.NAVY.MIL
 - Send administrative requests to GA-List-Request@AIC.NRL.NAVY.MIL
 - anonymous ftp archive: FTP.AIC.NRL.NAVY.MIL (see v6n5 for details)

[...Deleted...]

============================================================================

Date: Mon, 6 Apr 1992 20:21:53 -0400
From: bm02@PL118e.CC.Lehigh.EDU (Bijan Marjan)

R   From: wlfong@logos.waterloo.edu (Philip W. L. Fong)
   Newsgroups: comp.ai,comp.ai.edu
   Date: 6 Apr 92 21:24:43 GMT
   Organization: University of Waterloo


   Does anyone know what book/paper is a good reference of Simulated Annealing?
   What I want are both the mathematical foundation of SA and illustration
   of how SA can be applied, eg examples of good annealing schedule, how SA
   can be tailored to solve combinatorial optimization problems, etc.

   Your input will be greatly appreciated.

   Philip Fong
   wlfong@logos.waterloo.edu

Here are some references:
Kikpatrick, S., Gelatt, Jr., C. D. and Vecchi, M. P. "Optimization by 
Simulated Annealing" in Science 220 (May 13 1983) pp.671-80

Aarts, E. H. L. (Emile H. L.) _Simulated annealing and Boltzmann machines : 
a stochastic approach to combinatorial optimization and neural computing_.
Chichester [England] ; New York : Wiley, c1989

Laarhoven, P. J. M. van (Peter J. M.) _Simulated annealing : theory and 
applications_ Dordrecht ; Boston : D. Reidel ; Norwell, MA, U.S.A. : Sold and
          distributed in the U.S.A. and Canada by Kluwer Academic Publishers,
          c1987. 

There is also a book called _Genetic Algorithms and Simulated Annealing_,
but I don't have the reference with me.

--------------------------------------------------------------------------
Bijan Marjan EECS Department Lehigh University Bethlehem PA 18015-3048 USA
INTERNET: bmarjan@scarecrow.CSEE.Lehigh.EDU
--------------------------------------------------------------------------

===========================================================================

Newsgroups: comp.ai
From: sb4x@uvacs.cs.Virginia.EDU (Shumeet  Baluja)
Date: Mon, 6 Apr 1992 22:38:00 GMT

Here are three good references for Simulated Annealing:


 Kirkpatrick, S. , Gelatt, C., Vecchi, M. "Optimization by Simulated 
  Annealing.", SCIENCE, Vol. 220, No. 4598, May 1983, pp 671-680  1983

 
 Golden, B. , Skiscim, C., "Using Simulated Annealing to Solve Routing
  and Location Problems."  NAVAL RESEARCH LOGISTICS QUARTERLY. Vol 33
  pp. 261-279, 1986


 Nahar, S, Sahini, S. Shargowitz, E. "Experiments with SA",
  22ND DESIGN AUTOMATION CONFERENCE. PAper 44.6, pp. 748-752  1985



hope this helps. 



Shumeet Baluja
sb4x@virginia.edu
    
===============================================================================

Article: 11981 of comp.ai
From: smoore@dartmouth.edu (Sean Moore)
Date: 7 Apr 92 17:49:59 GMT

In article <1992Apr6.212443.2666@watdragon.waterloo.edu> wlfong@logos.waterloo.edu (Philip W. L. Fong) writes:

   >Does anyone know what book/paper is a good reference of Simulated Annealing?
   >What I want are both the mathematical foundation of SA ...

   >Philip Fong
   >wlfong@logos.waterloo.edu

There is an excellent book entitled

Simulated Annealing and Boltzmann Machines, by Aarts,E., Korst,J.,
John Wiley and Sons, NY, 1989.  

All the math foundations are explained.
- Sean

===========================================================================

Date: Wed, 8 Apr 1992 10:23:43 -0400
From: smoore@cabot.dartmouth.edu (Sean Moore)

Philip -
	Just for your information, my experience with SA was part of a
project that I did last year.  I knew nothing about SA when I started it
and I was able to learn it and carry out some experiments solely by using
the Aarts and Korst book (Kilpatrick's original paper is also very good
at explaining the general idea).  The most important thing that I learned
was that unless you pick your initial starting temperature correctly, SA
does not work well.  In Aarts and Korst, they describe how to pick the 
starting temperature using the statistics of changes in the evaluation
function - make sure you read that section and do it before trying
any experiments.  Have fun!
- Sean

============================================================================

From: Francesco Ricci <ricci@irst.it>
Date: Wed, 8 Apr 1992 09:59:08 -0400

Dear Philip,

I've written two papers on this subject. I include the abstracts of the
two and some references. Let me know if you wish a copy of my papers.

-francesco

---------------------------------------------------------------------------
		Equilibrium Theory and Constraint Networks
			Francesco Ricci
			   I.R.S.T.
			38050 Povo (TN)
			    Italy
IRST tec rep 9007-08

This paper presents a new way to map a Constraint Satisfaction Problem (CSP) 
onto a non-cooperative game. Constraint Satisfaction Problems arise 
in many areas of Artificial Intelligence and have usually been tackled
with backtracking based algorithms. The relevance of equilibrium 
theory in games with respect to the problem of finding a solution or a 
partial solution for a CSP is shown.
The concepts of Nash equilibrium, admissible equilibrium and perfect 
equilibrium are examined. We prove that the solutions of a CSP are equilibrium
points in pure strategy, both in the sense of Nash and in the sense of Selten.
Finally, it is shown a CSP solution can be reached through a step by step 
evolutionary process, in which variables update the probability of assuming a 
value, considering what the other variables will do. Some computer 
experiments are reported in the paper.

-----------------------------------------------------------------------------

   Solving Constraint Satisfaction Problems Using Reinforcement Schemes
			   Francesco Ricci
	    Istituto per la Ricerca Scientifica e Tecnologica
			  I38050 Povo (TN)
				Italy

IRST tec rep

In this paper we present the model of a decision maker, called learning 
automaton, exhibiting adaptive behaviour in highly uncertain stochastic 
environments. This learning model has been exploited in solving constraint 
satisfaction problems by a procedure that can be viewed as hill climbing in 
probability space. The main concern of this paper refers to the practical 
applicability of learning automata to constraint satisfaction problems.  
We investigate the use of a fast learning algorithm that relaxes previous 
common assumptions. We prove the algorithm is optimal and we show in a set of 
test problems good performance can be achieved. In particular, we show that 
our method achieves a higher level of performance than that presented in a 
previous similar approach.

----------------------------------------------------------------------------

H.-M. Adorf and M.~D. Johnston.
A discrete stochastic neural network algorithm for constraint satisfaction 
problems.
In {\em Proc. Int. Joint Conf. Neural Networks}, pages 17--21, San Diego, 
June 1990.

S.~H. Clearwater, B.~A. Huberman, and T.~Hogg.
Cooperative solution of constraint satisfaction problems.
{\em Science}, 254:1181--1183, november 1991.

Y.~P.~S. Foo and Y.~Takefuji.
Stochastic neural networks for solving job-shop scheduling: part 1. {Problem}
representation.
{\em Proceedings of the {IEEE} Second International Conference on
Neural Networks {(ICNN)}}, volume~II, pages 275--282, 1988.


J.~Hertzberg and H.~W. Guesgen.
Transforming constraint relaxation networks into boltzmann machines.
In {\em Proceedings of the German AI Conference, GWAI-91}, pages
244--253, Bonn, Germany, 1991. Springer Verlag.


R.~A. Hummel.
A design method for relaxation labeling applications.
In {\em Proceedings of the Second National Conference on Artificial
  Intelligence}, pages 168--171, 1983.


G.~A. Tagliarini.
Solving constraint satisfaction problems with neural networks.
In {\em Proceedings of the {IEEE} First International Conference on
  Neural Networks {(ICNN)}}, volume III, pages 741--747, 1987.

M.~A.~L. Thathachar and P.~S. Sastry.
Relaxation labeling with learning automata.
{\em IEEE Trans. Pattern Analysis and Machine Intelligence},
  8:256--268, 1986.

=============================================================================
Newsgroups: comp.ai