reference list on parallel GA/SA

[Yu Shen]

Here is the list of reference on parallel genetic algorithm and
parallel simulated annealing, compiled from the kind resposes from
people on the mailing list and other whatever ways I ran into. 
I thank all the help again! 

I have done a report on the impact of parallelism on genetic algorithm
and simulated annealing. Here are some of the major points:

Assuming constant size of neighborhood in a spatially distributed
population, the parallel genectic algorithm that selects mating partner
locally can usually achieve linear
speedup over the sequential version. But PGA has mainly shown
advantage in improving the quality of search. For parallel paradigm
increases the chance of crossing-over of gens, which is believed to be
the most important mechanism of optimization. Even with linear
speedup, PGA application is still very slow comparing with some
conventional heuristics, for example, for the case of Traveling
Salesman Problem. 

Parallel simulated annealing is not equivalent to parallelization of
Metropolis' relaxation, where the mainstream of practices 
concentrate on. Metropolis' is basically a sequential approach. More
significant speedup is usally achieved by alternatives away from it.
It is possible to devise more parallel paradigm oriented simulation
techniques, because the working mechanism of simulated annealing is
Boltzman distribution, instead of the particular generating method---
 Metropolis' relaxation. 

The report is being revised. It will be available to interested
parties in January.

The reference consists of two parts. The first is on genectic
algorithm, the second on simulated annealing. Very godd bibliography
on SA of D. Greening is refered to the original source to save space. 

By the way, I have profited a lot by asking question which seems
simple to some BIG profs B-]. I earnestly want to make up the noise I
made to them. I therefore suggest to the fellow pratictioner-to-be's
let's try to make the noise as little as possible. For example, we can
have the subject line as concise as possible, so non-interested people
can delete it beofor seeing it. As a example, when we ask such
"simple" question, we can put a X: in front of the subject line. X:
may mean that it might annoy some people but it might not to some
others. eg. X: Relationship between the cinema and the connectionist
mailing list 8-)

Yu Shen

PhD Student
Dept. d'Informatique et Recherche Operationnelle
University de Montreal
C.P. 6128 Succ. A.
Montreal, Que. 
Canada
H3C 3J7

(514) 342-7089 (H)
shen.iro.umontreal.ca
---------------------PGA----------------------------------------------------

@TechReport{Goldberg90:Boltzman-Tournament,
  author = 	"David E. Goldberg",
  title = 	"A Note on Boltzmann Tournament Selection for Genetic
		 Algorithms and Population-oriented Simulated Annealing",
  institution = 	"University of Alabama",
  year = 	"1990",
  OPTtype = 	"",
  OPTnumber = 	"90003",
  OPTaddress = 	"Tuscaloosa, AL 35487",
  OPTmonth = 	"May",
  OPTnote = 	"distribution across population"
}



@TechReport{ga:Goldberg90:messy,
  author = 	"David E, Goldberg",
  title = 	"An Investigation of Messy Genetic Algorithms",
  institution = 	"Dept. of Engineering Mechanics, Univ. of Alabama",
  year = 	"1990",
  OPTtype = 	"",
  OPTnumber = 	"90005",
  OPTaddress = 	"",
  OPTmonth = 	"May",
  OPTnote = 	""
}


@Article{ga:Goldberg89:messy,
  author = 	"David E. Goldberg",
  title = 	"Messy Genetic Algorithms: Motivation, Analysis, and
		 First Results",
  journal = 	"Complex Systems",
  year = 	"1989",
  OPTvolume = 	"",
  OPTnumber = 	"3",
  OPTpages = 	"493-530",
  OPTmonth = 	"",
  OPTnote = 	""
}
------------

@TechReport{ga:Goldberg90:selection,
  author = 	"David E. Goldberg",
  title = 	"A Comparative Analysis of Selection Schemes Used in
		 Genetic Algorithms",
  institution = 	"Dept. of Engineering Mechanics, Univ. of Alabama",
  year = 	"1990",
  OPTtype = 	"",
  OPTnumber = 	"90007",
  OPTaddress = 	"",
  OPTmonth = 	"July",
  OPTnote = 	""
}
-------------