Solving non-linear equations using Genetic Algorithms from scratch...in python

Genetic algorithms are a subset of a more broad category of algorithms known as Evolutionary Algorithms. Some of the other techniques that fall under the same umbrella are

1. Genetic Programming.
2. Evolutionary Programming.
3. Evolutionary Strategy.
4. Differential Evolution.
5. Neuroevolution

The common theme in all of these is that they are based on the concept of Biological Evolution of life and Natural Selection. In implementing these algorithms we play god as we create a population of individuals with some DNA like property.

Initially, we create the population which has only a randomly created DNA in them, later on, by the transformation that we will bring into the system will slowly alter the DNA property of the individuals better for the tasks that we want them to do. That is the main idea behind Evolutionary Algorithms.

Genetic algorithm

STEP 1

We define a criteria of the fitness among these individuals, called the fitness function. We perform some cheap version of natural selection based on the fitness function to select the strongest candidates. So, for example, we could just take the 20 most fit candidates and select them to go to the next generation of population or something like that.

STEP 2

The selected candidates are then used to perform mating, where different DNA gets mixed up, some mutations or variations might have occurred in between resulting in changing some part of the DNA and the next generation of agents are being born.

STEP 3

After this goes on for a while we find that the million-th generation is pretty strong and fit and hence we have successfully prepared a strong version of our DNA.

There is a theme to the kind of problems that can be solved using evolutionary algorithms. After I have had shown you an example I will try to explain what those problem categories are.

---

Let's get Started

Problem Statement: Find a solution of the non-linear equation using genetic algorithm.

$x^{3} - y^{2} + 2z = 100$

Solution Overview

We will take random values of x,y and z, call it an individual and then create a set of these triplet values, call them a population.

Sort the population list according to the the fitness of each individual. Select a few from the best and perform evolutionary operators, namely, mutations, crossovers or whatever kind of mixing that comes to your  mind to create new set of individuals from these.

We keep on creating new and new generations till we have found a  pretty close solution to our problem.

Python Code from scratch

Let's start by designing the fitness function and give it a function to our equation,

def equation(a,b,c):
	return a**3 - b**2 + 2*c - 100.0;

def fitness(a,b,c):
	val = equation(a,b,c)
	if val!=0:
		return abs(1/val)
	else:
		return 999999

Here, we check for the error in our parameters using the equation() function, we take the fitness to be the reciprocal of that 1/error because the lower the error greater is the fitness.

Let's create a class for our Individual member,

class Individual:
	def __init__(self,a,b,c):
		self.a=a
		self.b=b
		self.c=c
		self.fitness = fitness(self.a,self.b,self.c)

	def __lt__(self,other):
		return self.fitness < other.fitness

	def __str__(self):
		return str(self.fitness)+"->x="+str(self.a)+",y="+str(self.b)+",z="+str(self.c)

Here, I have taken 3 parameters to the class constructor, a,b,c which represents our 3 variables x,y,z.

Then we stored the fitness for that individual in that class object itself: self.fitness = fitness(self.a,self.b,self.c).

I have defined 2 more class methods, __lt__() and __str__() which are python class built ins for sort and print functions. You can ignore them as they are not a part of the genetic algorithm, they are just there for convenience.

And Finally, the main() function,

def main():
	population = [ Individual(random.random()*20,random.random()*20,random.random()*20) for x in range(1000) ]

	for i in range(5550):
		population.sort()
		population.reverse()
		best_of_population = population[:100]
		print("fitness:",best_of_population[0])

		pool_of_values = []

		for individual in best_of_population:
			pool_of_values.append(individual.a)
			pool_of_values.append(individual.b)
			pool_of_values.append(individual.c)
            
        	#the best 20 members are shifted directly to the next generation
		next_generation = best_of_population[:20]
		

		next_generation.extend([ Individual(random.choice(pool_of_values)+random.uniform(-1,1),random.choice(pool_of_values)+random.uniform(-1,1),random.choice(pool_of_values)+random.uniform(-1,1)) for x in range(900) ])
		population = next_generation


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

The first line creates a population of randomly generated 1000 Individuals. There is a loop after that, Loop of Evolution. Then we sort according to our fitness function(remember the __lt__ function inside the Individual class), and because we need the most fit members from the population we reverse the list.

We find the best_of_population which are just the best 100 candidates from the generation. We create a pool of the a,b,c values from these best candidates in order to use them to create the next generation!

In order to perform mutation, we simply add a uniformly distributed value, random.uniform(-1,1) , to each of the value selected from the pool of values.

And we repeat!! Let's save it in a file called genetic_algorithm.py  and run it using the command,

$ python3 genetic_algorithm.py

.
.
.
.
fitness: 75711.15804229603->x=5.146394207793115,y=6.573920882309008,z=3.456138508205333
fitness: 75711.15804229603->x=5.146394207793115,y=6.573920882309008,z=3.456138508205333
fitness: 75711.15804229603->x=5.146394207793115,y=6.573920882309008,z=3.456138508205333
fitness: 75711.15804229603->x=5.146394207793115,y=6.573920882309008,z=3.456138508205333
fitness: 75711.15804229603->x=5.146394207793115,y=6.573920882309008,z=3.456138508205333
fitness: 75711.15804229603->x=5.146394207793115,y=6.573920882309008,z=3.456138508205333
fitness: 75711.15804229603->x=5.146394207793115,y=6.573920882309008,z=3.456138508205333
fitness: 75711.15804229603->x=5.146394207793115,y=6.573920882309008,z=3.456138508205333
fitness: 75711.15804229603->x=5.146394207793115,y=6.573920882309008,z=3.456138508205333

As you can see, that the fitness has reached 75711.15 which is found for the values x=5.14639,y=6.5739,z=3.45613, you can check by putting it in the equation,

$x^{3} - y^{2} + 2z = 100$

gives the output of  100.00001320809278.

Note: Because of the random numbers use, you may find a different solution when you run the program!

What kind of problems can be solved using genetic algorithms?

Any problem which has a structure which directly is responsible for its fitness in a task can be solved using genetic algorithms. They are a bit underrated at the moment but they are very powerful.

Genetic Programming is the technique that can start with a basic computer program itself and build better programs to solve a problem.

It can be even used to start with a small neural network and gradually using mutation and variations create better neural networks, all you need is a fitness function!

Conclusion

In conclusion, evolutionary algorithms often perform well approximating solutions to all types of problems because they ideally do not make any assumption about the underlying fitness landscape.