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.     

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.     

Search strategies investigation in brain storm optimization

The canonical brain storm optimization (BSO) employs clustering, creating and selecting operators, which are all connected and have great impacts on the optimization performance. In this paper, the state-of-the-art search strategies are introduced and the potential strengths and weaknesses of these strategies in the BSO algorithm are analyzed and compared from the perspective of the analytical model rather than any metaphors. The numerical experiments are carried out to artificially amplify and highlight the performance of various strategies. Finally, the progressive directions of the BSO algorithm are discussed for further research.     

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.     

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.      

Scatter Search and Bionomic Algorithms for the aircraft landing problem

The problem of deciding how to land aircraft approaching an airport involves assigning each aircraft to an appropriate runway, computing a landing sequence for each runway and scheduling the landing time for each aircraft. Runway allocation, sequencing and scheduling for each aircraft must ensure the scheduled landing time lies within a predefined time window and meet separation time requirements with other aircraft. The objective is to achieve effective runway use.In this paper, the multiple runway case of the static Aircraft Landing Problem is considered. Two heuristic techniques are presented: Scatter Search and the Bionomic Algorithm, population heuristic approaches that have not been applied to this problem before.Computational results are presented for publicly available test problems involving up to 500 aircraft and five runways showing that feasible solutions of good quality can be produced relatively quickly.     

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.     

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.     

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.     

Experimental Testing of Advanced Scatter Search Designs for Global Optimization of Multimodal Functions

Scatter search is an evolutionary method that, unlike genetic algorithms, operates on a small set of solutions and makes only limited use of randomization as a proxy for diversification when searching for a globally optimal solution. The scatter search framework is flexible, allowing the development of alternative implementations with varying degrees of sophistication. In this paper, we test the merit of several scatter search designs in the context of global optimization of multimodal functions. We compare these designs among themselves and choose one to compare against a well-known genetic algorithm that has been specifically developed for this class of problems. The testing is performed on a set of benchmark multimodal functions with known global minima.     

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.     

An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem

In this paper we consider the two-dimensional (2D) rectangular packing problem, where a fixed set of items have to be allocated on a single object. Two heuristics, which belong to the class of packing procedures that preserve bottom-left (BL) stability, are hybridised with three meta-heuristic algorithms (genetic algorithms (GA), simulated annealing (SA), naı̈ve evolution (NE)) and local search heuristic (hill-climbing). This study compares the hybrid algorithms in terms of solution quality and computation time on a number of packing problems of different size. In order to show the effectiveness of the design of the different algorithms, their performance is compared to random search (RS) and heuristic packing routines.     

An adaptive domain-decomposition technique for parallelization of the fast marching method

The fast marching method (FMM) is an efficient technique to solve numerically the Eikonal equation. The parallelization of the FMM is not easy because of its intrinsic sequential nature. In this paper we propose a novel approach to parallelize the FMM. It leads to an equation-dependent domain decomposition and it turns out to be particularly suitable for machines with two or four cores that are in common use today. Compared to other techniques in the field, the proposed method is much simpler to implement and it gives a slightly better computational speed-up.In order to test the new method on a real-world application, we solve the shape-from-shading problem based on a Hamilton-Jacobi equation. On a standard four-core machine, the method confirms the good properties. It shows a reasonable speedup factor of about 2.5, and it reveals its potential to good performance if the arithmetic density of the problem is high.     

An empirical bioeconomic investigation of efficiency in the insecticide regulatory process

This paper presents an interdisciplinary approach to estimating the relative efficiency of static, myopic, and dynamic insecticide regulatory decision making when there are potential impacts associated with pest resistance. A theoretical control model was developed using expected total economic surplus as the objective function, with an empirical solution to the maximization problem attained by imposing a heuristic search procedure on a bioeconomic simulation model. Although the impact of nondynamic decision making was the most severe, in percentage terms, for shortrun planning horizons, the magnitude of the longrun losses associated with nondynamic decision making could serve as a rationale for modifying the regulatory process to include dynamic considerations. The static analyses usually used in the benefits assessment procedure may severely underestimate the actual benefits of continued chemical registration, and the efficiency gains to society have the potential to offset the increased costs of regulation that would occur under a revised process.     

Flexible working arrangements in context: An empirical investigation through self-organizing maps

This is one of the first studies to utilize Kohonen’s self-organizing maps on flexible work arrangements (FWAs), employee turnover and absenteeism within different national contexts and an array of organizational factors. While the majority of FWAs did not reduce significantly employee turnover or absenteeism, country and industry were significant contextual variables in FWA use: we deciphered six main country regions, where service and manufacturing organizations were important to FWA preferences. We found a curvilinear relationship between turnover and shift-work among manufacturing firms regardless of country: turnover decreases at low levels and increases at high levels of shift-work. We also found strong positive relationships between weekend work and turnover among manufacturing firms regardless of country and firms in the region comprising of Germany, Austria, Sweden, Finland, Denmark, Czech Republic and Belgium. Finally, we found consistently high concentration of organizations with low absenteeism throughout certain industries and countries: noteworthy are service organizations in the Netherlands and manufacturing organizations in Australia. The results demonstrate the contextuality of FWA use across countries and industries, and the usefulness of SOMs for research within human resource management.     

Convergent iterative schemes for time parallelization

Parallel methods are usually not applied to the time domain because of the inherit sequentialness of time evolution. But for many evolutionary problems, computer simulation can benefit substantially from time parallelization methods. In this paper, we present several such algorithms that actually exploit the sequential nature of time evolution through a predictor-corrector procedure. This sequentialness ensures convergence of a parallel predictor-corrector scheme within a fixed number of iterations. The performance of these novel algorithms, which are derived from the classical alternating Schwarz method, are illustrated through several numerical examples using the reservoir simulator Athena.

     

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.     

Relationships between the decision support system subspecialities and reference disciplines: An empirical investigation

This is a comprehensive study, that, by means of an empirical assessment of the DSS literature, systematically identifies the DSS reference disciplines and traces how concepts and findings by researchers in the contributing disciplines have been picked up by DSS researchers to be applied, extended, and refined in the development of DSS research subspecialties. Cluster analysis was employed to an author cocitation frequency matrix derived from a comprehensive database of the DSS literature over the period of 1970 through 1993. Twelve clusters were uncovered consisting of six major areas of DSS research (group DSS, foundations, model management, user interfaces, implementation, and multiple criteria DSS) and six contributing disciplines (multiple criteria decision making, cognitive science, organization science, artificial intelligence, group decision making, and systems science).