SSABA:Search Step Adjustment Based Algorithm

Fatemeh Ahmadi Zeidabadi,Ali Dehghani,Mohammad Dehghani,Zeinab Montazeri,tpán Hubálovsky,Pavel Trojovsky,and Gaurav Dhiman

1Department of Mathematics and Computer Sciences,Sirjan University of Technology,Sirjan,Iran

2Department of Civil Engineering,Islamic Azad University,Estahban Branch,Estahban,Iran

3Department of Mathematics,Faculty of Science,University of Hradec Králové,Hradec Králové,500 03,Czech Republic

4Department of Electrical and Electronics Engineering,Shiraz University of Technology,Shiraz,Iran

5Department of Applied Cybernetics,Faculty of Science,University of Hradec Králové,Hradec Králové,500 03,Czech Republic

6Department of Computer Science,Government Bikram College of Commerce,Patiala,Punjab,India

Abstract: Finding the suitable solution to optimization problems is a fundamental challenge in various sciences.Optimization algorithms are one of the effective stochastic methods in solving optimization problems.In this paper,a new stochastic optimization algorithm called Search Step Adjustment Based Algorithm(SSABA)is presented to provide quasi-optimal solutions to various optimization problems.In the initial iterations of the algorithm, the step index is set to the highest value for a comprehensive search of the search space.Then, with increasing repetitions in order to focus the search of the algorithm in achieving the optimal solution closer to the global optimal,the step index is reduced to reach the minimum value at the end of the algorithm implementation.SSABA is mathematically modeled and its performance in optimization is evaluated on twenty-three different standard objective functions of unimodal and multimodal types.The results of optimization of unimodal functions show that the proposed algorithm SSABA has high exploitation power and the results of optimization of multimodal functions show the appropriate exploration power of the proposed algorithm.In addition, the performance of the proposed SSABA is compared with the performance of eight well-known algorithms, including Particle Swarm Optimization (PSO), Genetic Algorithm (GA), Teaching-Learning Based Optimization (TLBO), Gravitational Search Algorithm (GSA), Grey Wolf Optimization (GWO), Whale Optimization Algorithm (WOA), Marine Predators Algorithm (MPA), and Tunicate Swarm Algorithm (TSA).The simulation results show that the proposed SSABA is better and more competitive than the eight compared algorithms with better performance.

Keywords: Optimization; population-based; optimization problem; search step;optimization algorithm;minimization;maximization

1 Introduction

Optimization is the process of presenting the best solution to a problem out of all the possible solutions to that problem given the limitations and needs of the problem [1].From a mathematical point of view,an optimization problem can be modeled using the three main parts of decision variables,constraints, and objective functions [2].Methods for solving optimization problems fall into two groups:deterministic methods and stochastic methods[3].

Deterministic methods using derivative and Gradient information of objective functions as well as mathematical operators are able to provide optimal solutions to optimization problems.The main advantage of deterministic methods is that they guarantee the proposed solution as the optimal solution.The inability of these methods to solve non-derivative problems,high computational volume in complex problems, time consuming in solving problems with high number of variables, and convergence dependence on initial values in methods that depend on the initial conditions are the most important disadvantages of deterministic methods[4].

On the other hand, optimization algorithms as stochastic methods of solving optimization problems, are able without the need for derivative and gradients information with using random operators and random scanning of the problem search space, in a repetition-based process provide appropriate and acceptable solutions for optimization problems [5].Optimization algorithms are inspired by the concepts of biology, animal behavior, physics, games, and other processes that can be modeled as optimizers[6].For example,in design of Ant Colony Optimization(ACO)is inspired by the ant colony behavior in locating food and how to find the shortest path between food sources and nests[7].Gravitational Search Algorithm(GSA)is inspired by the physical fundamentals of Newton’s laws of motion and the gravitational force[8].Darts Game Optimizer(DGO)is inspired by simulating the rules of the darts game and the behavior of the players in this game[9].

In optimization studies,global optimal solution is the main solution to the optimization problem.Deterministic methods, in optimizing problems that can be implemented, are able to provide this global optimal solution.Stochastic-based optimization algorithms do not necessarily provide the global optimal solution.However,the solutions obtained with optimization algorithms should be as close as possible to the global optimal.For this reason, the solutions obtained using optimization algorithms are called quasi-optimal [10].The concept of quasi-optimal solutions and the desire to improve them to better quasi-optimal and closer to global optimal solution has led to the design of numerous optimization algorithms by researchers.In this regard, these optimization algorithms are applied in various fields in the literature such as energy[11–14],protection[15],electrical engineering[16–21],and energy carriers[22,23]to achieve the optimal solution.

The contribution of this paper is the introduction and design of a new optimization algorithm called Search Step Adjustment Based Algorithm(SSABA)in order to provide quasi-optimal solutions to various optimization problems.Setting the search step in the problem-solving space during the iteration of the algorithm is the main idea in designing the proposed SSABA.In fact, by adjusting the search step,a member of the population,in the initial iterations of the algorithm,scans different spaces of the search space,and as the number of iterations of the algorithm increases,the search step becomes smaller in order to increase the exploitation power.The theory of the proposed SSABA is described and then mathematically modeled.The performance of SSABA is implemented on twentythree standard objective functions of different types of unimodal and multimodal and is also compared with eight well-known algorithms.

The rest of this paper is organized in such a way that a study on optimization algorithms is presented in Section 2.The proposed SSABA is introduced and modeled in Section 3.Simulation studies are presented in Section 4.Conclusions and several suggestions for future studies are provided in Section 5.

2 Background

Optimization algorithms use a relatively similar mechanism to discover the optimal solution.Initially, a number of feasible solutions are generated randomly considering the limitations of the problem.Then,based on the different steps of the algorithm,in an iteration-based process,these initial solutions are improved.The process of updating and improving the proposed solutions continues until the algorithm stop criterion is reached.The distinguishing point of optimization algorithms is the main design idea and mechanism used in updating the proposed solutions.Accordingly,optimization algorithms can be divided based on the main design idea into four groups: swarm-based, physicsbased,evolutionary-based,and game-based[24].

2.1 Swarm-Based Optimization Algorithms

Swarm-based optimization algorithms are designed based on simulation of the swarming behaviors of living organisms such as animals, plants, and insects.Particle Swarm Optimization (PSO)can be mentioned as one of the oldest and most widely used algorithms in this group.PSO is inspired by the social behavior of animals such as fish and birds that live together in small and large groups.In PSO, population members communicate with each other and solve problems using the experience of the best member of the population as well as the best personal experience [25].Grey Wolf Optimization (GWO) is one of the swarm-based algorithms to solve optimization problems that is inspired by the group life of wolves and how they hunt in nature.In GWO, the hierarchical behavior of leadership in the group of gray wolves is modeled using four different types of wolves.The status of each member of the population is updated as a solution to the problem based on the modeling of the hunting process in three phases tracking the prey,encircling the prey,and attacking the prey[26].Whale Optimization Algorithm(WOA)is a swarm-based optimization algorithm which is designed by inspiring the nature and social behavior of humpback whales in a bubble network hunting strategy to achieve a quasi-optimal solution[27].Some other algorithms that belong to this group are:Teaching-Learning Based Optimization(TLBO)[28],Marine Predators Algorithm(MPA)[29], Tunicate Swarm Algorithm (TSA) [30], Emperor Penguin Optimizer (EPO) [31], Following Optimization Algorithm(FOA)[32],Group Mean-Based Optimizer(GMBO)[4],Donkey Theorem Optimization (DTO) [33], Multi Leader Optimizer (MLO) [34], Two Stage Optimization (TSO) [3],Mixed Leader Based Optimizer (MLBO) [6], Good Bad Ugly Optimizer (GBUO) [35], Mixed Best Members Based Optimizer(MBMBO)[24],Teamwork Optimization Algorithm(TOA)[5],and Good and Bad Groups-Based Optimizer(GBGBO)[36].

2.2 Physics-Based Optimization Algorithms

