vaša sintaksa pri programiranju

Sorry - preden bom dal v javnost, bo 2006. Pa še to težko obljubim. Sem pacal tole leta, tale evo algoritem, da je zadosti agresiven.

Bom pa dal par produktov na trg. Če je za rabo - bo kar hit.

Uporaben, pa kakor vidim, že je. In milijone šol na svetu.

Morm prehitet Goertzla in njegov Novamente.

Za makerja je tole idealno.

Output (v obliki MXX) assemblerja - pa celo zna skompilirat. Lahkho gre pa ta tudi v MS C++ ali kam drugam.

Sample output code:

__asm {
pusha
mov eax,0
mov ebx,0
mov ecx,0
mov edx,0
mov edi,0
mov esi,0
mov edi,var000
mov esi,var001
add esi,16
add edi,16

pxor mm7,mm7
movd mm7,var003

mov bh,64
movq mm0,[edi]
add edi,8

pxor mm3,mm3

loop1:
mov ecx,4
loop2:
movq mm2,[s7]
pand mm2,mm0

psrl mm0,3
sub bh,3
movd eax,mm2
cmp eax,7
jne k201

movq mm2,[s255]
pand mm2,mm0
movd edx,mm2
mov [esi],dl

psrl mm0,8
sub bh,8
movq mm2,[s255]
pand mm2,mm0
movd edx,mm2
mov [esi+4],dl

................

Zanimivo. Zelo zanimivo. Sam eno vprasanje. Zakaj si najprej premaknil 0 v edi, potem pa se var000. A ni to brezveze?
...
mov edi,0
mov esi,0
mov edi,var000
mov esi,var001
...

Lahko pa povem še kaj o tej Evoluciji in urnikih.

Urnik je en tak klasičen NP problem. Problem, ki ni rešljiv v polinomskem času. N krat večji urnik zahteva ciklov^N. Če je "urnikov" za šolo s 5 oddelki 10¹²⁵ - jih je za šolo z 20 oddelki kar 10⁵⁰⁰!

Niso pa vsi dobri, dijaki morajo imeti toliko in toliko posameznega predmeta, en učitelj ne more učiti več kot enega razreda kadar ni posebej navedeno da lahko ... in 100 takih umazanih podrobnosti.

Tudi teh dobrih urnikov je verjetno milijarde milijard - kapljica v morje proti zgornji številki. Ali pa tudi nobeden!

Razni zviti algoritmi potem vseeno brskajo dobre urnike ven v nekem realnem - ali pa tudi ne - času.

Algoritmi, ki so aktivni v nekaterih človeških glavah - so zelo dobri. Vendar ne vemo, kako točno delujejo.

Sem mnenja, da tistim prvim, digitalnim algoritmom, nekaj milijonov generacij evolucije zanesljivo ne more škodovati.

Evolucijski pritisk smo usmerili v njihovo hitrost. Brute force algoritem lahko poišče en urnik za 3 razrede v kakšni sekundi. Maker (to je tisti PowerBasic program) mu ("MMX algoritmu") potem random doda jmp in podobne ukaze in pogleda če je v eni sekundi prišel ven. Po nekaj urah ponavljanja šele pride prvi tak, ki je tudi naredil pravilen urnik.

Nekje je rezerviran prostor za TOP 100 algoritmov - pač glede na hitrost. Alfa algoritem ima potem največ "random skvarjenih" potomcev. Če se kateri od njih izkaže bolje od 100. člana algoritemskega krdela, se uvrsti v to elito namesto njega - ampak na zasluženo in ne na zadnje mesto. Tudi trenutni alfa kmalu izpade. Upamo vsaj.

Drugi imajo manj potomcev. Pač glede na rank. Delijo si strande kode in delajo skupne potomce. Sex se reče temu. In to v troje in več. Random, kakor nanese. Vsak dark horse ima možnost, da (delno) njegov potomec prevzame alfa mesto.

Trenutni alfa v primeri s svojim davnim prednikom naredi v eni sekundi milijardokrat bolj zahtevno nalogo. Ima pač toliko exit ukazov, da ni več podoben brute force algoritmu.

Ko potem do tega prvega, legitimnega urnika pride - maker sproži evolucijo, ki naj ga poprijazni. Programe smo pospeševali, od urnikov pa hočemo, da so prijazni. Povsem isti proceduri so podvrženi. Vsako sekundo se rodi preko 40000 urnikov. Točkujemo kako je matematika zadnjo uro kot "slabo -60", kako je več kot npr. 3 proste ure za učitelja na teden "slabo -30", kako je prost dan za učitelja "slab -1000". Ali pa dober 500. En INI fajl to vsebuje in nastavljamo po želji.

Evolucija torej spet udari in izcimi urnik "čimbolj po želji". Trdim, da so tisti na biološkem substratu narejeni - slabši. Predvsem jih pa ni 100 alternativnih.

Tokla se dajemo. - bi rekli v Kranju in okolici.

No, avtomatično kreiranje namesto pisanja - je tukaj očitno obvezno.

čudno - naš urnik (gimnazijskega) je pisala profesorica. Usklajevala je nekje 50 profesorjev, 1300 dijakov, 36 razredov. Pa sem imel vsak dan začetek ob 08:00, brez prostih ur...

V njeni glavi se odvijajo dobri algoritmi - ni kaj. Ampak dvomim, da bi se še lahko kosali z digitalnimi.

Prostih ur pa dijaki ne smejo imeti. Profesorji jih pa očitno imajo, če jih je več kot razredov. Štos je v tem, da čimmanj vmesnih prostih ur. Ali pa po 3 na teden. Stvar preferenc pač. Digitalna evolucija vsako postavljeno preferenco/zahtevo resno vzame.

Thomas, daj predstavi mi svoje izdelke.

Pozdravljen THOMAS

Zagnjavil te bom z enim (ali pa več vprašanji glede evolucijskega (ih) algoritma (mov). Zadeva se nanaša na tvoj post, kjer omenjaš optimizacijo lopatic reakcijskih motorjev pri General Electricu...

Najprej za razumevanje:

Po izobrazbi sem strojnik. Od programskih jezikov sem se učil FORTRAN (Kaj drugega pričakuješ od strojnika ? Ja pa VAX je CAR ), največ kode pa sem njega dni spisal v SuperBASICU (ja ja imel sem Sinclair QL-a... ), zadnjo kodo pa sem spisal pred cca 10-timi leti v Turbo Pascalu (rabil za diplomo...). Torej, programiranje mi je (spet) španska vas....

Torej, če povzamem (prosim korigiraj me, če se motim!) tvoj način ustvarjanja urnikov. Torej uporabljaš en programski jezik (PowerBASIC), s katerim pa ne kodiraš kode za izračun urnika, temveč z njim generiraš nekaj (recimo temu) random programov, ki potem generirajo urnik(e). (Oziroma imaš nek izhodiščni (SEED) program, ki služi nato za mutacije). Nato te urnike preanaliziraš (programsko seveda), ter ugotoviš, kateri najbolj ustreza zadanim pogojem. Tisti programi, ki so izdelali najbolše urnike, grejo v nadaljnje mutacije in nato se iteracijsko stvar ponovi....dokler urniki ne zadovoljijo zahtev.

No tukaj je pa moje vprašanje glede turbinski lopatic pri General Electricu (GE). Problem vidim namreč v izvrednotenju (ocenjevanju uspešnosti) oblike lopatice. Če želijo oceniti uspešnost takšne lopatice, jo (po mojem menju) morajo analizirati z vsaj dvema programoma in sicer MKE (metoda končnih elementov) in CFD (računalniško podprta dinamika fluidov) in sicer tako, da jo najprej zanalizirajo z CFD, da dobijo vrednosti aerodinamičnih obremenitev na lopatico, ki so potem robni pogoj za analizo po MKE, ki potem izračuna napetost in deformacije. Ker deformacije spremenijo obliko lopatice, se spremenijo tudi aerodinamične vrednosti, torej gremo spet v CFD....(pavzaprav iteracijsko, dokler zadnja dva rezultata ne odstopata za neko določeno razliko. Seveda pod pogojem, da zadeva konvergira ). Pri tem je potrebno povdariti, da so CFD izračuni računalniško izredno zahtevni. Sicer verjamem, da ima GE na voljo superračunalnike (ki so kar običajno orodje pri večjih CFD simulacijah...). Glede na to, da ti govoriš o več desettisoč potomcih, dvamim, da GE dela z mutacijo oblike lopatice.
Moje vprašanje je, ali je to res to? (Prosim a maš kakšen link)
Prej verjamem, da se to počne z iteracijsko metodo, ko se na podlagi rezultatov analize spreminja eden (ali nekaj, vsekakor malo število) geometrijski parameter lopatice, dokler se ne doseže (kvazi) optimalna oblika.
Obstaja pa področje, kjer bi pa lahko že danes zelo dobro uporabili evolucijske algoritme pri CFD (in MKE) analizah. To je pri izdelavi generatorjev mrež (končnih volumnov ali končnih elementov) v smislu iskanja optimalne mreže glede na točnost rezultatov in čim manjšo pasovno širino matrike...

Ups sem se razpisal


LP

Jože

Evo Thomas en NP problem zate. Tole smo imel pol leta nazaj za rešit (čimbolje) na faksu: Klik!

Bi se dalo to tudi s tvojo evolucijsko tehniko?

Računaj, da pridejo v poštev tudi n > 10.000

ups! zgleda da so že vrgli dol s serverja.

Na srečo sem imel kopijo na disku. Nov link!

Tukaj je diff v C-ju. Kompleksnost je O(n^2). Mogoče gre še bolje, samo se nisem kaj preveč matral.

klik!

Generacija___Diff__________Permutacija

1____________27____________1__2__3__4__5__6__7
9____________25____________3__6__7__1__5__2__4
63___________23____________6__1__3__2__7__4__5
64___________22____________3__1__6__2__7__4__5
104__________21____________6__3__1__7__2__4__5
130__________20____________3__6__1__7__2__4__5

Takole zmutira v 130 generacijah od osnovne do optimalne permutacije.

Neoptimizirano sicer.

za tale alg. sm ponucal kar precej casa:
50 - 1048
100 - 4269
500 - 111092
1000 - 432791
5000 - 10525886
10000 - 40633584

vsi so 60 sek. in to na c3 800 (podn podna, ja:).

Ciki57

Evolucija je zdaj pri:

1065 za 50


37 34 4 20 23 27 44 33 25 39 21 16 28 26 17 12 32 36 24 35 40 30 22 29 31 14 42 38 9 6 3 45 43 46 47 48 49 50 41 13 1 8 2 5 7 15 18 10 11 19

A mnkplo je pa tvoj alter ego?

No če je ... in če ni ... potem bo zanimivo gledati, če se lahko približa tvojemu rezultatu 1048 ali ga celo preseže.

Bom pustu tečt zadevo.



BojlerTM

Ne boš vesel zdej kar ti bom povedal - najbolj koristijo biološke knjige na temo evolucija. Program že narediš, potem ko zastopiš cake.

Za začetek:

Dawkins, R. 1989. The Selfish Gene. Oxford: Oxford University Press

1048 zgleda takole:

34 20 4 23 37 27 44 33 25 39 21 16 26 17 28 32 12 24 35 30 36 40 22 29 31 14 42 9 38 6 3 45 43 46 47 48 49 41 50 1 8 5 2 13 7 11 15 18 19 10

Evolucija pa teče dalje ...

10000 bom poskusil kasneje ...

> ciki57: Tisto kar mas ti je povprecni polozaj? Samo ugibam - 3/4 letnika je imelo to :).

res je. Sem se matral pogruntat še kaj boljšega, pa ni šlo...
Kakšen algoritem si pa ti uporabil?

Thomas, še eno vprašanje. Ali ti tukaj skozi evolucijo izboljšuješ permutacijo ali kodo, ki generira permutacijo?

ciki57:

1. Zacnes z povprecnim polozajem (kar se da narediti s quick/heap-sortom v O(nlogn)).

2. Se eden O(n^2) algoritem: deluje tako, da gradi permutacijo, recimo imas ze k stevk, potem pa doda k+1 stevko na tisto mesto v ze obstojeco perm. k, da bo k+1 stevka povecala diff od perm. k za najmanj. Tako ponavljas dokler ti ne zmanjka stevk.

3. Alg. iz 2. ponavljas na majhnih (a s casom vedno vecjih) kosih permutacije iz tocke 1. Ta alg. se za velike n v 60 sek. ne iztece cisto do konca. Trik je v tem, da urejenost podpermutacije ne vpliva na ostali del cele permutacije.

4. Ker ta alg. iz 2. ni cisto 100%, sploh ti pa za male n ostane veliko casa, lahko alg. iz 3. uporabljas kar kot brute-force - isce vse podpermutacije in izbira najboljso.

Bilo nas je nekje 10-20, ki smo med sabo primerjali diff-e, pa me je to spodbudilo, da sem spisal ta monstrosity :).

