Many optimization algorithms represent solutions as permutations. However, despite their apparent simplicity, permutations pose significant challenges—especially for Global Random Search (GRS) algorithms—due to the mutual-exclusivity constraint. This constraint complicates both the learning and sampling of probability distributions over the permutation space, often leading to computationally expensive procedures. A promising alternative involves transforming permutation-encoded solutions into integer vectors using bijective functions on the symmetric group Sn, resulting in what are known as inversion vectors. While inversion vectors have been studied for centuries, a unified and formal framework encompassing all their codifications has been lacking. In this paper, we introduce precise definitions and a unified notation for various types of inversion vector codifications. We establish bijective transformations between them, providing a formal characterization of their relationships and properties. Leveraging this theoretical foundation, we analyze and explain the behavior of GRS algorithms across different permutation problems when using different inversion vector representations.

Academic research in dynamic optimisation uses benchmark generators to artificially simulate controlled and reproducible changing-environments to systematically compare algorithmic performance under uncertainty. However, due to the scarcity or difficulty in acquiring real-world data, benchmarks often fail to incorporate real-world features, such as problem constraints or the time-linkage property, where previously made decisions influence future events. This study introduces a Gaussian Copula-based real-world data-driven synthetic data generation model for Dynamic Truck and Trailer Scheduling Problem (DTTSP). The model offers a realistic, privacy-preserving DTTSP benchmark instance generator, which can be used to recreate the dynamism, constraints, heterogeneity, and time-linkage of logistics and supply chain operations. This work examines the utility, fidelity, and privacy of the suggested model in four workday case studies from a local transportation company. The conducted experiments demonstrate the systematical application of Gaussian Copulas to produce accurate, useful, and secure DTTSP benchmark instances that capture the statistical properties and correlation of variables, as well as the temporal patterns, in the original annual data. Nevertheless, the utility analysis of the conditional sampling indicates that there is still room for improvement in the modelling process.

Advances in large models, reinforcement learning, and open-endedness have accelerated progress toward autonomous agents that can learn and interact in the real world. To achieve this, flexible tools are needed to create rich, yet computationally efficient, environments. While scalable 2D environments fail to address key real-world challenges like 3D navigation and spatial reasoning, more complex 3D environments are computationally expensive and lack features like customizability and multi-agent support. This paper introduces Craftium, a highly customizable and easy-to-use platform for building rich 3D single- and multi-agent environments. We showcase environments of different complexity and nature: from single- and multi-agent tasks to vast worlds with many creatures and biomes, and customizable procedural task generators. Benchmarking shows that Craftium significantly reduces the computational cost of alternatives of similar richness, achieving +2K steps per second more than Minecraft-based frameworks.

We analyze three permutation-based combinatorial optimization problems in Fourier space, namely, the quadratic assignment problem, the linear ordering problem (LOP), and the symmetric and nonsymmetric traveling salesperson problem (STSP). In previous studies, one can find a number of theorems with necessary conditions that the Fourier coefficients of the aforementioned problems must satisfy. In this manuscript, we prove the sufficiency of these conditions, which implies that they constitute the exact characterization of the problems in Fourier space. In addition, the Fourier coefficients of the LOP and the symmetric and non-STSP are completely characterized by showing certain proportionality patterns that they must follow. Taking the characterization in Fourier space of the problems as a basis, we study classes of equivalent instances of the LOP and the symmetric and non-STSP, considering that two instances are equivalent if they have the same objective function. Furthermore, we give canonical representations for each problem in such a way that the input matrices have the minimum number of nonzero parameters.

Learning-based methods have gained significant popularity in the field of combinatorial optimization in recent times. Researchers in the deep learning community aim to design models that, given an instance of a problem, directly generate optimal solutions in the first shot. However, due to the inherent complexity of certain combinatorial problems, achieving this in a single attempt is not trivial, and additional strategies are required to search for the optimal solution in several tries. For this purpose, researchers have proposed sampling techniques or active search which, in our opinion, are computationally wasteful with a limited performance. In this paper we develop strategies that efficiently exploit the fast inference capability of learning methods. Particularly, the objective is to solve the entire problem by solving it in fragments. It can be applied to any problem where the improvement of the overall solution is guaranteed by improving any part of the problem. To illustrate this, we focus on the Linear Ordering Problem (LOP) as a case of study. We employ a Neural Combinatorial Optimization model within a sliding-window optimization strategy, where specific parts of a candidate solution are optimized without compromising the overall solution quality. We explore various implementation aspects, including window size, step size and overlapping configurations. Experimental results show that the presented method achieves superior performance and better efficiency compared to baseline strategies and competitors, and significantly surpasses the previous learning methods for LOP instances of size 200, achieving an average gap to the best known value of only 0.04% within a 1-minute run-time.

