# Binary Optimisation with Urban Pigeon-inspired Model

### Tags

binary optimization

Tagged by Sergio Rojas-Galeano over 2 years ago

bio-inspired model

Tagged by Sergio Rojas-Galeano over 2 years ago

meta-heuristic

Tagged by Sergio Rojas-Galeano over 2 years ago

optimization

Tagged by Sergio Rojas-Galeano over 2 years ago

swarm algorithm

Tagged by Sergio Rojas-Galeano over 2 years ago

Visible to everyone | Changeable by everyone
Model was written in NetLogo 6.1.0 • Viewed 218 times • Downloaded 14 times • Run 0 times

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

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.

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)
;;
;; 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)
][
;; PUPI normal foraging mode
]
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

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

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

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

Sergio Rojas-Galeano over 2 years ago Changed fitness histogram caption Download this version
Sergio Rojas-Galeano over 2 years ago Changed fitness histogram caption Download this version
Sergio Rojas-Galeano over 2 years ago Info tab encoding error fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version
Sergio Rojas-Galeano over 2 years ago Info tab fixed Download this version