A New Swarm Intelligence Approach for Clustering Based on Krill Herd with Elitism Strategy

Abstract

As one of the most popular and well-recognized clustering methods, fuzzy C-means (FCM) clustering algorithm is the basis of other fuzzy clustering analysis methods in theory and application respects. However, FCM algorithm is essentially a local search optimization algorithm. Therefore, sometimes, it may fail to find the global optimum. For the purpose of getting over the disadvantages of FCM algorithm, a new version of the krill herd (KH) algorithm with elitism strategy, called KHE, is proposed to solve the clustering problem. Elitism tragedy has a strong ability of preventing the krill population from degrading. In addition, the well-selected parameters are used in the KHE method instead of originating from nature. Through an array of simulation experiments, the results show that the KHE is indeed a good choice for solving general benchmark problems and fuzzy clustering analyses.

1. Introduction

Currently, fuzzy clustering is one of the important research branches in many fields, such as knowledge discovery, image processing, machine learning, and pattern recognition. With the expansion of scope of the study, more accurate clustering results are required from various aspects in scientific and practical application. Fuzzy C-Means (FCM) clustering is one of the most popular and well-recognized clustering methods. This method uses the concept of the geometric closeness of data points in Euclidean space. It allocates these data to different clustering, and the distance between these clusters is then determined. The FCM clustering algorithm is the basis of other fuzzy clustering analysis methods in theory and application respects, and it is therefore most widely-used among various clustering algorithms. However, the FCM algorithm is essentially a local search optimization algorithm. Herein, if its initial value is selected improperly, it will converge to a local minimum. Therefore, this drawback limits the FCM algorithm to be used in many applications.

Aiming at the disadvantages of the FCM algorithm, researchers have proposed several methods to improve its performance. Apart from the traditional methods, recently, various metaheuristic algorithms have been proposed by the inspiration of nature and successfully addressed all kinds of application problems, such as grey wolf optimizer (GWO) [1,2], genetic algorithm (GA) [3], biogeography-based optimization (BBO) [4,5,6], animal migration optimization (AMO) [7], gravitational search algorithm (GSA) [8,9,10], cuckoo search (CS) [11,12,13,14,15], stud genetic algorithm (SGA) [16], wolf search algorithm (WSA) [17], multi-verse optimizer (MVO) [18], dragonfly algorithm (DA) [19], moth-flame optimization (MFO) [20], earthworm optimization algorithm (EWA) [21], harmony search (HS) [22,23], firefly algorithm (FA) [24,25,26], particle swarm optimization (PSO) [27,28,29], monarch butterfly optimization (MBO) [30], ant colony optimization (ACO) [31], bat algorithm (BA) [32,33,34,35,36], differential evolution (DE) [37,38,39,40], and interior search algorithm (ISA) [41]. Among them, swarm-based metaheuristic search, so called swarm intelligence methods, are one of the most well-known paradigms in nature-inspired algorithms. Due to its remarkable performance, they have dealt with a variety of applications, such as reliability [42,43], knapsack problems [44], quantitative interpretation [45], scheduling [46], path planning [47], parameter estimation [48], global numerical optimization [49,50,51], neural network training [52,53] and feature selection [54]. The KH method that is inspired by the krill herding behavior of krill in sea was first proposed by Gandomi and Alavi in 2012 [55,56]. Since it has high stability and strong robustness when solving optimization problems, many researchers have made in-depth studies about it and various improved version of KH methods have been proposed [57,58,59,60]. The main differences between the KH algorithm and other swarm intelligence algorithms is that the parameters used in the KH algorithm is fully originated from the real krill herd in nature. Here, a new version of KH algorithm with elitism strategy, called KHE, is proposed. Elitism tragedy can prevent the krill population from degrading. In KHE, the well-selected parameters are used instead of originating from nature [61,62]. Furthermore, the KHE method is applied to solve clustering problem for the purpose of escaping a local minimum. Moreover, with the aim of showing the performance of KHE method, it is compared with six other metaheuristic algorithms through seven complicated benchmark problems. The results show that the KHE method is able to find the better function values on given benchmark problems than six others; KHE is also a good choice of implementing fuzzy clustering analyses.

