Een nieuwe constructieve heuristiek voor het circle-packing probleem

Pablo Bollansée
De thesis beschrijft een nieuwe constructieve heuristiek voor het circle-packing probleem, met als hoofddoel de berekeningen zeer snel te doen verlopen. De implementatie kan in milliseconden problemen oplossen waar andere algoritmen soms tot 24h voor nodig hebben, en geeft gemiddeld minder dan 6% slechtere oplossingen.

In de Ban van de Cirkel: Een nieuwe heuristiek voor circle-packing

Cirkels fascineren. Formules op een papyrusrol uit het tweede millennium voor Christus doen hun uiterste best om voor de eerste keer in de geschiedenis de oppervlakte van een cirkel te berekenen. Wanneer aliens de aarde bezoeken, dan is de boodschap bij uitstek die ze voor ons achterlaten een eenvoudige maar o-zo mysterieuze cirkel. Waarom laten ze geen vierkant achter? Of een barcode? Waarom spendeert de arme Egyptische papyrusschrijver zijn tijd aan het benaderen van pi en niet aan verfrissend bad in de Nijl? Dat mijn thesis antwoord geeft op één van die uiterst filosofische vragen, durf ik niet te beweren, maar ik hoop dat het stellen van die vragen wel één ding bewijst: mensen zijn gefascineerd door cirkels, en ze willen er al sinds het begin der tijden alles over weten. Geloof het of niet, maar informatica-studenten zijn ook mensen, en dus hoef ik het onderwerp van mijn thesis niet verder te verantwoorden: het virtueel puzzelen van kleine cirkels in één grote cirkel.

Stel, je hebt een cirkelvormig stuk land dat je wil laten begrazen door zoveel mogelijk geiten. Er is echter één probleem: die geiten kunnen elkaar niet uitstaan. Als het graasgebied van een geit overlapt met dat van een ander, dan komt er boel van. Je hebt gelukkig ook een aantal piketten en touwen van verschillende lengte. Het circle-packing probleem, waarover mijn thesis gaat, kan je in feite als volgt samenvatten: waar moet ik de pikketten in de grond slaan om zoveel mogelijk geiten gelukkig te maken, zonder dat hun territoria – eveneens cirkelvormig want begrensd door de lengte van het touw - overlappen.

Zelfs de meest agrarisch aangelegde lezers hebben wellicht hun vragen bij de relevantie van deze analogie, maar vervang die geiten misschien even door zendmasten en je ziet het licht. Hoe kan ik zendmasten – die hun signaal uitzenden in elke richting en dus een cirkelvormig bereik hebben – op zo’n manier plaatsen dat er een minimum aan gebieden is waar geen ontvangst is? Een algoritme dat een dergelijk probleem oplost kan een bedrijf miljoenen besparen, en menige tiener-romance in stand houden. Blijkbaar kan je circle-packing zelfs gebruiken om origami figuren van ongelooflijke complexiteit te bouwen (zoek maar eens op: black forest cuckoo clock origami).

Er zijn al verschillende pogingen gebeurd om het circle-packing probleem op te lossen, maar mijn thesis pakt het op een heel andere manier aan. Bijna al het voorgaande onderzoek ging ervan uit dat je de positie van alle cirkels tegelijk moet berekenen. Dat je het probleem in één enkele stap moet oplossen dus. Op die manier kan je heel nauwkeurig je cirkels samen puzzelen, met erg weinig verspilde plaats, maar deze manier van werken heeft één groot nadeel: het vraagt enorm veel rekenkracht om de posities van al die cirkels in één keer te berekenen. Elke cirkel hangt van elke andere cirkel af, en omdat je ze allemaal tegelijk probeert te plaatsen, schiet de processing power en rekentijd die je nodig hebt enorm de hoogte in. Vergelijk het met een puzzel die je probeert op te lossen door alle stukken tegelijkertijd in elkaar te passen, zonder er eerst eentje te leggen en dan nog eentje en daarop verder te bouwen. (Voorbeeld ter illustratie: met een dergelijk klassiek algoritme duurt het wel tot 24 uur om 30 cirkels samen te puzzelen. Niet zo efficiënt als je meer dan 30 geitjes hebt.)

Daar brengt mijn oplossing dus verandering in, en als je de titel van mijn thesis onder de loep legt, heb je de clue al door: Een nieuwe constructieve heuristiek voor het circle-packing probleem. Mijn methode om het circle-packing probleem op te lossen is “constructief”, wat wilt zeggen dat je het probleem aanpakt zoals elk zes jaar oud kind een legpuzzel oplost: stukje per stukje. Eerst plaatst het algoritme de drie grootste cirkels knus tegen elkaar. Daarna gaat het op zoek naar de grootst mogelijke cirkel die tussen die drie eerste cirkels past. Past er geen enkele, dan wordt de nieuwe cirkel aan de buitenkant geplaatst. Dan kijkt het algoritme of het een cirkel kan plaatsen in het nieuwe gat dat ontstaan is door de vierde cirkel te plaatsen. Past er geen, dan wordt nummer vijf aan de buitenkant geplaatst. En zo verder, tot je in een mum van tijd een enorme hoeveelheid cirkels bij elkaar gepuzzeld hebt. Als je de cijfers van daarnet nog in je hoofd hebt (24 uur voor 30 cirkels), dan geef ik nu even een tegenvoorbeeld: mijn methode doet over 1000 cirkels slechts 1 seconde, en de kwaliteit van de oplossingen is gelijkaardig (gemiddeld minder dan 6% slechter).

