Optimization Online


Multidirectional Physarum Solver: an Innovative Bio-inspired Algorithm for Optimal Discrete Decision Making

Luca Masi(luca.masi***at***strath.ac.uk)
Massimiliano Vasile(massimiliano.vasile***at***strath.ac.uk)

Abstract: This paper introduces a new bio-inspired algorithm for optimal discrete decision making, able to incrementally grow and explore decision graphs in multiple directions. The heuristic draws inspiration from the idea that building decision sequences from multiple directions and then combining the sequences is an optimal choice if compared with a unidirectional approach. The behaviour of the slime mould Physarum Polycephalum, a large single-celled amoeboid organism, is used as basic heuristic for graph exploration and growth. The algorithm is here applied to the solution of classical problems in operational research, i.e. symmetric Travelling Salesman and Vehicle Routing Problems, with a number of cities ranging from 10 to 199. Simulations on selected test cases demonstrate that a multidirectional solver performs better than a unidirectional one. The ability to evaluate decisions from multiple directions enhances the performance of the solver in the construction and selection of optimal decision sequences.

Keywords: Combinatorial optimization, Decision analysis, Physarum, Multidirectional, Traveling salesman problem, Vehicle routing problem

Category 1: Combinatorial Optimization

Citation: Report 01012013, University of Strathclyde, 75 Montrose Street G1 1XJ, Glasgow, UK

Download: [PDF]

Entry Submitted: 01/25/2013
Entry Accepted: 01/27/2013
Entry Last Modified: 01/25/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society