Re: Stumped on crossover/mating...

Looking at it differently, you might consider the entire puzzle answer being
the genome. The genome is just the sequence of letters, one for each opne
square in the puzzle. The crossover points would segment the entire puzzle
at a letter boundary. Say the puzzle has 250 letters. With 2-point
crossover, a random marriage might be 1-73, 74-211,212-250.

The children with the better fitness would inherit more correct letters
overall. Perfect fitness os a score of 250. A normalized fitness could be
(correct letters)/250

Jim Moore

"Tanari" <tanari.jay@xxxxxxxxx> wrote in message
news:1141146915.496440.249580@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I'm a programmer of many years and I reciently decided to jump in to
GA's and learn how to create them and solve search related problems.
For a start I decided to create a GA which would solve a crossword
puzzle. This is a task which is easy to solve without a GA, so it is
easy for me to quickly (programmatically) validate the results.

I started with a simple sub-problem to solving it: "Find one word in
the crossword grid". I've create a population whose chromosomes are
the same lengths as the word I am trying to find.

e.g. length of "word" (4 characters) = length of chromosome (4 pairs of
coordinates for cells on the grid - each coordinate pair is 1 gene)

I can easily determine the fitness of each member of the population &
order them by their fitness levels. Fitness is determined by how many
of the letters stored in the cells refferenced by the coordinates in
the chomosome, match the target word. Are the coordinates consecutive
& in the right order to spell the word.

What I am stumbling on is how to impliment crossover between the
chromosomes. How do I determine what genes to cross between parents?

My initial (& very newbe) understanding is that I randomly determine
the crossover point (position in the chromosome) and swap the genes
before the corssover point between the parents. Mutate some of the
chromosomes after all the swaps & repeat the cycle.

Should the crossing of genes be random (i.e. random crossover point)?
It does not seem that this strategy will develop a solution to my
problem.

Can someone provide some insight and constructive opinions on my
approach? Does anyone have any examples of similar problems being
solved?

Thank-you.



.

Relevant Pages

  • Re: Answer(s) to Kryptos Puzzle?
    ... >the answer I found was not the only possible answer to the puzzle. ... >The letters that were left over gave me enough letters to give me the ... >to an unknown location. ... this passage IS in the text. ...
    (sci.crypt)
  • Answer(s) to Kryptos Puzzle?
    ... Internet as being the "answer" to the puzzle. ... "Because codes based on kryptos are tough to crack, ... I decided to extract the following words' letters: ... this passage IS in the text. ...
    (sci.crypt)
  • Re: Wordplay
    ... four clues in the 8th puzzle from the 2005 tournament. ... 30A - 3 letters ... non-cryptic puzzles and British cryptics have changed a lot since, ...
    (rec.puzzles.crosswords)
  • Re: Answer(s) to Kryptos Puzzle?
    ... >And started removing all the letters from our nice little phrase about ... >Hee hee hee hee ... still not revealing the plaintext underneath. ... since of course this would spoil the journey through the puzzle. ...
    (sci.crypt)