Informed down-sampling (IDS) is known to improve performance in symbolic regression when combined with various selection strategies, especially tournament selection. However, recent work found that IDS's gains are not consistent across all problems. Our analysis reveals that IDS performance is worse for problems containing outliers. IDS systematically favors including outliers in subsets which pushes GP towards finding solutions that overfit to outliers. To address this, we introduce ROIDS (Robust Outlier-Aware Informed Down-Sampling), which excludes potential outliers from the sampling process of IDS. With ROIDS it is possible to keep the advantages of IDS without overfitting to outliers and to compete on a wide range of benchmark problems. This is also reflected in our experiments in which ROIDS shows the desired behavior on all studied benchmark problems. ROIDS consistently outperforms IDS on synthetic problems with added outliers as well as on a wide range of complex real-world problems, surpassing IDS on over 80% of the real-world benchmark problems. Moreover, compared to all studied baseline approaches, ROIDS achieves the best average rank across all tested benchmark problems. This robust behavior makes ROIDS a reliable down-sampling method for selection in symbolic regression, especially when outliers may be included in the data set.

In recent years, several new lexicase-based selection variants have emerged due to the success of standard lexicase selection in various application domains. For symbolic regression problems, variants that use an \(\epsilon\) -threshold or batches of training cases, among others, have led to performance improvements. Lately, especially variants that combine lexicase selection and down-sampling strategies have received a lot of attention. This article evaluates the most relevant lexicase-based selection methods as well as traditional selection methods in combination with different down-sampling strategies on a wide range of symbolic regression problems. In contrast to most work, we not only compare the methods over a given evaluation budget, but also over a given time budget as time is usually limited in practice. We find that for a given evaluation budget, \(\epsilon\) -lexicase selection in combination with a down-sampling strategy outperforms all other methods. If the given running time is very short, lexicase variants using batches of training cases perform best. Further, we find that the combination of tournament selection with informed down-sampling performs well in all studied settings.

In standard genetic programming (stdGP), solutions are varied by modifying their syntax, with uncertain effects on their semantics. Geometric-semantic genetic programming (GSGP), a popular variant of GP, effectively searches the semantic solution space using variation operations based on linear combinations, although it results in significantly larger solutions. This paper presents Transformer Semantic Genetic Programming (TSGP), a novel and flexible semantic approach that uses a generative transformer model as search operator. The transformer is trained on synthetic test problems and learns semantic similarities between solutions. Once the model is trained, it can be used to create offspring solutions with high semantic similarity also for unseen and unknown problems. Experiments on several symbolic regression problems show that TSGP generates solutions with comparable or even significantly better prediction quality than stdGP, SLIM_GSGP, DSR, and DAE-GP. Like SLIM_GSGP, TSGP is able to create new solutions that are semantically similar without creating solutions of large size. An analysis of the search dynamic reveals that the solutions generated by TSGP are semantically more similar than the solutions generated by the benchmark approaches allowing a better exploration of the semantic solution space.

OBJECTIVES: Explanations help to understand why anomaly detection algorithms identify data as anomalous. This study evaluates whether robustly standardized explanation scores correctly identify the implausible variables that make cancer data anomalous. MATERIALS AND METHODS: The dataset analyzed consists of 18 587 truncated real-world cancer registry records containing 8 categorical variables describing patients diagnosed with bladder and lung tumors. We identified 800 anomalous records using an autoencoder's per-record reconstruction error, which is a common neural network-based anomaly detection approach. For each variable of a record, we determined a robust explanation score, which indicates how anomalous the variable is. A variable's robust explanation score is the autoencoder's per-variable reconstruction error measured by cross-entropy and robustly standardized across records; that is, large reconstruction errors have a small effect on standardization. To evaluate the explanation scores, medical coders identified the implausible variables of the anomalous records. We then compare the explanation scores to the medical coders' validation in a classification and ranking setting. As baselines, we identified anomalous variables using the raw autoencoder's per-variable reconstruction error, the non-robustly standardized per-variable reconstruction error, the empirical frequency of implausible variables according to the medical coders' validation, and random selection or ranking of variables. RESULTS: When we sort the variables by their robust explanation scores, on average, the 2.37 highest-ranked variables contain all implausible variables. For the baselines, on average, the 2.84, 2.98, 3.27, and 4.91 highest-ranked variables contain all the variables that made a record implausible. DISCUSSION: We found that explanations based on robust explanation scores were better than or as good as the baseline explanations examined in the classification and ranking settings. Due to the international standardization of cancer data coding, we expect our results to generalize to other cancer types and registries. As we anticipate different magnitudes of per-variable autoencoder reconstruction errors in data from other medical registries and domains, these may also benefit from robustly standardizing the reconstruction errors per variable. Future work could explore methods to identify subsets of anomalous variables, addressing whether individual variables or their combinations contribute to anomalies. This direction aims to improve the interpretability and utility of anomaly detection systems. CONCLUSIONS: Robust explanation scores can improve explanations for identifying implausible variables in cancer data.

