This article examines various methods of computing uncertainty and diversity for active learning in genetic programming. We found that the model population in genetic programming can be exploited to select informative training data points by using a model ensemble combined with an uncertainty metric. We explored several uncertainty metrics and found that differential entropy performed the best. We also compared two data diversity metrics and found that correlation as a diversity metric performs better than minimum Euclidean distance, although there are some drawbacks that prevent correlation from being used on all problems. Finally, we combined uncertainty and diversity using a Pareto optimization approach to allow both to be considered in a balanced way to guide the selection of informative and unique data points for training.

In this contribution, we explore Cartesian Genetic Programming for image analysis of biomedical data. Producing large quantities of human-labeled biomedical data is an expensive task. Here, we introduce a way for CGP to use a small amount of training data, without loss in performance. To define the size of the training data, we utilize an Active Learning method to direct the algorithm towards informative samples. We examine how sampling a small set of data from the CELLPOSE dataset affects the performance of CGP. We also study the effects of restarting CGP with Active Learning. We found that using several restarts can lead to a more diverse set of the highest-performing solutions with fewer active nodes while maintaining similar performance to standard CGP.

Evolution provides a creative fount of complex and subtle adaptations that often surprise the scientists who discover them. However, the creativity of evolution is not limited to the natural world: Artificial organisms evolving in computational environments have also elicited surprise and wonder from the researchers studying them. The process of evolution is an algorithmic process that transcends the substrate in which it occurs. Indeed, many researchers in the field of digital evolution can provide examples of how their evolving algorithms and organisms have creatively subverted their expectations or intentions, exposed unrecognized bugs in their code, produced unexpectedly adaptations, or engaged in behaviors and outcomes, uncannily convergent with ones found in nature. Such stories routinely reveal surprise and creativity by evolution in these digital worlds, but they rarely fit into the standard scientific narrative. Instead they are often treated as mere obstacles to be overcome, rather than results that warrant study in their own right. Bugs are fixed, experiments are refocused, and one-off surprises are collapsed into a single data point. The stories themselves are traded among researchers through oral tradition, but that mode of information transmission is inefficient and prone to error and outright loss. Moreover, the fact that these stories tend to be shared only among practitioners means that many natural scientists do not realize how interesting and lifelike digital organisms are and how natural their evolution can be. To our knowledge, no collection of such anecdotes has been published before. This article is the crowd-sourced product of researchers in the fields of artificial life and evolutionary computation who have provided first-hand accounts of such cases. It thus serves as a written, fact-checked collection of scientifically important and even entertaining stories. In doing so we also present here substantial evidence that the existence and importance of evolutionary surprises extends beyond the natural world, and may indeed be a universal property of all complex evolving systems.

Genetic programming has been successfully applied to several real-world problem domains. One such application area is image classification, wherein genetic programming has been used for a variety of problems such as breast cancer detection, face detection, and pedestrian detection, to name a few. We present the use of genetic programming for detecting active tuberculosis in raw X-ray images. Our results demonstrate that genetic programming evolves classifiers that achieve promising accuracy results compared to that of traditional image classification techniques. Our classifiers do not require pre-processing, segmentation, or feature extraction beforehand. Furthermore, our evolved classifiers process a raw X-ray image and return a classification orders of magnitude faster than the reported times for traditional techniques.

Genetic diversity plays an important role in avoiding premature convergence, which is a phenomenon that stifles the search effectiveness of evolutionary algorithms. However, approaches that avoid premature convergence by maintaining genetic diversity can do so at the cost of efficiency, requiring more fitness evaluations to find high quality solutions. We introduce a simple and efficient genetic diversity technique that is capable of avoiding premature convergence while maintaining a high level of search quality in tree-based genetic programming. Our method finds solutions to a set of benchmark problems in significantly fewer fitness evaluations than the algorithms that we compared against.

