Combining K-means type algorithms with Hill Climbing for Joint Stratification and Sample Allocation Designs
This work addresses a combinatorial optimization problem in survey design, providing incremental improvements by offering more algorithm choices for designers.
The paper tackles the joint stratification and sample allocation problem, a combinatorial optimization challenge, by combining k-means type algorithms with hill climbing in stages, and reports that this multi-stage approach generally performs well compared to recent algorithms in terms of solution costs, evaluation times, and training times for both atomic and continuous strata.
In this paper we combine the k-means and/or k-means type algorithms with a hill climbing algorithm in stages to solve the joint stratification and sample allocation problem. This is a combinatorial optimisation problem in which we search for the optimal stratification from the set of all possible stratifications of basic strata. Each stratification being a solution the quality of which is measured by its cost. This problem is intractable for larger sets. Furthermore evaluating the cost of each solution is expensive. A number of heuristic algorithms have already been developed to solve this problem with the aim of finding acceptable solutions in reasonable computation times. However, the heuristics for these algorithms need to be trained in order to optimise performance in each instance. We compare the above multi-stage combination of algorithms with three recent algorithms and report the solution costs, evaluation times and training times. The multi-stage combinations generally compare well with the recent algorithms both in the case of atomic and continuous strata and provide the survey designer with a greater choice of algorithms to choose from.