Search

Database queries are one of the most important functions of a relational database. Users are interested in viewing a variety of data representations, and this may vary based on database purpose and the nature of the stored data. The Air Force Institute of Technology has approximately 100 data logs which will be converted to the standardized Scorpion Data Model format. A relational database is designed to house this data and its associated sensor and non-sensor metadata. Deterministic polynomial-time queries were used to test the performance of this schema against two other schemas, with databases of 100 and 1000 logs of repeated data and randomized metadata. Of these approaches, the one that had the best performance was chosen as AFIT’s database solution, and now more complex and useful queries need to be developed to enable filter research. To this end, consider the combined Multi-Objective Knapsack/Set Covering Database Query. Algorithms which address The Set Covering Problem or Knapsack Problem could be used individually to achieve useful results, but together they could offer additional power to a potential user. This paper explores the NP-Hard problem domain of the Multi-Objective KP/SCP, proposes Genetic and Hill Climber algorithms, implements these algorithms using Java, populates their data structures using SQL queries from two test databases, and finally compares how these algorithms perform.

Evolutionary algorithms can be applied to a variety of constrained network communication problems with centric type models. This paper shows that with real-world complex network communication problems of this type, sophisticated statistical search is required. This situation occurs due to the fact that these optimization problems are at least NP-complete. In order to appreciate the formal modeling of realistic communication networks, historical network design problems are presented and evolved into more complex real-world models with associated deterministic and stochastic solution approaches discussed. This discussion leads into the design of an innovative multiobjective evolutionary algorithm (MOEA) to solve a very complex network design problem variation called the multicommodity capacitated network design problem (MCNDP). This variation represents a hybrid real-world communication architecture as reflected in real-world network centric models with directional communications, multiple objectives including costs, delays, robustness, vulnerability, and operating reliability within network constraints. Nodes in such centric systems can have multiple and varying link capacities as well as rates and information (commodity) quantities to be sent and received. Each commodity can also have independent prioritized bandwidth and spectrum requirements. The nondominated sorting genetic algorithm (NSGA-II) is selected as the MOEA framework which is modified and parallelized to solve the generic MCNDP. Since the MCNDP is highly constrained but with an enormous number of possible network communication topologies, a novel initialization procedure and mutation method are integrated resulting in reduced search space. Empirical results and analysis indicate that effective topological Pareto solutions are generated for use in highly constrained, communication-based network design.

Developing multiobjective evolutionary algorithms (MOEAs) involves thoroughly addressing the issues of efficiency and effectiveness. Once convinced of an MOEA's effectiveness the researcher often desires to reduce execution time and/or resource expenditure, which naturally leads to considering the MOEA's parallelization. Parallel MOEAs (pMOEAs) or distributed MOEAs are relatively new developments with few associated publications. pMOEA creation is not a simple task, involving analyzing various parallel paradigms and associated parameters. Thus, a thorough discussion of the major parallelized MOEA paradigms is included in this paper and succinct observations are made regarding an analysis of the current literature. Specifically, a previous MOEA notation is extended into the pMOEA domain to enable precise description and identification of various sets of interest. Innovative concepts for pMOEA migration, replacement and niching schemes are discussed, as well as presenting the first known generic pMOEA formulation. Taken together, this paper's analyses in conjunction with an original pMOEA design serve as a pedagogical framework and example of the necessary process to implement an efficient and effective pMOEA.

This paper summarizes the results of a continuing investigation into the evolution of transforms that minimize the error present in satellite images compressed and subsequently reconstructed under conditions subject to quantization error. Using coefficients describing the Daubechies-4 (D4) discrete wavelet transform (DWT) as a starting point, our genetic algorithm (GA) evolves real-valued coefficients describing matched forward and inverse transform pairs that reduce mean squared error (MSE) by 17.9% (0.86 dB) on satellite images used for training, and by an average of more than 11.0% (0.5 dB) on a large test set of satellite images. This result improves upon previous work on satellite images, which evolved only the reconstruction transform, and establishes evolutionary computation as a viable methodology for identifying state-of-the-art solutions to this difficult class of problems.

Modern image processing applications often require robust performance in noisy or bandwidth-limited situations. In this research, we employ genetic algorithms (GAs) to evolve image transforms that reduce quantization error in reconstructed signals and images. The resulting transforms produce higher quality images than current wavelet-based transforms at a given compression ratio and thus allow transmission of compressed data at a lower bandwidth. We evaluate state-of-the-art variation operators for evolving reconstruction filters. Our results indicate that the careful selection of these operators has a strong positive effect upon the evolutionary search for superior image transforms.

