import math import random import sys TARGET = 100 # The number for the algorithm to find. MAX_INPUTS = 50 # Number of chromosomes in population. MAX_EPOCHS = 30 # Arbitrary number of cycles to stop after. MAX_SIZE = 36 """ 0000 0000 0000 0000 0000 0000 0000 0000 0000 Four bits are required to represent the range of characters used: DIGITS: 0: 0000 1: 0001 2: 0010 3: 0011 4: 0100 5: 0101 6: 0110 7: 0111 8: 1000 9: 1001 OPERATORS: +: 1010 +: 1011 -: 1100 -: 1101 *: 1110 /: 1111 """ DIGITS = [[0, 0, 0, 0], [0, 0, 0, 1], [0, 0, 1, 0], [0, 0, 1, 1], [0, 1, 0, 0], [0, 1, 0, 1], [0, 1, 1, 0], [0, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 1]] OPERATORS = [[1, 0, 1, 0], [1, 0, 1, 1], [1, 1, 0, 0], [1, 1, 0, 1], [1, 1, 1, 0], [1, 1, 1, 1]] class GA_Example1: def __init__(self, target, maxInputs, epochs, maxSize, digits, operators): self.mTarget = target self.mMaxInputs = maxInputs self.mEpochs = epochs self.mMaxSize = maxSize self.mDigits = digits self.mOperators = operators self.inputs = [] # Current population. self.nextGen = [] # Next population. self.totals = [] # Decoded values. self.fitness = [] # Fitness as percentage. self.selected = [] # Eligible parents. return def initialize_arrays(self): for i in range(self.mMaxInputs): self.inputs.append([0] * self.mMaxSize) self.nextGen.append([0] * self.mMaxSize) self.totals = [0] * self.mMaxInputs self.fitness = [0.0] * self.mMaxInputs self.selected = [False] * self.mMaxInputs return def initialize_chromosomes(self): getRand = 0 m = 0 # j = 0 1 2 3 4 5 6 7 8 # 0000 0000 0000 0000 0000 0000 0000 0000 0000 # # 0-3: operand # 4-7: operator # 8-11: operand # 12-15: operator # 16-19: operand # 20-23: operator # 24-27: operand # 28-31: operator # 32-35: operand for i in range(self.mMaxInputs): m = 0 for j in range(9): if math.fmod(j, 2) == 0: # j is even; this is an operand getRand = random.randrange(0, 9) for k in range(4): self.inputs[i][m] = self.mDigits[getRand][k] m += 1 else: # j is odd; this is an operator getRand = random.randrange(0, 5) for k in range(4): self.inputs[i][m] = self.mOperators[getRand][k] m += 1 return def math_round(self, inValue): outValue = 0.0 if math.modf(inValue)[0] >= 0.5: outValue = math.ceil(inValue) else: outValue = math.floor(inValue) return outValue def decode_input(self, inputIndex): # Take a chromosome, decode it, evaluate it mathematically, and return the answer. # Ignore the usual rules of algebraic evaluation, and simple go from left to right. pointer = 0 done = False operator = 0 operand = 0 total = 0 # 0000 0000 0000 0000 0000 0000 0000 0000 0000 # # 0-3: operand # 4-7: operator # 8-11: operand # 12-15: operator # 16-19: operand # 20-23: operator # 24-27: operand # 28-31: operator # 32-35: operand # Get first operand... for i in range(3, -1, -1): # Convert from binary to decimal. total += self.inputs[inputIndex][pointer] * math.pow(2, i) pointer += 1 while not done: # Get next operator... operator = 0 for i in range(3, -1, -1): # Convert from binary to decimal. operator += self.inputs[inputIndex][pointer] * math.pow(2, i) pointer += 1 # Get next operand... operand = 0 for i in range(3, -1, -1): # Convert from binary to decimal. operand += self.inputs[inputIndex][pointer] * math.pow(2, i) pointer += 1 if operator == 10 or operator == 11: # Addition total += operand elif operator == 12 or operator == 13: # Subtraction total -= operand elif operator == 14: # Multiplication total *= operand else: # Division if operand != 0: # Avoid divide-by-zero errors. total /= operand if pointer >= 35: done = True total = self.math_round(total) return total def get_maximum(self, intArray): # Returns an array index. maximum = 0 foundNewMaximum = False done = False while not done: foundNewMaximum = False for i in range(self.mMaxInputs): if i != maximum: # The maximum has to be in relation to the Target. if math.fabs(self.mTarget - intArray[i]) > math.fabs(self.mTarget - intArray[maximum]): maximum = i foundNewMaximum = True if foundNewMaximum == False: done = True return maximum def get_minimum(self, intArray): # Returns an array index. minimum = 0 foundNewMinimum = False done = False while not done: foundNewMinimum = False for i in range(self.mMaxInputs): if i != minimum: # The minimum has to be in relation to the Target. if math.fabs(self.mTarget - intArray[i]) < math.fabs(self.mTarget - intArray[minimum]): minimum = i foundNewMinimum = True if foundNewMinimum == False: done = True return minimum def get_fitness(self): # I've designed the fitness function like this to help avoid NAN math errors. # # Renders errors into percentage of correctness. # Lowest errors = 100% # Less errors renders to higher percentage. # More errors renders to lower percentage. # Highest errors = 0% bestScore = 0.0 worstScore = 0.0 # The worst score would be the one furthest from the Target. worstScore = math.fabs(self.mTarget - self.totals[self.get_maximum(self.totals)]) # The best would be the closest. bestScore = math.fabs(self.mTarget - self.totals[self.get_minimum(self.totals)]) # Convert to a weighted percentage. bestScore = worstScore - math.fabs(self.mTarget - self.totals[self.get_minimum(self.totals)]) for i in range(self.mMaxInputs): self.fitness[i] = (worstScore - (math.fabs(self.mTarget - self.totals[i]))) * 100 / bestScore return def do_selection(self): # We start out with n individuals, and will stay with n. # To do this, pick out the most fit, mate them, then replace the least fit # with the new offspring. The parents will remain for the next # population. Basically, the least fit are always being weeded out. getRand = 0 for i in range(self.mMaxInputs): getRand = random.randrange(0, 100) if self.fitness[i] >= getRand: self.selected[i] = True else: self.selected[i] = False return def choose_first_parent(self): parent = 0 done = False while not done: # Randomly choose an eligible parent. parent = random.randrange(0, self.mMaxInputs) if self.selected[parent] == True: done = True return parent def choose_second_parent(self, parentA): parentB = 0 done = False while not done: # Randomly choose an eligible parent. parentB = random.randrange(0, self.mMaxInputs) if parentB != parentA: if self.selected[parentB] == True: done = True return parentB def crossover(self, chromA, chromB, newChrom): # Select a random gene along the length of the chromosomes and swap all genes after that point. randomPoint = 0 # We want the point to be at a logical place, so that valid operands and # Operators are kept intact. randomPoint = random.randrange(9) randomPoint *= 4 for i in range(self.mMaxSize): if i < randomPoint: newChrom[i] = self.inputs[chromA][i] elif i >= randomPoint: newChrom[i] = self.inputs[chromB][i] return def do_mating(self): pointer1 = 0 pointer2 = 0 maxChild = 0 canMate = 0 cannotMate = [0] * self.mMaxInputs parentA = 0 parentB = 0 newChild = [0] * self.mMaxSize for i in range(self.mMaxInputs): cannotMate[i] = -1 # Determine total who can mate. pointer1 = 0 pointer2 = 0 for i in range(self.mMaxInputs): if self.selected[i] == True: canMate += 1 # Copy selected individuals to next generation. for j in range(self.mMaxSize): self.nextGen[pointer1][j] = self.inputs[i][j] pointer1 += 1 else: # cannot mate. cannotMate[pointer2] = i pointer2 += 1 maxChild = self.mMaxInputs - canMate; # Total number of offspring to be created. if canMate > 1 and pointer2 > 0: for i in range(maxChild): parentA = self.choose_first_parent() parentB = self.choose_second_parent(parentA) self.crossover(parentA, parentB, newChild) for j in range(self.mMaxSize): self.nextGen[pointer1][j] = newChild[j] pointer1 += 1 return def prep_next_epoch(self): # Copy next generation into current generation input. for i in range(self.mMaxInputs): for j in range(self.mMaxSize): self.inputs[i][j] = self.nextGen[i][j] # Reset flags for selected individuals. for i in range(self.mMaxInputs): self.selected[i] = False return def genetic_algorithm(self): done = False epoch = 0 self.initialize_chromosomes() while not done: for i in range(self.mMaxInputs): self.totals[i] = self.decode_input(i) if self.totals[i] == self.mTarget or epoch == self.mEpochs: done = True self.get_fitness() for i in range(self.mMaxInputs): for j in range(self.mMaxSize): sys.stdout.write(str(self.inputs[i][j])) sys.stdout.write(" = " + str(self.totals[i])) sys.stdout.write("\t" + str(self.fitness[i]) + "%\n") sys.stdout.write("\n") self.do_selection() self.do_mating() self.prep_next_epoch() epoch += 1 sys.stdout.write("Epoch: " + str(epoch) + "\n") sys.stdout.write("Done.\n") sys.stdout.write("Completed " + str(epoch) + " epochs.\n") return if __name__ == '__main__': ga1 = GA_Example1(TARGET, MAX_INPUTS, MAX_EPOCHS, MAX_SIZE, DIGITS, OPERATORS) ga1.initialize_arrays() ga1.genetic_algorithm()