Unlike black-box optimization problems, gray-box optimization problems have known, limited, non-linear relationships between variables. Though more restrictive, gray-box problems include many real-world applications in network security, computational biology, VLSI design, and statistical physics. Leveraging these restrictions, the Hamming-Ball Hill Climber (HBHC) can efficiently find high quality local optima. We show how 1) a simple memetic algorithm in conjunction with HBHC can find global optima for some gray-box problems and 2) a gray-box version of the Parameter-less Population Pyramid (P3), utilizing both the HBHC and the known information about variable relationships, outperforms all of the examined algorithms. While HBHC's inclusion into P3 adds a parameter, we show experimentally it can be fixed to 1 without adversely effecting search.

The parameter-less population pyramid (P3) is a recently introduced method for performing evolutionary optimization without requiring any user-specified parameters. P3's primary innovation is to replace the generational model with a pyramid of multiple populations that are iteratively created and expanded. In combination with local search and advanced crossover, P3 scales to problem difficulty, exploiting previously learned information before adding more diversity. Across seven problems, each tested using on average 18 problem sizes, P3 outperformed all five advanced comparison algorithms. This improvement includes requiring fewer evaluations to find the global optimum and better fitness when using the same number of evaluations. Using both algorithm analysis and comparison, we find P3's effectiveness is due to its ability to properly maintain, add, and exploit diversity. Unlike the best comparison algorithms, P3 was able to achieve this quality without any problem-specific tuning. Thus, unlike previous parameter-less methods, P3 does not sacrifice quality for applicability. Therefore we conclude that P3 is an efficient, general, parameter-less approach to black box optimization which is more effective than existing state-of-the-art techniques.

Understanding how search operators interact with solution representation is a critical step to improving search. In Cartesian genetic programming (CGP), and genetic programming (GP) in general, the complex genotype to phenotype map makes achieving this understanding a challenge. By examining aspects such as tuned parameter values, the search quality of CGP variants at different problem difficulties, node behavior, and offspring replacement properties we seek to better understand the characteristics of CGP search. Our focus is two-fold: creating methods to prevent wasted CGP evaluations (skip, accumulate, and single) and creating methods to overcome CGPs search limitations imposed by genome ordering (reorder and DAG). Our results on Boolean problems show that CGP evolves genomes that are highly inactive, very redundant, and full of seemingly useless constants. On some tested problems we found that less than 1% of the genome was actually required to encode the evolved solution. Furthermore, traditional CGP ordering results in large portions of the genome that are never used by any ancestor of the evolved solution. Reorder and DAG allow evolution to utilize the entire genome. More generally, our results suggest that skip-reorder and single-reorder are most likely to solve hard problems using the least number of evaluations and the least amount of time while better avoiding degenerate behavior.

Data centers have become a critical computing infrastructure in the era of cloud computing. Temperature monitoring and forecasting are essential for preventing server shutdowns because of overheating and improving a data center’s energy efficiency. This article presents a novel cyber-physical approach for temperature forecasting in data centers, one that integrates Computational Fluid Dynamics (CFD) modeling, in situ wireless sensing, and real-time data-driven prediction. To ensure forecasting fidelity, we leverage the realistic physical thermodynamic models of CFD to generate transient temperature distribution and calibrate it using sensor feedback. Both simulated temperature distribution and sensor measurements are then used to train a real-time prediction algorithm. As a result, our approach reduces not only the computational complexity of online temperature modeling and prediction, but also the number of deployed sensors, which enables a portable, noninvasive thermal monitoring solution that does not rely on the infrastructure of a monitored data center. We extensively evaluated the proposed system on a rack of 15 servers and a testbed of five racks and 229 servers in a small-scale production data center. Our results show that our system can predict the temperature evolution of servers with highly dynamic workloads at an average error of 0.52○C, within a duration up to 10 minutes. Moreover, our approach can reduce the required number of sensors by 67% while maintaining desirable prediction fidelity.

