I am trying to solve for the optimum combination of 6 discrete values that take any number between 2 and 16 which will return to me the minimum function value of the function = 1/x1 + 1/x2 + 1/x3 ... 1/xn
The constraint is that the function value has to be less than 0.3
I have followed an online tutorial which describes how to implement GA for such problems but I am getting erroneous results. Without the constraint, the optimum values should be the largest values which is 16 in this problem but I am not getting that
import random
from operator import add
def individual(length, min, max):
'Create a member of the population.'
return [ random.randint(min,max) for x in xrange(length) ]
def population(count, length, min, max):
"""
Create a number of individuals (i.e. a population).
count: the number of individuals in the population
length: the number of values per individual
min: the minimum possible value in an individual's list of values
max: the maximum possible value in an individual's list of values
"""
##print 'population',[ individual(length, min, max) for x in xrange(count) ]
return [ individual(length, min, max) for x in xrange(count) ]
def fitness(individual, target):
"""
Determine the fitness of an individual. Higher is better.
individual: the individual to evaluate
target: the target number individuals are aiming for
"""
pressure = 1/sum(individual)
print individual
return abs(target-pressure)
def grade(pop, target):
'Find average fitness for a population.'
summed = reduce(add, (fitness(x, target) for x in pop))
'Average Fitness', summed / (len(pop) * 1.0)
return summed / (len(pop) * 1.0)
def evolve(pop, target, retain=0.4, random_select=0.05, mutate=0.01):
graded = [ (fitness(x, target), x) for x in pop]
print 'graded',graded
graded = [ x[1] for x in sorted(graded)]
print 'graded',graded
retain_length = int(len(graded)*retain)
print 'retain_length', retain_length
parents = graded[:retain_length]
print 'parents', parents
# randomly add other individuals to
# promote genetic diversity
for individual in graded[retain_length:]:
if random_select > random.random():
parents.append(individual)
# mutate some individuals
for individual in parents:
if mutate > random.random():
pos_to_mutate = random.randint(0, len(individual)-1)
# this mutation is not ideal, because it
# restricts the range of possible values,
# but the function is unaware of the min/max
# values used to create the individuals,
individual[pos_to_mutate] = random.randint(
min(individual), max(individual))
# crossover parents to create children
parents_length = len(parents)
desired_length = len(pop) - parents_length
children = []
while len(children) < desired_length:
male = random.randint(0, parents_length-1)
female = random.randint(0, parents_length-1)
if male != female:
male = parents[male]
female = parents[female]
half = len(male) / 2
child = male[:half] + female[half:]
children.append(child)
parents.extend(children)
return parents
target = 0.3
p_count = 6
i_length = 6
i_min = 2
i_max = 16
p = population(p_count, i_length, i_min, i_max)
fitness_history = [grade(p, target),]
for i in xrange(100):
p = evolve(p, target)
print p
fitness_history.append(grade(p, target))
for datum in fitness_history:
print datum
The expected results is a combination of values between 2 and 16 that returns the minimum value of the function while honouring the constraint that the function cannot be greater than 0.3.
The order in which you perform the heuristics is very unusual for a genetic algorithm. Typically, a genetic algorithm follows the steps:
Another slightly different approach is called evolution strategy (ES), but which also performs different. None of the evolutionary algorithms I know of use crossover at the end. In ES the crossover is used to calculate a centroid individual of the population and use this as base for mutating. All mutants of the centroid then form the next generation. In ES also the next generation is formed using either the new generation only (comma selection - requires you to oversample the current parent generation) or using old and new generation (plus selection). ES performs
In your implemented algorithm, which is neither, you don't seem to apply enough selection pressure in order to drive the search towards better regions. Just sorting the population and taking an elite subset is not necessarily the idea of a genetic algorithm. You have to choose the parents from the whole population, but giving some bias to better individuals. Typically this is done using fitness proportional or tournament selection.
It is also not standard to introduce random individuals into the search. Are you sure that you require diversity preservation for your problem? Does it provide better results than without or maybe gives you even worse results? A simple alternative is to detect convergence and perform a restart of the whole algorithm until you reach the stopping criterion (timeout, number of generated individuals, etc.).
Crossover and mutation are okay. However, in single-point crossover typically you choose the crossover point random.
Another observation: The fitness function in your description and the one implemented in your code does not match.
1/(x1 + x2 + ... + xn)
does not equal
1/x1 + 1/x2 + ... + 1/xn