CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Frogs and Toads settings"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #744
Reading Topic #744
Frogs and Toads
guest
Jan-02-07, 02:18 PM (EST)
 
"Frogs and Toads settings"
 
   hello,
I have been doing a project to Artificial Inteligence course at my school. It'should be something with genetics algorithms, written in smalltalk and smallDevs, and it could be just some "rewrite" of something existing, so I have choosen Frogs and Toads puzzle from this site. I have the structure done, but it does not work as I want it (it does not solve the puzzle, the maximum quality of chromosome I have ever got was 13 out of 15).
I followed the notes above the puzzle
https://www.cut-the-knot.org/SimpleGames/evolutions.shtml
but there are still some things which are not clear to me...

1)at crossover, every pair of chromosomes is crossovered?
2)how exactly are chromosomes for crossing over choosen?
3)"On a single evolutionary step either all but the fittest chromosome are replaced, or I replace only the two worst performers."
what is the probability of these two cases?
4)what is probability that mutation (if is some performed) is classic mutation or shift?

Maybe these questions seem to be too detail, but those details are the "thing" which makes algorithm succesful, and unfortunately I havent found this settings yet :(.
I would be very grateful for any suggestions

best regards Petr Ent


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
1939 posts
Jan-02-07, 09:07 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
1. "RE: Frogs and Toads settings"
In response to message #0
 
   >1)at crossover, every pair of chromosomes is crossovered?

There would be too many chromosomes.

Choose a population size, say N. Given one population of size N, create another one from scratch by repeatedly selecting two chromosomes from the old population, crossing them over and possibly mutating. Algorithm runs faster if you pass the most fit chromosome to the new population unchanged.

>2)how exactly are chromosomes for crossing over choosen?

Straightforwardly: by selecting a number, splitting the chromosomes at this gene, and appending the tails to the wring heads.

Each of the new chromosomes undergoes either a mutation or a gene rotation with probability of 1/2.

(If two original chromosomes had equal fitness value the new chromosomes are rotated with probabilty of 1/2. Otherwise, they mutate with probability of 1/2.)

>3)"On a single evolutionary step either all but the fittest
>chromosome are replaced, or I replace only the two worst
>performers."
>what is the probability of these two cases?

It's rather two different algorithms that are selected with a checkbox.

>4)what is probability that mutation (if is some performed)
>is classic mutation or shift?

I believe #2 above answers that.

>Maybe these questions seem to be too detail, but those
>details are the "thing" which makes algorithm succesful, and
>unfortunately I havent found this settings yet :(.
>I would be very grateful for any suggestions

That's OK, although I had to go through the code I have not used in years.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
Frogs and Toads
guest
Jan-03-07, 08:21 AM (EST)
 
2. "RE: Frogs and Toads settings"
In response to message #1
 
   thank you very much, I followed your advices and the algorithm now produces solution in 600 iterations at average

best regards Petr Ent


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

Copyright © 1996-2018 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK