1。2 国内外研究现状及存在的问题

1。2。1 国外研究历程

1。2。2 国内研究历程

1。3 本文的主要内容

从第二章开始，我们首先描述遗传算法的基本思想和原理，以及遗传算法的基本操 作流程，这是我们使用遗传算法解决背包问题的基础。第三章将先阐释背包问题，然后 详细述说对遗传基因的编码，对遗传算子的选择，控制参数的确定，以及对于约束问题 的处理。第四章将使用测试函数对我们设计的遗传算法进行检测。使用通过检测的遗传 算法，观察其在不同参数以及初始条件下，对背包问题求解的过程，并分析实验结果。

第二章 遗传算法的基本思想

2。1 遗传算法的产生与发展

早在 1950 到 1960 年间，就已经有学者开始了早期进化算法的研究，当时是由几位 计算机科学家独立进行的，他们想将进化的思想发展成解决优化问题的工具，他们将这 项研究称为“人工进化系统”。这便是遗传算法的初始形态。

到了 20 世纪 70 年代初期，美国的 Holland 建立了较为完整的理论和方法，并出版 了《自然与人工系统的适应性行为》（Adaptation in Natural and Artificial System）一书[9]。 Holland 将这种算法正式命名为遗传算法，并且通过对遗传算法的研究将其利用到优化 问题的求解中，甚至尝试使机器利用遗传算法获得自主学习的能力。Holland 当初的基 础理论直到现代依然被学者们广泛使用，可见 Holland 对遗传算法做出来的贡献之大[9]。

几十年来，遗传算法日趋成熟，无论是用来解决实际问题还是用来建模，其应用范 围都在不断扩展。正是目睹了遗传算法的优秀能力，很多学者认为这位人工智能的产生 提供了一条行之有效的途径，他们希望计算机通过不断进化的算法来获得智能，这使人 们对遗传算法的研究热情日益高涨。

2。2 遗传算法的基本思想

由于遗传算法的思想来源于自然进化，我们就先从生物进化理论和遗传学的基本知 识开始讲起，这有助于我们更好地学习遗传算法。

从最原始的地球开始出现的原始生物，到现代社会的生物种类复杂繁多，更是出现 了先进的生物——人类，这一切都是生物自身经历了长期进化过程的演变，逐渐进化以 适应自然环境的结果。达尔文（1858 年）用自然选择对此作出了解释，表面上是生物为 了适应自然而造成的，其实也可以看出是自然对物种进行了有方向的选择，这才造成了 这样的结果，这正解释了生物的进化的原因。其自然选择学说主要分为以下三个方面[10]：

（1）遗传（heredity） 这是生物的普遍特征，由于有性生殖是通过把父代的遗传 信息复制过来并继承给子代，所以父代与子代之间拥有高程度相似的特性，这也就是我 们俗话中所说的种瓜得瓜，种豆得豆。正是遗传的这一特征，才保持了物种的稳定性， 在一定程度上可以说，只有获得稳定的子代，才是正确的遗传方式。

（2）变异（variation） 通过遗传连接的父代和子代之间具有高度的相似性，但并 不是说父代与子代就是完全一样的，他们之间总是或多或少地存在着某些差异，这种差

异是由一种现象产生的，我们把这种现象，称为变异。这一现象是随机发生的，而且是 不可预测其方向的，但是正是由于变异的存在才使得生物群体中的物种产生了多种多样 的特征，这也保证了生物的多样性。