遗传算法(GA)作为一门新兴学科,从二十世纪八十年代开始迅速发展。遗传算法是一种用于解决优化问题的并行寻优算法,已被广泛用于解决各类NP问题。但标准遗传算法仍然存在一些缺陷。为了克服这些缺陷,本文设计了一个全新的混合遗传算法SEGA,这一算法在进化方式上与传统的混合遗传算法明显不同,然后,用马尔可夫链的有关知识对SEGA算法进行数学分析。它综合了遗传算法和邻域搜索算法各自优势的全局搜索算法。它即有遗传算法的全局搜索能力,又有高效的局部搜索能力。该算法较好的解决了两种不同算法结合所产生的矛盾。通过实验表明,该算法具有良好的全局寻优性能。随着问题规模的不断扩大,面对复杂度越来越高的搜索空间,遗传算法在优化效率和求解质量上都显得“力不从心”。为解决大规模复杂优化问题,本文就并行遗传算法的并行化原理和应用平台进行分析,并结合SEGA算法和分布式遗传算法两种思想提出了一种基于网络环境的分布式遗传算法(Extended Network-based Distributed Genetic Algorithm,简称ENDGA)。并着重讨论了ENDGA实现中的关键问题,用马尔可夫链的有关知识对ENDGA算法进行数学分析,并给出了算法的具体程序实现。在本文中,我们实现了一个解决带约束条件的并行多机调度问题的分布式网络PGA。实验表明,ENDGA能显著节约寻优的时间,大大提高寻优的质量,为解决巨量优化问题提供一个可行的解决方法。