Co-evolving the Operators of Variation--论文代写范文精选

最经常被引用的是,研究参数的增量调整取决于最初聚集的人群，这样的技术也被应用到遗传编程。这通常涉及到存储额外的信息来指导算法。下面的essay代写范文进行详述。

Introduction 
Evolutionary algorithms are relatively robust over many problem domains. It is for this reason that they are often chosen for use where there is little domain knowledge. However for particular problem domains their performance can often be improved by tuning the parameters of the algorithm. The most studied example of this is the ideal mix of crossover and mutation in genetic algorithms. One possible compromise in this regard is to let such parameters be adjusted (or even evolve) along with the population of solutions so that the general performance can be improved without losing the generality of the algorithm1 . 

The most frequently quoted is [4], which investigates the incremental tuning of parameters depending on the success of the operators in initially converged populations. Such techniques have also been applied in genetic programming (GP)2 . This usually involved the storing of extra information to guide the algorithm, for example in [2] extra genetic material is introduced to record a weight ef fecting where the tree-crossover operator will act. As [1] says, “There is not reason to believe that having only one level of adaption in an evolutionary computation is optimal” (page 161). In genetic programming the genetic operators are usually fixed by the programmer. Typically these are a variety of crossover and propagation, but can also include others, for example mutation. A variety of alternative operators have been invented and investigated (e.g. [2]). It is usually found that, at least for some problems these preform better than the ‘classic’ mix3 of mostly tree-crossover and some propagation (e.g. [3]). Meta-Genetic Programming (MGP) encodes these operators as trees. These “act” on other tree structures to produce the next generation. 

This representation allows the simultaneous evolution of the operators along with the population of solutions. In this technique what is co-evolved along with the base population is not a fixed set of parameters or extra genetic material associated with each gene, by operators who are themselves encoded as variable length representations – so their form as well as their preponderance can be evolved.. This technique introduces extra computational cost, which must be weighed against any advantage gained. Also the technique turns out to be very sensitive to biases in the syntax from which the operators are generated, it is thus much less robust. Iterating this technique can involve populations of operators acting on populations of operators acting on populations etc., and even populations acting on themselves. This allows a range of techniques to be considered within a common framework - even allowing the introduction of deductive operators such as Modus Ponens to be included. In section 2., I describe the basic technique in more detail. In section 5., I describe the use of possible elaborations of MGP to provide a coherent framework for the analysis of a wide range of such structures. I test a few configurations of MGP on the parity problem at dif ferent levels of difficulty in section 4., followed by a general discussion (section 7.). I finish with a small sample of the further work that needs to be done about this technique in section 8..

The Basic Technique 
Instead of being hard-coded, the operators are represented as tree structures. For simplicity this is an untyped tree structure in the manner of Koza [8]. Two randomly chosen trees along with randomly chosen nodes from those trees are passed to be operated on by the operator tree. The terminals refer to one or other of these trees at the respective node. The structure of the operator tree represents transformations of this (tree, node) pair until the root node produces the resulting gene for the next operator.

This takes the first random gene, cuts off the top at the randomly chosen position and then substitutes this for the subtree at the randomly chosen position of the second chosen gene. The single leafrand1 would represent propagation. The population of operators is treated just like any other genetic population, being itself operated on by another population of operators. This sequence must eventually stop with a fixed non-evolving population of operators or a population that acts upon itself. The base population and operator population(s) will have different fitness functions - the basic one determined by the problem at hand and the operator ’s function by some measure of success in increasing the fitness of the population they operate on.

Short-term Operator Success and Population Variation Initial trials of the technique failed. It was discovered that this was due to the fact that the variation in the base population was too quickly destroyed. T o show this an experiment was run where a population of 200 randomly generated operators of depth 5 in the language described above, acted on a population of 10,000 base genes of depth 7 using nodes AND, OR and NOT and terminals input-1,..., input-3. The operators were applied to 50 pairs of input genes each, which were chosen with a probability proportional to their initial fitness (as in standard GP). The fitness of the base population was evaluated on the even parity 3 problem before and after the application of the operators. The effect of the operators was evaluated by the average change in fitness of the operand genes before and after, where binary operators were evaluated by comparing the average of the input genes compared to the result.

