Holografikus Kutatási Stratégia II. (iHRS)

Fórumok

Köszöntöm az olvasót!

Sokat gondolkoztam, hogy ez a bejegyzés blog, fórum, vagy írás legyen.
Fórum lett belőle, ha esetleg elvétettem a műfajt, elnézést kérek.

Itt a HUP-on néhányszór előkerült már a címben megjelölt módszer.
Íme az előzmények:

(1) http://hup.hu/node/7880
(2) http://hup.hu/node/22782
(3) http://hup.hu/node/8090

Az elmúlt hetekben elkészítettem a HRS-nek egy olyan változatát, amely
interneten keresztül is használható. A honlap elérhető itt:

(4) http://www.meditor.hu/ihrs.php

A honlapon keresztül hozzáférhető néhány segédinformáció is, az előzményeken
kívül ezekbe is érdemes belekukkantani.

Jelen fórumnak a célja: néhány érdeklődő számára lehetővé szeretném
tenni, hogy saját témájában kipróbálja a HRS-t. Szóval várom a
hozzászólásokat és az erdeklődőket (-::

Minden jót: Végvári Lajos [meditor]

Hozzászólások

Hm. Ez érdekes. Terjesztem a kutató ismerőseim között ;-)

Köszi!

Engem ugyan nem zavar, hogy fórumba írtad, de így kockáztatod, hogy hamar lekerül a fő oldalról -> kevés olvasója lesz.

Én hírként küldtem volna be emiatt.

G

Az ígért publikációs gyűjtemény:

itt: http://www.combi-nano.hu/information/Publications.htm
(az aláhúzott cikkek tölthetők le pdf-ben)

és még ezen az ftp szerveren::
host: meditor.hu vagy 62.77.254.100
user_név: public
jelszó: egy üres enter (nyomj egy entert és bent vagy)
és itt a ./hrspub/ könyvtár.

> Sol omnibus lucet.

Mint optimalizálási algoritmus, eléggé az a sanda gyanúm, hogy a legrosszabb előforduló futásidő alulról korlátozva lesz az input méretének exponenciális függvényével: http://www.meditor.hu/hrs_hu.php itt a Tejfalussy-tér létrehozásáról van szó. A mintaszám csökkentése meg költséges lesz... Még gondolkozom rajta egy kicsit. A Tejfalussy elrendezés egy konkrét hasznos alkalmazása lehet az, hogy egy korlátos poliéderen minden csúcsot meg akarunk határozni pivotálással (pl. akkor, ha egy konvex függvényt akarunk MAXimalizálni).

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

