Metode inspirate din natura in contextul web semantic

Budai Steliana: steliana@infoiasi.ro

Gorea Alexandra Diana: alexandra.gorea@infoiasi.ro

Webul semantic a creat diferite oportunitati in a explora informatiile prin diferite metode. Acum conteaza cat de repede putem avea acess la informatii. In acest scop, multi cercetatori s-au inspirat din natura in gasirea de solutii pentru a optimiza cautarea. Surse de inspiratii pot fi: psihologia, invatarea automata si masini de intare, algoritmi genetici, retele neuronale si cautari exhaustive. S-au apelat la aceste domenii deoarece volumul de informatii este estrem de mare, iar dorinta umana este de a primi tot ceea ce cauta intr-un timp cat mai scurt cu o calitate cat mai buna a informatiilor.

O sursa de inspiratie este si sistemul uman imunitar si se poate dezvolta o analogie intre anticorpi si interogari. Anticorpii importanti sunt acei care au fost activati de catre infectie. Acesti anticorpi sunt stimulati sa se multiplice ce pot da posibilitatea crearii de anticorpi similari sau chiar mai puternici pentru a infrunta infectia, decat ceilalti. Analog, interogari ce aduc rezultate relevante pot fi clonate pentru a da nastere unor interogari similare ce poate fi o imbunatatire a interogarii originale. Webul semantic contine un set de reguli pentru a crea interogari expressive, standardizate. Un concept inspirit din natura este combinarea unor arii de cercetate diferite precum: semantic web, sistemul imunitar arficial (AIS ), Expansiune interogari (QE – Query Expansion) si Preluare de Informatii (IR – Information Retrieval).

AIS este o arie noua de cercetare cu o aplicare diversificata, precum data-mining, securitate si cibernetica. Notiunile de interogari AIS pentru interogari semantice arata, utilizand ontologia genelor ca un exemplu, cum datele pot fi preluate bazate pe principiile imunitatii pentru interogari expansionale.

Implementari concrete:

O retea bazata pe posibilitatea de cautate semantica a fost dezvoltata cu infrastructura AIS implementata in ea. Un nivel inalt de ultilizare este arata in fig urmatoare si este de asemenea important la acest nivel sa se stabileasca maparea dintre AIS si BIS ( Biological Immune System – paradigma cloneaza si finiseaza – un corb expus la un antigen produce diferiti anticorpi, dintre care o parte sunt mult mai potriviti pentru a invinge infectia. O parte din anticorpi pot fi autoreactive ce trebuiesc distruse pentru a nu provoca o reactie autoimuna. Este adusa ideea pe teritoriul expansiunii interogarilor pentru a stabili o anologie intre anticorpi si interogari, finisand procesul de cautare prin clonarea expansiunii, a mutatiilor si depistarea interogarilor autoreactive). In sistemul AIS se vor pastra rezultatele

irelevante ca individ si rezultate relevante ca neindivid. Anticorpii sunt interogari semantice si antigenele sunt o colectie de rezultate relevante sau neindivizi. In final mutatia este echivalenta cu expansiunea interogarii. Astfel mutatie unei interogari poate duce la o interogare care este cea mai potrivita pentru o criteria de cautare particulara. Dar ar putea rezulta si interogari ce ar putea returna rezultate irelevante - aceste vor fi distruse.

Infrastructura AIS si fluxul informatiilor

Imagine preluata din articolul AIS and Semantic Query (link-ul 1 din bibliografie)

Interfata procesului de cautare este descrisa intr-un mod in care ii arata utilizatorului modul in care expansiunea interogarii este executata. La inceput utilizatorul alege o organizatie de interes particulara.

O alta sursa de inspiratie o reprezinta retelele neuronale. O conditie necesara importanta in succesul cercetarii in web semantic, o reprezinta constructia unui domeniu de ontologii complexe si usor de folosit. Construind ontologii inca necesita timp si o munca complexa, necesitand un grad inalt de supervizare si fiind un streang in dezvoltarea tehnologiei webului semantic. Procesul de imbogatire a domeniul de ontologii are doua intrari, o ontologie existenta – ce are rolul de cunostinte generale, si corpul text al domeniului.

