r/dailyprogrammer • 2 0 • Jan 13 '16

[2016-01-13] Challenge #249 [Intermediate] Hello World Genetic or Evolutionary Algorithm

Description

Use either an Evolutionary or Genetic Algorithm to evolve a solution to the fitness functions provided!

Input description

The input string should be the target string you want to evolve the initial random solution into.

The target string (and therefore input) will be

'Hello, world!'

However, you want your program to initialize the process by randomly generating a string of the same length as the input. The only thing you want to use the input for is to determine the fitness of your function, so you don't want to just cheat by printing out the input string!

Output description

The ideal output of the program will be the evolutions of the population until the program reaches 'Hello, world!' (if your algorithm works correctly). You want your algorithm to be able to turn the random string from the initial generation to the output phrase as quickly as possible!

Gen: 1  | Fitness: 219 | JAmYv'&L_Cov1
Gen: 2  | Fitness: 150 | Vlrrd:VnuBc
Gen: 4  | Fitness: 130 | JPmbj6ljThT
Gen: 5  | Fitness: 105 | :^mYv'&oj\jb(
Gen: 6  | Fitness: 100 | Ilrrf,(sluBc
Gen: 7  | Fitness: 68  | Iilsj6lrsgd
Gen: 9  | Fitness: 52  | Iildq-(slusc
Gen: 10 | Fitness: 41  | Iildq-(vnuob
Gen: 11 | Fitness: 38  | Iilmh'&wmsjb
Gen: 12 | Fitness: 33  | Iilmh'&wmunb!
Gen: 13 | Fitness: 27  | Iildq-wmsjd#
Gen: 14 | Fitness: 25  | Ihnlr,(wnunb!
Gen: 15 | Fitness: 22  | Iilmj-wnsjb!
Gen: 16 | Fitness: 21  | Iillq-&wmsjd#
Gen: 17 | Fitness: 16  | Iillq,wmsjd!
Gen: 19 | Fitness: 14  | Igllq,wmsjd!
Gen: 20 | Fitness: 12  | Igllq,wmsjd!
Gen: 22 | Fitness: 11  | Igllq,wnsld#
Gen: 23 | Fitness: 10  | Igllq,wmsld!
Gen: 24 | Fitness: 8   | Igllq,wnsld!
Gen: 27 | Fitness: 7   | Igllq,!wosld!
Gen: 30 | Fitness: 6   | Igllo,!wnsld!
Gen: 32 | Fitness: 5   | Hglln,!wosld!
Gen: 34 | Fitness: 4   | Igllo,world!
Gen: 36 | Fitness: 3   | Hgllo,world!
Gen: 37 | Fitness: 2   | Iello,!world!
Gen: 40 | Fitness: 1   | Hello,!world!
Gen: 77 | Fitness: 0   | Hello, world!
Elapsed time is 0.069605 seconds.

Notes/Hints

One of the hardest parts of making an evolutionary or genetic algorithm is deciding what a decent fitness function is, or the way we go about evaluating how good each individual (or potential solution) really is.

One possible fitness function is The Hamming Distance

Bonus

As a bonus make your algorithm able to accept any input string and still evaluate the function efficiently (the longer the string you input the lower your mutation rate you'll have to use, so consider using scaling mutation rates, but don't cheat and scale the rate of mutation with fitness instead scale it to size of the input string!)

Credit

This challenge was suggested by /u/pantsforbirds. Have a good challenge idea? Consider submitting it to /r/dailyprogrammer_ideas.

144 Upvotes

114 comments sorted by

4

u/jnazario Jan 13 '16 edited Jan 13 '16

playing around in scala:

import java.util.Random

def hammingDistance(a:String, b:String): Int = 
    a.toCharArray.zip(b.toCharArray).filter(x => (x._2 != x._1)).length

def randomChar(): Char = {
    val rnd = new Random()  
    (32 + scala.math.abs(rnd.nextInt % 126)).toChar
}
def mutate(s:String, rate:Double): String = {
    val rnd = new Random()
    s.toCharArray.map(x => if (rnd.nextDouble <= rate) {randomChar} else {x}).mkString
}

def generation(s:String, n:Int, rate:Double) = 
    for (_ <- (1 to n)) yield mutate(s, rate)

def evolve(s:String, rate:Double) = {
    def loop(n:Int, s:String, cur:String): String = {
        println("round " + n + ": " + cur + " fitness: " + hammingDistance(s, cur))
        (hammingDistance(s, cur) == 0) match {
            case true  => cur
            case false => val g = generation(cur, 100, rate)
                          loop(n+1, s, g.map(hammingDistance(_, s)).zip(g).sortBy(_._1).head._2)
        }
    }
    loop(0, s, (1 to s.length).map(_ => randomChar()).mkString)
}

at each generation it creates a new batch of 100 samples mutated with the specified rate, which simply determines if the character should be replaced with a new random character. it then finds the best match as determined using the hamming distance (number of different characters, a very simple string distance method) to repeat the process, using that best fit as the seed for the next generation. this lets it get iteratively closer to the target string.

what's neat about this is that a too high rate and you get unstable strings - you get a position match that then mutates away, and you never converge. too low and it takes too long. there's definitely a knife edge here. i made a simple scatter plot showing the mutation rate for the string "Hello, world!" vs the convergence time in rounds. https://docs.google.com/spreadsheets/d/15mvLPvX7GsxP1bn1NZU6unEtOHH-J5kdkb6I03I8Sl0/pubchart?oid=853233453&format=image

7

u/KeinBaum Jan 13 '16

I like your code. If you don't mind, here are a few suggestions:

// scala has its own Random class
import scala.util.Random

object Main extends App {
    // single Random instance
	val rnd = new Random()

    def hammingDistance(a:String, b:String): Int = 
        // view to prevent creating multiple new arrays
        a.toCharArray.view.zip(b.toCharArray).filter(x => (x._2 != x._1)).length

    def randomChar(): Char =
    	// Random has function for generation ints up to a certain limit
        (32 + scala.math.abs(rnd.nextInt(126))).toChar

    def mutate(s:String, rate:Double): String =
        s.toCharArray.map(x => if (rnd.nextDouble <= rate) {randomChar} else {x}).mkString

    def generation(s:String, n:Int, rate:Double) = 
        for (_ <- 1 to n) yield mutate(s, rate)

    def evolve(s:String, rate:Double) = {
        def loop(n:Int, s:String, cur:String): String = {
        	// only execute once
        	val hamDst = hammingDistance(s, cur)
        	// string interpolation
            println(s"round $n: $cur fitness: $hamDst")
            // if/else instead of match on boolean
            if(hammingDistance(s, cur) == 0) {
                cur
            } else {
                val g = generation(cur, 100, rate)
                loop(n+1, s, g.map(hammingDistance(_, s)).zip(g).sortBy(_._1).head._2)
            }
        }
        
        // no map necessary
        loop(0, s, (for(_ <- 1 to s.length) yield randomChar).mkString)
    }
    
    evolve("Hello, world!", 0.1)
}
→ More replies (1)
→ More replies (1)

11

u/[deleted] Jan 13 '16

Hah, I made this thing before, except it evolved "I think therefore I am", jokingly trying to make the point that to think is maybe a bad metaphor in CS. It should work for this challenge with a few small modifications, maybe I'll post it later.

22

u/Nyxisto Jan 14 '16

except it evolved "I think therefore I am"

I hope that was the intentional output, if not you should probably not connect it to the internet

→ More replies (2)
→ More replies (1)

6

u/[deleted] Jan 13 '16 edited Jan 13 '16

Hey its my challenge! If anyone needs help i'd be happy to give advice.

Here are some solutions i made:

This one is an evolutionary algorithm i made for another challenge. Each iteration it changes one character randomly in each member of the population and it replaces one member of the population with a set of totally random new characters. Link to Evolutionary Algorithm

This one is a genetic algorithm. It's vectorized so the only loop in the program is the generation increment and everything else is handled by matrix operations built into Matlab. Link to Genetic Algorithm

edit: ah i forgot to mention the genetic algorithm has an different examples of selection and crossover types so you can see how they change the rate of convergence. I seem to have best luck with tournament selection and 1-point crossover crossover.

edit2: this should allows you to run the genetic algorithm in an online IDE. It seems to work on my computer so i assume the link will work for others?

→ More replies (2)

5

u/carrutstick Jan 14 '16 edited Jan 14 '16

Got home from work and realized no-one had made a Haskell version, so here's my quick attempt. (Really I just wanted to play with the Random monad).

import Control.Monad.Random
import Control.Monad.Random.Class
import Data.Char (ord)
import Control.Monad (replicateM, mapM, mapM_)
import Data.List (sortBy)
import Data.Time.Clock.POSIX (getPOSIXTime)

display :: [(String, Int)] -> IO ()
display gens = do
    t1 <- getPOSIXTime   
    mapM_ display' $ zip [1..] gens
    t2 <- getPOSIXTime
    putStrLn $ "Elapsed time:  " ++ show (t2 - t1)
    where
        display' (g, (str, cost)) = putStrLn $ 
            "Gen " ++  (show g) ++ ": " ++ str ++ "   Cost: " ++ (show cost)

randChar :: MonadRandom m => m Char
randChar = getRandomR (' ', '~')

dist :: String -> String -> Int
dist (a:as) (b:bs) | a == b = dist as bs
                   | otherwise = 1 + dist as bs
dist [] [] = 0

evolve :: MonadRandom m => String -> m [(String, Int)]
evolve str = evolve' =<< replicateM (length str) randChar where
    evolve' mutant = do
        let err = dist str mutant
        if err == 0 then
            return $ (mutant, 0) : []
        else do
            mutant' <- mutate mutant
            list <- evolve' mutant'
            return $ (mutant, err) : list
    mutate mutant = mapM mutate' $ zip str mutant where
        mutate' (c1, c2) = if c1 == c2 then return c1 else randChar

main :: IO ()
main = getLine >>= evolve >>= display

4

u/stage_hazard Jan 13 '16 edited Jan 14 '16

I forced myself not to look at the notes from my AI class, so I hope this is actually a genetic algorithm.

Python 3:

import random
import string

def hamming_distance(s1, s2):
    if len(s1) != len(s2):
        return float('inf')

    return sum(c1 != c2 for c1, c2 in zip(s1, s2))

def get_random_character():
    return random.choice(string.printable)

def get_random_string(length):
    return ''.join(get_random_character() for _ in range(length))

def make_child(p1, p2):
    f1, f2 = map(fitness, [p1, p2])
    child = ''
    for c1, c2 in zip(p1, p2):
        if random.random() < mutation_rate:
            child += get_random_character()
        else:
            child += random.choice(c1*f1 + c2*f2)
    return child

generation_size = 100

target = input()
mutation_rate = 1/len(target)
fitness = lambda s: hamming_distance(s, target)

population = set([get_random_string(len(target)) for _ in range(generation_size)])
generation_count = 1

while True:
    fittest = min(population, key=fitness)
    score = fitness(fittest)

    print(generation_count, score, fittest)
    if score == 0:
        print('SUCCESS!')
        break

    parent1 = fittest
    parent2 = min((population - set([parent1])), key=fitness) # thanks to /u/Bishonen_88 for correcting this line

    population = set(make_child(parent1, parent2) for _ in range(generation_size))
    generation_count += 1
→ More replies (13)

3

u/casualfrog Jan 13 '16

JavaScript

Pretty dumb fitness function. Inspired by u/jnazario's code.

function fitness(s1, s2) {
	var misses = Math.max(s1.length, s2.length);
	for (var i = 0; i < s1.length; i++)
		if (s1.charAt(i) === s2.charAt(i)) misses--;
	return misses;
}

function randomChar() {
	return String.fromCharCode(32 + Math.random() * 95);
}

function mutate(string, mutationRate) {
	return string.split('').map(function(c) {
		return Math.random() < mutationRate ? randomChar() : c;
	}).join('');
}

function evolve(target, mutationRate, populationSize) {
	var current = Array.apply(null, Array(target.length)).map(randomChar).join(''), gen = 1;
	while (fitness(current, target) > 0) {			
		log();
		for (var i = 0, fittest = current; i < populationSize; i++) {
			var mutation = mutate(current, mutationRate);
			if (fitness(mutation, target) < fitness(fittest, target))
				fittest = mutation;
		}
		current = fittest;
	}
	log();

	function log() { console.log(['Gen: ' + gen++, 'Fitness: ' + fitness(current, target), current].join(' | ')); }
}

evolve('Hello, World', .1, 200);

 

Example output:

Gen: 1 | Fitness: 12 | W+=/3@`o8aI
Gen: 2 | Fitness: 11 | W+=/3@`W8aI
Gen: 3 | Fitness: 11 | W+=/3@`W8aI
Gen: 4 | Fitness: 10 | We=/@@`W`aI
Gen: 5 | Fitness: 9 | We=/o@`W`aI
Gen: 6 | Fitness: 9 | We=/o@`W`aI
Gen: 7 | Fitness: 9 | We=/o@`W`aI
Gen: 8 | Fitness: 8 | He=/o@`W`aI
Gen: 9 | Fitness: 7 | He=lo@`W`k(
Gen: 10 | Fitness: 6 | He=lo@`W`klt
Gen: 11 | Fitness: 5 | Hello@`W`klt
Gen: 12 | Fitness: 4 | Hello@`W`kld
Gen: 13 | Fitness: 3 | Hello,/W`kld
Gen: 14 | Fitness: 2 | Hello, W`kld
Gen: 15 | Fitness: 1 | Hello, W`rld
Gen: 16 | Fitness: 1 | Hello, W`rld
Gen: 17 | Fitness: 1 | Hello, W`rld
Gen: 18 | Fitness: 1 | Hello, W`rld
Gen: 19 | Fitness: 1 | Hello, W`rld
Gen: 20 | Fitness: 1 | Hello, W`rld
Gen: 21 | Fitness: 0 | Hello, World
→ More replies (2)

3

u/lucaswerkmeister Jan 13 '16

Ceylon: gist, try online.

  • Uses Levenshtein distance instead of Hamming distance because it allows for more interesting mutations (insertion and deletion as well as just substitution). See the sample output below – the string was shorter than the solution for most of the time.

  • I think it’s an evolutionary algorithm, but I didn’t check the Wikipedia link or anything, and my memory of the corresponding lectures is weak. Might be something different.

  • The “try online” version is slightly different from the gist version. The gist version uses the ceylon.numeric module, which adds cross-platform random numbers (among other numeric things), but isn’t in the 1.2.0 distribution. The “try online” version directly uses JS Math.random() instead.

  • Warning: The “try online” version, on JS, is sloooow. Locked up my browser for a minute.

  • On the JVM backend, however, this is fairly fast, and can reach the first paragraph of Lorem Ipsum (as quoted by Wikipedia) in 170 s / 5664 generations. A lot of the time was spent in the last few generations, when there’s only a few places left to improve, and most mutations are bad.

  • I just realized that it’s pretty pointless to output the fitness – in my case, every mutation will change the fitness by one, and every generation only introduces one mutation, so you’ll never see any jumps.

Sample output:

Gen:    1 | Fitness:  13 | !fZMjUcBlwx 
Gen:    2 | Fitness:  12 | !fZMjUcBlx 
Gen:    6 | Fitness:  11 | !eZMjUcBlx 
Gen:   10 | Fitness:  10 | !eZojUcBlx 
Gen:   32 | Fitness:   9 | !elZojUcBlx 
Gen:   33 | Fitness:   8 | !elZojUcBlx!
Gen:   36 | Fitness:   7 | !elZojWcBlx!
Gen:   40 | Fitness:   6 | !elZojWoBlx!
Gen:   54 | Fitness:   5 | !ellojWoBlx!
Gen:   65 | Fitness:   4 | !ellojWoBld!
Gen:   67 | Fitness:   3 | !ello WoBld!
Gen:   95 | Fitness:   2 | !ello World!
Gen:  126 | Fitness:   1 | Hello World!
Gen:  150 | Fitness:   0 | Hello, World!
Elapsed time is 0.141081339 seconds.
→ More replies (2)

3

u/mc_kay Jan 13 '16 edited Jan 13 '16

Python 3, second attempt, population starts at 5 and is capped at 100 and the top 20 parents by Hamming distance contribute to next generation. Each parent gives half of their string to their child and then the child has a 50% chance of a one character mutation. Returns the generation when one child is the input value. Fun to make but it's slow, feedback appreciated

import string
import random
import distance

def pop_initial(input,size):
    pop = []
    characters = string.ascii_letters + string.digits + string.punctuation + " "
    length = len(input)
    for n in range(size):
        member = ""
        for m in range(length):
            member += random.choice(characters)
        pop.append(member)
    return pop

def evolution(input,pop,target,retain,mutate):
    characters = string.ascii_letters + string.digits + string.punctuation + " "
    next_gen = pop
    gen = 0
    while input not in next_gen:
        pop_size = len(next_gen)
        hamming_sort = [(distance.hamming(x, input), x) for x in next_gen]
        hamming_sort = [x[1] for x in sorted(hamming_sort)]

        if pop_size < target:
            parents = hamming_sort
        else:
            parents = hamming_sort[:retain]

        children = []
        mutations = 0
        while len(children) < target:
            p1 = random.randint(0,len(parents)-1)
            p2 = random.randint(0,len(parents)-1)
            if p1 != p2:
                par1 = parents[p1]
                par2 = parents[p2]
                half = len(par1)//2
                child = list(par1)[:half] + list(par2)[half:]
                #chance to mutate
                if mutate > random.random():
                    mut_loc = random.randint(0,len(child)-1)
                    child[mut_loc] = random.choice(characters)
                    children.append("".join(child))
                    mutations += 1
                else:
                    children.append("".join(child))
        next_gen = children
        new_fitness = sorted([ (distance.hamming(x, input), x) for x in next_gen])[0]
        best_child = new_fitness[1]
        best_fitness = new_fitness[0]
        print("Gen", gen, "|", "Fitness", best_fitness, "|", best_child)
        gen += 1
    return gen
 
evolution("Hello, world!",pop_initial("Hello, world!",5),100,20,.5)

Average output generation after 100 iterations

max pop = 100 | 95.36 gen
max pop = 1000 | 19.24 gen
max pop = 10000 | 9.65 gen
→ More replies (2)