Genetic Algorithm Approach for Solving the Task Assignment Problem

This research was partially supported by the Serbian Ministry of Science and Ecology under project 144007. The authors are grateful to Ivana Ljubić for help in testing and to Vladimir Filipović for useful suggestions and comments.

DNA Simulation of Genetic Algorithms: Fitness Computation

* This work has been partially supported by Spanish Project TIC2003-9319-c03-03 “Neural Networks and Networks of Evolutionary Processors”.

Evolutionary Clustering of Complex Systems and Processes

In a paper the method of complex systems and processes clustering based use of genetic algorithm is offered. The aspects of its realization and shaping of fitness-function are considered. The solution of clustering task of Ukraine areas on socio-economic indexes is represented and comparative analysis with outcomes of classical methods is realized.

Online Genetic Algorithms

This paper present a technique based on genetic algorithms for generating online adaptive services. Online adaptive systems provide flexible services to a mass of clients/users for maximising some system goals, they dynamically adapt the form and the content of the issued services while the population of clients evolve over time. The idea of online genetic algorithms (online GAs) is to use the online clients response behaviour as a fitness function in order to produce the next generation of services. The principle implemented in online GAs, “the application environment is the fitness”, allow modelling highly evolutionary domains where both services providers and clients change and evolve over time. The flexibility and the adaptive behaviour of this approach seems to be very relevant and promising for applications characterised by highly dynamical features such as in the web domain (online newspapers, e- markets, websites and advertising engines). Nevertheless the proposed technique has a more general aim for application environments characterised by a massive number of anonymous clients/users which require personalised services, such as in the case of many new IT applications.

On Solving the Maximum Betweenness Problem Using Genetic Algorithms

In this paper a genetic algorithm (GA) is applied on Maximum Betweennes Problem (MBP). The maximum of the objective function is obtained by finding a permutation which satisfies a maximal number of betweenness constraints. Every permutation considered is genetically coded with an integer representation. Standard operators are used in the GA. Instances in the experimental results are randomly generated. For smaller dimensions, optimal solutions of MBP are obtained by total enumeration. For those instances, the GA reached all optimal solutions except one. The GA also obtained results for larger instances of up to 50 elements and 1000 triples. The running time of execution and finding optimal results is quite short.

Optimization of pavement maintenance and rehabilitation programming using shuffled complex evolution algorithm

The major barrier to practical optimization of pavement preservation programming has always been that for formulations where the identity of individual projects is preserved, the solution space grows exponentially with the problem size to an extent where it can become unmanageable by the traditional analytical optimization techniques within reasonable limit. This has been attributed to the problem of combinatorial explosion that is, exponential growth of the number of combinations. The relatively large number of constraints often presents in a real-life pavement preservation programming problems and the trade-off considerations required between preventive maintenance, rehabilitation and reconstruction, present yet another factor that contributes to the solution complexity. In this research study, a new integrated multi-year optimization procedure was developed to solve network level pavement preservation programming problems, through cost-effectiveness based evolutionary programming analysis, using the Shuffled Complex Evolution (SCE) algorithm.^ A case study problem was analyzed to illustrate the robustness and consistency of the SCE technique in solving network level pavement preservation problems. The output from this program is a list of maintenance and rehabilitation treatment (M&R) strategies for each identified segment of the network in each programming year, and the impact on the overall performance of the network, in terms of the performance levels of the recommended optimal M&R strategy. ^ The results show that the SCE is very efficient and consistent in the simultaneous consideration of the trade-off between various pavement preservation strategies, while preserving the identity of the individual network segments. The flexibility of the technique is also demonstrated, in the sense that, by suitably coding the problem parameters, it can be used to solve several forms of pavement management programming problems. It is recommended that for large networks, some sort of decomposition technique should be applied to aggregate sections, which exhibit similar performance characteristics into links, such that whatever M&R alternative is recommended for a link can be applied to all the sections connected to it. In this way the problem size, and hence the solution time, can be greatly reduced to a more manageable solution space. ^ The study concludes that the robust search characteristics of SCE are well suited for solving the combinatorial problems in long-term network level pavement M&R programming and provides a rich area for future research. ^

Customization of the design of antenna using genetic algorithm and finite-difference time-domain technique

Antenna design is an iterative process in which structures are analyzed and changed to comply with certain performance parameters required. The classic approach starts with analyzing a "known" structure, obtaining the value of its performance parameter and changing this structure until the "target" value is achieved. This process relies on having an initial structure, which follows some known or "intuitive" patterns already familiar to the designer. The purpose of this research was to develop a method of designing UWB antennas. What is new in this proposal is that the design process is reversed: the designer will start with the target performance parameter and obtain a structure as the result of the design process. This method provided a new way to replicate and optimize existing performance parameters. The base of the method was the use of a Genetic Algorithm (GA) adapted to the format of the chromosome that will be evaluated by the Electromagnetic (EM) solver. For the electromagnetic study we used XFDTD™ program, based in the Finite-Difference Time-Domain technique. The programming portion of the method was created under the MatLab environment, which serves as the interface for converting chromosomes, file formats and transferring of data between the XFDTD™ and GA. A high level of customization had to be written into the code to work with the specific files generated by the XFDTD™ program. Two types of cost functions were evaluated; the first one seeking broadband performance within the UWB band, and the second one searching for curve replication of a reference geometry. The performance of the method was evaluated considering the speed provided by the computer resources used. Balance between accuracy, data file size and speed of execution was achieved by defining parameters in the GA code as well as changing the internal parameters of the XFDTD™ projects. The results showed that the GA produced geometries that were analyzed by the XFDTD™ program and changed following the search criteria until reaching the target value of the cost function. Results also showed how the parameters can change the search criteria and influence the running of the code to provide a variety of geometries.

Genetic algorithms and investment strategies: A global perspective

The profitability of momentum portfolios in the equity markets is derived from the continuation of stock returns over medium time horizons. The empirical evidence of momentum, however, is significantly different across markets around the world. The purpose of this dissertation is to: (1) help global investors determine the optimal selection and holding periods for momentum portfolios, (2) evaluate the profitability of the optimized momentum portfolios in different time periods and market states, (3) assess the investment strategy profits after considering transaction costs, and (4) interpret momentum returns within the framework of prior studies on investors’ behavior. Improving on the traditional practice of selecting arbitrary selection and holding periods, a genetic algorithm (GA) is employed. The GA performs a thorough and structured search to capture the return continuations and reversals patterns of momentum portfolios. Three portfolio formation methods are used: price momentum, earnings momentum, and earnings and price momentum and a non-linear optimization procedure (GA). The focus is on common equity of the U.S. and a select number of countries, including Australia, France, Germany, Japan, the Netherlands, Sweden, Switzerland and the United Kingdom. The findings suggest that the evolutionary algorithm increases the annualized profits of the U.S. momentum portfolios. However, the difference in mean returns is statistically significant only in certain cases. In addition, after considering transaction costs, both price and earnings and price momentum portfolios do not appear to generate abnormal returns. Positive risk-adjusted returns net of trading costs are documented solely during “up” markets for a portfolio long in prior winners only. The results on the international momentum effects indicate that the GA improves the momentum returns by 2 to 5% on an annual basis. In addition, the relation between momentum returns and exchange rate appreciation/depreciation is examined. The currency appreciation does not appear to influence significantly momentum profits. Further, the influence of the market state on momentum returns is not uniform across the countries considered. The implications of the above findings are discussed with a focus on the practical aspects of momentum investing, both in the U.S. and globally.

Serial evolutionary networks of within-patient HIV-1 sequences reveal patterns of evolution of X4 strains

Background The HIV virus is known for its ability to exploit numerous genetic and evolutionary mechanisms to ensure its proliferation, among them, high replication, mutation and recombination rates. Sliding MinPD, a recently introduced computational method [1], was used to investigate the patterns of evolution of serially-sampled HIV-1 sequence data from eight patients with a special focus on the emergence of X4 strains. Unlike other phylogenetic methods, Sliding MinPD combines distance-based inference with a nonparametric bootstrap procedure and automated recombination detection to reconstruct the evolutionary history of longitudinal sequence data. We present serial evolutionary networks as a longitudinal representation of the mutational pathways of a viral population in a within-host environment. The longitudinal representation of the evolutionary networks was complemented with charts of clinical markers to facilitate correlation analysis between pertinent clinical information and the evolutionary relationships. Results Analysis based on the predicted networks suggests the following:: significantly stronger recombination signals (p = 0.003) for the inferred ancestors of the X4 strains, recombination events between different lineages and recombination events between putative reservoir virus and those from a later population, an early star-like topology observed for four of the patients who died of AIDS. A significantly higher number of recombinants were predicted at sampling points that corresponded to peaks in the viral load levels (p = 0.0042). Conclusion Our results indicate that serial evolutionary networks of HIV sequences enable systematic statistical analysis of the implicit relations embedded in the topology of the structure and can greatly facilitate identification of patterns of evolution that can lead to specific hypotheses and new insights. The conclusions of applying our method to empirical HIV data support the conventional wisdom of the new generation HIV treatments, that in order to keep the virus in check, viral loads need to be suppressed to almost undetectable levels.

Genetic Algorithms and Investment Strategies: A Global Perspective

