Marco Montemurro

Paolo Vannucci

Angela Vincenti

BIANCA, A Genetic Algorithm for Engineering Optimisation -User guide

come   L'archive ouverte pluridisciplinaire

The genetic algorithm (GA) BIANCA 3.1 is a multi-population GA able to deal and solve constrained and unconstrained hard combinatorial optimisation problems in engineering. The effectiveness and robustness of BIANCA reside upon the generality and richness in the representation of the information, and on the way the information is extensively exploited during genetic operations. For more details see [START_REF] Vincenti | Conception et optimisation de composites par mèthode polaire et algorithmes génétiques[END_REF][START_REF] Vincenti | Bianca: a genetic algorithm to solve hard combinatorial optimisation problems in engineering[END_REF].

In its previous version, BIANCA was a GA substantially based on the principles of the standard GA, see Fig. 1.1. Nowadays, BIANCA is a powerful modular numerical tool, able to deal with general problems of engineering optimisation. The version 3.1 of BIANCA tool-kit provides a flexible, extensive interface between the user simulation code and a variety of iterative methods and strategies.

Moreover, the version 3.1 of the code goes beyond the structure of the standard GA: this version, in fact, is able to let evolve individuals and species at the same time: this is an important feature that makes BIANCA able to deal with optimisation problems concerning modular systems/structures, such as composite plates or shells, stiffened panels and so on. Optimising modular systems with variable number of modules using a GA corresponds to the evolution of a population where individuals/points belonging to different species are mixed. The most part of standard GAs are not able to deal with such problems. For a deeper insight the matter see [START_REF] Montemurro | Design of laminate's elastic properties with minimum number of plies[END_REF][START_REF] Montemurro | A genetic algorithm with cross-over on species for structural optimisation[END_REF]. BIANCA is written in FORTRAN language.

Background and mathematical formulations

A general optimization problem is formulated as follows:

min x f (x)
subject to :

   g i (x) ≤ 0 i = 1, ..., r h j (x) = 0 j = 1, ..., m x L ≤ x ≤ x U (1.1) where vectors and matrix terms are marked in bold typeface. In this formulation x is the n-dimensional vector of design variables, while x L and x U are the n-dimensional vectors representing the lower and upper bounds of the design variables, i.e. the design space. Design variables can be of different type: continuous, regular discrete, scattered discrete or grouped. The optimisation goal is to minimize the objective function f (x) subject to a given number of constraints: g i (x) is the r-dimensional vector of inequality constraints, while h j (x) is the m-dimensional vector of equality constraints.

The optimization problem type can be characterized both by the types of constraints present in the problem and by the linearity or non-linearity of the objective and constraint functions. A problem where at least some of the objective and constraint functions are non-linear is called a non-linear programming (NLPP) problem. These NLPP problems predominate in engineering applications and are the primary focus of BIANCA 3.0.

In BIANCA the equality and inequality constraints are treated by means of a particular strategy which is based on the combination between classi-cal penalisation methods and the exploitation of the distributed information over the population along the generations. The name of this technique is ADP, which stands for Automatic Dynamic Penalisation. Classical penalisation methods transform Eq.(1.1) into an unconstrained optimisation problem through the definition of a new modified objective function F (x):

min x F (x) F (x) =              f (x) if g k (x) ≤ 0 k = 1, ..., r
and h j (x) = 0 j = 1, ..., m

f (x) + r k=1 c k G k (x) + m j=1
r j H j (x) if g k (x) > 0 k = 1, ..., r and h j (x) = 0 j = 1, ..., m (1.2) In Eq.(1.2) c k and r j are the penalisation coefficients for inequality and equality constraints respectively. The quantities G k (x) and H j (x) are defined as:

G k (x) = max [0, g k (x)] k = 1, ..., r H j (x) = max [0, | h j (x) | -ǫ] j = 1, ..., m (1.3)
In Eq.(1.2) and (1.3) the equality constraints have been transformed into inequality constraints having the form | h j (x) |≤ ǫ. Concerning the parameters c k and r j , in classical penalisation methods, the user must set their values to an appropriate level in order to ensure the search of solutions for the optimisation problem to be forced within the feasible domain. Nevertheless, the choice of these coefficients is very difficult and it is common practice to estimate their values by trial and error. Moreover, it could be useful to adjust penalisation pressure along the generations by tuning these coefficients, but this is directly linked on a guess or on a deep knowledge of the nature of the optimisation problem by the user. The idea of the ADP is that it is possible to exploit the information restrained in the population, at the current generation, in order to guide the search in the case of constrained optimisation problem. Generally, in the first generation the population is generated randomly. With high probability the individuals are evenly distributed over both feasible and unfeasible domain and the corresponding values of objective functions and constraints can be used to estimate an appropriate level of penalisation, i.e. the values of penalisation coefficients c k and r j . At the current generation, inside the population it is possible to separate feasible and unfeasible individuals and it is also possible classify each group in terms of increasing values of the objective function or constraint violation. The first individual in each group is the best candidate to be solution of the optimisation problem on the feasible and unfeasible side of the domain, respectively. One possible definition of the penalisation coefficients is the follow:

c k (t) = | f best F -f best N F | G kbest N F k = 1, ..., r r j (t) = | f best F -f best N F | H j best N F j = 1, ..., m (1.4)
In Eq.(1.4) the coefficients c k and r j are evaluated at the current generation t, while the apexes F and N F stand for feasible and non-feasible respectively. It is clear that the estimation of penalisation coefficients, according to the Eq. (1.4), can be repeated at each generation, thus tuning the appropriate penalisation pressure on the current population. The main advantages of this approach are substantially two: first of all this procedure is automatic because the GA can automatically calculate the values of the penalisation coefficients, secondly the method is dynamic since the evaluation of the penalisation level is updated at each generation.

General features of BIANCA

The version 3.1 of BIANCA shows several original features. As well as the previous version, one of the main features is the decomposition of the GA in a certain number of macros: it is possible to assembly them in various ways in order to suit many different optimisation problems and also to test and compare the effectiveness of different numerical strategies. In this sense, BIANCA is a bunch of genetic tools which the user can use as bricks to build up several GAs. Another important feature of BIANCA is the representation of the information which is rich and detailed, but also non redundant. The biological metaphor in GAs is a simple but powerful mean to return the richness and completeness of information linked to design variables. The information restrained in the population along the generation is treated in a peculiar manner in such a way to allow a deep mixing of the individuals' genotype by means of the reproduction operators, i.e. cross-over and mutation, which act on every single gene of the individuals. For a deep insight the matter see [START_REF] Vincenti | Bianca: a genetic algorithm to solve hard combinatorial optimisation problems in engineering[END_REF].

In order to allow the reproduction phase among individuals belonging to different species, in BIANCA 3.1 the structure of the individual and, con-sequently, the representation of the information as well as the reproduction operators of cross-over and mutation have been modified in order to deal with the optimisation problem of modular systems. We have introduced new genetic operators in BIANCA 3.1 for cross-over and mutation of individuals belonging to different species. BIANCA 3.1 has the following qualities:

• objective function evaluation: a library of functions corresponding to objective and constraint functions of different optimisation problems, in addition in BIANCA the user can write its model by means of a special macro;

• fitness evaluation: several choices are available for fitness evaluation depending on the kind of problem, i.e. minimisation or maximisation, and on the selection pressure that the user decides to introduce. The fitness is evaluated in such a way that the fitness function can assume all the possible values in the range [0 1];

• selection: two known techniques of selection are included, i.e. roulette wheel, tournament;

• standard genetic operators: the main genetic operators are cross-over and mutation, applying with a certain probability on each gene of the individual's genotype;

• additional genetic operators: elitism operator which preserve the best individual during each generation;

• handling constraints: automatic dynamic penalisation method for handling constraints;

• handling multiple populations: the need to simultaneously explore different regions of the design space, as well as the search of optima responding to distinct design criteria, led us to introduce the option of working with multiple populations in BIANCA. Moreover, a migration operator has been introduced in order to allow exchanges of informations between populations evolving through parallel generations. This migration operator is the classical ring-type.

• stop criterion: maximum number of generations reached or test of convergence, i.e. no improvements of the mean fitness of the population after a given number of cycles.

• new genetic operators: to deal with the problem which considers the number of variables among the optimisation variables, as in the case of modular systems, new genetic operators have been developed, such as the chromosome shift operator, the chromosome reorder operator, the chromosome addition/deletion operator. These new operators modify the reproduction phase allowing the reproduction among individuals of different species, see [START_REF] Montemurro | Design of laminate's elastic properties with minimum number of plies[END_REF];

• interface with external software: if the model to be optimised is written in an external environment, it is possible to call it by BIANCA 3.1 in order to evaluate the objective function and constraints, and then to pass the design variables to the model. The logical scheme of the structure of the interface is shown in Fig. 1.2.

• post-processing of results: graphical results concerning the trend of the best feasible solution and the average value of the objective function along the generation are obtained through the creation of a .m file (by means of MATLAB R environment) that reads the output files of BIANCA 3.1.

The structure of the individual's genotype

The biological metaphor in GAs is a simple but powerful mean to return the richness and completeness of information linked to design variables. The necessity to deal with any type of design variables, i.e. continuous, discrete, scattered led us to the choice of a discrete representation of the information.

As explained in Sec. 1.5, it exits a two-way relation among the variables and the pointers, i.e. integer numbers, which refer to the set of feasible discrete values for each variable. In a standard GA it is usual to encode integer values in the form of binary strings, in order to use the minimalist alphabet which increases the number of schemes, according to the theorem of the implicit parallelism that ensures improvement of the exploration of the domain and exploitation of information [START_REF] Goldberg | Genetic algorithms[END_REF][START_REF] Michalewicz | Genetic algorithms + data structures = evolutionary programming[END_REF]. In addition the use of binary representation allows the use of binary cross-over and mutation which are very effective when dealing with particular classes of optimisation problems.

In the previous version of BIANCA, an individual was represented by an array of dimensions n chrom × n gene . The number of rows, n chrom , is the number of chromosomes, while the number of columns, n gene , is the number of genes. Basically, each design variable is coded in the form of a gene, and its meaning is linked both to the position and to the value of the gene within the chromosome. In principle, no limit is imposed on the number of genes and chromosomes for an individual in BIANCA. A number n ind of individuals compose a population, and in BIANCA it is possible to work, at the same time, with several populations whose number, n pop , can be defined by the user.

In order to include the number of chromosomes (i.e. of design variables) among the design variables, and then to allow the reproduction among individuals belonging to different species, some modifications of the individual genotype have been done. In BIANCA 3.1, the genotype of each individual is represented by a binary array shown in Fig. 1.3. In this picture, the quantity (g ij ) k represents the j th gene of the i th chromosome of the k th individual. Letter e stands for empty location, i.e. there is no gene in this location while n k is the k th individual's chromosomes number. It appears clearly that every individual can have a different number of chromosomes, i.e. each individual can belong to a different species. As an example, for a composite laminate, one can assume, as design variables, the layers number, orientation angles and thickness. The information structure (i.e., in the GA's language, the genotype) of the individual-laminate is then structured as shown in Fig. 1.4. In this case the k th laminate's number of layers is n k while the orientation and the thickness of the i th ply are δ i and h i , respectively. One can notice that the number of layers n k is the number of chromosomes of the k th individual, while the orientation and thickness of the i th layer are the two genes of the i th chromosome.

Encoding/decoding of the variables

In BIANCA, the representation of the definition domain, i.e. the design space, of each design variable is made by the use of pointers, which are 1.5. ENCODING/DECODING OF THE VARIABLES themselves integer values. It exists a two-way relation between the variables and the pointers. This relation is clear in the case of discrete or grouped variables, in fact if the domain of definition have a finite dimension N , it is possible to enumerate all admissible values v i , (i = 1, ..., N ) and build a reference between each value v i and its index i, i.e. the pointer of that value. When the definition domain does not have finite dimension, it is necessary to restrict it, defining lower and upper bounds to the space of admissible values of v i , i.e. v min and v max respectively. In the case of continuous variables, the first step is the discretisation of the definition domain by choosing a given precision p, and then it is possible to apply the same system of referencing by pointers as for discrete and grouped variables, see Fig. 1.5.

In BIANCA pointers constitute the genotype of the individual, more precisely the single pointer corresponds to a gene, and all genetic operators are directly applied on the pointers representing the variables. Therefore, a step of decoding/encoding is necessary to translate the value of the pointer into the corresponding value of the design variable, and vice-versa. More details can be found in [START_REF] Vincenti | Conception et optimisation de composites par mèthode polaire et algorithmes génétiques[END_REF][START_REF] Vincenti | Bianca: a genetic algorithm to solve hard combinatorial optimisation problems in engineering[END_REF]. Chapter 2

BIANCA tutorial 2.1 Compiling BIANCA

The BIANCA batch file is named BIANCA 3.1.bat. You can compile BIANCA by a simple double click on this file. In the BIANCA 3.1 folder you must have the following files:

• libBIANCA.a: this is a library of BIANCA macros containing all the subroutines that BIANCA needs to run;

• MACRO MY PROBLEM.f95: this is the subroutine that you must use if you want to realise your model in FORTRAN environment as subroutine of BIANCA. The structure of this macro is explained in Sec 2.5.

After the compilation, the executable file BIANCAv3.1.exe is created.

Running BIANCA

The BIANCA executable file is named BIANCAv3.1.exe. You can run the code in two different way:

• by double click on the icon BIANCAv3.1.exe;

• by entering the command BIANCAv3.1 in the command prompt, after you have specified the correct path for BIANCAv3.1.

In both case, after the run of BIANCA, the code requires the specification of the name of the current job session. The choice of the job's name is completely arbitrary, but it must observe the following condition: the name of the current job session must be the same as the two input files with extension .gen and .opt, described in the following section.

CHAPTER 2. BIANCA TUTORIAL

Inputs to BIANCA

There are two different kind of inputs for BIANCA. In particular, the main inputs of the code are written in two input files with extension .gen and .opt respectively. As explained beforehand, these files must have the same name as the current job session. The input file with extension .gen contains the genetic parameters of the simulation, whilst the one with extension .opt contains the optimisation parameters. Moreover, in BIANCA there are two additional input files that have fixed name and structure, i.e. you can modify these input files but you can not change their name. These files are library.inp and post processing.inp and they contain the information about some library functions concerning the laminates' design (already implemented within BIANCA) and the information about the post-processing operations, respectively. In the following subsections the structure of all these input files is described in details.

Genetic parameters

As already explained, the input file with extension .gen contains the genetic parameters of the simulation. The structure of the file is defined below (we remark that each item-number in the list corresponds to the information restrained in a single line of the file):

1. n pop , number of population (integer), the maximum allowable number of population is 10; 2. n ind , number of individuals (integer), the maximum allowable number of individuals is 2000;

3. stop crit., stop criterion (character):

• fixed generations, to stop the GA after a given number of the generation;

• threshold, to stop the GA when the best individual satisfy the sill value on the objective function;

• mixed, is a combination of the two previous criteria;

4. in this line the user must write some values according to the stop criterion selected in line 3:

• n gen , number of generations (integer) if fixed generations;

• tresh, threshold value (double precision) if threshold ; • 0, the elitism is not applied;

•
• 1, the elitism is applied;

12. I time , isolation time (integer): when in line 1 n pop is greater then 1 you must choice this value. It represents the number of generation during which the populations are isolated. Every I time generations an exchange of the best feasible individuals among the populations is realised.

As example, we show here the structure of the .gen input file. In this example we use a single population with 100 individuals. The stop criterion is based on a fixed number of generations, i.e. the code stops the simulation after 200 generations; crossover probability is equal to 0.85, mutation probability is equal to 0.01, shift operator probability is 0.5 whilst the mutation probability of the number of chromosomes is 0.04. The selection operator is roulette wheel selection and it acts with a fitness pressure of 1.0. The elitism strategy is applied and the isolation time is set equal to 0 because in this example we have only one population.

Optimisation parameters

As said previously, the input file with extension .opt contains the optimisation parameters of the simulation. The structure of the file is defined below (we remark that each item-number in the list corresponds to the information restrained in a single line of the file):

1. EN V , flag variable (character) that denotes the type of the environment in which your physical model is realised:

• internal, if the model is realised in FORTRAN language as subroutine of BIANCA or if you want to use some internal function implemented within BIANCA ;

• external, for models realised in a different environment by means of external codes;

2. KIN DF , flag variable (character) that must be set only if you want to perform an optimisation with some functions already written within BIANCA or if you want to write your physical model in FORTRAN language (when in line 1 the internal option is active):

• test function, to access to the library of BIANCA test functions;

• library function, to access to BIANCA composite laminate function;

• my problem, if you want to write your physical/mathematical model in FORTRAN environment. The model must be written as subroutine of BIANCA;

3. CODE, flag variable (character) which must be set only if you want to perform an optimisation process on a model realised by means of external software (when in line 1 the external option is active):

• MATLAB, for models realised in MATLAB R environment;

• ANSYS, for models realised in ANSYS R environment;

• ABAQUS, for models realised in ABAQUS R environment; • 1, for maximisation;

• 2, for minimisation; 9. n obj , number of partial objective functions (integer). If your optimisation problem presents an objective function which is constituted by the sum of different terms, you can use this options in order to see the evolution of the different partial objectives along the generations. BEWARE: this options must be used when you want to perform an optimisation problem with the internal library function for the laminates' design of BIANCA, i.e. when in line 7 the function ID is 71 or 72. In this case the total objective function is composed by the sum of different terms and every one is linked to a particular elastic symmetry of the laminate. For more details see [START_REF] Vincenti | Conception et optimisation de composites par mèthode polaire et algorithmes génétiques[END_REF][START_REF] Vincenti | Bianca: a genetic algorithm to solve hard combinatorial optimisation problems in engineering[END_REF][START_REF] Montemurro | Design of laminate's elastic properties with minimum number of plies[END_REF][START_REF] Vannucci | Designing the elastic properties of laminates as an optimisation problem: a unified approach based on polar tensor invariants[END_REF]. The maximum allowable number of partial objective functions is 30; 10. IDCON ST R, ID for constraints (integer):

• 0, if constrains are inactive;

• 1, if constrains are active;

11. n constr , number of constraints (integer), the maximum allowable number of constraint functions is 30;

12. CHROM V AR, optimisation with individuals with variable number of chromosomes (character):

• yes, for individuals having different number of chromosomes;

• no, otherwise;

13. CHROM M IN exp, optimisation with minimum number of chromosome (character) and exponent of minimum chromosome function (double precision). BEWARE: this option must be set only when in line 2 the library function option is active and when in line 12 the yes option is active:

• yes p, if you want to perform the optimal laminates' design with the minimum number of plies and with an exponent p on the chromosome function;

• no 0.0, otherwise; LAST LINE : chromomask, chromo-mask (vector of integers). This mask denotes the position of the genes within the chromosomes of all individuals. This mask also shows the nature of the variable linked to each gene. This line is then constituted by a sequence of integer numbers, e.g. if in a given optimisation problem there are two different type of variables and two genes this line must be written in the following way: 1 2. Both variables are continuous, and we have defined their bounds. x 1 varies in a continuous way between 0.0 and 4π, while x 2 varies in a continuous way between 0.0 and 2π. Since there are two different types of variables the chromo-mask is made by two components 1 2.

Continuous

Concerning the meaning of the parameter n var , i.e. the number of different types of variables, and difference between this parameter and the number of genes n gene we show here below an example in order to understand in a better way how you must compile the .opt input file for this kind of situation: In this example we use an user self-created model, written in FORTRAN language as subroutine of BIANCA. The model has 1 objective function with 4 constraints. We want to minimise this function. The structure of the individual's genotype is made by 2 chromosomes with 3 genes, hence we have 6 design variables but only 2 different types of variables. The name of the first variable's type is angle while the name of the second one is height. The first type is continuous, whilst the second one is a discrete variable. We have also defined their bounds. angle varies in a continuous way between 0.0 • and 90 • , while height varies between 2.0mm and 5.0mm, with a discretisation step of 0.1mm. Since there are 2 different types of variables but 3 genes the chromo-mask is made up by 3 components: 1 2 1. The chromo-mask identifies the position of each design variable and also of each gene within the chromosome. So in this example each one of the two chromosomes, that constitute the genotype of the individual, is composed by 3 variables belonging to 2 different types: the first variable associated to the corresponding gene is an angle, e.g. α, and it varies between the bounds described by the variable type angle, the second variable is a height h and varies between the bounds described by the variable type height, while the third variable is also an angle, e.g. φ, which has a different physical meaning in our problem but that belongs to the same type of variable as the first one.

The library.inp file

The library.inp file must be compiled only when in the line 1 and line 2 of the .opt input file the options internal and library function are active, respectively. Moreover, in the line 7 of the .opt input file the only valid ID are 71 or 72.

The ID 71 identifies the problem of the optimal design of laminates' elastic symmetries with fixed number of plies, i.e. chromosomes: in this case the only design variables are the plies' orientations. The user must declare the bounds, and eventually the discretisation step, in degrees. A little remark occurs for this kind of design problem: the number of plies is equal to the number of chromosomes increased by one, e.g. when you set, in the .opt input file, the number of chromosomes equal to 10 you perform an analysis on a laminate with 11 layers, where the first layer has a fixed orientation equal to 0 • . An example of this kind of analysis can be found in Sec. 3.2.1. The ID 72 identifies the problem of the optimal design of laminates' elastic symmetries with variable number of plies, i.e. chromosomes: in this case you must perform an analysis with cross-over on species and the design variables are the plies' orientations and thickness. The user must declare the bounds, and eventually the discretisation step, of the orientations in degrees, while the ones of the thickness must be declared in mm. A little remark occurs for this kind of design problem: unlike the previous function ID, in this case the number of plies is equal to the number of chromosomes. An example of this kind of analysis can be found in Sec. 3.2.2.

The library.inp file presents a list of all the possible elastic symmetries of the laminate in terms of stiffness and compliance matrices. Each symmetry is characterised by a name, and every names are written in the file itself. You can copy the name of each symmetry over the line which contains the following words: Don't modify the following lines. You can see an example of the structure of this file in Fig. 2 BEWARE: the number of elastic symmetries must be equal to the number of partial objective function written in the input file with extension .opt at line 9. We show here below an example of the structure of both .opt and library.inp input files.

.opt input file In this example we want to find a laminate which posses the following elastic symmetries:

• elastic uncoupling;

• in-plane stiffness isotropy;

• bending stiffness orthotropy.

We use the internal function 71 and the objective function is made up by 3 partial objective: each one is associated to the symmetries cited beforehand. The number of chromosomes is associated to the number of plies (BEWARE, for the library function 71 the number of laminates'plies is equal to the number of chromosomes increased by one, so in this example we have 12 chromosomes and the laminate has 13 plies. In fact the first ply is CHAPTER 2. BIANCA TUTORIAL oriented at 0.0 • ). For each chromosome-ply we have one gene, i.e. one design variable: the angle which varies with a discretisation step of 5.0 • between -90.0 • and 90.0 • . We remark that the number of partial objective function is 3 and is equal to the number of the elastic symmetries written in the file library.inp.

The post processing.inp file

The post processing.inp input file contains several options that you can set if you want to perform the graphical post processing of the simulation's results.

Post processing operations are performed via MATLAB R software. At the end of the simulation BIANCA writes a file named graphic results.m which contains all the instructions for the plotting of the results. This file automatically reads the data restrained in the output files of BIANCA, whose structure is explained in the next Section. These MATLAB R instructions are strictly linked with what you write in the post processing.inp file. The graphical results that you obtain, after you have compiled in a correct way the post processing.inp input file, are substantially 2 files whose name is the same as the current job session preceded by the following words:

• obj min (job's session name) for the file which contains the plot of the best feasible solution vs. generations;

• obj mean (job's session name) for the file which contains the plot of the average value of the penalised objective function vs. generations;

The structure of the post processing.inp input file is defined below (we remark that each item-number in the list corresponds to the information restrained in a single line of the file):

1. P OST EN V , post processing environment (character). This is a flag variable that you must set if you want to activate the graphical treatment of results:

• M AT LAB, if you want to use MATLAB R package for the post processing of results;

• none, otherwise;

2. axis, flag variable (character) that allows you to choice the axis kind of the results' plot:

• linear, for a linear scale;

• semilog, for a semi-logarithmic scale;

3. grid, flag variable (character) that allows you to activate/deactivate the grid on the plots:

• on, grid is active;

• of f , grid is not active;

4. plot f ormat, flag variable (character) that allows you to choice the format for the simulation's plots:

• bmp, the graphical results are saved as Windows bitmap file;

• emf , the graphical results are saved as Enhanced metafile;

• eps, the graphical results are saved as EPS level 1;

• jpg, the graphical results are saved as JPEG image;

• pbm, the graphical results are saved as Portable bitmap;

• pcx, the graphical results are saved as Paintbrush 24-bit;

• pdf , the graphical results are saved as Portable Document Format;

• pgm, the graphical results are saved as Portable Graymap;

• png, the graphical results are saved as Portable Network Graphics;

• ppm, the graphical results are saved as Portable Pixmap;

• tif , the graphical results are saved as TIFF image, compressed;

We show here below an example of the structure of post processing.inp input file.

MATLAB linear off png

Outputs from BIANCA

In BIANCA, at the end of the optimisation process, we have 3 output files. The name of these files is the same as the one of the current job session. These output files have 3 different extension: .bio, .pop and .sta respectively. We describe the structure and the contents of those files in the following subsections.

The .bio output file

This file contains the informations about the best feasible individual for every generations. In particular in this file we can find:

• the number of generations;

• the ID of the population;

• the ID of the best individual within the population;

• the name and the number of each design variable for each chromosome of the best individual;

• the value of the non-penalised partial objective functions of the best individual;

• the value of the constraint functions of the best individual;

• the value of the total objective function of the best individual.

The .pop output file

In the output file with extension .pop the informations about the whole population are written every 10 generations. Concerning the informations about the whole population we can find:

• the number of generations;

• the ID of the population;

• the ID of every individual within each population;

• the name and the number of each design variable for each chromosome for each individual;

• the value of the non-penalised partial objective functions for each individual;

• the value of the constraint functions for each individual;

• the value of the total objective function for each individual.

The macro MACRO MY PROBLEM.f95

If you want to perform an optimisation process on your model, by means of the GA BIANCA, one possible way to do that is to write your model in FORTRAN environment. In this case you must observe the following conditions:

1. you must write your physical/mathematical model in FORTRAN language;

2. you must write your model as subroutine of BIANCA.

The macro MACRO MY PROBLEM.f95 has been realised in order to allow you to write in an easily way your model in FORTRAN language and to understand how your model can be interfaced within the code BIANCA. This macro contains 2 subroutines named my problem and my problem var which have some input and output quantities. Fig. 2.5 shows the structure of the macro. In the next subsections we explain in detail the structure of the two subroutines restrained in this macro and how and when you can use them. We show also an example on how you can write your model as subroutine of BIANCA, by means of the MACRO MY PROBLEM.f95, in Sec. 3.3.

The my problem subroutine

The my problem subroutine must be used when you want to write your mathematical model in FORTRAN environment, as subroutine of BIANCA, and when you have an optimisation problem where the number of design variables is fixed. In this case the cross-over between individuals belonging to different species is no longer required and you have to perform a standard genetic optimisation process.

The input quantities of this subroutine are:

• npop, number of populations (input derived from the input file .gen, line 1);

• nind, number of individuals for each population (input derived from the input file .gen, line 2);

• nchrom, number of chromosomes of each individual (input derived from the input file .opt, line 15);

• ngene, number of genes within each chromosome of the individual (input derived from the input file .opt, line 16);

• n obj, number of partial objectives (input derived from the input file .opt, line 9);

• n constr: number of constraints (input derived from the input file .opt, line 11);

• x being: phenotype of the whole population, the real size of this 4dimensional array is x being(npop, nind, nchrom, ngene). This array contains the value of each design variable, linked to each gene, for the whole population.

The output quantities of this subroutine are:

• obj: 3-dimensional array which contains the values of the partial objective functions for every individuals of each population. The real size of this array is obj(npop, nind, n obj);

• constr ineq: 3-dimensional array which contains the values of the inequality constraint functions for every individuals of each population.

The real size of this array is constr ineq(npop, nind, n constr).

The my problem var subroutine

The my problem var subroutine must be used when you want to write your mathematical model in FORTRAN environment, as subroutine of BIANCA, and when you have an optimisation problem where the number of design variables is also a variable of the process, such as the case of the optimisation of modular systems where the number of modules and, hence, the number of variables is also a design variable for the problem. In this case the cross-over between individuals belonging to different species is required and you have to perform a non-standard genetic optimisation process.

The input quantities of this subroutine are:

• npop, number of populations (input derived from the input file .gen, line 1);

• nind, number of individuals for each population (input derived from the input file .gen, line 2);

• nchrom min, minimum number of chromosomes (input derived from the input file .opt, line 14);

• nchrom max, maximum number of chromosomes (input derived from the input file .opt, line 14);

• ngene, number of genes within each chromosome of the individual (input derived from the input file .opt, line 16);

• n obj, number of partial objectives (input derived from the input file .opt, line 9);

• n constr: number of constraints (input derived from the input file .opt, line 11);

• x being: phenotype of the whole population, the size of this 4-dimensional array can change for each individual because each one can belong to a different specie and can have a different number of chromosome. In particular, the effective number of chromosomes of each individual is also restrained into the phenotype in a particular position of the array; if we consider the j th individual of the i th population the number of chromosomes of this individual, nchrom(i, j), is uniquely individuated by the following equality: nchrom(i, j) = x being(i, j, 1, ngene + 1). So for each individual the real size of the 4-dimensional array x being is x being(npop, nind, nchrom(npop, nind), ngene + 1). This array contains the value of each design variable, linked to each gene, for the whole population.

The output quantities of this subroutine are:

• obj: 3-dimensional array which contains the values of the partial objective functions for every individuals of each population. The real size of this array is obj(npop, nind, n obj);

• constr ineq: 3-dimensional array which contains the values of the inequality constraint functions for every individuals of each population.

The real size of this array is constr ineq(npop, nind, n constr).

Structure of the interface with external codes in BIANCA

In several problems, the value of the objective function and/or of the constraints, cannot be computed analytically, but it has to be evaluated using special numerical codes. Typically, this is the case of structural optimization, where the most part of times the structural response is numerically assessed using finite element (FE) codes. For these cases, a very general interface has been developed, which renders BIANCA able to exchange input/output informations with mathematical models supported by an external software. Fig. 2.6 shows the structure of the data-exchange between BIANCA and a generic external software. For each individual, BIANCA performs the genetic operations, such as selection, cross-over, mutation and so on, and then passes the design variables to the mathematical model written in a different environment. At this point, the external software evaluates the objective and the eventual constraint functions values, and then passes them back to BIANCA. The data-exchange between BIANCA and the external software is simply done by means of two I/O files.

The first one is the file written from BIANCA and passed to the external software, i.e. the input file, which contains the informations related to the current individual at the current generation, i.e. the number and the values of the design variables restrained in that individual's genotype. This input file also contains additional information such as the number of objective and constraint functions and also a particular variable, i.e. the counter whose meaning is explained in the next subsection. The second one is the file written from external software and passed to BIANCA, i.e. the output file, in which are written the values of objective and constraint functions, and once again the value of the counter.

The writing operations of these files are made for every individual in the current generation, so the external code, during the whole optimisation process, is called from BIANCA N ind × N gen times, where N ind is the number of individuals while N gen is the number of generations.

Some current and well known software packages have been interfaced with BIANCA in this way, like for instance MATLAB R , CAST3M R , ABAQUS R and ANSYS R . As shown in Fig. 2.7, in this input file BIANCA automatically writes:

• the number of chromosomes, n chrom , for the current individual at the current generation. In the case of an optimisation process where the number of chromosomes is fixed this value is equal to the one you declare in line 15 of the .opt input file of BIANCA, while in the case of an optimisation process where the number of chromosomes is also a variable of the problem, in this line you can find any possible integer value between the bounds that you declare in in line 14 of the .opt input file of BIANCA;

• the array of design variables for your model. The dimensions of this array are n chrom × m where m is equal to the number of genes n gene which you declare in line 16 of the .opt input file of BIANCA;

• the number of partial objective functions, n obj , which you declare in line 9 of the .opt input file of BIANCA;

• the number of constraint functions, n constr , which you declare in line 11 of the .opt input file of BIANCA;

• the counter. This is an integer variable which ensures the synchronisation between BIANCA and the external code. Within your model you must read the value of the counter from the input file and your model has to return this value to BIANCA by means of the creation of the output file, whose structure is explained in the next subsection.

As example, we show here below the structure of the .opt input file for BIANCA and the structure of the input file which BIANCA passes to the external software, in the case where the user mathematical model is realised by means of the MATLAB R package. In this simulation we have used the MATLAB R code for the construction of our mathematical model. This model is described in the example of Sec. 3.4. In this subsection we want to remark the parallelism which exists between the correct compilation of the .opt input file and the input file that BIANCA passes to the external code.

test
For our example, in the test matlab.opt input file, we can see that the name of the MATLAB R script is Vannucci, as written in line 4; at line 5 we have named the input file for our MATLAB R model as input mat.txt; the name of the output file which our MATLAB R model passes to BIANCA is output mat.txt. Moreover, the optimisation problem described in MATLAB R environment has two design variables, i.e. Concerning the input mat.txt (input file from BIANCA to MATLAB R ), for the current individual at the current generation BIANCA automatically writes the number of chromosomes, 1, the value of both design variables, x 1 = 1.4186705767350929 and x 2 = 0.97096774193548396, the number of partial objective functions, 1, the number of constraint functions, 0, and finally the value of the counter, 30.

The output file from the external code to BIANCA

As said beforehand, during the whole optimisation process, the external code passes an output file to BIANCA. You must include the writing operation of this file within your mathematical model (realised with your external code). The name of this file must be the same as the one you declare in line 6 of the .opt input file of BIANCA. The output file must be written from your model.

The structure of the output file which your model passes to BIANCA is shown in Fig. 2.8. As shown in Fig. 2.8, in this output file the following quantities must be written from your model:

• the counter. As previously said, this is an integer variable which ensures the synchronisation between BIANCA and the external code;

• the array of partial objective functions for your model. The dimensions of this array is n obj , where n obj is the number of partial objective functions which you declare in line 9 of the .opt input file of BIANCA;

• the array of constraint functions for your model. The dimensions of this array is n constr , where n constr is the number of constraint functions which you declare in line 11 of the .opt input file of BIANCA.

As example, we show here below the structure of the output file which the external software passes to BIANCA, in the case where the user mathematical model is realised by means of the MATLAB R package.

Structure of the output mat.txt output file which MATLAB R passes to BIANCA: -0.550094

In this simulation we have used the MATLAB R code for the construction of our mathematical model. This model is described in the example of Sec. 3.4. In this subsection we want to remark the parallelism which exists between the correct compilation of the .opt input file and what the output file (written by your model) passes to BIANCA.

For our example, the structure of the .opt input file is the same as the one described in the previous subsection. The name of the .opt input file is test matlab.opt. The name of the output file which our MATLAB R model passes to BIANCA is output mat.txt, as written in line 6.

You can see that in the output mat.txt we can find the value of the counter, 30, and the value of the objective function, -0.550094. Since our optimisation problem is an unconstrained problem we cannot write the value of constraint functions in the output mat.txt file.

Chapter 3 Examples

Test function example: welded beam design problem

In this section we show the input and output files concerning a particular test case optimisation problem: the welded beam design problem. This problem was firstly studied by Rao. The objective is to design a welded beam for minimum cost subject to several constraints, e.g. on shear stress, bending stress, buckling load, deflection of the beam and other side constraints. There are 4 design variables: the height of the weld h(x 1 ), the length of the weld l(x 2 ), and finally the height t(x 3 ) and the width b(x 4 ) of the beam. Mathematically, the problem can be stated as follows:

min x f (x) = 1.10471x 1 2 x 2 + 0.04811x 3 x 4 (14.0 + x 2 )
subject to :

                             g 1 (x) = τ (x) -13000 ≤ 0 g 2 (x) = σ (x) -30000 ≤ 0 g 3 (x) = x 1 -x 4 ≤ 0 g 4 (x) = 0.10471x 1 2 + 0.04811x 3 x 4 (14.0 + x 2 ) -5.0 ≤ 0 g 5 (x) = 0.125 -x 1 ≤ 0 g 6 (x) = δ (x) -0.25 ≤ 0 g 7 (x) = 6000 -P c (x) ≤ 0 (3.1) where:                                                                        τ (x) = (τ 1 ) 2 + 2τ 1 τ 2 x 2 2R + (τ 2 ) 2 τ 1 = 6000 √ 2x 1 x 2 τ 2 = M R J M = 6000 14 + x 2 2 R = x 2 2 4 + x 1 + x 3 2 2 J = 2 √ 2x 1 x 2 x 2 2 12 + x 1 + x 3 2 2 σ (x) = 504000 x 3 2 x 4 δ (x) = 2.1952 x 3 2 x 4 P c (x) = 64746.022 (1 -0.0282346x 3 ) x 3 x 4 3 (3.2)
The name of the job session is welded beam, so the input files must have the same name with extensions .gen and .opt and the 3 output files are going to have the same name with extensions .bio, .pop and .sta. For this case we perform an optimisation process with 2 population evolving at the same time.

The genetic parameters are:

• n pop = 2;

• n ind = 400;

• stop crit. = fixed generations;

• n gen = 200;

• p cross = 0.85;

• p mut = 0.0025;

• p shif t = 0.0;

• p mutchrom = 0.0;

• selection operator = roulette wheel;

• selection pressure = 1.0;

• elitism operator = active;

• isolation time = 50.

We show here below the structure of the welded beam.gen input file: The optimisation parameters are:

• simulation environment type = internal;

• kind of problem = test function;

• external code = none;

• external code model file = none;

• external code input file = none;

• external code output file = none;

• function ID = 80;

• minimisation or maximisation = minimisation;

• n obj = 1;

• constr. active or not = active;

• n constr = 7;

• CHROM V AR = no;

• CHROM M IN exp = no 0.0;

• n chrommin n chrommax = 0 0;

• n chrom = 1;

• n gene = 4;

• n var = 4;

• variables: • p mutchrom = 0.0;

-x 1,
• selection operator = roulette wheel;

• selection pressure = 1.0;

• elitism operator = active;

• isolation time = 0.

We show here below the structure of the Symmetries.gen input file:

1 500 fixed generations 500 0.85 0.002 0.0 0.0 1 1.0 1 0

For our example, the laminate has 14 plies and the only variables are the layers' orientations. According to what we have already explained in Sec.

2.3 about the library.inp input file and about the structure of individual's genotype, in this case the number of variables is 13 (the first ply has a fixed orientation, i.e. 0.0 • ). Each ply corresponds to a chromosome in the structure of the genotype and the layer's orientation is linked to a single gene. Then, the optimisation parameters are:

• simulation environment type = internal;

• kind of problem =library function;

• external code = none;

• external code model file = none;

• external code input file = none;

• external code output file = none; We perform also the post processing of results and we show here below the structure of the post processing.inp input file:

MATLAB semilog off png

Variable number of chromosomes/plies

In this second simulation we use the library function with ID 72. The name of the job session is Symmetries var, so the input files must have the same name with extensions .gen and .opt and the 3 output files are going to have the same name with extensions .bio, .pop and .sta. In addition we must compile in a correct way the library.inp input file.

The genetic parameters are:

• n pop = 1;

• n ind = 500;

• stop crit. = fixed generations;

• n gen = 500;

• p cross = 0.85;

• p mut = 0.002;

• p shif t = 0.5;

• p mutchrom = 0.008;

• selection operator = roulette wheel;

• selection pressure = 1.0;

• elitism operator = active;

• isolation time = 0.

We show here below the structure of the Symmetries var.gen input file:

1 500 fixed generations 500 0.85 0.002 0.5 0.008 1 1.0 1 0

For our example, the laminate has a variable number of plies and the design variables are the orientation and thickness of every layer. According to what we have already explained in Sec. 2.3 about the library.inp input file and about the structure of individual's genotype, in this case the number of variables is 2n where n is the number of chromosomes. We consider that the number of chromosome can varies between 12 and 16. Each ply corresponds to a chromosome in the structure of the genotype and the orientation and thickness of each layer are linked to two different genes. Then, the optimisation parameters are:

• simulation environment type = internal;

• kind of problem =library function;

• external code = none;

• external code model file = none;

• external code input file = none;

• external code output file = none;

• function ID = 72;

• minimisation or maximisation = minimisation;

• n obj = 3;

• constr. active or not = not active;

• n constr = 0;

• CHROM V AR = yes;

• CHROM M IN exp = yes 2.0;

• n chrommin n chrommax = 12 16;

• n chrom = 0;

• n gene = 2;

• n var = 2;

• variables:

angle, regular discrete, step 1.0 We perform also the post processing of results and we show here below the structure of the post processing.inp input file:

MATLAB semilog off png

User-defined model example: beam design problem

In this section we show the input and output files concerning the optimisation process on a possible user-defined model and also how to write the mathematical model in the MACRO MY PROBLEM.f95.

In this example we consider a simple optimisation problem about beams' design. We have a clamped beam subject to a tip load P of 1000 N. The beam is made up by an Aluminium alloy with a Young modulus E equal to 72 GPa and a tensile yield stress σ y of 345 MPa. The beam has a circular section. The design variables are the beam's length L and the beam's radius R. We want to find the optimal values of L and R which minimise the tip displacement δ and respect both constraints imposed on the maximum stress and on the beam's volume. The reference value of the volume V ref is 140000 mm 3 .

The problem can be formulated as follows:

min

L,R δ (L, R) = 4P L 3 3πER 4
subject to :

   4P L πR 3 -σ y ≤ 0 LπR 2 -V ref ≤ 0 (3.3)
The name of the job session is beam design, so the input files must have the same name with extensions .gen and .opt and the 3 output files are going to have the same name with extensions .bio, .pop and .sta. Since the problem do not require the cross-over between species, the structure of the individual's genotype is made up by a single chromosome with two genes which identify the design variables, i.e. the length L and the radius R. In addition, since the number of chromosome is fixed we must write our model by means of the subroutine my problem. We have written our model in the MACRO MY PROBLEM.f95 as shown in Fig. 3.7. • external code = none;

• external code model file = none;

• external code input file = none;

• external code output file = none;

• function ID = 0;

• minimisation or maximisation = minimisation;

• n obj = 1;

• constr. active or not = active;

• n constr = 2;

• CHROM V AR = no;

• CHROM M IN exp = no 0.0;

• n chrommin n chrommax = 0 0;

• n chrom = 1;

• n gene = 2;

• n var = 2;

Example of interface with MATLAB R code: Vannucci's function problem

In order to have a general idea on how BIANCA 3.1 works when it is interfaced with external codes, we show here the input and output files concerning the optimisation process on the unconstrained Vannucci's function problem.

The problem can be stated as follows:

       min f (x 1 , x 2 ) = -e ka √ x 2 1 +x 2 2 sin (ax 1 ) cos (2bx 2 ) 0 ≤ x 1 ≤ 4π 0 ≤ x 2 ≤ 2π (3.4)
Although this problem is already implemented as test function within BIANCA, we have rewrite this problem in MATLAB R environment in order to explain how you can easily interface with BIANCA any model realised within the MATLAB R code.

First of all we can consider the structure of the model written within MATLAB R . The structure is completely free, except for the part concerning the exchange of data with BIANCA. For our example the model is written as MATLAB R script whose name is Vannucci.m and whose structure is shown in The name of the job session is test matlab, so the input files must have the same name with extensions .gen and .opt and the 3 output files are going to have the same name with extensions .bio, .pop and .sta.

The genetic parameters are:

• n pop = 1;

• n ind = 100;

• stop crit. = fixed generations;

• n gen = 200;

• p cross = 0.85;

• p mut = 0.01; • p shif t = 0.0;

• p mutchrom = 0.0;

• selection operator = roulette wheel;

• selection pressure = 1.0;

• elitism operator = active;

• isolation time = 0.

Then we show here below the structure of the test matlab.gen input file: The optimisation parameters are:

• simulation environment type = external;

• kind of problem = none;

• external code = MATLAB;

• external code model file = Vannucci;

• external code input file = input mat.txt;

• external code output file = output mat.txt;

• function ID = 0;

• minimisation or maximisation = minimisation;

• n obj = 1;

• constr. active or not = not active;

• n constr = 0;

• CHROM V AR = no;

• CHROM M IN exp = no 0.0;

• n chrommin n chrommax = 0 0;

• n chrom = 1;

• n gene = 2;

• n var = 2;

• variables:

-

Example of interface with ANSYS R code: stiffened plate design problem

In order to have a general idea on how BIANCA 3.1 works when it is interfaced with external codes, we show here the input and output files concerning the optimisation process on the engineering problem of the optimal design of an aeronautical stiffened panel. Here, the optimal design of the stiffened panel is intended in terms of minimizing its weight and, at the same time, respecting a constraint imposed on its buckling load. The problem to obtain a minimum weight panel which presents particular characteristics in terms of buckling load, is a very important issue in the aeronautics.

We show here that this optimisation problem can be formulated and solved in a very general way by applying our approach for the optimisation of modular engineering systems where not only the characteristics of each module, but also the number of the constitutive modules are taken into account as optimisation variables. In addition, this problem is numerically more complex than the ones presented in the previous sections: in fact it is a constrained optimisation problem where either the objective or the constraint function are evaluated by means of a Finite Element (FE) code. To represent the wing-box section we use the ANSYS R FE code. The optimisation variables are: the number of stiffeners n, and for each stiffener there are two design variables, i.e. the thickness t si and the height h i , (i = 1...n). The total number of design variables is 2n.

Concerning the mathematical formalisation of the constrained optimisation problem, it can be stated as:

min n,ts,h W up stif f (n, t s , h) subject to : p ref -p cr (n, t s , h) ≤ 0 (3.5)
In Eq.(3.5), W up stif f (n, t s , h) stands for the weight of the upper panel's stiffeners, while the quantities n, t s , h represent the number of stiffeners for each panel and the vectors of stiffeners' thickness and heights respectively, i.e. the design variables. The quantity p cr (n, t s , h) stands for the first buckling load of the structure, while p ref is a reference value for this quantity. More details about this problem can be found in [START_REF] Montemurro | A genetic algorithm with cross-over on species for structural optimisation[END_REF].

First of all we can consider the structure of the model written within ANSYS R . The structure is completely free, except for the part concerning the exchange of data with BIANCA. As well explained in Sec. 2.6 the interface between the two codes is realised by means of the creation of two input/output files which pass the design variables from BIANCA to ANSYS R and the objective and constraints from ANSYS R to BIANCA. For our case the name of the ANSYS R file which contains all the information about the wing-box FE model is panel.lgw. You can see the structure of this file in the following path: The structure of this file is substantially articulated in three parts: the first one concerns the reading operations of design variables that BIANCA passes to the FE model, the second one concerns the creation of the model and, finally, the third one concerns the writing operations of the output file that contains the counter, objective function and constraint that ANSYS R passes to BIANCA.

The name of the job session is test ansys, so the input files must have the same name with extensions .gen and .opt and the 3 output files are going to have the same name with extensions .bio, .pop and .sta.

The genetic parameters are:

• n pop = 1;

• n ind = 150;

• stop crit. = fixed generations;

• n gen = 200;

• p cross = 0.85;

• p mut = 0.0067;

• p shif t = 0.5;

• p mutchrom = 0.04;

• selection operator = tournament;

• selection pressure = 1.0;

• elitism operator = active;

• isolation time = 0.

Then we show here below the structure of the test ansys.gen input file: The optimisation parameters are:

• simulation environment type = external;

• kind of problem = none;

• external code = ANSYS;

• external code model file = panel.lgw;

• external code input file = inputs.txt;

• external code output file = outputs.txt;

• function ID = 0;

• minimisation or maximisation = minimisation;

• n obj = 1;

• constr. active or not = active;

• n constr = 1;

• CHROM V AR = yes;

• CHROM M IN exp = no 0.0;

• n chrommin n chrommax = 20 26;

• n chrom = 0;

• n gene = 2;

• n var = 2;

• variables:

thick, regular discrete, step 0. We perform also the post processing of results and we show here below the structure of the post processing.inp input file: First of all we must consider the structure of the model written within ABAQUS R . Again, the structure is completely free, except for the part concerning the exchange of data with BIANCA. As well explained in Sec. 2.6 the interface between the two codes is realised by means of the creation of two input/output files which pass the design variables from BIANCA to ABAQUS R and the objective and constraints from ABAQUS R to BIANCA. For our case the name of the ABAQUS R file which contains all the information about the beam FE model is cantilevered beam.py. You can see the structure of this file in the following path: The structure of this file is substantially articulated in three parts: the first one concerns the reading operations of design variables that BIANCA passes to the FE model, the second one concerns the creation of the model and, finally, the third one concerns the writing operations of the output file that contains the counter, objective function and constraint that ABAQUS R passes to BIANCA.

The name of the job session is test abaqus, so the input files must have the same name with extensions .gen and .opt and the 3 output files are going to have the same name with extensions .bio, .pop and .sta.

The genetic parameters are:

• n pop = 1;

• external code input file = input.txt;

• external code output file = out.txt;

• function ID = 0;

• minimisation or maximisation = minimisation;

• n obj = 1;

• constr. active or not = not active;

• n constr = 0;

• CHROM V AR = no;

• CHROM M IN exp = no 0.0;

• n chrommin n chrommax = 0 0;

• n chrom = 1;

• n gene = 2;

• n var = 2;

• variables:

-

Figure 1 . 1 :

 11 Figure 1.1: Standard GA's scheme.

Figure 1 . 2 :

 12 Figure 1.2: Logical scheme of the structure of the interface with external software in BIANCA.

Figure 1 . 3 :

 13 Figure 1.3: Structure of the individual's genotype with variable number of chromosome in BIANCA 3.1.

Figure 1 . 4 :

 14 Figure 1.4: Example of individual-laminate with variable number of layers in BIANCA.

Figure 1 . 5 :

 15 Figure 1.5: Two-way relation between continuous variables and pointers in BIANCA.

  .1.

Figure 2 . 1 :

 21 Figure 2.1: Structure of the library.inp input file.

  input file membrane stiffness isotropy bending stiffness orthotropy K=0 uncoupling

Fig. 2 .

 2 Fig. 2.2 shows the structure of the .bio output file for the Vannucci's function problem with one inequality constraint. In this simulation we consider a population of 10 individuals evolving through 50 generations.

Figure 2 . 2 :

 22 Figure 2.2: Structure of the .bio output file.

Fig. 2 .

 2 Fig. 2.3 shows the structure of the .pop output file for the Vannucci's function problem with one inequality constraint. In this simulation we consider a population of 10 individuals evolving through 50 generations.

Figure 2 . 3 :

 23 Figure 2.3: Structure of the .pop output file.

Figure 2 . 5 :

 25 Figure 2.5: Structure of the macro MACRO MY PROBLEM.f95.

Figure 2 . 6 :

 26 Figure 2.6: Structure of interface with external software in BIANCA.

2. 6 . 1

 61 The input file from BIANCA to the external code As previously said, during the whole optimisation process, BIANCA passes an input file to the external code. You must read the value of design variables which your mathematical model (realised within your external code) needs from this file. The name of this file must be the same as the one you declare in line 5 of the .opt input file of BIANCA. The input file is automatically written from BIANCA for each individual at the current generation. It appears clearly that, within your model, you must provide a reading process of the design variables from that file.The structure of the input file which BIANCA passes to your model is shown in Fig.2.7.

Figure 2 . 7 :

 27 Figure 2.7: Structure of the input file which BIANCA passes to the external software.

x 1 and x 2 .

 2 In addition the structure of the genotype is made up by one chromosome with 2 genes. The problem has one objective function and no constraint function. You can see the coherence between what we have write in the test matlab.opt input file for BIANCA and what BIANCA writes in the input mat.txt. You can see the structure of the MATLAB R script in Sec. 3.4.

Figure 2 . 8 :

 28 Figure 2.8: Structure of the output file which the external software passes to BIANCA.

Figs. 3 .

 3 Figs. 3.1 and 3.2 show the curves of the best feasible solution vs generations and the average value of the objective function vs generations, respectively.

Figure 3 . 1 :

 31 Figure 3.1: Best feasible solution vs generations for the welded beam design problem.

Figure 3 . 2 :

 32 Figure 3.2: Average value of the objective function vs generations for the for the welded beam design problem.

Figs. 3 .

 3 Figs.3.3 and 3.4 show the curves of the best feasible solution vs generations and the average value of the objective function vs generations, respectively.

Figure 3 . 3 :

 33 Figure 3.3: Best feasible solution vs generations for the design of laminate's elastic symmetries.

Figure 3 . 4 :

 34 Figure 3.4: Average value of the objective function vs generations for the design of laminate's elastic symmetries.

Figs. 3 .

 3 Figs. 3.5 and 3.6 show the curves of the best feasible solution vs generations and the average value of the objective function vs generations, respectively.

Figure 3 . 5 :

 35 Figure 3.5: Best feasible solution vs generations for the design of laminate's elastic symmetries, variable number of layers.

Figure 3 . 6 :

 36 Figure 3.6: Average value of the objective function vs generations for the design of laminate's elastic symmetries, variable number of layers.

Figure 3 . 7 :

 37 Figure 3.7: Structure of the macro MACRO MY PROBLEM.f95 for the beam design problem.

-

  Figs.[START_REF] Montemurro | Design of laminate's elastic properties with minimum number of plies[END_REF].8 and 3.9 show the curves of the best feasible solution vs generations and the average value of the objective function vs generations, respectively.

Figure 3 .

 3 Figure 3.8: Best feasible solution vs generations for the beam design problem.

Figure 3 .

 3 Figure 3.9: Average value of the objective function vs generations for the beam design problem.

  Fig 3.10. The data exchange between BIANCA and our model is realised according to what we have explained in Sec. 2.6. You can see the structure of this MATLAB R script in the following path: BIANCA 3.1 User guide\ Examples\ Vannucci.m;

Figure 3 .

 3 Figure 3.10: Structure of the Vannucci.m MATLAB R script.

Figure 3 .

 3 Figure 3.11: Best feasible solution vs generations for the unconstrained Vannucci's function problem.

Figure 3 .

 3 Figure 3.12: Average value of the objective function vs generations for the unconstrained Vannucci's function problem.

BIANCA 3 . 1

 31 User guide\ Examples\ panel.lgw;

Figs. 3 .

 3 Figs.[START_REF] Montemurro | Design of laminate's elastic properties with minimum number of plies[END_REF].13 and 3.14 show the curves of the best feasible solution vs generations and the average value of the objective function vs generations, respectively.

Figure 3 .

 3 Figure 3.13: Best feasible solution vs generations for the stiffened plate design problem.

Figure 3 .

 3 Figure 3.14: Average value of the objective function vs generations for the stiffened plate design problem.

3. 6

 6 Example of interface with ABAQUS R code: beam design problemIn this section we consider a simple optimisation problem about beams' design. We have a clamped beam subject to a tip load P of 1000 N. The beam is made up by a Steel alloy with a Young modulus E equal to 200 GPa. The beam has a rectangular cross section. The design variables are the beam's length L and the beam's height h. The width b of the section is equal to 10 mm. The model of the beam is realised by means of the ABAQUS R FE code. We want to find the optimal values of L and h which minimise the absolute value of the tip displacement |δ|.The problem can be formulated as follows: min L,h |δ (L, h) | (3.6)

BIANCA 3 . 1

 31 User guide\ Examples\ cantilevered beam.py;

Figs. 3 .

 3 Figs. 3.15 and 3.16 show the curves of the best feasible solution vs generations

Figure 3 .

 3 Figure 3.15: Best feasible solution vs generations for the stiffened plate design problem.

Figure 3 .

 3 Figure 3.16: Average value of the objective function vs generations for the stiffened plate design problem.

  -71, model and functions for the optimisation of the laminates' elastic symmetries with fixed number of plies, i.e. chromosomes (BEWARE: if this option is active you must choose one or many objective functions from the library.inp file); -72, model and functions for the optimisation of the laminates' elastic symmetries with variable number of plies, i.e. chromosomes (BEWARE: if this option is active you must choose one or many objective functions from the library.inp file); 8. M AXORM IN , ID for maximisation or minimisation problems (integer):

4. M ODEL N AM E, name of the file (character) that describe the physical/mathematical model which you want to optimise (valid only when in line 1 the external option is active). BEWARE: the name of the file must contain the extension (e.g. for an ANSYS file a possible name can be cantilevered beam.lgw ). EXCEPTION: in case of MATLAB files the user do not write the extension (e.g. not rotorcraft dynamic.m but rotorcraft dynamic); 5. M ODEL I, name of the input file (character) which passes the design variables from BIANCA to the external model (valid only when in line 1 the external option is active). BEWARE: the name of the file must contain the extension. The structure of this file is explained in Sec. 2.6; 6. M ODEL O, name of the output file (character) which passes the values of constraint and objective functions from the external model to BIANCA (valid only when in line 1 the external option is active). BE-WARE: the name of the file must contain the extension. The structure of this file is explained in Sec. 2.6; 7. IDF , ID of the internal function written inside BIANCA (integer) (valid only when in line 1 the internal option is active): • if in line 2 the test function option is active: -6, Vannucci's function with one inequality constraint; -60, Vannucci's function without constraints; -61, Vannucci's function with one equality constraint; -80, Welded beam design problem, see []; -81, Pressure vessel design problem, see []; -82, Tension compression spring weight design problem, see [];

• if in line 2 the library function option is active:

Table 2 .

 2 For this example we use an internal test function written within BIANCA: the Vannucci's function with one inequality constraints. We want to minimise this function. So we perform an optimisation process with fixed number of chromosome. The structure of the individual's genotype is made by a single chromosome with two genes and, hence, with two different type of variables. The name of the first variable is x 1 while the name of the second one is x 2.

		Regular discrete	Scattered discrete
	variables	variables	variables
	Variable name	Variable name	Variable name
	(character)	(character)	(character)
	EXTENDED	REGULAR DISCR	SCATTERED DISCR
	Left bound value	Left bound value	Vector of scattered values
	(double precision) (double precision)	(double precision)
	Right bound value Right bound value
	(double precision) (double precision)
		Discretization step
		(double precision)
	4 lines	5 lines	3 lines
	internal
	test function
	none
	none
	none
	none
	6
	2
	1
	1
	1
	no
	no 0.0
	0 0
	1
	2
	2
	x 1
	EXTENDED
	0.0

1: Declaration of different types of variables in BIANCA

As example, we show here the structure of the .opt input file.

  matlab.opt input file (for more details about this .opt input file see Sec. 3.4):Structure of the input mat.txt input file which BIANCA passes to MATLAB R :

	2.6. STRUCTURE OF THE INTERFACE WITH EXTERNAL CODES IN BIANCA41
	6.283
	1 2
	1
	1.4186705767350929 0.97096774193548396
	1
	0
	30
	external
	none
	MATLAB
	Vannucci
	input mat.txt
	output mat.txt
	0
	2
	1
	0
	0
	no
	no 0.0
	0 0
	1
	2
	2
	x 1
	EXTENDED
	0.0
	12.556
	x 2
	EXTENDED
	0.0

  The structure of the library.inp input file is the following: You can see the structure of the Symmetries.bio, Symmetries.pop and Symmetries.sta output files in the following paths: BIANCA 3.1 User guide\ Examples\ Symmetries.bio BIANCA 3.1 User guide\ Examples\ Symmetries.pop BIANCA 3.1 User guide\ Examples\ Symmetries.sta.

	angle
	REGULAR DISCR
	-90.0
	90.0
	1.0
	1
	membrane stiffness isotropy
	bending stiffness orthotropy K=0
	uncoupling

  • , bounds [-90.0 • 90.0 • ]; You can see the structure of the Symmetries var.bio, Symmetries var.pop and Symmetries var.sta output files in the following paths: BIANCA 3.1 User guide\ Examples\ Symmetries var.bio BIANCA 3.1 User guide\ Examples\ Symmetries var.pop BIANCA 3.1 User guide\ Examples\ Symmetries var.sta.

	bending stiffness orthotropy K=0
	uncoupling
	-thick, extended, bounds [0.1 0.2]mm.
	We show here below the structure of the Symmetries var.opt input file:
	internal
	library function
	none
	none
	none
	none
	72
	2
	3
	0
	0
	yes
	yes 2.0
	12 16
	0
	1
	1
	angle
	REGULAR DISCR
	-90.0
	90.0
	1.0
	thick
	EXTENDED
	0.1
	0.2
	1 2
	The structure of the library.inp input file is the following:
	membrane stiffness isotropy

  Figs.[START_REF] Montemurro | Design of laminate's elastic properties with minimum number of plies[END_REF].11 and 3.12 show the curves of the best feasible solution vs generations and the average value of the objective function vs generations, respectively.

	MATLAB
	linear
	off
	png
	x 1, extended, bounds [0.0 12.556];
	-x 2, extended, bounds [0.0 6.283];

  You can see the structure of the test ansys.bio, test ansys.pop and test ansys.sta output files in the following paths: BIANCA 3.1 User guide\ Examples\ test ansys.bio; BIANCA 3.1 User guide\ Examples\ test ansys.pop; BIANCA 3.1 User guide\ Examples\ test ansys.sta.

	1 mm, bounds [2.0 5.0]mm;
	-height, regular discrete, step 0.5 mm, bounds [50.0 100.0]mm;
	Then we show here below the structure of the test ansys.opt input file:
	external
	none
	ANSYS
	panel.lgw
	inputs.txt
	outputs.txt
	0
	2
	1
	1
	1
	yes
	no 0.0
	20 26
	0
	2
	2
	thick
	REGULAR DISCR
	2.0
	5.0
	0.1
	height
	REGULAR DISCR
	50.0
	100.0
	0.5
	1 2

3.7 Example of interface with CAST3M R code:plate design problem

The .sta output file

This file contains the informations about the statistics on the whole population for each generation. In particular in this file we can find:

• the number of generations;

• the ID of the population;

• the number of each non-penalised partial objective function and the minimum and average values within the population for each generation;

• the minimum and average values of the total objective function within the population for each generation;

• the maximum and average values of the fitness function within the population for each generation;

Library function example: laminates' design problem

In this section we show the input and output files concerning the optimisation process on the laminate's elastic properties design problem. For more details about this kind of problem see [START_REF] Vincenti | Conception et optimisation de composites par mèthode polaire et algorithmes génétiques[END_REF][START_REF] Vannucci | Designing the elastic properties of laminates as an optimisation problem: a unified approach based on polar tensor invariants[END_REF][START_REF] Montemurro | Design of laminate's elastic properties with minimum number of plies[END_REF]. Here we want to find a laminate that has the following symmetries:

• elastic uncoupling;

• in-plane stiffness isotropy;

• bending stiffness orthotropy.

We make 2 kind of simulations: in the first one the number of layers is fixed and only the orientations are the design variables, while in the second one the number of plies is variable and the design variables are the orientation and the thickness of each layer. In this last case the reproduction between different species is required. In the following subsections we show how to perform the optimisation process by means of the library functions for the design of laminate elastic symmetries developed within BIANCA.

Fixed number of chromosomes/plies

In this first simulation we use the library function with ID 71. The name of the job session is Symmetries, so the input files must have the same name with extensions .gen and .opt and the 3 output files are going to have the same name with extensions .bio, .pop and .sta. In addition we must compile in a correct way the library.inp input file.

The genetic parameters are:

• n pop = 1;

• n ind = 500;

• stop crit. = fixed generations;

• n gen = 500;

• p cross = 0.85;

• p mut = 0.002;

• p shif t = 0.0;

• function ID = 71;

• minimisation or maximisation = minimisation;

• n obj = 3;

• constr. active or not = not active;

• n constr = 0;

• CHROM V AR = no;

• CHROM M IN exp = no 0.0;

• n chrommin n chrommax = 0 0;

• n chrom = 13;

• n gene = 1;

• n var = 1;

• variables:

angle, regular discrete, step 1.0 The genetic parameters are:

• n pop = 1;

• n ind = 100;

• stop crit. = fixed generations;

• n gen = 200;

• p cross = 0.85;

• p mut = 0.01;

• p shif t = 0.0;

• p mutchrom = 0.0;

• selection operator = roulette wheel;

• selection pressure = 1.0;

• elitism operator = active;

• isolation time = 0.

Then we show here below the structure of the beam design.gen input file: The optimisation parameters are:

• simulation environment type = internal;

• kind of problem = my problem;

Then we show here below the structure of the test matlab.opt input file: We perform also the post processing of results and we show here below the structure of the post processing.inp input file:

• n ind = 30;

• stop crit. = fixed generations;

• n gen = 100;

• p cross = 0.85;

• p mut = 0.033;

• p shif t = 0.0;

• p mutchrom = 0.0;

• selection operator = tournament;

• selection pressure = 1.0;

• elitism operator = active;

• isolation time = 0.

Then we show here below the structure of the test abaqus.gen input file: The optimisation parameters are:

• simulation environment type = external;

• kind of problem = none;

• external code = ABAQUS;

• external code model file = cantilevered beam.py;


Rémi Ronfard

Quentin Doussot

Generating 3D Scenes in the style of Keith Haring

Recently, interest in shape grammar models of pictorial style has been revived by the success of generative modelers for buildings and cities. Stochastic methods have been introduced for learning the parameters of shape grammars to adapt to different architectural or visual styles, including Mondrian. We extend those recent approaches for generating 3D graphics in the style of Keith Haring paintings, whose visual vocabulary is significantly more complex than Mondrian. We propose a four-tiered stochastic plex grammar which decomposes scenes into figures, figures into bodies, bodies into body parts, and body parts into surfaces. Each tier of the grammar is stochastic, which allows us to generate random variations of scenes while keeping the overall style of Keith Haring paintings. Because the scenes are generated as 3D graphics, we are able to animate them into generative "Keith Haring movies".

Introduction

Recently, interest in shape grammar models of pictorial style [START_REF] Stiny | Shape Grammars and the Generative Specification of Painting and Sculpture[END_REF] has been revived by the success of generative modelers for buildings and cities [START_REF] Muller | Procedural modeling of buildings[END_REF]. Stochastic methods have been introduced for learning the parameters of shape grammars to adapt to different architectural or visual styles, including Mondrian paintings [START_REF] Ilcik | Procedural Skeletons: Kinematic Extensions to CGA-Shape Grammars[END_REF].

Stochastic Plex Grammars

Traditional string grammars are not adequate for building two-dimensional or threedimensional structures. Shape grammars were introduced by Stiny and Gips [START_REF] Stiny | Shape Grammars and the Generative Specification of Painting and Sculpture[END_REF] as a general framework for such cases, including painting and sculpture. Interest in shape grammars has been revived with spectacular results in procedural generation of cityscapes and architectural building using specialized CGA grammars [START_REF] Muller | Procedural modeling of buildings[END_REF]. Such grammars have also been extended to humanoid figures [START_REF] Fiedler | Procedural human posing using CGA grammars[END_REF][START_REF] Ilcik | Procedural Skeletons: Kinematic Extensions to CGA-Shape Grammars[END_REF].

In this work, we use plex grammars [START_REF] Feder | [END_REF] rather than CGA grammars, because they are better suited for modelling complex figures with arbitrary connections between elements, which are typical of the Keith Haring style.

As introduced by Feder [START_REF] Feder | [END_REF], plex languages use a vocabulary of terminal and nonterminal plex structures with an arbitray number of attaching points. Plex grammars describe the inter-connections of plex structures in any given plex language. Typically, a plex structure A with NA attaching points can be composed with another plex structure B with NB attaching points to build a higher-level plex structure C with NC attaching points (NC < NA+NB). The plex grammar rule for such a transformation includes a list of joints (connecting attaching points) and tie-points (non connecting attaching points).

A stochastic plex grammar assigns a probability to each rule in the grammar and a probability over the list of joints and tie points in the rule. This is especially suited to the modelling of Keith Haring figures, where body parts can be inter-connected almost interchangeably. A stochastic plex grammar can also assign probabilities over other free parameters of each rule, for instance the relative distances, orientations and sizes of the left-hand side and right-hand side plex structures, but also their colors, shapes and textures.

In this work, we manually created production rules from a sample of Keith Haring paintings available on the internet. We computed empirical rule probabilities by manually labelling the grammar constituents in each paintings and counting how many times each rule was used. We also computed empirical joint probabilities by counting how many times each joint was used in its parent rule. We used the normalized counts as probabilities in all cases.

Similarly, we computed histograms of the distances, orientations, sizes, colors, shapes and textures observed in those paintings, and used the normalized histogram values as probabilities.

The Grammar of Keith Haring Paintings

The use of shape grammars for describing the structure of paintings goes back to at least two important papers by Kirsch and Kirsch [START_REF] Kirsch | The Anatomy of Painting Style: Description with Computer Rules[END_REF] and Lauzanna et al [START_REF] Lauzzana | A Rule System for Aesthetic Research in the Visual Arts[END_REF] in the same issue of the Leonardo journal in 1988. This pioneering work was illustrated with examples of automatically-generated paintings in the styles of Miro and Kandinski.

More recently, Talton et al. extended the approach to stochastic grammars for generating random paintings in the style of Mondrian [START_REF] Fiedler | Procedural human posing using CGA grammars[END_REF]. Their approach introduced the use of Metropolis sampling for choosing more aesthetic productions from a large number of randomly generated paintings according to a hand-tuned preference function.

We extend that approach for generating 3D graphics in the style of Keith Haring paintings [START_REF] Kolossa | [END_REF] whose visual vocabulary is significantly more complex than Mondrian. Our system is based on a four-tiered stochastic plex grammar, which decomposes scenes into figures, figures into bodies, bodies into body parts, and body parts into surfaces.

Interestingly, such structural decompositions of paintings appear to have a long tradition among art historians, starting with Alberti in 1453 [START_REF] Lauzzana | A Rule System for Aesthetic Research in the Visual Arts[END_REF]. According to Baxandall, such structural descriptions were originally adapted from humanist rhetoric, which praised the composition of words into propositions, clauses and sentencess [START_REF] Baxandall | Painting and experience in fifteenth century Italy[END_REF]. Hence, Alberti praised the composition of surfaces into body parts, bodies and paintings.

What makes Keith Haring especially interesting in this context is that his paintings provide a systematic and exhaustive exploration of the combinatorial possibilities of composing figures with bodies and body parts, into very large paintings and murals. Incidentally, the combinatorial nature of Haring's style has recently been spectacularly illustrated with a 17 x 6 puzzle comprised of a 32,256 pieces [16].

We now turn to a tier-by-tier description of our grammar of the Keith Haring style.

Surfaces to body parts

The first tier in our Keith Haring grammar contains rules for composing surfaces into body parts. We build torsos, arms, legs and heads by assembling together tubular surfaces, as follows:

arm -> pipe(biceps) artic(1.7) pipe(forearm) hand (10xx,x10x,xx10) (0xxx) leg -> pipe(thigh) artic(0.5) pipe(calf) foot (10xx,x10x,xx10) (0xxx) !"#$%&'($)*+,-$,&$.&'/0-$

The second tier in our Keith Haring grammar contains rules for composing body part surfaces into characters. The plex production rule for building a body is presented below.

body(x,y,c) -> torso(x

Bodies to figures

The third tier in our Keith Haring grammar contains rules for composing characters into figures. This tier demonstrates the creativity of Keith Haring with a large number of figures including couples, triplets, columns, bridges which can be combined together recursively.

Scene Generation

In this section, we describe how we use our grammar to randomly generate novel paintings and movies in the style of Keith Haring. Each novel scene is generated by randomly choosing rules that maximize the score of the panting with respect to a predetermined goal.

Generative paintings

We create novel paintings in the style of Keith Haring by generating a 3D scene and rendering it from a single viewpoint. In the following figure, we used a dart-throwing algorithm [START_REF] Crandall | Algorithms for localized dart-throwing[END_REF] to fill the planar shape of a heart with randomly generated figures without crossing or occlusion. In future work, we are planning to further extend the algorithm to also take into account other objective functions, including aesthetic or narrative goals, following the general approach proposed by Talton et al [START_REF] Fiedler | Procedural human posing using CGA grammars[END_REF].

Generative movies

We can create movies in the style of Keith Haring by generating a 3D scene, then moving the camera and rendering the scene from the camera's viewpoint. We can also create animated movies in the style of Keith Haring by generating a 3D scene and changing it at every frame. This can be done in any different ways by inserting, deleting and moving figures relative to the scene ; by inserting, deleting and moving bodies relative to their parent figures ; or by inserting, deleting and moving body parts relative to their parent bodies. At this point, such transformations are chosen manually.

5.Conclusion

In this paper, we have presented stochastic plex grammars as a generic framework for representing the paintings and murals of Keith Haring and we have used that framework for generating random 3D scenes in the same style. Plex grammars appear to be ideally suited for the task. In future work, we would like to extend our approaches to other painting and sculpting styles. Another interesting avenue for future research is the generalization of stochastic plex grammars to animation grammars with rules describing how 3D shapes should be inserted, deleted and moved in the temporal domain to produce 3D movies.

  ,y,c,0.78,0.78,0.5,0.78) arm arm leg leg head (00xxxx,1x0xxx,2xx0xx,3xxx0x,4xxxx0) Special cases are the open body, where the arms contain attaching points that can connect with other bodies; the looping body, where the arms are connected together; the headless body and the open trunk, where the torso contains multiple attaching points that can connect to other bodies (see accompanying figures). openbody(x,y,c) -> torso(x,y,c,...) pipe(biceps) pipe(biceps) leg leg head (00xxxx,1x0xxx,2xx0xx,3xxx0x,4xxxx0) (x1xxxx,xx1xxx) looping body(x,y,c) -> openbody(x,y,c) epsilon (01,10) headlessbody(x,y,c) -> torso(x,y,c,...) arm arm leg leg pipe(neck) (00xxxx,1x0xxx,2xx0xx,3xxx0x,4xxxx0) (xxxxx1) opentrunk(x,y,c) -> opentorso(x,y,c,...) arm arm leg leg (00xxx,1x0xx,2xx0x,3xxx0) (4xxxx,5xxxx)

3 . 4

 34 couple(x,y,c) -> openbody(x,y,c) openbody (01,10) triplet(x,y,c) -> openbody(x,y,c) openbody openbody (01x,x01,1x0) Chains are recursive structures built along the same lines ; loops are closed chains. Columns are another recursive structure characteristic of Keith Haring. column(x,y,c,scale) -> headlessbody(x,y,c,scale) opentrunk(x,y+scale*0.14,c,scale*0.8) opentrunk(x,y+scale*0.26,c,scale*0.64) head (01xx,x01x,xx00) Figures to scenes The fourth tier in our Keith Haring grammar contains rules for composing figures into 3D scenes. In our implementation, we only use planar figures and we place each figure by choosing the 3D location of the figure's origin and the 3D orientation of the figure's plane in camera coordinates.