Optimizacija mravlje kolonije

Sad prelazimo sa analogije metalurških procesa na biologiju :) E ta veštačka inteligencija, uvek traže inspiraciju u nečemu postojećem. Ideja je nastala na osnovu proučavanja konunikacije i upravljanja koji se dešava među insektima. Mravi kad traže neki izvor ispuštaju feromone. Feromoni vremenom isparavaju a količina feromona na nekoj stazi zavisi i od dužine staze. Mrav koji nađe kraći put na tom putu će ostaviti veću količinu feromona koji će drugim mravima poslužiti za navođenje na bolju putanju.

Pomoću ove ideje moguće je napisati heuristiku za rešavanje problema trgovačkog putnika (nalaženje što kraće Hamiltonove konture). 

Dovoljno je imati 3 proste formule, toliko proste da su matematičari morali da ih zakomplikuju lupanjem nekih čudnih oznaka, samo im rusko slovo Я fali. To me podseti na epizodu kad sam polagao statistiku kod jedne nemaštovite asistentkinje kojoj je bilo čudno što formulu uslovne verovatnoće nisam izveo identično kao u knjizi, tj. što nisam bubao već pravio delikt mišljenja. Pa sam joj rekao da dok god je formula ispravna mogu da koristim i Э kao oznaku :D Matematičar su uvek najveći problem matematike.

Zato ću ja formule prikazati uprošteno (a i ne znam kako bih napisao sve one indekse, stepene, klince, palce). Prva formula služi da se izračuna količina feromona za neku ivicu (direktnu vezu dva grada). Formula je rekurentna (programerski rečeno rekurzivna) jer se nova količina feromona izračunava preko stare prostim dodavanjem:

kolicina_feromona = kolicina_feromona + Q/duzina_Hamiltonove_konture *RO

Ili uprošćeno:

kolicina_feromona +=  Q/duzina_Hamiltonove_konture *RO

Q je neka konstanta koja označava količinu feromona kojom svaki mrav raspolaže. Pa mrav koji nađe kraću putanju ima ivicama da doda više feromona jer je Q/mala_vrednost veći broj nego Q/velika_vrednost. Konstanta RO je između 0 i 1 i služi da odredi koliko novog feromona treba dodati. Pošto je formula rekurentna mora postojati početna vrednost pa se uzima da je kolicina_feromona = 1 / broj_gradova

Druga formula simulira isparavanje feromona:

kolicina_feromona = kolicina_feromona * (1 - RO)

ili:

kolicina_feromona *= (1 - RO)

RO je ista konstanta kao iz prethodne formule. Npr. ako je RO = 0,7 to znači da će se na putanju kojom je mrav prošao staviti 70% vrednosti Q/duzina_Hamiltonove_konture, a od stare količine feromona 70% će ispariti.

I treća formula izračunava verovatnoću da se krene nekom ivicom tj. da se obiđe neki neposećeni grad iz tekućeg grada. Za svaku moguću ivicu (tj. za svaku direktnu vezu tekućeg i neposećenih gradova) se izračunava poželjnost. Poželjnost je proporcionalna količini feromona na ivici i njenoj kratkoći. Kratkoću definišemo kao 1 / duzina_ivice a količinu feromona čitamo direktno. Udeo pozeljnosti i-te moguće ivice u zbiru pozeljnosti svih mogućih ivica je upravo verovatnoća da se mrav zaputi tom ivicom. Količinu feromona matematičari označavaju ubercool slovom Tau, a kratkoću slovom Eta. Formula je (** je operator stepenovanja):

P = (Tau**ALFA * Eta**BETA) / SUM(Tau**ALFA * Eta**BETA)

Da bi se kontrolisao značaj kratkoće i feromona uvode se ALFA i BETA parametri kojim se stepenuju količine feromona (Tau) i kratkoće (Eta). Pošto su i Tau i Eta manji od 0 znači da što je stepen veći to se umanjuje značaj te karakteristike u poželjnosti. 

I konačno kod:

import random, copy, math, time

class Grad(object):     
    def __init__(self, x, y, ime):
        self.x = x
        self.y = y
        self.ime = ime
        
    def rastojanje(self, grad):
        """ 
        rastojanje ovog grada od grada primljenog kao prarametar
        preko euklidske metrike (odnosno funkcije hypot).
        """
        return math.hypot(self.x - grad.x, self.y - grad.y)
        
    def __str__(self):
        return "%s(%d, %d)" % (self.ime, self.x, self.y)
 
class Ivica(object):
    def __init__(self, feromoni, duzina):
        self.feromoni = feromoni
        self.duzina = duzina

