«Back to research topics list

Graph-based Problems

Graph-based problems described here concern finding characteristic subgraphs and finding good strategies for preventing the spread of a threat in a graph.

The Firefighter Problem (FFP)
The firefighter problem is a graph-based optimization problem that can be used for modelling the spread of fires, and also for studying the dynamics of epidemics. The original version of the firefighter problem was single objective.

Description of the problem:
  • Spread of fire is modelled on an undirected graph
  • Discrete-time model
  • Vertices are labeled:
       - ‘B’ – burning
       - ‘D’ – defended by firefighters
       - ‘U’ – untouched
  • Initially a certain number of nodes are burning (‘B’) and the remaining ones are untouched (‘U’)
  • At each time step:
       - Nf firefigters are assigned to the untouched (‘U’) nodes. These nodes become defended (‘D’)
       - Nodes adjacent to the burning nodes catch on fire (unless they are defended by firefighters)
  • The simulation stops when the fire is contained or when all undefended nodes are burning
  • Solution representation: a permutation which defines the order in which nodes are protected (the already burning ones are skipped)
  • Task: Find such an assignment that the maximum number of nodes is saved
A multiobjective version was proposed in a paper at the IDEAL 2014 Conference.
  • For each node v there are m different values vi(v), i = 1, …, m
  • The m objectives f i , i = 1, ..., m attained by a given solution are calculated as follows:
    where:
            vi(v) - the value of node v according to the i-th criterion,
            l(v) - the state of the node v.
  • Goal: maximize all the objectives
 An example for a permutation
P  = 3, 4, 2, 1, 6, 7, 8, 9, 10, 5
and the initial burning node #2 (click the images to enlarge)

t = 0

P  = 3, 4, 2, 1, 6, 7, 8, 9, 10, 5

t = 1

P  = 3, 4, 2, 1, 6, 7, 8, 9, 10, 5

t = 2

P  = 3, 4, 2, 1, 6, 7, 8, 9, 10, 5

t = 3

P  = 3, 4, 2, 1, 6, 7, 8, 9, 10, 5

t = 4

P  = 3, 4, 2, 1, 6, 7, 8, 9, 10, 5



ED-LS - A Heuristic Local Search for the Multiobjective Firefighter Problem
FFP problem instances used to test the ED-LS method are available for download here.



Simheuristics for the Multiobjective Nondeterministic Firefighter Problem
The research presented in a paper at the EvoStar 2016 Conference.

Highlights of the paper:
  • A non-deterministic version of the Firefighter Problem (FFP) was tackled
  • Fire spreaded from node to node with a fixed probability Psp ≤ 1
  • Multiple simulation runs were used to evaluate solutions
  • Simulation runs were implemented on the massively-parallel architecture of a GPU
  • Offline and online optimization modes were compared
  • Optimization was compared with heuristics determining which nodes to protect
  • Both optimization and heuristics can be useful for different values of Psp

An overview of an evolutionary algorithm using simulations for evaluation of specimens (click the image to enlarge)



The Sim-EA Algorithm with Operator Autoadaptation for the Multiobjective Firefighter Problem
The research presented in a paper at the EvoStar 2015 Conference.

Highlights of the paper:
  • A multiobjective version of the Firefighter Problem (FFP) was tackled
  • A multipopulation algorithm Sim-EA (presented in a paper at the IDEAL 2014 Conference) was used
  • Each subpopulation solves a scalarized version of the problem, but using a different weight vector
  • The performance of the Sim-EA algorithm was compared to the performance of the MOEA/D
  • A mechanism for auto-adaptation of operator probabilities (proposed in a paper at the IDEAL 2014 Conference) was used in both algorithms
  • The Sim-EA algorithm attained better results than the MOEA/D

An overview of elements of the Sim-EA algorithm (click the image to enlarge)



Auto-adaptation of Genetic Operators for Multi-objective Optimization in the Firefighter Problem
The research presented in a paper at the IDEAL 2014 Conference.

Highlights of the paper:
  • A multiobjective version of the Firefighter Problem (FFP) was proposed
  • An evolutionary algorithm with a mechanism for auto-adaptation of operator probabilities was proposed
  • 10 crossover operators: CX, LOX, MOX, NWOX, OBX, OX, PBX, PMX, PPX and UPMX
  • 5 mutation operators: displacement, insertion, inversion, scramble and transpose

Success rates of crossover operators plotted against the generation number for the instance with Nv = 1000 vertices and Ns = 100 fire starting points (click the image to enlarge)



Papers on evolutionary graph mining for detection of suspicious banking transaction
The research presented in two papers, at the FedCSIS 2011 Conference and in a journal paper.

Highlights of the papers:
  • Papers concern the problem of detecting suspicious banking transactions
  • Based on known money laundering schemes a model for detecting suspicious transactions was proposed
  • The model was parameterized using fuzzy numbers
  • An evolutionary algorithm was used for optimizing the parameters of the model
  • Fuzzy matching of the model to subgraphs of the transactions graph allowed recommending suspicious transactions for closer inspection

A fragment of the transactions graph (click the image to enlarge)


The subgraph model used in the paper (click the image to enlarge)
«Back to research topics list