当前位置:首页 >> >>

Novel Genetic Algorithm Crossover Approaches for Time-Series Problems

Novel Genetic Algorithm Crossover Approaches for Time-Series Problems
Paul M. Godley, Julie Cowie and David E. Cairns Department of Computing Science and Mathematics University of Stirling Scotland pgo@cs.stir.ac.uk August 24, 2007
Abstract Genetic Algorithms (GAs) are a commonly used stochastic search heuristic which have been applied to a plethora of problem domains. GAs work on a population of chromosomes (an encoding of a solution to the problem at hand) and breed solutions from ?t parents to hopefully produce ?tter children through a process of crossover and mutation. This work discusses two novel crossover approaches for GAs when applied to the optimisation of time-series problems, with particular application to bio-control schedules.



In optimization of intervention schedules for models of dynamic systems, Genetic Algorithms (GAs) commonly use Uniform Crossover (UC) as a method of achieving recombination [8]. Recent work [4] has produced alternative crossover approaches which work on variable length chromosomes that have been shown to outperform UC when applied to dynamic problems, with speci?c application to the area of bio-control scheduling. Although alternative variable length crossover approaches such as Messy GAs (mGA) exist [6], these have considerable complexity and a two-phase evolutionary approach [1]. This work discusses a simpli?ed approach, which is speci?cally designed for time-series problems.


Problem Domain

This work focuses on the optimisation of intervention schedules and has been tested initially in scheduling bio-control agents to combat sciarid ?ies. In mushroom farming, the presence of sciarid ?ies can drastically a?ect the quality of crop produced. Sciarid ?y larvae feed on the mycelium in the casing layer of mushrooms which cause degradation of the crop. The nematode worm Steinernema feltiae has proven e?ective as a bio-control agent to combat this pest. A set of di?erential equations which represents the lifecycle of the sciarid ?ies and potential infection from nematode worms has been produced [3]. These equations have been utilised as a ?tness function for testing the novel crossover approaches developed in this work, described in [4] and [5].


Crossover Approaches

The novel crossover approaches detailed in [4] were designed to investigate if incorporating the number of interventions (application of bio-control agent) used by good solutions could be used to e?ectively drive the crossover process. These approaches, CalEB (Calculated Expanding Bin) and TInSSel (Targeted Intervention with Stochastic Selection) both provide mechanisms for crossover of variable and ?xed length chromosomes, where each chromosome represents an intervention schedule. CalEB and TInSSel both use the number of interventions present in the parents to calculate the number required in the children, with CalEB utilising a “binning” approach to select the genetic material from the parents, whereas TInSSel contains an element of stochastic selection.



Previous experiments reviewed CalEB, TInSSel and UC across varying initial intervention samples [4],[5]. These experiments were undertaken for initial population samples from min intervention to min intervention (i.e. 1 to 1, where each member of the initial population has 1 intervention) to min intervention to max intervention (i.e. 1 to 50, where each member of the initial population has between 1 and 50 interventions). These di?ering variances in possible initial interventions enabled evaluation of how initial spread a?ects each of the crossover approaches in ?nding a solution. In addition it demonstrates how the initial variance in population a?ects the

Parameter Population size Number of parents Number of children Fitness Evaluations

Table 1: GA Run Parameters Value Parameter 50 Crossover probability 2 Mutation probability 2 Days in nematode schedule 50 - 500 Nematodes / intervention

Value 1 0.05 50 1000

robustness of each crossover approach. Current work reviews the quality of solutions produced when all experiments have min intervention to max intervention (1 to 50), which represents the decision maker being unsure of the sample population to use. The aim of this work is to evaluate the search ability of UC, CalEB and TInSSel across varying limits of ?tness functions evaluations to ascertain if there is any di?erence in search ability between these crossover types. The run parameters used for both these and previous experiments are shown in Table 1. Each run was undertaken 500 times and averaged for each ?tness function limit. Tournament selection was used to select parents for breeding as it has been shown to provide better or equivalent convergence and computational properties when compared to alternative approaches [2]. The average scores for these experiments along with the associated 95% con?dence intervals are depicted in Figures 1 and 2. Figure 1 shows that regardless of the number of ?tness functions available, UC solutions require more interventions than solutions returned by CalEB and TInSSel. Figure 2 shows a clear di?erence in ?tness score between TinSSel, CalEB and UC for most experiments, with the exception being those experiments where the number of ?tness functions are very large (as all approaches have su?cient time to ?nd a solution). This experiment shows that both CalEB and TInSSel outperform UC in terms of intervention usage and quality of solution found over a varying number of ?tness function limits. This was also true when experiments were undertaken over varying initial population intervention numbers [4].


Future Work

In order to better understand the dynamics of the novel approaches, application to varying problem domains is required. Future work will focus on deriving optimal treatment schedules for cancer chemotherapy [9], using the single drug model detailed in [7].

Figure 1: Intervention Utilisation for Solutions

Figure 2: Fitness Scores for Solutions

[1] D. Dasgupta and D. McGregor. Sga: A structured genetic algorithm, 1992. [2] K. Deb and D. Kalyanmoy. Multi-Objective Optimization Using Evolutionary Algorithms. John Wiley & Sons, Inc., New York, NY, USA, 2001. [3] A. Fenton, R. L. Gwynn, A. Gupta, R. Norman, J. P. Fairbairn, and P. J. Hudson. Optimal application strategies for entomopathogenic nematodes: integrating theoretical and empirical approaches. Journal of Applied Ecology, 39(3):481–492, 2002. [4] P. M. Godley, D. E. Cairns, and J. Cowie. Directed intervention crossover applied to bio-control scheduling. In IEEE CEC 2007: Proceedings of the IEEE Congress On Evolutionary Computation, 2007. [5] P. M. Godley, D. E. Cairns, and J. Cowie. Maximising the e?ciency of bio-control application utilising genetic algorithms. In EFITA / WCCA 2007: Proceedings of the 6th Biennial Conference of European Federation of IT in Agriculture, Glasgow, Scotland, UK, 2007. Glasgow Caledonian University. [6] D. Goldberg, K. Deb, and B. Korb. Messy genetic algorithms : motivation, analysis, and ?rst results. Clearinghouse for Genetic Algorithms, Dept. of Mechanical Engineering, University of Alabama, 1989. [7] A. Petrovski. An Application of Genetic Algorithms to Chemotherapy Treatments. PhD thesis, 1999. [8] A. Petrovski, A. Brownlee, and J. McCall. Statistical optimisation and tuning of ga factors. In Congress on Evolutionary Computation, pages 758–764, 2005. [9] A. Petrovski, J. McCall, and E. Forrest. An application of genetic algorithms to optimisation of cancer chemotherapy. Int. J. of Mathematical Education in Science and Technology, 29:377–388, 1998.



All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。