class Mrav(object):
    # atribut klase u kojem se cuva broj svih stvorenih mrava
    brojac = -1
    gradovi = None
    ivice = None
    
    def inicijalizuj_atribute(self):
        self.tek_grad = self.pocetni_grad
        self.putanja = [self.tek_grad]  
        self.duzina_putanje = 0.0
        
    def __init__(self, gradovi, alfa, beta, ro, q):
        Mrav.ALFA = alfa
        Mrav.BETA = beta
        Mrav.RO = ro
        Mrav.Q = q
        
        if not Mrav.gradovi: 
            Mrav.gradovi = gradovi
            
        if not Mrav.ivice:
            Mrav.ivice = {}
            init_feromoni = 1.0 / len(Mrav.gradovi)
            for i in Mrav.gradovi:
                for j in Mrav.gradovi:
                    if i != j :
                        rastojanje = i.rastojanje(j)
                        Mrav.ivice[i, j] = Ivica(init_feromoni, rastojanje)
                        
        Mrav.brojac += 1
        self.pocetni_grad = Mrav.gradovi[Mrav.brojac % len(Mrav.gradovi)]
        
        self.inicijalizuj_atribute()
       
    def _tau_x_eta(self, do_grad):
        # izracunava vrednost pozeljnosti ivice od tekuceg grada do grada
        # primljenog kao parametar. Pozeljnost ivice je direktno proporcionalna 
        # kolicini feromona na njoj (sto se oznacava sa tau), a obratni proporcionalna 
        # njenoj duzini (eta). Stepenovanjem tau i eta sa parametrima ALFA i BETA 
        # omogucava nam da dajemo prednost jednom ili drugom kriterijumu pozeljnosti
        # i to tako sto BETA oznacava koliko umanjujemo znacaj blizine a ALFA
        # koliko umanjujemo znacaj feromona. Npr. za ALFA: 1 i BETA: 5 znaci da
        # nam je vaznija kolicina feromona od blizine
        ivica = Mrav.ivice[self.tek_grad, do_grad]
        tau = ivica.feromoni
        eta = 1.0 / ivica.duzina
        
        return tau**Mrav.ALFA * eta**Mrav.BETA
        
    def _odaberi_sledeci_grad(self):
        imenilac = 0.0
        
        # svi gradovi razlika poseceni = neposeceni, skupovna operacija
        neposeceni_gradovi = set(Mrav.gradovi).difference(self.putanja)
        
        # ako nema neposecenih vrati None
        if not neposeceni_gradovi:        
            return None
        
        # za svaki neposeceni grad izracunaj _tau_x_eta i saberi
        # tj. racunamo zbir svih pozeljnosti posete neposecenim gradovima
        for grad in neposeceni_gradovi:
            imenilac += self._tau_x_eta(grad)
        
        # za svaki neposecen grad izracunaj verovatnocu posete p
        # i pokusaj da je ostvaris, ako je ne ostvaris probaj
        # ponovo sve iz pocetka dok konacno ne uspes u tome.
        # Verovatnoca posete se izravunava tako sto podelimo pozeljnost posete
        # neposecenog grada sa zbirom svih pozeljnosti posete neposecenim gradovima
        while True:
            for grad in neposeceni_gradovi:
                p = self._tau_x_eta(grad) / imenilac
                
                if random.random() < p:
                    return grad

    def pusti_mrava(self):
        sled_grad = self._odaberi_sledeci_grad()
        
        # dok postoji sledeci grad za obilazak stavi ga u putanju obishenih
        # azuriraj duzinu putanje mrava i tekuci grad a zatim nadji sledeci grad
        while sled_grad:
            self.putanja.append(sled_grad)
            self.duzina_putanje += Mrav.ivice[self.tek_grad, sled_grad].duzina
            self.tek_grad = sled_grad
            sled_grad = self._odaberi_sledeci_grad()
        
        # sad je sled_grad None znaci da smo prosli sve gradove
        # a Hamiltonovu konturu zatvaramo vezujuci 1. i poslednji 
        # poseceni grad koji se cuvaju u self.putanja (0. i -1. poziciju)
        self.duzina_putanje += Mrav.ivice[self.putanja[0], self.putanja[-1]].duzina
        
    def pospi_feromone(self):
        br_gradova = len(self.putanja)
        
        # svakoj ivici putanje mrava (Hamiltonove konture) u oba smera dodaj 
        # odgovarajucu kolicinu feromona po formuli Q / duzina_putanje * RO
        for i in xrange(br_gradova):
            od_grada = self.putanja[i]
            do_grada = self.putanja[(i + 1) % br_gradova]
            
            Mrav.ivice[od_grada, do_grada].feromoni += Mrav.Q / self.duzina_putanje * Mrav.RO
            Mrav.ivice[do_grada, od_grada].feromoni = Mrav.ivice[od_grada, do_grada].feromoni
            
    @staticmethod
    def ispari_feromone():
        # smanji kolicinu feromona na svakoj ivici po rekurentnoj formuli feromoni *= 1 / RO
        for ivica in Mrav.ivice.itervalues():
            ivica.feromoni *= (1.0 - Mrav.RO)
            
    def koordinate(self):
        x, y = [], []
        
        for grad in self.putanja:
            x.append(grad.x)
            y.append(grad.y)
        
        return x, y
    
    # toString u javi        
    def __str__(self):
        return "duzina puta: %f" % self.duzina_putanje
    
    # compare u javi
    def __cmp__(self, drugi):
        return cmp(self.duzina_putanje, drugi.duzina_putanje)
            
            
