一、遗传算法的定义

遗传算法的基本思想是参考生物学中物种“物竞天择，适者生存”的思想。在计算机中，通过给定约束条件，使初始参数不断迭代，从而接近最优解。
遗传算法可描述为：

Initialize population
process-chromosome
loop-while(no-solution OR generations < max-gen)crossovermutateselect new generations according to fitness
end-of-loop

对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代又一代变异。在每一代中评价整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。

二、遗传算法应用（一）：计算一元函数区间最值

• 问题描述：计算函数f(x)=xsin10x+xcos2x在[0,5]上的最大值。

• 分析：

  • 该问题中，采用二进制串来编码染色体，来表示自变量x的值，用函数的因变量作为适应度。因此，二进制转十进制的过程就是种群个体转化为解的过程，假设二进制串长度为10，转为[0,5]内的十进制的语法为：

    import numpy as np
    bytes = 0000000001
    value = np.dot(bytes, 2 ** np.arange(10)[::-1]) / float(2 ** 10 - 1) * 5
    

  • 交叉繁衍操作如下：假设父母DNA分别为DNA1与DNA2，以F代表继承父亲DNA，M代表继承母亲DNA，那么就生成了子代DNA3。

    DNA1 = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0]
    DNA2 = [0, 1, 0, 1, 0, 1, 0, 1, 0, 1][F, F, M, M, F, M, M, M, F, M]
    DNA3 = [1, 0, 0, 1, 1, 1, 0, 1, 1, 1]
    

  • 变异即随机将DNA中的一位取反，0变1，1变0。

  • 选择操作也代表了适者生存的思想，这里将适应度作为淘汰条件，适应度越高的个体越有可能交叉繁衍。

• 完整代码：

import numpy as npclass GA(object):def __init__(self, DNA_SIZE, POP_SIZE, CROSS_RATE, MUTATION_RATE, N_GENERATIONS, X_BOUND):self.DNA_size = DNA_SIZEself.pop_size = POP_SIZEself.cross_rate = CROSS_RATEself.mutate_rate = MUTATION_RATEself.generations = N_GENERATIONSself.bounds = X_BOUNDself.populations = np.random.randint(2, size=(POP_SIZE, DNA_SIZE))def fitness(self, y):return y + 1e-3 - np.min(y)def crossover(self, parent, pop):if np.random.rand() < self.cross_rate:i_ = np.random.randint(0, self.pop_size, size=1)cross_points = np.random.randint(0, 2, self.DNA_size).astype(np.bool)parent[cross_points] = pop[i_, cross_points]return parentdef mutate(self, child):for point in range(self.DNA_size):if np.random.rand() < self.mutate_rate:child[point] = 1 if child[point] == 0 else 0return childdef select(self, pop, fit):idx = np.random.choice(np.arange(self.pop_size), size=self.pop_size, replace=True, p=fit/fit.sum())return pop[idx]def translateDNA(self, pop):return np.dot(pop, 2 ** np.arange(self.DNA_size)[::-1]) / float(2 ** self.DNA_size - 1) * self.bounds[1]def F(self, x):return np.sin(10 * x) * x + np.cos(2 * x) * xif __name__ == '__main__':ga = GA(DNA_SIZE=10, POP_SIZE=100, CROSS_RATE=0.8, MUTATION_RATE=0.03, N_GENERATIONS=200, X_BOUND=[0, 5])fit_DNA = []for _ in range(ga.generations):F_values = ga.F(ga.translateDNA(ga.populations))fit = ga.fitness(F_values)fit_DNA.append(ga.translateDNA(ga.populations[np.argmax(fit), :]))ga.populations = ga.select(ga.populations, fit)pop_copy = ga.populations.copy()for parent in ga.populations:child = ga.crossover(parent, pop_copy)child = ga.mutate(child)parent[:] = childprint('最大值自变量x=', max(fit_DNA))print('最大值y=', ga.F(max(fit_DNA)))

• 演示
  

三、遗传算法应用（二）：猜句子

• 问题描述：给定目标句子，例如目标句为Genetic algorithm is a search algorithm used in computational mathematics to solve optimization.，由随机字符组成的句子演化成目标句。
• 分析
  • 基因编码
    对于该问题，需要一个基础字符集合，也需要一个目标字符串，如下所示：

    geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
    target = "Genetic algorithm is a search algorithm used in computational mathematics to solve optimization."
    

    geneSet表示所有包含的字符组成的集合，target表示目标字符串。
  • 生成初始个体
    接下来需要生成初始个体，即由字符集合随机生成一个与目标字符串长度相等的字符串。
  • 适应度
    遗传算法提供的适应度值是引擎获得的唯一反馈，可以引导其走向一个解决方案。在这个问题中，适应度值为当前字符串与目标字符串匹配的字符个数。
  • 变异
    将字符串的任意两个位置字符调换，即可完成变异操作。
  • 展示
• 完整代码

import datetime
import randomgeneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
target = "Genetic algorithm is a search algorithm used in computational mathematics to solve optimization."def generate_parent(length):genes = []while len(genes) < length:sampleSize = min(length - len(genes), len(geneSet))genes.extend(random.sample(geneSet, sampleSize))return ''.join(genes)def get_fitness(guess):return sum(1 for expected, actual in zip(target, guess) if expected == actual)def mutate(parent):idx = random.randrange(0, len(parent))childGenes = list(parent)newGene, alternate = random.sample(geneSet, 2)childGenes[idx] = alternate if childGenes[idx] == newGene else newGenereturn ''.join(childGenes)def display(guess, startTime):timeDiff = datetime.datetime.now() - startTimefitness = get_fitness(guess)print("{}\t{}\t{}".format(guess, fitness, timeDiff))random.seed()
startTime = datetime.datetime.now()
bestParent = generate_parent(len(target))
bestFitness = get_fitness(bestParent)
while True:child = mutate(bestParent)childFitness = get_fitness(child)if bestFitness >= childFitness:continuedisplay(child, startTime)if childFitness >= len(bestParent):breakbestFitness = childFitnessbestParent = child

• 演示
  

附上GitHub地址：遗传算法应用