Large language models have recently become known for their ability to generate computer programs, especially through tools, such as GitHub Copilot, a domain where genetic programming (GP) has been very successful so far. Although they require different inputs (free-text versus input/output examples) their goal is the same—program synthesis. Therefore, in this work, we compare how well GitHub Copilot and GP perform on common program synthesis benchmark problems. We study the structure and diversity of the generated programs by using well-known software metrics. We find that GitHub Copilot and GP solve a similar number of benchmark problems (85.2% versus 77.8%, respectively). We find that GitHub Copilot generated smaller and less complex programs as GP, while GP is able to find new and unique problem solving strategies. This increase in diversity of solutions comes at a cost. When analyzing the success rates for 100 runs per problem, GitHub Copilot outperforms GP on over 50% of the problems.

Genetic Programming (GP) often uses large training sets and requires all individuals to be evaluated on all training cases during selection. Random down-sampled lexicase selection evaluates individuals on only a random subset of the training cases, allowing for more individuals to be explored with the same number of program executions. However, sampling randomly can exclude important cases from the down-sample for a number of generations, while cases that measure the same behavior (synonymous cases) may be overused. In this work, we introduce Informed Down-Sampled Lexicase Selection. This method leverages population statistics to build down-samples that contain more distinct and therefore informative training cases. Through an empirical investigation across two different GP systems (PushGP and Grammar-Guided GP), we find that informed down-sampling significantly outperforms random down-sampling on a set of contemporary program synthesis benchmark problems. Through an analysis of the created down-samples, we find that important training cases are included in the down-sample consistently across independent evolutionary runs and systems. We hypothesize that this improvement can be attributed to the ability of Informed Down-Sampled Lexicase Selection to maintain more specialist individuals over the course of evolution, while still benefiting from reduced per-evaluation costs.

Epsilon-lexicase selection is a parent selection method in genetic programming that has been successfully applied to symbolic regression problems. Recently, the combination of random subsampling with lexicase selection significantly improved performance in other genetic programming domains such as program synthesis. However, the influence of subsampling on the solution quality of real-world symbolic regression problems has not yet been studied. In this paper, we propose down-sampled epsilon-lexicase selection which combines epsilon-lexicase selection with random subsampling to improve the performance in the domain of symbolic regression. Therefore, we compare down-sampled epsilon-lexicase with traditional selection methods on common real-world symbolic regression problems and analyze its influence on the properties of the population over a genetic programming run. We find that the diversity is reduced by using down-sampled epsilon-lexicase selection compared to standard epsilon-lexicase selection. This comes along with high hyperselection rates we observe for down-sampled epsilon-lexicase selection. Further, we find that down-sampled epsilon-lexicase selection outperforms the traditional selection methods on all studied problems. Overall, with down-sampled epsilon-lexicase selection we observe an improvement of the solution quality of up to 85% in comparison to standard epsilon-lexicase selection.

The automatic generation of computer programs is one of the main applications with practical relevance in the field of evolutionary computation. With program synthesis techniques not only software developers could be supported in their everyday work but even users without any programming knowledge could be empowered to automate repetitive tasks and implement their own new functionality. In recent years, many novel program synthesis approaches based on evolutionary algorithms have been proposed and evaluated on common benchmark problems. Therefore, we identify and discuss in this survey the relevant evolutionary program synthesis approaches in the literature and provide an in-depth analysis of their performance. The most influential approaches we identify are stack-based, grammar-guided, as well as linear genetic programming (GP). For the stack-based approaches, we identify 37 in-scope papers, and for the grammar-guided and linear GP approaches, we identify 12 and 5 papers, respectively. Furthermore, we find that these approaches perform well on benchmark problems if there is a simple mapping from the given input to the correct output. On problems where this mapping is complex, e.g., if the problem consists of several subproblems or requires iteration/recursion for a correct solution, results tend to be worse. Consequently, for future work, we encourage researchers not only to use a program’s output for assessing the quality of a solution but also the way toward a solution (e.g., correctly solved subproblems).

From a practitioners perspective, the number of in-put/output examples used during the training process in program synthesis studies is too large, as in practice, these examples must be labeled by hand. Therefore, this paper analyzes the influence of different training set sizes on the performance, generalization ability, as well as the structure of the programs generated by grammar-guided genetic programming. We compare down-sampled lexicase selection with standard lexicase selection on three common problems from the general program synthesis benchmark suite. First, we find that both lexicase variants are robust against reducing the amount of training data. We find that standard lexicase has a tendency to overfit the training data on some problems. With down-sampled lexicase, in contrast, overfitting on training data is reduced and evolved programs generalize better on held-out test cases. Consequently, we suggest to use grammar-guided genetic programming with down-sampled lexicase selection in the program synthesis domain.

GitHub Copilot, an extension for the Visual Studio Code development environment powered by the large-scale language model Codex, makes automatic program synthesis available for software developers. This model has been extensively studied in the field of deep learning, however, a comparison to genetic programming, which is also known for its performance in automatic program synthesis, has not yet been carried out. In this paper, we evaluate GitHub Copilot on standard program synthesis benchmark problems and compare the achieved results with those from the genetic programming literature. In addition, we discuss the performance of both approaches. We find that the performance of the two approaches on the benchmark problems is quite similar, however, in comparison to GitHub Copilot, the program synthesis approaches based on genetic programming are not yet mature enough to support programmers in practical software development. Genetic programming usually needs a huge amount of expensive hand-labeled training cases and takes too much time to generate solutions. Furthermore, source code generated by genetic programming approaches is often bloated and difficult to understand. For future work on program synthesis with genetic programming, we suggest researchers to focus on improving the execution time, readability, and usability.

Linear Genetic Programming (LGP) represents programs as sequences of instructions and has a Directed Acyclic Graph (DAG) dataflow. The results of instructions are stored in registers that can be used as arguments by other instructions. Instructions that are disconnected from the main part of the program are called noneffective instructions, or structural introns. They also appear in other DAG-based GP approaches like Cartesian Genetic Programming (CGP). This article studies four hypotheses on the role of structural introns: noneffective instructions (1) serve as evolutionary memory, where evolved information is stored and later used in search, (2) preserve population diversity, (3) allow neutral search, where structural introns increase the number of neutral mutations and improve performance, and (4) serve as genetic material to enable program growth. We study different variants of LGP controlling the influence of introns for symbolic regression, classification, and digital circuits problems. We find that there is (1) evolved information in the noneffective instructions that can be reactivated and that (2) structural introns can promote programs with higher effective diversity. However, both effects have no influence on LGP search performance. On the other hand, allowing mutations to not only be applied to effective but also to noneffective instructions (3) increases the rate of neutral mutations and (4) contributes to program growth by making use of the genetic material available as structural introns. This comes along with a significant increase of LGP performance, which makes structural introns important for LGP.

Abstract The initial population in genetic programming (GP) should form a representative sample of all possible solutions (the search space). While large populations accurately approximate the distribution of possible solutions, small populations tend to incorporate a sampling error. This paper analyzes how the size of a GP population affects the sampling error and contributes to answering the question of how to size initial GP populations. First, we present a probabilistic model of the expected number of subtrees for GP populations initialized with full, grow, or ramped half-and-half. Second, based on our frequency model, we present a model that estimates the sampling error for a given GP population size. We validate our models empirically and show that, compared to smaller population sizes, our recommended population sizes largely reduce the sampling error of measured fitness values. Increasing the population sizes even more, however, does not considerably reduce the sampling error of fitness values. Last, we recommend population sizes for some widely used benchmark problem instances that result in a low sampling error. A low sampling error at initialization is necessary (but not sufficient) for a reliable search since lowering the sampling error means that the overall random variations in a random sample are reduced. Our results indicate that sampling error is a severe problem for GP, making large initial population sizes necessary to obtain a low sampling error. Our model allows practitioners of GP to determine a minimum initial population size so that the sampling error is lower than a threshold, given a confidence level.

The generalizability of programs synthesized by genetic programming (GP) to unseen test cases is one of the main challenges of GP-based program synthesis. Recent work showed that increasing the amount of training data improves the generalizability of the programs synthesized by GP. However, generating training data is usually an expensive task as the output value for every training case must be calculated manually by the user. Therefore, this work suggests an approximation of the expected generalization ability of solution candidates found by GP. To obtain candidate solutions that all solve the training cases, but are structurally different, a GP run is not stopped after the first solution is found that solves all training instances but search continues for more generations. For all found candidate solutions (solving all training cases), we calculate the behavioral vector for a set of randomly generated additional inputs. The proportion of the number of different found candidate solutions generating the same behavioral vector with highest frequency compared to all other found candidate solutions with different behavior can serve as an approximation for the generalizability of the found solutions. The paper presents experimental results for a number of standard program synthesis problems confirming the high prediction accuracy.

Estimation of distribution genetic programming (EDA-GP) algorithms are metaheuristics where sampling new solutions from a learned probabilistic model replaces the standard mutation and recombination operators of genetic programming (GP). This paper presents DAE-GP, a new EDA-GP which uses denoising autoencoder long short-term memory networks (DAE-LSTMs) as probabilistic model. DAE-LSTMs are artificial neural networks that first learn the properties of a parent population by mapping promising candidate solutions to a latent space and reconstructing the candidate solutions from the latent space. The trained model is then used to sample new offspring solutions. We show on a generalization of the royal tree problem that DAE-GP outperforms standard GP and that performance differences increase with higher problem complexity. Furthermore, DAE-GP is able to create offspring with higher fitness from a learned model in comparison to standard GP. We believe that the key reason for the high performance of DAE-GP is that we do not impose any assumptions about the relationships between learned variables which is different to previous EDA-GP models. Instead, DAE-GP flexibly identifies and models relevant dependencies of promising candidate solutions.