Se ofera o idee pentru a adapta o ontologie data conform unui domeniul sprecificat. Se va imbogati coloana erarhica a ontologiei existente, a taxonomiei, cu concepte noi pentru domeniu – specificat extrase din corpus.

Se propune un framework pentru updatarea taxonomiei ce este bazat pe un model extins al hartilor ierarhizate, ce reprezinta o arhitectura de retea neuronala nesupervizata

Candidatii pentru etichetele conceptelor nou inserate, sunt termeni colectati prin explorarea corpulul de text. Procesul de extractie a termenului se bazeaza pe recunoasterea tiparele lingvistice (fraze substantiv), in documentele domeniului de corp. Fiecare termen codifica informatii de continut contextuale, intr-un spatiu vectorial de repartitie. caracteristicile de context a unui termen lung sunt frecventele de aparitie sale in diferite documente ale corpului. Clasificarea termenilor extrasi in taxonomie a unei ontologii de date continua prin asocierea fiecarui term cu un nod tinta din taxonomie, bazat pe o similitudine in spatiul vectorial de repartitie. Acest termen devine un nou concept adaugat la taxonomie, si este atasat ca succesor sub nodul tinta.

Modelul neuronal ierarhic nesupervizat, in general, incepe cu o dezvoltare dinamica a unei taxonomii de tip arbore de la un singur nod initial. Modelul utilizat ca exemplu de niste cercetatori, numit Enrich-GHSOM, este o extensie de unul dintre aceste sisteme existente, GHSOM, si permite dezvoltarea dintr-un arbore dat initial. Taxonomia care face obiectul de imbogatire este este dat ca starea initiala a harti ierarhice auto-organizata. Astfel, o structura de cunoastere simbolica esentiala - arbore taxonomic, este convertit intr-o reprezentare neuronala in starea initiala a unei harti ierarhice auto organizate. Dezvoltarea actualei taxonomii are loc prin invatarea unei retele neuronale nesupervizateprin expunerea hartii ierarhice auto organizate initializate la un vector reprezentare a termenilor extrasi din corpul domeniului. In revers, o translare neural simbolica este terminate dupa procesul de dezvoltare. Acum acesta reprezinta pasul de invatare a carui output este taxonomia finala dezvoltat. Mediul acesta de dezvoltare este in stadiul hibrid ce trebuie sa ofere suport si pentru integrari neuronale. Translatia neuronal simbolica in ambele directii au fost obtinute in mod natural in timp ce acest framework pur si simplu functioneaza pe structura taxonomica a antologiei, ce este in concordanta structurii erarhice a retelei neuronale auto organizate.

Conditia cea mai importanta pentru succesul cercetarii Semantic Web este construirea de domenii de ontologii complete si fiabile. Se vor da exemple de cadru neservizat pentru dezvoltarea domeniilor ontologice bazat pe descoperirea unui corp domeniu text. Mai exact, se doreste dezvoltarea a unei coloane vertebrale ierarhice a unei ontologii existente, exemplu taxonomia acestuia, cu conceptele noi specifice alte domeniului. Cadrul se bazeaza pe un model extins de harti ierarhice auto-organizate. Fiind intemeiat pe o arhitectura de retele neuronale nesupervizate, cadrul poate fi aplicat la diferite limbi si domenii. Termeni extrasi din exploatarea unui corpus de text codifica informatii contextuale de continut, intr-un spatiu vectorial de repartitie.

O cercetare mai ampla se gaseste in articolul intitulat Text-Based Ontology Enrichment Using Hierarchical Self-organizing Maps (http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-419/paper6.pdf)

Semantic web explicat prin Swarm Intelligence

Sistemul de rationamente semantic web sunt confruntate cu greutatea de a procesa resurse dinamice , distribute in continua crestere. Se propune un mod nou de abordare a grafului transversal RDF, exploatand avantajele inteligentei Swarm. Metodologia inspirata din natura este realizata de multimi autonome auto organizate, entitati usoare ce tranverseaza grafurile RDF prin anumite cai, urmarind a instantia regurile inferente bazate pe paternuri.

