多元优化算法及其收敛性分析

提出了一种搜索个体分工明确、协同合作的群智能优化算法,并从理论上证明了其收敛性. 由于搜索个体(搜索元)具有分工不同的多元化特点,所以我们称该算法为多元优化算法(Multivariant optimization algorithm, MOA).多元优化算法中, 全局搜索元和局部搜索元基于数据表高效的记录和分享信息以协同合作对解空间进行搜索. 在一次迭代中,全局搜索元搜索整个解空间以寻找潜在解区域,然后具有不同种群大小的局部搜索元组对潜力不同的历史潜在解区域以及新发现的潜在解区域进行不同粒度的搜索. 搜索元找到的较优解按照一定的规则保存在由队列和堆栈组成的结构体中以实现历史信息的高效记忆和共享. 结构体中保存的候选解在迭代过程中不断更新逐渐接近最优解,最终找到优化问题的多个全局最优解以及局部次优解.基于马尔科夫过程的理论分析表明:多元优化算法以概率1 收敛于全局最优解.为了评估多元优化算法的收敛性,本文利用多元优化算法以及其他五个常用的优化算法对十三个二维及十维标准测试函数进行了寻优测试. 实验结果表明,多元优化算法在收敛成功率和收敛精度方面优于其他参与比较的算法.

Multivariant Optimization Algorithm and Its Convergence Analysis

In this paper, we present a swarm intelligent algorithm and study its convergence property. We name it as multivariant optimization algorithm (MOA) because its multiple searchers (atoms) are variant in responsibilities. The solution space is searched through global-local search iterations which are based on the collaboration and coordination between the local and global search groups in the MOA. In each iteration, the global atoms explore the whole solution space to locate potential areas and then multiple local groups with different numbers of local search atoms are allotted to these potential areas for different levels of refinements. The historical better solutions are recorded in a structure made up of a queue and some stacks, according to a certain rule. The candidate solutions in the structure are improved iteratively and will converge to the optimal solutions. A theoretical convergence analysis based on Markov process shows that MOA converges to more than one global optimal solutions with probability 1. To evaluate its convergence property, MOA and other five frequently compared algorithms are employed to locate the optimal solutions of thirteen two-dimensional and ten-dimensional benchmark functions. The results show that the MOA has competitive performance to the other algorithms in terms of the convergence success rate and accuracy.