Physics-based optimization algorithms are developed based on the modeling of various physical laws and phenomena.Simulated Annealing(SA)is one of the well-known methods of this group of optimization algorithms, which is designed based on simulation of annealing process in metallurgy[37].Hook’s law simulation in a system consisting of weights and springs connected to each other is used in the design of Spring Search Algorithm (SSA) [38].Momentum Search Algorithm (MSA)is introduced based on the modeling of momentum law and Newtonian laws of motion [39].Some other algorithms that belong to this group are: Black Hole (BH) [40], Ray Optimization (RO)[41] algorithm, Magnetic Optimization Algorithm (MOA) [42], Galaxy-based Search Algorithm(GbSA) [43], Charged System Search (CSS) [44], Artificial Chemical Reaction Optimization Algorithm(ACROA)[45],Binary Spring Search Algorithm(BSSA)[46],Curved Space Optimization(CSO)[47],and Small World Optimization Algorithm(SWOA)[48].

2.3 Evolutionary-Based Optimization Algorithms

Evolutionary-based optimization algorithms are developed based on the modeling of genetics science, biology science and evolutionary operators.Genetic Algorithm (GA) is definitely the most well-known method of intelligent optimization and evolutionary algorithm that has many applications in various scientific and engineering disciplines.GA is introduced based on mathematical modeling of the reproductive process and Darwin’s theory of evolution.The process of updating population members of chromosomes, each of which is a solution to the problem, is simulated using three operators: selection, crossover, and mutation [49].Artificial Immune System (AIS) algorithms are among the algorithms inspired by the mechanism of the human body that fall into the category of evolutionary systems.The human immune system is one of the most accurate and astonishing living systems which modeling the mechanism of this system against viruses and microbes has been used in the design of AIS [50].Some other algorithms that belong to this group are: Biogeographybased Optimizer(BBO)[51],Differential Evolution(DE)[52],Genetic Programming(GP)[53],and Evolution Strategy(ES)[54].

2.4 Game-Based Optimization Algorithms

Game-based optimization algorithms are developed based on the modeling of rules of different games and the behavior of players in those games.HOGO is designed based on simulating the process of searching players to find a hidden object.In HOGO, players are the solution to a problem that moves through the search space to try to find the hidden object,which is actually the optimal solution to the problem[55].FGBO is developed based on mathematical modeling of the behavior of players and clubs in the game of football[56].Orientation Search algorithm(OSA)is introduced based on the simulation of players’movement in the direction specified by the referee[57].Some other algorithms that belong to this group are:Dice Game Optimizer(DGO)[58],Ring Toss Game Based Optimizer(RTGBO)[59],and Binary Orientation Search algorithm(BOSA)[60].

3 Search Step Adjustment Based Algorithm

In this section,the theory of the proposed Search Step Adjustment Based Algorithm(SSABA)is described and its mathematical modeling is presented for use in solving optimization problems.

The proposed SSABA is a stochastic and evolutionary-based algorithm for solving optimization problems.In population-based algorithms,each member of the population represents a solution to the optimization problem that contains information and values of decision variables.Initially,a number of possible solutions to the problem are generated randomly.Then,in an iterative process,the initial solutions are improved to converge towards the optimal global solution to the problem.In each iteration, population members suggest new values for the problem variables by randomly moving through the search space.The main idea of the SSABA in updating the position of population members in the search space is to set the search step during successive iterations of the algorithm.

In the proposed SSABA,each population member can be modeled using a vector and the whole population of the algorithm using a matrix based on Eq.(1).

whereXis the population matrix of SSABA,Xiis theith population member,Nis the number of population members,mis the number of problem variables,xi,dis thedth dimension of status ofith population member in search space.

The objective function of the optimization problem can be evaluated based on the values for the problem variables which are proposed by each population member.The calculated values for the objective function can be modeled using a vector based on Eq.(2).

whereFis the objective function vector andFiis the objective function value which is evaluated based on proposed problem variables by theith population member.

Based on the comparison and analysis of the values obtained for the objective function, the member that provides the best value for the objective function is determined as the best member of the population.The best member of the population as a leader is able to lead the members of the population in the search space towards the suitable solution.Therefore,in the proposed SSABA,the population members move towards the best population member.In this update process,the search step is set during the iterations of the algorithm.The mechanism of adjusting the search step is such that in the initial iterations that the algorithm must scan different areas of the search space well,it is set to its maximum value.Then,as the replication of the algorithm increases,and the population members approach the optimal global solution,the search step value decreases so that the population members converge with smaller and more accurate steps towards the global optimal solution.This search step adjustment mechanism is simulated using Eq.(3).

