【scikit-opt】七大启发式算法的使用

天涯怪客

@
目录

• 前言
  
• 1.测试函数
  
  
  
  • 1.1 针状函数
    
    
    
    • 1.1.1 表达式
      
    • 1.1.2 特征
      
    • 1.1.3 图像
      
    
    
  • 1.2 Brains’s rcos函数
    
    
    
    • 1.2.1 表达式
      
    • 1.2.2 特征
      
    • 1.2.3 图像
      
    
    
  • 1.3 Griewank函数
    
    
    
    • 1.3.1 表达式
      
    • 1.3.2 特征
      
    • 1.3.3 图像
      
    
    
  • 1.4 Easom’s函数
    
    
    
    • 1.4.1 表达式
      
    • 1.4.2 特征
      
    • 1.4.3 图像
      
    
    
  • 1.5 Schwefel’s函数
    
    
    
    • 1.5.1 表达式
      
    • 1.5.2 特征
      
    • 1.5.3 图像
      
    
    
  
  
• 2. PSO(Particle swarm optimization)
  
  
  
  • 2.1 解决的问题
    
  • 2.2 API
    
  • 2.3 参数
    
  • 2.4 示例
    
    
    
    • 2.4.1 不带约束条件
      
    • 2.4.2 带约束条件
      
    
    
  
  
• 3.Genetic Algorithm(recommended)
  
  
  
  • 3.1 解决的问题
    
  • 3.2 API
    
    
    
    • 3.2.1 Genetic Algorithm
      
    • 3.2.2 Genetic Algorithm for TSP(Travelling Salesman Problem)
      
    
    
  • 3.3 TSP的目标函数定义的示例
    
  • 3.4 示例
    
    
    
    • 3.5.1 目标函数优化
      
    • 3.5.2 TSP
      
    
    
  
  
• 4.Differential Evolution
  
  
  
  • 4.1 解决的问题
    
  • 4.2 API
    
  • 4.3 参数
    
  • 4.4 示例
    
  
  
• 特别篇：GA与DE的区别
  
• 5.SA(Simulated Annealing)
  
  
  
  • 5.1 解决的问题
    
  • 5.2 API
    
    
    
    • 5.2.1 Simulated Annealing
      
    • 5.2.2 SA for TSP
      
    
    
  • 5.3 示例
    
    
    
    • 5.3.1 目标函数优化
      
    • 5.3.2 TSP
      
    
    
  • 5.4 bug
    
  
  
• 6.ACA (Ant Colony Algorithm) for tsp
  
  
  
  • 6.1 解决的问题
    
  • 6.2 API
    
  • 6.3 参数
    
  • 6.4 示例
    
  
  
• 7.immune algorithm (IA)
  
  
  
  • 7.1 解决的问题
    
  • 7.2 API
    
  • 7.3 参数
    
  • 7.4 示例
    
  
  
• 8.Artificial Fish Swarm Algorithm (AFSA)
  
  
  
  • 8.1 解决的问题
    
  • 8.2 API
    
  • 8.3 参数
    
  • 8.4 示例
    
  
  

前言

本文着力于介绍scikit-opt工具包中七大启发式算法的API调用方法，关于具体的数学原理和推导过程，本文不再介绍，请读者自行查询相关文献。
1.测试函数

为了检验这些启发式算法的效果，本文使用了以下五种专门用于测试的函数。
1.1 针状函数

1.1.1 表达式

$$
f(r)=\frac{\sin(r)}{r}+1,r=\sqrt{(x-50){2}+(y-50){2}}+e
$$
$$
0\le x,y\le100
$$
1.1.2 特征

该函数是一个多峰函数，在(50,50)处取得全局最大值1.1512，第二最大值在其全局最大值附近，采用一般的优化方法很容易陷入局部极大值点。
1.1.3 图像

1.2 Brains’s rcos函数

1.2.1 表达式

$$
f(x_{1},x_{2})=a(x_{2}-bx_{1}{2}+cx_{1}-d)+e(1-f)\cos (x_{1})+e
$$
$$
a=1,b=\frac{5.1}{4\pi ^{2}},c=\frac{5}{\pi },d=6,e=10,f=\frac{1}{8 \pi }
$$
1.2.2 特征