Rationarea si Inteligenta Swarm: Este mai putin recunoscuta ca o abordare adaptativa spre rationalizari robuste, scalabile si distribuite ce sunt necesare in a exploata valoarea completa a datelor unui Semantic Web dinamic in dezvolatare. Determinarea locala este o optiune interesanta ce suporta publicari descentralizate ce are un potential de a respecta provenienta datelor ce permite utilizatorilor in a pastra controlul intimitatii si a apartenentii la grup si propagarea informatiilor lor. Un alt avantaj in rationalizarea propagate, o reprezinta capacitatea de a se integra natural in mod constant datele modificate. Adaptabilitate, robustete si scalabilitate sunt un grup de proprietati a multimilor si pot fi atribuite principiilor de baza lipsa unui control central,localizarea si simplitatea. De aceea combinarea rationalizarii si inteligentei Swarm pot fi o abordare promitatoare in a obtine performanta. Se propune un model a unui sistem descentralizat si se testeaza daca inteligenta swarm poate contribui in a reduce costurile computationale pe care le implica modelul si face aceasta paradigma de rationalizate nou o alternativa reala in abordarea curenta. In scopul calcularii inchiderii RDFS peste un graf RDF G, se aplica un set de reguli aplicate repetat triplelor din graf. Aceste reguli sunt formate de o contitie prealabila ce contine una sau doua triple ca argumente si o actiune ppentru a adauga un triplu in graf.

Acest process este terminat in urma indexarii triplelor si unirea rezultatelor a doua interogari. Prin inteligenta Swarm se da o alternative fara indexare pentru rationalizare asupra unei retea larga de grafuri RDF distribuite dinamic. Ideea este ca multimi de entitati simple traverseaza in mod autonom graful, fiecare reprezentant o regula de rationalizare ce poate fi partial instantiate. Entitatile pot comunicaa local si indirect. Atunci cand conditiile unei reguli se potriveste cu un nod, se adauga un nou triplu derivate. Se presupune ca Webul Semantic in acest caza poate fi vazut ca o colectie conectata de retele de date, ce este continuu updatata de catre entitati. In acest context, doar regulile de rationalizare active se misca in retea si nu datele, minimizand astfel traficul de pe retea, ca schema de date este mai putin numeros decat ca instante de date.

Ideea modelul rationalizarii este ca entitatile se deplaseaza prin graf folosinf varfurile. Rationalizarile RDF pot fi descompluse natural de distribuirea complementara a regulilor implicate in membrii multimii, astfel ca fiecare individ este responsabil de aplicarea unei reguli. Entitatile sunt instantiate automatic prin

considerarea schemei de date in graf. Daca o schema concreta de triplu a unui anumit patern este gasita, o entitate de rationalizare este generata.

Detalii despre aceasta idee se gasesc in articolul „Semantic Web Reasoning by Swarm Intelligence” de la adresa http://kcap09.stanford.edu/share/posterDemos/149/paper149.pdf

Modele inspirate din similaritati umane utilizand masini learning

Exista patru teorii ce incearca sa rezolve problema reprezentarii datelor in web semantic cand vine vorba de inspiratie umana, si s-a venit cu diferite idei in reprezentarea similaritatii in cautare cat msi eficient si mai rapid. Putem gasi multe surse de inspiratie din psihologia umana. Un agent rationeaza inductiv si deductiv, urmareste legaturile cauzale, rezolva probleme si ia decizii, dar problema este cum putem reprezenta datele. Limbajul standard in web semantic este RDF a carui concepte fundamentale sunt resursele, proprietatile si afirmatiile. Astfel se incearca modelarea lunii prin formalism.

Conceptul similaritatii este diferit in psihologie fata de masini learning ce foloseste reprezentari structurate. Diferente mari apar atunci cand grupuri de masini learning deseori folosesc reprezentatii ce nu sunt acceptate de psihologie. Un exemplu in acest sens: WordNet chiar si interogari Google.

