This paper proposes a framework combining genetic programming (GP) with other symbolic regression (SR) methods, called the symbolic regressor enhancer (SRE). The basic idea is to use the syntax tree of the expression obtained from other SR methods to improve both the efficiency and the quality of the evolutionary procedure. Specifically, this paper investigates on the different ways of hybridization, selection, and crossover to assemble the proposed SRE. The effectiveness of SRE is demonstrated with the Taylor polynomial, the fast function extraction, and the GP-based SR methods, including Operon, the GP variant of gene-pool optimal mixing evolutionary algorithm, the epsilon-Iexicase selection, and gplearn. Out of 28 benchmarks from the SR benchmark and the Feynman SR database, the statistical test indicates that SRE applied to each selected SR method significantly outperforms the respective SR method in at least 8 and at most 24 benchmarks.

Program synthesis (PS) is a field devoted to auto-matically generating computer programs from high-level specifications, and genetic programming (GP) is one commonly-used way to achieve PS. PushGP, operating on a stack-based language, is considered as a state-of-the-art program synthesizer among GPs, while another research trend foucus on the grammar-based languages due to the readability and the ease of maintenance. In this paper, we propose the repetitive structure genetic programming (RSGP), a new grammar-based program synthesizer under the pure functional programming paradigm. RSGP defines a recursive function to simulate the single-layer loop behavior and leverages the minimum redundancy maximum relevance$(\text{mRMR})$feature selection with the Pearson correlation coefficient (PCC) to select the capable and diverse programs for the next generation. The experiment results show that RSGP outperforms PushGP, CBGP, and HOTGP in terms of the number of successful programs on CountOdds and LastIndexofZero from PSBl, Luhn from PSB2, and 3 out of 4 designed problems. Additionally, the ablation study indicates that using$\text{mRMR}$with PCC does encourage proper problem decomposition with the trade-off of diminishing the search ability within a similar neighborhood. RSGP utilizes an adaptation mechanism to balance the trade-off to automatically fit the needs of different problems.

Despite recent advancements, deep reinforcement learning (DRL) still struggles at learning sparse-reward goal-directed tasks. Classical planning excels at addressing hierarchical tasks by employing symbolic knowledge, yet most of the methods rely on assumptions about pre-defined subtasks. To bridge the best of both worlds, we propose a framework that integrates DRL with classical planning by automatically inducing task structures and substructures from a few demonstrations. Specifically, genetic programming is used for substructure induction where the program model reflects prior domain knowledge of effect rules. We compare the proposed framework to state-of-the-art DRL algorithms, imitation learning methods, and an exploration approach in various domains. Experimental results show that our proposed framework outperforms all the abovementioned algorithms in terms of sample efficiency and task performance. Moreover, our framework achieves strong generalization performance by effectively inducing new rules and composing task structures. Ablation studies justify the design of our induction module and the proposed genetic programming procedure.

The multi-objective gene-pool optimal mixing evolutionary algorithm with interleaved multi-start scheme (MO-GOMEA) is a powerful, parameterless model-based genetic algorithm that excels at solving multi-objective combinatorial optimization problems. In this paper, we propose a new mixing mechanism, adaptive donor selection mixing (ADSM) and further integrate it into MO-GOMEA to form a new variant, ADSM-MO-GOMEA. The proposed ADSM mechanism adaptively switches between cluster-guided and elitist-guided mixing, with the latter having a customized donor selection for the receiver based on empirical observations and mathematical derivation. The empirical results on multiple benchmark problems indicate that ADSM-MO-GOMEA improves the effectiveness over the original MO-GOMEA and achieves a lower inverted generational diversity and higher front occupation within the given limited number of evaluations.

Deep learning has been widely adopted in many real-world applications, especially in image classification. However, researches have shown that minor distortions imperceptible to humans may mislead classifiers. One way to improve the robustness is using adversarial attacks to obtain adversarial examples and re-training the classifier with those images. However, the connections between attacks and application scenarios are rarely discussed. This paper proposes a novel black-box adversarial attack that is specifically designed for real-world application scenarios: The transfer-based black-box adversarial attack with genetic algorithms (TAGA). TAGA adopts a genetic algorithm to generate the adversarial examples and reduces the ensuing query costs with a surrogate model based on the transferability of adversarial attacks. Empirical results show that perturbing embeddings in the latent space helps the attack algorithm quickly obtain adversarial examples and that the surrogate fitness function reduces the number of function evaluations. Compared with several state-of-the-art attacks, TAGA improves the classifiers more under the application scenario in terms of the summation of natural and defense accuracy.