whereStis the search step in thetth iteration of algorithm,tis the counter of iterations,andTis the maximum number of iterations.

After adjusting the search step in each iteration, the members of the population are updated in the search space according to the search step, and based on the guidance of the best member of the population.The update process in the proposed SSABA is mathematically modeled using Eqs.(4)–(6).The new suggested position for each population member in the search space is determined based on the main idea of the proposed SSABA, which is to move towards the best member of the population by adjusting the search step, using Eqs.(4) and (5).This new position is acceptable to a population member if the value of the objective function improves in that new position, otherwise the member remains in its previous position.This process is simulated using Eq.(6).

whereis the new suggested status for theith population members,is itsdth dimension,is its objective function value,ris a random number in the interval[0,1],xbestis the best population member,andIis a random number which is equal to 1 or 2.

After updating all members of the population, the algorithm enters the next iteration.Based on the new values, the best member of the population is updated.Then the search step for the new iteration is calculated and the population members are updated according to Eqs.(4)–(6).This update process continues until the end of the algorithm iterations.At the end and after the complete implementation of the algorithm, the best quasi-optimal solution to which the SSABA has converged is presented as the solution of the problem.the pseudocode of the SSABA is presented in Algorithm 1.Also, the various stages of the proposed SSABA are shown as flowcharts in Fig.1.

Algorithm 1:Pseudocode of SSABA Start SSABA.1.Input optimization problem information:objective function,variables,and constraints.2.Specify the number of population members(N)and the maximum number of iterations of the algorithm(T).3.Create the initial population at random.4.Evaluate the objective function based on the initial population.5.for t=1:T 6.Update xbest based on objective function values.7.Update St using Eq.(3).8.Calculate Xnew i using Eqs.(4)and(5).9.Update Xi using Eq.(6).10.Save best quasi-optimal solution so far.11.end 12.Output the best quasi-optimal solution obtained using SSABA.End SSABA.

Figure 1:Flowchart of SSABA

The time complexity of the proposed SSABA can be represented as:

1.The initialization of population process needs (N×m) time, whereNis the number of population members andmis the number of dimensions of a given optimization problem.

2.The population member fitness needs (T×N×m)time,whereTis the maximum number of iterations.

3.Steps 1 and 2 are repeated until the satisfactory results is found which needs (S)time.

Thus,the overall time complexity of SSABA is (T×N×m×S).

4 Simulation Studies

Simulation studies and performance analysis of the proposed SSABA in optimization are presented in this section.SSABA is implemented on a standard set consisting of twenty-three objective functions of different types of unimodal, high-dimensional multimodal, and fixed-dimensional multimodal.Complete information on these objective functions is provided in Appendix A and in Tabs.A1–A3.In order to analyze the ability of SSABA in optimization, the optimization results obtained from it are compared with eight well-known algorithms including Particle Swarm Optimization(PSO)[25],Genetic Algorithm(GA)[49],Teaching-Learning Based Optimization(TLBO)[28],Gravitational Search Algorithm(GSA)[8],Grey Wolf Optimization(GWO)[26],Whale Optimization Algorithm(WOA)[27],Marine Predators Algorithm(MPA)[29],Tunicate Swarm Algorithm(TSA)[30].The simulation results of the optimization algorithms in solving the objective functions are reported using two indicators of the average of the best obtained solutions (ave) and the standard deviation of the best obtained solutions(std).

4.1 Evaluation of Objective Functions

4.1.1 Unimodal Functions

The first type of functions considered to evaluate the performance of optimization algorithms are seven unimodal functions, including F1 to F7.The optimization results of these objective functions using the SSABA and eight compared algorithms are presented in Tab.1.Based on the analysis of the optimization results,it is clear that the SSABA is able to provide the optimal global solution for F1 and F6 functions.SSABA is also the best optimizer for optimizing F2,F3,F4,F5,and F7 functions.The simulation results of F1 to F7 functions show that the proposed SSABA is far superior to the eight compared algorithms.

Table 1: Evaluation results of unimodal objective functions