class MravljiSimulator(object):
    def __init__(self, gradovi, ALFA = 1.0, BETA = 5.0, RO = 0.5, Q = 100.0):
        self.mravi = []
        for i in xrange(len(gradovi)):
            self.mravi.append(Mrav(gradovi, ALFA, BETA, RO, Q))
        self.najbolji_mrav = self.mravi[0] # proizvoljnog mrava proglasimo najboljim
        
    def start(self, ponavljanja=20):
        # za svako ponavljanje
        for i in xrange(ponavljanja):
            # pusti svakog mrava da napravi Hamiltonovu konturu
            for mrav in self.mravi:
                mrav.pusti_mrava()
                
            Mrav.ispari_feromone()
                
            # svaki mrav nek pospe feromone na svojoj konturi
            for mrav in self.mravi:
                mrav.pospi_feromone()
                
            najuspesniji_mrav_generacije = min(self.mravi)
            
            # pamtimo sveukupno najuspesnijeg mrava
            self.najbolji_mrav = copy.deepcopy(
                    min(self.najbolji_mrav, najuspesniji_mrav_generacije))
            
            # pripremamo mrave za ponavljanje tako sto ih resetujemo
            for mrav in self.mravi:
                mrav.inicijalizuj_atribute()
                
    def stampaj_resenje(self):  
        if self.najbolji_mrav:
            try:
                # ako je instalirana matplot biblioteka koristi je za graficki prikaz
                import matplotlib.pyplot as plt 
                
                x, y = self.najbolji_mrav.koordinate()
                                
                # 1. tacku dodajemo ponovo da bi zatvorili konturu od poslednje ka 1. tacki
                x.append(x[0])
                y.append(y[0])
                
                plt.title('prikaz nadjenog resenja')
                plt.plot(x, y, 'g', marker='.', markerfacecolor='r', markersize=20, label='najbolje r.')
                plt.xlabel('x koordinata')
                plt.ylabel('y koordinata')
                plt.text(2, 95, 'najbolja duzina: %f.2' % self.najbolji_mrav.duzina_putanje)
                plt.legend()
                
                for grad in self.najbolji_mrav.putanja:
                    plt.text(grad.x, grad.y - 2.5, grad.ime)
                
                plt.axis([min(x) -1, max(x) + 1, min(y) -1, max(y) +1])             
             
                plt.show()
            except ImportError:
                # nema matplot biblioteke stampaj resenje rucno
                print "Resenje"
                print self.najbolji_mrav.putanja
                print "duzina puta je: ", self.najbolji_mrav.duzina_putanje
                
        
def main():
    try:
        import psyco # ako je instalirana biblioteka koristi je (ubrzava izvsenje koda)
        psyco.full()
    except ImportError:
        pass    
    
    gradovi = [Grad(1, 2, 'a'), Grad(29, 21, 'b'),Grad(100, 60, 'c'), Grad(12, 86, 'd'), 
            Grad(92, 46, 'e'), Grad(83, 38, 'f'), Grad(55, 36, 'g'), Grad(71, 99, 'h'),
            Grad(12, 41, 'i'), Grad(34, 48, 'j'), Grad(69, 33, 'k'), Grad(78, 10, 'l'),
            Grad(86, 68, 'm'), Grad(79, 27, 'n'), Grad(22, 69, 'o'), Grad(75, 55, 'p'),
            Grad(51, 68, 'r'), Grad(91, 23, 's'), Grad(22, 42, 't'), Grad(47, 80, 'u'), 
            Grad(60, 10, 'w'), Grad(91, 79, 'v'), Grad(5, 66, 'x'), Grad(42, 90, 'y'),
            Grad(23, 59, '1'), Grad(46, 83, '2'), Grad(93, 63, '3'), Grad(47, 17, '4'),
            Grad(53, 79, '5'), Grad(76, 23, '6'), Grad(91, 62, '7'), Grad(44, 97, '8'),
            ]
            
    simulator = MravljiSimulator(gradovi, ALFA=1.0, BETA = 2.0, RO=0.5)
    
    t0 = time.time()
    simulator.start(ponavljanja=50)
    print "Izvrsenje trajalo", time.time() - t0, "sekundi"
    
    simulator.stampaj_resenje()

