» »

Digitalna evolucija

Digitalna evolucija

««
2 / 29
»»

asPeteR ::

Hm, Thomas cestitam!:)

SAMO, ce prav razumem gre vsa ta svar takole.

1. Napisemo program.
2. Hocemo ga optimizirat
3. Zalaufamo Thomas Miracle;)
4. Program je seda podvrzen bitnim mutacijam. Torej npr. imamo kratek programcek z recimo 100.000 bitov v pomnilniku. Torej to pomeni, da je vseh moznih mutacij kar 2^(10^5)! 8-O 8-O

Samo poglej, kaj pa ce je program daljsi(misljeno v bitih) od teh 100.000 bitov? To pomeni, da EA avtomatsko izloci nekatere mozne kandidate!

Drugace je pa zanimiva naslednja misel, ki se zelo sklada s tem.

Ce imamo na voljo N bitov, ki lahko nad njimi izvedemo M permuntacij lahko s tem opisemo katerikoli program ali algoritem...

Impresivno kaj?

McHusch ::

Zanimivo, res.

Thomas, ampak nekaj meni vseeno ni (še) čisto jasno. Praviš, da program prevedeš v bitni string in ga random bombardiraš z biti. Potem če je dobljeni algoritem hitrejši od začetnega in če da za enak input enak output, privzameš, da deluje.

Kaj pa če recimo nov program na tem primeru in še na desetih dá isti output, pri enajstem (ali pa magari pri milijontem) pa se mu zatakne. Kako preveriš splošno veljavnost, da velja za vse mogoče primere?

Thomas ::

asPeter

> Torej to pomeni, da je vseh moznih mutacij kar 2^(10^5)!

Tako je. Koliko je pa vseh možnih DNA sekvenc "ACTGGCC ..."? Še precej več, vendar evolucija prisopiha do medveda, ker gre po pogorju lokalnih maksimumov.

Če želiš iz Ljubljane priti na Mont Everest, prečkaš le relativno malo dolin, če se držiš visokih vrhov. Nikoli nisi več kot eye sight away od drugega visokega vrha. Če že ne prideš iz Ljubljane, izbereš na slepo še nekaj krajev na svetu - in uspeh je neizbežen.

Če bi pa skočil na slepo s padalom, bi težko zadel ravno Streho sveta.

Pri evoluciji (programov ali bitij) je to samo še neprimerljivo bolj drastično. Tukaj lahko "delamo reči do 10^10^10" v realnem času. To je to.

Evolucija je (zgolj) matematični trik - ki (jasno) deluje!

McHusch

> Kaj pa če recimo nov program na tem primeru in še na desetih dá isti output, pri enajstem (ali pa magari pri milijontem) pa se mu zatakne.

Če je torej program uspel najti mutantsko optimizacijo na prvem inputu, ga preizkusimo še na drugem, tretjem ...

Kaj če deluje na devetidevetdesetih, na stotem pa ne? Pomeni, da smo našli neko posebnost za prvih 99, ki bi avtomatično močno pomagala pri njihovem kompresu. Najbrž (že) bolj, kot je velikost preizkušanega programa. Pomeni, samo našli kompres za randomizirano dato!

Ko je kompleksnost v smislu Kolmogorova (tudi entropija lahko rečemo tej kompleksnosti date) nekajkrat večja od entropije programskega segmenta ki se optimizira - smo varni.

:)
Man muss immer generalisieren - Carl Jacobi

asPeteR ::

Hja, teorija evolucije mi je dokaj jasna (in koncept). Toda, trsi oreh je kako to preliti v programsko kodo.
Pravis, da je treba vedno paziti in hoditi po grabenih do Mt. Everesta ... Toda, kako ves, da hodis po grebenih pri EA?

Tkole po obcutku, se mi zdi FUL neverjetno, da bi z random permutacijo prvotnih bitov dobil optimiziran program oz. algoritem. Preprosto NEVERJETO. Tleke sem nejeverni Tomaz glede tega, definitivno.
(zaradi st. permutacij --jasno je da le manjhno st. permutacij da "normalen" program, ce ga sploh da! --zelo bi si zelel videti delovanje tega programa!:))

No, recimo, da nam rata, da hodimo po grebenih ... Samo, kaj ce zaidemo v slepo ulico? Oz. EA optimizira program, toda nismo se niti slujacno na Mt. Everestu?
Torej iz tega sledi, da ne moremo vedeti kdaj smo on top ...

