A Tunable Generator of Instances of Permutation-Based Combinatorial Optimization Problems
提出一种基于广义Mallows模型的实例生成器，通过求解线性规划控制实例的局部最优数量等性质，可用于生成类似基准实例或不同难度的实例，帮助测试算法性能。
In this paper, we propose a tunable generator of instances of permutation-based combinatorial optimization problems. Our approach is based on a probabilistic model for permutations, called the generalized Mallows model. The generator depends on a set of parameters that permits the control of the properties of the output instances. Specifically, in order to create an instance, we solve a linear programming problem in the parameters, where the restrictions allow the instance to have a fixed number of local optima and the linear function encompasses qualitative characteristics of the instance. We exemplify the use of the generator by giving three distinct linear functions that produce three landscapes with different qualitative properties. After that, our generator is tested in two different ways. First, we test the flexibility of the model by producing instances similar to benchmark instances. Second, we account for the capacity of the generator to create different types of instances according to the difficulty for population-based algorithms. We study the influence of the input parameters in the behaviors of these algorithms, giving an example of a property that can be used to analyze their performance.