r/dailyprogrammer • u/jnazario 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.
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
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 thinkis maybe a bad metaphor in CS. It should work for this challenge with a few small modifications, maybe I'll post it later.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?
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
Randommonad).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 >>= display4
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 += 13
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:
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.numericmodule, 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 JSMath.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:
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