Azt azért csípem, hogy mindenki mást lát ebben az egészben. (-::

Pillanatnyilag nem foglalkoztunk a futásidővel, mert a konkrét
példákban az új generáció kijelölése pillanatszerű. A
legfontosabb szempont a reprodukálhatóság (determinisztikus)
és az alacsony mintaszám (szűk keresztmetszet a mérési
kapacitás) volt. Tapasztalatunk szerint, a tér méretének
növelésével nem exponenciálisan és még csak nem is lineárisan
növekszik a megmérendő minták száma. Sejtésem szerint
a mintaszám növekedése a "kicsi_világ" elve alapján növekszik:
azaz a teljes tér méretének egyre kisebb hányada szükséges
az optimum eléréséhez.

Abban igazad lehet, hogy a tér transzformációjának időigénye
exponenciálisan növekszik a tér méretével. Ugyanakkor nem
biztos, hogy az egyes vetületeket úgy kell képezni, ahogy azt
én képzem. Nagyon sok a nyitott kérdés!

Elfelejtettem betenni a nyitóhozzászólásba:
kapcsolat: meditor_kukac_meditor_pont_hu

> Sol omnibus lucet.

Szia!
ELőre jelzem: a publikációkat nem olvastam, csak a weboldalt.

Ha jól értelmezem, a probléma egy sokváltozós egészoptimalizálási probléma (az oldalon szereplő példában a változók egészek mind). A módszer arra irányul, hogy a keresendő függvényen határozzuk meg a lehető legkevesebb vektor kipróbálásával az állapottér globális szélsőértékét. Az ok-okozati folytonosságot nem értem, tulajdonképpen arra tudok gondolni, hogy a vizsgált függvényre igaz az, hogy bármely két olyan vektorra, amelyre igaz az, hogy távolságuk az L1-normában (Minkowski-norma) 1, akkor a hozzájuk tartozó függvényértékek valamely m (előre rögzített )korláton belül vannak (természetesen az állítás mindig igaz, hiszen m-et választhatjuk a függvény által felvett legnagyobb értéknek az adott téren, azonban ez a fajta "folytonossági" definíció ezzel az m értékkel használhatatlan bármire is). Tulajdonképpen diszkrét állapottéren a klasszikus folytonosság nem is definiálható, a feladat szempontjából a folytonos változókra való relaxálás gyakorlati szempontból (megvalósíthatatlan megoldás, pl. félig nyitott-félig zárt kapcsoló) kétséges.

A tér folytonosságát nem értem, hogyan kell értelmezni, nyilván igaz az, hogy minden x vektorhoz található olyan y vektor, hogy d(x,y) = 1 legyen ( a fenti metrikát használva). Azonban ebből a tulajdonságból nem következik, hogy minden ilyen téren értelmezett függvényre igaz a fenti definíció szerinti folytonosság valamely kis m értékkel. Azaz lehet, hogy m=3-t választva a fenti definíció szerint a függvény "folytonos" (két szomszédos vektor által felvett függvényérték különbsége mindig kisebb, mint 3), azonban a függvényt folytonosnak már nem lehetne nevezni m=2 esetén.

A vektorforgatás nem csinál mást, mint ( ha jól értem) az állapottér más-más vetületét vizsgálod gradiensmódszerrel (azaz tkp más-más koordinták szerinti szomszédok esetében keresed az optimumot).
Azaz az első lépésben az első két koordináta szerinti szomszédokat vizsgálod, utána a vizsgált vektorok második két koordináta szerinti szomszédait vizsgálod, stb.

Nem látom annak a bizonyítását, hogy ez a módszer valóban megtalálja a globális optimumot (azaz a nem mért értékek között miért nem lehet a globális optimumhoz tartozó állapotté-vektor?)

Ui. Elolvastam a "Lajos Vegvari, Andras Tompos, Sandor Gobolos, Jozsef Margitfalvi, Holographic research strategy for catalyst library design: Description of a new powerful optimisation method, Catalysis Today, Volume 81, Issue 3, European Workshop on Combinatorial Catalysis, 30 June 2003, Pages 517-527" cikket. Ez alapjan kerdezem: mi alapjan dontitek el, mekkora kornyezetben mertek egy-egy lepesben? A cikkben 5-s tavolsag szerepel. Masreszt hogyan kerulitek el azt, hogy az allapotterben egy nagy kornyezetben lokalis optimumot tekintsetek globalis optimumnak a valodi, kis kornyezetben lokalis globalis optimum helyett, azaz magyaran hogyan tud az algoritmus egy nagymeretu godorbol a godor aljarol indulva kilabalni ahhoz, hogy megtalalja a szuk szakadekot?

Nem találtam semmilyen bizonyítást (nem matematikusi hozzáállás) vagy nagyszámú, jegyzőkönyves mérést (nem mérnöki hozzáállás) a mellékelt URL-eken. Ez még egy ln(a)-csillóstalpsovén-féle koketta-kokettő előadáshoz képest is bányászbéka alatti színvonalú - jelenlegi állapotában. Szerintem csak projekciókkal meg átkoordinátázásokkal való zsonglőrködés történik a leírásokban. Semmilyen korrektül definiált és tisztázott metrikafogalom, sem konvexitás, sem analítikus tulajdonságok, sem pedig kombinatorikus struktúrák fel- és kihasználása nem történik meg - ezek nélkül eredményt elérni nehéz lesz.

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

Kedves persicsb!

Először is köszönöm a kérdéseket. Az derül ki belőle, hogy érdemben próbáltad meg átgondolni az általam felvetett témát. Megpróbálok értelmes válaszokat adni, bár tőlem a matemetikai szakzsargon kissé távol áll:

Az első kérdéscsoport a folytonosság. két aspektusból merült ez föl: A tér aspektusából a folytonosságot úgy kell érteni, hogy bármely elrendezésre igaz az, hogy két szomszédos adat mindig csak egy kombinációban tér el, azaz minden pontot "legközelebbi rokonai vesznek körül". Ez a Tejfalussy tér leglényegesebb eleme.

A másik aspektus a változók folytonossága. Technológiai szempontból csak az a megoldás létezik, hogy a paramétereket egy konkrét értékre állítod. Vagyis a szóba vehető értelemzés tartományt kvantálod (nem muszáj lineárisan), és az így kapott paraméterértékeket állítod be. Természetesen nincs garancia arra, hogy pont az optimális értéket találod el, arra viszont van lehetőség, hogy (a) a paraméter szintjeit növeld, (b) a gradiens mértékét csökkentsd úgy, hogy az optimumot megpróbálod fókuszban tartani. Ezt nagyon hatékonyan alkalmaztuk egy 9 paraméteres térben, ahol egy matematikai modellben minimumot kerestünk. A HRS nagyságrendekkel gyorsabban talált sokkal jobb adatot, mint a korábbi próbálkozások. Erre a gradienscsökkentési lehetőségre mutat rá a
http://www.meditor.hu/IHRS/hrs_realmode.pdf fájl ábrája.

A kérdések sorában jön az ok-okozati kitétel. Itt arra utaltam, hogy nem lehet egy tetszőleges vektorrendszerhez egy tetszőleges adatbázist rendelni! Más szavakkal: egy 8 dimenziós technológiai tér segítségével nem lehet megtalálni Kékestetőt Magyarország domborzati térképén! Kipróbáltam (-::

A vektorforgatást jól érted.

Nézzük a gödröt: amit az egyik vetületben nagy-nagy dolinának látunk, az egy másik vetületben apró-pici lyukacska! Ez a lényeg! Nyilván elképzelhetők olyan terek, amelyek 2 féle értéket tartalmaznak: nagyon-nagyon sok egyforma értéket és egyetlen, ezektől különbözőt. Ezt nem fogja megtalálni a HRS! Érdekes lenne megvizsgálni, hogy az inhomogenitásnak milyen mértéke szükséges ahhoz, hogy az eljárás működjön. Ha azonban azt hinnénk, hogy nincs információtartalma annak, hogy a HRS egyhelyben topog, akkor tévedünk: ez azt jelenti, hogy a vizsgált vektoroknak az adott felbontás mellett nincs technológiailag kimutatható hatása!

A gyakorlati példák igazolták feltevéseinket: Amikor találsz egy olyan 8 komponensű katalizátort, amelynek 99.8 %-os a hatékonysága, akkor nem nagyon keresed meg a 100 %-os adatot (elméleti optimum), tudva azt, hogy a mérési hiba az elméleti adattól való eltérésnél legalább 1 nagyságrenddel nagyobb.

Remélem érthetően mondtam el a dolgokat.

> Sol omnibus lucet.

Bocsáss meg, ha hosszú leszek, de én is egészoptimalizálási, pontosabban vegyes egész optimalizálási problémákkal foglalkozom, így érdekel a dolog.

Kezdjük egy matematikailag modellezni a dolgot.

Adott n db változó, az i-edik változó n_i lehetséges értékkel rendelkezik (azaz hány részre kvantálod a vizsgálni kívánt intervallumot). Ekkor egy változó konkrét értéke leírható egy egész számokból álló rendezett n-essel, x = (x_1,...,x_n), ahol 0<= x_i <= n_i .

Ezen rendezett n-esek halmazát nevezzük most problématérnek, jelöljük O-val. Természetesen a problématér nem vektortér, mert nem teljesíti a vektortér definívióját. Ezért ezentúl a problématér egyes elemeit poblémának nevezzük, nem vektornak.

Definiáljuk a problématéren az alábbi metrikát: d(x,y) = szumma[i = 0, ] ( | x_i -y_i| ). Azaz a két probléma távolsága megegyezik a koordinánkénti elétérések összegével (úgynevezett L1-norma). Természetesen minden x problémához található legfeljebb 2n db olyan y probléma, hogy d(x,y) = 1. Azért legfeljebb 2n, mert a problématér szélén álló problémákra (azaza olyanokra, amelyre valamely x_i = 0, vagy x_i = n_i) igaz az, hogy abban a koordinátában csak n probléma van 1 táolságra (ahol x_i = 1, illetve ahol x_i = n_i -1 ), míg a problématér belsejében lévő problémákra minden i-edik koordinátára x_i -1 és x_i + 1 szomszédok. A Tejfalussy-elrendezés tkp. csak a problématér olyan a_1,a_2,...,a_nxn bejárását adja meg, amelyben biztosított, hogy minden j-re d(a_j,a_j+1) = 1. A Tejfalussy-elrendezés ezen kívül rendkívül jól vizualizálható, de ezen kívül más jelentősége nincsen, a feladat valódi szempontjából (optimaliálás) irreleváns a megoldási folyamat vizualizálása, legfeljebb jobban kommunikálható :). Te tulajdonképpen a tér folytonossága alatt azt érted, hogy a Tejfalussy-féle bejárás által adott problémasorozatra igaz a d(a_j,a_j+1) = 1 tulajdonság. Ez természetesen ilyen bejárás minden ilyen típusú térben megadható. Látható, hogy a tér folytonossága, mint a te definíciód szerinti fogalom, nem a Tejfalussy-féle elrendezés érdeme, az a tér alapvető tulajdonsága.

Legyen f: O -> R a problématéren értelmezett valós értékű korlátos függvény, amelynek keresed a problématéren vett maximumát ( vagy minimumát). Namármost f korlátosságából következik, hogy a f-re igaz az, hogy bármely x,y probléma esetén, ha d(x,y) = 1, akkor | f(x) - f(y) | <= M, valamely 0< M korlátra. Természetesen ez az M a függvénytől függ, értéke egészen nagy és egészen kicsi is lehet.
Tegyük fel, hogy a függvény kiértékelése valamely pontban (tkp. a mérés) költséges (nagy számítási teljesítményt igényel, nagy az anyagköltsége, stb., a HRS szempontjából ez irreleváns).

A HRS eljárás célja, hogy megadni az O olyan S részhalmazát, amelyre szűkítve a szükséges méréseket, az f optimuma jó közelítéssel megadható.

Az eljárás működését gondolom neked nem kell részleteznem, szerintem mindketten értjük, miről van szó.

Na és most jön az igazán lényeges dolog: az, hogy mennyire jó megoldásokat tudsz találni, a mérendő függvénytől függ, pontosan a fent említett M szám nagyságától. Ha ez az M nagyon nagy érték, akkor előfordulhat az, hogy egy nagyon rossz problématér-pont szomszédja éppen az optimális megoldás, azonban a HRS az ilyen pontokat, mivel rossz pontok szomszédai, nem fogja vizsgálni.

Tehát a végkövetkeztetés a következő: a HRS valóban használható arra, hogy technológiailag a keresett függvény tényleges optimumértékéhez közeli értékű megoldást adjon, azonban a HRS működésének jósága nagyban függ a vizsgált függvénytől, pontosabban a fent nevezett M értéktől. Amennyiben az M értéke kicsi, úgy a HRS által adott megoldás nem fog nagymértékben eltérni a valódi optimumértéktől. Azonban ha M értéke nagy, ez az eltérés nagy lehet.

És itt található meg a HRS legnagyobb hibája: nem mondható meg az algoritmusnak, hogy a valódi optimumtól legfeljebb mekkora eltérésű megoldást adjon, azaz nem lehet megmondani, hogy akkor álljon le a keresés, ha a talált megoldás 1-10-15%-ban tér el a valódi optimumtól.
Ezért annak a becslése, hogy a talált megoldás hány %-os hatékonyságú, teljesen értelmetlen, hiszen nem tudod, hogy a problématéren mekkora a valódi optimum, anélkül, hogy minden szükséges pontot végig nem számoltál volna, amely pesszimista esetben a teljes tér végigszámolását követeli. Sajnos ez elől nem lehet kibújni, hiszen egészoptimaliálásban ismert az a probléma, hogy bizony vannak olyan esetek (olyan f függvények), amelyeknél M értéke sajnos olyan nagy, hogy a valódi optimum megtalálásához végig kell számolni a teljes teret.

A HRS algoritmus tehát akkor működik jól, ha M értéke kicsi, azaz a függvény meglehetősen folytonos, nincsenek benne nagy kiugrások és gödrök. Amennyiben az általatok mért függvények ilyenek (ahogy a publikációkban láttam, általában katalizátorvegyületek szintézisére használjátok, itt sajnos nem tudom mi az a függvény, amely meghatározza egy katalizátorvegyület jóságát, így nem tudok arról beszélni, hogy itt mennyire használható a HRS), akkor a HRS használható arra, hogy egy jó megoldást adjon.
Viszont a fentiek miatt sajnos a követezőt nem lehet tenni:
- nem állítható, hogy az algoritmus megtalálja az optimumot.
- nem adható becslés arra, hogy az algoritmus által talált megoldás mekkora mértékben tér el az optimumtól. Természetesen ez csak akkor van így, ha az f függvény maximumának vagy minimumának az *értékét* nem ismerjük és csak az optimum helye a kérdéses. Ha tudjuk, hogy a problématéren mekkora ez a maximum, illetve minimum (tipikusan így van ez, ha valamiféle arányról beszélünk, azaz a függvény legnagyobb értéke 1, legkisebb 0, és ezt a téren valahol fel is veszi), akkor természetesen mondható, hogy mekkora az eltérés az optimumtól. Azonban sokszor magát az optimum értékét sem tudjuk, nemhogy csak a helyét.

Ezért lehetett az, hogy nem találtad meg Kékestetőt: az általad választott 8-dimenziós függvény M értéke nagy volt.

Remélem érthető.

A HRS korlátait ilyen precízen senki sem foglalta össze, köszönöm. Megpróbálok saját szavaimmal megfogalmazni néhány dolgot a fentiekből:

A Tejfalussy elrendezésről: való igaz, hogy az elrendezés a vizualizáció terén hozott nagy újítást. Ez szerintem óriási előrelépés a korábbi - sőt a mai napig bevett - módszerekhez képest. Van azonban egy nem triviális előnye is: amikor technológiai paramétereket állítgatsz, sokkal könnyebb Tejfalussy térben haladva ezt megtenni - hiszen mindig egyetlen paraméter egyetlen szintje változik csak!-, mint mondjuk egy random elrendezés esetén. Ez nemcsak a paraméterbeállításoknál jelentkezik előnyként, hanem - nem túl nehezn látható be - a mérési zajra is igen jó hatással van. Abban egyetértek, hogy bármilyen numerikus módszer esetén nincs szükség a Tejfalussy térre, hiszen egy bemeneti/kimentei adathalmazt kezelünk, amely nem az adatok elrendezésétől lesz folytonos.

Az teljesen világos, hogy az optimumkritériumnak megfelelő függvényértéket az ujjunkból kiszopni nem tudjuk, így a kapott eredmény és a tényleges optimum közötti eltérés nem adható meg. Éppen ezért volt fontos az a néhány keresés, amelynél ismert egy elméleti határ: ha ezt megközelíted elhanyagolható hibával, akkor O.K. (esetünkben: 100 % közeli hatásfok). Tehát csak bizakodhatunk abban, hogy megtaláltuk a globális optimumot. Ugyanakkor azt állítom, hogy ha a térben szakadás van (tekintsük ezt a feltételt a HRS halálának), ez két okból eredhet: (1) nem megfelelő vektorokat vettünk figyelembe (2) a kvantálási folyamat hibás. Az előbbire példa mondjuk a higany halmazállapota (a tömegszámok szerinti elrendezésű periódusos rendszerben kicsit érthetetlen a folyékony halmazállapot), a másodikra pedig túl ritka mintavétel. Ez utóbbi másként megfogalmazva: Ha egy jelenség körül sűrűn veszünk mintát (= a kvantálási távolságot csökkentjük), akkor a szakadékból előbb egy szűk völgy, majd egy széles plató lesz, ahogy a gradiens csökkentjük. Most nyer értelemet az a korábbi mondatom, hogy "a vizsgált vektoroknak az adott felbontás mellett nincs technológiailag kimutatható hatása!"

A HRS halála tehát valójában mintavételezési probléma! Nagyobb szemű hálóval akarunk halat fogni, mint amekkora a hal.

Ha teljesen biztos lennék a dolgomban, nem nyitottam volna meg ezt a topikot. Az eddigi tapasztalatok azt mutatják, hogy a HRS sok más optimalizációs módszernél(pl: simplex, G.A.) jobban teljesít. Szeretném kipróbálni olyan területeken is, amelyekre eddig nem volt rálátásom. Ugorjon ki a bokorból a nyúl!

További érdekes terület a "kicsi_világ" szerű működés, illetve a nem teljes kombinációs terek vizsgálata. Várom az ötleteket!

(-::

> Sol omnibus lucet.

Kicsit off: Gondolom te is ismersz jópár viccet az "igazi matematika" használhatóságáról. :-)

Az a helyzet, hogy Végvári kollégát személyesen is ismerem így azt hiszem, az a dolog, amit te "marketingblablaként" említesz nála valójában a téma iránti egyszerű lelkesedés.

---
Science for fun...

Magam is dzsávahuszár lennék, mégis inkább segíteni próbálok meditornak a magam módján. Foglalkozom optimalizálási dolgokkal is valamilyen szinten, ezért érdekel is a módszere, csak úgy látom, nem eléggé egzakt. Azt hiszem, ennek a topiknak pont az a célja (legalábbis azzá vált), hogy segítsünk egy kis matematikai alapot biztosítani a módszernek. Így bizonyíthatóak lesznek lehetőségei és korlátai.

Az, hogy ki milyen hasznos dolgot tud megmutatni, más kérdés. Hasznos dolog-e egy J2EE architektúrán íródott banki rendszer? Hasznos dolog-e az iWiW? Hasznos dolog-e a HRS? Ezekre a kérdésekre mindenki másképpen válaszol.

"Pedig tényleg nem ártana korrekt matematikával megtámogatni a dolgot..."

Ebben teljesen igazad van. A gond az, hogy - ha jól értem - ez egy fejlődőben levő módszer, ami jelenleg inkább heurisztikus, mint egzakt.

Az egzakt matematikai leírások törénetileg általában úgy születnek, hogy sok ember sokáig össze-vissza beszél mindent, aztán valaki, aki ezt sokáig csendben nézte egyszer csak megmodja a frankót három mondatban, meg pár általa bevezetett jelöléssel.

Hangsúlyozom, hogy én a HRS módszert abszolút érintőlegesen ismerem csak (Lajos mesélte egyszer, amikor nálunk járt), de az az érzésem, hogy egyelőre az össze-vissza beszélős fázisában tart, így olyasmit kérsz rajta számon, amire nem képes. Még nem.

---
Science for fun...

En sem vagyok expert matematikaban ( te pl tobbet tanultal matekot, lasd a matekszigorlatos forumbejegyzesemet), csak egy egyszeru informatikus vagyok, aki megtanult par problemat matematikailag tobbe-kevesbe egzaktul modellezni. Elvegre rendes elmeleti hatter nelkul sokat nem ernek az algoritmusok.

nem vitattam a szakmai hozzaerteset, vagy akarmit :) csak hogy ha mar matematikai elmeletekrol beszelunk, akkor kvazi kotelezo a pontos fogalmazas.

