图论和优化中的许多问题是NP-完全问题，也是科学和工程计算中重要和基本的问题。将遗传算法与启发式算法、邻近搜索方法结合解决这类问题，是遗传算法的主要研究领域之一。本文对遗传算法的基本理论进行了较深入研究，同时对图论和优化中的问题进行了相应的研究，提出了一些较为有效的混合遗传算法，并通过实验进行了仿真。针对分组问题的特性，从问题的编码、遗传算子的作用和模式三方面分析了标准GA解决分组问题所产生的弊端，提出了装箱和着色问题的分组遗传算法。具体内容如下： ●分析了遗传算法群体的概率密度序列的演化过程，以较简洁的方式给出了连续空间中群体概率密度演变公式的证明，导出了选择和变异条件下平均适应度单调递增并收敛到全局最优解的一个充分条件。分析了标准遗传算法中选择算子和变异算子的基本性质和作用。它对于加快收敛速度、确保群体不至于陷入局部极值具有重要意义。提出了离散空间中群体的演变过程收敛到全局最优状态的一个充分条件，从而得到了对遗传算法的实现具有一定指导意义的结果。这些结论在一定程度上为实现自适应调节变异算子的概率，保证遗传算法收敛到全局最优解提供了理论依据。 ●提出了图的顶点覆盖问题的混合遗传算法。设计了针对问题的扫描-修正算法和局部改进的策略，将遗传算法与邻近搜索方法有机地结合起来。在混合遗传算法中，将修正方法和局部优化技术应用于新产生的子代，产生局部最优解。而遗传算法用于进行全局搜索，从而有效地搜索解空间。实验结果表明，所设计的混合遗传算法可以在适中的时间内找到一类特定问题的最优解。对于一般问题，也优于标准遗传算法和经典的算法。因此所设计的算法可以得到问题高质量的解，表明了算法的有效性。 ●提出了求解0/1背包问题的遗传算法，是对经典算法的补充和扩充，实验表明，所提出的算法具有一定的有效性，适合于规模较大问题的求解，为用遗传算法解决复杂的NP-完全问题提供了多项选择。 ●在系统分析了图的正常顶点着色、边着色以及全着色问题的基础上，将启发式方法与遗传算法结合，提出了图的着色的混合遗传算法。在混合方法中，启发式贪婪算法用于尽可能的查找局部最优解，而遗传算法用于进行全局搜索。并与启发式算法和基于Tabu查找的遗传算法进行了比较。结果表明，基于启发式算法的混合遗传算法优于基于度序列的启发式算法。基于启发式算法的混合遗传算法可以在适中的时间n 西安电于科技大学博士学位论文内找到一类规则问题的最优解．对于随机图的顶点着色问题的求解，也优于启发式和基于Tabu查找的遗传算法．这表明文中设计的混合遗传算法的合理性和有效性． ·提出了解地 七hop问题的遗传算法，基于2－机问题，将仿真结果与JOhnson规则进行了比较，在同样是最优解的情况下，遗传算法得到问题的多个最优解．基于个机问题与启发式搜索算法进行了比较．结果表明所提出的遗传算法胜过各种启发式的搜索算法． ·针对分组问题的特性，从问题的编码、遗传算子的作用和模式三方面分析了标准GA解诀分组问题所产生的弊端．在交叉算子作用下，这种编码的方法常常导致结果与上下文无关．对于任一种将目标映射到基因的编码，这蕴含着一个好的模式是长的（组数减少）模式．然而，在标准的交叉算子作用下，模式被破坏的概率随着它的定义距的增长而增大．即，当经典的交叉算子一旦找到一个好的候选解时，在遗传搜索的一开始就可能收敛到一个较好的解，而不会改进这个解．最终导致其朝着破坏好的模式，阻碍自己进化的方向发展．此外，经典的GA编码的每一位上包含着分组的内容和位置，而GGA只对分组内容编码．对于规模为n的问题，GA的搜索空间为2”1，这样的搜索空问远远大于 GGA的搜索空间．我们设计了几种针对分组问题o着色问题和装箱问题）的遗传算子，所设计的遗传算子需要处理变长的染色体，并且直接作用在分组上．因此，变长的染色体编码，遗传算子作用的目标和遗传算子的设计正是GGA与标准GA的不同之处．