Od přesných metod k heuristikám

From Exact Methods to Heuristics

článek v časopise - ostatní, Jost

en

In this work, typical problems of manufacturing-process scheduling, logical circuit design, network optimisation and robotics were described. We focused on problems of combinatorial nature or on those that can be reduced to problems of combinatorial optimization. It was shown that, for small instances, deterministic methods such as the branch-and-bound method and, in a special case, the dynamic programming approach may also be used. On the other hand, due to NP-completeness, the branch-and-bound method and dynamic-programming approach are not efficient in solving these problems if they have a high number of input parameters because of the exponentially growing time in branch-and-bound method calculations and high memory requirements for static arrays in the dynamic-programming approach. We verified that commercial software tools, such as GAMS, fail for large instances of these problems, too. In these cases, we chose heuristic techniques, mainly stochastic heuristics (or metaheuristics) that define a general framework for computations and the user must find suitable problem-specific parameter settings and verify them using benchmarks. A genetic algorithm was found to work efficiently in many situations. It provides good results in a reasonable amount of time for hundreds of input parameters and tens of capacity constraints. Finally, we showed that using stochastic heuristics need not be the only way of solving NP-complete problems and proposed approaches based on geometric data structures such as Delaunay triangulation and Voronoi diagrams. They were applied in network optimisation to find a minimal Euclidean Steiner tree and in robotics to plan trajectories of a moving object in a scene with obstacles. While being able to provide good approximations of the optimum, the proposed deterministic heuristics do not require so much tuning as stochastic heuristics and, moreover, they run in a polynomial time. Therefore they are also applicable in real time computation. Using generalised Voronoi diagrams gives an efficient tool for robot motion planning and generates smooth trajectories in a scene with movable obstacles.

V této práci jsou popsány typické problémy rozvrhování výrobních procesů, návrhu logických obvodů, síťové optimalizace a robotiky. Zaměřili jsme se na problémy kombinatorické povahy, resp. takové problémy, které lze na problémy kombinatorické optimalizace převést. Bylo ukázáno, že pro malé instance lze použít deterministické metody, jako jsou metoda větví a mezí. Ve speciálním případě lze využít i přístup založený na dynamickém programování. Na druhé straně vzhledem k NP-úplnosti metoda větví a mezí a dynamické programování nejsou efektivní na řešení těchto problémů, jestliže mají velký počet vstupních parametrů, protože při použití metody větví a mezí exponenciálně roste čas výpočtu a u dynamického programování nároky na operační paměť pro statická pole. Ověřili jsme, že komerční softwarové nástroje, jako je GAMS, na velkých instancích těchto problémů rovněž selhávají. V těchto případech jsme volili heuristické techniky, zejména stochastické heuristiky (metaheuristiky), které definují obecný rámec výpočtu a uživatel musí najít vhodné problémově specifické nastavení parametrů a ověřit je na testovacích úlohách. Ukázalo se, že účinným nástrojem je v mnoha případech genetický algoritmus. Zajišťuje dobré výsledky v rozumném čase pro stovky vstupů a desítky omezení. Závěrem jsme ukázali, že použití stochastických heuristik nemusí být jediným způsobem řešení NP-úplných problémů a navrhli jsme přístupy založené na geometrických datových strukturách, jako jsou Delaunayho triangulace a Voroného diagramy. Tyto struktury byly použity v úlohách síťové optimalizace a robotiky spočívající v hledání minimálního Steinerova stromu v euklidovské rovině, resp. pro plánování dráhy pohybujícího se objektu (robotu) ve scéně s překážkami. Zmíněné přístupy zajišťují nalezení dobrých aproximací optimálního řešení a přitom nevyžadují tak rozsáhlá ladění parametrů jako stochastické heuristiky a navíc počítají v polynomiálním čase. To znamená, že jsou rovněž použitelné při výpočtech v reálném čase. Použití zobecněných Voroného diagramů dává účinný nástroj pro plánování pohybu robotu a generuje "hladké" trajektorie ve scéně s pohyblivými překážkami.

In this work, typical problems of manufacturing-process scheduling, logical circuit design, network optimisation and robotics were described. We focused on problems of combinatorial nature or on those that can be reduced to problems of combinatorial optimization. It was shown that, for small instances, deterministic methods such as the branch-and-bound method and, in a special case, the dynamic programming approach may also be used. On the other hand, due to NP-completeness, the branch-and-bound method and dynamic-programming approach are not efficient in solving these problems if they have a high number of input parameters because of the exponentially growing time in branch-and-bound method calculations and high memory requirements for static arrays in the dynamic-programming approach. We verified that commercial software tools, such as GAMS, fail for large instances of these problems, too. In these cases, we chose heuristic techniques, mainly stochastic heuristics (or metaheuristics) that define a general framework for computations and the user must find suitable problem-specific parameter settings and verify them using benchmarks. A genetic algorithm was found to work efficiently in many situations. It provides good results in a reasonable amount of time for hundreds of input parameters and tens of capacity constraints. Finally, we showed that using stochastic heuristics need not be the only way of solving NP-complete problems and proposed approaches based on geometric data structures such as Delaunay triangulation and Voronoi diagrams. They were applied in network optimisation to find a minimal Euclidean Steiner tree and in robotics to plan trajectories of a moving object in a scene with obstacles. While being able to provide good approximations of the optimum, the proposed deterministic heuristics do not require so much tuning as stochastic heuristics and, moreover, they run in a polynomial time. Therefore they are also applicable in real time computation. Using generalised Voronoi diagrams gives an efficient tool for robot motion planning and generates smooth trajectories in a scene with movable obstacles.

optimalizace, NP-těžké problémy, heuristické metody, genetický algoritmus, rozvrhování, robotika, počítačová geometrie, Voroného diagram, Delaunayho triangulace

optimisation, NP-hard problems, heuristic methods, genetic algorithm, scheduling, robotics, computational geometry, Voronoi diagram, Delaunay triangulation

2008

15.09.2008

VUTIUM

Brno

1213-418X

Vědecké spisy Vysokého učení technického v Brně Edice Habilitační a inaugurační spisy

2008

276

1–40

40