Estimation of Distribution Algorithms (EDAs) are metaheuristics where learning a model and sampling new solutions replaces the variation operators recombination and mutation used in standard Genetic Algorithms. The choice of these models as well as the corresponding training processes are subject to the bias/variance tradeoff, also known as under- and overfitting: simple models cannot capture complex interactions between problem variables, whereas complex models are susceptible to modeling random noise. This paper suggests using Denoising Autoencoders (DAEs) as generative models within EDAs (DAE-EDA). The resulting DAE-EDA is able to model complex probability distributions. Furthermore, overfitting is less harmful, since DAEs overfit by learning the identity function. This overfitting behavior introduces unbiased random noise into the samples, which is no major problem for the EDA but just leads to higher population diversity. As a result, DAE-EDA runs for more generations before convergence and searches promising parts of the solution space more thoroughly. We study the performance of DAE-EDA on several combinatorial single-objective optimization problems. In comparison to the Bayesian Optimization Algorithm, DAE-EDA requires a similar number of evaluations of the objective function but is much faster and can be parallelized efficiently, making it the preferred choice especially for large and difficult optimization problems.

Program synthesis is one of the relevant applications of GP with a strong impact on new fields such as genetic improvement. In order for synthesized code to be used in real-world software, the structure of the programs created by GP must be maintainable. We can teach GP how real-world software is built by learning the relevant properties of mined human-coded software - which can be easily accessed through repository hosting services such as GitHub. So combining program synthesis and repository mining is a logical step. In this paper, we analyze if GP can write programs with properties similar to code produced by human software developers. First, we compare the structure of functions generated by different GP initialization methods to a mined corpus containing real-world software. The results show that the studied GP initialization methods produce a totally different combination of programming language elements in comparison to real-world software. Second, we propose perplexity pressure and analyze how its use changes the properties of code produced by GP. The results are very promising and show that we can guide the search to the desired program structure. Thus, we recommend using perplexity pressure as it can be easily integrated in various search-based algorithms.

In linear variants of Genetic Programming (GP) like linear genetic programming (LGP), structural introns can emerge, which are nodes that are not connected to the final output and do not contribute to the output of a program. There are claims that such non-effective code is beneficial for search, as it can store relevant and important evolved information that can be reactivated in later search phases. Furthermore, introns can increase diversity, which leads to higher GP performance. This paper studies the role of non-effective code by comparing the performance of LGP variants that deal differently with non-effective code for standard symbolic regression problems. As we find no decrease in performance when removing or randomizing structural introns in each generation of a LGP run, we have to reject the hypothesis that structural introns increase LGP performance by preserving meaningful sub-structures. Our results indicate that there is no important information stored in structural introns. In contrast, we find evidence that the increase of diversity due to structural introns positively affects LGP performance.

Estimation of distribution programming (EDP) replaces standard GP variation operators with sampling from a learned probability model. To ensure a minimum amount of variation in a population, EDP adds random noise to the probabilities of random variables. This paper studies the bias of EDP's variation operator by performing random walks. The results indicate that the complexity of the EDP model is high since the model is overfitting the parent solutions when no additional noise is being used. Adding only a low amount of noise leads to a strong bias towards small trees. The bias gets stronger with an increased amount of noise. Our findings do not support the hypothesis that sampling drift is the reason for the loss of diversity.

Ensemble methods combine the predictions of a set of models to reach a better prediction quality compared to a single model's prediction. The ensemble process consists of three steps: 1) the generation phase where the models are created, 2) the selection phase where a set of possible ensembles is composed and one is selected by a selection method, 3) the fusion phase where the individual models' predictions of the selected ensemble are combined to an ensemble's estimate. This paper proposes CovSel, a selection approach for regression problems that ranks ensembles based on the coverage of adequately estimated training points and selects the ensemble with the highest coverage to be used in the fusion phase. An ensemble covers a training point if at least one of its models produces an adequate prediction for this training point. The more training points are covered this way, the higher is the ensemble's coverage. The selection of the "right" ensemble has a large impact on the final prediction. Results for two symbolic regression problems show that CovSel improves the predictions for various state-of-the-art fusion methods for ensembles composed of independently evolved GP models and also beats approaches based on single GP models.

DC∗ is a method for generating interpretable fuzzy information granules from pre-classified data. It is based on the subsequent application of LVQ1 for data compression and an ad-hoc procedure based on A∗ to represent data with the minimum number of fuzzy information granules satisfying some interpretability constraints. While being efficient in tackling several problems, the A∗ procedure included in DC∗ may happen to require a long computation time because the A∗ algorithm has exponential time complexity in the worst case. In this paper, we approach the problem of driving the search process of A∗ by suggesting a close-to-optimal solution that is produced through a Genetic Algorithm (GA). Experimental evaluations show that, by driving the A∗ algorithm embodied in DC∗ with a GA solution, the time required to perform data granulation can be reduced by at least 45% and up to 99%.

Recent work discovered that fitness landscapes induced by Iterated Local Search (ILS) may consist of multiple clusters, denoted as funnels or communities of local optima. Such studies exist only for perturbation operators (kicks) with low strength. We examine how different strengths of the ILS perturbation operator affect the number and size of clusters. We present an empirical study based on local optima networks from NK fitness landscapes. Our results show that a properly selected perturbation strength can help overcome the effect of ILS getting trapped in clusters of local optima. This has implications for designing effective ILS approaches in practice, where traditionally only small perturbations or complete restarts are applied, with the middle ground of intermediate perturbation strengths largely unexplored.