4.1.2 High-Dimensional Multimodal Functions

The second type of functions considered for analyzing the performance of optimization algorithms are six high-dimensional multimodal functions including F8 to F13.The results of the implementation of SSABA and eight comparative algorithms on high-dimensional multimodal functions are presented in Tab.2.What can be seen from the analysis of the results in this table is that the proposed SSABA provides the optimal global solution for the F9 and F11 functions.SSABA is the best optimizer for F8,F10,and F12 functions.Analysis of the performance of optimization algorithms in solving F8 to F13 functions shows that SSABA has a high capability in solving such optimization problems and is superior to the compared algorithms.

Table 2: Evaluation results of high-dimensional multimodal objective functions

4.1.3 Fixed-Dimensional Multimodal Functions

The third type of selective functions to analyze the capabilities of optimization algorithms are ten fixed-dimensional multimodal functions including F14 to F23.The results of optimization of F14 to F23 objective functions using SSABA and eight compared algorithms are presented in Tab.3.The optimization results show that SSABA has been able to provide the global optimal solution for the F17 function.SSABA is also the best optimizer for F15, F16, F19, and F20 functions.The proposed SSABA with less standard deviation,in F14,F18,F21,F22,and F23 functions has a better performance than similar algorithms.Analysis of the simulation results shows that SSABA has a high ability to solve fixed-dimensional multimodal optimization problems and is much more competitive than the eight compared algorithms.

4.2 Discussions

Exploitation and exploration are two factors influencing the performance of optimization algorithms in achieving appropriate solutions to optimization problems.

The concept of exploitation in the study of optimization algorithms shows the ability of the algorithm to search locally and get closer to the global optimal solution.In fact,an algorithm that has the suitable conditions in the power of exploitation is able to converge to a solution closer to the global optimal.The exploitation ability is especially important in solving optimization problems that have only one main solution without having local optimal areas.Unimodal functions with such features are very suitable for analyzing the ability of exploitation to achieve suitable quasi-optimal solutions.The results of optimization of the F1 to F7 Unimodal objective functions presented in Tab.1 indicate that the proposed SSABA with high exploitation capability has been converged to suitable solutions that are very close to the global optimal.The performance analysis of the compared algorithms shows that SSABA is much more competitive than them in terms of exploitation capability.

The concept of exploration in the study of optimization algorithms means the ability of the algorithm to globally search and accurately scan the problem search space.In fact, an algorithm must be able to scan different areas of the search space in order to explore the optimal solution.The exploration ability is especially important in implementing algorithms on problems that have optimal local solutions.Multimodal objective functions of both types of high-dimensional, including F8 to F13 and fixed-dimensional including F14 to F23,have several local solutions in addition to the main solution.Therefore, these types of functions are very suitable for evaluating the exploration power of optimization algorithms.What can be deduced from the analysis of the optimization results of this type of function presented in Tabs.2 and 3 is that the proposed SSABA with high ability in exploration power has been able to scan different areas of the search space and, as a result, cross local optimal solutions.Analysis of the simulation results shows that SSABA has more appropriate exploration power than the compared algorithms and is able to scan the problem search space more effectively.

Table 3: Evaluation results of fixed-dimensional multimodal objective functions

4.3 Statistical Analysis

In this subsection,a statistical analysis on the performance of optimization algorithms in solving optimization problems is presented.Analysis of optimization algorithms based on the two criteria of the average of the best solutions as well as the standard deviation of the best solutions provides valuable information about their ability.However,even after twenty independent runs,it is possible for an algorithm to be superior to compared algorithms at random.Therefore,in this study,the Wilcoxon sum-rank test [61] is used to analyze the superiority of the proposed SSABA from a statistically significant point of view.Wilcoxon sum-rank test is a non-parametric test that is used to compare and assess the similarity of two independent samples.

The results of statistical analysis of SSABA against the compared algorithms using Wilcoxon sum-rank test are presented in Tab.4.In the Wilcoxon sum-rank test,an index calledp-value is used to detect statistical differences between the two data sets.Based on the analysis of the results presented in Tab.4,it is concluded that the superiority of SSABA is statistically significant against the compared algorithm in cases where thep-value is less than 0.05.

