论文部分内容阅读
遗传算法(GA)是基于自然选择的一种搜索、优化策略，被广泛应用于各种领域，如搜索、优化、以及机器学习等。它适用于求解著名的TSP问题，调度问题，优化Steiner树，以及建立神经网络的初始节点等。在实际应用中，它已被成功地运用于VLSI电路设计中的门阵列分布设计，标准元放置，以及信号格式图压缩，从更广泛意义上说，它可应用到计算机、工程、经济、政治、心理学、语言学、免疫学、生物学、以及数学等各种领域。它从本质上讲是一种随机策略，由于其通用，简单且有效，以及其潜在并行性，使之越来越引人注目，目前已形成了一个研究GA的高潮。 本文介绍和分析了遗传算法的基本特性及其历史和现状。本文着重围绕如何提高遗传算法性能方面作了大量讨论及研究，并从几个层次入手进行研究。首先，从改进遗传算法本身入手，分析了加入带启发性信息操作的作用及其必要性，并结合3-SAT问题，提出Ncrossover与Nmutation操作，结合TSP问题提出三种适用于有序排列问题的三种新型操作，最后提出一种通用化，带有普遍适用性的平行于杂交和突变的两个新操作VOTE与NVOTE，并结合实例证明其有效性；在总体层次上讨论了将GA与其它局部搜索策略相结合的问题，提出几种新的控制策略。在求解可满足性问题上，与已知的算法Grad-U2([李未1994])相比，算法效率获得数量级的提高，至今在已发表的文献上尚未见到这种求解方法；在求解几个典型TSP问题上，取得了令人满意的解。解100城市TSP问题时，很容易找到最优解，求解318和532城市TSP问题时，在第10代就分别找到了比最优解长不超过5％的近似最优解(3分钟以内)，在第100代就分别找到了比最优解长不超过1％的近似最优解(30分钟以内)，在第1000代分别找到了比最优解长不超过万分之五(0.05％)和千分之六(0.6％)的近似最优解；至今在已发表的文献上尚未见到达到这种精度的结果。最后本文分析了GA的潜在并行性并就并行实现方面提出若干设想。