[xclite]

It's been a while, but I've finally found the time to put together another fun challenge.

Genetic algorithms are a method of generatively and somewhat randomly approaching a solution to a problem.

The general approach is:
1) Create a generation of random string representations of solutions to your problem
2) From among those, select parents to breed.
-This selection should be weighted - those whose "fitness score" is highest should be more likely to be selected
-these parents mate by randomly selecting a crossover point. The children are created by taking the first half of the first parent and the second half of the second parent for c1 and the reverse for c2, treating the crossover point as the half marker.
3) These children are then the next generation for step 2. Depending on the algorithm used, a mutation rate is factored in that has a chance to randomly change the value of each position in each child string.

For a better explanation, check this tutorial out.

Probably the most useful page for finding a better general description from that tutorial is here.

So the first part of the challenge is to write a genetic solver that begins with a population of character strings of length 26 characters and evolves the population until it finds a solution that is the English alphabet, or:
'abcdefghijklmnopqrstuvwxyz'

Once you've accomplished this, try to see how few generations (on average, obviously) it takes achieve this evolution. I haven't come up with some genius way of making this fair without seeding the initial population, so for now we'll just see what the results look like while I try to think of some way to find a winner.

This post has been edited by xclite: 15 February 2012 - 12:39 PM

[Karel-Lodewijk]

Here is the a very basic GA in ruby. I've gone for clarity and brevity, not really making any effort to make quicl or do anything beyond the bare essential. But anyway, it can serve as a base line.

$population_size = 100 #keep it dividable by 4 pls
$mutation_rate = 0.01 #chance an individual letter mutates

$alphabet = "abcdefghijklmnopqrstuvwxyz".chars.to_a 

#generate a random population
population = []
$population_size.times {
    population.push($alphabet.shuffle)
}

#fitness function, less is better
def fitness(candidate)
    #sum of squared differences of ascii value of letters and their corresponding letter in the alphabet
    $alphabet.zip(candidate).map{|x| (x[1].ord-x[0].ord)**2}.inject(:+)
end

#creates number_of_children children by crossover from parent1 and 2 and some mutation
def crossover_and_mutate(parent1, parent2, number_of_children)
    children = []
    for i in 0...number_of_children
        child = []
        for i in 0...parent1.size
            if rand() < $mutation_rate #mutate
                #push a random character a-z
                child.push( ('a'.ord + rand('z'.ord-'a'.ord+1)).chr );
            elsif rand() < 0.5 #take character from parent1
                child.push(parent1[i])
            else #take character from parent2
                child.push(parent2[i])
            end
        end
        children.push(child)
    end
    children
end

#loop through generations
while (true)
    #simple tournament selection
    #this code splits the population in 2 groups and compares group1[i] with group2[i] for all i,
    #selecting the fittest each time
    mid = population.size/2
    group1 = population[0...mid]
    group2 = population[mid..-1]
    parents = group1.zip(group2).map{|x| fitness(x[0]) < fitness(x[1]) ? x[0] : x[1] }

    #we do the same as above to take the fittest 2 by 2 and generate new offspring
    mid = parents.size/2
    group1 = parents[0...mid]
    group2 = parents[mid..-1]
    population = []
    group1.zip(group2).each{|x| population.push(*crossover_and_mutate(x[0],x[1],4)) }

    #this part is for monitoring
    fittest = population.min_by {|x| fitness(x)}
    puts fitness(fittest)
    if fitness(fittest) == 0
        break
    end    
end

As you can see, it took the algorithm a little under 200 generations with a population size of 100 to find the alphabet.

This is just the data from a random run, one should really calculate an average number of iteration to say anything meaningful about the performance, since results may vary wildly from run to run. But since performance was not my goal I couldn't be bothered.

Edit: tweaked mutation rate a little, it was somewhat on the low side.

This post has been edited by Karel-Lodewijk: 09 March 2012 - 01:07 PM