Python Genetic Algorithm - Why Isn't This Working?

327 Views Asked by At

I've written a small python program using neural networks to do an XOR gate, and I've tried to use a genetic algorithm to get the best one. The neural networks have DNA, this decides the weight of their connections, and I combine the DNA of 2 parents using single-point crossover and mutation (very low chance) to get a child DNA, however even after 1000 generations, the best neural network is the same for every generation, why is this? (I think it has to do with how the parents reproduce) Here is the code if you need it:

#imports
import math
import random
from datetime import datetime

#sorting
def merge(a,b):
    """ Function to merge two arrays """
    c = []
    while len(a) != 0 and len(b) != 0:
        if a[0] < b[0]:
            c.append(a[0])
            a.remove(a[0])
        else:
            c.append(b[0])
            b.remove(b[0])
    if len(a) == 0:
        c += b
    else:
        c += a
    return c

# Code for merge sort
def mergesort(x):
    """ Function to sort an array using merge sort algorithm """
    if len(x) == 0 or len(x) == 1:
        return x
    else:
        middle = len(x)/2
        a = mergesort(x[:int(middle)])
        b = mergesort(x[int(middle):])
        return merge(a,b)

def evolve(nets, progressReport=True):
  popCount = len(nets)

  if progressReport: print("Neural nets thinking...")
  for net in nets:
      for data in training_data:
          net.think([data[0],data[1]], data[2])
  if progressReport: print("Neural nets thought")

  if progressReport: print("Sorting neural nets...")
  nets = mergesort(nets)
  if progressReport: print("Sorted neural nets")

  print("Winner DNA:", nets[0].DNA)
  print("Winner Cost:", nets[0].getCost())

  if progressReport: print("Killing the weak...")
  nets = nets[int(popCount / 2):]
  if progressReport: print("Killed the weak")

  if progressReport: print("Breeding survivors...")

  for i in range(int(popCount/2)):
    dna = mixDNA(nets[i].DNA, nets[random.randint(1,int(popCount/2))].DNA)
    nets.append(NeuralNetwork(dna))

  if progressReport: print("Bred survivors")

  if progressReport: print("\n")


#sigmoid
def sigmoid(x):
    return 1 / (1 + math.e ** -x)

#Length of DNA
DnaLen = 20

#creates random DNA
def createRandomDNA():
    random.seed(datetime.now())
    return ''.join([str(random.randint(1, 9)) for i in range(DnaLen)])

#mutation chance (0 - 1)
mutationChance = 0.01

#mixes DNA (random chance of mutation)
def mixDNA(dna1, dna2):
    midpoint = random.randint(1,20)
    dna = dna1[:midpoint] + dna2[midpoint:] 
    for i in range(len(dna)):
      if random.random() <= mutationChance: dna = dna[:i] + str(random.randint(1,9)) + dna[i+1:]
    return dna

#XOR
training_data = [
    [0, 0, 0],
    [0, 1, 1],
    [1, 0, 1],
    [1, 1, 0]
]

#connects synapses
class Node(object):
    def __init__(self):
        self.inputs = []
        self.outputs = []
        self.value = 0

    def connect(self, other, syn):
        self.outputs.append(syn)
        other.inputs.append(syn)

    def update(self):
        total = sum([i.value for i in self.inputs])
        self.value = sigmoid(total)
        for out in self.outputs: out.trigger(self.value)

#input
class Receptor(Node):
    def __init__(self):
        Node.__init__(self)

    def update(self, inp):
        self.value = inp
        for out in self.outputs: out.trigger(self.value)

#output
class Effector(Node):
    def __init__(self):
        Node.__init__(self)

    def update(self):
        total = sum([i.value for i in self.inputs])
        self.value = total
        return self.value

#connection
class Neurone(Node): pass

#connects nodes
class Synapse(object):
    def __init__(self, weight):
        self.weight = weight
        self.value = 0

    def trigger(self, value):
        self.value = value * self.weight

#the whole network
class NeuralNetwork(object):
    def __init__(self, DNA):
        #DNA
        self.DNA = DNA
        #sets up nodes
        self.receptors = [Receptor() for i in range(2)]
        self.neurones = [Neurone() for i in range(3)]
        self.effectors = [Effector() for i in range(1)]
        #where to extract code from DNA
        counter = 0
        #connects receptors to neurones
        for receptor in self.receptors:
            for neurone in self.neurones:
                """change synapse weight to be based on DNA"""
                Node.connect(receptor, neurone, Synapse(self.getWeightFromDNA(counter)))
                counter += 2
        #connects neurones to effectors
        for neurone in self.neurones:
            for effector in self.effectors:
                """change synapse weight to be based on DNA"""
                Node.connect(neurone, effector, Synapse(self.getWeightFromDNA(counter)))
                counter += 2
        #how wrong
        self.costs = []

    def __lt__(self, other): return self.getCost() < other.getCost()
    def __le__(self, other): return self.getCost() <= other.getCost()
    def __eq__(self, other): return self.getCost() == other.getCost()
    def __ne__(self, other): return self.getCost() != other.getCost()
    def __ge__(self, other): return self.getCost() >= other.getCost()
    def __gt__(self, other): return self.getCost() > other.getCost()

    def getWeightFromDNA(self, location):
      return int(self.DNA[location] + self.DNA[location+1]) / 100 + 0.5

    def think(self, inputs, correct):
        for i in range(len(self.receptors)): self.receptors[i].update(inputs[i])
        for neurone in self.neurones: neurone.update()
        answer = [effector.update() for effector in self.effectors][0]
        self.costs.append(abs(answer - correct))
        return answer 

    def getCost(self):
        return sum(self.costs) / len(self.costs)


def main():
  print("Creating neural nets...")
  nets = [NeuralNetwork(createRandomDNA()) for i in range(1000)]
  print("Created neural nets")

  print("Evolving nets...")
  for i in range(1000):
    for j in nets: j.costs = []
    evolve(nets, False)
    print("Evolved Generation", i+1)

  nets = mergesort(nets)
  print("Evolved nets")

if __name__ == "__main__":
  main()
0

There are 0 best solutions below