TSP 可能不是这个问题的一个很好的描述。原因是您实际上并没有在寻找最佳套装列表,因为您只是在寻找一些好的套装列表。
话虽如此,您的问题让我想起了很多使用粒子过滤器来尝试定位某物的位置。
稍微调整一下该方法会得到如下结果:
- 使用加权概率随机生成 100 个集合列表。手工挑选一些可能会很有用。
- 计算每个集合列表的分数,然后将其用作权重,随机选择 10 个集合列表。
- 对于这些集合列表中的每一个,使用加权概率随机生成 10 首歌曲。例如,您可以使用歌曲的分数作为权重来确定是否应该更改它(较低的相对分数意味着歌曲更有可能被更改)。
- 根据需要重复步骤二和三。
- 选择当前最好的,或随机选择当前 100 个中的一个。
我使用了 100 个示例,但您可以使用几乎任何可能低于一百万左右的样本量,除非您有很多时间让它运行。请注意您选择了多少 VS 从选定的那些中生成了多少。选择的数字乘以生成的数字应该等于您最初开始使用的数字。
编辑:
不确定您是否熟悉加权概率,所以我可能应该总结一下,因为它对算法相当重要。假设您有歌曲 AC,权重分别为 1-3。处理加权概率的一种方法不是从 [A,B,C](未加权)中随机选择 100 个元素,而是从 [A,B,B,C,C,C] 中随机选择 100 个元素。由于 C 的权重是 A 的 3 倍,因此它被选中的可能性是 3 倍。
理想情况下,如果您使用该方法,您应该将分数保持为整数,并且它们应该相对较低(以便从中选择元素的列表的最大长度不会太高)。如果您不介意精度损失(在这种情况下可能没问题),您还可以标准化概率并使用它创建一个列表,该列表在其大小方面将更加可预测。这可以通过将权重相加,然后将每个权重除以总和,然后将所有结果乘以一个数字来完成。因此,例如,如果您的权重为 [1000,10000,100000] 而不是 1-3,则将每个权重除以总和 (111000) 得出大约 [0.009,0.090,0.901],乘以 100(给出列表大小约 100) 并四舍五入到最接近的整数给出: [1,9, 90] 因此,您从中随机选择元素的列表应恰好包含 1 个 A、9 个 B 和 90 个 C。有可能只选择 A 进行重新采样(步骤 3),但这是不太可能的,尽管如果发生它会出现问题。在这种情况下,您可能必须重新运行该程序。有一些方法可以解决这个问题,但最终会失去算法的很多随机性。
哦,再加上 3) 更改歌曲时,计算可以替换该歌曲的每首歌曲的分数。删除所有权重较低的歌曲或可能略低于其权重的一部分*,然后使用分数作为权重并随机选择将替换它的新歌曲(如果分数相当高,这实际上可能是同一首歌曲) .
*这是可选的,但如果您认为它可能有用,那么实施它可能不是一个坏主意,因为您可以将其设置为低于 0.0 * 重量。