MNK landscapes are multi-objective combinatorial optimization problems. For MNK landscapes, computing the entire set of Pareto local optima and the Pareto front by full enumeration quickly becomes infeasible within a reasonable amount of time. Approximation methods are faster, but cannot guarantee that all Pareto local optima or Pareto non-dominated solutions are found. To address this, we propose a multi-objective gray-box optimization algorithm based on hyperplane elimination. By exploiting gray-box information, the number of evaluations is reduced by maintaining and updating changes in subfunction values of the objectives instead of re-evaluating the entire bitstring after each bit flip. In addition, hyperplanes of bitstrings can be eliminated from the search space by knowing all dependencies between the bits and the delta values. Since this algorithm identifies all Pareto local optima, the Pareto front can be obtained with very low additional cost. We provide theoretical proofs of correctness and experimental results on adjacent, random and p-correlated MNK landscapes showing speed-ups of several orders of magnitude. Further improvements on runtime are obtained by using a bit reordering heuristic and a prefix mechanism. Altogether, our proposed method enables the computation of exact Pareto sets of MNK landscapes even for large bit lengths.

We demonstrate that there are strong patterns of periodicity in terms of how local optima are distributed across search spaces that can help to explain the "Big Valley" distribution of local optima. Examples of periodicity can be found by looking at several Partition Crossover events simultaneously and grouping together those that are nearer to each other in Hamming space. All of the local optima associated with one Partition Crossover event can be evaluated using a single linear equation. When looking at many Partition Crossover events simultaneously, linearity is preserved over complete and partially preserved recombining components.

Over decades of Traveling Salesperson Problem (TSP) research, powerful heuristics have been developed that efficiently solve many TSP instances. Among them, the local search optimizer LKH and the genetic algorithm EAX stand out as the two complementary state-of-the-art solvers. Yet, the links between instance structures and solver complementarity remain obscure, i.e., it is often unclear how instance structures affect solver performance and behavior.

The Partition Crossover is a deterministic crossover operator for the Traveling Salesman Problem (TSP). It decomposes the union graph of two TSP solutions, A and B, into connected components known as AB-cycles, from which the lower-cost edges are selected and recombined to produce offspring. The operator finds the best offspring within a search space of 2k solutions in linear time, where k is the number of recombining components. We introduce Generalized Partition Crossover 3 (GPX3), a new implementation of Partition Crossover. GPX3 features a new algorithm to quickly find AB-cycles in the union graph. It also identifies additional recombining AB-cycles, expanding the reachable search space. We show that GPX3 runs in O(n) time and is more efficient and effective than previous implementations of Partition Crossover for the TSP.

The Edge Assembly Crossover (EAX) algorithm is the state-of-the-art heuristic for solving the Traveling Salesperson Problem (TSP). It regularly outperforms other methods, such as the Lin-Kernighan-Helsgaun heuristic (LKH), across diverse sets of TSP instances. Essentially, EAX employs a two-stage mechanism that focuses on improving the current solutions, first, at the local and, subsequently, at the global level. Although the second phase of the algorithm has been thoroughly studied, configured, and refined in the past, in particular, its first stage has hardly been examined.

A combination of recombination and local search can expose the existence of an exponential number of parallel lattices that span the search space for all classes of k-bounded pseudo-Boolean functions, including MAX-kSAT problems. These "parallel" lattices sometimes have identical evaluations shifted by a constant. We use Partition Crossover to aid in the discovery of lattices, which are sets of 2q possible offspring from recombination events, organized into q-dimensional hypercubes, where q is the number of recombining components given two parents. Finally, we show that recursively embedded subspace lattices display a fractal structure, which can be captured using rewrite rules based on a Lindenmayer system that accurately model how local optima are distributed across different size lattices.

In pseudo-Boolean optimization, a variable interaction graph represents variables as vertices, and interactions between pairs of variables as edges. In black-box optimization, the variable interaction graph may be at least partially discovered by using empirical linkage learning techniques. These methods never report false variable interactions, but they are computationally expensive. The recently proposed local search with linkage learning discovers the partial variable interaction graph as a side-effect of iterated local search. However, information about the strength of the interactions is not learned by the algorithm. We propose local search with linkage learning 2, which builds a weighted variable interaction graph that stores information about the strength of the interaction between variables. The weighted variable interaction graph can provide new insights about the optimization problem and behavior of optimizers. Experiments with NK landscapes, knapsack problem, and feature selection show that local search with linkage learning 2 is able to efficiently build weighted variable interaction graphs. In particular, experiments with feature selection show that the weighted variable interaction graphs can be used for visualizing the feature interactions in machine learning. Additionally, new transformation operators that exploit the interactions between variables can be designed. We illustrate this ability by proposing a new perturbation operator for iterated local search.

When Partition Crossover is used to recombine two parents which are local optima, the offspring are all local optima in the smallest hyperplane subspace that contains the two parents. The offspring can also be organized into a non-planar hypercube "lattice." Furthermore, all of the offspring can be evaluated using a simple linear equation. When a child of Partition Crossover is a local optimum in the full search space, the linear equation exactly determines its evaluation. When a child of Partition Crossover can be improved by local search, the linear equation is an upper bound on the evaluation of the associated local optimum when minimizing. This theoretical result holds for all k-bounded Pseudo-Boolean optimization problems, including MAX-kSAT, QUBO problems, as well as random and adjacent NK landscapes. These linear equations provide a stronger explanation as to why the "Big Valley" distribution of local optima exists. We fully enumerate a sample of NK landscapes to collect frequency information to complement our theoretical results. We also introduce new algorithmic contributions that can 1) expand smaller lattices in order to find larger lattices that contain additional local optima, and 2) introduce an efficient method to find new improving moves in lattices using score vectors.

Next-generation genetic algorithms (GAs) should explore information from the problem structure whenever possible. Variable interactions can be inferred using linkage learning. Statistical linkage learning techniques were shown to improve GAs' effectiveness significantly in many problems, but may eventually report false linkages. On the other hand, empirical linkage learning (ELL) techniques discover only true variable dependencies. However, traditional ELL techniques are computationally expensive. We introduce the genetic algorithm with linkage learning (GAwLL), which discovers an empirical weighted variable interaction graph (VIGw) as a side-effect of the optimization performed by a GA, making it a no-cost ELL technique. Vertices of the VIGw represent decision variables and weights indicate the strength of the interaction between variables. The VIGw allows us to obtain new insights about the optimization problem and can be used to design genetic operators that efficiently explore the information about variable dependencies. Experiments with NK landscapes show that GAwLL is able to efficiently build the empirical VIGw. We also present an interesting machine learning application, where the VIGw represents a feature interaction network. By using GAwLL, the feature interaction network is built as a side-effect of evolutionary feature selection.

The U.S. Navy currently deploys Genetic Algorithms to schedule multi-resource satellites. We document this real-world application and also introduce a new synthetic test problem generator. A permutation is used as the representation. A greedy scheduler then converts the permutation into a schedule which can be displayed as a Gantt chart. Surprisingly, there have been few careful comparisons of standard generational Genetic Algorithms and Steady State Genetic Algorithms for these types of problems. In addition, this paper compares different crossover operators for the multi-resource satellite scheduling problem. Finally, we look at two ways of mapping the permutation to a schedule in the form of a Gantt chart. One method gives priority to reducing conflicts, while the other gives priority to reducing overlaps of conflicting tasks. This can produce very different results, even when the evaluation function stays exactly the same.

Rectified Linear Units (ReLU) are the default choice for activation functions in deep neural networks. While they demonstrate excellent empirical performance, ReLU activations can fall victim to the dead neuron problem. In these cases, the weights feeding into a neuron end up being pushed into a state where the neuron outputs zero for all inputs. Consequently, the gradient is also zero for all inputs, which means that the weights which feed into the neuron cannot update. The neuron is not able to recover from direct back propagation and model capacity is reduced as those parameters can no longer be further optimized. Inspired by a neurological process of the same name, we introduce Synaptic Stripping as a means to combat this dead neuron problem. By automatically removing problematic connections during training, we can regenerate dead neurons and significantly improve model capacity and parametric utilization. Synaptic Stripping is easy to implement and results in sparse networks that are more efficient than the dense networks they are derived from. We conduct several ablation studies to investigate these dynamics as a function of network width and depth and we conduct an exploration of Synaptic Stripping with Vision Transformers on a variety of benchmark datasets.

