Abstract: The Backtracking Search Optimization Algorithm（BSA） is an evolution algorithm based on population. The algorithm has good global search ability. However, it has the shortcoming of low convergence speed. Aiming at the shortcoming, an improved backtracking search optimization algorithm with self-adaptable mutation scale factor and hybrid selection strategy is proposed. The modified mutation scale factor, which may self-adaptable decrease in overall trend, is based on the Metropolis criterion. The modified selection strategy is a hybrid between the whole [q]% priority selection method and tournament selection method. In the selection process, a certain percentage of outstanding individuals are given priority to enter the next generation, and the rest individuals are counterpointed to select the individuals with higher fitness. The simulation experiments on 5 complex constrained optimization problems are performed by the improved algorithm. The experimental results are compared with those of original algorithm and other similar algorithms. Statistical results show that the improved algorithm has effectiveness and competitiveness.

Key words: backtracking search optimization algorithm, constrained optimization problems, mutation scale factor, selection strategy, Metropolis criterion

摘要： 回溯搜索算法（Backtracking Search Optimization Algorithm，BSA）是一种基于种群的进化算法。该算法有良好的全局搜索性能，但存在收敛速度慢的缺点。针对这一缺点，提出了自适应变异尺度系数和混合选择的改进的回溯搜索算法。改进的变异尺度系数是基于Metropolis准则提出的，它的总体趋势自适应减小。改进的选择策略是整体[q]%择优法与锦标赛选择法的混合选择机制，在选择过程中使一定比例的优秀个体优先进入下一代，剩余个体对位选取适应度较高的个体。对5个复杂的约束优化问题进行仿真实验，得到的实验结果分别与原算法和众多同类算法进行了比较，实验结果表明了改进算法的有效性和良好竞争力。

关键词: 回溯搜索算法, 约束优化问题, 变异尺度系数, 选择策略, Metropolis准则