Genetic algorithms using optimal mixing have shown promising results, while lack of theoretical supports. This paper investigates population sizing from the supply aspect under the optimal mixing scenario. Specifically, more precise analyses on supply, including the expectation and the lower bound, are made. In addition, considering recombining one randomly generated chromosome with the rest of the population to achieve the global optimum, the tight bounds of the size of the population providing proper fragments chosen by restricted oracles are derived. Tight bounds on problems with ring topologies where a subfunction overlaps two other subfunctions are also derived. Finally, experiments are conducted and well match the derivations.

Since numerous genetic algorithms (GAs) are developed every year, GA researchers need a fast algorithm to fairly compare their performances. In this paper, we formalized the performance metric and listed three algorithms to find the right population size for performance comparing in terms of the Number of Fitness Evaluations (NFE). Instead of finding the population nmNFE producing minimum NFE (mNFE), we took the methodology of finding n* which would converge to an arbitrary notion of success with a desired probability p*. Among all three algorithms, the first, the most commonly used bisection method, was proved to be biased and without generality. The second is an unbiased modification of the first with trade-off of more function evaluations. The third, called Greedy Approach Regarding Locality (GARL), is our recommendation, empirically outperforming the second one by an exponential factor. We also analyzed the time complexity of the second and third algorithms, providing the upper bound for an average case. This work could be viewed as a general efficiency-comparing framework to almost all GAs except for parameterless schemes.

Early development of GAs requires many parameters to be tuned. The tuning process increases the difficulty for inexperienced practitioners. Modern GAs have most of these parameters pre-determined, and therefore recent research concerning parameterless schemes has focused on population size. The techniques developed in this paper are mainly based on Harik and Lobo's work and the exponential population scheme (EPS), which double the population until the solution is satisfactory. In this paper, we modify EPS based on theoretical analyses. Specifically, we propose a new termination criterion and an optimized population multiplier. The experiment results show that our scheme reduces 33.4%, 19.1% and 29.6% number of function evaluations (NFE) on hBOA (the parameter-less hBOA), LT-GOMEA and DSMGA-II respectively when compared to Harik-Lobo scheme, and reduces 28.5%, 4.7% and 11.0% NFE on hBOA, LT-GOMEA and DSMGA-II respectively when compared to EPS. In addition, compared to EPS, our scheme empirically reduces the number of failures when using LT-GOMEA to solve the folded trap and MAX-SAT problems.

DSMGA-II, a model-based genetic algorithm, is capable of solving optimization problems via exploiting sub-structures of the problem. In terms of number of function evaluations (NFE), DSMGA-II has shown superior optimization ability to LT-GOMEA and hBOA on various benchmark problems as well as real-world problems. This paper proposes a two-edge graphical linkage model, which customizes recombination masks for each receiver according to its alleles, to further improve the performance of DSMGA-II. The new linkage model is more expressive than the original dependency structure matrix (DSM), providing far more possible linkage combinations than the number of solutions in the search space. To reduce unnecessary function evaluations, the two-edge model is used along with the supply bounds from the original DSM. Some new techniques are also proposed to enhance the model selection efficiency. Combining these proposed techniques, the empirical results show an average of 12.2% NFE reduction on eight benchmark problems compared with the original DSMGA-II.

This paper proposes two CUDA based implementations to speed up the model building process for DSMGA-II, which has shown superior optimization ability to hBOA and LT-GOMEA on various benchmark problems. The first implementation is lossless, which is algorithmically identical to the original version. The second implementation is lossy, which sacrifices some accuracy for further speedup. On several commonly used benchmark problems, the proposed implementations are stable. As the problems become larger, the amount of speedup increases accordingly. The lossless scheme speeds up the first part of model building for more than ten times; the lossy implementation further speeds up the second part of model building for more than 400 times on a 600-bit folded-trap problem. The limitation of such implementations are also discussed in detail in this paper.

Hierarchical problems represent an important class of nearly decomposable problems and come from hierarchical complex systems. Complex systems are important since they appear in a variety of different areas. The dependency structure matrix genetic algorithm II, performing exploration and exploitation properly, requires fewer number of function evaluations on several problems than some well-known evolutionary algorithms such as the linkage tree genetic algorithm and the hierarchical bayesian optimization algorithm. However, DSMGA-II does not preserve enough promising subsolutions to the upper levels in hierarchical problems due to the back mixing operator of DSMGA-II, so it fails to solve the hierarchical trap problem. This paper proposes a diversity preservation scheme for DSMGA-II to conquer the hierarchical difficulty by calculating the entropies of subsolutions and determining whether to perform the back mixing. The empirical results show that our algorithm works well on hierarchical problems and does not compromise the performance on other problems.

This paper proposes a new evolutionary algorithm, called DSMGA-II, to efficiently solve optimization problems via exploiting problem substructures. The proposed algorithm adopts pairwise linkage detection and stores the information in the form of dependency structure matrix (DSM). A new linkage model, called the incremental linkage set, is then constructed by using the DSM. Inspired by the idea of optimal mixing, the restricted mixing and the back mixing are proposed. The former aims at efficient exploration under certain constrains. The latter aims at exploitation by refining the DSM so as to reduce unnecessary evaluations. Experimental results show that DSMGA-II outperforms LT-GOMEA and hBOA in terms of number of function evaluations on the concatenated/folded/cyclic trap problems, NK-landscape problems with various degrees of overlapping, 2D Ising spin-glass problems, and MAX-SAT. The investigation of performance comparison with P3 is also included.

The optimal mixing evolutionary algorithms (OMEAs) have recently drawn much attention for their robustness, small size of required population, and efficiency in terms of number of function evaluations (NFE). In this paper, the performances and behaviors of convergence in OMEAs are studied by investigating the mechanism of optimal mixing (OM), the variation operator in OMEAs, under two scenarios---one-layer and two-layer masks. For the case of one-layer masks, the required population size is derived from the viewpoint of initial supply, while the convergence time is derived by analyzing the progress of sub-solution growth. NFE is then asymptotically bounded with rational probability by estimating the probability of performing evaluations. For the case of two-layer masks, empirical results indicate that the required population size is proportional to both the degree of cross competition and the results from the one-layer-mask case. The derived models also indicate that population sizing is decided by initial supply when disjoint masks are adopted, that the high selection pressure imposed by OM makes the composition of sub-problems impact little on NFE, and that the population size requirement for two-layer masks increases with the reverse-growth probability.

Discretization algorithms have been combined with discrete estimation of distribution algorithms (EDAs) to work on real-valued problems. Existing discretization algorithms, such as the fixed-height histogram (FHH) and the split-on-demand (SoD), utilize merely densities of selected chromosomes to build next-generation population, and therefore have limited exploration. This paper adds the concept of model building to FHH and SoD to solve these problems. The model utilizes a variety of information from selected chromosomes to improve the abilities of FHH and SoD to identify promising regions for future exploration. Specifically, a model of expected values of selected chromosomes is combined with FHH and SoD to form expected-value FHH and expected-value SoD. The expected-value-discretization algorithms outperform their original versions on an exploration test function as well as the 25 benchmark functions used in the SoD paper. This paper also introduces a model of differential-expected-value of selected chromosomes. The differential-expected-value FHH and differential-expected-value SoD outperform their expected-value versions when tested on the exploration test function and the 25 benchmark functions.

Traffic signal timing optimization problem aims at alleviating traffic congestion and shortening the average traffic time. However, most existing research considered only the information of one or few intersections at a time. Those local optimization methods may experience a decrease in performance when facing large-scale traffic networks. In this paper, we propose a cellular automaton traffic simulation system and conduct tests on two different optimization schemes. We use Genetic Algorithm (GA) for global optimization and Expectation Maximization (EM) as well as car flow for local optimization. Empirical results show that the GA method outperforms the EM method. Then, we use linear regression to learn from the global optimal solution obtained by GA and propose a new adjustment strategy that outperforms recent optimization methods.

The optimal mixing operator (OM) utilizes linkage sets (LSs) to exchange the information of variables between a pair of solutions, and the result of such exchange is adopted only if the exchange leads to improvement of the solution quality. The performance of OM highly depends on the LS it uses. This paper demonstrates that previously proposed LS, the linkage tree model (LT), does not yield the optimal performance. To measure the efficiency of OM on different LSs, the cost-performance (CP) index is defined. Both our CP index and experiments indicate (1) that for fully separable problems, the most suitable LS is the marginal product model (MP), and (2) that for separable problems with overlap, LT is more suitable than MP, and (3) that properly pruned LT leads to higher efficiency and yields a better performance, and (4) that the LS that properly reflects the problem structure yields the best performance on both fully separable problems and problems with overlap.

Hybridization of global and local searches is a well-known technique for optimization algorithms. Hill climbing is one of the local search methods. On estimation of distribution algorithms (EDAs), hill climbing strengthens the signals of dependencies on correlated variables and improves the quality of model building, which reduces the required population size and convergence time. However, hill climbing also consumes extra computational time. In this paper, analytical models are developed to investigate the effects of combining two different hill climbers with the extended compact genetic algorithm and the dependency structure matrix genetic algorithm. By using the one-max problem and the 5-bit non-overlapping trap problem as the test problems, the performances of different hill climbers are compared. Both analytical models and experiments reveal that the greedy hill climber reduces the number of function evaluations for EDAs to find the global optimum.

Since the existence of at least one mixed Nash equilibrium (NE) for any game was proved by Nash, finding NE has been an important issue in the field of game theory. However, polynomial-time algorithms for such task have not yet been discovered, and one of the difficulties is the infinite search space. In this paper, we define the so-called ε-representative strategy to reduce the search space. In general, the equilibria on these representative strategies are not the original equilibria but approximations.To find such approximate equilibria, we then propose a two-level method, which firstly uses co-evolutionary algorithms to co-evolve the representative strategies for each player and then the approximate equilibria.The computational time can be controlled by the parameters of the co-evolutionary algorithms. Empirical results show that our method finds the approximate NE in a reasonable time. Finally, the definitions developed in this paper help define the co-evolvability of NE.

This paper proposes a niching scheme, the dependency structure matrix restricted tournament replacement (DSMRTR). The restricted tournament replacement (RTR) is a well-known niching scheme in the field of estimation of distribution algorithms (EDAs). However, RTR induces spurious dependencies among variables, which impair the performance of EDAs. This paper utilizes building-block-wise distances to define a new distance metric, the one-niche distance. For those EDAs which provide explicit linkage information, the one-niche distances can be directly incorporated into RTR. For EDAs without such information, DSMRTR constructs a dependency structure matrix via the differential mutual complement to estimate the one-niche distances. Empirical results show that DSMRTR induces fewer spurious dependencies than RTR does while maintaining enough diversity for EDAs.

Parallelization is a straightforward approach to enhance the efficiency for evolutionary computation due to its inherently parallel nature. Since NVIDIA released the compute unified device architecture (CUDA), graphic processing units have enabled lots of scalable parallel programs in a wide range of fields. However, parallelization of model building for EDAs is rarely studied. In this paper, we propose two implementations on CUDA to speed up the model building in the extended compact genetic algorithm (ECGA). The first implementation is algorithmically identical to original ECGA. Aiming at a greater speed boost, the second implementation modifies the model building. It slightly decreases the accuracy of models in exchange for more speedup. Empirically, the first implementation achieves a speedup of roughly 359 to the baseline on 500-bit trap problem with order 5, and the second implementation achieves a speedup of roughly 506 to the baseline on the same problem. Finally, both of our implementations scale up to 9,800-bit trap problem with order~5 on one single Tesla C2050 GPU card.

Two types of problem structures, overlapping and conflict structures, are challenging for the estimation of distribution algorithms (EDAs) to solve. To test the capabilities of different EDAs of dealing with overlapping and conflict structures, some test problems have been proposed. However, the upper-bound of the degree of overlap and the effect of conflict have not been fully investigated. This paper investigates how to properly define the degree of overlap and the degree of conflict to reflect the difficulties of problems for the EDAs. A new test problem is proposed with the new definitions of the degree of overlap and the degree of conflict. A framework for building the proposed problem is presented, and some model-building genetic algorithms are tested by the problem. This test problem can be applied to further researches on overlapping and conflict structures.

In the field of genetic algorithms (GAs), some researches on overlapping building blocks (BBs) have been proposed. To further study on overlapping BBs, we need to measure the performance of an algorithm to solve problems with over-lap among subproblems. Several test problems have been proposed, but the controllability over the degree of overlapping is not yet fully satisfactory. Our new test problem is designed with full controllability of overlapping as well as conflict, a specific type of overlap, among BBs. We present a framework for building the structure of this problem in this paper. Some model-building GAs are tested by the proposed problem. This test problem can be applied to further researches on overlapping and conflicting BBs.

This paper aims at detecting the existence of building blocks directly from the fitness function without performing genetic algorithms. To do so, this paper extends the convergence time model and the gambler's ruin model so they can be applied to a larger variety of problems. With proposed models, the number of fitness evaluations can be estimated for both of these two cases: (1) some genes are transferred together in crossover (treated as a building block); (2) the genes are transferred separately. Therefore, we can compare the number of fitness evaluations and detect the existence of building blocks for a large family of fitness functions without actually performing a genetic algorithm.

Object segmentation needs to be driven by top-down knowledge to produce semantically meaningful results. In this paper, we propose a supervised segmentation approach that tightly integrates object-level top down information with low-level image cues. The information from the two levels is fused under a kernelized structural SVM learning framework. We defined a novel nonlinear kernel for comparing two image-segmentation masks. This kernel combines four different kernels: the object similarity kernel, the object shape kernel, the per-image color distribution kernel, and the global color distribution kernel. Our experiments show that the structured SVM algorithm finds bad segmentations of the training examples given the current scoring function and punishes these bad segmentations to lower scores than the example (good) segmentations. The result is a segmentation algorithm that not only knows what good segmentations are, but also learns potential segmentation mistakes and tries to avoid them. Our proposed approach can obtain comparable performance to other state-of-the-art top-down driven segmentation approaches yet is flexible enough to be applied to widely different domains.

Existing EDAs learn linkages starting from pairwise interactions. The characteristic function which indicates the relations among variables are binary. In other words, the characteristic function indicates that there exist or not interactions among variables. Empirically, it can occur that two variables should be sometimes related but sometimes not. This paper introduces a real-valued characteristic function to illustrate this property of fuzziness. We examine all the possible binary models and real-valued models on a test problem. The results show that the optimal real-valued model is better than all the binary models. This paper also proposes a crossover method which is able to utilize the real-valued information. Experiments show that the proposed crossover could reduce the number of function evaluations up to four times. Moreover, this paper proposes an effective method to find a threshold for entropy based interaction-detection metric and a method to learn real-valued models. Experiments show that the proposed crossover with the learned real-valued models works well.

Dependency structure matrix genetic algorithm (DSMGA), one of estimation of distribution algorithms (EDAs), builds models via dependency structure matrix clustering techniques. Previous researches have shown that DSMGA can effectively solve nearly decomposable problems. The efficiency of DSMGA and other model-building GAs greatly depend on their interaction-detection metrics. This paper investigates three commonly used metrics, nonlinearity, simultaneity, and entropy. Then it proposes a new interaction-detection metric which aims at what GAs really need. The proposed metric, namely the differential mutual complement, is based on both the disruption and reproduction effects of the crossover operator on significant schemata. Empirical results show that DSMGA with the proposed metric performs better than the other existing metrics on the aspects of sensitivity to threshold and function evaluation. This new metric is shown to perform well on DSMGA and could be expected to work with other EDAs.

This paper examines which elements are necessary for coevolutionary genetic algorithms to evolve cooperative strategies under pure egoistic considerations. Since competitions and cooperations coexist in an auction-based manpower allocation problem, the problem is adopted for further investigation. To alleviate analytical burden, the problem is abstracted to a resource-bidding game under the Nash game framework. A mathematical model for the resource-bidding game is defined and several special cases are illustrated. One of these special cases, named c-mNE, is further investigated due to the existance of cooperative modes. Various kinds of egoistic fitness functions and evolutionary mechanisms are experimented on c-mNE. Based on the experimental results, this paper suggests that coevolutionary mechanisms which properly eliminate aggressive strategies and preserve cooperative strategies can evolve cooperative modes under the pure egoistic assumption.

