Asynchronous evolutionary algorithms (AEAs) accelerate neuroevolution but are affected by evaluation-time bias, where networks that train quickly re-enter the population sooner and disproportionately influence evolutionary outcomes. In this work, we investigate memetic scheduling strategies that dynamically determine how much backpropagation should be done by generated genomes over the course of an asynchronous neuroevolution algorithm to see if this can mitigate evaluation-time bias under a strict 1-hour wall-clock budget per run. We compare constant, randomized, and exponentially scaled memetic backpropagation scheduling strategies across multiple time-series forecasting datasets and target variables. Our experiments find an interesting negative result - while it was expected that increasing the amount of backpropagation over time would allow a search to break out of local minima and mitigate time bias, instead we show that exponentially increasing training schedules consistently underperform. We further show that different forecasting targets find better solutions with different memetic schedules, highlighting the no free lunch nature of the problem. We do, however, find a correlation between average improvement per backpropagation epoch (given a varying constant number of backpropagation epochs) and schedules performing well, which can help guide memetic schedule selection.

Evolutionary Algorithms (EAs) are a flexible and powerful search technique that are frequently applied to a wide variety of problems. Much of their power comes from their ease of parallelization, lending themselves well to a master-worker parallelization scheme. When a synchronous (μ, λ)-style EA is parallelized and genome evaluation time is not constant, worker processors may spend a significant amount of time idle waiting for other genome evaluations to complete. (μ, λ)-style EAs with a steady-state population are frequently employed to avoid this idle time. There is an existing body of work that suggests that, while this does reduce idle processor time, it may not lead to better solutions because of evaluation time bias. In this work, results from a paper that demonstrate this experimentally are fully reproduced from scratch. During this replication, the roles crossover and population initialization play in this bias were uncovered. This is evaluated experimentally and motivates a mitigation strategy, which is compared to other mitigation strategies and is found to perform about as well as other strategies, without modifying anything other than the way the population is initialized. Moreover, a new open source library was developed in order to facilitate these experiments and further investigations.

Evolutionary algorithms have shown substantial progress in recent years, especially in neural architecture search applications, or neuroevolution. Despite their effectiveness, analyzing and understanding the evolutionary paths these algorithms traverse to reach solutions remains challenging. Often these algorithms involve distributed computing strategies, which can include subpopulations or islands, and they explore massive or even unbounded search spaces which can include both weights and architecture, in both continuous and non-continuous domains. Manually examining individual solutions to understand the evolutionary dynamics is often infeasible due to large population sizes, large genome sizes, and high generation counts. This work introduces a new methodology for visualizing neuroevolution population dynamics called genetic distance projections, along with a novel neural network based method for generating these representations. We evaluate this methodology empirically and find it performs better than other traditional methods in generating these representations. We further validate the usefulness of these visualizations using case studies from EXAMM, a long standing neuroevolution algorithm, in which one case study even led to finding and fixing a bug in EXAMM's algorithm.

Out-of-distribution (OOD) detection methods have recently become more prominent, serving as a core element in safety-critical autonomous systems. One major purpose of OOD detection is to reject invalid inputs that could lead to unpredictable errors and compromise safety. Due to the cost of labeled data, recent works have investigated the feasibility of self-supervised learning (SSL) OOD detection, unlabled OOD detection, and zero shot OOD detection. In this work, we identify a set of conditions for a theoretical guarantee of failure in unlabeled OOD detection algorithms from an information-theoretic perspective. These conditions are present in all OOD tasks dealing with real world data: I) we provide theoretical proof of unlabeled OOD detection failure when there exists zero mutual information between the learning objective and the in-distribution labels, a.k.a. ‘label blindness’, II) we define a new OOD task – Adjacent OOD detection – that tests for label blindness and accounts for a previously ignored safety gap in all OOD detection benchmarks, and III) we perform experiments demonstrating that existing unlabeled OOD methods fail under conditions suggested by our label blindness theory and analyze the implications for future research in unlabeled OOD methods.

Parameter prediction is essential for many applications, facilitating insightful interpretation and decision-making. However, in many real life domains, such as power systems, medicine, and engineering, it can be very expensive to acquire ground truth labels for certain datasets as they may require extensive and expensive laboratory testing. In this work, we introduce a semi-supervised learning approach based on topological projections in self-organizing maps (SOMs), which significantly reduces the required number of labeled data points to perform parameter prediction, effectively exploiting information contained in large unlabeled datasets. While few-shot learning has seen significant advances in recent years, the majority of existing approaches focus on classification tasks, making our regression-based method particularly novel for continuous parameter estimation problems. Our proposed method first trains SOMs on unlabeled data followed by only using a minimal number of available labeled data points to assign targets to key best matching units (BMU). The values estimated for newly-encountered data points are computed utilizing the average of the N closest labeled data points in the SOM’s U-matrix in tandem with a topological shortest path distance calculation scheme. The effectiveness of our approach has been validated through practical application in power engineering, specifically for estimating critical coal property values in coal power plants, where traditional laboratory testing is both time-consuming and costly. Our results indicate that the proposed minimally supervised model significantly outperforms traditional regression techniques, including linear and polynomial regression, Gaussian process regression, K-nearest neighbors, as well as deep neural network models and related clustering schemes.

Identifying phases of flight is important in the field of general aviation, as knowing which phase of flight data is collected from aircraft flight data recorders can aid in the more effective detection of safety or hazardous events. General aviation flight data for phase of flight identification is usually per-second data, comes on a large scale, and is class imbalanced. It is expensive to manually label the data and training classification models usually faces class imbalance problems. This work investigates the use of a novel method for minimally supervised self-organizing maps (MS-SOMs) which utilize nearest neighbor majority votes in the SOM U-matrix for class estimation. Results show that the proposed method can reach or exceed a naive SOM approach which utilized a full data file of labeled data, with only 30 labeled datapoints per class. Additionally, the minimally supervised SOM is significantly more robust to the class imbalance of the phase of flight data. These results highlight how little labeled data is required for effective phase of flight identification.

A lifelong learning agent is able to continually learn from potentially infinite streams of pattern sensory data. One major historic difficulty in building agents that adapt in this way is that neural systems struggle to retain previously-acquired knowledge when learning from new samples. This problem is known as catastrophic forgetting (interference) and remains an unsolved problem in the domain of machine learning to this day. While forgetting in the context of feedforward networks has been examined extensively over the decades, far less has been done in the context of alternative architectures such as the venerable self-organizing map (SOM), an unsupervised neural model that is often used in tasks such as clustering and dimensionality reduction. Although the competition among its internal neurons might carry the potential to improve memory retention, we observe that a fixed-sized SOM trained on task incremental data, i.e., it receives data points related to specific classes at certain temporal increments, it experiences severe interference. In this study, we propose the c-SOM, a model that is capable of reducing its own forgetting when processing information.

Predictive maintenance systems have the potential to significantly reduce costs for maintaining aircraft fleets as well as provide improved safety by detecting maintenance issues before they come severe. However, the development of such systems has been limited due to a lack of publicly labeled multivariate time series (MTS) sensor data. MTS classification has advanced greatly over the past decade, but there is a lack of sufficiently challenging benchmarks for new methods. This work introduces the NGAFID Maintenance Classification (NGAFID-MC) dataset as a novel benchmark in terms of difficulty, number of samples, and sequence length. NGAFID-MC consists of over 7,500 labeled flights, representing over 11,500 hours of per second flight data recorder readings of 23 sensor parameters. Using this benchmark, we demonstrate that Recurrent Neural Network (RNN) methods are not well suited for capturing temporally distant relationships and propose a new architecture called Convolutional Multiheaded Self Attention (Conv-MHSA) that achieves greater classification performance at greater computational efficiency. We also demonstrate that image inspired augmentations of cutout, mixup, and cutmix, can be used to reduce overfitting and improve generalization in MTS classification. Our best trained models have been incorporated back into the NGAFID to allow users to potentially detect flights that require maintenance as well as provide feedback to further expand and refine the NGAFID-MC dataset.

Self-adaptive systems frequently use tactics to perform adaptations. Tactic examples include the implementation of additional security measures when an intrusion is detected, or activating a cooling mechanism when temperature thresholds are surpassed. Tactic volatility occurs in real-world systems and is defined as variable behavior in the attributes of a tactic, such as its latency or cost. A system's inability to effectively account for tactic volatility adversely impacts its efficiency and resiliency against the dynamics of real-world environments. To enable systems' efficiency against tactic volatility, we propose a Tactic Volatility Aware (TVA-E) process utilizing evolved Recurrent Neural Networks (eRNN) to provide accurate tactic predictions. TVA-E is also the first known process to take advantage of uncertainty reduction tactics to provide additional information to the decision-making process and reduce uncertainty. TVA-E easily integrates into popular adaptation processes enabling it to immediately benefit a large number of existing self-adaptive systems. Simulations using 52,106 tactic records demonstrate that: I) eRNN is an effective prediction mechanism, II) TVA-E represents an improvement over existing state-of-the-art processes in accounting for tactic volatility, and III) Uncertainty reduction tactics are beneficial in accounting for tactic volatility. The developed dataset and tool can be found at https://tacticvolatility.github.io/

Event identification in technical logbooks poses challenges given the limited logbook data available in specific technical domains, the large set of possible classes, and logbook entries typically being in short form and non-standard technical language. Technical logbook data typically has both a domain, the field it comes from (e.g., automotive), and an application, what it is used for (e.g., maintenance). In order to better handle the problem of data scarcity, using a variety of technical logbook datasets, this paper investigates the benefits of using transfer learning from sources within the same domain (but different applications), from within the same application (but different domains) and from all available data. Results show that performing transfer learning within a domain provides statistically significant improvements, and in all cases but one the best performance. Interestingly, transfer learning from within the application or across the global dataset degrades results in all cases but one, which benefited from adding as much data as possible. A further analysis of the dataset similarities shows that the datasets with higher similarity scores performed better in transfer learning tasks, suggesting that this can be utilized to determine the effectiveness of adding a dataset in a transfer learning task for technical logbooks.

Farhad Akhbardeh, Cecilia Ovesdotter Alm, Marcos Zampieri, Travis Desell. Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2021.

Transfer learning entails taking an artificial neural network (ANN) that is trained on a source dataset and adapting it to a new target dataset. While this has been shown to be quite powerful, its use has generally been restricted by architectural constraints. Previously, in order to reuse and adapt an ANN's internal weights and structure, the underlying topology of the ANN being transferred across tasks must remain mostly the same while a new output layer is attached, discarding the old output layer's weights. This work introduces network-aware adaptive structure transfer learning (N-ASTL), an advancement over prior efforts to remove this restriction. N-ASTL utilizes statistical information related to the source network's topology and weight distribution in order to inform how new input and output neurons are to be integrated into the existing structure. Results show improvements over prior state-of-the-art, including the ability to transfer in challenging real-world datasets not previously possible and improved generalization over RNNs without transfer.

This paper presents a new algorithm, Evolutionary eXploration of Augmenting Memory Models (EXAMM), which is capable of evolving recurrent neural networks (RNNs) using a wide variety of memory structures, such as Δ-RNN, GRU, LSTM, MGU and UGRNN cells. EXAMM evolved RNNs to perform prediction of large-scale, real world time series data from the aviation and power industries. These data sets consist of very long time series (thousands of readings), each with a large number of potentially correlated and dependent parameters. Four different parameters were selected for prediction and EXAMM runs were performed using each memory cell type alone, each cell type and simple neurons, and with all possible memory cell types and simple neurons. Evolved RNN performance was measured using repeated k-fold cross validation, resulting in 2420 EXAMM runs which evolved 4, 840, 000 RNNs in ~24,200 CPU hours on a high performance computing cluster. Generalization of the evolved RNNs was examined statistically, providing findings that can help refine the design of RNN memory cells as well as inform future neuro-evolution algorithms.

