Python:用遗传算法解决背包优化问题？

Question

目前，我正在努力思考完成我正在做的事情的最佳方式。我有以下 pandas df。

    Player  Pos Salary  My Proj
0   James Harden    PG/SG   10600   51.94472302
1   Jose Juan Barea PG/SG   4200    22.20823452
2   Stephen Curry   PG/SG   8700    42.95809374
3   Eric Gordon     SG      5400    27.45218158
4   Nikola Vucevic  C       7400    37.00103015
5   Wilson Chandler SF/PF   4900    24.83866589

每天约有 200 名玩家发生这种情况。我需要运行优化来填充遵循以下约束的绘图王上最多 20 个阵容:

50,000 美元以下使用1个PG、1个SG、1个SF、1个PF、1个C、1个G、1个F和1个UTIL

正如您所看到的，大多数玩家可以在一个阵容中填补多个位置，这些位置由位置栏中的“/”字符表示。 G 位置可以由 PG 或 SG 填补，F 位置可以由 SF 或 PF 填补，UTIL 位置接受所有位置。

起初，我考虑使用背包蛮力方法，这似乎是最简单的方法，但实际上有数万亿种组合，因此这将花费大量时间，而不会真正做我真正想做的事情。

相反，我决定尝试使用遗传学方法，因为我已经观看了许多这方面的讲座视频，并认为这是解决这个问题的好主意。但是，我不知道如何在一般的 1/0 背包方法中设置这个问题，因为我需要包含很多东西。在典型的背包方法中，您只有重量和值(value)。我的权重和值(value)观是球员的薪水和他们的预计得分。不过，我还必须在此处包含玩家的位置，对于一名玩家来说，这可能是 1 种或有时 2 种不同的可能性。

希望这是有道理的，我基本上是在寻找有关如何在 Python 3 中开始解决此任务的某种见解。提前感谢您提供的任何信息!

Answer 1

这是一个好的开始:

完全理解遗传算法的基础知识，很好的例子here .

遗传算法的美妙之处在于，一旦您定义了如何评估适应度，其他一切都会自行落实。您可以从完全随机的项目开始，经过连续几代，它将变得有序。如果你以正确的方式处理的话，阵容和背包问题非常非常相似。您已经知道可以容纳多少元素(领先)；您现在只需选择哪些，这就是 GA 发挥作用的地方。

考虑以下步骤:

1. 创建您的人口(随机阵容)
2. 检查人口的健康状况、职位是否已填补、工资是否低于最高限额等
3. 在对阵容进行分级的同时发展人口
4. 继续新一代，直到您满意为止。