We present a new multiobjective evolutionary algorithm (MOEA), called fast Pareto genetic algorithm (FastPGA). FastPGA uses a new fitness assignment and ranking strategy for the simultaneous optimization of multiple objectives where each solution evaluation is computationally- and/or financially-expensive. This is often the case when there are time or resource constraints involved in finding a solution. A population regulation operator is introduced to dynamically adapt the population size as needed up to a user-specified maximum population size. Computational results for a number of well-known test problems indicate that FastPGA is a promising approach. FastPGA outperforms the improved nondominated sorting genetic algorithm (NSGA-II) within a relatively small number of solution evaluations.

Evolutionary algorithms have been applied to a variety of network flow problems with acceptable results. In this research, a multiobjective evolutionary algorithm (MOEA) is used to solve a variation of the multicommodity capacitated network design problem (MCNDP). This variation represents a hybrid communication network as found in network centric models with multiple objectives including costs, delays, robustness, vulnerability, and reliability. Nodes in such centric systems can have multiple and varying link capacities, rates and information (commodity) quantities to be delivered and received. Each commodity can have an independent prioritized bandwidth requirement as well. Insight to the MCNDP problem domain and Pareto structure is developed. The nondominated sorting genetic algorithm (NSGA-II) is modified and extended to solve such a MCNDP. Since the MCNDP is highly constrained, a novel initialization procedure and mutation method are also integrated into this MOEA. Empirical results and analysis indicate that effective solutions are generated very efficiently

Assignment problems are a common area of research in operational research and computer science. Military applications include military personnel assignment, combat radio frequency assignment, and weapon target assignment. In general, assignment problems can be found in a wide array of areas, from modular placement to resource scheduling. Many of these problems are very similar to one another. This paper models and compares some of the assignment problems in literature. These similar problems are then generalized into a generalized multi-objective problem, the constrained assignment problem. Using a multi-objective genetic algorithm, we solve an example of a constrained assignment problem called the airman assignment problem. Results show that good solutions along the interior portion of the Pareto front are found in earlier generations and later generations produce more exterior points.

In the search for a robust and efficient algorithm to be used for computer virus detection, we have developed an artificial immune system genetic algorithm (REALGO) based on the human immune system's use of reverse transcription ribonucleic acid (RNA). The REALGO algorithm provides memory such that during a complex search the algorithm can revert back to and attempt to mutate in a different "direction" in order to escape local minima. In lieu of non-existing virus generic templates, validation is addressed by using an appropriate variety of function optimizations with landscapes believed to be similar to that of virus detection. It is empirically shown that the REALGO algorithm finds "better" solutions than other evolutionary strategies in four out of eight test functions and finds equally "good" solutions in the remaining four optimization problems.

In the multiobjective messy genetic algorithm (MOMGA), the current version, MOMGA-IIa, incorporates efficient processes for obtaining the Pareto front while maintaining a distribution of solutions evaluating to vectors across the Pareto front. Initially described are principle classifiers within explicit building block (BB) multi-objective evolutionary algorithms (MOEAs). Novel design characteristics are addressed as essential elements for making MOMGA-IIa a state-of-the-art explicit BB MOEA. Additionally, a comparison of state-of-the-art explicit BB MOEAs using test suite problems, contemporary quality metrics, extensive testing, and statistical analysis is delivered. Finally, a supplementary historical view of the development of the MOMGA-series MOEA is provided

Genetic Algorithms (GAs) can efficiently produce high quality results for hard combinatorial real world problems such as the Vehicle Routing Problem (VRP). Genetic Vehicle Representation (GVR), a recent approach to solving instances of the VRP with a GA, produces competitive or superior results to the standard benchmark problems. This work extends GVR research by presenting a more precise mathematical model of GVR than in previous works and a thorough comparison of GVR to Path Based Representation approaches. A suite of metrics that measures GVR's efficiency and effectiveness provides an adequate characterization of the jagged search landscape. A new variation of a crossover operator is introduced. A previously unmentioned insight about the convergence rate of the search is also noted that is especially important to the application of a priori and dynamic routing for swarms of Unmanned Aerial Vehicles (UAVs). Results indicate that the search is robust, and it exponentially drives toward high quality solutions in relatively short time. Consequently, a GA with GVR encoding is capable of providing a state-of-the-art engine for a UAV routing system or related application.

