尽管遗传算法良好的性能使其在许多领域得到了广泛应用,但遗传算法在理论和应用两方面都还有许多不足和不完善。本文针对遗传算法的欺骗问题和基于遗传算法的图论规划求解问题进行了研究。对于遗传算法的欺骗问题,本文首先分析了遗传算法欺骗问题多项式度量的理论基础,给出了计算优化函数欺骗度的快速判定定理,接着证明了线性尺度变换不影响优化函数的欺骗度,证明了不相关子函数的和的欺骗度等于其子函数欺骗度的最大值,最后提出了快速计算单项式欺骗度的算法,提出了求单最优值函数欺骗度的快速算法,并分析了其相应的复杂度。对于遗传算法在图论规划模型的应用问题,本文首先说明了遗传算法在求解图论规划模型中的应用优势,提出了基于遗传算法的图论规划模型的一般求解思路,接着针对带权二部图规划模型和无权二部图规划模型:DVD在线租赁问题和学生面试问题,分别设计了基于遗传算法的求解算法,最后通过与其它求解方法的实验比较,验证了遗传算法求解图论规划问题的可行性和有效性。