Initiative

本来想正规的发到yeeyan的，可惜偶不是那种严肃认真的淫。所以写到自己blog里乱扯了。

遗传算法（Genetic Algorithms），blah，blah，blah……反正知道现在 r/programming 里这个东东很火就行了。Will Larson给大家带来了一篇精彩的Genetic Algorithms: Cool Name & Damn Simple。前面吹牛的部分就略过了，直接进入正题。

定义需要进化的问题

N个数，使之加起来恰好为X
唉。麻烦了。这样说最直观：
5个数，使之加起来恰好为200

例子：

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


遗传算法解题的成分

individual

individual这个东西理解起来就是 个体

>>> from random import randint
>>> def individual(length, min, max):
... 'Create a member of the population.'
... return [ randint(min,max) for x in xrange(length) ]
...
>>> individual(5,0,100)
[79, 0, 20, 47, 40]
>>> individual(5,0,100)
[64, 1, 25, 84, 87]


population

这个可以理解为 群体 哇？

>>> 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 min possible value in an individual's list of values
... max: the max possible value in an individual's list of values
...
... """
... return [ individual(length, min, max) for x in xrange(count) ]
...
>>> population(3,5,0,100)
[[51, 55, 73, 0, 80], [3, 47, 18, 65, 55], [17, 64, 77, 43, 48]]


fitness

这个叫 fitness 函数。物竞天择，适者生存。注意这个是针对individual的

>>> from operator import add
>>> def fitness(individual, target):
... """
... Determine the fitness of an individual. Lower is better.
...
... individual: the individual to evaluate
... target: the sum of numbers that individuals are aiming for
... """
... sum = reduce(add, individual, 0)
... return abs(target-sum)
...
>>> x = individual(5,0,100)
>>> fitness(x,300)
65

fitness越小越好

grade

评分。和上面fitness function差不多，不过是针对 population 群体的

>>> def grade(pop, target):
... 'Find average fitness for a population.'
... summed = reduce(add, (fitness(x, target) for x in pop), 0)
... return summed / (len(pop) * 1.0)
...
>>> x = population(3,5,0,100)
>>> target = 300
>>> grade(x, target)
116


进化！

下面进入遗传算法的核心：进化。

1. 每一个individual用fitness来判断是否可以作为下一代配种的父母。这样每一代里选择出最强的来配种
2. 配种的方式是，各取自己的一半，组合成一个新的individual。例如：
   
>>> father = [1,2,3,4,5,6]
>>> mother = [10,20,30,40,50,60]
>>> child = father[:3] + mother[3:]
>>> child
[1,2,3,40,50,60]

3. 新生individual和父母同时进入下一代竞争
4. 最后，每一代有少量的突变（mutate）
   
>>> from random import random, randint
>>> chance_to_mutate = 0.01
>>> for i in population:
... if chance_to_mutate > random():
... place_to_modify = randint(0,len(i))
... i[place_to_modify] = randint(min(i), max(i))
...


整合起来

最后综合得到的代码就是：

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    

测试一下

>>> target = 371
>>> p_count = 100
>>> i_length = 5
>>> 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
...

最后得到的结果是：
['76.06', '32.13', '26.34', '18.32', '15.08', '11.69', '14.05', '9.460', '4.950', '0.0', '0.0', '0.0', '0.0', '0.0', '0.800', '0.0', '0.239', '0.780', '0.0', '0.0', '0.0', '0.0', '1.48', '0.0', '0.0', '0.0', '0.0', '0.0', '0.0', '0.149', '0.239', '0.12', '0.0', '0.0', '0.0', '0.0', '0.0', '0.0', '0.0', '0.149', '0.0', '0.0', '0.0', '0.0', '0.0', '0.0', '4.200', '0.0', '2.049', '0.0', '0.200', '0.080', '0.0', '1.360', '0.0', '0.0', '0.0', '0.0', '1.399', '0.0', '0.0', '0.149', '1.389', '1.24', '0.0', '0.16', '0.0', '0.680', '0.0', '0.0', '1.78', '1.05', '0.0', '0.0', '0.0', '0.0', '1.860', '4.080', '3.009', '0.140', '0.0', '0.38', '0.0', '0.0', '0.0', '0.0', '0.0', '2.189', '0.0', '0.0', '3.200', '1.919', '0.0', '0.0', '4.950', '0.0', '0.0', '0.0', '0.0', '0.0', '0.0']
生存率是20%，变异率是1%，只花了9代就得到了比较完美的结果。

完整代码

"""
# 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