Search

When designing meta-heuristic strategies to optimize the quadratic assignment problem (QAP), it is important to take into account the specific characteristics of the instance to be solved. One of the characteristics that has been pointed out as having the potential to affect the performance of optimization algorithms is the symmetry of the distance and flow matrices that form the QAP. In this paper, we further investigate the impact of the symmetry of the QAP on the performance of meta-heuristic algorithms, focusing on local search based methods. The analysis is carried out using the elementary landscape decomposition (ELD) of the problem under the swap neighborhood. First, we study the number of local optima and the relative contribution of the elementary components on a benchmark composed of different types of instances. Secondly, we propose a specific local search algorithm based on the ELD in order to experimentally validate the effects of the symmetry. The analysis carried out shows that the symmetry of the QAP is a relevant feature that influences both the characteristics of the elementary components and the performance of local search based algorithms., IT1244-19, PID2019-106453GA-I00/AEI/10.13039/501100011033, H2020

A number of local search based algorithms have been designed to escape from the local optima, such as, iterated local search or variable neighborhood search. The neighborhood chosen for the local search as well as the escape technique play a key role in the performance of these algorithms. Of course, a specific strategy has a different effect on distinct problems or instances. In this paper, we focus on a permutation-based combinatorial optimization problem: the linear ordering problem. We provide a theoretical landscape analysis for the adjacent swap, the swap and the insert neighborhoods. By making connections to other different problems found in the Combinatorics field, we prove that there are some moves in the local optima that will necessarily return a worse or equal solution. The number of these non-better solutions that could be avoided by the escape techniques is considerably large with respect to the number of neighbors. This is a valuable information that can be included in any of those algorithms designed to escape from the local optima, increasing their efficiency., TIN2016-78365-R IT1244-19

Given a particular instance of a combinatorial optimization problem, the knowledge about the attraction basin sizes can help to analyze the difficulty encountered by local search algorithms while solving it. As calculating these sizes exhaustively is computationally intractable, we focus on methods for their estimation. The accuracy of some of these estimation methods depends on the way in which the sample of solutions of the search space is chosen. In this paper, we propose a novel sampling method, which incorporates the knowledge obtained by the already explored solutions into the sampling strategy. So, in contrast to those that already exist, our method can adapt its behavior to the characteristics of the particular attraction basin. We apply our proposal to a number of instances of three famous problems: the quadratic assignment problem, the linear ordering problem and the permutation flow shop scheduling problem. We consider permutation sizes $$n = 10$$ and $$n = 12$$ and three different neighborhoods: adjacent swap, 2-exchange and insert, and observe that the new method generally outperforms those that already exist.

The aim of this paper is to introduce the concept of intersection between combinatorial optimisation problems. We take into account that most algorithms, in their machinery, do not consider the exact objective function values of the solutions, but only a comparison between them. In this sense, if the solutions of an instance of a combinatorial optimisation problem are sorted into their objective function values, we can see the instances as (partial) rankings of the solutions of the search space. Working with specific problems, particularly, the linear ordering problem and the symmetric and asymmetric traveling salesman problem, we show that they can not generate the whole set of (partial) rankings of the solutions of the search space, but just a subset. First, we characterise the set of (partial) rankings each problem can generate. Secondly, we study the intersections between these problems: those rankings which can be generated by both the linear ordering problem and the symmetric/asymmetric traveling salesman problem, respectively. The fact of finding large intersections between problems can be useful in order to transfer heuristics from one problem to another, or to define heuristics that can be useful for more than one problem.

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.

Local search algorithms are one of the most developed metaheuristics to solve combinatorial optimisation problems. Particularly, hill-climbing algorithms are simple but effective techniques that have been extensively used to deal with this kind of problems. These algorithms draw paths through the search space, choosing at each step a better solution than the current solution. As already known, they stop when a local optimum is reached. It is commonly believed that the closer the solution to the local optimum, the better its fitness. This premiss has a main implication: under this intuition, it is assumed that at each step of a hill-climbing algorithm, the new solution reduces the distance to the local optima. In this paper, we prove that this statement is not necessarily true. In fact, for some permutation-based combinatorial optimisation problems, such as the Permutation Flowshop Scheduling Problem, the Linear Ordering Problem and the Quadratic Assignment Problem, when considering the 2-exchange and the insert neighbourhoods, we find that, in most of the cases, the paths defined by a hill-climbing algorithm do not monotonically reduce the distance to the local optimum. Moreover, this distance remains constant for several steps, or it even increases for some steps. We provide an analysis of the solutions found in the attraction basins according to the distance to the local optimum and to the number of steps of the algorithm. We also give some visual examples of the paths followed by the algorithm.

