python - 如何在python中找到一组不同列元素的最低总和？

Question

问题陈述:有 5 个项目和 15 名员工，每列的数字表示每个员工对给定项目的兴趣。每个项目最多可以有 3 名员工。分数是从 1-5 1 是最高偏好，5 是最低偏好。我必须以最少的人不满意或最低分数的方式在项目中分配员工。请注意，我的算法创建了所有可能的组合，然后使用 sum 按升序对这些组合进行排序，并选择具有不同员工的前 5 个组合。

但这就是问题所在，例如，我的 sortedsum 矩阵是 [1,1,1,4,9,9,...] 现在这在算法上是正确的，但问题是如果我选择其中的前 5 个我的总和将是 16。但是如果我将 [2,1,1,4] 作为前四个，那么第五个项目团队的总和可能会代替 [1,1,1,4,9]到 3，这样最小值就会改变，这就是我的算法失败的地方。

我有一个 3nXn 矩阵，对于这个例子，我将它作为 15x5:
所以矩阵看起来像这样( /image/omcq7.png ):

df = pd.read_csv(io.StringIO("""

employee  proj_A  proj_B  proj_C  proj_D  proj_E
      A1       1       5       3       4       2
      B1       5       4       1       2       3
      C1       2       3       4       1       5
      A2       4       2       1       3       5
      B2       4       5       3       2       1
      C2       3       1       2       5       4
      A3       1       2       4       3       5
      B3       2       3       1       5       4
      C3       5       3       4       1       2
      A4       4       5       3       2       1
      B4       5       3       4       2       1
      C4       1       2       3       4       5
      A5       1       3       2       5       4
      B5       2       1       3       5       4
      C5       2       1       4       5       4

      """), sep=r"\s+")

[格式化以方便粘贴到shell中]

我要解决的问题是在每列中选择三个不同的元素，从不同的行中选择不同的含义，以使所有 5 列的总和保持最少。

例如，这里如果我为 A 选择 A1、B1、C1，然后为 B 选择 A2、B2、C2 等等，那么总和为 A 为 1+5+2=8，B 为 2+5+1=8以此类推，即 8+8+... 应该是所有可能组合的最小总和。请注意，如果将 A1、B1 和 C1 分配给 A，则它们无法切换到 B 或任何其他下一列。

我尝试的是创建从 A1、B1、C1 到 A5、B5 和 C5 的所有可能组合，并计算它们的总和并按递增顺序对其进行排序，然后选择具有不同元素的前五个，如下所示:

我的代码的限制:
1. 我优化的矩阵(这是一个 30x10 的矩阵)花费了太多时间，因为组合太多了。
2.它会忽略任何通过将初始元素的分数妥协到更高一点，我们可能会得到可以减少很多的中间分数的情况。

import pandas as pd
data=pd.read_csv("csvfile.csv")
teamsize=3
employes=data["Name"]
PScore=[]
for i in range(10):
    PScore.append(data[f"Project {i+1}"])
Scorings_combo=[]
for i in range(len(employes)):
    for j in range(len(employes)):
        for k in range(len(employes)):
            for l in range(10):
                if i==j or j==k or k==i:
                    break
                score=0
                score=score+PScore[l][i]+PScore[l][j]+PScore[l][k]
                Scorings_combo.append([i+1,j+1,k+1,l+1,score])
a=[Scorings_combo[i][4]for i in range(len(Scorings_combo))]
#b=sorted(a,reverse=True)
b=sorted(a)
emps=[]
sig=1
empl=[]
passigned=[]
countee=0
for i in range(len(b)):
    for j in range(3):
        if Scorings_combo[a.index(b[i])][j] in emps or Scorings_combo[a.index(b[i])][3] in passigned:
            a[a.index(b[i])]=-1
            sig=0
            break
    if sig!=0:
        print("New")
        for k in range(3):emps.append(Scorings_combo[a.index(b[i])][k])
        empl.append(Scorings_combo[a.index(b[i])])
        passigned.append(Scorings_combo[a.index(b[i])][3])
        countee=countee+1
        if count==8:
            break
    sig=1
    print(f"Iteration:{i}/{len(b)}")

