遗传算法在电商物流集装箱的应用

业务场景

在电商行业中, 某个站点的产品只能服务当地区域的需求. 因此当该地需求增大导致该站点的sku缺货, 从而出现热销的sku没有货, 滞销的sku一直占用库存的现象.

因此当某一站点缺货或者预计即将缺货的时候, 为保证时效, 最佳的方案是从周围仓库调拨.

所以, 当某一次调拨时, 为了利润最大化, 则需要最小化成本, 无论包装成本, 物流成本或者是人力成本等等.

要求:

1. 单次发运建议量最低15kg，最高30kg，

数据结构

优化问题

类似背包问题, 不能超重的情况下, 是该背包的价值最大.

最小每次发运包裹数, 并不超过集装箱的重量限制不能超过30kg, 找出每组最大价值, 且包裹数最小.

输入

必要参数: data

格式符合json. 例如:

[
    {
        "sku": "aa",
        "weight": 1,
        "value": 2
    },
    {
        "sku": "bb",
        "weight": 3,
        "value": 4
    },
    {
        "sku": "aa",
        "weight": 1,
        "value": 2
    },
    {
        "sku": "bb",
        "weight": 3,
        "value": 4
    },
    {
        "sku": "aa",
        "weight": 1,
        "value": 2
    },
    {
        "sku": "bb",
        "weight": 3,
        "value": 4
    }
]

• data: list = None,
• weight_min: int = 0,
• weight_max: int = 9999,
• population_size: int = 10,
• epoch: int = 100,
• crossover_rate: float = 0.2,
• mutation_rate: float = 0.01

输出

• result: list. 使用输入data长度一直的True False的列表.

意义: 代表本次进化结果是将True对应data的元素合在一起发运

算法架构

流程图

主函数

# 初始化种群, 直至产生适应环境的初始种群

# 计算适应度
population_fitness = self.fitness(init_population)
# 选择操作
population_selection = self.selection(population_fitness)
# 重组操作
population_crossover = self.crossover(population_selection)
# 变异操作
population_mutation = self.mutation(population_crossover)

# 经过一代之后产生新的子代, 赋值给初始种群变量, 进行下一次运行
init_population = population_mutation
# 存储local最佳个体
epoch_best_list.append(local_best)
# 判断该代的适应度是否比以前更优
if all_best["value"] < local_best["value"]:
all_best = local_best

编码操作

0-1编码

将传入数据的列表理解成一条染色体, 每一个元素理解成基因位, 他们可能的值是0 or 1.

例子: data输入值:

[{"sku": "aa", "weight": 1, "value": 2},
{sku": "bb", "weight": 3, "value": 4},
{"sku": "aa", "weight": 1, "value": 2}, 
{sku": "bb", "weight": 3, "value": 4},
{"sku": "aa", "weight": 1, "value": 2}, 
{sku": "bb", "weight": 3, "value": 4},]

data长度为6, 那么一个个体的染色体编码可以表示为: 011001亦或是100110等等. 1表示组合这些数据

初始化种群

按照编码规则随机产生合适的种群数量.

这里要求包裹重量不超过30kg, 也就是每个个体的解的重量之和不超过30kg. 因此在初始化种群时, 需要有一个边界限制条件. 倘若初始种群不合适环境, 在之后的淘汰个体的环节会被全部给淘汰掉, 导致无法进化出合适的个体.

解决方案:

因为是随机从0 or 1 选出作为个体. 所以重量期望大于30kg的话, 那么产生的个体大多不适应环境. 所以需要不等概率选取0,1.

1. 当重量期望过大是, 需要循环降低0的权重, 反之需增大0的权重.

计算适应度

适应度函数的好坏直接决定了种群个体的质量. 所以对适应度函数的选择需要格外关心.

本例子是最大化同一批发运sku的价值总和.

选择操作

使用轮盘赌, 个体适应度越高被选中的几率就越大.

种群的总适应值

个体被选中的概率为

转动n之后选出n个个体作为下一代的父本.

重组操作

每个个体按重组概率选择, 再随机选择交换位置pos, 两两进行交换.

个体1: 011001

个体2: 101100

假设产生的pos为2, 那么在2之后的基因片段互换, 变为

个体1: 011100

个体2: 101001

变异操作

每个个体按变异概率, 确定该个体是否变异, 若是则再随机确定变异位置.

个体1: 011001

假设产生的pos为2, 那么变异后的个体为

个体1: 010001

结束

结束条件有多个:

1. 当到达代数
2. 产生子代差别不大
3. ....