将个人分组为家庭

Question

我们有一个模拟程序，在这个程序中，我们将非常多的个体群体，并将他们分组为一个家庭。然后对每个家庭进行模拟。

我负责把每个人分成几个家庭，我认为这是一个很酷的问题。

现在，我的技巧相当天真/简单。每个记录都有一些特征，包括已婚/单身、年龄、性别和收入水平。对于已婚人士，我选择一个个人，并在人口中循环，并根据匹配函数寻找匹配。对于有孩子的人/夫妇，我基本上做了同样的事情，寻找随机数量的孩子(根据经验分布选择)，然后循环遍历所有的孩子，挑选出他们，然后根据匹配函数将他们添加到家庭中。在此之后，并不是每个人都匹配，所以我放宽了我的匹配函数的限制，并再次循环。我一直这样做，但我停止了我的比赛功能变得太荒谬(例如结婚85岁到20岁)。任何剩馀的人都被写成一个人。

这对于我们目前的目标来说是很好的，而且我可能永远不会得到时间或许可去重新设计它，但是我至少想为这个场合做计划或者学习一些很酷的东西--即使我从来不使用它。另外，我担心这个算法对于较小的样本规模也不能很好的工作。有谁知道我可以研究哪些类型的算法可能与这个问题有关，或者我可能如何将它形式化？

作为参考，我对CLRS的第1-26章很满意，但我并没有真正触及NP-完备或近似算法。并不是说你不应该提起这些话题，但如果你提出了，也许对我宽容一点，因为我可能不会马上理解你所说的一切。)我对进化算法也不太了解。

编辑:我特别希望改进以下内容：

1. 不那么荒谬的婚姻。
2. 最后单身的人更少了。

Answer 1

也许你要找的是聚类分析

Answer 2

让我们试着像这样思考你的问题(从解决配偶匹配开始)：

如果要有一个矩阵，其中每一行都是男性，每一列都是女性，而该矩阵中的每个单元格都是匹配函数的返回值，那么您现在要寻找的是选择单元格，这样就不会有一行或列中选择多个单元格，并且所有选定单元格的总和应该是最大的。这非常类似于N皇后问题，修改后，“皇后”的每个分配都有一个奖励(我们应该最大化)。

您可以通过使用以下图形来解决这个问题：

你有根，

第一个原始单元格的每个值都是一个边的权重，导致第一个深度顶点

第二个原始单元格的每个值都是一个边的权重，导致第二个深度顶点。

等。

(请注意，当您找到第一个女性的匹配时，您不应该再考虑她，因此对于您找到匹配对象的其他每个女性)，最大分配可以由BFS完成，更好的是由*来完成(注意A*通常会查找最小成本，因此您将不得不修改它)。

对于夫妻之间的匹配(或者单身，稍后会有更多的介绍)孩子们，我认为做一些修改的KNN是你最好的选择，但是你需要根据你的需要优化它。但现在我要和你的编辑联系起来。

如何衡量算法的效率？

您需要一个函数，接收所有状态的预期分布(单身、已婚有一个子女、单身有两个子女等)，以及解决方案中所有状态的分布，并对解决方案进行相应的分级。如何计算预期的分布？这是相当多的统计工作。

首先，你需要知道所有州(单身、已婚)的分布情况。如上文所述)在人口中，

然后你需要知道年龄和性别在人口中的分布，

最后一件事你需要知道-年龄和性别的分布在，你的人口。只有这样，根据这三个人，你才能计算出每个州有多少人。然后你可以测量你所期望的和你得到的.那是很多打字..。对不起一般的部分..。