ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ v Praze Fakulta elektrotechnická Katedra měření
Separace signálů vibrací točivých strojů s využitím genetických algoritmů Diplomová práce
2010
Pavel KRPATA ČVUT Praha
Abstrakt Práce se zabývá metodami detekce různých kombinací vad valivých ložisek v točivých strojích. Hlavní náplní je návrh a experimentální ověření metod pro separaci frekvenčních pásem signálů vibrací generovaných vadou s využitím Genetických algoritmů. Obsahuje také srovnání těchto metod s klasickými metodami. V praktické části jsou otestovány různé modifikace algoritmu na reálných datech a zhodnocena schopnost detekce a rozlišení typu vady.
Abstract This diploma thesis deals with methods of detection different faults (fault combinations) on rolling bearings. The aim is to design and examine methods of separation of frequency bands from vibration signal generated by fault, exploiting Genetic algorithms. These methods are also compared with classical methods. In final part, different modifications of the algorithm are evaluated and their ability to distinguish the fault type is compared using real vibration signal.
Poděkování Na tomto místě bych chtěl poděkovat zejména vedoucímu mé diplomové práce Ing. Adamu Dočekalovi za konzultace, odborné připomínky a trpělivost, dále pak svému zaměstnavateli Ing. Ivanu Mikolášovi za poskytnutí času na studium i tuto práci, svým rodičům za poskytnutí zázemí a podpory a také všem ostatním, zejména přátelům, kteří mi přímo či nepřímo pomáhali při vzniku této práce.
2
OBSAH
3
Obsah 1 Úvod do řešeného problému
5
2 Metody detekce vad ložisek 2.1 Charakteristiky signálu vibrací ložisek . . . . . 2.2 Ukazatele přechodových dějů . . . . . . . . . . . 2.2.1 Crest faktor . . . . . . . . . . . . . . . . 2.2.2 Kurtosis . . . . . . . . . . . . . . . . . . 2.2.3 Robust Kurtosis . . . . . . . . . . . . . . 2.2.4 Porovnání ukazatelů přechodových dějů . 2.3 Klasické metody . . . . . . . . . . . . . . . . . . 2.4 Spectral Kurtosis a Kurtogram . . . . . . . . . 2.5 Využití adaptivní selekce frekvenčních pásem . . 2.6 Určení opakovací periody přechodových dějů . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
7 7 8 8 8 9 10 10 11 13 14
3 Optimalizační algoritmy 3.1 Úvod a přehled metod pro optimalizaci . . . . . . . . . . . . 3.2 Genetické algoritmy . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Úvod . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Princip genetických algoritmů . . . . . . . . . . . . . 3.2.3 Ohodnocovací funkce . . . . . . . . . . . . . . . . . . 3.2.4 Kódování jedinců . . . . . . . . . . . . . . . . . . . . 3.2.5 Selekce . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.6 Křížení . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.7 Mutace . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.8 Nahrazování generací . . . . . . . . . . . . . . . . . . 3.2.9 Teorie schémat . . . . . . . . . . . . . . . . . . . . . 3.3 Modifikace genetických algoritmů pro vyhledání více extrémů 3.3.1 Sdílení hodnocení . . . . . . . . . . . . . . . . . . . . 3.3.2 Dynamické sdílení hodnocení . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
16 16 18 18 18 22 22 23 24 27 27 28 30 31 32
4 Genetický algoritmus pro detekci vad 4.1 Hodnotící funkce . . . . . . . . . . . 4.2 Porovnání a výběr vhodného filtru . 4.3 Parametry genetického algoritmu . . 4.4 Modifikace genetického algoritmu . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
35 35 36 39 39
. . . .
40 40 43 43 46
ložisek . . . . . . . . . . . . . . . . . . . .
5 Výsledky experimentů 5.1 Popis ložiska a soustrojí použitého pro měření 5.2 Detekce vad . . . . . . . . . . . . . . . . . . . 5.2.1 Testy s využitím umělého signálu . . . 5.2.2 Testy s využitím reálného signálu . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
4
OBSAH
5.3 5.4
Rozlišitelnost vad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Identifikace vad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Zhodnocení identifikace vad . . . . . . . . . . . . . . . . . . . . . .
52 52 55
6 Závěr
57
A Slovník pojmů A.1 Diagnostika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2 Evoluční algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61 61 61
B Adresářová struktura přiloženého DVD B.1 Zdrojové kódy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Data a dokumentace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63 63 64
5
1
Úvod do řešeného problému
Práce se zabývá rozborem a experimentálním porovnáním několika metod detekce vad valivých ložisek ve stádiích, kdy se ještě viditelně neprojevují a neovlivňují správnou funkci zařízení. Ložiska patří mezi důležité součásti většiny točivých strojů. Při poruše ložiska je nutné často na dobu nezbytnou k zajištění opravy odstavit celý stroj, což přináší časové a ekonomické ztráty. Vada ložiska může mít navíc nepříznivý vliv na ostatní komponenty stroje nebo dokonce ohrozit zdraví obsluhy. Možnost detekovat vadu v okamžiku, kdy se ještě neprojevuje, umožňuje naplánovat odstávku stroje za účelem opravy vadné součásti dostatečně předem a minimalizovat tak možné nepříznivé dopady. Z těchto důvodů byla vyvinuta celá řada diagnostických metod pro analýzu stavu ložisek. Pozornost bude věnována metodám založeným na analýze vibrací zkoumané části stroje, snímaných pomocí akcelerometrů pevně spojených s danou částí. Počínající vada ložiska je charakteristická periodicky se opakujícími tlumenými vysokofrekvenčními zákmity1 . Z frekvence opakování těchto zákmitů lze navíc odhadnout na které části ložiska se vada nachází. Tyto průběhy, specifické pro vadu, jsou však téměř vždy utopeny v dalších komponentách signálu generovaných soustrojím a v šumu vznikajícím na všech prvcích měřicího řetězce, takže obecné metody, jako je například použití výkonové spektrální hustory, pro jejich identifikaci selhávají. Data vibrací
Pásmová propust
Detekce obálky
Vyhodnocení
Obrázek 1.1: Schema analýzy vibrací v pevně zvoleném pásmu
Klíčovou úlohou je proto nalezení vhodného frekvenčního pásma2 a odfiltrování nežádoucích komponent signálu. Nejednodušší metody (viz obr. 1.1) pracují s pevně zvoleným frekvenčním rozsahem, kde je signál po filtraci posuzován metodami pro detekci průběhů charakteristických pro hledanou vadu. Rozbor použitých metod je v kapitole 2.2. Tento přístup je vhodný pouze pro specifické případy, neboť frekvence generované vadou závisí na pracovních podmínkách stroje – například otáčkách, ale i dalších vlivech, které mohou ovlivnit vybuzené vlastní frekvence (módy). Dalším důležitým faktorem je typ a rozsah vznikající vady. Pozornost se proto zaměřuje na metody, schopné samostatně identifikovat a vybrat ze signálu komponenty charakteristické pro hledané vady, viz obr. 1.2. Oproti klasickým metodám je zde zavedena zpětná vazba, která se na základě vyhodnocení signálu po filtraci snaží adaptivně upravovat parametry filtru, tak aby charakter signálu po filtraci co nejvíce odpovídal průběhům charakteristickým pro vady ložiska. Jedná se vlastně o optimalizační úlohu, která se snaží pomocí různých modifikací filtru dosáhnout co nejlepšího vyhodnocení zvolenou funkcí pro detekci signálu charakteristického pro vadu 1 2
vznikajícími při styku poškozené části s dalšími částmi ložiska resp. frekvenčních pásem, pokud má být možnost detekovat více vad najednou
6
ÚVOD DO ŘEŠENÉHO PROBLÉMU
Data vibrací
Adaptivní pásmová propust
Nastavení pásma
Detekce obálky
Vyhodnocení
Vyhodnocení prech. deju
Obrázek 1.2: Schema analýzy vibrací s adaptivní selekcí frekvenčních pásem
(viz kapitola 2.2). Blok „Vyhodnocení přechodových dějů na obr. 1.2 představuje detekční metodu a blok „Nastavení pásma odpovídá algoritmu, který provádí vhodnou adaptaci pásma (příp. pásem) filtru. Pokud v signálu není přítomna složka pocházející od vady, dojde k nalezení nějaké jiné (falešné) složky, která je hledanému charakteristickému tvaru nejvíce podobná. Tento případ lze snadno rozpoznat podle výrazně nižšího výsledného ohodnocení (míry shody) a většinou i podle netypického výsledného pásma. Tato práce se zabývá podrobným rozborem a testováním metod s adaptivní selekcí frekvenčních pásem s využitím optimalizačních algoritmů založených na simulované evoluci – zejména genetických algoritmů. Výhodou těchto algoritmů je schopnost důkladného prozkoumání stavového prostoru, představovaného možnými frekvenčními pásmy, díky rysům paralelismu a vysoká odolnost proti uváznutí v lokálním extrému – tedy nalezení jiné (falešné) složky i když je přítomen lépe odpovídající signál, pocházející od skutečné vady.
7
2
Metody detekce vad ložisek
V této kapitole jsou rozebrány některé metody pro detekci vad valivých ložisek. Účelem je vytvoření představy a porovnání klasických metod a metod využívajících adaptivní selekci pásem.
2.1
Charakteristiky signálu vibrací ložisek
Signál ze senzoru vibrací lze rozdělit na složku x(t) související s hledanou vadou a okolní šum, zahrnující signály generované ostatními součástmi soustrojí n(t). s(t) = x(t) + n(t)
(2.1)
Složku x(t) lze dále aproximovat sekvencí zákmitů, vyvolaných setkáním defektu (trhlinky, pitting apod.) s další částí ložiska podle vztahu (2.2). x(t) = ak h(t − τk ) (2.2) k
průběh jednoho zákmitu vyvolaného defektem lze modelovat jako impulsní odezvu soustavy druhého řádu (2.3) se silným tlumením (malou časovou konstantou τ ). t
h(t) = e− τ cos 2πfv t
(2.3)
{ak } je posloupnost náhodných veličin, které udávají proměnnou intenzitu nárazu a zpravidla mívá periodický charakter. {τk } udává proměnný interval mezi nárazy, způsobený náhodnými prokluzy valivých elementů.3 Shrnutí vlastností signálu x(t) – viz [7] • širokospektrý: vlivem silného tlumení je doba trvání zákmitu velmi krátká. Důsledkem je velká šířka spektra, 4 zvláště v prvopočátečních stádiích defektu. Se zvětšováním defektu přestává mít buzení charakter diracova impulsu a frekvenční rozsah zákmitu se snižuje. Čím širší rozsah frekvencí signál generovaný vadou zasahuje, tím obtížnější je jeho detekce a separace – z toho plyne schopnost lepších metod5 detekovat vady v dřívějších stádiích. • malá energie: energie signálu vzniklého nárazem defektu je velmi malá, typicky méně než jedna tisícina celkové energie signálu. Větší podíl, nutný pro detekci, má pouze v omezeném frekvenčním rozsahu. • nestacionární: z výše popsaných důvodů a ze vztahů (2.2) a (2.3) je zřejmá nestacionární podstata. Signál má cyklostacionární 6 charakter nebo přesněji, vlivem náhodných posunů vlivem prokluzů pseudo-cyklostacionární charakter. 3
odchylka od periody bez prokluzů je malá – do 1 % pro časovou a frekvenční lokalizaci platí obdoba Heisenbergova principu neurčitosti: Δt · Δf = konst. 5 metody bez adaptivní selekce pásma zde výrazně zaostávají 6 statistické vlastnosti se v čase cyklicky opakují 4
8
METODY DETEKCE VAD LOŽISEK
2.2
Ukazatele přechodových dějů
V této podkapitole jsou rozebrány metody vhodné pro určování přítomnosti přechodových dějů v signálu. Nejedná se přímo o metody detekce vad, ale často bývají jejich velmi důležitou součástí. 2.2.1
Crest faktor
V české literatuře známý také jako činitel výkmitu. Jedná se o poměr špičkové a efektivní hodnoty určitého rozsahu vzorků, viz vztah (2.4). C=
|x|peak xrms
(2.4)
V diagnostice je používaný pro detekci občasných výrazných vibračních rázů, které příliš neovlivní efektivní hodnotu, ale mají znatelný vliv na špičkovou hodnotu, čímž způsobí nárůst hodnoty crest faktoru. Při vyšší intenzitě rázů crest faktor, díky nárůstu efektivní hodnoty, opět klesá. Za rázy lze považovat i přechodové děje vzniklé vadami ložiska. Crest faktor je velmi jednoduchý ukazatel, vhodný pouze pro hrubé posouzení počínajících vad. Je také velmi náchylný na nahodilé špičky v signálu, které ani nemusí pocházet ze snímaných vibrací, ale mohou vzniknout později v některém místě měřícího řetězce a zpracování signálu. 2.2.2
Kurtosis
Kurtosis, známá také jako koeficient špičatosti, je veličina používaná k podrobnějšímu popisu pravděpodobnostních rozdělení. Charakterizuje rozložení hustoty pravděpodobnosti veličiny kolem její střední hodnoty.7 Rozdělení s málo se měnící pravděpodobností výskytu v celém rozsahu hodnot mají malou hodnotu kurtosis. Naopak rozdělení, kde se většina hodnot nachází blízko střední hodnoty, ale s jistou malou pravděpodobností je možný výskyt hodnot značně vzdálených od střední hodnoty dosahují vysokých hodnot kurtosis. Při výpočtu se obvykle kurtosis normuje tak, aby pro normální (Gaussovo) rozdělení vycházela nula. Na obr. 2.1 je ukázka různých pravděpodobnostních rozdělení a jejich hodnot kurtosis. Obecný vztah pro výpočet kurtosis je K=
μ4 E([X − E(X)]4 ) − 3 = −3 σ4 D(X)2
(2.5)
Dále se budou uvažovat pouze veličiny s nulovou střední hodnotou (u reálných dat dostatečné délky lze snadno dosáhnout jejím odečtením). K= 7
E(X 4 ) −3 E(X 2 )2
Obrazně tedy špičatost grafu hustoty pravděpodobnosti
(2.6)
Ukazatele přechodových dějů
9
Obrázek 2.1: Hodnoty kurtosis pro různá pravděpodobnostní rozdělení
Transformací náhodné veličiny Y = U 4 , kde U je normované normální rozdělení, výpočtem střední hodnoty E(Y ) a využitím vztahu pro rozptyl D(X) = E(X 2 ) − E(X)2 , z kterého pro normované normální rozdělení8 plyne E(U 2 ) = 1, lze ověřit že pro normální rozdělení je hodnota kurtosis skutečně K(U ) = 3. Vztah pro odhad kurtosis konečného diskrétního signálu: n 4 n 4 1 x xi n i i=1 K = n n (2.7) − 3 = n i=1 2 2 − 3 1 2 2 ( i=1 xi ) i=1 xi n Signál s osamoceně se vyskytujícími přechodovými ději s výrazným rozkmitem a krátkou dobou trvání (vysoké tlumení) dosahuje vysokých hodnot kurtosis, neboť většina vzorků se nachází poblíž9 a během přechodového děje, vybuzeného vadou, se na krátkou dobu mnohonásobně zvětší amplituda. 2.2.3
Robust Kurtosis
Kurtosis určená obvyklým způsobem (viz vztah (2.6)) je díky vysokým mocninám vstupních hodnot citlivá i na nahodile se vyskytující vyšší hodnoty10 , které nesouvisí s přechodovými ději. Pro zmírnění vlivu této vlastnosti se v diagnostice využívá tzv. robust kurtosis. Výpočet je obdobný, ale místo čtvrté mocniny vstupní veličiny v čitateli se používá druhá 8
pro které platí E(U ) = 0 a D(U ) = 1 Uvažujeme-li nulovou stejnosměrnou složku 10 i když ne tak silně jako crest faktor 9
10
METODY DETEKCE VAD LOŽISEK
mocnina a ve jmenovateli se rozptyl nahradí střední hodnotou absolutních hodnot veličiny, viz [12]. Na tuto modifikaci se dá také pohlížet jako na transformaci vstupní veličiny (sig nálu) pomocí druhé odmocniny X = (X). Vztah pro výpočet Robust kurtosis je opět normovaný tak, aby pro normální rozdělení vycházela kurtosis nulová a opět se uvažuje veličina s nulovou střední hodnotou. K =
E(X 2 ) − 1.571 E(|X|)2
(2.8)
Výpočtem střední hodnoty transformované veličiny Y = |U | lze, podobně jako u obecné kurtosis, ověřit, že K (U ) = 1.571. Pro odhad robust kurtosis z velkého počtu vzorků bude platit: n ni=1 x2i (2.9) K = n 2 − 1.571 ( i=1 |xi |) 2.2.4
Porovnání ukazatelů přechodových dějů
Pro ukázku funkce popsaných ukazatelů byl použit testovací signál vytvořený opakováním přechodového děje, daného vztahem (2.3) s vlastní frekvencí fv = 8 kHz a tlumením τ = 1/6000 s. Opakovací frekvence přechodového děje je 300 Hz a délka signálu 10 sekund. Souhrn hodnot ukazatelů pro bez šumu, různé kombinace signálu a aditivního šumu s gaussovským rozdělením amplitud a samotný šum je v tab. 2.1. Metoda
pouze signál
Crest faktor Kurtosis Robust Kurtosis
6,754 23,59 9,733
-0,707
SN R (dB) -4,23 -10,25
-13,77
7,395 5,037 0,418
6,892 6,273 1,812 0,506 0,160 0,0513
5,357 0,04329 0,0064
pouze šum 4,709 0,0018 0,0013
Tabulka 2.1: Porovnání ukazatelů přechodových dějů
Z porovnání hodnot je zřejmá nejhorší rozlišovací schopnost u crest faktoru, kde je poměr mezi čistým signálem a čistým šumem pouze 1,43. Kurtosis a robust kurtosis mají rozumný poměr k hodnotě pro čistý šum ještě při SNR kolem −10 dB – robust kurtosis kolem 40 a klasická kurtosis dokonce 281. Nicméně je nutné si uvědomit, že se jedná o umělý signál, výsledky pro naměřená data budou zhodnocena v kapitole 5.2.
2.3
Klasické metody
Tyto metody jsou s menšími či většími modifikacemi a rozšířeními založený na principu podle obr. 1.1. V této podkapitole je pro přehled popsán princip některých z nich.
Spectral Kurtosis a Kurtogram
11
Shock Pulse Method vyvinutá firmou SPM, využívá speciálních akcelerometrů s vlastní frekvencí okolo 32 kHz. Při rázu v ložisku dojde k vybuzení této frekvence v samotném akcelerometru. Ze signál jsou pak pomocí filtru pevně nastaveného na tuto frekvenci odstraněny nežádoucí složky a dále zpracován klasicky. Empirical Mode Decomposition – tato metoda provádí rozklad signálu na součet obecných kmitavých módů11 , nazývaných IMF – Intrinsic Mode Function. Od ostatních metod se liší tím, že operuje čistě v časové oblasti. Princip spočívá v proložení lokálních minim a maxim dvěma kubickými spline a odečtení střední hodnoty obou funkcí vzniklých prokladem. Toto se cyklicky opakuje, dokud dochází při odečítání ke změně přesahující určitý práh. Tímto postupem se získá první IMF a jeho opakovanou aplikací na zbytek signálu se získají další IMF, až do požadovaného počtu. Pokud signál obsahuje vysokofrekvenční kmitavé módy, vzniklé poškozením ložiska, je možné je identifikovat analýzou jednotlivých IMF. Kepstrální analýza – kepstrum (cepstrum) je definováno jako Fourierova transformace logaritmu výkonové spektrální hustoty a jeho jednotka je čas. Mezi jeho významné vlastnosti patří schopnost detekovat interval mezi frekvenčními složkami s konstantním rozestupem, které jinak nejsou ve spektru signálu rozeznatelné. Opakované tlumené přechodové děje si lze představit jako amplitudovou modulaci harmonického signálu o vlastní frekvenci komponenty ložiska nelineárním signálem. Produktem je řada postranních pásem s odstupem daném frekvencí opakování přechodového děje a jejich vyšších harmonických. Špička v kepstru pak přímo udává opakovací frekvenci zákmitů. Podobně jako u klasických metod je i tady nutné alespoň částečně ze signálu odstranit nežádoucí složky pomocí předřazeného filtru.
2.4
Spectral Kurtosis a Kurtogram
Spectral Kurtosis je statistický nástroj určený k detekci nestacionárních komponent signálu, např. sekvencí přechodových dějů v zašumělém signálu, o kterých výkonová spektrální hustota nepřináší žádné informace. Je to jednorozměrná spojitá funkce závislá na frekvenci. Její přesné stanovení pro skutečný signál je problematické, proto se, podobně jako u výkonové spektrální hustoty používají odhady. Původní definice odhadu Spectral Kurtosis je standardizovaný čtvrtý centrální moment12 přes reálné části STFT13 přes všechny hodnoty časového parametru. Pro diskrétní STFT spektrum X(m, k) tedy platí N −1 N −1 4 n=0 (x − x) X(n, k) SK(k) = X(n, k) (2.10) 2 · N −1 2 n=0 n=0 (x − x) X(n, k) 11
nemusí mít harmonický průběh Kurtosis 13 Okénkové Fourierovy transformace 12
12
METODY DETEKCE VAD LOŽISEK
Problémem je vhodná volba velikosti okna STFT, podle [11] je nutné aby jeho délka nebyla řádově větší než délka přechodového děje a zároveň zároveň šířka jeho spektra nebyla příliš velká vzhledem k frekvenčním změnám přechodového děje. Volbou délky okna se tedy nastavuje citlivost Spectral Kurtosis pouze na nestacionární děje s určitými parametry, které ale předem nejsou známé. Dalším parametrem na kterém závisí správnost funkce je velikost překryvu oken při posunu po časové ose. V [11] se doporučuje 75% překrytí. Kurtogram řeší tuto nevýhodu několikanásobným výpočtem kurtosis s postupným geometrickým zvyšováním frekvenčního rozlišení. Výpočet lze realizovat pomocí STFT a postupného zkracování délky okna – tento způsob umožňuje zvyšovat frekvenční rozlišení s libovolně malým krokem (omezeným pouze vzorkovací frekvencí). Jiný, rychlejší způsob využívá dvou prototypů FIR filtru – dolní a horní propust, kterými se signál rozdělí ve frekvenční oblasti na dva stejně velké úseky, pro které se vypočte kurtosis. Dále se u obou úseků vynecháním každého druhého vzorku (decimací) sníží vzorkovací frekvence na polovinu a znovu se aplikují na oba úseky stejné prototypy jako v prvním kroku. Tím dojde k dalšímu rozdělení obou podúseků ve frekvenční oblasti na poloviny. Tento postup se dále rekurzivně opakuje dokud není dosažena stanovená úroveň (počet úseků) – viz obr. 2.2a. Po každém dělení se na všechny filtrací nově vzniklé signály aplikuje kurtosis. Takto vznikne diskrétní sada hodnot kurtosis, parametrizované dvojicemi hodnot (fc , Δf ), kde fc je centrální frekvence pásma a Δf je šířka pásma. Tento způsob výpočtu se nazývá Fast Kurtogram.
(a)
(b)
Obrázek 2.2: Princip kurtogramu – převzato z [13]
Modifikace pro jemnější dělení používá dalších tří prototypů, pomocí kterých se v každém kroku ještě signál vyhodnocuje po rozdělení na tři stejně velká pásma – viz obr. 2.2b.
Využití adaptivní selekce frekvenčních pásem
13
Složitost algoritmu14 je O(L.N log N ), kde N je počet úrovní a L je délka prototypu filtru. Popsané metody výpočtu kurtogramu jsou podrobně rozebrány v [13]. Ukázka kurtogramu z reálného signálu s využitím robust kurtosis je na obr. 2.3. Maximum kurtogramu je na úrovni 3,5, což odpovídá šířce pásma 1365 Hz. Centrální frekvence pásma je 10240 Hz.
Obrázek 2.3: Ukázka kurtogramu reálného signálu
Z předchozího rozboru plyne že kurtogram je relativně jednoduchý, rychlý a deterministicky fungující algoritmus vhodný pro stanovení frekvenčního pásma defektu. Nevýhodou je omezená flexibilita testovaných frekvenčních pásem – pozice i šířka pásma jsou dány binárním rozkladovým stromem. Přesto patří kurtogram mezi úspěšně používané metody a v případě náročnějších požadavků lze využít alespoň pro počáteční odhad hledaného pásma.
2.5
Využití adaptivní selekce frekvenčních pásem
Princip adaptivní selekce frekvenčních pásem byl již naznačen v úvodní kapitole, blokové schéma je na obr. 1.2. Důvodem jejich vzniku je snaha o odstranění nevýhod výše uvedených metod a snaha o dosažení co nejpřesnější separace signálu generovaného defektem. Základem je filtr typu pásmová propust s proměnnými parametry, který je ovlivňován zpětnou 14
Notace O(g(n)) vyjadřuje asymptotický horní odhad složitosti nějaké funkce f (n). Pokud f (n) ∈ O(g(n), tak existuje c ∈ R+ a n0 ∈ N takové, že platí 0 ≤ f (n) ≤ c.g(n), n ≥ n0 .
14
METODY DETEKCE VAD LOŽISEK
vazbou tak, aby bylo dosaženo jistých parametrů výstupního signálu – zde co nejvyšší hodnoty některého z ukazatelů přechodových dějů. Využití zde nacházejí různé optimalizační algoritmy, kterým se věnuje následující kapitola. V případě klasických deterministických metod je třeba, aby počáteční nastavení filtru nebylo příliš vzdáleno od hledaného pásma, proto je třeba zvolit počáteční podmínky do místa předpokládaného výskytu rezonančních frekvencí ložiska, případně využít pro jejich hrubý odhad jinou metodu, například výše popsanou kurtosis. Pokročilejší optimalizační algoritmy, které již nemají čistě deterministickou podstatu, jsou schopny mnohem efektivnějšího prohledání prostoru možných řešení, a proto lze s jejich využitím nalézt správné pásmo i se značně vzdálenými počátečními podmínkami.
2.6
Určení opakovací periody přechodových dějů
Metoda použitá v této práci, ale i většina ostatních popsaných metod, se zaměřuje na nalezení pásem vlastních frekvencí poškozených součástí a intenzity nestacionárních jevů v nich obsažených. Tyto výsledky jsou postačující pro stanovení diagnózy pouze v oboru hodnot { bez vady, vada přítomna }. Pokud je požadavek na určení předpokládaného typu vady, je potřeba detekovat i frekvenci opakování zákmitů generovaných vadou, neboť ta je závislá mimo rychlosti rotace pouze na typu vady a lze ji předem stanovit. Předpokládané opakovací frekvence lze určit podle těchto vztahů, viz [1]
RD n fBP F O = fr 1 − cos β , vada vnějšího kroužku (2.11) 2 PD
RD n fr 1 − cos β , vada vnitřního kroužku (2.12) fBP F I = 2 PD
2 RD PD , vada valivého elementu (2.13) fBSF = fr 1 − cos β 2RD PD
RD 1 fF T F = fr 1 − cos β , vada klece ložiska (2.14) 2 PD kde RD je průměr valivého elementu, P D roztečný průměr ložiska (průměr dráhy středu valivých elementů) a β je úhel dotyku mezi valivým elementem a kroužky ložiska. Pro určení opakovací frekvence je nejprve nutné získat obálku signálu z vybraného pásma. Pro přesné stanovení obálky diskrétního signálu se používá Hilbertova transformace [1] definovaná následujícím vztahem 1 x˜(t) = H{x(t)} = π
∞ −∞
x(τ ) 1 1 dτ = x(t) ∗ t−τ π t
V praxi se Hilbertova transformace počítá s využitím Fourierovy transformace 1 1 −1 x˜(t) = F F {x(t)} · F π t
(2.15)
(2.16)
Určení opakovací periody přechodových dějů
15
Pomocí hilbertovy transformace je definován tzv. analytický signál xa (t) = x(t) + jH{x(t)}
(2.17)
z analytického signálu lze obálku vyjádřit takto A(t) = |xa (t)| = x2 (t) + x˜2 (t)
(2.18)
Získání obálky je v principu demodulace amplitudově modulovaného signálu, což v tomto případě znamená odstranění vysokých frekvencí vlastních kmitů součásti ložiska. Obálka bude mít charakter periodického signálu se základní frekvencí rovnou hledané opakovací frekvenci a jejích vyšších harmonických, viz spektrum na obr. 5.10. Pro automatické určení periody se osvědčila autokorelační funkce, která má u periodické funkce maxima v násobcích periody signálu, příklad je opět v experimentální části práce na obr. 5.11. V rámci práce byl pro automatickou detekci opakovací periody navržen a otestován algoritmus (viz schéma 2.4), využívající detekci špiček pomocí změny znaménka první diference nevychýleného odhadu autokorelační funkce ˆ xx (r) = R
N −r 1 x(n) · x(n + r) N − r n=1
(2.19)
Uvažujme pouze první polovinu kladné části autokorelační funkce, kde jsou hlavní maxima výrazná. Pro odstranění nevýrazných špiček je nejprve na autokorelační funkce aplikován filtr typu klouzavý průměr. Poté je získána první diference Δx(n) = x(n) − x(n − 1) a vyhledány body, kde dochází k přechodu z kladných do záporných hodnot diference – maxima. Maxima jsou poté ještě prahována střední hodnotou autokorelační funkce, aby se odstranila nižší maxima, nesouvisející s opakovací frekvencí. Opakovací perioda je určena jako průměr časových vzdáleností mezi špičkami. Signál po filtraci
Detekce obálky
Autokorelační funkce (nevychýlený odhad)
Klouzavý průměr N = 16
1.Diference
Detekce špiček podle změny znaménka diference
Odstranění špiček pod střední hodnotou autokor. funkce
Střední hodnota diference časů špiček
Perioda špiček
Obrázek 2.4: Vývojový diagram detekce periody přechodových dějů
16
OPTIMALIZAČNÍ ALGORITMY
3
Optimalizační algoritmy
Vzhledem k tomu že optimalizace patří mezi základní stavební kámen této práce, bude se následující kapitola věnovat obecnému úvodu do optimalizačních metod a podrobnějšímu popisu evolučních algoritmů, které byly v práci použity.
3.1
Úvod a přehled metod pro optimalizaci
Obecná matematická definice optimalizační úlohy je nalezení takových hodnot vstupů určité funkce n-proměnných f (x1 , x2 , . . . , xn ), aby její hodnota dosahovala nějakého extrému15 . Funkce bývá nazývána jako účelová funkce, hodnotící funkce, případně ustáleným anglickým termínem fitness a její vstupní proměnné představují souřadnice v n-rozměrném prostoru, který se obyčejně nazývá stavový prostor. Ve stavovém prostoru dále nemusí být povoleny všechny kombinace hodnot jednotlivých proměnných – například pro n-tice reálných čísel nemusí být přípustné všechny kombinace hodnot obsažené v Rn . Zpravidla je snaha nalézt globální extrém, nicméně ve složitějších případech nelze globální extrém snadno nalézt, případně nelze ani zjistit zda nalezený extrém je globální nebo pouze jeden z lokálních. V těchto případech se lze spokojit i dostatečně kvalitním (splňujícím určité požadavky) lokálním extrémem. V praxi představuje optimalizační úloha nějaký netriviální fyzikální, ekonomický, logistický, algoritmický nebo jiný problém, který lze v některých případech vyjádřit exaktně matematicky řešitelnou funkcí. Většinou je matematický model klasickými matematickými metodami obtížně řešitelný a v nejhorším případě nelze sestavit vůbec a dosahované výsledky pro různé vstupy je nutné zjišťovat přímo na reálném systému, což přináší značná omezení. V nejtriviálnějším případě, kdy vstupy mohou nabývat pouze malého množství diskrétních hodnot lze použít postupného prohledání celého stavového prostoru, tedy vyzkoušení všech přípustných kombinací16 . Tato metoda však, zvláště u mnoharozměrných úloh, velmi brzy naráží na nepřijatelnost doby potřebné k prohledání celého stavového prostoru. Pro matematicky dobře popsané problémy lze použít deterministické informované metody, které využívají k orientaci ve stavovém prostoru informací získaných z popisu účelové funkce f . Volba konkrétní metody záleží na typu problému, zde je pro ukázku několik často používaných. Pro spojitý stavový prostor: n Lineární programování – pracuje pouze s lineární účelovou funkcí n typu f = j=1 cj xj a konvexními lineárními omezujícími podmínkami typu j=1 aij xj ≤ bi . Pomocí existujících algoritmů lze tyto úlohy vyřešit v malém počtu kroků a jedná se vždy o globální extrém. 15 16
minima nebo maxima anglicky též brute-force
Úvod a přehled metod pro optimalizaci
17
Nelineární programování – zahrnuje řadu metod využívajících zpravidla znalost několika prvních derivací zkoumané funkce. Nejednodušší metoda postupuje ve stavovém prostoru po malých krocích ve směru gradientu funkce z nějakého, vhodně zvoleného, počátečního bodu. Další metody využívají hodnotu druhé derivace k přímějšímu postupu k extrému. Nevýhodou je nutnost znalosti derivací funkce a nalezení pouze extrému, který je nejblíže k počátečnímu bodu a nemusí být globální. Pro diskrétní stavový prostor: Metoda větví a mezí – využívá postupné větvení s podle různě modifikované vybrané vstupní proměnné. V průběhu hledání udržuje odhadem horní a dolní meze a vylučuje větve, které mají horní mez nižší než aktuální dolní mez řešení. Diskrétní gradientní metoda (Hill-Climbing) – vychází z předem zvoleného bodu, v každém kroku vybere ze všech sousedních pozic ve stavovém prostoru bod s nejvyšším ohodnocením a pokud je lepší než aktuální, použije ho v příštím kroku. Pokud takový bod není, algoritmus končí. Nevýhodou je vyhledání pouze lokálního extrému v závislosti na zvoleném počátečním bodu. Výhodou je možnost použití na funkce, o jejichž vnitřním chování nejsou dostupné téměř nebo vůbec žádné informace17 . Dále popisované metody již budou zaměřeny právě na takový druh funkcí. Taboo Search – jedná se o Hill Climbing rozšířený o paměť, do které se ukládá určité množství naposled navštívených míst – tyto místa jsou v dalších krocích zakázaná (tabu). Další rozdíl oproti Hill Climbing je pokračování i v případě že žádný soused není lepší než aktuální pozice. Tento výčet je pouze orientační, zcela byly opomenuty algoritmy využívající postupné hledání částí výsledného řešení, využívané například pro hledání nejkratší a nejméně nákladné cesty k cíli. V případě potřeby nalezení globálního nebo alespoň co nejlepšího lokálního maxima komplikovaných účelových funkcí18 a problémů typu Black Box19 bývá šance na dosažení dobrého výsledku s využitím stochastických20 algoritmů. Právě prvek náhody umožňuje s jistou nenulovou pravděpodobností i přechod od lepšího řešení k horšímu a tím uniknout z lokálního extrému, ve kterém čistě deterministické algoritmy uváznou. Lokální prohledávání (First-improving) – náhodně se vybere bod z určitého okolí aktuální pozice. Pokud je lepší než aktuální, použije se v následujícím kroku jako nový, jinak se pozice nemění. Výchozí umístění se volí náhodně. Jedná se o nejednodušší stochastický algoritmus – umí opustit lokální extrém, ale je značně pomalý. 17
funkce typu Black Box zejména NP-těžké a NP-úplné problémy 19 o vnitřním fungování systému nevíme nic nebo je tak komplikovaný, že je jednodušší ho považovat za uzavřený 20 využívajících prvků náhody 18
18
OPTIMALIZAČNÍ ALGORITMY
Simulované žíhání (Simulated Annealing) – algoritmus inspirovaný procesy probíhajícími během chladnutí rozžhaveného kovu, jedná se o rozšíření lokálního prohledávání. Z určitého okolí21 aktuální pozice x se vybere náhodně libovolný bod y. Pokud je lepší než aktuální, prohlásí se za nový aktuální. V opačném případě se může také f (y)−f (x) stát aktuálním, ale jen s pravděpodobností p = e− T , tedy čím horší je zvolený bod, tím menší pravděpodobnost přesunu. Faktor T se nazývá plán chladnutí (cooling schedule) a za běhu je postupně snižován, což vede ke snižování pravděpodobnosti přesunu na horší pozice. Zvláštnost algoritmu je v tom, že se z na počátku značně stochastického postupně přechází na deterministický, což umožní na začátku překonání oblastí nízké kvality a ke konci přesnější zaměření nahrubo nalezeného extrému. Evoluční algoritmy – skupina algoritmů inspirovaných evolucí a přirozenou selekcí v přírodě. Nepracují s jedním dílčím řešením, ale zároveň z celou množinou vzájemně různých kandidátů řešení, což zavádí do prohledávání prvky paralelismu. Podstatou je simulace přirozeného výběru, kdy mají větší šanci kvalitnější jedinci22 a jejich vzájemná kombinace (křížení) nebo vzájemné ovlivňování. Mezi evoluční algoritmy se řadí zejména Genetické algoritmy. Z dalších, méně obvyklých lze jmenovat Memetické algoritmy, Ant Colony Optimization23 nebo Particle Swarm Optimization24 .
3.2
Genetické algoritmy
Genetické algoritmy patří mezi nejznámější zástupce metod založených na simulované evoluci. Tato práce je na nich z velké části založena, proto budou rozebrány podrobněji. 3.2.1
Úvod
Genetické algoritmy patří mezi evoluční algoritmy, jejichž charakteristickým znakem je simulace průběhu přirozeného vývoje živočišného nebo rostlinného druhu v přírodě. Využívají dvou principů, a to reprodukce, při které dochází ke kombinaci genetického materiálu více (zpravidla dvou) jedinců a přirozené selekce, podle které mají větší šanci na přežití lepší a silnější jedinci oproti horším a slabším. Kombinací těchto dvou principů se docílí postupného přizpůsobování jedinců prostředí (daného optimalizovanou úlohou). 3.2.2
Princip genetických algoritmů
Jak již bylo zmíněno, genetické algoritmy patří do obsáhlejší množiny evolučních algoritmů, které nepracují s jedním kandidátem řešení25 , ale z celou množinou potenciálních řešení, 21
Nemusí jít jen o bezprostřední sousedy. Jedinec je u evolučních algoritmů ekvivalentní pojem ke kandidátu na řešení. 23 Simulace spolupráce mravenců při hledání nejkratší cesty mezi hnízdem a potravou. 24 Simulace skupiny částic, pohybujících se stavovým prostorem určitým směrem a rychlostí, které se vzájemně ovlivňují. 25 Reprezentující nějakou pozici ve stavovém prostoru. 22
Genetické algoritmy
19
které se v průběhu navzájem vhodně ovlivňují. Tento princip zavádí prvky kooperativního paralelismu a umožňuje lépe prohledat stavový prostor. V genetických algoritmech pochází hlavní inspirace z reprodukce organismů v přírodě, kdy je předávána část genetické informace z obou rodičů na potomka, který obsahuje kombinaci jejich vlastností (ať už těch lepších nebo horších). U skutečných organismů je informace uložena v řetězcích DNA, které jsou rozděleny do určitého počtu chromozomů. Jednotlivé řetězce obsahují určité úseky, představující jednotlivé rysy jedince. Tyto úseky se nazývají geny a jejich možným hodnotám se říká alely. Souhrn všech genů se nazývá genotyp. Význam hodnot všech genů představuje fenotyp, což je souhrn vlastností jedince. Do hry vstupuje také mutace, která představuje nedokonalosti a chyby při kopírování genetické informace, a dává tak možnost vzniku zcela nových vlastností. Mutace je velmi důležitá v evolučním procesu, bez ní by se vývoj druhu v určitém okamžiku zastavil. Dalším prvkem, převzatým z oboru biologie, je přirozená selekce. Životní prostředí organismů není nikdy ideální, organismus musí odolávat nepříznivým vlivům a mít k dispozici dostatek potravy a jiných zdrojů, které jsou omezené. K tomu aby jedinec ve svém prostředí přežil potřebuje mít určité předpoklady (dobré vlastnosti). Tyto vlastnosti nejsou zárukou přežití, ale značně zvyšují jeho pravděpodobnost. Zároveň není vyloučeno přežití horších, slabších jedinců. Princip činnosti genetických algoritmů je znázorněn vývojovým diagramem na obr. 3.1. Prvním krokem je vytvoření množiny jedinců, kteří představují výchozí stav simulované evoluce druhu. Jedinci jsou v dalším kroku ohodnoceni pomocí fitness funkce. Inicializace bývá často náhodná, ale lze využít apriorních znalostí problému a část populace vytvořit tak, aby již na začátku obsahovala určité pozitivní rysy. Vždy by měla být alespoň část populace vytvořena čistě náhodně, jinak se snižuje kvalita prohledání stavového prostoru a významně zvyšuje riziko předčasné konvergence uváznutí v lokálním extrému. Následuje hlavní cyklus algoritmu, v němž proběhne nejprve selekce kandidátů na křížení na základě jejich kvality. V dalším kroku se z vybraných jedinců vytvoří náhodné páry a pomocí křížení a následné mutace vznikne množina potomků. V posledním kroku cyklu se pomocí nahrazovacího operátoru zkombinuje původní populace s potomky a dojde k vytvoření nové generace populace, stejně velké jako původní. Na konci každého cyklu se zkoumá pomocí ukončovacích podmínek, zda již bylo dosaženo nějaké mezní kvality populace26 , která je postačující nebo zda ještě dochází ke zlepšování nebo se kvalita populace ustálila a dále se nezlepšuje. Omezení může být také časovým limitem – je potřeba nejlepší možné řešení, ale čas k jeho získání je omezený. Po skočení evoluce je jako řešení z populace vybrán jeden nebo několik nejlepších jedinců.
26
zpravidla kvalita nejlepšího jedince
20
OPTIMALIZAČNÍ ALGORITMY
Generování výchozí populace n = 1
Ohodnocení počáteční populace
Počátek n-té generace
Selekce rodičů
Křížení
n = n+1
Mutace
Nahrazení rodičů potomky
Ohodnocení nové populace
ne
Splněny ukončovací podmínky?
ano Finální populace
Vyber nejlepšího jedince z populace
Obrázek 3.1: Vývojový diagram obecného genetického algoritmu
Genetické algoritmy
21
Výhody genetických algoritmů • schopnost pracovat se všemi druhy optimalizačních problémů – od nelineárních, nehladkých, nespojitých, multimodálních27 funkcí až po problémy typu Black Box. • plošné prohledávání stavového prostoru na mnoha různých místech, využívající prvky paralelismu. • odolnost proti uváznutí v lokálním extrému • možnost aplikace na systém měnící se dynamicky v čase Nevýhody genetických algoritmů • neopakovatelnost – při následném běhu algoritmu zpravidla není dosaženo stejného (zpravidla však velmi blízkého) řešení jako v předchozím běhu, což je důsledek stochastických složek algoritmu. • pomalejší konvergence k extrému, na rozdíl od většiny algoritmů pracujících s jedním kandidátem řešení. Základní parametry běhu genetického algoritmu jsou uvedené v tabulce 3.1. PopSize
Velikost populace – jeden z nejdůležitějších parametrů, má velký vliv na kvalitu prohledání stavového prostoru
Px
Pravděpodobnost s jakou bude na jedince vybrané selekcí aplikován operátor křížení, ostatní jedinci budou zkopírováni bez změny. Zpravidla je křížení aplikováno na všechny jedince, tedy Px = 1
Pm
Pravděpodobnost mutace – udává pro každý element (zpravidla bit) jedince, s jakou pravděpodobností dojde k jeho změně (zpravidla inverzi). Typická hodnota je 0,01–0,05.
selekční tlak
Určuje míru preference lepších jedinců nad horšími, většinou bývá dán implicitně operátorem selekce. V některých případech lze explicitně ovlivňovat, například počtem soupeřů v turnajové selekci. Velký selekční tlak urychluje eliminaci špatných jedinců, ale značně zvyšuje riziko předčasné konvergence v méně kvalitním lokálním extrému. Tabulka 3.1: Základní parametry běhu genetického algoritmu
Možné ukončovací podmínky pro běh genetického algoritmu: • maximální počet generačních cyklů • maximální počet volání ohodnocovací (fitness) funkce • maximální (resp. minimální) dosažená kvalita jedince 27
funkce má více extrémů
22
OPTIMALIZAČNÍ ALGORITMY • maximální počet generací bez nalezení lepšího jedince • minimální rozptyl (popř. směrodatná odchylka) kvality populace – malý rozptyl indikuje zkonvergovanou populaci, kdy je již malá pravděpodobnost nalezení jiného extrému
3.2.3
Ohodnocovací funkce
Ohodnocovací (fitness) funkce, společně s kódováním potenciálního řešení, jsou jedinými komponentami genetického algoritmu, které jsou problémově závislé, proto je třeba její tvorbě věnovat náležitou pozornost. Vstupem hodnotící funkce je chromozom představující jedince (potenciální řešení). Úkolem funkce je provést dekódování genotypu na fenotyp a stanovit míru kvality jedince jím představovaného. Míra kvality se většinou stanovuje jako reálné číslo. Jediný požadavek na ohodnocení je aby lepší jedinec dostal vyšší ohodnocení než horší jedinec. Funkce může obsahovat složité nelineární závislosti mezi vstupy (alely), může být nespojitá a nemusí přímo odrážet absolutní rozdíl kvality dvou porovnávaných jedinců. 3.2.4
Kódování jedinců
1 bit
Za základní způsob kódování se u genetických algoritmů považuje binární řetězec určité délky, do jehož jednotlivých částí jsou vhodně zakódovány vstupní veličiny optimalizovaného problému. Celý řetězec pak tvoří chromozom, jednotlivé úseky jsou geny, viz obr. 3.2.
Gen 1
Gen 2
Gen 3
Gen 4
Gen 5
Chromozom
Obrázek 3.2: Struktura chromozomu
Pokud jsou argumenty optimalizované funkce reálné je nutné zvolit vhodnou délku řetězce genu podle možného rozsahu hodnot a požadované přesnosti řešení ε. max(x) − min(x) L = Int log2 ε V případě konečného počtu diskrétních hodnot je třeba zvolit vhodné dekódování hodnoty, tak aby každé hodnotě alely odpovídal pokud možno stejné množství kombinací hodnot genu. Důležitá je i vhodná volba pořadí genů v chromozomu – hodnoty významně přispívající k řešení by měly být u sebe, neboť je tak menší pravděpodobnost rozbití nadějného stavebního bloku (viz kapitola 3.2.9 o schématech).
Genetické algoritmy
23
Další možnosti kódování, mimo binárního řetězce, jsou například sada reálných čísel28 , hodící se pokud jsou všechny optimalizované hodnoty reálná čísla. Pro problémy typu Obchodní cestující se využívá permutační kódování, které udává pořadí výběru hodnot ze seznamu vrcholů grafu. Těmto reprezentacím je nutné přizpůsobit rekombinační operátory, které jsou popsány dále. 3.2.5
Selekce
Selekce napodobuje princip přirozeného výběru, podle kterého mají větší šanci na přežití a tím i účasti na rozmnožovacím procesu (reprodukce) lepší a silnější (kvalitnější) jedinci. Zároveň nevylučuje přežití slabých ani eliminaci kvalitních jedinců. Proto i simulace přirozené selekce musí obsahovat pravděpodobnostní (stochastickou) složku. Ruletová selekce byla využívaná v genetických algoritmech jako první a proto je nutné ji zmínit i přes řadu nevýhod, kterými trpí. Název je odvozen od pomyslného ruletového kole, na kterém je každému jedinci přidělen úsek (viz obr. 3.3), jehož velikost je přímo úměrná ohodnocení (fitness) jedince. Poté se zatočí ruletovým kolem (náhodně zvolí bod na obvodu kola) a vybere jedinec, který daný úsek obsahuje. Tento postup se opakuje P10 P1
P9 P2
P3 P8
P4 P7 P6
P5
Obrázek 3.3: Ruletová selekce
tolikrát, kolik jedinců je třeba vybrat. Pravděpodobnost výběru i-tého jedince je tedy f (xi ) Pi = N , i = 1, . . . , N (3.1) j=1 f (xj ) 28
která jsou ovšem stejně interně v počítači uložena v binární formě
24
OPTIMALIZAČNÍ ALGORITMY
Jak již bylo zmíněno, ruletová selekce má řadu nevýhod. Mezi nejvážnější patří použitelnost pouze na maximalizační problémy a vyžaduje nezápornost ohodnocení. Problém také nastane, pokud jsou absolutní rozdíly kvality jedinců velmi malé v porovnání s průměrným ohodnocením populace (hodnoty fitness se pohybují z nějakého důvodu ve velkých číslech). V tomto případě vyjdou všechny pravděpodobnosti (úseky ruletového kola) přibližně stejné a ztratí se vlastní podstata selekce. Někdy lze tento problém, nazývaný škálovací (scaling), řešit odečtením minimální možné hodnoty fitness – meze hodnot fitness ovšem nemusí být známé. V případě nedostatečně velké populace29 nastane problém vzorkování (sampling), který způsobí značné odchylky poměru zastoupení jedinců od teoretického předpokladu, daného vztahem (3.1). Pořadová selekce (Rank selection) řeší většinu problémů ruletové selekce. Tato metoda ignoruje absolutní rozdíly ohodnocení jedinců a bere v potaz jen pořadí jedince v populaci seřazené30 od nejhoršího. Dává tak šanci i nejhorším jedincům nezávisle na rozdělení hodnot fitness Pravděpodobnost výběru i-tého jedince je pak i Pi = N
j=1 j
=
2.i , N (N + 1)
i = 1, . . . , N
(3.2)
Turnajová selekce (Tournament selection) využívá modelování soupeření jedinců o přežití – z náhodně vybraných n-tic31 jedinců je vždy vybrán nejlepší. Tento proces se opakuje dokud není vybrán potřebný počet jedinců. Počtem soupeřících jedinců lze ovlivňovat selekční tlak, tedy míru preference lepších jedinců před horšími. Pro tento typ selekce nelze nijak analyticky popsat jeho chování, přesto se v praxi osvědčil a je hojně využíván. 3.2.6
Křížení
Křížení je prvním ze základních rekombinačních operátorů genetických algoritmů. Podstatou je kombinace dvou32 jedinců (rodičů), doprovázená vznikem zpravidla dvou nových jedinců (potomků), kteří kombinují vlastnosti obou rodičů. Cílem je samozřejmě kombinace dobrých vlastností z obou jedinců v jednom potomkovi. Křížením dojde tedy ke vzniku nových, lepších, ale i horších jedinců. Oddělení kvalitních a nekvalitních potomků je již úkolem selekčního procesu v následující generaci. Křížení není nutné aplikovat na všechny selekcí vybrané jedince (Px < 1), z někteří rodiče se pak stanou potomky bez změny. Obvykle však bývá křížení aplikováno na všechny rodiče a jedinci z původní generace dostanou šanci přežít díky nahrazovacímu operátoru. 29
Teorém o schématech byl odvozen pro velmi velké populace, kdy platí zákon velkých čísel. proto pořadová selekce 31 nejčastěji dvojic 32 Počet rodičů může být i větší, viz např. diferenciální evoluce popsaná v [5], která využívá čtyři rodiče. 30
Genetické algoritmy
25
Následující operátory křížení jsou použitelné pro binární kódování jedince. Pro jiné reprezentace je nutné operátory vhodně upravit. Jednobodové křížení (1-point crossover) V řetězci chromozomu je náhodně zvolen jeden bod, ve kterém se oba rodiče rozdělí a potomek se vytvoří prohozením částí za dělícím bodem podle schématu na obr. 3.4. Jedná ze o základní variantu křížení. Rodic 1
Rodic 2
10110100010011011110
00011001010110110110
10110100010110110110
00011001010011011110
Potomek 1
Potomek 2
Obrázek 3.4: Princip jednobodového křížení
Rodic 1
Rodic 2
10110100010011011110
00011001010110110110
10110001010111011110
00011100010010110110
Potomek 1
Potomek 2
Obrázek 3.5: Princip dvoubodového křížení
Dvoubodové křížení (2-point crossover) Průběh je podobný jako u jednobodového křížení, s rozdílem že jsou zvoleny dva body a prohozena je část řetězce mezi nimi. Princip lze nalézt na obr. 3.5. Dvoubodové křížení je flexibilnější v možnostech rekombinace stavebních bloků (viz kapitola 3.2.9). Uvádí se (např. [14]), že dvoubodové křížení také zmenšuje pravděpodobnost rozbití schématu.
26
OPTIMALIZAČNÍ ALGORITMY
Částečně náhodné dvoubodové křížení (Partially Randomized 2-point crossover) Základní princip je stejný jako u klasického dvoubodového křížení. Při klasickém křížení je občas, zejména pokud je již populace částečně zkonvergovaná, část chromozomu obou rodičů stejná a shodný úsek se objeví i u obou potomků. Myšlenka částečně náhodného křížení je ve vybrání jednoho z potomků a provedení náhodné změny některých společných bitů (viz obr. 3.6). Jde tedy v podstatě o selektivní mutaci, zaměřující se na oblasti obsahující redundantní informace a automaticky zvyšující pravděpodobnost mutace při konvergenci populace. Rodic 1
Rodic 2
10110100110011011010
00011001010100110110
10110001010111011010
00011100110000110110
Potomek 2
Potomek 2
* 0* 1* * 0* * 10* * * * 1* * 10
00001100111000100110
Spolecné schema odpovídající oboum potomkum
Potomek 2 po náhodné inverzi
Obrázek 3.6: Princip dvoubodového křížení s mutací společného schématu rodičů
Jedna z možných implementací (viz [16]), která byla využita v této práci, spočívá v náhodném vybrání určitého úseku chromozomu a inverzí bitů náležících společnému schematu potomků s pravděpodobností PP RX =
IP RX 2 · NCS
(3.3)
kde IP RX je délka náhodně zvoleného úseku a NCS je počet společných bitů v úseku délky IP RX . Rovnoměrné křížení (Uniform crossover) Při tomto způsobu křížení se rozhoduje pro každou jednotlivou pozici zvlášť, zda dojde k prohození bitů na této pozici. Obvykle je pravděpodobnost prohození každého jednotlivého bitu 0,5. Tento způsob křížení se hodí
Genetické algoritmy
27
spíše pro malé populace, kde může pomoc vnést do populace větší diverzitu a zvětšit okruh prohledaných míst stavového prostoru. U větších populací, kde je diverzita zajištěna především množstvím různorodých jedinců, se projeví vysoká pravděpodobnost rozbití schématu, proto je většinou preferováno spíše jedno- nebo dvoubodové křížení. 3.2.7
Mutace
Pro binární reprezentaci chromozomu je nejčastěji používaná mutace náhodnou bitovou inverzí. Je definována pravděpodobnost s kterou se pro každý bit zvlášť rozhodně zda dojde k jeho inverzi nebo bude zachován. Tato pravděpodobnost bývá velmi malá, často kolem 0,01 – značně větší hodnoty by způsobily převahu náhodně složky nad informovanou složkou (využívající znalosti kvality jedince) a prohledávání by částečně nebo úplně zdegenerovalo na náhodné, podobné Lokálnímu prohledávání (viz kapitola 3.1).
10110100010011011110 Pm
10110100011011011100 Obrázek 3.7: Princip mutace náhodnou bitovou inverzí
Pro jiné než binární reprezentace jedinců je nutné samozřejmě zvolit jiný operátor mutace. V případě reálných čísel je možné s určitou pravděpodobností přičíst malou náhodně zvolenou hodnotu. Pro permutační kódování lze náhodně prohodit nějaké dva body v posloupnosti. Poznámka: pro zamezení předčasné konvergence lze využít dynamické zvyšování pravděpodobnosti mutace Pm v případě malé diverzity nebo déletrvajícího stavu bez nalezení nového, lepšího řešení. Úspěch této metody je ovšem nejistý, vzhledem neinformované podstatě mutace. Při testování v rámci této práce se tato modifikace neukázala jako užitečná. 3.2.8
Nahrazování generací
Posledním článkem simulované evoluce je vytvoření nové generace jedinců kombinací množiny nově vzniklých jedinců (potomků) a jedinců z původní generace (ještě před selekcí). Nejednoduší strategie, nazývaná generační (generational), spočívá ve vytvoření nové populace pouze z potomků – pracuje tedy s nepřekrývajícími se populacemi. Nevýhoda této strategie je v možné ztrátě dosud nejlepšího nalezeného řešení, neboť vlivem rekombinačních operátorů může dojít k rozbití výhodných stavebních bloků a nenalezení lepších. Proto
28
OPTIMALIZAČNÍ ALGORITMY
se generační strategie často doplňuje o elitismus, který zajistí přenesení nejlepšího jedince do následující generace, například nahrazením nejhoršího z potomků. Z nahrazovacích strategií pracujících s překrývajícími se populacemi (někdy nazýváno steady-state), lze uvést například sjednocení původní populace a potomků, seřazení podle kvality a odstranění (truncation) nejhorších jedinců, tak aby zůstala zachovaná velikost populace P opSize. Sofistikovanější strategie jsou založeny na podobných metodách jako selekce – například vzájemné soutěžení (Tournament) původních jedinců a potomků v náhodně zvolených dvojicích. 3.2.9
Teorie schémat
Z principu funkce genetických algoritmů není přímo zřejmé proč fungují, tedy proč dochází postupem času k přibývání kvalitnějších jedinců v populaci a naopak k úbytku méně kvalitních. Částečnou odpověď na tuto otázku poskytuje teorie o schématech, kterou odvodil J. Holland v r. 1975 [4, strana 129–133] pro standardní genetický algoritmus (SGA). Standardní genetický algoritmus33 je nejstarší a nejzákladnější formou, která má řadu nevýhod, nicméně vzhledem k jednoduchosti lze vcelku průhledně provést odvození Schema teorému. SGA je definován jako GA s binárním kódováním, ruletovou selekcí, jednobodovým křížením, mutací bitovou inverzí a nepřekrývajícími se populacemi.34 Teorie vychází z poznatku, že stejně kvalitní jedinci mají často na určitých pozicích stejné bity, tedy že určité pozice v řetězci chromozomu mají na kvalitu větší vliv než jiné. Hodnoty na těchto „vlivných pozicích se pak nazývají stavební bloky (building blocks). Všechny řetězce obsahující tyto stavební bloky lze definovat pomocí schémat, což jsou šablony jedinců, definující pozice, které tvoří stavební bloky pomocí symbolů reprezentující konkrétní binární hodnoty {0,1} a zástupného symbolu *, který znamená že na hodnotě této pozice nezáleží. V souvislosti se schématy se dále definují parametry L
délka schematu – celkový počet symbolů, rovná se délce jedince splňujícího schéma o(H) řád schematu – počet specifických (pevně definovaných) symbolů δ(H) definující délka schematu – největší možná vzdálenost dvou specifických symbolů (pro schémata řádu 0 a 1 je konvencí stanoveno δ(H) = 0) Například pro schéma H = (1, 1, 0, ∗, ∗, 1, ∗, 0, 1, ∗) je L = 10, o(H) = 6, δ(H) = 8 Dále definujme kvalitu schématu H jako střední ohodnocení (fitness) jedinců odpovídajících tomuto schématu f (xi ) f (H) = xi ∈H (3.4) |xi ∈ H| kde čitatel je součet fitness jedinců odpovídajících schématu a jmenovatel jejich počet. 33 34
Standard Genetic Algorithm, někdy také nazývaný Simple Genetic Algorithm Potomci nahrazují vždy celou předchozí generaci
Genetické algoritmy
29
Během přechodu na další generaci v SGA se postupně aplikují operátory selekce, křížení a mutace. Pro vyjádření pravděpodobnosti zachování schématu v následující generaci je třeba odvodit vliv všech těchto operací. Za základní metodu v SGA se považuje ruletová selekce, kde (při dostatečně velké populaci) pro počet zvolení určitého jedince platí f (xi ) , m(i, t + 1) ≈ m(i, t) · N j=1 f (xj )
N = P opSize
(3.5)
Podobně počet výskytu určitého schématu H lze definovat jako podíl kvality schématu (3.4) a průměrného fitness celé populace. m(H, t + 1) ≈ m(H, t) ·
f (H) f
(3.6)
Z toho je již zřejmé, že schémata definující pouze podprůměrné jedince (f (H) < f ) budou ve výběru zastoupena méně často než v původní populaci, zatímco počet nadprůměrných schémat bude větší. Při opakování selekce by růst i pokles teoreticky probíhal přibližně geometrickou řadou, v praxi bude růst i pokles postupně brzdit snižující se odchylka kvality schémat od středního fitness populace (homogenizace populace). Předchozí vztah uvažuje zjednodušený případ přechodu k nové generaci pouze prostřednictvím selekce, proto je třeba dále zahrnout i vliv rekombinačních operátorů. Při uvažování jednobodového křížení s rovnoměrnou pravděpodobností volny křížícího bodu závisí pravděpodobnost rozbití schématu pouze na jeho definiční délce δ(H).35 PxD (H) ≤ Px ·
δ(H) , L−1
Px je pravděpodobnost křížení
(3.7)
a pravděpodobnost přežití PxS (H) ≥ 1 − Px ·
δ(H) L−1
(3.8)
Čitatel je roven počtu rozhraní mezi symboly schématu (místy, kde lze schéma přerušit) a jmenovatel vyčísluje počet možností jednobodového křížení. Nerovnost je ve vztahu z důvodu existence šance na zachování schématu i když bod křížení připadne dovnitř schématu – pokud část řetězce převzatá od druhého rodiče také splňuje danou část schématu. Pro porovnání, pravděpodobnost přežití schématu pro rovnoměrné křížení je PxS = 0,5o(H)−1
(3.9)
Mutace změní každý bit s pravděpodobností PM . Předpokládáme-li že inverze jednotlivých bitů jsou nezávislé náhodné jevy, je možné vyjádřit pravděpodobnost přežití schématu po mutaci (3.10) PmS (H) ≥ (1 − Pm )o(H) 35
Čím je schéma delší, tím pravděpodobněji dojde k jeho roztržení
30
OPTIMALIZAČNÍ ALGORITMY
Nerovnost zohledňuje možnost zásahu mutace do zástupného symbolu *, kdy nedojde ke zničení schématu. Protože Pm 1, lze předchozí vztah aproximovat PmS (H) ≥ 1 − Pm · o(H)
(3.11)
Doplněním vztahu (3.6) o (3.8) a (3.11) vznikne f (H) δ(H) · [1 − Pm · o(H)] m(H, t + 1) ≥ m(H, t) · · 1 − Px · L−1 f
(3.12)
po roznásobení závorek je možné poslední člen vzhledem k ostatním zanedbat a vztah tak zjednodušit na δ(H) f (H) − Pm · o(H) (3.13) m(H, t + 1) ≥ m(H, t) · · 1 − Px · L−1 f Při sledování vývoje konkrétního schématu lze poslední člen v závorkách nahradit konstantou. Na trend vývoje počtu zástupců schématu má proto vliv hlavně člen odpovídající selekci, který představuje (jak již bylo zmíněno), alespoň z počátku geometrickou řadu. Z předcházejících úvah a odvození vyplývá že úkol selekce je pouze v zajištění postupné převahy kvalitnějších schémat36 nad horšími, zatímco vliv rekombinačních operátorů spočívá především ve vytváření nových (lepších i horších) schémat, bez nichž by genetický algoritmus nedokázal nalézt lepší řešení než nejlepší jedinec v počáteční populaci. Znovu je nutno připomenout, že realita se popsanému odvození blíží pouze v případě značně velké populace.
3.3
Modifikace extrémů
genetických
algoritmů
pro
vyhledání
více
Cílem genetického algoritmu je nalézt co možná nejlepší řešení, k dosažení tohoto cíle používá za běhu mnoha různých potenciálních řešení. Po skončení běhu se vybere nejlepší z nich a ostatní jedinci populace nejsou nijak využiti. Některé optimalizační problémy však mohou mít podobu funkce s více extrémy podobné kvality – takové úlohy se nazývají multimodální. Multimodální úlohou je i úloha separace frekvenčních pásem signálu vibrací generovaných kombinací vad valivého ložiska. V případech kdy postačuje nalezení kteréhokoliv extrému lze použít klasické genetické algoritmy. Pokud však nejsou extrémy stejné kvality, a jsou tedy mezi nimi oblasti podstatně horší kvality, existuje riziko nalezení některého z horších extrémů – jedinci se při nepříznivě nastavené počáteční populaci k lepším extrémům přes hluboké oblasti nedostanou. Příklad jednorozměrné multimodální funkce je na obr. 3.8. Proto se objevila snaha využít vnitřního paralelismu a dosáhnout v konečné populaci obsazení několika kvalitních oblastí stavového prostoru zároveň. Nicméně u běžných algoritmů začne dříve či později docházet k shlukování většiny populace v blízkosti nejlepšího 36
tedy i jim odpovídajících jedinců
Modifikace genetických algoritmů pro vyhledání více extrémů
31
jedince. Standardními prostředky pro udržení diverzity se dosáhne pouze zvětšení poloměru okolo extrému, ale až na vyjímky se jedinci stále budou držet v blízkosti jednoho extrému.
Obrázek 3.8: Ukázka multimodální funkce
Myšlenka popisované modifikace je opět založena na principech reálného světa a spočívá v simulaci vyčerpání přírodních zdrojů při obsazení určitého místa příliš mnoha jedinci a tím zhoršení životních podmínek – jakkoliv dobré místo se při velké koncentraci osídlení stává k životu nevhodné a někteří jedinci musí zkusit štěstí v jiné oblasti. Tyto modifikace jsou známé jako Niching,37 a modifikované algoritmy se někdy nazývají NGA (Niche Genetic Algorithms) a dále budou popsány dvě možné varianty. 3.3.1
Sdílení hodnocení
Zhoršení životních podmínek je simulováno pomocí snížení úpravy hodnocení jedinců v oblastech s vyšší koncentrací. Základním měřítkem u NGA je vzdálenost dvou jedinců. Jedná se o míru podobnosti řešení představovaných dvěma jedinci a její stanovení je problémově závislé. Pokud se označí vzdálenost jedinců i a j jako dij , lze definovat tzv. funkci sdílení pomocí následujícího vztahu α dij 1 − σsh pro dij < σsh (3.14) sh(dij ) = 0 jinde Základním parametrem funkce sdílení je poloměr sdílení – niche radius σsh , který určuje maximální vzdálenost na kterou se ještě jedinci ovlivňují. Druhým parametrem α lze upravovat závislost vzájemného vlivu na vzdálenosti jedinců, obecně se používá α = 1, funkce sdílení se pak označuje jako trojúhelníková funkce sdílení – viz obr. 3.9. Jiné hodnoty zavádí nelineární závislost a vytvářejí široké oblasti s ostrou hranicí pro α > 1 nebo oblasti se zvýrazněným vlivem poblíž středu pro α < 1. 37
Niche – výklenek, koutek, oblast
32
OPTIMALIZAČNÍ ALGORITMY 1
sh(dij )
0.8 0.6 0.4 0.2 0 0
50
100
150
200
250
300
350
400
dij
Obrázek 3.9: Funkce sdílení pro α = 1
Upravené, tzv. sdílené ohodnocení každého jedince, je pak definováno takto (f (i))β fsh (i) = N , j=1 sh(dij )
β≥1
(3.15)
Tato úprava hodnocení, znevýhodňující jedince úměrně počtu a vzdálenosti sousedů v poloměru σsh , účinně zamezuje konvergenci populace v okolí jednoho bodu, ale tím také ztěžuje prozkoumání okolí a přesné zaměření polohy extrému. Tento problém lze řešit využitím exponentu β ≥ 1, který se nazývá scaling factor a jeho vyšší hodnota snižuje penalizaci hodnocení v bodech s výraznou špičkou ohodnocovací funkce, tedy ve vlastních extrémech. Faktor β je vhodné na začátku běhu algoritmu nastavit na hodnotu 1 a zvyšovat postupně až za běhu, aby se umožnilo jedincům nejprve zaujmout postavení kolem všech extrému a neriskovalo se přitažení těmi nejvýraznějšími. Po skončení běhu algoritmu je třeba identifikovat tzv. vedoucí jedince oblastí (leader), jejichž poloha ve stavovém prostoru udává nalezené extrémy. Jeden z možných algoritmů je znázorněn na obr. 3.10. Jedinci jsou seřazeni podle velikosti a první jedinec představuje vedoucího první oblasti. Další jedinci se buď přiřadí k nejlepšímu vedoucímu už existující oblasti, v jehož poloměru jsou nebo se stanou vedoucím nové oblasti. Tento postup se opakuje až do vyčerpání hledaného počtu extrémů (parametr algoritmu). 3.3.2
Dynamické sdílení hodnocení
Tato varianta, nazývaná také dynamic niching je rozšířením výše popsané metody. Na rozdíl od klasického sdílení hodnocení zde dochází k rozdělení jedinců pomocí popsaného algoritmu (obr. 3.10) do oblastí v každém generačním kole, přičemž pro jedince uvnitř dynamických oblastí platí jiná pravidla pro úpravu hodnocení než pro jedince, kteří nejsou v poloměru žádné oblasti. Jedincům uvnitř oblasti se hodnocení upravuje pouze podle počtu jedinců nk v oblasti k – nezávisle na jejich vzdálenosti, zatímco nezařazeným jedincům
Modifikace genetických algoritmů pro vyhledání více extrémů
33
Začátek
Seřazení populace od nejlepšího
1.jedinec → vedoucí 1.oblasti
Další jedinec
Je v poloměru σsh od jiného vedoucího jedince?
ano
Zařazení do odpovídající oblasti
ne
Již existuje def. počet oblastí?
ne
Jedinec → vedoucí nové oblasti
ano
ne
Všichni jedinci zpracováni?
ano Konec
Obrázek 3.10: Princip nalezení oblastí a jejich vedoucích jedinců
34
OPTIMALIZAČNÍ ALGORITMY
se hodnocení upravuje stejně jako u klasického sdílení. Sdílené hodnocení lze tedy vyjádřit tímto vztahem nk jedinec i náleží do oblasti k f (i) Nniche fdsh (i) = (3.16) , mdsh (i) = N mdsh (i) j=1 sh(dij ) jedinec i je nezařazený opSize slouží k nastavení počtu jedinců, při jehož překročení Konstanta Nniche < MPaxP eaks jsou jedinci v oblasti oproti ostatním penalizováni. Bez tohoto koeficientu by byli jedinci v dynamických oblastech byly vždy penalizováni více než jedinci mimo oblasti. Nezávislost úpravy hodnocení na vzdálenosti uvnitř oblasti umožňuje lepší prozkoumání okolí extrému, neboť mezi jedinci nevzniká „odpudivý efekt a mohou se k sobě libovolně přiblížit. Dále mezi jedinci v jedné oblasti klesá složitost určení vzdálenosti z O(n2 ) na O(n), což v případě komplikovaného určování vzájemné polohy může přinést zrychlení běhu algoritmu.
Poznámka: sdílené hodnocení jedince má význam pouze v kontextu populace, jíž je jedinec součástí – nelze porovnávat jedince mezi různými generacemi. Z tohoto důvodu se v NGA používá nahrazování celých generací
35
4
Genetický algoritmus pro detekci vad ložisek
Tato kapitola se věnuje konkrétnímu popisu použitého genetického algoritmu. Je zde popsán způsob hodnocení jedinců, struktura chromozomu, parametry algoritmu a použité operátory. Pozornost několika rozšířením a modifikacím algoritmu.
4.1
Hodnotící funkce
Hodnotící funkce je klíčová komponenta, prostřednictví které algoritmus porovnává kvalitu nalezených kandidátů řešení. V tomto případě kvalitě odpovídá míra nestacionárního chování signálu v testovaném pásmu. Na obr. 4.1 je naznačen postup vyhodnocení jedince. Prvním krokem je dekódování parametrů filtru z chromozomu jedince. Chromozom je tvoVstup
Dekódování parametrů filtru
Filtrace úseku signálu
Ohodnocení výskytu přechodových dějů
Návrat
Obrázek 4.1: Vyhodnocení jedince
řen binárním řetězcem rozděleným na tři geny, jejichž alely určují centrální frekvenci filtru, šířku propustného pásma a řád filtru. Struktura chromozomu a způsob dekódování jsou shrnuty v tabulce 4.1. Délka jednotlivých genů je nastavena s ohledem na dostatečnou jemnost možných frekvencí – necelých 5 Hz pro centrální frekvenci i šířku pásma. Rozsah hodnot fc = < 5000, 25000 > Hz a BW = < 100, 5000 > Hz, přičemž omezení minimální šířky pásma konkrétního filtru (tab. 4.3), má vyšší prioritu. byl zvolen tak aby byl genetický algoritmus udržen v předpokládaném rozsahu hledaných pásem. Gen kódující řád filtru zavádí jistou redundanci38 , která je u genetických algoritmů žádoucí. Rozsah hodnot 29 byl zvolen zvolen z pro zachování rovnoměrné39 pravděpodobnosti hodnot zbytku po dělení 100. U filtrů typu IIR bylo empiricky zjištěno nejlepší chování N ≤ 4, proto byl řád omezen na hodnoty {2,3,4}. Význam genu
bitové pozice
dekódování
centrální frekvence
1–12
fc = 20000 ·
šířka pásma
13–22
BW = 4900 ·
řád filtru
23–31
pro FIR: N = 2 · [bin2int(23, 31) mod 100] + 2 pro ostatní: N = [(bin2int(23, 31) mod 100) mod 3] + 2
bin2int(1,12) 212
+ 5000 (Hz)
bin2int(13,22) 210
+ 100 (Hz)
Tabulka 4.1: Struktura chromozomu 38
Více různých chromozomů může představovat stejný nebo velice blízký fenotyp 2 je nejbližší mocnina dvou k násobku sta
39 9
36
GENETICKÝ ALGORITMUS PRO DETEKCI VAD LOŽISEK
Druhý krok je konstrukce vlastního filtru typu pásmová propust podle dekódovaných parametrů. Typ filtru je jedním z parametrů algoritmu – popisu testovaných filtrů se věnuje následující kapitola. Filtr je poté aplikován na vybraný úsek zdrojového signálu. Na délce úseku přímo závisí rychlost běhu algoritmu, ale zároveň musí obsahovat dostatečné množství hledaných zákmitů aby nemohlo dojít k ovlivnění nahodilými nestacionaritami. Pro testování byla zvolena délka 6 sekund, což při 25 ot./sec a počtem zákmitů během jedné otáčky40 typicky okolo deseti dává statisticky dostatečně významné množství. Dále se z signálu odstraní počáteční úsek o délce 300 vzorků pro eliminaci eliminaci přechodového děje samotného filtru41 , který by mohl ovlivnit výsledek. Nakonec se určí vlastní ohodnocení jedince pomocí zvoleného ukazatele přechodových dějů. Ukazatel přechodových dějů je také parametrem algoritmu, jejich rozboru se věnuje kapitola 2.2.
4.2
Porovnání a výběr vhodného filtru
Před testováním vlastních evolučních algoritmů bylo provedené porovnání schopností filtrů separovat nestacionární složky ze signálu podle zde popsané metodiky. Opakováním přechodového děje vytvořeného podle vztahu (2.3) s frekvencí fT a přičtením náhodného šumu s normálním rozdělením amplitud byly vytvořeny dva testovací signály s vzorkovací frekvencí fs = 64 kHz (viz skript prog/tools/gentra.m). Přehled parametrů je v tab. 4.2. V druhém signálu byla úmyslně přidaná druhá sekvence přechodových dějů, přestože filtr měl oddělit pouze první složku.
Označení
Přechodové děje (vlastní a opakovací frekvence)
Signál 1
fv = 8 kHz, fT = 300 Hz
Signál 2
fv1 = 8 kHz, fT 1 = 300 Hz fv2 = 14 kHz, fT 2 = 200 Hz
Šum
-
SN R
Typ šumu
-4,2 dB -8 dB
Gaussovský
-
Tabulka 4.2: Parametry signálů pro testování filtrů
Přehled použitých filtrů je v tab. 4.3. Nelinearity fázové charakteristiky IIR filtrů by způsobily narušení tvaru nestacionárních dějů v časové oblasti a proto potřeba signál filtrovat dvakrát – podruhé v obráceném směru.42 Výsledkem je konstantní fázové zpoždění na v celém pásmu a efektivně dvojnásobný řád filtru. Pro filtr FIR toto není nutné, neboť lze navrhnout s lineární fázovou charakteristiku a tedy konstantním skupinovým zpožděním 40
Závisí na počtu valivých elementů ložiska Týká se především filtru FIR. Funkce filtfilt použitá u IIR filtrů se sama stará o vhodné nastavené poč. podmínek pro minimalizaci přechodového děje filtru 42 V MATLABu pomocí funkce filtfilt 41
Porovnání a výběr vhodného filtru
37
v celém rozsahu.43 Funkce fir1 v MATLABu toto zajišťuje automaticky. Každý filtr má definovanou minimální šířku pásma pro zamezení prohledávání velmi úzkých pásem, kde se hledaný signál nemůže nacházet. Pro každý testovaný filtr byla postupně při konstantní centrální frekvenci fc = 8080 a řádu44 nastavována šířka pásma v rozsahu od BWmin do 11,1 kHz s krokem 160 Hz. Signál po průchodu filtrem byl vyhodnocen pomocí klasické kurtosis a mezi výslednými hodnotami nalezeno maximum. Tento postup byl zopakován 20x pro různé realizace náhodného šumu a z výsledků stanovena střední hodnota a rozptyl. Výsledky jsou shrnuty v tab. 4.4. U šedých hodnot se projevoval výrazný rozptyl šířky pásma vzhledem k jeho hodnotě. Na základě vysokého rozptylu byly vyloučeny IIR filtry typu Čebyšev a eliptický filtr.45 Filtr IIR LSM byl shledán nevhodným na základě plochého průběhu a nevýrazného maxima závislosti kurtosis na šířce pásma, viz obr. 4.2. Jako vhodný kandidát s výrazným maximem i u druhého signálu s vyšší hladinou šumu z porovnání vyšel IIR filtr Butterworth, viz obr. 4.3. Toto porovnání bylo považováno pouze za orientační a v reálných testech s evolučními algoritmy byly všechny filtry znovu otestovány. Označení
Typ
Generující funkce v MATLABu
Řád
FIR
FIR (metodou oken)
IIR Butterworth
fir1
30
okno Hann
Butterworth (analog. prototyp)
butter
2
BWmin = 250 Hz
IIR Čebyšev
Čebyšev, typ 2 (analog. prototyp)
cheby2
2
BWmin = 400 Hz, odstup nepropustného pásma Rs = −60 dB
IIR Eliptický
Eliptický (analog. prototyp)
ellip
2
BWmin = 250 Hz odstup nepropustného pásma Rs = −60 dB, zvlnění propustného pásma Rp = 0,5 dB
IIR LSM
Metoda nejmenších čtverců (obecná frekvenční char.)
yulewalk
2
BWmin = 200 Hz
Tabulka 4.3: Přehled testovaných filtrů 43
Při splnění sudé nebo liché symetrie podle středu. Při zvoleném řádu dosahovaly filtry v tomto testu nejlepších výsledků 45 Pro signál obsahující pouze šum je vysoký rozptyl normální 44
Další parametry
38
GENETICKÝ ALGORITMUS PRO DETEKCI VAD LOŽISEK
FIR
IIR Butterworth
IIR Čebyšev
IIR Eliptický
IIR LSM
Signál 1
ohodnocení šířka pásma (Hz)
6,033 7143
6,041 6545
0,16 4552
5,696 2564
6,095 4628
Signál 2
ohodnocení šířka pásma (Hz)
1,501 2105
1,494 4186
0,167 3836
1,277 389
1,456 2982
Šum
ohodnocení šířka pásma (Hz)
0,011 5898
0,037 3089
0,178 3332
0,005 6102
0,035 3060
)LWQHVV→
)LWQHVV→
Tabulka 4.4: Výsledky porovnání filtrů pro separaci frekvenčního pásma
PD[ILWQHVV
âtĜNDSiVPDN+] →
PD[ILWQHVV
(a) Signál 1
âtĜNDSiVPDN+] →
(b) Signál 2
Obrázek 4.2: Závislost hodnocení na šířce pásma pro filtr typu IIR LSM a jednu realizaci šumu
)LWQHVV→
)LWQHVV→
↑ PD[ILWQHVV
í
í í
↑ PD[ILWQHVV
âtĜNDSiVPDN+] →
(a) Signál 1
í
âtĜNDSiVPDN+] →
(b) Signál 2
Obrázek 4.3: Závislost hodnocení na šířce pásma pro filtr typu IIR Butterworth a jednu realizaci šumu
Parametry genetického algoritmu
4.3
39
Parametry genetického algoritmu
V tabulce 4.5 jsou uvedeny parametry vlastního genetického algoritmu. Velikost populace . . . . . . . . . . . . . . . . . . . . . PopSize = 110 Délka chromozomu. . . . . . . . . . . . . . . . . . . . D = 31 Kódování genů. . . . . . . . . . . . . . . . . . . . . . . . binární (little-endian) Pravděpodobnost křížení . . . . . . . . . . . . . . Px =1 Pravděpodobnost mutace . . . . . . . . . . . . . . Pm = 0,01 Maximální počet generací . . . . . . . . . . . . . MaxIter = 30 Max. generací bez zlepšení . . . . . . . . . . . . MaxNonImpr = 10 Minimální diverzita fitness . . . . . . . . . . . . . σmin = 0,0005 Inicializace. . . . . . . . . . . . . . . . . . . . . . . . . . . . náhodná s rovnoměrným rozdělením Selekce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . tournament (po dvojicích) Křížení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . dvoubodové Mutace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . náhodná bitová inverze Nahrazování . . . . . . . . . . . . . . . . . . . . . . . . . . tournament potomci vs. rodiče46 , generační Tabulka 4.5: Parametry použitého genetického algoritmu
Význam a funkce většiny parametrů odpovídá popisu v kapitole 3.2. Nahrazovací strategie se realizuje jako souboj dvojic, v nichž proti sobě stojí náhodně vybraný rodič a potomek. Přitom každý jedinec je právě v jedné dvojici, tím je zároveň zajištěn elitismus, tedy jistota že nedojde ke ztrátě nejlepšího dosud nalezeného kandidáta řešení.
4.4
Modifikace genetického algoritmu
V práci bylo testováno rozšíření genetického algoritmu pro nalezení více extrémů, jejichž teoretický rozbor byl proveden v kapitole 3.3. Vzdálenost mezi jedinci je určována jako rozdíl centrálních frekvencí pásem. V tab. 4.6 jsou uvedeny použité hodnoty parametrů. Nahrazování probíhá po celých generacích se zachováním nejlepšího47 jedince (elitismus). poloměr oblasti . . . . . . . . . . . . σsh = 400 Hz koeficient tvaru okolí . . . . . . α =1 scaling factor . . . . . . . . . . . . . . β = 1–4 max. počet oblastí . . . . . . . . . N =3 koeficient sdílení v oblasti . . Nniche = 20
lineární růst v rozsahu < 1, MaxIter >
Tabulka 4.6: Parametry pro niching 46 47
pouze při testování algoritmu hledajícího jeden extrém pro tento účel se porovnává neupravené hodnocení
40
VÝSLEDKY EXPERIMENTŮ
5
Výsledky experimentů
5.1
Popis ložiska a soustrojí použitého pro měření
Pro experimenty byla využita data, získaná měřením48 na experimentálním soustrojí, které obsahovalo na jedné, elektromotorem poháněné, hřídeli dvojici ložisek – jedno s laserem uměle vytvořenou vadou a druhé bez vady (viz obr. 5.1). Jedná se o jednořadá kuželíková ložiska, dodávaná firmou ZVL - Ložiska s.r.o., typu 32010 (viz [17]).
Obrázek 5.1: Uspořádání soustrojí při měření vibrací ložisek (A – vadné ložisko)
Kuželíková ložiska se řadí mezi valivá ložiska, avšak na rozdíl od kuličkových ložisek obsahují jako valivé členy válečky, jejichž osy se mírně sbíhají, viz obr. 5.2. Toto uspořádání umožňuje větší silovou zátěž ložiska i v axiálním směru. Vzhledem k rozdílnému poloměru vnitřního i vnějšího kroužku na obou stranách, musí mít i valivé elementy sbíhavý průřez, aby byl v každém bodě podél axiální osy dodržen stejný poměr převodu rychlosti z otáčejícího se kroužku na valivý element. Valivé elementy tedy nemají přesně válcovitý tvar, ale mírně se sbíhají – odtud plyne název ložiska.
Obrázek 5.2: Vnitřní uspořádání jednořadého kuželíkového ložiska 48
Toto měření nebylo součástí této práce.
Popis ložiska a soustrojí použitého pro měření
41
Obrázek 5.3: Pohled na komponenty rozebraného kuželíkového ložiska
vnější průměr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vnitřní průměr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . šířka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . přípustné referenční otáčky . . . . . . . . . . . . . . . . . . . . . . . mezní otáčky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . hmotnost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . průměr vnější dráhy kuželíku na užší straně . . . . . . . . průměr vnitřní dráhy kuželíku na užší straně . . . . . . . průměr vnější dráhy kuželíku na širší straně . . . . . . . . průměr vnitřní dráhy kuželíku na širší straně . . . . . . .
D d T nref nmax m Da da Db d1
80 mm 50 mm 20 mm 6000 min−1 8000 min−1 0,37 kg 72 mm 57 mm 77 mm 65,6 mm
Tabulka 5.1: Parametry ložiska ZVL 32010AXA použitého při měření (odpovídá 32010X/Q podle katalogu SKF)
42
VÝSLEDKY EXPERIMENTŮ
Na obr. 5.3 je pohled na komponenty skutečného rozebraného ložiska. V tabulce 5.1 jsou uvedeny některé parametry použitého ložiska. Význam uvedených parametrů je znázorněn na obr. 5.4.
(a)
(b)
Obrázek 5.4: Řez ložiskem a kóty rozměrů
Jak bylo zmíněno v úvodu této části, testovací soustrojí obsahovalo dvojici ložisek na společné hřídeli (viz obr. 5.1). Na ložisku označeném písmenem A byla uměle (laserem) vytvořená určitá kombinace vad, druhé ložisko sloužilo jako referenční a bylo bez vady. Čísla označují senzory vibrací, zde představované piezoelektrickými akcelerometry BK 4507B firmy Brüel & Kjær – podrobné specifikace viz [18]. Akcelerometr 4, resp. 5, vyznačený na obr. 5.1, snímal vibrace ložiska s vadou ve vertikálním, resp. horizontálním směru a obdobně akcelerometry 2, resp. 3 snímaly vibrace v obou směrech u ložiska bez vady. Vady měly podobu laserem vypálené drážky o šířce 0,1–0,5 mm a hloubce 0,5–1 mm po celé šířce kroužku nebo kuželíku. V tabulce 5.2 je uveden přehled vad testovacího ložiska a dalších podmínek při jednotlivých měřeních. V každé ze všech čtyř testovacích konfiguracích byly získány čtyři 60 sekundové záznamy vibrací. V tabulce 5.3 jsou uvedeny opakovací frekvence přechodových dějů pro různé defekty při otáčkách 1480 ot./min. Hodnoty byly získány pomocí webového kalkulátoru [22] na stránkách společnosti SKF.
Detekce vad
Označení ložiska A B C D
43
kombinace vad ložiska defekt defekt defekt defekt
na na na na
otáčky (ot./min)
axiální předpětí (N)
1481 1480 1481 1480
2800 2930 3200 3120
vnějším a vnitřním kroužku vnitřním kroužku a kuželíku vnějším kroužku a kuželíku vnějším i vnitřním kroužku a kuželíku
Tabulka 5.2: Přehled kombinací vad na testovacích ložiskách a podmínek měření lokalizace defektu
frekvence
vnitřní kroužek vnější kroužek kuželík
341 Hz 276 Hz 225 Hz
Tabulka 5.3: Opakovací frekvence zákmitů generovaných defektem při 1480 ot./min – podle [22]
5.2
Detekce vad
Pro ověřování funkčnosti testovaných algoritmů byla na vybrána základní podoba s parametry podle tab. 4.5. Pokud nebude uvedeno dále jinak, byla použita základní verze hodnotící funkce využívající filtr typu IIR Butterworth Robust Kurtosis jako ukazatel přechodových dějů. Pro genetické algoritmy bylo použito standardní sdílení ohodnocení (fitness sharing). 5.2.1
Testy s využitím umělého signálu
Před testy na reálných datech bylo provedeno porovnání několika modifikací algoritmu s využitím uměle vygenerovaných dat. Pozornost byla zaměřena pouze na vlastnosti samotného evolučního algoritmu. Modifikace hodnotící funkce, jejíž vlastnosti jsou značně závislé na dalších složkách testovaného signálu byly testovány přímo na reálných datech. Parametry testovacích signálů jsou uvedeny v tab. 5.4, další informace viz kapitola 4.2 a vztahy (2.1) až (2.3).
Označení
Přechodové děje (vlastní a opakovací frekvence)
Signál 3
fv1 = 8 kHz, fT 1 = 300 Hz fv2 = 14 kHz, fT 2 = 200 Hz fv2 = 19 kHz, fT 2 = 250 Hz
Šum
-
SN R
Typ šumu
-6,3 dB Gaussovský -
Tabulka 5.4: Parametry uměle generovaných signálů pro testování evolučních algoritmů
44
VÝSLEDKY EXPERIMENTŮ
Při testech byl vygenerovaný signál o délce 60 sekund rozdělen na 30 dvousekundových úseků a na každý úsek se aplikoval testovaný algoritmus. Ze souboru jednotlivých výsledků – fitness, centrální frekvence pásma fc a šířky pásma BW – byl vyhodnocen pro každou z těchto veličin medián x˜ a směrodatná odchylka σx . Výsledky jsou shrnuty v tabulce 5.5. Algoritmus (signál)
1.pásmo x ˜ σx
2.pásmo x ˜ σx
3.pásmo x ˜ σx
GA Fitness Sharing (signál 3)
f itness fc (kHz) BW (Hz)
0,1792 8,118 3277
0,0074 3,328 238
0,1576 18,951 3313
0,0089 3,331 453
0,1356 14,130 3407
0,0086 0,814 669
GA Dynamic Niching (signál 3)
f itness fc (kHz) BW (Hz)
0,1778 8,188 3179
0,0060 3,733 218
0,1569 18,926 3282
0,0096 3,793 489
0,1329 14,082 3304
0,0082 1,620 574
GA (šum)
f itness fc (kHz) BW (Hz)
0,0505 14,224 250
0,0097 7,004 29,04
0,0417 19,678 250
0,0090 7,147 160,14
0,0359 13,778 263
0,0080 9,002 115,69
Tabulka 5.5: Statistické srovnání modifikací algoritmů pro generovaný signál
Poznámka: jako odhad střední hodnoty byl zvolen medián z důvodu necitlivosti k extrémním hodnotám a šikmosti rozložení výsledků. Z výsledků jsou zřejmé minimální rozdíly mezi těmito variantami. Pořadí nalezených pásem (extrémů ve stavovém prostoru) je u obou modifikací genetického algoritmu stejné. Ve většině případů byla nalezena komponenta s vlastní frekvencí 8 kHz, která má největší hustotu výkonu na vzorek. Ve výsledcích pro signál obsahující pouze šum stojí za povšimnutí malá šířka pásma těsně nad definovanou minimální šířkou pásma filtru. Na obr. 5.5 jsou graficky znázorněny nalezená pásma a umístění jedinců v konečné populaci.49 . Z rozložení jedinců je, ve shodě s předpoklady (viz kapitola 3.3.2), parná větší míra konvergence kolem jednotlivých extrémů v případě dynamického sdílení fitness. Obě metody však prokázaly srovnatelnou schopnost nalezení všech extrémů a vzhledem malé časové náročnosti určení vzdálenosti jedinců bylo dále použito klasické sdílení hodnocení.
49
Vertikální poloha jedince je úměrná jeho ohodnocení
Detekce vad
45
$PSOLWXGové spektrum nalezených filtrů
$PSOLWXGD
I +]
I +]
F F
IF +]
I+]
(a) fitness sharing
$PSOLWXGRYpVSHNWUXPQDOH]HQêFKILOWUĤ
$PSOLWXGD
I +]
I +]
F F
IF +]
I+]
(b) dynamic niching Obrázek 5.5: Znázornění polohy jedinců ve finální populaci a nalezených pásem
46
VÝSLEDKY EXPERIMENTŮ
5.2.2
Testy s využitím reálného signálu
Pro testy s využitím dat z reálného soustrojí byly pro každé ložisko A–D (viz tab. 5.2) k dispozici 4 záznamy délky 60 sekund o vzorkovací frekvenci 64 kHz. Aby bylo možno provést statistické vyhodnocení různých variant použitých metod, byly tyto záznamy rozděleny na 40 úseků o délce 6 sekund50 a každý z úsek nezávisle vyhodnocen. Zohledněny byly pouze pásma s kvalitou alespoň 4/10 kvality prvního (nejlepšího) pásma, maximálně však 3 pásma. Ze získaného souboru hodnot byly vypočtený hodnoty uvedené v následujících tabulkách. Pokud není uvedeno jinak, většina zde uvedených porovnání se z prostorových důvodů vztahuje pouze k ložisku A. Nejdůležitější komponentou hodnotící funkce algoritmu je ukazatel přechodových dějů (viz kap. 2.2). V tab. 5.6 je pro každý ukazatel uveden medián, maximum a minimum dosaženého ohodnocení (fitness) pro signál vibrací v horizontálním i vertikálním směru na ložisku s vadou – fF AU LT i referenčním bez vady – fOK . Směr fOK fF AU LT
8,064 10,39
8,874
V
fOK fF AU LT
7,349 9,900
7,945
H
fOK fF AU LT
3,012 6,369
3,404
V
fOK fF AU LT
1,999 10,39
2,147
H
fOK fF AU LT
0,344 0,934
0,363
V
fOK fF AU LT
0,289 1,141
0,299
Kurtosis
Kurtosis
1.pásmo xmax xmin
H Crest faktor
Robust
x ˜
x ˜
2.pásmo xmax xmin
6,688 7,673
7,635
9,363
6,688 7,673
7,635
9,463
1,748 5,504
1,908
6,158
1,046 6,958
1,409
9,552
0,152 0,734
0,186
0,910
0,129 0,758
0,172
1,121
x ˜
3.pásmo xmax xmin
6,209 7,018
7,129
6,829
6,209 7,018
7,129
6,829
1,550 3,641
1,903
2,791
0,894 5,124
1,249
6,037
0,148 0,679
0,148
0,709
0,679
-
0,684
6,278 6,278 2,889 4,540 0,576 0,508
Tabulka 5.6: Statistické srovnání ohodnocení nalezeného pásma pro různé ukazatele přechod. dějů
Kvalitu funkce algoritmu lze posuzovat podle odstupu mediánů hodnocení signálu vadného ložiska a referenčního ložiska bez vady. Rozdíl hodnot fF AU LT min −fOKmax představuje odstup odhadů statistických rozložení obou hodnocení. U crest faktoru je tento rozdíl malý již u prvního pásma a u dalších dokonce záporný – risk chybné klasifikace je tedy značný. Překryv obou hodnocení je dobře patrný z obr. 5.6a. U klasické kurtosis se již překryv maximální a minimální hodnoty fitness neobjevuje v žádném z případů. Při porovnání poměru f˜F AU LT /f˜OK a fF AU LT min /fOKmax však vychází robust kurtosis lépe. Ve vertikálního směru bylo třetí pásmo úplně vyloučeno pro nedosažení hodnocení alespoň 4/10 prvního pásma. Lepší odstup a menší rozptyl hodnocení vadného a referenčního ložiska je patrný i z histogramů na obr. 5.6b a 5.6c. 50
Kompromis mezi počtem úseků a dostatečným počtem otáčkových cyklů v jednom úseku
Detekce vad +RUL]RQWiOQtYLEUDFH
9HUWLNiOQtYLEUDFH
1ILWQHVV
1ILWQHVV
47
ILWQHVV]HOHQi 2.þHUYHQi YDGD →
ILWQHVV]HOHQi 2.þHUYHQi YDGD →
(a) crest faktor, 2.pásmo
+RUL]RQWiOQtYLEUDFH
1ILWQHVV
1ILWQHVV
9HUWLNiOQtYLEUDFH
ILWQHVV]HOHQi 2.þHUYHQi YDGD →
ILWQHVV]HOHQi 2.þHUYHQi YDGD →
(b) klasická kurtosis, 2.pásmo
+RUL]RQWiOQtYLEUDFH
1ILWQHVV
1ILWQHVV
9HUWLNiOQtYLEUDFH
ILWQHVV]HOHQi 2.þHUYHQi YDGD →
ILWQHVV]HOHQi 2.þHUYHQi YDGD →
(c) robust kurtosis, 2.pásmo Obrázek 5.6: Porovnání rozlišitelnosti ložiska s vadou pro různé ukazatele přechodových dějů
48
VÝSLEDKY EXPERIMENTŮ
Další důležitou komponentou hodnotící funkce je typ filtru, který realizuje separaci testovaného pásma. Statistické vyhodnocení dosažených hodnot fitness pro 4 zvolené filtry je v tab. 5.7. Filtry FIR a IIR Butterworth dávají dobré odstupy mediánu i minima hodnocení vady od maxima hodnocení ložiska bez vady. Eliptický IIR filtr dosahuje horších odstupů fF AU LT min − fOKmax a u IIR LMS filtr (funkce yulewalk) se dokonce objevily hodnoty fOKmax výrazně převyšující medián hodnocení ložiska s vadou. Na základě těchto výsledků byl jako základní filtr vybrán IIR filtr podle analogového prototypu propusti Butterworth, který vzhledem k nízkému řádu a umožňuje rychlejší zpracování.51 Směr
Butterworth
IIR Eliptický
IIR LSM
1.pásmo xmax xmin
H
fOK fF AU LT
0,344 0,913
0,363
V
fOK fF AU LT
0,302 1,125
0,312
H
fOK fF AU LT
0,344 0,934
0,363
V
fOK fF AU LT
0,289 1,141
0,299
H
fOK fF AU LT
0,343 0,872
0,368
V
fOK fF AU LT
0,284 1,104
0,301
H
fOK fF AU LT
V
fOK fF AU LT
FIR
IIR
x ˜
x ˜
2.pásmo xmax xmin
0,159 0,821
0,261
0,874
0,157 0,754
0,237
1,108
0,152 0,734
0,186
0,910
0,129 0,758
0,172
1,121
0,297 0,780
0,339
0,809
0,127 0,782
0,166
1,004
x ˜
3.pásmo xmax xmin
0,074 0,743
0,165
0,757
0,130 0,597
0,168
0,657
0,148 0,679
0,148
0,709
0,679
-
0,684
0,162 0,732
0,193
0,567
0,121 0,532
0,131
0,695
0,325 1,808 0,851 0,760
0,294 0,339 0,737 0,679
0,192 0,694
0,320
0,259 3,348 0,955 0,903
0,245 0,263 0,790 0,764
0,184 0,751
0,246
0,666 0,528 0,576 0,508 0,388 0,474 0,604 0,544
Tabulka 5.7: Statistické srovnání dosažených ohodnocení pro různé typy filtrů
V tabulce 5.8 jsou již hodnoty mediánů a směrodatných odchylek centrálních frekvencí fc a šířky BW nalezených pásem. Za povšimnutí stojí nejnižší rozptyly centrálních frekvencí u filtru IIR Butterworth, což potvrzuje správnost volby tohoto filtru jako základního. Poslední modifikace, popsaná v [7], spočívala ve využití pásem nalezených pomocí Fast Kurtogramu pro vytvoření počáteční populace pro běh genetického algoritmu. Z důvodu zachování rozmanitosti počáteční populace je alespoň poloviční množství jedinců vždy inicializováno náhodně. V tabulce 5.9 je srovnání parametrů pásem nalezených při čistě náhodné inicializaci a při využití kurtogramu a na obrázku 5.7 lze porovnat histogramy pro obě varianty. Pro obě možnosti byly nalezeny shodná pásma, pouze u varianty s využitím kurtogramu došlo ke snížení rozptylu a eliminaci ojedinělých případů, kdy byla nalezena frekvence značně vzdálená od střední hodnoty ostatních. 51
Rychlost běhu hodnotící funkce je z pohledu časové optimalizace citlivé místo
Detekce vad
49
Směr
Butterworth
IIR Eliptický
IIR LSM
1.pásmo σx
x ˜
2.pásmo σx
3.pásmo x ˜ σx
H
fc (kHz) BW (Hz)
22,371 2103
1,498 570
18,265 3538
3,581 787
18,087 3081
4,504 1370
V
fc (kHz) BW (Hz)
19,444 3749
0,082 153
10,156 3498
1,375 1103
12,154 3488
6,347 1134
H
fc (kHz) BW (Hz)
22,437 2227
0,076 124
17,656 4629
1,447 1008
10,452 4696
1,832 926
V
fc (kHz) BW (Hz)
19,447 3665
0,041 89
8,982 3380
0,460 677,5
15,024 3753
1,617 543
H
fc (kHz) BW (Hz)
22,540 2561
3,812 1113
19,941 5412
5,140 1740
16,636 6519
6,779 1850
V
fc (kHz) BW (Hz)
19,466 2592
0,102 310
11,117 6110
0,720 1084
5,320 4366
8,757 2004
H
fc (kHz) BW (Hz)
22,328 1564
3,515 688
18,047 2129
2,787 1520
17,903 2627
3,952 1603
V
fc (kHz) BW (Hz)
19,217 624
2,384 545
12,201 2928
3,307 1455
11,956 2012
3,992 1541
FIR
IIR
x ˜
Tabulka 5.8: Statistické srovnání nalezených frekvenčních pásem s použitím různých typů filtrů
Směr
plně náhodná inicializace
částečná inicializace z kurtogramu
x ˜
1.pásmo σx
x ˜
2.pásmo σx
3.pásmo x ˜ σx
H
fc (kHz) BW (Hz)
22,437 2227
0,076 124
17,656 4629
1,447 1008
10,452 4696
1,832 926
V
fc (kHz) BW (Hz)
19,447 3665
0,041 89
8,982 3380
0,460 677,5
15,024 3753
1,617 543
H
fc (kHz) BW (Hz)
22,344 2354
0,105 164
17,407 4703
0,515 805
10,496 4634
1,046 719
V
fc (kHz) BW (Hz)
19,451 3679
0,026 54
8,879 3404
0,235 520
15,249 3718
1,303 436
Tabulka 5.9: Vliv částečně deterministické inicializace s využitím kurtogramu (pro filtr IIR Butterworth)
50
VÝSLEDKY EXPERIMENTŮ
+RUL]RQWiOQtYLEUDFH
1ILWQHVV
3IF
IFIDXOWN+] →
9HUWLNiOQtYLEUDFH
ILWQHVV]HOHQi 2.þHUYHQi YDGD → 9HUWLNiOQtYLEUDFH
1ILWQHVV
3IF
+RUL]RQWiOQtYLEUDFH
IFIDXOWN+] →
ILWQHVV]HOHQi 2.þHUYHQi YDGD →
(a) IIR Butterworth, plně náhodná inicializace
+RUL]RQWiOQtYLEUDFH
F
3I
1ILWQHVV
IFIDXOWN+] →
9HUWLNiOQtYLEUDFH
ILWQHVV]HOHQi 2.þHUYHQi YDGD →
9HUWLNiOQtYLEUDFH
1ILWQHVV
3IF
+RUL]RQWiOQtYLEUDFH
IFIDXOWN+] →
ILWQHVV]HOHQi 2.þHUYHQi YDGD →
(b) IIR Butterworth, částečná inicializace z kurtogramu Obrázek 5.7: Histogramy fitness a centrální frekvence ložiska A v 1.pásmu
Detekce vad
51
$PSOLWXGDG%
í í í í í í í í í
IUHNYHQFH+]
$PSOLWXGD
(a) výkonové spektrum původního signálu
$PSOLWXGRYiVSHNWUDQDOH]HQêFKILOWUĤ I +]
F
I +] F
I +] F
I+]
$PSOLWXGD
(b) plně náhodná inicializace GA
$PSOLWXGRYiVSHNWUDQDOH]HQêFKILOWUĤ IF +]
IF +] I +] F
I+]
(c) částečně deterministická inicializace z kurtogramu Obrázek 5.8: Grafické znázornění nalezených pásem včetně polohy jedinců ve finální populaci – ložisko A, horizontální směr
Na obr. 5.8 je pro ilustraci odhad výkonového spektra původního signálu před zpracováním a grafické znázornění nalezených frekvenčních pásem společně s polohou jedinců ve finální populaci.
52
VÝSLEDKY EXPERIMENTŮ
5.3
Rozlišitelnost vad
Dalším logickým krokem po prozkoumání možností odlišit ložisko s vadou od bezvadného je určení typu vady. Nejprve byla zkoumána pouze rozlišitelnost testovaných ložisek A, B a C. Ložisko D nebylo použito, protože obsahuje všechny vady a předpokladem možnosti rozlišení je alespoň částečná disjunktnost hledaných frekvencí. Na obrázku 5.9 je srovnání histogramů centrálních frekvencí prvního pásma v obou směrech pro jednotlivé dvojice ložisek, z kterého je zřejmá snadná rozlišitelnost jednotlivých případů. Se znalostí odhadu střední hodnoty a směrodatné odchylky je možné za předpokladu normálního rozdělení stanovit pomocí metod statistického rozpoznávání optimální rozhodovací mez frekvence pro minimalizaci rizika nesprávné klasifikace. Nicméně toto řešení funguje pouze pro pracovní podmínky, za kterých bylo provedeno měření a vzhledem k tomu že umí rozlišit pouze vady které byly již před měřením známé, v praxi postrádá smysl.
5.4
Identifikace vad
V praxi je úloha stavěna jako detekce vady a lokalizace poškozené součásti (vnější kroužek, vnitřní kroužek nebo kuželík). Nalezená frekvenční pásma poskytují přibližnou informaci o vlastní frekvenci poškozeného dílu, tato frekvence však často nebývá známá a je závislá na dalších faktorech – např. rychlosti otáček, druhu a stupni poškození, případně teplotě součásti. Naopak dobře definovaná je opakovací frekvence zákmitů generovaných vadou na dané součásti, neboť závisí pouze na otáčkách, které jsou snadno měřitelné. Frekvence přechodových dějů, včetně jejích vyšších harmonických, je viditelná ve výkonovém spektru obálky signálu po filtraci – viz obr. 5.10. Další možnost, použitá v této práci, je detekce periody pomocí maxim autokorelační funkce obálky filtrovaného signálu. Na obr. 5.11 části průběhů jsou autokorelační funkce obálky signálu v prvním a druhém pásmu. V prvním pásmu lze navíc pozorovat výraznější maxima od periody otáček soustrojí. Pro automatickou detekci maxim autokorelační funkce a jejich odstupu byl použit algoritmus popsaný v kapitole 2.6 na str. 14. Detekovaná maxima jsou v obr. 5.11 znázorněna svislými tečkovanými čarami. Na základě určených opakovacích frekvencí byly k jednotlivým pásmům přiřazeny odpovídající vady podle následujícího postupu 1. Z každého nezávisle zpracovaného 6-sekundového úseku52 na prvních třech pásmech byl vybrán úsek o délce 2 sekundy a popsaným algoritmem určen odhad opakovací periody zákmitů. 2. Dále byly uvažovány pouze frekvence ležící v toleranci ±4 % od jedné z frekvencí v tab. 5.3. 3. Pásma byly rozřazeny do skupin podle blízké vlastní a opakovací frekvence 4. Byla vybrána skupina s největším průměrným fitness a podle nejčastěji v ní zastoupené frekvenci nalezena v tab. 5.3 odpovídající vada. 52
viz kap. 5.2.2
Identifikace vad
53
+RUL]RQWiOQtYLEUDFH
/RåLVNR$ /RåLVNR%
+RUL]RQWálníYLEUDce
F
3I
&HQWUiOQtIUHNYHQFHíIN+]
F
&HQWUDOQtIUHNYHQFHíIN+]
F
9HUWLNiOQtYLEUDFH
/RåLVNR$ /RåLVNR%
9HUWLNiOQtYLEUDFH
/RåLVNR$ /RåLVNR&
F
3I
F
3I
Ložisko$ /RåLVNR&
F
3I
&HQWUiOQtIUHNYHQFHíI N+] F
(a) ložiska A a B
&HQWUiOQtIUHNYHQFHíI N+] F
(b) ložiska A a C +RUL]RQWiOQtYLEUDFH
/RåLVNR% /RåLVNR&
F
3I
&HQWUiOQtIUHNYHQFHíIN+]
F
9HUWLNiOQtYLEUDFH
/RåLVNR% /RåLVNR&
F
3I
&HQWUiOQtIUHNYHQFHíI N+] F
(c) ložiska B a C Obrázek 5.9: Rozlišitelnost vad ložisek v 1.pásmu
54
VÝSLEDKY EXPERIMENTŮ
í
KDUPRQLFNi
í
KDUPRQLFNi
í
KDUPRQLFNi
$PSOLWXGDG%
í í í í í í í í
I+]
Obrázek 5.10: Výkonové spektrum obálky signálu po filtraci v nalezeném pásmu
SHULRGDRWiþHN
5[[→
WPV →
(a) ložisko A, 1.pásmo, horizontálně
5[[→
WPV →
(b) ložisko A, 2.pásmo, horizontálně Obrázek 5.11: Autokorelační funkce obálky signálu po filtraci včetně automaticky detekovaných maxim
Identifikace vad
55
Tento postup byl aplikován s využitím tří modifikací genetického algoritmu pro všechny ložiska. V tabulce 5.10 je shrnutí nalezených vad společně vlastními i opakovacími frekvencemi přechodových dějů. 1.pásmo fT R část
2.pásmo fT R část
3.pásmo fT R část
Směr
A
H V
22,4 kHz 354 Hz vnitřní
B
H V
13,8 kHz 356 Hz vnitřní 19,2 kHz 356 Hz vnitřní
C
H V
22,7 kHz 230 Hz kuželík
D
H V
A
H V
22,3 kHz 354 Hz vnitřní
B
H V
11,6 kHz 354 Hz vnitřní 19,3 kHz 356 Hz vnitřní
21,8 kHz 354 Hz vnitřní 11,2 kHz 354 Hz vnitřní
17,9 kHz 356 Hz vnitřní
C
H V
22,5 kHz 230 Hz kuželík
22,8 kHz 229 Hz kuželík 23,4 kHz 229 Hz kuželík
11,2 kHz 288 Hz vnější 11 kHz 289 Hz vnější
D
H V
A
H V
22,3 kHz 354 Hz vnitřní
B
H V
11,5 kHz 356 Hz vnitřní 19,4 kHz 356 Hz vnitřní
21,4 kHz 356 Hz vnitřní 10,7 kHz 354 Hz vnitřní
C
H V
22,5 kHz 230 Hz kuželík
21,6 kHz 229 Hz kuželík 23,1 kHz 229 Hz kuželík
D
H V
Kurtogram + GA (IIR Butt)
GA (IIR Butt)
GA (FIR)
Ložisko
fc
fc
fc
22,7 kHz 354 Hz vnitřní 9 kHz 20,4 kHz 356 Hz vnitřní 12,3 kHz 354 Hz vnitřní
287 Hz vnější
10,4 kHz 354 Hz vnitřní 10,5 kHz 287 Hz vnější 23,3 kHz 229 Hz kuželík 21,9 kHz 356 Hz vnitřní 14,4 kHz 287 Hz vnější
16,9 kHz 354 Hz vnitřní 15,4 kHz 289 Hz vnější
21,9 kHz 356 Hz vnitřní 14,5 kHz 287 Hz vnější
16,9 kHz 358 Hz vnitřní 11 kHz
287 Hz vnější
21,5 kHz 356 Hz vnitřní 14,3 kHz 287 Hz vnější
Tabulka 5.10: Nalezené opakovací frekvence a jim příslušné vady
5.4.1
Zhodnocení identifikace vad
Při srovnání tabulek 5.10 a 5.2 lze posoudit úspěšnost jednotlivých modifikací algoritmů ve schopnosti identifikovat vady jednotlivých částí ložiska. Výsledky variant s čistě náhodnou inicializací genetického algoritmu a filtrem FIR i IIR Butterworth obsahují několik rozdílů, ale nalezené typy vad jsou shodné: u ložisek A a C se podařilo identifikovat všechny vady správně, zatímco u ložisek B a D nebyla nalezena vada na kuželíku, ale ostatní vady byly identifikovány správně.
56
VÝSLEDKY EXPERIMENTŮ
Varianta s částečnou inicializací populace pomocí pásem nalezených kurtogramem vykazuje o něco horší výsledky. U ložiska A nebyla algoritmem detekována vada na vnějším kroužku. Tato vada se vyskytuje u ostatních variant až ve třetím pásmu, což znamená malý výkon ve srovnání s ostatními pásmy – kurtogramem byly objeveny pouze silnější pásma, kterých se genetický algoritmus již držel.
57
6
Závěr
V teoretické části práce byla provedena rešerše metod pro diagnostiku vad valivých ložisek pomocí analýzy signálů vibrací. Pozornost byla věnována metodám založeným na adaptivním vyhledávání frekvenčních pásem obsahujících signál vady, zejména s využitím genetických algoritmů. Vzhledem k jejich důležitosti byla věnována samostatná kapitola shrnutí principů genetických algoritmů a jejich rozšíření pro hledání více extrémů. V praktické části byla navržena a zrealizována konkrétní podoba algoritmu pro adaptivní separaci frekvenčních pásem signálu vibrací a rozšířena o schopnost současné detekce kombinace různých pásem. Algoritmus byl v několika modifikacích otestován na uměle vygenerovaném signálu i reálných datech získaných z testovacího soustrojí a jednotlivé modifikace (fitness sharing, dynamic niching, částečně deterministická inicializace pomocí kurtogramu) vzájemně porovnány. Na základě výsledků testů byla zvolena vhodná varianta genetického algoritmu, typ filtru a detekční funkce (ukazatel přechodových dějů). Metody byly dále rozšířeny o možnost určení konkrétního typu vady nebo více vad současně a lokalizaci vadných součástí ložiska pomocí detekce periody obálky signálu ve vybraném pásmu. Vlastní separace různých kombinací vad se při srovnání výsledků různých ložisek a výsledků separace při vícenásobné aplikaci na stejné ložisko projevila jako velmi spolehlivá. Proces separace vad byl schopen nalézt u dvou ze čtyř testovaných vzorků kuželíkových valivých ložisek 32010AXA všechny přítomné vady, u zbylých dvou byly nalezeny pouze některé vady. V žádném z testovaných vzorků nedošlo při použití implementovaných genetických algoritmů k identifikaci neexistující vady. Navržená implementace genetického algoritmu se na základě experimentálního ověření ukázala jako aplikovatelná pro danou úlohu separace signálů vibrací valivých ložisek. Vzhledem k rozsahu práce nebyly genetické algoritmy aplikovány na úlohu separace signálu vibrací ozubeného převodu. Další možnosti rozvoje metod mohou spočívat v úpravách genetického algoritmu, zejména metod vyhledávání více extrémů. Tyto metody patří mezi slibně se rozvíjející odvětví genetických algoritmů a mají mnoho dalších variant (viz [9] a [10]). Jiná cesta by mohla také spočívat v implementaci jiných moderních stochasticky založených optimalizačních algoritmů, např. memetických algoritmů.
58
REFERENCE
Reference [1] M. Kreidl, et al Diagnostické systémy Nakladatelství ČVUT, Praha, 2001 [2] V. Hlaváč, M. Sedláček Zpracování signálů a obrazů Nakladatelství ČVUT, Praha, 2007 [3] M. Sedláček, R. Šmíd Matlab v měření Nakladatelství ČVUT, Praha, 2007 [4] V. Mařík, O. Štěpánková, J. Lažanský, et al Umělá inteligence 3, kapitola 3 Academia, Praha, 2000 [5] I. Zelinka Umělá inteligence v problémech globální optimalizace BEN – technická literatura, Praha, 2002 [6] Y. Zhang, R. B. Randall „Rolling element bearing fault diagnostis based on Genetic algorithms ICSV14, 14th International Congress on Sound and Vibration, Cairns - Australia, 2007 Diagnostika lozisek GA/Yongxiang Zhang.pdf [7] Y. Zhang, R. B. Randall „Rolling element bearing fault diagnostis based on the combination of genetic algorithms and fast kurtogram ICSV14, 14th International Congress on Sound and Vibration, Cairns - Australia, 2007 Diagnostika lozisek GA/Yongxiang Zhang - kurtogram.pdf [8] P. K. Lehre Niching and Speciation (Sharing) School of Computer Science, The University of Birmingham, United Kingdom, 2006 GA-Niching/l06-niching.pdf [9] B. L. Miller, M. J. Shaw Genetic Algorithms with Dynamic Niche Sharing for Multimodal Function Optimization University of Illinois at Urbana-Champaign, 1995 Geneticke algoritmy/GA dynNiche.pdf
REFERENCE
59
[10] S. W. Mahfoud Niching Methods for genetic Algorithms Illinois Genetic Algorithms Laboratory, Dept. of General Engineering, University of Illinois at Urbana-Champaign, 1995 GA-Niching/Niching Methods in GA.pdf [11] J. Antoni „The spectral kurtosis: a useful tool for characterising non-stationary signals Mechanical Systems and Signal Processing 20 (2006) 282-307, 2004 Kurtogram a Spectral Kurtosis/sdarticle.pdf [12] T. H. Kim, H. White On More Robust Estimation of Skewness and Kurtosis: Simulation and Application to the S&P500 Index School of Economics, University of Nottingham, Nottingham Department of Economics, University of California, San Diego, 2003 Kurtogram a Spectral Kurtosis/robust kurtosis.pdf [13] J. Antoni „Fast computation of the kurtogram for the detection of transient faults Mechanical Systems and Signal Processing 21 (2007) 108-124, 2005 Kurtogram a Spectral Kurtosis/kurtogram.pdf, http://www.utc.fr/˜antoni/ [14] D. Whitley A Genetic Algorithm Tutorial Computer Science Department, Colorado State University (2006) 282-307, 2004 Geneticke algoritmy/ga tutorial.pdf [15] J. Kubalík, P. Pošík Přednáška 1–6 k předmětu Softcomputing Katedra kybernetiky, ČVUT FEL, 2007 X33SCP-lectures [16] J. Kubalík A New Genetic Operator Maintaining Population Diversity Katedra kybernetiky, ČVUT FEL, Praha, 2001 Geneticke algoritmy/Kubalik-PRX.ppt [17] Katalog kuželíkových ložisek firmy SKF SKF Ložiska, a.s., Praha Kuzelikova loziska-SKF.pdf [18] Specifikace akcelerometrů řady 4507 a 4508 firmy Brüel & Kjær Brüel & Kjær accel 4507b.pdf
60
REFERENCE
[19] M. Obitko Introduction to Genetic Algorithms http://obitko.com/tutorials/genetic-algorithms [20] Wikipedia - The Free Encyklopedia http://www.wikipedia.com [21] WWW stránky společnosti SKF http://www.skf.com/portal/skf cz/home/products?contentId=259708&lang=cs [22] Kalkulátor frekvencí potenciálních defektů ložiska http://www.skf.com/skf/productcatalogue/calculationsFilter?lang=en&action=Calc6 Poznámka: Publikace [6] až [18] jsou umístěny v adresáři doc na přiloženém DVD.
61
A
Slovník pojmů
A.1
Diagnostika
Pojem
Význam
Crest factor
činitel výkmitu, poměr mezi maximální a efektivní hodnotou
Kurtosis
statistická veličina udávájící míru koncentrace nejpravděpodobnějších hodnot kolem střední hodnoty, pro své vlastnosti je vhodná na detekci přechodových dějů v signálu
Spectral Kurtosis
funkce vyjadřující míru nestacionarity (přechodových dějů) v závislosti na frekvenci, vzhledem k protichůdným omezujícím podmínkám lze obtížně stanovit obecně pro neznámý signál
Kurtogram
diskrétní varianta Spectral Kurtosis, použitelná pro signál neznámých parametrů
Fast Kurtogram
rychlý algoritmus pro výpočet kurtogramu, pomocí banky prototypů filtrů a rekurzivního dělení ve frekvenční oblasti
A.2
Evoluční algoritmy
Česky
Anglicky
Význam
jedinec
individual
soubor hodnot (vlastností) představující jedno přípustné řešení v prohledávaném stavovém prostoru
populace
population
množina různých jedinců reprezentující současný stav evolučního algoritmu
hodnotící funkce
fitness function
kvalitativní ohodnocení konkrétního jedince v populaci
chromozom
chromosome
řetězec hodnot obsahující informaci o vlastnostech jedince (u genetických algoritmů bývá jedinec tvořen právě jedním chromozomem)
gen
gene
úsek chromozomu obsahující právě jednu vlastnost jedince
alely
alleles
možné hodnoty, které může nabývat určitý gen
genotyp
genotype
popis konkrétního jedince, pro genetické algoritmy odpovídá chromozomu
fenotyp
phenotype
význam vlastností jedince (popis jejich interpretace)
62
SLOVNÍK POJMŮ
Česky
Anglicky
Význam
křížení
crossover
vytvoření nového chromozomu pomocí kombinace dvou stávajících chromozomů (rodičů)
mutace
mutation
náhodná změna části informace obsažené v jedinci
migrace
migration
posun jedince v N-rozměrném stavovém prostoru po určité trajektorii, při kterém se využívá informací poskytnutých okolními jedinci
perturbace
perturbation
náhodné změna trajektorie během migrace
selekční tlak
selection pressure
míra preference lepších jedinců před horšími, jeden z důležitých parametrů algoritmu
předčasná konvergence
premature convergence
stav, kdy je celá populace tvořena stejnými nebo podobnými jedinci v okolí určitého lokálního extrému, takže je malá šance na úniku a nalezení lepšího řešení; bývá důsledkem nedostatečné velikosti populace, špatně zvolených počátečních podmínek nebo příliš velkého selekčního tlaku
postupný vývoj
steady-state
označuje evoluci s překrývajícími se populacemi, kde rodiče koexistují se svými potomky
niching
modifikace genetických algoritmů (známe také jako NGA)pro nalezení více extrémů srovnatelné kvality, využívá penalizace fitness v oblastech stavového prostoru s vyšší koncentrací jedinců
niche radius
parametr NGA σsh – maximální vzdálenost na kterou se jedinci ještě vzájemně ovlivňují
-
poloměr sdílení
63
B B.1
Adresářová struktura přiloženého DVD Zdrojové kódy lib
rawdata
EA parseddata dataproc
stateval
output...
prog stateval_combi output... dataeval
tools
peaks
testfilt Obrázek B.1: Adresářová struktura zdrojových kódů
prog hlavní adresář se zdrojovými kódy skriptů pro MATLAB, obsahuje inicializační skript init.m pro počáteční nastavení cest k využívaným skriptům prog/lib – funkce realizující vlastní evoluční algoritmy a jejich pomocné funkce realizující selekci, nahrazování, křížení, mutace, rozdělování populace do jednotlivých výklenků (lokálních maxim) a další pomocné funkce. prog/EA – skripty pro zajištění přípravy parametrů a dat pro volání vlastních algoritmů (z adresáře lib), dále funkce realizují ohodnocení (fitness) a jejich pomocné funkce pro dekódování chromozomů na parametry filtru, aplikaci filtru na data a různé metody ohodnocení dat po filtraci; jsou zde také funkce pro inicializaci populace pomocí kurtogramu prog/dataproc – skripty pro automatické zpracování vstupních dat po úsecích a uložení sady výsledků
64
ADRESÁŘOVÁ STRUKTURA PŘILOŽENÉHO DVD
prog/stateval – vyhodnocení statistických parametrů a generování histogramů ze sady výsledků získaných automatickým zpracováním dat skripty v adresáři dataproc; součástí je skript joindata.m pro předzpracování dat do vhodnější podoby ke statistické analýze. prog/stateval/rawdata – surová data získaná skripty v adresáři dataproc prog/stateval/parseddata – předzpracovaná data ke statistické analýze prog/stateval/output. . . – získané statistické veličiny a histogramy prog/stateval combi – skripty určené pro statistické porovnání různých vad prog/stateval combi/output. . . – získané porovnání statistických veličin a histogramů prog/dataeval – skripty pro automatické zpracování celého setu vstupních dat nalezenými filtry prog/dataeval/peaks – skripty pro detekci periody přechodových dějů ze signálu po filtraci prog/tools – pomocné funkce využívané v ostatních skriptech prog/testfilt – skripty pro testování vhodnosti filtrů pro selektivní filtraci přechodových dějů (nezávisle na evolučních algoritmech)
B.2
Data a dokumentace
Data – data naměřená na testovacím soustrojí a příslušná dokumentace k výrobě vad a vlastním měření (Ing. Dočekal) - A–D – data z měření na reálném soustrojí - Dokumentace – popis a schémata měření, typy použitých součástí a dokumentace k použitému ložisku doc – odborné články a texty využité v diplomové práci - Diagnostika lozisek GA – využití genetických algoritmů k identifikaci vad ložisek, klíčové články k této práci - Kurtogram a Spectral Kurtosis – principy výpočtu kurtogramu - Geneticke algoritmy – texty o genetických algoritmech obecně - GA-Niching – texty a články o rozšíření GA o Niching - X33SCP-lectures – přednášky z předmětu Softcomputing, vyučovaném katedrou kybernetiky - Ostatni – ostatní nezařaditelné texty, vztahující se k řešené problematice, které nebyly využity