Resource allocation in military operations - optimization using a genetic algorithm

Abstract

The purpose of this study was to look at methods for resource allocation in military operations. In this report it is shown how a military operation can be viewed as a project, and how methods from project management can be used to automatically generate activity schedules for such operations. Mathematical models of this type are NP-hard, i.e. not solvable within reasonable time. Thus, heuristic algorithms must be used. Such algorithms are fast and flexible. However, solutions found by heuristic algorithms can not be proven to be optimal. The genetic algorithm was chosen for this study. This algorithm spans out the solution space to a larger extent than other heuristic algorithms. Other advantages of the genetic algorithm are that it seems to be effective as well as robust against getting trapped in local optima. The genetic algorithm developed in this study was compared to classical optimization methods by solving a very small version of the resource allocation problem. Results showed that the genetic algorithm was able to find an optimal solution and run-time was significantly shorter than for the exact optimization model. The genetic algorithm was used on a larger problem close to what can be found in real life. It was able to find optimal solutions. The solutions will not necessarily be the best in practice, but in an operational context they may be used as a basis for military decision making

Hensikten med denne studien var å se på metoder og modeller for ressursallokering i militære operasjoner. I rapporten vises det hvordan en slik operasjon kan sees på som et prosjekt, og hvordan metoder fra prosjektstyring kan benyttes for automatisk å generere aktivitetsplaner. Matematiske modeller av denne typen er "NP-hard". Det vil si at de ikke kan løses innenfor rimelig tid. I slike tilfeller blir ofte heuristiske optimeringsmetoder tatt i bruk. Slike algoritmer er effektive og fleksible, men de kan ikke finne løsninger som beviselig er optimale. I denne studien ble en genetisk algoritme valgt for å løse ressursallokeringsproblemet. Denne typen algoritme spenner ut løsningsrommet i større grad enn andre heuristiske metoder. I tillegg er den effektiv, og den har gode metoder for å ikke la seg fange i lokale optima. Algoritmen som ble utviklet gjennom denne studien, ble sammenlignet med eksakt optimering ved at en liten versjon av ressursallokeringsproblemet ble løst ved hjelp av begge metoder. Resultatene viste at den genetiske algoritmen var i stand til å finne optimale løsninger, og at kjøretiden var signifikant kortere enn for den eksakte optimeringsmetoden. Den genetiske algoritmen ble også brukt til å løse et større og mer virkelighetsnært problem. Optimale løsninger ble funnet. Løsningene er ikke nødvendigvis de beste i praksis, men i en operativ sammenheng vil de kunne brukes som utgangspunkt i en militær beslutningsprosess.