if __name__ == "__main__":
    main()    
    

Gradovi koje sam ovde koristio su isti oni koje sam korisitio sa Simuliranim kaljenjem. Rastojanja gradova se unapred izračunaju da bi se program brže izvršavao. Brzo se dobijaju dobra rešenja. Otprilike da je putanja koju pronađe u proseku dugačka oko 530. A svaki 15-20 put ubode se i rešenje čiju sam sliku postavio. Za razliku od Simuliranog kaljena ovde ima mnoštvo parametara sa kojima se treba igrati da se nađe njihova dobra vrednost.

Kako se kale kraljice

Još jedan problem s kojim se ljudi koji se bave umetnošću programiraju vaćaju u koštac je problem N kraljica. Na tabli N x N treba postaviti N kraljca a da jedna drugu ne jedu.

I ovaj problem se može rešiti Simuliranim kaljenjem. Funkcija cilja je u ovom slučaju broj sukoba, samo za razliku od prošlog primera sa trgovcem ovde se zna da je optimalno rešenje kad je f. cilja = 0.

Počentno rešenje se lako nalazi. Prvo ne sme se desti da više od jedne kraljce bude u bilo kom redu i bilo kojoj koloni. Dakle najprostije je da se poređaju po dijagonali. U mom rešenju se takvo rešenje tvikuje par puta i dobija se početno rešenje.

Tvikovanje se sastoji u nasumičnoj zameni 2 kolone.

Implementacija je takva da se u klasi Resenje u nizu koji se zove kraljice čuva pozicija kraljice u redu za svaku kolonu. Npr. niz [1, 0, 2] znači da se u 1. koloni kraljica nalazi u 2. redu, 2. koloni u redu 1, a u 3. koloni u redu 3 (i u Pythonu su prvi elementi niza na poziciji 0). Dakle u početnom rešenju ćemo pre tvikovanja imati ovakav niz: [0, 1, 2, 3, ...] jer kraljice postavljamo po dijagonali.

Dalje formiramo tabelu N x N i koja se puni None objektima (u pythonu je sve objekat pa i Null vrednost ) osim što se na dijagonalama postavi string K kao oznaka da je tu kraljica.

Samo simulirano kaljenje je slično kao u prošlom primeru. Jedino se manje vrši resetovanje tekućeg rešenja jer je takav zadatak da se tvikovanje može obaviti na već tvikovano rešenje bez većeg problema.

A pošto znamo koje je optimalno rešenje, kaljenje se ponavlja iznova sve dok ne dođemo do tog rešenja kad se štampa optimalni raspored na tabli.

import random, copy, math, time

class Resenje(object):
    def __init__(self, br_kraljica):
        self.br_kraljica = br_kraljica
        # resenje: pozicija kraljice u koloni 0 do len - 1
        self.kraljice = range(br_kraljica)  
        # energija: treba da je  0 
        self.__broj_sukoba = None
        
        ## postavljamo pocetno resenje
        # generisemo tabelu br_kraljica X br_kraljica popunjenu None elementima
        self.tabla = [[None for i in range(br_kraljica)] for j in range(br_kraljica)]
        
        # postavimo kraljice po dijagonali
        for i in xrange(br_kraljica):
            self.tabla[i][i] = 'K'
        
        # promesamo kolone    
        for i in xrange(br_kraljica):
            self.tvikuj_resenje()
        
    # f-ja cilja, optimalno resenje ima 0 sukoba   
    def get_broj_sukoba(self):
        # Ovo je optimizacija da se broj sukoba racuna samo ako vec nije izrazcunat
        if not self.__broj_sukoba:
            self.__broj_sukoba = self.__racunaj_broj_sukoba()
        return self.__broj_sukoba
    
    # racuna energiju resenja, prakticno funkciju cilja koja se minimizuje
    # a je ovde broj sukoba svih kraljica na tabli
    def __racunaj_broj_sukoba(self):
        # povratna vr. 
        # zato sto se sukobljava sam sa sobom i to pri proveri svake od 4 
        # dijagonala a to se ne racuna
        br_sukoba = -4 * self.br_kraljica 
        
        dx = (-1, 1, -1, 1) # pomeraj koordinate x za kretanje po dijagonalama
        dy = (-1, 1, 1, -1) # pomeraj koordinate y -//-
        
        # provera dijagonala
        for x, y in enumerate(self.kraljice): # (x,y) koord. kraljica
            for i in xrange(4): # za sva 4 kraka dijagonala
                pomx, pomy = x, y # pretraga krece od koordinata kraljice
                # dok se pomeranjem po dijagonali nalazimo na tabli ispitujemo 
                # da li smo nabasali na kraljicu. Svaki od 4 ciklusa za 4 dijagonale
                # nailazi na sopstvenu kraljicu pa je zato br_sukoba inicijalizovan 
                # na -4 * self.br_kraljica 
                while (0 <= pomx < self.br_kraljica) and (0 <= pomy < self.br_kraljica): 
                    if self.tabla[pomx][pomy] == 'K':
                        br_sukoba += 1
                    pomx += dx[i]
                    pomy += dy[i]
            
        return br_sukoba
    
    broj_sukoba = property(get_broj_sukoba)
    
    # zamenjuje 2 kolone
    def tvikuj_resenje(self):
        r1 = random.randrange(self.br_kraljica)
        r2 = random.randrange(self.br_kraljica)
        
        # kolone moraju biti razlicite
        while r2 == r1:
            r2 = random.randrange(self.br_kraljica)
            
        # zameni redove r1 i r2
        self.tabla[r1], self.tabla[r2] = self.tabla[r2], self.tabla[r1]
        
        # zameni elemente
        self.kraljice[r1], self.kraljice[r2] = self.kraljice[r2], self.kraljice[r1]
        
        # prethodno izracunata duzina puta vise ne vazi pa se setuje na None
        self.__broj_sukoba = None
    
    def __str__(self):
        rez = ''
        for red in self.tabla:
            s = ''
            for element in red:
                if element: s += element
                else: s += '.'
            rez += s 
            rez += '\n'
        return rez
        
    
