遗传算法 ( GA , Genetic Algorithm ) ，也称进化算法 。 遗传算法是受达尔文
的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍
遗传算法前有必要简单的介绍生物进化知识。
一.进化论知识
作为遗传算法生物背景的介绍，下面内容了解即可：
种群(Population)：生物的进化以群体的形式进行，这样的一个群体称
为种群。
个体：组成种群的单个生物。
基因 ( Gene ) ：一个遗传因子。
染色体 ( Chromosome ) ：包含一组的基因。
生存竞争，适者生存：对环境适应度高的、牛 B 的个体参与繁殖的机会比
较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越
来越少。
遗传与变异：新个体会遗传父母双方各一部分的基因，同时有一定的概率发
生基因变异。
简单说来就是：繁殖过程，会发生基因交叉( Crossover ) ，基因突变
( Mutation ) ，适应度( Fitness )低的个体会被逐步淘汰，而适应度高的个体
会越来越多。那么经过 N 代的自然选择后，保存下来的个体都是适应度很高的，
其中很可能包含史上产生的适应度最高的那个个体。
二.遗传算法思想
借鉴生物进化论，遗传算法将要解决的问题模拟成一个生物进化的过程，通
过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，
增加适应度函数值高的解。这样进化 N 代后就很有可能会进化出适应度函数值
很高的个体。
举个例子，使用遗传算法解决“0-1 背包问题”的思路：0-1 背包的解可以编
码为一串 0-1 字符串（0：不取，1：取） ；首先，随机产生 M 个 0-1 字符串，
然后评价这些 0-1 字符串作为 0-1 背包问题的解的优劣；然后，随机选择一些
字符串通过交叉、突变等操作产生下一代的 M 个字符串，而且较优的解被选中
评论0