Thomas: Ce ti ne isce/gradi/izbolsuje algoritma, potem nima veze. Jaz bi lahko pustil stvar laufat tudi cez noc. Slej ko prej bi imel optimalen diff :).

Ce se ne motim, tole ni permutacija 1...100 :).

> Kakršenkoli string lahko izboljšuje. Program, križanko, genom ...

To ze, samo mislil sem, da bos z EA zgradil kar algoritem, ki ti bo to nalogo resil. Po moznosti v manj ko minuti. Ocitno se moras kar precej poglobiti v problem za kaj taksnega, jap? Verjetno ni kar vsakrsen brute-force program ok za nadaljnji evolucijski razvoj?

ok, zdaj se moram pa se za kak izpit kej naucit :)

Tole da z EA izboljšuješ algoritem se sliši precej zanimivo.

A pa lahko to narediš kar tako, da pošlješ skozi EA neko kodo v C-ju ali moraš algoritem prej predelati v kakšno drugo obliko?

Ali bi se dalo, da recimo na manjhnih n razviješ algoritem, ki zadevo reši skoraj optimalno pri majhni časovni zahtevnosti, nato pa isti alg. uporabiš še za velike n?

> Ali bi se dalo, da recimo na manjhnih n razviješ algoritem, ki zadevo reši skoraj optimalno pri majhni časovni zahtevnosti, nato pa isti alg. uporabiš še za velike n?

