One of the main problems in the application of a Particle Swarm optimization in combinatorialoptimization problems, especially in routing type problems like the Traveling Salesman Problem, the Vehicle Routing Problem...
详细信息
ISBN:
(数字)9783642371981
ISBN:
(纸本)9783642371981
One of the main problems in the application of a Particle Swarm optimization in combinatorialoptimization problems, especially in routing type problems like the Traveling Salesman Problem, the Vehicle Routing Problem, etc., is the fact that the basic equation of the Particle Swarm optimization algorithm is suitable for continuous optimization problems and the transformation of this equation in the discrete space may cause loose of information and may simultaneously need a large number of iterations and the addition of a powerful local search algorithm in order to find an optimum solution. In this paper, we propose a different way to calculate the position of each particle which will not lead to any loose of information and will speed up the whole procedure. this was achieved by replacing the equation of positions with a novel procedure that includes a Path Relinking Strategy and a different correspondence of the velocities withthe paththat will follow each particle. the algorithm is used for the solution of the Capacitated Vehicle Routing Problem and is tested in the two classic set of benchmark instances from the literature with very good results.
Many applications involve matching two graphs in order to identify their common features and compute their similarity. In this paper, we address the problem of computing a graph similarity measure based on a multivale...
详细信息
ISBN:
(纸本)3540331786
Many applications involve matching two graphs in order to identify their common features and compute their similarity. In this paper, we address the problem of computing a graph similarity measure based on a multivalent graph matching and which is generic in the sense that other well known graph similarity measures can be viewed as special cases of it. We propose and compare two different kinds of algorithms: an Ant Colony optimization based algorithm and a Reactive Search. We compare the efficiency of these two algorithms on two different kinds of difficult graph matching problems and we show that they obtain complementary results.
We present a hybrid evolutionary algorithm for the graph coloring problem (Evocol). Evocol is based on two simple-but-effective ideas. First, we use an enhanced crossover that collects the best color classes out of mo...
详细信息
ISBN:
(纸本)9783642010088
We present a hybrid evolutionary algorithm for the graph coloring problem (Evocol). Evocol is based on two simple-but-effective ideas. First, we use an enhanced crossover that collects the best color classes out of more than two parents;the best color classes are selected using a ranking based on both class fitness and class size. We also introduce a simple method of using distances to assure the population diversity: at each operation that inserts an individual into the population or that eliminated an individual from the population, Evocol tries to maintain the distances between the remaining individuals as large as possible. the results of Evocol match the best-known results from the literature on almost all difficult DIMACS instances (a new solution is also reported for a very large graph). Evocol obtains these performances with a success rate of at least 50%.
the Shortest Common Supersequence Problem (SCSP) is a well-known hard combinatorialoptimization problem that formalizes many real world problems. this paper presents a novel randomized search strategy, called probabi...
详细信息
ISBN:
(纸本)9783540716143
the Shortest Common Supersequence Problem (SCSP) is a well-known hard combinatorialoptimization problem that formalizes many real world problems. this paper presents a novel randomized search strategy, called probabilistic beam search (PBS), based on the hybridization between beam search and greedy constructive heuristics. PBS is competitive (and sometimes better than) previous state-of-the-art algorithms for solving the SCSP. the paper describes PBS and provides an experimental analysis (including comparisons with previous approaches) that demonstrate its usefulness.
combinatorialoptimization problems can involve computationaly expensive fitness function, making their resolution challenging. Surrogate models are one of the effective techniques used to solve such black-box problem...
详细信息
ISBN:
(纸本)9783031577116;9783031577123
combinatorialoptimization problems can involve computationaly expensive fitness function, making their resolution challenging. Surrogate models are one of the effective techniques used to solve such black-box problems by guiding the search towards potentially good solutions. In this paper, we focus on the use of surrogate based on multinomial approaches, particularly based onWalsh functions, to tackle pseudo-Boolean problems. Although this approach can be effective, a potential drawback is the growth of the polynomial expansion with problem dimension. We introduce a method for analyzing real-world combinatorial black-box problems defined through numerical simulation. this method combines Walsh spectral analysis and polynomial regression. Consequently, we propose a sparse surrogate model that incorporates selected, relevant terms and is simpler to optimize. To demonstrate our approach, we apply it to the bus stop spacing problem, an exemplary combinatorial pseudo-Boolean challenge.
Graphs are powerful and versatile data structures, useful to represent complex and structured information of interest in various fields of science and engineering. We present a system, called EvoGeneS, based on an evo...
详细信息
optimization methods based on complete neighborhood exploration such as Tabu Search are impractical against large neighborhood problems. Strategies of candidate list propose a solution to reduce the neighborhood explo...
详细信息
ISBN:
(纸本)9783540786030
optimization methods based on complete neighborhood exploration such as Tabu Search are impractical against large neighborhood problems. Strategies of candidate list propose a solution to reduce the neighborhood exploration complexity. We propose in this paper a generic Tabu Search algorithm using adaptive candidate list strategy based on two alternate candidate lists. Each candidate list strategy corresponds to a given search phase: intensification or diversification. the optimization algorithm uses a Tabu list containing the variables causing loops. the paper proposes a classification of Tabu tenure managing in the literature and presents a new and original Tabu tenure adaptation mechanism. the generic method is tested on the k-coloring problem and compared with some best methods published in the literature. Obtained results show the competitiveness of the method.
the quadratic multiple knapsack problem is an extension of the well known 0/1 multiple knapsack problem. In the quadratic multiple knapsack problem, profit values are associated not only with individual objects but al...
详细信息
ISBN:
(纸本)9783540716143
the quadratic multiple knapsack problem is an extension of the well known 0/1 multiple knapsack problem. In the quadratic multiple knapsack problem, profit values are associated not only with individual objects but also with pairs of objects. Profit value associated with a pair of objects is added to the overall profit if both objects of the pair belong to the same knapsack. Being an extension of the 0/1 multiple knapsack problem, this problem is also NP-Hard. In this paper, we have proposed a new steady-state grouping genetic algorithm for the quadratic multiple knapsack problem and compared our results with two recently proposed methods - a genetic algorithm and a stochastic hill climber. the results show the effectiveness of our approach.
this paper deals withthe design of improved construction heuristics and iterated local search for the Routing and Wavelength Assignment problem (RWA). Given a physical network and a set of communication requests, the...
详细信息
ISBN:
(纸本)9783540786030
this paper deals withthe design of improved construction heuristics and iterated local search for the Routing and Wavelength Assignment problem (RWA). Given a physical network and a set of communication requests, the static RWA deals withthe problem of assigning suitable paths and wavelengths to the requests. We introduce benchmark instances from the SND library to the RWA and argue that these instances are more challenging than previously used random instances. We analyze the properties of several instances in detail and propose an improved construction heuristic to handle 'problematic' instances. Our iterated local search finds the optimum for most instances.
the design of spacecraft trajectories for missions visiting multiple celestial bodies is here framed as a multi-objective bilevel optimization problem. A comparative study is performed to assess the performance of dif...
详细信息
ISBN:
(数字)9783319554532
ISBN:
(纸本)9783319554532;9783319554525
the design of spacecraft trajectories for missions visiting multiple celestial bodies is here framed as a multi-objective bilevel optimization problem. A comparative study is performed to assess the performance of different Beam Search algorithms at tackling the combinatorial problem of finding the ideal sequence of bodies. Special focus is placed on the development of a new hybridization between Beam Search and the Population-based Ant Colony optimization algorithm. An experimental evaluation shows all algorithms achieving exceptional performance on a hard benchmark problem. It is found that a properly tuned deterministic Beam Search always outperforms the remaining variants. Beam P-ACO, however, demonstrates lower parameter sensitivity, while offering superior worst-case performance. Being an anytime algorithm, it is then found to be the preferable choice for certain practical applications.
暂无评论