An Intelligent Technique for Initial Distribution of Genetic Algorithms

Abstract

The need to find the global minimum in multivariable functions is a critical problem in many fields of science and technology. Effectively solving this problem requires the creation of initial solution estimates, which are subsequently used by the optimization algorithm to search for the best solution in the solution space. In the context of this article, a novel approach to generating the initial solution distribution is presented, which is applied to a genetic optimization algorithm. Using the k-means clustering algorithm, a distribution based on data similarity is created. This helps in generating initial estimates that may be more tailored to the problem. Additionally, the proposed method employs a rejection sampling algorithm to discard samples that do not yield better solution estimates in the optimization process. This allows the algorithm to focus on potentially optimal solutions, thus improving its performance. Finally, the article presents experimental results from the application of this approach to various optimization problems, providing the scientific community with a new method for addressing this significant problem.

1. Introduction

The task of locating the global minimum of a function f can be defined as:

$$x^{*}=\arg \underset{x\in S}{min}f\left(x\right)$$

(1)

with S:

$$S=\left[a_1,b_1\right]\times \left[a_2,b_2\right]\times \dots \left[a_n,b_n\right]$$

This task finds application in a variety of real-world problems, such as problems from physics [1,2,3], chemistry [4,5,6], economics [7,8], medicine [9,10], etc. The methods aimed at finding the global minimum are divided into two major categories: deterministic methods and stochastic methods. The most-frequently encountered techniques of the first category are interval techniques [11,12], which partition the initial domain of the objective function until a promising subset is found to find the global minimum. The second category includes the vast majority of methods, and in its ranks, one can find methods such as controlled random search methods [13,14,15], simulated annealing methods [16,17,18], differential evolution methods [19,20], particle swarm optimization (PSO) methods [21,22,23], ant colony optimization methods [24,25], etc. Furthermore, a variety of hybrid techniques have been proposed, such as hybrid Multistart methods [26,27], hybrid PSO techniques [28,29,30], etc. Also, many parallel optimization methods [31,32] have appeared during the past few years or methods that take advantage of the modern graphics processing units (GPUs) [33,34].

One of the basic techniques included in the area of stochastic techniques is genetic algorithms, initially proposed by John Holland [35]. The operation of genetic algorithms is inspired by biology, and for this reason, they utilize the idea of evolution through genetic mutation, natural selection, and crossover [36,37,38].

Genetic algorithms can be combined with machine learning to solve complex problems and optimize models. More specifically, the genetic algorithm has been applied in many machine learning applications, such as in the article by Ansari et al., which deals with the recognition of digital modulation signals. In this article, the genetic algorithm is used to optimize machine learning models by adjusting their features and parameters to achieve better signal recognition accuracy [39]. Additionally, in the study by Ji et al., a methodology is proposed that uses machine learning models to predict amplitude deviation in hot rolling, while genetic algorithms are employed to optimize the machine learning models and select features to improve prediction accuracy [40]. Furthermore, in the article by Santana, Alonso, and Nieto, which focuses on the design and optimization of 5G networks in indoor environments, the use of genetic algorithms and machine learning models is identified for estimating path loss, which is critical for determining signal strength and coverage indoors [41].

Another interesting article is by Liu et al., which discuss the use of genetic algorithms in robotics [42]. The authors propose a methodology that utilizes genetic algorithms to optimize the trajectory and motion of digital twin robots. A similar study was presented by Nonoyama et al. [43], where the research focused on optimizing energy consumption during the motion planning of a dual-arm industrial robot. The goal of the research is to minimize energy consumption during the process of object retrieval and placement. To achieve this, both genetic algorithms and particle swarm optimization algorithms are used to adjust the robot’s motion trajectory, thereby increasing its energy efficiency.

