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)