遗传算法是模拟自然界生物进化理论—适者生存,优胜劣汰的遗传机制而得到的一种随机搜索算法,也属于启发式算法。自90年代,遗传算法得到广泛发展和应用,目前已广泛应用于组合优化、信号处理、机器学习、自适应控制和人工生命等众多领域。算法本身也具有很强的可塑性,近年来多被人们与其它算法如模拟退火算法,最小冲突算法,贪心算法等结合运用。本文主要讲述了遗传算法在PPI网络中蛋白质的挖掘,N-queens问题和最短路径问题的应用及算法改进。首先不同于其它基于节点的聚类方法,本文提出一种基于链接聚类(边聚类)的启发式算法—遗传算法GA(Genetic Algorithm)。因为链接(边)通常代表节点之间的独特关系,利用链接聚类便会发现具有相同特征的链接群体。实验中,使用酵母蛋白质数据DIP,通过编码获得个体,再评价个体,中间经过种群的迭代选择,最终选出最优个体,并通过解码获得蛋白质复合物预测集。将所获的预测集与两个标准复合物数据集进行匹配计算,并与其它两种具有代表性的算法进行性能分析比较。实验结果表明该算法能够识别出标准复合物数据集中更多的已知蛋白质,在计算召回率,调和平均数方面性能较好。其次是N-queens问题研究,针对遗传算法的搜索效率会随着状态空间的指数增大而降低这一弱点,提出了贪心算法初始化种群,并在遗传算法的交叉突变操作后添加最小冲突算法,从而保证子代效果的良好性,提高整体算法效率。最后是最短路径问题,以多个旅行商并行问题为测试实验,提出了基于粗粒度和细粒度的混合并行遗传算法,并证明了该混合并行算法在寻找正确最小路径以及时间效率方面比单个的粗粒度并行或细粒度并行遗传算法效果好。