class SimulatorKaljenja(object):
    def __init__(self, br_kraljica):
        self.br_kraljica = br_kraljica
        self.resenje = None
        
    def start(self, pocetna_temperatura=90.0, alpha=0.997, ponavljanja=None):
        najbolje_resenje = Resenje(self.br_kraljica)
        tekuca_temp = pocetna_temperatura
        if not ponavljanja: ponavljanja = self.br_kraljica / 2
        
        
        while tekuca_temp > 0.10 and najbolje_resenje.broj_sukoba > 0:
            privremeno_resenje = copy.deepcopy(najbolje_resenje)
            
            # Monte Carlo na tekucoj temperaturi
            for i in xrange(ponavljanja):
                privremeno_resenje.tvikuj_resenje()
                
                delta_e = privremeno_resenje.broj_sukoba - najbolje_resenje.broj_sukoba
                
                # ako je resenje bolje uzimamo ga a ako nije tada uz 
                # odredjenu verovatnocu odabiramo losije resenje kao tekuce
                if delta_e < 0.0 or (math.exp(-delta_e / tekuca_temp) > random.random()):
                    if  privremeno_resenje.broj_sukoba < najbolje_resenje.broj_sukoba:
                        najbolje_resenje = copy.deepcopy(privremeno_resenje)
                else:
                    privremeno_resenje = copy.deepcopy(najbolje_resenje)
                
            tekuca_temp *= alpha
        
        self.resenje = najbolje_resenje
    
def main():
    try:
        import psyco
        psyco.full()
    except ImportError:
        pass
        
    simulator = SimulatorKaljenja(32)    
    
    t0 = time.time()

    i = 1
    while True:
        print 'ciklus', i
        i += 1
        simulator.start()
        print 'najbolje resenje', simulator.resenje.broj_sukoba
        if simulator.resenje.broj_sukoba == 0:
            break
       
    print simulator.resenje
    print "Izvrsenje trajalo", time.time() - t0, "sekundi"
    

if __name__ == "__main__":
    main()

Primer rezultat ovoga koda je:

ciklus 1 
najbolje resenje 2 
ciklus 2 
najbolje resenje 0 
.K.............................. 
....................K........... 
..................K............. 
............K................... 
..K............................. 
...........................K.... 
.................K.............. 
K............................... 
..........K..................... 
.....K.......................... 
...............................K 
...................K............ 
..........................K..... 
.............K.................. 
.....................K.......... 
............................K... 
...............K................ 
.............................K.. 
......................K......... 
......K......................... 
.........................K...... 
.......K........................ 
..............K................. 
...........K.................... 
..............................K. 
....K........................... 
................K............... 
........................K....... 
.........K...................... 
.......................K........ 
...K............................ 
........K....................... 

Izvrsenje trajalo 35.1647040844 sekundi

Kako se kalio čelik

Nešto mi je ovijeh dana dosadno bilo, a dokon um đavolje dvorište. Te se dovatim jedne knjige o AI algoritmima. U pa tu ima svakakve 'euristike, ovi iz Operacionih bi zinuli

E ovde ću kako budem stizao da postavljam neke algoritme. Knjiga ima neke C kodove, sad malo ko parla C, a i ti kodovi su tako odvratni i u knizi dati iz delova i nepotpuno. Pa sam ih ja sredio u mom omiljenom prog. jeziku

