Parallel multiobjective evolutionary algorithms for batch scheduling in heterogeneous computing and grid systems

This article presents six parallel multiobjective evolutionary algorithms applied to solve the scheduling problem in distributed heterogeneous computing and grid systems. The studied evolutionary algorithms follow an explicit multiobjective approach to tackle the simultaneous optimization of a system-related (i.e. makespan) and a user-related (i.e. flowtime) objectives. Parallel models of the proposed methods are developed in order to efficiently solve the problem. The experimental analysis demonstrates that the proposed evolutionary algorithms are able to efficiently compute accurate results when solving standard and new large problem instances. The best of the proposed methods outperforms both deterministic scheduling heuristics and single-objective evolutionary methods previously applied to the problem.     

Computing the nadir point for multiobjective discrete optimization problems

We investigate the problem of finding the nadir point for multiobjective discrete optimization problems (MODO). The nadir point is constructed from the worst objective values over the efficient set of a multiobjective optimization problem. We present a new algorithm to compute nadir values for MODO with \(p\) objective functions. The proposed algorithm is based on an exhaustive search of the \((p-2)\)-dimensional space for each component of the nadir point. We compare our algorithm with two earlier studies from the literature. We give numerical results for all algorithms on multiobjective knapsack, assignment and integer linear programming problems. Our algorithm is able to obtain the nadir point for relatively large problem instances with up to five-objectives.     

Evaluation of the multiobjective ant colony algorithm performances on biobjective quadratic assignment problems

The difficulty of resolving the multiobjective combinatorial optimization problems with traditional methods has directed researchers to investigate new approaches which perform better. In recent years some algorithms based on ant colony optimization (ACO) metaheuristic have been suggested to solve these multiobjective problems. In this study these algorithms have been reported and programmed both to solve the biobjective quadratic assignment problem (BiQAP) instances and to evaluate the performances of these algorithms. The robust parameter sets for each 12 multiobjective ant colony optimization (MOACO) algorithms have been calculated and BiQAP instances in the literature have been solved within these parameter sets. The performances of the algorithms have been evaluated by comparing the Pareto fronts obtained from these algorithms. In the evaluation step, a multi significance test is used in a non hierarchical structure, and a performance metric (P metric) essential for this test is introduced. Through this study, decision makers will be able to put in the biobjective algorithms in an order according to the priority values calculated from the algorithms’ Pareto fronts. Moreover, this is the first time that MOACO algorithms have been compared by solving BiQAPs.     

Constructive generation of very hard 3-colorability instances

Graph colorability (COL), is a typical constraint satisfaction problem to which phase transition phenomena (PTs), are important in the computational complexity of combinatorial search algorithms. PTs are significant and subtle because, in the PT region, extraordinarily hard problem instances are found, which may require exponential-order computational time to solve. To clarify PT mechanism, many studies have been undertaken to produce very hard instances, many of which were based on generate-and-test approaches. We propose a rather systematic or constructive algorithm that repeats the embedding of 4-critical graphs to arbitrarily generate large extraordinarily hard 3-colorability instances. We demonstrated experimentally that the computational cost to solve our generated instances is of an exponential order of the number of vertices by using a few actual coloring algorithms and constraint satisfaction algorithms.     

Multicriteria tour planning for mobile healthcare facilities in a developing country

A multiobjective combinatorial optimization (MOCO) formulation for the following location-routing problem in healthcare management is given: For a mobile healthcare facility, a closed tour with stops selected from a given set of population nodes has to be found. Tours are evaluated according to three criteria: (i) An economic efficiency criterion related to the tour length, (ii) the criterion of average distances to the nearest tour stops corresponding to p-median location problem formulations, and (iii) a coverage criterion measuring the percentage of the population unable to reach a tour stop within a predefined maximum distance. Three algorithms to compute approximations to the set of Pareto-efficient solutions of the described MOCO problem are developed. The first uses the P-ACO technique, and the second and the third use the VEGA and the MOGA variant of multiobjective genetic algorithms, respectively. Computational experiments for the Thiès region in Senegal were carried out to evaluate the three approaches on real-world problem instances.     

An experimental analysis of evolutionary heuristics for the biobjective traveling purchaser problem

Given a set of markets and a set of products to be purchased on those markets, the Biobjective Traveling Purchaser Problem (2TPP) consists in determining a route through a subset of markets to collect all products, minimizing the travel distance and the purchasing cost simultaneously. As its single objective version, the 2TPP is an NP-hard Combinatorial Optimization problem. Only one exact algorithm exists that can solve instances up to 100 markets and 200 products and one heuristic approach that can solve instances up to 500 markets and 200 products. Since the Transgenetic Algorithms (TAs) approach has shown to be very effective for the single objective version of the investigated problem, this paper examines the application of these algorithms to the 2TPP. TAs are evolutionary algorithms based on the endosymbiotic evolution and other interactions of the intracellular flow interactions. This paper has three main purposes: the first is the investigation of the viability of Multiobjective TAs to deal with the 2TPP, the second is to determine which characteristics are important for the hybridization between TAs and multiobjective evolutionary frameworks and the last is to compare the ability of multiobjective algorithms based only on Pareto dominance with those based on both decomposition and Pareto dominance to deal with the 2TPP. Two novel Transgenetic Multiobjective Algorithms are proposed. One is derived from the NSGA-II framework, named NSTA, and the other is derived from the MOEA/D framework, named MOTA/D. To analyze the performance of the proposed algorithms, they are compared with their classical counterparts. It is also the first time that NSGA-II and MOEA/D are applied to solve the 2TPP. The methods are validated in 365 uncapacitated instances of the TPPLib benchmark. The results demonstrate the superiority of MOTA/D and encourage further researches in the hybridization of Transgenetic Algorithms and Multiobjective Evolutionary Algorithms specially the ones based on decomposition.     

Modeling sequence evolution with kernel methods

We model the evolution of biological and linguistic sequences by comparing their statistical properties. This comparison is performed by means of efficiently computable kernel functions, that take two sequences as an input and return a measure of statistical similarity between them. We show how the use of such kernels allows to reconstruct the phylogenetic trees of primates based on the mitochondrial DNA (mtDNA) of existing animals, and the phylogenetic tree of Indo-European and other languages based on sample documents from existing languages. Kernel methods provide a convenient framework for many pattern analysis tasks, and recent advances have been focused on efficient methods for sequence comparison and analysis. While a large toolbox of algorithms has been developed to analyze data by using kernels, in this paper we demonstrate their use in combination with standard phylogenetic reconstruction algorithms and visualization methods.     

Heuristics and metaheuristics for the maximum diversity problem

This paper presents extensive computational experiments to compare 10 heuristics and 20 metaheuristics for the maximum diversity problem (MDP). This problem consists of selecting a subset of maximum diversity from a given set of elements. It arises in a wide range of real-world settings and we can find a large number of studies, in which heuristic and metaheuristic methods are proposed. However, probably due to the fact that this problem has been referenced under different names, we have only found limited comparisons with a few methods on some sets of instances. This paper reviews all the heuristics and metaheuristics for finding near-optimal solutions for the MDP. We present the new benchmark library MDPLIB, which includes most instances previously used for this problem, as well as new ones, giving a total of 315. We also present an exhaustive computational comparison of the 30 methods on the MDPLIB. Non-parametric statistical tests are reported in our study to draw significant conclusions.     

Solving multiobjective,multiconstraint knapsack problems using mathematical programming and evolutionary algorithms

In this paper, we solve instances of the multiobjective multiconstraint (or multidimensional) knapsack problem (MOMCKP) from the literature, with three objective functions and three constraints. We use exact as well as approximate algorithms. The exact algorithm is a properly modified version of the multicriteria branch and bound (MCBB) algorithm, which is further customized by suitable heuristics. Three branching heuristics and a more general purpose composite branching and construction heuristic are devised. Comparison is made to the published results from another exact algorithm, the adaptive ε-constraint method [Laumanns, M., Thiele, L., Zitzler, E., 2006. An efficient, adaptive parameter variation scheme for Metaheuristics based on the epsilon-constraint method. European Journal of Operational Research 169, 932–942], using the same data sets. Furthermore, the same problems are solved using standard multiobjective evolutionary algorithms (MOEA), namely, the SPEA2 and the NSGAII. The results from the exact case show that the branching heuristics greatly improve the performance of the MCBB algorithm, which becomes faster than the adaptive ε -constraint. Regarding the performance of the MOEA algorithms in the specific problems, SPEA2 outperforms NSGAII in the degree of approximation of the Pareto front, as measured by the coverage metric (especially for the largest instance).     

Novel evolutionary models and applications to sequence alignment problems

In this paper, we present a novel graph-theoretical approach for representing a wide variety of sequence analysis problems within a single model. The model allows incorporation of the operations “insertion”, “deletion”, and “substitution”, and various parameters such as relative distances and weights. Conceptually, we refer the problem as the minimum weight common mutated sequence (MWCMS) problem. The MWCMS model has many applications including multiple sequence alignment problem, the phylogenetic analysis, the DNA sequencing problem, and sequence comparison problem, which encompass a core set of very difficult problems in computational biology. Thus the model presented in this paper lays out a mathematical modeling framework that allows one to investigate theoretical and computational issues, and to forge new advances for these distinct, but related problems. Through the introduction of supernodes, and the multi-layer supergraph, we proved that MWCMS is -complete. Furthermore, it was shown that a conflict graph derived from the multi-layer supergraph has the property that a solution to the associated node-packing problem of the conflict graph corresponds to a solution of the MWCMS problem. In this case, we proved that when the number of input sequences is a constant, MWCMS is polynomial-time solvable. We also demonstrated that some well-known combinatorial problems can be viewed as special cases of the MWCMS problem. In particular, we presented theoretical results implied by the MWCMS theory for the minimum weight supersequence problem, the minimum weight superstring problem, and the longest common subsequence problem. Two integer programming formulations were presented and a simple yet elegant decomposition heuristic was introduced. The integer programming instances have proven to be computationally intensive. Consequently, research involving simultaneous column and row generation and parallel computing will be explored. The heuristic algorithm, introduced herein for multiple sequence alignment, overcomes the order-dependent drawbacks of many of the existing algorithms, and is capable of returning good sequence alignments within reasonable computational time. It is able to return the optimal alignment for multiple sequences of length less than 1500 base pairs within 30 minutes. Its algorithmic decomposition nature lends itself naturally for parallel distributed computing, and we continue to explore its flexibility and scalability in a massive parallel environment.     

Tabu search and GRASP for the maximum diversity problem

In this paper, we develop new heuristic procedures for the maximum diversity problem (MDP). This NP-hard problem has a significant number of practical applications such as environmental balance, telecommunication services or genetic engineering. The proposed algorithm is based on the tabu search methodology and incorporates memory structures for both construction and improvement. Although proposed in seminal tabu search papers, memory-based constructions have often been implemented in naïve ways that disregard important elements of the fundamental tabu search proposals. We will compare our tabu search construction with a memory-less design and with previous algorithms recently developed for this problem. The constructive method can be coupled with a local search procedure or a short-term tabu search for improved outcomes. Extensive computational experiments with medium and large instances show that the proposed procedure outperforms the best heuristics reported in the literature within short computational times.     

A comparative study of decomposition algorithms for stochastic combinatorial optimization

This paper presents comparative computational results using three decomposition algorithms on a battery of instances drawn from two different applications. In order to preserve the commonalities among the algorithms in our experiments, we have designed a testbed which is used to study instances arising in server location under uncertainty and strategic supply chain planning under uncertainty. Insights related to alternative implementation issues leading to more efficient implementations, benchmarks for serial processing, and scalability of the methods are also presented. The computational experience demonstrates the promising potential of the disjunctive decomposition (D ²) approach towards solving several large-scale problem instances from the two application areas. Furthermore, the study shows that convergence of the D ² methods for stochastic combinatorial optimization (SCO) is in fact attainable since the methods scale well with the number of scenarios.     

An interactive dynamic approach based on hybrid swarm optimization for solving multiobjective programming problem with fuzzy parameters

Real engineering design problems are generally characterized by the presence of many often conflicting and incommensurable objectives. Naturally, these objectives involve many parameters whose possible values may be assigned by the experts. The aim of this paper is to introduce a hybrid approach combining three optimization techniques, dynamic programming (DP), genetic algorithms and particle swarm optimization (PSO). Our approach integrates the merits of both DP and artificial optimization techniques and it has two characteristic features. Firstly, the proposed algorithm converts fuzzy multiobjective optimization problem to a sequence of a crisp nonlinear programming problems. Secondly, the proposed algorithm uses H-SOA for solving nonlinear programming problem. In which, any complex problem under certain structure can be solved and there is no need for the existence of some properties rather than traditional methods that need some features of the problem such as differentiability and continuity. Finally, with different degree of α we get different α-Pareto optimal solution of the problem. A numerical example is given to illustrate the results developed in this paper.     

Combining the Scalability of Local Search with the Pruning Techniques of Systematic Search

Systematic backtracking is used in many constraint solvers and combinatorial optimisation algorithms. It is complete and can be combined with powerful search pruning techniques such as branch-and-bound, constraint propagation and dynamic variable ordering. However, it often scales poorly to large problems. Local search is incomplete, and has the additional drawback that it cannot exploit pruning techniques, making it uncompetitive on some problems. Nevertheless its scalability makes it superior for many large applications. This paper describes a hybrid approach called Incomplete Dynamic Backtracking, a very flexible form of backtracking that sacrifices completeness to achieve the scalability of local search. It is combined with forward checking and dynamic variable ordering, and evaluated on three combinatorial problems: on the n-queens problem it out-performs the best local search algorithms; it finds large optimal Golomb rulers much more quickly than a constraint-based backtracker, and better rulers than a genetic algorithm; and on benchmark graphs it finds larger cliques than almost all other tested algorithms. We argue that this form of backtracking is actually local search in a space of consistent partial assignments, offering a generic way of combining standard pruning techniques with local search.     

Multiobjective scatter search for a commercial territory design problem