Diversity is an important consideration in the construction of robust neural network ensembles. A collection of well trained models will generalize better if they are diverse in the patterns they respond to and the predictions they make. Diversity is especially important for low-cost ensemble methods because members often share network structure in order to avoid training several independent models from scratch. Diversity is traditionally analyzed by measuring differences between the outputs of models. However, this gives little insight into how knowledge representations differ between ensemble members. This paper introduces several interpretability methods that can be used to qualitatively analyze diversity. We demonstrate these techniques by comparing the diversity of feature representations between child networks using two low-cost ensemble algorithms, Snapshot Ensembles and Prune and Tune Ensembles. We use the same pre-trained parent network as a starting point for both methods which allows us to explore how feature representations evolve over time. This approach to diversity analysis can lead to valuable insights and new perspectives for how we measure and promote diversity in ensemble methods.

Ensemble Learning is an effective method for improving generalization in machine learning. However, as state-of-the-art neural networks grow larger, the computational cost associated with training several independent networks becomes expensive. We introduce a fast, low-cost method for creating diverse ensembles of neural networks without needing to train multiple models from scratch. We do this by first training a single parent network. We then create child networks by cloning the parent and dramatically pruning the parameters of each child to create an ensemble of members with unique and diverse topologies. We then briefly train each child network for a small number of epochs, which now converge significantly faster when compared to training from scratch. We explore various ways to maximize diversity in the child networks, including the use of anti-random pruning and one-cycle tuning. This diversity enables "Prune and Tune" ensembles to achieve results that are competitive with traditional ensembles at a fraction of the training cost. We benchmark our approach against state of the art low-cost ensemble methods and display marked improvement in both accuracy and uncertainty estimation on CIFAR-10 and CIFAR-100.

Combining Iterated Local Search with Partition Crossover (PX) has the potential to be a powerful hybrid search strategy for MAX-kSAT problems. The disadvantage of standard Partition Crossover is that it touches every variable and every clause. This paper borrows strategies from WalkSAT to improve Partition Crossover such that it only touches a fraction of clauses by focusing on unsatisfied clauses. On average, it is possible to speed up Partition Crossover by one or two orders of magnitude. The PX-preprocessor also simplifies the interface between Partition Crossover and local search. Partition Crossover is compared with and without the PX-preprocessor on 478 SAT instances from the 2014 SAT competition; PX is particularly effective on application problems and larger problem instances.

Perturbing solutions is a key factor in iterated local search (ILS). The standard approach for perturbing a solution is to randomly change a fixed number of decision variables from the current local optimum. Finding suitable values of perturbation strength is difficult. It is desirable that consecutive local optima generated by ILS be close to each other and correlated in fitness. However, if the perturbation is too small, we can get stuck in the same local optimum. We propose a new perturbation strategy for ILS applied to pseudo-Boolean optimization problems where decision variables that interact are perturbed. These interactions are identified in a variable interaction graph (VIG), that is available in gray-box optimization. For black-box optimization, we propose a local search strategy that estimates an empirical VIG. Theoretical and experimental results show that perturbation based on the VIG is efficient in random and adjacent NK landscapes. Results also show that the proposed local search strategy was able to build empirical VIGs with more than 97% of the edges of the true VIG.

Local optima networks (LONs) model the global distribution and connectivity pattern of local optima under given search operators. Recent research has looked at how recombination operators can jump from a pair of parents that are locally optimal to a new child that is either a local optimum, or is guaranteed to be in a new basin of attraction. Recombination can therefore also induce a local optima network which maps how crossover moves between local optima. In this paper, we prove that recombination induces a LON which is actually a network of overlapping hypercube lattices. Given two or more samples from any lattice, we can also infer the existence of additional local optima that have not previously been reached by sampling. We prove that these lattices can be exponentially large. Finally, we prove that there exists TSP instances can be solved in polynomial time by exploiting Partition Crossover; these same instances are not solved by local search.

An optimal recombination operator for two-parent solutions provides the best solution among those that take the value for each variable from one of the parents (gene transmission property). If the solutions are bit strings, the offspring of an optimal recombination operator is optimal in the smallest hyperplane containing the two parent solutions. Exploring this hyperplane is computationally costly, in general, requiring exponential time in the worst case. However, when the variable interaction graph of the objective function is sparse, exploration can be done in polynomial time. In this article, we present a recombination operator, called Dynastic Potential Crossover (DPX), that runs in polynomial time and behaves like an optimal recombination operator for low-epistasis combinatorial problems. We compare this operator, both theoretically and experimentally, with traditional crossover operators, like uniform crossover and network crossover, and with two recently defined efficient recombination operators: partition crossover and articulation points partition crossover. The empirical comparison uses NKQ Landscapes and MAX-SAT instances. DPX outperforms the other crossover operators in terms of quality of the offspring and provides better results included in a trajectory and a population-based metaheuristic, but it requires more time and memory to compute the offspring.

Iterative Partial Transcription (IPT) is an important recombination operator for Traveling Salesman Problem (TSP), and is a key component in the LKH inexact solver for the TSP. IPT shares many characteristics with Partition Crossover for the TSP. However, the standard implementation of IPT searches for all common subchains of sizes from 4 to n/2 between two parent tours and thus has a time complexity of O(n2) in the worst case. In this paper, an efficient implementation of IPT is proposed that uses a special data structure called the Extended Edge Table (EET) to find the recombination components. We prove that the proposed technique is approximately equivalent to IPT and has a time complexity of O(n). The performance of the two implementations of IPT is compared based on some random and benchmark TSP instances to establish the efficiency of the proposed algorithm.

Partition crossover (PX) is an efficient recombination operator for gray-box optimization. PX is applied in problems where the objective function can be written as a sum of subfunctions fl(.). In PX, the variable interaction graph (VIG) is decomposed by removing vertices with common variables. Parent variables are inherited together during recombination if they are part of the same connected recombining component of the decomposed VIG. A new way of generating the recombination graph is proposed here. The VIG is decomposed by removing edges associated with subfunctions fl(.) that have similar evaluation for combinations of variables inherited from the parents. By doing so, the partial evaluations of fl(.) are taken into account when decomposing the VIG. This allows the use of partition crossover in continuous optimization. Results of experiments where local optima are recombined indicate that more recombining components are found. When the proposed epsilon-PX (ePX) is compared with other recombination operators in Genetic Algorithms and Differential Evolution, better performance is obtained when the epistasis degree is low.

A parallel ensemble of Genetic Algorithms for the Traveling Salesman Problem (TSP) is proposed. Different TSP solvers perform efficiently on different instance types. However, finding the best solver for all instances is challenging. A hybrid of the Mixing Genetic Algorithm (MGA) and Edge Assembly Crossover (EAX) has been shown to perform well on hard instances. The MGA uses Generalized Partition Crossover (GPX) to find the best and worst out of 2k possible solutions, where k is a decomposition factor of two-parent tours. MGA mixes the edges without any loss of diversity in the population. The best individuals move to the top of the population. The worst individuals are filtered to the bottom of the population. Previously, MGA was applied to TSP instances with less than 4,500 vertices. In this article, various Island Model implementations of MGA are introduced to handle larger problem sizes. The island model uses two mixing policies - migration, which does not lose diversity, and replacement, which loses some population diversity. The islands are configured in two patterns - a ring and a hypercube. An ensemble running multiple versions of an hybrid of MGA and EAX algorithms yields excellent performance for problems as large as 85,900.

While there are many inexact heuristics for generating high quality solutions to the Travelling Salesman Problem, our understanding of why these methods are effective and efficient is still limited. This paper looks at two population based heuristics: the EAX algorithm and the Mixing GA using partition crossover. We show that the local optima used to construct the initial population are also sampling edges found in the global optimum at an extremely high rate: in the majority of TSP instances, the number of global edges in the initial population is more than 73%. Next, we look at how recombination operators increase the representation of edges from the global optimum in the population, or increase the number of global edges in the best solutions in the population. We also look at TSP instances that are more difficult to solve, and again we find that edge frequency information can help to explain algorithm performance. Finally we use these result to suggest new strategies for generating high quality solutions for Travelling Salesman Problems.

There exist general transforms that convert pseudo-Boolean functions into k-bounded pseudo-Boolean functions, for all k ≥ 2. In addition to these general transforms, there can also exist specialized transforms that can be applied in special cases. New results are presented examining what happens to the "bit flip" neighborhood when transforms are applied. Transforms condense variables in a particular order. We show that different variable orderings produce different results in terms of problem difficulty. We also prove new results about the embedding of the original function in the new k-bounded function. Finally, this paper also looks at how parameter optimization problems can be expressed as high precision k-bounded pseudo-Boolean functions. This paper lays a foundation for the wider application of evolutionary algorithms to k-bounded pseudo-Boolean functions.