The use of genetic algorithms is still prevalent even in the business world. In the article by Liu et al. [44], the application of genetic algorithms in an effort to optimize energy conservation in a high-speed methanol spark ignition engine fueled with methanol and gasoline blends is discussed. In this study, genetic algorithms are used as an optimization technique to find the best operating conditions for the engine, such as the air–fuel ratio, ignition timing, and other engine control variables, aiming to save energy and reduce energy consumption and emissions. In another research, the optimization of the placement of electric vehicle charging stations is carried out [45]. Furthermore, in the study by Chen and Hu [46], the design of an intelligent system for agricultural greenhouses using genetic algorithms is presented to provide multiple energy sources. Similarly, in the research by Min, Song, Chen, Wang, and Zhang [47], an optimized energy-management strategy for hybrid electric vehicles is introduced using a genetic algorithm based on fuel cells in a neural network under startup conditions.

Moreover, genetic algorithms are extremely useful in the field of medicine, as they are employed in therapy optimization, medical personnel training, genetic diagnosis, and genomic research. More specifically, in the study by Doewes, Nair, and Sharma [48], data from blood analyses and other biological samples are used to extract characteristics related to the presence of the SARS-CoV-2 virus that causes COVID-19. In this article, genetic algorithms are used for data analysis and processing to extract significant characteristics that can aid in the effective diagnosis of COVID-19. Additionally, there are studies that present the design of dental implants for patients using artificial neural networks and genetic algorithms [49,50]. Lastly, the contribution of genetic algorithms is significant in both implant techniques [51,52] and surgeries [53,54].

The current work aims to improve the efficiency of the genetic algorithm in global optimization problems, by introducing a new way of initializing the population’s chromosomes. In the new initialization technique, the k-means [55] method is used to find initial values of the chromosomes that will lead to finding the global minimum faster and more efficient than chromosomes generated by some random distribution. Also, the proposed technique discards chromosomes, which, after applying the k-means technique, are close to each other.

During the past few years, many researchers have proposed variations for the initialization of genetic algorithms, such as the work of Maaranen et al. [56], where they discuss the usage of quasi-random sequences in the initial population of a genetic algorithm. Similarly, Paul et al. [57] propose initializing the population of genetic algorithms using a vari-begin and vari-diversity (VV) population seeding technique. Also, in the same direction of research, Li et al. propose [58] a knowledge-based technique to initialize genetic algorithms used mainly in discrete problems. Recently, Hassanat et al. [59] suggested the incorporation of regression techniques for the initialization of genetic algorithms.

The rest of this article is organized as follows: in Section 2, the proposed method is discussed in detail; in Section 3, the test functions used as well the experimental results are fully outlined, and finally, in Section 4, some conclusions and future guidelines are listed.

2. The Proposed Method

The fundamental operation of a genetic algorithm mimics the process of natural evolution. The algorithm begins by creating an initial population of solutions, called chromosomes, which represents a potential solution to the objective problem. The genetic algorithm operates by reproducing and evolving populations of solutions through iterative steps. Following the analogy to natural evolution, the genetic algorithm allows optimal solutions to “evolve” through successive generations. The main steps of the used genetic algorithm are described below:

• Initialization step:

  (a)

  Set $N_c$ as the number of chromosomes.

  (b)

  Set $N_g$ as the maximum number of allowed generations.

  (c)

  Initialize randomly the $N_c$ chromosomes in S. In most implementations of genetic algorithms, the chromosomes will be selected using some random number distribution. In the present work, the chromosomes will be selected using the sampling technique described in Section 2.3.

  (d)

  Set $p_s$ as the selection rate of the algorithm, with $p_s\le 1$.

  (e)

  Set $p_m$ as the mutation rate, with $p_m\le 1$.

  (f)

  Set iter = 0.

• For every chromosome $g_i,i=1,\dots ,N_c$: Calculate the fitness $f_i=f\left(g_i\right)$ of chromosome $g_i$.
• Genetic operations step:

  (a)

  Selection procedure: The chromosomes are sorted according to their fitness values. Denote $N_b$ as the integer part of $\left(1-p_s\right)\times N_c$; chromosomes with the lowest fitness values are transferred intact to the next generation. The remaining chromosomes are substituted by offspring created in the crossover procedure. During the selection process, for each offspring, two parents are selected from the population using tournament selection.

  (b)

  Crossover procedure: For every pair $(z,w)$ of selected parents, two additional chromosomes $\tilde{z}$ and $\tilde{w}$ are produced using the following equations:

  $$\begin{array}{ccc}\hfill \widetilde{z_i}& =& a_i{z}_i+\left(1-a_i\right)w_i\hfill \\ \hfill \widetilde{w_i}& =& a_i{w}_i+\left(1-a_i\right)z_i\hfill \end{array}$$

  (2)

  where $i=1,\dots ,n$. The values $a_i$ are uniformly distributed random numbers, with $a_i\in [-0.5,1.5]$ [60].

  (c)

  Replacement procedure:

  i.

  For $i=N_b+1$ to $N_c$, do:

  • Replace $g_i$ using the next offspring created in the crossover procedure.

  ii.

  EndFor:

  (d)

  Mutation procedure:

  i.

  For every chromosome $g_i,i=1,\dots ,N_c$, do:

  • For each element $j=1,\dots ,n$ of $g_i$, a uniformly distributed random number $r\in \left[0,1\right]$ is drawn. The element is altered randomly if $r\le p_m$.

  ii.

  EndFor

• Termination check step:

  (a)

  Set $iter=iter+1$.

  (b)

  If $iter\ge N_g$ or the proposed stopping rule of Tsoulos [61] holds, then goto the local search step, else goto Step 2.

• Local search step: Apply a local search procedure to the chromosome of the population with the lowest fitness value, and report the obtained minimum. In the current work, the BFGS variant of Powell [62] was used as a local search procedure.

The current work proposes a novel method to initiate the chromosomes that utilizes the well-known technique of k-means. The significance of the initial distribution in the solution finding within optimization is essential across various domains and techniques. Apart from genetic algorithms, the initial distribution impacts other optimization methods like particle swarm optimization (PSO) [21], evolution strategies [63], and neural networks [64]. The initial distribution defines the starting solutions that will evolve and improve throughout the algorithm. If the initial population contains solutions close to the optimum, it increases the likelihood of evolved solutions being in proximity to the optimal solution. Conversely, if the initial population is distant from the optimum, the algorithm might need more iterations to reach the optimal solution or even get stuck in a suboptimal solution. In conclusion, the initial distribution influences the stability, convergence speed, and quality of optimization algorithm outcomes. Thus, selecting a suitable initial distribution is crucial for the algorithm’s efficiency and the discovery of the optimal solution in a reasonable time [65,66].

2.1. Proposed Initialization Distribution

The present work replaces the randomness of the initialization of the chromosomes by using the k-means technique. More specifically, the method takes a series of samples from the objective function, and then, the k-means method is used to locate the centers of these points. These centers can then be used as chromosomes in the genetic algorithm.

The k-means algorithm emerged in 1957 by Stuart Lloyd in the form of Lloyd’s algorithm [67], although the concept of clustering based on distance had been introduced earlier. The name “k-means” was introduced around 1967 by James MacQueen [68]. The k-means algorithm is a clustering algorithm widely used in data analysis and machine learning. Its primary objective is to partition a dataset into k clusters, where data points within the same cluster are similar to each other and differ from data points in other clusters. Specifically, k-means seeks cluster centers and assigns samples to each cluster, aiming to minimize the distance within clusters and maximize the distance between cluster centers [69]. The algorithm steps are presented in Algorithm 1.

The algorithm terminates when there is no change in cluster centers between consecutive iterations, implying that the clusters have stabilized in their final form [70,71].

2.2. Chromosome Rejection Rule

An additional technique for discarding chromosomes where they are similar or close to each other is listed and applied below. Specifically, each chromosome is extensively compared to all the other chromosomes, and those that have a very small or negligible Euclidean distance between them are sought, implying their similarity. Subsequently, the algorithm incorporates these chromosomes into the final initial distribution table, while chromosomes that are not similar are discarded.

2.3. The Proposed Sampling Procedure

The proposed sampling procedure has the following major steps:

• Take $N_m$ random samples from the objective function using a uniform distribution.
• Calculate the k centers of the $N_m$ points using the k-means algorithm provided in Algorithm 1.
• Remove from the set of centers C points that are close to each other.
• Return the set of centers C as the set of chromosomes.

Algorithm 1 The k-means algorithm.

Set the number of clusters k. The input of the algorithm is the $N_m$ initial points $x_i,i=1,\dots ,N_m$. For the current algorithm, the points $x_i$ are randomly selected samples in S. For every point $x_i,i=1,\dots ,N_m$, do assign randomly the point $x_i$ in a cluster $S_j$. For every center $c_j,j=1,\dots ,k$, do: (a)   Set $M_j$ as the number of points in $S_j$. (b)   Compute $c_j$ as $$c_j=\frac{1}{M_j}\sum _{x_i\in S_j}{x}_i.$$ EndFor. Repeat. (a)   Set $S_j=\left\{\right\},j=1,\dots ,k$. (b)   For every point $x_i,i=1,\dots ,N_m$, do:   i.  Set $j^{*}={\mathrm{argmin}}_{m=1}^k\left\{D\left(x_i,c_m\right)\right\}$, where $D(x,y)$ is the Euclidean distance of $(x,y)$.     ii.  Set $S_{j^{*}}=S_{j^{*}}\cup \left\{x_i\right\}$. (c)   EndFor: (d)   For every center $c_j,j=1,\dots ,k$, do:   i.  Set $M_j$ as the number of points in $S_j$     ii.  Compute $c_j$ as $$c_j=\frac{1}{M_j}\sum _{x_i\in S_j}{x}_i.$$ (e) EndFor: Stop the algorithm, if there is no change in centers $c_j$.

3. Experiments

In the following, the benchmark functions used in the experiments, as well as the experimental results are presented. The test functions used here were proposed in a variety of research papers [72,73].

3.1. Test Functions

The definitions of the test functions used are given below:

• Bohachevsky 1 (Bf1) function:

  $$f\left(x\right)=x_1^2+2x_2^2-\frac{3}{10}cos\left(3\pi x_1\right)-\frac{4}{10}cos\left(4\pi x_2\right)+\frac{7}{10}$$

  with $x\in {[-100,100]}^2$.
• Bohachevsky 2 (Bf2) function:

  $$f\left(x\right)=x_1^2+2x_2^2-\frac{3}{10}cos\left(3\pi x_1\right)cos\left(4\pi x_2\right)+\frac{3}{10}$$

  with $x\in {[-50,50]}^2$.
• Branin function: $f\left(x\right)={\left(x_2-\frac{5.1}{4{\pi }^2}{x}_1^2+\frac{5}{\pi }{x}_1-6\right)}^2+10\left(1-\frac{1}{8\pi }\right)cos\left(x_1\right)+10$ with $-5\le x_1\le 10,0\le x_2\le 15$.
• CM function:

  $$f\left(x\right)=\sum _{i=1}^n{x}_i^2-\frac{1}{10}\sum _{i=1}^{n}cos\left(5\pi x_i\right)$$

  where $x\in {[-1,1]}^n$. In the experiments conducted, the value $n=4$ was used.
• Camel function:

  $$f\left(x\right)=4x_1^2-2.1x_1^4+\frac{1}{3}{x}_1^6+x_1{x}_2-4x_2^2+4x_2^4,x\in {[-5,5]}^2$$
• Easom function:

  $$f\left(x\right)=-cos\left(x_1\right)cos\left(x_2\right)exp\left({\left(x_2-\pi \right)}^2-{\left(x_1-\pi \right)}^2\right)$$

  with $x\in {[-100,100]}^2.$
• Exponential function, defined as:

  $$f\left(x\right)=-exp\left(-0.5\sum _{i=1}^n{x}_i^2\right),-1\le x_i\le 1$$
  The values $n=4,8,16,32$ were used in the executed experiments.
• Griewank2 function:

  $$f\left(x\right)=1+\frac{1}{200}\sum _{i=1}^2{x}_i^2-\prod _{i=1}^2\frac{cos\left(x_i\right)}{\sqrt{\left(i\right)}},x\in {[-100,100]}^2$$
• Griewank10 function: The function is given by the equation:

  $$f\left(x\right)=\sum _{i=1}^n\frac{x_i^2}{4000}-\prod _{i=1}^{n}cos\left(\frac{x_i}{\sqrt{i}}\right)+1$$

  with $n=10$.