Real world applications of evolutionary techniques are often hindered by the need to determine problem specific parameter settings. While some previous methods have reduced or removed the need for parameter tuning, many do so by trading efficiency for general applicability. The Parameter-less Population Pyramid (P3) is an evolutionary technique that requires no parameters and is still broadly effective. P3 strikes a balance between continuous integration of diversity and exploitative elitist operators, allowing it to solve easy problems quickly and hard problems eventually. When compared with three optimally tuned, state of the art optimization techniques, P3 always finds the optimum at least a constant factor faster across four benchmarks (Deceptive Trap, Deceptive Step Trap, HIFF, Rastrigin). More importantly, on three randomized benchmarks (NK Landscapes, Ising Spin Glasses, MAX-SAT), P3 has a lower order of computational complexity as measured by evaluations. We also provide outlines for expected runtime analysis of P3, setting the stage for future theory based conclusions. Based on over 1 trillion evaluations, our results suggest P3 has wide applicability to a broad class of problems.

In this paper we examine how Cartesian Genetic Programming's (CGP's) method for encoding directed acyclic graphs (DAGs) and its mutation operator bias the effective length of individuals as well as the distribution of inactive nodes in the genome. We investigate these biases experimentally using two CGP variants as comparisons: Reorder, a method for shuffling node ordering without effecting individual evaluation, and DAG, a method for removing the concept of node position. Experiments were performed on four problems tailored to highlight potential search limitations, with further testing on the 3-bit multiplier problem.

Data centers have become a critical computing infrastructure in the era of cloud computing. Temperature monitoring and forecasting are essential for preventing overheating-induced server shutdowns and improving a data center's energy efficiency. This paper presents a novel cyber-physical approach for temperature forecasting in data centers, which integrates Computational Fluid Dynamics (CFD) modeling, in situ wireless sensing, and real-time data-driven prediction. To ensure the forecasting fidelity, we leverage the realistic physical thermodynamic models of CFD to generate transient temperature distribution and calibrate it using sensor feedback. Both simulated temperature distribution and sensor measurements are then used to train a real-time prediction algorithm. As a result, our approach significantly reduces the computational complexity of online temperature modeling and prediction, which enables a portable, noninvasive thermal monitoring solution that does not rely on the infrastructure of monitored data center. We extensively evaluated our system on a rack of 15 servers and a test bed of five racks and 229 servers in a production data center. Our results show that our system can predict the temperature evolution of servers with highly dynamic workloads at an average error of 0.52C, within a duration up to 10 minutes.

Several approaches have been introduced for modeling and prediction of nonlinear dynamics which have chaotic characteristics. Among these methods, data driven approaches such as Auto Regressive (AR) models, Nonlinear Auto Regressive (NAR) models, Radial Basis Function (RBF) networks, and Multi Layered Perceptron (MLP) neural networks have proven themselves to be powerful approaches in modeling and prediction of chaotic dynamics. However, the structure of these models should be known before the training phase, which is a very complicated problem. In this research, we introduce a co-evolutionary approach for modeling and system identification of chaotic dynamics. The proposed algorithm is composed of two co-evolving populations: candidate data driven models, and test data sets which either extract new information from the nonlinear chaotic system or elicit desirable behavior from it. The fitness of candidate models is their ability to explain behavior of the target chaotic system observed in response to tests carried out so far by predicting the future values of these data sets; the fitness of candidate test data sets is their ability to make the models disagree in their predictions. To check the performance of this algorithm, three case studies are considered. First, we apply this method to approximate a static function which has complicated behavior near zero. Then, we use this algorithm to predict two bench mark time series in chaos literature: Sunspot Number (SSN) and Mackey-Glass (MG) time series. Simulation results depict the power of proposed method in modeling and predicting complicated nonlinear systems.

If you change the CS1 language to Python, what is the impact on the rest of the curriculum? In earlier work we examined the impact of changing CS1 from C++ to Python while leaving CS2 in C++. We found that Python-prepared CS1 students fared no differently in CS2 than students whose CS1 course was in C++, even though CS2 was taught in C++ and covered the same topics as in previous years. Was that an anomaly? What happens in the next tier of courses? When our CS1 was first changed to Python there were many students who had taken CS1 in C++ still in the system. The result is that there is a cadre of students with either CS1 in Python or CS1 in C++ moving together through our curriculum. This one-time occurrence is an opportunity to study the students with many variables fixed. Our next tier of courses is a C-based computer organization course, a C++ based object-oriented software design course, and a data structures course. We found that the students who started with Python fared as well as the CS1 C++ students. As before, the best predictor of performance was their college GPA. Python versus C++ CS1 preparation was not a predictor of performance in any course. We conclude again that in our C++ based curriculum changing CS1 to Python had no negative impact on student performance and did not require any significant change in those subsequent courses.

How suitable is a Python-based CS1 course as preparation for a C++-based CS2 course? After fifteen years of using C++ for both CS1 and CS2, the Computer Science Department at Michigan State University changed the CS1 course to Python. This paper examines the impact of that change on the second course in the sequence, CS2, which kept C++ as its primary language. We report results on a CS2 class which had a mixture of students who had used either C++ or Python from our CS1 course. The CS2 class covered the same topics as previously, though with some changes, and even gave the same final exam as a previous offering. Independent samples t-tests were used to compare students from the Python group with students from the non-Python group on three outcomes: final exam grade, programming projects scores, and final grade for the course. The main result was that there were no significant differences between the groups for all three outcomes. In addition, multiple regression analysis showed that students' past performance (overall GPA) in the University predicted final grades, final exam scores, and programming project scores for the course, but there was no effect of the programming language feature: Python or non-Python. We feel this shows that the Python-based CS1 course prepared students for the C++-based CS2 course as well as the C++-based CS1 course did---while exposing them to a different, powerful and useful language.

This paper presents an algorithm for recommending items using a diverse set of features. The items are recommended by performing a random walk on the k-partite graph constructed from the heterogenous features. To support personalized recommendation, the random walk must be initiated separately for each user, which is computationally demanding given the massive size of the graph. To overcome this problem, we apply multi-way clustering to group together the highly correlated nodes. A recommendation is then made by traversing the subgraph induced by clusters associated with a user's interest. Our experimental results on real data sets demonstrate the efficacy of the proposed algorithm.

Spatial based gene selection for division of chromosomes used by crossover operators is proposed for three-dimensional problems. This spatial selection is shown to preserve more genetic material and reduce the disruptive effects of crossover. The disruptive effects of crossover can be quantified by counting the destruction of subgraphs that represent strong linkages between genes. The spatial operator is compared to simple crossover on a practical class of molecular clustering searches. This comparison shows that the spatial crossover significantly out performs simple crossover. Consistent good performance for spatial crossover is demonstrated on the molecular cluster conformation problem [9].

A genetic algorithm is proposed with real value variables, spatially based crossover operator, a small mutation, large scale mutation, vector sum local search and geometric only based objective function to generate candidate molecule conformations from atomic pair distance data. To better simulate experimental data only information from the pair distance data is used as constraints. Ideal Bucky ball with 60 atoms is used as the test case with both perfect pair distance data and Gaussian noise perturbed pair distance data. The GA generated result shows molecules close to ideal Bucky balls but with some defects. A description of the spatially based crossover operator is provided along with a local search based on vector summed error for each atom.

Clustering ensembles have emerged as a powerful method for improving both the robustness as well as the stability of unsupervised classification solutions. However, finding a consensus clustering from multiple partitions is a difficult problem that can be approached from graph-based, combinatorial, or statistical perspectives. This study extends previous research on clustering ensembles in several respects. First, we introduce a unified representation for multiple clusterings and formulate the corresponding categorical clustering problem. Second, we propose a probabilistic model of consensus using a finite mixture of multinomial distributions in a space of clusterings. A combined partition is found as a solution to the corresponding maximum-likelihood problem using the EM algorithm. Third, we define a new consensus function that is related to the classical intraclass variance criterion using the generalized mutual information definition. Finally, we demonstrate the efficacy of combining partitions generated by weak clustering algorithms that use data projections and random data splits. A simple explanatory model is offered for the behavior of combinations of such weak clustering components. Combination accuracy is analyzed as a function of several parameters that control the power and resolution of component partitions as well as the number of partitions. We also analyze clustering ensembles with incomplete information and the effect of missing cluster labels on the quality of overall consensus. Experimental results demonstrate the effectiveness of the proposed methods on several real-world data sets.

Web-based educational technologies allow educators to study how students learn (descriptive studies) and which learning strategies are most effective (causal/predictive studies). Since web-based educational systems collect vast amounts of student profile data, data mining and knowledge discovery techniques can be applied to find interesting relationships between attributes of students, assessments, and the solution strategies adopted by students. This paper focuses on the discovery of interesting contrast rules, which are sets of conjunctive rules describing interesting characteristics of different segments of a population. In the context of webbased educational sy stems, contrast rules help to identifY attributes characterizing patterns of performance disparity between various groups of students. We propose a general formulation of contrast rules as well as a framework for finding such patterns. We apply this technique to an online educational sy stem developed at Michigan State University called LON-CAP A.

Clustering ensembles have emerged as a powerful method for improving both the robustness and the stability of unsupervised classification solutions. However, finding a consensus clustering from multiple partitions is a difficult problem that can be approached from graph-based, combinatorial or statistical perspectives. We offer a probabilistic model of consensus using a finite mixture of multinomial distributions in a space of clusterings. A combined partition is found as a solution to the corresponding maximum likelihood problem using the EM algorithm. The excellent scalability of this algorithm and comprehensible underlying model are particularly important for clustering of large datasets. This study compares the performance of the EM consensus algorithm with other fusion approaches for clustering ensembles. We also analyze clustering ensembles with incomplete information and the effect of missing cluster labels on the quality of overall consensus. Experimental results demonstrate the effectiveness of the proposed method on large real-world datasets.

A data set can be clustered in many ways depending on the clustering algorithm employed, parameter settings used and other factors. Can multiple clusterings be combined so that the final partitioning of data provides better clustering? The answer depends on the quality of clusterings to be combined as well as the properties of the fusion method. First, we introduce a unified representation for multiple clusterings and formulate the corresponding categorical clustering problem. As a result, we show that the consensus function is related to the classical intra-class variance criterion using the generalized mutual information definition. Second, we show the efficacy of combining partitions generated by weak clustering algorithms that use data projections and random data splits. A simple explanatory model is offered for the behavior of combinations of such weak clustering components. We analyze the combination accuracy as a function of parameters controlling the power and resolution of component partitions as well as the learning dynamics vs. the number of clusterings involved. Finally, some empirical studies compare the effectiveness of several consensus functions.

A key element of bioinformatics research is the extraction of meaningful information from large experimental data sets. Various approaches, including statistical and graph theoretical methods, data mining, and computational pattern recognition, have been applied to this task with varying degrees of success. Using a novel classifier based on the Bayes discriminant function, we present a hybrid algorithm that employs feature selection and extraction to isolate salient features from large medical and other biological data sets. We have previously shown that a genetic algorithm coupled with a k-nearest-neighbors classifier performs well in extracting information about protein-water binding from X-ray crystallographic protein structure data. The effectiveness of the hybrid EC-Bayes classifier is demonstrated to distinguish the features of this data set that are the most statistically relevant and to weight these features appropriately to aid in the prediction of solvation sites.

