Algorytm ewolucyjny dla problemu pakowania

• Autorzy: Stawowy A.

Warianty tytułu

EN

Evolutionary algorithm for bin packing problem

• Języki publikacji: PL

Abstrakty

PL

Z prac E. Falkenauera wynika, że standardowy schemat i elementy algorytmu ewolucyjnego nie nadają się do problemu grupowania wyrobów. Obserwacje te potwierdziły badania S. Khuriego i zespołu. Jako rozwiązanie E. Faikenauer zaproponował specjalizowany schemat kodowania i nowe operatory genetyczne dostosowane do problemów grupowania (ang. Grouping Genetic Algorithm - GGA). Zdaniem autora nie ma potrzeby stosowania specjalizowanych operatorów i reprezentacji do problemów grupowania. W pracy przedstawiono udane zastosowanie strategii ewolucyjnej do jednego z problemów grupowania jakim jest zagadnienie pakowania pudełek. Zastosowano (1, X) - ES, w której X potomków jest generowanych z jednego rodzica za pomocą prostej mutacji. Krzyżowanie nie jest stosowane. Najlepszy z potomków zastępuje rodzica w nowej populacji. W algorytmie zastosowano znaną z literatury reprezentację porządkową, w której dopuszczalne rozwiązania są reprezentowane przez listę n obiektów i s separatorów grup, przy czym wartość ;' (1 <;'< n) określająca numer obiektu może wystąpić na liście tylko jeden raz, podobnie jak wartość i (n + 1 < i < n + s) określająca numer separatora. Jednym z elementów funkcji dopasowania jest funkcja kary, eliminująca niedopuszczalne rozwiązania. Przeprowadzone badania eksperymentalne wykazały dużą przydatność strategii ewolucyjnej dla problemu pakowania pudełek. Zaproponowany algorytm daje tylko nieznacznie gorsze rozwiązania niż, o wiele bardziej skomplikowany, GGA, natomiast dużo lepsze niż inne algorytmy przybliżone.

EN

From the works by E. Falkenauer it appears that a standard scheme and elements of an evalutionary algorithm are not suitable for the problem of grouping the products. These observations are confirmed by researches by S. Khuri at all. As a remedy E. Falkenauer proposed a new encoding scheme and genetic operators adapted to the grouping problem, yielding Grouping Genetic Algorithm (GGA). In our opinion there is no need to apply specialized operators and representations for the grouping problems. In this paper we investigate the use of evolutionary strategy for the bin packing problem. We used (1, X) - ES, where 30 children are generated from one parent by means of a simple mutations; the cross-over is not applied. The best of the descendants becomes the new parent solution. A widely known ordered representation modified for the purposes of the grouping the objects was used in the algorithm. Admissible solutions arę represented by a list of n objects and s. Separators of groups.; the value ;' (1 <;'< n) determiningjhe object number can appear in the list just once, just as the value / (n + 1 < /'< n + s) determining the number of separators. One of the term of the fitness function is the penalty. The researches shown a great usefulness of the evolutionary strategy for the bin packing problem. The results of the experiments confirmed once more the power of the evolutionary algorithms which consist in ability to generale very good solutions without going into the structure of the problem.

Słowa kluczowe

PL

algorytm ewolucyjny; schemat kodowania; operatory genetyczne; grupowanie; Grouping Genetic Algorithm GGA; strategia ewolucyjna; zagadnienie pakowania pudełek

• Wydawca: Wydawnictwa AGH
• Czasopismo: Mechanika / Akademia Górniczo-Hutnicza im. St. Staszica
• Rocznik: 1998
• Tom: T. 17, z. 4
• Strony: 593--598
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Stawowy A.

• Akademia Górniczo-Hutnicza, Wydział Zarządzania