Firstly, the operators which were effectively binary increased the fitness of the population by significantly less than those that were only unary . It was not that the unary operators were particularly good at increasing fitness, just that, on average, the binary operators were worse than average - this is illustrated in figure 4 (operators that were strictly equivalent to straight propagation are excluded to aid the scaling - there were 59 of these, all unary of course). 

The presence (or absence) of substitution, random node choice (as opposed to starting at the root) and the lack of movement up or down, were most significant in af fecting fitness change. This, however may be problem specific. What is not apparent from the above is that operators which corresponded in effect to a standard half of a crossover operator , did less well than the average in improving the fitness of the base population (on average they decreased the fitnesses by a factor of 0.98), but were good at preserving variety. This indicates that short-term average increase in fitness may be less important than the occasional discovery of sharply better solutions while preserving variety.

Here we can see the significant effect of the presence or otherwise of top, rand and bott type nodes in an operator. It would seem that omitting either top or rand1 & rand2 will have the effect of preserving the variation in the population. I chose to omit both top and rand1 & rand2 as the above table suggest that the effect of this might be to maximise the increase in fitness as but without the overall bias of the operator language being towards destruction of variety (as it indeed turned out). As we shall see this did have the effect of preserving the base population’s variety while allowing the operator population to evolve.

Preliminary Test Results 
The main practical questions to be resolved with respect to MGP are whether using this technique leads to improved results and whether such improvements are worth the additional computational cost. To do this a straight comparison of the number of evaluations of the base population is unfair as when using MGP one has to also evaluate the operator population as well. Thus if one has a base population of 600 in both cases and an operator population of 200 in the second case execution time is increased by a factor of about 1.33. This is a bit rough and ready but seems to give a reasonably fair comparison reflecting computational times in practice.

I chose a problem that was deliberately straight-forward, but not too easy for simple GP algorithms: the 4-parity problem allowing nodes of AND, OR and NOT only , nodes for the four possible inputs, using base populations of 600. The fitness function was the number of correct cases the gene made (out of the total of 16), with a slight penalty for depth which can never be greater than one. The initial population was randomly generated with an even depth of 7. 

The MGP algorithm had in addition a population of 200 operators using nodes up1, up2, down, down1 and subs with terminals of bott1 and bott2 (as described in section 2. above). This is turn was operated on by a population of 9 cut-and-graft operators (as illustrated in figure 3) and one simple propagation operator, all with fixed equal weights (as illustrated in figure 13). This population was also initially randomly generated with an even depth of 6. The fitness function for this population was found to be critical to the success of MGP . The basic fitness was the average proportionate change effected in the fitnesses of the base genes it operated upon. There were several (necessary) elaborations on this basic function: the fitnesses were smoothed by a running average over the last 3 generations; new genes were accorded a fitness of 1; and genes that had no ef fect on the fitness of genes (i.e. they were essentially propagation operators) were heavily discounted. (otherwise these came to quickly dominate the population as most ‘active’ operators had a fitness of less than one). 

The MGP version had, in addition, two further modifications, found necessary to make it run successfully. Firstly, there was a depth limitation of 15 imposed, as the MGP algorithm is susceptible to hyper-inflation (this is potentially far worse than in a GP algorithm as an operator with multiple subs operations can be evolved). Secondly, in the MGP algorithm fitness dif ferentials were vastly magnified by a ranking mechanism, this was necessary in the operator population because of the small differences in their fitnesses but was also because MGP introduces a higher level of variation into the base population so a stronger selection force is needed (in the GP algorithm a shifted fitness proportionate system was used as the GP performed worse under a ranking system). Both algorithms were implemented in the high-level declarative language SDML5 , with some time critical sections implemented in VisualWorks/Smalltalk. The execution times are both for the same Sun 5 Sparcstation. In figure 5 the average fitness and the fitness of the best individual is shown vs. execution time; the dotted lines are plus and minus one standard deviation of the population fitnesses and the crosses indicate when the generations occurred.

51Due网站原创范文除特殊说明外一切图文著作权归51Due所有；未经51Due官方授权谢绝任何用途转载或刊发于媒体。如发生侵犯著作权现象，51Due保留一切法律追诉权。（essay代写)
更多essay代写范文欢迎访问我们主页 www.51due.com 当然有essay代写需求可以和我们24小时在线客服 QQ:800020041 联系交流。-X（essay代写)