The profitability of momentum portfolios in the equity markets is derived from the continuation of stock returns over medium time horizons. The empirical evidence of momentum, however, is significantly different across markets around the world. The purpose of this dissertation is to: 1) help global investors determine the optimal selection and holding periods for momentum portfolios, 2) evaluate the profitability of the optimized momentum portfolios in different time periods and market states, 3) assess the investment strategy profits after considering transaction costs, and 4) interpret momentum returns within the framework of prior studies on investors’ behavior. Improving on the traditional practice of selecting arbitrary selection and holding periods, a genetic algorithm (GA) is employed. The GA performs a thorough and structured search to capture the return continuations and reversals patterns of momentum portfolios. Three portfolio formation methods are used: price momentum, earnings momentum, and earnings and price momentum and a non-linear optimization procedure (GA). The focus is on common equity of the U.S. and a select number of countries, including Australia, France, Germany, Japan, the Netherlands, Sweden, Switzerland and the United Kingdom. The findings suggest that the evolutionary algorithm increases the annualized profits of the U.S. momentum portfolios. However, the difference in mean returns is statistically significant only in certain cases. In addition, after considering transaction costs, both price and earnings and price momentum portfolios do not appear to generate abnormal returns. Positive risk-adjusted returns net of trading costs are documented solely during “up” markets for a portfolio long in prior winners only. The results on the international momentum effects indicate that the GA improves the momentum returns by 2 to 5% on an annual basis. In addition, the relation between momentum returns and exchange rate appreciation/depreciation is examined. The currency appreciation does not appear to influence significantly momentum profits. Further, the influence of the market state on momentum returns is not uniform across the countries considered. The implications of the above findings are discussed with a focus on the practical aspects of momentum investing, both in the U.S. and globally.

An application of evolutionary algorithms for WAG optimisation in the Norne Field

Water-alternating-gas (WAG) is an enhanced oil recovery method combining the improved macroscopic sweep of water flooding with the improved microscopic displacement of gas injection. The optimal design of the WAG parameters is usually based on numerical reservoir simulation via trial and error, limited by the reservoir engineer’s availability. Employing optimisation techniques can guide the simulation runs and reduce the number of function evaluations. In this study, robust evolutionary algorithms are utilized to optimise hydrocarbon WAG performance in the E-segment of the Norne field. The first objective function is selected to be the net present value (NPV) and two global semi-random search strategies, a genetic algorithm (GA) and particle swarm optimisation (PSO) are tested on different case studies with different numbers of controlling variables which are sampled from the set of water and gas injection rates, bottom-hole pressures of the oil production wells, cycle ratio, cycle time, the composition of the injected hydrocarbon gas (miscible/immiscible WAG) and the total WAG period. In progressive experiments, the number of decision-making variables is increased, increasing the problem complexity while potentially improving the efficacy of the WAG process. The second objective function is selected to be the incremental recovery factor (IRF) within a fixed total WAG simulation time and it is optimised using the same optimisation algorithms. The results from the two optimisation techniques are analyzed and their performance, convergence speed and the quality of the optimal solutions found by the algorithms in multiple trials are compared for each experiment. The distinctions between the optimal WAG parameters resulting from NPV and oil recovery optimisation are also examined. This is the first known work optimising over this complete set of WAG variables. The first use of PSO to optimise a WAG project at the field scale is also illustrated. Compared to the reference cases, the best overall values of the objective functions found by GA and PSO were 13.8% and 14.2% higher, respectively, if NPV is optimised over all the above variables, and 14.2% and 16.2% higher, respectively, if IRF is optimised.

Heritability and genetic correlations of personality traits in a wild population of yellow-bellied marmots (Marmota flaviventris)

This article is protected by copyright. All rights reserved. Acknowledgments We thank all the marmoteers that helped collect data over the years, and specifically Amanda Lea for help with the pedigree and Leon Chong for help in the field. The comments of two anonymous reviewers helped us improve our original MS. M.B.P. was funded by two U.S. Department of Education GAANN Fellowships, an NSF GK-12 Fellowship, and the UCLA Department of Ecology and Evolutionary Biology. J.G.A.M. was supported by a Marie-Curie Fellowship. D.T.B was supported by the National Geographic Society, UCLA (Faculty Senate and the Division of Life Sciences), a Rocky Mountain Biological Laboratory research fellowship and by the NSF (IDBR-0754247 and DEB-1119660 to D.T.B., as well as DBI 0242960 and 0731346 to the Rocky Mountain Biological Laboratory).

Molecular analysis of evolutionary relationships of Phaseolus dumosus with the gene pool of common bean

