Scatter Search and Genetic Algorithms for MAX-SAT Problems

In this paper, both scatter search (SS) and genetic algorithms (GAs) are studied for the NP-Hard optimization variant of the satisfiability problem, namely MAX-SAT. First, we investigate a new selection strategy based on both fitness and diversity to choose individuals to participate in the reproduction phase of a genetic algorithm. The resulting algorithm is enhanced in two ways leading to two genetic algorithm variants: the first one uses a uniform crossover. The second one uses a specific crossover operator (to MAX-SAT). The crossover operator is combined with an improved stochastic local search (SLS). The crossover operator is used to identify promising regions while the stochastic local search performs an intensified search of solutions around these regions. Secondly, we propose a scatter search variant for MAX-SAT. Both the SS and the GAs implementations share the solution selection strategy, the improved SLS method and the combination operator. Experiments on several instances from MAX-SAT libraries are performed to show and compare the effectiveness of our approaches. The computational experiments show that both (SS) and (GAs) with a stochastic local search (SLS) improvement technique outperform a classical genetic algorithm (without SLS). The two metaheuristics are able of balancing search diversification and intensification which leads to good results. In general, the specific genetic algorithm with a (SLS) improvement technique and a specific combination method provides competitive results and finds solutions of a higher quality than a scatter search.     

A Scatter Search for the periodic capacitated arc routing problem

This paper considers the Periodic Capacitated Arc Routing Problem (PCARP), a natural extension of the well-known CARP to a multi-period horizon. Its objective is to assign a set of service days to each edge in a given network and to solve the resulting CARP for each period, in order to minimize the required fleet size and the total cost of the trips on the horizon. This new and very hard problem has various applications in periodic operations on street networks, like waste collection and sweeping. A greedy heuristic and a Scatter Search (SS) are developed and evaluated on two sets of PCARP instances derived from classical CARP benchmarks. The results show that the SS strongly improves its initial solutions and clearly outperforms the greedy heuristic. Preliminary lower bounds are also provided. As they are not sufficiently tight, the SS is also tested in the single-period case (CARP) for which tight bounds are available: in fact, it competes with one state-of-the-art metaheuristic proposed for the CARP.     

Heuristic Algorithms and Scatter Search for the Cardinality Constrained P||Cmax Problem

We consider the generalization of the classical P||C_max problem (assign n jobs to m identical parallel processors by minimizing the makespan) arising when the number of jobs that can be assigned to each processor cannot exceed a given integer k. The problem is strongly NP-hard for any fixed k > 2. We briefly survey lower and upper bounds from the literature. We introduce greedy heuristics, local search and a scatter search approach. The effectiveness of these approaches is evaluated through extensive computational comparison with a depth-first branch-and-bound algorithm that includes new lower bounds and dominance criteria.     

Solving feature subset selection problem by a Parallel Scatter Search

The aim of this paper is to develop a Parallel Scatter Search metaheuristic for solving the Feature Subset Selection Problem in classification. Given a set of instances characterized by several features, the classification problem consists of assigning a class to each instance. Feature Subset Selection Problem selects a relevant subset of features from the initial set in order to classify future instances. We propose two methods for combining solutions in the Scatter Search metaheuristic. These methods provide two sequential algorithms that are compared with a recent Genetic Algorithm and with a parallelization of the Scatter Search. This parallelization is obtained by running simultaneously the two combination methods. Parallel Scatter Search presents better performance than the sequential algorithms.     

Scatter Search for Network Design Problem

A fixed charge capacitated multicommodity network design problem on undirected networks is addressed. At the present time, there exists no algorithm that can solve large instances, common in several applications, in a reasonable period of time. This paper presents an efficient procedure using a scatter search framework. Computational experiments on a large set of randomly generated problems show that this procedure is capable of finding good solutions to large-scale problems within a reasonable amount of time.     

Scatter Search in software testing,comparison and collaboration with Estimation of Distribution Algorithms

One of the main tasks software testing includes is the generation of the test cases to be used during the test. Due to its expensive cost, the automatization of this task has become one of the key issues in the area. The field of Evolutionary Testing deals with this problem by means of metaheuristic search techniques.An Evolutionary Testing based approach to the automatic generation of test inputs is presented. The approach developed involves different possibilities of the usage of two heuristic optimization methods, namely, Scatter Search and Estimation of Distribution Algorithms. The possibilities comprise pure Scatter Search options and Scatter Search—Estimation of Distribution Algorithm collaborations. Several experiments were conducted in order to evaluate and compare the approaches presented with those in the literature. The analysis of the experimental results raises interesting conclusions, showing these alternatives as a promising option to tackle this problem.     

