查看文章

Solving a problem by using metaheuristic algorithms requires the evaluation of a large number of potential solutions. This paper presents a theoretical and experimental study of the application of partial evaluation in the Rank Aggregation Problem (RAP). Partial evaluation just computes the part of the objective function that is affected by the modifications introduced by certain operators. In particular, we study some of the most common mutation/neighboring operators that are used in problems defined in the space of permutations, namely insertion, interchange and inversion. The theoretical study shows that the complexity of evaluating the original objective function can be reduced from quadratic to linear by using partial evaluation after applying insertion and interchange. Regarding the experimental study, it shows that for the insertion and interchange operators, the running time for the evaluation of the objective …