有3个全局最小值：0.397887，分别位于 (-pi, 12.275), (pi,  2.275), (9.42478, 2.475)。
还有一个局部最小值为：0.8447
1.2.3 图像

1.3 Griewank函数

1.3.1 表达式

$$
f(x)=\sum_{i=1}{N}\frac{x_{i}{2}}{4000}-\prod_{i=1}^{N}\cos (\frac{x_{i}}{\sqrt[]{i}})+1
$$
$$
-600\le x_{i} \le 600,i=1,2,...,N
$$
1.3.2 特征

在(0,0,…,0)处取得全局极小值0
1.3.3 图像

1.4 Easom’s函数

1.4.1 表达式

$$
f(x,y)=-\cos (x) \cos (y)\exp (-(x-\pi)^{2}-(y- \pi)^{2})
$$
$$
-100 \le x,y \le 100
$$
1.4.2 特征

在(pi,pi)处取得全局最小值-1。
1.4.3 图像

1.5 Schwefel’s函数

1.5.1 表达式

$$
f(x)=\sum_{i=1}^{N}-x_{i}\sin (\sqrt{\left | x_{i} \right | }  )
$$
$$
-500 \le x_{i} \le 500,i=1,2,...,N
$$
1.5.2 特征

$$
x_{i}=420.9687时有一个全局最小值-n\times 418.9839
$$
1.5.3 图像

2. PSO(Particle swarm optimization)

2.1 解决的问题

• 目标函数优化
  

2.2 API

1. class PSO(SkoBase):
2.     def __init__(self, func, n_dim=None, pop=40, max_iter=150, lb=-1e5, ub=1e5, w=0.8, c1=0.5, c2=0.5,
3.                  constraint_eq=tuple(), constraint_ueq=tuple(), verbose=False
4.                  , dim=None):...

复制代码

2.3 参数

参数含义func欲优化的目标函数n_dim所给函数的参数个数pop粒子群规模max_iter最大迭代次数lb(lower bound)函数参数的下限ub(upper bound)函数参数的上限w惯性因子c1个体学习因子c2社会学习因子constraint_eq等式约束条件，适用于非线性约束constraint_ueq不等式约束条件，适用于非线性约束参数详解：

• 定义目标函数func时，参数有且只有一个
  
• 惯性权重w描述粒子上一代速度对当前代速度的影响。w 值较大，全局寻优能力强，局部寻优能力弱；反之，则局部寻优能力强。 当问题空间较大时，为了在搜索速度和搜索精度之间达到平衡，通常做法是使算法在前期有较高的全局搜索能力以得到合适的种子，而在后期有较高的局部搜索能力以提高收敛精度。所以w不宜为一个固定的常数。
  
• 个体学习因子c1 =0称为无私型粒子群算法，即“只有社会，没有自我”，会迅速丧失群体多样性，容易陷入局部最优解而无法跳出；社会学习因子c2=0称为自我认识型粒子群算法，即“只有自我，没有社会”，完全没有信息的社会共享，导致算法收敛速度缓慢； c1，c2都不为0，称为完全型粒子群算法，完全型粒子群算法更容易保持收敛速度和搜索效果的均衡，是较好的选择。通常设置c1=c2=2，但不一定必须等于2，通常c1=c2∈[0,4]。
  
• 群体大小pop是一个整数，pop很小时陷入局部最优解的可能性很大；pop很大时PSO的优化能力很好, 但是当群体数目增长至一定水平时，再增长将不再有显著作用，而且数目越大计算量也越大。群体规模pop一般取20～40，对较难或特定类别的问题 可以取到100～200。
  
• 定义约束条件时，需要用元组，元组中用匿名函数
  

2.4 示例

2.4.1 不带约束条件

[code]# 导入必要的库，定义函数import sko.PSO as PSOimport numpy as npimport matplotlib.pyplot as pltdef Schwefel(x):    '''    Schwefel's 函数，自变量为一个n维向量    该向量的每一个分量 -500