Explore: An Optimisation Algorithm

Objective: To optimize a function or to search for a solution in a finite ‘n’ dimensional space.

Requirements: A fitness function to assign fitness/correctness of a particular solution

Terms:

  • ‘N’ dimensional space: a function having n parameters/variables. The end points of each dimension are interconnected. That is, if x ranges from 0-9 then 9+1 would be 0 and 0-1 would be 9.
  • Population: A collection of solutions/individuals
  • Individuals: A particular solution to the function being optimized
  • Positions: A particular individual occupies a single point in the space which corresponds to a specific solution. It is basically an array of size ‘m’ and is associated with each individual.
  • Velocities: An individual’s coordinate can have a velocity or +1, 0 or -1. Each coordinate value is added this much after each loop. It is basically an array of size ‘m’ and is associated with each individual.
  • Orientation of velocity: It is changing the velocity of an individual so that when its position is updated it may be as close to best solution as possible. Example- if an individual has position (3,2,9) and he has to orient his velocity to position (1,5,9) then the velocity of the individual will be changed to (-1,+1,0). It enables the individual to reach the best solution.
  • Best individual: An individual having highest fitness value
  • Worst individual: An individual having smallest fitness value
  • Patience value: It is a globally constant value which is associated with each individual. It tracks if an individual has lost his patience for searching the best algorithm. Or number of iterations is he allowed being a target individual without making any progress.
  • Progress value: It is a value which is associated with each individual. It tracks if an individual is progressing (in terms of fitness) or not.
  • Random individual: These individuals move in the search space randomly
  • Target individual: These individuals move in the search space towards the currently best location (location corresponding to largest fitness)
  • Swapping: It is an operation which will interchange the positions of two individuals without changing their group.

Algorithm: Let us take the function as an ‘n’ dimensional space and let the fitness denote the altitude in this space. And then, the objective of the algorithm is to find the highest point globally. The coordinates of this space correspond to a unique solution to the function.

  • Let us have a ‘n’ dimensional
  • Generate a population of ‘m’ number of individuals.
  • Place them at random positions throughout the space. That is, assign them random coordinates. This corresponds to generating random solutions. That is, associate an array of (p1, p2, p3……pn) with each individual.
  • Assign them random velocities. That is, associate an array of (v1, v2, v3……vn) with each individual. A velocity range is predefined preferably it must lie between -1 and 1
  • Make two groups of these individuals according to a predefined fixed ratio preferably 1:1. These two groups are:
    • Random group
    • Target group
  • All the individuals are assigned their respective patience values which is little different from main patience value (globally constant) according to randomness specified. Patience must be greater than 1. Progress=True is also allotted to an individual.
  • Loop until best solution is found or a fixed condition is met
    • Fitness of all individuals is calculated and assigned
    • A list of worst random individuals on the basis of their fitness is made. Example of this list: [{1st individual: fitness=10}, {2nd individual:fitness=19}, …, {last random individual: fitness=highest of all random individuals}]
    • If this is not the first iteration of loop
      • For all individuals: If current fitness>last fitness then Progress=True else Progress=False
    • For target group individuals only
      • If Progress=False AND Patience=0 then swap the individual with the next worst individual in random group. (The counter is increased in the list of worst random individual)
      • If Progress=True then set Patience value to its initial value
      • Else Patience=Patience-1
    • The position of best individual is found out and made available globally
    • The next worst random individual is assigned the position of best individual
    • The velocity of best individual is made to be zero. That is, best individual is fixed to its position
    • For target group: The individuals of this group orient their velocities towards the best solution
    • For random group: Do nothing
    • Update the positions of all individuals by adding value of velocities to their current
  • Return the best position of the best individual as the solution

This algorithm is kind a hybrid between hill climbing algorithm and genetic algorithm. And also, the random group ensures that the algorithm is not trapped in local maxima forever.

Please Note: You may use or modify this algorithm provided you give me (i.e. Paras Chopra) credit wherever I deserve.

Source Code: An implementation of this algorithm is available in the language Python. Click here to download it.