We conduct an analysis of local optima networks extracted from fitness landscapes of the Kauffman NK model under iterated local search. Applying the Markov Cluster Algorithm for community detection to the local optima networks, we find that the landscapes consist of multiple clusters. This result complements recent findings in the literature that landscapes often decompose into multiple funnels, which increases their difficulty for iterated local search. Our results suggest that the number of clusters as well as the size of the cluster in which the global optimum is located are correlated to the search difficulty of landscapes. We conclude that clusters found by community detection in local optima networks offer a new way to characterize the multi-funnel structure of fitness landscapes.

Previous studies have used statistical analysis of fitness landscapes such as ruggedness and deceptiveness in order to predict the expected quality of heuristic search methods. Novel approaches for predicting the performance of heuristic search are based on the analysis of local optima networks (LONs). A LON is a compressed stochastic model of a fitness landscape's basin transitions. Recent literature has suggested using various LON network measurements as predictors for local search performance.

For fixed-length binary representations as used in genetic algorithms, standard recombination operators (e.g.,~one-point crossover) are unbiased. Thus, the application of recombination only reshuffles the alleles and does not change the statistical properties in the population. Using a geometric view on recombination operators, most search operators for fixed-length strings are geometric, which means that the distances between offspring and their parents are less than, or equal to, the distance between their parents. In genetic programming (GP) and grammatical evolution (GE), the situation is different since the recombination operators are applied to variable-length structures. Thus, most recombination operators for GE and GP are not geometric.

We present a parallel version of RBM-EDA. RBM-EDA is an Estimation of Distribution Algorithm (EDA) that models dependencies between decision variables using a Restricted Boltzmann Machine (RBM). In contrast to other EDAs, RBM-EDA mainly uses matrix-matrix multiplications for model estimation and sampling. Hence, for implementation, standard libraries for linear algebra can be used. This allows an easy parallelization and leads to a high utilization of parallel architectures. The probabilistic model of the parallel version and the version on a single core are identical. We explore the speedups gained from running RBM-EDA on a Graphics Processing Unit. For problems of bounded difficulty like deceptive traps, parallel RBM-EDA is faster by several orders of magnitude (up to 750 times) in comparison to a single-threaded implementation on a CPU. As the speedup grows linearly with problem size, parallel RBM-EDA may be particularly useful for large problems.

Genetic programming (GP) has problems with structural difficulty as it is unable to search effectively for solutions requiring very full or very narrow trees. As a result of structural difficulty, GP has a bias towards narrow trees which means it searches effectively for solutions requiring narrow trees. This paper focuses on the structural difficulty of grammatical evolution (GE). In contrast to GP, GE works on variable-length binary strings and uses a grammar in Backus-Naur Form (BNF) to map linear genotypes to phenotype trees. The paper studies whether and how GE is affected by structural difficulty. For the analysis, we perform random walks through the search space and compare the structure of the visited solutions. In addition, we compare the performance of GE and GP for the Lid problem. Results show that GE representation is biased, this means it has problems with structural difficulty. For binary trees, GE has a bias towards narrow and deep structures; thus GE outperforms standard GP if optimal solutions are composed of very narrow and deep structures. In contrast, problems where optimal solutions require more dense trees are easier to solve for GP than for GE.

In the Euclidean optimal communication spanning tree problem, the edges in optimal trees not only have small weights but also point with high probability toward the center of the graph. These characteristics of optimal solutions can be used for the design of problem-specific evolutionary algorithms (EAs). Recombination operators of direct encodings like edge-set and NetDir can be extended such that they prefer not only edges with small distance weights but also edges that point toward the center of the graph. Experimental results show higher performance and robustness in comparison to EAs using existing crossover strategies.

This paper considers the Euclidean variant of the optimal communication spanning tree (OCST) problem. Previous work analyzed features of high-quality solutions and found that edges in optimal solutions have low weight and point towards the center of a tree. Consequently, integrating this problem-specific knowledge into a metaheuristic increases its performance. In this paper, we present an approach to dynamically change the objective function to guide the search process into promising areas. Our approach is based on guided local search. The resulting problem-specific guided local search method considering weight and orientation of edges outperforms standard variants considering only edge weights as well as state-of-the-art evolutionary algorithms using edge-sets for larger problems.

In the field of decision-making a fundamental problem is how to uncover people's choice behavior. While choices them- selves are often observable, our underlying decision strategies determining these choices are not entirely understood. Previous research defined a number of decision strategies and conjectured that people do not apply only one strategy but switch strategies during the decision process. To the best of our knowledge, empirical evidence for the latter conjecture is missing. This is why we monitored the purchase decisions 624 consumers shopping online. We study how many of the observed choices can be explained by the existing strategies in their pure form, how many decisions can be explained if we account for switching behavior, and investigate switching behavior in detail. Since accounting for switching leads to a large search space of possible mixed decision strategies, we apply a genetic algorithm to find the set of mixed decision strategies which best explains the observed behavior. The results show that mixed strategies are used more often than pure ones and that a set of four mixed strategies is able to explain 93.9% of choices in a scenario with 4 alternatives and 75.4% of choices in a scenario with 7 alternatives.

