Prognozowanie popytu.Algorytmy genetyczne.pdf

Zastosowanie algorytmów genetycznych

w prognozowaniu popytu

Grzegorz Chodak

Instytut Organizacji i Zarządzania

Politechnika Wrocławska

e-mail: chodak@ines.ins.pwr.wroc.pl

Witold Kwaśnicki

Instytut Nauk Ekonomicznych

Uniwersytet Wrocławski

e-mail: kwasnicki@ci.pwr.wroc.pl

http://www.prawo.uni.wroc.pl/~kwasnicki

Prognozowanie popytu stanowi jeden z istotnych czynników w procesie podejmowania

decyzji taktyczno-operacyjnych jak również strategicznych w przedsiębiorstwie. Zarządzanie

przepływem materiałowym w przedsiębiorstwie zgodnie ze strategią just-in-time , nie byłoby

możliwe bez dokładnego określenia wielkości sprzedaży. Zarówno dla metod ilościowych,

jak i dla jakościowych, istnieją możliwości wykorzystania komputerów i zaawansowanych

programów umożliwiających zautomatyzowanie obliczeń oraz przedstawienie danych w

postaci graficznej. Kolejnym etapem w rozwoju metod prognozowania będzie

prawdopodobnie wykorzystanie elementów sztucznej inteligencji (takich jak programowanie

ewolucyjne czy sieci neuronowe), co powinno poprawić dokładność określania wielkości

sprzedaży. W artykule zaproponowano metodę prognozowania wielkości sprzedaży, w

przypadku występowania sezonowości popytu. Do identyfikacji parametrów funkcji popytu

zastosowano algorytmy genetyczne.

1. Ogólna charakterystyka algorytmów genetycznych

W ostatnich kilkudziesięciu latach „człowiek-inżynier” zaczął się uważniej przyglądać

naturze i z pokorą od niej się uczyć. Wynikiem tych obserwacji było stworzenie m.in. takich

procedur, naśladujących naturę jak algorytmy ewolucyjne czy sieci neuronowe. Zanim

naturze (ukierunkowanej przez swojego Stwórcę) udało się stworzyć mózg ludzki, minęły

cztery miliardy lat (taki wiek Ziemi jest obecnie uważany za najbardziej prawdopodobny). W

tym czasie, dzięki doborowi naturalnemu, organizmy ewoluowały w kierunku coraz lepszego

przystosowania się do środowiska, w którym żyją. Ten sposób doskonalenia został

zaadaptowany do rozwiązywania zadań optymalizacyjnych i nazwano go algorytmami

ewolucyjnymi.

Zastosowanie algorytmów genetycznych w prognozowaniu popytu

Wśród algorytmów ewolucyjnych wyróżnia się trzy główne klasy (de Jong, 1998 za

Kwaśnicka, 1999): algorytmy genetyczne ( GAs – Genetic Algorithms ), strategie ewolucyjne

( ESs – Evolutionary Strategies ) i programowanie ewolucyjne ( EP – Evolutionary

Programming ). Coraz popularniejsze programowanie genetyczne ( GP – Genetic

Programming ) zwykle bywa uważane za podgrupę algorytmów genetycznych. Szybki wzrost

zainteresowania algorytmami genetycznymi obserwuje się od czasu opublikowania pracy

J.Hollanda (1975). Wyróżnia się trzy zasadnicze grupy zastosowań AG: algorytmy

przeszukujące ( Search ), optymalizujące ( Optimization ) i uczące ( Learning ) (Kwaśnicka,

1999). Wymienione grupy nie są jednak rozłączne i granica między nimi jest płynna.

Algorytmy genetyczne (AG) są procedurami opartymi na podstawowych mechanizmach

ewolucji biologicznej: doborze naturalnym i dziedziczenia. Algorytm działa w dyskretnym

czasie. W każdej jednostce czasu t , w pewnym środowisku Q istnieje populacja osobników

tego samego gatunku P(t) , które konkurują ze sobą oraz mogą się dowolnie krzyżować w

obrębie całej populacji. Podstawową ideą AG jest wykorzystanie ewolucyjnej zasady

przeżycia osobników najlepiej przystosowanych. Oznacza to, że osobniki „lepsze” mają

większe szanse przeżycia i wydania licznego potomstwa. Osobniki „gorsze” mogą przeżyć

i wydać potomstwo, ale prawdopodobieństwo tego jest znacznie mniejsze. Zatem w populacji

zachodzi proces reprodukcji, tzn. osobniki wydają potomstwo.

