Heuristic Optimizationhttp://hdl.handle.net/20.500.11824/112022-12-09T03:28:38Z2022-12-09T03:28:38ZA General Framework Based on Walsh Decomposition for Combinatorial Optimization ProblemsUnanue, I.Merino, M.Lozano, J.A.http://hdl.handle.net/20.500.11824/15212022-09-09T22:20:54Z2021-01-01T00:00:00ZA General Framework Based on Walsh Decomposition for Combinatorial Optimization Problems
Unanue, I.; Merino, M.; Lozano, J.A.
In this paper we pursue the use of the Fourier transform for a general analysis of combinatorial optimization problems. While combinatorial optimization problems are defined by means of different notions like weights in a graph, set of numbers, distance between cities, etc., the Fourier transform allows to put all of them in the same framework, the Fourier coefficients. This permits its comparison looking for similarities and differences. Particularly, the Walsh transform has recently been used over pseudo-boolean functions in order to design new surrogate models in the black-box scenario and to generate new algorithms for the linkage discovery problem, among others, presenting very promising results. In this paper we focus on binary problems and the Walsh transform. After presenting the Walsh decomposition and some main properties, we compute the transform of the Unconstrained Binary Quadratic Problem and several particular cases of this problem such as the Max-Cut Problem and the Number Partitioning Problem. The obtained Walsh coefficients not only reinforce the similarities and differences among the problems which are known in the literature, but given a set of Walsh coefficients we can say whether or not they are produced by any of the problems analyzed. Finally, a geometrical interpretation of the space of Walsh coefficients with maximum order 2 and the subspace of each analyzed problem is presented.
2021-01-01T00:00:00ZA mathematical analysis of EDAs with distance-based exponential modelsUnanue, I.Merino, M.Lozano, J.A.http://hdl.handle.net/20.500.11824/15202022-09-09T22:20:53Z2022-09-01T00:00:00ZA mathematical analysis of EDAs with distance-based exponential models
Unanue, I.; Merino, M.; Lozano, J.A.
Estimation of Distribution Algorithms have been successfully used to solve permutation-based Combinatorial Optimization Problems. In this case, the algorithms use probabilistic models specifically designed for codifying probability distributions over permutation spaces. One class of these probability models are distance-based exponential models, and one example of this class is the Mallows model. In spite of its practical success, the theoretical analysis of Estimation of Distribution Algorithms for permutation-based Combinatorial Optimization Problems has not been developed as extensively as it has been for binary problems. With this motivation, this paper presents a first mathematical analysis of the convergence behavior of Estimation of Distribution Algorithms based on Mallows models. The model removes the randomness of the algorithm in order to associate a dynamical system to it. Several scenarios of increasing complexity with different fitness functions and initial probability distributions are analyzed. The obtained results show: a) the strong dependence of the final results on the initial population, and b) the possibility to converge to non-degenerate distributions even in very simple scenarios, which has not been reported before in the literature.
2022-09-01T00:00:00ZPyDDRBG: A Python framework for benchmarking and evaluating static and dynamic multimodal optimization methodsAhrari, A.Elsayed, S.Sarker, R.Essam, D.Coello, C.A.http://hdl.handle.net/20.500.11824/14522022-03-16T23:19:42Z2022-01-01T00:00:00ZPyDDRBG: A Python framework for benchmarking and evaluating static and dynamic multimodal optimization methods
Ahrari, A.; Elsayed, S.; Sarker, R.; Essam, D.; Coello, C.A.
PyDDRBG is a Python framework for generating tunable test problems for static and dynamic multimodal optimization. It allows for quick and simple generation of a set of predefined problems for non-experienced users, as well as highly customized problems for more experienced users. It easily integrates with an arbitrary optimization method. It can calculate the optimization performance when measured according to the robust mean peak ratio. PyDDRBG is expected to advance the fields of static and dynamic multimodal optimization by providing a common platform to facilitate the numerical analysis, evaluation, and comparison in these fields.
2022-01-01T00:00:00ZPreference incorporation into many-objective optimization: An Ant colony algorithm based on interval outrankingRivera, G.Coello, C.A.Cruz-Reyes, L.Fernandez, E.R.Gomez-Santillan, C.Rangel-Valdez, N.http://hdl.handle.net/20.500.11824/14202022-02-04T00:19:24Z2022-03-01T00:00:00ZPreference incorporation into many-objective optimization: An Ant colony algorithm based on interval outranking
Rivera, G.; Coello, C.A.; Cruz-Reyes, L.; Fernandez, E.R.; Gomez-Santillan, C.; Rangel-Valdez, N.
In this paper, we enriched Ant Colony Optimization (ACO) with interval outranking to develop a novel multi-objective ACO optimizer to approach problems with many objective functions. This proposal is suitable if the preferences of the Decision Maker (DM) can be modeled through outranking relations. The introduced algorithm (Interval Outranking-based ACO, IO-ACO) is the first ant-colony optimizer that embeds an outranking model to bear vagueness and ill-definition of the DM's preferences. This capacity is the most differentiating feature of IO-ACO because this issue is highly relevant in practice. IO-ACO biases the search towards the Region of Interest (RoI), the privileged zone of the Pareto frontier containing the solutions that better match the DM's preferences. Two widely studied benchmarks were utilized to measure the efficiency of IO-ACO, i.e., the DTLZ and WFG test suites. Accordingly, IO-ACO was compared with four competitive multi-objective optimizers: The Indicator-based Many-Objective ACO, the Multi-objective Evolutionary Algorithm Based on Decomposition, the Reference Vector-Guided Evolutionary Algorithm using Improved Growing Neural Gas, and the Indicator-based Multi-objective Evolutionary Algorithm with Reference Point Adaptation. The numerical results show that IO-ACO approximates the RoI better than leading metaheuristics based on approximating the Pareto frontier alone.
2022-03-01T00:00:00Z