Swarm Optimization with Genetic Algorithm

In the interest of academic integrity, I will not post my simulation code. The code for the genetic algorithm itself is here.

Optimization is an important class of problems and one method for the non-convex case is the genetic algorithm. In this project, I implemented a genetic algorithm in MATLAB to optimize the behavior of a swarm of drones.

As a caveat, there were a number of simplifications in the problem. All obstacles and targets were stationary; furthermore, all agents know the positions of all obstacles, targets, and other agents at all times. Additionally, the drones move by exerting a force in an arbitrary direction, effectively ignoring any constraints on their movement. While these simplifications eliminate any applicability of the results, we are nevertheless still left with a technically interesting problem.

The swarm strategy consists of a set of exponentially decaying attractive and repulsive forces exerted by each object in the space. Each drone computes their own total resulting force and then exerts a propulsive force to move in that direction. This is an effective strategy as evidenced by the (somewhat) respectable performance even in the first generation.

The genetic algorithm rapidly improved over this performance, converging to a much more successful design within 50 generations.

This optimized design maps all targets, loses no drones, and takes only 33 seconds to map all of the targets.