根据球员排名创建公平/势均力敌的球队的算法

Question

我有一个球员技能排名、年龄和性别的数据集，我想创建势均力敌的球队。

• 每队的球员人数相同(目前是 8 支球队，每队 12 名球员)。
• 团队的男女比例应相同或相似。
• 团队应该有相似的年龄曲线/分布。

我想在 Haskell 中尝试这个，但是编码语言的选择是这个问题中最不重要的方面。

Answer 1

这是一个 bin packing problem , 或 multi-dimensional knapsack problem . Björn B. Brandenburg 制作了a bin packing heuristics library in Haskell您可能会觉得有用。

你需要像...

data Player = P { skill :: Int, gender :: Bool, age :: Int }

确定队伍数量 n(我猜这是玩家总数的函数)。

找到每个团队所需的总技能:

teamSkill n ps = sum (map skill ps) / n

找到理想的性别比例:

genderRatio ps = sum (map (\x -> if gender x then 1 else 0)) / length ps

找到理想的年龄方差(您需要 Math.Statistics 包):

ageDist ps = pvar (map age ps)

并且您必须为这三个约束分配一些权重才能为给定团队得出得分:

score skillW genderW ageW team = skillW * sk + genderW * g + ageW * a
  where (sk, (g, a)) = (teamSkill 1 &&& genderRatio &&& ageDist) team

问题简化为最小化团队之间的分数差异。蛮力方法将花费与 Θ(n^k−1) 成正比的时间。考虑到您的问题的规模(8 支球队，每队 12 名球员)，这在典型的现代 PC 上相当于大约 6 到 24 小时。

编辑

可能适合您的方法(因为您在实践中不需要精确的解决方案)是模拟退火，或者通过随机排列持续改进:

1. 随机挑选团队。
2. 获得此配置的分数(见上文)。
3. 在两个或多个团队之间随机交换球员。
4. 为新配置打分。如果它比前一个好，则保留它并递归到步骤 3。否则丢弃新配置并再次尝试步骤 3。
5. 当某些固定次数的迭代(通过实验找到该曲线的拐点)得分没有提高时，停止。您此时拥有的配置很可能足够接近理想状态。运行此算法几次，以确保您没有找到比理想情况差得多的局部最优值。