Deception problems are among the hardest problems to solve using ordinary genetic algorithms. Recent studies show that Bayesian optimization can help in solving these problems. This work compares the results acquired from the multiobjective fast messy genetic algorithm (MOMGA-II), multiobjective Bayesian optimization algorithm (mBOA), and the nondominated sorting genetic algorithm-II (NSGA-II) when applied to three different deception problems. The three deceptive problems studies are: interleaved minimal deceptive problem, interleaved 5-bit trap function, and the interleaved 6-bit bipolar function. The unmodified MOMGA-II, by design, explicitly learns building block linkages which is required if an algorithm is to solve these hard deception problems. Preliminary results using the MOMGA-II are favorable.

The multi-objective quadratic assignment problem (mQAP) is an non-deterministic polynomial-time complete (NPC) problem with many real-world applications. The application addressed in this paper is the minimization of communication flows in a heterogenous mix of Organic Air Vehicles (OAV). A multi-objective approach to solving the general mQAP for this OAV application is developed. The combinatoric nature of this problem calls for a stochastic search algorithm; moreover, two linkage learning algorithms, the multi-objective fast messy genetic algorithm (MOMGA-II) and MOMGA-IIa, are compared. Twenty-three different problem instances having three different sizes (10, 20, and 30) plus two and three objectives are solved. Results indicate that the MOMGA-IIa resolves all pareto optimal points for problem instances < 20.

Deception problems are among the hardest problems to solve using ordinary genetic algorithms. Designed to simulate a high degree of epistasis, these deception problems imitate extremely difficult real world problems. [1]. Studies show that Bayesian optimization and explicit building block manipulation algorithms, like the fast messy genetic algorithm (fmGA), can help in solving these problems. This paper compares the results acquired from an extended multiobjective fast messy genetic algorithm (MOMGA-IIa), ordinary multiobjective fast messy genetic algorithm (MOMGA-II), multiobjective Bayesian optimization algorithm (mBOA), and the non-dominated sorting genetic algorithm-II (NSGA-II) when applied to three different deception problems. The extended MOMGA-II is enhanced with a new technique exploiting the fmGA's basis function to improve partitioned searching in both the genotype and phenotype domain. The three deceptive problems studied are: interleaved minimal deceptive problem, interleaved 5-bit trap function, and interleaved 6-bit bipolar function. The unmodified MOMGA-II, by design, explicitly learns building block linkages, a requirement if an algorithm is to solve these hard deception problems. Results using the MOMGA-IIa are excellent when compared to the non-explicit building block algorithm results of both the mBOA and NSGA-II.

This research uses an explicit building block based MOEA to solve the multiobjective quadratic assignment problem. We use the multiobjective messy genetic algorithm II (MOMGA-II) to determine what role certain building blocks sizes play in filling up the Pareto front. Additionally, we investigate the role of the competitive template. The algorithm uses the competitive template by propagating it through all the building block sizes and by randomizing it for each building block size. We show that randomized competitive templates produce better results due to more exploration, and larger building block sizes are more common on the outer edges of the Pareto front because they fill more chromosome characteristics in the genotype space.

This research emphasizes explicit building block (BB) based MOEA performance with detailed symbolic representations. An explicit BB-based MOEA for solving constrained and real-world multiple objective problems (MOPs) is developed, the multiobjective messy genetic algorithm II (MOMGA-II) in order to validate symbolic BB concepts. This algorithm provides insight into solving difficult NP-complete MOPs that are generally not realized through the use of implicit BB-based MOEA approaches. Specific constrained integer problem examples include advanced logistics and modified knapsack problems. A primary focus is on generic repair mechanisms for generating feasible solutions per generation. The insight provided is necessary to increase the effectiveness and efficiency over all possible MOEA approaches.

The multiobjective quadratic assignment problem is an NP-complete problem with a multitude of real-world applications. The specific application addressed is the minimization of communication flows in a heterogenous mix of unmanned aerial vehicles. Developed is a multiobjective approach to solving the general mQAP for this UAV application. The combinatoric nature of this problem calls for a stochastic search algorithm; moreover, the multiobjective fast messy genetic algorithm (MOMGA-II) [Jesse Zydallis (2003)] is used for experimentation. Results indicate that much of the Pareto optimal points are found.

