Volcano eruption algorithm for solving optimization problems

Abstract

Meta-heuristic algorithms have been proposed to solve several optimization problems in different research areas due to their unique attractive features. Traditionally, heuristic approaches are designed separately for discrete and continuous problems. This paper leverages the meta-heuristic algorithm for solving NP-hard problems in both continuous and discrete optimization fields, such as nonlinear and multi-level programming problems through extensive simulations of volcano eruption process. In particular, a new optimization solution named volcano eruption algorithm is proposed in this paper, which is inspired from the nature of volcano eruption. The feasibility and efficiency of the algorithm are evaluated using numerical results obtained through several test problems reported in the state-of-the-art literature. Based on the solutions and number of required iterations, we observed that the proposed meta-heuristic algorithm performs remarkably well to solve NP-hard problem. Furthermore, the proposed algorithm is applied to solve some large-size benchmarking LP and Internet of vehicles problems efficiently.

1 Introduction

We have witnessed fast developments in the field of nature-inspired algorithms in the past few years. The popularity of nature-inspired algorithms has been possible as a result of their promising applications in solving engineering problems. In particular, these algorithms enable gradient-free mechanism and avoid local optima. The first advantage of meta-heuristic is that it does not require the derivative of the search space and leads to finding many good solutions. Properties of guided random search technique as well as exploration and exploitation make meta-heuristic algorithms avoid getting trapped in local optima. As a result, there are several applications of such algorithm in many engineering applications [1].

Meta-heuristic algorithms can be used to train neural network in solving real-life problems, though every approach has its own limitations. Some of the prominent meta-heuristic algorithms include particle swarm optimization (PSO) [1] and autonomous groups particles for PSO (AGPSO) [2], [3], bat algorithm (BA) [4] and its recent application in optimizing beamforming for mmWave in 5G communication [5] and firefly (FF) [6]. On the other hand, nature creature-inspired algorithms have also been proposed to solve optimization problems, such as whale optimization algorithm (WOA) [7], ions motion optimization (IMO) [8] and grey wolf optimizer (GWO) [9], while together with those inspired by nature phenomena, such as chaotic gravitational search algorithm (CGSA) [10] and the recent application of multi-verse algorithm in optimizing the accuracy of fraud detections in smart e-commerce ecosystem [11]. However, no heuristic algorithm is best suited to solve all optimization problems. Moreover, the limitations of high computational cost and premature convergence, the difficulties of selecting best tunable parameters such as the mutation/crossover rate and cutoff time all raise the needs of designing more advanced approaches.

In machine learning, classification in a supervised learning process refers to the process of computer learning to which class of data a new set of observation belongs. This is based on a prior learning conducted on a labeled training dataset. Evolutionary or nature-inspired meta-heuristic algorithms can be a good option in the process of designing/training a classification system. As an example, support vector machine (SVM) is an efficient supervised learning algorithm that can be applied for classification [12]. The optimization of SVM parameters is possible through algorithms like PSO or FF. Feature selection plays a vital role in the process of classification. It turns out that feature selection can be achieved through parameter optimization of SVM using a meta-heuristic algorithm [12]. Feature selection through this process is another example of an application area where a meta-heuristic approach could be effective. It should be noted, however, that there are certain challenges with SVM such as high algorithmic complexity which leads to higher computational cost, extensive memory requirements and selection of appropriate kernel parameters which may be tricky [6].

As a result, success of a meta-heuristic approach in one instance may not guarantee a similar success in another. Researchers have proposed meta-heuristic approaches designed for solving specific problems (e.g., see [1, 13, 14] and references cited therein). They have tried to solve optimization problems by simulating several algorithms based on behavior of animals and insects, natural phenomena or scientific theories [4, 6, 12, 15–22]. Some of these proposed algorithms are artificial bee colony algorithm [16], krill herd algorithm [17], social spider optimization [12], chicken swarm optimization (CSO) [18], big bang algorithm (BBA) [19], laying chicken algorithm (LCA) [20, 23], modified genetic algorithm [21, 24], combined meta-heuristic and classic algorithm [22]. Almost all previous meta-heuristics have been inspired from behavior of animals or insects, and only one of them has been simulated from a scientific theory [19].

This paper proposes, for the first time, an algorithm which is inspired from a natural event, that is, volcano eruption. The algorithm is a novel optimizer for solving various types of continuous and discrete optimization problems. The main contribution of this paper is the translation of natural process of volcano eruption that formulated our proposed volcano eruption algorithm (VEA) to be used as an optimizer. VEA optimizer has gained its robustness from the nature concept of volcano in generating the initial population, movement of solutions, explosion and eruption in the space. Furthermore, the proposed VEA optimizer could achieve an acceptable computational complexity in comparison with the state of the art. The reason was that the proposed algorithm originates from a scientific process and involves simple steps and implementation. However, the algorithm requires a high number of solutions in some iteration as its inherent behavior in changing all feasible solutions in different directions, though VEA provides acceptable best solution in comparison with other meta-heuristics algorithms. This is because it uses different exploration directions, (due to explosions and eruptions) and large region of feasible space. Eventually, our proposed VEA could contribute in solving wide range of linear, nonlinear, multi-level, multi-objective and transportation based on IoV complex optimization problems.

The rest of this paper is organized as follows. Section 2 provides the motivation behind the proposed VEA. Section 3 provides the literature review on recent advances of developed meta-heuristic algorithms. This is followed by presenting an overview of the proposed approach and details of the designed algorithm in Sect. 4. Section 5 presents the experiments and computational results which are conducted in the paper. Finally, Sect. 6 concludes the paper.

2 Inspiration

The nature of volcano has motivated the development of our new optimization algorithm called VEA. VEA optimizer mimics volcano eruption, which is an opening or a hole on the earth’s surface that acts as a vent for release of pressurized gases, ashes and molten rock or magma deep beneath the surface of earth. Deep underground, pressurized magma is passed through a passageway or a conduit, called the volcanic pipe. Magma is referred to as lava when it reaches the hole on the surface of earth and erupts out of it [25]. There are a number of stages leading to formation of a volcano that can be summarized as follows:

• 1. Rise of magma through cracks in the earth.

• 2. Buildup of pressure.

• 3. Volcanic eruption and rise of magma to earth’s surface.

• 4. Formation of a crust as a result of lava’s cooling down.

• 5. Repetition of this process over time leading to several layers of rock that builds up over time resulting in a volcano.

Taking into account the aforementioned volcano eruption stages, a new meta-heuristic VEA algorithm is introduced. In the process of volcano eruption, mass of magma is needed at the first step of this process, so VEA starts with some solutions as initial population. In the volcano eruption process, magma rises through pipes; hence, similar idea is used to move some of solutions in different directions for certain determined distances. In the next step, all solutions will come down and move again in different directions just like the process of volcano eruption.

Finally, some of the solutions in the “pipes”, and points near the surface of earth, are exploded in the region of optimization programming problem. This step comes from eruption of volcano at the top of the mountain into the space. Best solution of all populations will be found, and the algorithm will be using it as an initial solution for the next iteration. As VEA optimizer progresses, it changes and modifies the population and set of solutions, in each iteration. To sum up, the movement of magma from inside the ground to the top of mountain and its explosion have motivated in formulating the main concept for simulation of our proposed VEA optimizer.

3 Related work

There are two main classes of optimization algorithms. The first class is known as deterministic, while the second named stochastic method. When an optimization algorithm works over a deterministic method, it could be whichever gradient-based or non-gradient-based type. The gradient-based method that deployed to locate global solution is a method where mathematical programming is used. Gradient method is incorporating linear and nonlinear programming [26]. In contrast, using a condition-based method, another type of optimization algorithms could be formulated to find the global solution of a given problem [27]. One of the main issues facing mathematical programming approaches is that the trapping within the local optima solutions while searching for a feasible solution in a nonlinear problem.