Section 2 provides a basic knowledge of FCM clustering algorithm. Section 3 reviews the optimization process of KH, and then a framework of KHE method is given. This is followed by the usage of KHE method to solve the clustering problem. With the aim of the showing the performance of the KHE method, several simulation results comparing KHE with other methods for general benchmark functions and clustering are presented in Section 4. The discussion and future work orientation can be provided in Section 5.

2. Fuzzy C-Means (FCM) Clustering Algorithm

Let X = {x₁, x₂, …, x_n} be n data samples; c (2 ≤ c ≤ n) is the number of the divided categories for these data samples; {A₁, A₂, …, A_c} indicates that the corresponding c categories, and U is their similarity classification matrix, whose cluster centers are {v₁, v₂, …, v_c}; μ_k(x_i) is the membership degree of x_i in the category A_k (abbreviated as μ_ik). The objective function J_b can be expressed as follows:

$$J_b(U,v)={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{k=1}^c{({\mu }_{ik})}^b{(d_{ik})}^2}}$$

(1)

where d_ik is the Euclidean distance that is used to measure distance between the i-th sample x_i and the center point of the k-th category. It can be calculated as follows:

$$d_{ik}=d(x_i-v_k)=\sqrt{{\displaystyle \sum _{j=1}^m{(x_{ij}-v_{kj})}^2}}$$

(2)

where m is the number of characteristics of the data sample; b is the weighting parameter and its range is $1\le b\le \infty$. The FCM clustering algorithm is to find an optimal classification, so that the classification is able to produce the smallest function value J_b. It is required that the sum of the values of membership degree for a sample in terms of each cluster is 1. That is to say, it can be described as

$${\displaystyle \sum _{j=1}^c{\mu }_j(x_i)=1,i=1,2,\cdots ,n}$$

(3)

As stated before, μ_ik is the membership degree of x_i in the category A_k, and it can be updated as

$${\mu }_{ik}=\frac{1}{{\displaystyle \sum _{j=1}^c{\left(\frac{d_{ik}}{d_{jk}}\right)}^{\frac{2}{b-1}}}}$$

(4)

Subsequently, all the cluster centers {v_i} are calculated as

$$v_{ij}=\frac{{\displaystyle \sum _{k=1}^n{\left({\mu }_{ik}\right)}^b{x}_{kj}}}{{\displaystyle \sum _{k=1}^n{\left({\mu }_{ik}\right)}^b}}$$

(5)

here, we suppose $I_k=\left\{i\right|2\le c<n;d_{ik}=0\}$. For all of category i, $i\in I_k$, μ_ik = 0.

The updating process mentioned above is repeated by Equations (4) and (5) until the method converges. When the algorithm converge, in theory, various cluster centers for each sample and the membership degree in terms of each category are obtained at this time, thus fuzzy clustering partition has been done by now. Although FCM has a high search speed, it is essentially a local search algorithm, and is therefore very sensitive to initial cluster centers. If the cluster centers have the initial poor choice, it will converge to a local minimum.

3. KHE Method for Clustering Problem

3.1. KH Method

Krill herd (KH) [55] is a novel swarm intelligence method for solving optimization problems. It is the simplification and idealization of the herding of the krill swarms in sea. The position of an individual krill is determined by three motions as:

(i)

movement induced by other krill individuals;

(ii)

foraging action; and

(iii)

random diffusion

In KH, the Lagrangian model is used in a d-dimensional decision space as shown in Equation (6).

$$\frac{d{X}_i}{dt}\approx N_i+F_i+D_i$$

(6)

where N_i is the motion induced by other krill individuals; F_i is the foraging motion, and D_i is the physical diffusion of the i-th krill individuals.

3.1.1. Motion Induced by Other Krill Individuals

The direction of motion induced, α_i, is approximately evaluated by the target effect, a local effect, and a repulsive effect. For krill i, it can be defined as:

$$N_i^{new}=N^{\max }{\mathsf{\alpha }}_i+{\omega }_n{N}_i^{old}$$

(7)

where

$${\mathsf{\alpha }}_i={\mathsf{\alpha }}_i^{local}+{\mathsf{\alpha }}_i^{target}$$

(8)

