#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    13
    Rep Power
    0

    Talking Genetic Algorithm


    So I've worked with genetic algorithms before but until today I couldn't write one entirely on my own. I just finished it, and I kinda wanted to show it off. I think I'll incorporate a neural network into it next.

    Code:
    #Hovestar's first Genetic Algorithm
    #Tries to find the ideal string(all 1's)
    #Written on 11/21/12
    #Completely customizable change these functions:
    	#findFitness()
    	#initalPop()
    	#maybe newGeneration() too, if your dna has more than 1's and 0's or it's not a string
    
    import random
    from random import randrange
    
    genes = []
    numGens = 30
    dnaLength = 100
    popSize = 100
    
    def main():
    	global genes
    	global numGens
    	global dnaLength
    	global popSize
    	genes = initalPop()
    	genes = sortFitness()
    	for j in range(0,numGens):
    		print 'The best fit member is: ' + str(genes[0]) + ' with a fitness of: ' + str(findFitness()[0])
    		genes = newGeneration()
    		genes = sortFitness()
    
    def initalPop():
    	return [''.join(['0' if random.random()>=0.5 else '1' for i in range(dnaLength)]) for j in range(popSize)]
    
    def findFitness():
    	#Returns an array that has the fitness of each chromosome in order of the population in genes
    	popfit = []
    	for i in range(0,len(genes)):
    		temp = genes[i]
    		fitness = 0
    		while(temp.find("1") != -1):
    			fitness += 1
    			temp = temp[temp.find("1")+1:]
    		popfit.append(fitness)
    	return popfit
    
    def sortFitness():
    	#returns population in descending order from best to worst
    	fitness = findFitness()
    	tempGenes = genes
    	temp = []
    	while(len(fitness) >=1):
    		temp.append(tempGenes[fitness.index(max(fitness))])
    		del tempGenes[fitness.index(max(fitness))]
    		del fitness[fitness.index(max(fitness))]
    	return temp
    
    def sum(i):
    	if(i <= 1):
    		return i
    	return i + sum(i-1)
    
    def getIndexForWeight(value):
    	index = 0
    	while(value >= 0):
    		index += 1
    		value -= index
    	index -= 1
    	return -index
    
    def newGeneration():
    	weight = sum(len(genes))
    	size = len(genes)
    	new = [genes[0]]
    	for i in range(0,size-1):
    		a = genes[getIndexForWeight(randrange(0,weight))]
    		b = genes[getIndexForWeight(randrange(0,weight))]
    		num = randrange(0,weight)
    		temp = a[:num] + b[num:]
    		for k in range(0, len(temp)):
    			if(random.random() <= 0.05):
    				if(temp[k] == 1):
    					temp = temp[:k] + '0' + temp[k+1:]
    				else:
    					temp = temp[:k] + '1' + temp[k+1:]
    		new.append(temp)
    	return new
    
    main()
    Sorry it's not very well annotated...
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,995
    Rep Power
    481
    # faster than your recursion
    def sum(n):
    return n*(n+1)/2
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    13
    Rep Power
    0
    Thank you, I also noticed in the new Generation method I made a mistake(I forgot the "" around the 1), so here is the up to date method:

    Code:
    def newGeneration():
    	#This chooses two chromosomes randomly base on weight, eg position in list
    	#Also adds best from prior generation to end of list
    	weight = sum(len(genes))
    	size = len(genes)
    	new = []
    	for i in range(0,size-1):
    		a = genes[getIndexForWeight(randrange(0,weight))]
    		b = genes[getIndexForWeight(randrange(0,weight))]
    		num = randrange(0,weight)
    		temp = a[:num] + b[num:]
    		for k in range(0, len(temp)):
    			if(random.random() <= mutationRate):
    				if(temp[k] == "1"):
    					temp = temp[:k] + '0' + temp[k+1:]
    				else:
    					temp = temp[:k] + '1' + temp[k+1:]
    		new.append(temp)
    	new.append(genes[0])
    	return new
    If anyone has suggestions I would happy to take them.

IMN logo majestic logo threadwatch logo seochat tools logo