Welcome, guest | Sign In | My Account | Store | Cart

Evolution optimization strategy (Python recipe) by Agnius Vasiliauskas
ActiveState Code (http://code.activestate.com/recipes/576645/)

Algorithm for solving search and optimization problems.

Python, 122 lines
Download
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
###############################################################################
# Evolution optimization strategy, based on genes frequency in genotype.      #
# Suitable for solving NP-complete problems such as generating sudoku game,   #
# tasks scheduling, designing networks and etc.                               #
# Algorithm idea is taken from:                                               #
# http://www.cad.polito.it/FullDB/exact/sac98.html                            #
# Implemented by: vasiliauskas.agnius@gmail.com                               #
###############################################################################

import random

class sgaLocus:
	"""
	Class for defining allele position (locus) in genome
	"""
	def __init__(self, Alleles):
		self.Genes = [None, None, None]  # [FirstGenome, SecondGenome, BestGenome]
		self.Alleles = dict([(x, 1.0/len(Alleles)) for x in Alleles])

class sgaGenotype:
	"""
	Class for defining population genotype.
	Main class for evolving problem solutions
	"""
	def __init__(self, alleleGroups, Amount, FitnessFunc, NotifyFunc = None, Minimize = True):
		self.FitnessFunc = FitnessFunc
		self.NotifyFunc = NotifyFunc
		self.Minimize = Minimize
		self.AlleleAffectValue = 0.005
		self.Fitness = [None, None, None]  # [FirstGenome, SecondGenome, BestGenome]
		self.MutationProbability = 1.0/(Amount * len(alleleGroups))
		self.Lgroups = [[sgaLocus(algr) for algr in alleleGroups] for x in range(Amount)]
		# Initializing random generators
		self.randmut = random.Random()
		self.randsel = random.Random()
		self.randfrq = random.Random()
	
	# >>> private methods starts
	
	def __GenerateIndividual(self, GenomeNo):
		assert GenomeNo in [0,1]
		for group in self.Lgroups:
			for locus in group:
				al = None
				# Does mutation occur
				if self.randmut.random() < self.MutationProbability:
					al = self.randsel.choice(locus.Alleles.keys())
				# select allele by it`s frequency in genotype
				else:
					while al == None:
						for allele in locus.Alleles.keys():
							if self.randfrq.random() < locus.Alleles[allele]:
								al = allele
								break
				# allele is selected, now setting genome
				locus.Genes[GenomeNo] = al
				if locus.Genes[2] == None:
					locus.Genes[2] = al
	
	def __AffectAlleles(self, BetterGenome, UpdateBest):
		assert BetterGenome in [0,1]
		afirst  = self.AlleleAffectValue if BetterGenome == 0 else -self.AlleleAffectValue
		asecond = self.AlleleAffectValue if BetterGenome == 1 else -self.AlleleAffectValue
		
		for group in self.Lgroups:
			for locus in group:
				pfirst  = locus.Alleles[locus.Genes[0]] + afirst
				psecond = locus.Alleles[locus.Genes[1]] + asecond
				pfirst  = 1.0 if pfirst > 1.0  else 0.0 if pfirst < 0.0  else pfirst
				psecond = 1.0 if psecond > 1.0 else 0.0 if psecond < 0.0 else psecond
				locus.Alleles[locus.Genes[0]] = pfirst
				locus.Alleles[locus.Genes[1]] = psecond
				# check do we need to update best genome
				if UpdateBest:
					locus.Genes[2] = locus.Genes[BetterGenome]
	
	# <<< private methods ends
	
	def Evolve(self,cycles):
		for iter in range(cycles):
			BetterGenome, UpdateBest = None, False
			self.__GenerateIndividual(0)
			self.__GenerateIndividual(1)
			self.Fitness[0] = self.FitnessFunc(self,0)
			self.Fitness[1] = self.FitnessFunc(self,1)
			if self.Fitness[2] == None:
				self.Fitness[2] = self.FitnessFunc(self,2)
			
			if self.Fitness[0] > self.Fitness[1]:
				BetterGenome = 0 if not self.Minimize else 1
			elif self.Fitness[0] < self.Fitness[1]:
				BetterGenome = 1 if not self.Minimize else 0
			
			if BetterGenome != None:
				if (self.Fitness[BetterGenome] > self.Fitness[2] and not self.Minimize) or \
					(self.Fitness[BetterGenome] < self.Fitness[2] and self.Minimize):
						UpdateBest = True
						self.Fitness[2] = self.Fitness[BetterGenome]
				self.__AffectAlleles(BetterGenome,UpdateBest)
				if self.NotifyFunc and UpdateBest:
					self.NotifyFunc(self,iter)
	
	def DumpGenotype(self):
		for ixg,group in enumerate(self.Lgroups):
			for ixl,locus in enumerate(group):
				for ixa,allele in enumerate(locus.Alleles):
					print "Grp_"+str(ixg),"|","Loc_"+str(ixl),"|",allele,"=>",locus.Alleles[allele],"prob."

def testFitness(gen,n):
	# Try to find x,y,z such that equation x^2 - y^2 - z^2 - 27 = 0
	return abs(gen.Lgroups[0][0].Genes[n]**2-gen.Lgroups[0][1].Genes[n]**2-gen.Lgroups[0][2].Genes[n]**2-27)

def testNotify(gen,iter):
		print 'iteration_'+str(iter)+':   ','|'+str(gen.Lgroups[0][0].Genes[2])+'^2 - '+\
						str(gen.Lgroups[0][1].Genes[2])+'^2 - '+\
						str(gen.Lgroups[0][2].Genes[2])+'^2 - 27| =',gen.Fitness[2]

if __name__ == "__main__":
	print 'Solving equation x^2 - y^2 - z^2 - 27 = 0'
	print '--------------------------------------------'
	gen = sgaGenotype([range(2,61),range(2,61),range(2,61)], 1, testFitness, testNotify, Minimize = True)
	gen.Evolve(1000)

Tarantula alternative solution was very helpful, because it demonstrated how laconic code should look like :-) So according to this I also made some adjustmets to code:

  1. Moved unnesessary code from fitness function into genome Evolve method. Now fitness function is as short as it can be.

  2. Made optional genome initialization parameter "NotifyFunc",- it is useful when we need to know iterations in detail.

Tags: ai, evolution, evolution_strategy, gene, genetic_algorithm, np_complete, optimization

2 comments

Tarantula 15 years, 2 months ago  # | flag

The same using GA with Pyevolve (http://pyevolve.sourceforge.net):

from pyevolve import G1DList
from pyevolve import GSimpleGA
from pyevolve import Selectors
from pyevolve import Consts
from pyevolve import Mutators
import pyevolve

def eval_func(chromo):
   return abs(chromo[0]**2 - chromo[1]**2 - chromo[2]**2 - 27)

genome = G1DList.G1DList(3)
genome.setParams(rangemin=2, rangemax=60)
genome.mutator.set(Mutators.G1DListMutatorIntegerRange)
genome.evaluator.set(eval_func)
ga = GSimpleGA.GSimpleGA(genome)
ga.selector.set(Selectors.GRouletteWheel)
ga.setMutationRate(0.2)
ga.setMinimax(Consts.minimaxType["minimize"])
ga.setGenerations(100)
ga.evolve(freq_stats=20)
print ga.bestIndividual()
Rodney Drenth 15 years, 2 months ago  # | flag

Try using several spaces instead of tabs for indentation so code doesn't spread out so far across page.