Aja, pa na tole nisi odgovoril. Kaj ce je "on top" EA optimizacija vecja od st. bitov prvotnega programa? Kajti jasno je da ni nujno da je daljsi program tudi pocasnejsi od krajsega(po st. bitov ki ga zavzameta) prvotnega ...

Thomas ::

> Kaj ce je "on top" EA optimizacija vecja od st. bitov prvotnega programa?

Imamo šestnajstkratno rezervo v bitih. V bitnem stringu, no.


> No, recimo, da nam rata, da hodimo po grebenih ...

Tule sem dolžan pojasnila!

Hoditi ne moreš! Oziroma - vsaj ne prideš zelo daleč.

Bolj gre zadeva (v primeri) takole:

V Ljubljani v random smer in random razdaljo (a njaveč 300 km) izstrelimo raketo. Ta ponese na cilj višinomer in radijski oddajnik. Kjerkoli že pristane, odda podatke kje in kako visoko je pristala. Gremo najverjetneje na najvišjo točko, za eno od desetih raket. "In no time" bomo na Mont Blancu!

Mont Blanc imamo! Od tam spet streljamo, preferenčno v neraziskana območja.

Morda bomo kdaj našli Mont Everest ...

Če dolgo časa ne, nekaj smo že dosegli! Lahko si privoščimo strel v slepo. Če bomo pristali v puščavi Gobi ... je tudi Everest naš!

:)
Man muss immer generalisieren - Carl Jacobi

asPeteR ::

Impresivno, posebej tole z raketami!

Potem sem res narobe razmisljal! S hojo ne prides nikamor.

Moram rect, da je mi je stvar mnogo bolj jasna.

Samo zakaj nisi spodbijal mojega Tomanizma?;)

Bom pa drugace vprasal. Koliko casa povprecno pretece za optimizacijo preko EA povprecnega programa od ene mutacije(uspesne!!!) do druge na povprecnem procesorju? Se da to izracunat?

Thomas ::

> Koliko casa povprecno pretece za optimizacijo preko EA povprecnega programa od ene mutacije(uspesne!!!) do druge na povprecnem procesorju? Se da to izracunat?

Od sekunde, do nekaj ur. Minuto v "povprečju".

Po tisočih mutacijah se program tako spremeni, da ga na videz ni prepoznati.

Tako kažejo izkušnje. Računi (=moje ocene čez palec) kažejo še precej bolje. No, ja - stvar optimizacije! :D
Man muss immer generalisieren - Carl Jacobi

Fury ::

nej bo opensource ;) ;)

dejansko men se zmer ni prevec jasno :) seprav ti nakljucno bite spreminjas? kaksne operacije pa se izvajas na njih? odstranjujes? dodajas? spreminjas string s prestavljanjem skupin bitov, itd.?

cist tko statisticno - koliko od mutacij (%), ti da dejansko valid C kodo? koliko pa dejansko delujoc algoritem (isti rezultati)?

Thomas ::

Delujočih je kakšnih 10% mutiranih kod. Včasih celo 60%, včasih pa samo nekaj procentov. Zelo odvisno od vsebine, se pravi od programskega segmenta, ki ga obdeluje.

Do katerih in kakšnih mutacij prihaja? Najprej do vsakršnih, potem se pa njihovi uspešni tipi shranjujejo v spominu.

:)
Man muss immer generalisieren - Carl Jacobi

Fury ::

hudo.. dej pol vdeli (ce se nisi) da se da pogledat pac kksn info okno kjer ti pise najuspesnejse tipe mutacij pa mal statistike.. to je vedno lepo gledat.. ce se ti da seveda :)

asPeteR ::

Thomas:

10% oz. 60% delujocih kod od cesa?? Od (ce predpostavljamo, da je program dolg 100k bitov) (2^(10^5)) vseh moznih kompleksij jih je lahko kar 60% properly?? To je (2^(10^5))*0.6 dejujocih mutacij ...

Men se to zdi FUL velik!

Ce je tako potem mutanti kar letijo iz racunalnika ...

8-)

Thomas ::

Bitni string, ki se naredi iz C segmenta je tak, da nekoliko spremenjen, rad da nazaj smiselen C program.

Koliko C segmentov ustreza (za dan input) enemu samemu outputu?

Milijarde. Misija se je približati najboljšim.

:)


p.s.

Ja, en graf pa je!
Man muss immer generalisieren - Carl Jacobi

asPeteR ::

->Bitni string, ki se naredi iz C segmenta je tak, da nekoliko spremenjen, rad da nazaj smiselen C program.

Tole bi mene bolj natancno zanimal ...

Oz. cel tale tvoj post se mi zdi ful kljucen za EA. Ker ce res miljarde mutacij ustreza nasemu prvotnemu programu (po I/O) je to izredno!

Sam ne morem si kaj, da bi bil glede tega skepticen. Po kljucu: prevec dobro, da bi bilo res.

Thomas ::

Preizkusni program bi bil lahko že na voljo. Vendar sem še nekaj sitn glede designa in testiranja.

V začetku Junija bo zagotovo!

:)
Man muss immer generalisieren - Carl Jacobi

asPeteR ::

No upam, da se mi bo potem v zacetku junija moj skepticizem razblinil ...

Kaksen je potem user interface tega programa? V konzoli? In kako poteka ta EA z vidika userja? Npr. mamo program test.c, ki ga zelimo optimizirati; potem povemo EA programu kater program zelimo optimizirati in npr. pritisnemo gumb(ali vpisemo v konzolo) "optimiziraj" in EA program nas sproti obvesa o stanju in na outputu EA programa se nam nalagajo optimizirane verzije programam test.c ...

Thomas ::

Ne, ne konzole. Design mora bit na nivoju.

;)
Man muss immer generalisieren - Carl Jacobi

darh ::

eno otroško vprašanje 8-)

Kaj pa če ti tole zmutira v kak stvor, ki naprimer prepiše kak record z informacijami o particijah al pa kej še bolj butastega...?:\
Excuses are useless! Results are priceless!

Thomas ::

xbite,

Če mu boš dal optimizirat nek 3D rotating algoritem, pa ČE bo zaradi neke subrotine (ki mimogrede formatira disk) kaj hitrejši - ti bo formatiral disk.

Arhitektura Critticalla je AFriendly.

Ne bo ti "nalašč" škodoval, vendar če je subcilj glavnega cilja kakršenkoli, bo ta subcilj pač kolateralni učinek.

Na srečo, je taka situacija zaenkrat še malo verjetna. Bo pa vsak dan verjetnejša. Ne samo zaradi tega programa. Zato bo FAI kmalu - eksistencialna nuja!

:)
Man muss immer generalisieren - Carl Jacobi

Alec999 ::

ce si kdo hoce pogledat par znanih sortirnih algoritmov graficno s krogci in primerjat med njmi case si lohka sname
Sortiranje v0.85 tukaj. mal samo reklame 0:)

Drgac pa morm pohvalt Tomasa za zelo uporabn program in dobro zamisel.
Upam, da bo Critticallu uspel izplunt ksn novi supa duba algoritem :D

lp,
Alec999

Zgodovina sprememb…

  • spremenilo: Alec999 ()

Thomas ::

Alec,

Sej skromnost mi komej dovoljuje še enkrat poudart - da nov sortni algoritem - tisti ki sem ga pastal na začetku, je že padel ven. Kar med testiranjem.

- na netu ga ne najdem

- za malo unikatnih ključev je the best od vseh

8-)
Man muss immer generalisieren - Carl Jacobi

romci ::

Thomas, zanimivo bi blo spustit Critticall cez TSP, ki ma za osnovo brute (iz vseh permutacij poti izbere najboljso pot).

Sam kot ideja :)
-- not all those who wander are lost...

Thomas ::

Razmišljam, če bi to šlo kar kot built in demo ...

Ali drugače rečeno - dobra ideja!
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Tole sem (med ostalim) dobil od Paula E. Blacka.




I haven't seen any sort exactly like this. Having tried to develop a program with genetic programming, I am impressed.



Tole stran fura možakar.

Lahko noč.

:)
Man muss immer generalisieren - Carl Jacobi

snow ::

In kaj bo Critticall naslednje optimiziral?
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

Pišemo help in iščemo zadnje ščurke.

Potem bo na strani uporabnikov, da optimizirajo karkoli jim srce poželi.

:)
Man muss immer generalisieren - Carl Jacobi

Alec999 ::

Tomas ce un algoritem se ne obstaja .. ga lohka poimenujes Tomasov algoritem .. pa napises kako deluje :D

asPeteR ::

->Potem bo na strani uporabnikov, da optimizirajo karkoli jim srce poželi.

Potem bo Crittical open source, kakor jaz razumem ... Odlicno.

8-)

Thomas ::

Alec,

Lahko bi ga, ja. To je najmanj kar lahko naredim iz tega. Zato sem ga že tudi pastal sem in tja, da ne bo kakšne pomote za prvenstvo, če bi se že tako odločil.

Vendar bom skoraj zagotovo sklenil le "pobirati slavo" od samega Critticalla in ne toliko njegovih izumov.

Ki jih bodo zdaj "lahko delali vsi".

asPeter,

Ne bo open source. Shareware exe black box 4 Windows bo.

:)
Man muss immer generalisieren - Carl Jacobi

asPeteR ::

Aha, Thomas, razumljivo da bo shareware, cudn se mi je zdel da bi blo open soure, sam vseen skoda da ni!

V enem od zgornjem postov si napisal. Odpravljamo buge ... Pol pa userji bojo optimiziral kar jim srce pozeli ... Sem posledicno hitro sklepal, da se vse nanasa na sam Crittical.

Mea culpa.

0:)

Kostko ::

Ne bo open source. Shareware exe black box 4 Windows bo.
tut kakšna verzija za linux (in druge *nix sisteme) bi bila ql... :)
Human stupidity is not convergent, it has no limit!

Thomas ::

Ja, bo treba portat. Trenutno nimam pojma, kako zahtevno bi to bilo. Če ne prav zelo, potem kmalu.
Man muss immer generalisieren - Carl Jacobi

asPeteR ::

Zaradi takih programov kot je Crittical se kvantni racunalniki se bolj potrebujejo.

Kvantri racunalnik v trenutku nasel najbojso mozno optimizacijo programa.(edini pogoj pri tem je toliko bitov ki zelimo skopmleksirati, toliko "execute enot"(beri: atomov) potrebujemo).

Nepredstavljiva hitrost. V bistvu potem ne bomo potrebovali EA, ker bo na brute force nacin vse postimal. Tko, da takrat Crittacal ne bo potreboval algoritma "za grebene".

8-)

Thomas ::

Ja. Superpozicija mnogih potencialnih rešitev naenkrat - pa gremo!

1000+ qubitni QC bi lahko obdelal celo vrsto 1000 bitnih (nekvantnih)algoritmov naenkrat.

Toda potem postanejo celo optimizacije precej odveč. Oziroma vsaj niso več najpomembnejše, če je QC splošno razširjena zadeva. Vprašanje samo, koliko let od danes naprej? Več kot 5, in manj kot 20. IMHO.

;)
Man muss immer generalisieren - Carl Jacobi

asPeteR ::

Ja to je edini problem QC - trajal bo preden bodo splosno uporabni.

Zato je pa treba posluziti "crnih lukej", da se pride kam.:))

ciki57 ::

Ideja: mogoče bi lahko naredil tudi Critticall@home podobno kot SETI...

blabla ::

Thomas: Zakaj Critticall in ne Critical? :\ Tole mi ne da miru.

Thomas ::

Predstavljaj si, da pri F@H dobiš paket, ki zoptimizira segment kode za siceršnji protein folding.

Potem naslednja verzija klientov dela vsem nekoliko hitreje - rezultat je hitreje dosegljiv.

Na ta način.

Ali pa da na Stanfordu kar sami optimizirajo, preden pošiljajo. Za začetek čisto dobro.

Samo vprašanje pristopa. O ciljih pa ni debate.


:)
Man muss immer generalisieren - Carl Jacobi

Thomas ::

Blabla,

Hočem imet Google (skoraj) unique ime. Sej je rahlo butasto dodajat črke tkole - ampak to je še nezakoličen prostor.

:)
Man muss immer generalisieren - Carl Jacobi

McHusch ::

Pravkar mi je padlo na pamet. Kaj dobiš, če daš Critticallu optimizirat -- samega sebe? Je to sploh možno?

Thomas ::

Dobiš naspidiran/zoptimiziran Critticall. To bomo začeli delat, kakor hitro gre osnovna verzija ven.

:)
Man muss immer generalisieren - Carl Jacobi

snow ::

Kako dolga pa je koda Critticalla? Recimo ti algoritmi, ki si jih je optimiziral, do sedaj (in si jih pokazal :)) ) so bili dolgi le nekaj vrstic.

Pri daljših algoritmih/programih pa najbrž zadeva deluje dosti bolj počasno oz. dosti manj učinkovito? Pa ti pravimo da rabiš Critticall@home :)
Random mutation plus nonrandom cumulative natural selection - Richard Dawkins

Thomas ::

Kako dolg je sam programski odsek, niti ni važno.

while (i==i) {
    j=k;

}

Zgornji vsebuje samo tri programske vrstice, a se izvaja zeloooo dolgo. Važno je, koliko korakov programa/algoritma se dejansko izvrši, za posamezne inpute.

Critticall engine ima cca. 4500 vrstic. Sam lahko obdeluje še večje kose, kot je sam.

Zanimiva je njegova tendenca, da segment prej napihne, kot oklesti. Ampak kot rečeno - edino važno je, koliko korakov se dejansko vsakič naredi.

:)
Man muss immer generalisieren - Carl Jacobi

romci ::

@Thomas:

Ce bi Critticallu dal optimizirati samega sebe - kako bi preverjal pravilnost mutacij, glede na to, da algoritme obstreljujes z random biti?
Oz. kar nas napelje na naslednje vprasanje - kako in ce je sposoben optimizirat oz. evulirat nedeterministicne algoritme?

Al morm pocakat na shareware verzijo, pa sam poskusit? :)

LP,
Roman
-- not all those who wander are lost...

Thomas ::

U ja! Hvala romci, skoraj bi pozabil v helpu napisat primer za optimizacijo random algoritma. En tak primer mora tud bit!

;)
Man muss immer generalisieren - Carl Jacobi

romci ::

Torej tud to dela, zanimivo.

Pol obstaja se kaka druga vrsta preverjanja pravilnosti algoritma poleg (rezultat mutiranga == rezultat originala)?
Hm, to je pa ze enmicken cez meje mojga razmisljanja :)
Ni kej, cestitke - ce res deluje :)
-- not all those who wander are lost...

ciki57 ::

Kakšne bodo pa omejitve shareware verzije? Koliko bo pa cena celotnega programa?

Imaš mogoče že kakšen houmpejð?

Thomas ::

Ena omejitev shareware verzije bo. Da ti bo vsake toliko, ko bo našel izboljšano verzijo algoritma, zahteval click z mišjo na gumb "Proceed evaluating", preden bo mogel iskati naprej.

Cena - prgišče desetdolarskih bankovcev. Tudi evrotov lahko. Točna odločitev še ni padla.

Toliko, da bo gospodu direktorju razvoja ceneje registrirati verzijo, kot zaposliti nekoga, ki bo ponoči 10 krat kliknil mousa.


:)
Man muss immer generalisieren - Carl Jacobi

darh ::

Kdaj pa pride v javnost?

Daj naštej še kakšne uspele rezultate. Na improvanju enega sort algoritma se pač ne gre delat takega boooma, ali pač?
Excuses are useless! Results are priceless!

Thomas ::

V enem tednu mora v javnost. Največ 10 dni, pa upam da niti ne.

Izboljšanje sorta se je zgodilo, ker sem (med testiranjem) nalašč napadel ravno sorte, o katerih je bilo prelitega že veliko črnila in drugih tekočin. Horde ljudi so se desetletja ukvarjale s tem, pa ni nobeden naletel na sort iz prvega posta, ki je v eni česti niši povsem superioren.

Točno to sem hotel, vendar že kar pri sortih nisem računal na kaj takega. Čista smola! >:D

Aja .. homepage bo po izdaji, ko bodo že nekateri nekoliko potestirali.

:)
Man muss immer generalisieren - Carl Jacobi

darh ::

javim se za izdelavo spletišča :D. Cena -- prgišče desetdolarskih bankovcev. Tudi evrotov lahko. >:D
Excuses are useless! Results are priceless!
««
2 / 29
»»


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Najhitrejši programski jezik? (strani: 1 2 )

Oddelek: Programiranje
755830 (3650) Senitel
»

Funkcija z logičnimi operaterji.... (strani: 1 2 )

Oddelek: Programiranje
903584 (2930) CaqKa
»

Petaflopsu naproti (strani: 1 2 3 )

Oddelek: Novice / Procesorji
1056120 (6120) Marjan
»

cene permutacij help please

Oddelek: Programiranje
261546 (1153) Sergio
»

kako definirtati prastevilo

Oddelek: Programiranje
143154 (2959) ooux

Več podobnih tem