and N^max is the maximum induced speed, ω_n is the inertia weight of the motion induced, $N_i^{old}$ is the last motion induced, ${\mathsf{\alpha }}_i^{local}$ is the local effect provided by the neighbors and ${\mathsf{\alpha }}_i^{target}$ is the target direction effect provided by the best krill individual.

3.1.2. Foraging Motion

The foraging motion is influenced by the two main factors: The previous and current food location. For the i-th krill individual, this motion can be expressed as follows:

$$F_i=V_f{\mathsf{\beta }}_i+{\omega }_f{F}_i^{old}$$

(9)

where

$${\mathsf{\beta }}_i={\mathsf{\beta }}_i^{food}+{\mathsf{\beta }}_i^{best}$$

(10)

and V_f is the foraging speed, ω_f is the inertia weight of the foraging, $F_i^{old}$ is the last foraging motion, ${\mathsf{\beta }}_i^{food}$ is the food attractiveness and ${\mathsf{\beta }}_i^{best}$ is the effect of the best fitness of the i-th krill so far.

3.1.3. Random Diffusion

This motion can be expressed in terms of a maximum diffusion speed and a random directional vector. It can be formulated as follows:

$$D_i=D^{\max }\delta$$

(11)

where D_max is the maximum diffusion speed, and δ is the random directional vector.

Based on the above motions, the position of a krill individual from t to t + Δt is given by the following equation:

$$X_i\left(t+\Delta t\right)=X_i(t)+\Delta t\frac{d{X}_i}{dt}$$

(12)

It should be noted that Δt is a constant that can be determined by problem of interest. More details about the KH algorithm can be found in [55].

3.2. KH Method with Elitism Strategy (KHE)

As stated before, the KH method can always include the best krill individual in the population. However, the positions of all the krill individuals in the population will be updated during the optimization process regardless of its good and bad. When the best one is being updated, there is a probability of worsening the best one. If this happens, the whole population will deteriorate so that it may lead to slow convergence.

With the aim of preventing the krill population degrade, an elitism strategy is incorporated into the basic KH method. That is, in our current work, a new version of the KH method with elitism strategy (abbreviated as KHE) is proposed. In KHE method, certain best krill individuals are memorized, and then all the krill are updated by three motions. Finally, certain worst krill individuals in the new population will be replaced by the memorized best ones in the last generation. Elitism strategy can forbid the best ones being destroyed by three krill motions, and can guarantee the population can always proceed to the better status. Limited by the length of the paper, the more detailed process of elitism strategy can be referred to in [4,63].

3.3. KHE Method for Clustering Problem

The clustering problem is essentially an optimization problem. Therefore, clustering problem can be solved by the KHE method. As per Section 2, Section 3.1, and Section 3.2, the optimization process of KHE method for clustering problem can be simply represented as follows:

(1)

Initialize the control parameters. All the parameters used in KHE are firstly initialized.

(2)

Randomly initialize c cluster centers, and generate the initial population, calculate membership degree of each cluster center for all samples by Equation (4), and the fitness of each krill individual value f_i, where i = 1, 2, …, NP. Here, NP is the number of population size.

(3)

Set t = 0.

(4)

Save the KEEP best krill individuals as BEST.

(5)

Implement three motions and update the positions of krill individuals in population.

(6)

Replace the KEEP worst krill individuals with the KEEP best krill individuals saved in BEST.

(7)

Calculate c clustering centers, membership degree and fitness for each individual.

(8)

If the t < Maxgen, t = t + 1, go to Equation (4); Otherwise, the algorithm is over and finds the final global optimal solution.

Based on the above steps, a brief presentation of KHE for clustering problem is shown in Figure 1.

Figure 1. Flowchart of FCM algorithm by using the KHE method.

Figure 1. Flowchart of FCM algorithm by using the KHE method.

4. Simulation Results

In this section, after function evaluation through an array of experiments conducted in benchmark functions (see Table 1), the clustering problem is dealt with by the KHE method. More detailed descriptions of all the benchmarks can be referred to in [4,64,65]. Note that the dimensions of functions are thirty. In order to obtain fair results, all the implementations are conducted under the same conditions as shown in [59].

Table 1. Benchmark functions.

