Drone Squadron Optimization: a Self-adaptive Algorithm for Global Numerical Optimization

Vinícius Veloso de Melo, Wolfgang Banzhaf

TL;DR

This paper introduces Drone Squadron Optimization (DSO), a novel self-adaptive metaheuristic inspired by artificial systems rather than nature. DSO features a "Command Center" that dynamically evolves the "firmware" (search strategies) of autonomous "drones" to optimize numerical problems, showing competitive performance against established methods.

What Problem Does This Paper Address?

The field of optimization heavily relies on metaheuristics, which are general-purpose algorithms for finding optimal solutions, especially when traditional calculus-based methods are not applicable (e.g., non-differentiable or noisy problems). Many existing metaheuristics are inspired by natural phenomena (like ant colonies or bird flocks). However, this reliance on specific natural behaviors can limit their flexibility. The authors propose a new paradigm, "artifact-inspired" optimization, to overcome this limitation by drawing inspiration from human-made systems, which are inherently more flexible and modifiable. This allows for a more dynamic and adaptive approach to optimization.

Methods

DSO is a population-based metaheuristic with two main components:

  • Drones: These are the agents that explore the search space (the "landscape" of the objective function). Each drone is not a solution itself but moves to a coordinate that represents a potential solution. Drones are organized into teams.
  • Command Center: This central unit supervises the drones. It collects data from the drones, analyzes it, and crucially, updates the drones' "firmware."

The core novelty lies in DSO's self-adaptation. Instead of just tuning parameters, DSO evolves the actual procedures (code) that the drones use to generate new candidate solutions. This "firmware" dictates how drones move and explore. The Command Center dynamically modifies this firmware during the optimization process, adapting the search strategy to the specific problem landscape. This is achieved by evolving the "perturbation/movement scheme," which defines how drones generate target coordinates. The paper describes this as a "generative hyper-heuristic approach" where code is evolved online.

Datasets

DSO was evaluated on the first ten benchmark functions from the CEC'2005 Special Session in Real Parameter Optimization. These functions are designed to present a diverse set of challenges, including multimodality, ruggedness, ill-conditioning, and interdependency. The experiments were conducted in 10 dimensions with a maximum of 100,000 objective function evaluations per problem.

Key Insights and Ideas

  • Artifact Inspiration: Moving away from nature-inspired algorithms to artifact-inspired ones offers greater flexibility. Human-made systems are designed for modification and adaptation, which translates well to creating dynamic optimization algorithms.
  • Evolving the "Firmware": The most significant insight is the ability to evolve the actual search procedures (code) rather than just parameters. This allows DSO to fundamentally change its exploration strategy on-the-fly, adapting to different problem characteristics.
  • Command Center's Role: The Command Center acts as a dynamic controller, not just a passive observer. Its ability to update drone firmware based on performance metrics (rank and boundary violations) is key to the self-adaptive nature of DSO.
  • Team-based Exploration: Organizing drones into teams with potentially different firmwares allows for diverse exploration strategies to be employed simultaneously, increasing the chances of finding global optima.

Key Results

DSO demonstrated competitive performance when compared to several state-of-the-art evolutionary and swarm optimization methods on the CEC'2005 benchmark functions. Statistical analysis (Friedman rank sum test and Nemenyi posthoc test) indicated that DSO performed comparably to other leading algorithms. While DSO achieved good results, it was noted that it sometimes generated inefficient perturbation schemes, leading to wasted objective function evaluations.

Limitations and Future Work

The authors acknowledge that DSO's current implementation, particularly its reliance on generating and evaluating code during optimization, can lead to slower processing times compared to methods with hard-coded strategies. A significant weakness identified is the generation of inefficient perturbation schemes, which wastes computational resources.

Future work will focus on:

  • Reducing the occurrence of poor perturbation schemes by incorporating learning mechanisms into DSO.
  • Further investigating the influence of various parameters on DSO's performance.
  • Exploring more sophisticated ways to update firmware, potentially moving beyond simple random generation of scalings and selections.
  • Expanding testing to a larger set of benchmark functions and different problem dimensions.

Summary updated

Abstract

This paper proposes Drone Squadron Optimization, a new self-adaptive metaheuristic for global numerical optimization which is updated online by a hyper-heuristic. DSO is an artifact-inspired technique, as opposed to many algorithms used nowadays, which are nature-inspired. DSO is very flexible because it is not related to behaviors or natural phenomena. DSO has two core parts: the semi-autonomous drones that fly over a landscape to explore, and the Command Center that processes the retrieved data and updates the drones' firmware whenever necessary. The self-adaptive aspect of DSO in this work is the perturbation/movement scheme, which is the procedure used to generate target coordinates. This procedure is evolved by the Command Center during the global optimization process in order to adapt DSO to the search landscape. DSO was evaluated on a set of widely employed benchmark functions. The statistical analysis of the results shows that the proposed method is competitive with the other methods in the comparison, the performance is promising, but several future improvements are planned.
BibTeX
@article{melo2018drone,
  author = {Vinícius Veloso de Melo and Wolfgang Banzhaf},
  title = {{Drone Squadron Optimization: a Self-adaptive Algorithm for Global Numerical Optimization}},
  journal = {Neural Computing and Applications},
  year = {2018},
  url = {https://openreview.net/forum?id=iCYG5y7TDx},
}

Loading related content...

Figure