# Binary Optimisation with Urban Pigeon-inspired Model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)

## 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

Copyright (c) July 2020

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

;; ------------------------------------------------------------------------------ ;; 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.

## 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' | about 4 years ago, by Sergio Rojas-Galeano | Download |

PUPIBinary_UserGuide.pdf | User guide | about 4 years ago, by Sergio Rojas-Galeano | Download |

This model does not have any ancestors.

This model does not have any descendants.