一个易用、易部署的Python遗传算法库

本文涉及的产品
传统型负载均衡 CLB,每月750个小时 15LCU
网络型负载均衡 NLB,每月750个小时 15LCU
EMR Serverless StarRocks,5000CU*H 48000GB*H
简介: # [scikit-opt](https://github.com/guofei9987/scikit-opt) [![PyPI](https://img.shields.io/pypi/v/scikit-opt)](https://pypi.org/project/scikit-opt/) [![release](https://img.shields.io/github/v/relea

scikit-opt

PyPI
release
Build Status
codecov
PyPI_downloads
Stars
Forks
Join the chat at https://gitter.im/guofei9987/scikit-opt

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

sa_tsp.png

sa_tsp1.gif

sa.png

aca_tsp.png
ga_1.png
ga_tsp.png

ia2.png

pso.gif

pso.png

安装

pip install scikit-opt

或者直接把源代码中的 sko 文件夹下载下来放本地也调用可以

特性

特性1:UDF(用户自定义算子)

举例来说,你想出一种新的“选择算子”,如下
-> Demo code: examples/demo_ga_udf.py#s1

# step1: define your own operator:
def selection_tournament(algorithm, tourn_size):
    FitV = algorithm.FitV
    sel_index = []
    for i in range(algorithm.size_pop):
        aspirants_index = np.random.choice(range(algorithm.size_pop), size=tourn_size)
        sel_index.append(max(aspirants_index, key=lambda i: FitV[i]))
    algorithm.Chrom = algorithm.Chrom[sel_index, :]  # next generation
    return algorithm.Chrom

导入包,并且创建遗传算法实例
-> Demo code: examples/demo_ga_udf.py#s2

import numpy as np
from sko.GA import GA, GA_TSP

demo_func = lambda x: x[0] ** 2 + (x[1] - 0.05) ** 2 + (x[2] - 0.5) ** 2
ga = GA(func=demo_func, n_dim=3, size_pop=100, max_iter=500, lb=[-1, -10, -5], ub=[2, 10, 2],
        precision=[1e-7, 1e-7, 1])

把你的算子注册到你创建好的遗传算法实例上
-> Demo code: examples/demo_ga_udf.py#s3

ga.register(operator_name='selection', operator=selection_tournament, tourn_size=3)

scikit-opt 也提供了十几个算子供你调用
-> Demo code: examples/demo_ga_udf.py#s4

from sko.operators import ranking, selection, crossover, mutation

ga.register(operator_name='ranking', operator=ranking.ranking). \
    register(operator_name='crossover', operator=crossover.crossover_2point). \
    register(operator_name='mutation', operator=mutation.mutation)

做遗传算法运算
-> Demo code: examples/demo_ga_udf.py#s5

best_x, best_y = ga.run()
print('best_x:', best_x, '\n', 'best_y:', best_y)

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

Scikit-opt 也提供了十来个算子,参考这里

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

-> Demo code: examples/demo_ga_udf.py#s6

class MyGA(GA):
    def selection(self, tourn_size=3):
        FitV = self.FitV
        sel_index = []
        for i in range(self.size_pop):
            aspirants_index = np.random.choice(range(self.size_pop), size=tourn_size)
            sel_index.append(max(aspirants_index, key=lambda i: FitV[i]))
        self.Chrom = self.Chrom[sel_index, :]  # next generation
        return self.Chrom

    ranking = ranking.ranking


demo_func = lambda x: x[0] ** 2 + (x[1] - 0.05) ** 2 + (x[2] - 0.5) ** 2
my_ga = MyGA(func=demo_func, n_dim=3, size_pop=100, max_iter=500, lb=[-1, -10, -5], ub=[2, 10, 2],
        precision=[1e-7, 1e-7, 1])
best_x, best_y = my_ga.run()
print('best_x:', best_x, '\n', 'best_y:', best_y)

特性2: GPU 加速

GPU加速功能还比较简单,将会在 1.0.0 版本大大完善。
有个 demo 已经可以在现版本运行了: https://github.com/guofei9987/scikit-opt/blob/master/examples/demo_ga_gpu.py

特性3:断点继续运行

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

from sko.GA import GA

func = lambda x: x[0] ** 2
ga = GA(func=func, n_dim=1)
ga.run(10)
ga.run(20)

快速开始

1. 差分进化算法

Step1:定义你的问题,这个demo定义了有约束优化问题
-> Demo code: examples/demo_de.py#s1

'''
min f(x1, x2, x3) = x1^2 + x2^2 + x3^2
s.t.
    x1*x2 >= 1
    x1*x2 <= 5
    x2 + x3 = 1
    0 <= x1, x2, x3 <= 5
'''


def obj_func(p):
    x1, x2, x3 = p
    return x1 ** 2 + x2 ** 2 + x3 ** 2


constraint_eq = [
    lambda x: 1 - x[1] - x[2]
]

constraint_ueq = [
    lambda x: 1 - x[0] * x[1],
    lambda x: x[0] * x[1] - 5
]