Hence, many research studies have recently been carried out as a way to overcome this issue by developing some of the existing optimization approaches or hybrid them with different types of algorithms. In some instances, an optimization algorithm has been developed to uniquely address a specified problem, while makes it limited and not generalized to a wide range of optimization problems [28]. The other challenge that could be experienced while developing a non-gradient (deterministic method) is that their implementation required a sophisticated mathematical modeling [29]. Therefore, the use of meta-heuristic algorithms has emerged to overcome such kind of challenges, as they are much easier to understand and adopt, though such kind of algorithms is classified as a stochastic optimization that requires random operators. These operators and other random variables will help meta-heuristics during their global search and avoid them from trapping into a local solution of a given problem.

Meta-heuristic algorithms are inspired from either the behavior of animals, insects or certain natural events. Chemical pheromone of ants is the fundamental concept used for ant colony optimization [30] and [31]. However, the direction and global best have inspired the foundation of particle swarm optimization (PSO) [1]. In contrast, fire fly algorithm [32] has simulated the light indication of fireflies. Similarly, laying chicken algorithm [20] is simulated based on warming of eggs (heat distribution between eggs), as the main concept in formulating the exploration and exploitation strategies.

On the other hand, the authors in [33] have proposed a novel optimization method that inspired from one of the theories of the evolution of the universe, called the big bang and big crunch (BB–BC). In the BB–BC, two phases are formulated. At the first phase of BB, random points are generated, while in the second phase of BC, these generated points are shrunk to a single demonstrative point. This was achieved using an approach called a center of mass or minimal cost. The authors in [34] have examined the exploration–exploitation strategies related to multi-armed bandit settings. They have introduced an adaptive clustering technique for content recommendation. The algorithm considers the collaborative effects that occur due to the interaction of the users with the items.

As another attempt, the authors in [35] have introduced a distributed clustering for solving linear bandits in peer-to-peer networks with the presence of controlled communication facilities. On the other hand, mining $\lambda$-maximal cliques from a fuzzy graph was introduced in [36], and the stochastic optimization techniques are deployed for quantification performance measures by the authors in [26, 37]. In spite of all the aforementioned related work, we could observe that different natures of problems require various optimization methods to support efficient and cost-effective approaches. To this end, in this paper we have presented a new optimization algorithm that is inspired from the nature of volcano to formulate volcano eruption algorithm (VEA), which is detailed out in the next section.

4 The proposed volcano eruption algorithm (VEA)

In this section, we present the details of the proposed VEA. More particularly, we discussed mathematical equations, details of VEA simulation and various steps to find the optimal solution in several types of optimization problem.

4.1 The solutions and populations of VEA

VEA starts with initial solution that is created randomly, and initial population is generated as magma in the volcano eruption process. In fact, initial population in VEA represents the mass of magma below the surface of earth. In volcano eruption process, after the formation of magma, it is distributed in different directions through pipes (points near surface of the earth) and rises toward the surface of earth. Similar to this natural phenomenon, the solution of initial population is distributed in different directions. In the initial population, each possible solution $x_{i}$ is created randomly in proximity to the initial solution $x_{0}$. To form possible solutions, one of the following probability distribution functions is used: (a) probability function of the binomial distribution; (b) probability function of the geometric distribution; (c) probability function of the hypergeometric distribution; (d) probability function of the Poisson distribution, and according to the following formula:

$$\begin{aligned} ||x_{i}-x_{0}||\le \epsilon \end{aligned}$$

(1)

where in $R^{n}$, $i=1,2,n$, $\epsilon$ is a small positive number.

Figure 1 shows the movement of initial population and generation of the possible next population by varying the value of $\epsilon$ from 0.01 to 0.4. We can observe feasible solutions in the initial population (small blue points) and their movement in different directions for a given problem. More importantly, the point with red color in the figure is the optimal solution. Further, in Fig. 1, the next population is represented as black points and distributed in random directions based on the following equation:

$$\begin{aligned} x_{j+1}=x_{j}+ \lambda * d_{rj} \end{aligned}$$

(2)

where $d_{rj}$ is the jth random direction to reach the solution.

Algorithm 1 shows the procedure of generating initial solution and population. The pseudocode starts with a set of random initial feasible solutions and then generates initial population near initial solution according to Formula 1. Thereafter, at each iteration, the algorithm generates a solution of population based on Formula 2.

Fig. 1

