影片递送问题(简称FDP)是一个典型的NP-Hard组合优化问题。一般很难精确地求出其最优解,因而人们都在寻找快速、有效的近似求解算法。影片递送问题是旅行商问题和多路旅行商问题的扩展,具有重要的理论和实际意义。遗传算法是一种生物自然选择与遗传机理的随机搜索与优化方法,广泛应用于很多领域。 本文针对影片传递问题的特点,设计了一种遗传算法的新的交叉算子,并保证了整个进化过程中所有个体的可行性,以确保运算效率。通过比较和分析得到了一种较满意的改进混合GA方案:μ+λ选择、依概率边重组交叉(依边)、变异和2-opt邻域搜索,能够较快收敛到全局最优解。在此基础上又引入嫁接遗传算法的思想,求解规模较大的FDP问题,能够提高抗早熟能力,进而提高解的精度。具体实例测试表明:改进混合GA及其嫁接遗传算法的有效性和优越性,在解决FDP时新算法有较强的优化求解能力。