根据生物学理论，生物的性状由基因决定，而基因会发生变化，有一些变化使得生物的生存能力变强，而另一些变化效果相反。那些不适应环境的生物会被淘汰，适应的才能生存下来的。而它们后代的基因又会变化。不断重复这个过程，大自然最后选择出具有很强生存能力的生物。

美国的科学家J.Holland借鉴了进化论于1975年提出遗传算法。这里从机器学习的角度说说遗传算法。机器学习是从已知的样本总结出规律，这个规律既能符合已知的样本数据，又能预测新的样本数据。这个规律一般用函数来表示，所以可把机器学习看作是在函数空间里进行搜索。

遗传算法是这样的。先随机列出一些函数。把每个函数都看成是一个染色体，由若干个基因组成。测试这些函数的适应度。函数在训练数据上的错误率越高，则适应度越低。从这些函数中选择一些保留下来，适应度高的函数被选中的概率越大，没被选中的函数淘汰掉。这些被选中的函数通过基因重组产生后代，其中有一些发生基因突变。然后再测试这些函数的适应度，再淘汰一些函数。……多次重复这个过程，如果某个函数的适应度高于预先设定的阈值，则过程终止，这个函数被选出来。

这里有个关键的问题，函数应该如何怎样表示，才能把它看成是由若干个基因组成的？

不知是不是所有的函数都能这样表示，这里只举一个离散值的例子。假设西瓜是不是好瓜，由它的颜色和敲声这两个属性决定。颜色包括三种可能，浅白、青绿、乌黑，而敲声也有三种可能：清脆、浊响、沉闷。现在考虑颜色，我们用长度为3的位串来表示对属性的约束，每位表示一个可能值。若该位为1，则表示该属性可以取对应的值。比如010表示颜色是青绿，而110表示浅白或青绿都行。

多个属性约束的合取表示成单个属性对应位串的合取。比如“当颜色为浅白或乌绿，而且敲声清脆”，表示成位串110100。好瓜用1表示，坏瓜用0表示，“当颜色为浅白或乌绿而且敲声清脆时，西瓜是好瓜”，用位串表示：1101001。类似地，可用位串表示完整的函数。

    不同函数的位串重新组合，或位串发生变化，对应于遗传算法里的基因重组和突变。这些变化的规则应该保证得到的函数是合法的，比如颜色的三个值里，最少必须有一个值为1，不能用000来表示对颜色的约束。