Artificial Bee Colony

in Artificial Bee Colony

Introduction

xlOptimizer fully implements Artificial Bee Colony (ABC), a new stochastic swarm intelligence algorithm inspired by the foraging behavior of honey bees. ABC was introduced by Karaboga and Basturk [1] and was later employed in a plethora of applications.

How does it work?

In ABC, the colony of artificial bees consists of three groups: employed bees, onlookers and scouts. The first half of the colony consists of the employed artificial bees and the second half includes the onlookers. For every food source, there is only one employed bee, i.e. the number of employed bees is equal to the number of food sources around the hive. The employed bee whose the food source has been abandoned becomes a scout. In ABC algorithm, the position of a food source represents a possible solution to the optimization problem and the nectar amount of a food source corresponds to the quality (fitness) of the associated solution. 

Mathematical formulation

At the first step, the ABC generates a random initial distribution of SN/2 solutions (food source positions), where SN denotes the total number of bees. Each solution is a  D-dimensional vector.

After initialization, the food source positions are subjected to repeated cycles of improvement. An employed bee produces a modification on the position (solution) in her memory depending on the local information and tests the nectar amount (fitness value) of the new source (new solution). Provided that the nectar amount of the new one is higher than that of the previous one, the bee memorizes the new position and forgets the old one. Otherwise she keeps the position of the previous one in her memory.

Next, the employed bees share the nectar information of the food sources and their position information with the onlooker bees on the dance area. An onlooker bee evaluates the nectar information taken from all employed bees and chooses a food source with a probability related to its nectar amount. As in the case of the employed bee, she produces a modification on the position in her memory and checks the nectar amount of the candidate source. Providing that its nectar is higher than that of the previous one, the bee memorizes the new position and forgets the old one.

Usual parameter values are the following: (a) Colony size (populations) = 20-50 bees, (b) limit before a food source becomes abandoned=POP*VARS/2.

Options in xlOptimizer add-in

The following options are available in xlOptimizer add-in. Note that whenever an asterisk (*) is indicated in a text field, this means that the field accepts a formula rather than a certain value. The formula is identical to Microsoft Excel's formulas, without the preceding equal sign '='. Also, the function arguments are always separated by comma ',' while the dot '.' is used as a decimal point.

Artificial Bee Colony xloptimizer options step 1 

General settings

  • Name: the name of the scenario to be run. It should be descriptive but also concise, as a folder with the same name will be (optionally) created, which will hold the log files for further statistical analysis.
  • Active: select whether the scenario is active or not. If it is active, it will be run in sequence with the other active scenaria. In the opposite case, it will be ignored. This is very helpful when you experiment with settings. 

Seeds and repetitions

Metaheuristic algorithms are based on random number generators. These are algorithms that produce a different sequence of random numbers for each seed they begin with. A seed is just an integer, and a different seed will produce a different evolution history with a different outcome. Robust metaheuristic algorithms should, on average, perform the same no matter what the seed is.

  • Random number generator: select the random number generator to be used. The Mersenne Twister is default. The following options are available:
    • NumericalRecipes: Numerical Recipes' long period random number generator of L’Ecuyer with Bays-Durham shuffle and added safeguards
    • SystemRandomSource: Wraps the .NET System.Random to provide thread-safety
    • CryptoRandomSource: Wraps the .NET RNGCryptoServiceProvider
    • MersenneTwister: Mersenne Twister 19937 generator
    • Xorshift: Multiply-with-carry XOR-shift generator
    • Mcg31m1: Multiplicative congruential generator using a modulus of 2^31-1 and a multiplier of 1132489760
    • Mcg59: Multiplicative congruential generator using a modulus of 2^59 and a multiplier of 13^13
    • WH1982: Wichmann-Hill's 1982 combined multiplicative congruential generator
    • WH2006: Wichmann-Hill's 2006 combined multiplicative congruential generator
    • Mrg32k3a: 32-bit combined multiple recursive generator with 2 components of order 3
    • Palf: Parallel Additive Lagged Fibonacci generator
  • Random repetitions: use this option if you wish the program to select random seeds for every run. Also, select the number of repetitions. If you wish to perform a statistical analysis of the results, a sample of 30 runs should be sufficient.
  • Specific seed: use this option if you wish to use a selected range of integers as seeds. Note that seeds are usually large negative integers. 

Log files

  • Create log files: select whether you wish to create a log file for each run. This is imperative if you wish to statistically analyze the results. If you are only interested in the best result out of a certain number of runs, disabling this will increase performance (somewhat).
  • Delete existing log files before the analysis: select this option if you want the program to delete all existing (old) log files (with the extension ".output") in the specific folder, before the analysis is performed.
  • Save in relative path: select this option to create and use a folder relative to the spreadsheet's path. The name of the folder is controlled in the General Settings > Name.
  • Save in absolute path: select this option to create and use a custom folder. Press the corresponding button with the ellipses "..." to select the folder. 

Termination criteria

Each scenario needs a specific set of termination criteria. You can use an excel-like expression with the following variables (case insensitive):

  • 'BEST_1', 'BEST_2', etc represent the best value of the objective function 1, 2, etc in the population.
  • 'AVERAGE_1', 'AVERAGE_2', etc represent the average value of the objective function 1, 2, etc in the population.
  • 'WORST_1', 'WORST_2', etc represent the worst value of the objective function 1, 2, etc in the population.
  • 'MIN_1', 'MIN_2', etc represent the minimum value of the objective function 1, 2, etc in the population.
  • 'MAX_1', 'MAX_2', etc represent the maximum value of the objective function 1, 2, etc in the population.
  • 'FE' represents the function evaluations so far.
  • 'TIME_MIN' represents the elapsed time (in minutes) since the beginning of the run.
  • 'BEST_REMAINS_FE' represents the number of the last function evaluations during which the best solution has not been improved.

The default formula is 'OR(FE>=20000, TIME_MIN>10)' which means that the run is terminated when the number of function evaluations is more than 20000 or the run has lasted more than 10 minutes. 

Algorithm

  • Algorithm: select the algorithm to be used in the specific scenario. In this case 'Simulated Annealing' is selected.
  • Comparison of solutions: select whether feasibility (i.e. the fact that a specific solution does not violate any constraints) is used in the comparison between solutions. The following options are available:
    • By objective function only: feasibility is ignored, and only the objective function (potentially including penalties from constraint violations) is used to compare solutions.
    • By objective function and feasibility: the objective function (potentially including penalties from constraint violations) is used to compare solutions, but in the end, a feasible solution is always preferred to an infeasible one. 

Artificial Bee Colony

The following options are specific to Artificial Bee Colony. 

  • Population. The total population of bees in the colony. You can use an excel-like expression with the following variables (case insensitive):
    • 'VARS' represents the number of variables (i.e. the dimensionality of the problem).

Default value is '50'.

  • Limit. The limit of steps before a food source becomes abandoned. You can use an excel-like expression with the following variables (case insensitive):
    • 'POP' represents the colony size (i.e. total population)
    • 'VARS' represents the number of variables (i.e. the dimensionality of the problem).

Default value is 'POP*VARS/2'. 

References

[1] Karaboga D., Basturk B. On the performance of Artificial Bee Colony (ABC), Appl Soft Comp 2008;8(1):687–697.