type
status
date
slug
summary
tags
category
icon
password
Property
目标函数加速
为了提升速度，scikit-opt 支持3种提升速度的方案：矢量化，并行化，缓存化
- 矢量化：要求目标函数本身支持矢量化运算（详见代码）。矢量化运算拥有极高的性能，通常比并行化运算要快。算法中，每代对应1次矢量化运算
- 多线程：对目标函数没什么要求，通常比一般运算要快。如果目标函数是 IO 密集型，能达到更优的性能
- 多进程：对目标函数没什么要求，通常比一般运算要快。如果目标函数是 CPU 密集型，能达到更优的性能
- 缓存化：把每次计算的输入和输出缓存下来，下次调用时，如果已经缓存中已经存在，那么直接取出结果，而不再调用。缓存化特别适用于输入值有限的情况，例如纯整数规划、迭代到后期的TSP问题等。
总的来说，性能上，矢量化 远远大于 多线程/多进程 大于 不加速，如果是输入值得可能个数有限，缓存化 远大于其他方案。
下面比较 不加速、矢量化、多线程、多进程 的性能：
下面比较 不加速 和 缓存化 的性能:
算子优化加速
主要手段是 矢量化 和 逻辑化
对于可以矢量化的算子，
scikit-opt 都尽量做了矢量化，并且默认调用矢量化的算子，且 无须用户额外操作。另外，考虑到有些算子矢量化后，代码可读性下降，因此矢量化前的算子也会保留，为用户进阶学习提供方便
0/1 基因的mutation
做一个mask，是一个与Chrom大小一致的0/1矩阵，如果值为1，那么对应位置进行变异（0变1或1变0）自然想到用整除2的方式进行
如此就实现了一次性对整个种群所有基因变异的矢量化运算。用pycharm的profile功能试了一下，效果良好
再次改进。我还嫌求余数这一步速度慢，画一个真值表
A | mask：是否变异 | A变异后 |
1 | 0 | 1 |
0 | 0 | 0 |
1 | 1 | 0 |
0 | 1 | 1 |
发现这就是一个 异或
测试发现运行速度又快了1~3倍，与最原始的双层循环相比，快了约20倍
0/1基因的crossover
同样思路，试试crossover.
- mask同样，1表示对应点交叉，0表示对应点不交叉
做一个真值表，总共8种可能，发现其中只有2种可能基因有变化（等位基因一样时，交叉后的结果与交叉前一样）
A基因 | B基因 | 是否交叉 | 交叉后的A基因 | 交叉后的B基因 |
1 | 0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 0 |
可以用
异或 和 且 来表示是否变化的表达式: mask = (A^B)&C，然后可以计算了A^=mask, B^=mask测试结果，效率提升约1倍
锦标赛选择算子selection_tournament
实战发现，selection_tournament 往往是最耗时的，几乎占用一半时间，因此需要优化。
优化前的算法是遍历，每次选择一组进行锦标赛。但可以在二维array上一次性操作。
发现own time 和time 都降为原来的10%~15%，效率提升了约9倍