Po fazie reprodukcji (lub w jej trakcie) następuje krzyżowanie, będące odpowiednikiem

naturalnej wymiany materiału genetycznego, w której potomek dziedziczy część materiału

genetycznego od jednego, pozostałą część od drugiego rodzica. Drugim procesem, który

może zachodzić równolegle do krzyżowania, jest mutacja, czyli losowa zmiana genu.

Krzyżowanie i mutacja zwane są operatorami genetycznymi.

Ewolucja populacji jest procesem przeszukiwania przestrzeni potencjalnych rozwiązań.

W procesach takich istotne jest zachowanie równowagi pomiędzy przekazywaniem

najlepszych cech do następnego pokolenia, a szerokim przeszukiwaniem przestrzeni

rozwiązań. Algorytm genetyczny umożliwia zachowanie takiej równowagi (Kwaśnicka,

1999).

W ogólnym schemacie wykorzystania algorytmów genetycznych przy rozwiązywaniu

rzeczywistych problemów można wyróżnić dwie fazy:

– wstępną, polegającą na sprecyzowaniu problemu i dostosowaniu go do terminologii

używanej w AG oraz utworzeniu początkowej populacji;

Zastosowanie algorytmów genetycznych w prognozowaniu popytu

– poszukiwania rozwiązań, składającą się z oceny osobników, procesu reprodukcji oraz

zastosowania operatorów genetycznych. Faza poszukiwania rozwiązań zostaje

zakończona w momencie gdy zostało znalezione satysfakcjonujące rozwiązanie lub

nastąpił warunek końca algorytmu (np. przekroczona została założona liczba pokoleń).

Zastosowanie AG do identyfikacji parametrów funkcji popytu nie wprowadza ograniczeń

na postać tej funkcji, jak i liczby parametrów. Wadą algorytmów genetycznych (jak i każdej

iteracyjnej metody szukania ekstremum) jest brak gwarancji, że osiągnie się optimum

globalne i nie zakończy się poszukiwania rozwiązania w optimum lokalnym (dokładność

otrzymanych wyników, a więc np. postać funkcji popytu, może okazać się niezgodna z

funkcją jaka mogłaby w najlepszy sposób przybliżyć oczekiwaną sprzedaż). Istnieje jednak

możliwość dostosowania parametrów AG do potrzeb konkretnego zadania, jak również

przetestowania, czy algorytm identyfikuje wartości parametru w sposób odpowiedni np. nie

przekraczający założonego błędu, na danych testowych, przy znanej postaci funkcji. Więcej

informacji na temat algorytmów genetycznych można znaleźć w licznych publikacjach, np.

(Kwaśnicka 1999, Goldberg 1998, Rutkowska 1997).

2. Charakterystyka algorytmów genetycznych używanych w eksperymentach

Osobniki opisane są przez ciągi binarne zerojedynkowe oraz elementy charakterystyczne

dla AG, takie jak metoda selekcji, funkcja przystosowania i operatory genetyczne. Każdy

osobnik składa się z jednego chromosomu. Poszczególne cechy osobnika (parametry funkcji

lub zmienne decyzyjne) kodowane są na kilku do kilkunastu bitach. Poszczególny bit

nazwany jest genem. Przy takiej interpretacji można mówić o efekcie poligeniczności – kilka

genów reprezentuje jedną cechę.

Geny pierwszego pokolenia wybierane są w drodze losowania, po czym następuje ocena

osobników z wykorzystaniem funkcji przystosowania. Każdemu osobnikowi przydzielana jest

jego wartość, będąca wyliczoną przez funkcję przystosowania liczbą. W następnym kroku

osobniki są reprodukowane do następnego pokolenia (liczba osobników w pokoleniu jest

stała). Reprodukcja następuje zgodnie z zasadą ruletki. Każdemu osobnikowi z populacji

odpowiada sektor koła o rozmiarze proporcjonalnym do wartości funkcji przystosowania.

Następnie losujemy fragment koła (liczbę na ruletce), tyle razy, ile jest osobników w

populacji. Osobniki, którym przyporządkowany jest większy wycinek koła, mają

podwyższone szanse na przejście do następnego pokolenia (Goldberg, 1998). Dla każdego

wylosowanego osobnika tworzymy dokładną replikę, która stanowi potomka wchodzącego do

Zastosowanie algorytmów genetycznych w prognozowaniu popytu

następnego pokolenia. Można zauważyć, że dla osobników o dużej wartości funkcji

przystosowania, istnieje znacznie większe prawdopodobieństwo, że będą mieć kilku