When self-adaptive systems encounter changes withintheir surrounding environments, they enacttacticsto performnecessary adaptations. For example, a self-adaptive cloud-basedsystem may have a tactic that initiates additional computingresources when response time thresholds are surpassed, or theremay be a tactic to activate a specific security measure when anintrusion is detected. In real-world environments, these tacticsfrequently experiencetactic volatilitywhich is variable behaviorduring the execution of the tactic.Unfortunately, current self-adaptive approaches do not accountfor tactic volatility in their decision-making processes, and merelyassume that tactics do not experience volatility. This limitationcreates uncertainty in the decision-making process and mayadversely impact the system's ability to effectively and efficientlyadapt. Additionally, many processes do not properly account forvolatility that may effect the system's Service Level Agreement(SLA). This can limit the system's ability to act proactively, especially when utilizing tactics that contain latency.To address the challenge of sufficiently accounting for tacticvolatility, we propose aTactic Volatility Aware(TVA) solution.Using Multiple Regression Analysis (MRA), TVA enables self-adaptive systems to accurately estimate the cost and timerequired to execute tactics. TVA also utilizesAutoregressiveIntegrated Moving Average(ARIMA) for time series forecasting, allowing the system to proactively maintain specifications.

This work examines the use of ant colony optimization (ACO) to improve long short-term memory (LSTM) recurrent neural networks (RNNs) by refining their cellular structure. The evolved networks were trained on a large database of flight data records obtained from an airline containing flights that suffered from excessive vibration. Results were obtained using MPI (Message Passing Interface) on a high performance computing (HPC) cluster, which evolved 1000 different LSTM cell structures using 208 cores over 5 days. The new evolved LSTM cells showed an improvement in prediction accuracy of 1.37%, reducing the mean prediction error from 6.38% to 5.01% when predicting excessive engine vibrations 10 seconds in the future, while at the same time dramatically reducing the number of trainable weights from 21,170 to 11,650. The ACO optimized LSTM also performed significantly better than traditional Nonlinear Output Error (NOE), Nonlinear AutoRegression with eXogenous (NARX) inputs, and Nonlinear Box-Jenkins (NBJ) models, which only reached error rates of 11.45%, 8.47% and 9.77%, respectively. The ACO algorithm employed could be utilized to optimize LSTM RNNs for any time series data prediction task.

Automated object detection within imagery is challenging in the field of wildlife biology. Uncontrolled conditions, along with the relative size of target species to the more abundant background makes manual detection tedious and error-prone. In order to address these concerns, the Wildlife@Home project has been developed with a web portal to allow citizen scientists to inspect and catalog these images, which in turn provides training data for computer vision algorithms to automate the detection process. This work focuses on a project with over 65,000 Unmanned Aerial System (UAS) images from flights in the Hudson Bay area of Canada gathered in the years 2015 and 2016. This data set comprises over 3TB of raw imagery and also contains a further 2 million images from related ecological projects. Given the data scale, the person-hours that would be needed to manually inspect the data is extremely high. This work examines the efficacy of using citizen science data as inputs to convolutional neural networks (CNNs) used for object detection. Three CNNs were trained with expert observations, citizen scientist observations, and matched observations made by pairing citizen scientist observations of the same object and taking the intersection of the two observations. The expert, matched, and unmatched CNNs overestimated the number of lesser snow geese in the testing images by 88%, 150%, and 250%, respectively, which is less than current work using similar techniques on all visible (RGB) UAS imagery. These results show that the accuracy of the input data is more important than the quantity of the input data, as the unmatched citizen scientists observations are shown to be highly variable, but substantial in number, while the matched observations are much closer to the expert observations, though less in number. To increase the accuracy of the CNNs, it is proposed to use a feedback loop to ensure the CNN gets continually trained using extracted observations that it did poorly on during the testing phase.

This work presents improvements to a neuroevolution algorithm called Evolutionary eXploration of Augmenting Convolutional Topologies (EXACT), which is capable of evolving the structure of convolutional neural networks (CNNs). While EXACT has multithreaded and parallel implementations, it has also been implemented as part of a volunteer computing project at the Citizen Science Grid to provide truly large scale computing resources through over 5,500 volunteered computers. Improvements include the development of a new mutation operator, which increased the evolution rate by over an order of magnitude and was also shown to be significantly more reliable in generating new CNNs than the traditional method. Further, EXACT has been extended with a simplex hyperparameter optimization (SHO) method which allows for the co-evolution of hyperparameters, simplifying the task of their selection while generating smaller CNNs with similar predictive ability to those generated with fixed hyperparameters. Lastly, the backpropagation method has been updated with batch normalization and dropout. Compared to previous work, which only achieved prediction rates of 98.32% on the MNIST handwritten digits testing data after 60,000 evolved CNNs, these new advances allowed EXACT to achieve prediction rates of 99.43% within only 12,500 evolved CNNs - rates which are comparable to some of the best human designed CNNs.

This paper explores the use of Convolutional Neural Networks (CNNs) to detect Interior Least Tern in uncontrolled outdoor videos for the Wildlife@Home project. To be able to use CNNs on this video, this work developed strategies to bridge the gap between video collected by wildlife biologists and the methodlogies common for training and testing CNNs by utilizing a striding methodology to extract positive and negative training examples of a fixed size. Then in order to efficiently run trained CNNs over full videos, software was developed using OpenCL which was capable of utilizing multiple GPUs and other OpenCL capable compute devices concurrently. It was also shown that an already trained CNN can be further refined by training it further on new imagery, without having to retrain the whole network from scratch, saving significant time. Further, while the CNNs trained were only for detection of Interior Least Terns, they show promise for actually detecting behavior, as obvious peaks resulted for periods of video when a tern was in flight. To the authors' knowledge, this is the first attempt to utilize CNNs for the task of detecting wildlife in uncontrolled outdoor video.

This paper examines building viable Recurrent Neural Networks (RNN) using Long Short Term Memory (LSTM) neurons to predict aircraft engine vibrations. The model is trained on a large database of flight data records obtained from an airline containing flights that suffered from excessive vibration. RNNs can provide a more generalizable and robust method for prediction over analytical calculations of engine vibration, as analytical calculations must be solved iteratively based on specific empirical engine parameters, and this database contains multiple types of engines. Further, LSTM RNNs provide a “memory” of the contribution of previous time series data which can further improve predictions of future vibration values. LSTM RNNs were used over traditional RNNs, as those suffer from vanishing/exploding gradients when trained with back propagation. The study managed to predict vibration values for 5, 10 and 20 seconds in the future, with 3.3%, 5.51% and 10.19% mean absolute error, respectively. These neural networks provide a promising means for the future development of warning systems so that suitable actions can be taken before the occurrence of excess vibration to avoid unfavorable situations during flight.

Image recognition is challenging in the field of wildlife ecology as samples of a specific species can be rare, making manual detection cumbersome. With over 2,060,000 images taken from motion-sensor trail cameras and unmanned aerial vehicle flights, a touch enabled web interface has been developed to allow citizen scientists and ecologists to categorize positive samples. To minimize categorization errors, the same images are shown to multiple separate users. The observations of each user are then compared using two novel validation strategies: percentage of overlapping area and maximum corner distance. Two novel methods for the extraction of final images from validated results are presented and compared as well: average corner points and area intersection. These methods were evaluated using a set of 142 images with a total of 811 observations of objects generated by citizen scientists that were manually inspected for ground truth. Results show that for this research a maximum corner distance of 10 pixels and the use of area intersection provided the best extracted imagery for future use as training and testing data by computer vision methods.

