Novelty-Driven Binary Particle Swarm Optimisation for Truss Optimisation Problems

Truss optimisation problems are subject to structural constraints such as stability, failure criteria and design codes by practice and manufacturing specifications. The constraints can conflict with objectives which makes the problem more challenging.

For decades, several numerical methods have been applied to different truss optimisation problems. Conventional methods such as gradient-based showed limited efficiency in dealing with structural constraints and handling the discreteness and discontinuities in truss optimisation problems which led to trapping in local optima [5]. The inadequacy of classical optimisation methods led to the development of population-based algorithms and metaheuristics in truss optimisation [22].

Two-stage approaches for topology, size and shape optimisation in the literature considers these design variables are linearly separable and initially find optimal topology considering fixed equal size for all active bars. Next, it determines the optimal sizing for the obtained topology. The assumption of linear separability can lead to missing out good solutions and may result in infeasible solutions with respect to real practice [5].

Other approaches, namely single-stage approaches consider topology, size and shape design variables simultaneously and consequently expand the search space considering both design variables. The search is guided towards finding one ultimate single solution and still may ignore interactions among different variables.

Bilevel optimisation is a more effective approach than previous two approaches to deal with truss optimisation problems because it can model the interaction among different aspects of the problem more explicitly. In the bilevel formulation, the upper level optimisation problem determines the truss configuration, such as topology, where the lower level optimises bars’ sizing.

Islam et al. [17] adopted a bilevel representation for the truss optimisation problem, where the weight of the truss was the main optimisation objective for both upper and lower levels. In the upper level, a modified binary Particle Swarm Optimisation (PSO) with niching capability was used to enhance its population diversity while still maintaining some level of exploitation. The niching technique was based on a speciation scheme that applies a niching radius to subdivide the swarm, in an effort to locate multiple high-quality solutions. For the lower level, a standard continuous PSO was employed to supply good sizing solutions to the upper level.

However, using standard PSO for such constrained engineering problems can lead to trapping in local optima [15]. It has been showed that truss optimisation should incorporate domain-specific information of the problem instead of only considering pure optimisation [2].

It has been observed that there exist multiple distinct topologies with almost equal overall weight in the truss optimisation search space [5, 17, 27]. Therefore finding multiple equally good truss designs with respect to the topology, size and shape can enable practitioners to choose according to their preferences.

Niching methods [27] and novelty search [24] are capable of finding multiple optima in multi-modal search space. Niching techniques employ rules to keep diversity in the population by primarily focusing on optimising a fitness function. However, novelty search drives the search towards different candidate solutions from the ones previously have been encountered. Novelty search was proposed in [24] enhances the ability of exploration in population-based algorithms, and keeps the diversity by looking for more novel solutions considering their similarity to other previously visited solutions. Novelty search aims to improve diversity with respect to the behavioural space instead of exclusively considering objective function value [28, 25].

In this paper, we consider the bilevel optimisation of trusses with a primary focus on the upper level as a combinatorial optimisation problem. We propose two approaches considering the upper level search space in the truss test problems. We introduce an exact enumeration approach for rigorous analysis of the upper level search space for small test problems. Exact enumeration iterates over all possible upper level topologies, and we apply the lower level optimisation to every feasible upper level design. Using exact enumeration enables us to remove randomness in the upper level and better characterise its search space and report on the quality of potential designs.

For larger problems, we propose a novelty-driven binary particle swarm optimisation for bilevel truss optimisation. We aim to discover new designs at the upper level by maximising novelty, and we apply the lower level optimisation to obtained novel solutions. Using novelty search can guide the search in the upper level towards unseen topologies instead of using only the overall weight to explore the search space. Therefore we set different objective functions for the upper and lower levels. Our proposed novelty search driven binary PSO for bilevel optimisation of trusses consists of a modified binary PSO in the upper level to deal with the exploration of topology search space and maximise novelty. The upper level of truss optimisation is subject to primary essential constraints.

We employ a repair mechanism to fix infeasible produced solutions. As lower level sizing in truss optimisation is challenging due to the nature of the problem, we use a reliable evolutionary optimiser that incorporates domain-based knowledge to determine the size of bars.

We carry out the proposed approaches to truss optimisation test problems. Our experimental investigation shows that our approaches can outperform the current state of art methods and achieve multiple high-quality truss designs. The source code is available at https://github.com/hiraaaad/BinaryNoveltyPSOTruss.

