Catálogo de publicaciones - libros

We introduce a novel representation for the graph colouring problem, called the Integer Merge Model, which aims to reduce the time complexity of an algorithm. Moreover, our model provides useful information for guiding heuristics as well as a compact description for algorithms. To verify the potential of the model, we use it in dsatur , in an evolutionary algorithm, and in the same evolutionary algorithm extended with heuristics. An empiricial investigation is performed to show an increase in efficiency on two problem suites , a set of practical problem instances and a set of hard problem instances from the phase transition.

This paper addresses minimizing makespan by genetic algorithm (GA) for scheduling jobs with non-identical sizes on a single batch processing machine. We propose two different genetic algorithms based on different encoding schemes. The first one is a sequence based GA (SGA) that generates random sequences of jobs and applies the batch first fit (BFF) heuristic to group the jobs. The second one is a batch based hybrid GA (BHGA) that generates random batches of jobs and ensures feasibility through using knowledge of the problem. A pairwise swapping heuristic (PSH) based on the problem characteristics is hybridized with BHGA that has the ability of steering efficiently the search toward the optimal or near optimal schedules. Computational results show that BHGA performs considerably well compared with a modified lower bound and significantly outperforms the SGA and a simulated annealing (SA) approach addressed in literature. In comparison with a constructive heuristic named FFLPT, BHGA also shows its superiority.

We take a relation-algebraic view on the formulation of evolutionary algorithms in discrete search spaces. First, we show how individuals and populations can be represented as relations and formulate some standard mutation and crossover operators for this representation using relation-algebra. Evaluating a population with respect to their constraints seems to be the most costly step in one generation for many important problems. We show that the evaluation process for a given population can be sped up by using relation-algebraic expressions in the process. This is done by examining the evaluation of possible solutions for three of the best-known NP-hard combinatorial optimization problems on graphs, namely the vertex cover problem, the computation of maximum cliques, and the determination of a maximum independent set. Extending the evaluation process for a given population to the evaluation of the whole search space we get exact methods for the considered problems, which allow to evaluate the quality of solutions obtained by evolutionary algorithms.

In this paper, we present a scatter search algorithm for the well-known nurse scheduling problem (NSP). This problem aims at the construction of roster schedules for nurses taking both hard and soft constraints into account. The objective is to minimize the total preference cost of the nurses and the total penalty cost from violations of the soft constraints. The problem is known to be NP-hard. The contribution of this paper is threefold. First, we are, to the best of our knowledge, the first to present a scatter search algorithm for the NSP. Second, we investigate two different types of solution combination methods in the scatter search framework, based on four different cost elements. Last, we present detailed computational experiments on a benchmark dataset presented recently, and solve these problem instances under different assumptions. We show that our procedure performs consistently well under many different circumstances, and hence, can be considered as robust against case-specific constraints.

This paper proposes an evolutionary algorithm (EA) that is applied to the traveling salesman problem (TSP). Existing approximation methods to address the TSP known to be state-of-the-art heuristics almost exclusively utilize Lin-Kernighan local search (LKLS) and its variants. We propose an EA that does not use LKLS, and demonstrate that it is comparable with these heuristics even though it does not use them. The proposed EA uses edge assembly crossover (EAX) that is known to be an efficient and effective crossover for solving TSPs. We first propose a modified EAX algorithm that can be executed more efficiently than the original, which is 2–7 times faster. We then propose a selection model that can efficiently maintain population diversity at negligible computational cost. The edge entropy measure is used as an indicator of population diversity. The proposed method called EAX-1AB(ENT) is applied to TSP benchmarks up to instances of 13509 cities. Experimental results reveal that EAX-1AB(ENT) with a population of 200 can almost always find optimal solutions effectively in most TSP benchmarks up to instances of 5915 cities. In the experiments, a previously proposed EAs using EAX can find an optimal solution of usa13509 with reasonable computational cost due to the fast EAX algorithm proposed in this paper. We also demonstrate that EAX-1AB(ENT) is comparable to well-known LKLS methods when relatively small populations such as 30 are used.

As shown in recent researches, in a distribution system, ignoring routes when locating depots may overestimate the overall system cost. The Location Routing Problem (LRP) overcomes this drawback dealing simultaneously with location and routing decisions. This paper presents a memetic algorithm with population management (MA|PM) to solve the LRP with capacitated routes and depots. MA|PM is a very recent form of memetic algorithm in which the diversity of a small population of solutions is controlled by accepting a new solution if its distance to the population exceeds a given threshold. The method is evaluated on three sets of instances, and compared to other heuristics and a lower bound. The preliminary results are quite promising since the MA|PM already finds the best results on several instances.

We present the newly developed core concept for the Multidimensional Knapsack Problem (MKP) which is an extension of the classical concept for the one-dimensional case. The core for the multidimensional problem is defined in dependence of a chosen efficiency function of the items, since no single obvious efficiency measure is available for MKP. An empirical study on the cores of widely-used benchmark instances is presented, as well as experiments with different approximate core sizes. Furthermore we describe a memetic algorithm and a relaxation guided variable neighborhood search for the MKP, which are applied to the original and to the core problems. The experimental results show that given a fixed run-time, the different metaheuristics as well as a general purpose integer linear programming solver yield better solution when applied to approximate core problems of fixed size.

We consider scheduling heuristics for batching machines from semiconductor manufacturing. A batch is a collection of jobs that are processed at the same time on the same machine. The processing time of a batch is given by the identical processing time of the jobs within one incompatible family. We are interested in minimizing total weighted tardiness and makespan at the same time. In order to solve this problem, i.e. generate a Pareto-front, we suggest a multiobjective genetic algorithm. We present results from computational experiments on stochastically generated test instances that show the good solution quality of the suggested approach.

Combinatorial optimization problems with multiple objectives are, in general, more realistic representations of practical situations than their counterparts with a single-objective. The bi-objective minimum spanning tree problem is a NP-hard problem with applications in network design. In this paper a memetic algorithm is presented to solve this problem. A computational experiment compares the proposed approach with AESSEA, a known algorithm of the literature. The comparison of the algorithms is done with basis on the binary additive (-indicator. The results show that the proposed algorithm consistently produces better solutions than the other method.

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.