Prvi algoritam je Simulirano kaljenje. Ima nešto o tome u knjizi iz Operacionih, ali to su pisali matematičari (čitaj: dosadni tipovi). Ideja je da se podražava proces kaljenja. To smo valjda učili iz Teknologije, eto neke koristi i od toga Pa kako se kali? Podigne se temperatura pa se čuka metalni predmet i izvaja u neki oblik, pa se polako 'ladi a i dalje čuka.

U ovom algoritmu se prvo nađe neko najobičnije rešenje, zatim se to rešenje tvikuje (malo se promeni) i gleda kakvo je u odnosu na prethodno. Ako je bolje super, usvajamo ga, ako nije onda po nekoj verovatnoći usvaja. Jer lošije rešenje može u nekoj sledećoj iteraciji voditi u bolje. Usvajanjem ponekog lošijeg rešenja se izbegava nalaženje nekog lokalnog minimuma koji je daleko od globalnog.

E sad da se ne bi mlogo lutalo ta vervatnoća da se usvoji lošije rešenje se iz ciklusa u ciklus smanjuje. To podražava smanjenje se temperatura metala pri kaljenju, što je metal ladniji teže ga je oblikovati. A verovatnoća usvajanja lošijeg rešenja zavisi i od toga koliko je to rešenje lošije. Ako je mlogo loše onda je mala verovatnoća da ga usvojimo.

Znam da vam ništa nije jasno Evo primer primene algoritma. Setite se problema trgovačkog putnika. Postoje algoritmi ali su oni NP-kompletni (u prevodu, teški u p.m za više od 30 čvorova). E sad Simuliranim kaljenjem se dobija rešenje blisko optimalnom ako ne i optimalno (ako vas baš ukenja).

I kako to radi? Pa uzme se neka putanja. Može nasumična može sistemo najbližih čvorova (ovo je bolje početno rešenje). Pa se onda u tom rešenju zamene mesta nekih čvorova i izračuna nova dužina i poredi sa prethodnom. Ako je bolja usvaja se rešenje, ako nije ide po onoj verovatnoći. I tako se iz ciklusa u ciklus smanjuje temperatura sve dok ne padne na neku zaustavnu a pamti se najbolje rešenje. Prosto ko pasulj

Nemojte da vas uplaši kod, to je prost jezik, a naveći deo koda odlazi na štampanje, što vam nije potrebno da razumete jer je to pythonizovan matlab.

Prvo pravimo klasu Grad koja će predstavljati jedan čvor u grafu (__init__ metoda je konstruktor u Pythonu):

Potom prvimo klasu za rešenje koje se sastoji od redosleda gradova koje treba obići.  Ima metodu za dužinu rešenja (vrednost funkcije cija što bi rekli ćelavi matematičari), metodu za tvikovanja i jednu pomoćnu za grafike:

I konačno klasa u kojoj se simulirano kaljenje obavlja. U konstruktoru se prihvata početno rešenje a u metodi start() se dešava ćudo, sa namenim ć :) :

Ovoj se klasi dodaje i metoda za prikaz rešenja u grafičkom obliku preko matplot biblioteke (i svet to besplatno i slobodno):

I na kraju puštamo u pogon ovu skalameriju koja uz to i radi :)

I jedan od rezultata može se prikazati graficima (rezultet metode stampaj_resenje):

Zna li ko kako da se postuje kod na ovom glupom blogu, otelih se slikajući i uploudovajući slike i razmeštajući ih na pravo mesto...

Zdravo svete iz Flex-a

Dugo me nije bilo, zaboravio sam i kako da se ulogujem :) Ali pokušaću da od sada pa na dalje i u buduće budem vredniji. Materijala za pisanje imam dovoljno, samo volje i vremena da nađem... A vidim da su i drugi blogeri zaspali i da nisam najgori od sve dece :)

Čitao sam Misliti na javi 4. izdanje i u poglavlju o GUI-u se pominje nekoliko alternativa za SWING. Najviše me je zainteresovao Flex kao flash frontend za javu, i ne samo to, kao zgodna stavrčica za Web i prilika da se podsetim JavaScript-a, prvog jezika kog sam naučio posle COBOL-a :) Delovao je tako osvežavajuće. Doduše Flex koristi malo drugačiji JS pod nazvom ActionScript, a ni JS nije više igračka kao pre 8 godina.

Vraški mi je bilo teško naći link za sam Flex SDK. Mnogo kliktanja i paženja da se ne skine Flex Builder, što ti Adobe uporno pokušava uvaliti. Za one koji bi da se ne smaraju i odmah skinu SDK link je http://download.macromedia.com/pub/flex/sdk/flex_sdk_3.zip One file to rule them all, odnosno isti zip za Linux, MacOSX i Windows. Instalacija se sastoji u odzipovanju :)

Flex ima sopstvetni XML zapis GUI-a koji se zove MXML (Macromedia XML). Skript kojim se kontrolišu GUI elementi može biti direktno stavljen u MXML ali može biti linkovan u drugoj datoteci kao u HTML-u. Slično tome moguće je MXML tagove dekorisati CSS-om.

