将人分成最具多样性的小组的算法

Question

我想要一个算法来将参加即将到来的会议的人分组。有很多人来自不同的地区、部门、性别等，他们想尽可能地分散人员，以便每个小组都有多样性。

是否有已知的算法或者工具（例如Excel）可以解决这个问题，这应该是非常普遍的问题？

简化这个问题，假设有 n个人（比如100个） 要分为g个小组（比如6个），每个小组应该有尽量接近数量的人。

他们有以下类别：伦敦、北部、中部、西部、苏格兰（大部分在伦敦）

性别：女、男、其他

部门：销售、支持、管理

等级：6个不同等级

额外信息： 每个类别中的人比例不同，即销售人员比管理人员多。

可能有优先顺序，他们更希望性别平均分配而不是部门平均分配。

我使用C#，但愿意阅读任何内容。

谢谢！ Ben

- Ben Dessau

---

你可能想查找“装载问题”。2000年前，罗马人尝试解决这个问题并取得了不太成功的成果。数学家们仍在努力解决这些问题。罗马人在出征时试图最少地使用战车来高效地装载物资。因此，将过多的物品放入一个战车中会减慢速度或使其翻车。所以像你一样，罗马人希望均匀分配物品。 - jdweng

编程方面的内容翻译如下：简单的编码方法是选择一些随机排序（应该围绕着平衡），然后根据您选择的标准选择最佳的排序。您还可以尝试在组之间交换人员，看看是否有任何交换会改善得分。 - Peter de Rivaz

例如，他可以编写一些代码来填充People对象列表以包含示例数据。如果没有包含代码，最终这个问题可能会被关闭。https://meta.stackexchange.com/questions/165519/where-should-i-post-questions-about-algorithms-stack-overflow-or-software-engin 可能会对@YairHalberstadt感兴趣。 - mjwills

公平地说，我想这应该属于软件工程领域。 - Yair Halberstadt

例子总是很好的。当然，人们可以提出答案，但如果有一些例子，从他的角度来看，更好的答案是可以预期的。这里有一些非正式的东西，例如区域->离散名称与坐标以及某些距离度量。如果像那样编写，您将无法将它们视为离散的。还有一些经典的东西，比如：组大小上的l1 vs. l2损失？或其他指标？最好决定一下，但有时候例子也有帮助。 - sascha

Answer 1

这绝不是一个琐碎的问题，如果没有确切的算法，很难解决。我不知道学术上的类似情况，但这是随机/概率优化的完美应用案例。

您需要一个适合的适应度函数，可以用一个数字来传达当前分配的多样性，例如一些简单直观的东西：

sum
  for each group
    for each trait
      trait_weight * abs(%_occurrence_in_group - %_occurrence_in_population)

（在上述情况下，越低越好）

选择像模拟退火或遗传算法这样的方法，并搜索极值。

- j4nw

---

我认为爬山算法比遗传算法或模拟退火算法简单得多，对于这种具有密集解的问题，使用随机重启的爬山算法应该足够了。 - Yair Halberstadt

嗯，SA（软件架构）在我看来非常简单。但他没有提到邻域，这是一个核心成分/必需品。 - sascha

如果你是自己编程，而且这是你第一次接触人工智能，那么这并不是那么简单。 - Yair Halberstadt

这只是一个概率计算和一个随机抽样，与您的算法相比只需进行一些 if 判断。 - sascha

Answer 2

首先定义一个实用函数。我们希望这个函数既准确又快速计算，那么如何比较每个类别中人数的比例在群体中与总体中每个类别的实际比例有多接近呢？

因此，如果一个由8个人组成的团队有5个男性，3个女性，4个销售人员和4个支持人员，但是在总体中男女平分，总人数的2/3是销售人员，另外1/3支持实用功能将是-((5/8-1/2)+(3/8-1/2)+(4/8-2/3)+(4/8-1/3))

之所以前面有一个减号，是因为实用功能随着多样性的增加而增加。

一旦定义了实用函数，就有很多方法可以实现它，包括模拟退火等。然而，为了你的目的，我建议使用随机重启的爬山法，因为我认为这已经足够了。

随机将人们分配到不同的组中，然后计算实用函数。从一个组中随机选择一个人，从另一个组中选择另一个人，如果交换后实用性更高，则进行交换。继续交换，进行若干轮（例如200轮），然后记录分配和实用函数。从新的随机分配重新开始，重复整个过程几次。选择具有最高实用函数的那一个。

如果不清楚，请让我解释一下。

- Yair Halberstadt

---

这是一个不错的开始，但你的群组大小是基于你的邻域定义的不变量（在两个群组之间切换）。大小永远不会改变。这可以通过随机重启来绕过，但也可以考虑其他邻域（例如，在三个群组之间）。 - sascha

他说每组应该有大致相等的数量，我认为不改变这一点很容易找到一个好的解决方案。 - Yair Halberstadt

但是“大致上”是一个非常数，取决于要优化的函数，当考虑到这一点时，优化值可能会发生很大变化。 - sascha