The rest of the paper is organised as follows. In the next section, we state the bilevel truss optimisation problem, explain the lower level optimiser and give background on standard and binary PSO. Afterwards, we introduce the exact enumeration and propose the bilevel novelty search framework including the upper level repair operator. We carry out experimental investigations and report on the quality of obtained solutions for different truss test problems. We finish with some concluding remarks and some suggestions for future work.

Bilevel truss optimisation problem embeds an upper level topology optimisation problem into a lower level size optimisation problem. The bilevel optimisation problem can be stated as,

where $\vec{x}$ refers to the binary topology variable in the upper level where it shows if a truss bar is active (1) or excluded (0). $m$ shows the length of upper level topology design variables. For instance, in 25-bar truss $m$ is 8 due to symmetry. For the same problem, we can show the upper bound of topology as the ground structure where all bars are active as $\vec{x}=[11111111]$.

$\vec{y}$ denotes the design variable in the lower level optimisation problem including size and shape with respect to the test problem. The size variables of $\vec{y}$ should be selected from an available size set ($S$). $F(\vec{x},\vec{y})$ shows the objective function considered in the upper level such as weight minimisation used in [17] or maximising novelty in this study.

Solutions in the upper level should satisfy the topology constraints for feasibility. $G_{1}$ enforces that the design should have active nodes that support the truss and carry the external load, because they are necessary elements in the design space’s predefined boundary conditions. For example for 10-bar truss (depicted in Figure 1 (I)) nodes 1 and 4 are support nodes and nodes 2 and 3 are carrying external loads. Therefore these four nodes are necessary nodes in the design space.

$G_{2}$ states the external stability of a truss. The external stability satisfaction criteria are fully detailed in Section 4.2. Feasible topology solutions should meet $G_{1}$ and $G_{2}$. In this case, the lower level optimiser aims to find the optimum $\vec{y}$ to minimise the overall weight of truss ($W$) which is the summation of the weight of all included bars ($\hat{m}$) in the truss.

where $\rho$ and $l$ show the density of the material used in the truss (such as aluminium or steel) and length of a bar with respect to its end points in the design space, respectively. upper level external stability satisfaction is necessary but not sufficient. Therefore, in the lower level, the internal stability should be checked through lower level function evaluation.

If $(\vec{x},\vec{y})$ meets the internal stable condition, extra constraints should be satisfied. These constraints state that the computed stress in bars ($\sigma_{i}$, $i\in\{1,2,..,\hat{m}\}$) and displacement of truss nodes ($\delta_{k}$, $k=\{1,2,..,n\}$) after applying the external loads should not exceed their problem-dependent allowable values $\sigma_{i}^{max},i\in\{1,2,..,\hat{m}\}$, and $\delta_{k}^{max},k\in\{1,2,..,n\}$, respectively.

The lower level constraints $g_{j}$, $j=1,2,3$, used as part of $G_{3}(\vec{x})$ are therefore defined as follows.

We use a domain knowledge-based evolutionary optimiser for lower level optimisation [2] to determine the optimum layout. The loweroptimiser is a variant of Covariance Matrix Adaptation Evolution Strategy algorithm (CMA-ES) that is customised to be problem-specific. loweroptimiser follows the main principles of evolutionary strategies to evolve the solutions. However, it uses specific operators to adjust solutions with respect to the allowable stress and displacement in the truss. loweroptimiser uses a probabilistic scheme to round the values to the discrete set to avoid biasing the search towards sub-optimal solutions.

loweroptimiser employs a mapping strategy with respect to the response after performing finite element analysis to adjust the sizing of a violating bar by multiplying its current size with a factor that depends on the amount of violation. Another operator is a resizing strategy for producing new individuals near boundary designs of the problem and the problem-dependent constraints. For brevity, we refer the reader to [2, 1] for detailed explanations on different components of the loweroptimiser.

PSO is a population-based algorithm evolving a swarm where it contains particles as candidate solutions to a problem [20]. Each particle has three vectors at the time ($t$) of evolution : position ($\vec{z_{t}}$), velocity ($\vec{v_{t}}$) and personal best where it keeps the best position is has been evolved to as ($\vec{p_{t}}$). PSO updates particle positions based on the velocity for each component ($i$) as follows.

where $\vec{p_{g}}$ is the global best position in the swarm. $\omega$ is the inertia factor to control the impact of current velocity in velocity updating. $r_{1}$ and $r_{2}$ are vectors with size of a particle containing random values from a uniform distribution in the range [0, 1]. $c_{1}$ and $c_{2}$ are cognitive and social factors to attract particles toward their personal best and global best.

PSO is typically used as a continuous optimisation algorithm. Therefore, to use it for binary search spaces, we need to employ a transfer function, such as Sigmoid transfer function, to map a continuous search space into a binary search space. In this study, we use global topology for the PSO and employ a time-varying transfer function [17] to balance between exploration and exploitation. Velocities of all particles are updated according to the velocity update equation. The following equation determines the probabilities for flipping the position vector elements ($i$).

where $rand()$ denotes a random value in a uniform distribution in the range [0, 1] and, $TV$ is given as [17],

$\phi$ is the control parameter to balance exploration and exploitation in the course of evolution where it linearly decreases from 5.0 to 1.0 in this study according to [17].

Novelty-Driven PSO (NdPSO) is a variant of PSO employing novelty search to drive particles toward novel solutions that are different from previously encountered ones [11]. The main idea is to explore the search space by ignoring objective-based fitness functions and reward novel individuals. NdPSO uses the score of novelty to evaluate the performance of particles. For this purpose, it maintains an archive of past visited solutions to avoid repeatedly cycling through the same series of behaviours.

NdPSO evaluates the novelty of particles by computing the average distance of a behaviour to its k-nearest neighbours in the archive as follows:

where $\mu_{i}$ is the $i$^th nearest neighbour of $x$ and dist is the Hamming distance metric. Novelty score ensures that individuals in less dense areas with respect to the archive get higher novelty scores.

NdPSO employs core principles of PSO and mainly replaces the objective function with novelty evaluation. Note that personal best and global best value in NdPSO show a dynamic behaviour. For more details on NdPSO, we refer the reader to [11]. We use NdPSO in the upper level of truss optimisation to discover novel topology designs.

Topology designs in the upper level are feasible if they meet $G_{1}(\vec{x})$ and $G_{2}(\vec{x})$.

The following conditions should be satisfied for $G_{2}(\vec{x})$ [2]:

• •

  The degree of freedom (DoF) in a truss should be non-positive [5].

• •

  The summation of the number of members and restrain forces on a node must be equal or greater than the truss dimension.

• •

  The summation of the number of members and restraint forces on a non-carrying node must be greater than the truss dimension.

As stated in [5], necessary node constraints are more important than the DoF constraint. To deal with infeasible topologies, we use the (1+1)-EA [8] with the following comparator to repair solutions:

where $\alpha$ is the violation degree of active necessary nodes, $\beta$ is the violation degree of truss DoF and $\theta$ is the violation degree of second and third criteria in external stability. (1+1)-EA is a simple evolutionary algorithm where it produces an offspring by mutation and the offspring replaces the parent if the offspring is better with respect to the objective function mentioned above.

Our proposed approach works as follows (see Algorithm 2). Initially, the binary PSO generates a random population of binary strings. Next, the repair mechanism performs on the population to ensure the feasibility of particles. The particles’ velocities are drawn randomly from $[-\upsilon,\upsilon]$. Then, the novelty score is computed for particles with respect to the archive. Because all particles are feasible, loweroptimiser computes the corresponding optimal size (and shape) for the upper level topology. With this, we update the archive with the current population. Next, the position and velocity of particles are updated, and the above process repeats till the termination criterion is met.

Figure 1 (II) shows the ground structure of 25-bar truss which is a spatial truss for size and topology optimisation [7]. This problem splits into two cases with respect to different load cases. The truss undergoes a single and multiple external loads for the first and second cases, respectively. The sizing of bars should be selected from different discrete sets for each case [7].

This is a symmetric truss where 25 truss bars are grouped into eight groups of bars. Therefore, there are 256 possible topologies at the upper level. Figures 2 and 3 show the outcome of exact enumeration on this test problem where we observed that up to first 50 and 55 designs with respect to $d_{H}$ are feasible and the rest of the search space is infeasible. We can see that most of the feasible designs are in the upper bound vicinity where $d_{H}\leq 3$. We can also observe that the high-quality solutions exist in the region where $d_{H}\leq 2$ and $d_{H}\leq 3$ for cases 1 and 2, respectively.

Table 1 shows our findings for both cases.

10-bar truss is a well-known size and topology optimisation problem which its ground structure is depicted in Figure 1 (I). It undergoes single load and the sizing of bars should be selected from a discrete set where There are 10 bars in the topology design, which results in 1024 possible upper level topologies. See [26] for details on the simulation.

Figure 4 shows the outcome of exact enumeration and the designs are ordered according to their $d_{H}$. We only show the first 320 sorted designs because the rest of the designs are infeasible. This figure also shows the top obtained designs for this problem.

