混合遗传算法及其硬件实现的研究-管理科学与工程专业论文.docx

1{)m’7摘 1{)m’7 摘 要 本文围绕旨在改善标准遗传算法性能的混合遗传算法、混合遗传算法的硬 件实现等相关问题展开研究。 首先，总结了近十几年来遗传算法和混沌现象的起步及发展情况，概括说 明了遗传算法的结构、功能和特征，并分析了混沌的主要特点及现状，针对遗 传算法研究和应用中存在的问题和不足，探讨了几种新的混合遗传算法的体系 和结构。 ， ／在对遗传算法的数学理论基础进行了详细论述和总结的基础上，分析了遗 传算法的遗传机制、收敛性和计算效率。同时概括总结了混沌的形成条件、理 论基础及典型方程。 为解决遗传算法的模式欺骗和多峰问题，在分析了各种解决约束问题的方 法及应用条件后，基于通常的惩罚方法，本文提出了一种惩罚．修补法来应用于 各种约束问题，避免了单纯的惩罚方法使种群数量严重退化及算法要花较长的 时间去评价那些可行解很少的不可行解的现象，同时也很好的处理了最优值位 于可行解边缘的问题。为了使优化过程尽快收敛，本文又引进了免疫的概念， 即用生命科学中的免疫思想有目的性的去指导对遗传算子的修补，并把此方法 应用于电子设计自动化(EDA)应用中所涉及的强约束问题，成功的解决了FPGA 设计中CLB模块的利用率问题并建立了数学优化模型，为遗传算法在大规模集 成电路设计方面的应用开拓了新的领域。 在综合分析了各种主要混合算法的基础上，为解决遗传算法缺乏产生最优 个体的强大能力而陷入局部最优及“爬山”能力弱而收敛慢的通病，首次提出 了一种混沌免疫混合算法，利用混沌在一定的范围内按其“自身的规律”不重 复的遍历所有状态的特性，使遗传算法跳出局部最优：同时也利用了免疫算法 对快速收敛的指导作用来改善遗传算法的特性，建立了数学模型，给出了实现 的方法，并比较了标准遗传算法与混沌免疫算法解决同样问题时的效率。 硬件进化是遗传算法应用的一个重要方面，利用硬件进化的自适应性和容 错性，可使设计出的电路结构自动地适应未知的环境J本文在深入探讨了硬件 进化的机理和FPGA内部结构的基础上，针对目前主要使用GAL器件作为硬 件进化手段的状况，提出了用EDA的思想，建立FPGA硬件进化的数学模型， 件进化手段的状况，提出了用EDA的思想，建立FPGA硬件进化的数学模型， 并重新定义了染色体串，克服了传统的硬件进化性能越好运算量增长越快的弊 端。作为数学模型的验证，用FPGA实现了二进制选择器、二进制带进位位全 加器、全减器及简单表决器的硬件进化逻辑电路，取得了很好的结果。 J f目前，人们在遗传算法方面的研究主要集中在用软件实现的算法上，很少 用硬件研究基因算法，尤其是在混合算法方面，这主要是因为受到硬件复杂程 、 度的限制。作为一种尝试，夕本文还首次提出了一种用硬件实现混沌混合遗传算 法的方案，并设计了具体电路，在兼顾了电路的简易性及易实现性基础上，讨 论了实现电路的各种可能。总体电路分步通过了计算机的仿真。 {最后，对论文的主要研究内容进行了总结，对今后研究前景作了展望0 、 ／’ 关键字： 遗传算法，混沌，FPGA，免疫算法，混沌混合算法，硬件进化 AbstractThis Abstract This thesis deals witll the relevant subjects of improving the function of hybrid genetic algorithms，the standard genetic algorithms and hardware realization ofhybrid genetic algorithms． First，having summarized the original and developing status ofthe genetic algorithms and chaos theory in the last decades；I am intending to explain the structure、function and characteristics of genetic algorithms with analyses ofthe main features as well as the current development of chaos theory．Being aimed at the questions and inadequacy血at exist in the research and application of genetic algorithms．1 want to explore several kinds ofnew systems and structures ofhv蜥d genetic algorithms．