• Gkls function: $f\left(x\right)=Gkls(x,n,w)$ is a function with w local minima, described in [74] with $x\in {[-1,1]}^n$, and n is a positive integer between 2 and 100. The values $n=2,3$ and $w=50$ were used in the experiments conducted.
• Goldstein and Price function:

  $$\begin{array}{ccc}\hfill f\left(x\right)& =& \left[1+{\left(x_1+x_2+1\right)}^2\right.\hfill \\ & & \left(19-14x_1+3x_1^2-14x_2+6x_1{x}_2+3x_2^2\right)]\times \hfill \\ & & [30+{\left(2x_1-3x_2\right)}^2\hfill \\ & & \left(18-32x_1+12x_1^2+48x_2-36x_1{x}_2+27x_2^2\right)]\hfill \end{array}$$

  with $x\in {[-2,2]}^2$.
• Hansen function: $f\left(x\right)={\sum }_{i=1}^{5}icos\left[(i-1)x_1+i\right]{\sum }_{j=1}^{5}jcos\left[(j+1)x_2+j\right]$, $x\in {[-10,10]}^2$.
• Hartman 3 function:

  $$f\left(x\right)=-\sum _{i=1}^4{c}_{i}exp\left(-\sum _{j=1}^3{a}_{ij}{\left(x_j-p_{ij}\right)}^2\right)$$

  with $x\in {[0,1]}^3$ and $a=\left(\begin{array}{ccc}3& 10& 30\\ 0.1& 10& 35\\ 3& 10& 30\\ 0.1& 10& 35\end{array}\right),c=\left(\begin{array}{c}1\\ 1.2\\ 3\\ 3.2\end{array}\right)$ and

  $$p=\left(\begin{array}{ccc}0.3689& 0.117& 0.2673\\ 0.4699& 0.4387& 0.747\\ 0.1091& 0.8732& 0.5547\\ 0.03815& 0.5743& 0.8828\end{array}\right)$$
• Hartman 6 function:

  $$f\left(x\right)=-\sum _{i=1}^4{c}_{i}exp\left(-\sum _{j=1}^6{a}_{ij}{\left(x_j-p_{ij}\right)}^2\right)$$

  with $x\in {[0,1]}^6$ and $a=\left(\begin{array}{cccccc}10& 3& 17& 3.5& 1.7& 8\\ 0.05& 10& 17& 0.1& 8& 14\\ 3& 3.5& 1.7& 10& 17& 8\\ 17& 8& 0.05& 10& 0.1& 14\end{array}\right),c=\left(\begin{array}{c}1\\ 1.2\\ 3\\ 3.2\end{array}\right)$ and

  $$p=\left(\begin{array}{cccccc}0.1312& 0.1696& 0.5569& 0.0124& 0.8283& 0.5886\\ 0.2329& 0.4135& 0.8307& 0.3736& 0.1004& 0.9991\\ 0.2348& 0.1451& 0.3522& 0.2883& 0.3047& 0.6650\\ 0.4047& 0.8828& 0.8732& 0.5743& 0.1091& 0.0381\end{array}\right)$$
• Potential function: The molecular conformation corresponding to the global minimum of the energy of N atoms interacting via the Lennard–Jones potential [75] was used as a test function here, and it is defined by:

  $$V_{LJ}\left(r\right)=4ϵ\left[{\left(\frac{\sigma }{r}\right)}^{12}-{\left(\frac{\sigma }{r}\right)}^6\right]$$
  The values $N=3,5$ were used in the experiments conducted. Also, for the experiments conducted, the values $ϵ=1,\sigma =$ 1 were used.
• Rastrigin function:

  $$f\left(x\right)=x_1^2+x_2^2-cos\left(18x_1\right)-cos\left(18x_2\right),x\in {[-1,1]}^2$$
• Rosenbrock function:

  $$f\left(x\right)=\sum _{i=1}^{n-1}\left(100{\left(x_{i+1}-x_i^2\right)}^2+{\left(x_i-1\right)}^2\right),-30\le x_i\le 30.$$
  The values $n=4,8,16$ were used in the experiments conducted.
• Shekel 5 function:

  $$f\left(x\right)=-\sum _{i=1}^5\frac{1}{(x-a_i){(x-a_i)}^T+c_i}$$

  with $x\in {[0,10]}^4$ and $a=\left(\begin{array}{cccc}4& 4& 4& 4\\ 1& 1& 1& 1\\ 8& 8& 8& 8\\ 6& 6& 6& 6\\ 3& 7& 3& 7\end{array}\right),c=\left(\begin{array}{c}0.1\\ 0.2\\ 0.2\\ 0.4\\ 0.4\end{array}\right)$

• Shekel 7 function:

  $$f\left(x\right)=-\sum _{i=1}^7\frac{1}{(x-a_i){(x-a_i)}^T+c_i}$$

  with $x\in {[0,10]}^4$ and $a=\left(\begin{array}{cccc}4& 4& 4& 4\\ 1& 1& 1& 1\\ 8& 8& 8& 8\\ 6& 6& 6& 6\\ 3& 7& 3& 7\\ 2& 9& 2& 9\\ 5& 3& 5& 3\end{array}\right),c=\left(\begin{array}{c}0.1\\ 0.2\\ 0.2\\ 0.4\\ 0.4\\ 0.6\\ 0.3\end{array}\right)$.

• Shekel 10 function:

  $$f\left(x\right)=-\sum _{i=1}^{10}\frac{1}{(x-a_i){(x-a_i)}^T+c_i}$$

  with $x\in {[0,10]}^4$ and $a=\left(\begin{array}{cccc}4& 4& 4& 4\\ 1& 1& 1& 1\\ 8& 8& 8& 8\\ 6& 6& 6& 6\\ 3& 7& 3& 7\\ 2& 9& 2& 9\\ 5& 5& 3& 3\\ 8& 1& 8& 1\\ 6& 2& 6& 2\\ 7& 3.6& 7& 3.6\end{array}\right),c=\left(\begin{array}{c}0.1\\ 0.2\\ 0.2\\ 0.4\\ 0.4\\ 0.6\\ 0.3\\ 0.7\\ 0.5\\ 0.6\end{array}\right)$.

• Sinusoidal function:

  $$f\left(x\right)=-\left(2.5\prod _{i=1}^{n}sin\left(x_i-z\right)+\prod _{i=1}^{n}sin\left(5\left(x_i-z\right)\right)\right),0\le x_i\le \pi .$$
  The values of $n=4,8,16$ and $z=\frac{\pi }{6}$ were used in the experiments conducted.
• Test2N function:

  $$f\left(x\right)=\frac{1}{2}\sum _{i=1}^n{x}_i^4-16x_i^2+5x_i,x_i\in [-5,5].$$
  The function has $2^n$ in the specified range, and in our experiments, we used $n=4,5,6,7$.
• Test30N function:

  $$f\left(x\right)=\frac{1}{10}{sin}^2\left(3\pi x_1\right)\sum _{i=2}^{n-1}\left({\left(x_i-1\right)}^2\left(1+{sin}^2\left(3\pi x_{i+1}\right)\right)\right)+{\left(x_n-1\right)}^2\left(1+{sin}^2\left(2\pi x_n\right)\right)$$

  with $x\in [-10,10]$, with ${30}^n$ the local minima in the search space. For our experiments, we used $n=3,4$.

3.2. Experimental Results

The freely available software OPTIMUS was utilized for the experiments, available at the following address: https://github.com/itsoulos/OPTIMUS (accessed on 9 September 2023). The genetic algorithm variant of the OPTIMUS package used in the experiments conducted was the pDoubleGenetic algorithm, which can utilize different methods for the initialization of the chromosomes. The machine used in the experiments was an AMD Ryzen 5950X with 128 GB of RAM, running the Debian Linux operating system. To ensure research reliability, the experiments were executed 30 times for each objective function, employing different seeds for the random generator and reporting the mean values. The values used for the parameters in the experiments are listed in Table 1. The values in the experimental tables denote the average number of function calls. For the experimental tables, the following notation is used:

• The column UNIFORM indicates the incorporation of uniform sampling in the genetic algorithm. In this case, $N_c$ randomly selected chromosomes using uniform sampling were used in the genetic algorithm.
• The column TRIANGULAR defines the usage of the triangular distribution [76] for the initial samples of the genetic algorithm. For this case, $N_c$ randomly selected chromosomes with a triangular distribution were used in the genetic algorithm.
• The column KMEANS denotes the application of k-means sampling as proposed here in the genetic algorithm. In this case, $N_m$ randomly selected points were sampled from the objective function and k centers were produced using the k-means algorithm. In order to have a fair comparison between the results produced between the proposed technique and the rest, the number of centers produced by the k-means method was set to be equal to the number of chromosomes $N_c$ of the rest of the techniques. Ten-times the number of initial points were used to produce the centers. In addition, through the discard process of Algorithm 2, some centers were eliminated.
• The numbers in the cells represent the average number of function calls required to obtain the global minimum. The fraction in parentheses denotes the percentage where the global minimum was successfully discovered. If this fraction is absent, then the global minimum was successfully discovered in all runs.
• In every table, an additional line was added under the name TOTAL, representing the total number of function calls and, in parentheses, the average success rate in finding the global minimum.

Algorithm 2 Chromosome rejection rule.

Set C the set of centers, $C=\left\{c_i,i=1,\dots ,k\right\}$. Set $ϵ>0$ a small positive number. For every center $c_i$, do: (a)   For every center $c_j,j=1,\dots ,i-1$, do:   i.  If $∥c_i-c_j∥\le ϵ$, then remove $c_i$ from C. (b)   EndFor: EndFor: Return the final set of centers C.

Table 1. The values for the parameters used in the experiments.

Parameter	Meaning	Value
$N_c$	Number of chromosomes	200
$N_m$	Initial samples for k-means	2000
k	Number of centers in k-means	200
$N_g$	Maximum number of allowed generations	200
$p_s$	Selection rate	0.9
$p_m$	Mutation rate	0.05
$ϵ$	Small value used in comparisons	${10}^{-6}$

Table 1. The values for the parameters used in the experiments.

Parameter	Meaning	Value
$N_c$	Number of chromosomes	200
$N_m$	Initial samples for k-means	2000
k	Number of centers in k-means	200
$N_g$	Maximum number of allowed generations	200
$p_s$	Selection rate	0.9
$p_m$	Mutation rate	0.05
$ϵ$	Small value used in comparisons	${10}^{-6}$

Table 2. Comparison of function calls and success rates with different distributions. The fractions in parentheses indicate percentage of runs where the global optimum was successfully discovered. When this fraction is absent, it is an indication that the global minimum was discovered in every execution (100% success).

Problem	Uniform	Triangular	Kmeans
BF1	5731	5934	4478
BF2	5648 (0.97)	5893	4512
BRANIN	4680	4835	4627
CM4	5801	5985	4431
CAMEL	4965	5099	4824
EASOM	5657	7089	4303
EXP4	4934	4958	4539
EXP8	5021	5187	4689
EXP16	5063	5246	4874
EXP32	5044	5244	5016
GKLS250	4518	4710	4525
GKLS350	4650	4833	4637
GOLDSTEIN	8099	8537	7906
GRIEWANK2	5500 (0.97)	5699 (0.97)	4324
GRIEWANK10	6388 (0.70)	7482 (0.63)	4559
HANSEN	5681 (0.93)	6329	6357
HARTMAN3	4950	5157	4998
HARTMAN6	5288	5486	5258
POTENTIAL3	5587	5806	5604
POTENTIAL5	7335	7824	7450
RASTRIGIN	5703	5848	4481
ROSENBROCK4	4241	4441	4241
ROSENBROCK8	41,802	41,965	4523
ROSENBROCK16	42,196	42,431	4962
SHEKEL5	5488 (0.97)	5193 (0.97)	5232 (0.97)
SHEKEL7	5384	5711 (0.97)	5695 (0.97)
SHEKEL10	6360	5989	6396
TEST2N4	5000	5179	5047
TEST2N5	5306	5309	5039
TEST2N6	5245	5492	5107
TEST2N7	5282 (0.93)	5583	5216
SINU4	4844	5046	4899
SINU8	5368	5503	5509
SINU16	6919	5583	5977
TEST30N3	7215	8115	5270
TEST30N4	7073	7455	6712
Total	273,966 (0.98)	282,176 (0.985)	186,217 (0.998)

presents the three different distributions for the initialization of the chromosomes, along with the objective function evaluations. It is evident that, with the proposed initialization, the evaluations are fewer compared to the other two initialization methods. Specifically, compared to the uniform initialization, there was a reduction of 47.88%, while in comparison to the triangular initialization, the reduction was 50.25%. As for the success rates, no significant differences were observed, and this is graphically outlined in Figure 1.

An additional set of experiments was performed to verify the reliability of the proposed technique with high-dimensional objective functions. The following functions were used:

• High conditioned elliptic function, defined as

  $$f\left(x\right)=\sum _{i=1}^n{\left({10}^6\right)}^{\frac{i-1}{n-1}}{x}_i^2$$
• CM function, defined as

  $$f\left(x\right)=\sum _{i=1}^n{x}_i^2-\frac{1}{10}\sum _{i=1}^{n}cos\left(5\pi x_i\right)$$

These were used as test cases in this series of experiments. For the first function, the dimension values $n=1,\dots ,20$ were used, and the comparative results are outlined in

Table 3. Objective function ELP. Comparison of function calls with different distributions and dimensions.

Dimension	Calls (200 Uniform Samples)	Calls (200 k-Means Centers)
5	15,637	4332
10	24,690	4486
15	39,791	4743
20	42,976	5194
25	43,617	7152
30	44,502	6914
35	45,252	15,065
40	46,567	13,952
45	47,640	15,193
50	49,393	22,535
55	50,062	23,692
60	52,293	25,570
65	52,546	25,678
70	53,346	28,153
75	54,110	28,328
80	57,209	29,320
85	60,970	29,371
90	65,319	32,121
95	68,097	35,721
100	66,803	35,396
Total	980,820	392,916

and graphically in Figure 2. It is evident that, with the proposed initialization, the results improved compared to those of the uniform distribution. Additionally, as expected, the required function evaluations increased in parallel with the dimension of the problem.

Likewise, a series of experiments was conducted for the CM function with the dimension n increased from 2 to 30, and the results are shown in

Table 4. Objective function CM. Comparison of function calls and success rates using different distributions.The fractions in parentheses indicate percentage of runs where the global optimum was successfully discovered. When this fraction is absent, it is an indication that the global minimum was discovered in every execution (100% success).

Dimension	Calls (200 Uniform Samples)	Calls (200 k-Means Centers)
2	5665	4718
4	6212	4431
6	7980	4390
8	9917	4449
10	12,076 (0.97)	4481
12	14,672	4565
14	18,708 (0.87)	4685
16	23,251 (0.77)	4687
18	24,624 (0.77)	4766
20	30,153 (0.80)	4848
22	35,851 (0.77)	15,246 (0.97)
24	43,677 (0.93)	7865 (0.93)
26	41,492 (0.77)	5627
28	38,017 (0.73)	10,566 (0.97)
30	47,538 (0.83)	24,803 (0.90)
Total	359,833 (0.84)	110,127 (0.98)

and graphically in Figure 3. The proposed initialization method requires fewer function calls to obtain the global minimum of the function, and also, the average success rate with the proposed initialization method reached 100%, whereas with the uniform distribution, it was smaller by 15%.

4. Conclusions

In this work, an innovative chromosome initialization method for genetic algorithms was proposed that utilizes the well-known k-means technique. These genetic algorithms are used to find the global minimum of multidimensional functions. This method replaces the initialization of chromosomes in genetic algorithms, which is traditionally performed by some random distribution, with centers produced by the k-means technique. In addition, in this technique, centers that are close enough are rejected from being genetic algorithm chromosomes. The above procedure significantly reduced the required number of function calls compared to random distributions, and furthermore, in difficult high-dimensional functions, it appears to be a more-efficient technique at finding the global minimum than random distributions. Future research may include the incorporation of parallel techniques such as MPI [77] or OpenMP [78] to speed up the method or application of the initialization process to other stochastic techniques such as particle swarm optimization or differential evolution.