Step2: 做差分进化算法
-> Demo code: examples/demo_de.py#s2

from sko.DE import DE

de = DE(func=obj_func, n_dim=3, size_pop=50, max_iter=800, lb=[0, 0, 0], ub=[5, 5, 5],
        constraint_eq=constraint_eq, constraint_ueq=constraint_ueq)

best_x, best_y = de.run()
print('best_x:', best_x, '\n', 'best_y:', best_y)

2. 遗传算法

第一步:定义你的问题
-> Demo code: examples/demo_ga.py#s1

import numpy as np


def schaffer(p):
    '''
    This function has plenty of local minimum, with strong shocks
    global minimum at (0,0) with value 0
    '''
    x1, x2 = p
    x = np.square(x1) + np.square(x2)
    return 0.5 + (np.sin(x) - 0.5) / np.square(1 + 0.001 * x)

第二步:运行遗传算法
-> Demo code: examples/demo_ga.py#s2

from sko.GA import GA

ga = GA(func=schaffer, n_dim=2, size_pop=50, max_iter=800, lb=[-1, -1], ub=[1, 1], precision=1e-7)
best_x, best_y = ga.run()
print('best_x:', best_x, '\n', 'best_y:', best_y)

第三步:用 matplotlib 画出结果
-> Demo code: examples/demo_ga.py#s3

import pandas as pd
import matplotlib.pyplot as plt

Y_history = pd.DataFrame(ga.all_history_Y)
fig, ax = plt.subplots(2, 1)
ax[0].plot(Y_history.index, Y_history.values, '.', color='red')
Y_history.min(axis=1).cummin().plot(kind='line')
plt.show()

ga_1.png

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

GA_TSP 针对TSP问题重载了 交叉(crossover)变异(mutation) 两个算子

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

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

import numpy as np
from scipy import spatial
import matplotlib.pyplot as plt

num_points = 50

points_coordinate = np.random.rand(num_points, 2)  # generate coordinate of points
distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric='euclidean')


def cal_total_distance(routine):
    '''The objective function. input routine, return total distance.
    cal_total_distance(np.arange(num_points))
    '''
    num_points, = routine.shape
    return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)])

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


from sko.GA import GA_TSP

ga_tsp = GA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=50, max_iter=500, prob_mut=1)
best_points, best_distance = ga_tsp.run()

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

fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
ax[1].plot(ga_tsp.generation_best_Y)
plt.show()

ga_tsp.png

3. 粒子群算法

(PSO, Particle swarm optimization)

3.1 带约束的粒子群算法

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

def demo_func(x):
    x1, x2, x3 = x
    return x1 ** 2 + (x2 - 0.05) ** 2 + x3 ** 2

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

from sko.PSO import PSO

pso = PSO(func=demo_func, dim=3, pop=40, max_iter=150, lb=[0, -1, 0.5], ub=[1, 1, 1], w=0.8, c1=0.5, c2=0.5)
pso.run()
print('best_x is ', pso.gbest_x, 'best_y is', pso.gbest_y)

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

import matplotlib.pyplot as plt

plt.plot(pso.gbest_y_hist)
plt.show()

pso.png

pso.gif
see examples/demo_pso.py

3.2 不带约束的粒子群算法

-> Demo code: examples/demo_pso.py#s4

pso = PSO(func=demo_func, dim=3)
fitness = pso.run()
print('best_x is ', pso.gbest_x, 'best_y is', pso.gbest_y)

4. 模拟退火算法

(SA, Simulated Annealing)

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

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

demo_func = lambda x: x[0] ** 2 + (x[1] - 0.05) ** 2 + x[2] ** 2

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

from sko.SA import SA

sa = SA(func=demo_func, x0=[1, 1, 1], T_max=1, T_min=1e-9, L=300, max_stay_counter=150)
best_x, best_y = sa.run()
print('best_x:', best_x, 'best_y', best_y)

sa.png

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

import matplotlib.pyplot as plt
import pandas as pd

plt.plot(pd.DataFrame(sa.best_y_history).cummin(axis=0))
plt.show()

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

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

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

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

from sko.SA import SA_TSP

sa_tsp = SA_TSP(func=cal_total_distance, x0=range(num_points), T_max=100, T_min=1, L=10 * num_points)

best_points, best_distance = sa_tsp.run()
print(best_points, best_distance, cal_total_distance(best_points))

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

from matplotlib.ticker import FormatStrFormatter

fig, ax = plt.subplots(1, 2)

best_points_ = np.concatenate([best_points, [best_points[0]]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(sa_tsp.best_y_history)
ax[0].set_xlabel("Iteration")
ax[0].set_ylabel("Distance")
ax[1].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1],
           marker='o', markerfacecolor='b', color='c', linestyle='-')
ax[1].xaxis.set_major_formatter(FormatStrFormatter('%.3f'))
ax[1].yaxis.set_major_formatter(FormatStrFormatter('%.3f'))
ax[1].set_xlabel("Longitude")
ax[1].set_ylabel("Latitude")
plt.show()

sa_tsp.png