Kod izgleda ovako:


a rezultat je:


Prevođenje mxml datoteke u swf se obavlja pomoću komande:
direktorijum_gde_je_sdk/flex_sdk_3/bin/mxmlc zdravosvete2.mxml

Flex je mnogo vezan za Adobe, izgleda da za bilo šta ozbiljno mora da se kešira. Ali tu je i otvorena varijanta OpenLaszlo

Toliko za sada a možete očekitavti i tekst o interakciji flex-a sa javom.

Izmena: Adobe je otvorio flex pre nekoliko meseci i sada naplaćuje samo FlexBuilder. Živeo slobodni softver!!!

Zalazak izvršnog koda

Svi znamo kako je tekao razvoj programiranja i programskih jezika, od mašinskog koda, preko asemblera pa do današnjih viših programskih jezika. Svaka generacija se naslanjala na prethodnu i svodila je na najmanju moguću meru.

Danas prisustujemo još jednoj smeni. Jezici čiji se kod kompajlira u izvršni polako bivaju skrajnuti. Na TIOBE listi od 10 prvoplasiranih jezika samo 3 su klasična. Pri tom je moguće da delphi sklizne sa top 10 liste, a java već godinama vodi.

Šta je uzrok tome? Sve je u parama prost je odgovor. A pravi odgovor je malo složeniji. Glavni razlog je sniženje troškova razvoja i održavanja. Da bi jezik bio produktivniji mora da se izdigne iznad mašine, da postvi debeo izolacioni sloj. Pri tom taj izolacioni sloj dovodi do još jednog efekta a to je lako postizanje platformske nezavisnosti što su neki jezici postvili kao cilj (npr. java) a drugi su bili pragmatični pa su se poveli onom: sve može, a i ne mora, kao u pythonu. Zato se već godinama nije pojavio novi jezik a da je prevodio kod u izvršni (native code) osim projekta jezika D.

Pošto je ovaj razlog stalno prisutan mora da ima još nešto. Rad programera je sve skuplji, a mašina je sve jeftinija. I ne samo to, mašine su sada dovoljno snažne da ne moraju direktno koristiti izvršni kod. Količina biblioteka i softvera napisanog u klasičnim jezicima je dovela do toga da se programiranje u većini slučajeva svodi na pozivanje tog koda koji je već isprogramiran i preveden u izvršni. Npr. PHP je mnogo sporiji od C-a. Ipak za web se programira u PHP-u jer najveći deo obrade nekog web zateva izvršava baza koja je pisana u C-u. PHP samo poziva kod baze i to je par procenata ukupnog vremena a za tih par procenata niko neće da se bakće C-om.

I sami interpreteri koriste kod od ranije i ubrzavaju izvršenje za razliku od starih interpretera. Klasična je priča o upređivanje javine i C implementacije Linpack algoritma. Pokazuje se da nema razlike u brzini, što i ne čudi obzirom na to da se najveći rad u algoritmu svodi na numerička izračunavanja a oba jezika za to koriste istu BLAS biblioteku programiranu u FORTRAN-u :)

Moderni jezici ne koriste priglupe interpretere koji su izvršavali liniju po liniju izvornog koda. Danas se često izvorni kod prevodi na međujezik, imamo inteligentne virtelne mašine koje analiziraju kod, pronalaze uska grla i optimizuju ga, odlučuju da li da objekat alociraju na heap-u ili stacku, primenjuju različite algoritme sakupljanja smeća zavisno od situacije...

Došlo se do novih otkrića i rešenja kod VM. Tu su nove arhitekture, primena niti, novi algoritmi za optimizaciju. To je dovelo do toga da se sad new operator u javi izvrši u nekoliko taktova brže nego najbrža implementacija malloc funkcije u C-u a pri tom JVM uz alokaciju radi i inicijalizaciju memorije.

Šta se danas događa kod jezika sa VM? Primetno je stremljenje ka razdvajanju jezika i VM. Sad je situacija da se jedan jezik izvršava na više VM i da jedna VM može da pokrene više jezika. Za to je potrebno napisati mini interpreter. Pokušava se sve više da se olakša pisanje tih mini interpretera kako bi VM mogla da podrži više jezika. Npr. u JVM 1.6 se to znatno olakšava i samo je potrebno napisati određen pllugin, a plugin za JavaScript se dobija uz JVM.

