9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # 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.

1

Introduction

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.

2

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].

3

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.

4

Experiments

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].

5

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

References

[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.

赞助商链接

- 神经网络算法
- Crossover improvement for the genetic algorithm in information retrieval
- A NEW GENETIC ALGORITHM WITH ARITHMETIC CROSSOVER TO ECONOMIC AND ENVIRONMENTAL ECONOMIC DI
- A New PSO Algorithm with Crossover Operator for Global Optimization Problems
- YASA Yet another time series segmentation algorithm for anomaly detection in big data problems

更多相关文章：
**
...in OFDM System Based on ***Genetic* *Algorithm*

Based on*Genetic* *Algorithm*_工学_高等教育_教育专区...user k at *time* slot t is: t rkt = ∑ bn ... the new *cross*-layer resource allocation *problem*....**
Hardware Implementation of ***Genetic* *algorithm*

Hardware Implementation of*Genetic* *algorithm*_法律资料...Due to their iterative *problem* solving method, ...In this case the complete selection, *crossover* ...**
英文翻译PID参数整定方法
**

*Genetic* *algorithm* is put forward by John ...The optimisation *problem* *for* the GP is to ...*Cross over*. In this work sub tree *crossover* ...**
...Test Based on ***Genetic* Annealing *Algorithm*

Parallel Test Based on*Genetic* Annealing *Algorithm*...Definition: Total *time* of all test tasks that ...Then a C *Crossover* operator As shown in Fig.1...**
基于GA求解JOBSHOP问题
**

*problem* based on *genetic* *algorithm* Abstract Simply ...Therefore, this *algorithm* making the*crossover* and ...completion*time*, can avoid such disadvantages as ...**
外文翻译-***遗传算法*

*problem*-solving techniques Concisely stated, a *genetic* *algorithm* (or GA *for* ...The upper diagram *shows* two individuals undergoing single-point *crossover*; ...**
...contrast enhancement method based on ***genetic* *algorithm*_...

method based on*genetic* *algorithm*_医药卫生_专业...Change over *time* 3. The research study: ...*Crossover* strategies evaluation 4.4. Learning ...**
外文翻译-***遗传算法*

*time* is chosen.) Scaling selection: As the ...*crossover*; the point of exchange is set between... the *genetic* *algorithm* optimization *problem* solutions...**
毕业论文-***遗传算法*研究_图文

Compared at the same*time* by solving the same ...国内外研究现状*遗传算法*(*Genetic* *Algorithm* 简称 GA)...交叉(*crossover*)操作:交叉就是互换两个染色体某些位...**
...and Isolation Based on GANNWA-PF ***Algorithm*

(RAIM) based on*genetic* *algorithm*-optimizedneural ...*Crossover*. Select two random samples ( xk , xk... base on GANNWA-PF setsalarmat the *time* k ?...
更多相关标签：

Based on

Hardware Implementation of

Parallel Test Based on

method based on

Compared at the same

(RAIM) based on