ahmedfgad / GeneticAlgorithmPython

Source code of PyGAD, a Python 3 library for building the genetic algorithm and training machine learning algorithms (Keras & PyTorch).
https://pygad.readthedocs.io
BSD 3-Clause "New" or "Revised" License
1.91k stars 466 forks source link

For some reason fitness never exceeds 1.0 #8

Closed CheshireCat26 closed 4 years ago

CheshireCat26 commented 4 years ago

I use pygad to train my neural network. The code below is a test of pygad. And it worked. After I wrote simple NN implementation and tried to train it by pygad. But for some reason, fitness never exceeds 1.0. First I thought that my code doesn't work properly. But I again run my first test of pygad(the code below) and it has the same issue.

`

import math
import pygad

def calculate_neuron(input, weight, nonlinear=None, bias=False):
    """
    Calculate value of neuron.

    :param input: Input for neuron
    :param weight: Weight for each input
    :param nonlinear: Nonlinear function for neuron. If == None then neuron is linear
    :param bias: If true bias exist in previous layer
    :return: value of neuron
    """

    value = 0
    for i in range(len(input)):
        value += input[i] * weight[i]

    if bias:
        value += 1 * weight[len(weight) - 1]

    if nonlinear is not None:
        value = nonlinear(value)

    return value

def sigmoid(x):
    return math.exp(x) / (math.exp(x) + 1)

def xor_neural_network(input, weight):
    """
    This is neural network that must implement xor function. (I didn't read about objects yet)

    :param input: Input for neural network. For this is 2
    :param weight: Weight for neural. Length is 9
    :return:
    """

    hid1 = calculate_neuron(input, weight[:3], sigmoid, True)
    hid2 = calculate_neuron(input, weight[3:6], sigmoid, True)

    output = calculate_neuron([hid1, hid2], weight[6:9], sigmoid, bias=True)
    return output

function_inputs = [[0, 0],
                   [0, 1],
                   [1, 0],
                   [1, 1]]

des_outputs = [0, 1, 1, 0]

def fitness_func(solution):
    outputs = []
    for input in function_inputs:
        outputs.append(xor_neural_network(input, solution))

    error = 0
    for output, des_output in zip(outputs, des_outputs):
        error += abs(output - des_output)

    fitness = 1 / error
    return fitness

if __name__ == "__main__":
    num_generations = 1000
    sol_per_pop = 800
    num_parents_mating = 4

    mutation_percent_genes = 10

    parent_selection_type = "sss"

    crossover_type = "single_point"

    mutation_type = "random"

    keep_parents = 1

    num_genes = 9

    ga_instance = pygad.GA(num_generations=num_generations,
                           sol_per_pop=sol_per_pop,
                           num_parents_mating=num_parents_mating,
                           num_genes=num_genes,
                           fitness_func=fitness_func,
                           mutation_percent_genes=mutation_percent_genes,
                           parent_selection_type=parent_selection_type,
                           crossover_type=crossover_type,
                           mutation_type=mutation_type,
                           keep_parents=keep_parents,
                           )

    while True:
        ga_instance.run()
        print(ga_instance.best_solution())
        print(xor_neural_network(function_inputs[0], ga_instance.best_solution()[0]))
        print(xor_neural_network(function_inputs[1], ga_instance.best_solution()[0]))
        print(xor_neural_network(function_inputs[2], ga_instance.best_solution()[0]))
        print(xor_neural_network(function_inputs[3], ga_instance.best_solution()[0]))
        ga_instance.plot_result()

`

CheshireCat26 commented 4 years ago

I tried this code on linux. Before I run it on windows. After I first run this code it worked. But on second and another times not.

ahmedfgad commented 4 years ago

Hi @CheshireCat26 ,

Glad you are using PyGAD for your project.

I tested your code that builds a neural network with just a single neuron for simulating the XOR gate. Neither my code nor your code has a problem. They work pretty well but just the result does not meet your expectations. Let's add more explanation.

A network with just a single neuron can build a linear classifier. In the case of the XOR gate, it is only solved using a non-linear classifier. The reason is that you cannot separate the 2 classes in such a gate using a single line but using 2 lines. Check the next figure [source]. Thus, you need to use another neuron in addition to the currently existing one to build an XOR gate successfully. XOR

Because your code only works with linear problems, then I tested it using 2 linear problems to build the AND and OR gates. I tested your code that uses PyGAD with the OR and the AND gates and the error reaches 0. In your code, an error of 0 gives a ZeroDivisionError exception while calculating the fitness: fitness = 1 / error So, you need to add a very small number to error to make sure that the denominator will not be zero even if the error is zero. fitness = 1 / (error + 0.0000000001)