Scatter search for the cutwidth minimization problem

The cutwidth minimization problem consists of finding a linear layout of a graph so that the maximum linear cut of edges is minimized. This NP-hard problem has applications in network scheduling, automatic graph drawing and information retrieval. We propose a heuristic method based on the Scatter Search (SS) methodology for finding approximate solutions to this optimization problem. This metaheuristic explores solution space by evolving a set of reference points. Our SS method is based on a GRASP constructive algorithm, a local search strategy based on insertion moves and voting-based combination methods. We also introduce a new measure to control the diversity in the search process. Empirical results with 252 previously reported instances indicate that the proposed procedure compares favorably to previous metaheuristics for this problem, such as Simulated Annealing and Evolutionary Path Relinking.     

Scatter Search—Wellsprings and Challenges

This article is concerned with two global optimization problems (P1) and (P2). Each of these problems is a fractional programming problem involving the maximization of a ratio of a convex function to a convex function, where at least one of the convex functions is a quadratic form. First, the article presents and validates a number of theoretical properties of these problems. Included among these properties is the result that, under a mild assumption, any globally optimal solution for problem (P1) must belong to the boundary of its feasible region. Also among these properties is a result that shows that problem (P2) can be reformulated as a convex maximization problem. Second, the article presents for the first time an algorithm for globally solving problem (P2). The algorithm is a branch and bound algorithm in which the main computational effort involves solving a sequence of convex programming problems. Convergence properties of the algorithm are presented, and computational issues that arise in implementing the algorithm are discussed. Preliminary indications are that the algorithm can be expected to provide a practical approach for solving problem (P2), provided that the number of variables is not too large.     

Scatter Search for the 0–1 Multidimensional Knapsack Problem

The evolutionary metaheuristic called scatter search has been applied successfully to optimization problems for several years. In this paper, we apply the scatter search technique to the well-known 0–1 multidimensional knapsack problem. We propose a new relaxation-based diversification generator, which produces an initial population with elite solutions. The computational results obtained for a set of classic and correlated instances clearly show that (1) this generator can also be used as a heuristic for solving the multidimensional knapsack problem; (2) using the population produced by our generator as a starting point for the scatter search algorithm leads to better performance. We also enhance the scatter search algorithm by integrating memory and by using adapted intensification phases. Overall, the results are interesting and competitive compared to other population-based algorithms, such as genetic algorithms.      

A genetic local search algorithm with a threshold accepting mechanism for solving the runway dependent aircraft landing problem

As the demand for air transportation continues to grow, some flights cannot land at their preferred landing times because the airport is near its runway capacity. Extra fuel consumption and air pollution are then caused by the landing delays. Moreover, such delays may possibly yield extra costs for both passengers and airline companies that result from rescheduling transfer passengers and crew members. Consequently, how to increase the handling efficiency of congested airports is a crucial management issue. Building new runways at existing airports is often not feasible due to environmental, financial and geographical constraints. Therefore, devising a method for tackling the aircraft landing problem (ALP) in order to optimize the usage of existing runways at airports is the focus of this paper. This paper aims to develop a solution procedure based on a genetic local search (GLS) algorithm for solving the ALP with runway dependent attributes. A set of numerical experiments were conducted to test the validity of the proposed algorithm based on five test instances created and investigated by previous studies. The numerical results showed that the proposed GLS algorithm can effectively and efficiently determine the runway allocation, sequence and landing time for arriving aircraft for the five test cases by minimizing total delays under the separation constraints in comparison with the outcomes yielded by previous studies.     

An empirical investigation on parallelization strategies for Scatter Search

As other metaheuristics, Scatter Search can gain from a parallel implementation. However, it is not clear beforehand which of the possible alternative parallelization strategies is more effective. To address this question, it has been selected as a test bed for empirical testing a classical combinatorial optimization problem, namely 0–1 knapsack problem, for which the sequential application of Scatter Search is well known. Two phases or groups of steps in the Scatter Search template have been identified as natural candidates for parallelization and several ways of carrying out that parallelization are proposed. An extensive experimental analysis involving 18 different parallel algorithms has been carried out testing the combinations of these alternative parallelization strategies on a battery of large random instances generated using a public code from the literature. The interpretation of the ANOVA results gives cues about the significance of the alternatives used in each phase and about the effect of the dynamic (vs. static) updating of the RefSet. A low average efficiency has been observed, although it has to be taken into account that, due to the termination condition used, not all algorithms tested carry out the same number of iterations.     

Grasp Embedded Scatter Search for the Multicommodity Capacitated Network Design Problem

A GRASP embedded Scatter Search is developed for the multicommodity capacitated network design problem. Difficulty for this problem arises from the fact that selection of the optimal network design is an NP-complete combinatorial problem. There exist no polynomial exact algorithms which can solve this problem in a reasonable period of time for realistically sized instances. In such cases, heuristic procedures are commonly used. Two strategies were designed for GRASP: a traditional approach and a memory based technique. As for Scatter Search, 5 different strategies were used to update the reference set. Computational results on a large set of randomly generated instances show the convenience of the proposed procedures.     

Algorithms and codes for the assignment problem

This paper analyzes the most efficient algorithms for the Linear Min-Sum Assignment Problem and shows that they derive from a common basic procedure. For each algorithm, we evaluate the computational complexity and the average performance on randomly-generated test problems. Efficient FORTRAN implementations for the case of complete and sparse matrices are given.Research supported by C.N.R., Progetto Finalizzato Informatica-SOFMAT, Italy.     

Scatter search for the vehicle routing problem with time windows

In this paper we use a scatter search framework to solve the vehicle routing problem with time windows (VRPTW). Our objective is to achieve effective solutions and to investigate the effects of reference set design parameters pertaining to size, quality and diversity. Both a common arc method and an optimization-based set covering model are used to combine vehicle routing solutions. A reactive tabu search metaheuristic and a tabu search with an advanced recovery feature, together with a set covering procedure are used for solution improvement. Our approach led to a robust solution method, generating solution quality that is competitive with the current best metaheuristics.     

An Experimental Evaluation of a Scatter Search for the Linear Ordering Problem

Scatter search is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear global optimization problems. Based on formulations originally proposed in the 1960s for combining decision rules and problem constraints, such as in generating surrogate constraints, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we present a scatter search implementation designed to find high quality solutions for the NP-hard linear ordering problem, which has a significant number of applications in practice. The LOP, for example, is equivalent to the so-called triangulation problem for input-output tables in economics. Our implementation incorporates innovative mechanisms to combine solutions and to create a balance between quality and diversification in the reference set. We also use a tracking process that generates solution statistics disclosing the nature of combinations and the ranks of antecedent solutions that produced the best final solutions. Extensive computational experiments with more than 300 instances establishes the effectiveness of our procedure in relation to approaches previously identified to be best.     

Scatter search for the single source capacitated facility location problem

This paper considers the Single Source Capacitated Facility Location Problem (SSCFLP). We propose a Scatter Search approach to provide upper bounds for the optimal solution of the problem. The proposed approach uses GRASP to initialize the Reference Set. Solutions of the Reference Set are combined using a procedure that consists of two phases: (1) the initialization phase and (2) the improvement phase. During the initialization phase each client is assigned to an open facility to obtain a solution that is then improved with the improvement phase. Also, a tabu search algorithm is applied. In order to evaluate the proposed approach we use different sets of test problems. According to the results obtained we observe that the method provides good quality solutions with reasonable computational effort.     

Nonmonotone Algorithms for Pattern Search Methods

This work deals with the solution of ill-conditioned unconstrained minimization problems by means of pattern search methods. To this end, the usual requirement of monotonic reduction of the objective function is relaxed and nonmonotone pattern search methods are proposed, which maintain the convergence properties of their monotone counterparts. Numerical experimentation on several well-known ill-conditioned functions is reported. The results highlight a class of pattern search methods which benefit very much by the introduction of nonmonotone strategies.     

Algorithms for the vector maximization problem

We consider a convex setB inR ⁿ described as the intersection of halfspacesa _i ^T x ≦b _i (i ∈ I) and a set of linear objective functionsf _j =c _j ^T x (j ∈ J). The index setsI andJ are allowed to be infinite in one of the algorithms. We give the definition of theefficient points ofB (also called functionally efficient or Pareto optimal points) and present the mathematical theory which is needed in the algorithms. In the last section of the paper, we present algorithms that solve the following problems:

1. To decide if a given point inB is efficient.
2. To find an efficient point inB.
3. To decide if a given efficient point is the only one that exists, and if not, find other ones.
4. The solutions of the above problems do not depend on the absolute magnitudes of thec _j. They only describe the relative importance of the different activitiesx _i. Therefore we also consider $$\begin{gathered} \max G^T x \hfill \\ x efficient \hfill \\ \end{gathered} $$ for some vectorG.