# Hidden-variables genetic algorithm for variable-size
design space optimal layout problems with application
to aerospace vehicles

Juliette Gamot, Mathieu Balesdent, Arnault Tremolet, Romain Wuilbercq, Nouredine Melab, El-Ghazali Talbi

<figure><img src="image_1.png" /></figure>

► To cite this version:

Juliette Gamot, Mathieu Balesdent, Arnault Tremolet, Romain Wuilbercq, Nouredine Melab, et al. Hidden-variables genetic algorithm for variable-size design space optimal layout problems with application to aerospace vehicles. Engineering Applications of Artificial Intelligence, 2023, 121, pp.105941. 10.1016/j.engappai.2023.105941. hal-04381315

HAL Id: hal-04381315

https://inria.hal.science/hal-04381315v1

Submitted on 31 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à 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.

<figure><img src="image_2.png" /></figure>
# Hidden-Variables Genetic Algorithm for Variable-Size Design Space Optimal Layout Problems with Application to Aerospace Vehicles

Juliette Gamot<sup>a,b</sup>, Mathieu Balesdent<sup>a</sup>, Arnault Tremolet<sup>a</sup>, Romain Wuilbercq<sup>a</sup>, Nouredine Melab<sup>b</sup>, El-Ghazali Talbi<sup>b</sup>

## Abstract

The optimal layout of a complex system such as aerospace vehicles consists in placing a given number of components in a container in order to minimize one or several objectives under some geometrical or functional constraints. This paper presents an extended formulation of this problem as a variable-size design space (VSDS) problem to take into account a large number of architectural choices and components allocation during the design process. As a representative example of such systems, considering the layout of a satellite module, the VSDS aspect translates the fact that the optimizer has to choose between several subdivisions of the components. For instance, one large tank of fuel might be placed as well as two smaller tanks or three even smaller tanks for the same amount of fuel. In order to tackle this NP-hard problem, a genetic algorithm enhanced by an adapted hidden-variables mechanism is proposed. This latter is illustrated on a toy case and an aerospace application case representative to real world complexity to illustrate the performance of the proposed algorithms. The results obtained using the proposed mechanism are reported and analyzed.

**Keywords:** Multi-disciplinary optimization, Optimization, Aerospace Design, Genetic Algorithms

## 1. Introduction

### 1.1. General context

The field of Multidisciplinary Design and Optimization introduces a wide range of optimization techniques capable to generate innovative preliminary design solutions for various complex systems including automotive, satellites, reusable launchers, etc. [1] The design process of aerospace concepts requires a strong coupling between all the disciplines involved in their preliminary sizing. While a number of engineering fields such as aerodynamics, propulsion, structure and flight mechanics are often tightly integrated at the early design stage, the design of the internal layout of future systems [1] is, however, often put aside and is rarely part of a fully integrated design process. In fact, the internal layout problem is often solved by hand or by a set of simple heuristic rules (e.g. expert system) able to mimic the cognitive process of experts. For instance, in the process of designing a new satellite platform, engineers must take into account subsystems' incompatibility and then position each component to guarantee a number of mission requirements. However, by the fact that this process is performed in the last

<footnote><sup>a</sup>ONERA/DTIS, Université Paris-Saclay, Palaiseau, France</footnote>

<footnote><sup>b</sup>INRIA, Université de Lille, Villeneuve d'Ascq, France</footnote>
steps of the design procedure, it does not guarantee that an overall optimal solution has been identified at preliminary design stages. Indeed, the arrangement of components often has a first-order impact on the performance of the system (e.g. for flying qualities of an aircraft) and can thus be critical to the feasibility of a concept. The main concern is thus the automated optimal design of the internal layout of complex systems that makes it compatible with the inclusion in the early design phases.

The optimal layout design of a system consists in placing a set of components (various instruments and equipment) into an available space. The layout optimization often involves minimizing or maximizing one or several objective(s) (e.g. minimize the inertia, the volume, the location of the center of gravity) while satisfying multiple constraints. For illustration purposes, in this paper, the layout optimization of satellite module is derived, without loss of generality. This problem is a representative example of layout optimization problems [2, 3, 4] and its formulation will be extended in this paper. Indeed, in most of real-world engineering design problems, many architecture choices have to be made (e.g. number of engines for an aircraft, number of tanks of fuel for a satellite, etc.) and are often represented as discrete variables in addition to other continuous design variables. Furthermore, the choices made in terms of architecture or topology have a critical impact on the problem definition (number of variables to be optimized, number of constraints). For instance, a possible choice would be either to place in the container two small tanks of fuel or a large one. The number of components is consequently not the same in both cases and hence, the number of decision variables (e.g. the positions of the tanks of fuel for instance) will vary from one sub-problem to another. Allowing the number of components to vary during the optimization may provide a better solution at the end. Consequently, the purpose is to provide a catalog of all the components which can possibly be chosen to be part of the system layout and let an optimization algorithm find the best combinations of components, as well as their positions in the container. This type of problems is referred to in the literature as both mixed-variable problems and variable-size design space (VSDS) problems [5]. Thus, in this paper, a new formulation of the optimal layout problem is proposed including the VSDS aspect which is, to the best of our knowledge, not covered in the literature. Then, a method dedicated to this kind of problems for optimal layout is proposed and associated to a genetic algorithm (GA). The algorithms proposed to solve such problems are described in Section 2.2.

In order to solve this problem, the simplified model of the international commercial communication satellite module (INTELSAT-III) is considered as a benchmark [2]. Figure 1 shows different views of this satellite module.

## 1.2. Optimal layout problem

To illustrate the proposed mechanism, a satellite problem is presented. Indeed, the problem that is most of the time tackled in the literature is a fixed-size design space problem and consists in finding the layout that minimizes the inertia of the whole system composed with *N* cuboid and cylindrical components on two bearing plates (or four surfaces) while respecting certain geometric constraints (e.g. no overlapping between components, accurate placement of the center of gravity of the module). According to the studies [2, 3], *N* varies from a few dozens to one hundred.
<figure><img src="image_3.png" /><figcaption>Figure 1: Different views of the simplified representation of the satellite module [2].</figcaption></figure>

Generally, the optimal layout problem can be expressed as follows:

$$ \left\{ \begin{array}{l} \text{Minimize } f(\mathbf{x}, \mathbf{z}) \\ \text{where: } \mathbf{x} \in \mathbb{R}^{n_x}, \mathbf{z} \in \mathbb{Z}^{n_z} \\ \text{subject to:} \\ \mathbf{h}(\mathbf{x}, \mathbf{z}) = 0 \\ \mathbf{g}(\mathbf{x}, \mathbf{z}) \le 0 \end{array} \right. \qquad (1) $$

where $f$ is the objective function taking continuous design variables $\mathbf{x}$ and discrete design variables $\mathbf{z}$ as arguments. $\mathbf{h}$ and $\mathbf{g}$ stand for respectively equality and inequality constraints.

Regarding the satellite module layout problem, the continuous design variables $\mathbf{x}$ are most of the time the positions of the components on a given surface and the discrete design variables $\mathbf{z}$ are the orientations of the several components (e.g cuboid, often 0 or 90 degrees) or the number of the plate on which the components have to be placed. While minimizing the inertia of the system, the following constraints must be satisfied: no overlapping between components and between components and the container (equality constraints), and the center of gravity of the module must be positioned accurately given a tolerance (inequality constraints).

In the literature, the number of components is set at the beginning of the study and a plate number is assigned to each of the components [2, 3]. This problem belongs to the category of "Fixed-size variable design space problems" [5]. The algorithms that can be used to solve such problems are described in Section 2.1.

In this paper, the previous formulation is extended in order to let the optimizer find the best combination of components, instead of dealing with a fixed set of components that have to be placed in the container. This new formulation of the optimal layout problem is detailed in Section 3. The optimizer has now to optimize the list of components to place in the container as well as their positions and orientations. The extended problem belongs to the VSDS class of problems. The methods that can be used to solve it are reviewed in Section 2.2.

The main contributions of the paper are as follows. The formulation of the problem 1 is extended in order to take into account the VSDS aspect. To solve it, a mechanism entitled "Hidden-Variables Mechanism" is adapted from [6]. The resulting adapted algorithms are applied to the extended satellite module optimal layout problem as a
representative example of optimal layout problems. Moreover, the constraints handled
in the problem described above are essentially geometrical (e.g. center of mass, over-
lap). Functional constraints must be added in order to describe the problem more
realistically if real-world problems are meant to be tackled. For instance, some compo-
nents are incompatible for functional reasons and must be placed at a certain distance
apart. The functional constraints can describe any requirements that the system needs
to behave properly (e.g. existence of a radiation threshold in the container).
Finally, a performance study on the compactness of the layout container (corresponding
to the occupation rate of the container by the components) is conducted. Most of the
time in the existing literature, the compactness is set during the whole study, and often
to a low value. The more the compactness increases, the more the constraints might be
difficult to handle.

The rest of the paper is organized as follows: Section 2 reviews the existing methods either for fixed-size and variable-size design space problems. Section 3 introduces the new mathematical formulation of the variable-size layout optimization problem. In Section 4, the proposed mechanism is described as well as its application to a GA. Section 5 illustrates the proposed algorithms on a toy case. Finally, the proposed methods are applied in Section 6 to a real-world benchmark test case and the results are analyzed.

## 2. State of the Art

### 2.1. *Review of the fixed-size design space methods*

The methods developed in the literature in order to tackle the problem formulated
in the system of equations 1 are reviewed in this section. This type of problems belongs
to the class of NP-hard problems due to its mathematical complexity, and is therefore
not solvable by exact optimization methods [4]. During the past 20 years, various meth-
ods have been developed in order to solve layout optimization problems first defined
by Cagan et al. [7]. In [8], a number of approaches used to solve the facility layout
problems (mostly meta-heuristics) are reviewed. Meller et al. introduced a simulated
annealing algorithm to solve facility layout problems [9]. In [10], Jacquenot used a
genetic algorithm (GA) to address multi-objective layout problems adding a separation
algorithm in order to facilitate the treatment of overlapping constraints. Liu et al. pro-
posed a Multi-Objective Particle Swarm Optimization algorithm to solve unequal-area
facility layout problems [11]. In [12], a Covariance Matrix Adaptation - Evolution Strat-
egy (CMA-ES) is compared to a Particle Swarm Optimization (PSO) algorithm and a
GA to solve layout optimization problem, giving advantage to the CMA-ES algorithm.
Hasan et al. [13] proposed an extended Ants Colony Optimization (ACO) algorithm to
solve Dynamic Layout problems.

With the increase in the number of design objectives, constraints or design vari-
ables, other techniques have been proposed in order to improve the computational per-
formance of evolutionary algorithms (EAs). Among them, cooperative co-evolutionary
algorithms first introduced by Potter and De Jong [14] and based on the *divide and con-
quer* method along with the biological model of co-evolution of cooperating species have
been developed. Ma *et al.* recently proposed a survey on cooperative co-evolutionary
algorithms [15]. Those algorithms were successfully applied to satellite layout optimization [3, 4, 16].

Metaheuristics methods have also been often hybridized between themselves [17] where a GA is hybridized with differential evolution, artificial bee colony and PSO in order to optimize layouts for multi-robot cellular manufacturing systems. EAs can also be hybridized with other methods as in [18] where heuristic rules are coupled with EAs like PSO and ACO and applied to the layout optimization of a satellite module. Liu et al. [19] tried a Multi-agent GA for Constrained Layout Optimization in Satellite Cabin problems defining evolutionary operators adapted to a multi-agent environment.

Metaheuristics have also been hybridized with heuristic techniques especially for the balance circular packing problem which consists in placing equal or non-equal radius circular components in a circular container while minimizing the congestion along with placing the center of mass of the system of circles. In [20], a GA optimizes the order of the components to place while a greedy algorithm based on the order-based positioning technique and heuristic rules construct the layout component by component. The same authors then extended the placement heuristic rules to parallelepipedic items in [21]. In [22], EAs are also hybridized with a new load balancing heuristic to tackle the optimal layout satellite problem.

Other methods than metaheuristics have been applied to layout optimization problems even if they are less investigated. Tarkesh et al. presented an approach based on multi-agent system to solve a facility layout problem where the procedure can be assimilated to a Markov chain and modeled as a Markov Decision Process [23]. Burggräf et al. conducted a study on the use of machine learning as resolution techniques for facility layout problems in [24]. Unsupervised learning, supervised learning and reinforcement learning (RL) are explored to solve these problems. More specifically, Tsuchiya et al. [25] focused on a neural network approach to optimize the layout of *N* components on *N*² locations. Despite the small amount of articles using RL to tackle aerospace vehicles optimal layout problems, some recent articles use this method to address chip floorplanning which is a similar layout problem. In [26], a cyclic combination of RL and simulated annealing (SA) is proposed to solve integrated circuit placement. This cyclic application of RL and SA is used to provide a better initialization for SA. In [27], the authors developed a deep RL approach capable to learn from its experience of achieving the layout of the chip in order to become better and faster. A trained agent places the macros one by one on the chip and by the end obtains a reward which is function of the wirelength, the congestion and the density of the chip. Moreover, the authors created a neural network architecture in order to predict reward on new lists of components and use it as the encoder layer of their policy. In [28], a joint learning method for solving both placement and routing problems is detailed. It integrates reinforcement learning with a gradient-based optimization scheme. As in [27], a policy network learns how to maximize the rewards.

## 2.2. Review of the variable-size design space methods

As the problem formulated in the system of equations 1 will be extended to become a VSDS problem, the methods designed to handle such problems are reviewed in this section.

Most of the aforementioned algorithms are usually designed to handle fixed-size design space problems even though some of them can address the mixed-variable prob-
lems. Some previous research has been conducted on VSDS problems. Pelamatti [5] extended Bayesian Optimization (BO) algorithms to mixed-variable and VSDS prob- lems. However, BO algorithms are used for small numbers of design variables (typically lower or equal to 10) and are not applicable for layout optimization problem in which a few hundreds optimization variables have to be handled [5]. Dasgupta et al. [29] developed a Structured GA which utilizes a multi-layer structure for the chromosome initially designed to tackle non-stationary function optimization. Gentile et al. [30] used the same idea to tackle VSDS problems applied to satellite tracking problems. Hutt et al. [31] created a new crossover operator used with a GA in order to perform mean- ingful crossover between variable-length chromosome. In [32], a Dynamic-Size Multiple Population Genetic Algorithm (DSMPGA) is described. A certain number of initial subpopulations of fixed-size design spaces are generated and classical genetic operators are carried out at each generation. Finally, the process leads to an increase in the size of subpopulations of more fit solutions and a decrease in the size of subpopulations of less fit solutions. Recently, a self-adaptive PSO using the self-adaptive mechanism strategy as well as a parameter self-adaptive mechanism has been proposed for solving large-scale feature selection problems [33, 34].

Another idea to solve VSDS problems is the Hidden-Genes GA (HGGA) first intro-
duced by Abdelkhalik in [6, 35]. In HGGA, all chromosomes have the same length but
only some of their genes are expressed during the objective and constraints evaluations.
To the best of our knowledge, none of the previous methods have been applied to op-
timal layout problems. Moreover, BO as well as DSMPGA are not adapted to large
combinatory VSDS problems [5]. The Structured GA requires some engineering ex-
pertise on the problem tackled regarding its encoding and is consequently not adapted
to address various VSDS layout problems. The proposed mechanism in this paper is
inspired and adapted from HGGA. It is the most versatile method and requires very
few engineering expertise on the problem tackled regarding its encoding, unlike the
Structured Genetic Algorithm. It also allows to tackle large-sized problems including
several thousands of subproblems unlike the Bayesian Optimization and the DSMPGA.

3. Description of variable-size optimal layout problem

3.1. *Illustrative example*

The classical optimal layout problems described in the literature have to be extended
as mentioned in Section 1 to address general layout design and subdivision optimization.
The main extension consists in dealing with VSDS features. As an example, a very
simple case is considered in which only a tank of fuel has to be placed in the container.
Several architecture choices might therefore be possible, without loss of generality. For
instance, for a given amount of fuel, one large tank may be placed, as well as two
smaller tanks, or even three smaller tanks of fuel. Figure 2 shows the three possible
layouts for the same problem definition corresponding to this example. The possible
decompositions of the components are introduced by the designer and the optimizer
will draw from it. Thus, the subdivisions of the components are optimized along with
the layout.

In this paper, in order to propose a general mathematical formulation of the mixed-
variable VSDS problem, the design variables, the objective function and the constraints
considered are described.
<figure><img src="image_4.png" /><figcaption>Figure 2: Three possible layouts for the same component to be placed with w the number of tanks.</figcaption></figure>

## 3.2. Design variables

The design variables can be split into 3 categories [5]:

* Continuous variables: **x**. These variables refer to real numbers, each of them defined in a given interval. Example: position and orientation of the components.

* Discrete variables: **z**. These variables are non-relaxable variables, defined among a finite set of possibilities. Example: the number of the bearing plate on which a component will be positioned.

* Dimensional variables: **w**. These variables are also non-relaxable variables defined among a finite set of possibilities. According to their values, the number and type of continuous and discrete variables that have to be optimized in the problem may vary and also the considered constraints. Example: the subdivision choices.

Compared to the fixed-size design space problem definition [2, 3, 19], the dimensional variables are added in order to translate the VSDS features to the optimal layout problem. The dimensional variables are illustrated in Figure 2: to each value of *w* corresponds a subdivision of the components. If *N* components must be placed and each of them has $n_i$ subdivisions (for $i \in \{1, ..., N\}$), then the number of configurations corresponds to the cardinality of the set of achievable values of *w*, $F_w$, and is defined by:

$$Card(F_w) = \prod_{i=1}^{N} n_i$$

## 3.3. Objective function

One of the most popular objective function to minimize in optimal layout problems is the inertia of the whole module calculated at the current center of mass [36]. The three coordinates systems initially proposed by Sun et al. [37] are adopted in order to calculate the total inertia of the module:

* $O''x''y''z''$: the coordinate system related to each component. $O''$ corresponds to the center of inertia of the component and the axes are defined as shown in Figure 3 as the symmetry axes of the components.

* $O'x'y'$: the coordinates system related to the system of components. $O'$ represents the current centroid of the system of components and the axes are defined as the symmetry axes of the module.
• Oxy: the coordinates system related to the module. O is the geometric center of the container and the axes are its symmetry axes. Figure 3 illustrates the three systems of coordinates [2].

<figure><img src="image_5.png" /><figcaption>Figure 3: Sketch of the coordinates systems, [2]</figcaption></figure>

The total inertia is calculated in the O'x'y'z' system of coordinates and is defined as:

$$f(\mathbf{x}, \mathbf{z}, \mathbf{w}) = I_{x'} + I_{y'} + I_{z'}$$

Each component has a solid inertia which depends on its shape and is expressed in its O"x"y"z" coordinates system. The inertias along the three axes are noted $I_{x''i}$, $I_{y''i}$ and $I_{z''i}$. Thus, the inertia of the component in the system of coordinates Oxyz is:

$$I_{xi} = I_{x''i} \cos \alpha_i^2 + I_{y''i} \sin \alpha_i^2 + m_i(c_{iy}^2 + c_{iz}^2)$$

$$I_{yi} = I_{y''i} \cos \alpha_i^2 + I_{x''i} \sin \alpha_i^2 + m_i(c_{ix}^2 + c_{iz}^2)$$

$$I_{zi} = I_{z''i} + m_i(c_{ix}^2 + c_{iy}^2)$$

where $m_i$ is the mass of the component $i$, $c_{ix}$, $c_{iy}$, $c_{iz}$ are the coordinates of its center of inertia in the system of coordinates Oxyz and $\alpha_i$ its orientation.

A configuration $k$ where $k \in \{1, ..., Card(F_w)\}$ is now considered, composed of $N_k$ components. The Huygens theorem is used in order to express the inertia of this whole system of components in the system of coordinates O'x'y'. The coordinates of the current centroid of the system of components are noted $(x_c, y_c, z_c)$ and $m = \sum_{i=1}^{N_k} m_i$.

$$I_{x'} = \sum_{i=1}^{N_k} I_{xi} - m(y_c^2 + z_c^2)$$

$$I_{y'} = \sum_{i=1}^{N_k} I_{yi} - m(x_c^2 + z_c^2)$$

$$I_{z'} = \sum_{i=1}^{N_k} I_{zi} - m(x_c^2 + y_c^2)$$

$I_{x'}$, $I_{y'}$ and $I_{z'}$ are the inertia of the module along each axis and calculated at the point O'.
### 3.4. Constraints

The constraints considered in this paper can be split into 2 categories: geometrical constraints and functional constraints. Geometrical constraints that are considered are as follows:

- No overlap between the components. Figure 4 shows two layouts where the overlap constraint is respectively violated because of two components overlapping each other and solved because no overlap is observed.

With the same formalism as in Section 3.3 the overlap constraint is expressed as:

$$h_1(\mathbf{x}, \mathbf{z}, \mathbf{w}) = \sum_{i=1}^{N_k-1} \sum_{j=i+1}^{N_k} \Delta V_{ij} = 0$$

Where $\Delta V_{ij}$ is the volume of intersection between two components i and j, and is function of the components centroids and their orientation.

<figure><img src="image_6.png" /><figcaption>Figure 4: (a) Overlap between components (b) The overlap constraint is solved.</figcaption></figure>

- No overlap between the components and the exclusion zones which may represent some components fixed to the container, for instance connection buses. Figure 5 shows two layouts where the exclusion constraint is respectively violated because of one component overlapping the exclusion zone and its resolution. With the same formalism as before, the exclusion constraint is expressed:

$$h_2(\mathbf{x}, \mathbf{z}, \mathbf{w}) = \sum_{j=1}^{N_k} \Delta V_i^E = 0$$

where $\Delta V_i^E$ is the volume between a component and the exclusion zone, and is function of the components and exclusion zone centroids and orientation.

- The center of mass of the whole module must be placed at the center of the container. Figure 6 illustrates two layouts where the center of mass constraint is respectively violated because the center of mass is not accurately positioned and solved because the center of mass is in the right zone. Using the same formalism as before, this constraint can be expressed as:

$$g_1(\mathbf{x}, \mathbf{z}, \mathbf{w}) = \sqrt{(x_c - x_e)^2 + (y_c - y_e)^2 + (z_c - z_e)^2} \le \delta$$
<figure><img src="image_7.png" /><figcaption>Figure 5: (a) Overlap between a component and the exclusion zone (b) The exclusion constraint is solved.</figcaption></figure>

where $(x_c, y_c, z_c)$ are the coordinates of the current centroid of the whole module and $(x_e, y_e, z_e)$ are the coordinates of the ideal position of the centroid. The geometric center $(0, 0, 0)$ is considered here. $\delta$ represents a tolerance which corresponds, in this paper, to a circle centered about the origin of the $(Oxyz)$ coordinates system and whose radius is taken as 1% of the outer radius of the container, without loss of generality.

<figure><img src="image_8.png" /><figcaption>Figure 6: (a) Center of mass out of the tolerance zone (b) Center of mass in the tolerance zone.</figcaption></figure>

A variety of functional constraints can also be added to the problem formulation via the use of special components that induce further restrictions on the feasibility of the layout.

- For instance, the existence of specific components may involve some restrictions in the layout. For example, fuel components and energy components must be kept at a certain distance from each other for functional reasons such as not exceeding a radiation (e.g. heat, electromagnetic) threshold at any point of the module. Figure 7 shows two layouts where the functional constraint is respectively violated because the energy and fuel components are too close and solved because the minimal distance between them is respected. With the same formalism as before, considering the configuration $k$ with $N_k$ components and $N_k^f$ fuel components and $N_k^e$ energy components, the constraint is expressed as:

$$g_3(\mathbf{x}, \mathbf{z}, \mathbf{w}) = \sum_{i=1}^{N_k^e} \sum_{j=1}^{N_k^f} \max(D_{min} - D(C_i^e, C_j^f), 0)$$

Where $C_i^e$ is the energy component $i$ and $C_j^f$ is the fuel component $j$ and $D(C_i^e, C_j^f)$ is the distance between their centroids in the current layout. $D_{min}$ is the minimal distance to be respected and is function of the type of components. Without loss of
generality, other types of components can be considered within this formalism (e.g. for electromagnetic compatibility).

<figure><img src="image_9.png" /><figcaption>Figure 7: (a) Components too close (b) Components spaced from the minimal distance.</figcaption></figure>

### 3.5. Mathematical formulation of the general variable-size optimal layout Problem

The generic single-objective VSDS optimal layout problem can be mathematically formulated as follows:

$$ 
\left\{ 
\begin{array}{l} 
\text{Minimize } f(\mathbf{x}, \mathbf{z}, \mathbf{w}) \\ 
\text{where: } \mathbf{x} \in F_x(\mathbf{w}) \subseteq \mathbb{R}^{n_x(\mathbf{w})}, \mathbf{z} \in F_z(\mathbf{w}) \subseteq \mathbb{Z}^{n_z(\mathbf{w})}, \mathbf{w} \in F_w \\ 
\text{subject to :} \\ 
\mathbf{h}(\mathbf{x}, \mathbf{z}, \mathbf{w}) = 0 \\ 
\mathbf{g}(\mathbf{x}, \mathbf{z}, \mathbf{w}) \le 0 
\end{array} 
\right. 
$$

Where $f$ is the objective function, $\mathbf{x}$ is a $n_x(\mathbf{w})$-dimensional vector (continuous variables), $\mathbf{z}$ is a $n_z(\mathbf{w})$-dimensional vector (discrete variables) and $\mathbf{w}$ is a $n_w$-dimensional vector (dimensional variables). $\mathbf{h}$ are the equality constraints defined by a $n_h(\mathbf{w})$-dimensional vector and $\mathbf{g}$ are the inequality constraints defined by a $n_g(\mathbf{w})$-dimensional vector. In this formulation, because of the dimensional variables, the domains of definition ($F_x(\mathbf{w})$, $F_z(\mathbf{w})$) of the optimization variables are functions of the value taken by the dimensional variables. Furthermore, the number and type of constraints evolve also according to the value taken by the dimensional variables.

To summarize, the problem to solve is a large scale, mixed-variable and VSDS problem, as well as strongly constrained. The sizes of the definition spaces of the continuous and discrete variables as well as the expression of the constraints vary along with the number of components selected to be in the container. For instance, if one component is added to the list of the components, the number of continuous variables increases by 2 if it is a cylinder and by 3 if it is a cuboid (position of the center of inertia and orientation), the number of discrete variables increases by 1 (the plate to position the new component). Moreover, the expressions of the constraints will also be modified. The expressions of the overlap constraint and the exclusion constraint are changing because the number of components $N_k$ is modified. The functional constraint is changing too if the component is a fuel or an energy component. Finally, the center of mass of the module is recalculated and will be different but the expression of the centroid constraint remains unchanged.
# 4. Hidden-variables mechanisms for genetic algorithms

## 4.1. General description of hidden-variables technique

In order to solve VSDS problems, an adaptation of an hidden-variables mechanism is proposed in this paper and is added to a GA. This mechanism consists in modifying the encoding of the design variables. Indeed, all the design variables are implemented so that all the individuals (e.g the chromosomes) in the population have the same length. However, some of the variables are hidden, meaning that they will not be taken into account during the objective function and constraints evaluations. For the aforementioned optimal layout problem, the hidden variables represent the design variables **x** and **z** of the components of the subdivisions that are not selected by the dimensional variables **w** to be part of the current layout. On the contrary, the revealed design variables correspond to the variables of components selected to be in the container and so used to calculate the characteristics of the module such as the inertia or the position of the center of mass.

Thus, this method allows to tackle the VSDS aspect of optimization problems while ensuring that all chromosomes (corresponding to the individuals of a population) have the same length which enables to use many of existing operators. This method is preferred to the other methods mentioned in Section 2.2 such as Bayesian Optimization or DSMPGA. Indeed, it is well suited for the large number of design variables. It is a flexible and generic mechanism limiting the introduction of expert knowledge during the implementation process unlike the Structured-Chromosome solution and relatively simple to be implemented. In addition, it allows to keep an entire freedom of choice for the evolutionary operators unlike some techniques which do not guarantee the same number of design variables for all individuals of the population.

Depending on the method used to hide the variables, some of the evolutionary operators must nevertheless be adapted. Two methods are proposed in order to hide variables and those methods will be applied to a GA. Those methods as well as the resulting adaptations are detailed in the following section.

## 4.2. Implementations of the hidden-variables mechanism with a genetic algorithm

Different methods exist for the implementation of the hidden-variables mechanism. Two of them are described in the following section.

### 4.2.1. First method: dimensional variables

The first possibility to hide variables is to implement dimensional variables as design variables. More specifically, dimensional variables responsible for the choice of hidden or revealed variables are added to the design variables. Before evaluating the objective function and the constraints, the dimensional variables are read for each candidate solution and their values indicate which design variables of the candidate solution must be taken into account (and so which ones must be ignored) to calculate the objective and constraints. Figure 8 illustrates this method on an example. Taking the case of the optimal layout of a satellite module as a representative example, two subdivisions for a unique component can be chosen between one cylindrical component or two smaller ones. As only two configurations of the satellite module are considered, a unique dimensional variable taking binary values is enough to describe this feature. If the dimensional variable value is 0 then the first subdivision is chosen and the design variables linked are revealed and, on the contrary, if the dimensional variable value is
1 the second subdivision is chosen and the other design variables are revealed. It is worth noting that there exists various ways to define dimensional variables in order to describe the possible configurations.

<figure><img src="image_10.png" /><figcaption>Figure 8: Illustration of the implementation of the hidden-variables mechanism thanks to dimensional variables. Blue variables are the revealed variables while grey ones are hidden ones.</figcaption></figure>

Taking into account a GA as optimization algorithm, this consists in considering additional genes to handle the dimensional variables without modifying the main mechanisms and operators of the GA. Table 1 sums up the operators that can be used without loss of generality.

<table><caption>Table 1: Operators used for GA with hidden-variables mechanism</caption><thead><tr><th>Step</th><th>Operator</th></tr></thead><tbody><tr><td>Constraints handling</td><td>Constraint-Dominance [38]</td></tr><tr><td>Selection</td><td>Tournament</td></tr><tr><td>Crossover</td><td>Simulated Binary Crossover [39]</td></tr><tr><td>Mutation</td><td>Polynomial Mutation [40]</td></tr><tr><td>Replacement</td><td>Non-dominated truncating</td></tr></tbody></table>

### 4.2.2. Second method: tags

Another possible way to deal with VSDS is to introduce tags as proposed in [6]. In this method, a tag vector is attached to each chromosome of the population such that a tag value is assigned to each gene of the chromosome. If the value of the tag is 0, then the corresponding gene will not participate in the objective function evaluation and reciprocally. This mechanism is shown in Figure 9a. The tags are a direct translation of the dimensional variables: their role is to choose which variables will be expressed or not during the fitness evaluation as well as the corresponding constraints to activate. Figure 9b illustrates the adaptation on the same example as in the previous section. If the second subdivision of the component is chosen to be part of the layout, the tag vector will activate all the design variables (coordinates of the center of mass and orientation if needed) to be part of the objective function and constraints evaluations.

As the chromosomes are enhanced by tags, the operators of the GA must be compatible with the tags which will take part in the evolution process. The chromosomes and tags will undergo independent operators of crossover and mutation as proposed in [6].
<figure><img src="image_11.png" /><figcaption>Figure 9: Illustration of the tag mechanism.</figcaption></figure>

## Crossover

For the chromosomes, the crossover operator can be chosen among all the operators available for "classical" genetic algorithms [40]. For the tags, a *n*-points crossover operator is chosen in this paper, without loss of generality [40]. This mechanism must be adapted as not all the points of the tag vector can be crossover points because of the fact that the design variables are not independent from each other. The crossover operator on the tags must provide a feasible configuration of subdivisions. Figure 10 illustrates the principle of the *n*-points crossover on the tags adapted for the subdivisions of the components. On the example, two components able to subdivide themselves into two smaller components are considered so that there are four possible configurations of components in the container. For each component, only one of the two subdivisions can be present in the container and so in the tag vector, amongst the three points that may be considered as crossover points only one (indicated in red) guarantees the fact that the crossover operation will lead to feasible individuals.

<figure><img src="image_12.png" /><figcaption>Figure 10: Crossover operator for the tags on an example.</figcaption></figure>

## Mutation

For the mutation operator, again the mechanism differs according to the chromo-
somes or tags. For the chromosomes, the mutation operator can be chosen amongst all the operators available for "classical" genetic algorithms. For the tags, a bit flip operator can be applied [40]. Like the crossover operator, it must be adapted for the subdivision case to provide feasible solutions. The bit flip consists in fact in flipping the subdivision chosen. Hence the tags cannot be flipped randomly as for each component only one tag must be equal to one in order to select a unique subdivision amongst the possible ones. Figure 11 illustrates the mutation operator designed for the tags. Only a few mutations are possible to guarantee the feasibility of the solution.

<figure><img src="image_13.png" /><figcaption>Figure 11: Mutation operator for the tags on an example.</figcaption></figure>

As for the crossover operators, the probability of mutation for chromosomes and tags can differ as a 2-dimensional mutation operator is also used.

The two ways described in this section to implement the hidden-variables mechanism allowing a GA to tackle the VSDS nature of the problem (dimensional variables and tags) will be compared in Section 5 in a toy case and in Section 6 on a realistic design problem.

# 5. Illustration on a toy case

In this section, a test case that can be analytically solved is presented. This example allows to validate the hidden-variables mechanisms described in Section 4. Indeed, the methods are implemented on a very simple case in order to illustrate the hidden-variable mechanisms on a first example, as well as to illustrate the ability of the adapted algorithms to reach the optimum obtained analytically.

## 5.1. Configuration

The configuration of the test case is as follows:

* **Container:** one single-sided bearing plate.

* **Components:** two cylindrical components which can be subdivided into 2 sub-components resulting in the 4 different configurations of subdivisions illustrated in Figure 12. For illustration purposes, in all the following figures, one of the components will be colored in blue while the other in green to differentiate them.
* **Design variables:** the coordinates of the center of gravity of each component parameterized in cylindrical coordinates (e.g. radius and angle: $(r_{j,k}^i, \theta_{j,k}^i)$) for component $i$, sub-component $k$ of the subdivision $j$. They correspond to 12 genes in each chromosome.

* **Objective function:** the inertia of the module (to be minimized).

* **Constraints:** no overlapping between the components and the center of gravity must be placed at the center of the bearing plate (with a tolerance zone set equal to 1% of the outer radius of the plate).

<figure><img src="image_14.png" /><figcaption>Figure 12: The four possible configurations of subdivisions for the toy case.</figcaption></figure>

Figure 13 shows one of the optimal layouts (the problem is rotationally symmetric and so there is an infinite number of optimal solutions). For this toy case, the optimal value of inertia, that can be found analytically, is $4.49 \times 10^5$.

<figure><img src="image_15.png" /><figcaption>Figure 13: One of the optimum configurations and layouts of the case test</figcaption></figure>

## 5.2. *Hidden-variables mechanism implementations*

As described in Section 4, different ways for implementing the hidden-variables mechanism are possible. Three implementations will be studied on the toy case in
order to verify their behavior. Figure 14 illustrates the three corresponding encodings of the chromosomes.

The two first ones correspond to the first method developed in Section 4.2.1 which uses dimensional variables (DV) directly integrated as design variables. Here, either one dimensional variable is used taking a value between 1 and 4 or two dimensional variables are used taking binary values. In both cases, the dimensional variables represent the 4 different configurations and their values allow to express the corresponding genes during the objective and constraint evaluations. Those three ways to implement the proposed mechanism will be applied to a GA.

<figure><img src="image_16.png" /><figcaption>Figure 14: Three ways of implementing the design variables.</figcaption></figure>

To sum up, the three methods implemented on the toy case are:

* A hidden-variables GA with the tag method to hide genes (GA-tags);

* A GA with the numerical dimensional variables method as hidden-variables mechanism (GA-DV-num);

* A GA with the binary dimensional variables method as hidden-variables mechanism (GA-DV-bin).

Appendix B encompasses the Tables which sum up the operators, strategies and hyper-parameters (set thanks to a parametric study) for all algorithms: GA-tags on Table B.6, as well as GA-DV-bin and GA-DV-num on Table B.7. Table B.8 in Appendix B sums up the numerical configuration for all three algorithms. Figure 15 shows the convergence curves obtained for each method.

The results show that the GA enhanced by several hidden-variables mechanisms implementations manage to reach the optimum analytically obtained of the toy case. On this example, all the three methods are quite equivalent in terms on convergence speed. Indeed, these methods require about 40 iterations to find the optimal configuration.

Thus, this toy case shows that a GA, coupled with an appropriate genotype representation, is indeed capable of successfully solving a VSDS problem. In the next section, the various methods are being applied to a more representative application to test their efficiency on a more complex test case.
<figure><img src="image_17.png" /><figcaption>Figure 15: Convergence curves for each hidden-variables mechanism implementations with the described GA.</figcaption></figure>

# 6. Application of the proposed hidden-variables mechanisms to the optimal layout of a satellite

In order to illustrate the performance of the proposed methods on a representative industrial case, the application of the satellite layout provided from [2, 3, 4] is extended as a VSDS problem. The configuration of the problem and numerical schemes are outlined and the obtained results analyzed.

## 6.1. *Configuration of the problem*

Considering the INTELSAT-III satellite introduced in Section 1, some changes are added as well as the variable-size design space aspect. First of all, the orientations of the components are now continuous design variables instead of discrete ones. An exclusion zone is added on the bearing plate in order to break the symmetry of the problem. A functional constraint is also added in order to simulate the inconsistency between some components. All these modifications make the problem solving much complicate. To sum up, the configuration of the application case is as follows:

* **Container:** one one-sided plate of the satellite module with an exclusion zone.

* **Components:** twelve components (cylinders and cuboids) which can be subdivided into 2 to 4 subcomponents such that there are 3888 possible configurations as detailed in Table A.5 in Appendix A.

* **Design variables:** the 2D position of the center of gravity of each component and its orientation (as a continuous variable) so 129 genes.

* **Objective function:** the inertia of the module (to be minimized).

* **Geometric constraints:** no overlapping between the components. No overlapping between the components and the exclusion zones. The center of gravity must be placed at the center of the bearing plate (with a tolerance of 1% of the outer radius of the plate).
* **Functional constraint:** the fuel components centroids must be at a minimal distance of 300 mm from the energy components centroids.

Thus, the length of the chromosomes for this configuration varies linearly along with the number of cylinder and cuboid components. If $N_{cyl}$ and $N_{cub}$ corresponds respectively to the number of cylinders and cuboids which can possibly be chosen to be part of the layout, the length of the chromosomes $L_c$ can be expressed as follows:

$$L_c = 2N_{cyl} + 3N_{cub} \qquad (2)$$

Moreover, the size of the components will be modified in order to study the performance of the proposed algorithm with respect to the occupation rate of the container. The occupation rate (OR) is defined as:

$$OR = \frac{A_{components}}{A_{container}} \qquad (3)$$

where $A_{components}$ and $A_{container}$ correspond respectively to the total area of components and to the area of the available space in the container.

In this section, the satellite module problem described in Section 6.1 is derived for five occupation rates of the container: 30%, 40%, 50%, 60% and 70%. For summary purpose, Figure 16 shows the evolution on the bearing plate between a first random layout and one corresponding solved layout for 3 different occupation rates of the plate: 30%, 50%, and 70%. One can observe that the occupation rate induces overlap between components and the constraints may be more and more difficult to be satisfied.

<figure><img src="image_18.png" /><figcaption>Figure 16: Evolution between the initial plate and a feasible layout for the 3 occupation rates. The pink rectangle corresponds to the exclusion zone, the green cylinders correspond to the fuel components, the yellow cuboids to the energy components and the blue cuboids to other components (e.g. electronics ...).</figcaption></figure>

## 6.2. Implementations of the hidden-variables mechanisms

In this section, both possible implementations of the proposed mechanism are applied to a GA in order to address the satellite module layout problem.
### 6.2.1. First method: dimensional variable implementation (GA-DV)

The first implementation of the hidden-variable mechanism consists in a GA for which chromosomes have been enhanced with dimensional variables (GA-DV), as described in Section 4.2.1. Those variables are responsible for choosing the components to be placed in the container. Due to the high combinatorial of the problem (3888 possible configurations), a practical way to implement this method is to extend the chromosomes by as many dimensional variables as components that can be subdivided in the problem.

Table 2 illustrates the partial structure of a corresponding chromosome. For synthesis and understanding purposes, only one cylindrical component is considered. This component can either be placed itself in the container (S1), or be subdivided into two or three smaller components (respectively S2 or S3). The design variables correspond to the coordinates of the center of inertia of each sub-components (located in cylindrical coordinates) in the container (highlighted in orange). The chromosome is then elongated by as many dimensional variables as subdivided components. Consequently, in the example of Table 2 only one dimensional variable (highlighted in grey) is necessary taking the values from 1 to 3. The value of the dimensional variable indicates that the two sub-components of the second subdivision are chosen to be placed in the container. Thus, only design variables $r_{21}^1, \theta_{21}^1, r_{22}^1$ and $\theta_{22}^1$ of this chromosome take part into the objective and constraints evaluations.

<table><caption>Table 2: Structure (partial) of a chromosome for one cylindrical component for the GA-DV method.</caption><thead><tr><th>Components</th><th colspan="8">C1</th></tr><tr><th>Subdivisions</th><th colspan="2">S1</th><th colspan="3">S2</th><th colspan="5">S3</th></tr></thead><tbody><tr><th>Chromosome</th><td>r<sup>1</sup><sub>11</sub></td><td>θ<sup>1</sup><sub>11</sub></td><td>r<sup>1</sup><sub>21</sub></td><td>θ<sup>1</sup><sub>21</sub></td><td>r<sup>1</sup><sub>22</sub></td><td>θ<sup>1</sup><sub>22</sub></td><td>r<sup>1</sup><sub>31</sub></td><td>θ<sup>1</sup><sub>31</sub></td><td>r<sup>1</sup><sub>32</sub></td><td>θ<sup>1</sup><sub>32</sub></td><td>r<sup>1</sup><sub>33</sub></td><td>θ<sup>1</sup><sub>33</sub></td><td>2</td></tr></tbody></table>

### 6.2.2. Second method: tags implementation (GA-tags)

The second method to implement the hidden-variables mechanism in a GA corresponds to the tag implementation (GA-tags) described in Section 4.2.2. Table 3 shows the principle of chromosomes and tags implementation. The same example as in the previous section is used to illustrate the tag mechanism for the application case. Indeed, a tag vector is attached to the chromosome and aims to select one possible subdivision of the component to be part of the layout. The second subdivision is chosen thanks to the tag value equal to 1 in second place.

<table><caption>Table 3: Structure (partial) of a chromosome and associated tag (in grey) for one cylindrical component for the GA-tags method.</caption><thead><tr><th>Components</th><th colspan="8">C1</th></tr><tr><th>Subdivisions</th><th colspan="2">S1</th><th colspan="3">S2</th><th colspan="5">S3</th></tr></thead><tbody><tr><th>Chromosome</th><td>r<sup>1</sup><sub>11</sub></td><td>θ<sup>1</sup><sub>11</sub></td><td>r<sup>1</sup><sub>21</sub></td><td>θ<sup>1</sup><sub>21</sub></td><td>r<sup>1</sup><sub>22</sub></td><td>θ<sup>1</sup><sub>22</sub></td><td>r<sup>1</sup><sub>31</sub></td><td>θ<sup>1</sup><sub>31</sub></td><td>r<sup>1</sup><sub>32</sub></td><td>θ<sup>1</sup><sub>32</sub></td><td>r<sup>1</sup><sub>33</sub></td><td>θ<sup>1</sup><sub>33</sub></td></tr><tr><th>Tag</th><td colspan="2">0</td><td colspan="3">1</td><td colspan="5">0</td></tr></tbody></table>

### 6.2.3. Numerical settings

Given the combinatorial dimension of the problem, different operators have been tested and compared in order to promote diversity and to prevent premature convergence. A Taguchi's experiment plan [41] have been adopted to analyze in depth the
performance of a GA enhanced by the proposed mechanisms, with several evolutionary operators, on the satellite module layout problem and with different occupation rates. The Taguchi's experiment plan allows to study exploration and exploitation capabilities of the algorithms and therefore to select the best sequence of operators. Moreover, a parametric study has been run to set the hyperparameters. The following sequence of operators as well as hyperparameters are selected after a test campaign:

* **Constraint handling:** Stochastic Ranking [42] with probability $P_f = 0.45$.

* **Selection:** Tournament with 15 individuals.

* **Crossover design variables:** Simulated Binary Crossover (SBX) [39], with probability $P_c^g = 0.9$.

* **Crossover dimensional variables** (for GA-DV): SBX with probability $P_c^{DV} = 0.9$.

* **Crossover tags** (for GA-tags): 1-point, with probability $P_c^t = 0.9$.

* **Mutation:** Polynomial Mutation (PM) [40] with probability $P_m = 0.2$.

* **Replacement:** Non-Dominated Truncating [43].

The GA-tags and GA-DV methods are ran 20 times for the five occupation rates. For each occupation rate, the algorithms are randomly initialized, even though those initializations are the same between the two methods so that they are comparable. The objective evaluations cost is set to $3.5 \times 10^5$, distributed as follows: 500 individuals in the populations and 7000 generations.

## 6.3. *Experimental results*

Figure 17 shows the experimental results for both methods and the five occupation rates of the container. For each occupation rate, the median of the 20 convergence curves obtained for both algorithms are plotted, and the corresponding interquartile is shown. The interquartile corresponds to the gap between the quantiles at 25% and 75% to study the dispersion of the results. Furthermore, the best run is plotted as well. For each method, it corresponds to the run (among the 20) which allows to reach the smaller objective function value.

Table 4 sums up the corresponding numerical results. For both methods and all occupation rates, the number of successful runs are first reported. They correspond to the number of runs that reach a feasible solution. Then, the final median of the objective function as well as the final interquartile range are listed. Finally, the generation corresponding to the apparition of the first feasible solution is specified.

### 6.3.1. *General analysis*

First of all, Figure 17 and Table 4 highlight that both methods allow to find feasible solutions to the aforementioned VSDS problem. As a matter of fact, an appropriately set up GA enhanced with the proposed mechanism provides a layout of the satellite module among the 3888 possible configurations of components, and manages to solve the constraints for all occupation rates.
<figure><img src="image_19.png" /><figcaption>(a) Occupation rate: 30%</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>(b) Occupation rate: 40%</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>(c) Occupation rate: 50%</figcaption></figure>

<figure><img src="image_22.png" /><figcaption>(d) Occupation rate: 60%</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(e) Occupation rate: 70%</figcaption></figure>

Figure 17: Experimental results for both methods (GA-DV and GA-tags) and the five occupation rates.

Table 4 shows that until the 60% occupation rate, 100% of the runs find a feasible solution from random initializations. For the highest occupation rate, 25% of them fail to find a feasible solution, regardless of the algorithm. Indeed, the more the occupation rate of the container increases, the more the constraints are difficult to solve. For the same reason, it takes more and more time for both algorithms to find a first feasible solution as the occupation rate raises, and simultaneously the convergence speed decreases. From 50%, not all runs seem to have converged by the end of the chosen evaluations cost. Finally, the interquartile range (IQR) allows to characterize the robustness of the algorithms. For both algorithms and all the occupation rates, the final IQR is approximately between 5% and 10% of the median of the objective function. This indicates a reasonable dispersion of the final results.
<table><caption>Table 4: Numerical results obtained for both GA-tags and GA-DV algorithms.</caption><thead><tr><th></th><th>OR</th><th>GA-tags</th><th>GA-DV</th></tr></thead><tbody><tr><td rowspan="5">Nb of successful runs (a feasible solution is found)</td><td>30%</td><td><b>20</b></td><td><b>20</b></td></tr><tr><td>40%</td><td><b>20</b></td><td><b>20</b></td></tr><tr><td>50%</td><td><b>20</b></td><td><b>20</b></td></tr><tr><td>60%</td><td><b>20</b></td><td><b>20</b></td></tr><tr><td>70%</td><td>14</td><td><b>15</b></td></tr><tr><td rowspan="5">Final objective function (median)</td><td>30%</td><td>1.55e7</td><td><b>1.49e7</b></td></tr><tr><td>40%</td><td><b>1.87e7</b></td><td><b>1.87e7</b></td></tr><tr><td>50%</td><td>2.13e7</td><td><b>2.08e7</b></td></tr><tr><td>60%</td><td>2.47e7</td><td><b>2.36e7</b></td></tr><tr><td>70%</td><td><b>2.65e7</b></td><td>2.68e7</td></tr><tr><td rowspan="5">Final interquartile range (IQR)</td><td>30%</td><td><b>1.34e6</b></td><td>1.87e6</td></tr><tr><td>40%</td><td>2.33e6</td><td><b>2.10e6</b></td></tr><tr><td>50%</td><td><b>9.05e5</b></td><td>1.47e6</td></tr><tr><td>60%</td><td>2.0e6</td><td><b>1.94e6</b></td></tr><tr><td>70%</td><td>1.62e6</td><td><b>1.13e6</b></td></tr><tr><td rowspan="5">Generation of first feasible solution (mean)</td><td>30%</td><td>25.6</td><td><b>14.3</b></td></tr><tr><td>40%</td><td>92.6</td><td><b>40.4</b></td></tr><tr><td>50%</td><td>347.0</td><td><b>98.2</b></td></tr><tr><td>60%</td><td>1219.7</td><td><b>174.5</b></td></tr><tr><td>70%</td><td>2050.2</td><td><b>744.0</b></td></tr></tbody></table>

Both algorithms seem to behave similarly in terms of convergence. However, some differences may be pointed out regarding the results. Firstly, the GA-DV method reaches a better objective function median for occupation rates below 60%. At 70%, the results are more mitigated when it comes to convergence speed and final objective median. However, the GA-DV algorithm always provides the best final inertia, regardless of the occupation rate. Moreover, the GA-DV technique allows to find a feasible solution (and so solve the constraints) systematically faster than the GA-tags method. At last, the IQR final values are similar and no trend seems to emerge between the two algorithms and over the generations.

All the results must be contrasted with the fact that they depend on the initializations, even if the algorithms are identically initialized at equal occupation rates. The random initialization allow to keep the general and versatile nature of the methods.

### 6.3.2. Constraints handling

In order to understand more deeply the behavior of the algorithms, the resolution of the constraints is analyzed in this section. For the sake of conciseness, the results related to the constraints are only shown on Figure 18 for the GA-tags and only for the 70% occupation rates. This corresponds to the configuration for which the constraints are solved the slowest.

Figure 18a shows the evolution of the median of the overlap constraint among the 20 runs, corresponding to the sum of the overlap constraint between the components and the overlap constraint between components and the exclusion zone. The figure shows the evolution of the overlap constraint over the 7000 generations and show more
details over the 200 first generations. Figure 18b shows the evolution of the median of the center of mass constraint among the 20 runs and for the 7000 generations as well as the tolerance zone. Figure 18c shows the evolution of the median of the functional constraint among the 20 runs. The figure shows the evolution of the overlap constraint over the 7000 generations and show more details over the 200 first generations.

<figure><img src="image_24.png" /><figcaption>Figure 18: Evolution of the mean of the constraints in the population for the 70% compactness and over the 7000 generations.</figcaption></figure>

Figure 18 demonstrates that the center of mass constraint seems to be the most difficult to solve while the overlap and functional constraints are solved pretty easily even for this high occupation rate. When it comes to the center of gravity constraint, it takes more generations to reach the tolerance zone when the occupation rate increases. For high occupation rates, all the runs corresponding to different initial populations do not find a feasible solution and these runs are non-feasible because of the center of gravity constraint which remains unsolved during the 7000 generations, while the other constraints are respected. This analysis shows that in the general case, the satisfaction of constraints has to be carefully taken into account in order to provide best convergence rates.

### 6.3.3. Exploration and diversity

In order to analyze more in details the exploration behavior of the algorithms, the number of different configurations reached by the methods among the 3888 possible ones will be examined. In more details, for both algorithms and the five occupation rates, the numbers of configurations reached among all individuals and only among the feasible individuals are considered. They are plotted on Figure 19.

Figure 19a shows that among all individuals of their populations, the GA-tags methods explores three times more configurations than the GA-DV method. Moreover, considering only the feasible individuals of their populations, the more the occupation rate increases, the less the GA-tags algorithm seems to explore feasible configurations. For its part, the GA-DV algorithm focuses always on the first feasible configuration found. Those results balance the general conclusions drawn in Section 6.3.1. Indeed, even if a slightly better convergence tendency was highlighted in favor of the GA-DV method, the better exploration capacities of the GA-tags method must be underlined. It can be explained by the presence of evolutionary operators dedicated to the tag vector responsible for the choices of configurations.

### 6.4. Summary of the analyses

Figure 20 shows the best layout found by both algorithms for occupation rates equal to 30%, 50% and 70%.
<figure><img src="image_25.png" /><figcaption>Figure 19: Number of configurations reached by both algorithms and for the five occupation rates.</figcaption></figure>

<figure><img src="image_26.png" /><figcaption>Figure 20: Optimal layout obtained for the 30%, 50% and 70% occupation rates.</figcaption></figure>

It is worth noting that for the three different occupation rates different subdivisions of the components have been chosen. In addition, the more the occupation rates increase, the more the algorithms seem to privilege bigger components for the layout. Globally, both hidden-variable mechanism implementations coupled to a GA manage to find systematically a feasible solution for occupation rates lower than 70%. However, for both of them, the exploration of feasible configurations is limited and focuses quickly on very few configurations from the time a feasible solution is reached, despite the efforts made to induce diversity trough the operators study. Moreover, the more the occupation rate increases, the more the constraints are difficult to solve and consequently less and less runs succeed either in finding a feasible solution during the 7000 generations or in converging enough. This is relatively a classical results for GA [44]. Constraint handling has to be finely tuned to provide best results.

In general, the hidden-variables mechanism allows to extend the range of layout problems to be solved. It enables to tackle a variable-size design space aspect and so to increase the number of architecture choices to be made during the design of the layout phase where a classical GA could only tackle a problem with a fixed number of elements to be placed.
# 7. Conclusion

In this paper, a new formulation of the optimal layout problem is proposed taking into account a variable-size design space aspect as well as new design variables, new functional constraints, and a new exclusion zone in the design space. This extension enables to describe more realistically engineering problems with the aim to tackle cases of industrial complexity in the future and to extend the range of layout problems to be solved beyond the aerospace vehicles application cases. An adapted hidden-variables mechanism has been proposed in order to tackle this new optimal layout problem. It has been applied thanks to two different implementations with a GA (tags and dimensional variables). Both hidden genes mechanisms were compared on an extended realistic satellite optimal layout design problem and a sensitivity analysis has been conducted to the occupation rate of the satellite container to illustrate the performance of the proposed approaches in case of highly constrained problem. The results enable to conclude that both methods revealed convergence capabilities and can be used to solve VSDS problems. Further observations lead to focus more in details on the constraints and their resolution, as well as the diversity purpose. In the future, more experimentation should be performed on the present algorithms (increase in the occupation rate, variation of the number of configurations of the problem ...). Moreover, the proposed mechanism should be adapted for other evolutionary methods (particle swarm, ant colony), but it is necessary to focus on the adaptations of each evolutionary processes in order to deal properly with the dimensional variables and this was out of the scope of the present paper. Finally, a research for hybridation may be conducted in order to handle easily constraints and diversity.

# Acknowledgments

This work is part of a PhD thesis cofunded by INRIA and ONERA.
## Appendix A. Components and decompositions

<table><caption>Table A.5: Components and their characteristics for a 30% compactness</caption><thead><tr><th>Components type</th><th>Geometry</th><th>d1</th><th>d2</th><th>Mass</th><th>Subdivisions</th></tr></thead><tbody><tr><td>Fuel</td><td>Cylinder</td><td>100</td><td></td><td>15</td><td>[1,2,3]</td></tr><tr><td>Fuel</td><td>Cylinder</td><td>100</td><td></td><td>8</td><td>[1,2]</td></tr><tr><td>Fuel</td><td>Cylinder</td><td>50</td><td></td><td>4</td><td>[1,2]</td></tr><tr><td>Energy</td><td>Cuboid</td><td>200</td><td>200</td><td>10</td><td>[1,2,3]</td></tr><tr><td>Energy</td><td>Cuboid</td><td>150</td><td>100</td><td>10</td><td>[1,2]</td></tr><tr><td>Diverse</td><td>Cuboid</td><td>100</td><td>100</td><td>8</td><td>[1,2,4]</td></tr><tr><td>Diverse</td><td>Cuboid</td><td>150</td><td>100</td><td>10</td><td>[1,2]</td></tr><tr><td>Diverse</td><td>Cuboid</td><td>150</td><td>150</td><td>12</td><td>[1,2,4]</td></tr><tr><td>Diverse</td><td>Cuboid</td><td>200</td><td>100</td><td>15</td><td>[1,2,3]</td></tr><tr><td>Diverse</td><td>Cuboid</td><td>100</td><td>75</td><td>6</td><td>[1]</td></tr><tr><td>Diverse</td><td>Cuboid</td><td>75</td><td>50</td><td>2</td><td>[1]</td></tr><tr><td>Diverse</td><td>Cuboid</td><td>200</td><td>100</td><td>15</td><td>[1]</td></tr></tbody></table>

d1 and d2 are the dimensions of the components (in mm). The subdivisions are written as [i,j,k] meaning that the corresponding component can be subdivided in three different ways: in i components or j components or k components. The dimensions of those sub-components are obtained such that the area and mass of the initial component are conserved.

The other compactnesses are obtained by multiplying all the dimensions by the same coefficient to obtain the 50% and 70% occupation rates.

## Appendix B. Algorithms configurations for the toy case

<table><caption>Table B.6: GA-tags configuration for the test case.</caption><thead><tr><th>Operators</th><th>Choice</th><th>Hyper-parameters</th></tr></thead><tbody><tr><td>Constraints Handling</td><td colspan="2">Constraint-Dominance</td></tr><tr><td>Selection</td><td>Tournament</td><td>2 individuals</td></tr><tr><td>Crossover genes</td><td>Simulated Binary Crossover</td><td>P<sub>c</sub><sup>genes</sup> = 0.85</td></tr><tr><td>Crossover tags</td><td>1-point</td><td>P<sub>c</sub><sup>tags</sup> = 0.85</td></tr><tr><td>Mutation genes</td><td>Polynomial Mutation</td><td>P<sub>m</sub><sup>genes</sup> = 0.25</td></tr><tr><td>Mutation tags</td><td>Polynomial Mutation</td><td>P<sub>m</sub><sup>tags</sup> = 0.4</td></tr><tr><td>Replacement</td><td colspan="2">Non-dominated Truncating</td></tr></tbody></table>
<table><caption>Table B.7: GA-DV configurations for the test case and the two possible chromosome implementations.</caption><thead><tr><th>Operators</th><th>Choice</th><th>GA-DV-num</th><th>GA-DV-bin</th></tr></thead><tbody><tr><td>Constraints Handling</td><td colspan="3">Constraint-Dominance</td></tr><tr><td>Selection</td><td>Tournament</td><td>2 individuals</td><td>2 individuals</td></tr><tr><td>Crossover</td><td>Simulated Binary<br>Crossover</td><td>P<sub>c</sub><sup>genes</sup> = 0.85</td><td>P<sub>c</sub><sup>genes</sup> = 0.9</td></tr><tr><td>Mutation</td><td>Polynomial Mutation</td><td>P<sub>m</sub><sup>genes</sup> = 0.35</td><td>P<sub>m</sub><sup>genes</sup> = 0.4</td></tr><tr><td>Replacement</td><td colspan="3">Non-dominated Truncating</td></tr></tbody></table>

<table><caption>Table B.8: Numerical configuration for the toy case</caption><thead><tr><th>Parameters</th><th>value</th></tr></thead><tbody><tr><td>Population size</td><td>50</td></tr><tr><td>Number of generations</td><td>60</td></tr></tbody></table>

## References

[1] Y. Deremaux, N. Pietremont, J. Negrier, E. Herbin, M. Ravachol, Environmental mdo and uncertainty hybrid approach applied to a supersonic business jet, In 12th AIAA/ISSMO multidisciplinary analysis and optimization conference, Victoria, British Columbia Canada (2008) 5832.

[2] J.-F. Liu, L. Hao, G. Li, Y. Xue, Z.-X. Liu, J. Huang, Multi-objective layout optimization of a satellite module using the wang-landau sampling method with local search, Frontiers of Information Technology Electronic Engineering 17 (6) (2016) 527-542.

[3] F.-Z. Cui, C.-Q. Zhong, X.-K. W. et al., A collaborative design method for satellite module component assignment and layout optimization, Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering 233(15) (2019) 5471-5491.

[4] Y.-S. Wang, H.-F. Teng, Y.-J. Shi, Cooperative co-evolutionary scatter search for satellite module layout design, Engineering Computations 26 (7) (2009) 761-785.

[5] J. Pelamatti, Mixed-variable bayesian optimization, application to aerospace system design, PhD thesis Université de Lille (2020).

[6] A. Gad, O. Abdelkhalik, Hidden genes genetic algorithm for multi-gravity-assist trajectories optimization, AIAA Journal of Spacecraft and Rockets 48(4) (2011) 629-641.

[7] J. Cagan., S. Szykman, Constrained three-dimensional component layout using simulated annealing., ASME. Journal of Mechanical Design 119 (1) (1997) 28-35.

[8] S. P. Singh, R. R. K. Sharma, A review of different approaches to the facility layout problems, The International Journal of Advanced Manufacturing Technology 30(5) (2006) 425-433.
[9] R. D. Meller, Y. A. Bozer, A new simulated annealing algorithm for the facility layout problem, International Journal of Production Research 34:6 (1996) 1675–1692.

[10] T. G. Jacquenot, Méthode générique pour l'optimisation d'agencement géométrique et fonctionnel., PhD thesis (in French), Ecole Centrale de Nantes (ECN) (2010).

[11] J. Liu, H. Zhang, K. He, S. Jiang, Multi-objective particle swarm optimization algorithm based on objective space division for the unequal-area facility layout problem, Expert Systems With Applications 102 (2018) 179–192.

[12] A. D. Asl, K. Y. Wong, M. K. Tiwari, Unequal-area stochastic facility layout problems: solutions using improved covariance matrix adaptation evolution strategy, particle swarm optimisation, and genetic algorithm, International Journal of Production Research 54(3) (2016) 799–823.

[13] R. A. Hasan, M. A. Mohammed, N. Tăpuş, O. A. Hammood, A comprehensive study: Ant colony optimization (aco) for facility layout problem, 16th RoEduNet conference: networking in education and research (RoEduNet) IEEE (2017) 1–8.

[14] Potter, A. Mitchell, D. Jong, A. Kenneth, A cooperative coevolutionary approach to function optimization, International Conference on Parallel Problem Solving from Nature Springer, Berlin, Heidelberg (1994) 249–257.

[15] X. Ma, X. LI, Q. Z. et al., A survey on cooperative co-evolutionary algorithms, IEEE Transactions on Evolutionary Computation 23 (2018) 421–441.

[16] H. fei Teng, Y. Chen, W. Z. et al., A dual-system variable-grain cooperative co-evolutionary algorithm: satellite-module layout design, IEEE transactions on evolutionary computation 14 (3) (2009) 438–455.

[17] Z. Y. Lim, S. Ponnambalam, et Kazuhiro Izui, Multi-objective hybrid algorithms for layout optimization in multi-robot cellular manufacturing systems, Knowledge-Based Systems 120 (2017) 87–98.

[18] Z. Li, Y. Zeng, Y. Wang, L. Wang, B. Song, A hybrid multi-mechanism optimization approach for the payload packing design of a satellite module, Applied Soft Computing 45 (2016) 11–26.

[19] J. Liu, Constrained layout optimization in satellite cabin using a multiagent genetic algorithm, Asia-Pacific Conference on simulated evolution and learning, Springer, Berlin, Heidelberg, Deutschland (2012) 440–449.

[20] Y. C. Xu, R. B. Xiao, M. Amos, A novel genetic algorithm for the layout optimization problem, 2007 IEEE Congress on Evolutionary Computation, Tokyo, Japan (2007) 3938–3943.

[21] Y. C. Xu, F. M. Dong, Y. Liu, R. B. Xiao, M. Amos, Ant colony algorithm for the weighted item layout optimization problem, arXiv preprint:1001.4099 (2010).
[22] G. F. O. Alves, J. C. Becceneri, S. Sandri, A balancing heuristic for spacecraft equipment layout optimization, 2015 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), Istanbul, Turkey (2015) 1-8.

[23] H. Tarkesh, A. Atighehchian, A. S. Nookabadi, Facility layout design using virtual multi-agent system, Journal of Intelligent Manufacturing 20 (4) (2009) 347.

[24] P. Burggraäf, J. Wagner, B. Heinbach, Bibliometric study on the use of machine learning as resolution technique for facility layout problems, IEEE Access 9 (2021) 22569-22586.

[25] K. Tsuchiya, S. Bharitkar, Y. Takefuji, A neural network approach to facility layout problems, European Journal of Operational Research 89 (3) (1996) 556-563.

[26] D. Vashisht, H. Rampal, H. Liao, Y. Lu, D. Shandbhag, E. Fallon, L. B. Kara, Placement integrated circuits using cyclic reinforcement learning and simulated annealing, arXiv preprint arXiv:2011.07577 (2020).

[27] A. Mirhoseini, A. Goldie, M. Yazgan, J. W. Jiang, E. Songhori, S. Wang, J. Dean, A graph placement methodology for fast chip design, Nature 594(7862) (2021) 207-212.

[28] R. Cheng, J. Yan, On joint learning for solving placement and routing in chip design, arXiv preprint arXiv:2111.00234 (2021).

[29] D. Dasgupta, D. R. McGregor, Non-stationary function optimization using the structured genetic algorithm, Parallel Problem Solving from Nature (PPSN-2) Conference, Brussels, Belgium 2 (1992) 145-154.

[30] L. Gentile, C. Greco, E. Minisci, T. Bartz-Beielstein, Structured-chromosome ga optimisation for satellite tracking, Proceedings of the Genetic and Evolutionary Computation Conference Companion, Prague, Czech Republic (2019) 1955-1963.

[31] B. Hutt, K. Warwick, Synapsing variable-length crossover: Meaningful crossover for variable-length genomes, IEEE transactions on evolutionary computation 11 (1) (2007) 118-131.

[32] O. Abdelkhalik, A. Gad, Dynamic-size multiple populations genetic algorithm for multigravity-assist trajectory optimization, Journal of Guidance, Control, and Dynamics 35(2) (2012) 520-529.

[33] Y. Xue, B. Xue, M. Zhang, Self-adaptive particle swarm optimization for large-scale feature selection in classification, ACM Transactions on Knowledge Discovery from Data (TKDD) 13(5) (2019) 1-27.

[34] Y. Xue, T. Tang, W. Pang, A. X. Liu, Self-adaptive parameter and strategy based particle swarm optimization for large-scale feature selection problems with multiple classifiers, Applied Soft Computing 88 (2020) 106031.

[35] A. Ellithy, O. Abdelkhalik, J. Englander, Multi-objective hidden genes genetic algorithm for multigravity-assist trajectory optimization, Journal of Guidance, Control, and Dynamics (2022) 1-17.
[36] Z. W. Liu, H. F. Teng, Human-computer cooperative layout design method and its application, Computers Industrial Engineering 55(4) (2008) 735-757.

[37] Z. G. Sun, H. F. Teng, Optimal layout design of a satellite module, Engineering Optimization 35(5) (2003) 513-529.

[38] K. Deb, An efficient constraint handling method for genetic algorithms, Computer methods in applied mechanics and engineering 186(2-4) (2000) 311-338.

[39] K. Deb, R. B. Agrawal, Simulated binary crossover for continuous search space, Complex systems 9 (2) (1995) 115-148.

[40] E.-G. Talbi, Metaheuristics: from design to implementation, John Wiley & Sons (2009).

[41] R. K. Roy, A primer on the taguchi method, Society of Manufacturing Engineers (2010).

[42] T. P. Runarsson, X. Yao, Stochastic ranking for constrained evolutionary optimization, IEEE Transactions on Evolutionary Computation 4 (3) (2000) 284-294.

[43] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: Nsga-ii, IEEE transactions on evolutionary computation 6(2) (2002) 182-197.

[44] K. Deb, An efficient constraint handling method for genetic algorithms, Computer methods in applied mechanics and engineering 186 (2-4) (2000) 311-338.