pl nem lehet azt irni, hogy folytonos a ter, csak ha:
- az alap folytonossagi definiciora gondolunk (mint itt kiderult, nem arra9
- definialjuk matematikai alapossaggal a mi folytonossagdefinicionkat

Hát, azért azt nem hiszem, hogy a matematika fogalma definiálásra szorulna, meg azt se, hogy a flame kategóriában volna a helye. És egyébként is, a téma maga lenne a dögunalom, hiszen matematikai egzaktsággal nem lehet se káromkodni se anyázni. :-)

Ellenben a "marketingblabla" na az már egy érdekesebb dolog. Adnék rá egy 1.0-ás meghatározást, aztán lehet tovább finomítani, akár a HRS-sel.

'A marketingblabla az a jelenség, amikor egy eszközt, személyt vagy bármely tetszőlegesen általános témakört megpróbálunk úgy bemutatni, hogy arra a közönség fölfigyeljen.'

Marketingblabla tehát bármely mosóporreklám, ilyen a kormányprogram, illetve ilyen bármely szakmai önéletrajz. (Igen NagyZ, a tiéd is.)

---
Science for fun...

Téged is értelek, a magad módján igazad is van. Mégis a jelen témával kapcsolatban az az érzésem, hogy az a bajod, hogy matematikusok tanítottak.

Amit követelményrendszerként leírtál, az egy matematikai szaklap követelményrendszere. Ha azonban megpróbálsz a gyakorlat oldaláról közelíteni hozzá (kémikus laborban katalizátorokat buzerál), akkor te magad is láthatod, hogy ez olyan, mintha egy gyerektől azt várnád, hogy 27 évesen, öltönyben, nyakkendőben, PhD fokozattal a zsebében szülessen meg. Semmi pelus, semmi kamaszkor, téged csak a végeredmény érdekel.

Na, ettől olyan használhatatlan az "igazi" matematika. Nem engedi játszani az embert.

---
Science for fun...

Sot a simplexrol bizonyitott, hogy ( noha nehany esetben exponencialis lepesszam alatt), de mindig megtalalja a globalis optimumot. Ugyanugy, mint a mi tanszekunkon hasznalt halozatoptimalizalasi kombinatorikus algoritmusok is bizonyitottak. A HRS eseteben egzakt hatteret es annak a bizonyitasat sem lehet latni, hogy egyaltalan veges lepesben megall-e.

Egy matematikailag joldefinialt rendszer nem feltetlenul dogunalmas. Peldaul a HRS-t definialod matematikailag, fogalomrendszered es allitasaid lesznek. Innentol kezdve jon csak az erdekes resz: az allitasok nem alkalmazhatok szelesebb fogalomkorre? Mely esetben lehet pontosabb allitasokat megfogalmazni? Stb.

A vizualizacionak mi koze van a modszerek lefutasahoz? Nem ertem, miert befolyasolja a vizualizacio soran a problemak elrendezese az algoritmus lefutasat. Rendezett n-esekrol beszelunk, es a vizualizacio, vagyis ahogyan te nevezed, az elrendezes nem befolyasolja a ter tenyleges szerkezetet, igy a Tejfalussy-elrendezes a feladat es a megoldas lenyegen semmit, de semmit nem valtoztat, matematikailag irrelevans. Nehogy egy algoritmus mukodeset a vizualizalas befolyasolja! De tenyleg. Ne felejtsuk el, rendezett n-esek korlatos reszhalmazarol, es ezen a reszhalmazon ertelmezett optimalizalasi problemarol beszelunk, semmi masrol.

Mit ertesz az alatt, hogy a meresi zajra minek van hatasa? Van produktum(i=0,n) n_i db problemad. Ne felejtsuk el, hogy a problemak diszkretek. A meresi hibak csak abban az esetben okozbak bajt ( es ez fuggetlen az "elrendezestol"), ha a meresi hiba nagyobb, mint az adott valtozo finomsaga. Finomsag alatt itt az analizisbeli definiciot ertem: a kvantalasi intervallumok hosszanak a supremuma.

Azt, hogy a terben szakadas van, az hulyeseg, legfeljebb a fentebb felirt modellre mondhato az, hogy a fuggveny, amit vizsgalunk, ket szomszedos problemater-pont eseteben egy bizonyos M szamnal nagyobbb mertekben ternek el egymastol.

Ugy latom, nalatok nincs elkulonulve a szohasznalatban a vizsgalt fuggveny, es az a ter, amin a fuggvenyt vizsgalod, pedig ez jo lenne.
A vizsgalt fuggveny folytonossagarol lehet beszelni, a fuggveny ertelmezesi tartomanyanak folytonossagarol is, csak esetetekben ugy van megkonstrualva az ertelmezesi tartomany, hogy az eleve folytonos (nekem nagyon zavaro diszkret ertekek eseteben folytonossagrol beszelni, nektek nem?).

Ezek a mondatok szamomra nehezen ertelmezheto:"a vizsgált vektoroknak az adott felbontás mellett nincs technológiailag kimutatható hatása!", "(1) nem megfelelő vektorokat vettünk figyelembe", "Az előbbire példa mondjuk a higany halmazállapota (a tömegszámok szerinti elrendezésű periódusos rendszerben kicsit érthetetlen a folyékony halmazállapot)"
Namarmost egyetlen vektornak (problemater-pontnak) mire is lenne hatasa?

Szerintem ti keveritek a vektor( a problemater egy eleme ) es a vizsgalt dimenziok (parameterek) fogalmat. Termeszetesen lehetseges, hogy az adott parameter figyelembevetele/nem vetele nem befolyasolja a feladat megoldasat. Gondolom erre akart utalni a higyanos pelda.
"ha a térben szakadás van (tekintsük ezt a feltételt a HRS halálának)". Diszkret ertekekbol allo teren mit tekintesz szakadasnak? Folytonos teren meg csak-csak van ertelme, de diszkreten legfeljebb azt mondhatod, hogy ket 1-tavolsagra levo problema fuggvenyerteke kozotti elteres valamely elore rogzitett M szamnal nagyobb, mint azt mar fentebb irtam.

Ugy latom, az okozza a legnagyobb problemat a HRS egzaktta tele eseteben, hogy par dologra olyan nevet hasznaltok, amelynek joldefinialt jelentese van a matematikaban. Azonban a ti dolgaitokra ezek a fogalmak es azok matematikai hasznalata nem alkalmazhato (peldaul folytonos matematikai fogalmakat diszkret problemak eseteben nem lehet hasznalni, ilyen a szakadas, a folytonossag, stb). Ismerjetek fel, hogy a ti problematok a folytonos matematika eszkozevel es fogalomrendszerevel nem oldhato meg. Onnantol kezdve, hogy a vizsgalt parameterek ( a problemater dimenzioi) kvantaltak, kovetkezik a problema nem folytonos jellege.

Szerintem csinaljatok a kovetkezot ahhoz, hogy egzaktta tegyetek a HRS leirasat:
1. alkalmazzatok jol definialt fogalomrendszert (feladat, vektor, problema, "folytonossag", stb.)
2. tegyetek allitasokat a HRS mukodeserol a fenti fogalomrendszert hasznalva.
3. Deduktiv matematikai modszerekkel bizonyosodjatok meg a 2-es pontban elkeszitett allitasok igazsagarol/hamissagarol.

Enelkul nem fog menni a dolog.

A kicsi vilag- szeru mukodes alatt mit ertesz? A kis vilag fogalom a grafelmeleti kutatasok fogalma, a skalafuggetlen grafok egyik tulajdonsaga. Hogy jon ez diszkret optimalizalasi problemakorbe?
Barabasi-Albert Laszlo Behalozva (Linked) c. konyvet tudom ajanlani ismeretterjeszto jelleggel a kis vilag temaban.

No, látom elment konstruktív irányba a téma. Ez jó. A feladat tehát adott: Egzakt módon le kell írni a HRS-t. Ahogy buki kolléga mondja az összevissza_beszéd fázison kéne túl lépni. Én - és ez talán nem túl nagy szégyen - erősen korlátos vagyok matematikailag. Tehát: segítséget kérek az itt előforduló kollégáktól.

Érdemes esetleg megnézni a guglival a "Holographic Research Strategy" címszót, hátha van egy-két értelmezhető - ha nem is egzakt - megközelítés.

> Sol omnibus lucet.

Foglaljuk egy kicsit össze az elhangzottakat!

Először is két dolgot el kell különíteni: A HRS működőképességét és a HRS leírását. Mondjuk jobban örültem volna, ha többet foglalkozunk azzal, hogy hol és miként lehet kipróbálni a HRS-t, itt most konkrét feladatok felvetésére gondolok.

Most először nézzünk néhány apróságot:

Abban egyetértünk, hogy a vizualizációnak nincs hatása az optimumkeresésre, abban viszont nem, hogy a Tejfalussy elrendezés egy konkrét technológiai folyamatban ne lenne hatással a mérési eredményre (itt a zajra gondolok elsősorban, beleértve az emberi tévedés valószínűségét is.)

Abban is egyetértünk, hogy a matematikai alapok nagyrészt hiányoznak részben beleértve a saját fogalomrendszert is.

