Binary Optimisation with Urban Pigeon-inspired Model

1 collaborator

WHAT IS IT?

This is an extension of an agent-based model for numeric real-valued unconstraint optimisation to binary domains, inspired in the foraging behaviour of urban pigeons (see [1]). Optimisation problems with binary domains contemplate variables taking values 0 or 1, representing decisions associated to conditions being false or true. Hence, these kind of domains are of interest in many applications in engineering and management.

The model maintains an internal representation of the pigeons locations which is transformed to binary values via a threshold function. The movement rules of the internal representation are identical to the continuous-valued version, and the inspiration of the original method is sustained: a leader pigeon located at a promising source of food is pursued by a flock of follower pigeons, while simultaneously other pigeons are walking around exploring the space for new sources of food too. Food sources in this context refers to maximal values of the binary cost function that is being optimised. The details of the binary version of the algorithm is given in [2].

HOW IT WORKS

A benchmark of binary problems is included. Each PROBLEM consists of finding a bitstring that maximises a cost function (currently there are three functions: "oneMax", "powSum" and "squareWave", see definitions in [2]).

Pigeons are characterised by an internal array of continuous-valued coordinates of size DIM. These coordinates are mapped to binary coordinates via a cut-off threshold called TAU. This is a mechanism similar to the genotype-to-phenotype mapping widely used in evolutionary algorithms (here, implemented as the GPM code block).

Two types of pigeon breeds were defined, namely followers and walkers. The initial population is created with an amount of pigeons given by the parameter POP-SIZE, with the subset of walkers assigned randomly in proportion to the parameter WALKERS-RATE; the remainder pigeons are assigned to the subset of followers.

At each step of the simulation, the model performs four simple actions: find the leader, move the followers, move the walkers and update the best solution found so far. These actions correspond to the following routines: UPDATE-LEADER (chooses as leader pigeon the one having the best fitness and updates the best fitness ever if necessary), FOLLOW-MOVE (moves each follower towards the leader in one randomly chosen dimension, with a step-size ALPHA plus a random shift in its orientation due to wind or collisions), and WALK-MOVE (moves each walker around randomly with a step-size SIGMA, again in one randomly chosen dimension). These two movement rules correspond to the exploration/exploitation mechanisms of the search algorithm (see [2]).

HOW TO USE IT

Firstly choose an optimisation PROBLEM to be solved, from the pull-down list. For any of these problems, then define a particular dimension DIM. Additionally, choose the algorithm parameters POP-SIZE, WALKERS-RATE, TAU, ALPHA and SIGMA. You can also set the termination criterium MAX-TICKS. Then press SETUP, then GO.

The initial genotypes of the population of pigeons will be assigned randomly and their phenotypes would be obtained. Afterwards, at each time step pigeons move according to its role, the population fitness is updated, and if needed, the leader is re-assigned. The simulation view area will display the phenotype, or bitstring, of the best pigeon found so far. This bitstring is reshaped and displayed as a 2D binary matrix.

The output monitors show the fitness (cost) of the true solution for the problem, the best fitness ever found by the algorithm during the simulation, and the fitness associated to the current leader. If the algorithm is able to find the true solution, the simulation stops and the BEST-TICK and RUNTIME monitors will display a "!!!" sign inserted behind their actual values. Otherwise the simulation finishes when MAX-TICKS are elapsed.

Lastly, the model also outputs the plot of the leader fitness vs time, the plot of fitness of the best solution found vs time, the histogram of fitness of the population and the plot of flock cohesion vs time if the COHESION? switch is enabled. The latter implies an additional cost to the running time, as the model needs to compute distances between all the pigeons in the follower's flock.

THINGS TO NOTICE

Although the actual locations of the pigeons can not be visualised (because the problems have high-dimensional search spaces), one can notice that the leader and the flock move out from one local minima to another. This occurs because every certain number of ticks, the entire population become walkers wandering about other regions of the search space. This phenomenon is explained by the fitness variation of the leader pigeon during the simulation timeline, as it can be seen in the corresponding plot. Nonetheless, the best found ever solution always has an increasing fitness as it can be verified in its respective plot. Besides, the flock formation behaviour is suggested by the periodic patterns that appear in the cohesion plot.

Lastly, we remark that the pattern of solutions showed in the view area resemble a blacked display for the "oneMax" and "powSum" problems, and a half-and-half black and white display for the "squareWave" problem, as it was expected from their mathematical definitions. Notice that for the "powSum" problem, the last bits to be set are those in the bottom of the view (the least significant loci of the bitstring), as they contribute the least to its cost function.

THINGS TO TRY

Experiment with different DIM sizes for each problem and compare if a different configuration of parameters is needed. For starters, we suggest a typical configuration of: POP-SIZE=40, WALKERS-RATE=0.2, ALPHA=0.9, SIGMA=0.1, MAX-TICKS=40000.

EXTENDING THE MODEL

An interesting question arising is if the convergence speed of the algorithm can be improved without compromising its simplicity for practical purposes, for example using dynamic updates of the step sizes of pigeon movements.