We can see feasible designs are where $d_{H}\leq 4$ and the best-found design’s $d_{H}$ is 4. Table 2 shows our findings, and we can see that designs (b) and (c) with $d_{H}=2$, both identify two bars as redundant and incorporate all six nodes in their designs.

However, design (a) which is the best-found design identifies four bars ($A_{2}$, $A_{5}-A_{6}$ and $A_{10}$) as redundant and eliminates node 6. We can also see that other state of art methods, including [9] and [21] also identified the same topology as the optimal topology. However, our approach can obtain a solution with a lower weight due to the efficient lower lover optimiser.

This is a size and topology optimisation problem where 52-bar truss are grouped into 12 bar groups resulting in 4096 possible designs. The truss undergoes three load cases and the sizing of bars should be selected from a discrete set [36]. Figure 5 (I) shows the ground structure of 52-bar truss, which is composed of 12 bars resulting in 4096 possible designs.

Figure 6 shows the outcome of exact enumeration where we only show the first 250 designs sorted according to their $d_{H}$. For clear presentation, Out of all sorted combinations, 1900 designs are feasible, and the rest of the search space is infeasible. We also observed that feasible designs are located where $d_{H}\leq 6$.

Table 3 shows our findings and, we can see that the top three designs for this problem identify one to three group of bars redundant, respectively.

Design (a) depicted in Figure 7 (I) shows the best-found design that eliminates all redundant bars identified in design (b) and (c) and removes $A_{37}-A_{39}$ summing up to nine redundant bars.

This is a size and topology truss optimisation problem which is non-symmetric truss composed of 15 bars and truss undergoes three load cases and the sizing should be selected from a discrete set [37]. Figure 1 (III) shows the ground structure of 15-bar truss which is a non-symmetric truss composed of 15 bars.

Table 4 shows our findings by the proposed bilevel novelty search compared with other methods. We can see that designs (b) and (c) find the same weight, and they are symmetric around the vertical axis with respect to the topology and size of bars. Both designs remove 6 bars from the design space, and symmetrically they eliminate nodes 2 and 4 from the design space, respectively. Design (d) eliminates five bars and node 2 from the design space.

Figure 8 shows these three designs. Design (a) is the best-found design depicted in Figure 7 (II) eliminates five bars in the design space and provides a lighter solution compared with other methods.

72-bar truss represents a four storey structure for size and topology optimisation where which is a symmetric truss composed of 72 bars grouped into 16 groups of bars. The truss undergoes two load cases and the sizing of bars should be selected from a set [36].

Table 5 shows our findings by the proposed bilevel novelty search compared with other methods. We can see that designs (b) and (c) identify five groups of bars as redundant, including four common groups. This will lead to the elimination of 16 bars from the design space. Design (a) depicted in Figure 7 (III) is the best-found design. It combines the identified redundant bars in designs (b) and (c) and removes 20 bars in total from the design space and achieves a lighter solution.

This problem represents a transmission tower with symmetric truss bars grouped into 27 groups, and it considers size and shape optimisation in the lower level. See [13] for structural constraints and technical information to simulate the problem. Table 6 shows our findings in comparison with state of the art. We can see that our method obtained three different designs with respect to the topology. Design (a) incorporates 23 topology bars, and design (b) and (c) both incorporate 21 groups of bars and the main difference is including member groups of 23 and 26, respectively.

This size and topology optimisation problem includes 200-bars grouped into 29 bar groups. The truss undergoes three loading conditions and is subject to no displacement constraint. See [19] for details on simulation. Table 7 shows our findings and compared with reported weights in state of the art. The best-reported weight is 25156.5 lb, but this is an infeasible design because it violates the stress constraint by about 8%. We can see that the best design obtained by our method (design (a)) outperforms other designs. Design (a) and (c) both include 24 group bars but with different topologies; however, Design (b) incorporates all group members as 29.

This problem represents a pyramid truss where the truss bars are grouped into 32 groups and considers size, shape and topology optimisation subject to complex design specifications. See [13] for details on the simulation. Table 8 lists obtained designs by our method compared with state of the art. Design (a) outperforms other designs, and design (b) is as alike as the optimum design obtained in [2].

This size, shape and topology optimisation problem is a multi-load truss optimisation with 68 non-symmetric topology design variables. The optimum design should be feasible considering the structural reactions subject to 8 different loading conditions. See [2] for details on the simulation. Table 9 shows our findings in comparison with state of the art. We can see that our method obtained the best design alike to the one obtained in [2], where this design incorporates 34 group bars. However, designs (b) and (c) include 37 and 39 bars, respectively.