Nem értünk egyet abban, hogy a HRS pusztán numerikus módszer. Meglátásom szerint a pillanatnyi optimum vándorlása gráfelméleti módon is megközelíthető, ugyanis a sokdimenziós térben (egy keresőablak használata esetén) ez a vándorút úgy rajzolható meg, hogy közben csak megmért pontokat érintünk. (Megkockáztatom: a cerozát sem kell fölemelni!) Tehát eljutunk valahonna valahová, mégpedig irányított módon.

Egyelőre ennyi.

> Sol omnibus lucet.

Nos, nézzük.

A HRS működőképessége következik az egzakt leírásásából (az egzakt leírásból következtetni lehet az eljárás hatékonyságára pl.), így ez a két dolog nem lehet egymástól független.

Nyilván senki nem fog addig neked konkrét ötleted adni arra, hogy hol és miként használható (kipróbálható) ez a módszer, ha az érintett illető egyrészt nem találja meg sehol az egzakt leírását annak, hogy 1. hogyan kell elvégezni a méréssorozatot, azaz mi valójában a módszer (erre pontos leírást még a publikációkban sem láttam - azaz az eljárás nem reprodukálható teljesen pontosan más által), 2. nem látja bizonyítottnak, hogy a módszert érdemes-e egyáltalán alkalmazni az ő célfüggvényének az optimalizálására.

"Tejfalussy elrendezés egy konkrét technológiai folyamatban ne lenne hatással a mérési eredményre (itt a zajra gondolok elsősorban, beleértve az emberi tévedés valószínűségét is.)".
Nem értem miért kell ragaszkodni a Tejfalussy-elrendezéshez, mint olyanhoz. Már fentebb írtam, hogy az általatok használt rendezett n-esek esetében minden x vektor esetében találsz olyan y "szomszédot", amelyre igaz az, hogy a távolságuk 1. Az, hogy ezután ezeket a problématér-beli pontok egymástól való távolságát hogyan vizualizálod, az tök más kérdés. Például nem kell tudnom, hogy mi az a Tejfalussy-elrendezés ahhoz, hogy tudjam, hogy az (1,2,15) vektornak az (1,2,16) vektor és az (1,3,15) vektor is szomszédja (sőt, az 1,1,15 vektor is). Ahhoz, hogy egy problématér-beli pont szomszédjait meg tudjam mondani, semmi más nem kell, mint egy egyszerű algoritmus, nem kell hozzá semmiféle speciális elrendezés, vagy bármi ilyesmi. Nem értem, hogy a problématér-pontok vizualizálása miért van hatással a mérési eredményekre. A mérések nem mások, mint az optimalizálandó célfüggvény kiértékelése a problématér pontjaiben. Hogyan befolyásolná mondjuk az f (1,2,5) pontban való kiértékelése az (1,2,4) pontban való kiértékelését?

Nyilván az is igaz, hogy az algoritmus (amely algoritmus teljes leírását még nem közölted a fórumozókkal, pl. kiindulási feltételek, leállási feltételek, stb) futása során a k-adik lépésben vizsgált n-dimenziós problématérben az éppen tárolt legjobb megoldás értéke ábrázolható úgy, mint egy k hosszúságú sorozattal. Természetesen lehet a problématér pontjaiból gráfot definiálni, például a következő módon: legyen G = (V,E) a kérdéses gráf, E a problématér pontjaiból álljon, és (x,y) eleme E pontosan akkor , ha d(x,y) = 1. De gráfot kapunk akkor is, ha a G fenti definíciójában azt mondjuk, hogy d(x,y) = 3, stb. Nem látom, hogy egy tetszőlegesen definiált gráf csúcsain való lépkedésnek mi köze van egy n-dimenziós diszkrét halmazon való optimalizálásnak. Nem látom, hogy az algoritmus által bejárt pontok k hosszúságú sorozatából hogyan lehetne következtetni a k+1-edik elemre (akár arra, hogy melyik lesz az, akár arra, hogy melyik nem lehet az) a függvényértékek becslése nélkül.

Talán a simplex-módszerrel szeretnéd párhuzamba hozni? Tény, hogy a simplex-módszer által az algoritmus futása során bejárt csúcsok sorozatát lehet értelmezni a feladat feltételei által kifeszített konvex n-dimenziós poliéder gráfjának élein való lépkedéssel, azonban sajnos van egy nagy különbség a simplex-módszer problématere és a ti problémateretek között: a simplex-módszer valóban folytonos téren operál, valamint a problématér konvex, és igaz az, hogy a megoldáshalmaznak mindig eleme csúcspont (a problématér egy bázisvektora). Azonban ez diszkrét optimalizálási problémáknál nincs így, nem feltétlenül igaz az, hogy a problématér "szélei" mindig benne vannak az optimális részhalmazban. Ez azért van így, mert folytonos téren értelmezett optimalizálási problémák esetén 3 eset lehetséges: a feladatnak nincs megoldása, pontosan egy megoldása van, végtelen sok megoldása van. Diszkrét esetben pedig mindig van megoldás (lehet, hogy egy, lehet, hogy a tér összes pontja - ha a függvény egyértékű), hiszen véges sok pont van, azaz véges sok lehetséges függvényérték is. Véges halmaznak pedig mindig létezik legkisebb, vagy legnagyobb eleme.

Szerintem a forumozók nyitottak arra, hogy segítsünk egzaktabbá tenni a módszereteket, azonban azt kérném, hogy foglaljátok össze a következőt:

1. Pontosan milyen probléma kapcsán használtátok az algoritmust? Mi volt a bemenet, mi volt a vizsgálandó célfüggvény?
2. Mik a pontos lépései az algoritmusnak? Mi a megállási feltétel? Ezt sajnos sehol nem láttam leírva. Algoritmusok publikálásakor illik a pszeudokódot is közölni, mert anélkül nehezen reprodukálható az algoritmus. A kísérlet (akár elméleti) reprodukálhatósága nélkül viszont maga a publikáció nem sokat ér.

Légyszíves ezeket írd le, enélkül nem tudunk segíteni.

Nos, úgy látom az egyik legnagyobb probléma, hogy, ami nektek nyilvánvaló, az nekem nem és fordítva. Próbáljuk ki, mi van akkor, ha teljesen új foglamakat vezetünk be HRS leírása során és a működést ezeknek a fogalmaknek a segítségével mutatjuk be.

Azokat a fizikai vagy logikai ismérveket, amelyek a kimeneti adatra hatással vannak és amelyeket a megfigyelésbe bevontunk (pl: hőmérséklet, nyomás), nevezzük FIGURÁnak (nem röhögni!). Jelölésük F0, F1, F2...stb.

A figura egy konkrét értékét nevezzük ÁLLAPOTnak és konkrét értékével jelöljük pl F0_350.

Egy figura állapotának legkisebb és legnagyobb értéke közti távolságot TERJEDELEMnek (T) nevezzük.

Az összes figura összes állapotának kombinációja(?) által meghatározott kimeneti táblázatot MEZŐnek nevezzük (M). Több kimenet esetén a mezőket M0, M1, M2-vel, vagy fizikai tartalmukkal jelöljük

A mező egy elem az EGYED (E), egy konkrét egyedet sorszámával (táblázatban elfoglalt helyével) jelülünk. Az egyed számértékének nagyságát MAGASSÁGnak nevezzük. A konkrét számértékkel bíró (megmért, kiszámolt) egyed HATÁROZOTT, egyébként határozatlan.

A határozatlan egyedek összessége a VAKMEZŐ, a határozottaké SZÉPMEZŐ.

A figurák egy meghatározott sorrendjét és az ehhez tartozó mezőt VETÜLETnek nevezzük.

A figurák egymáshoz képest sorrendjét POZÍCIÓnak nevezzük.
(P0...Pn). Ertelemszerűen egy figurának annyi pozíciója lehet,
ahány figura létezik és két különböző vetületben a legalább két figura pozíciója különbözik.

Gyorsan bevezetünk egy segédjelölést: Az állapotot jelölhetjük a gradiensben elfoglalt helyével is. Azaz, ha a egy figura terjedelmét mondjuk 5 lépésben határozzuk meg, akkor beszélhetünk F_l0, F_l1, F_l2, F_l3 és F_l4 állapotokról.

Most ezt gyorsan megpróbálom megjegyezni és csinálok egy kis leírást a HRS működéséről ezeknek a foglamaknak a segítségével.
Ne felejtsük: ez most egy játék, hátha kisül belőle valami.

> Sol omnibus lucet.

Elöljáróban: megpróbálom az egészet értelmes magyar nyelven, a definiált fogalmak segítségével leírni. Aztán, ha kisül belőle valami, lehet visszahelyettesítani a matematika terminus_technikusait.

I. Sokfigurás mező meghatározása.

1. veszünk tetszőleges, de véges számú figurát.
2. meghatározzuk az egyes figurák terjedelmét.
3. A terjedelmeket tetszőleges, de véges számú szakaszra
osztjuk. A szakaszok határai lesznek az adott figura
állapotai.

Megjegyzés: a gyakorlatban 6-16 figurát és figuránként 3-6 állapotot szoktunk használni.

4. A figurák szintjeit Tejfalussy szerint rendezzük el.

Megjegyzés: általában igyekszünk "négyzet-közeli" ábrát
használni a jobb nyomonkövethetőség érdekében. Nevezzük
el a kiinduló vetületet BÁZISvetületnek (Vb)

Itt térek ki a célfüggvénnyel kapcsolatos kérdésre. Végzünk
ugyan szimulációkat (hogyan generálunk ezekhez célfüggvényt,
az egy külön történet, valszeg ezért még többet kapnék itt a
pofámra, mint a HRSért), de a való életben NINCS célfüggvény.
Van egy határozatlan egyed az ő figuráinak állapotával, és
ebből mérés útján határozott egyedet csinálunk.

> Sol omnibus lucet.

II A kezdeti szépmező meghatározása.

Erre két lehetséges módszert használunk. Az egyik
a véletlen kiválasztás. Ez különösebben nem szorul magyarázatra. Véletlengenerátor segítségével [srand() fv]. kiválasztunk néhány egyedet (gyakorlati érték 20-120 dbot) és ezeket megmérjük. Természtesen semmiféle elvi megkötés nincs arra, hogy hány egyedet jelöljünk a kezdeti szépmezőbe, rendszerint a mérési kapacitás a meghatározó. Megjegyzés: csak és kizárólag szimuláció közben és összehasonlító céllal szoktuk használni.

HRS kiválasztás:

1. Vesszük a bázisvetületet (Vb) és ennek szimmetriapontjait mérésre jelöljük ki: az egszerűség kedvéért beteszek egy képet, hogy érthető legyen, aki akarja foglamazza meg nálam ügyesebben azt, hogy mit lát.

http://www.meditor.hu/IHRS/d4first.gif

2. Megvizsgálom hogy minden figura minden állapota legalább egyszer képviselve van-e, ha nincs biztosítom ezt. (Ez rendszerint egy átló mentén elhelyezkedő egyed-sorozat szokott lenni.)

Természetesen bármilyen más módon is inícializálni lehetne a szépmezőt.

> Sol omnibus lucet.