Interest in protein structure prediction is widespread, and has been previously addressed using evolutionary algorithms, such as the simple genetic algorithm (GA), messy GA (mga), fast messy GA (fmGA), and linkage learning GA (LLGA). However, past research used off the shelf software such as GENOCOP, GENESIS, and mGA. In this study we report results of a modified fmGA, which is found to be "good" at finding semi-optimal solutions in a reasonable time. Our study focuses on tuning this fmGA in an attempt to improve the effectiveness and efficiency of the algorithm in solving a protein structure and in finding better ways to identify secondary structures. Problem definition, protein model representation, mapping to algorithm domain, tool selection modifications and conducted experiments are discussed.

The Quadratic Assignment Problem (QAP) is an NP-Complete problem [1]. The multiobjective Quadratic Assignment Problem (mQAP) is the multiobjective version of the QAP and was formalized in 2002 [2]. The QAP has had extensive research, but mQAP research is still in its infancy. The mQAP has been been used to optimize communication for formations of heterogenous unmanned aerial vehicles (UAVs) through the use of the Multi-Objective Messy Genetic Algorithm – II (MOMGA-II) [3]. This research extends that research by using a parallelized version of MOMGA-II and comparing the speedup and efficiency of the parallel results to the serial results.

This paper presents two methods designed to improve the efficiency and effectiveness of the parallel fast messy GA used in solving the Protein Structure Prediction (PSP) problem. The first is an application of a farming model - targeting algorithm efficiency. The second successful method addresses the building block sizes used in the algorithm - targeting algorithm effectiveness.

Two different multiobjective genetic algorithms, built using the GENOCOP III system are employed, for the design of wire antenna geometries. Designs are examined using a priori and a posteriori decision criteria. The relative advantages of each of these criteria and their applicability to the problem domain are examined.

Significant work has been conducted in developing techniques for multi-objective problem (MOP) optimizations. This paper investigates the use of a Mendel-like dominance scheme for improving the efficiency of a MOP genetic algorithm. This paper shows, for the selected MOP test suite, that the mendelian GA outperforms a simple GA.

Current signature-based approaches for detecting the presence of hidden messages in digital files - the initial step in steganalysis - rely on discerning "footprints" of steganographic tools. Of greater recent concern is detecting the use of novel proprietary or "home-grown" tools for which no signature has been established. This research focuses on detecting anomalies in seemingly innocuous images, applying a genetic algorithm within a computational immune system to leverage powerful image processing through wavelet analysis. The sensors developed with this new, synergistic system demonstrated a surprising level of capability to detect the use of steganographic tools for which the system had no previous exposure.© (2003) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.

Remediation of groundwater contamination remediation can involve very expensive processes. A recent field evaluation of in situ aerobic cometabolic bioremediation demonstrated that this in situ (meaning "in place") technology has promise as an inexpensive and effective alternative to current technologies for the remediation of trichloroethylene (TCE)-contaminated groundwater. A mathematical fate and transport model has been developed to simulate the relevant physical, chemical, and biological processes that affect TCE fate and transport during the application of in situ bioremediation. In order to cost-effectively implement the technology developers must understand how to adjust engineered parameters in order to optimize system performance. While the fate and transport model can provide system performance information, the complexity of the system and the number of engineered parameters that can be varied make determining an optimal design problematic. Thus, real-valued genetic algorithms are used to determine those design parameter values that attempt to optimize the performance of this complex treatment system. In augmenting the remediation objective function with time-varying penalty weights associated with the model constraints, "acceptable" design parameter values were obtained. By executing the genetic algorithm in parallel using a "farming model" on an efficient parallel computational platform with MPI, we were able to obtain reasonable run times.

Publisher Summary The protein folding problem (PFP) involves the determination of the 3D structures of proteins given only their amino acid sequences. One reason for the significant interest in general and efficient techniques to solve this type of problem is that such knowledge would facilitate understanding of the tremendous amount of genetic information produced by the Human Genome Project. This chapter refers to efforts aimed at identifying in vivo structures of naturally occurring proteins or structures of arbitrary polypeptides in arbitrary environments. In particular, it looks at the general problem of identifying three-dimensional structures of arbitrary polypeptides in arbitrary environments, and focuses on a particular kind of evolutionary algorithm (the messy genetic algorithm) for use on this task. It concentrates on improved effectiveness through the exploitation of domain constraints (i.e., dihedral-angle constraints inspired by the Ramachandran plot) and the exploitation of prior secondary structure analysis. The work described is performed on high-grade parallel and heterogeneous computing resources.

A hybrid genetic algorithm for polypeptide structure prediction is proposed which incorporates efficient gradient-based minimization directly in the fitness evaluation. Fitness is based on a polypeptide specific potential energy model. The algorithm includes a replacement frequency parameter which specifies the probability with which an individual is replaced by its minimized counterpart. Thus, the algorithm can implement either Baldwinian, Lamarckian, or probabilistically Lamarckian evolution. Experiments are described which compare the effectiveness of the genetic algorithm with and without the local minimization operator, and for various probabilities of replacement. The experiments apply the techniques to the minimization of the ECEPP/2 energy model for [Met] Enkephalin. Using fitness proportionate selection, the hybrid approaches obtain better energies (and better basins of attraction) than the standard genetic algorithm, and often find the global minimum. When tournament selection is used, the results are qualitatively similar, except that the hybrid approaches are prone to premature convergence.

A remote monitoring system's performance is measured largely by its associated antennas' efficacy. Improving antenna performance is not a straightforward process, as many (sometimes conflicting) design trade-offs must be considered. An alternative approach specifies the desired antenna properties and then searches for antenna geometries producing those properties. We implement this approach of designing a wire antenna having optimal performance under user-defined adverse conditions by using a genetic algorithm, where the fitness of promising designs is analyzed using the Numerical Electromagnetics Code (NEC) Version 4.1. Two versions of an integrated GA-NEC code are implemented; both produce geometries showing improvements over current designs. Results for both versions are presented, compared and discussed.

To evaluate the performance of a real valued genetic algorithm (GA) exploiting domain knowledge, we systematically evaluate the effect of exogenous parameters using analysis of variance. The GA platform used for this study is Genocop-III, a real valued, co evolutionary algorithm implementation for numerical optimization. We use the protein structure prediction (PSP) problem as our test domain. Nearly all PSP research assumes the native conformation of a protein corresponds to its global minimum free energy state. Thus, our application integrates Genocop-III with our implementation of the CHARMM energy model as the objective function. Results and conclusions drawn from an extensive experiment set using the polypeptide [Met]-Enkephalin are presented from an exogenous parameter selection perspective.

The concepts of efficiency and effectiveness must be addressed in conducting research into using a Evolutionary Algorithm (EA) for optimization problems. The increased use of evolutionary approaches for real-world applications, containing multiple objectives and high dimensionality, has led to the design and generation of a number of Multiobjective Evolutionary Algorithms (MOEA). When analyzing these algorithms, the issues of effectiveness and efficiency are extremely important and typically drive the urge to parallelize these algorithms. The parallelization of MOEAs is a relatively new concept, with few researchers contributing work in this area. This parallelization process is not a simple task and involves the analysis of various parallel models and the parameters associated with these models. This paper presents a thorough analysis of the various parallel MOEA models, the issues associated with these models and recommendations for using these models in MOEAs. In particular, these parallelization concepts are applied to the Multiobjective Messy Genetic Algorithm II.

Popular press and congressional record report a belief by the intelligence community that Al Qaeda members communicate through messages embedded invisibly in images shared via the Internet. This is certainly plausible as steganography has a rich history of military and civilian use. Current signature-based approaches for detecting the presence of hidden messages rely on discerning "footprints" of steganographic tools. Of greater recent concern is detecting the use of novel tools for which no signature has been established. This research addresses this concern by using a method for detecting anomalies in seemingly innocuous images, applying a genetic algorithm within a computational immune system to leverage powerful image processing through wavelet analysis. The sensors developed with this system demonstrated a surprising level of capability to detect the use of steganographic tools for which the system had no previous exposure, including one tool designed to be statistically stealthy.

Selection of run-time parameters is a critical step in the application of genetic algorithms (GAs). Numerous investigations have discussed parameter set selection, both theoretically and empirically. Theoretical work has focused on the choice of population size, while empirical studies cover a wide range of GA parameters. Theory suggests population sizes which increase exponentially with string length. The available experimental data suggests small populations perform consistently well, but the test problems are limited to small string lengths. Thus, we still do not have a complete understanding of how parameters should be chosen, especially for problems with large string lengths. This study extends Schaffer's (1989) results by performing a similar empirical analysis of GA parameters on a real-world application (protein structure prediction), with longer string lengths and a very large number of local optima. Relationships between population size, mutation rates and crossover rates similar to those reported by Schaffer are shown.