O teorie ce incearca sa rezolve aceasta problema ar fi: caracteristici continue in modelul spatial. Se spune ca psihologii pot utiliza spatiul metric ca un model intern reprezentativ pentru aproape fiecare stimul (forme. Intensitati, semnale, morse). Rar s-a intamplat sa se gaseasca doua situatii identice in acelasi timp. Tot timpul apar schimbari in mediu. Modelul spatiului vectorial, din obtinerea informatiilor, mizeaza pe aceasta. Se grupeaza cuvinte intr-un spatiu cu atat de multe dimensiuni cate concepte exista in tot. Modelul cedeaza atunci cand un text foloseste, de exemplu, sinonime pentru a exprima mesaje similare.

O alta idee in rezolvarea situatiei, inspirata din teoria lui Shepard, ar fi analiza latenta semantica (Latent Semantic Analysis-LSA) ce solutioneaza oarecum prin rularea unei singure valori de analiza (SDV). Dar nici aceasta solutie nu este fara probleme, negatia nu functioneaza pe unele modele spatiale. LSA utilizeaza un set de cuvinte atunci cand ordinea cuvintelor nu mai conteaza. O propunere in Web Semantic este o operatie ce ruleaza intr-un corp static. O idee, folosirea unui corp larg, iar dimensiunile reprezentate prin articole etichetate. De exemplu, fiecare text poate fi un vector cu similaritati ale articolelor de pe Wikipedia.

O a treia idee, sub numele de model teoretic ale seturilor distorsionate, pleaca de la abordarea teoretica a lui Tversky, ce considera ca similaritatea este o relatie asimetrica ce s-a dovedit ca nu functioneaza (de aceea a si fost foarte mult criticat).

Reprezentari structurate castiga o parte din puterea lor din abilitatea de a crea reprezentari ce in ce mai complexe ale unei situatii prin implementarea relatiilor

in alte relatii pentru crearea unor structuri relationale. Aceste structuri de nivel superior pot codifica elemente psihologice importante cum ar fi relatiile cauzale si a implicatii. De fapt, RDF ca o structura de date are aceasta proprietate (corectare, de asemenea, numita compozitionalitate). In prezent, compozitionalitatea este greu sa implementeze pentru modele metrice si modele caracteristice.

Modele teoretice de seturi discrete: Ideea pleaca de la abordarea teoretica a lui Tversky ce considera ca simetria este o relatie si are la baza campul Bayesian este dezvoltata de Griffiths, Steyvers si Tenenbaum, ce propun o reprezentare ce poate fi un limbaj de caracteristi discrete si generative de modele Bayesiene in loc de spatii continue. Modelul topic este deci un model caracteristic deoarece "asocierea dintre doua cuvinte este dezvoltata de fiecare topic ce asigneaza o probabilitate mare la ambele si este scazuta de topic ce asigneaza probabilitatea la una dar nu si la cealalta, int-un mod in care caracteristici comune si distinctive ar trebui sa afecteze similaritatea."(Tverksy)

La nivelul implementarii, acest model nu este intensic - memorabil, are la baza lanturi Markov si modelul Montecarlo.

O alta idee face referile la modele ierarhice si modele bazate pe aliniere. Structura modelelor mapate este cea mai apropiata structura fata de RDF. Acest model poate fi un model activ de imprastiere, ce consta dintr-o retea de noduri ce reprezinta toate posibilitatile de corespondenta caracteristica la caracteristica, obiect la obiect si rol la rol intre stimulii comparati. Activarea unui nod particular indica teoria unei corespondente ce o reprezinta. Se testeaza maparea unu cate una ca o constrangere slaba.