Egy baj van ezzel: a bázisvetület szimmetriapontjai függenek a bázisvetület szerkezetétől. Ugyanis a bázisvetület így ered: két halmazra osztod a figurák halmazát, amely két halmaz a vetület két tengelyét adja. De ez a két halmaz meghatározása tetszőleges, így valójában a kezdeto szépmező kiválasztására nincsen szabály. Ez viszont baj, hiszen így ugyanazokkal a figurákkal, ugyanazokkal a terjedelmekkel az algoritmus a bázisvetület tetszőlegesége miatt gyakorlatilag véletlen értékekkel indul. Mi a szabálya a bázisvetület képzésének? Azaz mi alapján osztod két halmazra a figurákat? Ez nagyon nem mindegy, hiszen befolyásolhatja az algoritmus futását (amelyről még mindig nem tudunk semmit...)

Nem írod le, hogy mi az algoritmus célja. Az első lépését, a bemenet meghatározását leírod, de a célt nem.

Azt írod, nincsen célfüggvényed. Dehogy nincsen. Az egyes mezők magassága. Célfüggvény nélkül optimalizálásról nem is lehet beszélni, így egy vicc lenne az egész, semmi más.

Azt írod, tetszőleged módon lehet inicializálni a szépmezőt. Felmerül a kérdés, hogy akkor miért nem random bemenetet használtok mindig? Illetve írod, hogy biztosítani kell minden figura minden szintjének szereplését a bemeneti szépmezőben? Ez miért fontos az algoritumus lefutása szempontjából? Ha ez szükséges az algoritmushoz, miért írod, hogy tetszőleges lehet a bemenet?

Kíváncsian várom a fejleményeket, valamint az eddigi kérdéseimre a választ. Azt hiszem, az eddigi leírásod alapján csak részben lehet formalizálni az algoritmust Természetesen az egzaktság viszont szükséges, hogy a valódi használhatóságát és esetleges tulajdonságait bizonyítani tudjuk. Bizonyított működés nélkül viszont egy algoritmus sokat nem ér tudományos szempontból, legfeljebb egy bizonyos szabályok szerinti próbálgatásról lehet beszélni, nem algoritmusról.

Bizonyított működés nélkül viszont egy algoritmus sokat nem ér tudományos szempontból, legfeljebb egy bizonyos szabályok szerinti próbálgatásról lehet beszélni, nem algoritmusról.

Ez így nem teljesen igaz, ld. pl. GA, Neural networks.. Az algoritmust pedig egészen biztos, hogy le lehet írni formálisan, vizsgálni viszont már valószínűleg nem olyan egyszerű.

Ha már szóba került:

Genetikus Algoritmus. Ez volt a kiinduló probléma. Egyrészt nem tudták reprodukálni a működést, másrészt időnként elakadt egy áloptimumba. Az okokat ne kérdezzétek, nem tudom. A G.A. és a HRS összehasonlítása ebben a cikkben történt:

http://www.meditor.hu/IHRS/HRSvsGA.pdf

Neurális hálók. Az ember kiváncsi lény, így szeretné tudni azt is, hogy milyen adatai keletkeznének azokon a helyeken, ahol tényleges mérés nem történt. Általában két predikciós eljárást használunk. Az egyik az ANN (mesterséges neuronhálok), a másik a Zorax kristályok. Az utóbbi nem publikált, az ANN-nel való együttműködésről az egyik publikáció ez:

http://www.meditor.hu/IHRS/HRSandANN.pdf

Egy válasz a egy kérdésre. A bázisvetületben mérésre kijelölt egyedek meghatározásánál azért igyekszünk minden figura minden állapotából legalább egyet bevonni, mert ellenkező esetben előfodulhat az, hogy az optimum felé lépkedés során lesz olyan állapot, amely egyszer sem szerepel. Ez pedig a predikciós eljárások pontosságát rontja. (A jóslásnál nem áll rendelkezésre az összes figura terjedelme - leglábbis, határozott egyed formájában.)

> Sol omnibus lucet.

Ez csak részben válasz a kérdésemre. A kérdés lényege: ez a fajta kezdeti szépmező kiválasztás az algoritmus lefutásának szempontjából miért fontos? Mi történne az algoritmussal, ha nem így határoznám meg a bemeneti szépmezőt? Megtalálná így is az optimumot? Elkerülné? Az alapján, hogy tetszőlegesen inicializálható a kezdeti szépmező (ezt írtad), azt gondolja az ember, hogy a kezdeti szépmező nincs befolyással az algoritmus eredményességére, azaz akármilyen a bemenet, az algoritmus akkor is megtalálja az optimumot, legfeljebb több lépésben.

Ha viszont az algoritmus szempontjából szüksges, hogy minden figura minden állapota legalább egyszer szerepeljen, akkor a kérdésem: az algoritmus ezt hol használja ki? Miért szükséges ez? Az, hogy előfordulhat, hogy az optimum felé lépkedés során lesz olyan állapot, amely egyszer sem szerepel, az nem érdekes az optimalizáció célja szempontjából, hiszen a lényeg, hogy az algoritmus találja meg az optimumot. Hogy ezt hogyan teszi (kimarad ey figura egy állapota, vagy nem), az nem érdekes.

III. A vetületek képzése.

(1) A bázisvetület képzése véletlen. Más szavakkal: a figurák kiindulási sorrendje tetszőleges.

(2) Ha a bázisvetületet tekintjük a 0. vetületnek (BV=V0),
akkor a páratlan sorszámú vetületket (V1, V3, V5...)
így képzem:

V0: F0=P0, F1=P1, F2=P2, F3=P3 ... Fn=Pn
V1: F0=Pn, F1=P0, F2=P1, F3=P2 ... Fn=P(n-1)
(vagyis ez egy rotáció az összes figurára)

(3) A páros sorszámú vetületeket így képzem:
V1: F0=Pn, F1=P0, F2=P1, F3=P2 ... Fn=P(n-1)
V2: F0=P(n-1) F1=P0, F2=Pn, F3=P1 ... Fn=P(n-2)
(vagyis ez egy olyan rotáció, amely a P0-ban
lévő figura kivételével az összes többit érinti)

Megjegyzés: tudom, ez a vetületképzés önkényes. A lényege az lenne, hogy a figurák pozíciójának megváltoztatásán kivül a figurák egymáshoz képesti sorrendjét is megváltoztassuk. Lehet, hogy van ennél hatékonyabb eljárás erre.

> Sol omnibus lucet.

IV. Rendezés és néhány új fogalom

A határozott egyedeket magasságuk szerint sorba állítjuk. Az optimumkritériumnak leginkább megfelelő egyed (általában a legkisebb vagy a legnagyobb) a KIRÁLY. Rendszerint megjelölünk még további egyyedeket is a királyon kívül. Ezek a TISZTek. A tisztek ugyan nem magasabbak (alacsonyabbak) a királynál, de magasabbak (alacsonyabbak) a többieknél (GYALOGOK). A tisztek rangját jelölhetjük, a továbbiakban hasznos lehet:

T0=király, T1, T2, T3...

A továbbiakban általában 3-5 tiszttel dolgozunk. Számukat a mérési kapacitás határozza meg: több tiszt --> nagyobb szépmező.

A tisztek körül a vetületben elhelyezkedő határozott és határozatlan egyedeket HÁZnak nevezzük. A ház alakja (többnyire) négyzet, amelynek középpontjában a tiszt áll. A ház méretét a tiszt rangja adja meg, legnagyobb háza a királynak van. A házak mérete szabadon paraméterezhető.

Az összes tiszt által birtokolt határozatlan egyedek halmazát GENERÁCIÓnak nevezzük. Sorszámozásuk együtt halad a vetületképzéssel (G0 = kiinduló szépmező, bázisvetület, G1, G2, stb.)

> Sol omnibus lucet.

Kérdés: ezen a képen: http://www.meditor.hu/pic/step_01.gif a két tengely miért van azonosan színezve?
Ha hat figura van, akkor miért nem jelölitek több színnel? A hat figura (melyek: függőleges kék, 2 szint, f. sárga, 4 szint, f. fehér, 3 szint, vízszintes kék, 2 szint, v. sárga, 3 szint, v. fehér, 4 szint) összes lehetséges kombinációja: 2*4*3*2*3*4 = 576. Ezek szerepelnek a táblázatban.

A linkelt kép alapján csináltam egy ábrát, itt van: http://developers.mik.uni-pannon.hu/~persicsb/hrs/hrs_step.png

Itt bejelöltem egy mezőt pirossal. Az egyértelműség kedvéért vezessük be az alábbi jelölést:

A szintek értéketi jelöljük az 0..szintszám-1 értékekkel, és minden mezőt azonosítsunk egy rendezett 6-ossal:
x = (x1,x2,x3,x4,x5,x6). x1 a függőleges kék, x2 a f. sárga, x3 a f. fehér, x4 a vízszintes kék, x5 a v. sárga, x6 a v. fehér figura szint-értéke.
Például a következő a piros mezőt az (1,0,2,0,0,2) azonsítja.
Ennek a mezőnek a szomszédai (olyan mezők, amelyek pontosan egy figura pontosan egy szintjében térnek el tőle):
(0,0,2,0,0,2), (1,1,2,0,0,2). (1,0,1,0,0,2), (1,0,2,1,0,2). (1,0,2,0,1,2), (1,0,2,0,0,1) és (1,0,2,0,0,3). Ez összesen 7 mező, őket az ábrán zölddel bejelöltem. Kérdés: egy-egy lépésben a házak ezekre a mezőkre (amely a tiszttől nincsenek "messze"), miért nem terjednek ki? A publikációkban nem láttam sehol, hogy az összes házon belüli mező számításba vettétek volna. Csak négy mezőt vizsgáltok 1-1 távolságra.

Ezt meg tudnád indokolni? Ha nem veszitek figyelembe az összes szomszédos mezőt, hogyan működik az algoritmus?

(1)
A tisztek körül a vetületben elhelyezkedő határozott és határozatlan egyedeket HÁZnak nevezzük. A ház alakja (többnyire) négyzet, amelynek középpontjában a tiszt áll. A ház méretét a tiszt rangja adja meg, legnagyobb háza a királynak van. A házak mérete szabadon paraméterezhető.

(2)
http://www.meditor.hu/IHRS/cattoday.pdf

Lehet, hogy az (1) szerinti megfogalmazás nem teljesen egyértelmű. A pontosítás érdekében ajánlom a (2) szerinti publikáció 4-es és 5-ös ábrasorozatát. Tehát egy generáció NEM csak a tisztek legközelebbi rokonaiból áll, hanem akár 6-8 távolságnyira.

A vektorok színétől a kifogásolt ábrán vonatkoztassunk el, nincs jelentősge. Valóban célszerűbb lenne különböző színekkel ábrázolni őket.

> Sol omnibus lucet.

Nem a generaciokkal van a baj, hanem a generacioba bekerulo, uj merendo egyedek kivalasztasaval. A (2) publikacio 4-es abrasorozatanak a c) abraja a bajos. Itt az latszik, hogy figyelembe vesztek olyan elemeket, amelyek a megjelolt tiszttol 1 ertek tavolsagra vannak valamely figura szerint. Azonban nem az osszes figura szerinti 1-tavolsagra levo elemeket nezitek at. Tehat meg egyszer, talan igy jobban ertheto:
emlitetted, hogy a Tejfalussy-elrendezes azert jo, mert igy egy mezo korul olyanok vannak, amelyek bizonyos valtozok szerint csak 1-1 egysegben ternek el. Azonban: az egyed mellett az adott elrendezesben nem minden, a tiszttol 1 tavolsagra levo egyed talalhato meg. A Tejfalussy-elrendezes ponthogy bizonyos valtozok szerint 1 tavol levo egyedeket az abran jo messze rak egymastol, lasd a linkelt kepet, amit rajzoltam.

A hivatkozott publikacioban az latszik, hogy a tiszttol elmesz ugyan 3-3-nyi tavolsagra, azonban nem vizsgalsz minden 3-tavolsagra levo egyedet, csak bizonyos valtozok szerinti 3-tavolsagra levo egyedet. Es ez baj. Amig egy tiszt teljes kornyezetet (minden iranyban) vegig nem vizsgalod, addig nem tudhatod, el kell-e indulnod masfele.

Masreszt annak az indoklasat sehol nem latom, hogy az algoritmus kihasznalja-e vagy nem a kezdeti szepmezo kivalasztasanal azt, hogy minden figura minden szintje legalabb egy egyedben szerepeljen. Ez nem latom miert fontos, ha fontos. Mi van akkor, ha teljesen veletlenszeru a kivalsztas? Az algoritmus igy is megtalalja az optimumot?

Nem latom annak indokat, hogy a meg nem mert mezokon miert nem lehet a globalis optimum erteke (az algoritmusotok szerint ahol nem kell merni, ott nem is lehet optimum). Erre kernek magyarazatot.

Nézzük a tisztek körüli környezet változását.

Azt jól látod, hogy a ház kialakításakor nem veszünk figyelembe minden olyan egyedet, amely adott távolságra van a tiszttől, de
ez nem jelenti azt, hogy ezek a nem figyelembe vett egyedek soha nem is válhatnak határozottá.

Ha ugyanis a tisztikarban változás áll be, akkor más helyre kerül a 'súlypont', más egyed alapít házat, ha nem, akkor a következő vetületben olyan egyedek kerülnek látókörbe, amelyek adott távolságra vannak, de eddig nem lettek megmérve. (Ezzel összességében a mérési igényt csökkentjük - lám ez mindig visszatérő motívum!)

> Sol omnibus lucet.

V Haladás az optimum felé.

Az optimum felé a következő lépésekkel haladunk.

(0) A megjelölt (G0, vagy házban lévő) határozatlan egyedek magasságát megmérjük.
(1) képezzük a következő vetületet.
(2) Az aktuális szépmezőt sorbarendezzük.
(3) kiválasztjuk a tiszteket.
(4) A tisztek házat alapítanak.
(5a) Ha egyetlen tiszt házába sincs határozatlan egyed, akkor megállunk.
(5b) Ha bármely tiszt házában van határozatlan egyed, akkor --> (0)

> Sol omnibus lucet.

:-)))

Hát, mondjuk azt én se értem, hogy miért nem lehet itt közönséges matematikai kifejezéseket használni. Teszem azt MAGASSÁG ---> helyettesítési érték. Meg a többi...

Meg kell mondjam, tisztelem persicsb átlátóképességét, hogy képes ezen a nyelven is kommunikálni. :-)

---
Science for fun...

Persze, csak ha ragaszkodunk a közismert fogalmakhoz, akkor egyszerűbb követni, hogy mi történik. Ez a lovagos-királyos algoritmus tényleg kicsit olyan, mintha egy busman mesélne el neked egy közlekedési balesetet. Szóval teljesen meg tudom érteni NagyZ "gyermeki rácsodálkozását", ezért is szóltam hozzá. :-)))

---
Science for fun...

hnnn...

nos amennyit sikerült kihámoznom ebből a az egészből, megpróbálom megfogalmazni a tiszta matematika nyelvén, lehetőleg egy mondatban, hogy mindenki számára világos és érthető legyen:

ez a cucc egy valamiből(valamikből) egy csomó másik valamiket csinál valamilyen tetszőlegesen (önkényesen) kiválasztott módszer illetve módszerek szerint azzal a sok kis előre beállított valamivel - ezek szintén lehetnek valamilyen módon generáltak vagy önkényesen választottak - amik csinálnak valamit a beérkező valamiből(valamikből) illetve egymással, aztán ezt az egészet képes legyen egy valamilyen grafikus ábrázolási módszer szerint ábrázolni, - mert az valamennyire mindig érdekeseb mint pusztán a számok - valamint hogy a megszülető végeredmény hasonlítson arra a véges vagy véhtelen számú valamire amire egyáltalán nem mertünk gondolni, hogy ezt a betáplált valamiből valaha is ki lehet hozni.

No rainbow, no sugar

:):):)
Ne nezzuk le a HRS-t. Lehet, hogy hasznos, de ezt egyelore ketlem. Az teny, hogy eddigi informacioink alapjan:
1) globalis optimalizalasra nehezen, vagy egyaltalan nem hasznalhato (nem latom annak indoklasat, hogy a meg nem mert mezok kozott miert nem lehet a globalis optimum)
2) nincs egzakttul megfogalmazva, igy nehezen reprodukalhato, azaz nehezen ellenorizheto a mukodese
3) lokalis optimum megtalalasara ugy nez ki, hogy hasznalhato, de ez sokat nem er. Lokalis optimumok megtalalasara nagyszeru determinisztuikus modszerek vannak
4) Zavaros a fogalomrendszere

Az inícializálással kapcsolatban volt egy kérdés: hogy, ha mindegy hogyan választjuk ki a G0-t miért úgy választjuk ki és ez milyen hatással van a futásra.

Csináltam 2 próbát.

(A) próba - 8 figurás mező, valós(mért) határozott egyedekből álló szépmező, és a vakmező predikciós eljárással feltöltve.

Adat (HRS/random inícializálás)
G0 generáció mérete: 38/38
A szépmező mérete a keresés után: 953/1247
Leállás: G33/G36 után
A király személye nem változik: G8/G12 után

(B) próba - 12 figurás mező szimulált adatokkal
Adat (HRS/random inícializálás)
G0 generáció mérete: 32/32
A szépmező mérete a keresés után: 2081/3106
Leállás: G31/G36 után
A király személye nem változik: G6/G17 után

Ebből az látszik, hogy:
(1) - a király személye ígyis úgyis kiderül.
(2) - a random inícializálás esetén később, és több méréssel.

Mielőtt valaki azt mondaná: 2 próba nem próba, akkor azoknak azt üzenem, ha itt 50 próba lenne, akkor mind az ötven estben ez az eredmény jönne ki.

Van egy harmadik inícializálási módszer, amikor is behatároljuk a G0 méretét és úgy választjuk ki a hozzátartozó egyedeket, hogy azok a legmagasabb diverzitást eredményezzék. Ezt pillanatnyilag nem használjuk, viszont az a meglátásom, hogy megfelelően nagy G0 esetén ez semmiben nem különbözik a random inícializálástól.

> Sol omnibus lucet.

No, azért a gyakorlatban ennyire nem rossz a helyzet. Általában lehet tudni, hogy egy optimalizálandó (mondjuk kémiai) rendszer hogyan szokott viselkedni, tehát szó nincs arról, hogy sötétben kellene tapogatózni.

Ha meg mégis adódik a kísérletek során valami meglepő, akkor azt le lehet reagálni. Ha mondjuk van egy katalizátorod, ami világ életében sárga volt és porszerű, aztán a HRS utasításai alapján tekergetve a paramétereket egyszer csak azt látod, hogy a színe vörösre változott, kimászott a lombikból, leugrott sörért és randira hívta a barátnődet, akkor biztos lehetsz benne, hogy valami különleges történt, amit a továbbiakban nem numerikusan kell kezelni. :-)

---
Science for fun...

Amikor találunk egy optimumot, akkor sohasem magát a konkrét egyedet és az ahhoz tartózó figurák állapotát kell nézni! A határozatlan és a határozott egyedek ugyanis szigetekbe tömörülnek. (Tehát optimum és pesszimum centrumok alakulnak ki) Nagyon érdekes, hogy a kísérleti zaj növelésével (ez a zaj lehet akár a jel többszöröse is!!) az optimumcentrumok helye nem nagyon változik, sőt a határozott egyedek száma sem nő jelentősen.

Ez nagyjából összecseng imp megállapításával: "Ha a globális optimumhely elég nagy környezete utal az optimumhelyre, az elég lehet..."

> Sol omnibus lucet.

"hogy a kísérleti zaj növelésével (ez a zaj lehet akár a jel többszöröse is!!)"

Egyrészt mi az a "kísérleti zaj" (mérés pontatlansága?), másrészt meg attól tartok, hogy ha egy mérésnél a zaj a jel többszöröse, akkor ott már nem numerikus zsonglőrködésre van szükség, hanem a mérési módszer tökéletesítésére.

---
Science for fun...

"Mielőtt valaki azt mondaná: 2 próba nem próba, akkor azoknak azt üzenem, ha itt 50 próba lenne, akkor mind az ötven estben ez az eredmény jönne ki."

Ezzel sajnos tényleg az a gond, hogy a próbálgatás semmilyen körülmények között nem helyettesíti a bizonyítást. Szóval ez nem érv. Azt talán lehetne mondani, hogy az eddig vizsgált gyakorlati problémák esetében a függvény (MAGASSÁG függése a FIGURÁKtól) minden esetben elég sima volt ahhoz, hogy az algoritmus ne hasaljon el rajta, de ez tényleg nem bizonyítja az általános alkalmazhatóságot.

---
Science for fun...

Nem olvastam a cikkeket, de azt hiszem abban nem kell kételkedni, hogy eddig működött. Természettudományos problémánál vannak ugyanis egyéb információk, amelyek bizonyossá teszik a találatot. Például egy katalizátor esetében ha sikerült eltalálni azt a paraméteregyüttest, amely mellett mondjuk 98% a konverzó, akkor nyugodtak lehetünk, hogy győztünk. Vagy azt is lehet mondani, hogy lehet ugyan valahol egy másik pont is, ahol 98,3% ez az érték, de az ezek után kit érdekel. :-)

---
Science for fun...

Attol meg az algoritmus nem lesz altalanosan hasznalhato, hogy katalizatoroka jo kozelitessel mukodott. meditor az elozo cikkekben azt allitotta, ez egy altalanosan hasznalhato algoritmus. Ezert voltam ra kivancsi. Mert mi is optimalizalassal foglalkozunk. Az egeszoptimalizalas NP-teljes feladat altalaban, minden uj algoritmus, amely valoban mukodik is, nagy eredmeny. Ezert vagyok nagyon kivancsi a HRS-re. De mint kiderul, korantsem olyan eros, hasznalhato a rendszer, mint azt allitottak.

A 0,3% is sokakat erdekelhet optimalizalasban. Az USA energiafelhasznalasanak nagy resze nagy vegyipari uzeek huto/futo berendezeseiben megy el. Itt 0,3%-os optimalizalas mar eves szinten tobbtizmillard dollart er.

A példát NEM a globális optimum megtalálására hoztam, hanem annek bemutatására, hogy egyrészt az optimum megtalálásának ténye nem igan függ a kiinduló szépmezőtől (G0), ugyanakkor a lefutása függhet tőle és ennek gyakorlati jelentősége van, mikor egy mérés költség magas.

> Sol omnibus lucet.

Nagyon lényeges elem, és egy kicsit elsikkadt a következő:

Amikor egy HRS ciklus lezajlik nem elégszel meg az eredménnyel: A figurák terjedelmét csökkentve újra indítjuk az egész rendszert. A terjedelem csökkentésekor úgy jársz el, hogy az optimumot megpróbálod fókuszban tartani. (Ebből látszik csak igazán, hogy valójában nem egy konkrét egyeddel dolgozol, hanem egy szigettel)

Ez egy lépés - ha kicsi is - a folytonosság fel. Kínai kollégák tanulmányozták a kérdést, megkeresem a cikket.

> Sol omnibus lucet.

Az ezzel foglalkozó kínai cikkek egyikének abstractja:

Holographic research strategy (HRS) is a novel determinate optimization method. The principle of HRS is based on a special, two-dimensional presentation of a multidimensional space. This presentation was termed two-dimensional hologram. HRS translated the optimization operation in multidimensional space into finding better points in the neighborhood around the current best data points. In this way, HRS can find the global optimal parameters in all probability. However, HRS can't be applied to optimize continuous variables, it was only used in optimizing discrete systems. Therefore, it is necessary of improving HRS and ensuring the optimization algorithm can being applied in multidimensional continuous systems. Modified holographic research strategy (MHRS) was designed for the purpose. MHRS changed continuous variables into discrete variables in the searching region firstly, and then found the optimum in the discrete system. In order to reduce the deviation between the continuous system and the discrete system, MHRS adopted iterative algorithm to shrink the searching region gradually according to the location of the current optimal value. Furthermore, in order to improve the efficiency of HRS in searching for the global optimum, random mutation operator was added to the optimizing process. Ten-dimensional Rastrigin function was applied to testing MHRS, the results demonstrated that its global optimization performance is superior to one of eugenic evolution genetic algorithm (EGA). Further, MHRS was applied to estimate the kinetic model parameters of residue hydrofining. Satisfactory results were obtained.

> Sol omnibus lucet.

Itt egy másik, ugyanzoktól (itt iterativ HRS-nek nevezik a dolgot)

Holographic research strategy (HRS) is a determinate optimization method with high efficiency in searching for the global optimum. However, HRS can't be applied to optimize continuous variables, it can only be used in optimizing discrete systems. Therefore, it is necessary to improve HRS and to ensure the optimization algorithm can be applied in multidimensional continuous systems. A novel optimization algorithm named as iterative holographic research strategy (IHRS) was designed for these purposes. IHRS changes continuous variables into discrete variables in the searching region firstly, and then finds the optimum in the discrete system. In order to reduce the deviation between the continuous system and the discrete system, IHRS adopts iterative algorithm to shrink the searching region gradually according to the location of the current optimal value. The influence of several important parameters of IHRS, including the number of the region being partitioned averagely, the shrinking factor of the searching region and the individual amount of a cluster, on the optimization efficiency of IHRS was discussed. Six-dimensional Alpine function was applied to testing IHRS, the results demonstrate that its global optimization performance is superior to those of genetic algorithm (GA) and simplex method. Further, IHRS was applied to estimate the kinetic model parameters of SO2 catalytic oxidation, and satisfactory results were obtained.

> Sol omnibus lucet.

Bocs, hogy csak most reagalok, de hetvegen nethozzaferes nelkuli helyen voltam.

Naszoval: kernem annak a *bizonyitasat*, hogy a HRS altal adott megoldas valoban a globalis optimum. Nem latom, az algoritmus miert talalja meg a globalis optimumot. A globalis optimumkereses egeszoptimalizalasban fontos, hiszen itt egy lokalis optimum jo messze lehet a globalistol, hiszen nem folytonos a ter, diszkret ertekek vannak. Kerlek, kozold annak a bizonyitasat, hogy az algoritmus valoban megtalalja a globalis optimumot. Nem tudom, ti mibol gondoljatok ezt.

Nem, nem derul ki az sem, hogy 1. milyen tipusu celfiggveny eseten talalja meg az optimumot (ugyanis addig, amig nem tudod a celfuggvenyt nem empirikusan, hanem analitikusan megadni, addig nem tudod, milyen a celfuggveny szerkezete, 2. Az algoritmus leirasabol nem derul ki sehol, nincs bizonyitva, hogy az altaluk hasznalt specialis celfuggvenyen (melynek szerkezeterol semmit nem tudunk) az algoritmus kimenete valoban a vizsgalt teren globalis optimum lesz, nem pedig csak egy lokalis optimum. Ez sehol nincs bizonyitva. Nemhogy az altalanos, de a specifikus celfuggveny eseten sem.

A spidron.hu-n lévő Spidron rendszert ismeritek?
Én nem vagyok szakértője a témának, de úgy vélem, lehet sok köze ;O)

érdemes angolul is beütni a spidront - kiad egy csomó releváns szakmai publikációt..

subscribe

/mazursky

Love your job but never love your company!
Because you never know when your company stops loving you!

Szerintem felesleges volt feliratkoznod. Azt hiszem, a topic kifulladt, a legtobben felismertuk,hogy bizony ez a modszer arra, amire elvileg szanva van (egeszerteku problemak gobalis optimalizalasa) jelen formajaban hasznalhatatlan es az alapelvei annyira hibasak, hogy alapveto modositasok nelkul arra, amire szanva van az algoritmus, soha nem is lesz hasznalhato.

Szerintem nem teljesen sportszerű mást lebeszélni arról, hogy
kipróbálja a HRS-t, még akkor is, ha sok tekintetben igazatok
van. Az élet sokkal összetettebb annál, mintsem egy konkrét
matematikai bizonyiték hiánya vagy lehetetlensége döntően
befolyásolná pró vagy kontra. Nem tudhatod, hogy mazursky-nak
nem pont egy olyan problémája van-e, amire jó a HRS?

Azt kijelenteni talán túlzás, hogy a HRS semmire sem jó!
Márpedig valakit lebeszélni a használatáról úgy, hogy a konkrét
helyzetet nem ismered - nos ez szerintem nem igazán szerencsés.
Sőt, a helyedben én benyomtam volna ide egy függvényt azzal,
hogy "na, ennek az optimumát találd meg öcsi, aztán hadoválj"
vagy valami ilyesmit léptem volna.

Szerintem azokban a feladatokban, amelyekben a genetikus
algoritmusnak létjogosultsága van, ott mindenképpen használható
a HRS. Nem tudjuk azonban, hogy még hol, illetve milyen
korlátjai vannak.

Eddig a szimulációkon kívül jellemzően 3 területen tudok arról,
hogy kipróbálták a HRS-t. Mindegyik esetben a leggyorsabb és
leghatékonyabb módszernek bizonyult, a kimeneteket az mérési
hibán belül az elméleti határra tette le.

Készséggel elismerem, hogy a HRS tartalmaz önkényes elemeket.
Ilyen a bázisvetület meghatározása, a vetületképzés, a G0
mérete, a figurák terjedelme, és konkrét állapotuk, a
keresőablakok száma, mérete. Éppen az lenne az egyik feladat,
hogy ezeket az önkényességeket miként lehet csökkenteni,
vizsgálni: van-e egyáltalán jelentőségük.

Ha azt mondjátok, hogy az algoritmus egy mohó hegymászó,
és azokra ez meg ez jellemző, vagy azt, hogy ez a G.A.-nak
az a változata, ahol a pontmutáció nem megengedett és
a szülőpárok kiválasztása nem tetszőleges egy megadott
fitness fölött sem, akkor ez oké. Ennek mentén tudnék
gondolkodni, de azzal, hogy a próba lehetőségét is elveted,
ezzel nem igazán tudok mit kezdeni.

Akkor StrangeLove dokinak is egy megjegyzés: amikor látsz
egy publikációt, úgye nem gondolod azt, hogy egy abban leírt
szám mögött nincsenek KONKRÉT mérések, esetleg mérések százai,
ezrei? Ezt csak a jegyzőkönyvek hiánya miatt említett
mérnöki_szemlélet_nélküliség véglényszinvonalával kapcsolatban
hozom fel.

> Sol omnibus lucet.

"Nem tudhatod, hogy mazursky-nak
nem pont egy olyan problémája van-e, amire jó a HRS? "
Mondj olyan módszert, amellyel eldönthető, hogy mely problémákra alkalmazható a HRS. Sajnos az, hogy ki kell próbálni, hogy működik-e , nem járható út mondjuk abban az esetben, ahol a mérések elvégzése nagyon költséges.
Az a helyzet, hogy nem lehet tudni, hogy a HRS által adott érték valóban globális optimum-e.

"Szerintem azokban a feladatokban, amelyekben a genetikus
algoritmusnak létjogosultsága van, ott mindenképpen használható
a HRS."
No, ezt mi alapján mondod?

"Eddig a szimulációkon kívül jellemzően 3 területen tudok arról,
hogy kipróbálták a HRS-t. Mindegyik esetben a leggyorsabb és
leghatékonyabb módszernek bizonyult, a kimeneteket az mérési
hibán belül az elméleti határra tette le."
Ez rendben is van, nagyon szép eredmény. Viszont következik a fenti mondatodból az is, hogy abban az esetben, amikor nincs ilyen, hogy elméleti határ (pont ezt a határt keresed), akkor a módszer hasznosságáról nem lehet beszélni, mivel nem tudható, hogy amit kimenetként kiadott, az valóban a globális optimum-e, vagy nem. Valamint kérdés még, hogy abban az esetben, amikor több globális optimum van (a te fogalomrendszereddel élve több olyan határozott egyed van, amelynek magassága az optimális), akkor nem adja meg az összes ilyen elemet. Azonban ez fontos lehet, hiszen az egyes megoldások megvalósítási költsége más, így lehet olyen megoldás, amelyet alkalmazni olcsóbb, mint egy másik, viszont az optimalitzálási szempontból megegyeznek. A valóságban sokszor nem tudod, mi a probléma elméleti határa. Mondok egy tipikus példát, amivel nálunk a PE-n foglalkozunk. Adott egy gyártó üzem, amelynek működése szakaszos. A működést gráffal reprezentáljuk. Feladat megadni azt az optimális ütemezést, amelynek segítségével az adott termékmennyiség a lehető legrövidebb idő alatt legyártható. Ez egy tipikusan egészoptimalizálási probléma. Itt a problémák esetében nem ismert, hogy mi az elméleti határ a legrövidebb időre, hiszen az összes előforduló lehetőség közül sok olyan van, amely az adott feltételek mellett nem megvalósítható megoldást jelent. Legfeljebb becsléseket lehet adni, azonban a legtöbb esetben ezek a becslések a feladat szerkezete miatt nem elég élesek. Ebben az esetben tehát nem alkalmazható a HRS, hiszen nem tudom, hogy amit kimenetként kiad, mennyire jó megoldás. Így azt sem tudom, hogy meg kell-e állnom az algoritmussal, vagy nem.