No.	Name	Definition
F01	Dixon & Price	$f(\overrightarrow{x})={\left(x_1-1\right)}^2+{\displaystyle \sum _{i=2}^{n}i{\left(2x_i^2-x_{i-1}\right)}^2}$
F02	Griewank	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^n\frac{x_i^2}{4000}}-{\displaystyle \prod _{i=1}^n\cos \left(\frac{x_i}{\sqrt{i}}\right)+1}$
F03	Holzman 2 function	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^{n}i{x}_i^4}$
F04	Powell	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^{n/4}{(x_{4i-3}+10x_{4i-2})}^2}+5{(x_{4i-1}-x_{4i})}^2\text{\hspace{0.05em}+ }{(x_{4i-2}-x_{4i-1})}^4+10{(x_{4i-3}-x_{4i})}^4$
F05	Quartic with noise	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^n(i\cdot x_i^4+U(0,1))}$
F06	Rosenbrock	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^{n-1}\left[100{\left(x_{i+1}-x_i^2\right)}^2+{\left(x_i-1\right)}^2\right]}$
F07	Sphere	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^n{x}_i^2}$

Table 1. Benchmark functions.

No.	Name	Definition
F01	Dixon & Price	$f(\overrightarrow{x})={\left(x_1-1\right)}^2+{\displaystyle \sum _{i=2}^{n}i{\left(2x_i^2-x_{i-1}\right)}^2}$
F02	Griewank	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^n\frac{x_i^2}{4000}}-{\displaystyle \prod _{i=1}^n\cos \left(\frac{x_i}{\sqrt{i}}\right)+1}$
F03	Holzman 2 function	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^{n}i{x}_i^4}$
F04	Powell	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^{n/4}{(x_{4i-3}+10x_{4i-2})}^2}+5{(x_{4i-1}-x_{4i})}^2\text{\hspace{0.05em}+ }{(x_{4i-2}-x_{4i-1})}^4+10{(x_{4i-3}-x_{4i})}^4$
F05	Quartic with noise	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^n(i\cdot x_i^4+U(0,1))}$
F06	Rosenbrock	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^{n-1}\left[100{\left(x_{i+1}-x_i^2\right)}^2+{\left(x_i-1\right)}^2\right]}$
F07	Sphere	$f(\overrightarrow{x})={\displaystyle \sum _{i=1}^n{x}_i^2}$

The parametric study about KH has been done in [61]. The parameters for KHE method are the same as [61], which are set as follows: V_f = 0.02, D^max = 0.005 and N^max = 0.01. For the parameters used in the other methods, their settings can be referred to in [4,63].

In order to remove the influence of the randomness and get the relatively representative statistical results, 200 implementations have been done independently on each benchmark. The population size and maximum generation number are set to 50 in the experiments conducted in Section 4.1. In the following experiments, the optimal solution for each test problem is bolded.

4.1. Convergent Performance Compared KHE with Six Other Methods

The performance of KHE was compared with basic KH and other five optimization methods (ACO [31], GA [3], HS [22,23], PSO [27,66] and SGA [16]) on seven optimization problems (see Table 2).

From Table 2, it can be seen that, for the best, mean and worst function values, KHE has the best performance on all the seven benchmarks on average. For other methods, their obtained function values are similar. Carefully looking at Table 2, generally speaking, SGA has the relatively better final optimization values than the other five methods. The results in Table 2 indicate that the KHE method is the proper strategy for most optimization problems.

Table 2. Mean, best and worst function values obtained by different methods.

	Function	ACO	GA	HS	KH	KHE	PSO	SGA
MEAN	F01	3.36E5	1.25E5	8.26E5	1.55E5	18.90	2.77E5	8.64E3
	F02	32.55	106.40	403.60	67.46	1.13	172.70	29.50
	F03	8.72E4	3.51E4	2.07E5	3.74E4	1.86	8.36E4	2.29E3
	F04	5.92E3	1.88E3	6.06E3	3.70E3	36.01	2.47E3	182.80
	F05	17.75	7.92	54.68	10.14	4.44E−4	13.77	0.66
	F06	5.47E3	1.86E3	3.99E3	1.22E3	31.60	1.38E3	313.10
	F07	85.19	21.57	119.50	20.03	0.04	50.05	11.02
BEST	F01	1.14E5	1.71E4	3.13E5	5.31E4	3.37	2.44E4	1.41E3
	F02	14.90	33.08	266.10	35.84	1.02	91.07	9.64
	F03	2.36E4	6.30E3	9.39E4	1.76E4	0.03	1.16E4	300.60
	F04	2.43E3	388.10	2.26E3	1.00E3	2.41	1.01E3	52.56
	F05	6.12	1.28	25.52	5.10	5.13E−6	4.22	0.08
	F06	3.73E3	513.10	2.20E3	697.30	28.19	508.00	137.50
	F07	55.53	5.80	70.20	10.44	3.84E−3	29.45	4.16
WORST	F01	8.46E5	3.63E5	1.26E6	2.85E5	167.60	2.39E6	4.90E4
	F02	69.45	235.90	498.70	101.70	1.63	568.30	68.65
	F03	1.76E5	1.35E5	3.29E5	6.26E4	20.86	6.00E5	8.98E3
	F04	8.89E3	4.42E3	1.07E4	6.35E3	218.40	4.72E3	558.50
	F05	37.48	28.87	81.76	17.74	7.82E−3	32.10	5.08
	F06	8.08E3	4.14E3	5.70E3	1.90E3	46.15	2.88E3	688.00
	F07	126.40	42.72	143.40	33.13	0.31	65.62	21.11

Table 2. Mean, best and worst function values obtained by different methods.

	Function	ACO	GA	HS	KH	KHE	PSO	SGA
MEAN	F01	3.36E5	1.25E5	8.26E5	1.55E5	18.90	2.77E5	8.64E3
	F02	32.55	106.40	403.60	67.46	1.13	172.70	29.50
	F03	8.72E4	3.51E4	2.07E5	3.74E4	1.86	8.36E4	2.29E3
	F04	5.92E3	1.88E3	6.06E3	3.70E3	36.01	2.47E3	182.80
	F05	17.75	7.92	54.68	10.14	4.44E−4	13.77	0.66
	F06	5.47E3	1.86E3	3.99E3	1.22E3	31.60	1.38E3	313.10
	F07	85.19	21.57	119.50	20.03	0.04	50.05	11.02
BEST	F01	1.14E5	1.71E4	3.13E5	5.31E4	3.37	2.44E4	1.41E3
	F02	14.90	33.08	266.10	35.84	1.02	91.07	9.64
	F03	2.36E4	6.30E3	9.39E4	1.76E4	0.03	1.16E4	300.60
	F04	2.43E3	388.10	2.26E3	1.00E3	2.41	1.01E3	52.56
	F05	6.12	1.28	25.52	5.10	5.13E−6	4.22	0.08
	F06	3.73E3	513.10	2.20E3	697.30	28.19	508.00	137.50
	F07	55.53	5.80	70.20	10.44	3.84E−3	29.45	4.16
WORST	F01	8.46E5	3.63E5	1.26E6	2.85E5	167.60	2.39E6	4.90E4
	F02	69.45	235.90	498.70	101.70	1.63	568.30	68.65
	F03	1.76E5	1.35E5	3.29E5	6.26E4	20.86	6.00E5	8.98E3
	F04	8.89E3	4.42E3	1.07E4	6.35E3	218.40	4.72E3	558.50
	F05	37.48	28.87	81.76	17.74	7.82E−3	32.10	5.08
	F06	8.08E3	4.14E3	5.70E3	1.90E3	46.15	2.88E3	688.00
	F07	126.40	42.72	143.40	33.13	0.31	65.62	21.11

4.2. Clustering Problem Compared KHE with Seven Other Methods

As stated before, a clustering problem is essentially an optimization problem, so it can be solved by the KHE method. Here, KHE is compared with pure FCM and the other five metaheuristic methods including the basic KH method. The dataset used in this paper is the same with the data in [67]. The data have four-hundred data samples, and its characteristic dimension is two. Now, we will divide these data samples into four categories. Therefore, each krill contains eight elements. Population size and maximum generation number are set to 16 and 25, respectively. For other algorithms, their parameter settings are the same as Section 4.1. Figure 2 is the clustering results by pure FCM clustering algorithm when its final objective function value is 3.620176. Figure 3 shows the optimization process of KHE method for clustering problem. From Figure 3, we can see, KHE has a fast convergent speed for clustering problem. Figure 4 is the clustering results by KHE algorithm when its final objective function value is 3.303485. From Figure 2 and Figure 4, we can see that, KHE method can obtain more accurate clustering results than pure FCM. More results can be recorded in Table 3. From Table 3, on average, the KHE method has the most accurate clustering results, and both SGA and KHE have the optimal performance for the best clustering results. For the worst performance, all the methods except FCM have the similar clustering results that are significantly better than pure FCM. For standard deviation (STD), KHE has the second performance that is only inferior to HS. From Table 3 and Figure 2, Figure 3 and Figure 4, it can be see that, the KHE method can solve the clustering problem better than other comparative methods in most cases.

It should be pointed out that, each run may generate completely different results. This is because the clustering results are dependent on the initial clustering centers.

Table 3. Optimization results for the fuzzy C-means (FCM) problem.

	ACO	FCM	GA	HS	KH	KHE	PSO	SGA
Mean	3.303556	3.368558	3.303527	3.303536	3.303624	3.303510	3.303542	3.303523
Best	3.303474	3.303478	3.303466	3.303468	3.303471	3.303462	3.303463	3.303462
Worst	3.303766	3.728121	3.303766	3.303766	3.303766	3.303766	3.303766	3.303766
Std	5.6032E−5	0.09555	5.9076E−5	4.0144E−5	1.1470E−4	4.6495E−5	5.0819E−5	5.1780E−5

Table 3. Optimization results for the fuzzy C-means (FCM) problem.

	ACO	FCM	GA	HS	KH	KHE	PSO	SGA
Mean	3.303556	3.368558	3.303527	3.303536	3.303624	3.303510	3.303542	3.303523
Best	3.303474	3.303478	3.303466	3.303468	3.303471	3.303462	3.303463	3.303462
Worst	3.303766	3.728121	3.303766	3.303766	3.303766	3.303766	3.303766	3.303766
Std	5.6032E−5	0.09555	5.9076E−5	4.0144E−5	1.1470E−4	4.6495E−5	5.0819E−5	5.1780E−5

Figure 2. Clustering results of FCM algorithm.

Figure 2. Clustering results of FCM algorithm.

Figure 3. Optimization process for clustering problem of the KHE method.

Figure 3. Optimization process for clustering problem of the KHE method.

Figure 4. Clustering results of the KHE method.

Figure 4. Clustering results of the KHE method.

5. Discussion and Conclusions

In many application fields, fuzzy clustering, especially fuzzy C-means (FCM) clustering, is one of the important hot research branches. FCM clustering algorithm is the most widely-used one among various clustering algorithms and has been used to successfully solve several application problems. However, the FCM algorithm is essentially a local search optimization algorithm. Herein, if its initial value is selected improperly, it will converge to a local minimum. Aiming at the disadvantages of the FCM algorithm, a new kind of swarm-based metaheuristic search, called KHE, is proposed to solve the clustering problem. Elitism strategy used in the KHE method can prevent the krill population from degrading. In KHE, the well-selected parameters are used instead of originating from nature. Furthermore, the KHE method is applied to solve the clustering problem for the purpose of escaping a local minimum. Moreover, with the aim of showing the performance of KHE method, it is compared with six other metaheuristic algorithms through seven complicated benchmark problems. The results show that the KHE method performs well on given benchmark problems and fuzzy clustering analyses.

Moreover, there are no additional operators added to the basic KH method. Therefore, the KHE method is simple and easy to implement.

Despite the above advantages of the KHE method, two prospective research points should be oriented as follows. On the one hand, in the current work, there is no study of computational requirements. The research of computational requirements should be made in future. On the other hand, only a few test problems and the clustering problem is solved by the KHE method in the present work. More problems should be used to test the KHE method from various aspects, and then it is used to solve more application problems, such as image segmentation, constrained optimization, knapsack problems, scheduling, dynamic optimization, antenna and microwave design problems, and water, geotechnical and transport engineering.