A genetic algorithm with SOM neural network clustering for multimodal function optimization

Abstract

Identifying the number of niches in multimodal optimization is vital to enhancement of efficiency of algorithms. This paper presents a genetic algorithm (GA)-based clustering method for multiple optimal determinations. The approach uses self-organizing map (SOM) neural networks to detect clusters in GA population. After clustering all population and recognizing the number of niches, the phenotypic space is partitioned. Within each partition, a simple GA is independently running to evolve to the actual optima. Before the SOM starts, we allow GA to run several generations until the borders of clusters are identified. Our proposed algorithm is easy to implement, and does not require any prior knowledge about the fitness function. The algorithm was tested for seven multimodal functions and four constrained engineering optimization functions, and the results have been compared with the other related algorithms based on three performance criteria. We found that the present algorithm has acceptable diversification and function evaluation number.

Keywords

Multimodal optimization genetic algorithms SOM neural network clustering

1 Introduction

Many real engineering optimization problems are very complex in nature, and have multimodal behavior in search domain; that is, they have different multiple optima (several global optima and some local optima). Considering operational rules, cost and time limitations, and other physical constraints, it is necessary to obtain all global/local solutions of multimodal functions, for some solutions may be suitable alternatives during the optimization search process. Multimodal optimization (MMO) refers to the art of finding the number and location of all global and local optima of an objective function in its search space. Over the last decades, a large number of mathematical programming methods such as linear, non-linear, integer and dynamic programming have been proposed for solving MMO, which suffer from some serious difficulties including i) they are applicable to continues and differentiable objective functions, as they use the first or second order information of objective functions, ii) they start the search process near the initial point; however, to be convergence with an acceptable computational effort, choosing an appropriate starting point is vital to these algorithms, iii) these methods do not handle discrete and continuous variables simultaneously, and hence, are not applicable to some engineering MMO problems such as tension/compression spring design problem [1], and iv) these methods cannot solve those engineering MMO problems with non-convex search spaces and the problems whose objective functions may be very smooth in some region and very rugged in other regions (such as Rastrigin’s and Shubert’s functions). Though some modifications of mathematical programming methods such as mixed integer nonlinear programming [2, 3], stochastic and adaptive dynamic programming [4, 5], approximate dynamic programming [6], geometric programming [7], quadratic programming [8], fuzzy programming [9], non-convex integer programming [10] and etc. were proposed to overcome the aforementioned problems, they in general need a considerable computational effort.

With increasing the complexity of industrial engineering problems, non-gradient methods and specially evolutionary algorithms (EAs) such as genetic algorithm (GA) [11], particle swarm (PSO) [12], ant colony optimization (ACO) [13], Simulated Annealing (SA) [14], Bee Colony Optimization (BCO) [15], harmony search (HS) [16], and hybrid metaheuristic methods [17] have been broadly used to obtain global (or near global) and local optimum solutions. These techniques are robust and efficient, capture multiple solutions in a single run without requiring any additional information such as continuity, differentiable or convexity about the objective function and fitness landscape, and enjoy a reasonable convergence speed. Since the EAs are population-based approaches, and provide multiple good solutions in every generation, an optimal search for probable optima locations is necessary. Moreover, it is also high significance to get as close as possible to the actual optima. These two issues respectively refer to intensification (exploitation) and diversification (exploration), reflecting the performance of the algorithm. Many techniques such as niching method have been recently developed for preserving diversity in the fitness landscape, and for promoting the convergence of GA in MMO. Most of the existing niching methods such as crowding, fitness sharing, clustering, restricted tournament selection, speciation, and clearing can be hardly successfully applied to real-world MMO engineering problems. Some of the challenges are: i) difficulties in setting many parameters, ii) a good selection pressure tuning in rugged problems, iii) an extra computational effort especially in high dimensional problems and iv) diversity maintenance throughout all generations.

In this paper, we propose a simple powerful population-based evolutionary algorithm for solving MMO problems. In this algorithm, the phenotypic search space is partitioned, and using traditional GA operators, a simple GA searches optima in each sub-region independently. The number of partitions is identified with the use of Kohonen self-organizing map (SOM) neural network which clusters the solutions in the fitness landscape according to their fitness values. The proposed algorithm requires no prior knowledge about the fitness landscape, and only needs the GA and SOM parameters to be set. Moreover, no additional EA scheme such as the external population for elite individuals is used in the algorithm. To evaluate the performance of the proposed method, and compare the obtained results with other reports [18 –20], we have used seven difficult benchmark functions and four constrained multimodal engineering problems with three performance criteria.

The paper is organized as follow; Section 2 reviews the previous relevant works; Section 3 describes the proposed algorithm in detail; Section 4 provided experimental numerical results by presenting standard mathematical and real-world engineering functions characteristics, the performance criteria and finally comparison between the obtained results with other reports. Finally, Section 5 ends the paper with the conclusions and some suggestions for further works.

2 Related works

