Optimization of Benchmark Functions using VTS-ABC Algorithm

3905 words (16 pages) Essay

4th Apr 2018 Computer Science Reference this

Disclaimer: This work has been submitted by a university student. This is not an example of the work produced by our Essay Writing Service. You can view samples of our professional work here.

Any opinions, findings, conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of UKEssays.com.

Performance Optimization of Benchmark Functions using VTS-ABC Algorithm

Twinkle Gupta and Dharmender Kumar

Abstract– A new variant based on tournament selection called VTS-ABC algorithm is provided in this paper. Its performance is compared with standard ABC algorithm with different size of data on several Benchmark functions and results show that VTS-ABC provides better quality of solution than original ABC algorithm in every case.

Keywords Artificial Bee Colony Algorithms, Nature-Inspired Meta-heuristics,Optimizations, Swarm Intelligence Algorithms, Tournament selection.

NOMENCLATURE

ABC – Artificial Bee Colony

ACO – Ant Colony Optimization

BFS – Blocking Flow-Shop Scheduling

DE – Differential Evolution

EA – Evolutionary Algorithm

GA – Genetic Algorithm

MCN – Maximum Cycle Number

PSO – Particle Swarm Optimization

TS – Tournament size

TSP – Travelling Salesman Problem

1.INTRODUCTION

For optimization problems, various algorithms havebeendesigned which are basedonnature-inspiredconcepts [1].Evolutionary algorithms(EA) and swarmoptimizationalgorithmsare two different classes in which nature inspired algorithms are classified.Evolutionary algorithms like Geneticalgorithms (GA)andDifferentialevolution (DE) attempt to carry out the phenomenon ofnaturalevolution [2]. However, a swarm like ant colony, a flock of birds can be described as collection of interacting agents and their intelligence lieintheir way of interactions with other individuals andtheenvironment [3]. Swarm optimization includes Particle swarm optimization (PSO) modelon socialbehaviorofbirdflocking [4], Antcolony optimization (ACO) model on swarmofants and Artificial Bee Colony (ABC) model on the intelligent foraging behaviour of honey bees [5]. Some important characteristics of ABC algorithm which makesitmoreattractivethanotheroptimizationalgorithms are:


  1. Employs only three control parameters (population size, maximum cycle number and limit) [6].

  2. Fastconvergencespeed.
  3. Quite simple, flexible and robust [7] [8].
  4. Easyintegrationwithotheroptimizationalgorithms.

Therefore, ABC algorithm is a very popular nature inspired meta-heuristic algorithm used to solve various kinds of optimization problems. In recent years, ABC has earned so much popularity and used widely in various application such as: Constrained optimization, Image processing, Clustering, Engineering Design, Blocking flow shop scheduling (BFS), TSP, Bioinformatics, Scheduling and many others [9]-[18].Similar to other stochastic population-based approaches like GA, Ant Colony etc. ABC algorithm also applied Roulette Wheel selection mechanism which chooses best solution always with high selection pressure and leads the algorithm into premature convergence. With ever-growing size of dataset, optimization of algorithm has become a big concern. This calls for a need of better algorithm.

The aim of this paper is to create such an algorithm named VTS-ABC algorithm. This new variant is based on tournament selection mechanism and selects variable tournament size each time in order to select the employed bees sharing their information with onlooker bees. Onlooker bees select solution from selected tournament size of solutions with less selection pressure so that high fitness solutions can’t dominate and give better quality of solutions with large data set as well. A worst solution is also replaced by better solution generated randomly in each cycle.

Get Help With Your Essay

If you need assistance with writing your essay, our professional essay writing service is here to help!

Find out more

Rest of the paper is divided in different sections as follows: Introduction to standard ABC algorithm is described in section 2. Section 3 describes the proposed VTS-ABC algorithm. Experiments and its simulation results to show performance on several Benchmark functions are described in section 4 and in the last; Conclusion of the paper is discussed.

2.ARTIFICIAL BEE COLONY ALGORITHM