identycznych potomków niż w przypadku osobników o małej wartości funkcji

przystosowania.

Kolejnym krokiem algorytmu genetycznego jest zastosowanie operatorów genetycznych:

krzyżowania i mutacji. Krzyżowanie realizowane w pracy jest jednopunktowe i polega na

wymianie fragmentu genotypu pomiędzy dwoma osobnikami (Rysunek 1.). Przy założonym

prawdopodobieństwie krzyżowania losujemy czy dany osobnik będzie podlegał krzyżowaniu,

a następnie, jeżeli został wybrany, losujemy osobnika z populacji, z którym ma zostać

skrzyżowany.

losowo

wybrane

miejsce

krzyżowania

1 0 0 0 0 1 0 1 0 1 0 0

osobnik 1

1 1 1 0 0 0 1 1 1 1 0 1

osobnik 2

krzyżowanie

1 0 0 0 0 0 1 1 1 1 0 1

osobnik 1

1 1 1 0 0 0 0 1 0 1 0 0

osobnik 2

Rysunek 1. Schemat krzyżowania jednopunktowego

Mutacja polega na zamianie wartości pojedynczego genu na przeciwny ( Rysunek 2 .).

Przeprowadzono eksperymenty symulacyjne dwoma metodami realizacji mutacji:

dwustopniowo i jednostopniowo. Mutacja dwustopniowa – najpierw losujemy, czy dany

osobnik będzie mutowany, następnie losujemy dla każdego genu, czy ma on być zmutowany.

Prawdopodobieństwo mutacji poszczególnego genu jest więc iloczynem prawdopodobieństwa

mutacji osobnika oraz prawdopodobieństwem mutacji genu. Przeprowadzone doświadczenia

wykazały, że lepsze efekty daje mutacja jednostopniowa. Polega ona na tym, że dla każdego

genu przeprowadzane jest losowanie, czy ma on być mutowany, czy też nie – brane pod

uwagę jest więc tylko jedno prawdopodobieństwo mutacji genu. Zastosowanie mutacji

jednostopniowej powodowało, że większa liczba osobników podlegała mutacji i rozkład

mutacji na poszczególnych osobników był więc bardziej równomierny niż w przypadku

mutacji dwustopniowej, gdzie mutacji podlegała mniejsza liczba osobników, natomiast

Zastosowanie algorytmów genetycznych w prognozowaniu popytu

mutacje te były bardziej skoncentrowane (jeden osobnik był mutowany kilka razy). Duża

liczba przeprowadzonych doświadczeń wykazała, że dobrze dobrana wartość

prawdopodobieństwa mutacji znacznie poprawia efektywność algorytmu. Przy zbyt małym

prawdopodobieństwie mutacji, następuje szybka zbieżność algorytmu do jednego osobnika

(maksimum lokalnego), natomiast zbyt duża wartość prawdopodobieństwa mutacji, znacznie

przedłuża czas potrzebny na znalezienie wystarczająco dobrego rozwiązania.

1 0 0 0 0 1 0

1 0 1 0 0 1 0

Rysunek 2. Mutacja jednego genu osobnika

W przypadku gdy występują trudności ze znalezieniem maksimum globalnego ze

względu na zbieżność osobników do maksimów lokalnych istnieje możliwość zastosowanie

makromutacji.

3. Zastosowanie algorytmów genetycznych w prognozowaniu okresowego popytu

3.1. Postać funkcji popytu

Propozycja funkcji popytu powinna wynikać ze znajomości wewnętrznego

i zewnętrznego środowiska przedsiębiorstwa. Nie istnieje możliwość zbudowania ogólnej

funkcji, pasującej do przedsiębiorstw działających w różnych branżach lub innych warunkach

ekonomicznych. Dla jednego przedsiębiorstwa wielkość sprzedaży będzie uzależniona tylko

od jednego czynnika, dla innego, mogą być to setki czynników wzajemnie powiązanych,

trudnych do jednoznacznego określenia. Dokładność prognozy sprzedaży będzie więc

zależała od określenia czynników wpływających na popyt oraz w jakim stopniu wpływają one

na popyt. Często sprowadza się to określenia klasy funkcji, np. czy ma być to funkcja liniowa,

o postaci wielomianowej, eksponencjalna, logarytmiczna.

Wydaje się, że podstawowym czynnikiem wpływającym na wielkość sprzedaży, jest

cena. Jako pierwsze przybliżenie można przyjąć, że funkcja sprzedaży ma postać:

(

)

gdzie:

D – wielkość sprzedaży;

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: