混沌遗传算法优化公路运输路径

Optimizing Highway Transportation Path by Chaos Genetic Algorithm

公路运输路径问题已被证明是高维非线性完全问题,实际中还会增加非流通图约束,使求解更复杂,研究价值较高.鉴于传统遗传算法在求解过程中容易出现早熟收敛、冗余迭代的缺陷,在初始种群生成、交叉变异及搜索操作方面提出改进,设计混沌遗传算法.采用遍历城市顺序的染色体编码,结合随机法与贪心法生成较优初始种群,避免出现大量非可行染色体,提高了后续的遗传效率.接着,执行优先保留交叉和平移变异操作,依次引入局部邻域搜索以及混沌搜索以加快算法收敛,还给出最优解的非连通公路约束满足判据.最后,实验结果验证了新算法的有效性,不但取得了较优解,而且子代种群离散程度较小,收敛性更好.

Highway transportation path problem has been proven to be a non-deterministic polynomial complete problem with high research value. It involves some unconnected graph constraints that make the solving process become more complex. In view of the defects of premature convergence and slow convergence of the traditional genetic algorithm, this paper makes the generation of initial population, crossover, mutation and search operation to design a chaos genetic algorithm. The algorithm adopts the chromosome encoding scheme based on sequence of city that highway vehicle passed through. It combines the stochastic method and greedy method to produce the initial populations in order to contain the optimal value, avoid infeasible chromosomes and improve the subsequently genetic efficiency. Then, precedence preservation crossover and shift change mutation operations are operated. Meanwhile, the local neighborhood search and chaos search are successively introduced to accelerate the convergence. Furthermore, the criterion is given to verify whether the optimal solution meets unconnected graph constraints or not. Finally, the computation results prove the effectiveness of the proposed method. The method can generate the optimal solution with less rangeof offspring population and better convergence