基于遗传算法的客户分配

Question

在我们目前的项目中，我们需要每个周末为主人分配一些家庭午餐。

每个主机可以为一组客人提供服务（主机容量）。每个家庭可以拥有不同数量的成员。

在将族分配给主机之前，需要应用几个规则：

1. 有些家庭不想一起共进午餐（这意味着如果已经分配给其他家庭，则无法将其分配给主持人）。
2. 一个家庭连续两周不能分配到同一个主人。
3. 13岁以下的儿童不应超过宿主容量的50％。
4. 成员年龄超过50岁的家庭不应超过主机容量的50％。

还有更多......

每个规则可以具有不同的重要性，即如果第一个规则中断，则不能进行从家庭到主机的分配，但是第3个和第4个可以放宽。

这种问题类似于婚礼计划表的安排，但要复杂得多。我研究了几天，似乎遗传算法可能是一个很好的方向。但是，我坚持如何建模，编码输入并实现算法。

我真的很感激任何建议。提前致谢。

Answer 1

像任何其他遗传算法问题一样，您需要制作有效/部分无效的染色体（可以评估的情景）。

染色体的一个例子可以是W1: [{H1: F2, F3, F7}; {H2: F4, F6}; {H3: F1, F5}], W2: [{H1: F4, F3, F7}; {H2: F2}; {H3: F1, F5, F6}], ...，意思是第1周（W1），宿主1（H1）是寄宿家庭2,3和7等等。

这可以通过随机分配或其他方法生成，称为Population Initialization

现在需要有一种方法来评估这种染色体。可以根据问题中定义的点来完成。

在此之后，可以想到一些基本功能，如交叉和变异。

基本示例：

1) for mutation, families can be shifted or switched from one host to another, 
2) for crossover, some weekends can be chosen from one parent, and some from the second, duplicate families can be adjusted.

希望这可以帮助。