Metody i Algorytmy Sztucznej Inteligencji

Raport z wykonania dużego projektu

Porównanie Algorytmów Dla Problemu Wielorzędowego Rozmieszczenia Maszyn

Politechnika Wrocławska

Wrocław 12.06.2006 r.

Wykonanie: Tomasz Rogalski

Prowadzący: Dr inż. Witold Paluszyński

1. Wstęp

Raport prezentuje problem poszukiwania najlepszego rozmieszczenia maszyn w hali produkcyjnej, minimalizującego całkowite koszty transportu elementów w hali produkcyjnej. Znalezienie optymalnego rozwiązania jest trudne ponieważ jest to problem NP-trudny. Rozwiązanie problemu otrzymujemy wykorzystując algorytmy konstrukcyjne oraz algorytm poszukiwań z zabronieniami Tabu Serach wspomagany metodą skoku powrotnego (MSP). W raporcie przedstawiono wyniki badań komputerowych, które ukazują rezultaty otrzymanych rozwiązań oraz jaki wpływ na otrzymane wyniki ma zastosowanie algorytmu  Tabu Serach do powyższego problemu.

[Spis treści]

2. Definicja problemu

Problem wielorzędowego rozmieszczenia maszyn w hali polega na takim rozmieszczeniu maszyn, które minimalizuje całkowite koszty transportu półproduktów (np. detali) pomiędzy maszynami. Wyliczany koszt transportu zależy w tym przypadku przede wszystkim od:

·        odległości między maszynami

·        oraz jednostkowego kosztu transportu

Poniżej przedstawiono, jedną z możliwych, koncepcję rozwiązania problemu, w oparciu o kombinatoryczny model wielorzędowego rozmieszczenia maszyn (stanowisk roboczych) w hali produkcyjnej, który określa specyficzny sposób rozmieszczenia maszyn zgodny z rysunkiem nr 1. Dla rozwiązania problemu zaproponowano algorytmy konstrukcyjne, których wynik został poprawiony przez metaheurystykę tabu, tj. algorytm TS (ang. Tabu Search).

Rys. 1. Wielorzędowe rozmieszczenie maszyn w hali produkcyjnej.

[Spis treści]

4. Algorytmy konstrukcyjne

Aby rozwiązać tak zdefiniowany problem, wykorzystamy dwa algorytmy konstrukcyjne, których celem jest pozyskanie dobrego rozwiązania początkowego (wstępnego rozmieszczenia maszyn), które będzie rozwiązaniem bazowym dla algorytmu Tabu Serach.

Algorytm "Konstrukcyjny 1" (o złożoność 0(n²)), na podstawie jednostkowego kosztu transportu materiałów  rozmieszcza maszyny tak aby zminimalizować "lokalne" koszty transportu.

Schemat algorytmu "Konstrukcyjnego 1"

Krok 1.

W macierzy   znajdź maksymalny element
           

i przypisz  dla  oraz jako rozwiązanie częściowe przypisz

.

Krok 2.

Jeżeli częściowe rozwiązanie  nie zawiera wszystkich maszyn to dla macierzy kosztów  znajdź maksymalny element:

Jeżeli  to przypisz  oraz  dla ; w przeciwnym wypadku podstaw oraz dla .

Algorytm "Konstrukcyjny 2" (o złożoności 0(nlogn)), wyznacza sekwencję maszyn według obliczonej funkcji priorytetu:

rozmieszczając maszyny rozpoczynając od największej wartości priorytetu - w położeniu centralnym sekwencji , do najmniejszej wartości priorytetu - położenia skrajne sekwencji .

Schemat algorytmu "Konstrukcyjnego 2": 

Krok 1.

Dla każdej maszyny  oblicz wartość priorytetu:

Krok 2.

Utwórz listę maszyn  według niemalejącej wartości funkcji priorytetu:

Krok 3.

Wyznacz rozwiązanie  przypisując
, i tak dalej.

5. Algorytm Tabu Search

   Otrzymane w wyniku zastosowania algorytmów konstrukcyjnych rozwiązanie, poprawiamy przez zastosowanie algorytmu Tabu Search. Do otrzymania lepszego rozwiązania stosujemy algorytm TS wyposażony w mechanizmy dywersyfikujące i intensyfikujące proces poszukiwań takie jak: pamięć krótko terminowa, pamięć długo terminowa, metoda skoku powrotnego.

Oznaczenia:

             - Rozwiązanie należące do zbioru rozwiązań dopuszczalnych.

             -  Wartość funkcji celu w - tej iteracji.

      - Rozwiązanie poprawione przez algorytm TS.

      - Najlepsza wartość funkcji celu znaleziona przez algorytm TS.

      - Licznik wykonanych iteracji.

             - Globalna liczba iteracji przewidzianych do wykonania.

             - Licznik iteracji wykonanych bez poprawy funkcji celu.

 - Liczba iteracji wykonana bez poprawy funkcji celu po której następuje zakończenie pracy algorytmu.

             - Górna lista tabu – pamięć krótkoterminowa.

             - Dolna lista tabu – pamięć długoterminowa.

             - Poziom aspiracji.

      - Okres tabu.

             - Stała różnicowania procesu poszukiwań.

Schemat algorytmu Tabu Search z zastosowaniem pamięci krótkoterminowej, długoterminowej i kryterium aspiracji:

Krok 1.

Początek poszukiwania podstaw:

Krok 2.

Dla  do  wykonaj

a) Wyznacz najlepsze rozwiązanie w otoczeniu:
                               Jeżeli  to

            Jeżeli  to

               Podstaw:

                               b) Poprawa rozwiązań:

                                               Jeżeli  to podstaw:

                                   Jeżeli   to wykonaj instrukcje:

                                               Podstaw:

                                   Podstaw
                                   Jeżeli  to STOP;

c) Korekta stanu pamięci:

                             Dla  podstaw .
                             Jeżeli wykonano instrukcje  to podstaw: 
                                        

 i 

w przeciwnym wypadku:

 i 

[Spis treści]

6. Opis programu

Rys. 2. Widok interfejsu graficznego programu użytego do obliczeń

W ramach projektu został wykorzystany program, którego interfejs graficzny został pokazany na rysunku nr 2. Program został napisany przez projektanta w języku C++ i uruchamiany jest w systemie Microsoft Windows. W programie zostały zaimplementowane omówione powyżej algorytmy.

Po uruchomieniu programu należy wybrać źródło danych. Do testów zostały stworzone gotowe zestawy danych dla 5, 10, 15, 20 liczby maszyn. Można z nich skorzystać zaznaczając w panelu Dane opcje Przykłady a następnie wybrać jeden z nich. Dodatkowo możemy wprowadzać zmiany dla wybranych danych m. in. możemy modyfikować poszczególne macierze poprzez kwiknięcie na poszczególne komórki macierzy i wpisanie dowolnej wartości całkowitej. Można wprowadzać dane z innych plików ale dane w nich zapisane muszą być zapisane w odpowiednim formacie, który będzie omówiony w dalszej części raportu. Aby tego dokonać w panelu Dane zaznaczamy opcję Z pliku. Program umożliwia tworzenie własnych danych w przypadku wyboru opcji i Własne i wówczas wpisujemy do macierzy własne dane.

Ponadto musimy określić szerokość rzędów hali oraz wybrać algorytm przy pomocy którego zostanie wygenerowane rozwiązanie. Dzięki tej opcji możemy przeprowadzić w łatwy sposób testy zaimplementowanych algorytmów i porównać otrzymane wyniki. Porównanie wyników można przeprowadzić na podstawie wyliczonych kosztów transportu jak i tez czasu obliczeń algorytmów.

Jeżeli wybierzemy algorytm Tabu Search, pojawi się przycisk opisany jako Opcje, wówczas mamy możliwość zmiany parametrów dla tego algorytmu. Możemy wybrać  który z algorytmów konstrukcyjnych wykorzystany zostanie do wygenerowania  rozwiązania bazowego, które będzie poprawiane przez  algorytm TS. Kolejne parametry które możemy zmieniać to:

1.      liczba iteracji algorytmu TS dobierana w zależności od rozmiaru zadania (ilości  maszyn)

2.      maksymalna liczba iteracji po której zostanie zakończony algorytm TS jeżeli nie    zostanie znalezione rozwiązanie polepszające funkcje celu. Jest to warunek stopu który można wykorzystać przy minimalizacji kosztów transportu dla zadań o dużych rozmiarach. Dla takich zadań należy ustawić odpowiednio dużą liczbę iteracji algorytmu TS co powoduje, że  czas działania programu jest bardzo długi.

3.      okres Tabu ( liczba iteracji po której zostaje zdjęty status tabu )

Możliwość zmiany powyższych parametrów czyni program dosyć elastycznym. Na przykład możemy zmieniać liczbę iteracji w zależności od wielkości rozwiązywanego zadania, dzięki czemu możemy ograniczyć czas działania programu. 

Po zakończeniu działania algorytmu otrzymujemy rozwiązanie problemu w postaci:

• Rozmieszczenia maszyn w hali przedstawionej w oknie programu zatytułowanym jako Hala. Hale należy traktować jak układ współrzędnych tj. dla każdej maszyny podana jest współrzędna  w macierzy Maszyny, oraz dla każdego rzędu w hali podana jest współrzędna .
• Obliczona zostaje zdefiniowana wcześniej funkcja celu, stanowiąca główne kryterium jakości działania danego algorytmu.
• Ponadto w programie obliczany jest czas obliczeń wykonywanych przez algorytm.