Generalized Partition Crossover (GPX) is a deterministic recombination operator developed for the Traveling Salesman Problem. Partition crossover operators return the best of [Formula: see text] reachable offspring, where [Formula: see text] is the number of recombining components. This article introduces a new GPX2 operator, which finds more recombining components than GPX or Iterative Partial Transcription (IPT). We also show that GPX2 has O([Formula: see text]) runtime complexity, while also introducing new enhancements to reduce the execution time of GPX2. Finally, we experimentally demonstrate the efficiency of GPX2 when it is used to improve solutions found by the multitrial Lin-Kernighan-Helsgaum (LKH) algorithm. Significant improvements in performance are documented on large ([Formula: see text]) and very large ([Formula: see text]) instances of the Traveling Salesman Problem.

A new evolutionary algorithm called the Mixing Genetic Algorithm is introduced for the Traveling Salesman Problem. The Mixing Genetic Algorithm does not use selection or mutation, and the children replace the parents every generation. The recombination operator is partition crossover. Partition crossover is respectful and transmits alleles (edges); this makes it possible to generate two offspring, the best possible offspring and the worst possible offspring, such that no edges are lost during recombination. The Mixing Genetic Algorithm organizes the population so that better solutions are usually recombined with other good solutions. Because no edges are lost or created during recombination, there is no need to access the evaluation function after the first generation. This dramatically reduces communication costs; this makes it possible to implement the Mixing Genetic Algorithm on massively parallel SIMD machines with limited memory. The Mixing Genetic Algorithm never loses diversity and cannot prematurely converge. We compare the Mixing Genetic Algorithm to EAX, one of the best inexact solvers for the Traveling Salesman Problems. For many problems the Mixing Genetic Algorithm finds optimal solutions using fewer recombinations than EAX.

Partition crossover operators use information about the interaction between decision variables to recombine solutions. The Generalized Asymmetric Partition Crossover (GAPX) was recently proposed for the asymmetric Traveling Salesman Problem (TSP). Unlike former partition crossover operators, GAPX is capable of finding crossover points by splitting vertices of degree 4. GAPX also finds recombining components with more than two crossover points. The first step of GAPX is to define candidate components for recombination by finding connected components in the union graph formed by two parents. Some of the candidate components are infeasible for recombination. However, candidate components can be fused in order to create new recombining components. We introduce a fusion mechanism that allows GAPX to find more recombining components. When k recombining components are found, GAPX generates the best of 2koffspring at cost O(n). When two local optima are recombined by partition crossover, the offspring is very often a local optimum. Fusion can be used to increase k, allowing GAPX to exploit many more offspring. Experimental results show that GAPX with fusion is capable of improving solutions generated by the LKH heuristic. Very good results are also obtained by a hybrid Genetic Algorithm that uses GAPX with fusion.

There are two important challenges for local search algorithms when applied to Maximal Satisfiability (MAXSAT). 1) Local search spends a great deal of time blindly exploring plateaus in the search space and 2) local search is less effective on application instances. This second problem may be related to local search's inability to exploit problem structure. We propose a genetic recombination operator to address both of these issues. On problems with well defined local optima, partition crossover is able to "tunnel" between local optima to discover new local optima in O(n) time. The PXSAT algorithm combines partition crossover and local search to produce a new way to escape plateaus. Partition crossover locally decomposes the evaluation function for a given instance into independent components, and is guaranteed to find the best solution among an exponential number of candidate solutions in O(n) time. Empirical results on an extensive set of application instances show that the proposed framework substantially improves two of best local search solvers, AdaptG2WSAT and Sparrow, on many application instances. PXSAT combined with AdaptG2WSAT is also able to outperform CCLS, winner of several recent MAXSAT competitions.

Partition Crossover is a recombination operator for pseudo-Boolean optimization with the ability to explore an exponential number of solutions in linear or square time. It decomposes the objective function as a sum of subfunctions, each one depending on a different set of variables. The decomposition makes it possible to select the best parent for each subfunction independently and the operator provides the best out of 2q solutions, where q is the number of sub-functions in the decomposition. These subfunctions are defined over the connected components of the recombination graph: a subgraph of the objective function variable interaction graph containing only the differing variables in the two parents. In this paper, we advance further and propose a new way to increase the number of linearly independent subfunctions by analyzing the articulation points of the recombination graph. These points correspond to variables that, once flipped, increase the number of connected components. The presence of a connected component with an articulation point increases the number of explored solutions by a factor of, at least, 4. We evaluate the new operator using Iterated Local Search combined with Partition Crossover to solve NK Landscapes and MAX-SAT.

Accepted version of publication "NK Hybrid Genetic Algorithm for Clustering", published in IEEE Transactions on Evolutionary Computation

In this paper, we propose an optimization algorithm for literature-derived model and parameter identification in multi-valued biological regulatory networks. Our approach is a multi-objective optimization method where the objectives are inspired from structural Efficiency, dynamical Robustness and biological selectivity of cells in their actions. Given an incomplete model derived from literature and partially instrumented clinical observations, our method identifies the optimal model parameterization by maximizing structural Efficiency, dynamical Robustness and Selectivity. As the parameterization space is super exponential, we implemented our method in a constraint satisfaction framework by defining logical equivalences of the dynamical features. The implemented framework is then solved with a lazy clause solver known as Chuffed. We apply our method on female Hypothalamic-Pituitary-Gonadal axis (HPG) and demonstrate how it is able to identify a model that reproduces the complex menstrual cycle. The algorithm found a structure and parameterization for the 5 node 14 edge (≈ 50% edge density) HPG model with a normalized length cost and robustness of 1.46 and 0.35 respectively in 713 seconds on an Intel core i7 machine.Our method discovered that there are at least 6 more regulatory interactions that must be added to the commonly accepted HPG basic model in order to reproduce the menstrual cycle efficiently and robustly. The discovery of additional interactions suggest that our algorithm provides new insight to the biological model identification by combining the information from literature, clinical measurements and dynamical parameters.

In gray-box optimization, the search algorithms have access to the variable interaction graph (VIG) of the optimization problem. For Mk Landscapes (and NK Landscapes) we can use the VIG to identify an improving solution in the Hamming neighborhood in constant time. In addition, using the VIG, deterministic Partition Crossover is able to explore an exponential number of solutions in a time that is linear in the size of the problem. Both methods have been used in isolation in previous search algorithms. We present two new gray-box algorithms that combine Partition Crossover with highly efficient local search. The best algorithms are able to locate the global optimum on Adjacent NK Landscape instances with one million variables. The algorithms are compared with a state-of-the-art algorithm for pseudo-Boolean optimization: Gray-Box Parameterless Population Pyramid. The results show that the best algorithm is always one combining Partition Crossover and highly efficient local search. But the results also illustrate that the best optimizer differs on Adjacent and Random NK Landscapes.

A genetic algorithm using Edge Assemble Crossover (EAX) is one of the best heuristic solvers for large instances of the Traveling Salesman Problem. We propose using Partition Crossover to recombine solutions produced by EAX. Partition Crossover is a powerful deterministic recombination that is highly exploitive. When Partition Crossover decomposes two parents into q recombining components, partition crossover returns the best of 2q reachable offspring. If two parents are locally optimal, all of the offspring are also locally optimal in a hyperplane subspace that contains the two parents. One disadvantage of Partition Crossover, however, is that it cannot generate new edges. By contrast, the EAX operator is highly explorative; it not only inherits edges from parents, it also introduces new edges into the population of a genetic algorithm. Using both EAX and Partition Crossover together produces better performance, with improved exploitation and exploration.

The best known exact solver for generating provably optimal solutions to the Traveling Salesman Problem (TSP) is the Concorde algorithm. Concorde uses a branch and bound search strategy, as well as cutting planes to reduce the search space. The first step in using Concorde is to obtain a good initial solution. A good solution can be generated using a heuristic solver outside of Concorde, or Concorde can generate its own initial solution using the Chained Lin Kernighan (LK) algorithm. In this paper, we speed up Concorde by improving the initial solutions produced by Chained LK using Partition Crossover. Partition Crossover is a powerful deterministic recombination operator that is able to tunnel between local optima. In every instance we examined, the addition of recombination resulted in an average speed-up of Concorde, and in the majority of cases, the difference in the runtime costs was statistically significant.

Efficient hill climbers have been recently proposed for single- and multi-objective pseudo-Boolean optimization problems. For k-bounded pseudo-Boolean functions where each variable appears in at most a constant number of subfunctions, it has been theoretically proven that the neighborhood of a solution can be explored in constant time. These hill climbers, combined with a high-level exploration strategy, have shown to improve state of the art methods in experimental studies and open the door to the so-called Gray Box Optimization, where part, but not all, of the details of the objective functions are used to better explore the search space. One important limitation of all the previous proposals is that they can only be applied to unconstrained pseudo-Boolean optimization problems. In this work, we address the constrained case for multi-objective k-bounded pseudo-Boolean optimization problems. We find that adding constraints to the pseudo-Boolean problem has a linear computational cost in the hill climber.

