天辰平台注册登录导航站
 
 

七种启发式算法

浏览:次    发布日期:2024-09-09

老师推荐的一篇知乎北大大神非常好的文章:

主要介绍的是scikit-opt

https://github.com/guofei9987/scikit-opt

主要计算:一个封装了7种启发式算法的 Python 代码库:(差分进化算法、遗传算法、粒子群算法、模拟退火算法、蚁群算法、鱼群算法、免疫优化算法)

安装:pip install scikit-opt

Step1:定义你的问题,这个demo定义了有约束优化问题

 

Step2: 做差分进化算法

 
 

第一步:定义你的问题

 

第二步:运行遗传算法

 

*第三步**:用 matplotlib 画出结果

 

2.2 遗传算法用于旅行商问题

?针对TSP问题重载了?、?两个算子

第一步,定义问题。
这里作为demo,随机生成距离矩阵. 实战中从真实数据源中读取。

-> Demo code:?examples/demo_ga_tsp.py#s1

 

第二步,调用遗传算法进行求解
-> Demo code:?examples/demo_ga_tsp.py#s2

 

第三步,画出结果:
-> Demo code:?examples/demo_ga_tsp.py#s3

 

(PSO, Particle swarm optimization)

3.1 粒子群算法

第一步,定义问题
-> Demo code:?examples/demo_pso.py#s1

 

第二步,做粒子群算法
-> Demo code:?examples/demo_pso.py#s2

 

第三步,画出结果
-> Demo code:?examples/demo_pso.py#s3

 

3.2 带非线性约束的粒子群算法

3.2 PSO with nonlinear constraint

加入你的非线性约束是个圆内的面积?
这样写代码:

 

可以有多个非线性约束,向加就行了。

(SA, Simulated Annealing)

4.1 模拟退火算法用于多元函数优化

第一步:定义问题
-> Demo code:?examples/demo_sa.py#s1

 

第二步,运行模拟退火算法
-> Demo code:?examples/demo_sa.py#s2

 

第三步,画出结果 -> Demo code:?examples/demo_sa.py#s3

 

另外,scikit-opt 还提供了三种模拟退火流派: Fast, Boltzmann, Cauchy. 更多参见?more sa

4.2 模拟退火算法解决TSP问题(旅行商问题)

第一步,定义问题。(我猜你已经无聊了,所以不黏贴这一步了)

第二步,调用模拟退火算法
-> Demo code:?examples/demo_sa_tsp.py#s2

 

第三步,画出结果 -> Demo code:?examples/demo_sa_tsp.py#s3

 

咱还有个动画

蚁群算法(ACA, Ant Colony Algorithm)解决TSP问题

-> Demo code:?examples/demo_aca_tsp.py#s2

 

(immune algorithm, IA) -> Demo code:?examples/demo_ia.py#s2

 

人工鱼群算法(artificial fish swarm algorithm, AFSA)

-> Demo code:?examples/demo_afsa.py#s1

 
 
 

举例来说,你想出一种新的“选择算子”,如下 -> Demo code:

examples/demo_ga_udf.py#s1?github.com/guofei9987/scikit-opt/blob/master/examples/demo_ga_udf.py#L1

 

导入包,并且创建遗传算法实例

 

把你的算子注册到你创建好的遗传算法实例上

 

scikit-opt 也提供了十几个算子供你调用

 

做遗传算法运算

 

现在udf支持遗传算法的这几个算子:,,,

提供一个面向对象风格的自定义算子的方法,供进阶用户使用:

 
 

例如,先跑10代,然后在此基础上再跑20代,可以这么写:

 
 
  • 矢量化计算:vectorization
  • 多线程计算:multithreading,适用于 IO 密集型目标函数
  • 多进程计算:multiprocessing,适用于 CPU 密集型目标函数
  • 缓存化计算:cached,适用于目标函数的每次输入有大量重复

see

https://github.com/guofei9987/scikit-opt/blob/master/examples/example_function_modes.py?github.com/guofei9987/scikit-opt/blob/master/examples/example_function_modes.py

GPU加速功能还比较简单,将会在 1.0.0 版本大大完善。
有个 demo 已经可以在现版本运行了:

https://github.com/guofei9987/scikit-opt/blob/master/examples/demo_ga_gpu.py?github.com/guofei9987/scikit-opt/blob/master/examples/demo_ga_gpu.py

可以使用类似?,查看详细介绍,例如:

 

GA

GA_TSP

PSO

DE

SA

ACA_TSP

IA_TSP

AFSA

GA&GA_TSP

  • ?每一代的最优函数值
  • ?每一代的最优函数值对应的输入值
  • ?每一代的每个个体的适应度
  • ?每一代每个个体的函数值
  • ?最优函数值
  • ?最优函数值对应的输入值

DE

  • ?每一代的最优函数值
  • ?每一代的最优函数值对应的输入值
  • ?每一代每个个体的函数值
  • ?最优函数值
  • ?最优函数值对应的输入值

PSO

  • ?每一代的粒子位置、粒子速度、对应的函数值。?才开启记录
  • ?历史最优函数值
  • ?最优函数值 (迭代中使用的是?,?)
  • ?最优函数值对应的输入值

SA

  • ?每一代的最优函数值
  • ?每一代的最优函数值对应的输入值
  • ?最优函数值
  • ?最优函数值对应的输入值

ACA

  • ?每一代的最优函数值
  • ?每一代的最优函数值对应的输入值
  • ?最优函数值
  • ?最优函数值对应的输入值

AFSA

  • ?最优函数值
  • ?最优函数值对应的输入值

IA

  • ?每一代的最优函数值
  • ?每一代的最优函数值对应的输入值
  • ?每一代的每个个体的适应度
  • ?每一代每个个体的函数值
  • ?最优函数值
  • ?最优函数值对应的输入值

平台注册入口