Any computer scientists in here?

[GenericKen]

Hey.

I haven't been here in a while, so I'm not sure of the level of expertise on the boards, but I figured it was worth a shot.


I'm playing around with genetic algorithms, and I'm trying to implement a phenome composed of real numbers (a data structure as opposed to simple bit-strings).

Does it make sense to do a bit-crossover on the bit-encodings of the real numbers, or does the crossover function have to take into account the logical structure of the bit-encodings?

I suppose I could modify the problem so that the phenome would use unsigned integer numbers normalized to 0, as that would make more sense, but it doesn't make particularly much more sense.


The third possibility is for the crossover to consider the real values to be atomic, and just crossover around em, but again, I'm not sure if the theory is sound.



Thanks for any help. If you can't help, well, thanks for listening. :blush:

[Kylearan]

Hi,

I'm playing around with genetic algorithms, and I'm trying to implement a phenome composed of real numbers (a data structure as opposed to simple bit-strings).

I've recently done something similar; I've used a genetic algorithm with real numbers as "genes" to evolve an AI to play the card game San Juan against, which worked quite well. For those who are interested, the end result can be downloaded on my website.

Does it make sense to do a bit-crossover on the bit-encodings of the real numbers, or does the crossover function have to take into account the logical structure of the bit-encodings?

First, I think any kind of cross-over will work, as genetic algorithms are amazingly robust. Choosing the type of cross-over, the chance of mutation, the data structures for genes etc. will only affect how fast the algorithm will converge.

That said, I did not do cross-over at bit level because that would tear apart a real number and create a new one most of the time, thus leading to an unwanted mutation. I like to control mutation with the function specifically written for mutation, and don't want to have any similar side-effects when doing cross-over.

Instead, I considered the real values to be atomic and did the crossover around them as you suggested as your third possibility, thus ensuring that the real values are preserved and will only altered by the mutation function.


But all these decisions are directly dependant on the problem you want to solve with the genetic algorithm. There are problems for which bit-encoding is preferred, and others for which real values are better. All will work out in the end, but will converge slower or faster which might be critical. My Athlon 3400+ spent over six weeks of raw computing time evolving my AIs. :blink:

Other decisions are how to order your genes (building block hypothesis), what kind of cross-over you do (one-point, two-point, ...), how to design your fitness function, how to decide who is allowed to generate offspring etc., which might have even more impact than the representation of the genes.

-Kylearan

[GenericKen]

Sweet, how fortunate.


Keeping the values atomic makes sense, thanks. I'm working on a custom little thing in flash (yes flash), and I'll post a link if it ever turns out.

Thanks for the help, man!


P.S. Since my GA is going to be time-sensitive, how much of a mathematical improvement do you think the following modification to truncation selection would be?

choose p from pop {
p(k / (1+k)) choose random from population with fitness > pop avg fitness
p(1 / (1+k)) choose random from total population
}

k may be arbitrary, or may be the healthy fitness normalized to the avg fitness:
(avg fitness of pop with fitness>pop avg fitness)/(pop avg fitness)


And I'm pretty sure what you get is a O(n) rough aproximation of roulette wheel selection for n different ps; the roulette wheel implementation is O(n^2) iirc (or maybe O(n logn) if you cumulate the fitnesses and do a search on them). I'd like a second opinion on this, though.

[ima_nerd]

:blink:

*changes major from CS to Management*

[whyBish]

the roulette wheel implementation is O(n^2) iirc (or maybe O(n logn) if you cumulate the fitnesses and do a search on them).  I'd like a second opinion on this, though.
[right][snapback]98419[/snapback][/right]

If you keep them in a sorted list based on fitness (assuming that fitness is a calculation internal to an organism, (i.e. doesn't change when your list changes)) then it wouldn't be O(n^2)...you could also maintain the cumulative fitness of the population. It does however mean that you take a hit on insertion (& deletion) so the overall runtime may end up back looking like O(nlogn)?

[GenericKen]

If you keep them in a sorted list based on fitness (assuming that fitness is a calculation internal to an organism, (i.e. doesn't change when your list changes)) then it wouldn't be O(n^2)...you could also maintain the cumulative fitness of the population.  It does however mean that you take a hit on insertion (& deletion) so the overall runtime may end up back looking like O(nlogn)?
[right][snapback]98565[/snapback][/right]

Reworking it in my head, O(nlogn) is right. On very large sets, it would matter, but the overhead of the modivied trunc would probably be like half of log n on average anyway.

Still, I'm somewhat enamored with my modified truncation idea. I think I may try it out anyway.

[Pesmerga]

:blink:

*changes major from CS to Management*
[right][snapback]98430[/snapback][/right]

I felt the same exact way... and I graduated with a CD degree!

[GenericKen]

I felt the same exact way... and I graduated with a CD degree!
[right][snapback]98590[/snapback][/right]

Pft... undergrads...

B)

[Kylearan]

Hi,

sorry for answering so late; I was busy during the last few days.

Reworking it in my head, O(nlogn) is right. On very large sets, it would matter, but the overhead of the modivied trunc would probably be like half of log n on average anyway.

Indeed. Normally, population size is between 100 and 500, less than 1000 most of the time - so the improvement from O(nlogn) to O(n) doesn't really matter (apart from it being theoretical aesthetic...) . And in many cases, selection isn't the most time-consuming process anyway - but it's quite hard to discuss this if we don't know exactly what you are trying to solve with the GA. ;) In the few cases I programmed a GA, calculating the fitness function dominated selection time-wise anyway, so I found it better to optimize that instead. And if you expect your GA to be time-consuming, flash might not be the best choice of language here anyway... :P

I'll post a link if it ever turns out.

Please do so! I'm curious about anything GA related. :)


By the way, do you know the works of Karl Sims? He has done amazing things with GAs. He simulated a physical world and used a GA to evolve "creatures" that learned to move. His representation of genes is nothing short of amazing, and best of all, he animated the results in a video than can be downloaded from his website, along with the scientific papers he published about the subject. Well worth to check out for anyone interested in GAs!

If you're interested, look for the paper "Evolving Virtual Creatures" and the corresponding videos on his website

-Kylearan