Besides the difficulty of scheduling, major challenges of the nurse scheduling problems (NSPs) are constraint handling and chief nurses' psychological preference that is not clearly defined. It is too strong an assumption that the constructed objective functions in some existing researches are close to chief nurses' preference. This research presents a psychological preference-based optimization framework (PPOF) which optimizes constrained problems based on human preference. Moreover, an implementation on a realistic NSP is introduced. The experiments show that PPOF is able to optimize a monthly nurse schedule for National Taiwan University Hospital according to chief nurses' preference.

This paper investigates the difficulty of linkage learning, an essential core, in EDAs. Specifically, it examines allelicpairwise independent functions including the parity, paritywith-trap, and Walsh-code functions. While the parity function was believed to be difficult for EDAs in previous work, our experiments indicate that it can be solved by CGA within a polynomial number of function evaluations to the problem size. Consequently, the apparently difficult paritywith-trap function can be easily solved by ECGA, even though the linkage model is incorrect. A convergence model for CGA on the parity function is also derived to verify and support the empirical findings. Finally, this paper proposes a socalled Walsh-code function, which is more difficult than the parity function. Although the proposed function does deceive the linkage-learning mechanism in most EDAs, EDAs are still able to solve it to some extent.

Some coevolutionary issues are illustrated elsewhere. This paper investigates the ability of coevolutionary genetic algorithm to solve games. Specifically, it focuses on two-player, zero-sum and symmetric games with both pure and mixed strategies. Games with mixed strategies are challenging for coevolution since the Nash strategy does not yield a higher payoff. On the other hand, games with pure strategies are more co-evolvable especially with mechanisms to keep the population diverse. Empirically, adopting niching techniques such as restricted tournament selection helps coevolution. Finally, this paper demonstrates the existence of games that require an exponential population size with respect to the size of the game.

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.

This paper investigates the utility of sampling as an evaluation-relaxation technique in genetic algorithms (GAs). In many real-world applications, sampling can be used to generate a less accurate, but computationally inexpensive fitness evaluator to speed GAs up. This paper focuses on the problem of polynomial regression as an example of problems with positive dependency among genes. Via statistical analysis of the noise introduced by sampling, this paper develops facet-wise models for the optimal sampling size, and these models are empirically verified. The results show that when the population is sized properly, small sampling sizes are preferred for most applications. When a fixed population size is adopted, which is usually the case in real-world applications, an optimal sampling size exists. If the sampling size is too small, the sampling noise increases, and GAs would perform poorly because of an insufficiently large population. If the sampling size is too large, the GA would spend too much time in fitness calculation and cannot perform well either within limited run duration.

Natural ways of input greatly enhance the entertainment experience for emerging gaming systems represented by the Sony Playstation 2 EyeToy and the Nintendo Wii Console. In this paper we present a novel method of using human body gestures depth image as gaming application input. Depth images have natural advantages over grayscale or color images in terms of robustness against illumination change, texture complexity, and background interference. Our proposed method consists of three major components: depth image acquisition, mean shift based preprocessing, and HMM-based gesture recognition. We validate our method by applying it to a boxing game scenario to distinguish boxing gestures such as dodge, jab, hook, and uppercut. The experiment results indicate that our method can efficiently distinguish the subtle differences among these gestures and yield excellent accuracy (up to about 98%). The potential usage of the proposed method on gaming applications and generic human computer interaction is very promising.

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.

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 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.

This paper proposes a chromosome compression scheme which represents subsolutions by the most expressive schemata. The proposed chromosome compression scheme is combined with the dependency structure matrix genetic algorithm and the restricted tournament replacement to create a scalable optimization tool which optimizes problems via hierarchical decomposition. One important feature of the proposed method is that at the end of the run, the problem structure obtained from the proposed method is comprehensible to human researchers and is reusable for larger-scale problems. The empirical result shows that the proposed method scales sub-quadratically with the problem size on hierarchical problems and is able to capture the problem structures accurately.

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 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.