zak, informatyka
[ Pobierz całość w formacie PDF ]
Zmodyfikowany algorytm genetyczny dla
dwuwymiarowego nieregularnego problemu
optymalnego rozkroju
Sławomir
Zak
Politechnika Krakowska
Mi edzywydziałowy Kierunek Informatyka Stosowana, Rok IV
slawomir.zak@gmail.com
Streszczenie
Problemy optymalnego rozkroju wystepuj a niezmiernie czesto w róznych dzie-
dzinach techniki. Opracowano liczne algorytmy pozwalaj ace na rozwi azywanie szcze-
gółowych wariantów tychze problemów (rozkrój gilotynowy, niegilotynowy itp.) W
artykule zaproponowano zmodyfikowany algorytm genetyczny pozwalaj acy na opty-
malizacje wykroju elementów o nieregularnych kształtach z powierzchni dwuwy-
miarowych. Przedstawiono wyniki symulacji, w trakcie których zbadano wpływ do-
boru standardowych operatorów genetycznych. Pokazano równiez mozliwosc prak-
tycznego uzycia algorytmu w zastosowaniach inzynierskich dzieki integracji z pro-
gramem AutoCAD 2007.
Słowa kluczowe:
problem rozkroju, algorytm genetyczny, automatyzacja AutoCAD
1 Wstep
Problem rozkroju to zagadnienie, dla którego istnieje szereg mozliwych wariantów (roz-
krój gilotynowy, niegilotynowy, nieregularny itp.). Najogólniej mozna go scharakteryzo-
wac w nastepujacy sposób: dysponuj ac jednolitym płaskim elementem (płat blachy, kartka
papieru) o okreslonym wymiarze oraz zbiorem kształtów, poszukujemy takiego ich roz-
mieszczenia na tym elemencie, aby zminimalizowac ilosc powstałych scinków podczas
ich wycinania.
Pierwsze badania nad problemem rozkroju zostały zapocz atkowane w roku 1940,
gdzie w pracy [1] rozwazano optymalny podział prostok ata na kwadraty. W pózniejszych
latach wykazano NP-zupełnosc problemu rozkroju jak i przedstawiono szereg róznych
jego odmian czesto wraz z dedykowanymi dla nich algorytmami. W niniejszym artyku-
le rozpatrywano minimalizacje powierzchni uzytego płata materiału, maj acego zadekla-
rowan a z góry wysokosc i nieograniczon a długosc, wycinaj ac z niego elementy o nie-
regularnych kształtach [2]. Dla tak postawionego problemu został zaproponowany oraz
przebadany, pod wzgledem efektywnosci działania, uniwersalny algorytm genetyczny z
dodatkowym parametrem pozwalajacy na opymalizacje ułozenia zarówno elementów re-
gularnych jak i nieregularnych. Przeanalizowano wpływ doboru operatorów genetycznych
1
na jakosc otrzymywanego rozwi azania celem doboru ich najlepszej kombinacji. Dodatko-
wo została przedstawiona mozliwosc praktycznego uzycia algorytmu w zastosowaniach
inzynierskich dzieki integracji z programem firmy Autodesk - AutoCAD 2007.
2 Charakterystyka zastosowanego algorytmu
Ze wzgledu na nieregularny charakter wycinanych elementów składowane s a one w pliku
XML w postaci wektorowej. Takie podejscie jest bardzo wygodne, jezeli chodzi o ła-
twosc manipulowania geometri a kształtu i pozwala w prosty sposób definiowac dowoln a
liczbe otworów (ang. holes) wewn atrz figur. Niesie jednak ze sob a trudnosc w okresleniu
stanu, kiedy dwie figury nachodz a na siebie wymagaj ac zastosowania skomplikowanych
technik badania przecinania sie krawedzi [3]. Problem ten został rozwi azany poprzez za-
stosowanie rasteryzacji figur i porównywanie, czy poszczególne piksele dwóch figur nie
nachodz a na siebie. Została tu równiez uzyta technika zmniejszaj aca rozmiar macierzy
rastra, poprzez zgrupowanie pikseli i przechowywanie ich jako 32-bitowej zmiennej typu
Integer [4].
Stworzony algorytm wykorzystuje technike układania elementów na tasmie zwan a
Bottom-Up-Left-Justified [5], w której rozwi azanie jest sekwencj a wystepuj acych kolejno
po sobie kształtów układanych pocz awszy od górnego lewego rogu tasmy kolejno w dół,
a nastepnie coraz bardziej na prawo, jezeli figury nie mieszcz a sie juz w danej kolumnie.
Dodatkowo zastosowano mozliwosc obrotu figur o nastepuj ace k aty: 0
±
, 90
±
, 180
±
, 270
±
,
co zapewnia wieksz a swobode w układaniu rozwi azania.
Zastosowany sposób rozmieszczania kształtów na tasmie uwzgledniaj acy k aty obrotu
figur z góry odrzuca mozliwosc uzycia binarnego kodowania z jakim najczesciej mamy
do czynienia w przypadku algorytmów genetycznych. Z tego tez powodu zastosowano
chromosom o nastepuj acej budowie:
<
(
X
1
;R
1
)
;
(
X
2
;R
2
)
;
(
X
3
;R
3
)
;:::;
(
X
i
;R
i
)
;:::;
(
X
n
;R
n
)
>
(1)
gdzie :
(
X
i
;R
i
)- okresla połozenie oraz k at obrotu elementu
Funkcja przystosowania rozwi azania okreslona jest jako liczba pikseli na długosc wy-
maganych do rozmieszczenia wszyskich układanych kształtów. Wartosci blizsze zeru cha-
rakteryzuj a rozwi azania lepsze.
3 Zastosowane operatory genetyczne
Zaimplementowano oraz sprawdzono efektywnosc działania dwóch klasycznych operato-
rów selekcji -
selekcja metod a koła ruletki
(R) oraz
selekcja turniejowa
(T). W przypadku
pierwszej proporcjonalnie czesciej wybierane s a osobniki o funkcji przystosowania bliz-
szej zeru. Natomiast selekcja turniejowa tworzy podpopulacje o rozmiarze 10% populacji
wejsciowej z losowo wybranymi osobnikami i dopiero z niej dokonywany jest wybór ko-
lejnego rodzica.
Specyficzna budowa chromosomu, w której zakodowane rozwi azania ma charakter
permutacyjny bez powtórze n, wymaga zastosowania specjalnych operatorów krzyzowa-
nia, które bed a czuwały, aby nie dochodziło do generowania błedów. Takie ograniczenie
2
posiada wiekszosc operatorów krzyzowania znanych z problemu TSP (Traveling Sale-
sman Problem). W toku bada n wykorzystano nastepuj ace krzyzowania:
jednopunktowe
(1PX),
dwupunktowe
(2PX),
porz adkowe
(DOX) [6],
liniowe
(LOX) [7],
pozycyjne
(PBX)
[8],
z czesciowym dopasowaniem
(PMX) [9],
cyklicze
(CX) [10] oraz
równomierne
(EX).
Wszystkie powyzsze operatory pracuj a na całym chromosomie przetwarzaj ac zarówno
kolejnosc układanych elementów jak i k aty obrotu.
Głównym zadaniem operatorów mutacji jest zapewnienie wyjscia algorytmu z lokal-
nego minimum. Na bazie ich klasycznych wersji, stosowanych zazwyczaj przy binarnym
kodowaniu chromosomu, czyli mutacji
jednopunktowej
(1PM),
dwupunktowej
(2PM),
równomiernej
(EM) stworzono operatory, które nie pracuj a na całym rozwi azaniu (chro-
mosomie) a jedynie na jego czesci (k atach obrotu kształtów). W ten sposób wyjscie z
lokalnego minimem zapewnione jest, dzieki mozliwosci obrotu figury o jeden z losowo
wybranych k atów (0
±
, 90
±
, 180
±
, 270
±
).
W ramach prób podniesienia efektywnosci algorytmu zaproponowano i przebadano
dodatkowy operator genetyczny. Istota jego działania jest nastepuj aca: z pewnym praw-
dopodobie nstwem czesc osobników w populacji (10%) zostaje usunieta, a na ich miejsce
wprowadzane s a nowe. Eliminowane osobniki wybierane s a w sposób losowy, co ma za-
pewnic wieksz a róznorodnosc populacji.
4 Implementacja algorytmu
Algorytm został zaimplementowany w srodowisku Borland Developer Studio 2006 z wy-
korzystaniem jezyka C++. Wiekszosc kodu oparto o biblioteke STL (Standard Template
Library) celem zagwarantowania jak najwiekszej wydajnosci. Schemat blokowy algoryt-
mu przedstawiono na Rys. 1.
Rys. 1: Diagram blokowy algorytmu
Fig. 1: Block diagram of the implemented algorithm
3
5 Wyniki przeprowadzonych testów
Przeprowadzono eksperymenty badaj ace wpływ róznych kombinacji operatorów gene-
tycznych na jakosc uzyskiwanych wyników. Wykonano próby zarówno z zaproponowa-
nym dodatkowym parametrem jak i bez niego. Testy zostały przeprowadzone według na-
stepuj acego planu Tab. 1:
Tab. 1: Zastosowane kombinacje operatorów genetycznych
Test Selekcja Krzyzowanie Mutacja Test Selekcja Krzyzowanie Mutacja
1
R
1PX
1PM
25
T
1PX
1PM
2
R
1PX
2PM
26
T
1PX
2PM
3
R
1PX
EM
27
T
1PX
EM
4
R
2PX
1PM
28
T
2PX
1PM
5
R
2PX
2PM
29
T
2PX
2PM
6
R
2PX
EM
30
T
2PX
EM
7
R
DOX
1PM
31
T
DOX
1PM
8
R
DOX
2PM
32
T
DOX
2PM
9
R
DOX
EM
33
T
DOX
EM
10
R
LOX
1PM
34
T
LOX
1PM
11
R
LOX
2PM
35
T
LOX
2PM
12
R
LOX
EM
36
T
LOX
EM
13
R
PBX
1PM
37
T
PBX
1PM
14
R
PBX
2PM
38
T
PBX
2PM
15
R
PBX
EM
39
T
PBX
EM
16
R
PMX
1PM
40
T
PMX
1PM
17
R
PMX
2PM
41
T
PMX
2PM
18
R
PMX
EM
42
T
PMX
EM
19
R
CX
1PM
43
T
CX
1PM
20
R
CX
2PM
44
T
CX
2PM
21
R
CX
EM
45
T
CX
EM
22
R
EX
1PM
46
T
EX
1PM
23
R
EX
2PM
47
T
EX
2PM
24
R
EX
EM
48
T
EX
EM
Ta
b. 2: Przyjete wartosci parametrów steruj acych algoryt
mu
Parametr
Wartosc
Prawdopodobie nstwo krzyzowania
0.6
Prawdopodobie nstwo mutacji
0.05
Rozmiar populacji
30
Liczba epok
20
Liczba powtórze n algorytmu
5
Dodatkowy parametr (gdy był uzywany)
0.1
4
Wartosci zastosowanych parametrów algorytmu genetycznego zostały dobrane a prio-
ri, w oparciu o klasyczne przykłady z literatury, i przedstawione w Tab. 2. Wykorzystano
klasyczny algorytm, bez mechanizmów adaptacyjnych, co moze stanowic podstawe do
jego dalszej rozbudowy. Testy były prowadzone dla trzech instancji problemu rozkroju
licz acych kolejno 20, 40 i 60 elementów, a otrzymane wyniki zostały usrednione.
Rys. 2: Skutecznosc kombinacji operatorów genetycznych (mniejsze wartosci s a lepsze)
Fig. 2: Combinational efficiency for the genetic operators (lower values are better)
Rys. 3: Skutecznosc kombinacji operatorów genetycznych (mniejsze wartosci s a lepsze)
Fig. 3: Combinational efficiency for the genetic operators (lower values are better)
Otrzymane rezultaty zaprezentowano na Rys. 2 i Rys. 3. Ze wzgledu na stosunkowo
duze zróznicowanie wyników (Rys. 3), trudno jest jednoznacznie okreslic jaki wpływ na
wartosc funkcji przystosowania maj a poszczególne operatory. W przypadku algorytmu
bez zastosowanego dodatkowego parametru najlepsze rozwi azanie zapewniła kombina-
cja numer 9, natomiast z dodatkowym parametrem kombinacja numer 33 daj aca rów-
niez rozwi azanie globalnie najlepsze. Uzycie tego parametru, z selekcj a metod a ruletki,
w wiekszosci przypadków obniza efektywnosc algorytmu, a z selekcj a turniejow a przy-
nosi poprawe wyników.
5
[ Pobierz całość w formacie PDF ]