【作者】 张建萍；

【导师】 刘希玉；

【作者基本信息】 山东师范大学 ， 计算机软件与理论， 2007， 硕士

【摘要】 伴随着遗传算法应用的深入开展,由于遗传算法有着其他优化算法不可比拟的优点,因此,遗传算法在优化计算中得到了广泛的应用,将遗传算法用于解决各种实际优化问题后,人们发现遗传算法也会由于各种原因,产生所谓“早熟收敛”问题,从而影响算法向全局最优解的搜索。随着科学技术的不断发展,问题规模的不断扩大,面对复杂程度越来越高的搜索空间,遗传算法在优化效率和求解质量上都显得“过于苍白”。为了加速决策的时效性和准确性,在文中以无源光网络中OBD与OUN位置分配问题为例,在工作站机群上对此算法进行研究。首先,本文研究了根据生物机体免疫系统的抗原识别、保持抗体的多样性和免疫记忆的特性而提出的一种改进遗传算法——免疫遗传算法,该算法将生物系统免疫思想引入到遗传算法中,通过计算抗体之间的亲和度来促进和抑制抗体,既保留了全体中的较优抗体又保证了抗体的多样性,从而避免搜索进化的过早收敛,得到全局最优解。本文通过对改进的免疫遗产算法和传统的遗传算法的产生效果进行比较,证明了IGA的有效性和优越性。其次,本文通过对并行遗传算法的发展和特点进行综述,并介绍并行处理的硬件系统及其并行环境下的支撑软件——工作站机群平台上所采用的高效的编程环境MPI。再次,论文重点分析遗传算法固有的隐式并行性,结合主从并行程序设计特点,提出了工作站机群环境下基于MPI求解最短路径问题的并行遗传算法,加快算法的执行速度和效率。在该算法并行设计中的划分、通讯、组合和映射四个过程,提出遗传算法初始种群的划分原则;利用MPI消息传递的六个基础通信子集在各种群间进行通信和传播各子种群的最优解;运用组合法,以保持灵活性,减少通信开销;将该算法映射为主从式工作站机群上的粗粒度并行遗传算法,并使用静态负载平衡任务调度技术改善映射质量。最后,利用MPICH进行仿真试验。作者通过配置工作站机群并行环境,在Windows和MPI平台上使用Visual C++6.0编程实现该并行算法,通过分析对比多组实验数据,计算该算法加速比性能,结果表明:算法适应度高,寻优速度快。但是该并行算法求解问题规模较小、遗传参数设置和消息传递内容与时机固定,这些都有待进一步完善。更多还原

【Abstract】 Along with the in-depth application of genetic algorithms, and as any of the genetic algorithm optimization algorithm has other advantages, therefore, Genetic Algorithm for the Optimization Calculation of a wide range of applications.but people have found that for a variety of problems the genetic algorithm will create "premature convergence" or weak ability of local search,which affects the algorithm to overall search for the optimal solution. With the continuous development of science and technology, the continued expansion of the scale of the problem, and facing increasing complexity of the search space, genetic algorithms for optimizing the efficiency and quality have become "too pale"! To speed up the timeliness and accuracy of decision-making,we can research and test GAs as the example as the the distribution location of OBD and OUN of Passive Optical Network on Cluster Of Workstations(COW) in this paper.Firstly,based on the mechanism of such features as antigen recognition,variability of antibody and immune memory in immune systems,a new improved GA,namely,Immune Genetic Algorithm is presented in this thesis.In order to overcome premature convergence and find out optimal solution,the immune mechanism of creature is used in IGA and antibodies will be promoted or restrained according to the computation result of affinity between antibodies,which reserves the excellent antibodies as well as guarantees the variability of antibody.In addition,the IGA’slocal searching ability is improved by combining it with gradient method.The computation results show that both global and local searching abilities of the IGA are improved and premature convergence is overcome availably.The effectiveness and the superiority of IGA is proved by optimization experiments using another optimization algorithm comparisons to.Secondly,this paper summarizes the development and feature of parallel GA.We introduce hardware system and of parallel process and software in the parallel environment—MPI on COW. Thirdly,the point is this:we analyze the inherent potential parallel in Parallel Genetic Algorithm.In terms of master-slave parallel programming design,we put forward a Parallel immune Genetic Algorithm of shortest path based on MPI in COW.So this can avoid the premature convergence problem and enhance the global convergence.In the process of parallel algorithm design including partition,communication,combination and mapping,put forward the partition principle of genetic algorithm used to originate the groups.Finally in the experiment part by MPI, we configure COW parallel environment and in the platform of Windows and MPI,we program the algorithm with Visual C++6.0.The experiment platform and Parallel Genetic Algorithm,and establishes the foundation for Emergency Decision System.By analyzing and comparing to experiment data,we compute the accelerated performance.Results show The algorithm has high fitness and optimized speed.But the size of this parallel algorithm is not enough.Genetic parameter is not allowed to modify,so is the content and time of message passing.What we can do is making it more perfect.更多还原