An Efficient Optimization Algorithm for Modular Product Design

Modular design has a significant impact on product development processes that respond to market trends requiring large varieties within small production processes [1]. Modularity is an important method to break down large systems into smaller modules for easier management of such large systems. The modules are interdependent in the same module and independent between different modules. Modular design involves clustering different components forming a product to create modules which are effective and useful for production. Effective product modularity acquires more importance when similar modules are used in different products [2]. A desirable product architecture is an architecture that partitions a product into modules such that, some modules can be updated on regular cycles of time, others can be changed to generate various type of products, others can be deleted without affecting the product function, and some other modules might be swapped to offer additional functionality [3].

Modularity has an impact on profit and sustainability. Concerning manufacturers, a modular product has modules that can be replaced with newly developed modules, without the need to develop or manufacture entirely new products. Concerning customers, they can upgrade their products by replacing existing modules with new upgraded ones without the need to dispose of the product. This leads to reducing total waste since the entire product will not be disposed [4].

Design Structure Matrix (DSM) is a well-recognized tool that assists in the analysis, as well as, management of large and complex systems [5]. Also, it is a product representation tool used to model, visualize, and analyze dependencies between the elements of a system, and recommends actions for the improvement or formation of a DSM to represent a system. A product can be represented by a DSM containing a list of the product’s components. Product’s DSM also provides information exchange and dependency relationships among these components [6]. Transformation an initial DSM to functional blocks of components is a process known as DSM clustering; the clustering process creates modules which are effective and useful for the company [7].

Within such context, this paper aims to propose an efficient algorithm that divides a DSM into clusters based on minimizing the total coordination cost as the objective function. The total coordination cost is a term introduced by Gutierrez (1998) to quantify the summation of interactions inside clusters (IntraClusterCost) and interactions between clusters (ExtraClustercost) [8]. To propose such efficient algorithm, a number of metaheuristic algorithms, available in the literature, are considered. The algorithms are tailored to solve the problem of dividing a DSM into clusters with the objective of minimizing the total coordination cost. In this paper, five metaheuristic algorisms are used to determine: (1) the optimal number of clusters of DSM, and (2) the optimal components assignment to clusters such that the total coordination cost is minimized. The five metaheuristic algorithms utilized in this work are:

1-Cuckoo Search (CS)

2- Modified Cuckoo Search (MCS)

3- Particle Swarm Optimization (PSO)

4- Simulated Annealing (SA)

5- Gravitational Search Algorithm (GSA)

Comprehensive comparisons are conducted between the results obtained using the five metaheuristic algorithms. The output of the comparisons is a recommendation on the efficient algorithm to solve the problem presented in this research.

To the best of our knowledge, this is the first time to use these metaheuristic algorithms with cost minimization as the objective function in solving product design problem under modularity while having dynamic number of clusters.

Following the introduction, the rest of the paper is structured as follows: Section 2 provides a brief introduction about DSM, followed by a review of related literature in Section 3. Problem definition and proposed solution algorithms are provided in Sections 4 and 5, respectively. Section 6 includes numerical experimentation and analysis of the algorithms and, finally, the paper conclusion and points for future research are provided in Section 7.

Cuckoo Search clustering algorithm is used to find the optimal number of clusters and the optimal assignment of components to clusters with total coordination cost as an objective [6, 9]. Genetic clustering is proposed with Minimum Description Length measure. a new assumption is added to minimize the total execution time. The proposed algorithm is tested on four case studies [7]. mathematical model was developed by Gutierrez [8], this model minimizes the coordination cost [8] with fixed number of clusters. A Genetic Algorithm is used to find optimal arrangement of elements within DSM which optimize the minimum description length (MDL) [11].

Eppingeret et al. introduced the idea of minimizing interactions between modules, while maximizing interactions within modules in a DSM [12]. Idicula proposed a stochastic clustering algorithm for DSM clustering [13]. Thebeau developed a stochastic hill climbing algorithm to cluster DSM with the objective function of cost minimization [14].

A new method is developed to define the difference between designing modular systems and integrative systems [15]. The study is focused on the specification of modules, modules architecture, and their interfaces.

To obtain better output from a clustering algorithm, a method known as conceptual module generation phase can be employed [16]. Liang [17] developed a model known as group decomposition model. The proposed model decomposes a complex set of activities into simpler ones. The DSM is used as a system simplification tool. The clustering algorithm employed is K-means algorithm [17]. Li [18] proposed an integrated tool that addresses problems in matrix-based decomposition [18]. Four DSM types are provided with their corresponding application in engineering design, as well as, in concurrent engineering. Various techniques dealing with DSM partitioning, taring, banding, and clustering are proposed [19]. A modularization scheme based on functional modeling is proposed and K-means is used for clustering [20]. Neural networks algorithms and DSMs have been utilized to cluster DSM components with the objective function of clustering efficiency; however, the algorithm requires a predetermined number of clusters [21]. Borjesson and Hölttä [22] develop an algorithm named Idicula-Gutierrez-Thebeau Algorithm (IGTA) for clustering DSM. An improved algorithm, named IGTA-plus, is proposed. IGTA-plus provide significant improvement when compared with IGTA. Recorded improvements are in terms of computational time and solution quality [22].

Yang et al. [23] developed a systematic clustering algorithm for organizational DSM. The algorithm evaluates clustering structures based on the strength of interaction.

Another novel approach for product design is introduced by integrating the sequence structure planning of assembly and disassembly of a product [24].

A hybrid approach is developed, based on multidimensional scaling (MDS) and clustering methods. This approach is applied on DSM to provide product architecting [25]. A new practical method is proposed by Sakao et al. to support designers in creating service modules by extending the DSM [26]. research focused on the answering the questions, how modularity used in product design, how it is helped in product Varity and how modularity increased the organization performance [27], Finally Non-dominated Cuckoo Search is proposed to maximize Sustainability through DSM, This multi objective optimization technique wants to find s set of Pareto optimal solutions; each solution represents the structure of modules and the number of modules in the product which optimize functionality and sustainability objectives. The problem has set of conflicting objectives, product functionality objective, labor time, environmental impact and labor cost. [28].

The reviewed literature on product design using DSM as a system analysis tool revealed the existence of several points of view to cluster the DSM for modularity. One major difference between those points of view is the objective of clustering. Another difference is in the solution technique. Considering the objective of clustering, Minimal Description Length (MDL) is one of the objectives [11]. Another objective is Minimizing the total coordination cost, which is recognized as one of the most widely targeted objectives [14]. Clustering Efficiency (CE) index with static number of clusters is also among the considered objectives in the literature [21]. As for the solution technique for solving the problem, several techniques exist in the literature, for example: Genetic Algorithm [11], stochastic hill-climbing algorithm [14], and neural networks [21].

To the best of our knowledge, this research is the first one to use the five previously mentioned metaheuristic algorithms with cost minimization as the objective function in solving product design problem under modularity with dynamic number of clusters.

Metaheuristic optimization algorithms are general iterative algorithms capable of solving combinatorial optimization problems. These algorithms are stochastic in manner. They simulate the behavior of particles. Metaheuristic algorithms try to find optimal or near optimal solutions for complex problems [30] To solve the problem in this research, five metaheuristic algorithms are utilized. Four of the selected algorithms represent a population-based optimization method, and one algorithm represents a trajectory optimization method. The selected algorithms are Cuckoo Search (CS), Modified Cuckoo Search (MCS), Particle Swarm Optimization (PSO), Gravitational Search Algorithm (GSA), and Simulated Annealing (SA). In the following subsections, a brief description of the algorithms is given, along with a pseudo code to provide easy implementation to the problem under consideration.

5.1 Cuckoo Search (CS)

The Cuckoo Search (CS) algorithm was proposed by Yang and Deb [31]. The algorithm simulates the behavior of cuckoo birds to explore the solution space for an optimum or near optimum solution. CS is inspired from the behavior of some brood parasite cuckoo species that lay their eggs in the nests of host birds of other species. Brood parasite cuckoos distribute their eggs among several different nests. Their aim is to escape the parental investment in raising their offspring, and to minimize the risk of their egg loss [31].

One of the significant advantages of CS is its efficiency that has been proven using a considerable number of benchmark studies. When comparing results with other metaheuristic algorithms, CS performed better. Another advantage of CS compared to other metaheuristic algorithms is its simplicity, since it requires setting only two parameters. This feature simplifies the time and effort needed to adjust and fine tune the algorithm’s parameter settings [32].

In CS algorithm, an egg represents a solution. Initial solutions are randomly generated. X_i^t is solution i in generation t. X_i^t+1 is obtained using a levy flight using equation 4. A levy flight is a random walk with step lengths that follow a heavy tailed probability distribution given in Eq. (5). Random walks through Lévy flights experience longer step lengths on the long run, and hence are efficient in exploring search spaces.

$\mathrm{X}_{\mathrm{i}}^{\mathrm{t}+1}=\mathrm{X}_{\mathrm{i}}^{\mathrm{t}}+\alpha \oplus \operatorname{Levy}(\lambda)$      (4)

where, α is a number greater than zero that denotes the step size, $\oplus$ product denotes entry-wise multiplications.

Levy ∼ u = t −λ, (1 < λ ≤ 3)       (5)

The main steps of the CS algorithm are given in the pseudo code in Figure 2.

2.png

Figure 2. Pseudo code of CS [33]

5.2 Modified Cuckoo Search (MCS)

A Modified Cuckoo Search algorithm was provided by Walton et al. [33] with the same structure of original Cuckoo Search maintained but with two modifications. The first modification is changing the size of the Levy flight step size α. In CS, α is set to the value of 1, and hence has a constant value at all generations. In MCS, the value of α decrease as the number of generations increases. This modification leads to a more localized search as the individuals, or the eggs, get closer to the solution. The second modification is the information exchange among the eggs, aiming to speed convergence of the solution. In CS, there is no information exchange among individuals, and hence, searches are performed independently.

In MCS, a fraction of the eggs with the best fitness are categorized as a group of top eggs. Two eggs are randomly chosen from the group of top eggs. A new egg is then generated on the line connecting the two chosen top eggs. The new egg is located closer to the egg with the best fitness. The distance of the new egg along the line is calculated using the inverse of the golden ratio ᶲ =(1+√5)/2. If the two chosen top eggs have the same fitness value, then the new egg is placed at the midpoint. If the same egg is chosen twice, a local Levy flight search is performed from the randomly picked nest with step size α = A/G² [34].

5.3 Particle Swarm Optimization (PSO)

3.png

Figure 3. Pseudo code of PSO [35]

The PSO algorithm was first introduced by Kennedy and Eberhart [36]. The algorithm was inspired by mimicking the social behavior of flocks of birds or schools of fishes. A flock of birds or a school of fishes has a leader. The leader guides the movement of all individuals of the swarm. The movement of every individual depends of the leader’s knowledge [36]. The main steps of the PSO algorithm are summarized in the pseudo code in Figure 3.

5.4 Gravitational Search Algorithm (GSA)

The GSA was first proposed by Rashedi et al. [37] as a nature-inspired algorithm. The algorithm is population-based, where Newton’s laws of gravity and motion are considered to solve complex optimization problems. GSA is based on the law of gravity and mass interactions. The algorithm requires a set of search agents that interact with each other through gravity force [37].

Steps of the GSA algorithm are summarized in the pseudo code in Figure 4.

4.png

Figure 4. Pseudo code of GSA [38]

5.5 Simulated Annealing (SA)