Pena et al. [21] motivates the benefits, challenges and difficulties of data clustering in MMO. The authors first introduce the capabilities of data clustering in alleviating all optima in MMO. Then, they propose the use of Bayesian networks and conditional Gaussian networks to perform data clustering when the EA is used. Niching evolutionary algorithms (NEA) are the most common methods for maintaining the diversity in population, and preserving the elite solutions during all generations. Since for finding the number of niches, and increasing the performance of the algorithm, priori knowledge of the fitness landscape is necessary and the niching radius must be chosen adaptively, innovative methods based on elitism [22], niche formation [23] and subpopulation search methods [24] have been developed. Many elitism methods are based on the survival of dominant solutions during crossover and mutation, copying them into new population, or trying to liken the new children to the elite solutions. Through using adaptive/dynamic niche number and radius, creating new penalty functions, dividing elite and other solutions into different populations, niche formation methods try to increase the efficiency of the algorithm. Several clustering techniques have been reported to suitably improve the inabilities of the traditional NEA. Imrani et al. [25] uses the fuzzy C-mean algorithm to cluster the population. The output of GA with shared block is imported to the fuzzy clustering block to partition the individuals. Then, in each cycle, according to the center and radius of each cluster, all sub-populations are formed by a spatial separation operator. To determine the number of niches, the fuzzy clustering-based PSO dynamically adapts the clusters radius [26]. The population can also be divided by the fuzzy clustering technique through considering social environment principle [27]. Then, each subpopulation proceeds to actual optima by their own local cultural algorithm. Through using the k-means clustering algorithm, the center of clusters in PSO populations were identified for detecting the best neighborhood positions for the best particle in each iteration [28]. Magele et al. [29] uses the hierarchically clustering with [k (μ (τ)/ρ, λ)] evolution strategy, and completes the gap between centers of clusters to identify the k optima of the optimization function. Some researchers proposed a sharing-based niching or PSO algorithm which makes use of adaptive Macqueen’s k-mean clustering method to divide the population up to k clusters, assuming that each cluster center is associated to one optimum [30]. To reduce the niching impact in the EA, the clustering-based niching (CBN) algorithm was proposed, which specifies one species to each sub-population whereas ecological evolution of each species is completely independent. Ando et al. proposed a novel technique based on isolating subpopulations and suppressing the information of the isolated clusters from the entire population, without calculating the distance between clusters or variance/covariance matrix of the subpopulations [31]. Moreover, a full-dimensional clustering method known as CHIDID clustering high dimensional data (CHIDID) identifies clusters of solutions in multimodal optimization based on the Manhattan distance as the proximity measure, and detects the radius and center of the clusters [32]. The proximity measure index distinguishes the clusters borders. The density-clustering-based niching GA (DCNGA) was proposed to form the shape and size of clusters through adjusting the fitness on the basis of the dynamic niche population size, and using the mating restriction scheme to build up the exploitation of each cluster [33].

3 Methodology of the proposed algorithm

Clustering is an efficient technique to organize an unlabeled input data into a number of groups or classes, the so-called clusters, such that all objectives within a cluster are as similar as possible. The similarity measurement index (SMI) controls the shape of the clusters, i.e. their radii and centers. In the hard classification, according to SMI method, each data can belong to only one cluster, while the specific degree of membership in fuzzy classification dictates the data be included in several clusters [34].

Self-organizing map (SOM) is an unsupervised neural network which produces a low-dimensional cluster map from the input data. On the other hand, based on competitive learning and the discriminant function between neurons, the SOM transforms an incoming data (discrete or continuous) of an arbitrary dimension into a one-or two-dimensional discrete map. The winning neurons at any time are connected in the lateral network.

Genetic algorithm (GA) is a population-based heuristic search method which evolves a group of individuals in a population to the optimal point with the use of biological evolution rules such as reproduction, mutation, recombination and selection. The GA is an evolutionary algorithm which optimizes problems with the help of natural evolution.

To introduce the clustering analysis in the MMO, we combined two intelligent methods (SOM and GA) to find the number and location of multiple optima in multimodal functions, and to enhance the diversity and intensity of the algorithm. In the proposed algorithm, all the individuals of the population in the phenotype space are clustered by the SOM, which results in the identification of all species/niches with the actual optimum hopefully located at the center of the cluster. This clustering divides the fitness landscape into some sub-regions with some simple curves (or hypervolume). The number of the clusters is identified automatically by the SOM and independent from the fitness function characteristics. Then, a simple GA with a small population is run within each cluster to find the actual optimum. To increase the diversity and decrease the number of the fitness evaluations, three policies are adopted including:

Before SOM clustering, the GA runs several generations (k times) until the borders of the clusters are identified, which releases the curse of a high dimensionality problem in high dimensional data and increase the efficiency of SOM [35]. Since the GA tends to converge into one optimum, in this work k is less than 10. In fact, after k generations, GA provides the SOM input data with the pre-distribution of individuals in the phenotype search space;

If two optima are located within the same partitions, the number of the partitions must be increased. Then, the hamming distance between two elites within the same cluster at two consecutive iterations is smaller than the cluster’s radius. The number of the partitions is corrected by the SOM so that all conditions are satisfied;

As illustrated in Fig. 1 the optima maybe is located in the border of cluster. In this case two neighbor clusters is merged together and the radius of cluster is increased. GA runs within new cluster until the obtained optima is closer to the center of cluster.

Fig. 1

Schematic illustration of the solutions distribution over fitness function after k^th generation. All solutions that located on the border of two partitions will be merged within the same partition

Figure 2 illustrated the overall flowchart of the proposed method. The algorithm does not need a large population, an external population to save elite solutions, any pervious information about the fitness function, or any extra parameter setting.

Fig. 2

Flowchart of the proposed algorithm.

4 Evaluation of proposed method

Here, we evaluate the performance of the proposed algorithm after introducing seven well-known benchmark functions. After applying the proposed algorithm, three standard performance metrics of the obtained results were calculated. The numerical findings have been compared with other similar works. Then to demonstrate the efficiency and robustness of the proposed algorithm, we apply the proposed algorithm on four constrained design engineering problem including gear train design, pressure vessel design, welded beam design, tension/compression spring design. For all engineering design problems, numerical obtained results compare with other well-known algorithms.

4.1 Description of the mathematical test functions

To test and analyze the proposed method, we consider a set of unconstrained multimodal benchmark functions with different characteristics. Table 1 shows the multimodal test functions, their initial intervals and number of global/local optima for maximization problem. Some of these functions have symmetric landscapes or equal optima (e.g. F3, F6), some have unequal optima (e.g. F1) with a varying optima distribution over the landscape (e.g. F2, F7) and some functions have both rigid and very smooth fitness landscape (e.g. F2, F6).

Table 1
Test functions, initialization interval and their number of global/local optima

Name Test function Range Peaks (global/local)