In 2005, Karaboga firstly proposed Artificial Bee Colony algorithm for optimizing numerical problems [19] which includes employed bees, onlooker bees and scouts. The bee carrying out search randomly is known as a scout. The bee going to the food source visited by it before and sharing its information with onlooker bees is known as employed bee and the bee waiting on the dance area called onlooker bee. ABC algorithm as a collective intelligence searching model has three essential components: Employed bees, Unemployed bees (onlooker and scout bees) and Food sources. In the view of optimization problem, a food source represents a possible solution. The position of a good food source indicates the solution providing better results to the given optimization problem. The quality of nectar of a food source represents the fitness value of the associated solution.

Initially, a randomly distributed food source position of SNsize, the size of employed bees or onlooker bees is generated. Each solution xi is a D-dimensional vector that represents the number of optimized parameters and produced usingthe equation 1:

where,xmaxandxminare the upper and lower bound of the parameterxi,respectively and j denotes the dimension. The fitness of food sources to find the global optimal is calculated by the following formula:

where, fm(xm)is the objective function value of xm. Then the employed bee phase starts. In this phase, each employed bee xi finds a new food source viin its neighborhood using the equation 3:

where, t: Cycle number; : Randomly chosen employed bee and k is not equal to i ; ( ): A series of random variable in the range [-1, 1]. The fitness of new solution produced is compared with that of current solution and memorizes the better one by means of a greedy selection mechanism.

Employed bees share their information about food sources with onlooker bees waiting in the hive and onlooker bees probabilistically choose their food sources using fitness based selection technique such as roulette wheel selection shown in equation 4:

where, Pi: Probability of selecting the ith employed bee, S: Size of employed bees, θi: Position of the ith employed bee and F : Fitness value. Afterthatonlookerbeescarried outrandomly searchintheirneighborhood similar to employed bees and memorize the better one.

Employed bees whose solutions can’t be improved through a predetermined number of cycles, called limit, become scouts and their solutions are abandoned. Then, they find a new random food source position using the following equation 5:

Where, r: A random number between 0 and 1 and these steps are repeated through a predetermined number of cycles called Maximum Cycle Number (MCN).

3.PROPOSED WORK: VTS-ABC ALGORITHM

In every meta-heuristic algorithm mainly two factors need to be balanced for global optimization outcome i.e. Exploration and Exploitation but ABC is a poor balance of these two factors. Various variants of ABC have been modelled for its improvement in different phases by number of researchers like Sharma and Pant have proposed a variant of ABC called RABC for solving the numerical optimization problem [20] and Tsai et al. have presented an interactive ABC optimization algorithm to solve combinational optimization problem [21] in which the concept of universal gravitational force for the movement of onlooker bees is introduced to enhance the exploration ability of the ABC algorithm. D. Kumar and B. Kumar also reviewed various papers on ABC and give a modified RABC algorithm based on topology for optimization of benchmark functions [22] [23].

Intelligence of ABC algorithm mainly depends upon the communication between individual agents. Employed beesshare their information with onlooker bees waiting in the hive and flow of this information from one individual to another depends on the selection mechanism used. Different selection schemes select different individuals to share the information which affect the communication ability of individuals and primarily the outcome of the algorithm. ABC algorithm uses Roulette wheel selection mechanism in which each onlooker bee selects the food source based on certain probability. Each onlooker bee selects the best food source with high selection pressure and lead to premature convergence. To overcome this problem, its new variant is proposed in which Tournament Selection method is applied based on Cycle number and number of employed bees.

In Tournament selection, a tournament size (TS) is chosen to select the number of employed bees sharing the information with onlooker bees. For better exploration, TS=2 i.e. Binary Tournament is applied in early stages and for better exploitation, variable tournament size is applied based on the current cycle number (CYL) and size of employed bee in middle stages. As the stages grow, this method works similar to Roulette wheel method in the end. Hence, the selection pressure is less in early stages and more in final stages which provide us better quality of solution. As variable size of tournament is used at different stages of the algorithm, hence the algorithm named VTS-ABC (Variable Tournament Size Artificial Bee Colony) algorithm. Method used for calculating TS is shown in equation 6 and equation 7:

If SN >= 20

If SN<20

Where

