[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re:



Hello Richard,
I am currently working with a metaheuristics algorithm framework for scheduling problems that includes GA and SA approaches (as well as hill
climber, random, and application-based iterative algorithms). It is quite simple to change the search manager and solution-acceptance modules to
use SA approaches with a GA solution manager. (Also much simpler to do in C++  than C...)

SA/GA hybrids can have quite interesting results and can speed up performance for cases where the evaluation function time is substantial and users
can't wait for slower, more careful convergence. However, for some of these problems where SA does well, I find that the hill climber also does
much better than the GA - so how much is due to the acceptance criteria is not obvious.

I suggest that you look at the pseudo code for SA's in "Genetic Algorithms + Data Structures = Evolution Programs"  by Zbigniew Michalewicz. Sorry
I can't tell you the page number as my copy is at my current client's site, but the SA discussion only appears in one place in the book (right next
to hill climbing pseudo code - somewhere around the middle of the book). This pseuocode is straightforward and should be enough to implement SA
search/acceptance criteria. It can be a little confusing to extrapolate to implementation details and parameters. (If you get stuck, send me an
email directly and we can go into details.)

"An Introduction to Genetic Algorithms", Melanie Michell also gives a short description of using Boltzmann selection near the end of the book (I
don't have that copy here either!).

A search on metacrawler.com using " Boltzmann selection" might get you started:
-- Check out http://www.cs.indiana.edu/l/www/classes/b553/ga3.html
-- GA Archive Source Code Collection webpage at http://www.aic.nrl.navy.mil/galist/src/
it says that GENEsYs 1.0 has multiple selection options, including Boltzmann selection. (I have never looked at this code so I can't say anything
more than what the description says.)
... and so on.

Good luck,
Wendy




Richard Bradwell wrote:

> Hi folks,
>
> I am looking for GAs in the literature which carefully control their convergence using an acceptance criteria which rejects newly created
> individuals which are either too good or too poor to fit in with the current
> population.   I believe I have seen GA/SA hybrids that accept new children
> based on the SA acceptance criteria.  They employ a cooling schedule. I don't seem to be able to find specific papers though.  Can anyone help?
>
> Thanks
>
> Richard.
>
> Richard Bradwell, Computing Science Dept, Aberdeen University, Scotland, UK.

--
Wendy L. Williams
Software Architect

wendy@magma.ca
613-825-0050 (Bus.)
613-825-0564 (Fax )