F1 (Beasley’s function) $\begin{array}{l} f_{1} (x) = \\ \exp [- 2 \log (2) \times {(\frac{x - 0.08}{0.854})}^{2}] \times \\ \sin^{6} (5 π (x^{0.075} - 0.05)) \end{array}$ 0≼x≼1 1/4

F2 $f_{2} (x) = (1 - x) \times \sin^{4} (\frac{5 π}{{(1 + x)}^{4}})$ 0 ≼ x ≤ 1 1/4

F3 $f_{3} (x) = \ln (x) (\sin (e^{x}) + \sin (3 x))$ 0 ≤ x ≤ 4 1/8

F4 (1D shekel function) $\begin{array}{l} f_{3} (x) = \\ \sum_{i = 1}^{10} {[{(x - a_{i})}^{T} (x - a_{i}) + c_{i}]}^{- 1} \\ Where \end{array}$ 0 ≤ x ≤ 10 1/7

i $a_{i}^{T}$ c_i

1 4.0 4.0 4.0 4.0 0.1

2 1.0 1.0 1.0 1.0 0.2

3 8.0 8.0 8.0 8.0 0.2

4 6.0 6.0 6.0 6.0 0.4

5 3.0 7.0 3.0 7.0 0.4

6 2.0 9.0 2.0 9.0 0.6

7 5.0 5.0 3.0 3.0 0.3

8 8.0 1.0 8.0 1.0 0.7

9 6.0 2.0 6.0 2.0 0.5

10 7.0 3.6 7.0 3.6 0.5

F5 (6-Hump Camel Back function) $\begin{array}{l} f_{5} (x, y) = \\ - [(4 - 2.1 x^{2} + \frac{x^{4}}{3}) x^{2} + x y + (- 4 + 4 y^{2}) y^{2}] \end{array}$ −1.9 ≤ x ≤ 1.9−1.1 ≤ y ≤ 1.1 1/4

F6 (Ursem f3 function) $\begin{array}{l} f_{6} (x, y) = \\ \sin (2.2 π x + \frac{π}{2}) \frac{2 - | y |}{2} \frac{3 - | x |}{2} + \\ \sin (\frac{π}{2} y^{2} + \frac{π}{2}) \frac{2 - | y |}{2} \frac{2 - | x |}{2} \end{array}$ −2 ≤ x ≤ 2−2 ≤ y ≤ 2 1/10

F7 (waves function) $\begin{array}{l} f_{7} (x, y) = \\ {(0.3 x)}^{3} - (x^{2} - 4.5 y^{2}) x y - \\ 4.7 \cos (3 x - y^{2} (2 + x)) \sin (2.5 π x) \end{array}$ −0.9 ≤ x ≤ 1.2−1.2 ≤ y ≤ 1.2 1/9

Name		Test function	Range	Peaks (global/local)
F1 (Beasley’s function)		$\begin{array}{l} f_{1} (x) = \\ \exp [- 2 \log (2) \times {(\frac{x - 0.08}{0.854})}^{2}] \times \\ \sin^{6} (5 π (x^{0.075} - 0.05)) \end{array}$	0≼x≼1	1/4
F2		$f_{2} (x) = (1 - x) \times \sin^{4} (\frac{5 π}{{(1 + x)}^{4}})$	0 ≼ x ≤ 1	1/4
F3		$f_{3} (x) = \ln (x) (\sin (e^{x}) + \sin (3 x))$	0 ≤ x ≤ 4	1/8
F4 (1D shekel function)		$\begin{array}{l} f_{3} (x) = \\ \sum_{i = 1}^{10} {[{(x - a_{i})}^{T} (x - a_{i}) + c_{i}]}^{- 1} \\ Where \end{array}$	0 ≤ x ≤ 10	1/7
		i			$a_{i}^{T}$	c_i
	1	4.0	4.0	4.0	4.0	0.1
	2	1.0	1.0	1.0	1.0	0.2
	3	8.0	8.0	8.0	8.0	0.2
	4	6.0	6.0	6.0	6.0	0.4
	5	3.0	7.0	3.0	7.0	0.4
	6	2.0	9.0	2.0	9.0	0.6
	7	5.0	5.0	3.0	3.0	0.3
	8	8.0	1.0	8.0	1.0	0.7
	9	6.0	2.0	6.0	2.0	0.5
	10	7.0	3.6	7.0	3.6	0.5
F5 (6-Hump Camel Back function)		$\begin{array}{l} f_{5} (x, y) = \\ - [(4 - 2.1 x^{2} + \frac{x^{4}}{3}) x^{2} + x y + (- 4 + 4 y^{2}) y^{2}] \end{array}$	−1.9 ≤ x ≤ 1.9−1.1 ≤ y ≤ 1.1	1/4
F6 (Ursem f3 function)		$\begin{array}{l} f_{6} (x, y) = \\ \sin (2.2 π x + \frac{π}{2}) \frac{2 - \| y \|}{2} \frac{3 - \| x \|}{2} + \\ \sin (\frac{π}{2} y^{2} + \frac{π}{2}) \frac{2 - \| y \|}{2} \frac{2 - \| x \|}{2} \end{array}$	−2 ≤ x ≤ 2−2 ≤ y ≤ 2	1/10
F7 (waves function)		$\begin{array}{l} f_{7} (x, y) = \\ {(0.3 x)}^{3} - (x^{2} - 4.5 y^{2}) x y - \\ 4.7 \cos (3 x - y^{2} (2 + x)) \sin (2.5 π x) \end{array}$	−0.9 ≤ x ≤ 1.2−1.2 ≤ y ≤ 1.2	1/9

4.2 Performance measurements

As discussed earlier, final aim of MMO is finding all optima in search space with acceptable diversity and convergence speed. To analysis the performance of proposed algorithm, three criteria are used to measure the performance of algorithm. Table 2 presented some performance measurements.

Table 2
Performance measures

Measure Description

Success rate (SR) The percentage of independent runs for which all obtained solutions is located near local/global optima.

Maximum peak ratio (MPR) $M P R = \frac{\sum_{i = 1}^{q} f_{i}}{\sum_{i = 1}^{q} F_{i}}$ , Where q is the number of the actual optima, and f_i and F_i are respectively the fitness values of the obtained and actual optima within the final generation.

Chi-square like deviation (Pchi) $p_{c h i} = \sqrt{\sum_{i = 1}^{q + 1} {(\frac{n_{i} - μ_{i}}{σ_{i}})}^{2}}, σ_{i} = \sqrt{\frac{1}{N} \sum_{i = 1}^{q + 1} {(n_{i} - μ_{i})}^{2}}$ , Where μ_i and σ_i are the mean and standard deviation of n_i solutions over the accuracy level of ith optima in the last iteration, and q is the number of the actual optima.

Measure	Description
Success rate (SR)	The percentage of independent runs for which all obtained solutions is located near local/global optima.
Maximum peak ratio (MPR)	$M P R = \frac{\sum_{i = 1}^{q} f_{i}}{\sum_{i = 1}^{q} F_{i}}$ , Where q is the number of the actual optima, and f_i and F_i are respectively the fitness values of the obtained and actual optima within the final generation.
Chi-square like deviation (Pchi)	$p_{c h i} = \sqrt{\sum_{i = 1}^{q + 1} {(\frac{n_{i} - μ_{i}}{σ_{i}})}^{2}}, σ_{i} = \sqrt{\frac{1}{N} \sum_{i = 1}^{q + 1} {(n_{i} - μ_{i})}^{2}}$ , Where μ_i and σ_i are the mean and standard deviation of n_i solutions over the accuracy level of ith optima in the last iteration, and q is the number of the actual optima.

4.3 Experiments and results

The simulation was implemented using Microsoft Visual C# compiler (for GA code) and MATLAB R2009a neural network clustering tool (for SOM classification toolbox) in a computer with Intel core 2 Duo CPU running at 2.0GHz, 2GB of RAM with a Vista Home premium operating system. Table 3 shows the dimension of the objective function, proposed algorithm’s parameters and number of partitions that SOM detected. Note that for all functions, learning rate of SOM is set to 0.01. The crossover operator was chosen to be roulette wheel selection, and the crossover probability and chromosome length were respectively set to 0.9 and 20 for all functions. Since the search space of the GA is limited within each partition, the mutation rate is adjusted to Pm = 0. The algorithm was run 50 times (iteration) for each test function, and the best fitted optimal solutions were obtained. Table 4 presents the values of considered metrics within the accuracy level and number of function evaluations. The value of the standard deviation is dependent on accuracy level; indeed, with a very low accuracy level, we can reduce the standard deviation. As seen from Table 4, the proposed algorithm not only achieves all global/local maxima with a good performance in the success rate and MPR (more efficiency) but also can balance between number of function evaluation, standard deviation and execution time.

Table 3
Partition’s Population size, number of generation, level of accuracy, gradient threshold and partition number for each objective function

Function number	Dimension	Population size	Number of generation	Level of accuracy	Partition count
F1	2D	10	6	0.000001	4
F2	2D	10	6	0.000001	4
F3	2D	10	6	0.005	8
F4	2D	5	6	0.000001	8
F5	3D	5	8	0.005	4
F6	3D	10	8	0.005	12
F7	3D	10	8	0.005	10

Table 4

The execution time, success rate, maximum peak ratio, standard deviation, Pchi and number of function evaluations for 50 runs

Function number	SR	MPR	Standard deviation	Pchi	NFEs
F1	1.00	0.9997	0.0031	5.7	9100
F2	0.98	0.9957	0.0041	5.04	12200
F3	1.00	0.9979	0.0092	4.16	21275
F4	1.00	0.9995	0.0224	4.06	890
F5	1.00	0.9995	0.0211	5.11	6540
F6	1.00	0.9750	0.0122	5.19	12640
F7	0.98	0.9875	0.1155	6.03	44100

For more challenging problems (F6 and F7), although the MPR is relatively low, the value of the SR is significantly near 1.00. This happens because both functions have sharp and smooth peaks simultaneously. This problem could be solved more efficiency if the iteration of GA increased adaptively.

Figure 3 shows the SOM neighbor weight distances for F5 and F7 that illustrated the border of clusters. Figure 4 shows the distribution of the solutions over the fitness landscape of F1–F4, and Fig. 5 shows the contour plot of the solution distribution for F5 and F7; as seen, the proposed algorithm has properly located all the local and global optima.

Fig. 3

SOM clustering map for F5 and F7.

Fig. 4

Solution distribution over fitness landscape of F₁–F₄.

Fig. 5

Contour plot of solution distribution for F₅ and F₇.

Table 5 compares the SR and MPR of the proposed algorithm with the results of other researcher methods. The dashes in the Table 5 indicate that the corresponding results are not available from the literature. Table 6 also compares the success rate and the execution time of the proposed algorithm with well-known algorithms that proposed by reference [20]. It is obviously that when the GA iteration is increased, the computational effort of the algorithm is increased too. It causes that execution time of the algorithm growth significantly. In contrast to other well known algorithms (especially PSO niching methods), proposed method performed better in terms of accuracy (success rate and MPR) and has competitive results in term of convergence speed (number of function evaluations).

4.4 Engineering design problems

To show the validity and effectiveness of the proposed algorithm, four well-studied constrained engineering design problems are considered here. To handle the constraints, we have made use of Joines-Houck dynamic penalty approach, evaluating individuals at any generation using a new fitness function defined as Equation (4.1) [39]

\tilde{f} (x) = f (x) + {(C \times t)}^{α} \times SVC (β, x)

(4.1)

Table 5

Comparison results with differential evolution, PSO niching and its related algorithms