Another related idea worth of exploring is if convergence speedup an be achieved by hybridising the model with local search techniques.

Finally, it would be appealing to include additional binary problems and try to solve them with this model. For this purpose, users only need to add a code block that computes the cost function of the new problem, based on the bitstring phenotype of the pigeons. We suggest for example, studying combinatorial problems such as the N-queens or the Knapsack problem.

RELATED MODELS

Modeling Commons -> Simple Genetic Algorithm, see [3]. Modeling Commons -> Urban Pigeon-inspired Model for Unconstraint Optimisation, see [4].

CREDITS AND REFERENCES

Authors:

Sergio Rojas-Galeano

email: srojas@udistrital.edu.co

Version 1.4

Licenses:

The model code is licensed as GNU General Public License (GPLv3) (see https://www.gnu.org/licenses/gpl-3.0.txt)
This Info Tab document is licensed as CC BY-NC-ND (see https://creativecommons.org/licenses/by-nc-nd/4.0/)

References:

[1] Garzon, M., and Rojas-Galeano, S. (2019, November). An Agent-Based Model of Urban Pigeon Swarm Optimisation. In 2019 IEEE Latin American Conference on Computational Intelligence (LA-CCI) (pp. 1-6). IEEE. doi: 10.1109/LA-CCI47412.2019.9036758. https://ieeexplore.ieee.org/document/9036758

[2] Rojas-Galeano, S. (2019, October). Binary optimisation with an urban pigeon-inspired swarm algorithm. In Workshop on Engineering Applications (pp. 190-201). Springer. https://link.springer.com/chapter/10.1007/978-3-030-31019-6_17

[3] Stonedahl, F. and Wilensky, U. (2008). NetLogo Simple Genetic Algorithm model. http://ccl.northwestern.edu/netlogo/models/SimpleGeneticAlgorithm. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.

[4] Rojas-Galeano, S. and Garzon, M. (2020). Urban Pigeon-inspired Model for Unconstraint Optimisation. http://modelingcommons.org/browse/one_model/6390.

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

;; ------------------------------------------------------------------------------
;; Binary version of PUPI optimiser
;;
;; A model by Sergio Rojas-Galeano
;; v1.4 Copyright (c) July 2020 The author
;; Correspondance email: srojas@udistrital.edu.co
;; Universidad Distrital Francisco Jose de Caldas, Bogota, Colombia
;;
;; An extension of Urban Pigeon-inspired Model for Unconstraint Optimisation
;; v1.16 (2020) by Sergio Rojas-Galeano and Martha Garzón
;; http://modelingcommons.org/browse/one_model/6390
;;
;; This program is free software: you can redistribute it and/or modify
;; it under the terms of the GNU General Public License (GPLv3)
;; (see license at: https://www.gnu.org/licenses/gpl-3.0.txt)
;;
;; The model is made publicly available in the hope that it will be useful
;; to modelers, but WITHOUT ANY WARRANTY whatsoever (see license for details).
;; ------------------------------------------------------------------------------

;; Definition of global variables
globals[
  ;; PUPI globals
  pigeons               ; agentset of all pigeons (walkers+followers)
  pupi-leader           ; best pigeon in current iteration
  pupi-best-solution    ; best solution found by PUPI ever
  pupi-best-fitness     ; fitness of best solution found ever
  pupi-best-tick        ; tick where best solution was found
  pupi-best-time        ; runtime where best solution was found
  pupi-runtime          ; overall algorithm runtime (ms)
  pupi-cohesion         ; flock cohesion

  ;; Problem globals
  true-best-fitness     ; the ground-truth fitness of optimum solution
  wave-signal
]

;; PUPI breeds
breed [walkers walker]
breed [followers follower]

;; Pigeon attributes for binary problems
turtles-own [
  xcors    ; a d-dimensional list of coordinates (i.e "location" of the pigeon)
  xbits    ; a binary mapping of the coordinates (genotype-to-phenotype representation)
  fitness  ; value of cost function for the pigeon
]

;; Execute one iteration of the optimisation procedure

to go
  reset-timer
;    ifelse ticks mod 1000 > 800 [
  ifelse ticks mod 500 > 400 [
    ;; PUPI wild search (starvation move)
    ask pigeons [ walk-move ]
  ][
    ;; PUPI normal foraging mode
    ask pigeons [ compute-fitness ]
    update-leader
    ask followers [ follow-move ]
    ask walkers [ walk-move ]
  ]
  set pupi-runtime pupi-runtime + timer

  ;; The following steps do not count as runtime; they are ancilliary to the algorithm
  if cohesion? [ set pupi-cohesion sum map [ bits -> hamming-distance [xbits] of pupi-leader bits ] [xbits] of followers ]
  update-display
  tick
  if (ticks > max-ticks) or ((pupi-best-tick > 0) ) [ stop ]
end 

;; Compute fitness of pigeon depending on selected problem

to compute-fitness
  gmp
  run problem     ; call the procedure corresponding to problem (see benchmarks below)
end 

;; Genotype-to-phenotype mapping

to gmp
  set xbits map [x -> ifelse-value (x < tau) [0] [1] ] xcors   ; apply binarisation according to \tau threshold
end 

;; Find current leader and update best solution ever

to update-leader
  set pupi-leader max-one-of pigeons [fitness]

  ;; update solution and statistics if the new leader is fitter than ever
  if [fitness] of pupi-leader > pupi-best-fitness [    ; maximises by default. Change to "<" to minimise instead
    set pupi-best-solution [xbits] of pupi-leader
    set pupi-best-fitness [fitness] of pupi-leader

    ;; verify stopping condition
    if [fitness] of pupi-leader = true-best-fitness [
      set pupi-best-tick ticks
      set pupi-best-time pupi-runtime
    ]
  ]
end 

;; Move followers towards pigeon leader

to follow-move
  let index random dim  ; choose a random coordinate to modify
  let xi item index xcors
  let delta-xi (item index [xcors] of pupi-leader) - (item index xcors)
  set xcors replace-item index xcors ( (xi + alpha * delta-xi) + sigma * random-normal 0 0.1 ) ;mod 1
end 

;; Move walkers around

to walk-move
  let index random dim  ; choose a random coordinate to modify
  let xi item index xcors
  set xcors replace-item index xcors ((xi + sigma * random-normal 0 1) mod 1)
end 

;; Get ready to go

to setup
  clear-all
  setup-problem
  setup-display
  create-walkers pop-size * walkers-rate       ;; create walkers accroding walkers-rate
  create-followers pop-size - count walkers    ;; create followers accroding walkers-rate
  set pigeons (turtle-set followers walkers)   ;; populate pigeons agentset
  ask pigeons [
    set xcors n-values dim [ random-float 1 ]  ;; set pigeon initial random location (coordinates)
    compute-fitness                            ;; set pigeon initial fitness value
    hide-turtle                                ;; no need to show turtles
  ]
  initial-solution
  update-leader
  update-display
  reset-ticks
end 

;; Define true optimal cost and other global variables

to setup-problem
  set true-best-fitness ( ifelse-value
    problem = "oneMax" [ dim ]                   ; the number of bits that must be set on
    problem = "powSum" [ dim * (dim + 1) / 2 ]   ; in a all-ones bitstring, the sum of n powers is equals to n(n+1)/2
    problem = "squareWave" [ dim ]               ; the number of bits that should be identical to those in the wave signal
  )
  if problem = "squareWave" [
    let root sqrt dim
    let index range dim
    set wave-signal map [ i -> -1 * (2 * int (i / root) - int (2 * i / root)) ] index
  ]
end 

;; Resize view area according to problem dimension

to setup-display
  let side-size sqrt dim
  resize-world 0 (side-size - 1) 0 (side-size - 1)
  set-patch-size 300 / side-size
end 

;; Initialise best solution

to initial-solution
  let anyone one-of pigeons       ;; choose any pigeon as initial solution
  set pupi-best-solution [xbits] of anyone
  set pupi-best-fitness [fitness] of anyone
end 

;; Show current best solution on display

to update-display
  ask patches [
    let index  (max-pxcor + 1) * pycor + pxcor  ; obtain linear location of bit corresponding to patch coordinates
    set pcolor ifelse-value (item index pupi-best-solution = 0) [white] [black]
  ]
end 

;; Compute hamming distance between bitstrings

to-report hamming-distance [xbits1 xbits2]
  report (length remove true (map [ [b1 b2] -> b1 = b2 ] xbits1 xbits2))
end 

;;;;;;;; Benchmark problems ;;;;;;;;;

;; oneMax computes the sum of the bits

to oneMax
  set fitness (sum xbits)
end 

;; powSum computes the sum of power exponents where bits are on

to powSum
  let powers (range 1 (dim + 1) )
  set fitness sum (map [ [power bit] -> power * bit ] powers xbits)
end 

;; squareWave computes the number of bits identical to those in the wave-signal of size dim

to squareWave
  set fitness sum (map [ [wave bit] -> ifelse-value wave = bit [1][0] ] wave-signal xbits)
end

There are 19 versions of this model.

Uploaded by	When	Description	Download
Sergio Rojas-Galeano	over 4 years ago	Changed fitness histogram caption	Download this version
Sergio Rojas-Galeano	over 4 years ago	Changed fitness histogram caption	Download this version
Sergio Rojas-Galeano	over 4 years ago	v1.4	Download this version
Sergio Rojas-Galeano	over 4 years ago	v1.4	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab encoding error fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Info tab fixed	Download this version
Sergio Rojas-Galeano	over 4 years ago	Initial upload	Download this version

Attached files

File	Type	Description	Last updated
Binary Optimisation with Urban Pigeon-inspired Model.png	preview	Preview for 'Binary Optimisation with Urban Pigeon-inspired Model'	over 4 years ago, by Sergio Rojas-Galeano	Download
PUPIBinary_UserGuide.pdf	pdf	User guide	over 4 years ago, by Sergio Rojas-Galeano	Download

This model does not have any ancestors.

This model does not have any descendants.

NetLogo