This paper considers the Euclidean variant of the optimal communciation spanning tree (OCST) problem. Researches have analyzed the structure of the problem and found that high quality solutions prefer edges of low cost. Further, edges pointing to the center of the network are more likely to be included in good solutions. We add to the literature and provide additional insights into the structure of the OCST problem. Therefore, we investigate properies of the whole tree, such as node degrees and the Wiener index. The results reveal that optimal solutions are structured in a star-like manner. There are few nodes with high node degrees, these nodes are located next to the graph's center. The majority of the nodes have very low node degrees. Especially, nodes with degree one are very common and located far away of the center. We exploit these insights to develop a construction heuristic, which builds spanning trees with similar properties. Experiments indicate a high solution quality for the OCST problem. In a next step, we seed the initial population of an evolutionary algorithm (EA) with solutions constructed with our method. An experimental study demonstrates the merits of using a biased initialization: the algorithm is faster, better compared to the same algorithm using random starting solutions.

Problem-specific encodings can improve the performance of metaheuristics, such as genetic algorithms or simulated annealing. This paper studies the link-biased (LB) encoding, which is a tree representation, and applies metaheuristics using this encoding to the minimum communication spanning tree (MCST) problem. Given the communication requirements of the nodes, the MCST problem seeks a communication spanning tree with minimum total cost. Optimal solutions for MCST problems are similar to minimum spanning trees (MSTs), and the LB encoding exploits this property by encoding trees similar to MSTs with higher probability. The paper investigates how to systematically design problem-specific encodings for MCST problems and how to set the encoding-specific parameter that controls the bias of the LB encoding towards MSTs; it then presents performance results for various MCST problems.

The edge-set encoding of trees directly represents trees as sets of their edges. Nonheuristic operators for edge-sets manipulate trees' edges without regard for their weights, while heuristic operators consider edges' weights when including or excluding them. In the latter case, the operators generally favor edges with lower weights, and they tend to generate trees that resemble minimum spanning trees. This bias is strong, which suggests that evolutionary algorithms (EAs) that employ heuristic operators will succeed when optimum solutions resemble minimum spanning trees (MSTs) but fail otherwise.

Software development is becoming more and more complex. Traditionally and to date, the software development process rather corresponds to job-shop manufacturing. Therefore, the ever growing demands for different kinds of software as well as the ongoing globalization require more efficient development processes. Both scientific literature and practical experience hence postulate a necessary industrialization of software development and design of novel forms of specialization, task distribution, and collaboration. Existing approaches to collaborative software development can be classified and analyzed according to multiple categories. By evaluating these, current deficiencies are identified and discussed for further investigation.

The node-depth encoding has elements from direct and indirect encoding for trees which encodes trees by storing the depth of nodes in a list. Node-depth encoding applies specific search operators that is a typical characteristic for direct encodings. An investigation into the bias of the initialization process and the mutation operators of the node-depth encoding shows that the initialization process has a bias to solutions with small depths and diameters, and a bias towards stars. This investigation, also, shows that the mutation operators are unbiased. The performance of node-depth encoding is investigated for the bounded-diameter minimum spanning tree problem. The results are presented for Euclidean instances presented in the literature. In contrast with the expectation, the evolutionary algorithm using the biased initialization operator does not allow evolutionary algorithms to find better solutions compared to an unbiased initialization. In comparison to other evolutionary algorithms for the bounded-diameter minimum spanning tree evolutionary algorithms using the node-depth encoding have a good performance.

While in the past decades research on multi-objective evolutionary algorithms (MOEA) has aimed at finding the whole set of Pareto optimal solutions, current approaches focus on only those parts of the Pareto front which satisfy the preferences of the decision maker (DM). Therefore, they integrate the DM early on in the optimization process instead of leaving him/her alone with the final choice of one solution among the whole Pareto optimal set. In this paper, we address an aspect which has been neglected so far in the research on integrating preferences: in most real-world problems, there is not only one DM, but a group of DMs trying to find one consensus decision all participants are willed to agree to. Therefore, our aim is to introduce methods which focus on the part of the Pareto front which satisfies the preferences of several DMs concurrently. We assume that the DMs have some vague notion of their preferences a priori the search in form of a reference point or goal. Thus, we present and compare several reference point based approaches for group decisions and evaluate them on three ZDT and two flow shop problems.