The SA algorithm was proposed in 1982 by Kirkpatric et al. [39]. SA is a probabilistic local search technique used to find an optimum or near optimum solutions for large combinatorial optimization problems. SA is best used when the search space is discrete. Simulated Annealing imitates the annealing process of metals. The algorithm explores the solution space using neighborhood search methods. Worse solutions are accepted with low probabilities to avoid being trapped in local optima [39]. Basic steps of the SA algorithm are summarized in the pseudo code in Figure 5

5.png

Figure 5. Pseudo code of SA [40]

5.6 Implementation

5.6.1 Solution representation

Solution representation of the problem is a vector of length that is equal to the number of elements of the DSM. Each value in the vector is an integer between 1 and the number of clusters, as shown in Figure 6. Figure 6 illustrates a vector of size 7. The vector represents a solution for an original DSM consisting of 7 elements. The solution presented in Figure 6 means that cluster 1 contains elements 1 and 7, cluster 2 contains elements 2, 3, and 4, and cluster 3 contains elements 5 and 6. The presented solution representation ensures avoiding multi-clustering; in other words, each element will be assigned to exactly one cluster. The solution procedure starts with a number of clusters that is equal to the number of elements available within the DSM. Hence, the solution procedure starts with the maximum possible number of clusters. The next step is to reform sets of clusters to obtain the optimum number of clusters with the corresponding elements in each cluster.

6.png

Figure 6. Solution representation vector

In this work, five algorithms are proposed to solve the problem in hand. Four of the proposed algorithms (CS, MCS, PSO and GSA) are present in the literature to solve continuous optimization problems. The problem presented in this work is discrete in nature, and hence, the proposed algorithm requires a process of discretization. Several methods are available in the literature to perform discretization. Among the known discretization methods is the random key technique, where continuous values are transformed into discrete integer values [41]. Another method is the smallest position value (SPV) [42]. A different technique available in the literature is the nearest integer (NI) method. In this method, a continuous valueis trasnformed to thenearestinteger value by simply rounding, trancatingup, or trancatingdown [43].

SPV and random key methods do not permit the repetition of integer values in the solution. Solving the problem presented in this research necessarily requires repeating some integer values. Hence, SPV and random key methods cannot be used to solve the problem in hand. The nearest integer method, on the other hand, allows the repetition of integer values in a solution, and therefore, the nearest integer discretization technique is chosen to solve the problem in this research.

When using CS and MCS to cluster a DSM, the algorithm begins with generating several nests. A nest consists of a vector having a length that is equal to the number of elements of the DSM to be clustered. Entries of vectors are randomly generated uniformly between the upper limit and lower limit. Then, these entries are transformed into integer values using the nearest integer method. Vectors represent solutions that require evaluation. Therefore, each vector is sent to the evaluation function. The evaluation function calculates the corresponding total coordination cost, conducts comparisons and performs updates using Levy flight and the probability of discovery (pa), details are available in Section 5.1 and Section 5.2.

In PSO, the algorithm begins with generating several particles. A particle consists of a vector having a length that is equal to the number of elements of the DSM to be clustered. Entries of vectors are randomly generated uniformly between the upper limit and lower limit. Then, these entries are transformed into integer values using the nearest integer method. Vectors represent solutions that require evaluation. Therefore, each vector is sent to the evaluation function. The evaluation function calculates the corresponding total coordination cost, and generates a new solution using a new position and a new velocity. Details are given in Section 5.3.

Finally, in GSA, the process starts with a set of objects. The fitness function is evaluated, mass and acceleration are calculated, and the velocity and position are updated to generate a new solution Details are given in Section 5.4.

Regarding SA, the solution is a vector of length that equals to the number of elements in the DSM. This vector contains integer numbers whose values are between lower and upper limits. The vector represents the current solution. A new solution is updated by generating a neighbor solution, then old and new solutions are compared. Details are given in Section 5.5.

5.6.2 Solution evaluation

Clustering a DSM requires minimizing the total coordination cost which is based on IntraClusterCost and ExtraClusterCost. IntraClusterCost is calculated if interaction DSMik belongs to cluster j, otherwise, ExtraClusterCost is calculated. At the beginning of the solution procedure, feasible solutions are randomly generated, and the total coordination cost is calculated. Details of calculating the total coordination cost, IntraClusterCost, and ExtraClusterCost, are given in Section 4. Evaluation of the solution(s) is performed, then the algorithm selects the best obtained solution and a new iteration begins. In this research, five algorithms are used, hence, each algorithm moves to the next solution according to its specific procedure as follows: (1) CS and MCS utilize Levy flight to move the best nests with high quality eggs (solutions) to the following generation, (2) PSO moves to a new position with a different velocity, (3) SA obtain a neighbor solution (4) GSA utilizes a set of agents, each agent has a corresponding position, inertial mass, active gravitational mass, and passive gravitational mass. Gravitational masses and inertia masses are adjusted in each iteration to obtain the new solution, where the heaviest mass represents the best obtained solution. Each of the five algorithms moves from generation to the next till the stopping criteria is reached.

5.6.3 Handling constraints

The five proposed algorithms rely on unconstraint objective function evaluation. The problem considered in this research is a constrained problem. Hence, a constraint handling method is required to solve the problem considered in this research. There are several methods that can be used to handle constraints, one of the simplest and most common methods is using a penalty function. The main idea is to transform a constrained optimization problem to an unconstrained optimization problem by adding a certain value (penalty) to the objective function. This value depends on the amount of violation presented in a certain solution [44].

In the proposed algorithms, a penalty is added to the fitness function according to Eqns. (6) and (7) which guarantee reaching a feasible solution as iterations proceed.

penalty $(\mathrm{x})=\left\{\begin{array}{c}0, \text { if no violation occurs } \\ (\mathrm{C} * \text { iter })^{\alpha} \sum_{\mathrm{j}=1}^{\mathrm{m}} \mathrm{f}_{\mathrm{j}}^{\beta}(\mathrm{x}), \text { otherwise }\end{array}\right.$        (6)

$\operatorname{eval}(x) \\ \quad=\left\{\begin{array}{l}f(x), \quad \text { if } x \in \text { feasible solutions } \\ f(x)+\text { penalty }(x), & \text { otherwise }\end{array}\right.$          (7)

where, f(x) is the fitness function (total coordination Cost), $(C * \text { iter })^{\alpha}$ is to make the constraint violation of the same order of magnitude as the objective function based on iter (iteration number) violation which expands when iterations grow; β is defined as the multiplication of violation which highly leads to feasibility by maximizing violation value which, in turn, encourages the solution to be feasible through differentiating between feasible and non-feasible solutions with a high impact.

This paper aimed to provide an efficient clustering algorithm capable of obtaining a high-quality solution in reasonable computation time for the product design problem under modularity. Five Meta-heuristics techniques are examined, namely, CS, MCS, PSO, SA, and GSA. The algorithms aim to find: (1) the optimal number of clusters within a DSM; and (2) the optimal components’ assignment forming clusters. The objective function was to minimize the total coordination cost.

In this context, DSM was employed as a system analysis tool. It provided a compact and clear representation of complex systems. Also, it helped in visualizing the interactions between system elements. The utilized algorithms were tested and compared on eighty test instances. These instances were generated randomly with different dimensions and complexity to provide different product complexity. Results showed that Cuckoo Search provided better solutions compared to the other algorithms in most cases regarding mean objective function value. Modified Cuckoo Search provided better solutions compared to other algorithms in most cases regarding mean computational time.

A Penalty method was used as constraint handling to prevent forming large clusters. Another comparison was conducted between solutions with limiting clusters’ sizes and without limiting clusters’ sizes, limiting cluster size is needed and important in product design problem, since product design main objective is to create small modules to be useful and important for the company, that can be replaced and updated at any time to provide new product or new functions. Future work includes providing multi-objective Cuckoo Search algorithm to find the optimal assignment of each element in the cluster and the optimal number of clusters which minimize total coordination cost of the product and maximize product sustainability with a fuzzy logic approach in designing sustainability matrix.