In this paper, a multiobjective scatter search procedure for a bi-objective territory design problem is proposed. A?territory design problem consists of partitioning a set of basic units into larger groups that are suitable with respect to some specific planning criteria. These groups must be compact, connected, and balanced with respect to the number of customers and sales volume. The bi-objective commercial territory design problem belongs to the class of NP-hard problems. Previous work showed that large instances of the problem addressed in this work are practically intractable even for the single-objective version. Therefore, the use of heuristic methods is the best alternative for obtaining approximate efficient solutions for relatively large instances. The proposed scatter search-based framework contains a diversification generation module based on a greedy randomized adaptive search procedure, an improvement module based on a relinked local search strategy, and a combination module based on a solution to an assignment problem. The proposed metaheuristic is evaluated over a variety of instances taken from literature. This includes a comparison with two of the most successful multiobjective heuristics from literature such as the Scatter Tabu Search Procedure for Multiobjective Optimization (SSPMO) by Molina et al. (INFORMS J. Comput. 19(1):91?C100, 2007), and the Non-dominated Sorting Genetic Algorithm (NSGA-II) by Deb et?al. (Parallel problem solving from nature ?C PPSN VI, Lecture notes in computer science, vol. 1917, Springer, Berlin, pp.?849?C858, 2000). Experimental work reveals that the proposed procedure consistently outperforms both heuristics, SSPMO and NSGA-II, on all instances tested.     

Comparative analysis of multiobjective evolutionary algorithms for random and correlated instances of multiobjective d-dimensional knapsack problems

This study analyzes multiobjective d-dimensional knapsack problems (MOd-KP) within a comparative analysis of three multiobjective evolutionary algorithms (MOEAs): the ε-nondominated sorted genetic algorithm II (ε-NSGAII), the strength Pareto evolutionary algorithm 2 (SPEA2) and the ε-nondominated hierarchical Bayesian optimization algorithm (ε-hBOA). This study contributes new insights into the challenges posed by correlated instances of the MOd-KP that better capture the decision interdependencies often present in real world applications. A statistical performance analysis of the algorithms uses the unary ε-indicator, the hypervolume indicator and success rate plots to demonstrate their relative effectiveness, efficiency, and reliability for the MOd-KP instances analyzed. Our results indicate that the ε-hBOA achieves superior performance relative to ε-NSGAII and SPEA2 with increasing number of objectives, number of decisions, and correlative linkages between the two. Performance of the ε-hBOA suggests that probabilistic model building evolutionary algorithms have significant promise for expanding the size and scope of challenging multiobjective problems that can be explored.     

Multiobjective GRASP with Path Relinking

In this paper we review and propose different adaptations of the GRASP metaheuristic to solve multiobjective combinatorial optimization problems. In particular, we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with Path Relinking for single-objective optimization. Moreover, we propose different hybridizations of GRASP and Path Relinking for multiobjective optimization. We apply the proposed GRASP with Path Relinking variants to two combinatorial optimization problems, the biobjective orienteering problem and the biobjective path dissimilarity problem. We report on empirical tests with 70 instances and 30 algorithms, that show that the proposed heuristics are competitive with the state-of-the-art methods for these problems.     

An approximate dynamic programming approach for the vehicle routing problem with stochastic demands

This paper examines approximate dynamic programming algorithms for the single-vehicle routing problem with stochastic demands from a dynamic or reoptimization perspective. The methods extend the rollout algorithm by implementing different base sequences (i.e. a priori solutions), look-ahead policies, and pruning schemes. The paper also considers computing the cost-to-go with Monte Carlo simulation in addition to direct approaches. The best new method found is a two-step lookahead rollout started with a stochastic base sequence. The routing cost is about 4.8% less than the one-step rollout algorithm started with a deterministic sequence. Results also show that Monte Carlo cost-to-go estimation reduces computation time 65% in large instances with little or no loss in solution quality. Moreover, the paper compares results to the perfect information case from solving exact a posteriori solutions for sampled vehicle routing problems. The confidence interval for the overall mean difference is (3.56%, 4.11%).     

Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem

We consider the generalized version of the classical Minimum Spanning Tree problem where the nodes of a graph are partitioned into clusters and exactly one node from each cluster must be connected. We present a Variable Neighborhood Search (VNS) approach which uses three different neighborhood types. Two of them work in complementary ways in order to maximize search effectivity. Both are large in the sense that they contain exponentially many candidate solutions, but efficient polynomial-time algorithms are used to identify best neighbors. For the third neighborhood type we apply Mixed Integer Programming to optimize local parts within candidate solution trees. Tests on Euclidean and random instances with up to 1280 nodes indicate especially on instances with many nodes per cluster significant advantages over previously published metaheuristic approaches. This work is supported by the RTN ADONET under grant 504438.