Marc Schoenauer

Spyros Xanthakis

Constrained GA optimization

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

Most optimization problems are constrained problems, i.e. the search space is restricted to some subspace of the de ning space of the function to optimize. Let us suppose we want to maximize a non negative realvalued function F, called the objective function, dened on some space E, called the search space.

The constraints are equalities or inequalities the solution is required to satisfy, involving some real-valued functions C i de ned on E. In many cases, the main di culty of this problem lies in identifying the feasible region E 0 , the subspace of E where the constraints are satis ed. The feasible region can have any shape: It can be neither convex nor connected.

The classical numerical algorithms (see (Fletcher 87) for instance) quickly fail to give the right solution (or to give any solution at all) when the problem lacks "regularity" (like linearity, convexity, di erentiability).

Genetic Algorithms (GAs) (Holland 75,Goldberg 89) have now been used successfully to solve optimization problems in many domains, even though they are not function optimizers (De Jong 92). Their ability to converge to the ttest points of the search space, in a nite, though often very large, number of generations, has been studied in many works: Theoretically in (Zhigljavski 91,Davis 91) with uncheckable hypotheses, heuristically with the well-known Schema Theorem (Holland 75) and its generalizations (Radcli e 91) and of course experimentally (see papers in (ICGA 89, ICGA 91, PPSN 92) for instance).

But most of the works on GAs address the general optimization problem, rarely mentionning explicitely constrained problems.

We present in this paper a general-purpose technique for handling constraints in GA optimization processes.

It is based on the notion of Behavioural Memory (de Garis 90), which takes into account the information contained in the whole population after some genetic evolution. The rst steps of the whole process are devoted to just sampling the feasible region. The last step is then the genetic evolution of that sample, to optimize the nal objective function.

In section 2, we review some existing works in the eld of GAs devoted to constrained optimization. In Section 3 we introduce and discuss our method on a simple example. In Section 4 we give the rst results obtained on some Truss Structures Optimization problem, for which other GA approaches failed to succeed. Section 5 presents the problem of Automatic Software Test Data Generation, where other classical optimiza-tion approaches have encountered major combinatorial limitations. The particularity of this problem is that constraint C i can only be computed after constraints C 1 ; : : : ; C i?1 are satis ed.

GAs AND CONSTRAINTS

As constrained problems are quite numerous among optimization problems, there has been many attempts to solve them using GAs. Nevertheless, as pointed out in (Davis 87), the methods used are either based on some penalty function, or problem dependent, or restricted to some particular objective functions and/or constraints. A review of the different ways GAs handle constraints can be found in (Michalewicz 91). We shall brie y discuss the weaknesses or the limitations of these approaches.

ADJUSTING THE WEIGHTS, OR THE PENALTY FUNCTION METHOD

The most widely used method to treat constraints is to incorporate them in the objective function, and to use standard methods for unconstrained optimization:

In GAs, the tness function usually becomes some weighted sum of the original objective function minus some penalty for every constraint violation. The problem then becomes to adjust the penalty function, and the relative weight of the objective function as well as the di erent constraint violation penalizations.

There is no general solution to this problem, neither in classical numerical methods, nor in the GAs eld. Some guidelines for the penalty functions design are given in (Richardson 89). The authors unfortunately conclude that their method can hardly be generalized.

From our experience, the penalty function method is robust when the feasible region is "large" 1 or when the problem is "smooth". It then remains the easiest and best way to treat constraints. On more di cult problems, designing a reasonnable penalty function can become a domain dependent task.

DOMAIN SPECIFIC GAs

The best results obtained by GAs on constrained problems use problem dependent methods, where the genetic operators, the tness function and the search space itself are tailored to take the constraints into account. When possible, this approach, which uses as much domain-speci c knowledge as possible, is probably the best way to tackle constraints.

1 depending for instance on the ratio Cardinality(E')/Cardinality(E) for discrete problems, and on measure(E')=measure(E) for continuous problems.

Note that the constrained problem (P) on E can always be posed as the unconstrained problem on the feasible region E 0 . But, as already mentioned, we are concerned by constrained problems where the feasible region is not computable by direct methods. In particular, in order to apply successfully GAs to the unconstrained problem, one should be able to both generate an initial random population in E 0 , and design recombination and mutation operators closed in E 0 , suitable for genetic optimization. Theoretical studies adressing the design of good recombination operators are yet incomplete (Radcli e 91). It is nevertheless well established that initial repartitions of the population and mutation operators must have continuous density of probability on E (Zhigljavski 91). And all the widely used (when available) projection operators, and other repair algorithms certainly don't respect these conditions, as they induce a discontinuity on the boundary of the feasible region. Of course this warning does not prevent such approaches from succeeding. By domain-speci c GAs we don't exclusively mean the above mentioned family of repair algorithms, but also the following approaches:

the TSP as solved in (Grefenstette 87) ; the handling of linear constraints where the feasible region is convex, ensuring that the solution lies on its boundary (Michalewicz 91) ; the general method based on constraint propagation (Paredis 92), which applies on problems like job shop scheduling, where the constraints are analytically dened, and the propagation of the constraints is symbolically or numerically possible.

BEHAVIOURAL MEMORY

We propose to address the general problem of genetic constrained optimization by a multi-steps process: The initial steps are devoted to sampling the feasible region, i.e. initializing a population on which, in the sole last step, the objective function is optimized using standard GAs. The scheme we use is based on the Behavioural Memory paradigm: the population resulting from an evolution under genetic presssure can be viewed in a whole as a memory containing some essential information about the context it evolved in, that is the tness function used in the GA. Such scheme, despite the fact that it has already been proved to be helpful on some di cult optimization problems (de Garis 90, Desquilbet 92), has not yet, as far as we know, been systematically applied to constrained optimization.

In the simplest case, the whole optimization process is a two phases process: Evolve an initial random population with some standard GA, the tness function being related to the constraint satisfaction. Take the nal population resulting from this evolution, and use it as initial population for a GA with the objective cost function as tness function, which we override by assigning zero tness whenever the constraints are not satis ed.

AN ARTIFICIAL PROBLEM

Consider the following function of two real variables: F(x; y) = sin(x) 3 sin(y)

x 3 (x + y) , on the space E = f(x; y) ; 0 < x 10 ; 0 < y 10g This function has many local optima in E. Let us treat two optimization problems involving F:

(P 1) 8 < : Max f F(x,y) ; (x,y)2E g x 2 ?y+1 0 x?(y?4) 2 1 (P 2) 8 < : Max f F(x,y) ; (x,y)2E g
x 2 ?y+1 0 x?(y?4) 2 1 OR x?(y?1)2 0:1 The characteristics of the problems can be found on This explains why the design of a penalty function is di cult here 2 : with low weights, the global maximum of the penalized function is still outside the feasible region, near (0,0) ; with high weights, region A appears in the tness landscape like some plateau, making hard for the GAs to distinguish between di erent maxima. The experiments reported are done with a lab-made GA package based on standards: real encoding, stochastic remainder selection with tness scaling factor of 2.0, crossover at rate 0.2 performed by random barycentric combination, both o springs replacing the parents, and mutation at rate 0.2 by addition of gaussian noise of standard deviation 0.5. The algorithm stops after 50 generations without improvement.

SAMPLING THE FEASIBLE REGION

The scheme we propose is contained in Figure 2 for problem P1:

A randomly initialized population evolves to minimize the violation of the rst constraint, until a given percentage of the population (we call the ip threshold, and denote by ) is feasible for the rst constraint. This population is then the starting point for the second phase of evolution, minimizing the violation of the second constraint. During that phase, points that are not feasible for the rst constraint have zero tness, and thus disappear due to selection. The stop criterion is again the satisfaction of the second constraint by the ip threshold percentage of the population. We now have a feasible population to start optimizing function F. During this last step, non feasible points are in turn eliminated through selection.

Of course, this is the ideal case. Let us now detail some of the key features.

FITNESS FUNCTIONS

It is wellknown that the shape of the tness landscape is of utter importance for the behaviour of GAs. During the minimization of constraint C i , we set the tness function to M ?C i , for a "su ciently large" positive number M. But two reasons prohibit an absolute choice of M: constraint will be (see section 4 for instance) ; and choosing a too large constant leads to forbid any distinction between "nearly feasible" and "really feasible" points for the constraint C i at hand, as the whole tness landscape nearby the feasible region -with low constraint violation -will be attened by the zero tness assigned to the points failing to satisfy constraints C 0 ; : : : ; C i?1 . This is why parameter M is adjusted dynamically at each generation. At generation t, the maximum value of the constraint violation ? t is computed. But some uke mutation can suddenly give very high constraint violation, in which case setting parameter M directly to ? t can have the same disastrous e ect than choosing a too large constant value for M. So we want parameter M to be non-decreasing along generations. The tness function we used throughout the following experiments is de ned at generation t by (M t ? C i ) + , where M t is the minimum of ? t and M t?1 .

GENETIC DIVERSITY

All experiments on problem P1 made with the preceeding algorithms converged to the global maximum (with pop. size 30 to 100, ip threshold from 0.5 to 0.9). The two rst steps were achieved in 10 to 30 generations, the optimal point being reached after 100 to 150 more generations.

But the rst experiments on problem P2 showed that the key feature in the Behavioural Memory paradigm is to sustain genetic diversity within the population: We wish the nal population of each intermediate step to be the initial population of the following step, sampled as uniformly as possible over the feasible region of the current constraint.

All the points of the target feasible region must admit the same tness value, to avoid any convergence inside that region. In particular, the nal objective function must not be taken into account before the nal step. Premature convergence toward the rst feasible points found by the algorithm must be avoided. And this is specially important when the feasible region is not a connected domain, as in P2. To this end, we use the sharing scheme as described in (Goldberg 89, Deb 89), together with restricted mating.

Figure 3 shows the repartition of the population at the end of step 2 for problem P2, with and without sharing: Without sharing, the smaller domain B is not sampled at all and the initial population of the third phase is completely contained in domain A. The right solution, which lies in B, will only be found depending on a lucky mutation, as the whole space between A and B gets zero tness in the last step.

The choice of the sharing factor is important, but that of the ip thershold is as well, as demonstrates Table 1. For a population size of 50 on problem P2, it reports the results of ten independent runs: First the number of successes of the algorithm in nding the maximum in B and not in A, then the average number of generations it took to get the required percentage of feasible points for the second constraint3 . 2 6 -35 5 -46 3 -75 3 -358 .3 8 -47 5 -55 3 -144 3 The time to correctly sample the feasible region increases with the ip threshold , which is natural, but also with the sharing factor . Using sharing, every point can be thought of as a small elastic ball of radius , repelling other points of the population, and -possibly -sending them in other components of the feasible region. Therefore, the "amount" of feasible region so sampled increases with . But, in order to satisfy the second constraint, a certain amount of such "balls" must get in the feasible region, whose size is nite -small in our case. So, as goes on increasing, it becomes more and more di cult to meet the requirement of constraint satisfaction for the same number of points. In which case the unavoidable genetic drift due to so numerous useless generations spoils the possible genetic diversity this sharing factor could have brought. And, of course, when and are too large, the required constraint satisfaction simply becomes impossible. The sharing factor and the ip threshold must be adjusted together: the order of magnitude of can be approximated from below using large , and increasing until the required percentage of feasible points cannot be reached any more. Slightly decreasing should then allow to nd good values for both and .

TRUSS STRUCTURE OPTIMIZATION

The previous scheme has been sucessfully applied to the test problems of truss structure optimization (Haug 79): The 10-bar (2D) and the 25-bar (3D) truss structures.

The design variables to optimize are here the section areas of the bars, the objective function to minimize is the weight of the structure, and the constraints are maximum values of the stress in the bars, to avoid collapsing of the structure. These problems can be solved by many gradient-like numerical methods when the sections take continuous real values. But such methods cannot be used when some of the design variables are discrete: It could be the material the bars are made of, or even the possible section areas (if limited to manufactured items). And GAs indeed can solve both discrete and continuous problems, as we shall now brie y report (more details can be found in (Schoenauer 93)).

Only the section areas are taken here as design variables, taking values in some given real interval (the continuous problem) or in a given set of 36 preset values (the discrete problem). The genetic operators are those of section 3.1, "naturally" discretized in the discrete case.

The constraints are maximal values for the stress in every bar when some given loading is applied to the structure. There is no analytical way to express such stress values ; they have to be computed using some nite element method (which takes up to a few tenth of second on a 68040-based computer). Moreover, it is not easy to guess some upper bound for these stress values: The mechanical model will go on giving huge values long after the structure has in fact collapsed. We use 100 structures in the population ; the given results express averages on 5 runs with di erent initial populations. In the discrete case, around 30 generations are needed to satisfy all the stress constraints in 70% of the population (being of the same nature, the 10 constraints are considered in one single step). The convergence toward the solution is reached in 500 to 800 generations. In the continuous case, about 100 generations are necessary to sample the feasible region, and about 5000 generations are necessary to reach a good approximation of the solution4 . On both problems, most of the penalty functions, rst tried with GAs, failed -converging towards local maxima, or failing to stabilize. To end this section, it must be stated that GAs have a huge eld of application in Structure Optimization: Problems involving qualitative variables (e.g. the material), and even the topological optimization problem, where the number and connections of the elements are unknown. And all these problems involve constraints.

GENERATING SOFTWARE TEST DATA

Software testing is generally considered to be the most signi cant and labour intensive phase in the software lifecycle because of both of its economic consequences and technical complexity. The major part of the testing e ort is the Test Data Generation process (TDG), nowadays poorly automated, which consists in choosing a representative subset of inputs then executing the program and verifying that the results are in accordance with the speci cations. Our concern is the automation of the structural test data generation task, that is the generation of test data (TD) which are able to execute (we also say "cover" or "sensitize") selected substructures of the software (i.e. statements, crucial paths, etc). It has been established that providing a general automated tool for TDG is formally impossible (Howden 77). In fact the sensitization of a software substructure can be considered as the satisfaction of a set of conditions, that is the conditions which lead the execution ow to visit the speci c statement. For instance if we wish to execute the Do exception state- ... we have to satisfy the two conditional if statements. Moreover the second condition cannot be established before the rst one has been satis ed (we need to know the new values of variables a and b after the execution of function f 2 ).

Three main approaches tackle the automatic TDG problem :

The predominant approach is random testing (Duran 80): Input values are randomly generated and the substructures covered are observed by means of instrumentation (additional statements tracking program execution). The limitation of this approach comes from its blindness: Too nested structures are never executed and equality conditions are rarely satis ed. In symbolic execution, variables are assigned symbolic values and program statements are executed symbolically by means of algebraic manipulations (Clarke 83). However, dynamic informations (like pointers, arrays or number of iterations) must be hypothesized during symbolic execution, leading to an unavoidable combinatorial explosion when non toy programs are considered. In the dynamic approach (Korel 90), an initial random set of TD is generated and progressively adapted during consecutive executions with the goal of sensitizing the substructure chosen by a test strategy.

The condition satisfaction task (e.g. satisfy statement if (a < b) :::) is expressed in terms of optimization (e.g. minimize the expression a ? b where a and b are the observed values just before the rst if statement). Classic gradient-like optimization methods meet a number of di culties. First there is no analytic way (unless we adopt symbolic execution) to express the condition to be optimized. Secondly, a problem of lack of orthogonality comes from the interdependency between parameters. Moreover, the values may evolve discontinuously during the execution of the program. Lastly is the problem of local optima. All these observations lead to adopt GA for the automatic TDG using a dynamic approach. Given the stepwise nature of the constraint satisfaction process, we adopted the Behavioral Memory paradigm as previously described. The constrained GA optimisation algorithm is embedded into an automatic test data generator named TAGGER. The inner loop is the following: Given a structure, 1. A simple Data Flow Analysis algorithm as described in (Xanthakis 92) is used to determine the subset of inputs which a ect the conditions appearing at the structure to cover. 2. An initial random population of values for this subset is produced. 3. For each constraint, the popuulation evolves until some given percentage of the population satis es it, allowing to compute the next one. When one individual satis es this last constraint, the given structure is covered. The loop exits, asking the generator for the next structure to cover.

The TAGGER prototype has been used on a number of critical programs, though not yet in an industrial environment. Nonetheless the results so far are extremely promising. Coverage metrics of 100 % of branches are often achieved with a performance well beyond by random testing (5 -35 times faster when a solution can be found by random testing).

CONCLUSION

We presented a general method to handle constraints in GAs: First sample the feasible region by genetically evolving a population in the whole search space minimizing some constraint violation ; then, evolve the resulting population to maximise the initial objective function on the feasible region so sampled.

Our method is problem independent. We emphasize it can handle any computable constraints. It also allows GAs to be independant of the tness landscape outside the feasible region: It can be non de ned at some points, or have numerous local optima, ... Moreover, it optimizes in its last step the exact objective function, not some arti cial transformation. The counterparts are an increased computational cost as each step is a partial GA optimization in itself, and the need to maintain genetic diversity during evolution, whatever scheme is used. And when using the sharing scheme, the sharing factor must be adjusted very carefully.

We do not claim to outperform all other methods for constraints handling using GAs. In particular when feasible region is large, using penalty function may be a cheaper strategy. And designing problem-speci c operators will probably, when possible, give better results than any general method. But in many problems, like in engineering optimization for instance, the feasible region is small and quite sparse in the whole search space, and the constraints are available only through some heavy numerical computation. These restrictions forbid the use of standard methods (the feasible region is not convex, nor does the solution lie on its boundary) as well as the design of speci c closed genetic operators. Moreover in problems like the generation of software test data, the method we propose seems to be the only one to be able to handle "hierarchically computable" constraints.

Figure 1 :

 1 Figure 1: The feasible regions.

Fig. 1 :

 1 Fig.1: Domain A (resp A S B) is the feasible region of P1 (resp. P2) ; there are in A two maxima (points a and a 0 ) with very similar values for F ; but many other local maxima take considerably higher values,

Figure 2 :

 2 Figure 2: End of rst steps (Problem P1).

Figure 3 :

 3 Figure 3: E ect of sharing (Problem P2).

Table 1

 1

	: E ects of the Flip Threshold and the Sharing Factor
	n 50 % 60 % 70 % 80 % 0 1 -18 1 -26 2 -32 0 -32 .01 6 -26 8 -35 7 -40 5 -71 .05 6 -24 9 -32 7 -45 5 -61 .1 7 -33 9 -36 6 -54 8 -87 .

though we did nd sucessful weights and a priori maximum values of the constraint violations for these simple and smooth problems.

where *** indicates at least one run could not reach that percentage.

which is more than

times slower than classical gradient methods!


Marc Schoenauer

Edmund Ronald

Neuro-Genetic Truck Backer-Upper Controller

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Neuro-Genetic Truck Backer-Upper Controller Marc Schoenauer and Edmund Ronald Abstract| The precise docking of a truck at a loading dock has been proposed in Nguyen & Widrow 90] as a benchmark problem for non-linear control by neural-nets. The main di culty is that back-propagation is not a priori suitable as a learning paradigm, because no set of training vectors is available: It is non-trivial to nd solution trajectories that dock the truck from anywhere in the loading yard. In this paper we show how a genetic algorithm can evolve the weights of a feedforward 3-layer neural net that solves the control problem for a given starting state, achieving a short trajectory from starting point to goal. The tness of a net in the population is a function of both the nearest position from the goal and the distance travelled. The in uence of input data renormalisation on trajectory precision is also discussed.

I. PLANT DESCRIPTION

The plant to be controlled here is a truck with trailer, which should be backed up to a loading dock; the truck is initially located at some random position in the parking lot. The truck backs up by small uniform steps, denoted by r, while steering is e ected by re-orienting the front wheels before each step. There is thus only one control variable, the angle of the steering wheels with respect to the cab, denoted u.

Our truck is the same as that described in the pioneering studies of Nguyen & Widrow 90], who devised backpropagation through time to investigate the system. We have followed Nguyen & Widrow 90] in chosing the observable state variables which together de ne a state: The coordinates of the center back of the trailer, and the orientation of the cab and the trailer with repect to the x axis. The constraints on the steering range and the sizing of the truck have been retained.

We have however adopted a di erent set of dynamic equations, which allow us to resolve more easily the uncertainty on the angles S and C occasioned by the use of the arctangent in the paper cited above. The reader may verify that both derivations are equivalent in the rst order, and thus de ne similar trajectories.

Both authors can be reached at Centre de Math ematiques Appliqu ees, URA CNRS 756, Ecole Polytechnique, 91128 Palaiseau, France. Email should be adressed to marc@cmapx.polytechnique.fr L S 14m length of the trailer, from rear to pivot.

B = A cos( C t] S t]) x t + 1] = x t] B cos( S t]) y t + 1] = y t] B sin( S t]) S t + 1] = S t] arcsin( A sin( C t] S t]) LS ) C t + 1] = C t] + arcsin( r sin(u) LS+LC ) C t + 1] is
L C 6m length of the cab, from pivot to front axle.

II. EXPERIMENTAL SETUP

The problem we set out to investigate was the precise docking of the truck, with the center back of the trailer at the origin, and the trailer perfectly straight, ie. aligned with the x axis and thus with angle S = 0. We rst concerned ourselves with docking from some random starting point such that x > 0, with the trailer arbitrarily jackknifed with repect to the cab.

In order to solve this problem by a genetic algorithm, we decided not to search for short trajectories directly, but rather to postulate an intermediate agent, a neural net controller. Such a neural net acts as truck driver. Thus in the rst instance we applied genetic search to the task of evolving a neural net able to dock the truck, from some single starting point. We then attempted to extend the method to nding nets capable of docking the truck from various starting con gurations.

The experiments reported in this paper were done with a homebrew general-purpose genetic algorithm package embodying the principles described in Holland, Goldberg] as well as in Radcli e, Michalewicz 92]. Our software subjects a small population of nets to crude parody of natural evolution. This arti cial evolutionary process aims to achieve nets which display a large tness. This is a positive real value which denotes how well a net does at its assigned task of driving the car. In other words, the tness gets large if the net docks the car, larger yet if the trajectory it traverses is short. The details of the calculation of the tness are found below.

For the purpose of applying the genetic algorithm, a given net is canonically represented by the chromosome consisting of its weights, i.e. as a vector of real numbers. Note that our genetic engine di ers from the rst methods presented by John Holland in that it does not use bit-strings; it is hybridised in that it directly represents oating-point numbers with the usual arithmetic precision achieved with 8 byte double-precision reals on workstations. In these experiments the genetic engine was not customised to re ect the structure of neural nets -a net structure-speci c adaptation of the crossover operator may be undertaken in future research.

A stated in the introduction, a classical 3-layered feedforward net architecture was employed PDP], with complete interconnection between layers 1 and 2, and 2 and 3. The neural transfer function was the usual sigmoid logistic f(x) = 1=(1 + exp( x)). Regarding the crucial question of the number of neurons in the middle layer, the Kolmogorov model Hecht-Nielsen] for such a net with n inputs and 1 output requires at least 2n+1 intermediate neurons and this paradigm was adopted.

The tness calculation is central to solving a problem by a genetic algorithm. In our case, in the initial stages of this research we were considering a truck without trailer ie. a car, and did not take into account the length of a trajectory, but only whether it approached the (0; 0; 0) docking position. To this end, each net was allowed to drive the car for 300 steps, and, at each step, the distance d to (0; 0; 0) (in 3d-space) was computed, by the formula d 2 = x 2 + y 2 + min( S 2 ; ( S 2 ) 2 ; ( S + 2 ) 2 ) where the expression min( S 2 ; ( S 2 ) 2 ; ( S + 2 ) 2 ) was employed to allow an o set of one complete turn either way. However, genetic algorithms maximise, rather than minimise, so the above distance was rescaled by taking an inverse, yielding the following tness function: Perf(x; y; S ) = 1 " + min trajectory d 2 With the above tness Perf(x; y; ), a set of 10 numerical experiments was made: In each experiment, the car was started from (20,10 -2), and a di erent random seed was used to generate an initial population of 30 nets with random weights, with 1 < w j i < 1. The genetic algorithm was then allowed to run for 100 generations, and the best-performing net consistently achieved d 2 < 5, which translates to a maximum angular error of 0,1 radians (i.e. 6 degrees) and p 5 linear units in x, y. Note that with a car move-step size of 3 a better result was hardly to be expected! However, as trajectory length was not taken into account in the performance function, the nets took a circuitous, roundabout route in getting to the goal, a bit like a taxi driver who takes his guest for an expensive ride but ends up delivering him safe and sound. More results concerning the car are reported in Schoenauer & Ronald 93]. The gure1 below shows such a roundabout trajectory in the case of the truck. In order to take into account the length of the trajectory, the tness function was amended to read: Perf(x; y; S ) = 1 " + min trajectory d 2 + ẁhere `is the number of time steps needed to dock the truck to (0; 0; 0). The values " = 0:1 and gamma = 0:001 were adopted as ensuring a good compromise between trajectory accuracy and length.

III. RESULTS

The results presented below fall into two categories that re ect the chronology of our experimentation: Single-point learning and multi-point learning.

A. SINGLE POINT LEARNING For the single starting-point docking problem, successive experimental runs for the truck-with-trailer were made with neural nets di ering by the type and number of inputs. These are detailed below.

At rst, the same input-output architecture as in Nguyen & Widrow 90] was essayed. Here the controller net takes the 4 variables (x; y; S ; C ) as inputs and, by the Kolmogorov paradigm cited above, consists of a 4-9-1 fully connected neural net; this means that the chromosome of weights and biases is formed of 55 oating point numbers.

In this case, genetic learning yielded adequately short and precise trajectories, as in The single-starting point problem allows an interesting optimisation: Recall that all we require of a controller is that it be able to dock the car from the given unique position. This means generating a set of steering angles u t] for each time-step t. It is reasonable to wonder whether a net really needs much information for this simple task, or whether it can be taught to " y by instruments". We investigated this question by reducing the number of inputs to 3, by rendering the state variable C unobservable. Thus the net does not "know" the angle of the cab. In practice this optimisation corresponds to a 3-7-1 net, ie. chromosomes of 36 reals. These 3-input nets could be trained at a lesser computational cost, yet provided excellent results, as can be seen in the gure below. We are still investigating just how far we can pursue this type of optimisation by removal of excess information.

Figure 4: 3-Input net trajectory with best approach at (0:99; 0:32; 1:11)

B. MULTI-POINT LEARNING

In order to teach the nets to be able to dock from several points, we chose to compute a global tness by taking the aritmetic mean, or the minimum of the single-point tness mentioned earlier. Both methods gave acceptable results for a training ensemble of 15 points consisting of 5 angular orientations (-90, -30, 0, 30, 90) degrees clustered at the 3 locations of coordinates (100,0), (80,50), (80,-50). This yielded accptable accuracy after about 1500 generatiions of the GA.

In an attempt to improve the accuracy, which had stabilised, we enhanced the net structure, going from 4 inputs to 8. The additional inputs reproduced the original ones, but were rescaled by a factotr of 10. This was done in order to give the net the more precise perception necessary for ne control. The resulting 8-17-1 nets needed fewer generations (800) to learn, and were more precise. Actual computation time went up however because of the increase of the number of weights from 55 to 171.

IV. DISCUSSION AND FUTURE WORK

Our study of the truck-and-trailer problem is complementary to, rather than competitive with the results in Nguyen &Widrow], because our results apply to travel starting far from the goal, while their study yielded complex close-up manoeuvering behaviour which we have yet failed to reproduce.

This foray into genetic learning in neural nets has established the basic feasibility of the appproach, howewver it has also raised a number of specifc issues:

Sizing the nets is always a problem , however we have not seen it posed in the context of supplying a net with additional, redundant, renormalized copies of some inputs. In our experiments with the truck this has proven useful. We have employed the same technique with success in ne-tuning the controller of a lunarlander simulation Ronald &Schoenauer 93].

We have also seen that in some cases, in particular for the single-start trajectories, the number of necessary input variables can be reduced. We went from 4 to 3 inputs without performance degradation, ultimately perhaps all precise topographic inputs might be eliminated. The resultant blind net would still receive some time or elapsed distance input, or even embody a looped recurrent architecture with no input at all. The computation of the tness in the multi-point learning utilizes the tness employed for the single-point case, in our study. However, the tness values computed for each starting point in the training ensemble must still be summated or amalgamated. The exact form of the summation needs ne-tuning. Also, the trajectory computations become very time consuming; runs can take hours on a workstation. If it were feasible not to represent all the starting points in the training ensemble, then the genetic search procedure could be notably speeded up. In Mitchell, Haber & Crutch eld], in the context of evolving cellular automata, a di erent random sampling of the training ensemble is presented at each generation; the genetic algorithm embodies elitism to the extent of passing 20% of the population unchanged from generation to generation. We will investigate this strategy in future work.

  Figure 1: Truck-Trailer System Description

Figure 2 : 2 -

 22 Figure 2: 2-Input net docking trajectory, goal is at center-left

  Fig 1. However convergence to a satisfying performance was only achieved by setting a fairly large value r = 3 to the step-length by which the truck backs up. the gure shows 500 generations (100 without improvement) with a population size of 100 individuals.

Figure 3

 3 Figure 3: 4-Input net trajectory with best approach at (1:35; 0:37; 1:52)

Figure 5 :

 5 Figure 5: Multi-point learning ensemble and ensuing tra c The remarkable generalization properties of neural nets are demonstrated by the fact that the net performed trained on the above described ensemble performed reasonably well when launched from any point in the 3-d space 50 100] 50; 50] 180; 180], whatever the jacknife angle C . In the gure below one the trajectories from 10 randomly chosen starting points are presented.

Figure 6 :

 6 Figure 6: 8 random starting points and ensuing tra c

In all gures the region 0; 100] 50; 50] is shown, with the goal at (0; 00)


Governing structural changes and sustainability through (new) institutions and organizations

Nathalie Lazaric, Pasquale Tridico, Sebastiano Fadda, "The important thing for Government is not to do things which individuals are doing already, and to do them a little better or a little worse; but to do those things which at present are not done at all." John M. [START_REF] Keynes | The end of laissez-faire[END_REF] The Special Issue collects articles on the structural change with the potential danger of a new age of capitalism shaped by several and different topics like financialization and robotization, along with jobless growth and low productivity growth, in the service sector, and the need to integrate sustainability issues at the supply and demand levels. This issue investigates which institutions and type of governance would be able to govern these changes, risks and opportunities that are reshaping ways of doing things. Our goal also to create some cross-fertilization of diverse schools of thought combining innovation, path dependency, trajectories, demand issues, and post Keynesian insights. Some early works have paved the way for this synthesis [START_REF] Dosi | Schumpeter meeting Keynes: A policy-friendly model of endogenous growth and business cycles[END_REF][START_REF] Dosi | What if supply-side policies are not enough? The perverse interaction of flexibility and austerity[END_REF]. In this roadmap, some scholars ask for a new European industrial policy where the nature of structural challenges are addressed with a focus on the content of instruments [START_REF] Mazzucato | Which Industrial Policy Does Europe Need?[END_REF].

Before to go further, we need some clarification about the way we define structural changes and sustainability. Structural change may be defined as the continuous introduction of new products and new production technologies with energy efficiency and de-materialisation (Ayres and van der Bergh, 2005: 116). In addtion, we are also oberving not a single structural change but diverse sources of structural changes in various domains such as consumption, technologies, production techniques and inputs and show aspects of structural change at macro and meso levels ( Ciarli and Savona, 2018 ;Savona and Ciarli, 2019). In thier recent survey, Savona and Ciarli (2019) review diverse aspects of structural change that have a direct impact on environmetnal sustainability, supply and demand side.

These dimensions imply fourth dimensions that are : 1) a focus on sectoral composition of the economy with a move from manufacturing to services called the tertiarisation; 2) the international division of labour and the impact on countries of changes in Global Values Chains ( GVCs) ; 3) technical change with possible ecological innovations and opportunities for cleaner products and services; 4) demand changes affecting consumption patterns and preferences (Savona and Ciarli, 2019: 247). In relation to these diverse components of structural changes, these authors emphasis the interrelated area of these dynamics such as a change in GCVs that impact the division of labour and has huge impact on the emissions of energy intensity and the enviromental burden linked to global trade. We may also add to these fourth dimensions the impact of technological breakthroughs notably with the digital transformation of the industry called Industry 4.0 [START_REF] Cézanne | Exploring the economic and social impacts of Industry 4.0[END_REF] and its impact on the international division of labour and employment both within Europe and between Europe and the rest of the world [START_REF] Dachs | Bringing it all back home? Backshoring of manufacturing activities and the adoption of Industry 4.0 technologies[END_REF][START_REF] Szalavetz | Industry 4.0 and capability development in manufacturing sub-sidiaries[END_REF]. Finally the long term trend of the financialization of the economy that has accelerated structural change and their outcomes on various economies is the last dimension that should be scrutinized to have a global view on these dynamics.

Indeed, over the last three decades, many advanced economies have experienced significant changes in their productive structures, with a decline in the share of workers in manufacture and a transition towards the service sector [START_REF] Kander | Baumol's disease and dematerialization of the economy[END_REF]. This idea is obviously not new and dates back at least to [START_REF] Baumol | On the Performing Arts: The Anatomy of Their Economic Problems[END_REF], [START_REF] Kaldor | Causes of the slow rate of economic growth in the United Kingdom[END_REF] and [START_REF] Baumol | Macroeconomics of Unbalanced Growth[END_REF]. It is easy summarized as follows: "a transfer of resources from manufacturing to services may provide a structural change burden" (Szirmai and Verspagen, 2015: 47). In recent years, the speed of technological progress increased vigorously, and many scholars started to speak in terms of robotization and danger of a jobless growth.

Simultaneously, financialization emerged as a phenomenon which creates strong dependencies, in advanced economies, from the financial sector. According to critical political economists, financialization may have negative impact on labor productivity, because financial managers and financial corporations are more interested in maximizing their bonuses, shareholders' dividends and financial compensation rather than in embarking on strategies oriented towards productive investments [START_REF] Lazonick | Maximizing Shareholder Value : A New Ideology for Corporate Governance[END_REF][START_REF] Palley | From Financial Crisis to Stagnation: The Destruction of Shared Prosperity[END_REF][START_REF] Lavoie | Post-Keynesian Economics: New Foundations[END_REF]. In this context, assets are wasted in financial speculation and short-term strategies rather than being used for real investment expansions, innovation, job creation and labor productivity gains. Moreover, labor markets became more flexible, and jobs often unprotected, with the danger for "the integrity of employment and social protection regimes", and more in general for the European and other advanced economic systems of industrial relations (Prosser, 2014: 359), mainly due to the looming threat of job relocations, the weakening of labor bargaining power and trade unions, in the context of globalization, vis-a-vis capital.

The aim of this special issue is clearly to show these issues in diverse countries according to their initial specialization, their path dependency and institutions. Structural changes do not have the same impact and outcomes for Eastern or Western countries in Europe as they experienced distinct coevolution of technology and institution that shaped the contours and limits of these dynamics.Welfare models, and the institutions at the basis of the varieties of capitalism and of welfare policy may affect these processes. For instance, some European continental countries, have avoided, to a large extent, the pre-mature de-industrialization and have continued to invest in manufacturing and in capital intensive sectors rather than in services and finance. Scandinavian countries, have managed to drive the transition towards a service sector dominated by public administration employment and social services of higher quality and standards, resulting in benefits in terms of productivity and wages.

Other countries have experienced both de-industrialization and financialization, along with robotization, but also ecological transition. Finally, other countries embarked a transition towards low skilled manufacture sectors, or low skilled sub-sectors in the service with low productivity gains and low wages and experiment various ways to integrate (or not) environmental in their productive systems. This variation, which is not even exhausting the different possibilities of transitions, offer opportunities of analysis, of studies, comparisons and of empirical reflections, as well as theoretical formulations beyond the current state of the art and the mainstream approaches.

Finally, climate change and sustainability constraints create burdens for the manufacture sector, which is considered more polluting than others. In this context, rules, institutions and governance are needed more than ever, to create the right incentives and the appropriate coordination among agents for embarking a sustainable path of development and have decent jobs. Sustainability, however, needs to be understood not only in terms of environmental sustainability. It should encompass also social sustainability, avoiding inequality and poverty as well as macroeconomic sustainability (or stability) avoiding boom and boost and financial euphoria and panics. About consumption, neoclassical economic models still dominate research on sustainable consumption, representing consumers as substantively rational individuals that make deliberate and autonomous decisions to maximize their individual utility based on stable and exogenous preferences and perfect information. However, a vast, but scattered, interdisciplinary literature -including sociology, behavioral economics, evolutionary economics, psychology and anthropology -provide many new insights for explaining sustainable behavior and structural changes needed in this field [START_REF] Axsen | Social Influence, Consumer Behavior, and Low-Carbon Energy Transitions[END_REF][START_REF] Cordes | Technological diffusion and preference learning in the world of Homo sustinens: The challenges for politics[END_REF][START_REF] Babutsidze | Look at me Saving the Planet! The Imitation of Visible Green Behavior and its Impact on the Climate Value-Action Gap[END_REF]. Indeed, changing consumption is as much dependent on the economic values of different consumers groups as on the capability of certain groups to convey new values and to co-opt new consumers, suggesting a potential place for learning sustainable consumption which may have an impact both at macro and micro levels [START_REF] Witt | The evolution of consumption and its welfare effects[END_REF]. The evolution of demand and consumption, analyzed already by Veblen, was further developed more recently, for instance based on work by U. Witt and others (e.g., [START_REF] Witt | The evolving economy: essays on the evolutionary approach to economics[END_REF][START_REF] Witt | What is specific about evolutionary economics[END_REF]Lazaric et al. this volume). An evolutionary economics of consumption and demand scrutinizes preferences and values, which is symptomatic of evolutionary research responding to contemporary problems (e.g., [START_REF] Buensdorf | Can sustainable consumption be learned? A model of cultural evolution[END_REF][START_REF] Cordes | Technological diffusion and preference learning in the world of Homo sustinens: The challenges for politics[END_REF][START_REF] Cordes | The promises of a naturalistic approach: how cultural evolution theory can inform (evolutionary) economics[END_REF]. This includes research within interdisciplinary so-called naturalistic perspectives, for instance on learning and transmission processes of new behavior, such as in consumption qualified as "green". Work along these lines also makes evident the pertinence of environmental questions, which may become the new battle horse of evolutionary-institutional approaches as much as innovation and consumption, all in both research and policy (e.g., [START_REF] Maréchal | Overcoming inertia: insights from evolutionary economics into improved energy and climate policy[END_REF][START_REF] Brouillat | Dynamic efficiency of extended producer responsibility instruments in a simulation model of industrial dynamics[END_REF]. With respect to innovation, the long-standing lack of a critical stance towards innovation, failures to link innovation to social inclusiveness and ecological sustainability, and the reluctance to think about innovation in terms of governance should be taken more seriously and reflects one direction for shaping these structural changes (e.g., Metcalfe et al., 2005, Gifford and[START_REF] Gifford | Knowledge-Intensive Entrepreneurship and S3: Conceptualizing Strategies for Sustainability[END_REF][START_REF] Savona | Structural changes and sustainability. A selected review of the empirical evidence[END_REF].

In this special issue, papers discuss sources of these structural changes with three axes.

The first axis explored the discussion around the complementarity between Keynes and Schumpeter.

Pariboni and Tridico's article explores the famous Baumol's disease and the productivity slowdown in capital accumulation. Following Sylos Labini's insights, they show with a panel data of 25 European countries, that the increase part of services and the transfer of resources from manufacturing to services may provide a structural change burden with little room for productivity gains and labor productivity. This process of change affects both structures and international division of labor. If the schumpetarian dynamics is important for generating innovation, for accelerating growth and productivity path, fiscal policies and sitmuli to demand are necessary. In short the keynesian engine is a natural engine to the schumpetarian dynmics and may correct some negative externalities of these sctructural changes linked to the creative destruction.

In the same vein, Saviotti et al's article ( this volume) shows the nature and the complexity of this structural change. Structural change may be a mechanism of growth that enables continuition of growth in the long run with the hypothesis of increasing return [START_REF] Young | Increasing Returns and Economic Progress[END_REF]. In this case structural change depends on the efficiency and creativity trade off. Efficiency operates on all existing porccesses and reduces the amount of outputs to produce a qualitative constant of output. Creativity generates new goods and services that change the economic structure of the system. Both efficiency and creativity are required to drive change in the structure of the economic systems. The nature of these changes will depend on the combination of two scenarios (low quality -with only an inter sectorial diversification-and high quality with an inter and intra sectorial diversification-).

With a focus on the nature and the content of sustainable conumption, Lazaric et al., explore the main determinants of sustainable consumption in France.Their emripical findings illustrate at meso and microlevel how to define sustainable consumption and to build some indicators. Based on a cluster methodology from the" highest" to" lower" level of sustainable conumption, they show the diffisuion of environmental values and social influences among consumers. While their result show significant amount of inequalities towards sustainable consumption (according age, gender issues, income and localization), empircal findings illustrate also how sustainable consumption is learnt through a process of peer's pressure producing local interactions and opportunities to learn with those around you and who matter ( friends, family, colleagues). In others words the weight of small networks has a huge impact on sutainable consumption and reinforces pre-existing path and prior green preferences. This local path dependency and local interactions show also the difficulty to changes consumption pattern and the need of policy makers to act in this direction to correct inequalities in consumption and to include inclusiveness for providing an equal access to citizens to learn about sustainability while providing an access to green products and practices.

The second axis of papers discuss the impact of financialization and its change. Imami et al's paper ( this volume) show more precisely after the collapase of the socialist system, a change in the informal systems of finances. These informal sytems such as rotating saving and credit schema have been diffused have bee very important in many countries and socialist countries stimulated by a lack of access to loans. In the absence of private banks and with restriction on loans by state Banks, this informal finance became a useful instrument for meeting different households needs during socialism period and in context of centralized State where any deviation to legal and idelogical frame would be punished. During the post socialist and the transition peirod, these tools decrease with the emergence of an increase mobility of people, job insecurity, and an increased level of distrust among citizens generating a new form of reluctance towards these ancient monetary tools.

In the different direction, Perillo and Battiston ( this volume) explain the dramatic accelerator of the finance growth in Western countries. This financialization of the economy has two sources: 1) the provision of credit and financial services to the economy and to housheolds; 2) the striking growth in assets management activities and profits. They explain why the common view that financialization was good for the economy and economic growth has changed after the 2007-2008 crisis and the post recession with rising of inequalities as an important structural change, also raised by Jacobs and Mazzucato (2016). In this context, their empirical analysis show the implication of an unconventional financial tool :the QE (quantititive easing) implemented by the European Central Bank, with possible positive development for the economic sphere and the change in the bank's borrowing behaviour.

They scrutinize the impact of this new tool for creating additional resources to the real economy and implications in terms of financialization ( intra financial exposure and among financial actors).

The third axis of this special issue explores impacts of these strutcural changes according from diverse clusters of countries. Deleidi et al., ( this volume) illustrate these trends with nine selected countries from the period of 1970-2015. Their results show that the stagnation of the labor productivity is explained by a small increase within sector and structural change towards service sectors and show the tertiarization 's trend. They assess the weight of structural change within sector and across sectors affecting the weight of the overall productivity dynamics. Testing the impact of demand factor on the within productivity growth with use the Kaldor Verdoorn law, they assess the small role of the tertiarization in the recent period (1999)(2000)(2001)(2002)(2003)(2004)(2005)(2006)(2007)(2008)(2009)(2010)(2011)(2012)(2013)(2014)(2015), and the role of demand growth for determining productivity dynamics in manufacturing and private sector of the economy. The poor dynamics of demand after the 2008 crisis has contributed to productivity stagnation especially in large economies and countries with larger manufacturing sector. Gräber et al. article worth to be noticed here. This paper that received the EAEPE Kapp Prize in 2020 for its originality and quality of its empirical findings, harmoniously combines post keynesian insights with the notion of path dependency to illustrate diversity and distinct ways among countries to respond to the openness shock imposed by the European integration. Four clusters have been identified: core, periphery, catchup countries in Eastern Europe and financial hubs countries. They demonstate the uneven distribution of technological capabilities for understanding the core periphery duality and show, more generally, the relationship between positive change and product complexity and the importance of accumulating technological capabilities. Given the fact that the accumulation of these capabilities is a path dependent processs, with the absence of policy intervention these trajectories are self reinforcing accross time. A policy response will be to support more convergence within Europe though institutions to rebalance the position of leaders with the position of laggards.

This could be done with institutions more inclusive contributing to increase convergence of living standard in the Union. Finally Pusch's paper ( this volume) scrutinizes the impact of the minum wage in Germany and observes two groups of firms a group A affected by the minimum wage and a group B with all firms that pay wages above the minimum wage level. Their results show a very low overall employment loss in sector A, a small shift from low wage industries to higher wage industries ( from sector A to sector B) and more generally the minimum wage is most likely to be negligeable and provide no contractionary monetary reactions. The introduction of a binding minum wage which has caused a small shift from sector A to sector B has created an overall drop of 0, 1 % of jobs and a drop of a number of "mini job"s and produced a new area for a re-regulation of industrial relations in Germany in favour of supporting demand.


Marc Schoenauer

Edmund Ronald

Genetic Extensions of Neural Net Learning: Transfer Functions and Renormalisation Coefficients

This paper deals with technical issues relevant to arti cial neural net (ANN) training by genetic algorithms. Neural nets have applications ranging from perception to control; in the context of control, achieving great precision is more critical than in pattern recognition or classi cation tasks. In previous work, the authors have found that when employing genetic search to train a net, both precision and training speed can be greatly enhanced by an input renormalisation technique. In this paper we investigate the automatic tuning of such renormalisation coe cients, as well as the tuning of the slopes of the transfer functions of the individual neurons in the net. Waiting time analysis is presented as an alternative to the classical "mean perfomance" interpretation of GA experiments. It is felt that it provides a more realistic evaluation of the real-world usefulness of a GA.

1 The Usefulness of Automatic Parameter Tuning

The operator of a heuristic program spends a lot of time predicting what his program will do. Now and then a test run actually validates the programmer's prediction and life, science, and everything is wonderful { yet more often, the program goes o to do its own thing and the programmer is left to scratch his head.

In this context, manual tuning of parameters is one of the least rewarding facets of heuristic programming. For instance, the authors have spent hours in front of computer screens, when investigating neural net training. These hours were occupied by running the same program time and again with just the change of a single real parameter like the slope of the neural transfer function.

Computer programming is of necessity experimental; however every worker in the eld of genetic algorithms has been brought to conjecture that the experimenter's action could be automated. In the case of GA research, the manual variation of GA parameters {eg. search for good mutation or crossover rates { could be replaced by the action of a meta-GA. Unfortunately, the computational expense of running a population of GA's in parallel usually discourages the GA experimenter from pursuing such a course of automatic experimentation, although object-oriented software engineering makes a 2-level GA easily feasible. Indeed, the possibility of running a meta-GA is a design goal of the authors' next generation GA software.

In the special case of the authors' research in neural net control, some of the parameters originally subject to tuning could be varied by the same GA employed to train the net by searching the space of weight matrices. In this document the results of this automated research is confronted with the results originally published in Ronald & Schoenauer 93] .

In summary, by confronting the results of our previous work with this automated tuning by GA, we show that the GA improves on a human operator in tuning some of the net parameters, namely the transfer functions. On the other hand, automatic renormalisation, as presented in section 5 does not improve mean precision, and indeed produces barely acceptable results; but it holds the promise of obsoleting the painful data pre-processing steps which hinder real-world and industrial applications of neural nets.

We have included a waiting-time interpretation of our results; we believe that this interpretation methodology, while unusual, is more appropriate in an industrial context than mean performance: GAs are stochastic, and estimations of their performance must perforce be formulated in probabilistic terms. A waiting time estimation provides us with a con dence factor whereby a control problem can be solved with a predetermined amount of computation.

The plan of the paper follows: In section 2 below we recall the neural net formalism and its application to control, and summarise earlier work. Section 3 presents an investigation into the automatic tuning of the neural transfer function slopes. Section 4 introduces the waiting time analysis, and applies it to the results of section 3. Section 5 describes experiments in generalised tuning of both data renormalisation coefcients and transfer functions. Section 6 discusses the signi cance of the results, and highlights some possible applications.

Genetic Training of Neural Net Controllers

In order to make this paper self-contained, this section summarises the methods employed by the authors for neural net control in Ronald & Schoenauer 93], Schoenauer & Ronald 94]. This establishes the background for the numerical experiments on the lunar lander simulator, whose results form the body of sections 3 and 4 below. The reader desiring an overview of the eld may refer to Yao 93], a broad survey of evolutionary methods as applied to neural net training and design.

Lunar lander dynamics

This paper deals with training a neural net to land a simulated rocket-driven lunar-lander module, under a gravity of 1.5 m=s 2 . This simulation has given rise to numerous computer games since the advent of interactive computing, and will be familiar to most readers.

The lunar module is dropped with no initial velocity from a height of 1000 meters. The fuel tank is assumed to contain 100 units of fuel. Burning one unit of fuel yields one unit of thrust. Maximum thrust is limited to 10 units and the variation of the mass of the lunar module due to fuel consumption is not taken into account. The simulation time-slice was arbitrarily xed at 0.5 seconds. All the experiments reported i this document were conducted with the given initial height; the net can be trained to solve the general control problem by the expedient of supplying random starting points. However such training was deemed too expensive computationnally to allow for the exhaustive experimentation whose results are reported here.

The input parameters relayed to the neural net once every time-step are the speed, and the altitude. The net then computes the desired fraction of maximal thrust, on a scale from 0 to 1, which is then linearly rescaled between 0 and 10 units. A very nice lunar landing e ected in this study is shown in Figure 1. This achieved a landing speed of 7 10 7 m=s, ie. 0:7mm=s, hardly enough to mark the lunar surface! Such excellence would hardly be necessary in practice. This result was obtained by straightforward application of neuro-genetic control, with no data renormalization.

It was attained at the price of a long run, namely almost 2000 generations. The control action is also exemplary in the economy of fuel in the deceleration phase: For the main deceleration burst, thrust is pulsed in what amounts to almost a square wave to its maximal permissible value. The remarkable landing softness is attained by means of a long -and very smooth-hover phase which begins immediately after deceleration.

The best landing we achieved in this study is shown in Figure 1. The landing speed of 7 10 9 m=s, ie. 0:002mm=s is a 2 orders of magnitude improvement over the previous result, and was attained in half as many ( 1035) generations. This is an achievement of data renormalisation: The net was presented with the two previously cited state inputs, namely speed and altitude, and another pair consisting of the same variables pre-multiplied by a factor of 10. The interesting features of the best "Armstrong", as displayed in Figure 2, are its surprising precision, and the fact that this precision is attained either in spite of, or more probably, because of the displayed sawtooth shape and roughness of the thrust control. Of course, control by rocket to t a speed tolerance of 20 Angstroms/s seems rather implausible in reality.

The Networks

A classical 3-layered net architecture was employed, with complete interconnection between layers 1 and 2, and 2 and 3. The neural transfer function (non-linear squashing) was chosen to be the usual logistic function F, a sigmoid de ned by F(x) = 1 1+e x

In our work the parameter was xed, = 3:0.

Each individual neuron j computes the traditional PDP] squashed sum-of-inputs o j = F( P i w j i x i )

Regarding the sizing of the middle layer, we chose to apply the Kolmogorov model Hecht-Nieslen 90] which for a net with n inputs and 1 output requires at least 2n+1 intermediate neurons.

Only two net architectures occur in this paper. Both types have only one output (controlling the lunar module's thrust). The canonical method for solving the control problem entails 2 inputs, namely speed and altitude, appropriately normalised between 0 and 1. However, the optimisation by input renormalisation which forms the core of Ronald entails adding two inputs to the above cited net, therefore employing 4-input nets. As in both cases we have adhered to the Kolmogorov paradigm, we are studying 2-5-1 and 4-9-1 nets, which respectively have 21 and 55 weights/biases. With the topology xed, training these nets for a given purpose is a search in a space of dimension 21 or 55, to which must be added real numbers representing the parameters , and those for the renormalisation, when these parameters are left to the GA to nd. In the neuro-genetic approach, net training is thus a search in a 21 or 55-dimensional space, to which must be added real numbers representing the parameters , and those for the renormalisation, when these parameters are left to the GA to nd.

The Genetic Model

Our genetic algorithm software subjects a small population of nets to a crude parody of natural evolution. This arti cial evolutionary process aims to achieve nets which display a large tness. The tness is a positive real value which denotes how well a net does at its assigned task of landing the lunar module. Thus our tness will be greater for slower landing speeds. The details of the calculation of the tness are found below.

For the purpose of applying the genetic algorithm, a net is canonically represented by its weights, i.e. as a vector of real numbers. During the initial stages of this work, two distinct homebrew GA software packages were employed. One package followed the rst methods presented by John Holland in that it uses bitstrings to encode oating-point numbers. The second software package, described below, was a hybridized GA which directly exploits the native oating-point representation of the worktations which it was run on. The hybridization towards real numbers is described in Radcli e 91] and Michalewicz 92]. The results obtained with both programs were consistent, and only the experiments with the oating point package are detailed in this document.

The genetic algorithm progresses in discrete time steps called generations. At every generation the tness values of all the nets in the population are computed. Then a new population is derived from the old by applying the stochastic selection, crossover and mutation operators to the members of the old population.

Selection is an operator that discards the least t members of the population, and allows tter ones to reproduce. We use the roulette wheel selection procedure as described in Goldberg 89], with tness scaling and elitism, carrying the best individual over from one generation to the next. Crossover mixes the traits of two parents into two o spring. In our case, random choice is made between two crossover operators: Exchange of the weights beteween parents, at random positions. Or assigning to some of the weights of each ospring a random barycentric combination of its parents' weights. Mutation randomly changes some weights by adding some gaussian noise. The experiments described in the next section used the following parameters in the GA: The net connection weights forming the object of the search were conned to the interval 10; +10] thereby avoiding overow conditions in the computation of the exponential. Population size was held to 50 over the whole length of each run, tness scaling was set to a constant selecetive pressure of 2.0, crossover rate was 0.6, mutation rate 0.2, the gaussian noise had its standard deviation set to half the weight space diameter, ie. 10.0, decreasing geometrically in time by a factor 0.999 at each generation.

Adjusting Transfer Functions

The family of logistic transfer functions

A great deal of work in the neural net community has employed logistic sigmoid transfer functions of the form

F (x) = 1 1 + e x
where the parameter , usually set to 1, can be seen to be de ning the slope of the function for x = 0, ie. = F 0 (0) In the gure below, we show the behaviour of F for values of , taken from the set f0:1; 0:5; 1:0; 2:0; 5g, with the slopes steepness increasing with from a quasi-linear function, through a sigmoid to a very steep staircase. In an analogy to biological systems, can be interpreted as a chemical parameter de ning the sensitivity of a neuron. However, researchers in back-propagation usually x this parameter, although Yao, in his survey Yao 93] cites Mani, as having experimented with a modi ed form of back-prop which performs gradient descent learning by adjusting the slopes as well as the synaptic connection weights themselves. However, Yao also cites Stork &al. 90] as having applied a GA approach to the de nition of both neural connectivity and transfer functions, an investigation similar to the one reported here.

Experimental Results

In our case, we investigated how allowing a GA to individually tune the transfer functions a ects the precision of control in the "genetic lander" experiment. Our results in allowing the GA to vary the slope for each individual neuron in the controller net may be compared with work reported in Ronald & Schoenauer 93], where the slopes of the transfer functions of all neurons were held constant at = 3 . In Figure 4 we have graphed the performance of the GA search, comparing the mean of a set of 60 1 runs of 2000 generations length with xed , as reported in Ronald & Schoenauer 93] with two new experiments of identical size. In these new experiments the GA was permitted to adjust the slope of each neuron, within the limits indicated in the gure.

Generations

It can be seen that the mean maximum precision of the runs greatly improves when the GA is allowed to search a larger range of slopes. The computational cost involves adding just one degrees of freedom per intermediate and output layer neuron, and can thus be considered negligible. In summary, we nd the technique of varying the slopes fully successful here, and we believe it deserves to be investigated in other contexts.

Waiting Time Estimation

In the real world, a user who wishes to exploit a GA for a given task is not interested in average performance over a number of runs { she may rather wish for an estimation of how much it will take to achieve a result of a given quality: Such a result is an acceptable solution to the control problem, which can be acted upon. Now, if we assume a really bizarre genetic algorithm which yields a very bad result eg a crash at 10 m/s for half the random seeds, and an excellent result eg. 10e-3 m/s for the other half, then the average result is a 5 m/s crash! However, just a very few runs of the algorithm will usually yield one of the "good" controllers, capable of piloting a safe ight.

We may wish to formalize the above reasoning by asking the following question like someone who must run the GA in batch processing: If I know that on average a runs yields an acceptable result with probability a, then how many runs N must I schedule in order to have probability p or more of nding a good run in the schedules runs?

Elementary probability theory tells us that the condence number N(p,n) is given by the equation N(p; n) >= log(p)=log(1 a)

In the above formula we my assume any desired base for the logarithm. Hence for instance in the example, with a =0.5, and p=0.001 we can approximate in our heads that p = 2e 10 , and hence N = 10= 1 = 10 . The results of comparing the graphs in Figures 4 and5 { created from the same experimental data { are nothing short of amazing! When we peer at gure 4, the mean landing speed of the 60 runs of 2000 generations' duration never reaches 10e 3. The waiting time graph in gure 4 however tells us that 10e 3 is a soft landing which we can reach with a con dence factor of 99% by e ecting just 10 runs of 500 generations duration! The waiting time graph can be interpreted as showing that precisions of 10e 4 are perfectly attainable in practice with any of the investigated learning methods, be it manual or automatic tuning of the slopes.

Generalised Tuning

In gure 6 below we have reproduced the waiting time graph obtained from 4 experimental batches of 60 runs each, with and without GA search for input renormalisation coe cients. It can be seen that having no renormalisation at all is better than leaving the search of renormalisation coe cients entirely to the GA to nd in an interval 1e 10; 1e + 10].

However, these results may be considered less discouraging when the reader is told that the inputs for "full genetic renormalisation" were not preprocessed in any way! Thus the neural net, as trained by the GA, was left to deal with input values of eg. starting altitudes of 1000 m/s and free-fall speeds to 500 m/s, whereas in all other experiments neural input data had been folded (by hard code) into 0; 1]. Hence the "full genetic renormalisation" results are still promising -they yield a case of functional albeit imprecise control, as might be exploited by a prototype application. However such a prototype is obtained without any human expertise whatsoever being applied in the problem-domain.

In this way one might imagine this "full genetic renormalisation" experiment to represent an industrial context, in which a feasibility study would be done for GA learning, without any prior attempt at data pre-processing. The authors would not believe their lives in danger even if landing is e ected at 10 cm/s which the graph shows the GA-trained nets routinely achieve. Of course, a hand{tuned net able to land at 10e-7 m/s or so, would be more appropriate for piloting the director of a funding agency visiting a scienti c lunar base. The results of the numerical experiments reported in this paper are mixed. On the one hand our data indicates that the slopes of the neural transfer functions can be pro tably trained by the same GA which trains the net. On the other hand the experiments on training renormalisation coe cients by GA proved surprisingly disappointing, and will be investigated further. This should be contrasted with past experiments in which tuning these coe cients by hand yielded excellent results.

Required precision

The waiting time metric which we in introduced in section 3 above seems more suited to the logic of industrial application of GA control than the more conventional mean performance metric. Moreover, the counter-intuitive nature of this metric might inspire some statistical re{interpretation of existing data. Indeed, it may be pro table to unearth old experiments, deemed failures by the mean tness method, and reevaluate them. Let us remember the dictum of Edgar Allan Poe, that there be lies, damned lies, and statistics!

Figure 1 :

 1 Figure 1: Best non-normalised control action in study.

Figure 2 :

 2 Figure 2: Best overall control action in study.

  Fig 4. Mean performance with varying

Fig 5 .

 5 Fig 5. Waiting time estimation with varying

Fig 6 .

 6 Fig 6. Waiting time estimation with varying and renormalisations