Local Optima Networks were proposed to understand the structure of combinatorial landscapes at a coarse-grained level. We consider a compressed variant of such networks with features that are meaningful for the study of search difficulty in the context of local search. In particular, we investigate different landscapes of the Permutation Flowshop Scheduling Problem. The insert and 2-exchange neighbourhoods are considered, and two different objective functions are taken into account: the makespan and the total flow time. The aim is to analyse the network features in order to find differences between the landscape structures, giving insights about which features impact algorithm performance. We evaluate the correlation between landscape properties and the performance of an Iterated Local Search algorithm. Visualisation of the network structure is also given, where evident differences between the makespan and total flow time are observed.

The solution of many combinatorial optimization problems is carried out by metaheuristics, which generally make use of local search algorithms. These algorithms use some kind of neighborhood structure over the search space. The performance of the algorithms strongly depends on the properties that the neighborhood imposes on the search space. One of these properties is the number of local optima. Given an instance of a combinatorial optimization problem and a neighborhood, the estimation of the number of local optima can help not only to measure the complexity of the instance, but also to choose the most convenient neighborhood to solve it. In this paper we review and evaluate several methods to estimate the number of local optima in combinatorial optimization problems. The methods reviewed not only come from the combinatorial optimization literature, but also from the statistical literature. A thorough evaluation in synthetic as well as real problems is given. We conclude by providing recommendations of methods for several scenarios.

The performance of local search algorithms is influenced by the properties that the neighborhood imposes on the search space. Among these properties, the number of local optima has been traditionally considered as a complexity measure of the instance, and different methods for its estimation have been developed. The accuracy of these estimators depends on properties such as the relative attraction basin sizes. As calculating the exact attraction basin sizes becomes unaffordable for moderate problem sizes, their estimations are required. The lack of techniques achieving this purpose encourages us to propose two methods that estimate the attraction basin size of a given local optimum. The first method takes uniformly at random solutions from the whole search space, while the second one takes into account the structure defined by the neighborhood. They are tested on different instances of problems in the permutation space, considering the swap and the adjacent swap neighborhoods.

The Linear Ordering Problem is a combinatorial optimization problem which has been frequently addressed in the literature due to its numerous applications in diverse fields. In spite of its popularity, little is known about its complexity. In this paper we analyze the linear ordering problem trying to identify features or characteristics of the instances that can provide useful insights into the difficulty of solving them. Particularly, we introduce two different metrics, insert ratio and ubiquity ratio, that measure the difficulty of solving the LOP with local search type algorithms with the insert neighborhood system. Conducted experiments demonstrate that the proposed metrics clearly correlate with the complexity of solving the LOP with a multistart local search algorithm.

Designing customized optimization problem instances is a key issue in optimization. They can be used to tune and evaluate new algorithms, to compare several optimization algorithms, or to evaluate techniques that estimate the number of local optima of an instance. Given this relevance, several methods have been proposed to design customized optimization problems in the field of evolutionary computation for continuous as well as binary domains. However, these proposals have not been extended to permutation spaces. In this paper we provide a method to generate customized landscapes in permutation-based combinatorial optimization problems. Based on a probabilistic model for permutations, called the Mallows model, we generate instances with specific characteristics regarding the number of local optima or the sizes of the attraction basins.

This work is related to the search of complexity measures for instances of combinatorial optimization problems. Particularly, we have carried out a study about the complexity of random instances of the Traveling Salesman Problem under the 2-exchange neighbor system. We have proposed two descriptors of complexity: the proportion of the size of the basin of attraction of the global optimum over the size of the search space and the proportion of the number of different local optima over the size of the search space. We have analyzed the evolution of these descriptors as the size of the problem grows. After that, and using our complexity measures, we find a phase transition phenomenon in the complexity of the instances.