基于Backbone的极值进化算法

Backbone based extremal evolutionary optimization

由于变量的适应度最优与问题的目标函数最优无法达到一致,从而利用极值过程原则的局部搜索算法对TSP问题效果不好,而通过改变变量的适应度,使其与目标函数相关,就能够提高个体解的搜索能力。比较参数取不同值时个体解搜索到的目标函数,可以发现存在使个体解搜索性能最佳的参数取值,且与变量的变异方式无关,这就为参数设置提供了依据。但个体解接近最优解后改善缓慢,无法快速到达最优解,为此引入组合优化问题解的Backbone概念,在种群进入最优解域后固定解中的相同部分,从而保留解中包含的最优解的信息,在减小问题规模后继续进行优化,增强搜索能力,提高搜索性能。

Because of the inconsistence between optimal fitness of variables and optimal objective,local searching algorithm using extremal process rules is ineffective for Traveling Salesman Problem（ TSP ）.We change the definition of variables and make them related with the objective function,whlch enhances the searching capability of an individual solution.Through comparison of objectives with different parameter values of r,we found that there is the optimal value of r to get the best searching performance. This result provides rules for parameter setting and it is independent of mutation ways of variables.However,when an individual solution gets near to sub-optlma,the improvement of objective function is very slow and the solution cannot arrive at the optimum quickly.So we introduce the concept of backbone of combinatorial optimization solutions.While the colony comes in.to the optimal space engine,we fix the same parts in the solutions to reserve the best solution,and reduce the scale of real problem to solve to continue the optimization,which enhances the searching capability, and improve the searching performance.