A key element of bioinformatics research is the extraction of meaningful information from large experimental data sets. Various approaches, including statistical and graph theoretical methods, data mining, and computational pattern recognition, have been applied to this task with varying degrees of success. We have previously shown that a genetic algorithm coupled with a k-nearest-neighbors classifier performs well in extracting information about protein-water binding from X-ray crystallographic protein structure data. Using a novel classifier based on the Bayes discriminant function, we present a hybrid algorithm that employs feature selection and extraction to isolate salient features from large biological data sets. The effectiveness of this algorithm is demonstrated on various biological and medical data sets.

Pattern recognition generally requires that objects be described in terms of a set of measurable features. The selection and quality of the features representing each pattern affect the success of subsequent classification. Feature extraction is the process of deriving new features from original features to reduce the cost of feature measurement, increase classifier efficiency, and allow higher accuracy. Many feature extraction techniques involve linear transformations of the original pattern vectors to new vectors of lower dimensionality. While this is useful for data visualization and classification efficiency, it does not necessarily reduce the number of features to be measured since each new feature may be a linear combination of all of the features in the original pattern vector. Here, we present a new approach to feature extraction in which feature selection and extraction and classifier training are performed simultaneously using a genetic algorithm. The genetic algorithm optimizes a feature weight vector used to scale the individual features in the original pattern vectors. A masking vector is also employed for simultaneous selection of a feature subset. We employ this technique in combination with the k nearest neighbor classification rule, and compare the results with classical feature selection and extraction techniques, including sequential floating forward feature selection, and linear discriminant analysis. We also present results for the identification of favorable water-binding sites on protein surfaces.

This paper presents two approaches that address the problems of the local character of the search and imprecise state representation of reinforcement learning (RL) algorithms for solving combinatorial optimization problems. The first, Bayesian, approach aims to capture solution parameter interdependencies. The second approach combines local information as encoded by typical RL schemes and global information as contained in a population of search agents. The effectiveness of these approaches is demonstrated on the quadratic assignment problem. Competitive results with the RL-agent approach suggest that it can be used as a basis for global optimization techniques.

Evolutionary programming (EP) has historically used a number of approaches for selection of the mutation step size. Current EP implementations typically use self-adaptive meta-parameters for mutation step size selection. However, one of the potential drawbacks of this scheme is that it is not directly responsive to the variance reduction caused by selection. We investigate an alternate method for mutative step size selection that reacts directly to the variance-reducing effects of selection.

Many black box optimization algorithms have sufficient flexibility to allow them to adapt to the varying circumstances they encounter. These capabilities are of two primary sorts: user-determined choices among alternative parameters, operations, and logic structures; and the algorithm-determined alternative paths chosen during the process of seeking a solution to a particular problem. We discuss the process of algorithm design and operation, with the intent of integrating the seemingly distinct aspects described above within a unified framework. We relate this algorithmic optimization process to the field of dynamic process control. An approach is proposed toward the optimization of a process for controlling a specific class of systems, and its application to dynamic adjustment of the algorithm used in the search problem. An instance of this approach in genetic algorithms is demonstrated. The experimental results show the adaptability and robustness of the proposed approach.

A realworld computer vision module must deal with a wide variety of environmental parameters. Object recognition, one of the major tasks of this vision module, typically requires a preprocessing step to locate objects in the scenes that ought to be recognized. Genetic algorithms are a search technique for dealing with a very large search space, such as the one encountered in image segmentation or object recognition. The article describes a technique for using genetic algorithms to combine the image segmentation and object recognition steps for a complex scene. The results show that this approach is a viable method for successfully combining the image segmentation and object recognition steps for a computer vision module.

The concept of the generic task, one of a small set of ubiquitous cognitive tasks that together account for some part of human cognition, is examined. In particular, how hierarchical classification is one such generic task and how it is useful for diagnosis is shown. It is also shown that a diagnosis system based on hierarchical classification naturally lends itself to solving a number of issues traditionally associated with sensor validation is examined.>