Valuable genetic variation for bean breeding programs is held within the common bean secondary gene pool which consists of Phaseolus albescens, P. coccineus, P. costaricensis, and P. dumosus. However, the use of close relatives for bean improvement is limited due to the lack of knowledge about genetic variation and genetic plasticity of many of these species. Characterisation and analysis of the genetic diversity is necessary among beans' wild relatives; in addition, conflicting phylogenies and relationships need to be understood and a hypothesis of a hybrid origin of P. dumosus needs to be tested. This thesis research was orientated to generate information about the patterns of relationships among the common bean secondary gene pool, with particular focus on the species Phaseolus dumosus. This species displays a set of characteristics of agronomic interest, not only for the direct improvement of common bean but also as a source of valuable genes for adaptation to climate change. Here I undertake the first comprehensive study of the genetic diversity of P. dumosus as ascertained from both nuclear and chloroplast genome markers. A germplasm collection of the ancestral forms of P. dumosus together with wild, landrace and cultivar representatives of all other species of the common bean secondary gene pool, were used to analyse genetic diversity, phylogenetic relationships and structure of P. dumosus. Data on molecular variation was generated from sequences of cpDNA loci accD-psaI spacer, trnT-trnL spacer, trnL intron and rps14-psaB spacer and from the nrDNA the ITS region. A whole genome DArT array was developed and used for the genotyping of P. dumosus and its closes relatives. 4208 polymorphic markers were generated in the DArT array and from those, 742 markers presented a call rate >95% and zero discordance. DArT markers revealed a moderate genetic polymorphism among P. dumosus samples (13% of polymorphic loci), while P. coccineus presented the highest level of polymorphism (88% of polymorphic loci). At the cpDNA one ancestral haplotype was detected among all samples of all species in the secondary genepool. The ITS region of P. dumosus revealed high homogeneity and polymorphism bias to P. coccineus genome. Phylogenetic reconstructions made with Maximum likelihood and Bayesian methods confirmed previously reported discrepancies among the nuclear and chloroplast genomes of P. dumosus. The outline of relationships by hybridization networks displayed a considerable number of interactions within and between species. This research provides compelling evidence that P. dumosus arose from hybridisation between P. vulgaris and P. coccineus and confirms that P. costaricensis has likely been involved in the genesis or backcrossing events (or both) in the history of P. dumosus. The classification of the specie P. persistentus was analysed based on cpDNA and ITS sequences, the results found this species to be highly related to P. vulgaris but not too similar to P. leptostachyus as previously proposed. This research demonstrates that wild types of the secondary genepool carry a significant genetic variation which makes this a valuable genetic resource for common bean improvement. The DArT array generated in this research is a valuable resource for breeding programs since it has the potential to be used in several approaches including genotyping, discovery of novel traits, mapping and marker-trait associations. Efforts should be made to search for potential populations of P. persistentus and to increase the collection of new populations of P. dumosus, P. albescens and P. costaricensis that may provide valuable traits for introgression into common bean and other Phaseolus crops.

Testing for biases in selection on avian reproductive traits and partitioning direct and indirect selection using quantitative genetic models

Key life history traits such as breeding time and clutch size are frequently both heritable and under directional selection, yet many studies fail to document micro-evolutionary responses. One general explanation is that selection estimates are biased by the omission of correlated traits that have causal effects on fitness, but few valid tests of this exist. Here we show, using a quantitative genetic framework and six decades of life-history data on two free-living populations of great tits Parus major, that selection estimates for egg-laying date and clutch size are relatively unbiased. Predicted responses to selection based on the Robertson-Price Identity were similar to those based on the multivariate breeder’s equation, indicating that unmeasured covarying traits were not missing from the analysis. Changing patterns of phenotypic selection on these traits (for laying date, linked to climate change) therefore reflect changing selection on breeding values, and genetic constraints appear not to limit their independent evolution. Quantitative genetic analysis of correlational data from pedigreed populations can be a valuable complement to experimental approaches to help identify whether apparent associations between traits and fitness are biased by missing traits, and to parse the roles of direct versus indirect selection across a range of environments.

Genetic medicines for CF: hype versus reality

Since identification of the CFTR gene over 25 years ago, gene therapy for cystic fibrosis (CF) has been actively developed. More recently gene therapy has been joined by other forms of “genetic medicines” including mRNA delivery, as well as genome editing and mRNA repair-based strategies. Proof-of-concept that gene therapy can stabilize the progression of CF lung disease has recently been established in a Phase IIb trial. An early phase study to assess the safety and explore efficacy of CFTR mRNA repair is ongoing, while mRNA delivery and genome editing-based strategies are currently at the pre-clinical phase of development. This review has been written jointly by some of those involved in the various CF “genetic medicine” fields and will summarize the current state-of-the-art, as well as discuss future developments. Where applicable, it highlights common problems faced by each of the strategies, and also tries to highlight where a specific strategy may have an advantage on the pathway to clinical translation. We hope that this review will contribute to the ongoing discussion about the hype versus reality of genetic medicine-based treatment approaches in CF.