I have implemented two pieces of code as part of an Evolutionary Algorithm study: Particle Swarm Optimisation (PSO) and Genetic Algorithm (GA). Both are designed to find an optimal solution to a problem, in this case finding the global minimum of a mathematical function.
PSO performs very efficiently and quickly requiring very few iterations. GA, however, uses a lot of memory and I cannot see why.
The memory used depends on the input dimensions and population size, but it has been well over 8GB in some cases without reaching the max number of iterations (terminated myself).
I have tried using the garbage collector, gc
, without success. Can anyone see why this may be? Also feel free to comment on the coding style.
To run the code, you will need use cec2005real (pip install cec2005real
). The idea is a list of numbers is passed into a function from cec2005real, and a single value >0 called the fitness is returned (0 is the optimal solution).
import numpy as np
from cec2005real.cec2005 import Function
np.random.seed(12)
class GeneticAlgorithm():
def __init__(self, pop_size, mutation_rate, dimen):
self.pop_size = pop_size
self.mutation_rate = mutation_rate
self.dimen = dimen
def _initialize(self):
self.population = np.empty(shape=(self.pop_size,self.dimen))
for i in range(self.pop_size):
individual = np.random.uniform(-100.0,100.0,self.dimen)
self.population[i] = individual
def _calculate_fitness(self):
pop_fitness = np.empty(self.pop_size)
for i,individual in enumerate(self.population):
fbench = Function(1, self.dimen)
fitness_func = fbench.get_eval_function()
fitness = fitness_func(individual)
pop_fitness[i]=fitness
return pop_fitness
def _tournamentSelection(self, pop_fitness):
N = len(pop_fitness)
best_fitness = 0.0
idx = 0
for i_ in range(3):
j = np.random.randint(0,N)
fit = pop_fitness[j]
if fit > best_fitness:
best_fitness = fit
idx = j
return idx
def _mutate(self, individual):
for j in range(len(individual)):
if np.random.random() < self.mutation_rate:
individual[j] = np.random.uniform(-100.0,100.0)
return individual
def _twoPointCrossover(self, parent1, parent2):
N = len(parent1)
cx1 = np.random.randint(0,N)
cx2 = np.random.randint(0,N)
if cx1 == cx2:
if cx1 == 0:
cx2 += 1
else:
cx1 -= 1
if cx2 < cx1:
cx1,cx2 = cx2,cx1
child1 = np.concatenate((parent1[:cx1], parent2[cx1:cx2], parent1[cx2:]))
child2 = np.concatenate((parent2[:cx1], parent1[cx1:cx2], parent2[cx2:]))
return child1, child2
def main(self, iterations):
self._initialize()
for epoch in range(iterations):
pop_fitness = self._calculate_fitness()
fittest_individual = self.population[np.argmin(pop_fitness)]
min_fitness = min(pop_fitness)
pop_fitness = 1/np.array(pop_fitness)
mfit = 1/min_fitness
probabilities = [f / sum(pop_fitness) for f in pop_fitness]
# Determine the next generation
new_pop = np.empty(shape=(self.pop_size,self.dimen))
for i in np.arange(0, self.pop_size, 2):
idx1 = self._tournamentSelection(pop_fitness)
idx2 = self._tournamentSelection(pop_fitness)
# Perform crossover to produce children
child1, child2 = self._twoPointCrossover(self.population[idx1],
self.population[idx2])
# Save mutated children for next generation
new_pop[i] = self._mutate(child1)
new_pop[i+1] = self._mutate(child2)
self.population = new_pop
if epoch%1000==0:
print ("[Epoch %d, Fitness: %f]" % (epoch+1, min_fitness))
if __name__ == "__main__":
ga = GeneticAlgorithm(10, 0.01, 10)
ga.main(100000)