Sposób rozmieszczania maszyn nie jest przypadkowy, tzn. maszyny są ustawiane począwszy od pierwszego rzędu od lewej strony hali, wskutek czego pierwsza maszyna ma współrzędną  równą połowie jej szerokości. W następnym rzędzie maszyny są tym razem ustawiane od prawej strony hali i tak na przemian. Rząd pierwszy ma współrzędną  równą 0. Natomiast współrzędna  kolejnego rzędu zależy od najszerszej maszyny przewidzianej do ułożenia w tym rzędzie, uwzględniając dodatkowo przestrzeń potrzebną dla wózka przewożącego półprodukty pomiędzy maszynami. Współrzędne rzędów są wyświetlane w oknie obrazującym rozmieszczenie maszyn na hali, obok prawej ściany hali na wysokości rzędu

[Spis treści]

7. Wyniki testów
 

W przeprowadzonych testach wykorzystano dane przykładowe programu oraz dane pochodzące z innych źródeł, które zostały podane w literaturze w pozycji [3] i [4].

Wszystkie dane testowe muszą być zapisane w plikach tekstowych w formacie opisanym poniżej na rysunku nr 3.

 
Rys. 3. Przykładowa zawartość pliku  z zestawem danych testowych

 
Rys. 4. Tabela wyników z testów

8. Wnioski

Przeprowadzono 40 testów dla trzech algorytmów, których wyniki są zamieszczone w tabeli na rysunku nr 4. Dla algorytmu Tabu Search przeprowadzono po dwa testy z tego samego źródła testów z rozróżnieniem na pochodzenie rozwiązania bazowego tj. rozwiązania pochodzącego z algorytmów konstrukcyjnych 1 i 2.

Z przeprowadzonych badań wynika, że algorytm Tabu Search daje rozwiązanie problemu znacznie lepsze niż algorytmy konstrukcyjne. Wśród algorytmów konstrukcyjnych lepszym okazał się algorytm konstrukcyjny 1. Uzyskał lepsze wyniki dla większości testów niż algorytm konstrukcyjny 2. Jednak pod względem czasu wykonywanych obliczeń wyróżnia się algorytm konstrukcyjny 2, ponieważ jest algorytmem o najmniejszej złożoności obliczeniowej. Najwolniej z wszystkich algorytmów działał algorytm Tabu Search, ponieważ jego złożoność obliczeniowa jest dużo większa niż algorytmów konstrukcyjnych.

Testy Dla algorytmu Tabu Search przeprowadzone zostały z następującymi parametrami algorytmu:

·        Maksymalna ilość iteracji TS – 30

·        Maksymalna ilość iteracji TS bez poprawy funkcji celu – 10

·        Okres tabu

·        Stała różnicowa procesu poszukiwań

Najlepsze wyniki uzyskano dla algorytmu Tabu Search w którym rozwiązanie bazowe pochodziło od algorytmu konstrukcyjnego 1, który jak się okazało jest najlepszym pod względem otrzymanego rozwiązania algorytmem wśród algorytmów konstrukcyjnych. Czas obliczeń dla Tabu Search w obu przypadkach nie różnił się znacząco tj. uzyskiwano podobne czasy obliczeń.

Algorytm Tabu Search daje rozwiązania dużo lepsze w porównaniu do algorytmów konstrukcyjnych szczególnie wtedy gdy rozmiar zadań tzn. ilość maszyn do rozmieszczenia w hali produkcyjnej jest duża. Ale jest to bardzo czasochłonne, ponieważ złożoność obliczeniowa algorytmu Tabu Search jest wykładnicza, tak jak widać to na rysunku nr 5.

Rys. 5. Czas działania algorytmu Tabu Search w zależności rozmiaru zadania

Rys. 6. Wykres otrzymanego rozwiązania z zależności od rozmiaru zadania

Zatem dla mniejszych instancji problemu dobre jest stosować algorytm Tabu Search, natomiast dla dużych instancji tj. dla liczby maszyn przekraczającej 100 maszyn dobrze jest stosować jeden z algorytmów konstrukcyjnych w celu oszczędzenia czasu co również wiąże się z kosztami. Na rysunku nr 6 przedstawiono wykres otrzymanych rozwiązań dla badanych algorytmów w zależności od ilości maszyn do rozmieszczenia w hali. Widać jak algorytm Tabu Search poprawia wartość funkcji celu w stosunku do rozmiaru zadania. 

 
[Spis treści]

Literatura:

[3] QAPLIB - A Quadratic Assignment Problem Library

[4] Dane profesora Érica Taillarda