组合优化算法中摆脱局部极小值的几种策略

A Number of Strategies of Escaping Local Minima in Algorithm of Solving Combinatrorial Optimization Problems

局部搜索算法是一种非常有效的求解组合优化问题的算法 ,它具有通用、灵活等特点 .但是 ,由于搜索空间和目标函数的复杂性 ,目标函数在搜索空间中有许多局部极小值点 ,使算法在这些局部极小值点处被“卡住”,大大影响算法的效果 .对于此问题 ,笔者查阅了大量文献资料 ,结合自己的研究实践 ,总结出几种跳出局部极小“陷井”的策略 .使用这些策略 ,有望使算法更加完善 ,在求解组合优化问题过程中更能发挥其作用 .

Local Search algorithm is a very effective way of solving combinatrorial optimization problems. It is characterized in common use and flexibility. However, there are many local minima for the object function in search space because of the complexity of the search space and object function, which “blocks” the algorithm in the area of the local minima. Therefore, it affects the algorithm result. The auther of the paper summarized several strategies to escape local minina by reading much literature to this problem and combine it with the research practice. By applying these strategies, algorithm is expected to be improved and its function to be played fully in solving combinatrorial optimization problems.