清华大学毕业设计论文
摘 要
研究能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应的控
制搜索过程，从而得到最优解或准最优解的通用搜索算法一直是令人瞩目的课
题。遗传算法就是这种特别有效的算法。
遗传算法（Genetic Algorithm——GA），是模拟达尔文的遗传选择和自然
淘汰的生物进化过程的计算模型，它是由美国 Michigan 大学的 J.Holland 教授
于 1975 年首先提出的。J.Holland 教授和它的研究小组围绕遗传算法进行研究的
宗旨有两个：抽取和解释自然系统的自适应过程以及设计具有自然系统机理的
人工系统。遗传算法的大致过程是这样的：将每个可能的解看作是群体中的一
个个体或染色体，并将每个个体编码成字符串的形式，根据预定的目标函数对
每个个体进行评价，即给出一个适应度值。开始时，总是随机的产生一些个体，
根据这些个体的适应度利用遗传算子——选择（Selection）、交 叉（ Crossover）、
变异（Mutation）对它们重新组合，得到一群新的个体。这一群新的个体由于
继承了上一代的一些优良特性，明显优于上一代，以逐步向着更优解的方向进
化。遗传算法主要的特点在于：简单、通用、鲁棒性强。经过二十多年的发展，
遗传算法已经在旅行商问题、生产调度、函数优化、机器学习等领域得到成功
的应用。
传统的遗传算法虽然具有隐含的并行性，但其实实现方法在本质上仍然是
串行的。这种串行的遗传算法在解决一些实际问题时，由于需要较多的个体数
量和大量的计算，使得进化过程比较缓慢，难以达到实时的要求。因此并行遗
传算法（Parallel Genetic Alogrithm——PGA）就受到了较大的重视，并且已经
成为目前遗传算法研究的主要课题。遗传算法与并行计算机相结合，能把并行
机的高速性和遗传算法固有的并行性两者的长处彼此结合起来。
尽管遗传算法比其他传统搜索方法有更强的鲁棒性，但它更擅长全局搜索，
而局部搜索能力却不足。有研究证明，GA 可以用极快的速度达到最优解的 90%
左右，但要达到真正的最优解则要花费相当长的时间。实验表明，如果兼顾收
敛速度和解的质量两个指标，单纯的遗传算法未必能比其他搜索算法快很多。
目前较为活跃的研究领域是将遗传算法于传统的、基于问题知识的启发式搜索
i
剩余61页未读，继续阅读
评论1