提问人：Mathieu 提问时间：3/19/2018 最后编辑：vlad_tepeschMathieu 更新时间：4/11/2018 访问量：126
如何洗牌八个项目以接近最大熵？
How to shuffle eight items to approximate maximum entropy?
问：
我需要在 5 天内重复分析 8 个化学样品（每个样品每天分析一次）。我想每天生成伪随机样本序列，以实现以下目标：
- 避免日常序列位置的偏差（例如，避免一些样品主要在早上处理）
- 避免在不同日期重复样品对（例如 在第 1 天和第 2 天）
1234567887654321 - 通常将两个给定样本之间的距离从一天随机化到另一天
我可能把上述条件说得不好，但总体思路是尽量减少系统性影响，如每天的样品交叉污染和/或分析漂移。我可以随机随机地打乱每个序列，但由于生成的序列数量很少（N=5 与 40,320 种可能的组合），我不太可能接近最大熵之类的东西。
有什么想法吗？我怀疑这是分析科学中的一个常见问题，已经解决了，但我不知道该去哪里寻找。
答：
0赞
vlad_tepesch
4/11/2018
#1
只要想想：
您可能使用的基本指标是 Levenshtein 距离或一些轻微的修改（可能
myDist(w1, w2) = min(levD(w1, w2), levD(w1.reversed(), w2))
)
由于您想防止任何一对日子之间的近距离， 总体指标可以是两天之间样本订单的任意组合的总和。
Similarity = myDist(day1, day2)
+ myDist(day1, day3)
+ myDist(day1, day4)
+ myDist(day1, day5)
+ myDist(day2, day3)
+ myDist(day2, day4)
+ myDist(day2, day5)
+ myDist(day3, day4)
+ myDist(day3, day5)
+ myDist(day4, day5)
仍然缺少，这是启发式的如何创建示例订单。
你的问题让我想起了一些最快的路径查找问题，但更困难的是，每个选定的节点都会影响整个图的权重。所以这要困难得多。
也许可以创建一个包含每对组合之间所有距离的表（其可交换的，只有三角形（没有恒等对角线）矩阵需要（~1GB 内存）） 这可能有助于加快速度。myDist8!
也许从这个矩阵中获取最大值，并认为值低于某个阈值的每个组合同样没有价值，以减少搜索空间。
构建起始集。 使用 12345678 作为修复 day1，因为第一天无关紧要。永远不要改变这一点。 然后重复，直到选择 n 天：
- 添加距当前点最远的点。
- 如果有多个相等的可能性，请使用与前几天相距最远的那个。
现在迭代改进解决方案 - 也许使用一些破坏和重新创建的方法。您应该始终备份您找到的绝对最大值，并且您可以根据需要运行任意数量的迭代（并且您有时间）
- 选择与其他日子距离最小的（一两天）天
- 也许蛮力是这两天的最佳（就总距离而言）组合。
- 重复
- 如果优化卡住了（只选择了相同的 2 天或距离根本没有变小）
- 随机更改一两天为随机订单。
- 可以完全随机（除了第 1 天）可以选择起始集
下一个：了解令人困惑的算法表示法
评论