Movement of initial population and generation of the next population by different values of $\epsilon$

Fig. 2

Eruption and explosion of the population by considering different values of $\epsilon$

4.2 Explosion and eruption of VEA

In this section, we present the solutions of the current population represented as black points in Fig. 2. These black points are then exploded (represented as green points) and erupted (shown as red points) in feasible search space. This mimics the explosion and eruption of volcano at the top of the mountain. In fact, solutions are changed in the direction of the vector, which connects solutions and the center solution of the population. These movements are according to Eqs. 3 and 4:

$$\begin{aligned} x_{j+1} &= x_{j}+ \alpha d_{cj} \end{aligned}$$

(3)

$$\begin{aligned} x_{j+1} &= x_{j}- \beta d_{cj} \end{aligned}$$

(4)

where $d_{cj}$ is the vector to connect $x_{c}, x_{j}$, $\alpha$ and $\beta$. It is worth mentioning that $\alpha$ and $\beta$ are positive constants and $x_{c}$ is the solution derived from initial solution in the previous direction to compose a population (center solution). Moreover, Eq. 3 represents the formulation of the explosion phenomenon, and Eq. 4 represents the eruption process.

In the process of explosion and eruption phenomenon, the proposed VEA finds the best solutions in all populations. The populations include initial population, second population which is created after movement of initial population in different directions (black points), third population which is generated after explosion using Eq. 3 (green points), and finally the fourth population which is constructed after eruption and using Eq. 4 (red points). Then, the best solution can be found and is shown by large blue point in Fig. 2. The VEA continuously searches for the optimal point using the best solution as initial solution for the next iteration. The process of explosion and eruption in the first iteration is shown in Fig. 2 with $\epsilon$=0.1, $\epsilon$=0.25. Algorithm 2 shows the pseudocode for explosion and eruption.

4.3 Analysis of VEA convergence behavior

In the previous section, we have shown that VEA intelligently explores the promising regions of the search space and targets the best one. The VEA promptly replaces initial solutions with the best ones and then progressively converges. To achieve this goal, the procedure of the proposed algorithm is summarized as follows:

• 1. Initial solution is generated randomly. It will be the origin for constrained problems.

• 2. Initial population is generated near to the initial solution. Here, $\epsilon$ is a given positive small number and j = 1. The VEA finishes the search process when meets the termination condition.

• 3. Solutions are moved into different directions for a specific distance (until reaching the pipes).

• 4. New solutions near pipes are generated.

• 5. Explosion of the solutions is performed near pipes.

• 6. Falling of solutions near pipes from different directions.

• 7. Find the best solution of the population. If $j<2$, (let j = j + 1) go to the step 2 with the best solution serving as the initial solution to the next population. For instance, Fig. 3 shows the process of convergence for Examples 4 to 7.

• 8. VEA is terminated by reaching the termination condition $d(f(x_{j+1}),f(x_{j}))<\epsilon$ and converges $x_{j+1}$ as the best solution whereas $x_{j}$ is the best solution in the jth iteration. If the termination criteria are not satisfied, set the value of j to j+1 and go to step 2. In Fig. 4, the aforementioned steps and the progress of the algorithm to find optimal solution $R^2$ are illustrated. Furthermore, we defined d in Eq. 5:

  $$\begin{aligned} \max _{i} \qquad |f(x^{i}_{j+1})-f(x^{i}_{j})|=d(f(x_{j+1}),f(x_{j})) \end{aligned}$$

  (5)

Fig. 3

The process of finding optimal solution (convergence) by VEA—Example 4–7

Fig. 4

Steps of the algorithm to solve a given problem

Convergence behavior and property of any meta-heuristic algorithm are very significant. To achieve this goal, the following theorem proves that the proposed VEA algorithm is convergent.

Theorem 1

The sequence of ${F_{k}}$, which is proposed in the procedure of VEA, is convergent to the optimal solution. Note that ${F_{k}}$ is defined as an objective function at point x(k).

Proof