咱还有个动画
sa_tsp1.gif
参考代码 examples/demo_sa_tsp.py

5. 蚁群算法

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

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

from sko.ACA import ACA_TSP

aca = ACA_TSP(func=cal_total_distance, n_dim=num_points,
              size_pop=50, max_iter=200,
              distance_matrix=distance_matrix)

best_x, best_y = aca.run()

aca_tsp.png

6. 免疫优化算法

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


from sko.IA import IA_TSP

ia_tsp = IA_TSP(func=cal_total_distance, n_dim=num_points, size_pop=500, max_iter=800, prob_mut=0.2,
                T=0.7, alpha=0.95)
best_points, best_distance = ia_tsp.run()
print('best routine:', best_points, 'best_distance:', best_distance)

ia2.png

7. 人工鱼群算法

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

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

def func(x):
    x1, x2 = x
    return 1 / x1 ** 2 + x1 ** 2 + 1 / x2 ** 2 + x2 ** 2


from sko.AFSA import AFSA

afsa = AFSA(func, n_dim=2, size_pop=50, max_iter=300,
            max_try_num=100, step=0.5, visual=0.3,
            q=0.98, delta=0.5)
best_x, best_y = afsa.run()
print(best_x, best_y)
相关实践学习
SLB负载均衡实践
本场景通过使用阿里云负载均衡 SLB 以及对负载均衡 SLB 后端服务器 ECS 的权重进行修改,快速解决服务器响应速度慢的问题
负载均衡入门与产品使用指南
负载均衡(Server Load Balancer)是对多台云服务器进行流量分发的负载均衡服务,可以通过流量分发扩展应用系统对外的服务能力,通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
相关文章
|
9天前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
23 0
|
12天前
|
机器学习/深度学习 算法 搜索推荐
从理论到实践,Python算法复杂度分析一站式教程,助你轻松驾驭大数据挑战!
【10月更文挑战第4天】在大数据时代,算法效率至关重要。本文从理论入手,介绍时间复杂度和空间复杂度两个核心概念,并通过冒泡排序和快速排序的Python实现详细分析其复杂度。冒泡排序的时间复杂度为O(n^2),空间复杂度为O(1);快速排序平均时间复杂度为O(n log n),空间复杂度为O(log n)。文章还介绍了算法选择、分而治之及空间换时间等优化策略,帮助你在大数据挑战中游刃有余。
39 4
|
12天前
|
机器学习/深度学习 缓存 算法
Python算法设计中的时间复杂度与空间复杂度,你真的理解对了吗?
【10月更文挑战第4天】在Python编程中,算法的设计与优化至关重要,尤其在数据处理、科学计算及机器学习领域。本文探讨了评估算法性能的核心指标——时间复杂度和空间复杂度。通过详细解释两者的概念,并提供快速排序和字符串反转的示例代码,帮助读者深入理解这些概念。同时,文章还讨论了如何在实际应用中平衡时间和空间复杂度,以实现最优性能。
44 6
|
4天前
|
网络协议 数据库连接 Python
python知识点100篇系列(17)-替换requests的python库httpx
【10月更文挑战第4天】Requests 是基于 Python 开发的 HTTP 库,使用简单,功能强大。然而,随着 Python 3.6 的发布,出现了 Requests 的替代品 —— httpx。httpx 继承了 Requests 的所有特性,并增加了对异步请求的支持,支持 HTTP/1.1 和 HTTP/2,能够发送同步和异步请求,适用于 WSGI 和 ASGI 应用。安装使用 httpx 需要 Python 3.6 及以上版本,异步请求则需要 Python 3.8 及以上。httpx 提供了 Client 和 AsyncClient,分别用于优化同步和异步请求的性能。
python知识点100篇系列(17)-替换requests的python库httpx
|
10天前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
17 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
2天前
|
Linux Python
【Azure Function】Python Function部署到Azure后报错No module named '_cffi_backend'
ERROR: Error: No module named '_cffi_backend', Cannot find module. Please check the requirements.txt file for the missing module.
|
7天前
|
机器学习/深度学习 人工智能 算法
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
玉米病害识别系统,本系统使用Python作为主要开发语言,通过收集了8种常见的玉米叶部病害图片数据集('矮花叶病', '健康', '灰斑病一般', '灰斑病严重', '锈病一般', '锈病严重', '叶斑病一般', '叶斑病严重'),然后基于TensorFlow搭建卷积神经网络算法模型,通过对数据集进行多轮迭代训练,最后得到一个识别精度较高的模型文件。再使用Django搭建Web网页操作平台,实现用户上传一张玉米病害图片识别其名称。
20 0
【玉米病害识别】Python+卷积神经网络算法+人工智能+深度学习+计算机课设项目+TensorFlow+模型训练
|
13天前
|
Shell Python
Python 的 os 库的应用实例
Python 的 os 库的应用实例
15 3
|
13天前
|
Linux Python Windows
Python sys 库的应用实例
Python sys 库的应用实例
19 3
|
13天前
|
Python
Python 中的 spell checker 库
Python 中的 spell checker 库
28 1