查看更多>>摘要：Abstract Solving an optimization problem with local search algorithms consists of evolving a solution by means of an evaluation function, which is usually directly derived from the objective function of the problem. The resolution difficulties appear when the fitness landscape naturally induced by the problem instance is not perfectly exploitable, has a certain level of ruggedness, and therefore has many local optima. We propose here to shift the problem of searching a solution, from searching an evaluation function that maximizes the efficiency of the corresponding local search algorithm. In particular, we propose an evolution strategy scheme designed to evolve fitness functions and their corresponding fitness landscapes. The purpose is to generate a local search algorithm guided by an evolved fitness function specifically dedicated to tackling the problem instance to solve. Here, we focus on hill‐climbing algorithms and NK landscapes and show that such a strategy can be efficient to generate relevant search algorithms whose components are not?problem‐specific.
查看更多>>摘要：Abstract In this work, we study partial neighborhood local search (PNLS) techniques, which consist of adaptive walks where moves are chosen in a random subset of the current solution neighborhood. PNLSs balance between intensification and diversification is mainly determined by its single parameter λ designing the subset size. We analyze and discuss three PNLSs variants, using the abstraction of several combinatorial optimization problems into fitness landscapes: NK landscapes, Unconstrained Binary Quadratic Programming, Flow‐shop scheduling, and Quadratic Assignment. Our empirical study first analyses the structure of these landscapes through indicators. Then, we perform a parameter study of PNLSs for two computational budgets to study the impact of the sample size on the balance between intensification and diversification on different landscapes. Moreover, these experiments allow us to set an appropriate parameter value to compare the ability of PNLSs to reach good‐quality solutions accurately. Finally, we compare PNLS variants with two classical metaheuristics, identifying links between landscape characteristics and algorithms?behavior.
查看更多>>摘要：Abstract Grammar‐based automatic algorithm design has been shown to generate stochastic local search algorithms that compete with or outperform state‐of‐the‐art methods. In such systems, algorithms are divided in components and a grammar is used to describe how to properly combine the components to create a working algorithm. In our approach, the grammar is converted into parameters and an automatic parameter configuration tool is used to find the best configuration. This approach allows us to consider and hybridize different metaheuristic templates producing combinations never tested before, but this flexibility leads to a very large configuration space to explore. Is such complexity really needed to achieve state‐of‐the‐art performance? In this paper, we investigate this question by creating grammars that allow the hybridization of stochastic local search algorithms at most two, one, or zero times. We use these grammars to generate algorithms for the three most studied objectives of the permutation flowshop problem: makespan, total completion time, and total tardiness. The generated algorithms are compared using benchmark sets from the literature as well as a quantitative measure of algorithm complexity using a metric based on concept directed acyclic graphs. The experiments show that our system tends to generate hybridized algorithms only when they can provide a substantial performance improvement. On the contrary, when such algorithms do not improve performance, the system generates simpler algorithms regardless of the grammar?used.
查看更多>>摘要：Abstract Scheduling problems are a subclass of combinatorial problems consisting of a set of tasks/activities/jobs to be processed by a set of resources usually to minimize a time criterion. Some optimization methods used to solve these problems are hybridized with knowledge discovery techniques to extract information during the optimization process and enhance it. However, most of these hybrid techniques are custom‐designed and lack generalization. In this paper, a module for knowledge extraction in Stochastic Local Searches is designed, aiming to be problem independent and plugged into optimization methods that relies on multiple Stochastic Local Search replications. The objective is to prune parts of the search space for which the exploration is likely to lead to poor solutions. This is performed through the extraction of high‐quality patterns occurring in locally optimal solutions. Benchmarked on two well‐known scheduling problems, the Job‐shop Problem and the Resource Constrained Project Scheduling Problem, the results show both a speed up in the convergence and the reaching of better local optima?solutions.
查看更多>>摘要：Abstract The label printing problem (LPP) arises in the printing industry, where we have a set of labels that require printing. Each one has different demands and must be printed using a single template. The number of labels we can allocate in a template is a fixed one, and the number of templates varies in a small range of different sizes. The goal of the LPP is to design templates to meet the demands for the labels while minimizing the percentage of material wasted. In each grid, the need for each printed cover must be met to facilitate label management. To deal with LPP, we used two known metaheuristics: a threshold accepting and a tabu search. These heuristics, with the aid of a Hill climbing double neighborhood, improved the results?significantly.
查看更多>>摘要：Abstract Given binary matrix A$A$, the term A(π)$A^{(\pi )}$ refers to the matrix obtained by permuting the columns of A$A$ according to permutation π$\pi$. A 1‐block in a binary matrix is any maximal sequence of consecutive 1s situated on the same row. Given binary matrix A$A$, consecutive block minimization (CBM) is a combinatorial optimization problem that seeks a permutation π$\pi$ of A$A$ columns such that the number of 1‐blocks in A(π)$A^{(\pi )}$ is minimum. Since CBM is NP‐hard, we solve it by iterating local search where the neighborhood is exponential in the instance size and is always constructed in the vicinity of the best current solution. Seeking a local optimum in the exponential neighborhood amounts to solving a small traveling salesman problem (TSP). Instead, we obtain a good near local optimal solution using an implementation of Lin–Kernighan heuristic. Our method is compared with a recently published iterated local search metaheuristic as well as with two TSP solvers. The comparison shows that the proposed method provides better quality?solutions.
Juan Milán‐GarcíaNuria Rueda‐LópezJaime De Pablo‐Valenciano
28页
查看更多>>摘要：Abstract This paper has reviewed the international literature on the explaining factors of efficiency of local governments from 1990 to June 2019. The main objective of this work is to explore the dynamics of the development of this line of research, not only to find out the terminology preferences that have dominated the pre‐ and post‐crisis period in this field but also to identify the latest worldwide research trends. For this purpose, a bibliometric and cluster analysis by fractional accounting has been carried out. The principal result of this article is twofold. First, during the whole period 1990–2019, the ranking of the most used terms is dominated by the keywords of the publications in the second subperiod 2008–2019. Second, the analysis of the latest trends, which has been extended until June 2021, shows that in recent years, the study of the determinants of local government efficiency has revolved around concepts related to environmental issues and new forms of local management.
查看更多>>摘要：Abstract The increasing demand for electric power is an established trend in China, of which coal power accounts for a large proportion. This paper proposes an inventory hub location model considering multi‐type coal to minimize the total transportation and inventory cost in a multi‐coal‐power supply chain. A second‐order cone programming method is adopted to convert the original model. The exact solutions of the small‐scale real case show that the model can greatly reduce the total costs by CPLEX. For real‐world large‐scale cases, a customized greedy randomized adaptive search simulated annealing algorithm is devised and tested to obtain near‐optimal solutions within a reasonable time. The research has strong practical guiding significance for the management of the thermal coal supply chain.
NSTL
Wiley