Si nu in ultimul rand, o solutie mai plauzibila in rezolvarea situatiilor: modele bazate pe distanta transformationala. In teoria distantei transformationala, similaritatea a doua entitati este invers proportional cu numarul de operatii necesar pentru a transforma o entitate astfel ca ea sa fie la fel cu cealalta. Acest model rezolva multe probleme, pe care celelalte nu le poate rezolva. Se pleca de la ideea reprezentarii distorsionate a lui HAHN si Chater ce utilizeaza o transformare numita complexitatea Kolmogorov iar masura similaritatii poate fi definita ca lungimea celui mai scurt program ce produce x ca iesire dandu-l pe x ca input, de fapt, cate instructiuni sunt necesare reprezentarii x sa produca y. Alta abordare a acestui model o reprezinta teoria stringului editat ce are la baza ideea ca un string poate fi transformat rapid in al doilea string utilizand serii de operatii de editare , operatii simple de transformare ca inserare stergere potrivire si substituire.

Ambele XML si RDF au la baza o structura arborescenta, si astfel arborele de editare distanta este o subclasa a teoriei de editare siruri.

Acest subiect este dezbatut pe larg in articolul „Human Similarity theories for the semantic web” din adresa http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-419/paper7.pdf

O alta sursa de inspiratie in acest domeniul il reprezinta algoritmii genetici. Ei au fost implementati pentru a optimiza alinierea ontologiilor, o problema care se poate realize prin cautari exhaustive doar pentru un numar mic al masurii similaritatii.

Alinierea Ontologiei este un aspect cheie in scopul de a face schimb de cunostinte in aceasta extensie a Web pot fi reale; ea permite organizatiilor sa modeleze cunostintele lor proprii, fara a trebui sa ramanem la un anumit standard. De fapt, exista doua motive bune de ce cele mai multe organizatii nu sunt interesate de a lucra cu un standard pentru modelarea propriilor cunostinte: (a) este foarte dificil sau scump pentru multe organizatii de a ajunge la un acord cu privire la un standard comun, si (b) aceste standarde nu se potrivesc cu nevoile specifice tuturor participantilor la procesul de standardizare. Astfel alinierea ontologiei este, probabil, cea mai valoroasa cale de a rezolva probleme de eterogenitate si, chiar exista o multime de tehnici pentru alinierea ontologiilor intr-un mod foarte precis, experientele ne spun faptul ca natura complexa a problemei de rezolvat face dificil ca aceste tehnici sa opereze intr-un mod satisfacator pentru toate tipurile de date, in toate domeniile spre asteptarile utilizatorilor.

Ca un rezultat, tehnici care combina metodele existente au aparut. Scopul acestor tehnici este de a obtine un algoritm de potrivire mai complex si precis. O modalitate de a combina acesti algoritmi de potrivire sub cercetare exhaustiva. Si astfel se propune un mecanism, diferit fata de cele care exista, pentru a calcula functia optima pentru alinierea seturi arbitrare de ontologii precum si posibilitatea suplimentara de a obtine rezultatele dorite, pentru a optimiza unele dintre caracteristicile unei iesiri aliniate.

Algoritmii de potrivire se impart in mai multe tipuri (conform articolului Optimizing Ontology Alignments by Using Genetic Algorithms)

1. Normalizare sir. Aceasta consta din metode precum eliminarea cuvintelor sau simbolurilor nefolositoare. Se foloseste pentru a detecta substantive la plural si poate lua in considerare chestii legate de limbajul natural.

2. Asemanarii de siruri. Similaritatea textului este o metoda bazata pe siruri pentru a identifica similaritatile entitatilor de nume.

3. Comparatie de tipuri de date. Aceste metode compara tipul de date din elemente ale ontologiei.

4. Metode de lingvistica. Aceasta consta in includerea de resurse lingvistice , cum ar fi lexicoane si tezaure pentru a identifica posibile simililaritati. De exemplu WordNet pentru a identifica unele tipuri de relatii intre entitati.

5. Analiza de mostenire. Aceste tipuri de metode iau in considerare legaturile dintre concepte pentru a identifica relatii.

6. Analiza datelor. Aceste tipuri de metode se bazeaza pe regula: Daca doua concepte au aceleasi instante, acestea vor fi, probabil, similare. Ne uitam la cazurile oferite pentru a ne da seama din ce atribut fac parte.

7. Mapare grafica. Aceasta consta in identificarea structuri grafice similare in doua ontologii necesitand algoritmi grafici pentru a facec acest lucru.

8. Analiza statistica. Acesta consta in extragerea de cuvinte cheie dintr-o descriere pentru a detecta intelesul entitatilor in relatie cu alte entitati

9. Analiza Taxonomica. Se incearca identificarea conceptelor similare prin conceptele legate de ele. Doua concepte ce apartin ontologii diferite, au o oarecare probabilitate ca cele doua sa fie similare daca au acelasi vecin

Ideea de baza este de a combina valori similare prezise prin mai multi algoritmi simpli pentru a determina corespondente intre entitati ce apartin unor ontologii diferite.

Acest cod este un exemplu de o iesire dintr-o evaluare a unui proces de aliniere unde doua ontologii din referite standard au fost aliniate.

Cod 1 Exemplu de aliniere de Evaluare <? xml version = '1 .0 'encoding =' UTF-8 "standalone = 'Da'?> <rdf: xmlns rdf: RDF = 'http://www.w3.org/1999/02/22-rdf-syntax-ns #' xmlns: harta = 'http://.../projects/ontology/ResultsOntology.n3 #'> <map:output rdf:about=''> <map:input1 rdf:resource="http://.../benchmarks/101/onto.rdf"/> <map:input2 rdf:resource="http://.../benchmarks/204/onto.rdf"/> <map:precision> 1.0 </ harta: de precizie> <map:recall> 0.6288 </ harta: rechemare> <fallout> 0.0 </ Fallout> <map:fMeasure> 0.7721 </ harta: fMeasure> <map:oMeasure> 0.6288 </ harta: oMeasure> <result> 0.6288 </ rezultat> </ harta: iesire> </ rdf: RDF> (conform articolului Optimizing Ontology Alignments by Using Genetic Algorithms – link-ul 2 din bibliografie)

Metodologia de aplicare a unui GA necesita definirea unor strategii:

- Caracterizeaza problema prin codificare intr-un sir de valori a continutului unei solutii temporare

- Furnizeaza o functie numerica fittness, care va permite de a cota calitatea relativa a fiecarei tentativa de solutie dintr-o populatie.

In acest context, o alta idee ar putea fi bazata pe pe tehnici de protrivire Masini learning ce se impart in doua categorii: feedback de relevanta si retele neuronale:

- Ideea din spatele feedback-ului de relevanta este de a lua in considerare rezultatele, care sunt initial returnate de la o interogare data si de a utiliza informatii despre indiferent daca sunt sau nu aceste rezultate sunt relevante pentru a efectua o noua interogare:

- APFEL (Alignment Process Feature Estimation and Learning) este o abordare machine learning care exploreaza validarea alinierii initiale pentru optimizarea automatica a parametrilor de configurare a unor strategii de masina in sistem precum greutatea pentru un task de potrivire dat.

- Retele neuronale sunt modelari statistice non-lineare de date sau de decizie. Ele pot fi folosite pentru a modela relatiile complexe intre intrari si iesiri sau pentru gasi asemanari intre modele de date. SFS este un instrument pentru ontologii meta-matching ce incearca sa obtina in mod automat un vector de greutati pentru diferite aspecte semantice pentru un task de potrivire, precum compararea numelor conceptelor, comparatii a proprietatilor conceptelor, comparatia relatiilor conceptelor. In acest caz se folosesc retele neuronale.

Exemple si implementari, precum si rezultatele unor experimente se pot gasi in articolul Optimizing Ontology Alignments by Using Genetic Algorithms (http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-419/paper2.pdf)

Algoritmi genetici pot fi utilizati deasemenea in optimizarea rutelor de interogare RDF. In ciuda eforturilor actuale, o inplementare reusita a unei aplicatii care este in masura sa interogare de mai multe surse eterogene pare inca departe. Un interesant camp de cercetare in acest context este determinarea unei rute de interogare: ordinea in care diferite parti dintr-o anumita interogare sunt evaluate. Timpului de executie a unei interogari depinde de acest lucru. Un algoritm bun pentru determinarea rutei de interogare poate sa contribuie la o interogare rapida si eficienta.

In contextul web-ului semantic, unele cercetari in acest domeniu s-au facut deja: un algoritm bazat pe imbunatatirea iterativa, urmat de simulated annealing(SA), de asemenea, mentionat ca algoritm cu doua faze de optimizare (2PO), adresat pentru a determina ruta optima de interogare. Dar, alti algoritmi nu au fost folosit pentru determinari rute pentru interogari RDF, in timp

ce AG s-au dovedit a fi mai eficient decat SA in cazul unor caracteristici similare. De exemplu, un GA se comporta mai bine decat SA in rezolvarea problemei circuitul de partitionare, in cazul in care componentele trebuie sa fie introduse pe un cip in asa fel, ca numarul de interconexiunilor este optimizat. Problema determinarii rutei de interogare este oarecum similar cu aceasta problema, deoarece parti distinctive ale interogare trebuie sa fie ordonate in asa fel, ca timpul executiei sa fie optimizat. In plus, algoritmi genetici s-au dovedit a genera rezultate bune in medii de interogare traditionala. S-a incercat aplicarea acestor cunostinte traditionale in cazul executiilor interogarilor RDF.

Scopul principal consta ne urmareasca de a cerceta daca o abordare bazata pe algoritmi genetici este mai buna decat un algoritm de optimizare in doua faze pentru a stabili rute de interogare RDF.

Algoritmul in doua faze aleator genereaza random un set de solutii initiale, care sunt folosite ca puncte de plecare pentru o cautare in spatiul de solutii prin punctele vecine.

Daca nu poate fi gasit nici un cel mai bun vecin, atunci acel punct devine un optim local. Cel mai bun optim local gasit in subsecventa este folosit pentru inceputul algoritmului SA.

Un exemplu de algoritm descoperit de cercetatori, BushyGenetic (BG), considera spatiul solutiilor continand interogari stufoase pe arbori de procesare.

Algoritmul BG poate fi adaptat pentru a imbunatati performarta sa intr-un mediu de executii a interogarilor. In instanta algoritmul ar putea fi fortat pentru a selecta solutia cea mai buna pentru proliferare in generatia urmatoare cel putin odata (selectie eletista), incercanduse evitarea pierderii unei solutii bune.

Rezultatele obtinute de catre cercetaori au ajuns la concluzia ca, in determinarea rutei optime de interogare intr-o singura sursa de mediu de executie RDF, un algoritm genetic corect configurat poate depasi performanta algoritmului de optimizare in doua faze in solutie de calitate, in timpul de executie necesar si consistenta in performanta, in special pentru mai multe spatii complexe de solutii. Referitor la timpul de executie, algoritmul genetic, actioneaza mai rau ca algoritmul in doua faze.

Superioritatea algoritmului genetic in raport cu cele doua faze de algoritm de optimizare devine mai clar in corelatie pozitiva cu restrictivitate a mediului (de exemplu, o limita de timp), precum

si complexitatea spatiului solutie. Mai mult, in unele cazuri, procesul de optimizare ar putea dura mai mult decat executarea propriu-zisa a unei interogari.

Dupa cum se observa, acest domeniu a strarnit interes in randul multor cercetatori in a dezvolta solutii fiabile in problemele subliniate in acest studiu. Chiar daca multe dintre ele sunt inca in stadiul de test, sau in faza de concepere, in scurt timp metodele inspirate din natura vor deveni parte integranta a webului semantic.

Bibliografie:

http://books.google.ro/books? id=L6ewgfrnWvwC&pg=PA333&dq=AIS+and+Semantic+Query&lr=&as_drrb_is=q&as_minm_is=0&as_miny_is=&as_maxm_is=0&as_maxy_is=&as_brr=0&cd=1#v=onepage&q=AIS%20and%20Semantic%20Query&f=false

http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-419/ paper2.pdf

http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-419/ paper7.pdf

http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-419/ paper3.pdf

http://kcap09.stanford.edu/share/posterDemos/149/paper149.pdf

http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-419/ paper6.pdf