Function		Present work	FERPSO-LS [19]	SPSO-LS [19]	R3PSO-LS [19]	R3PSO-LHC [19]	MSPO [36]	Crowding DE-STL [37]	DE/isolated /1 [38]
F1	SR	1.00	0.00	0.00	0.00	0.00	1.0	1.00	–
	MPR	0.997	0.288	0.29	0.441	0.872	–	–	–
F5	SR	1.00	0.76	0.52	0.64	0.72	–	–	1.00
	MPR	0.995	1.00	0.38	1.00	1.00	–	–	1.00

Table 6

Success rate and execution time comparison results with other numerical optimization algorithms

Test function		Present work	BMPGA	MPGA	DNC	MNGA	CLEARING
F3	SR	1.00	1.00	1.00	1.00	1.00	0.967
	time (s)	4.01	0.49	0.49	0.49	0.49	0.49
F5	SR	1.00	0.933	0.733	0.033	0.067	0.067
	time (s)	2.42	1.684	1.427	2.301	2.49	9.52
F7	SR	0.98	1.00	0.933	0.067	0.964	1.00
	time (s)	9.12	9.23	2.65	22.65	3.34	51.9

where C, α, and β are some constants defined by the user (in this work C = 0.5, α = β = 2 or 3); t is the number of generations, and SVC (β, x) is defined as Equation (4.2) where g_i (x) and h_j (x) are respectively inequality and equality constraint.

S V C (β, x) = \sum_{i = 1}^{n} D_{i}^{β} (x) + \sum_{i = 1}^{p} D_{i}^{β} (x)

(4.2)