例如:
3,3,3,4,9
即使以下是可能的，也将是解决方案:
4,4,4,4,4
因为它将寻找降序的不同元素，这给了我第一个解决方案。

如果您有任何想法，请帮助我。谢谢

这是数据的驱动器链接: https://drive.google.com/file/d/1yaswBEi3RzrhQ743hJTnUeZFZNo-QBBR/view?usp=sharing

这是一个更简单的例子:
矩阵=[[1,2],[2,1],[1,2],[1,2],[2,1],[1,2]]
现在最小可能的组合是:对于第一列:[1,1,1] 和 [1,1,2] 对于第二列。

Answer 1

我想试验遗传算法，这似乎是一个很好的优化类型问题，可以应用它。有 15 行可以按任何顺序排列，有 15 行!排列，或 1.0e+12。尝试所有排列的蛮力方法是不切实际的。

我有下面的函数来计算群体中个体的“适应度”。分数是平均值和标准差的组合。我的数学可能并不完全合理，而且我肯定会用 numpy 来完成它，但它似乎确实产生了不错的结果。

def calculate_fitness(population):
    fitness_scores = []

    for individual in population:
        # Group the rows in 3's according to the columns.
        proj_a = individual[  : 3,1]  # First 3 rows, column 1.
        proj_b = individual[ 3: 6,2]  # Next  3 rows, column 2, etc.
        proj_c = individual[ 6: 9,3]
        proj_d = individual[ 9:12,4]
        proj_e = individual[12:15,5]  # Bottom 3 rows, last column.

        arr = np.array([proj_a, proj_b, proj_c, proj_d, proj_e])

        mean = arr.mean()          # Mean.
        std  = np.abs(arr.std())   # Standard deviation.

        # We want both the lowest mean and lowest standard deviation.
        # For simplicity, let's just add them and use that as the score.
        fitness_scores.append(mean + std)

    # Invert and scale the values so they can be used as weights
    # for random selection.
    fitness_scores  = np.array(fitness_scores)
    fitness_scores  = (fitness_scores.max() + .3 ) - fitness_scores
    fitness_scores /= (fitness_scores.max() + .07)
    fitness_scores *= 100

    return fitness_scores

输出 - 前 3 行属于 A，接下来的 3 行属于 B，依此类推:

employee proj_A proj_B proj_C proj_D proj_E
      A3      1      2      4      3      5
      C4      1      2      3      4      5
      A1      1      5      3      4      2
      C2      3      1      2      5      4
      B5      2      1      3      5      4
      C5      2      1      4      5      4
      A2      4      2      1      3      5
      A5      1      3      2      5      4
      B3      2      3      1      5      4
      B1      5      4      1      2      3
      C3      5      3      4      1      2
      C1      2      3      4      1      5
      B2      4      5      3      2      1
      B4      5      3      4      2      1
      A4      4      5      3      2      1

在这个分组中，似乎每个人都很高兴，这可能是最佳组合。

在这里，除了 A3 得到 3 之外，每个人都对所有的 1 都非常满意。

employee proj_A proj_B proj_C proj_D proj_E
      C4      1      _      _      _      _
      A1      1      _      _      _      _
      A5      1      _      _      _      _
      B5      _      1      _      _      _
      C2      _      1      _      _      _
      C5      _      1      _      _      _
      A2      _      _      1      _      _
      B3      _      _      1      _      _
      B1      _      _      1      _      _
      C1      _      _      _      1      _
      A3      _      _      _      3      _
      C3      _      _      _      1      _
      A4      _      _      _      _      1
      B4      _      _      _      _      1
      B2      _      _      _      _      1

我发现调整高突变率并保护前 5 名个体免受突变和死亡的影响极大地改善了结果。

parent 是通过随机选取 4 个人使用他们的健康分数作为权重来选择的，以选择健康程度更高的 parent 。然后将 4 个中的顶部与任何其他不具有相同适应度分数的人进行匹配，以尝试防止近亲繁殖并将种群多样性保持在一个良好的范围内。

每次迭代，一个个体死亡，两个 parent 被选择并产生一个 child ，并且以 50% 的比率通过随机交换它的几行来选择和变异一个个体。

我发现最好的群体是 150 名成员，1k 到 2k 次迭代似乎得到了一致的结果。