2006年计算机组成原理课程设计

《2006年计算机组成原理课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、石家庄经济学院第四届学生科技基金科研项目研究报告项目名称：基于改进遗传算法求解可满足性问题的研究负责人：曹国生所属学院:信息工程学院指导老师：贺毅朝2008年1月20日目录1.选题依据12.国内外研究现状53．个人主要工作64.数据分析85.总结9致谢10参考文献10附录10摘要本文通过介绍遗传算法和可满足性问题的起源、描述、重要理论意义和应用价值，进而提出了一种新的方法来解决可满足性问题，即在将SAT问题等价转换为{0,1}n上的多项式是否存在零点的判断问题基础上，将局部搜索算法(LSA)与SGA相结合，给

2、出一种求解3-SAT问题的改进混合遗传算法(MHGA)，并通过对随机大规模3-SAT问题实例的实际求解验证了MHGA的可行性与有效性。关键词：遗传算法，可满足性问题一.选题依据1.遗传算法及其重要性遗传算法(GeneticAlgorithm，GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法，它起源于对生物系统所进行的计算机模拟研究。早在本世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。如Fra

3、ser的模拟研究，他提出了和现在的遗传算法十分相似的概念和思想。进入60年代以后，美国密执安大学的Holland教授及其学生们受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术---遗传算法。70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。Holland和DeJong的创造性研究成果改变了早期遗传算法研究的无目标性和理论指导的缺乏，其中，Holland于1975年出版的著名著作<<自然系统和人工系统的适配>>系统地阐述

4、了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论。这一理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，DeJong的重要论文<<遗传自适应系统的行为分析>>将Holland的模式理论与他的计算实验结合起来，并提出了诸如代沟等新的遗传操作技术，可以认为，DeJong所做的研究工作是遗传算法发展过程中的一个里程碑。在一系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。80年代以后，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用

5、研究都成了十分热门的课题，遗传算法的应用领域也不断扩大。生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景，遗传算法就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力，它所借鉴的生物学基础就是生物的遗传和进化。达尔文的自然选择学说是一种被人们广泛接受的生物进化学说。这种学说认为，生物要生存下去，就必须进

6、行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟无机环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的。达尔文把这种在生存斗争中适者生存，不适者淘汰的过程叫做自然选择。它表明，遗传和变异是决定生物进化的内在因素。自然界中的多种生物之所以能够适应环境而得以生存进化，是和遗传和变异生命现象分不开的。正是生物的这种遗传特性，使生物界的物种能够保持

7、相对的稳定；而生物的变异特性，使生物个体产生新的性状，以致于形成新的物种，推动了生物的进化和发展。遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。主要是基于达尔文进化论中“物竞天择，适者生存”理论，模拟生物进化的步骤,将繁殖、杂交、变异、竞争和选择等概念引入到算法中，通过对一组可行解的重新组合，改进可行解在多维空间内的移动轨迹或趋向,17最终走向最优解。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术

8、指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。遗传算法求解问题的基本思想是从问题的解