Let ${(F_{v})=(F(t^{v}))=(F(t_{1}^{v}),F(t_{2}^{v}),\ldots ,F(t_{n}^{v}))=(F_{1}^{(v)},F_{2}^{(v)},\ldots ,F_{n}^{(v)})}$ According to step 6 in the procedure of the proposed algorithm (Sect. 4.3)

$$\begin{aligned} \max |f(x^{i}_{j+1})-f(x^{i}_{j})|=d(f(x_{j+1}),f(x_{j}))=d(F_{j+1},F_{j})<\epsilon _{1}. \end{aligned}$$

Therefore, $|f(x^{i}_{j+1})-f(x^{i}_{j})|$ for each i. There is a large number such as N which $k+1>k>N$ and $j=1,2,\ldots ,n.$ . Now, we have:

$$\begin{aligned} |F_{j}^{(k+1)},F_{j}^{(k)}|<\epsilon _{1} \end{aligned}$$

Now, let m = k + 1, r = k then we have:

$$\begin{aligned} |F_{j}^{(m)},F_{j}^{(r)}|<\epsilon _{1} \,\, For \;\; m>r>n \end{aligned}$$

This shows that for each fixed j, $1\le j\le n$, the sequence $(F_{j}^{(1)},F_{j}^{(2)},\ldots )$ is Cauchy of real numbers, then it converges, say to ${F_{k}}$. Using these n times, we define $(F_{1},F_{2},\ldots ,F_{n})$ and if m = k + 1, r = k,

$$\begin{aligned} d(F_{m},F_{r})<\epsilon _{1} \end{aligned}$$

Now if ${F_{k}}$ we have

$$\begin{aligned} d(F_{m},F_{r})\le \epsilon _{1} \end{aligned}$$

This shows that F is the limit of ${F_{m}}$ and the sequence is convergent. Thus, this is considered a proof of the theorem. $\square$

4.4 Mathematical nature of the algorithm

This section presents the mathematical background of the VEA and summarized in the following points:

• 1. Generation of feasible initial solution and population.

• 2. Movement of solutions to improve population and reach better solutions.

• 3. Termination of the algorithm when it reaches the best solution.

• 4. Convergent of the algorithm.

Firstly, a feasible solution is created randomly in the feasible region. Then to produce feasible initial population, it is generated near enough to the initial solution based on the following formula: $\sqrt{(x_{i1}-x_{01})^2++(x_{i2}-x_{02})^2+\ldots +(x_{in}-x_{0n})^2}\le \epsilon.$ In this phase, the algorithm tries to move solutions of initial population in different random directions to increase the chances for finding better solutions. This movement is based on Eq. 2. In the second phase, explosion and eruption of volcano are simulated by going up and then coming down based on Eqs. 3 and 4. The third phase satisfies the termination of the algorithm based on the following condition:

If $d(f(x_{j+1}),f(x_{j}))=Max |f(x^{i}_{j+1})-f(x^{i}_{j})|<\epsilon$, then the algorithm will be finished and $x_{j+1}$ is the best solution by VEA and $x_{j}$ is the best solution in jth iteration.

Finally, convergence feature of VEA has been proven by the aforesaid condition and Theorem 1.

5 Computational results

To show the numerical efficiency of the proposed VEA, several mathematical optimization problems are addressed and solved using our proposed VEA optimizer. In particular, two classes of optimization problems are considered and solved: a) continuous problems with small size and b) discrete and practical problems with large size. Then, VEA is used to solve complex routing optimization NP-hard problem in harsh IoV scenarios.

5.1 VEA solving continuous problems

This section presents almost all kinds of continuous optimization problems: Constrained, unconstrained, linear, nonlinear, multi-level and multi-objective will be solved by the proposed VEA.

Fig. 5

Finding optimal solution by VEA—Example 1

Example 1

[38](Constrained—Nonlinear) The initial and optimal solutions as well as different populations of the algorithm for Example 1 are shown in Fig. 5. The large blue point in Fig. 5 is the optimal solution, which has been found by solutions after two iterations.

In order to compare the proposed VEA with classical methods, we consider the following nonlinear programming problem, as shown in Eq. 6:

$$\begin{aligned}&\min _{} \quad -(x_{1}-4)^{2} -(x_{2}-4)^{2}\nonumber \\&{\text {s.t.}} \quad x_{1}-3\le 0\nonumber \\&\quad -x_{1}+x_{2}-2\le 0\nonumber \\&\quad x_{1}+x_{2}-4\le 0\nonumber \\&\quad x_{1}, x_{2}\ge 0\nonumber \\ \end{aligned}$$

(6)

Table 1 Comparison of VEA with nonlinear algorithms—Examples 1 and 2

Example 2

[40] (Multi-level) Consider the following linear bi-level programming problem:

$$\begin{aligned}&\min x-4y\nonumber \\&subject \,to\nonumber \\&\min y\nonumber \\&subject \,to\nonumber \\&x+y\ge 3\nonumber \\&-2x+y\le 0\nonumber \\&2x+y\le 12\nonumber \\&3x-2y\le 4\nonumber \\&x, y\ge 0 \end{aligned}$$

(7)

Using Karush–Kuhn–Tucker (KKT) conditions, the problem will be converted into the following problem:

$$\begin{aligned}&\min x-4y\nonumber \\&subject \,to\nonumber \\&-\lambda _{1} +\lambda _{2} +\lambda _{3} -2\lambda _{4} =-1\nonumber \\&\lambda _{1}(-x-y+3)=0\nonumber \\&\lambda _{2}(-2x+y)= 0\nonumber \\&\lambda _{3}(2x+y-12)=0\nonumber \\&\lambda _{4}(3x-2y-4)=0\nonumber \\&- x-y+3\le 0\nonumber \\&-2x+y\le 0\nonumber \\&2x+y-12\le 0\nonumber \\&3x-2y-4\le 0\nonumber \\&x, y, \lambda _{1}, \lambda _{2}, \lambda _{3}, \lambda _{4}\ge 0 \end{aligned}$$

(8)

The bi-level programming problem is NP-hard because of its two objective functions. In fact, these two objective functions should be optimized in two different levels at the same time. Therefore, proposing a solution for this problem is significant. The proposed VEA optimizer could find optimal solution in a fast pace (within two iterations as shown in Table 1), which is the exact solution found by algorithms with relatively small number of agents. By solving such problems presented in Examples 1 and 2, VEA shows its high performance with less complexity. Behavior of solutions, constraints of the problem and optimal solution are shown in Fig. 6.

Fig. 6

Process of finding optimal solution by VEA—Example 2

Fig. 7

Generations of VEA to find optimal solution—Example 3

Example 3

[41] (Multi-objective) In this example, VEA is used for solving DTLZ benchmark problems [42]. Behavior of the algorithm in finding the pareto optimal for DTLZ1 problem is shown in Fig. 7. It is clear that some of the solutions in the population have reached pareto optimal solution; this illustrates the feasibility of the algorithm as shown in Fig. 7c, d, which also indicates the initial population. Moreover, efficiency of the algorithm is obvious by comparing Fig. 7a, f. At the beginning of applying the algorithm, most of the solutions are completely far from pareto optimal. However, during the searching process, the algorithm solutions achieve pareto optimal. Figure 7f shows that the last population has surrounded pareto optimal solutions.

Table 2 shows the comparison of best solutions to get pareto optimal of DTLZ problems by VEA and the best method in [42].

Table 2 Comparison of VEA and other methods for DTLZ problems

Example 4

In this example, we apply our proposed VEA on non-convex optimization problem named Rastrigin function (RF). Figure 8 shows the process of finding optimal solution using VEA for Example 4.

$$\begin{aligned} \min 20+(x^2-10\mathrm{cos}(2\pi x))+(y^2-10\mathrm{cos}(2\pi y)) \end{aligned}$$

(9)

Fig. 8

Process of finding optimal solution by VEA—Example 4

Fig. 9

Process of finding optimal solution by VEA—Example 5

Example 5

In this example, we consider Holder Table Function (HTF) because it has many local minima, with four global minima. We have evaluated the function using the input domain of $x_i$ $\in$ [$-10$, 10]. It is worth mentioning that the HTF is not convex, multimodal and defined in two-dimensional space. HTF is shown in Eq. 10:

$$\begin{aligned} \begin{aligned} \min -|\mathrm{sin}(x)\mathrm{cos}(y)\mathrm{exp}(|1-\sqrt{(x^2+y^2)}/\pi |)|\\ \end{aligned} \end{aligned}$$

(10)

We have applied our proposed VEA to solve HTF. The process of the algorithm, initial population, optimal solution of generations and constraints of the problems have been shown for two iterations in Fig. 9.

Fig. 10

Process of finding optimal solution by MV—Example 6

Example 6

In this example, we consider Mishra’s bird function (MBF), which is shown in Eq. 11. The problem has been solved by VEA; the process of the algorithm, initial population, optimal solution of generations and constraints of the problems have been shown for two iterations in Fig. 10.

$$\begin{aligned} \begin{aligned} \min \mathrm{sin}(x)\mathrm{exp}((1 - \mathrm{cos}(y))^{2}) + \mathrm{cos}(y)\mathrm{exp}((1 - \mathrm{sin}(x))^{2}) + (x - y)^{2}\\ \end{aligned} \end{aligned}$$

(11)

Table 3 Details of Examples 7–10

Fig. 11

Process of finding optimal solution by VEA—Examples 7–10

Table 4 Results of VEA for Examples 7–10

Further, more benchmark examples are required to test and evaluate the proposed VEA. Accordingly, we consider functions such as unimodal, multimodal, fixed dimension and multimodal. Table 3 shows the Examples from 7 to 10 with equations and details. Table 4 and Fig. 11 show the results of VEA for Examples 7 to 10, where optimal solutions are found in 1 to 3 iterations.

5.2 VEA solving large-size practical problems

To show efficiency of the algorithm for real-life/size problems, in this section three kinds of practical problems have been solved: large-size real linear programming problems and IoV problems. In MATLAB, we used “Linprog” as an exact method based on simplex to solve linear programming problems. Table 5 shows the superiority of VEA in solving large-size problems as compared with several benchmark linear programming functions. Further, absolute error of “Linprog” and VEA in terms of the optimal solution, in Table 6, indicates that the classic method is impractical and inefficient as compared to the proposed VEA. Moreover, finding a suitable feasible solution of transportation problem is very significant; thus, VEA was applied to some random transportation problems [14]. Table 7 shows the results of applying VEA in intelligent transportation problems.

Table 5 Results of VEA for more test problems

Table 6 Comparison errors of VEA and classic methods

Table 7 Comparison among VEA and other algorithms for large-size problems

Table 8 shows the comparison of our proposed VEA with Vogel algorithm, which is the best algorithm in finding feasible solutions of transportation problem. As can be seen, we have shown the superiority of the proposed VEA.

Table 8 Improvement amount of Vogel algorithm by VEA

5.3 VEA solving route optimization in IoV scenario

Fig. 12

Optimal routing process in IoV environment

The objective of this problem is to maximize the connectivity probability and link quality of the available routes from source to destination as illustrated in Fig. 12 [23, 43]. The probability of connectivity can be found by real-time estimation of traffic density from source to destination [44]. Further, the maximization process is subject to signal to interference and noise ratio threshold ($\mathrm{SINR}{_th}$) in order to find more reliable and connected route in urban SDN-based vehicular scenarios. The city road networks in vehicular scenario are represented as graph model G(i,e) where i is an intersection and e is the road segment between two intersections [45, 46]. Therefore, each optimal route $\zeta$ consists of a set of intersections $(i_{1},i_{2},i_{3},i_{4},i_{5},i_{6}, \ldots , i_{m})$ and a set of streets $(e_{1},e_{2},e_{3},e_{4},e_{5},e_{6}, \ldots , e_{n})$, where $n=m-1$. According to the aforementioned assumptions, the objective function of the optimization problem can be written as:

$$\begin{aligned}&\max _{\zeta }\quad F(\zeta )= \lambda _{1} \times PC(\zeta )+ \lambda _{2} \times \mathrm{SINR}(\zeta ) \end{aligned}$$

(12)

