Tudományos Diákköri Dolgozat
Gép- és Terméktervezési Tanszék Genetikus algoritmusok a gépészetben Próbatestek gyártásának optimálása genetikus algoritmusokkal
Készítette:
Témavezető:
Jónás Szabolcs
Dr. Kamondi László
G1-MAG
Tanszékvezető, egyetemi docens Gép- és Terméktervezési Tanszék
1
Tartalom Bevezető ............................................................................................................................................. 3 A Genetikus Algoritmusok .................................................................................................................. 4 A genetikus algoritmusok alapfogalmai ............................................................................................. 8 Néhány gépészeti probléma ............................................................................................................ 11 A Small Punch vizsgálat .................................................................................................................... 14 A genetikus algoritmus háttere ........................................................................................................ 16 Körpakolás ........................................................................................................................................ 18 A körpakolás matematikája.......................................................................................................... 19 A darabszám meghatározása ........................................................................................................... 21 Összefoglalás .................................................................................................................................... 25 Felhasznált irodalom ........................................................................................................................ 26
2
Bevezető
A jelen dolgozatban a genetikus algoritmusokkal foglalkozunk. A genetikus algoritmusok az ún. evolúciós módszerek egyik fajtája. Az evolúciós algoritmusok a mesterséges intelligencia fejlesztésében játszanak úttörő szerepet. A dolgozatban egy korszerű anyagvizsgálati módszerhez szükséges próbatest kivágási tervét vizsgáljuk genetikus algoritmusokkal. Az anyagvizsgálat az ún. Small Punch vizsgálat jelenleg szabványosítás útján van, mivel Magyarországon nincs meghonosodva, ezért az angol terminust használjuk. A cél, hogy genetikus algoritmusok segítségével határozzuk meg azt a maximális darabszámú próbatestet, ami kinyerhető az egyszeri mintából adott szerszám esetén, ami egy reprezentatív vizsgálat sorozathoz szükséges. A dolgozatban bemutatom, hogy mik is azok a genetikus algoritmusok. Hogyan működnek, és mire jók. Néhány ipar közeli alkalmazáson keresztül ismertetem jelentőségüket. A dolgozat második felében pedig egy olyan módszert mutatok be, amely a próbatest kivágási tervét optimálja, illetve meghatározza azt az n darabszámot, ami kinyerhető az anyagdarabkából.
3
„Mivel minden fajnak sokkal több egyede születik, mint amennyi életben maradhat, és mivel ennek következtében a létért való küzdelem gyakran ismétlődik, világos, hogy bármely lénynek, amely ha tetszőlegesen kicsiny mértékben is, de saját előnyére változik, az élet összetett és gyakran változó feltételei között jobb esélye lesz a túlélésre, és ezzel a természetes kiválasztódásra. Az öröklés elve alapján pedig bármely kiválasztott változat az új, módosult alakjában fog továbbterjedni.”
C. Darwin – A fajok eredete
A Genetikus Algoritmusok
Az evolúciós algoritmusok a természetet veszik alapul. A természetes kiválasztódás elvét igyekszenek utánozni. Az evolúciós elmélet mai napig nem teljesen tisztázott kérdéseket vet fel, gondoljunk csak az emberi egyedfejlődésre [2]. A genetikus algoritmus (GA) a globális optimáló eljárásokkal rokon módszer. Elvi hátterét a darwini evolúciós elmélet adja. Nagyon széles körben használható módszerről van szó, így azokon a területeken, ahol a sok lehetséges megoldás közül a legjobbat kell megkeresni. A legjobb megoldás kiválasztásához egy értékelő függvényt (fitness függvény) kell találni, aminek meg kell feleljen a megoldás. Talán épp ez a függvény a legbonyolultabb kérdés, hiszen ha több paraméter is létezik, akkor a függvény is sokkal bonyolultabb. A GA futása közben a biológiából kölcsönzött terminussal élve egy populációt vizsgál. Az összes GA-sal kapcsolatos cikkben, könyvben a genetika kifejezéseit alkalmazzák. Az elnevezések valóban hasonlóan működnek, mint a természetben [1][2].
4
Az evolúciós algoritmus egy iteratív és sztochasztikus folyamat, amely a populáción alapszik. Minden egyed egy potenciális megoldást kínál az adott problémára. A megoldás egy kódoló/dekódoló részegységből áll *2+. Vannak szülők, mint a kiinduló populáció tagjai, amelyek keresztezésével „születnek” az utódok. Az utódok véletlenszerű módosítása létrehozza a mutációt. A populáció egy tagja (egyed), ha teljes mértékben kielégíti a fitness függvényt megoldódik a probléma. Ha ez nem valósul meg egy lépésben, márpedig gyakran nem szokott, újabbnál újabb populációkat hoz létre. Az új populációk a korábbi populációk egyedeinek keresztezésével és/vagy mutációjával állítódnak elő (rekombinációs és mutációs operátorok)[1][2]. Az evolúció, mint folyamat a kromoszómákon keresztül történik. Az élőlényeknek olyan eszközeik vannak, amelyekkel kódolják az életet. A természetes szelekció egy mechanizmus, amely a kromoszómák kapcsolatán alapszik. A kromoszómáknak fő tulajdonsága, hogy képesek a következő generációt a környezetnek sokkal megfelelőbben előállítani. Darwin elméletét (1859) használva működik a GA, tehát elvileg az újabb egyedek jobban megfelelnek, és így tovább. Tehát elviekben elegendően sok megoldás generálása előállítja a keresett megoldást [1][2].
1. ábra Charles Darwin (1809-1882) 5
Mivel a genetikus algoritmusok elvei visszavezethetőek C. Darwin A fajok eredete (a dolgozat mottója is egyben) című művére, néhány szót ejteni kell róla is. Shrewsburyben született 1809-ben, és 1882-ben, Downe-ban halt meg. Angol természettudós volt, kidolgozta az evolúció elméletet. Egy volt tanára lehetőséget kínált számára, egy világ körüli tudományos expedíció formájában. 5 éven keresztül, a Beagle nevű hajón utazva jutott el (1831) a világ számos pontjára, ahol feljegyzéseket készített az élőlényekről. A napló feljegyzésekből később könyvet is adtak ki, olyan népszerűségnek örvendett. Darwin elmélete ezen lejegyzett gondolatok alapján alakult ki, miután rendszerezte, feldolgozta. A kor gondolkodása aggasztotta, hiszen a keresztény vallási nézetekkel szembe megy az evolúciós elmélet. Mivel voltak tényezők, amit nem tudott megmagyarázni sok támadás érte, az egyház is elutasította. Később genetikával egyesített elméleteként jött létre a neodarwinizmus irányzata. Az irodalom szerint a GA-ok alkalmazhatóak a gépi tanulás területén, mivel a probléma felfogható optimálási kérdésként is. A genetikus programozás (GP) az irodalom szerint az egyik legfontosabb elérendő cél, hiszen minden programot jelenleg kézzel írnak. A GP pedig kiküszöbölné azt a mellékidőt, amit a fejlesztés vesz igénybe. A saját magukat fejleszteni, akár újat kifejleszteni tudó programok ötlete nagyjából 50 éve merült fel. 1959-ben jelent meg a kifejezés: gépi tanulás. Bár ezt a kifejezést Samuel magára a programozási folyamatra értette. Mitchell 1996-ban mondta az egyik legjobb definíciót a gépi tanulásra, mégpedig, hogy azon számítógép algoritmusok, amelyek tapasztalat útján fejlesztik önnön magukat. Kezdetben
például
repülőgép
szárnyak
paramétereinek
meghatározására
használták, ekkor a módszert evolúciós stratégiának/programozásnak nevezték [2]. A GP célja, hogy egy kezdeti számú program populáció a kezdeti adatok alapján készüljön el. Tehát valamilyen elv szerint, valamilyen célnak megfelelően
6
történjen meg a szoftverfejlesztés, azonban egyszerre több program is készülhet [1]. Az evolúciós folyamatok reprodukciós fázisa egy viszonylag hosszú időt vesz igénybe. Itt gondoljunk csak az élőlények fejlődése során létrejött formákra, amelyek a fennmaradásuk érdekében alakultak ki. Ilyen példa lehet a halak úszáshoz idomult formája, de szinte minden élőlény esetén megfigyelhetünk valami különleges vonást. A természetben számos reprodukciós folyamat játszódik le ezeken a szinteken. A leggyakoribb folyamat a mutáció, ez okozza az utódok és a szülők közti különbségeket. A genetikus algoritmusokban a populációk minden egyede egy függvénnyel írható le, a függvényeket vizsgálva megkaphatjuk, hogy az elérni kívánt célt melyik elégíti ki a legjobban. Ez a jósági érték kvantitatív információt hordoz a keresések irányításban. A GA-ok a legkiterjedtebb evolúciós eszközök. A GA-k szelekciós, keresztezési és mutációs operátort alkalmaznak működésük során. A GA-ok intuitív módon képezik a jobbnál jobb egyedeket, egyszerű műveleteken keresztül. A fittnes függvény és a cél közötti értéket fel lehet használni az egyedek rangsorolására, aszerint hogy megoldandó problémát mennyire elégíti ki. Az irodalom szerint az evolúciós algoritmusokat (EA) hegymászó algoritmusokat kombinálva nagyon hatékony módszert kaphatunk. A GA-kat intenzíven használják helyi minimum keresésére, ezeket a Mimetikus Algoritmusoknak nevezik [2]. A GA-ok jelenleg a leginkább elterjedt számítási módszereket jelöli a mesterséges intelligencia (MI) evolúciójában [3].
7
A genetikus algoritmusok alapfogalmai
A populáció az egyedek adott időpillanatban vett halmazát nevezzük. Az egyedek a lehetséges megoldásokat reprezentálják. Ebben a halmazban benne vannak a lehetséges megoldások és ugyanazon egyedek benne lehetnek többszörösen is. A számítások során az egyedeket kódolják, ez az egyed genotípusa. A tulajdonságokat a fenotípusok írják le. A kimeneti változók a gének, a felvett értékek az allélok. A genetikus algoritmusok egy iterációs folyamatként fogható fel, amely folyamat minden lépése új populációt állít elő. Ezen folyamat lépései a generációk. Amennyiben az aktuális populáció legjobb megoldását változtatás nélkül viszi tovább az algoritmus, úgy elitista megvalósításnak nevezzük.
2. ábra Az öröklődés szemléltetése A 2. ábra azt mutatja meg, hogy az utódok a szülők genomjainak kereszteződéséből jönnek létre, ahogy a valóságban is. Az egyik és másik szülő genomjait véletlenszerűen összekeverve jönnek létre az új egyedek, amelyek később egymással is és a szülők genomjaival variálva is hozhatnak létre új egyedet. Minden új egyed az előző generáció legjobb egyediből származik. 8
A fitness függvény vagy rátermettségi függvény a megoldásokat értékeli. Ez az a függvény, aminek a globális minimumát kell keresni. Minél rátermettebb az adott egyed, annál inkább nő a „túlélési esélye”. Ezen függvény megválasztása a legnehezebb illetve a legfontosabb lépés az algoritmus felépítésében. A szelekció az egyedkiválasztás operátora. Ennek segítségével az algoritmus a jónak tekintett szülőket kiválasztja, hogy létrehozza az utódokat.
3. ábra A szelekció és a túlélés A genetikus algoritmusok értékei között hibaszámítást kell végezni, hogy az egyes egyedek saját állapotuk alapján jellemezhetővé váljanak. A minél kisebb hiba nagyobb túlélést biztosít. Genetikus algoritmusok speciális esetei -
szimulált hűtés: a fémek hőkezelésének folyamata az analógia
-
tabu keresés: tabulista, egyelemű populáció
-
sztochasztikus hegymászó: lokális optimumkeresési feladatok
-
hangya kolónia: útkeresési problémák megoldása
9
Az alábbi folyamatábra szemlélteti a genetikus algoritmusok működését (4. ábra).
Inicializálás
Kezdeti értékelés
Szelekció
Mutáció
Értékelés
Megfelel?
4. ábra Folyamatábra Eszerint első lépésben a kezdeti értékek megválasztása történik. A fitness függvénnyel megtörténik az összehasonlítás, majd ezekből kiválasztja a legrátermettebbeket, majd keresztezi/mutálja az eredményeket. Az így nyert új egyedek vizsgálata történik. Ha megfelel a peremfeltételnek az adott egyed, akkor véget ér az algoritmus, ha nem, akkor újra keresztezés/mutáció útján új egyedek létrehozásával folytatódik a számítás.
10
Néhány gépészeti probléma
A tervezés manapság fő célja, hogy a ismerjük a termék egész életciklusát. Kiindulva az ötlettől, egészen az újrahasznosításig vagy éppen megsemmisítésig. Vannak módszerek számos tényezőre vonatkozóan, azonban vannak esetek, amikor több lehetséges megoldás közül is lehet választani. Ezen megoldásokhoz különböző megkötéseket, kényszereket kell felírni, amelynek eredményeként egy többtalálatos megoldás halmazt kapunk. Maga a megoldás halmaz nem intuitív, hiszen előre definiálunk jó néhány értéket, azonban az ismeretlen értékeket analitikusan megoldani többnyire nem lehet. A genetikus algoritmusok fő alkalmazási területei a szélsőérték keresések, gráfok megoldásai, játékelméleti kérdések stb. Ezeket a feladatokat át lehet ültetni jól megfogalmazva a gépészet területére. Kezdetben repülőgépszárnyak optimálása, tervezése volt a cél, de műholdak pályájának számítása, sőt a műholdakban lévő berendezések optimálása is megtörtént a NASA-nál, így sokkal kisebb helyen elfértek az egységek, így tömeget tudtak minimalizálni, ezáltal költséget takarítottak meg. A genetikus algoritmusokba számos szempontot lehet beállítani, amit az iteráció során figyelembe vesz az algoritmus. Ekkor egy specifikációs halmazt kapunk eredményül. Ilyen specifikáció lehet a tömeg, a forma, az anyag, stb. A [10] tanulmányban tartókat optimáltak. A cél, hogy adott terhelés esetén megkapják az a két tartót, amely a legjobban kielégíti az anyagköltség minimumát. A geometria részben ismert volt. A gravitációt elhanyagolták, a stabilitási kérdések egyszerűsítése végett. A tartót közepes szilárdságú szerkezeti acélból tervezték. A geometria (5. ábra) W és
11
h értékei ismertek voltak. A cél, hogy az 1 és 2 jelű tagok külső/belső átmérőjét (lehet cső, de lehet rúd is) meghatározzák, továbbá az ábra szerinti s paramétert.
5. ábra Tartó optimálása
Több feltételezéssel is élte az egyes számítások során. Elsőként megvizsgálták, hogy az 1-es tag cső, a 2-es tag rúd. Majd megvizsgálták, hogy mi van, ha mindkét tag cső. Abban az esetben, amikor a 2-es jelű tag cső volt, akkor az s értéke illetve az anyag mennyisége is nagyobb volt, mint, ha csak rúdnak feltételezzük. A [8] tanulmányban gördülő elemes csapágyak fejlesztésében használták a genetikus algoritmusokat. Célfüggvénynek a maximális kifáradási határt vették. A kinematikus kényszereket formálisan kezelték. A tervezési paraméterek, mint a csapágy külső illetve belső átmérője, gördülő elemek száma, stb. volt. További ismeretleneket is tartalmazott a feladat. Az optimálás eredményeként sikerült egy olyan csapágyat tervezniük, amelynek a kifáradási határa jobb, mint a katalógusokban szereplőké. Konvergencia vizsgálatokat végeztek, amelyek eredményeként kiderült, hogy nincsenek terhelésből fakadó extrém nagy értékek.
12
6. ábra 100 generáció után a legjobb értékek dinamikus teherviselő képességre A 6. ábra a [8] tanulmányból való, és azt mutatja, hogy miként változott a dinamikus teherviselő képessége a csapágynak. 7000 generáció után 26500N-os dinamikus tényező értéket vettek fel az egyedek. A [9] cikkben fogaskerék fogprofil optimálását végezték el. A feladat célja, hogy az üzemeléskor keletkező zajokat csökkenthessék. A fordulatszám függvényében vizsgálták a zajmértékét, és sikerült olyan fogprofilt kialakítaniuk, amely csendesebb a kiindulási állapotétól.
13
A Small Punch vizsgálat
Ebben az alfejezetben a Small Punch vizsgálatot mutatjuk be, hogy az olvasónak legyen képe az alkalmazott genetikus algoritmus céljáról. A vizsgálat lényege, hogy egy kis (Ø8x0,5mm) tárcsát kilyukasztanak egy golyóval, és felveszik az erő-elmozdulás diagramot, amiből különféle módszerek segítségével
meghatározhatóak
az
adott
anyag
mechanikai
jellemzői
(szakítóvizsgálati mérőszámok, törésmechanikai mérőszámok, stb.). A próbatesteket célszerűen az üzemelő berendezés falából kell venni, ugyanis így a tényleges üzemi körülmények hatását tudjuk vizsgálni. A mintavételezés
általában
roncsolásos
módon
történik
(pl.:
koronafúró
segítségével). Azonban a teljes keresztmetszetből történő mintavételezés újabb hibaforrás is egyben, hiszen helyre kell állítani a berendezést (pl.: javító hegesztés alkalmazása). Ennek a hibaforrásnak a kiküszöbölésére lett kidolgozva a felületi mintavételezésre alkalmas készülékek családja. Ezek a mintavételező készülékek az üzemelő szerkezet falának felső rétegéből vágnak le egy darabot, analóg módon a fagylaltkanalazáshoz. Az így lemunkált anyagdarab geometriája az alkalmazott szerszámtól függően változhat (pl.: gömbsüveg, csónakforma). A leválasztott anyagdarabból lehet szikraforgácsolás útján eltávolítani a próbatesteket.
7. ábra Mintavételezés
8. ábra Próbatest
14
9. ábra Befogó készülék
10. ábra Metszetek
11. ábra VEM modell
12. ábra Mérések, számítások
Az ábrákon a SP vizsgálat lépései követhetőek végig. A 7. ábra a mintavételezés elvét mutatja. Egy gömbsüveg alakú kivágó szerszám segítségével lehet leválasztani az anyagot az üzemelő szerkezet falából. A 8. ábra a kivágott anyagdarabból kimunkált próbatest geometriáját mutatja. A vizsgálatot a 9. ábra szerinti elrendezésű befogó készülékben végezhetjük. Ez a készülék a Bay Zoltán Intézetben alkalmazott készülék. A vizsgálat során egy kis golyót nyomunk a tárcsába. A vizsgálat után a deformálódott próbatestet mutatja az 10. és a 11. ábra. A 11. ábra MSC Marc végeselem rendszerben készült. A modell és a mérések között összehasonlítást végeztünk egy korábbi feladat kapcsán, ezt (illetve az erőelmozdulás diagramot) a 12. ábra szemlélteti. A feladat kapcsán hazai tudományos cikkek is jelentek meg [4], [5], [6]. A Small Punch-csal foglalkozó szakirodalmak szerint egy kicsit befolyásolja a próbatest orientációja a nyerhető jellemzők értékét, így korlátoznunk kell a módszert. Ez a korlátozás, hogy csak azonos irányban állhatnak a próbatestek.
15
A genetikus algoritmus háttere
A megoldás elvi háttere a logisztikából jól ismert kamion pakolási példa (bin packing problem). A kamion pakolási probléma elnevezés azt takarja, hogy van egy kamion konténer, amibe a lehető legtöbb dobozt pakoljuk be úgy, hogy a lehető legkevesebb levegő (üres tér) maradjon benn, úgy, hogy a lepakolás majd a lehető leggyorsabban történjen (természetesen figyelembe lehet venni, hogy több helyre szállítunk, de az csak bonyolítja a kérdést). Ha ennek analógiájára képzeljük el a feladatunkat, akkor a kamion konténernek feleltethetjük meg az anyagdarabot, a csomagoknak pedig a kis tárcsáinkat. Folytatva az analógiát, a levegő a fel nem használható anyagmennyiségnek felel meg. Az alap problémát megfordítva jutunk tehát a próbatest mennyiségének maximumának kereséséhez, tehát hány darab próbatestet tudunk kivenni az anyagdarabból. Mivel a genetikus algoritmusok a globális minimum megtalálására lettek kifejlesztve alapvetően, így gyakorlatilag a hulladék anyag minimumát kell megtalálni, ami n darab tárcsa árán lehet elérni. Mivel a próbatestek átmérője nagyobb, mint az irodalmakban említett leválasztott anyagdarab vastagság, kerüljenek a próbatestek egy-egy szeleten elhelyezésre. A probléma redukálása egy újabb ismert optimálási problémára vezet, mégpedig a terítéktervezésre (CSP-Cutting Stock Problem). Ennek lényege, hogy egy olyan algoritmust kell írni, amely a legjobb teríték tervet adja eredményül, tehát a legtöbb próbatest gyártható le. Az egyes szeleteknek más-más mérete van, így gyakorlatilag többször lefuttatva, paramétereket változtatva határozhatjuk meg próbatest darabszámot. Ez a probléma ismert körpakolási problémát adja eredményül, amire számos megoldás létezik. További kitétel, hogy a kivágást végző szerszám egy gömbsüveget választ le. Mivel a gömbsüveg szeletei a gömb tulajdonságiból fakadóan nem azonos vastagságúak a széleken illetve a középfelületen, így a körből egy négyszöget kell kialakítani. Tehát egy négyszög
16
alapú hasábunk van. A négyszögbe kell tehát a legtöbb kört tenni. A 13. ábra egy lehetséges megoldást mutat be, ahol az egységnégyzetbe 10 kört írunk be. Az optimális pakolások n=30 darabszámig ismertek. 2-16
között
matematikai módszerekkel lettek megoldva, e fölött számítógépes modellek végezték a számítást. Közelítő pontossággal 200 darab körig ismert a probléma megoldása.
13. ábra A feladat A képlékeny alakítás területén, mint sávterv ismert a kérdés. Az analitikus megoldások szerint az optimális pakolások a szabályos háromszögek csúcsaiban elhelyezett körök adják.
17
Körpakolás
A probléma, hogy van egy adott terület, és abba a lehető legtöbb kört úgy pakoljuk be, hogy azok ne fedjék egymást. Az európai történelem első körpakolással kapcsolatos feladat Malfatti (1731-1807) nevéhez fűződik. Malfatti kérdése, hogy egy adott derékszögű háromszög alapú hasábba, hogyan lehet három (nem feltétlenül egyenlő átmérőjű) hengert elhelyezni, úgy hogy a térfogatuk a legnagyobb legyen. A megoldása szerint 3 olyan kör, amelyek egymást is érintik, és a háromszög oldalait is. A probléma általánosítása tetszőleges háromszögekre híresült el Malfatti-körök néven (14. ábra).
14. ábra Malfatti körök
15. ábra Bólyai Farkas problémája
A feladattal már Bólyai Farkas (1775-1856) is foglakozott. Ő a körpakolási sorozat sűrűségét vizsgálta. Tentamen című munkájában 19 kört helyez el egy szabályos háromszögben. A problémának itt egy gyakorlati kérdés volt az apropója. A cél, hogy háromszög alapú kertbe úgy telepítsenek fákat, hogy azok egymás életterét ne csökkentsék (15. ábra) [7], ennek az elrendezésnek a határértéke π/12. A körpakolás három dimenzióra általánosított alakja a Kepler-probléma néven ismeret. Kepler szerint a lapközepes köbös elrendezés a leggazdaságosabb elrendezési lehetőség, ez 74%-os kihasználtságot ad eredményül, de jelenleg ez nincsen bizonyítva. Ez anyagtudományban is érdekes kérdés lehet. 18
A feladattal kapcsolatos másik magyar vonatkozás, Lázár Dezső nevéhez fűződik, aki 1930-ban vetette fel a problémát, sajnos publikálni nem tudta eredményeit halála miatt. A körpakolás matematikája A körpakolás matematikai leírásakor meg kell felelni néhány könnyen belátható kényszernek. Ilyen kényszer, hogy a négyszögbe pakolt kisebb körök egymást ne fedjék, illetve, hogy a négyszögbe essenek egészen. Tehát a feladat, hogy a következő függvényt optimáljuk: 𝜇 𝑥, 𝑦 = 𝑚𝑖𝑛1≤𝑖,𝑗 ≤𝑛
𝑥𝑖 − 𝑥𝑗
2
+ 𝑦𝑖 − 𝑦𝑗
2
𝑚𝑎𝑥𝜇 𝑥, 𝑦 𝑥, 𝑦 ∈ [0,1]𝑛 , 𝑛 > 1, 𝑛 𝑒𝑔é𝑠𝑧 Az egyenletek az n pont távolságát maximálja az egységnégyzetben. Az x és az y a pontok koordinátáit írják le. Továbbá a négyzethez viszonyított helyzetet is leírja a függvény.
16. ábra Körpakolás A körpakolás ezek szerint megfelel egy-egy pont lerakásának. A pontok közötti távolságoknak tehát ki kell egyenlítenie a definiált feltéteknek. A körpakolás sűrűségét a 19
𝑑𝑛 = 𝑛𝑟𝑛2 𝜋 összefüggés írja le. Így a probléma a maximális sűrűség körpakolás megtalálásaként is felírhatjuk. Ha két körpakolást valamilyen úton (például tükrözés stb.) átvihetjük egy másikba, akkor azt azonosnak vesszük, így az nem számít új megoldásnak. Ez a geometriai modellje a feladatnak.
20
A darabszám meghatározása
A feladat tehát, hogy meghatározzuk azt az n darabszámú próbatestet, amit ki lehet nyerni az anyagdarabból. A korábbiakban már redukálva lett a probléma, így csak a megoldást mutatjuk be. A megoldáshoz a SciLab ingyenes programot használtuk, amely a MatLabhoz hasonlóan működik. Elsőként az y=x2 függvény optimumát kerestem meg, mint példafeladat. A függvény egy parabola, annak a minimuma pedig jelen esetben 0. 85 lépésben történt megoldás, azt az alábbi diagram (17. ábra) szemlélteti. A több lépés nem hozott gyorsabb megoldást is, mivel próbálkozás útján sikerült meghatároznia 10nél kevesebb lépésben is. Az eredményeket Excelben ábrázolva kaphatunk egy görbét is, ami azt mutatja, hogy hány lépésben jutunk el az optimális megoldáshoz. A programot a kivágás feladatához igazítva jutunk el egy megoldáshoz. 0,00009 0,00008 0,00007 0,00006
Érték
0,00005 0,00004 0,00003 0,00002 0,00001
0 0
10
20
30
40
-0,00001
50
60
70
80
90
Iteráció
17. ábra Teszt A SciLab program tartalmaz egy előre definiált genetikus algoritmust, amit hozzá lehet idomítani a kijelölt feladatunkhoz. Mivel a feladat egy anyag kihozatali probléma, a képlékenyalakításból megismert összefüggést optimálhatjuk. 21
𝛾=
𝑛 ∙ 𝐴𝑝𝑟 ó𝑏𝑎𝑡𝑒𝑠𝑡 ∙ 100% 𝐴ö𝑠𝑠𝑧𝑒𝑠
Ahol n a próbatestek száma, Apróbatest a próbatest felülete, az Aösszes pedig a lemez felülete. Alább látható a program kódja: function y=f(x, a, b) y =((sum(x*%pi*16))/(sum(x*%pi*16)*a*b))*100 endfunction PopSize = 100; Proba_cross = 0.7; Proba_mut = 0.1; NbGen = 10; NbCouples = 110; Log = %T; pressure = 0.05; ga_params = init_param(); ga_params = add_param(ga_params,"minbound",[-2; -2]); ga_params = add_param(ga_params,"maxbound",[2; 2]); ga_params = add_param(ga_params,"dimension",2); ga_params = add_param(ga_params,"beta",0); ga_params = add_param(ga_params,"delta",0.1); ga_params = add_param(ga_params,"init_func",init_ga_default); ga_params = add_param(ga_params,"crossover_func",crossover_ga_default); ga_params = add_param(ga_params,"mutation_func",mutation_ga_default); ga_params = add_param(ga_params,"codage_func",coding_ga_identity); ga_params = add_param(ga_params,"selection_func",selection_ga_elitist); ga_params = add_param(ga_params,"nb_couples",NbCouples); ga_params = add_param(ga_params,"pressure",pressure); a=16; b=8; [pop_opt, fobj_pop_opt, pop_init, fobj_pop_init] = .. optim_ga(f, PopSize, NbGen, Proba_mut, Proba_cross, Log, ga_params); disp([min(fobj_pop_opt) mean(fobj_pop_opt) max(fobj_pop_opt)]) [fmin ,k] = min(fobj_pop_opt) 22
xmin = pop_opt(k) [fmax ,k] = max(fobj_pop_opt) xmax = pop_opt(k)
Az a és b paraméterek változtatásával lehet a lemez méretét beállítani. A többi sorban a genetikus algoritmus kezdeti egyedszámát, keresztezési paramétereket, stb. lehet változtatni. Ha a=8 és b=8 esetét vesszük, és a próbatest átmérőjét 8 mm-nek vesszük, akkor algoritmus futásának az eredménye: 1.5625. Ekkor egyetlen próbatest férne a lemezbe, mint ahogy az várható, de marad fenn hulladék is. Az 1. táblázatban láthatjuk néhány esetre lefuttatva a számítást. 1. táblázat Eredmények néhány esetre a
b
f
8
8
1.5625
8
16
0.78125
8
32
0.390625
24
24
0.173611
A feltételezés, hogy a leválasztott tárcsa legnagyobb szeltét biztosító téglalap területe 24x24mm. A megoldást az alábbi ábra mutatja a Wolfram Alpha egy programja szerint. Nyilvánvaló, hogy ennél többet nem lehet bele tenni, de meg lehet vizsgálni genetikus algoritmussal is.
23
18. ábra Megoldás A célfüggvény megváltoztatása legyen most a sűrűségfüggvény és a szelet terület hányadosa. Az algoritmus ebben az esetben 11.45 db kört hoz ki. Jól látszik, hogy ez nem lehetséges, így további fejlesztés szükséges. Az algoritmus ebben a formában csak a fedés kényszerét tartalmazza, azaz két kör nem lehet egymáson, azonban még nem tartalmaz számos másikat, így azt sem, hogy ne vegye figyelembe a hulladékot. Az internetes fórumok szerint a SciLab környezet jelen formájában nem alkalmas teljes mértékben a feladat teljes körű megoldására, így már a továbbfejlesztési lehetőséget is magában rejti a feladat. A következő lépés, hogy egy alkalmasabb környezetben egy jól működő genetikus algoritmust használó körpakoló programot fejlesszünk.
24
Összefoglalás A dolgozatban, nagyvonalakban bemutattam a genetikus algoritmusokat. Az anyag
mennyisége
miatt
ez
ilyen
terjedelemben
nem
is
lehetséges
mélyrehatóbban. Bemutattam néhány példán keresztül, hogy alkalmasak lehetnek gépészeti tervezési feladatok ellátására, ha jól vannak megfogalmazva az algoritmusok. Más algoritmusokkal kombinálva a genetikus algoritmusokat, sokkal jobb megoldásokat nyerhetünk. Bemutattam a célkitűzés alapjául szolgáló próbatestes vizsgálatot, annak néhány alkalmazását. Így érthetővé vált a feladat miértje. A próbatestek kinyerésére megpróbáltam egy algoritmust készíteni valamilyen sikerrel. Bizonyos határokon belül megfelelő kihozatalt jósol, azonban egy határ felett ez már nem működik a hulladék mennyisége miatt. A későbbiekben célom, hogy egy olyan algoritmust fejlesszek ki, amellyel teljes mértékben le lehet követni a feladatot, illetve a valós eredményt kapjuk meg, továbbá megadja azt az elrendezést is, amit analitikusan ki lehet találni.
25
Felhasznált irodalom
[1] Genetic Programming – An Introduction: Banzhaf, W., Nordin, P., Robert E. K. , Frank D. F. - Morgan Kaufmann Publishers, Inc. [2] Introduction to Genetic Algorithms: S. N. Sivanandam, S. N. Deepa – Springer, 2008 [3] Numerikus Módszerek, Optimalizálás: Paláncz, B. – Oktatási segédlet, 2011 [4] Determination of Material Properties Using Small Punch Test: Sz., Jónás, Sz., Szávai, P., Rózsahegyi, R., Beleznai - XXVII. microCAD, Miskolc [5]
Small
Punch
vizsgálat
alkalmazása
mechanikai
anyagjellemzők
meghatározására: Jónás Sz.; Szávai Sz.; Rózsahegyi P.; Beleznai R.; Kelenföldi B. XVIII. FMTÜ, Kolozsvár [6] Determination of aged mechanical properties of NPP components using instrumented hardness testing and other miniature specimen testing techniques: Lenkey G., Szavai S., Rózsahegyi P.,
Köves T.,
Jónás S., Beleznai R. -
INTERNATIONAL CONFERENCE, “STRUCTURAL INTEGRITY and Life of NPP Equipment”, SIL – 2012, Kyiv, Ukraine, October 2 – 5, 2012 [7] Egybevágó körök pakolásai négyzetekbe: Szeidl Rita Betti , Szakdolgozat, 2011 [8] Optimum design of rolling element bearings using genetic algorithms : B. Rajeswara Rao, Rajiv Tiwari - Mechanism and Machine Theory 42 (2007) 233–250 [9]
Corrigendumto:
Optimum
profile
modifications
of
spur
gears
by
meansofgeneticalgorithms - Marco Barbieri, Giorgio Bonori, Francesco Pellicano Journal of Sound and Vibration 331 (2012) 4825–4829
26
[10] Design of truss-structures for minimum weight using genetic algorithms : Kalyanmoy Deb, Surendra Gulati - Finite Elements in Analysis and Design 37 (2001) 447-465
27
