论文标题
用于关节分层和样品分配设计的模拟退火算法
A Simulated Annealing Algorithm for Joint Stratification and Sample Allocation Designs
论文作者
论文摘要
这项研究结合了模拟退火与增量评估，以解决关节分层和样本分配问题。在这个问题中，原子层被分为相互排斥和综合详尽的地层。原子层的每个分区都是分层问题的可能解决方案，其质量以其成本来衡量。可能的溶液的钟数是巨大的，即使是适度的原子地层，并且在每个溶液的评估时间中添加了额外的复杂性层。许多较大规模的组合优化问题无法解决为最佳性，因为对最佳解决方案的搜索需要大量的计算时间。许多本地搜索启发式算法是为此问题而设计的，但是这些算法可能会被困在当地的最小值中，从而阻止了任何进一步的改进。我们在现有的本地搜索算法套件中添加了一种模拟退火算法，该算法允许逃离本地最小值，并使用Delta评估来利用连续解决方案之间的相似性，从而减少评估时间。我们将模拟退火算法与最近的两种算法进行了比较。在这两种情况下，模拟的退火算法在计算时间较小的情况下都达到了可比质量的解决方案。
This study combines simulated annealing with delta evaluation to solve the joint stratification and sample allocation problem. In this problem, atomic strata are partitioned into mutually exclusive and collectively exhaustive strata. Each partition of atomic strata is a possible solution to the stratification problem, the quality of which is measured by its cost. The Bell number of possible solutions is enormous, for even a moderate number of atomic strata, and an additional layer of complexity is added with the evaluation time of each solution. Many larger scale combinatorial optimisation problems cannot be solved to optimality, because the search for an optimum solution requires a prohibitive amount of computation time. A number of local search heuristic algorithms have been designed for this problem but these can become trapped in local minima preventing any further improvements. We add, to the existing suite of local search algorithms, a simulated annealing algorithm that allows for an escape from local minima and uses delta evaluation to exploit the similarity between consecutive solutions, and thereby reduces the evaluation time. We compared the simulated annealing algorithm with two recent algorithms. In both cases, the simulated annealing algorithm attained a solution of comparable quality in considerably less computation time.
