A new natural-inspired continuous optimization approach

1. Introduction

During the optimization, an objective function is to be minimized or maximized. Optimization can be considered as a black-box that takes a problem (an objective function) as input and gives an optimized solution as output. It can be viewed as a mathematical tool or as a meta heuristic tool. A natural phenomenon can be also motivation of an optimization algorithm. Optimization irrespective of its mechanism concerns with finding the solution among a huge number of potential solutions which has the best objective function value [1]. In optimization, finding the best solution to a problem is the target. The term of “the best” implicitly suggests that there is more than one solution to a given problem, which of course those different potential solutions don’t have the identical values. The definition of the best solution depends on the discussed problem as well as the admissible error rate. So, the way that the problem is formulated, also has a direct effect on the quality of the best solution. Some problems have a clear solution; such as the best player of a sport branch, the longest day of the year and solution of an ordinary first grade differential equation. These are the examples that can be named as easy problems. In contrast, some problems have the various maximum or minimum solutions known as the optimal or extreme points and therefore the best solution is a relative concept there. The best work of art, the most beautiful landscape and the most dulcet track of music are among examples that can be said for these problems [2–4]. The inputs in the optimization process are the variables of the evaluated function which is also called the objective function, the cost function or the fitness function. In this paper, according to many articles related to the subject, all the optimization problems are considered as minimization of a cost function [5]. It is easy to show that any optimization problem can be redefined as a minimization problem. The SSPCO algorithm is a population based algorithm which has been introduced first in 2015, by inspiring of the behavior of partridge chicks.

Chaos is a fundamental concept in the science describing exactly many natural phenomena which resemble random at first glance. Chaotic behaviors are apparently random-like and disordered behaviors, which occurs in many phenomena of the real world. Known phenomena such as the butterfly effect are among the special features of chaos theory. In this paper, we use this theory during implementing the population of the proposed algorithm. In section 2, we state the related optimization algorithms; we explain chaos theory in section 3. In section 4, we present the proposed algorithm. In section 5, we discuss on the simulation and results and at last, in section 6, we conclude the paper.

2. Related work

Genetic Algorithm (GA) is a random evolutionary optimization algorithm with a potential of the general search, which has been introduced by Holland in 1975. GA is among the most successful evolutionary algorithms inspired by the natural evolution (the natural evolutionary). However, due to its outstanding performance in optimization, it has been widely considered as a function optimizer. The algorithm begins with initializing the population of the solutions (or chromosomes). A usual chromosome is a bit vector. Then, the fitness of each chromosome is evaluated using a fitness function of the problem. The best chromosomes go to a mating pool, where they undergo crossover and mutation, and therefore a new set of solutions is obtained. Simulated annealing algorithm or in other words the heating/cooling algorithm has been first introduced by Kirkpatrick et al. in the early 1980’s [6–8]. This method, i.e. the simulating process of cooling metals, simulates the materials cooling. During the simulating process of cooling metals, the material is heated to a temperature higher than its melting temperature and then gradually, the temperature is lowered. The temperature reduction is very slow and to extent that the material remains in thermodynamic equilibrium. In other words, the body temperature remains constant to the extent that the best crystal structure with the least energy is composed at that temperature. Bodies that their crystal structure have been formed at higher energies, are more fragile. On the contrary, if the crystal structure of the body has been formed at lower energy, it may have far more physical resistance.

Water Cycle Algorithm (WCA) [44] has been proposed inspired by water cycle and its extended version, Gradient-based Water Cycle Algorithm (GWCA) [45] considering evaporation rate, then recently has been proposed. Harmony Search has been one of the most interesting optimizers among many researchers due to its simplicity [46]. A special discrete type of HS, fuzzy discrete harmony search (FDHS), has been recently introduced [47]. Ant colony optimization algorithm, or briefly ant algorithm, is inspired by the natural behavior of the ants living together in large collections. Other algorithms which have been also created based on the ant algorithm, all are multi-agent systems and agents are artificial ants that act like real ants [9], [10]. The ant algorithm is a clear example of the swarm intelligence, in which the agents don’t have very high capability, but through collaboration with and next to each other, they can achieve the excellent results. This algorithm is used for surveying and solving a wide range of optimization problems. The simplified ant algorithm has a few limitations, due to high amount of its simplicity. In this section, the ant algorithm has been fully introduced which in addition to having the basic properties of the simplified algorithm, has been optimized to deal with the more complex problems and it overcomes the limitations of its simplified algorithm. For example, the pheromone that is casted on edges by any ant, is proportional to the quality of the solution that the ant has found. So, the information created by pheromones is far more efficient and has the better effect in guiding the ants into the right directions. On the other hand, the simple ant algorithm is not appropriate for dealing with the larger and more complex problems and just is usable to find the shortest path between two vertexes of a graph. But it is not suitable for finding the shortest Hamiltonian path in a graph. Therefore, to solve this problem, ants must also have a kind of memory [11, 12]. The ant colony system (ACS) algorithm has been designed in 1997 by Dorigo and Gambardla to optimize the performance of ant algorithm to solve the more complicated problems with higher dimensions. This algorithm has been created by creating some changes in the basic ant algorithm [13, 14]. James Kennedy, a social psychologist, and Russel Eberhart, an electrical engineer, are the original owners of the Particle Swarm Optimization (PSO) algorithm. At first, they intended to create a kind of computational intelligence with the utilization of social models and available social relations that doesn’t need to the special personal abilities. Their first simulation that was done in 1995 [15–17], and it led them to simulate the behavior of the birds to find seeds. That was a method in the evolutionary computation area, which deals with finding the optimal solutions of different optimization problems. This algorithm offers an algorithm for solving the mathematical optimization problems through mathematical modelling of the socio-political evolution process [18]. Functionally, this algorithm is included in the category of evolutionary optimization algorithms such as genetic algorithm, particle swarm optimization algorithm, ant colony algorithm, simulated annealing algorithm and etc. A Fractional Particle Swarm Optimization-based Memetic Algorithm (FPSOMA), as a special PSO, has been recently introduced [48]. Like all algorithms in this category, Imperialist Competitive Algorithm (ICA) also produces an initial set of potential solutions. Each initial solution is known as a country. Imperialist competitive algorithm gradually improves the initial solutions (i.e. the countries) with a special process that mimics the social behaviors of the colonies and the imperialists.

3. Chaos theory

The one, who identified a chaotic phenomenon for the first time in history and partly explained about it, was a mathematician named Henry Poincare. He faced with the phenomenon during the solving of three bodies’ problem in 1880 [19, 20]. Three bodies’ problem is associated to three planets in space which are moving with their mutual gravity. He realized that the problem is in some way unsolvable. The reason for this was that a small difference in the starting point or the initial speed made a huge difference in the continuation of the process. He realized that it is possible to find the circuits that are not alternative and neither are increasing and nor tending to a fixed point. Jacques Hadamard, in 1989, when working on a system based on glide on the surface without fiction and constant bending, realized that this system is very sensitive to the initial condition [21] and are dynamic and stochastic systems [22–24]. After that, some of the other scientists like George David Birkhoff, Littlewood and Mary Lucy Cartwright also addressed the issues of nonlinear dynamical systems.

After 1950, chaos theory more quickly continued to expand, because the behaviors for which it had response, increased day after day. Furthermore, with the emergence of personal computers and their ability in repetitive actions, many issues about chaotic behaviors that involved in so many repetitions of simple mathematical computations, seemed to be attainable. In 1977, for the first time, a hundred scientists of different sciences came together in Italy to exchange their information about chaos theory and it was the first universal meeting on the chaos theory. Chaos theory is a branch of mathematics that deals with the study of the behavior of dynamical systems that are highly sensitive to the initial conditions and its best example is the butterfly effect. Small changes in the initial conditions (like rounding error in numerical computations), make the results of dynamical systems divergent and in general, the long term predictions impossible. Even though, the systems is completely deterministic, its severe sensitivity to initial conditions is there; it means that the future behavior of the system entirely depends on the initial conditions. In other words, the chaotic nature of these systems makes them unpredictable. This behavior is known as deterministic chaos or for short chaos. Chaotic behaviors have been observed in many natural systems like climate system [25, 26]. Chaos can be studied using chaotic mathematic models or the analytical methods such as diagrams or maps. Almost all of random phenomena we have found so far in the nature, can be justified with the help of chaos theory. Chaos theory is based on mathematics, physics and even philosophy; each of these sciences, have studied and discussed the chaos theory with their special tools. Chaos theory is not a new phenomenon, the law of cause and effect is established based on it, just with this difference that surveys more reasons by different tools for an effect. Chaos theory is not so new to computer science and has been used in encryption for years. A type of encryption, is secret key or symmetric key, which is based on emission and noise and has been successfully modeled by chaos theory [27]. Another kind of its application in the computer science is in DNA computing. By combining DNA computing with chaos theory, the more efficient ways are obtained to encode the images and other information [28]. Robotic [29] is one of the applications to which the chaos theory has been recently applied. Chaos has been used to predict instead of using trial and error to purify the robot’s environment.

4. CSSPCO algorithm

The SSPCO algorithm is inspired by the behavior of partridge chicks [30, 43]. Feeling risk, the chicks of this bird begin to move in an ordered queue behind their mother to come away from the danger zone. This behavior is arisen from the good experience of the front chick in the desired queue. A priority variable is considered for each chick (particle), in this type of the bird (algorithm). The priority variable is set to zero at first, and any time that the position of particle is more appropriate than the best public or personal experience, one unit is added to its priority variable. In any iteration, the priority variable values of different particles are sorted in an elite array like Fig. 2. To go to the next position, each particle sets its movement based on the particle that its priority value is a unit higher than his priority value in the elite array. In other words, any particle tries to reach the position of the particle that its priority variable is an index higher than the given particle.

According to Fig. 1, chick X adjusts its speed vector based on the position of chick Y which its priority variable is an index higher in the arranged priority array of particles. It is worthy to be mentioned that the local search has been done by following the next best particle while the global search has been done implicitly by following the ordered queue.

OPEN IN VIEWER

Fig. 1.

Setting for document template.

OPEN IN VIEWER

Fig. 2.

Sorted array based on priority parameter of chicks.

Now, we combine this algorithm with chaos theory based on two methods. Chaos as a subfield in the research topic of the nonlinear dynamic systems has been widely studied. There are many applications in the actual systems, whether man-made or natural, which seem apparently random. However, it is not random originally, and generally it is a result of a deterministic and defined process. It is for more than a hundred years that the biologists have been examined the samples of the populations of various species. Recently, the scientists have been able to implement chaotic models in certain populations [31]. For example, the study of the Canadian Lynx showed that there is also a chaotic behavior in the population growth [32]. For this reason, we have made a change in the population based algorithms and combined the chaos theory with the evolutionary algorithms. To do this, we use the chaotic generators for generating the populations of these algorithms.

4.1 CSSPCO1

As mentioned, the initial population will be generated according to chaos theory. In the first approach, we generate the initial population based on the chaos function known as Logistic [33]. The equation of Logistic function is as follows: x n + 1 = μ . x n ( 1 - x n ) , 0 ≤ x 0 ≤ 1 ,(1)

where μ ∈ (0 ; 4] is the control parameter, x _i , the ith chaotic value, is a variable and n a natural number. The parameter μ is set to 4.

The population of the SSPCO algorithm is created according to Equation (1). Now, the cost function is applied to the chaotically generated population and the value of any particle of population is determined according to the fitness or cost function. In each iteration, if the position of any particle is better than its best personal experience, a unit will be added to its priority variable. X i . fitness > X i . P best → ( X i . P best = X i . position ) ∧ ( X i . priority = X i . priority + 1 )(2)