The optimal communication spanning tree (OCST) problem is a well known $\mathcal{NP}$-hard combinatorial optimization problem which seeks a spanning tree that satisfies all given communication requirements for minimal total costs. It has been shown that optimal solutions of OCST problems are biased towards the much simpler minimum spanning tree (MST) problem. Therefore, problem-specific representations for EAs like heuristic variants of edge-sets that are biased towards MSTs show high performance.In this paper, additional properties of optimal solutions for Euclidean variants of OCST problems are studied. Experimental results show that not only edges in optimal trees are biased towards low-distance weights but also edges which are directed towards the graph's center are overrepresented in optimal solutions. Therefore, efficient heuristic search algorithms for OCST should be biased towards edges with low distance weight \emph{and} edges that point towards the center of the graph. Consequently, we extend the recombination operator of edge-sets such that the orientation of the edges is considered for constructing offspring solutions. Experimental results show a higher search performance in comparison to EAs using existing crossover strategies of edge-sets. As a result, we suggest to consider not only the distance weights but also the orientation of edges in heuristic solution approaches for the OCST problem.

Recently, advances have been made in continuous, normal-distribution-based Estimation-of-DistributionAlgorithms (EDAs) by scaling the variance upfrom the maximum-likelihood estimate. When doneproperly, such scaling has been shown to preventpremature convergence on slope-like regions ofthe search space. In this paper we specificallyfocus on one way of scaling that was previouslyintroduced as Adaptive Variance Scaling (AVS). It wasfound that when using AVS, the average number offitness evaluations grows subquadratically withthe dimensionality on a wide range of unimodaltest-problems, competitively with the CMA-ES.Still, room for improvement exists because thevariance doesn't always have to be scaled. Apreviously introduced trigger based on correlationthat determines when to apply scaling was shownto fail on higher dimensional problems. Here weprovide a new solution called the Standard-DeviationRatio (SDR) trigger that is integrated with theIterated Density-Estimation Evolutionary Algorithm(IDEA). Intuitively put, scaling istriggered with SDR only if improvements are foundto be far away from the mean. SDR works even inhigh dimensions as a result of factorizing thedecision rule behind the trigger according to theestimated Bayesian factorization. We evaluateSDR-AVS-IDEA on the same set ofbenchmark problems and compare it with AVS-IDEAand CMA-ES. We find that the addition of SDR givesAVS-IDEA an important extra edgefor it to be used in future research and inapplications both in single-objective optimizationas well as in multi-objective and dynamicoptimization. In addition, we provide practical rulesof thumb for parameter settings for usingSDR-AVS-IDEA that result in anasymptotic scale-up behavior that is sublinearfor the population size (O(l^{0.85})) andsubquadratic (O(l^{1.85})) for thenumber of evaluations.

No abstract available.

The distribution of software engineering tasks is becoming ever more common. Requirements engineering, as the most critical phase, therefore requires methods and tools to support distributed teams. However, nearly all requirements engineering methods have originally been designed for collocated scenarios. Before applying these methods in distributed settings in practice and for scientific rigor, proper evaluation has to be conducted. Hence, we developed a methodologically sound and cost-effective evaluation method for distributed requirements engineering methods as well as the corresponding tool infrastructure for conducting evaluation projects.

This paper uses an entertaining student "sports" game to illustrate that GAs can be adapted to problems with uncertain properties and complexity. These problems can be solved easily through GAs within a few seconds. Contrary to this, using standard MILP techniques does not yield results in a reasonable time.

It has previously been shown analytically and experimentally that continuous Estimation of Distribution Algorithms (EDAs) based on the normal pdf can easily suffer from premature convergence. This paper takes a principled first step towards solving this problem. First, prerequisites for the successful use of search distributions in EDAs are presented. Then, an adaptive variance scaling theme is introduced that aims at reducing the risk of premature convergence. Integrating the scheme into the iterated density--estimation evolutionary algorithm (IDEA) yields the correlation-triggered adaptive variance scaling IDEA (CT-AVS-IDEA). The CT-AVS-IDEA is compared to the original IDEA and the Evolution Strategy with Covariance Matrix Adaptation (CMA-ES) on a wide range of unimodal test-problems by means of a scalability analysis. It is found that the average number of fitness evaluations grows subquadratically with the dimensionality, competitively with the CMA-ES. In addition, CT-AVS-IDEA is indeed found to enlarge the class of problems that continuous EDAs can solve reliably.

Of late, much progress has been made in developing estimation of distribution algorithms (EDA), algorithms that use probabilistic modelling of high quality solutions to guide their search. While experimental results on EDA behaviour are widely available, theoretical results are still rare. This is especially the case for continuous EDA. In this article, we develop theory that predicts the behaviour of the univariate marginal distribution algorithm in the continuous domain (UMDA/sub c/) with truncation selection on monotonous fitness functions. Monotonous functions are commonly used to model the algorithm behaviour far from the optimum. Our result includes formulae to predict population statistics in a specific generation as well as population statistics after convergence. We find that population statistics develop identically for monotonous functions. We show that if assuming monotonous fitness functions, the distance that UMDA/sub c/ travels across the search space is bounded and solely relies on the percentage of selected individuals and not on the structure of the fitness landscape. This can be problematic if this distance is too small for the algorithm to find the optimum. Also, by wrongly setting the selection intensity, one might not be able to explore the whole search space.

