2018 Computational Intelligence Homework No.4
#多尺度协同变异的粒子群优化算法
#问题描述
实现文《一种多尺度协同变异的粒子群优化算法》[1]的测试实验。
#算法设计
粒子群算法(Particle Swarm Optimizer，PSO)是由Kennedy和Eberhart博士提出的一种基于群体智能的优化算法, 其基本思想是受到他们早期对许多鸟类的群体行为进行建模与仿真研究的启发. 粒子群算法的优势在于其简单容易实现,没有很多参数需要调整,是非线性连续优化问题、组合优化问题和混合整数非线性优化问题的有效优化工具. 由于PSO算法概念简单、实现容易，在函数优化和神经网络权值训练等方面都有很好的表现. 由于其又具有深刻的智能背景，既适合科学研究，又特别适于工程应用, 因此在近年来得到了飞速的发展. 其应用涉及系统控制、人工智能、模式识别、计算机、通信工程等各个领域. 粒子群优化算法问世以来受到了广泛的重视, 经过十几年的研究, 其不论在应用方面还是在优化性能方面都得到了很大的发展. 然而, 研究人员仍然无法解决一直困扰该算法的两个难题: 早熟和收敛速度慢.
文中提出一种多尺度协同变异的微粒群算法(MAEPSO). 该算法利用不同大小方差的高斯变异机制实现解空间的探索, 这种多个或大或小的变异机制, 能促使整个种群以尽量分散的变异尺度来对解空间进行更加详尽的探索. 同时高斯变异的范围随着适应值的变小也逐渐降低, 在算法后期有利于提高最优解的精度; 在利用不同大小变异算子提高局部精确搜索能力的同时, 该算法同样利用均匀算子维护种群多样性. 利用试验对不同评测函数进行测试均验证新算法优良的优化性能.
#速度更新
速度更新的公式为:
$$ v_{id}(t+1)=w×v_{id}(t) + c_1×r_1×(p_{id}(t)−x_{id}(t)) \\ \ + c_2×r_2×(p_{gd}(t)−x_{id}(t)) \tag{1} $$#位置更新
位置更新的公式为:
$$ x_{id}(t+1) = x_{id}(t) + v_{id}(t+1) \tag{2} $$#多尺度高斯变异算子
设尺度个数为$M$, 首先初始化多尺度高斯变异算子的初始方差
$$ \sigma^{(0)} = (\sigma_1^{(0)},\sigma_2^{(0)},\cdots,\sigma_M^{(0)}) \tag{3} $$初始时, 方差一般设定为优化变量的取值范围, 随着迭代次数的增加, 多尺度高斯变异算子的方差会随之进行调整, 具体调整方式如下所示, 首先根据适应值的大小对种群中的微粒进行由小到大排序, 然后对其进行组合, 生成$M$个子群, 每一个子群的微粒个数为$P = N / M $, $K$是当前迭代次数, 计算每一个子群的适应度:
$$ FitX_m^{(K)} = \sum_{i=1}^Pf(x_i^m) / P,m = 1,2,\cdots,M \tag{4} $$其中$f$是微粒的适应值计算函数, 不同变异尺度之间相互竞争, 根据适应能力的不同而设置不同的变异能力, 因此第$m$个变异算子的标准差为:
$$ \sigma_m^{(K)} = \sigma_m^{(K-1)} exp(\frac{M\cdot FitX_m^{(K)} - \sum_{m=1}^MFitX_m^{(K)}}{FitX_{max} - FitX_{min}}) \tag{5} $$ $$ FitX_{max} = max(FitX_1^{(K)},FitX_2^{(K)},\cdots,FitX_M^{(K)}) \tag{6} $$ $$ FitX_{min} = min(FitX_1^{(K)},FitX_2^{(K)},\cdots,FitX_M^{(K)}) \tag{7} $$由于变异算子的进化是一个递归过程, 排在后面的变异算子可能很大, 因此对变异算子的标准差做如下规范: 如果$\sigma_i^{(k)} >W/4$, 则
$$ \sigma_i^{(k)} = \vert W/4 - \sigma_i^{(k)} \vert \tag{8} $$$W$为待优化变量空间的宽度, 重复使用上式, 直到满足$\sigma_i^{(k)} < W/4$. 为了能最大范围的实现空间勘探$i$能力, 在进行完多尺度高斯变异后, 同时进行一次均匀变异操作, 比较后取所有变异后适应值最好的位置作为新的逃逸点, 均匀变异算子实现同式(9).通过多尺度变异算子能实现整个搜索空间的覆盖, 其中大尺度有利于实现解空间的粗搜索, 可以快速定位到最优解区域, 小尺度能在进化后期实现局部精确解的搜索.
#程序流程
程序流程如图1所示
图1 程序流程图
#代码运行及测试
代码运行结果如表1所示.
| function | min | max | mean | derivation |
|---|---|---|---|---|
| Tablet | 1.7048e-25 | 1.8725e-13 | 2.4511e-14 | 3.3659e-27 |
| Quadric | 4.6845e-24 | 2.1658e-13 | 1.5153e-14 | 2.4005e-27 |
| Rosenbrock | 24.6117 | 35.1629 | 27.9979 | 13.0007 |
| Griewank | 0 | 9.7511e-13 | 1.1072e-13 | 9.2515e-26 |
| Rastrigin | 0 | 0.9950 | 0.0995 | 0.0990 |
| Schaffer | 0.0797 | 0.3685 | 0.1838 | 0.0099 |
#结论
论文提出一种新的多尺度协同变异的微粒群算法, 利用不同大小初始方差的高斯变异机制实现解空间的探索, 这种多个或大或小的变异机制, 能促使整个种群以尽量分散的变异尺度来对解空间进行更加详尽的探索. 同时高斯变异的范围随着适应值的变小也逐渐降低, 有利于提高最优解的精度; 在利用不同大小变异算子提高局部精确搜索能力的同时, 该算法同样利用均匀变异算子维护种群多样性. 通过6个benchmark 数据进行测试, 实验结果表明新算法能够在算法初期就能够快速定位到搜索空间的最优解区域, 进而使得微粒通过进化PSO及小尺度变异算子向着最优精确解空间逼近, 使其在进化过程中保持局部最优解空间开采的能力, 加快了算法的收敛速度.