algorithm - 如何找到遗传算法的 "Crossover"运算符？

Question

披露:是的，这是我的作业。

我有以下问题:我有 50 名男性、50 名女性和 50 条狗。他们每个人都有一份他最喜欢的 list 。例如，6 号女士有一个从最不喜欢到最喜欢的 50 个男人的列表，以及一个从最不喜欢到最喜欢的 50 个最喜欢的狗的列表。男人有女人和狗的名单，狗有女人和男人的名单。

我需要找到我能找到的最佳匹配，这样女人、男人和狗都会尽可能快乐。我需要通过遗传算法来完成。

假设我有匹配项 A 和 B(我将所有 150 个实体与 50 个家庭匹配，因此每个女人/男人/狗只出现一次)。

如何交叉 A 和 B？我能想到的每一个交叉都会导致我遇到以下问题:有人会出现两次，而其他人则根本不会出现。

例如，如果我在 1 到 50 之间随机选择 X，并从 A 中取出前 X 个族，从 B 中取出 50-x 个第二个族，则新的概率大约为 0匹配是合法的，每个人只出现一次。

我该如何处理这样的问题？

任何提示都会有所帮助。

Answer 1

方法有很多种，没有一种是完美的。

A 和B 可以轮流向C 推荐家庭。由于 C 以 50 名免费男性、50 名免费女性和 50 条免费狗组成的池开始，因此它可以构成第一个建议的家庭。如果建议的家庭需要一个成员，比如一只狗，而该成员已经在一个家庭中，则新家庭可以从免费狗池中随机选择一只狗。

A 可以向 C 贡献一组，比如说 10 个家族，然后 B 可以贡献其在C(即与 A 中的 10 兼容的那些)。剩男剩女剩狗随意组建家庭。

C可以继承A的男女对和B的女狗对，没有任何冲突。