用单亲遗传算法解决影片递送问题

Solving Film Deliver Problem with a Partheno-genetic Algorithm

遗传算法(简称GA)是基于生物进化原理的普适性全局优化算法,是解决NP难问题的一种行之有效的方法.但是,序号编码的遗传算法不能在任意两条染色体的任意位置进行交叉,必须使用PMX,CX和OX等特殊的交叉算子,这些算子实施起来都很麻烦且效率不高.针对这一问题,采用单亲遗传算法,取消交叉操作,强化变异作用.这样既简化了遗传操作,又克服了早熟现象.较成功的解决了影片递送问题,文中的算例表明,该算法是实际有效的.

Based on natural evolution principle,genetic algorithms(GA) are the overall algorithms which are universal applicable.But,genetic algorithms using ordinal strings must use special crossover operators such as PMX,OX and CX,instead of general crossover operators.Considering the above deficiency of GA using ordinal strings,we propose a Partheno-genetic algorithm (PGA) method that uses ordinal strings and repeals crossover operators while introduces some particular genetic operators such as gene exchange operator which have the same function as crossover operators.Therefore genetic operation of PGA is simple and its initial population need not be varied and there is no immature convergence in PGA.Calculated examples show the efficiency of PGA.