"Sőt, a helyedben én benyomtam volna ide egy függvényt azzal,
hogy "na, ennek az optimumát találd meg öcsi, aztán hadoválj"
vagy valami ilyesmit léptem volna."

Nos, akkor legyen! Adott a következő probléma: Legyen T és E,P három véges halmaz, T taszkokat, E műveleti egységeket, P termékeket jelöl. Legyen adott a p: T->P(E) függvény, amely megadja, hogy mely taszk mely műveleti egységekkel hajtható végre. (P(E) itt az E halmaz hatványhalmazát jelenti). Természetesen minden x eleme T esetén p(x) nemüres halmaz.
Legyen adott a w:TxE->R függvény, amely megadja, hogy az adott taszk elvégzése az adott műveleti egységgel mennyi ideig tart.
Legyen adott az n:T->P(T u P) függvény, amely megadja, hogy a végrehajtás során mely taszkot mely taszkok követnek közvetlenül. (ez a leírás egy irányított körmentes gráffal is megadható).
Természetesen minden x eleme P esetén p(x) üres halmaz ( a termékeket már nem kell végrehajtani semmivel).
A leírás megkönnyítése céljából legyen p:(T u P)->P(T) ennek fordítottja (nem inverze n-nek), amely megadja, hogy a végrehajtás során egy taszkot vagy terméket mely taszkok előznek meg közvetlenül.
Nevezzük allokációs függvényeknek azokat a T->E típusú függvényeket (jelülje összességüket A), amelyekre igaz az, hogy minden a eleme A és minden x eleme T esetén a(x) eleme p(x)-nek (azaz gyakorlatilag egy taszkhoz csak olyan műveleti egységet rendelek hozzá, amellyel végre is hajtható).

Legyen a eleme A esetén az allokációs függvényhez tartozó végrehajtási idő függvény t (t típusa Ax(T u P)->R+0). t megadja, hogy az adott allokáció esetén 1-1 taszk mikor kezdődik el.
t-re teljesülnie kell annak, hogy minden x eleme T u P esetén t(x) >= max(t(y) + w(y,a(y):{y eleme p(x)}), azaz egy taszk nem kezdődhet el, illetve termék nem készülhet el hamarabb, mint ahogyan az őt megelőző taszkok befejeződtek. Amennyiben ilyen t nem létezik, akkor a-t nem megengedett allokációnak nevezzük (tipikusan ilyenek a 22-es csapdája: egy taszk arra várna, hogy egy rá következő taszk befejeződjön). Természetesen egy-egy allokációhoz végtelen sok lehetséges t függvény létezik, azonban ezek között van olyan, amely a legrövidebb végrehajtást valósítja meg, azaz egy taszk azonnal elkezdődik, amint lehetséges.

Feladatunk olyan megengedett allokációt és végrehajtási idő függvényt adni, amely esetén a max(t(y):y eleme P) minimális, azaz gyakorlati értelemben olyan ütemezést és az ütemezéshez tartozó műveleti egység-taszk hozzárendelést adni, amely a megadott termékeket a lehető legrövidebb idő alatt legyártja.

Ilyen biztosan létezik, hiszen véges sok allokáció lehet csak, mert T és E mérete (ezért P(E), tehát végsősoron A mérete is) véges.

Adok is rögtön egy feladatot, próbáld meg megoldani HRS-sel:
T = {T1,T2,T3,T4,T5,T6,T7,T8,T9,T10,T11}
E = {E1,E2,E3,E4,E5)
P = {A,B,C,D}
A p függvény:

p(T1) = {E1,E2}
p(T2) = {E3}
p(T3) = {E2,E5}
p(T4) = {E4}
p(T5) = {E3,E4}
p(T6) = {E1,E2,E3}
p(T7) = {E2,E3}
p(T8) = {E4,E5}
p(T9) = {E3}
p(T10) = {E1,E3}
p(T11) = {E4,E5}

A w függvény:
w(T1,E1) = 6
w(T1,E2) = 8
w(T2,E3) = 9
w(T3,E2) = 7
w(T3,E5) = 7
w(T4,E4) = 10
w(T5,E3) = 15
w(T5,E4) = 12
w(T6,E1) = 10
w(T6,E2) = 17
w(T6,E3) = 13
w(T7,E2) = 6
w(T7,E3) = 10
w(T8,E4) = 12
w(T8,E5) = 16
w(T9,E3) = 8
w(T10,E1) = 9
w(T10,E3) = 8
w(T11,E4) = 18
w(T11,E5) = 16

Az n függvény:
n(T1) = {T2}
n(T2) = {T3}
n(T3) = {A}
n(T4) = {T5}
n(T5) = {T6}
n(T6) = {B}
n(T7) = {T8}
n(T8) = {C}
n(T9) = {T10}
n(T10) = {T11}
n(T11) = {D}
Ebből p kiszámolható, nem írom le.

Jó munkát!

Ha nem sikerült magadban lefordítani a HRS fogalmaira a dolgot (pedig rendes egészoptimalizációs probléma, ha pontosan tudom, a halmazlefedésekhez van köze), megteszem ezt helyetted, legalábbis megpóbálom.

Az egyedek, amelyeket keresel, a különféle allokációfüggvények. Azt az allokációfüggvényt keresed, amelyhez tartozó végrehajtási idő függvény legnagyobb értéke (az egyed magassága) a legkisebb.

Az egyes figurák a taszkok, a figurák terjedelmei pedig a taszkot végrehajtó műveleti egységek lesznek.

Egy kis segítségképpen vállakozom arra, hogy ha adsz nekem egy egyedet (mondjuk erre a szálra kommentként), megmondom a magasságát (esetleg végtelent, abban az esetben, ha az adott allokáció nem megvalósítható).

Jó munkát!

Szerk. Bocsánatodat kérem, tényleg nem érhetted a fenti commentet, mert elírtam, két függvényt is, melyek különbözőek, p-vel jelöltem. A második esetben (tehát amikor p-t n fordítottjaként jelöltem), jelöljük b-vel a függvényt. A comment további részei is emiatt szerkesztésere szorulnak, a következő helyekenn:

"t-re teljesülnie kell annak, hogy minden x eleme T u P esetén t(x) >= max(t(y) + w(y,a(y):{y eleme p(x)})" helyesen:
t-re teljesülnie kell annak, hogy minden x eleme T u P esetén t(x) >= max(t(y) + w(y,a(y):{y eleme b(x)})

"p kiszámolható, nem írom le." helyesen: b kiszámolható, nem írom le.

A többi helytálló.

Szerk2. Esetleg adj egy iHRS accountot, hogy magam kipróbáljam.
Szerk3. Tényleg ki szeretném próbálni.

"Akkor StrangeLove dokinak is egy megjegyzés: amikor látsz
egy publikációt, úgye nem gondolod azt, hogy egy abban leírt
szám mögött nincsenek KONKRÉT mérések, esetleg mérések százai,
ezrei? Ezt csak a jegyzőkönyvek hiánya miatt említett
mérnöki_szemlélet_nélküliség véglényszinvonalával kapcsolatban
hozom fel."

[offtopik]
0. "It wouldn't be difficult..." "...Giddap, my Little Boy, giddap!..."

0.5. Breki nem véglény. Kioperált agy nélkül is tud vadászni légyre, párzani (, sőt talán még bányászni is, ha lenne kezében csákány, zsebében sárkány). Szerintem eléggé ügyes redundancia szempontjából a testi felépítése :Đ
[/offtopik]

1. Úgy szokás bevezetni pííjááár (vhááááh) jelleggel vagy még magasabb szinten egy új/spanyolviasz algoritmust, hogy korábban ismert algoritmusokat is implementálva ugyanazokon a modelleken lefuttatjuk, és mégha konkrét modellek nem leközöltek (pl. azért, mert titkos, vagy ismert publikus modellkönyvtáron történtek a próbák), legalább a futási időket publikáljuk. Ilyet sem láttam az általam megtekintett URL-en, azaz konkrét lépésszám/futási időket, pszeudokódot

[SZERK]Összehasonlított futási időket[/SZERK]

[offtopik]
Pl. mostanában is használnak folytonos lineáris programozási feladatok megoldására pivot algoritmusokat (melyek közül minden ismert legrosszabb esetben exponenciális futási idejű) annak ellenére, hogy ismertek pl. ún. belsőpontos eljárások is, melyek elméleti legrosszabb futási ideje polinomiális. Viszont egyéb bonyolultságelméleti és számítástudományi, illetve gyakorlati szempontok alapján kipróbálják és összehasonlítják mind a mai napig a két algoritmusosztályt minden újonnan fölvetődő modellosztálybeli problémákon, és a tapasztalatok alapján döntenek a megfelelő algoritmus élesben történő alkalmazásáról.
[/offtopik]

Szimulált lehűlés, genetikus algoritmusok, véletlent használó ( != sztochasztikus) vagy approximációs algoritmusok tömkelege létezik még különböző, modelledhez hasonlító egészértékű programozási feladatok megoldására.

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

[szerkesztve]

Szerintem nem volt felesleges feliratkoznom, mgha nálam nagyobb matek-zsenik is álltják mindezt. Sok-sok matemaikai módszer van, amik gyerekcipős newbie korszakukban még nagyon viccesnek hatottak, aztán valaki tényleg megmondta a frankót. Ahogyan ez feljebb olvasható volt.
Én kíváncsi vagyok, hogy ez hová vezet, mikor érik meg.

/mazursky

Love your job but never love your company!
Because you never know when your company stops loving you!

Szóval:

http://hup.hu/node/65898#comment-709997

Nem mintha matek-zsenibb lennék, de nem szokás szívatni matematikus körökben a népet azzal, hogy "Nem fért ki a csodás bizonyításom (mérésem) a lap szélére", persze Pierre Fermat megtehette anno.

Megsúgom neked, hogy pl. LP problémák esetén még a bonyolultságelmélet, számítási modellek alapfogalmainak bevezetése előtt voltak ismertek polinomiális legrosszabb futásidejű LP algoritmusok és használták őket még harcászatban is, csak pl. pivot algoritmusok, és más, kevésbé tetszetősebb gyors belsőpontos algoritmusok futásidejének igazolása után évtizedekkel később vették észre (és igazolták) azokról, hogy szintén gyorsak.

ami át van húzva, azt teljesen fölösleges elolvasni. az olyan, mintha ott sem lenne

up, mert kell a nepnek a cirkusz, na.

nagyon meghalt ez a thread, pedig kivancsi lennek persicsb eredmenyeire.