$$\begin{aligned}&\text {where} \quad PC(\zeta )= \prod _{i=1}^{n} PC(e_{i}),\nonumber \\&\quad \mathrm{SINR}(\zeta )= \frac{\sum _{i=1}^{n} \mathrm{SINR}(e_{i})-\sum _{i=1}^{n}\mathrm{SINR}_{th}(e_{i}))}{\sum _{i=1}^{n} \mathrm{SINR}(e_{i})},\end{aligned}$$

(13)

$$\begin{aligned}&\text {subject to}\qquad \mathrm{SINR}(\zeta ) \ge \mathrm{SINR}_{th}(\zeta ), \end{aligned}$$

(14)

where F($\zeta$) is defined as the objective function with a set of routes $\zeta$ from source to destination. $\lambda 1$ and $\lambda 2$ are the weights that empirically set in the simulation, and their summation is equal to 1. $PC(\zeta )$ and $\mathrm{SINR}(\zeta )$ represent connectivity and reliability of routes, respectively. $PC(e_{i})$ and $\mathrm{SINR}(e_{i})$ represent the street’s connectivity and link reliability. Figure 12 illustrates the routing process in SDIoV [23].

This problem is addressed by both mathematical and heuristic algorithms. Laying chicken algorithm (LCA) [20] has been used to find optimal route from source to destination [23]. The comparison of results of LCA and VEA is provided in Table 9.

Table 9 Comparison of LCA and VEA for Internet of vehicles

For each problem, an initial solution has been generated randomly and these initial solutions are different for both LCA and VEA algorithms. Table 10 shows improvement in their initial solutions after five iterations.

Table 10 Improvement in VEA and LCA from their random initial solutions (RIS) in five iterations

5.4 Comparison of VEA with other optimization techniques

In this section, VEA is compared with other techniques, VEA is used to solve two different categories of test functions: unimodal and multimodal. Unimodal test functions have just a global optimum, but multimodal test functions have a global optimum as well as multiple local optima. Details of these benchmark functions are shown in Table 11. For the verification of the results, the proposed algorithm is compared with multi-verse optimizer (MVO) [8], grey wolf optimizer (GWO) [9], PSO and GA.

Table 11 Optimization test functions

Table 12 Comparison of VEA and other methods with benchmarks

Note that the number of agents is set on 50 and the maximum number of iterations is equal to 100 and epsilon is 0.1; also, the algorithm is run 50 times. The results presented in Table 12 show that the proposed algorithm is able to provide very competitive and efficient performance on both the unimodal and multimodal test functions. Ave. and Std. are average results and corresponding standard deviations, respectively. Low standard deviation of VEA is significant, which indicates that the values tend to be close to the mean of the set.

6 Conclusion

A novel meta-heuristic optimization algorithm has been proposed in this paper, which is inspired from a natural event of volcano eruption. The proposed algorithm has formulated a new optimizer for solving numerous sorts of continuous and discrete optimization problems. Utilizing the natural process of volcano eruption, our proposed volcano eruption algorithm (VEA) has been formulated and been used as an optimizer. The significance of our proposed VEA lied in its robustness in producing a wide-range set of the initial population, movement pattern across the solutions space, explosion and eruption in the space. This was achieved from the concept of the volcano eruptions nature, which has contributed significantly in improving the optimization process. Therefore, the proposed VEA optimizer could achieve an acceptable computational complexity with noticeable improved performance in comparison with the state of the art. Numerical results presented in this paper have shown that our proposed VEA could significantly contribute in solving wide range of linear, nonlinear, multi-level, multi-objective and transportation based on IoV complex optimization problems. The following briefly outlines some areas for future work to be further studied:

• 1. Explore the possibility of solving some NP-hard problems such as travelling salesman problem using the proposed VEA.

• 2. VEA should be attempted in solving problems that involve big data as it has appropriate complexity.

• 3. The algorithm should be extended for solving discrete problems such as shortest path problem.

• 4. Combination of the proposed algorithm as an inspired approach with exact methods, for example, finding an approximate gradient vector by VEA for using methods such as simplex, which uses gradient directly.

• 5. Implementation of such similar ideas like floods, hurricanes, earthquakes and others.