7
$\begingroup$

I have been looking for a while for examples of how I could find the points at which a function achieves its minimum using a genetic algorithm approach in Python. I looked at DEAP documentation, but the examples there were pretty hard for me to follow. For example:

def  function(x,y):
     return x*y+3*x-x**2

I am looking for some references on how I can make a genetic algorithm in which I can feed some initial random values for both x and y (not coming from the same dimensions). Can someone with experience creating and using genetic algorithms give me some guidance on this?

$\endgroup$
  • 2
    $\begingroup$ This problem is solvable analytically using calculus and does not require statistical learning. Assuming you want a numerical solution, its more readily solvable using stochastic gradient descent rather than a genetic algorithm. Also, notice that you have defined a function that is linear in y and the x term that scales fastest goes like -x^2, so for most parameter regimes, the solution is uninteresting (xmax,ymin). I suggest spending a little more time finding an example that is more meaningful and deciding between SGD and GA. Here's a true genetic algorithm example $\endgroup$ – AN6U5 Jan 5 '16 at 12:50
  • $\begingroup$ Hi , in fact it is just an example. In practice my function is a combination of 2 nested functions in which I dont even have a hessian. $\endgroup$ – gm1 Jan 5 '16 at 12:58
  • $\begingroup$ But do you see the relation between stochastic gradient descent and genetic algorithms? And that the example you provided is so simplistic that there is no difference between the two? All I'm getting at is that you need a more complex example to illicit the differences and hence better understand the latter. $\endgroup$ – AN6U5 Jan 5 '16 at 16:44
  • $\begingroup$ I was looking for an example where it is described a trivial example like the one aboce in order to generalize from it. $\endgroup$ – gm1 Jan 5 '16 at 16:48
6
$\begingroup$

Here is a trivial example, which captures the essence of genetic algorithms more meaningfully than the polynomial you provided. The polynomial you provided is solvable via stochastic gradient descent, which is a simpler minimimization technique. For this reason, I am instead suggesting this excellent article and example by Will Larson.

Quoted from the original article:

Defining a Problem to Optimize Now we're going to put together a simple example of using a genetic algorithm in Python. We're going to optimize a very simple problem: trying to create a list of N numbers that equal X when summed together.

If we set N = 5 and X = 200, then these would all be appropriate solutions.

lst = [40,40,40,40,40]
lst = [50,50,50,25,25]
lst = [200,0,0,0,0]

Take a look at the entire article, but here is the complete code:

# Example usage
from genetic import *
target = 371
p_count = 100
i_length = 6
i_min = 0
i_max = 100
p = population(p_count, i_length, i_min, i_max)
fitness_history = [grade(p, target),]
for i in xrange(100):
    p = evolve(p, target)
    fitness_history.append(grade(p, target))

for datum in fitness_history:
   print datum
"""
from random import randint, random
from operator import add

def individual(length, min, max):
    'Create a member of the population.'
    return [ 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

    """
    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
    """
    sum = reduce(add, individual, 0)
    return abs(target-sum)

def grade(pop, target):
    'Find average fitness for a population.'
    summed = reduce(add, (fitness(x, target) for x in pop))
    return summed / (len(pop) * 1.0)

def evolve(pop, target, retain=0.2, random_select=0.05, mutate=0.01):
    graded = [ (fitness(x, target), x) for x in pop]
    graded = [ x[1] for x in sorted(graded)]
    retain_length = int(len(graded)*retain)
    parents = graded[:retain_length]
    # randomly add other individuals to
    # promote genetic diversity
    for individual in graded[retain_length:]:
        if random_select > random():
            parents.append(individual)
    # mutate some individuals
    for individual in parents:
        if mutate > random():
            pos_to_mutate = 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] = 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 = randint(0, parents_length-1)
        female = 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

I think it could be quite pedagogically useful to also solve your original problem using this algorithm and then also construct a solution using stochastic grid search or stochastic gradient descent and you will gain a deep understanding of the juxtaposition of those three algorithms.

Hope this helps!

$\endgroup$
  • 1
    $\begingroup$ How is SGD a subset of Genetic Algorithms? SGD isn't population-based, doesn't use any of the genetic operators, and genetic algorithms do not use gradient-based optimization. $\endgroup$ – Jérémie Clos Jan 5 '16 at 18:00
  • 1
    $\begingroup$ Hi ANSU5 , excelent reference , just wait to put it in pracitce tommorow $\endgroup$ – gm1 Jan 5 '16 at 19:45
  • $\begingroup$ @Jérémie Clos, you are correct. I have edited the answer to reflect this. I was caught up in the discussion above and was trying to illustrate some similarities in various optimization techniques. But this likely obfuscated more than in elucidated. $\endgroup$ – AN6U5 Jan 5 '16 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.