Kot sem omenil že nekje zgoraj - urnik za 3 oddelke. Brute force, potem pa nekaj evolucije na njem. Zdaj dela za nekaj 10 oddelkov. EA mu pa še ne da miru.

4305.

4261

45 6 91 41 29 59 93 68 90 95 92 2 94 7 52 5 40 79 30 78 72 85 31 25 96 39 10 73 97 76 20 98 44 48 46 9 99 50 89 27 56 61 66 75 11 37 60 18 3 21 33 13 67 34 12 86 32 24 42 74 55 15 63 80 14 82 83 62 84 87 53 88 65 100 36 4 70 8 71 1 64 57 69 51 17 54 77 16 28 81 23 22 38 47 49 19 26 35 58 43

> Sam je pa tole že opazno počasneje kot za 50.

Je bilo ja. Ampak a je pomembno?

Po moje ni. Samo majhen eksperiment je bil, ki naj dokaže/preizkusi koncept. Kakor tale Goddardova raketa



Letela je čez streho in pristala v zelniku njegove tete.

"Saturn V" bo poletel enkrat v naslednjem desetletju. Če ne še v tem.

> Če bi bil tole kakšen resen problem, bi bilo bolje razviti agoritem.

Nič več. kmnolpov algoritem je bil premagan. Mar ne?

A to ti mene izzivaš, da skozi EA dam tvoj algoritem in ga poskušam izboljšati?

Ker zate sam rezultat (sicer boljši od tvojega) ni dovolj dober. Ti bi rad še, da EA naredi od tvojega hitrejši algoritem?

Se bo zgodilo. Trenutno sicer ne utegnem, ampak kar kmalu pa bom.

Kaj ma kdo kaki link, ki malo to programiranje razložil, da bi še navadni smrtniki razumeli?
pls!