In search tasks, for example when individuals search for the best price of a product, individuals are confronted in sequential steps with different situations and they have to decide whether to continue or stop searching. The decision behavior of individuals in such search tasks is described by a search strategy.This paper presents a new approach of finding high-quality search strategies by using genetic algorithms (GAs). Only the structure of the search strategies and the basic building blocks (price thresholds and price patterns) that can be used for the search strategies are pre-specified. It is the purpose of the GA to construct search strategies that well describe human search behavior. The search strategies found by the GA are able to predict human behavior in search tasks better than traditional search strategies from the literature which are usually based on theoretical assumptions about human behavior in search tasks. Furthermore, the found search strategies are reasonable in the sense that they can be well interpreted, and generally that means they describe the search behavior of a larger group of individuals and allow some kind of categorization and classification.The results of this study open a new perspective for future research in developing behavioral strategies. Instead of deriving search strategies from theoretical assumptions about human behavior, researchers can directly analyze human behavior in search tasks and find appropriate and high-quality search strategies. These can be used for gaining new insights into the motivation behind human search and for developing new theoretical models about human search behavior.

For the reliable communication network design (RCND) problem unreliable links are available, each bearing several options which have different levels of reliability and varying costs. The goal is to find the most cost-effective communication network design that satisfies a predefined overall reliability constraint. This paper presents two new evolutionary algorithm (EA) approaches to solving the RCND problem: LaBORNet and BaBORNet. LaBORNet uses an encoding that represents the network topology as well as the used link options while repairing infeasible solutions using an additional repair heuristic (CURE). BaBORNet encodes only the network topology and determines the link options by using the repair heuristic CURE as a local search method. The experimental results show that the new EA approaches using repair heuristics outperform existing EA approaches from the literature using penalties for infeasible solutions. They also find better solutions for existing problems from the literature, as well as for new and larger test problems.

This work presents and compares three heuristics for the combinatorial auction problem. Besides a simple greedy (SG) mechanism, two metaheuristics, a simulated annealing (SA), and a genetic algorithm (GA) approach are developed which use the combinatorial auction process to find an allocation with maximal revenue for the auctioneer. The performance of these three heuristics is evaluated in the context of a price controlled resource allocation process designed for the control and provision of distributed information services. Comparing the SG and SA method shows that depending on the problem structure the performance of the SA is up to 20% higher than the performance of the simple greedy allocation method. The proposed GA approach, using a random key encoding, results in a further improvement of the solution quality. Although the metaheuristic approaches result in higher search performance, the computational effort in terms of used CPU time is higher in comparison to the simple greedy mechanism. However, the absolute overall computation time is low enough to enable real-time execution in the considered IS application domain.

This paper discusses how the use of redundant representations influences the performance of genetic and evolutionary algorithms. Representations are redundant if the number of genotypes exceeds the number of phenotypes. A distinction is made between synonymously and non-synonymously redundant representations. Representations are synonymously redundant if the genotypes that represent the same phenotype are very similar to each other. Non-synonymously redundant representations do not allow genetic operators to work properly and result in a lower performance of evolutionary search. When using synonymously redundant representations, the performance of selectorecombinative genetic algorithms (GAs) depends on the modification of the initial supply. We have developed theoretical models for synonymously redundant representations that show the necessary population size to solve a problem and the number of generations goes with O(2(kr)/r), where kr is the order of redundancy and r is the number of genotypic building blocks (BB) that represent the optimal phenotypic BB. As a result, uniformly redundant representations do not change the behavior of GAs. Only by increasing r, which means overrepresenting the optimal solution, does GA performance increase. Therefore, non-uniformly redundant representations can only be used advantageously if a-priori information exists regarding the optimal solution. The validity of the proposed theoretical concepts is illustrated for the binary trivial voting mapping and the real-valued link-biased encoding. Our empirical investigations show that the developed population sizing and time to convergence models allow an accurate prediction of the empirical results.

When using genetic and evolutionary algorithms for network design, choosing a good representation scheme for the construction of the genotype is important for algorithm performance. One of the most common representation schemes for networks is the characteristic vector representation. However, with encoding trees, and using crossover and mutation, invalid individuals occur that are either under- or over-specified. When constructing the offspring or repairing the invalid individuals that do not represent a tree, it is impossible to distinguish between the importance of the links that should be used. These problems can be overcome by transferring the concept of random keys from scheduling and ordering problems to the encoding of trees. This paper investigates the performance of a simple genetic algorithm (SGA) using network random keys (NetKeys) for the one-max tree and a real-world problem. The comparison between the network random keys and the characteristic vector encoding shows that despite the effects of stealth mutation, which favors the characteristic vector representation, selectorecombinative SGAs with NetKeys have some advantages for small and easy optimization problems. With more complex problems, SGAs with network random keys significantly outperform SGAs using characteristic vectors. This paper shows that random keys can be used for the encoding of trees, and that genetic algorithms using network random keys are able to solve complex tree problems much faster than when using the characteristic vector. Users should therefore be encouraged to use network random keys for the representation of trees.