The use of good evaluation functions is essential when evolutionary algorithms are employed for clustering. The NK internal clustering validation measure is proposed for hard partitional clustering. The evaluation function is composed of N subfunctions, where N is the number of objects in the dataset. Each subfunction is influenced by a group of K+1 objects. By using neighbourhood relations among connected small groups, density-based regions can be identified. The NK internal clustering validation measure allows the application of partition crossover (PX). PX for hard partitional clustering is also proposed in this work. By using PX, the evaluation function can be decomposed in q partial evaluations. As a consequence, PX deterministically finds the best of 2q possible offspring at the cost of evaluating 2 solutions. In the experiments, the application of PX resulted in a high number of successful recombinations. It was able to improve partitions defined by the best parents.

We observed that Conjunctive Normal Form (CNF) encodings of structured SAT instances often have a set of consecutive clauses defined over a small number of Boolean variables. To exploit the pattern, we propose a transformation of CNF to an alternative representation, Conjunctive Minterm Canonical Form (CMCF). The transformation is a two-step process: CNF clauses are first partitioned into disjoint subsets such that each subset contains CNF clauses with shared Boolean variables. CNF clauses in each subset are then replaced by Minterm Canonical Form (i.e., partial solutions), which is found by enumeration. We show empirically that a simple Stochastic Local Search (SLS) solver based on CMCF can consistently achieve a higher success rate using fewer evaluations than the SLS solver WalkSAT on two representative classes of structured SAT problems.

This article investigates Gray Box Optimization for pseudo-Boolean optimization problems composed of M subfunctions, where each subfunction accepts at most k variables. We will refer to these as Mk Landscapes. In Gray Box Optimization, the optimizer is given access to the set of M subfunctions. We prove Gray Box Optimization can efficiently compute hyperplane averages to solve non-deceptive problems in [Formula: see text] time. Bounded separable problems are also solved in [Formula: see text] time. As a result, Gray Box Optimization is able to solve many commonly used problems from the evolutional computation literature in [Formula: see text] evaluations. We also introduce a more general class of Mk Landscapes that can be solved using dynamic programming and discuss properties of these functions. For certain type of problems Gray Box Optimization makes it possible to enumerate all local optima faster than brute force methods. We also provide evidence that randomly generated test problems are far less structured than those found in real-world problems.

A partition crossover operator is introduced for use with NK landscapes, MAX-kSAT and for all k-bounded pseudo-Boolean functions. By definition, these problems use a bit representation. Under partition crossover, the evaluation of offspring can be directly obtained from partial evaluations of substrings found in the parents. Partition crossover explores the variable interaction graph of the pseudo-Boolean functions in order to partition the variables of the solution vector. Proofs are presented showing that if the differing variable assignments found in the two parents can be partitioned into q non-interacting sets, partition crossover can be used to find the best of 2q possible offspring. Proofs are presented which show that parents that are locally optimal will always generate offspring that are locally optimal with respect to a (more restricted) hyperplane subspace. Empirical experiments show that parents that are locally optimal generate offspring that are locally optimal in the full search space more than 80 percent of the time. Experimental results also show the effectiveness of the proposed crossover when used in combination with a hybrid genetic algorithm.

Local optima networks are a recent model of fitness landscapes. They compress the landscape by representing local optima as nodes, and search transitions among them as edges. Previous local optima networks considered transitions based on mutation; this study looks instead at transitions based on deterministic recombination. We define and analyse networks based on the recently proposed partition crossover for k-bounded pseudo-Boolean functions, using NKq landscapes as a case study. Partition crossover was initially proposed for the travelling salesman problem, where it was found to ``tunnel" between local optima, i.e., jump from local optimum to local optimum. Our network analysis shows that this also happens for NK landscapes: local optima are densely connected via partition crossover. We found marked differences between the adjacent and random interaction NK models. Surprisingly, with the random model, instances have a lower number of local optima on average, but their networks are more sparse and decompose into several clusters. There is also large variability in the size and pattern of connectivity of instances coming from the same landscape parameter values. These network features offer new insight informing why some instances are harder to solve than others.

This paper investigates Gray Box Optimization for pseudo-Boolean optimization problems composed of M subfunctions, where each subfunction accepts at most k variables. We will refer to these as Mk Landscapes. In Gray Box optimization, the optimizer is given access to the set of M subfunctions. If the set of subfunctions is k-bounded and separable, the Gray Box optimizer is guaranteed to return the global optimum with 1 evaluation. A problem is said to be order k deceptive if the average values of hyperplanes over combinations of k variables cannot be used to infer a globally optimal solution. Hyperplane averages are always efficiently computable for Mk Landscapes. If a problem is not deceptive, the Gray Box optimizer also returns the global optimum after 1 evaluation. Finally, these concepts are used to understand the nonlinearity of problems in the complexity class P, such as Adjacent NK Landscapes. These ideas are also used to understand the problem structure of NP Hard problems such as MAX-kSAT and general Mk Landscapes. In general, NP Hard problems are profoundly deceptive.

Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in p, the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem (Onemax), and an NP-hard problem, MAX-SAT. We also discuss a connection of the results with runtime analysis.

Hill climbing algorithms are at the core of many approaches to solve optimization problems. Such algorithms usually require the complete enumeration of a neighborhood of the current solution. In the case of problems defined over binary strings of length n, we define the r-ball neighborhood as the set of solutions at Hamming distance r or less from the current solution. For r ll n this neighborhood contains Θ(nr) solutions. In this paper efficient methods areintroduced to locate improving moves in the r-ball neighborhood for problems that can be written as a sum of a linear number of subfunctions depending on a bounded number of variables. NK-landscapes and MAX-kSAT are examples of these problems. If the number of subfunctions depending on any given variable is also bounded, then we prove that the method can explore the neighborhood in constant time, despite the fact that the number of solutions in the neighborhood is polynomial in n. We develop a hill climber based on our exploration method and we analyze its efficiency and efficacy using experiments with NKq-landscapes instances.

Subtle Higher Order Mutants (HOMs) are those HOMs that cannot be killed by existing test suites that kill all First Order Mutants (FOMs) for the program under test. Subtle HOMs simulate complex, real faults, whose behavior cannot be simulated using FOMs. However, due to the coupling effect, subtle HOMs are rare in the exponentially large space of candidate HOMs and they can be costly to find even for small programs.

In the dynamic traveling salesman problem (DTSP), the weights and vertices of the graph representing the TSP are allowed to change during the optimization. This work first discusses some issues related to the use of evolutionary algorithms in the DTSP. When efficient algorithms used for the static TSP are applied with restart in the DTSP, we observe that only some edges are generally inserted in and removed from the best solutions after the changes. This result indicates a possible beneficial use of memory approaches, usually employed in cyclic dynamic environments. We propose a memory approach and a hybrid approach that combines our memory approach with the elitism-based immigrants genetic algorithm (EIGA). We compare these two algorithms to four existing algorithms and show that memory approaches can be beneficial for the DTSP with random changes.

The Generalized Partition Crossover (GPX) constructs new solutions for the Traveling Salesman Problem (TSP) by finding recombining partitions with one entry and one exit in the graph composed by the union of two parent solutions. If there are k recombining partitions in the union graph, 2^k-2 solutions are simultaneously exploited by GPX. Generalized Asymmetric Partition Crossover (GAPX) is introduced; it finds more recombining partitions and can also find partitions for the asymmetric TSP. GAPX does this by locating partitions that cut vertices of degree 4 in the union graph and by finding partitions with multiple entry and exit points, both in O(n) time. GAPX can improve the quality of solutions generated by the Lin-Kernighan-Helsgaun heuristic and improve the state of the art for the asymmetric TSP.

Stochastic local search (SLS) is the dominant paradigm for incomplete SAT and MAXSAT solvers. Early studies on small 3SAT instances found that the use of “best improving” moves did not improve search compared to using an arbitrary “first improving” move. Yet SLS algorithms continue to use best improving moves. We revisit this issue by studying very large random and industrial MAXSAT problems. Because locating best improving moves is more expensive than first improving moves, we designed an “approximate best” improving move algorithm and prove that it is as efficient as first improving move SLS. For industrial problems the first local optima found using best improving moves are statistically significantly better than local optima found using first improving moves. However, this advantage reverses as search continues and algorithms must explore equal moves on plateaus. This reversal appears to be associated with critical variables that are in many clauses and that also yield large improving moves.

Local search methods based on explicit neighborhood enumeration require at least $O(n)$ time to identify all possible improving moves. For k-bounded pseudo-Boolean optimization problems, recent approaches have achieved $O(k^2*2^{k})$ runtime cost per move, where $n$ is the number of variables and $k$ is the number of variables per subfunction. Even though the bound is independent of $n$, the complexity per move is still exponential in $k$. In this paper, we propose a second order partial derivatives-based approach that executes first-improvement local search where the runtime cost per move is time polynomial in $k$ and independent of $n$. This method is applied to NK-landscapes, where larger values of $k$ may be of particular interest.

By converting the MAXSAT problem to Walsh polynomials, we can efficiently and exactly compute the hyperplane averages of fixed order k. We use this fact to construct initial solutions based on variable configurations that maximize the sampling of hyperplanes with good average evaluations. The Walsh coefficients can also be used to implement a constant time neighborhood update which is integral to a fast next descent local search for MAXSAT (and for all bounded pseudo-Boolean optimization problems.) We evaluate the effect of initializing local search with hyperplane averages on both the first local optima found by the search and the final solutions found after a fixed number of bit flips. Hyperplane initialization not only provides better evaluations, but also finds local optima closer to the globally optimal solution in fewer bit flips than search initialized with random solutions. A next descent search initialized with hyperplane averages is able to outperform several state-of-the art stochastic local search algorithms on both random and industrial instances of MAXSAT.

One goal of higher order mutation testing is to produce higher order mutants (HOMs) that represent subtle faults. We define subtle HOMs as those that are not killed by an existing test set that kills all the first order mutants of a given program. The fault detection effectiveness of the test set can be improved by adding test cases that kill subtle HOMs. However, finding subtle HOMs can be costly even for small programs because of the large space of candidate HOMs. Moreover, a large majority of HOMs are killed by test sets that kill all first order mutants, making the subtle ones relatively rare. We introduce three search-based algorithms (Genetic Algo-rithm, Local Search, and Random Search) for finding subtle HOMs in Java and AspectJ programs. All three algorithms found subtle HOMs for all studied programs but Local Search was more successful in finding subtle HOMs than Genetic Algorithm and Random Search.

The frequency distribution of a fitness function over regions of its domain is an important quantity for understanding the behavior of algorithms that employ randomized sampling to search the function. In general, exactly characterizing this distribution is at least as hard as the search problem, since the solutions typically live in the tails of the distribution. However, in some cases it is possible to efficiently retrieve a collection of quantities (called moments) that describe the distribution. In this paper, we consider functions of bounded epistasis that are defined over length-n strings from a finite alphabet of cardinality q. Many problems in combinatorial optimization can be specified as search problems over functions of this type. Employing Fourier analysis of functions over finite groups, we derive an efficient method for computing the exact moments of the frequency distribution of fitness functions over Hamming regions of the q-ary hypercube. We then use this approach to derive equations that describe the expected fitness of the offspring of any point undergoing uniform mutation. The results we present provide insight into the statistical structure of the fitness function for a number of combinatorial problems. For the graph coloring problem, we apply our results to efficiently compute the average number of constraint violations that lie within a certain number of steps of any coloring. We derive an expression for the mutation rate that maximizes the expected fitness of an offspring at each fitness level. We also apply the results to the slightly more complex frequency assignment problem, a relevant application in the domain of the telecommunications industry. As with the graph coloring problem, we provide formulas for the average value of the fitness function in Hamming regions around a solution and the expectation-optimal mutation rate.

Uniform crossover is a popular operator used in genetic algorithms to combine two tentative solutions of a problem represented as binary strings. We use the Walsh decomposition of pseudo-Boolean functions and properties of Krawtchouk matrices to exactly compute the expected value for the fitness of a child generated by uniform crossover from two parent solutions. We prove that this expectation is a polynomial in Á, the probability of selecting the best-parent bit. We provide efficient algorithms to compute this polynomial for ONEMAX and MAX-kSAT problems, but the results also hold for domains such as NK-Landscapes.

A modified form of steepest descent local search is proposed that displays an average complexity of O(1) time per move for NK-Landscape and MAX-kSAT problems. The algorithm uses a Walsh decomposition to identify improving moves. In addition, it is possible to compute a Hamming distance 2 statistical lookahead: if x is the current solution and y is a neighbor of x, it is possible to compute the average evaluation of the neighbors of y. The average over the Hamming distance 2 neighborhood can be used as a surrogate evaluation function to replace f. The same modified steepest descent can be executed in O(1) time using the Hamming distance 2 neighborhood average as the fitness function. In practice, the modifications needed to prove O(1) complexity can be relaxed with little or no impact on runtime performance. Finally, steepest descent local search over the mean of the Hamming distance 2 neighborhood yields superior results compared to using the standard evaluation function for certain types of NK-Landscape problems.

When the epistasis of the fitness function is bounded by a constant, we show that the expected fitness of an offspring of the (1+1)-EA can be efficiently computed for any point. Moreover, we show that, for any point, it is always possible to efficiently retrieve the "best" mutation rate at that point in the sense that the expected fitness of the resulting offspring is maximized. On linear functions, it has been shown that a mutation rate of 1/n is provably optimal. On functions where epistasis is bounded by a constant k, we show that for sufficiently high fitness, the commonly used mutation rate of 1/n is also best, at least in terms of maximizing the expected fitness of the offspring. However, we find for certain ranges of the fitness function, a better mutation rate can be considerably higher, and can be found by solving for the real roots of a degree-k polynomial whose coefficients contain the nonzero Walsh coefficients of the fitness function. Simulation results on maximum k-satisfiability problems and NK-landscapes show that this expectation-maximized mutation rate can cause significant gains early in search.

The Traveling Salesman Problem (TSP) is known to display an elementary landscape under all k-opt move operators. Previous work has also shown that partial neighborhoods may exist that retain some properties characteristic of elementary landscapes. For a tour of n cities, we show that the 2-opt neighborhood can be decomposed into n/2-1 partial neighborhoods. While this paper focuses on the TSP, it also introduces a more formal treatment of partial neighborhoods which applies to all elementary landscapes. Tracking partial neighborhood averages in elementary landscapes requires partitioning the cost matrix. After every move in the search space, the relevant partitions must be updated. However, just as the evaluation function allows a partial update for the TSP, there also exists a partial update for the cost matrix partitions. By only looking at a subset of the partial neighborhoods we can further reduce the cost of updating the cost matrix partitions.

A small number of combinatorial optimization problems have search spaces that correspond to elementary landscapes, where the objective function f is an eigenfunction of the Laplacian that describes the neighborhood structure of the search space. Many problems are not elementary; however, the objective function of a combinatorial optimization problem can always be expressed as a superposition of multiple elementary landscapes if the underlying neighborhood used is symmetric. This paper presents theoretical results that provide the foundation for algebraic methods that can be used to decompose the objective function of an arbitrary combinatorial optimization problem into a sum of subfunctions, where each subfunction is an elementary landscape. Many steps of this process can be automated, and indeed a software tool could be developed that assists the researcher in finding a landscape decomposition. This methodology is then used to show that the subset sum problem is a superposition of two elementary landscapes, and to show that the quadratic assignment problem is a superposition of three elementary landscapes.

Data anonymization techniques have received extensive attention in the privacy research community over the past several years. Various models of privacy preservation have been proposed: k-anonymity, ℓ-diversity and t-closeness, to name a few. An oft-cited drawback of these models is that there is considerable loss in data quality arising from the use of generalization and suppression techniques. Optimization attempts in this context have so far focused on maximizing the data utility for a pre-specified level of privacy. To determine if better privacy levels are obtainable with the same level of data utility, majority of the existing formulations require exhaustive analysis. Further, the data publisher's perspective is often missed in the process. The publisher wishes to maintain a given level of data utility (since the data utility is the revenue earner) and then maximize the level of privacy within acceptable limits. In this paper, we explore this privacy versus data quality trade-off as a multi-objective optimization problem. Our goal is to provide substantial information to a data publisher about the trade-offs available between the privacy level and the information content of an anonymized data set.

Privacy constraints are typically enforced on shared data that contain sensitive personal attributes. However, owing to its adverse effect on the utility of the data, information loss must be minimized while sanitizing the data. Existing methods for this purpose modify the data only to the extent necessary to satisfy the privacy constraints, thereby asserting that the information loss has been minimized. However, given the subjective nature of information loss, it is often difficult to justify such an assertion. In this paper, we propose an interactive procedure to generate a data generalization scheme that optimally meets the preferences of the data publisher. A data publisher guides the sanitization process by specifying aspirations in terms of desired achievement levels in the objectives. A reference direction based methodology is used to investigate neighborhood solutions if the generated scheme is not acceptable. This approach draws its power from the constructive input received from the publisher about the suitability of a solution before finding a new one.

We analyze various forms of the Frequency Assignment Problem using the theory of elementary landscapes. We show that three variants of the Frequency Assignment Problem are either directly an Elementary Landscape, or are a superposition of two Elementary Landscapes. We also examine the computability of neighborhood averages for partial neighborhoods.

Location obfuscation using cloaking regions preserves location anonymity by hiding the true user among a set of other equally likely users. Furthermore, a cloaking region should also guarantee that the type of queries issued by users within the region are mutually diverse enough. The first requirement is fulfilled by satisfying location k-anonymity while the second one is ensured by satisfying query l-diversity. However, these two models are not sufficient to prevent the association of queries to users when the service depends on continuous location updates. Successive cloaking regions for a user may be k-anonymous and query l-diverse but still be prone to correlation attacks. In this paper, we provide a formal analysis of the privacy risks involved in a continuous location-based service, and show how continuous queries can invalidate the privacy guarantees provided by k-anonymity and l-diversity. Drawing upon the principle of m-invariance in database privacy, we show how query m-invariance can provide location and query privacy in continuous services.

Local search algorithms for MAX-k-SAT must often explore large regions of mutually connected equal moves, or plateaus, typically by taking random walks through the region. In this paper, we develop a surrogate plateau "gradient" function using a Walsh transform of the objective function. This function gives the mean value of the objective function over localized volumes of the search space. This information can be used to direct search through plateaus more quickly. The focus of this paper is on demonstrating that formal analysis of search space structure can direct existing algorithms in a more principled manner than random walks. We show that embedding the gradient computation into a hill-climbing local search for MAX-k-SAT improves its convergence profile.

We present an adaptive framework for condensation algorithms in the context of human-face tracking. We attack the face tracking problem by making factored sampling more efficient and appearance update more effective. An adaptive affine cascade factored sampling strategy is introduced to sample the parameter space such that coarse face locations are located first, followed by a fine factored sampling with a small number of particles. In addition, the local linearity of an appearance manifold is used in conjunction with a new criterion to select a tangent plane for updating an appearance in face tracking. Our proposed method seeks the best linear variety from the selected tangent plane to form a reference image. We demonstrate the effectiveness and efficiency of the proposed method on a number of challenging videos. These test video sequences show that our method is robust to illumination, appearance, and pose changes, as well as temporary occlusions. Quantitatively, our method achieves the average root-mean-square error at 4.98 on the well-known dudek video sequence while maintaining a proficient speed at 8.74 fps. Finally, while our algorithm is adaptive during execution, no training is required.

Data generalization is widely used to protect identities and prevent inference of sensitive information during the public release of microdata. The k-anonymity model has been extensively applied in this context. The model seeks a generalization scheme such that every individual becomes indistinguishable from at least k-1 other individuals and the loss in information while doing so is kept at a minimum. The search is performed on a domain hierarchy lattice where every node is a vector signifying the level of generalization for each attribute. An effort to understand privacy and data utility trade-offs will require knowing the minimum possible information losses of every possible value of k. However, this can easily lead to an exhaustive evaluation of all nodes in the hierarchy lattice. In this paper, we propose using the concept of Pareto-optimality to obtain the desired trade-off information. A Pareto-optimal generalization is one in which no other generalization can provide a higher value of k without increasing the information loss. We introduce the Pareto-Optimal k-Anonymization (POkA) algorithm to traverse the hierarchy lattice and show that the number of node evaluations required to find the Pareto-optimal generalizations can be significantly reduced. Results on a benchmark data set show that the algorithm is capable of identifying all Pareto-optimal nodes by evaluating only 20% of nodes in the lattice.

Privacy models such as k-anonymity and l-diversity typically offer an aggregate or scalar notion of the privacy property that holds collectively on the entire anonymized data set. However, they fail to give an accurate measure of privacy with respect to the individual tuples. For example, two anonymizations achieving the same value of k in the k-anonymity model will be considered equally good with respect to privacy protection. However, it is quite possible that for one of the anonymizations a majority of the individual tuples have lesser probabilities of privacy breaches than their counterparts in the other anonymization. We therefore reject the notion that all anonymizations satisfying a particular privacy property, such as k-anonymity, are equally good. The scalar or aggregate value used in privacy models is often biased towards a fraction of the data set, resulting in higher privacy for some individuals and minimalistic for others. Consequently, to better compare anonymization algorithms, there is a need to formalize and measure this bias. Towards this end, we advocate the use of vector-based methods for representing privacy and other measurable properties of an anonymization. We represent the measure of a given property for an anonymized data set using a property vector. Anonymizations are then compared using quality index functions that quantify the effectiveness of the property vectors. A formal analysis with respect to their scope and limitations is provided. Finally, we present preference based techniques when comparisons are to be made across multiple properties induced by anonymizations.

Public data sharing is utilized in a number of businesses to facilitate the exchange of information. Privacy constraints are usually enforced to prevent unwanted inference of information, specially when the shared data contain sensitive personal attributes. This, however, has an adverse effect on the utility of the data for statistical studies. Thus, a requirement while modifying the data is to minimize the information loss. Existing methods employ the notion of "minimal distortion" where the data is modified only to the extent necessary to satisfy the privacy constraint, thereby asserting that the information loss has been minimized. However, given the subjective nature of information loss, it is often difficult to justify this assertion. In this paper, we propose an evolutionary algorithm to explicitly minimize an achievement function given constraints on the privacy level of the transformed data. Privacy constraints specified in terms of anonymity models are modeled as additional objectives and an evolutionary multi-objective approach is proposed. We highlight the requirement to minimize any bias induced by the anonymity model and present a scalarization incorporating preferences in information loss and privacy bias as the achievement function.

The autocorrelation function and related correlation length are statistical quantities that capture the ruggedness of the fitness landscape: a measure that is directly related to the hardness of a problem for certain heuristic search algorithms. Typically, these quantities are estimated empirically by sampling along a random walk. In this paper, we show that a polynomial-time Walsh decomposition of the k-satisfiability evaluation function allows us to compute the exact autocorrelation function and correlation length for any given k-satisfiability instance. We also use the decomposition to compute a theoretical expectation for the autocorrelation function and correlation length over the ensemble of instances generated uniformly at random. We find that this expectation is invariant to the constrainedness of the problem as measured by the ratio of clauses to variables. However, we show that filtered problems, which are typically used in local search studies, have a bias that causes a significant deviation from the expected correlation structure of unfiltered, uniformly generated problems.

A new recombination operator is introduced for the Traveling Salesman Problem called partition crossover. Theoretical and empirical results indicate that when two local optima are recombined using partition crossover, two offspring are produced that are highly likely to also be local optima. Thus, the operator is capable of jumping or tunneling from two local optima to two new and distinct local optima without searching intermediate solutions. The operator is respectful and it transmits alleles which means that 1) all common edges from the two parents are inherited and 2) the offspring are constructed using only edges inherited from the two parents. Partition crossover is not always feasible: sometimes two new Hamiltonian circuits cannot be constructed by the operator using only edges inherited from the two parents. But empirical results indicate that partition crossover is feasible 95 percent of the time when recombining randomly selected local optima. Furthermore, from a sample of local optima that are within a short random walk of the global optimum, partition crossover typically relocates the global optimum in a single move when crossover is feasible.

This paper introduces a new component based model that makes it relatively simple to prove that certain types of landscapes are elementary. We use the model to reconstruct proofs for the Traveling Salesman Problem, Graph Coloring and Min-Cut Graph Partitioning. The same model is then used to efficiently compute the average values over particular partial neighborhoods for these same problems. For Graph Coloring and Min-Cut Graph Partitioning, this computation can be used to focus search on those moves that are most likely to yield an improving move, ignoring moves that cannot yield an improving move. Let x be a candidate solution with objective function value f(x). The mean value of the objective function over the entire landscape is denoted f. Normally in an elementary landscape one can only be sure that a neighborhood includes an improving move (assuming minimization) if f(x) > f. However, by computing the expected value of an appropriate partial neighborhood it is sometimes possible to know that an improving move exists in the partial neighborhood even when f(x) < f.

Data dissemination in pervasive environments is often accomplished by on-demand broadcasting. The time critical nature of the data requests plays an important role in scheduling these broadcasts. Most research in on-demand broadcast scheduling has focused on the timely servicing of requests so as to minimize the number of missed deadlines. However, there exists many pervasive environments where the utility of the data is an equally important criterion as its timeliness. Missing the deadline reduces the utility of the data but does not make it zero. In this work, we address the problem of scheduling on-demand data broadcasts with soft deadlines. We investigate search based optimization techniques to develop broadcast schedulers that make explicit attempts to maximize the utility of data requests as well as service as many requests as possible within the acceptable time limit. Our analysis shows that heuristic driven methods for such problems can be improved by hybridizing them with local search algorithms. We further investigate the option of employing a dynamic optimization technique to facilitate utility gain, thereby surpassing the requirement of a heuristic in the process. An evolution strategy based stochastic hill climber is investigated in this context.

Data broadcasting makes effective use of low bandwidth and is commonly used in applications involving mobile devices. We consider the case where data must be broadcast in a particular order and within a specified response time. However, communication bottlenecks prohibit the timely serving of all requests; although, missing the deadline does not make the data utility zero. In this work, we consider the problem of real-time data broadcast scheduling in the presence of soft deadlines together with constraints on the order in which data-items should be broadcast to be useful. We explore the method of evolution strategy to solve the problem, keeping in view that the real-time scheduler has to effectively trade-off between its running time and the quality of schedules generated.

Proofs and empirical evidence are presented which show that a subset of algorithms can have identical performance over a subset of functions, even when the subset of functions is not closed under permutation. We refer to these as focused sets. In some cases focused sets correspond to the orbit of a permutation group; in other cases, the focused sets must be computed heuristically. In the smallest case, two algorithms can have identical performance over just two functions in a focused set. These results particularly exploit the case where search is limited to m steps, where m is significantly smaller than the size of the search space.

The landscape formalism unites a finite candidate solution set to a neighborhood topology and an objective function. This construct can be used to model the behavior of local search on combinatorial optimization problems. A landscape is elementary when it possesses a unique property that results in a relative smoothness and decomposability to its structure. In this paper we explain elementary landscapes in terms of the expected value of solution components which are transformed in the process of moving from an incumbent solution to a neighboring solution. We introduce new results about the properties of elementary landscapes and discuss the practical implications for search algorithms.

When disseminating data involving human subjects, researchers have to weigh in the requirements of privacy of the individuals involved in the data. A model widely used for enhancing individual privacy is k-anonymity, where an individual data record is rendered similar to k - 1 other records in the data set by using generalization and/or suppression operations on the data attributes. The drawback of this model is that such transformations result in considerable loss of information that is proportional to the choice of k. Studies in this context have so far focused on minimizing the information loss for some given value of k. However, owing to the presence of outliers, a specified k value may or may not be obtainable. Further, an exhaustive analysis is required to determine a k value that fits the loss constraint specified by a data publisher. In this paper, we formulate a multi-objective optimization problem to illustrate that the decision on k can be much more informed than being a choice solely based on the privacy requirement. The optimization problem is intended to resolve the issue of data privacy when data suppression is not allowed in order to obtain a particular value of k. An evolutionary algorithm is employed here to provide this insight.

Researchers have previously looked into the problem of determining if a given set of security hardening measures can effectively make a networked system secure. Many of them also addressed the problem of minimizing the total cost of implementing these hardening measures, given costs for individual measures. However, system administrators are often faced with a more challenging problem since they have to work within a fixed budget which may be less than the minimum cost of system hardening. Their problem is how to select a subset of security hardening measures so as to be within the budget and yet minimize the residual damage to the system caused by not plugging all required security holes. In this work, we develop a systematic approach to solve this problem by formulating it as a multi-objective optimization problem on an attack tree model of the system and then use an evolutionary algorithm to solve it.

Recent results show that the Differential Evolution algorithm has significant difficulty on functions that are not linearly separable. On such functions, the algorithm must rely primarily on its differential mutation procedure which, unlike its recombination strategy, is rotationally invariant. We conjecture that this mutation strategy lacks sufficient selective pressure when appointing parent and donor vectors to have satisfactory exploitative power on non-separable functions. We find that imposing pressure in the form of rank-based differential mutation results in a significant improvement of exploitation on rotated benchmarks.

An algorithm independent metric is introduced that measures the dispersion of a uniform random sample drawn from the top ranked percentiles of the search space. A low dispersion function is one where the dispersion decreases as the sample is restricted to better regions of the search space. A high dispersion function is one where dispersion stay constant or increases as the sample is restricted to better regions of the search space. This distinction can be used to explain why the CMA Evolution Strategy is more efficient on some multimodal problems than on others.

Recent dissemination of personal data has created an important optimization problem: what is the minimal transformation of a dataset that is needed to guarantee the anonymity of the underlying individuals? One natural representation for this problem is a bit-string, which makes a genetic algorithm a logical choice for optimization. Unfortunately, under certain realistic conditions, not all bit combinations will represent valid solutions. This means that in many instances, useful solutions are sparse in the search space. We implement a new crossover operator that preserves valid solutions under this representation. Our results show that this reproductive strategy is more efficient, effective, and robust than previous work. We also investigate how the population size and uniqueness can affect the performance of genetic search on this application.

Particle Swarm Optimization (PSO) is a population-based optimization method in which search points employ a cooperative strategy to move toward one another. In this paper we show that PSO appears to work well on optimization functions. On more complex optimization problems, PSO tends to converge too quickly and then fail to make further progress. We contend that most benchmarks for PSO have classically been demonstrated on single-funnel functions. However, in practice, optimization tasks are more complex and possess higher problem dimensionality. We present empirical results that support our conjecture that PSO performs well on single-funnel functions but tends to stagnate on more complicated landscapes.

In contrast with the diverse array of genetic algorithms, the Genetic Programming (GP) paradigm is usually applied in a relatively uniform manner. Heuristics have developed over time as to which replacement strategies and selection methods are best. The question addressed in this paper is relatively simple: since there are so many variants of evolutionary algorithm, how well do some of the other well known forms of evolutionary algorithm perform when used to evolve programs trees using s-expressions as the representation? Our results suggest a wide range of evolutionary algorithms are all equally good at evolving programs, including the simplest evolution strategies.

The best performing algorithms for a particular oversubscribed scheduling application, Air Force Satellite Control Network (AFSCN) scheduling, appear to have little in common. Yet, through careful experimentation and modeling of performance in real problem instances, we can relate characteristics of the best algorithms to characteristics of the application. In particular, we find that plateaus dominate the search spaces (thus favoring algorithms that make larger changes to solutions) and that some randomization in exploration is critical to good performance (due to the lack of gradient information on the plateaus). Based on our explanations of algorithm performance, we develop a new algorithm that combines characteristics of the best performers; the new algorithm's performance is better than the previous best. We show how hypothesis driven experimentation and search modeling can both explain algorithm performance and motivate the design of a new algorithm.

Testing of VLSI circuits can cause generation of excessive heat which can damage the chips under test. In the random testing environment, high-performance CMOS circuits consume significant dynamic power during testing because of enhanced switching activity in the internal nodes. Our work focuses on the fact that power minimization is a traveling salesman problem (TSP). We explore application of local search and genetic algorithms to test set reordering and perform a quantitative comparison to previously used deterministic techniques. We also consider reduction of the original test set as a dual-objective optimization problem, where switching activity and fault coverage are the two objective functions.

The global search properties of heuristic search algorithms are not well understood. In this paper, we introduce a new metric, mobility, that quantifies the dispersion of local optima visited during a search. This allows us to explore two questions: How disperse are the local optima visited during a search? How does mobility relate to algorithm performance? We compare local search with two evolutionary algorithms, CHC and CMA-ES, on a set of non-separable, non-symmetric, multi-modal test functions. Given our mobility metric, we show that algorithms visiting more disperse local optima tend to be better optimizers.

We present a Genetic Programming approach to evolve cooperative controllers for teams of UAVs. Our focus is a collaborative search mission in an uncertain and/or hostile environment. The controllers are decision trees constructed from a set of low-level functions. Evolved decision trees are robust to changes in initial mission parameters and approach the optimal bound for time-to-completion. We compare results between steady-state and generational approaches, and examine the effects of two common selection operators.

Tournament selection is a popular form of selection which is commonly used with genetic algorithms, genetic programming and evolutionary programming. However, tournament selection introduces a sampling bias into the selection process. We review analytic results and present empirical evidence that shows this bias has a significant impact on search performance. We introduce two new forms of unbiased tournament selection that remove or reduce sampling bias in tournament selection.

The well-known Griewangk function, used for evaluation of evolutionary algorithms, becomes easier as the number of dimensions grows. This paper suggests three alternative implementations that maintain function complexity for high-dimensional versions of the problem. Diagonal slices of the search landscape and local search are used to demonstrate and evaluate the difficulty of each function.

Tabu search is one of the most effective heuristics for locating high-quality solutions to a diverse array of NP-hard combinatorial optimization problems. Despite the widespread success of tabu search, researchers have a poor understanding of many key theoretical aspects of this algorithm, including models of the high-level run-time dynamics and identification of those search space features that influence problem difficulty. We consider these questions in the context of the job-shop scheduling problem (JSP), a domain where tabu search algorithms have been shown to be remarkably effective. Previously, we demonstrated that the mean distance between random local optima and the nearest optimal solution is highly correlated with problem difficulty for a well-known tabu search algorithm for the JSP introduced by Taillard. In this paper, we discuss various shortcomings of this measure and develop a new model of problem difficulty that corrects these deficiencies. We show that Taillard's algorithm can be modeled with high fidelity as a simple variant of a straightforward random walk. The random walk model accounts for nearly all of the variability in the cost required to locate both optimal and sub-optimal solutions to random JSPs, and provides an explanation for differences in the difficulty of random versus structured JSPs. Finally, we discuss and empirically substantiate two novel predictions regarding tabu search algorithm behavior. First, the method for constructing the initial solution is highly unlikely to impact the performance of tabu search. Second, tabu tenure should be selected to be as small as possible while simultaneously avoiding search stagnation; values larger than necessary lead to significant degradations in performance.

Representations are formalized as encodings that map the search space to the vertex set of a graph. We define the notion of bit equivalent encodings and show that for such encodings the corresponding Walsh coefficients are also conserved. We focus on Gray codes as particular types of encoding and present a review of properties related to the use of Gray codes. Gray codes are widely used in conjunction with genetic algorithms and bit-climbing algorithms for parameter optimization problems. We present new convergence proofs for a special class of unimodal functions; the proofs show that a steepest ascent bit climber using any reflected Gray code representation reaches the global optimum in a number of steps that is linear with respect to the encoding size. There are in fact many different Gray codes. Shifting is defined as a mechanism for dynamically switching from one Gray code representation to another in order to escape local optima. Theoretical results that substantially improve our understanding of the Gray codes and the shifting mechanism are presented. New proofs also shed light on the number of unique Gray code neighborhoods accessible via shifting and on how neighborhood structure changes during shifting. We show that shifting can improve the performance of both a local search algorithm as well as one of the best genetic algorithms currently available.

The use of random test problems to evaluate algorithm performance raises an important, and generally unanswered, question: Are the results generalizable to more realistic problems? Researchers generally assume that algorithms with superior performance on difficult, random test problems will also perform well on more realistic, structured problems. Our research explores this assumption for the permutation flow-shop scheduling problem. We introduce a method for generating structured flow-shop problems, which are modeled after features found in some real-world manufacturing environments. We perform experiments that indicate significant differences exist between the search-space topologies of random and structured flow-shop problems, and demonstrate that these differencescanaffect the performance of certain algorithms. Yet despite these differences, and in contrast to difficult random problems, the majority of structured flow-shop problems were easily solved to optimality by most algorithms. For the problems not optimally solved, differences in performance were minor. We conclude that more realistic, structured permutation flow-shop problems are actually relatively easy to solve. Our results also raise doubts as to whether superior performance on difficult random scheduling problems translates into superior performance on more realistic kinds of scheduling problems.

Velocity Picking is the problem of picking velocity-time pairs based on a coherence metric between multiple seismic signals. Coherence as a function of velocity and time can be expressed as a 2-D color semblance velocity image. Currently, humans pick velocities by looking at the semblance velocity image; this process can take days or even weeks to complete for a seismic survey. The problem can be posed as a geometric feature matching problem. A feature extraction algorithm can recognize islands (peaks) of maximal semblance in the semblance velocity image: a heuristic combinatorial matching process can then be used to find a subset of peaks which maximizes the coherence metric. The peaks define a polyline through the image, and coherence is measured in terms of the summed velocity under the polyline and the smoothness of the polyline. Our best algorithm includes a constraint favoring solution near the median solution for the local area under consideration. Each image is first processed independently. Then, a second pass of optimization includes proximity to the median as an additional optimization criterion. Our results are similar to those produced by human experts.

When dealing with object classification, each object is defined by a set of features (characteristics) that classify the object to a particular class. The problem is how to choose the best subset of characteristics that provide an accurate classification. Previous research has shown that decision tables are as accurate as C4.5 for classification purposes. Two different genetic search techniques, CHC and CF/RSC, are applied to this problem. Results shows that CF/RSC and decision tables are a very good combination when dealing with large feature spaces. Results also suggest that CHC is better when used for problems with noise added to the features.

Classically, epistasis is either computed exactly by Walsh coefficients or estimated by sampling. Exact computation is usually of theoretical interest since the computation typically grows exponentially with the number of bits in the domain. Given an evaluation function, epistasis also can be estimated by sampling. However this approach gives us little insight into the origin of the epistasis and is prone to sampling error. This paper presents theorems establishing the bounds of epistasis for problems that can be stated as mathematical expressions. This leads to substantial computational savings for bounding the difficulty of a problem. Furthermore, working with these theorems in a mathematical context, one can gain insight into the mathematical origins of epistasis and how a problem's epistasis might be reduced. We present several new measures for epistasis and give empirical evidence and examples to demonstrate the application of the theorems. In particular, we show that some functions display "parity" such that by picking a well-defined representation, all Walsh coefficients of either odd or even index become zero, thereby reducing the nonlinearity of the function.

We compare several techniques for scheduling shipment of customer orders for the Coors Brewing warehouse and production line. The goal is to minimize time at dock for trucks and railcars while also minimizing inventory. The techniques include a genetic algorithm, local search operators, heuristic rules, systematic search and hybrid approaches. Initial results show a hybrid genetic algorithm to be superior to the other methods. The evaluation function is a fast approximate form of a warehouse simulation. We also assess the sensitivity of the search algorithms to noise in an approximate evaluation function using a more detailed (and costly) simulation.

We compare several techniques for scheduling shipment of customer orders for the Coors Brewing warehouse and production line. The goal is to minimize time at dock for trucks and railcars while also minimizing inventory. The techniques include a genetic algorithm, local search operators, heuristic rules, systematic search and hybrid approaches. Initial results show a hybrid genetic algorithm to be superior to the other methods. The evaluation function is a fast approximate form of a warehouse simulation. We also assess the sensitivity of the search algorithms to noise in an approximate evaluation function using a more detailed (and costly) simulation.

Delta coding is an iterative genetic search strategy that dynamically changes the representation of the search space in an attempt to exploit different problem representations. Delta coding sustains search by reinitializing the population at each iteration of search. This helps to avoid the asymptotic performance typically observed in genetic search as the population becomes more homogeneous. Here, the optimization ability of delta coding is empirically compared against CHC, ESGA, GENITOR, and random mutation hill-climbing (RMHC) on a suite of well-known test functions with and without Gray coding. Issues concerning the effects of Gray coding on these test functions are addressed.

A grammar tree is used to encode a cellular developmental process that can generate whole families of Boolean neural networks for computing parity and symmetry. The development process resembles biological cell division. A genetic algorithm is used to find a grammar tree that yields both architecture and weights specifying a particular neural network for solving specific Boolean functions. The current study particularly focuses on the addition of learning to the development process and the evolution of grammar trees. Three ways of adding learning to the development process are explored. Two of these exploit the Baldwin effect by changing the fitness landscape without using Lamarckian evolution. The third strategy is Lamarckian in nature. Results for these three modes of combining learning with genetic search are compared against genetic search without learning. Our results suggest that merely using learning to change the fitness landscape can be as effective as Lamarckian strategies at improving search.

The usefulness of connectionist models for software reliability growth prediction is illustrated. The applicability of the connectionist approach is explored using various network models, training regimes, and data representation methods. An empirical comparison is made between this approach and five well-known software reliability growth models using actual data sets from several different software projects. The results presented suggest that connectionist models may adapt well across different data sets and exhibit a better predictive accuracy. The analysis shows that the connectionist approach is capable of developing models of varying complexity.>

Software reliability growth models have achieved considerable importance in estimating reliability of software products. The authors explore the use of feed-forward neural networks as a model for software reliability growth prediction. To empirically evaluate the predictive capability of this new approach, data sets from different software projects are used. The neural networks approach exhibits a consistent behavior in prediction and the predictive performance is comparable to that of parametric models.>

GENITOR is a genetic algorithm which employs one-at-a-time reproduction and allocates reproductive opportunities according to rank to achieve selective pressure. Theoretical arguments and empirical evidence suggest that GENITOR is less vulnerable to some of the biases that degrade performance in standard genetic algorithms. A distributed version of GENITOR which uses many smaller distributed populations in place of a single large population is introduced. GENITOR II is able to optimize a broad range of sample problems more accurately and more consistently than GENITOR with a single population. GENITOR II also appears to be more robust than a single population genetic algorithm, yielding better performance without parameter tuning. We present some preliminary analyses to explain the performance advantage of the distributed algorithm. A distributed search is shown to yield improved search on several classes of problems, including binary encoded feedforward neural networks, the Traveling Salesman Problem, and a set of ‘ deceptive problems’ specially designed to be hard for genetic algorithms.