求解旅行商问题的萤火虫遗传算法

Firefly genetic algorithm for traveling salesman problem

为改善基本遗传算法陷入局部最优的问题,提出一种改进的遗传算法,即萤火虫遗传算法。根据萤火虫算法能够自动划分成子组的优点,将萤火虫个体引入遗传算法的变异算子,即萤火虫变异;为防止萤火虫难以跳出局部极值的缺陷,引入变邻域扰动机制,提出萤火虫遗传算法。运用旅行商问题对改进遗传算法进行计算机测试仿真,仿真结果表明,改进遗传算法在求解精度和收敛速度上优于基本遗传算法。

Aiming at the problem of local optimization of basic genetic algorithm,an improved genetic algorithm-firefly genetic algorithm was proposed. According to the advantage of firefly algorithm that subgroup can be automatically divided,the firefly individual was introduced into the mutation operator of the genetic algorithm,namely,the firefly mutation. To prevent the fireflies from jumping out of the local optimal,the variable neighborhood perturbation mechanism was introduced and the firefly genetic algorithm was proposed. The improved genetic algorithm was simulated by computer solving using traveling salesman problem. The results show that the improved genetic algorithm is better than the basic genetic algorithm in solving precision and convergence speed.