This work introduces a growable and modular neural network architecture that naturally avoids catastrophic forgetting and interference in continual reinforcement learning. The structure of each module allows the selective combination of previous policies along with its internal policy accelerating the learning process on the current task. Unlike previous growing neural network approaches, we show that the number of parameters of the proposed approach grows linearly with respect to the number of tasks, and does not sacrifice plasticity to scale. Experiments conducted in benchmark continuous control and visual problems reveal that the proposed approach achieves greater knowledge transfer and performance than alternative methods.

Emergency Medical Services are essential for health systems as their effective management can improve patient prognosis. Nevertheless, designing an optimized distribution of resources is a difficult task due to the complex nature of these systems. Moreover, locating the resources is particularly challenging in heterogeneous density territories where, in addition to their efficient management, the equity principle in the medical access of inhabitants of rural areas is also desirable. This paper approaches the ambulance (re)location–allocation problem in the geographical area of the Basque Country. The area has three major cities, which account for a third of the emergencies, while there are few emergencies in rural areas, with a sparse population. To that end, a two-stage stochastic 0-1 integer linear programming model that balances the response time between densely populated and isolated areas is proposed. Specifically, the model incorporates two relevant principles: (1) optimizing emergency attendance through the option of allocating ambulances via a multi-interval response time and (2) equitably responding to emergencies so remote areas are not neglected. Conducted experiments have been validated and indicate that the proposed model can improve the success rate in rural areas by 23 percentage points, while reducing the overall success rate by less than 9 percentage points.

Neural Combinatorial Optimization has emerged as a new paradigm in the optimization area. It attempts to solve optimization problems by means of neural networks and reinforcement learning. In the past few years, due to their novelty and presumably good performance, many research papers have been published introducing new neural architectures for a variety of combinatorial problems. However, the incorporation of such models in the conventional optimization portfolio raises many questions related to their performance compared to other existing methods, such as exact algorithms, heuristics, or metaheuristics. This article aims to present a critical view of these new proposals, discussing their benefits and drawbacks with respect to the tools and algorithms already present in the optimization field. For this purpose, a comprehensive study is carried out to analyze the fundamental aspects of such methods, including performance, computational cost, transferability, and reusability of the trained model. Moreover, this discussion is accompanied by the design and validation of a new neural combinatorial optimization algorithm on two well-known combinatorial problems: the Linear Ordering Problem and the Permutation Flowshop Scheduling Problem. Finally, new directions for future work in the area of Neural Combinatorial Optimization algorithms are suggested.

Probability-based algorithms have proven to be a solid alternative for approaching optimization problems. Nevertheless, in many cases, using probabilistic models that efficiently exploit the characteristics of the problem involves large computational overheads, and therefore, lower complexity models such as those that are univariate are usually employed within approximation algorithms. With the motivation to address such an issue, in this article, we aim to introduce an iterative optimization framework that employs generative models to efficiently estimate the parameters of probability models for optimization problems. This allows the use of complex probabilistic models (or those that are appropriate for each problem) in a way that is feasible to apply them iteratively. Specifically, the framework is composed of three elements: a generative model, a probability model whose probability rule is differentiable, and a loss function. The possibility of modifying any of the three elements of the framework offers the flexibility to design algorithms that best adapt to the problem at hand. Experiments conducted on two case studies reveal that the presented approach has strong performance in terms of objective value and execution time when compared to other probability-based algorithms. Moreover, the experimental analysis demonstrates that the convergence of the algorithms is controllable by adjusting the components of the framework. For the sake of reproducibility, the source code, results, scripts, figures, and other material related to the manuscript are available at https://github.com/mikelma/nnco_lib .

Recent advances in graph neural network (GNN) architectures and increased computation power have revolutionized the field of combinatorial optimization (CO). Among the proposed models for CO problems, neural improvement (NI) models have been particularly successful. However, the existing NI approaches are limited in their applicability to problems where crucial information is encoded in the edges, as they only consider node features and nodewise positional encodings (PEs). To overcome this limitation, we introduce a novel NI model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each iteration. Conducted experiments demonstrate that the proposed model can recommend neighborhood operations that outperform conventional versions for the preference ranking problem (PRP) with a performance in the 99th percentile. We also extend the proposal to two well-known problems: the traveling salesman problem and the graph partitioning problem (GPP), recommending operations in the 98th and 97th percentile, respectively.

Previous works have shown that studying the characteristics of the Quadratic Assignment Problem (QAP) is a crucial step in gaining knowledge that can be used to design tailored meta-heuristic algorithms. One way to analyze the characteristics of the QAP is to decompose its objective function into a linear combination of orthogonal sub-functions that can be independently studied. In particular, this work focuses on a decomposition approach that has attracted considerable attention: the Elementary Landscape Decomposition (ELD).

Problems with solutions represented by permutations are very prominent in combinatorial optimization. Thus, in recent decades, a number of evolutionary algorithms have been proposed to solve them, and among them, those based on probability models have received much attention. In that sense, most efforts have focused on introducing algorithms that are suited for solving ordering/ranking nature problems. However, when it comes to proposing probability-based evolutionary algorithms for assignment problems, the works have not gone beyond proposing simple and in most cases univariate models. In this paper, we explore the use of Doubly Stochastic Matrices (DSM) for optimizing matching and assignment nature permutation problems. To that end, we explore some learning and sampling methods to efficiently incorporate DSMs within the picture of evolutionary algorithms. Specifically, we adopt the framework of estimation of distribution algorithms and compare DSMs to some existing proposals for permutation problems. Conducted preliminary experiments on instances of the quadratic assignment problem validate this line of research and show that DSMs may obtain very competitive results, while computational cost issues still need to be further investigated.

Global random search algorithms are characterized by using probability distributions to optimize problems. Among them, generative methods iteratively update the distributions by using the observations sampled. For instance, this is the case of the well-known Estimation of Distribution Algorithms. Although successful, this family of algorithms iteratively adopts numerical methods for estimating the parameters of a model or drawing observations from it. This is often a very time-consuming task, especially in permutation-based combinatorial optimization problems. In this work, we propose using a generative method, under the model-based gradient search framework, to optimize permutation-coded problems and address the mentioned computational overheads. To that end, the Plackett–Luce model is used to define the probability distribution on the search space of permutations. Not limited to that, a parameter-free variant of the algorithm is investigated. Conducted experiments, directed to validate the work, reveal that the gradient search scheme produces better results than other analogous competitors, reducing the computational cost and showing better scalability.

In the field of optimization and machine learning, the statistical assessment of results has played a key role in conducting algorithmic performance comparisons. Classically, null hypothesis statistical tests have been used. However, recently, alternatives based on Bayesian statistics have shown great potential in complex scenarios, especially when quantifying the uncertainty in the comparison. In this work, we delve deep into the Bayesian statistical assessment of experimental results by proposing a framework for the analysis of several algorithms on several problems/instances. To this end, experimental results are transformed to their corresponding rankings of algorithms, assuming that these rankings have been generated by a probability distribution (defined on permutation spaces). From the set of rankings, we estimate the posterior distribution of the parameters of the studied probability models, and several inferences concerning the analysis of the results are examined. Particularly, we study questions related to the probability of having one algorithm in the first position of the ranking or the probability that two algorithms are in the same relative position in the ranking. Not limited to that, the assumptions, strengths, and weaknesses of the models in each case are studied. To help other researchers to make use of this kind of analysis, we provide a Python package and source code implementation athttps://zenodo.org/record/6320599.

Handling nonlinear constraints in continuous optimization is challenging, and finding a feasible solution is usually a difficult task. In the past few decades, various techniques have been developed to deal with linear and nonlinear constraints. However, reaching feasible solutions has been a challenging task for most of these methods. In this article, we adopt the framework of estimation of distribution algorithms (EDAs) and propose a new algorithm (EDA++) equipped with some mechanisms to deal with nonlinear constraints. These mechanisms are associated with different stages of the EDA, including seeding, learning, and mapping. It is shown that, besides increasing the quality of the solutions in terms of objective values, the feasibility of the final solutions is guaranteed if an initial population of feasible solutions is seeded to the algorithm. The EDA with the proposed mechanisms is applied to two suites of benchmark problems for constrained continuous optimization and its performance is compared with some state-of-the-art algorithms and constraint-handling methods. Conducted experiments confirm the speed, robustness, and efficiency of the proposed algorithm in tackling various problems with linear and nonlinear constraints.

Since their introduction, Estimation of Distribution Algorithms (EDAs) have proved to be very competitive algorithms to solve many optimization problems. However, despite recent developments, in the case of permutation-based combinatorial optimization problems, there are still many aspects that deserve further research. One of them is the influence of the codification employed to represent the solutions on the overall performance of the algorithm. When considering classical EDAs, optimizing permutation problems is challenging, and specific mechanisms are needed to hold the restrictions associated with the permutation nature of solutions.In this paper, in addition to the permutation-vector codification, we investigate alternative representations to describe solutions of permutation problems in the context of EDAs. In order to evaluate their influence, we adopted a classical EDA and conducted an experimental study on two different permutation problems and representations for codifying solutions. The results revealed a narrow relationship between the type of combinatorial problem optimized and the selected representation used to codify its solutions. Moreover, the results point out that choosing the appropriate representation to codify solutions of the given permutation problem is critical for the performance of the algorithm.

Network Function Virtualization (NFV) introduces a new network architecture framework that evolves network functions, traditionally deployed over dedicated equipment, to software implementations that run on general-purpose hardware. One of the main challenges for deploying NFV is the optimal resource placement of demanded network services in the NFV infrastructure. The virtual network function placement and network embedding can be formulated as a mathematical optimization problem concerned with a set of feasibility constraints that express the restrictions of the network infrastructure and the services contracted. This problem has been reported to be NP-hard, as a result most of the optimization work carried out in the area has focused on designing heuristic and metaheuristic algorithms. Nevertheless, in highly constrained problems, as in this case, inferring a competitive heuristic can be a daunting task that requires expertise. Consequently, an interesting solution is the use of Reinforcement Learning to model an optimization policy. The work presented here extends the Neural Combinatorial Optimization theory by considering constraints in the definition of the problem. The resulting agent is able to learn placement decisions by exploring the NFV infrastructure with the aim of minimizing the overall power consumption. The experiments conducted demonstrate that when the proposed strategy is also combined with heuristics, highly competitive results are achieved using relatively simple algorithms.

The linear ordering problem (LOP) is one of the classical NP-Hard combinatorial optimization problems. Motivated by the difficulty of solving it up to optimality, in recent decades a great number of heuristic and meta-heuristic algorithms have been proposed. Despite the continuous work on this problem, there is still room nowadays for designing strategies that beat the state-of-the-art algorithms, and take a step forward in terms of the quality of the obtained solutions.In this paper, two novel schemes are presented. The first algorithm consists of an iterated local search algorithm that carries out an organized exploration of the search space. The second scheme is an extension of the previous algorithm that, based on the properties of the LOP, proposes an exact procedure that allows us to improve the quality of the solutions systematically. Conducted experiments on one of the hardest LOP benchmarks (xLOLIB) show that 77 new best results were found out of 78 instances. The described strategies also provide innovative ideas for developing more advanced algorithms for solving the LOP.

In the last decade, many works in combinatorial optimisation have shown that, due to the advances in multi-objective optimisation, the algorithms from this field could be used for solving single-objective problems as well. In this sense, a number of papers have proposed multi-objectivising single-objective problems in order to use multi-objective algorithms in their optimisation. In this article, we follow up this idea by presenting a methodology for multi-objectivising combinatorial optimisation problems based on elementary landscape decompositions of their objective function. Under this framework, each of the elementary landscapes obtained from the decomposition is considered as an independent objective function to optimise. In order to illustrate this general methodology, we consider four problems from different domains: the quadratic assignment problem and the linear ordering problem (permutation domain), the 0-1 unconstrained quadratic optimisation problem (binary domain), and the frequency assignment problem (integer domain). We implemented two widely known multi-objective algorithms, NSGA-II and SPEA2, and compared their performance with that of a single-objective GA. The experiments conducted on a large benchmark of instances of the four problems show that the multi-objective algorithms clearly outperform the single-objective approaches. Furthermore, a discussion on the results suggests that the multi-objective space generated by this decomposition enhances the exploration ability, thus permitting NSGA-II and SPEA2 to obtain better results in the majority of the tested instances.

The trade-off between diversification and intensification has been investigated recurrently in the field of evolutionary computation. Proof of this is the numerous approaches that have been devoted to finding a balance in the diversification-intensification behavior of algorithms. Despite the large amount of work on this topic, dynamically adjusting such behavior is still difficult and depends on the algorithm at hand. In this paper, we focus on estimation of distribution algorithms (EDAs). Usually, research on EDAs mainly focuses on the design of probability models that either represent as best as possible the characteristics of the problem, or accurately fit the domain of the solutions. In this work, we propose implementing mixtures of probability models that permit the dynamic adjustment of the scope of the EDA. Particularly, we design a mixture model that combines two unimodal Thurstone family probability models: the Plackett-Luce model and the Bradley-Terry model. The first model tends to concentrate the probability around the mode, while the second spreads the probability more. Using a homogeneity measure on the population of solutions, we dynamically decide the ratio of solutions to sample from each model. Performed experiments on the linear ordering problem demonstrate that this research line is definitively promising.

In the field of evolutionary computation, it is usual to generate artificial benchmarks of instances that are used as a test-bed to determine the performance of the algorithms at hand. In this context, a recent work on permutation problems analyzed the implications of generating instances uniformly at random (u.a.r.) when building those benchmarks. Particularly, the authors analyzed instances as rankings of the solutions of the search space sorted according to their objective function value. Thus, two instances are considered equivalent when their objective functions induce the same ranking over the search space. Based on the analysis, they suggested that, when some restrictions hold, the probability to create easy rankings is higher than creating difficult ones. In this paper, we continue on that research line by adopting the framework of local search algorithms with the best improvement criterion. Particularly, we empirically analyze, in terms of difficulty, the instances (rankings) created u.a.r. of three popular problems: Linear Ordering Problem, Quadratic Assignment Problem and Flowshop Scheduling Problem. As the neighborhood system is critical for the performance of local search algorithms three different neighborhood systems have been considered: swap, interchange and insert. Conducted experiments reveal that (1) by sampling the parameters uniformly at random we obtain instances with a non-uniform distribution in terms of difficulty, (2) the distribution of the difficulty strongly depends on the pair problem-neighborhood considered, and (3) given a problem, the distribution of the difficulty seems to depend on the smoothness of the landscape induced by the neighborhood and on its size.

The ftowshop scheduling problem (FSP) has been widely studied in the last decades, both in the single objective as well as in the multi-objective scenario. Besides, due to the real-world considerations on scheduling problems, the concern regarding sequence-dependent setup times has emerged. In this paper, we present a decomposition-based iterated local search algorithm (MOLS/D) to deal with the multi-objective sequence-dependent setup times permutation FSP. In order to demonstrate the validity of the proposed algorithm, we have conducted an experimental study on a set of 220 benchmark instances minimizing the criteria makespan and total weighted tardiness. The results, according to various performance metrics and statistical analysis, show that MOLS/D significantly outperforms a tailored MOEA/D variant and the best-known reference sets from the literature. Thus, we have established a state-of-the-art approach for the problem considered.

Permutation problems are combinatorial optimization problems whose solutions are naturally codified as permutations. Due to their complexity, motivated principally by the factorial cardinality of the search space of solutions, they have been a recurrent topic for the artificial intelligence and operations research community. Recently, among the vast number of metaheuristic algorithms, new advances on estimation of distribution algorithms (EDAs) have shown outstanding performance when solving some permutation problems. These novel EDAs implement distance-based exponential probability models such as the Mallows and Generalized Mallows models. In this article, we present a Matlab package, perm_mateda, of estimation of distribution algorithms on permutation problems, which has been implemented as an extension to the Mateda-2.0 toolbox of EDAs. Particularly, we provide implementations of the Mallows and Generalized Mallows EDAs under the Kendall’s-τ, Cayley, and Ulam distances. In addition, four classical permutation problems have also been implemented: Traveling Salesman Problem, Permutation Flowshop Scheduling Problem, Linear Ordering Problem, and Quadratic Assignment Problem.

Estimation of Distribution Algorithms have proved to be very competitive for solving combinatorial and continuous optimisation problems. However, there are problems for which they have not been extensively developed: we refer to constrained optimisation problems. Existing proposals approach these problems by (i) modifying the sampling strategy of the probabilistic model to allow feasible solutions or (ii) adopting general approaches used in the context of heuristic optimisation such as penalisation. Nonetheless, from a theoretical point of view, little progress have been given in the context of EDAs when developing algorithms designed specifically to solve constrained problems. In this paper, we propose developing EDAs by introducing probability models defined exclusively on the space of feasible solutions. In this sense, we give a first approach by taking the Graph Partitioning Problem (GPP) as a case of study, and present a probabilistic model defined exclusively on the feasible region of solutions: a square lattice probability model. The experiments conducted on a benchmark of 22 artificial instances confirm the effectiveness of the proposal in terms of quality of solutions and execution time.

In evolutionary computation, it is common practice to use sets of instances as test-beds for evaluating and comparing the performance of new optimisation algorithms. In some cases, real-world instances are available, and, thus, they are used to constitute the experimental benchmark. Unfortunately, this is not the general case. Due to the difficulties for obtaining real-world instances, or because the optimisation problems defined in the literature are not exactly as those defined in the industry, practitioners are forced to create artificial instances. In this paper, we study some aspects related to the random generation of artificial instances. Particularly, we elaborate on the assumption that states that sampling uniformly at random in the space of parameters is equivalent to sampling uniformly at random in the space of functions. Illustrated with some experiments, we prove that for some type of algorithms this assumption does not hold.

In space environment, perturbations make the spacecraft lose its predefined orbit in space. One of these undesirable changes is the in-plane rotation of space orbit, denominated as orbital precession. To overcome this problem, one option is to correct the orbit direction by employing low-thrust trajectories. However, in addition to the orbital perturbation acting on the spacecraft, a number of parameters related to the spacecraft and its propulsion system must be optimized. This article lays out the trajectory optimization of orbital precession missions using Evolutionary Algorithms (EAs). In this research, the dynamics of spacecraft in the presence of orbital perturbation is modeled. The optimization approach is employed based on the parametrization of the problem according to the space mission. Numerous space mission cases have been studied in low and middle Earth orbits, where various types of orbital perturbations are acted on spacecraft. Consequently, several EAs are employed to solve the optimization problem. Results demonstrate the practicality of different EAs, along with comparing their convergence rates. With a unique trajectory model, EAs prove to be an efficient, reliable and versatile optimization solution, capable of being implemented in conceptual and preliminary design of spacecraft for orbital precession missions.

Advances in evolutionary computation have demonstrated that Evolutionary Algorithms (EAs) proposed in this area are a solid alternative for solving combinatorial and continuous optimization problems. Despite their success in innumerable real-world scenarios, EAs depend on a set of input parameters that characterize their performance and need to be adjusted. In fact, identifying and setting the most appropriate parameters for an EA is a complex task, which, in some cases, can be as difficult as the optimization problem at hand. Recently, parameter tuning has attracted the interest of the research community, designing and proposing techniques that (1) help the algorithm to perform to its best, and (2), indirectly, make fairer comparisons of different methods. In this manuscript, we propose a novel offline parameter tuning algorithm based on Bayesian Optimization, a sequential design strategy for global optimization. In order to illustrate the validity of the proposed method, we considered as a case of study the Hybrid Kernel EDA, an EA that is characterized by 6 parameters. We ran the algorithm with the parameters tuned by means of Bayesian Optimization, and compared the results with those obtained by setting the parameters by hand (using some prior knowledge). Experiments were carried out on a benchmark of 60 instances of the permutation flowshop scheduling problem. Experimental results show that, in general, Hybrid Kernel EDA obtains better results when using the parameters tuned by means of Bayesian Optimization.

Recently, distance-based exponential probability models have demonstrated their validity in the context of estimation of distribution algorithms when solving permutationbased combinatorial optimisation problems. However, despite their successful performance, some of these models are unimodal, and, therefore, they might not be flexible enough to model the different modalities that may be represented in heterogeneous populations. In this paper, we address the particular case of the Generalized Mallows models under the Cayley distance, and propose mixtures of these models in the context of estimation of distribution algorithms. In order to evaluate their competitiveness, we considered the quadratic assignment problem as a case of study, and conducted experiments over a set of 90 instances for four different configurations of mixtures. Results reveal that the EDA with mixtures is able to outperform the Generalized Mallows EDA, especially in large instances.

Recently, distance-based exponential probability models, such as Mallows and Generalized Mallows, have demonstrated their validity in the context of estimation of distribution algorithms (EDAs) for solving permutation problems. However, despite their successful performance, these models are unimodal, and therefore, they are not flexible enough to accurately model populations with solutions that are very sparse with regard to the distance metric considered under the model.

Recently, probability models on rankings have been proposed in the field of estimation of distribution algorithms in order to solve permutation-based combinatorial optimisation problems. Particularly, distance-based ranking models, such as Mallows and Generalized Mallows under the Kendall's-τ distance, have demonstrated their validity when solving this type of problems. Nevertheless, there are still many trends that deserve further study. In this paper, we extend the use of distance-based ranking models in the framework of EDAs by introducing new distance metrics such as Cayley and Ulam. In order to analyse the performance of the Mallows and Generalized Mallows EDAs under the Kendall, Cayley and Ulam distances, we run them on a benchmark of 120 instances from four well known permutation problems. The conducted experiments showed that there is not just one metric that performs the best in all the problems. However, the statistical test pointed out that Mallows-Ulam EDA is the most stable algorithm among the studied proposals.

The aim of this paper is two-fold. First, we introduce a novel general estimation of distribution algorithm to deal with permutation-based optimization problems. The algorithm is based on the use of a probabilistic model for permutations called the generalized Mallows model. In order to prove the potential of the proposed algorithm, our second aim is to solve the permutation flowshop scheduling problem. A hybrid approach consisting of the new estimation of distribution algorithm and a variable neighborhood search is proposed. Conducted experiments demonstrate that the proposed algorithm is able to outperform the state-of-the-art approaches. Moreover, from the 220 benchmark instances tested, the proposed hybrid approach obtains new best known results in 152 cases. An in-depth study of the results suggests that the successful performance of the introduced approach is due to the ability of the generalized Mallows estimation of distribution algorithm to discover promising regions in the search space.

Estimation of distribution algorithms are known as powerful evolutionary algorithms that have been widely used for diverse types of problems. However, they have not been extensively developed for permutation-based problems. Recently, some progress has been made in this area by introducing probability models on rankings to optimize permutation domain problems. In particular, the Mallows model and the Generalized Mallows model demonstrated their effectiveness when used with estimation of distribution algorithms. Motivated by these advances, in this paper we introduce a Thurstone order statistics model, called Plackett-Luce, to the framework of estimation of distribution algorithms. In order to prove the potential of the proposed algorithm, we consider two different permutation problems: the linear ordering problem and the flowshop scheduling problem. In addition, the results are compared with those obtained by the Mallows and the Generalized Mallows proposals. Conducted experiments demonstrate that the Plackett-Luce model is the best performing model for solving the linear ordering problem. However, according to the experimental results, the Generalized Mallows model turns out to be very robust obtaining very competitive results for both problems, especially for the permutation flowshop scheduling problem.

Estimation of Distribution Algorithms are a class of evolutionary algorithms characterized by the use of probabilistic models. These algorithms have been applied successfully to a wide set of artificial and real-world problems, achieving competitive results in most scenarios. Nevertheless, there are some problems whose solutions can be naturally represented as a permutation, for which EDAs have not been extensively developed. Although some work has been done in this area, most of the approaches are adaptations of EDAs designed for problems based on integer or real domains, and only a few algorithms have been specifically designed to deal with permutation-based problems. In this paper, we present an EDA that learns probability distributions over permutations. Particularly, our approach is based on the use of k-order marginals. In addition, we carry out some preliminary experiments over classical permutation-based problems in order to study the performance of the proposed k-order marginals EDA.