自然选择的过程从选择群体中最适应环境的个体开始。后代继承了父母的特性，并且这些特性将添加到下一代中。如果父母具有更好的适应性，那么它们的后代将更易于存活。迭代地进行该自然选择的过程，最终，我们将得到由最适应环境的个体组成的一代。
遗传算法含以下五步：
初始化
个体评价（计算适应度函数）
选择运算
交叉运算
变异运算
验收阶段
1. 初始化
个体以一组参数（变量）为特征，这些特征被称为基因，串联这些基因就可以组成染色体（问题的解）。
在遗传算法中，单个个体的基因组以字符串的方式呈现，通常我们可以使用二进制（1 和 0 的字符串）编码，即一个二进制串代表一条染色体串。因此可以说我们将基因串或候选解的特征编码在染色体中。
2. 个体评价（计算适应度函数）
个体评价利用适应度函数评估了该个体对环境的适应度（与其它个体竞争的能力）。每一个体都有适应度评分，个体被选中进行繁殖的可能性取决于其适应度评分。适应度函数值越大，解的质量就越高。适应度函数是遗传算法进化的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。
3. 选择运算
选择阶段经历了适应性选择和随机选择。在适应性选择中，我们通过适应性函数(fitness function)对种群中的每一条染色体进行适应性评估，按评估结果对染色体进行排序。筛选出适应性最好的一定数量（可以通过参数调节）的染色体，作为下一代的父母加入存货列表。而在随机选择中，我们会随机挑选一些没有通过适应性选择的个体也加入存活列表，这样做是为了使得一些拥有潜在价值基因但适应性很差的个体得以生存下来。
4.交叉运算
每一代染色体的数量是一定的，我们淘汰了一部分染色体，就要生成新的染色体来补足空缺。从上一代中，我们保留了一部分存活的染色体，它们之间将会进行交叉。交叉是指随机从存活列表中抽取两个染色体，将这两条染色体进行融合从而生成新的染色体（就是取一部分父染色体的基因，再在母染色体取在父染色体没有取到的基因，把这些基因合成一条新的染色体），把新的染色体加入种群中。交叉操作会一直持续，直到种群数量跟之前的种群数量相同。
举个例子，下图的交叉点为 3：
父母间在交叉点之前交换基因，从而产生了后代。
父母间交换基因，然后产生的新后代被添加到种群中。
5.变异运算
对于种群中的每一条染色体，使其一定几率地发生随机变异（在这个例子下就是反转染色体上某一个bit的值）。
6.验收阶段
经过很多代的进化之后，种群里面的染色体基本上符合最优化的要求了。这时就可以去对里面的染色体进行解码(decode)，将其转化为实际的解。
案例实现
*求解函数 f(x) = x + 10sin(5x) + 7cos(4*x) 在区间[0,9]的最大值。 **
以我们的目标函数 f(x) = x + 10sin(5x) + 7cos(4x), x∈[0,9] 为例。假如设定求解的精度为小数点后4位，可以将x的解空间划分为 (9-0)×(1e+4)=90000个等分。
2^16<90000<2^17，需要17位二进制数来表示这些解。换句话说，一个解的编码就是一个17位的二进制串。一开始，这些二进制串是随机生成的。一个这样的二进制串代表一条染色体串，这里染色体串的长度为17。
算法流程图如下：
Python实现如下：
#encoding=utf-8
import math
import random
import operator
class GA():
def __init__(self, length, count):
# 染色体长度
self.length = length
# 种群中的染色体数量
self.count = count
# 随机生成初始种群
self.population = self.gen_population(length, count)
def evolve(self, retain_rate=0.2, random_select_rate=0.5, mutation_rate=0.01):
"""
进化
对当前一代种群依次进行选择、交叉并生成新一代种群，然后对新一代种群进行变异
"""
parents = self.selection(retain_rate, random_select_rate)
self.crossover(parents)
self.mutation(mutation_rate)
def gen_chromosome(self, length):
"""
随机生成长度为length的染色体，每个基因的取值是0或1
这里用一个bit表示一个基因
"""
chromosome = 0
for i in xrange(length):
chromosome |= (1 << i) * random.randint(0, 1)
return chromosome
def gen_population(self, length, count):
"""
获取初始种群（一个含有count个长度为length的染色体的列表）
"""
return [self.gen_chromosome(length) for i in xrange(count)]
def fitness(self, chromosome):
"""
计算适应度，将染色体解码为0~9之间数字，代入函数计算
因为是求最大值，所以数值越大，适应度越高
"""
x = self.decode(chromosome)
return x + 10*math.sin(5*x) + 7*math.cos(4*x)
def selection(self, retain_rate, random_select_rate):
"""
选择
先对适应度从大到小排序，选出存活的染色体
再进行随机选择，选出适应度虽然小，但是幸存下来的个体
"""
# 对适应度从大到小进行排序
graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
graded = [x[1] for x in sorted(graded, reverse=True)]
# 选出适应性强的染色体
retain_length = int(len(graded) * retain_rate)
parents = graded[:retain_length]
# 选出适应性不强，但是幸存的染色体
for chromosome in graded[retain_length:]:
if random.random() < random_select_rate:
parents.append(chromosome)
return parents
def crossover(self, parents):
"""
染色体的交叉、繁殖，生成新一代的种群
"""
# 新出生的孩子，最终会被加入存活下来的父母之中，形成新一代的种群。
children = []
# 需要繁殖的孩子的量
target_count = len(self.population) - len(parents)
# 开始根据需要的量进行繁殖
while len(children) < target_count:
male = random.randint(0, len(parents)-1)
female = random.randint(0, len(parents)-1)
if male != female:
# 随机选取交叉点
cross_pos = random.randint(0, self.length)
# 生成掩码，方便位操作
mask = 0
for i in xrange(cross_pos):
mask |= (1 << i)
male = parents[male]
female = parents[female]
# 孩子将获得父亲在交叉点前的基因和母亲在交叉点后（包括交叉点）的基因
child = ((male & mask) | (female & ~mask)) & ((1 << self.length) - 1)
children.append(child)
# 经过繁殖后，孩子和父母的数量与原始种群数量相等，在这里可以更新种群。
self.population = parents + children
def mutation(self, rate):
"""
变异
对种群中的所有个体，随机改变某个个体中的某个基因
"""
for i in xrange(len(self.population)):
if random.random() < rate:
j = random.randint(0, self.length-1)
self.population[i] ^= 1 << j
def decode(self, chromosome):
"""
解码染色体，将二进制转化为属于[0, 9]的实数
"""
return chromosome * 9.0 / (2**self.length-1)
def result(self):
"""
获得当前代的最优值，这里取的是函数取最大值时x的值。
"""
graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
graded = [x[1] for x in sorted(graded, reverse=True)]
return ga.decode(graded[0])
if __name__ == '__main__':
# 染色体长度为17， 种群数量为300
ga = GA(17, 300)
# 200次进化迭代
for x in xrange(200):
ga.evolve()
print ga.result()
运行结果：
7.85672650701