Table 4: Obtained results from the Wilcoxon sum-rank test(p ≥0.05)

4.4 Sensitivity Analysis

The proposed SSABA is a population-based algorithm that in an iteration-based process is able to provide a quasi-optimal solution for an optimization problem.Therefore, the two parameters of the maximum number of iterations and the number of population members affect the performance of the proposed algorithm.Therefore,in this subsection,the sensitivity analysis of SSABA to these two parameters is presented.

In order to provide the sensitivity analysis of SSABA to the maximum number of iterations, in independent performances, the proposed algorithm for the maximum number of iterations of 100,500,800,and 1000 is implemented on all twenty-three objective functions.The simulation results of this analysis are presented in Tab.5.What can be deduced from the simulation results presented in this table is that the values of the objective functions decrease when the maximum number of iterations of the algorithm increases.

In order to provide a sensitivity analysis of the proposed algorithm to the number of population members,in independent implementations,SSABA for the number of population members 20,30,50,and 80 is implemented on all twenty-three objective functions.The simulation results of this analysis are presented in Tab.6.Based on the results of the sensitivity analysis of the proposed SSABA to the number of population members,it is clear that increasing the number of population members leads to the more accurate search of the search space and thus converges the algorithm to appropriate quasioptimal solutions which are closer to global optimal.

Table 5: Results of the algorithm sensitivity analysis to the maximum number of iterations

Table 6: Results of the algorithm sensitivity analysis to the number of population members

Table 6:Continued

5 Conclusions and Future Works

Numerous optimization problems designed in different sciences require optimization using appropriate methods.Optimization algorithms, which are one of the stochastic methods of problem solving, are able to provide acceptable quasi-optimal solutions to optimization problems based on random scan of the search space.In this paper, a new optimization algorithm called Search Step Adjustment Based Algorithm(SSABA)was introduced to be used in solving optimization problems.In designing the proposed SSABA,the idea of setting the search step in the problem-solving space for population members during the replication of the algorithm was applied.The step setting process is such that in the initial iterations, the search step is given the highest value in order to explore different areas of the search space.Then, as the iterations of the algorithm increase, the search steps become smaller to converge towards the optimal solution as the exploitation power of the algorithm increases.The proposed SSABA was mathematically modeled and its performance was tested on twenty-three standard functions of different types of unimodal and multimodal.The results of optimizing the unimodal functions indicated the high exploitation power of the SSABA in local search and approaching the global optimal.The results of optimizing the multimodal functions indicated the optimal capability of the SSABA in the exploration and accurate scanning of the problem search space.The performance of the proposed SSABA in providing quasi-optimal solutions was compared with eight algorithms Particle Swarm Optimization(PSO),Genetic Algorithm(GA),Teaching-Learning Based Optimization(TLBO),Gravitational Search Algorithm(GSA),Grey Wolf Optimization(GWO),Whale Optimization Algorithm(WOA),Marine Predators Algorithm(MPA),and Tunicate Swarm Algorithm(TSA).Analysis of the simulation results showed that SSABA is much more competitive compared to the eight mentioned algorithms and has a good performance in solving optimization problems of different types.

The authors offer several suggestions for future work, including the design of binary versions and multi-objective of the proposed SSABA.In addition,the use of SSABA in solving optimization problems in various sciences, nonlinear dynamic systems optimization problems, unconstrained optimization problems, and real-world problems in order to achieve appropriate solutions are from other suggestions for future researches.

Funding Statement:PT (corresponding author) and SH was supported by the Excellence project PF UHK No.2202/2020-2022 and Long-term development plan of UHK for year 2021,University of Hradec Králové, Czech Republic, https://www.uhk.cz/en/faculty-of-science/about-faculty/officia l-board/internal-regulations-and-governing-acts/governing-acts/deans-decision/2020#grant-compe tition-of-fos-uhk-excellence-for-2020.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.

Appendix A.Objective functions

The information of the F1 to F23 objective functions used in the simulation section is specified in Tabs.A1–A3.

Table A1: Unimodal objective functions

Table A2: High-dimensional objective functions

Table A2:Continued

Table A3: Fixed-dimensional objective functions

Table A3:Continued