Methods for Network Optimization and Parallel Derivative-free Optimization
Per-Magnus Olsson · Linköping studies in science and technology. Dissertations · 2014
This thesis is divided into two parts that each is concerned with a specific problem.The problem under consideration in the first part is to find suitable graph representations, abstractions, cost measures and algorithms for calculating placements of unmanned aerial vehicles (UAVs) such that they can keep one or several static targets under constant surveillance.Each target is kept under surveillance by a surveillance UAV, which transmits information, typically real time video, to a relay UAV.The role of the relay UAV is to retransmit the information to another relay UAV, which retransmits it again to yet another UAV.This chain of retransmission continues until the information eventually reaches an operator at a base station.When there is a single target, then all Pareto-optimal solutions, i.e. all relevant compromises between quality and the number of UAVs required, can be found using an efficient new algorithm.If there are several targets, the problem becomes a variant of the Steiner tree problem and to solve this problem we adapt an existing algorithm to find an initial tree.Once it is found, we can further improve it using a new algorithm presented in this thesis.The second problem is optimization of time-consuming problems where the objective function is seen as a black box, where the input parameters are sent and a function value is returned.This has the important implication that no gradient or Hessian information is available.Such problems are common when simulators are used to perform advanced calculations such as crash test simulations of cars, dynamic multibody simulations etc.It is common that a single function evaluation takes several hours.Algorithms for solving such problems can be broadly divided into direct search algorithms and model building algorithms.The first kind evaluates the objective function directly, whereas the second kind builds a model of the objective function, which is then optimized in order to find a new point where it is believed that objective function has a good value.Then the objective function is evaluated in that point.Since the objective function is very time-consuming, it is common to focus on minimizing the number of function evaluations.However, this completely disregards the possibility to perform calculations in parallel and to exploit this we investigate different ways parallelization can be used in model building algorithms.Some of the ways to do this are to use several starting points, generate several new points in each iteration, new ways of predicting a point's value and more.We have implemented the parallel extensions in one of the state of the art algorithms for derivative-free optimization and report results from testing on synthetic benchmarks as well as from solving real industrial problems.v vi Populärvetenskaplig sammanfattningAvhandlingen består av två delar.Den första delen behandlar problem relaterade till obemannade flygfarkoster (UAVer) och handlar om att hitta platser där dessa kan placeras för att filma ett eller flera mål.I fallet med ett mål bildas en kedja där en UAV övervakar målet och sänder filmen till en annan UAV, vilken sänder filmen till en tredje, som i sin tur sänder den till en fjärde o.s.v.Så fortgår det tills filmen når en basstation där en användare tar emot den.I fallet med flera mål vill man t.ex.hitta placeringar av UAVerna så att det krävs så få UAVer som möjligt för att övervaka alla mål samtidigt.Att placera UAVerna har två delproblem.Det första är att bedöma vad som är lämpliga positioner, samt att avgöra hur bra det fungerar att sända film mellan positionerna, om det överhuvudtaget bedöms som möjligt.Det andra problemet är att hitta effektiva metoder för att beräkna UAVernas placering.I avhandlingen presenteras nya metoder för att beräkna var UAVerna ska placeras, både i fallet med ett mål och i fallet med flera mål.De utvecklade metoderna har implementerats i ett system för obemannade flygfarkoster.Avhandlingens andra del handlar om optimering av tidskrävande problem, där funktionen som ska optimeras ses som en svart låda, eftersom man inte vet hur beräkningarna görs.Sådana problem uppkommer ofta i samband med utveckling av mekaniska produkter.Ofta görs en mycket stor mängd beräkningar, vars resultat beror på varandra.För att få fram en så bra produkt som möjligt, görs många och noggranna beräkningar, vilket leder till att beräkningarna tar mycket lång tid.Det är inte ovanligt att en enda beräkning av funktionen tar flera timmar.Optimering används för att hitta den bästa produkten, givet att denna ska uppfylla vissa krav.Eftersom man vet så lite om funktionen så använder optimeringsalgoritmen modeller av funktionen, vilka anses giltiga inom ett begränsat område.Eftersom varje beräkning är mycket tidskrävande är det vanligt att man fokuserar på att minimera antalet gånger funktionen beräknas.Betänker man däremot att moderna datorer kan utföra flera beräkningar parallellt inser man att det viktiga är att minska antalet gånger en eller flera punkter beräknas parallellt.Om vi kan beräkna fem punkter parallellt istället för två sekventiellt har vi inte bara sparat tid utan också fått mera information om funktionen.I avhandlingen presenterar vi olika sätt att minska tiden för att uppnå ett bra resultat genom att utföra beräkningarna parallellt.Vi undersöker hur man kan bygga modellen parallellt, använda flera olika startpunkter samtidigt, samt hur man kan generera flera punkter vilkas värden beräknas parallellt.Vidare diskuterar vi hur man kan försöka att skapa synergieffekter mellan de olika startpunkterna och olika sätt att implementera parallellisering och vad de får för effekter på optimeringsalgoritmen.Vi har implementerat en algoritm för att lösa problem enligt ovan samt de nya parallella utökningarna.Denna har använts för att lösa såväl testproblem som att lösa industriella problem.