For the AND gate, here is the des_outputs list:

des_outputs = [0, 0, 0, 1]

After passing 5,000 generations, here are the outputs of the print statements where you can find that the predictions match the desired outputs.

    print(ga_instance.best_solution())
    print(xor_neural_network(function_inputs[0], ga_instance.best_solution()[0]))
    print(xor_neural_network(function_inputs[1], ga_instance.best_solution()[0]))
    print(xor_neural_network(function_inputs[2], ga_instance.best_solution()[0]))
    print(xor_neural_network(function_inputs[3], ga_instance.best_solution()[0]))

(array([-14.37959057, -15.80686528,  20.23551117, -23.24053507,
       -10.74882437,  27.42294462, -51.74553544, -77.037499  ,
        41.55176339]), 10000000000.0)
1.3059915651403266e-38
2.403786809456487e-38
4.819790303468448e-38
1.0

Here is the fitness values plot for the AND gate. Note that the fitness value is not equal to 1.0 only but 1.0x1e10. AND

For the OR gate, here is the des_outputs list:

des_outputs = [0, 1, 1, 1]

After passing 5,000 generations, here are the outputs of the print statements where you can find that the predictions match the desired outputs.

    print(ga_instance.best_solution())
    print(xor_neural_network(function_inputs[0], ga_instance.best_solution()[0]))
    print(xor_neural_network(function_inputs[1], ga_instance.best_solution()[0]))
    print(xor_neural_network(function_inputs[2], ga_instance.best_solution()[0]))
    print(xor_neural_network(function_inputs[3], ga_instance.best_solution()[0]))

2.5414722620791583e-42
1.0
1.0
1.0

Here is the fitness values plot for the OR gate. OR

Here are some notes:

The edited code that builds the AND and OR gates is as follows where sol_per_pop = 8:

import math
import pygad

def calculate_neuron(input, weight, nonlinear=None, bias=False):
    """
    Calculate value of neuron.

    :param input: Input for neuron
    :param weight: Weight for each input
    :param nonlinear: Nonlinear function for neuron. If == None then neuron is linear
    :param bias: If true bias exist in previous layer
    :return: value of neuron
    """

    value = 0
    for i in range(len(input)):
        value += input[i] * weight[i]

    if bias:
        value += 1 * weight[len(weight) - 1]

    if nonlinear is not None:
        value = nonlinear(value)

    return value

def sigmoid(x):
    return math.exp(x) / (math.exp(x) + 1)

def xor_neural_network(input, weight):
    """
    This is neural network that must implement xor function. (I didn't read about objects yet)

    :param input: Input for neural network. For this is 2
    :param weight: Weight for neural. Length is 9
    :return:
    """

    hid1 = calculate_neuron(input, weight[:3], sigmoid, True)
    hid2 = calculate_neuron(input, weight[3:6], sigmoid, True)

    output = calculate_neuron([hid1, hid2], weight[6:9], sigmoid, bias=True)
    return output

function_inputs = [[0, 0],
                   [0, 1],
                   [1, 0],
                   [1, 1]]

des_outputs = [0, 1, 1, 1] # OR gate outputs
# des_outputs = [0, 0, 0, 1] # AND gate outputs

def fitness_func(solution):
    outputs = []
    for input in function_inputs:
        outputs.append(xor_neural_network(input, solution))

    error = 0
    for output, des_output in zip(outputs, des_outputs):
        error += abs(output - des_output)
    print(error)
    fitness = 1 / (error + 0.0000000001)
    return fitness

if __name__ == "__main__":
    num_generations = 5000
    sol_per_pop = 8
    num_parents_mating = 4

    mutation_percent_genes = 10

    parent_selection_type = "sss"

    crossover_type = "single_point"

    mutation_type = "random"

    keep_parents = 1

    num_genes = 9

    ga_instance = pygad.GA(num_generations=num_generations,
                           sol_per_pop=sol_per_pop,
                           num_parents_mating=num_parents_mating,
                           num_genes=num_genes,
                           fitness_func=fitness_func,
                           mutation_percent_genes=mutation_percent_genes,
                           parent_selection_type=parent_selection_type,
                           crossover_type=crossover_type,
                           mutation_type=mutation_type,
                           keep_parents=keep_parents,
                           )

    ga_instance.run()
    print(ga_instance.best_solution())
    print(xor_neural_network(function_inputs[0], ga_instance.best_solution()[0]))
    print(xor_neural_network(function_inputs[1], ga_instance.best_solution()[0]))
    print(xor_neural_network(function_inputs[2], ga_instance.best_solution()[0]))
    print(xor_neural_network(function_inputs[3], ga_instance.best_solution()[0]))
    ga_instance.plot_result()

Still have some issues, please reply to offer help as much as I can.

Regards, Ahmed

CheshireCat26 commented 4 years ago

Hmm... Maybe I wrote something wrong, but I thought that my neural network has a hidden layer with 2 neurons and an output layer with 1 neuron.

# It's a function that calculates answer from the whole  neural network
def xor_neural_network(input, weight):

    # Here calculates hiddent layer
    hid1 = calculate_neuron(input, weight[:3], sigmoid, True) # Answer from firs neuron in the layer
    hid2 = calculate_neuron(input, weight[3:6], sigmoid, True) # Anwer from second neuron in the layer

    # Here calculates output layer
    output = calculate_neuron([hid1, hid2], weight[6:9], sigmoid, bias=True) 
    return output
# It's a function that calculates answer from neuron.
def calculate_neuron(input, weight, nonlinear=None, bias=False):
    """
    Calculate value of neuron.

    :param input: Input for neuron
    :param weight: Weight for each input
    :param nonlinear: Nonlinear function for neuron. If == None then neuron is linear
    :param bias: If true bias exist in previous layer
    :return: value of neuron
    """

    # Calculate sum for the input
    value = 0
    for i in range(len(input)):
        value += input[i] * weight[I]

   # Add bias's vaule
    if bias:
        value += 1 * weight[len(weight) - 1]

    # Use some nonlinear function
    if nonlinear is not None:
        value = nonlinear(value)

    return value
ahmedfgad commented 4 years ago

That is right! You use 2 neurons. I missed that.

Your code seems to be working but you may need to restart it to use different initial populations which helps to reach the desired outputs.

Here are the inputs and outputs:

function_inputs = [[0, 0],
                   [0, 1],
                   [1, 0],
                   [1, 1]]

des_outputs = [0, 1, 1, 0] # XOR gate outputs

The weights reached after by the code are as follows:

print(ga_instance.best_solution())

(array([ 34.82515259, -31.31674013,  15.69234828,  26.04845489,
        -30.5789862 , -16.1293943 , -53.79681621,  64.48365107,
         26.18911697]), 9409448191.531862)

The predicted outputs are:

1.023610911643879e-12
0.9999999999957713
0.9999999999999998
1.0235962787301161e-12

Here is how fitness evolves: XOR

I think the problem occurs due to the design of the neural network. I already worked on building and training neural networks using the genetic algorithm where you can find this tutorial published in March 2019.

I was working on extending PyGAD to include building and training neural networks. I made 2 different tests for on 2 different networks (one of them builds the XOR) and the results are working from the first run of the genetic algorithm.

The library is to be updated soon.

ahmedfgad commented 4 years ago

Hi,

PyGAD supports building neural networks using the pygad.nn module and training it using the genetic algorithm using the pygad.gann module. The source code of these modules is available in these GitHub projects:

Check the documentation of these 2 modules:

An example is available for building and training a neural network that simulates the XOR gate. Check its code here: https://pygad.readthedocs.io/en/latest/README_pygad_gann_ReadTheDocs.html#xor

import pygad
import pygad.nn
import pygad.gann

def fitness_func(solution, sol_idx):
    global GANN_instance, data_inputs, data_outputs

    predictions = pygad.nn.predict(last_layer=GANN_instance.population_networks[sol_idx],
                                   data_inputs=data_inputs)
    correct_predictions = numpy.where(predictions == data_outputs)[0].size
    solution_fitness = (correct_predictions/data_outputs.size)*100

    return solution_fitness

def callback_generation(ga_instance):
    global GANN_instance, last_fitness

    population_matrices = pygad.gann.population_as_matrices(population_networks=GANN_instance.population_networks,
                                                            population_vectors=ga_instance.population)

    GANN_instance.update_population_trained_weights(population_trained_weights=population_matrices)

    print("Generation = {generation}".format(generation=ga_instance.generations_completed))
    print("Fitness    = {fitness}".format(fitness=ga_instance.best_solution()[1]))
    print("Change     = {change}".format(change=ga_instance.best_solution()[1] - last_fitness))

    last_fitness = ga_instance.best_solution()[1].copy()

# Holds the fitness value of the previous generation.
last_fitness = 0

# Preparing the NumPy array of the inputs.
data_inputs = numpy.array([[1, 1],
                           [1, 0],
                           [0, 1],
                           [0, 0]])

# Preparing the NumPy array of the outputs.
data_outputs = numpy.array([0,
                            1,
                            1,
                            0])

# The length of the input vector for each sample (i.e. number of neurons in the input layer).
num_inputs = data_inputs.shape[1]
# The number of neurons in the output layer (i.e. number of classes).
num_classes = 2

# Creating an initial population of neural networks. The return of the initial_population() function holds references to the networks, not their weights. Using such references, the weights of all networks can be fetched.
num_solutions = 6 # A solution or a network can be used interchangeably.
GANN_instance = pygad.gann.GANN(num_solutions=num_solutions,
                                num_neurons_input=num_inputs,
                                num_neurons_hidden_layers=[2],
                                num_neurons_output=num_classes,
                                hidden_activations=["relu"],
                                output_activation="softmax")

# population does not hold the numerical weights of the network instead it holds a list of references to each last layer of each network (i.e. solution) in the population. A solution or a network can be used interchangeably.
# If there is a population with 3 solutions (i.e. networks), then the population is a list with 3 elements. Each element is a reference to the last layer of each network. Using such a reference, all details of the network can be accessed.
population_vectors = pygad.gann.population_as_vectors(population_networks=GANN_instance.population_networks)

# To prepare the initial population, there are 2 ways:
# 1) Prepare it yourself and pass it to the initial_population parameter. This way is useful when the user wants to start the genetic algorithm with a custom initial population.
# 2) Assign valid integer values to the sol_per_pop and num_genes parameters. If the initial_population parameter exists, then the sol_per_pop and num_genes parameters are useless.
initial_population = population_vectors.copy()

num_parents_mating = 4 # Number of solutions to be selected as parents in the mating pool.

num_generations = 500 # Number of generations.

mutation_percent_genes = 5 # Percentage of genes to mutate. This parameter has no action if the parameter mutation_num_genes exists.

parent_selection_type = "sss" # Type of parent selection.

crossover_type = "single_point" # Type of the crossover operator.

mutation_type = "random" # Type of the mutation operator.

keep_parents = 1 # Number of parents to keep in the next population. -1 means keep all parents and 0 means keep nothing.

init_range_low = -2
init_range_high = 5

ga_instance = pygad.GA(num_generations=num_generations,
                       num_parents_mating=num_parents_mating,
                       initial_population=initial_population,
                       fitness_func=fitness_func,
                       mutation_percent_genes=mutation_percent_genes,
                       init_range_low=init_range_low,
                       init_range_high=init_range_high,
                       parent_selection_type=parent_selection_type,
                       crossover_type=crossover_type,
                       mutation_type=mutation_type,
                       keep_parents=keep_parents,
                       callback_generation=callback_generation)

ga_instance.run()

# After the generations complete, some plots are showed that summarize how the outputs/fitness values evolve over generations.
ga_instance.plot_result()

# Returning the details of the best solution.
solution, solution_fitness, solution_idx = ga_instance.best_solution()
print("Parameters of the best solution : {solution}".format(solution=solution))
print("Fitness value of the best solution = {solution_fitness}".format(solution_fitness=solution_fitness))
print("Index of the best solution : {solution_idx}".format(solution_idx=solution_idx))

if ga_instance.best_solution_generation != -1:
    print("Best fitness value reached after {best_solution_generation} generations.".format(best_solution_generation=ga_instance.best_solution_generation))

# Predicting the outputs of the data using the best solution.
predictions = pygad.nn.predict(last_layer=GANN_instance.population_networks[solution_idx],
                               data_inputs=data_inputs)
print("Predictions of the trained network : {predictions}".format(predictions=predictions))

# Calculating some statistics
num_wrong = numpy.where(predictions != data_outputs)[0]
num_correct = data_outputs.size - num_wrong.size
accuracy = 100 * (num_correct/data_outputs.size)
print("Number of correct classifications : {num_correct}.".format(num_correct=num_correct))
print("Number of wrong classifications : {num_wrong}.".format(num_wrong=num_wrong.size))
print("Classification accuracy : {accuracy}.".format(accuracy=accuracy))

The next figure shows how the fitness value evolves. The accuracy is 100.

Please let me know if there is something I could help.

Regards, Ahmed

ahmedfgad commented 4 years ago

Closed for no further interaction.