Shi*_*il 6 python python-3.x pandas
问题陈述：有 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：所以矩阵看起来像这样（https://i.stack.imgur.com/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
这是一个更简单的例子： Matrix=[[1,2],[2,1],[1,2],[1,2],[2,1],[1,2]] 现在最小可能的组合是：对于第一列： [1,1,1] 和 [1,1,2] 对于第二列。
我想尝试遗传算法，这似乎是一个很好的优化类型问题，可以应用它。有 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 个个体免受突变和死亡的影响，可以大大改善结果。
通过随机选取 4 个人，使用他们的健康得分作为权重来选择父母，以选择较高健康的父母。然后将 4 个中的顶部与任何其他不具有相同适应度分数的进行匹配，以尝试防止近亲繁殖并将种群多样性保持在良好的范围内。
每次迭代，一个个体死亡，两个父母被选择并产生一个孩子，并且以 50% 的概率选择一个个体并通过随机交换其几行来变异。
我发现最好的群体是 150 名成员，并且 1k 到 2k 次迭代似乎得到了一致的结果。