Dat cirkels ondertussen al hun geheimen hebben prijsgegeven, durf ik niet beweren, maar ik hoop dat mijn thesis ten minste een nieuwe manier aanreikt om na te denken over een abstract probleem dat misschien wel erg onverwachte toepassingen kan hebben. Hoe ver van de echte wereld een wiskundig vraagstuk ook lijkt te staan, er is altijd wel een geitenboer of een zendmastenbouwer die er mee aan de slag kan.

Voorbeeld packing van 1000 cirkels

Bibliografie
  1. Hakim Akeb and Yu Li. A basic heuristic for packing equal circles into a circular container. Comput. Oper. Res, 33:2125-2142, 2006.
  2. I Al-Mudahka, Mhand Hi?, and Rym M'Hallah. Packing circles in the smallest circle: an adaptive hybrid algorithm. Journal of the Operational Research Society, 62(11):1917-1930, 2011.
  3. P. Bollansée. Circle packing. https://github.com/circle-packing/best-fit.
  4. P. Bollansée. Packomania tabellen. https://github.com/circle-packing/docs/blob/master/thesis/packomania-ta….
  5. Edmund K Burke, Graham Kendall, and Glenn Whitwell. A new placement heuristic for the orthogonal stock-cutting problem. Operations Research, 52(4):655-671, 2004.
  6. John A George, Jennifer M George, and Bruce W Lamar. Packing di?erent-sized circles into a rectangular container. European Journal of Operational Research, 84(3):693-712, 1995.
  7. Ronald L Graham and Boris D Lubachevsky. Repeated patterns of dense packings of equal disks in a square. the electronic journal of combinatorics, 3(1):R16, 1996.
  8. Ronald L Graham, Boris D Lubachevsky, Kari J Nurmela, and Patric RJ Östergård. Dense packings of congruent circles in a circle. Discrete Mathematics, 181(1):139-154, 1998.
  9. Andrea Grosso, ARMJU Jamali, Marco Locatelli, and Fabio Schoen. Solving the problem of packing equal and unequal circles in a circular container. Journal of Global Optimization, 47(1):63-81, 2010.
  10. Mhand Hi? and Rym M'Hallah. Approximate algorithms for constrained circular cutting problems. Computers & Operations Research, 31(5):675-694, 2004.
  11. Mhand Hi?, Vangelis Th Paschos, and Vassilis Zissimopoulos. A simulated annealing approach for the circular cutting problem. European Journal of Operational Research, 159(2):430-448, 2004.
  12. Wen Qi Huang, Yu Li, Chu Min Li, and Ru Chu Xu. New heuristics for packing unequal circles into a circular container. Computers & Operations Research, 33(8):2125-2142, 2006.
  13. WenQi Huang, ZhangHua Fu, and RuChu Xu. Tabu search algorithm combined with global perturbation for packing arbitrary sized circles into a circular container. Science China Information Sciences, 56(9):1-14, 2013.
  14. CO Lopez and JE Beasley. Packing unequal circles using formulation space search. Computers & Operations Research, 40(5):1276-1288, 2013.
  15. Boris D Lubachevsky and Ronald L Graham. Curved hexagonal packings of equal disks in a circle. Discrete & Computational Geometry, 18(2):179-194, 1997.
  16. Rym M'Hallah, Abdulaziz Alkandari, and Nenad Mladenovic. Packing unit spheres into the smallest sphere using vns and nlp. Computers & Operations Research, 40(2):603-615, 2013.
  17. E. Specht. Packomania. http://www.packomania.com/. Accessed: 2016-05-23.
  18. Sunshine. Computing the smallest enclosing disk in 2d. http://www.sunshine2k.de/coding/java/Welzl/Welzl.html, 2008.
  19. Huaiqing Wang, Wenqi Huang, Quan Zhang, and Dongming Xu. An improved algorithm for the packing of unequal circles within a larger containing circle. EuropeanJournal of Operational Research, 141(2):440-453, 2002.
  20. Emo Welzl. Smallest enclosing disks (balls and ellipsoids). Springer, 1991.
  21. Tao Ye, Wenqi Huang, and Zhipeng Lu. Iterated tabu search algorithm for packing unequal circles in a circle. arXiv preprint arXiv:1306.0694, 2013.
  22. Zhizhong Zeng, Xinguo Yu, Kun He, Wenqi Huang, and Zhanghua Fu. Iterated tabu search and variable neighborhood descent for packing unequal circles into a circular container. European Journal of Operational Research, 250(2):615-627, 2016.
Universiteit of Hogeschool
Master in de toegepaste informatica
Publicatiejaar
2016
Promotor(en)
Patrick De Causmeaker
Kernwoorden
Deel deze scriptie