Lithography simulation is a critical step in VLSI design and optimization for manufacturability. Existing solutions for highly accurate lithography simulation with rigorous models are computationally expensive and slow, even when equipped with various approximation techniques. Recently, machine learning has provided alternative solutions for lithography simulation tasks such as coarse-grained edge placement error regression and complete contour prediction. However, the impact of these learning-based methods has been limited due to restrictive usage scenarios or low simulation accuracy. To tackle these concerns, we introduce an dual-band optics-inspired neural network design that considers the optical physics underlying lithography. To the best of our knowledge, our approach yields the first published via/metal layer contour simulation at 1nm2/pixel resolution with any tile size. Compared to previous machine learning based solutions, we demonstrate that our framework can be trained much faster and offers a significant improvement on efficiency and image quality with 20× smaller model size. We also achieve 85× simulation speedup over traditional lithography simulator with ~ 1% accuracy loss.

Estimation of distribution algorithms (EDAs) are stochastic optimization techniques that explore the space of potential solutions by building and sampling explicit probabilistic models of promising candidate solutions. While the primary goal of applying EDAs is to discover the global optimum or at least its accurate approximation, besides this, any EDA provides us with a sequence of probabilistic models, which in most cases hold a great deal of information about the problem. Although using problem-specific knowledge has been shown to significantly improve performance of EDAs and other evolutionary algorithms, this readily available source of problem-specific information has been practically ignored by the EDA community. This paper takes the first step toward the use of probabilistic models obtained by EDAs to speed up the solution of similar problems in the future. More specifically, we propose two approaches to biasing model building in the hierarchical Bayesian optimization algorithm (hBOA) based on knowledge automatically learned from previous hBOA runs on similar problems. We show that the proposed methods lead to substantial speedups and argue that the methods should work well in other applications that require solving a large number of problems with similar structure.

This paper analyzes the effects of an initial-population bias on the performance of the univariate marginal distribution algorithm (UMDA). The analysis considers two test problems: (1) onemax and (2) noisy onemax. Theoretical models are provided and verified with experiments. Intuitively, biasing the initial population toward the global optimum should improve performance of UMDA, whereas biasing the initial population away from the global optimum should have the opposite effect. Both theoretical and experimental results confirm this intuition. Effects of mutation on performance of UMDA with initial-population bias are also investigated.

This paper presents a class of NK landscapes with nearest-neighbor interactions and tunable overlap. The considered class of NK landscapes is solvable in polynomial time using dynamic programming; this allows us to generate a large number of random problem instances with known optima. Several genetic and evolutionary algorithms are then applied to the generated problem instances. The results are analyzed and related to scalability theory for genetic algorithms and estimation of distribution algorithms.

Abstract In many different fields, researchers are often confronted by problems arising from complex systems. Simple heuristics or even enumeration works quite well on small and easy problems; however, to efficiently solve large and difficult problems, proper decomposition is the key. In this paper, investigating and analyzing interactions between components of complex systems shed some light on problem decomposition. By recognizing three bare-bones interactions-modularity, hierarchy, and overlap, facet-wise models are developed to dissect and inspect problem decomposition in the context of genetic algorithms. The proposed genetic algorithm design utilizes a matrix representation of an interaction graph to analyze and explicitly decompose the problem. The results from this paper should benefit research both technically and scientifically. Technically, this paper develops an automated dependency structure matrix clustering technique and utilizes it to design a model-building genetic algorithm that learns and delivers the problem structure. Scientifically, the explicit interaction model describes the problem structure very well and helps researchers gain important insights through the explicitness of the procedure.

The hierarchical Bayesian optimization algorithm (hBOA) can solve nearly decomposable and hierarchical problems of bounded difficulty in a robust and scalable manner by building and sampling probabilistic models of promising solutions. This paper analyzes probabilistic models in hBOA on four important classes of test problems: concatenated traps, random additively decomposable problems, hierarchical traps and two-dimensional Ising spin glasses with periodic boundary conditions. We argue that although the probabilistic models in hBOA can encode complex probability distributions, analyzing these models is relatively straightforward and the results of such analyses may provide practitioners with useful information about their problems. The results show that the probabilistic models in hBOA closely correspond to the structure of the underlying optimization problem, the models do not change significantly in consequent iterations of BOA, and creating adequate probabilistic models by hand is not straightforward even with complete knowledge of the optimization problem.

Michigan-style learning classifier systems (LCSs) are online machine learning techniques that incrementally evolve distributed subsolutions which individually solve a portion of the problem space. As in many machine learning systems, extracting accurate models from problems with class imbalances-that is, problems in which one of the classes is poorly represented with respect to the other classes-has been identified as a key challenge to LCSs. Empirical studies have shown that Michigan-style LCSs fail to provide accurate subsolutions that represent the minority class in domains with moderate and large disproportion of examples per class; however, the causes of this failure have not been analyzed in detail. Therefore, the aim of this paper is to carefully examine the effect of class imbalances on different LCS components. The analysis focuses on XCS, which is the most-relevant Michigan-style LCS, although the models could be easily adapted to other LCSs. Design decomposition is used to identify five elements that are crucial to guaranteeing the success of LCSs in domains with class imbalances, and facetwise models that explain these different elements for XCS are developed. All theoretical models are validated with artificial problems. The integration of all these models enables us to identify the sweet spot where XCS is able to scalably and efficiently evolve accurate models of rare classes; furthermore, facetwise analysis is used as a tool for designing a set of configuration guidelines that have to be followed to ensure convergence. When properly configured, XCS is shown to be able to solve highly unbalanced problems that previously eluded solution.

Evolutionary Algorithms are largely used search and optimization procedures that, when properly designed, can solve intractable problems in tractable polynomial time. Efficiency enhancements are used to turn them from tractable to practical. In this paper we show preliminary results of two efficiency enhancements proposed for the Extended Compact Genetic Algorithm. First, a model building enhancement was used to reduce the complexity of the process from O($n^3$) to O($n^2$), speeding up the algorithm by 1000 times on a 4096 bits problem. Then, local-search hybridization was used to reduce the population size by at least 32 times, reducing the memory and running time required by the algorithm. These results draw the first steps toward a competent and efficient Genetic Algorithm.

Estimation of distribution algorithms (EDAs) are stochastic optimization techniques that explore the space of potential solutions by building and sampling probabilistic models of promising candidate solutions. While the primary goal of applying EDAs is to discover the global optimum (or an accurate approximation), any EDA also provides us with a sequence of probabilistic models, which hold a great deal of information about the problem. Although using problem-specific knowledge has been shown to significantly improve performance of EDAs and other evolutionary algorithms, this readily available source of information has been largely ignored by the EDA community. This paper takes the first step towards the use of probabilistic models obtained by EDAs to speed up the solution of similar problems in the future. More specifically, we propose two approaches to biasing model building in the hierarchical Bayesian optimization algorithm (hBOA) based on knowledge automatically learned from previous runs on similar problems. We show that the methods lead to substantial speedups and argue that they should work well in other applications that require solving a large number of problems with similar structure.

This paper proposes the incremental Bayesian optimization algorithm (iBOA), which modifies standard BOA by removing the population of solutions and using incremental updates of the Bayesian network. iBOA is shown to be able to learn and exploit unrestricted Bayesian networks using incremental techniques for updating both the structure as well as the parameters of the probabilistic model. This represents an important step toward the design of competent incremental estimation of distribution algorithms that can solve difficult nearly decomposable problems scalably and reliably.

Brainstorming has been greatly used as a method to generate a large number of ideas by variety of each participant's knowledge. However, brainstorming does not always work well because of spatial and communication limitations. Moreover, brainstorming techniques present limited scalability. Meanwhile, genetics algorithms have been mostly regarded as an engineering or technological tool. However, the innovation intuition suggests that genetic algorithms may be also regarded as models of human innovation and creativity. This paper focuses on online creativity sessions. Modeling those creative efforts using selecto-recombinative mechanism can provide three times more novel ideas, increase the posting frequency by a 2.6 factor, and help overcome superficiality on online communications by favoring synthetic thinking.

In this paper we report on the effect of viral infection with tropism on the formation of building blocks in genetic operations. In previous research, we applied genetic algorithms to the analysis of time-series signals with noise. We demonstrated the possibility of reducing the number of required entities and improving the rate of convergence when searching for a solution by having some of the host chromosomes harbor viruses with a tropism function. Here, we simulate problems having both multimodality and deceptiveness features and problems that include noise as test functions, and show that viral infection with tropism can increase the proportion of building blocks in the population when it cannot be assumed that a necessary and sufficient number of entities are available to find a solution. We show that this capability is especially noticeable in problems that include noise.

This paper presents a simple real-coded estimation of distribution algorithm (EDA) design using χ-ary extended compact genetic algorithm (χECGA) and discretization methods. Specifically, the real-valued decision variables are mapped to discrete symbols of user-specified cardinality using discretization methods. The χECGA is then used to build the probabilistic model and to sample a new population based on the probabilistic model. The effect of alphabet cardinality and the selection pressure on the scalability of the real-coded ECGA (rECGA) method is investigated. The results show that the population size required by rECGA—to successfully solve a class of additivelyseparable problems—scales sub-quadratically with problem size and the number of function evaluations scales sub-cubically with problem size. The proposed rECGA is simple, making it amenable for further empirical and theoretical analysis. Moreover, the probabilistic models built in the proposed realcoded ECGA are readily interpretable and can be easily visualized. The proposed algorithm and the results presented in this paper are first step towards conducting a systematic analysis of real-coded EDAs and towards developing a design theory for development of scalable and robust real-coded EDAs

This paper presents the real-coded extended compact genetic algorithms (rECGA) for decomposable real-valued optimization problems. Mutual information among real-valued variables is employed to measure variables interaction or dependency, and the variables clustering and aggregation algorithms are proposed to identify the substructures of a problem through partitioning variables. Then, mixture Gaussian probability density function is estimated to model the promising individuals for each substructure, and the sampling of multivariate Gaussian probability density function is done by adopting Cholesky decomposition. Finally, experiments on decomposable test functions are conducted. The results show that the rECGA is able to correctly identify the substructure of decomposable problems with linear or nonlinear correlations, and achieves a good scalability.

The Bayesian optimization algorithm (BOA) uses Bayesian networks to learn linkages between the decision variables of an optimization problem. This paper studies the influence of different selection and replacement methods on the accuracy of linkage learning in BOA. Results on concatenated m-k deceptive trap functions show that the model accuracy depends on a large extent on the choice of selection method and to a lesser extent on the replacement strategy used. Specifically, it is shown that linkage learning in BOA is more accurate with truncation selection than with tournament selection. The choice of replacement strategy is important when tournament selection is used, but it is not relevant when using truncation selection. On the other hand, if performance is our main concern, tournament selection and restricted tournament replacement should be preferred. These results aim to provide practitioners with useful information about the best way to tune BOA with respect to structural model accuracy and overall performance.

This paper focuses on automated procedures to reduce the dimensionality of protein structure prediction datasets by simplifying the way in which the primary sequence of a protein is represented. The potential benefits of this procedure are faster and easier learning process as well as the generation of more compact and human-readable classifiers. The dimensionality reduction procedure we propose consists on the reduction of the 20-letter amino acid (AA) alphabet, which is normally used to specify a protein sequence, into a lower cardinality alphabet. This reduction comes about by a clustering of AA types accordingly to their physical and chemical similarity. Our automated reduction procedure is guided by a fitness function based on the Mutual Information between the AA-based input attributes of the dataset and the protein structure feature that being predicted. To search for the optimal reduction, the Extended Compact Genetic Algorithm (ECGA) was used, and afterwards the results of this process were fed into (and validated by) BioHEL, a genetics-based machine learning technique. BioHEL used the reduced alphabet to induce rules for protein structure prediction features. BioHEL results are compared to two standard machine

The hierarchical Bayesian optimization algorithm (hBOA) can solve nearly decomposable and hierarchical problems of bounded difficulty in a robust and scalable manner by building and sampling probabilistic models of promising solutions. This paper analyzes probabilistic models in hBOA on two common test problems: concatenated traps and 2D Ising spin glasses with periodic boundary conditions. We argue that although Bayesian networks with local structures can encode complex probability distributions, analyzing these models in hBOA is relatively straightforward and the results of such analyses may provide practitioners with useful information about their problems. The results show that the probabilistic models in hBOA closely correspond to the structure of the underlying optimization problem, the models do not change significantly in subsequent iterations of BOA, and creating adequate probabilistic models by hand is not straightforward even with complete knowledge of the optimization problem.

A byproduct benefit of using probabilistic model-building genetic algorithms is the creation of cheap and accurate surrogate models. Learning classifier systems -- and genetics-based machine learning in general -- can greatly benefit from such surrogates which may replace the costly matching procedure of a rule against large data sets. In this paper we investigate the accuracy of such surrogate fitness functions when coupled with the probabilistic models evolved by the $\chi$-ary extended compact classifier system ($\chi$eCCS). To achieve such a goal, we show the need that the probabilistic models should be able to represent all the accurate basis functions required for creating an accurate surrogate. We also introduce a procedure to transform populations of rules based into dependency structure matrices (DSMs) which allows building accurate models of overlapping building blocks -- a necessary condition to accurately estimate the fitness of the evolved rules.

This paper analyzes the scalability of the population size required in XCS to maintain nichesthat are infrequently activated.Facetwise models have been developed to predict the effect of the imbalance ratio--ratio betweenthe number of instances of the majority class and the minority class that are sampled to XCS--on population initialization, andon the creation and deletion of classifiers of the minority class. While theoretical models show that, ideally, XCS scales linearly with the imbalance ratio, XCS with standard configuration scales exponentially. The causes that are potentially responsible for this deviation from the ideal scalability are also investigated. Specifically, the inheritance procedure of classifiers' parameters, mutation, and subsumption are analyzed, and improvements in XCS's mechanisms are proposed to effectively and efficiently handle imbalanced problems. Once the recommendations are incorporated to XCS, empirical results show that the population size in XCS indeed scales linearly with the imbalance ratio.

In this paper, we derive models of the selection pressure in XCS for proportionate (roulette wheel) selection and tournament selection. We show that these models can explain the empirical results that have been previously presented in the literature. We validate the models on simple problems showing that, (i) when the model assumptions hold, the theory perfectly matches the empirical evidence; (ii) when the model assumptions do not hold, the theory can still provide qualitative explanations of the experimental results.

This paper analyzes the relative advantages between crossover and mutation on a class of deterministic and stochastic additively separable problems with substructures of non-uniform salience. This study assumes that the recombination and mutation operators have the knowledge of the building blocks (BBs) and effectively exchange or search among competing BBs. Facetwise models of convergence time and population sizing have been used to determine the scalability of each algorithm. The analysis shows that for deterministic exponentially-scaled additively separable, problems, the BB-wise mutation is more efficient than crossover yielding a speedup of o(llogl), where l is the problem size. For the noisy exponentially-scaled problems, the outcome depends on whether scaling on noise is dominant. When scaling dominates, mutation is more efficient than crossover yielding a speedup of o(llogl). On the other hand, when noise dominates, crossover is more efficient than mutation yielding a speedup of o(l).

This paper presents a highly efficient, fully parallelized implementation of the compact genetic algorithm (cGA) to solve very large scale problems with millions to billions of variables. The paper presents principled results demonstrating the scalable solution of a difficult test function on instances over a billion variables using a parallel implementation of cGA. The problem addressed is a noisy, blind problem over a vector of binary decision variables. Noise is added equaling up to a tenth of the deterministic objective function variance of the problem, thereby making it difficult for simple hillclimbers to find the optimal solution. The compact GA, on the other hand, is able to find the optimum in the presence of noise quickly, reliably, and accurately, and the solution scalability follows known convergence theories. These results on noisy problem together with other results on problems involving varying modularity, hierarchy, and overlap foreshadow routine solution of billion-variable problems across the landscape of search problems.

This paper analyzes the behavior of a selectorecombinative genetic algorithm (GA) with an ideal crossover on a class of random additively decomposable problems (rADPs). Specifically, additively decomposable problems of order k whose subsolution fitnesses are sampled from the standard uniform distribution U[0,1] are analyzed. The scalability of the selectorecombinative GA is investigated for 10,000 rADP instances. The validity of facetwise models in bounding the population size, run duration, and the number of function evaluations required to successfully solve the problems is also verified. Finally, rADP instances that are easiest and most difficult are also investigated.

This paper proposes a population-sizing model for entropy-based model building in discrete estimation of distribution algorithms. Specifically, the population size required for building an accurate model is investigated. The effect of selection pressure on population sizing is also preliminarily incorporated. The proposed model indicates that the population size required for building an accurate model scales as Θ(m log m), where m is the number of substructures of the given problem and is proportional to the problem size. Experiments are conducted to verify the derivations, and the results agree with the proposed model.

Evolutionary algorithms (EAs) are a largely used search and optimization technique. They have been successfully applied to a wide variety of problems, overcoming traditional algorithms in performance. However, few EAs and traditional algorithms are able to handle complex combinatorial problems involving a large number of variables (thousands or millions). This paper proposes a new EA, capable of solving combinatorial problems with large number of variables. This algorithm is the result of two extensions from the extended compact genetic algorithm, a state-of-the-art EA.

Over the last ten years XCS has become the standard for Michigan-style learning classifier systems (LCS). Since the initial CS-1 work conceived by Holland, classifiers (rules) have widely used a ternary condition alphabet {0,1,#} for binary input problems. Most of the freely available implementations of this ternary alphabet in XCS rely on character-based encodings---easy to implement, not memory efficient, and expensive to compute. Profiling of freely available XCS implementations shows that most of their execution time is spent determining whether a rule is match or not, posing a serious threat to XCS scalability. In the last decade, multimedia and scientific applications have pushed CPU manufactures to include native support for vector instruction sets. This paper presents how to implement efficient condition encoding and fast rule matching strategies using vector instructions. The paper elaborates on Altivec (PowerPC G4, G5) and SSE2 (Intel P4/Xeon and AMD Opteron) instruction sets producing speedups of XCS matching process beyond ninety times. Moreover, such a vectorized matching code will allow to easily scale beyond tens of thousands of conditions in a reasonable time. The proposed fast matching scheme also fits in any other LCS other than XCS.

This paper builds introduces visual-analytic techniques to aggregate, summarize, and visualize the information generated during interactive evolutionary processes. Special visualizations of the user-provided partial ordering of solutions, the synthetic fitness surrogates induced, and the model of user preferences were prepared. The proposed visual-analytic techniques point out potential pitfalls, strengths, and possible improvements in a non-trivial case study where the hierarchical tournament selection scheme of an active interactive genetic algorithm is replaced by an incremental selection scheme. Visual analytics provided an intuitive reasoning environment that unveiled important properties that greatly affect the performance of active interactive genetic algorithms that could not have been easily reveled otherwise.

... This paper describes a class of random additively decomposable problems with and without interactions between the subproblems and tests hBOA on a large number of random instances of the proposed class of problems. The performance of hBOA is compared to that of the simple genetic algorithm with standard crossover and mutation operators, the univariate marginal distribution algorithm, and the hill climbing with bitflip mutation. The results confirm that hBOA achieves quadratic or subquadratic performance on the proposed class of random decomposable problems and that it significantly outperforms all other methods included in the comparison. The results also show that low-order polynomial scalability is retained even when only a small percentage of hardest problems are considered and that hBOA is a robust algorithm because its performance does not change much across the entire spectrum of random problem instances of the same structure. The proposed class of decomposable problems can be used to test other optimization algorithms that address nearly decomposable problems

This paper describes and analyzes sporadic model building, which can be used to enhance the efficiency of the hierarchical Bayesian optimization algorithm (hBOA) and other advanced estimation of distribution algorithms (EDAs) that use complex multivariate probabilistic models. With sporadic model building, the structure of the probabilistic model is updated once every few iterations (generations), whereas in the remaining iterations only model parameters (conditional and marginal probabilities) are updated. Since the time complexity of updating model parameters is much lower than the time complexity of learning the model structure, sporadic model building decreases the overall time complexity of model building. The paper shows that for boundedly difficult nearly decomposable and hierarchical optimization problems, sporadic model building leads to a significant model-building speedup that decreases the asymptotic time complexity of model building in hBOA by a factor of Θ(n 0.26) to Θ(n 0.5), where n is the problem size. On the other hand, sporadic model building also increases the number of evaluations until convergence; nonetheless, the evaluation slowdown is insignificant compared to the gains in the asymptotic complexity of model building.

This paper studies the effectiveness of multiobjective genetic and evolutionary algorithms in multiscaling excited state direct dynamics in photochemistry via rapid reparameterization of semiempirical methods. Using a very limited set of ab initio and experimental data, semiempirical parameters are reoptimized to provide globally accurate potential energy surfaces, thereby eliminating the need for full-fledged ab initio dynamics simulations, which are very expensive. Through reoptimization of the semiempirical methods, excited-state energetics are predicted accurately, while retaining accurate ground-state predictions. The results show that the multiobjective evolutionary algorithm consistently yields solutions that are significantly better---up to 230% lower error in the energy and 86.5% lower error in the energy-gradient---than those reported in the literature. Multiple high-quality parameter sets are obtained that are verified with quantum dynamical calculations, which show near-ideal behavior on critical and untested excited state geometries. The results demonstrate that the reparameterization strategy via evolutionary algorithms is a promising way to extend direct dynamics simulations of photochemistry to multi-picosecond time scales.

The paper presents an evaluation-relaxation scheme where a fitness surrogate automatically adapts to the problem structure and the partial contributions of subsolutions to the fitness of an individual are estimated efficiently and accurately. In particular, the probabilistic model built by extended compact genetic algorithm is used to infer the structural form of the surrogate and a least squares method is used to estimate the coefficients of the surrogate. Using the surrogate avoids the need for expensive fitness evaluation for some of the solutions, and thereby yields significant efficiency enhancement. Results show that a surrogate, which automatically adapts to problem knowledge mined from probabilistic models, yields substantial speedup (1.75--3.1) on a class of boundedly-difficult additively-decomposable problems with and without additive Gaussian noise. The speedup provided by the surrogate increases with the number of substructures, substructure complexity, and noise-to-signal ratio.

The quality of corpus-based text-to-speech systems depends on the accuracy of the unit selection process, which in turn relies on the cost function definition. This function should map the user perceptual preference when selecting synthesis units, which is a very difficult task. This paper continues our previous work on fusing the human judgements with the cost function by means of interactive weight tuning. The application of active interactive genetics algorithms mitigates user fatigue by improving user consistency. As a result, the obtained weights generate more natural synthetic speech when compared to previous objective and subjective proposals

This paper presents an analysis of how maximally general and accurate rules can be evolved in a Pittsburgh-style classifier system. In order to be able to perform such an analysis we introduce a simple bare-bones Pittsburgh-style classifier systems—the compact classifier system (CCS)—based on estimation of distribution algorithms. Using a common rule encoding schemes of Pittsburgh-style classifier systems, CCS mantains a dynamic set of probability vectors that compactly describe a rule set. The compact genetic algorithm is used to evolve each of the initially perturbated probability vectors. Results show how CCS is able to evolve in a compact, simple, and elegant manner rule sets composed by maximally general and accurate rules. The initial theoretical analysis and results also show that traditional encoding schemes used by Pittsburgh-style classifiers add an extra facet of diffiiculty. Such a bias plays a central role on the overall performance and scalability of CCS and other Pittsburgh-style systems using such encoding schemes. 1

The paper analyzes the scalability of multiobjective estimation of distribution algorithms (MOEDAs), particularly multiobjective extended compact genetic algorithm (meCGA), on a class of boundedly-difficult additively-separable multiobjective optimization problems. The paper demonstrates that even if the linkage is correctly identified, massive multimodality of the search problems can easily overwhelm the nicher and lead to exponential scale-up. The exponential growth of the Pareto-optimal solutions introduces a fundamental limit on the scalability of MOEDAs and the number of competing substructures between the multiple objectives. Facetwise models are subsequently used to predict this limit in the growth rate of the number of differing substructures between the two objectives to avoid the niching method from being overwhelmed and lead to polynomial scalability of MOEDAs.

This paper proposes an online population size adjustment scheme for genetic algorithms. It utilizes linkage-model-building techniques to calculate the parameters used in facet-wise population-sizing models. The methodology is demonstrated using the dependency structure matrix genetic algorithm on boundedly-difficult problems. Empirical results indicate that the proposed method is both efficient and robust. If the initial population size is too large, the proposed scheme decreases the population size and yields significant savings in the number of function evaluations required to obtain high-quality solutions; if the initial population size is too small, the scheme increases the population size and avoids premature convergence.

This paper presents an approach to combine competent crossover and mutation operators via probabilistic model building. Both operators are based on the probabilistic model building procedure of the extended compact genetic algorithm (eCGA). The model sampling procedure of eCGA, which mimics the behavior of an idealized recombination---where the building blocks (BBs) are exchanged without disruption---is used as the competent crossover operator. On the other hand, a recently proposed BB-wise mutation operator---which uses the BB partition information to perform local search in the BB space---is used as the competent mutation operator. The resulting algorithm, called hybrid extended compact genetic algorithm (heCGA), makes use of the problem decomposition information for (1) effective recombination of BBs and (2) effective local search in the BB neighborhood. The proposed approach is tested on different problems that combine the core of three well known problem difficulty dimensions: deception, scaling, and noise. The results show that, in the absence of domain knowledge, the hybrid approach is more robust than either single-operator-based approach.

This paper presents an initial analysis of how maximally general and accurate rules can be evolved in a Pittsburgh-style classifier system. In order to be able to perform such analysis we introduce a simple bare-bones Pittsburgh classifier systems---the compact classifier system (CCS)---based on estimation of distribution algorithms. Using a common rule encoding scheme of Pittsburgh classifier systems, CCS maintains a dynamic set of probability vectors that compactly describe a rule set. The compact genetic algorithm is used to evolve each of the initially perturbed probability vectors which represents the rules. Results show how CCS is able to evolve in a compact, simple, and elegant manner rule sets composed by maximally general and accurate rules.

One of the daunting challenges of interactive genetic algorithms (iGAs)---genetic algorithms in which fitness measure of a solution is provided by a human rather than by a fitness function, model, or computation---is user fatigue which leads to sub-optimal solutions. This paper proposes a method to combat user fatigue by augmenting user evaluations with a synthetic fitness function. The proposed method combines partial ordering concepts, notion of non-domination from multiobjective optimization, and support vector machines to synthesize a fitness model based on user evaluation. The proposed method is used in an iGA on a simple test problem and the results demonstrate that the method actively combats user fatigue by requiring 3--7 times less user evaluation when compared to a simple iGA.

Summary. This paper discusses scalability of standard genetic programming (GP) and the probabilistic incremental program evolution (PIPE). To investigate the need for both eective mixing and linkage learning, two test problems are considered: ORDER problem, which is rather easy for any recombination-based GP, and TRAP or the deceptive trap problem, which requires the algorithm to learn interactions among subsets of terminals. The scalability results show that both GP and PIPE scale up polynomially with problem size on the simple ORDER problem, but they both scale up exponentially on the deceptive problem. This indicates that while standard recom-bination is sucient when no interactions need to be considered, for some problems linkage learning is necessary. These results are in agreement with the lessons learned in the domain of binary-string genetic algorithms (GAs). Furthermore, the paper investigates the eects of introducing unnecessary and irrelevant primitives on the performance of GP and PIPE.

This paper describes a scalable algorithm for solving multiobjective decomposable problems by combining the hierarchical Bayesian optimization algorithm (hBOA) with the nondominated sorting genetic algorithm (NSGA-II) and clustering in the objective space. It is first argued that for good scalability, clustering or some other form of niching in the objective space is necessary and the size of each niche should be approximately equal. Multiobjective hBOA (mohBOA) is then described that combines hBOA, NSGA-II and clustering in the objective space. The algorithm mohBOA differs from the multiobjective variants of BOA and hBOA proposed in the past by including clustering in the objective space and allocating an approximately equally sized portion of the population to each cluster. The algorithm mohBOA is shown to scale up well on a number of problems on which standard multiobjective evolutionary algorithms perform poorly.

We propose a sub-structural niching method that fully exploits the problem decomposition capability of linkage-learning methods such as the estimation distribution algorithms and concentrate on maintaining diversity at the sub-structural level. The proposed method consists of three key components: (1) Problem decomposition and sub-structure identification, (2) sub-structure fitness estimation, and (3) sub-structural niche preservation. The sub-structural niching method is compared to restricted tournament selection (RTS)---a niching method used in hierarchical Bayesian optimization algorithm---with special emphasis on sustained preservation of multiple global solutions of a class of boundedly-difficult, additively-separable multimodal problems. The results show that sub-structural niching successfully maintains multiple global optima over large number of generations and does so with significantly less population than RTS. Additionally, the market share of each of the niche is much closer to the expected level in sub-structural niching when compared to RTS.

This paper aims at an important, but poorly studied area in genetic algorithm (GA) field: How to design the crossover operator for problems with overlapping building blocks (BBs). To investigate this issue systematically, the relationship between an inaccurate linkage model and the convergence time of GA is studied. Specifically, the effect of the error of so-called false linkage is analogized to a lower exchange probability of uniform crossover. The derived qualitative convergence-time model is used to develop a scalable recombination strategy for problems with overlapping BBs. A set of problems with circularly overlapping BBs exemplify the recombination strategy.

This paper studies fitness inheritance as an efficiency enhancement technique for a class of competent genetic algorithms called estimation distribution algorithms. Probabilistic models of important sub-solutions are developed to estimate the fitness of a proportion of individuals in the population, thereby avoiding computationally expensive function evaluations. The effect of fitness inheritance on the convergence time and population sizing are modeled and the speed-up obtained through inheritance is predicted. The results show that a fitness-inheritance mechanism which utilizes information on building-block fitnesses provides significant efficiency enhancement. For additively separable problems, fitness inheritance reduces the number of function evaluations to about half and yields a speed-up of about 1.75-2.25.