This paper examines the use of three different background subtraction algorithms -- Mixture of Gaussians (MOG), Visual Background Extractor (ViBe), and Pixel-Based Adaptive Segmentation (PBAS) -- to detect events of interest within uncontrolled outdoor avian nesting video for the Wildlife@Home project. Many computer vision techniques are unsuccessful in this domain due to low frame-rates and resolution of battery powered surveillance cameras in combination with the cryptic coloration (camouflage) of the animals. Modifications to ViBe and PBAS are presented which provide more robust results in this challenging video, and address issues caused by the cryptic coloration of the species being monitored by the project. These algorithms were run on over 250 hours of video and compared to human observations generated by Wildlife@Home's project scientists and volunteer citizen scientists. All three algorithms provide accurate detection of events however we see much fewer false postives from the modified versions of the ViBe and PBAS algorithms. This is especially true for Interior Least Tern (Sternula antillarum) and Piping Plover (Charadrius melodus) video, which do not suffer from as much moving vegetation as the Sharp-Tailed Grouse (Tympanuchus phasianellus) footage. These results provide initial justification for utilizing Wildlife@Home's 2,000+ volunteered computers to analyze the project's 85,000 hours of avian nesting video, so that this information can be integrated into the Wildlife@Home user interface. Further, the videos and human observations used to test these algorithms have been made available as part of Wildlife@Home's first data release, to encourage future study by computer vision researchers.

DNA@Home is a volunteer computing project that aims to use Gibbs Sampling for the identification and location of DNA control signals on full genome-scale datasets. A fault tolerant and asynchronous implementation of Gibbs sampling using the Berkeley Open Infrastructure for Network Computing (BOINC) was used to identify the location of binding sites of the SNAI1 (Snail) and SNAI2 (Slug) transcription factors across the human genome. Genes regulated by Slug but not Snail, and genes regulated by Snail but not Slug provided two datasets with known motifs. These datasets contained up to 994 DNA sequences which to our knowledge is largest scale use of Gibbs sampling for discovery of binding sites. 1000 parallel sampling walks were used to search for the presence of 1, 2 or 3 possible motifs using small, medium, and full size sets of these sequences. These runs were performed over a period of two months using over 1500 volunteered computing hosts and generated over 2.2 Terabytes of sampling data. High performance computing resources were used for post processing. This paper presents intra and inter walk analyses used to determine walk convergence. The results were validated against current biological knowledge of the Snail and Slug promoter regions and present avenues for further biological study.

New camera technology is allowing avian ecologists to perform detailed studies of avian behavior, nesting strategies and predation in areas where it was previously impossible to gather data. Unfortunately, studies have shown mechanical triggers and a variety of sensors to be inadequate in capturing footage of small predators (e.g., snakes, rodents) or events in dense vegetation. Because of this, continuous camera recording is currently the most robust solution for avian monitoring, especially in ground nesting species. However, continuous video footage results in a data deluge, as monitoring enough nests to make biologically significant inferences results in massive amounts of data which is unclassifiable by humans alone. In the summer of 2012, Dr. Ellis-Felege gathered video footage from 63 sharp-tailed grouse (Tympanuchus phasianellus) nests, as well as preliminary interior least tern (Sternula antillarum) and piping plover (Charadrius melodus) nests, resulting in over 20,000 hours of video footage. In order to effectively analyze this video, a project combining both crowd sourcing and volunteer computing was developed, where volunteers can stream nesting video and report their observations, as well as have their computers download video for analysis by computer vision techniques. This provides a robust way to analyze the video, as user observations are validated by multiple views as well as the results of the computer vision techniques. This work provides initial results analyzing the effectiveness of the crowd sourced observations and computer vision techniques.

Using passwords to verify a user's identity is the most widely deployed method for electronic authentication. When system administrators need to recover lost passwords or test accounts for easily guessable passwords, it can require millions of hash function and string comparison operations. These operations can be computationally expensive but are easily parallelizable because each password can be tested independently. Therefore, using high performance computing (HPC) can greatly reduce the time required to perform password recovery. Due to the high level of fine-grained parallelism of this type of problem, GPU computing using Compute Unified Device Architecture (CUDA) can be used to further improve performance. The scale of HPC can be further increased through the use of multiple GPUs, but this requires communication between the GPU devices and can reduce the overall performance due to increased communications latency. In this work a well established HPC framework, Message Passing Interface (MPI), was used to minimize the amount of latency and handle the communication between the devices. This allowed for a course-grained division of the problem using MPI where each device applies a fine-grained division of the problem using CUDA to perform the actual calculations. This paper describes three dictionary-based password recovery algorithms that use both MPI and CUDA. In this approach the hashed values of known words are computed and compared with hash values of unknown user passwords. The algorithms differed in GPU memory utilization and how the data was divided and distributed among the MPI nodes and GPU devices. A divided dictionary algorithm split the dictionary of potential passwords over the G PUs and copied the password database to each GPU. A divided password database algorithm split the password database and copied the potential passwords. A minimal memory algorithm split the password database and sequentially processed individual passwords on the GPUs. The divided dictionary and the divided password database algorithms performed well, resulting in a speedup of 57x and 40x over a single processor using 8 GPUs across 4 compute nodes, respectively. Illustrating the cost of communication latency between MPI nodes and GPUs, the minimal memory algorithm performed significantly slower than a single CPU. The algorithms are shown to scale well to multiple GPUs, so this password recovery system could be used for much larger systems for larger databases. In addition to recovering lost passwords, this work could be used to help improve the security of computer systems by identifying accounts with weak or common passwords. The framework described may also be useful for other research that needs to process large amounts of data with similar characteristics using MPI and CUDA.

Computational science is placing new demands on optimization algorithms as the size of data sets and the computational complexity of scientific models continue to increase. As these complex models have many local minima, evolutionary algorithms (EAs) are very useful for quickly finding optimal solutions in these challenging search spaces. In addition to the complex search spaces involved, calculating the objective function can be extremely demanding computationally. Because of this, distributed computation is a necessity. In order to address these computational demands, top-end distributed computing systems are surpassing hundreds of thousands of computing hosts; and as in the case of Internet based volunteer computing systems, they can also be highly heterogeneous and faulty. This work examines asynchronous strategies for distributed EAs using simulated computing environments. Results show that asynchronous EAs can scale to hundreds of thousands of computing hosts while being highly resilient to heterogeneous and faulty computing environments, something not possible for traditional distributed EAs which require synchronization. While the simulation not only provides insight as to how asynchronous EAs perform on distributed computing environments with different latencies and heterogeneity, it also serves as a sanity check because live distributed systems require problems with high computation to communication ratios and traditional benchmark problems cannot be used for meaningful analysis due to their short computation times.

Volunteer computing grids offer significant computing power at relatively low cost to researchers, while at the same time generating public interest in different scientific projects. However, in order to be used effectively, their heterogeneity, volatility and restrictive computing models must be overcome. As these computing grids are open, incorrect or malicious results must also be handled. This paper examines extending the BOINC volunteer computing framework to allow for asynchronous global optimization as applied to scientific computing problems. The asynchronous optimization method used is resilient to faults and the heterogeneous nature of volunteer computing grids, while allowing scalability to tens of thousands of hosts. A work verification strategy that does not require the validation of every result is presented. This is shown to be able to effectively reduce the need for verification done to less than 30% of the reported results, without degrading the performance of the asynchronous search methods. An asynchronous version of particle swarm optimization (APSO) is presented and com- pared to previously used asynchronous genetic search (AGS) using the MilkyWay@Home BOINC computing project. Both search methods are shown to scale to MilkyWay@Home's current user base, over 75,000 heterogeneous and volatile hosts, something not possible for traditional optimization methods. APSO is shown to provide faster convergence to optimal results while being less sensitive to its search parameters. The verification strategy presented is shown to be effective for both AGS and APSO.

Abstract Malleability enables a parallel application's execution system to split or merge processes modifying granularity. While process migration is widely used to adapt applications to dynamic execution environments, it is limited by the granularity of the application's processes. Malleability empowers process migration by allowing the application's processes to expand or shrink following the availability of resources. We have implemented malleability as an extension to the process checkpointing and migration (PCM) library, a user‐level library for iterative message passing interface (MPI) applications. PCM is integrated with the Internet Operating System, a framework for middleware‐driven dynamic application reconfiguration. Our approach requires minimal code modifications and enables transparent middleware‐triggered reconfiguration. Experimental results using a two‐dimensional data parallel program that has a regular communication structure demonstrate the usefulness of malleability. Copyright © 2008 John Wiley & Sons, Ltd.

This paper examines the use of a probabilistic simplex operator for asynchronous genetic search on the BOINC volunteer computing framework. This algorithm is used to optimize a computationally intensive function with a continuous parameter space: finding the optimal fit of an astronomical model of the Milky Way galaxy to observed stars. The asynchronous search using a BOINC community of over 1,000 users is shown to be comparable to a synchronous continuously updated genetic search on a 1,024 processor partition of an IBM BlueGene/L supercomputer. The probabilistic simplex operator is also shown to be highly effective and the results demonstrate that increasing the parents used to generate offspring improves the convergence rate of the search. Additionally, it is shown that there is potential for improvement by refining the range of the probabilistic operator, adding more parents, and generating offspring differently for volunteered computers based on their typical speed in reporting results. The results provide a compelling argument for the use of asynchronous genetic search and volunteer computing environments, such as BOINC, for computationally intensive optimization problems and, therefore, this work opens up interesting areas of future research into asynchronous optimization methods.

Use of large-scale heterogeneous computing environments such as computational grids and the Internet has become of high interest to scientific researchers. This is because the increasing complexity of their scientific models and data sets is drastically outpacing the increases in processor speed while the cost of supercomputing environments remains relatively high. However, the heterogeneity and unreliability of these environments, especially the Internet, make scalable and fault tolerant search methods indispensable to effective scientific model verification. The paper introduces two versions of asynchronous master-worker genetic search and evaluates their convergence and performance rates in comparison to traditional synchronous genetic search on both a IBM BlueGene supercomputer and using the MilkyWay@HOME BOINC Internet computing project1. The asynchronous searches not only perform faster on heterogeneous grid environments as compared to synchronous search, but also achieve better convergence rates for the astronomy model used as the driving application, providing a strong argument for their use on grid computing environments and by the Milky Way@Home BOINC Internet computing project.

Malleability enables a parallel application's execution system to split or merge processes modifying granularity. While process migration is widely used to adapt applications to dynamic execution environments, it is limited by the granularity of the application's processes. Malleability empowers process migration by allowing the application's processes to expand or shrink following the availability of resources. We have implemented malleability as an extension to the PCM (process checkpointing and migration) library, a user-level library for iterative MPI applications. PCM is integrated with the Internet operating system (IOS), a framework for middleware-driven dynamic application reconfiguration. Our approach requires minimal code modifications and enables transparent middleware- triggered reconfiguration. Experimental results using a two-dimensional data parallel program that has a regular communication structure demonstrate the usefulness of malleability.

This paper presents GMLE1, a generic and distributed framework for maximum likelihood evaluation. GMLE is currently being applied to astroinformatics for determining the shape of star streams in the Milky Way galaxy, and to particle physics in a search for theory-predicted but yet unobserved sub-atomic particles. GMLE is designed to enable parallel and distributed executions on platforms ranging from supercomputers and high-performance homogeneous computing clusters to more heterogeneous Grid and Internet computing environments. GMLE's modular implementation seperates concerns of developers into the distributed evaluation frameworks, scientific models, and search methods, which interact through a simple API. This allows us to compare the benefits and drawbacks of different scientific models using different search methods on different computing environments. We describe and compare the performance of two implementations of the GMLE framework: an MPI version that more effectively uses homogeneous environments such as IBM's BlueGene, and a SALSA version that more easily accommodates heterogeneous environments such as the Rensselaer Grid. We have shown GMLE to scale well in terms of computation as well as communication over a wide range of environments. We expect that scientific computing frameworks, such as GMLE, will help bridge the gap between scientists needing to analyze ever larger amounts of data and ever more complex distributed computing environments.