Wyniki wyszukiwania - BazTech

1

Hyper-Heuristic Approach for Improving Marker Efficiency

Domović D., Rolich T., Golub M.

Autex Research Journal

|

2018

|

Vol. 18, no. 4

348--363

EN

Marker planning is an optimization arrangement problem, where a set of cutting parts need to be placed on a thin paper without overlapping to create a marker – an exact diagram of cutting parts that will be cut from a single spread. An optimal marker that utilizes the length of textile material has to be obtained. The aim of this research was to develop novel algorithms for obtaining an efficient marker that would achieve competitive results and optimize the garment production in terms of improving the utilization of textile material. In this research, a novel Grid heuristic was introduced for obtaining a marker, alongside its improvement methods: Grid-BLP and Grid-Shaking. These heuristics were hybridized with genetic algorithm that determined the placement order of cutting parts using the newly introduced All Equal First (AEF) placement order. A novel individual representation for genetic algorithm was designed that was composed of order sequence, rotation detection and the choice of placement algorithm (hyper-heuristic). Experiments were conducted to determine the best marker making method, and hyper-heuristic efficiency. The implementation and experiments were conducted in MATLAB using GEATbx toolbox on five datasets from the garment industry: ALBANO, DAGLI, MAO, MARQUES and MAN SHIRT. Marker efficiency in percentage was recorded with best results: 84.50%, 80.13%, 79.54%, 84.67% and 86.02% obtained for the datasets respectively. The most efficient heuristic was Grid-Shaking. Hyper-heuristic applied Grid-Shaking in 88% of times. The created algorithm is independent of cutting parts’ shape. It can produce markers of arbitrary shape and is flexible in terms of expansion to new instances from the garment industry (leather nesting, avoiding damaged areas of material, marker making with materials with patterns).

2

A Flexible and Adaptive Hyper-heuristic Approach for (Dynamic) Capacitated Vehicle Routing Problems

Garrido P., Castro C.

Fundamenta Informaticae

|

2012

|

Vol. 119, nr 1

29-60

EN

We present a self-adaptive hyper-heuristic capable of solving static and dynamic instances of the capacitated vehicle routing problem. The hyper-heuristic manages a generic sequence of constructive and perturbative low-level heuristics, which are gradually applied to construct or improve partial routes. We present some design considerations to allow the collaboration among heuristics, and to find the most promising sequence. The search process is carried out by applying a set of operators which constructs new sequences of heuristics, i.e., solving strategies. We have used a general and low-computational cost parameter control strategy, based on simple reinforcement learning ideas, to assign non-arbitrary reward/penalty values and guide the selection of operators. Our approach has been tested using some standard state-of-the-art benchmarks, which present different topologies and dynamic properties, and we have compared it with previous hyper-heuristics and several well-known methods proposed in the literature. The experimental results have shown that our approach is able to attain quite stable and good quality solutions after solving various problems, and to adapt to dynamic scenarios more naturally than other methods. Particularly, in the dynamic case we have obtained high-quality solutions when compared with other algorithms in the literature. Thus, we conclude that our self-adaptive hyper-heuristic is an interesting approach for solving vehicle routing problems as it has been able (1) to guide the search for appropriate operators, and (2) to adapt itself to particular states of the problem by choosing a suitable combination of heuristics.

3

Hyper-heuristics for cross-domain search

Cichowicz T.., Drozdowski M., Frankiewicz M., Pawlak G., Rytwinski F., Wasilewski J.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2012

|

Vol. 60, nr 4

801-808

EN

In this paper we present two hyper-heuristics developed for the Cross-Domain Heuristic Search Challenge. Hyper-heuristics solve hard combinatorial problems by guiding low level heuristics, rather than by manipulating problem solutions directly. Two hyper-heuristics are presented: Five Phase Approach and Genetic Hive. Development paths of the algorithms and testing methods are outlined. Performance of both methods is studied. Useful and interesting experience gained in construction of the hyper-heuristics are presented. Conclusions and recommendations for the future advancement of hyper-heuristic methodologies are discussed.

4

Hyper-heuristics for power-aware routing protocols

Pilski M., Seredynski F.

Studia Informatica : systems and information technology

|

2008

|

Vol. 2(11)

37--47

EN

The idea underlying hyper-heuristics is to discover some combination of straightforward heuristics that performs very well across a whole range of problems. In this paper we describe genetic algorithm-based (GA) approach that learns such a heuristic combination for solving energy-efficient routing problem in mobile ad hoc networks (MANETs).

5

Hiperheurystyki w kolorowaniu grafów

Dąbrowski J., Obszarski P.

Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne

|

2007

|

T. 13

443-448

PL

Hiperheurystyki to jeden z nowych trendów w technice obliczeniowej. Można je zdefiniować jako algorytmy, które wykorzystują zdefiniowany zbiór prostych heurystyk do znalezienia przybliżonego rozwiązania. Celem algorytmu jest znalezienie takiej sekwencji uruchamiania tych prostych operacji, która będzie dawała najlepsze rozwiązanie dla danej instancji problemu lub danej klasy instancji problemu. W pracy zdefiniowano heurystyki dla problemu wierzchołkowego kolorowania grafów oraz przedstawiono algorytm genetyczny, w którym ewolucji podlegają sekwencje ich wyboru przy kolorowaniu zachłannym.

EN

Hyperheuristics are optimization algorithms that use sets of simple heuristic operations that can change the state of a solution. The goal of the algorithm is to find a good sequence of those operations that produces a good solution to the problem. This work presents low-level heuristics for the well known Graph Coloring Problem and a genetic algorithm that evolves sequences of choices for a greedy coloring algorithm.