Here, two equations are shown for calculating tournament size of tournament selection method. The purpose of using these two equations is to increase the speed of algorithm. When the size of employed bee i.e. given population of food source positions is small like 10, a solution can be easily found by changing the tournament size by 1 but as the size grows i.e. when best food source position is to be found in large set of population for example when SN=40 or more than 40, increasing size of tournament by 1 and 2 only is a very tedious task as it will take more time to run the algorithm. Hence, in order to increase speed of algorithm, the tournament size based on current cycle and size of population is increased.

One more concept is applied to increase its convergence speed. At each iteration or cycle, a new solution is generated randomly similar to scout and its fitness value is calculated. Greedy selection mechanism is applied between new solution and worst one and the better solution is memorized. Hence, it helps in finding good quality of solution as well as improving the convergence speed and provides better balance between exploration and exploitation.

4.experiments and simulation results

4.1 Benchmark Functions

The Benchmark Functions used to compare the performance of VTS-ABC algorithm with original ABC algorithm are illustrated below:

  1. Sphere Function:

  1. Schwefel Function:

  1. Griewank Function:

Where

  1. Ackley Function:

Here, ObjVal is the function value calculated for each food source position. A food source is represented by X and population size is taken of n*p matrix where n is the no. of possible food source positions and p represents the dimension of each position.

Find out how UKEssays.com can help you!

Our academic experts are ready and waiting to assist with any writing project you may have. From simple essay plans, through to full dissertations, you can guarantee we have a service perfectly matched to your needs.

View our services

4.2 Performance Measures & Simulation Result

The experimental results of VTS-ABC and ABC algorithm in MATLAB are taken under the parameter of size of food source positions (n*p) i.e. different size of population with different dimensions are taken to run and compare both algorithms. MCN is set as 2000 and each algorithm is run for 3 iteration i.e. Runtime=3. Limit for scouts is set equals to 300. In order to provide the quantitative assessment of the performance of an optimization algorithm, Mean of Global Minimum i.e. mean of minimum objective function value at each cycle of all iterations are taken as performance measure whose values are shown in table1and figure 1-4.

Table1: Mean of Global minimum on different size of data

Benchmark function

Algorithm

20*10

100*100

150*100

Sphere

ABC

0.340462

13.0503

0.0124608

 

VTS-ABC

0.0988222

6.70776

0.011053

Schwefel

ABC

1.23231

0.107861

19.0437

 

VTS-ABC

0.729075

0.107592

14.3503

Griewank

ABC

0.0619326

0.000526703

0.447714

 

VTS-ABC

0.0146616

0.00043907

0.189238

Ackley

ABC

1.56513

0.0648988

2.57993

 

VTS-ABC

0.946886

0.0604899

2.13692

Fig. 1: Mean of Sphere function values on different size of data

Fig. 2: Mean of Schwefel function values on different size of data

Fig. 3: Mean of Griewank function values on different size of data

Fig. 4: Mean of Ackley function values on different size of data

Figure 1 to 4 show simulation results of ABC and VTS-ABC algorithm with different size of data on Sphere, Schwefel, Griewank, Ackley respectively and reveal that VTS-ABC algorithm provides us better quality of solution than original ABC algorithm by minimizing objective function value or producing higher fitness solutions.

5. DISCUSSION AND CONCLUSION

In this paper, a new algorithm VTS-ABC is presented. In this algorithm, firstly variable tournament size (TS) is applied to select the food source position for onlooker bees which helps to achieve diversity in solution. Then to increase convergence speed, a new solution is generated in each cycle which replaced the worst one. In order to demonstrate the performance of proposed algorithm, it is applied on several Benchmark functions with different size of data set as input. Simulation results show that it provides better quality of solution than original ABC algorithm in every case. Therefore, it can be applied in different fields of optimization with large and higher dimensions data set efficiently.

References

Cite This Work

To export a reference to this article please select a referencing stye below:

Reference Copied to Clipboard.
Reference Copied to Clipboard.
Reference Copied to Clipboard.
Reference Copied to Clipboard.
Reference Copied to Clipboard.
Reference Copied to Clipboard.
Reference Copied to Clipboard.

Related Services

View all

DMCA / Removal Request

If you are the original writer of this essay and no longer wish to have your work published on the UKDiss.com website then please: