用改进遗传算法求解影片投递问题(FDP)

Improved GA Algorithm for Film Delivery Problem

影片投递问题是近十几年来研究相当活跃的旅行商问题(TSP)的拓展,是组合优化的新问题。FDP也是一个NP难问题,且一般比TSP要难解得多。本文采用改良点编码方案,运用惩罚函数、禁止相同基因段交叉和重置变异参数的技术以避免非可行解的干扰,通过测试发现:标准遗传算法的选择机制和FDP问题求解的常用交叉和变异方法,两者之间的简单撮合很难实现求解。经多次试验数据证明,改进后的算法大大提高了全局收敛性性能。

Film Delivery Problem, a new problem of optimization grouping, is the extension of the Traveling Salesman Problem(TSP) on which has been done research for over ten years. FDP is also a NP difficult problem,and generally speaking, is harder to solve than TSP. Making use of the system of improving dot coding and punishment function, the thesis attempts to limit the intersection of the same genes and to replace the variation parameter in order to avoid the interference of the unfeasible solution. Through testing, it can be found that the alternative system of the standard genetic algorithm and the intersection and variation used by FDP cannot mix to get a solution. Based on the numerous testing, it can be concluded that the improvement of algorithm prompts the function to run well in the aspect of general astringent.