Postoje i pokušaji da se naprave zajedničke VM za nekoliko jezika. Za Perl, Python i PHP se radi jedna takva mašina. MS se otvorio ka raznim jezicima. Najnovija je podrška pythonu preko IronPython-a. To omogućava da se koriste standardne i druge biblioteke nekog drugog jezika samim izvršavanjem u VM tog jezika. Npr. da se iz pythona koristi SWING i Hibernate. I više od toga: da se python kod prevede u javin bajtod i korsti iz jave ili bilo kog jezika na JVM. Moguće je i odbratno da se bibiliteke u drugom jeziku prilagode VM preko omotavanja, tj. dekorator obrasca. Npr. u pythonu je moguće koristiti QT GUI biblioteku programiranu u C++ preko PyQT omotača.

Sve to dovodi do snažne sinergije. Više nije bitno ko u čemu šta piše. Izbor postaje velik. Svako može da osmisli svoj jezik za neku specifičnu namenu (domain specific) i to implementira za neku VM. Ruše se ograde između jezika i između platformi.

3 džepna linuxa

Juče sam se igrao sa 3 mala linuxa, ali moćna kao uvek:

• Damn Small Linux verovatno najmanji i najmanje zahtevan linux uopšte. Iako je mali ima sve što mu treba. Automatski mi je prepoznao mrežnu karticu i konfigurisao mrežu. I ostala hardverska podešavanja je uradio automatski. Mana je što ne podrzava NTFS sistem ili bar meni nije pošlo za rukom da uradim mount. GUI je Fluxbox, što će reći da nije lepotica. Kernel je generacije 2.4.* Pozitivna stvar je i to što preko Knoppixa ima Debian korene a to znači da sa apt-getom nema problema. Veličina mu je samo 49 MB a autori tvrde da im je gornji limit 50 MB. Podiže se i na 486DX mašinama sa 16 MB RAM. Postoji i embedded izdanje koje pomoću QUEMU VM može da se vrti i na Win i na Linux OS i to sve radi jedna ista verzija! Što je još neverovatnije uspeli su da stave još jedan window manager JVM koji koristi i Puppy linux. Sledi slika DSL sa Fluxbox wm:

  



• Austrumi 1.2: poslastica iz Letonije. Automatski je podesio sve osim mreže. A za to korsiti prilično bazične alatke u tekstualnom modu (netconfig). Trebate znati sve parametre mreže, a posle toga nema problema. GUI je E17 koji jos nije u finalnoj verziji ali je najvažnije da je izuzentno napredan i lep a pri tom lagan. Kernel svežiji nego kod novog Ubuntua. Jest mali ali nije zaostao. Automatski je mountovao ntfs particiju. Učitava se u potpunosti u RAM, čak izbaci CD iz drajva kad završi. Vidi se da je malo nedovršen, dosta je grešaka što u njemu što u E17, ali da ima potencijala da bude najpotpuniji mali linux. ISO fajl je 49,5 MB a za pokretanje traži 128 MB. Moguće je intalirati ga na hdd:

  



• Puppy 1.09CE: Mnogo smara kod boota. Dok su prethodna 2 sve sama podesila ovaj samo zapitkuje u text modu. Ali to je prvi linux koji je zalajao na mene. Ako pri podešavanju zvukačujete AV nemojte se uplasiti, ne ujeda :) Koristi JWM kao GUI. Po lepoti je negde blizak Fluxboxu. Nije konfigurisao mrežu ali ima wizard koji sa par kliktanja sam pronalazi mrežu. Inače nisam nigde video toliko wizarda, ima čak i wizard za wizard (ne šalim se bukvalno tako piše). Puppy iso fajl ima 62 MB. Troši manje memorije nego Austrumi samim tim što ne mora da se sav učita u RAM, mada ta opcija postoji. Kernel je 2.4 generacije. Nisam uspeo da mountujem ntfs particiju.

  

Damn Small i Puppy se mogu lako prilagoditi dodavanjem modula na CD. Imaju mogućnost da zapamte podešavanja na USB, a Puppy čak može sam sebe da doreže sa novim podešavanjima ako je CD u rezaču. Sva tri linuxa se mogu instalirati i na hard a Puppy i DSL i na USB, zipdrive, Compact Flash drive itd. Bilo kuda linux svuda! Problem sa mountovanjem dolazi iz činjenice da kernel verzija 2.4 ne podržava direktno NTFS, a i kad se podrška uključi ona je read only. Tako je sve do kernela 2.6.15 mada i tu postoje problemi sa fajlovima manjim od 512 B. Problem sa zatvorenim kodom jedne velike firme sitnih duša (pesničko nadahnuće :) ). Drugi uzrok je što imam novi hard SATA 2 (koji se kao uređaj u linuxu prijavljuju sa /dev/sda). Šteta što nisam imao FAT32 particiju na njemu čisto da vidim da li bi se i to mountovalo.

Prvo pa muško, pa se zove Persa :)

Svečano otvaram blog, nek nam je živ i zdrav!

Šta će svega na njemu biti, ko to zna. Važno je da se krenulo, pa će se stići vremenom.