\begin{matrix} D_{i} (x) = {\begin{matrix} 0 & g_{i} (x) \leq 0 \\ | g_{i} (x) | & otherwise \end{matrix} 1 \leq i \leq n \end{matrix}

(4.3)

D_{j} (x) = {\begin{matrix} 0 & - ɛ \leq h_{j} (x) \leq ɛ \\ | h_{j} (x) | & otherwise \end{matrix} 1 \leq j \leq p

4.4.1 Gear train design

The objective of the compound gear train problem, presented by Sandgren [40], is to find the number of gears teeth such that the difference between gear ratio approaches as closely as possible to raise0.7ex1 / - lower0.7ex6.931. Obviously, the variables (number of teeth) must be integer. Figure 6 shows the relationship between the driver and follower shafts. The mathematical model of this problem is stated as Equation (4.4).

Fig. 6

Schematic of gear train problem.

\begin{matrix} Minimize (F (x_{1}, x_{2}, x_{3}, x_{4})) = {(\frac{1}{6.931} - \frac{x_{1} x_{2}}{x_{3} x_{4}})}^{2} \\ subject to 12 \leq x_{1}, x_{2}, x_{3}, x_{4} \leq 60, \\ and all {x_{i}}^{,} s are integers . \end{matrix}

(4.4) The results obtained by other well-known researches have been compared in Table 7 with those we have found here using our proposed algorithm.

Table 7

Optimum results for the gear train design

Methods	Optimal design variables
	x ₁	x ₂	x ₃	x ₄	F (x₁, x₂, x₃, x₄)
HAIS [43]	18	18	42	53	1.62E-06
GA [43]	12	20	32	52	4.86E-05
PSO [43]	22	19	16	27	6.78E-01
AIS [43]	14	31	60	56	2.28E-04
Sandgren [40]	18	22	45	60	5.712E-06
Kannan and Kramer [41]	13	15	33	41	2.146E-08
Deb and Goyal [42]	17	14	33	50	1.362E-09
Present work	19	16	49	43	2.728E-12

4.4.2 A tension/compression spring design problem

This problem, introduced by Belegundu [1] and Arora [44], aims at minimizing the weight of a tension/compression spring such that constraints on the outer diameter, minimum deflection, shear stress, and surge frequency are met. The problem illustrated in Fig. 7, is mathematically expressed as Equation (4.5):

Fig. 7

A tension/compression spring.

Minimize (F (x_{1}, x_{2}, x_{3})) = (x_{3} + 2) x_{2} x_{1}^{2}

(4.5) where the design variables are the mean coil diameter (x₁), the wire diameter (x₂), and the number of active coils (x₃). Constraints are

\begin{matrix} g_{1} (x) = 1 - \frac{x_{2}^{3} x_{3}}{7178 x_{1}^{4}} \leq 0, \\ g_{2} (x) = \frac{4 x_{2}^{2} - x_{1} x_{2}}{12566 x_{2} x_{1}^{3} - x_{1}^{4}} + \frac{1}{5108 x_{1}^{2}} - 1 \leq 0 \\ g_{3} (x) = 1 - \frac{140.45 x_{1}}{x_{3} x_{2}^{2}} \leq 0, \\ g_{4} (x) = \frac{x_{1} + x_{2}}{1.5} - 1 \leq 0 \end{matrix}

(4.6) The design variables is changed by

0.05 \leq x_{1} \leq 2.0, 0.25 \leq x_{2} \leq 1.3, 2.0 \leq x_{3} \leq 15.0

(4.7) Table 8 compares the obtained solution of the problem using our proposed algorithm with the other works.

Table 8

Optimum results for the tension/compression spring problem

Methods	Optimal design variables				F (x₁, x₂, x₃)
	x ₁	x ₂	x ₃
Belegundu [1]	0.050000	0.315900	14.250000	0.0128334
Arora [44]	0.053396	0.399180	9.185400	0.0127303
Coello [45]	0.051480	0.351661	11.632201	0.0127048
Coello and Montes [46]	0.051989	0.363965	10.890522	0.0126810
He and Wang [47]	0.051728	0.357644	11.244543	0.0126747
Montes and Coello [48]	0.051643	0.355360	11.397926	0.012698
Kaveh and Talatahari [13]	0.051865	0.361500	11.000000	0.0126432
Kaveh and Talatahari [18]	0.051744	0.358532	11.165704	0.0126384
Present work	0.0516	0.3546	11.3979	0.0126495

4.4.3 A welded beam design problem

As shown in Fig. 8, the aim of the welded beam design problem is to minimize the overall fabrication cost of a special beam welded to a metal body with constraints on shear stress (τ), bending stress (σ), buckling load (P_c), and end deflection (δ) as well as side constraints. The mathematical formulation of the function is:

Fig. 8

Schematic of a pressure vessel.

\begin{matrix} Minimize (F (x)) = 1.10471 x_{1}^{2} x_{2} \\ + 0.04811 x_{3} x_{4} (14 + x_{2}) \end{matrix}

(4.8) Where constraints are:

\begin{matrix} g_{1} (X) = τ ({x}) - τ_{max} \leq 0, \\ g_{2} (X) = σ ({x}) - σ_{max} \leq 0, \\ g_{3} = x_{1} - x_{4} \leq 0, \\ g_{4} (X) = 0.10471 x_{1}^{2} + 0.04811 x_{3} x_{4} (14 + x_{2}) - 5 \leq 0, \\ g_{5} (X) = 0.125 - x_{1} \leq 0, \\ g_{6} (X) = δ ({x}) - δ_{max} \leq 0, \\ g_{7} (X) = P - P_{c} ({x}) \leq 0, \end{matrix}

(4.9)

Table 9

Optimum results for the design of welded beam

Methods	Optimal design variables
	x ₁	x ₂	x ₃	x ₄	F (x₁, x₂, x₃, x₄)
Regsdell and Phillips [50]
APPROX	0.2444	6.2189	8.2915	0.2444	2.3815
DAVID	0.2434	6.2552	8.2915	0.2444	2.3841
SIMPLEX	0.2792	5.6256	7.7512	0.2796	2.5307
RANDOM	0.4575	4.7313	5.0853	0.6600	4.1185
Deb [58]	0.248900	6.173000	8.178900	0.253300	2.433116
Coello [54]	0.208800	3.420500	8.997500	0.210000	1.748309
Coello and Montes [46]	0.205986	3.471328	9.020224	0.206480	1.728226
He and Wang [47]	0.202369	3.544214	9.048210	0.205723	1.728024
Montes and Coello [48]	0.199742	3.612060	9.037500	0.206082	1.737300
Kaveh and Talatahari [13]	0.205700	3.471131	9.036683	0.205731	1.724918
Kaveh and Talatahari [18]	0.205820	3.468109	9.038024	0.205723	1.724866
Present work	0.2273	2.1633	8.2273	0.2487	1.714807

Table 10

Optimum results for pressure vessel problem

Methods	Optimal design variables
	x ₁	x ₂	x ₃	x ₄	F (x₁, x₂, x₃, x₄)
Sandgren [40]	1.125000	0.625000	47.700000	117.701000	8129.1036
Kannan and Kramer [41]	1.125000	0.625000	58.291000	43.690000	7198.0428
Deb [49]	0.937500	0.500000	48.329000	112.679000	6410.3811
Coello [45]	0.812500	0.437500	40.323900	200.000000	6288.7445
Coello and Montes [46]	0.812500	0.437500	42.097398	176.654050	6059.9463
He and Wang [47]	0.812500	0.437500	42.091266	176.746500	6061.0777
Montes and Coello [48]	0.812500	0.437500	42.098087	176.640518	6059.7456
Kaveh and Talatahari [13]	0.812500	0.437500	42.0 9835	176.637751	6059.7258
Kaveh and Talatahari [18]	0.812500	0.437500	42.103624	176.572656	6059.0888
Present work	0.812500	0.437500	42.023	177.7373	6072.1534

where

\begin{matrix} τ (X) = \sqrt{{(τ^{'})}^{2} + 2 τ^{'} τ^{″} \frac{x_{2}}{2 R} + {(τ^{″})}^{2}}, \\ τ^{'} = P (L + \frac{x_{2}}{2}), R = \sqrt{\frac{x_{2}^{2}}{4} +} {(\frac{x_{1} + x_{2}}{2})}^{2}, \\ J = 2 {\sqrt{2} x_{1} x_{2}} [\frac{x_{2}^{2}}{12} + {(\frac{x_{1} + x_{3}}{2})}^{2}], \\ σ (X) = \frac{6 PL}{x_{4} x_{3}^{2}}, δ (X) = \frac{4 P L^{3}}{E x_{4} x_{3}^{3}}, P = 6, 000 lb, \\ P_{c} (X) = \frac{4.013 E \sqrt{\frac{x_{4}^{6} x_{3}^{2}}{36}}}{L^{2}} (1 - \frac{x_{3}}{2 L} \sqrt{\frac{E}{4 G}}), \\ L = 14 in, E = 30 \times 10^{6} psi, G = 12 \times 10^{6} psi \end{matrix}

(4.10) The design variables is changed by Equation (4.11).

0.1 \leq x_{1}, x_{4} \leq 2.0, 0.1 \leq x_{2}, x_{3} \leq 1.3

(4.11) The results obtained by the other researches have been compared in Table 9 with those we have found here using our proposed algorithm.

4.4.4 A pressure vessel design problem

This problem, illustrated in Fig. 9, aims at minimizing the sum of the material, forming, and welding costs for a cylindrical vessel clapped at its ends. This problem, first proposed by Sandgren [40], can be mathematically expressed as Equation (4.12).

Fig. 9

A welded beam system.

\begin{matrix} Min (F (x)) = 0.6224 x_{1} x_{3} x_{4} + 1.7781 x_{2} x_{3}^{3} + \\ x_{1}^{2} (3.1611 x_{4} + 19.84 x_{3}) \end{matrix}

(4.12) subject to:

\begin{matrix} g_{1} (X) : 0.0193 x_{3} - x_{1} \leq 0, \\ g_{2} (X) : 0.00954 x_{3} - x_{2} \leq 0, \\ g_{3} (X) : 750 \times 1728 - π x_{3}^{2} (x_{4} + 0.7 ex 4 / - 0.7 ex 3 x_{3}) \leq 0, \\ g_{4} (X) : x_{4} - 240 \leq 0 \end{matrix}

(4.13) The design variables is changed by

\begin{matrix} 0 \leq x_{1}, x_{2} \leq 99 and granularity 0.0625, \\ 10 \leq x_{3}, x_{4} \leq 200 \end{matrix}

(4.14) Table 10 compares the results obtained from optimal famous algorithms and the present algorithm.

5 Conclusions

Detecting and determining the number and radius of all niches in multimodal optimization play a vital rule in increasing the efficiency and effectiveness of the optimization algorithm.

This paper has introduced a new GA-based technique that uses self-organizing map (SOM) neural network to automatically identify the number of the niches for finding all local and global optima of multimodal problems. In the proposed algorithm, all the individuals of the population in the phenotype space are clustered by the SOM NN, which results in the identification of all species/niches with the actual optimum hopefully located at the center of the cluster. This clustering divides the fitness landscape into some sub-regions with some simple curves (or hypervolume). Then, a simple GA with a small population is run within each cluster to find the actual optimum. Except the adjusted SOM settings, the proposed algorithm does not need the niche radius, many parameters settings, and any prior knowledge about the objective function. Various optimization problems including seven benchmark unconstrained mathematical functions, and four constrained real-world engineering optimization problems were presented to demonstrate the effectiveness and robustness of the proposed algorithm. Obtained results were compared to other well-known optimization methods, based on three common performance criteria. The experimental results show that the proposed method is efficient, and superior in the number of function evaluations and convergence rate to existing well-known algorithms, and gives competitive results in accuracy and efficiency.

For the future work, it is straightforward to determine the number of clusters with mathematical methods such as multivariate statistical methods. Another interesting research work is to combine the proposed method with local search methods or other evolutionary algorithms. It would be also interesting to examine the performance of the proposed algorithm with other criteria such as Mann-Whitney U-test and two-sample Kolmogorov-Smirnov test.

References

A.D.

Belegundu , A study of mathematical programming methods for structural optimization, Ph.D. thesis, Department of Civil and Environmental Engineering, University of Iowa, USA, 1982.

Shabani and

Sowlati , A mixed integer non-linear programming model for tactical value chain optimization of a wood biomass power plant, Appl Energy 104 (2013), 353–361.

R.G.

Garroppo ,

Giordano ,

Nencioni and

M.G.

Scutella , Mixed integer non-linear programming models for green network design, Comput OperRes 40(1) (2013), 273–281.

Kompas and

Chu , Comparing approximation techniques to continuous-time stochastic dynamic programming problems: Applications to natural resource modelling, Environ Model Softw 38 (2012), 1–12.

Liu ,

Wang and

Yang , An iterative adaptive dynamic programming algorithm for optimal control of unknown discrete-time nonlinear systems with constrained inputs, Inform Sci 220 (2013), 331–342.

Si ,

A.G.

Barto ,

W.B.

Powell and

D.C.

Wunsch , Handbook of Learning and Approximate Dynamic Programming, Wiley, New York, 2004.

Samadi ,

Mirzazadeh and

M.M.

Pedram , Fuzzy pricing, marketing and service planning in a fuzzy inventory model: A geometric programming approach, Appl Math Model 37 (2013), 6683–6694.

Yelchuru and

Skogestad , Convex formulations for optimal selection of controlled variables and measurements using Mixed Integer Quadratic Programming, J Process Contr 22(6) (2012), 995–1007.

Y.M.

Zhang ,

G.H.

Huang ,

Q.G.

Lin and

H.W.

Lu , Integer fuzzy credibility constrained programming for power system management, Energy 38(1) (2012), 398–405.

10.

Burer and

A.N.

Letchford , Non-convex mixed-integer nonlinear programming: A survey, Surv Oper Res Manage Sci 17(2) (2012), 97–106.

11.

W.M.

Jenkins , Towards structural optimization via the genetic algorithm, Comput Struct 40(5) (1991), 1321–1327.

12.

Poli , Analysis of the publications on the applications of particle swarm optimization, JAEA 10 (2008), 1–10.

13.

Kaveh and

Talatahari , An improved ant colony optimization for constrained engineering design problems, Eng Comput 27(1) (2010), 155–182.

14.

F.O.

Sonmez , Structural Optimization using Simulated Annealing, InTech, 2008.

15.

Sonmez , Artificial bee colony algorithm for optimization of truss structures, Appl Soft Comput 11(2) (2011), 2406–2418.

16.

K.S.

Lee and

Z.W.

Geem , A new meta-heuristic algorithm for continuous engineering optimization: Harmony search theory and practice, Comput Method Appl M 194 (2005), 3902–3933.

17.

Yi ,

Duan and

T.W.

Liao , Three improved hybrid meta-heuristic algorithms for engineering design optimization, Appl Soft Comput 13(5) (2013), 2433–2444.

18.

Kaveh and

Talatahari , A novel heuristic optimization method: Charged system search, Acta Mech 213(3) (2010), 267–289.

19.

B.Y.

Qu ,

J.J.

Liang and

P.N.

Suganthan , Niching particle swarm optimization with local search for multi-modal optimization, Inform Sci 197 (2012), 131–143.

20.

Yao ,

Kharma and

Grogono , Bi-objective multipopulation genetic algorithm for multimodal function optimization, Evol Comput 14(1) (2010), 80–102.

21.

J.M.

Pena ,

J.A.

Lozano and

Larranaga , Benefits of data clustering in multimodal function optimization via EDAs, in: P. Larranaga and J.A. Lozano (eds.), Estimation ofDis-tribution Algorithms, Springer, 2002, pp. 101–127.

22.

Costa and

Oliveira , An adaptive sharing elitist evolution strategy for multiobjective optimization, Evol Comput 11(4) (2003), 417–438.

23.

D.E.

Goldberg and

Wang , Adaptive niching via coevo-lutionary sharing, ILLiGAL Technical Report No. 97007, Illinois Genetic Algorithms Laboratory, University of Illi-noise, Urbana, IL, 1997.

24.

R.K.

Ursem , Multinational evolutionary algorithms, Proceedings of the IEEE Int. Conference on Evolutionary Computation, Washington, USA, 1999, pp. 1633–1640.

25.

A.E.

Imrani ,

Bouroumi ,

Z.E.

Abidine ,

Limouri and

Essaid , A fuzzy clustering-based niching approach to multimodal function optimization, Cogn Syst Res 1 (2) (2000), 119–133.

26.

Alami ,

Benameur and

A.El.

Imrani , A fuzzy clustering based PSO for multimodal optimization, Int J Comput Intell Res (2009), 96–107.

27.

Alami ,

A.El.

Imrani and

Bouroumi , A multipopulation cultural algorithm using fuzzy clustering, Appl Soft Comput 7(2) (2007), 506–519.

28.

Kennedy , Stereotyping: Improving particle swarm performance with cluster analysis, Proceedings of the Congress on Evolutionary Computation, California, USA, 2000, pp. 1507–1512.

29.

Ch.

Magele ,

Aichholzer ,

Aurenhammer ,

Brandstat-ter ,

Krasser ,

Muhlmann and

Renhart , Evolution strategy and hierarchical clustering, Proceeding of 13th COMPUMAG Conference, Lyon-Evian, France, 2001, pp.

30.

Passaro and

Starita , Particle swarm optimization for multimodal functions: A clustering approach, J Artif Evol Appl 2008(2008), 1–15.

31.

Ando ,

Sakuma and

Kobayashi , Adaptive isolation model using data clustering for multimodal function optimization, Proc Genet Evol Comput Conf (2005), 1417–1424.

32.

P.J.

Ballester and

J.N.

Carter , An algorithm to identify clusters of solutions in multimodal optimisation, in: C.C. Ribeiro and S.L. Martins (eds.), Experimental and Efficient Algorithms. Lecture Notes in Computer Science, Springer Verlag, 2004, pp. 42–56.

33.

Zhang ,

Yu ,

Shao and

Feng , A clustering based GA for multimodal optimization in uneven search space, Proceeding of 6th World Congress on Intelligent Control and Automation, China, 2006, pp. 3134–3138.

34.

Duda and

Hart , Pattern Classification and Scene Analysis, Wiley, New York, 1973.

35.

Bellman , Adaptive Control Processes: A Guided Tour, Princeton University Press, 1961.

36.

Wang ,

Moon ,

Yang and

Wang , A memetic particle swarm optimization algorithm for multimodal optimization problems, Inform Sci 197 (2012), 38–52.

37.

K.C.

Wong ,

C.H.

Wu ,

R.K.P.

Mok ,

Peng and

Zhang , Evolutionary multimodal optimization using the principle of locality, Inform Sci 194 (2012), 138–170.

38.

Otani ,

Suzuki and

Arita , DE/isolated/1: A new mutation operator for multimodal optimization with differential evolution, J Mach Learn Cybern 4(2) (2013), 99–105.

39.

Joinnes and

Houck , On the use of non-stationary penalty function to solve nonlinear constrained optimization problems with GAs, Proceedings of Evolutionary Computation, Florida, USA, 1994, pp. 579–584.

40.

Sandgren , Nonlinear integer and discrete programming in mechanical design, Proceedings of the ASME Design Technology Conference, Kissimme, FL, 1988, pp. 95–105.

41.

B.K.

Kannan and

S.N.

Kramer , An augmented Lagrange multiplier based method for mixed integer discrete continuous optimization and its applications to mechanical design, JMechDes 116(2) (2008), 405–411.

42.

Deb and

Goyal , A combined genetic adaptive search (GeneAS) for engineering design, Comput Sci Inform 26(4) (1988), 1–20.

43.

D.F.W.

Yap ,

S.P.

Koh ,

S.K.

Tiong and

S.K.

Prajindra , A swarm-based artificial immune system for solving multimodal functions, Appl Artif Intell 25(8) (2011), 693–707.

44.

J.S.

Arora , Introduction to Optimum Design, McGraw-Hill, New York, 1989.

45.

C.A.C.

Coello , Use of a self-adaptive penalty approach for engineering optimization problems, Comput Ind 41(2) (2000), 113–127.

46.

C.A.C.

Coello and

E.M.

Montes , Constraint-handling in genetic algorithms through the use of dominance-based tournament selection, Adv Eng Inform 16(3) (2002), 193–203.

47.

He and

Wang , An effective co-evolutionary particle swarm optimization for constrained engineering design problems, Eng Appl Artif Intel 20(1) (2007), 89–99.

48.

E.M.

Montes and

C.A.C.

Coello , An empirical study about the usefulness of evolution strategies to solve constrained optimization problems, Int J Gen Syst 37(4) (2008), 443–473.

49.

Deb , Optimal design of a welded beam via genetic algorithms, Astronaut Aeronaut 29(11) (1991), 2013–2015.

50.

K.M.

Ragsdell and

D.T.

Phillips , Optimal design of a class of welded structures using geometric programming, J Manuf Sci E-T ASME 98(3) (1976), 1021–1025.

A genetic algorithm with SOM neural network clustering for multimodal function optimization

Abstract

Keywords

1 Introduction

2 Related works

3 Methodology of the proposed algorithm

4.1 Description of the mathematical test functions

Table 3 Partition’s Population size, number of generation, level of accuracy, gradient threshold and partition number for each objective function

References

Table 3
Partition’s Population size, number of generation, level of accuracy, gradient threshold and partition number for each objective function