If the estimated value of the fitness (the estimated fitness value) in the objective function for each particle is better than the best public experience, the position of that particle will be introduced as the best new public experience and a unit is added to its priority variable. X i . P best > G best → ( G best = X i . position ) ∧ ( X i . priority = X i . priority + 1 ) ,(3)

Now in each iteration, we arrange particles based on the value of their priority variables. Suppose, we call this array π, π _i is the particle with the ith least priority value, the speed equation of the particles will be as follows: X i . velocity = w × X i . velocity + c × x i × ( X φ i . position - X i . position )(4)

where w is the weight of the inertia that determines the amount of effectiveness of the particle current speed in the particle next speed, X _i  . velocity is the current speed of the particle, c is the social coefficient which is a constant number, x _i is a chaotic number between zero and one. Also, X _i  . position is the current position of the ith particle and X _φi  . position is the position/location of the particle which the given particle tries to follow, which in fact is the position of the particle that is an index higher than the given particle (i.e. the ith particle) in the arranged array of priorities where φ _i is defined as index of the next particle in the ordered priority list. φ i = { j + 1 ( π j = i ) ∧ ( j ≠ PopSize ) 0 ( π j = i ) ∧ ( j = PopSize )(5)

By obtaining the velocity vector of particles, the next step position of the ith particle is computed as follows: X i . position = X i . position + X i . velocity(6)

where, the right-hand side X _i  . position is the current location of the ith particle and X _i  . velocity is the velocity of the ith particle that is calculated by Equation (4). It is worthy to note that the similarity between this algorithm and PSO algorithm is exactly in Equation (6). Figure 3 shows the pseudo code of the first proposed algorithm.

OPEN IN VIEWER

Fig. 3.

Pseudo code of the proposed algorithm 1.

4.2 CSSPCO2

In the second proposed method depicted in Fig. 4, the populating is created based on another chaotic function [34, 35]. This equation is presented based on nonlinear dynamics. This pseudo random number generator is the first equation of the nonlinear dynamics in a network with the continuous statement for each node. This generator is discrete in time and space, but is continuous in state (in this generator, time and space are discrete, but the state is continuous), unlike the cellular machines that Wolfram used to generate the random numbers. In the second proposed method, we generate the population based on this function. The function is defined according to Equation (7): x n + 1 = 1 - 2 | x n - 0.5 | ,(7)

where x₀ is a random number in range (0,1). After producing the population using Equation (7), the particles are put in the objective function and their fitness are determined. According to the first method, in the case of fitness of particles, the priority values of them are added. The speed and motion equations of particles in this method are initialized same as the first method.

OPEN IN VIEWER

Fig. 4.

Pseudo code of the proposed algorithm 2.

The CSSPCO1 and CSSPCO2 methods have been implemented in MATLAB 2015a. Their performances have been compared with chaotic algorithms and other state of the art optimization algorithms which have been proposed in recent years. The experimental results have been presented in two sections.

First, we see motion of the particles in the CSSPCO1 method in Fig. 5 on an objective function. Figure 5 shows the procedure of the particle motions over an objective function to achieve a global optimum in a chaotic manner based on the Logistic function. Figure 5 shows how the particles in the population of the CSSPCO1 method is scattered in search space. Figure 5 contains 9 images each of which shows the population distribution in different iterations. The number of particles in the population of this simulation has been 100. We can observe in the consecutive images of Fig. 5 that particles are moving in a queue towards the optimal solution, according to the general framework of CSSPCO1 algorithm. According to the process of the optimization algorithm CSSPCO1, a particle or chick adjusts its next move based on the chick (chicks) that the value (values) of its (their) priority is (are) the next priority value (values) after the priority value of the given particle. This causes to form a queue-like situation towards the optimum solution.

OPEN IN VIEWER

Fig. 5.

Movement of chicks in the CSSPO1 algorithm on a fitness function and in different iterations with first chaos function

Also in Fig. 6, the procedure of particles moving towards the global optimum on the same objective function used in Fig. 5 has been showed. Also, in Fig. 6, the procedure of population convergence can be observed. Figure 6 shows that in the second chaotic function, the manner of creating population is more appropriate for the objective function.

OPEN IN VIEWER

Fig. 6.

Movement of chicks in the CSSPO1 algorithm on a fitness function and in different iterations with second chaos function.

In the first part of experimentations, we present two suggested methods, i.e. the CSSPCO1 and CSSPCO2 methods, along with the chaotic optimization algorithms and based on the parameters of Table 1.

The results have been presented for 12 different objective functions presented in Table 2. In the first part of experimentations, the results have been repeated with 5 known chaotic optimization algorithms and the results have been given in Table 3. The results are based on the best cost in 100th iteration, standard deviation of the particles’ costs in 100th iteration and their 100-iterations execution times. We have reported all of the experimental results in the form of averaged over 30 independent runs so as to avoid random results.

The results are presented in terms of the best cost value among the cost values of particles in the last population (denoted by Best Cost), the standard deviation of the cost values of the last iteration particles (denoted by STD), and run time of the whole process. The results show that the proposed algorithms have had the best performance for each of the 12 cost functions introduced in Table 2 and have outperformed the baselines. For 7 functions, the first proposed method has the best performance among the 7 different algorithms, and for 5 functions, the second proposed method outperforms the others. In function F1, algorithm Chaotic ABC has the worst performance with the cost of 807.58, while for the same function, the first proposed algorithm has the cost value of 7.32E-06, and the second proposed algorithm has the cost value of 7.12-E06; therefore, the CSSPCO2 algorithm has the best cost value among all algorithms. The highest standard deviation for this cost function is associated to Chaotic GA and the lowest standard deviation is associated to CSSPCO2 algorithm. For the cost function F1, the least and most run times are respectively associated to the Chaotic GA algorithm and the Chaotic HS algorithm respectively. Due to the more complexity of the population creation mechanism, the run time of this function for the second proposed method is higher than the first, and this fact is held for all 12 functions. Since the optimized solution of all functions, except for function F6, has been zero, for the rest of objective functions, the two proposed methods have been able to find solutions close to global optima in the 100-th iteration, while for the most of these functions, other algorithms have found the solutions with the same qualities at later iterations.

For detailed analysis, Fig. 7 depicts the best cost during time (iteration). As it can be observed, the proposed methods, converge faster than the other methods in all objective functions. Figure 8 depicts the standard deviation of population particles’ costs in different iterations. This results indicates that the proposed methods have good diversity in the middle-iterations and converge well in the last-iterations. Figure 9 also presents the run time of different methods.

OPEN IN VIEWER

Fig. 7.

The best cost plot in 7 chaotic algorithms PSO, GA, BA, ABC, HS, SSPCO1 and SSPCO2 for (A) F1. (B) F2. (C) F3. (D) F4. (E) F5. (F) F6. (G) F7. (H) F8. (I) F9. (J) F10. (K) F11. (L) F12.

OPEN IN VIEWER

Fig. 8.

The standard deviation plot in 7 chaotic algorithms PSO, GA, BA, ABC, HS, SSPCO1 and SSPCO2 for (A) F1. (B) F2. (C) F3. (D) F4. (E) F5. (F) F6. (G) F7. (H) F8. (I) F9. (J) F10. (K) F11. (L) F12.

OPEN IN VIEWER

Fig. 9.

The run time plot in 7 chaotic algorithms PSO, GA, BA, ABC, HS, SSPCO1 and SSPCO2 for (A) F1. (B) F2. (C) F3. (D) F4. (E) F5. (F) F6. (G) F7. (H) F8. (I) F9. (J) F10. (K) F11. (L) F12.

In this section and in Table 4, we compare the results of two chaotic methods, namely CSSPCO1 and CSSPCO2, with random SSPCO algorithm (traditional SSPCO) to realize the difference between the performance of these algorithms.

The results of this section show that SSPCO algorithm with population created randomly has the best performance for 4 functions and the worst performance for 3 functions. Unlike other optimization algorithms, the difference between results of random SSPCO and chaotic SSPCO methods is low, which arises from the appropriate mechanism of this algorithm to reach the optimized solution. In the second part, the results of the proposed methods and different optimization algorithms that have been proposed in recent years, have been compared. We have compared the proposed methods with algorithms NPSO [36], FIPS [37], CPSO [38], CLPSO [39], EPSDE [40], MRPSO [41] and CCABC [42] in Table 5. In this part, we have done the simulation with the number of particles 500, the number of variables 30 and the number of fitness evaluations 200000. The number of fitness evaluations has been counted in the objective function code. We present the results based on two components, mean cost and standard deviation. The results in terms of mean cost (F _m ean) and standard deviation (SD) of particles have been presented at the end of execution.

The results show that among 9 algorithms, the first and second proposed algorithms, have had the best performances respectively for 6 and 10 cost functions, where 4 functions were common in these two categories. The first proposed method has converged to the optimal solution for 4 functions and the second one could obtain the global optimal point for 6 of cost functions at the end of evaluations. For cost function F1, CLPSO algorithm and the first proposed method commonly reached the optimal point and had the best performance. In this function, CPSO algorithm had the lowest efficiency and reached the mean cost of 5.14E-01. For cost function F2, the best mean cost was related to the first proposed algorithm with the mean cost of 4.13E-027. For this cost function, CLPSO algorithm had the worst mean cost. For the cost function F3, the highest and lowest performances are respectively related to the first proposed and CLPSO algorithms. For the cost function F4, the second proposed method has the best mean cost and CCABC algorithm that is an artificial bee colony based on chaos algorithm had the lowest performance. The same process is repeated for the cost function F5. For the cost function F6, FIPS, CPSO, NPSO and two proposed methods commonly had the best performance. For function F7, the first and second proposed and NPSO algorithms commonly had the best mean cost that was just the optimized point of the problem. Among algorithms, CCABC algorithm had the worst mean cost for functions F7, F8 and F9.

The left-side image in Fig. 10, represents the diagram of the best cost of random population-based SSPCO algorithm (SSPCO algorithm based on random population) and chaos-based SSOCO algorithms averaged on all of the objective functions for various dimensions and the right-side image shows the diagram of the best cost averaged on all of the objective functions, over the various iterations. In Fig. 10, the convergence characteristics of SSPCO, CSSPCO1 and CSSPCO2 algorithms are based on changes in the dimension number of objective functions set. As we can see, the chaotic algorithms are also not sensitive to changes in the feature size of cost functions. Sensitivity analysis of these algorithms to C parameter has been presented in Fig. 11. The cost values have been averaged over all objective functions.

OPEN IN VIEWER

Fig. 10.

The best cost plot averaged on all of the objective functions in SSPCO, CSSPCO1 and CSSPCO2 based on different problem sizes (or dimensions) and iterations.

OPEN IN VIEWER

Fig. 11.

Sensitivity analysis to C parameter.

If the initial population is selected appropriately for optimization algorithms, there is a possibility for its convergence to the optimal points. Therefore, this issue has been investigated in this paper. The paper has proposed using the combination of chaos theory and intelligent algorithms, as a hybrid optimization method, to find a better initial population. It is noticeable that the original versions of evolutionary algorithms, are not lonely effective to find a better initial population. Therefore, using the ideas of chaotic sequences and pseudo-random initial populations, we have improved the performances of these algorithms. Thus, the probability falling at local optima is reduced. In this paper, the population of the SSPCO algorithm has been created by two chaotic functions and it has been observed that for the most of experimentations, chaotic methods have outperformed the other methods. The results of experimentations have compared first with the chaos-based optimization algorithms and then with the new optimization algorithms and the results showed the positive impact of chaos theory on SSPCO algorithm. As the future work in this area, it can be mentioned to the combination of the algorithm with other chaotic functions and its usage for solving the uncertain various complex problems.