Browsing Doctoral Dissertations by Title
-
Radojčić, Nina (Beograd , 2018)[more][less]
Abstract: In this dissertation, three NP-hard optimization problems are studied and va- rious computational intelligence methods are considered for solving them, with a special emphasis on the possibilities of applying fuzzy logic in order to improve the performances of proposed methods. In addition, it is shown how fuzzy logic can be incorporated into a model to make it more adequate to real world applications. The first problem considered is the Risk-Constrained Cash-in-Transit Vehicle Routing Problem (RCTVRP) that represents a special case of the vehicle routing problem (VRP). Similar to the classical VRP, the aim is to determine the collection routes from one depot to a number of customers in order to minimize the overall travel distance (or cost). Additionally, the safety aspect of the routed risk constraints are introduced in the case of RCTVRP. The RCTVRP concerns the issue of secu- rity during the transportation of cash or valuable goods (e.g. in the cash-in-transit industry). The other two problems studied in this dissertation belong to the class of loca- tion problems: the Load Balancing Problem (LOBA) and the Max-Min Diversity Problem (MMDP). The goal of the LOBA problem is to locate a fixed number of facilities, such that the difference between the maximum and minimum number of customers served by each facility is balanced. The LOBA model is useful in cases where customers naturally choose the closest facility. The MMDP consists of se- lecting a subset of a fixed number of elements from a given set in such a way that the diversity among the selected elements is maximized. This problem also arises in real world situations encompassing a variety of fields, particularly the social and biological sciences. In order to solve the RCTVRP, a fuzzy GRASP (Greedy Randomized Adaptive Search Procedure) is hybridized with Path Reliking (PR) methodology. Carefully adjusted fuzzy modification incorporated into the proposed GRASP for the RC- TVRP improved its performance. Moreover, in this dissertation a new PR structure is implemented and can be used for other vehicle routing problems. To improve the algorithm’s time complexity, a new data structure for the RCTVRP is incor- porated. The proposed fuzzy GRASP with PR hybrid shows better computational performance compared to its non-fuzzy version. Furthermore, computational results on publicly available data sets indicate that the proposed algorithm outperforms all existing methods from the literature for solving the RCTVRP. For solving the LOBA problem two efficient hybrid metaheuristic methods are proposed: a combination of reduced and standard variable neighborhood search met- hods (RVNS-VNS) and hybridization of evolutionary algorithm and VNS approach (EA-VNS). The proposed hybrid methods are first benchmarked and compared to all the other methods on existing test instances for the LOBA problem with up to 100 customers and potential suppliers. In order to test the effectiveness of the pro- posed methods, we modify several large-scale instances from the literature with up to 402 customers and potential suppliers. Exhaustive computational experiments show that the proposed hybrid methods quickly reach all known optimal solutions while providing solutions on large-scale problem instances in short CPU times. Re- garding solution quality and running times, we conclude that the proposed EA-VNS approach outperforms other considered methods for solving the LOBA problem. EA approach is also proposed for solving the MMDP. Computational experi- ments on a smaller benchmark data set showed that the classic EA quickly reached all optimal solutions obtained previously by an exact solver. However, some of the larger instances of MMDP were challenging for classic EA. Although researchers have established the most commonly used parameter setting for EA that has good performance for most of the problems, it is still challenging to choose the adequate values for the parameters of the algorithm. One approach to overcome this is chan- ging parameter values during the algorithm run. As part of this dissertation this problem was addressed by extending the evolutionary algorithm by adding a fuzzy rule formulated from EA experts’ knowledge and experience. The implemented fuzzy rule changes the mutation parameter during the algorithm run. The results on tested instances indicate that the proposed fuzzy approach is more suitable for solving the MMDP than classic EA. For all three problems addressed whereas the smaller instances that CPLEX was able to solve, obtained optimal solutions were used for comparison with proposed methods and all of the proposed methods obtained these optimal solutions. Moreover, in this dissertation it has been shown that fuzzy logic is a successful tool in modeling the RCTVRP. In this problem the risk constraints are set by using a risk threshold T on each route and thus, the routes with risk larger than T are forbidden. However, in this dissertation the aim is to take into account the probability of being robbed along each route instead of just allowing solutions with routes that satisfy the risk constraints. A new fuzzy model for the RCTVRP is developed which takes into account the value of the risk index of each route and the solutions with lower values of risk indexes on their routes are considered superior. In order to achieve that fuzzy numbers are used in the improved model. Moreover, two mixed integer program formulations of new fuzzy model are developed and presented in this dissertation. The introduced fuzzy model is compared with the model from the literature using an adequate example and the advantages of the newly proposed fuzzy RCTVRP is demonstrated. Computational experiments are performed and the comparison of the two models given in the paper show that the newly presented approach leads to safer routes. URI: http://hdl.handle.net/123456789/4737 Files in this item: 1
tezaNinaRadojicic.pdf ( 1.665Mb ) -
Popstanojević, Zoran (Belgrade , 1963)[more][less]
URI: http://hdl.handle.net/123456789/224 Files in this item: 1
phdZoranPopstojanovic.pdf ( 1.549Mb ) -
Muzika Dizdarević, Manuela (Beograd , 2017)[more][less]
Abstract: Subject of this doctoral thesis is the application of algebraic techniques on one of the central topics of combinatorics and discrete geometry - polyomino tiling. Polyomino tilings are interesting not only to mathematicians, but also to physicists and biologists, and they can also be applied in computer science. In this thesis we put some emphasis on possibility to solve special class of tiling problems, that are invariant under the action of nite group, by using theory of Gr obner basis for polynomial rings with integer coe cients. Method used here is re ecting deep connection between algebra, geometry and combinatorics. Original scienti c contribution of this doctoral thesis is, at the rst place, in developing a techniques which enable us to consider not only ordinary Z?tiling problems in a lattice but the problems of tilings which are invariant under some subgroups of the symmetry group of the given lattice. Besides, it provides additional generalizations, originally provided by famous mathematicians J. Conway and J. Lagarias, about tiling of the triangular region in hexagonal lattice. Here is a summary of the content of the theses. In the rst chapter we give an exposition of the Gr obner basis theory. Especially, we emphasize Gr obner basis for polynomial rings with integer coe cients. This is because, in this thesis, we use algorithms for determining Gr obner basis for polynomials with integer coe cients. Second chapter provides basic facts about regular lattices in the plane. Also, this chapter provides some fundamental terms of polyomino tiling in the square and hexagonal lattice. Third chapter of this thesis is about studying Ztilings in the square lattice, which are invariant under the subgroup G of the group of all isometric transformations of the lattice which is generated by the central symmetry. One of the steps to resolve this problem was to determine a ring of invariants PG and its generators and relations among them. We use Gr obner basis theory to achieve this. Forth chapter covers the analysis of Ztilings in the hexagonal lattice which are symmetric with respect to the rotation of the plane for the angle of 120 . Main result of the fourth chapter is the theorem which gives conditions for symmetric tiling of the triangular region in plane TN, where N is the number of hexagons on each side of triangle. This theorem is one of the possible generalizations of the well known result, provided by Conway and Langarias. Fifth chapter provides another generalization of Conway and Lagarias result, but this time it is about determining conditions of tiling of triangular region TN in the hexagonal lattice not only with tribones, but with nbones. nbone is basic shape of of n connected cells in the hexagonal lattice, where n is arbitrary integer. URI: http://hdl.handle.net/123456789/4503 Files in this item: 1
muzikadizarevic.manuela.pdf ( 33.23Mb ) -
Lazarević, Ilija (Belgrade)[more][less]
-
Lazović, Bojana (Beograd , 2018)[more][less]
URI: http://hdl.handle.net/123456789/4748 Files in this item: 1
B_Lazovic_Doktorska_disertacija.pdf ( 2.269Mb ) -
Šašić, Mane (Belgrade , 1966)[more][less]
-
Vukobrat, Mirko (Belgrade , 1978)[more][less]
-
Lukačević, Mirjana (Beograd , 1974)[more][less]
Abstract: Relativisti6ka hidromehanika je po6ela da se razvija 1914. godine; kada je Ajatajn [1] formulisao izraz za tenzor energije relativisti6kog idealnog fluida i izveo njegove diferencijalne dna6ine kretanja,•ograni6iv6i se pri tome na adijabatska strujanja, kada za fluid vazi karakteristi6na jedna6ina koja vezuje pritisak i gustinu. Jednaine kretanja takvog fluida ispitivao je 1924. godine Ajzenhart (Eisenhart) [2]. On je pokaZao da je, .kada se radio adj.• jabatskom strujanju idealnog fluida, mogu6e prona6i. metriku kola je konformna metrici'prostor-vremena, u odnosu na koju strujne:iinije fluida predstavljaju geodezijske linije. Pri tome je utvrdio i oblik skalarne funkcije pomo6u koje se pomenuta konformna metrika uvodi To su, medjutim, bili samo pojedina6ni, iako veoma zna6aj-. ni rezultati iz oblasti relativisti6ke mehanike fluida. Tek 1937. godine pojavljuje se•prvi rad.koji sistematski.izlaZe relativisti6ku teoriju-idealnog•fluidapo uzoru na odgovaraju, 6u klasi6nu teoriju. To je ops6irni Singov.( . L. Synge) rad nRela-r tivisti6ka hidrodinamika" [3]. U njemu actor pre svega izlaze ono to je do tada o relativisti6kom idealnom fluidu bilo poznato, Tret7 postavljajuoi kao i njegovi prethodnici da za fluid van.. karakteri- Virtual Library of Faculty of Mathematics - University of Belgrade elibrary.matf.bg.ac.rs stiena jodnacina koja vezuje sopotveni pritioak i sopstvenu'guStinu. on prihvata od Ajzenharta skalarnu funkciju pomo6u koje se . strujne linije idealnogfluida preslikavaju na geodezijske linije jednog prostora oija je metrika konformna metrici prostor-vremena, i pomoCu nje uvodi svoju funkciju; tzv. funkciju-indeksl ) , koja u relativistiCkoj hidrodinamici igra veoma vaInu ulogu. Pored toga, Sing je u• svome radu uveo i 6itav niz novih pojmova: definisao je kinemati6ku i'dinami6ku cirkulaciju, uveo pojam.kinemati6kog i dinamiekog tenzora vrtlolenja, kinemati6kog dinamiCkog vektor-vrtloga, i definisao je i ispitivao bezvrtloZno strujanje. Izvestan broj definicija iz ()yoga' rada je docnije pretrpeo izmene, pa se 6ak neki pojmovi definisani u njemu i ne pomi- . nju u docnijim radovima, kako Singovim tako i ostalih autora, jer uu pokazalo da 110 predutavijaju relativiutiaa uop6tonja odgovarajuaih klasi6nih pojmova: Tako, recimo, udanaSnjiM radovima ne molemo najoi . na Singovu kinemati6ku'cirkulaciju; kao izraz koji predstavlja relativistieko uopftenje klasi6nog pojma cirkulacije vektora brzine prihvadena je samo njegova dinami6ka cirkulacija, pod imenom cirkulacije vektora toka. Ipak, ovaj Singov rad predstavlja zna6ajan doprinos razvoju relativisti6ke teorije fluida, buduai da je posluZio kao osnovica na kojoj su docniji autori, ukljusoujuOi i samoga Singa4 gradili dalje to teoriju. 1) Funkcija-indeks koju Sing uvodi, i koju tako naziva zbog njene analogije sa klasi6nim indeksom prelamanja.date transparentne sredine, ne razlikuje se bitno od pomenute AjzenhartoVe funkci -• je: samo iz formalnih razloga, umesto da koristi . Ajzenhartovu funkciju qq= ft. 41i1.. leNtil- (gde je ft/ sopstveni pritisak:fluida, a S njegova sopstvena gustina), Sing kao funkciju-indeks defini..6e (f,)=exp(A(p4). U svojim radovima Lihnerovi6 prihvata Singovu funkciju i naziva je indeks fluida. Virtual Library of Faculty of Mathematics - University of Belgrade elibrary.matf.bg.ac.rs -3_ Posle izvesne praznine u literaturi koju je doneo drugi sve-. tski rat, krajem 6etrdesetih, a zatim.pedesetih i 6ezdesetih godina, pojavljuje se atav niz.veoma zna6ajnih radova iz ove oblasti. PomenuCemo; pre svega, Taubove. (A. H. Taub) radove [4],[5] i [6] Koristeei Ekartove (C. Eckart) [7] ideje.o relativisti6koj -termodinamici koje prenosi iz specijalne u .op6tu teoriju relativnosti, Taub se ne ogranieava na adijabatska i izotermi6ka strujanja, pri kojima za fluid vaZi karakteristi6na jednaina kCja vezuje sopstveni pritisak i sopstvenu gustinu, veo posmatra opgiti slu6aj, kada su dve termodinamifte Veli6ine nezavisno 'promenllive. U svojim ra- ___ . _ doVima on, izmedju ostalog, fotmulibe i jedan nov oblik tenzora energije relativisti6kog idealnog fluida. To je oblik u kome se unutra-6nja energija pojaVljuje eksplicitno, aokoji je.veoma pogodan za rad kada uz diferencijalne jedna6ine kretanja• fluida . i uz jedna_inu kohtinuiteta treba, pored .karakteristione jednaane, koristiti i druge termodinami6ke veze. Uporedo sa Taubovim radovima, u literaturi iz toga perioda nailazimo na niz radova A. LihneroviOa. (A. Lichnerowilpz) [8],[93 i njegovih u6enika. U njima autori uzimaju u obzir pojave provodjenja toplote i elektriciteta kroz idealnu fluidnu sredinu, a takodje posmatraju naelektrisani iii namagnetisani idealni fluid.. Tenzor energije koji nalazimo u.njihovim radovima dopunjen je 61anovima koji se odnose na pojave koje smo pomenuli. Veoma znaajno mesto u tim radovima zauzima i Kogijey problem_koji,se postavlja i ispituje u razli6itim slu6ajevima_materijalnih.sredina. Najzad, A. Lihnerovic je prvi koji . je u relativisti6koj teoriji uzeo u obzir unutra6nje trenje, koje postoji izmedju 6estica fluida pri njihovom relativnom pomeranju. Po6to je postavio izraz za tenzor energije relativistiekog viskoznog,fluida, on je, pola7 zea oduslova konzervativnosti toga tenzora, izveo i'diferencijalne jednaane kretanja takve . materijalne sredine i.ispitivao nje- Virtual Library of Faculty of Mathematics - University of Belgrade elibrary.matf.bg.ac.rs no bezvrtloZno strujanje. Relativistieki viskozni fluid koji je uz to i naelektrisan . u svojoj studiji [10] Pion (G. Pichon). Tenzor vis- Prou6avao je koznosti koji nalazimo u njegovom radu ne poklapa se sa izrazom koji za taj tenzor daje Lihnerovie. U odeljku 1.1 ovoga rada govorieemo detaljnije o tome zbog 6ega te izrazi za tenzor viskoznosti kod dvojice pomenutih autora razlikuju. Primena varijacionih principa u relativistiekoj mehanici fluida takodje je razmatrana od nekoliko autora o ko.jima smo ovde govorili. Koliko nam je poznato, ve6 pomenuti Ajzenhartov rad [2] je prvi rad u kome su diferencijalne jedna6ine kretanja relativistiekog idealnog fluida za koji vaIi adijabatska jednanna propene staftja izvedene primenom jednog varijacionog principa. Potpunu. formalnu analogiju toga principa sa Fermaovim principom geometrijske optike istakao je u svome radu [3] Sing. Godine 1954. je Taub [11] formulisao varijacioni princip koji dovodi do jedna6ina polja opfte relativnosti i do jednanna kretanja relativistincog idealnog fluida. Najzad, jedan interesan7 tan prilaz tome pitanju razmatrao je 1970. godine Bernard Suc (Bernard G. Schutz, Jr.) [12] v drle6i se i dalje granica idealnog fluida. Iz ovog kratkog istorijskOg prikaza razvoja relativistieke hidromehanike mote se zapaziti da.je u literaturi uglavnom prow:- eavan relativistieki.idealni fluid; dok upadljivo mali broj radova uzima u - obzir pojavu viskozhosti. Osim dva rada, koje smo ovde citirali, u 6itavoj relativisti6koj:literaturi koja nam je bila • 'dostupna nismo naigli ni na jedan drugi rad u kome se razmatra unutragnje trenje izmedju 6estica .fluida pri njihovom relativnom pomeranju. Pri tome se, kao gto smo Ve64stakli, izrazi za tenzor viskoznosti u dva pomenuta rada razlikuju, izvodjenju jedna6i- ,•a kretanja posmatrane sredine autori polaze od uslova konzervativ- Virtual Library of Faculty of Mathematics - University of Belgrade elibrary.matf.bg.ac.rs nosti tenzora energije, to zna6i da koriste put kojiAe u rela- . tivisti6koj teoriji fluida uobi6ajen.. U ovome radu eemo posmatrati relativistieki viskozni flu- . , sa ciljem da pri izvodjenju diferencijalnih id jednaeina kretanja takve materijalne sredine primenimo tzv. Pfafovu metodu. Primeni Pfafove metode u mehanici i teorijskoj fizici po-. ove6en je veliki broj radova objavljenih u Beogradu krajem•eetrdesetih i pedesetih.godina. Ovde 6emo pomenuti pre svega radove A. Bilimovi6a [133 i [143. Baveoi se pitanjem utvrdjivanja fenomenolOgke osnove za Pfafovu metodu, on je u svojoj monografiji [14] f.ormulisao jedan op'Sti fenomenolaki diferencijalni'princip: Taj princip analizi- ra st. anje posmatranog sistema i uzroke koji izazivaju promenu toga stanja, i na osnovu to analize sastavija jedan matemati6ki izraz u obliku Pfafove forme, iz koga se dobivaju diferencijalne je7 dna6ine kretanja sistema kao Pfafove jedna6ine. On'je zatim primenio Pfafovu metodu na niz problema teorijske mehanike, nebeske • mehanike i geometrijske optike . C14]. Pri izvodjenju diferencijalnih jedna6ina kretanja krutog Lela, zatim osnovnih diferencijalnih jednaeina hidrodinamike i mehanike elasti6nih tela, ovu metodu je koristio T..Andjelie [153, [16], [173. Time je on ukazao na op6tu primenljivost Pfafove me- . tole u dinamici kako krutih tela, tako i deformabilnih sredina. Najzad, u svome radu [18] Dj.. Niu6icki je pokazao da se Pfafova metoda mote koristiti i u teorijskoj fizici. On je izvr6io . generalizaciju Pfafovog izraza i Pfafovih jedna6ina, dokazao Aa i za takav Pfafov izraz i jedna6ine vane sli6ne osobirie kao i za .6an 'Pfafov izraz jednaCine, a.zatim tako generalisana Pfafovu todu primenio u razli6itimoblastima teorijske fizike - termodina- . mici, elektromagnetizmu i'kvantnoj mehanici. . Virtual Library of Faculty of Mathematics - University of Belgrade elibrary.matf.bg.ac.rs Ovaj rad smo podelili na dve glave. U prvoj glavi nam je bio cilj da dodjemo do oblika za tenzor energije relativistiOkog viskoznog fluida. Po!ho .smo u prvom odeljku objasnili 6ta•nas je navelo da se na tome pitanju, kojc je u literaturi ve6 re6avano, ipak zadrZimo, u drugom odeljku raspravljamo koji oblik tenzora brzine deformacije i tenzora vrtlolenja treba usvojiti u relativistiftoj teoriji. Pri tome smo kao osnovicu u na s6im razmatranjima uzeli Zahtev da rezultati do kojih dolazimo moraju biti u skiadu sa postojedom Bornovom definicijom krutosti u opkoj teoriji relativnosti, a takodje i u skiadu sa rezultatima rada [193 o vrstama kretanja Bornovog relativisti6ki krutog tela. U posiednjem, tre6em odeljku prve glave, dolazimo do relativistiOkog tenzora.viskoznosti polaze6i od zahteva da se njegove prostorne komponente u odnosu na sopstveni koordinatni sistem svo- . de na komponente odgovaraju6eg klasiOnog tenzora, dok mu ostale komponente u odnOsu na taj sistem moraju biti .jednake null. Osnovnom pitanju koje u ovom radu razmatramo pitanju primene Pfafove metode u relativistiOkoj mehanici fluida - posve6ena . je druga glava rada. Posle kratkog izlaganja o tome kako je nastala tzv. Pfafova metoda u mehanici, i 6ta predstavlja njenu sadrZinu, u drugom, centralnom odeljku toga dela rada postavlja se izraz za Pfafovu formu koja odgovara posmatranom materijalnom sistemu. Iz toga izraza zatim, pOstupkbm koji Pfafova metoda nalaZe, izvode diferencijalne jednaOine kretanja relativi.stiOkog viskoznog fluida. Dobivene jednaOine, c,je predstavljaju relativistiOko uop6tenje Navije-Stoksovih jedna6ina . klasjOne hidrodinamike, razlikuju se od. odgovaraju6ih jednaina do . kojih jedo6ao Lihnerovi6 [83; to je razumljivo ako se ima u vidu da se tenzor viskoznosti koji je formulisac ne poklapa sa izrazom koji 'sm.() u ovom radu za taj ten- Virtual Library of Faculty of Mathematics - University of Belgrade elibrary.matf.bg.ac.rs zor U tre6em, poslednjem odeljku druge glave, ogranioili smo se na slaaj relativistiftog idealnog fluida za koji van adijabatska • jedna6ina promene stanja. Pokazali smo da se u tome slu6aju Pfafov izraz za deli6 fluidne sredine mote obrazovati na veoma jednostavan naCin, bez potreba da se trai relativisti6ko uop6tenje za.klasi6ni izraz koji predstavlja rad rezultuju6e sile pritiska kojom. okolina na uoceni delic deluje, prilikom njegovog pomeranja. od po- 6etnog do krajnjeg polo2aja. Pri tome fluidnu sredinu moramo posmatrati u prottoru 6ija je.metrika konformna metrici prostor-vremena, a koja se uvodi pomo6u indeksa fluida tako. da strujne linije'. fluida predstavljaju geodezijske linije toga prostora. Najzad, zakljusaujemo da bi sa taj.rezultat pod izvesnim uslovima mogao primeniti i u slu6aju ralativisti6kog . viskoznog fluida. URI: http://hdl.handle.net/123456789/4095 Files in this item: 1
Pfafova_metoda.PDF ( 9.783Mb ) -
Lukačević, Mirjana (Belgrade)[more][less]
-
Jandrlić, Davorka (Beograd , 2016)[more][less]
Abstract: Application of association rule and support vector machine technique for T cell epitope prediction Abstract: Data mining is an interdisciplinary sub eld of computer science, including various scienti c disciplines such as: database systems, statistics, machine learning, arti cial intelligence and the others. The main task of data mining is automatic and semi-automatic analysis of large quantities of data to extract previously unknown, nontrivial and interesting patterns. Rapid development in the elds of immunology, genomics, proteomics, molecular biology and other related areas has caused a large increase in biological data. Drawing conclusions from these data requires sophisticated computational analyses. Without automatic methods to extract data it is almost impossible to investigate and analyze this data. Currently, one of the most active problems in immunoinformatics is T cell epitope identi cation. Identi cation of T - cell epitopes, especially dominant T - cell epitopes widely represented in population, is of the immense relevance in vaccine development and detecting immunological patterns characteristic for autoimmune diseases. Epitope-based vaccines are of great importance in combating infectious and chronic diseases and various types of cancer. Experimental methods for identi cation of T - cell epitopes are expensive, time consuming, and are not applicable for large scale research (especially not for the choice of the optimal group of epitopes for vaccine development which will cover the whole population or personalized vaccines). Computational and mathematical models for T - cell epitope prediction, based on MHC-peptide binding, are crucial to enable the systematic investigation and identi cation of T - cell epitopes on a large dataset and to complement expensive and time consuming experimentation [16]. T - cells (T - lymphocytes) recognize protein antigen(s) only when degradated to peptide fragments and complexed with Major Histocompatibility Complex (MHC) molecules on the surface of antigen-presenting cells [1]. The binding of these peptides (potential epitopes) to MHC molecules and presentation to T - cells is a crucial (and the most selective) step in both cellular and humoral adoptive immunity. Currently exist numerous of methodologies that provide identi cation of these epitopes. In this PhD thesis, discussed methods are exclusively based on peptide sequence binding to MHC molecules. It describes existing methodologies for T - cell epitope prediction, the shortcomings of existing methods and some of the available databases of experimentally determined linear T - cell epitopes. The new models for T - cell epitope prediction using data mining techniques are developed and extensive analyses concerning to whether disorder and hydropathy prediction methods could help understanding epitope processing and presentation is done. Accurate computational prediction of T cell epitope, which is the aim of this thesis, can greatly expedite epitope screening by reducing costs and experimental e ort. These theses deals with predictive data mining tasks: classi cation and regression, and descriptive data mining tasks: clustering, association rules and sequence analysis. The new-developed models, which are main contribution of the dissertation are comparable in performance with the best currently existing methods, and even better in some cases. Developed models are based on the support vector machine technique for classi cation and regression problems. À new approach of extracting the most important physicochemical properties that in uence the classi cation of MHC-binding ligands is also presented. For that purpose are developed new clustering-based classi cation models. The models are based on k-means clustering technique. The second part of the thesis concerns the establishment of rules and associations of T - cell epitopes that belong to di erent protein structures. The task of this part of research was to nd out whether disorder and hydropathy prediction methods could help in understanding epitope processing and presentation. The results of the application of an association rule technique and thorough analysis over large protein dataset where T cell epitopes, protein structure and hydropathy has been determined computationally, using publicly available tools, are presented. During the research on this theses new extendable open source software system that support bioinformatic research and have wide applications in prediction of various proteins characteristics is developed. A part of this thesis is described in the works [71][82][45][42][43][44][72][73] that are published or submitted for publications in several journals. The dissertation is organized as follows: In section1 is illustrated introduction to the problem of identifying T - cell epitopes, the importance of mathematical and computational methods in this area, vii as well as the importance of T - cell epitopes to the immune system and basis for functioning of the immune system. In section 2 are described in details data mining techniques that are used in the thesis for development of new models. Section 3 provides an overview of existing methods for predicting the T - cell epitopes and explains the work methodologies of existing models and methods. It pointed out the shortcomings of existing methods which have been the motivation for the development of new models for the T - cell epitope prediction. Some of the publicly available databases with the experimentally determined MHC binding peptides and T - cell epitope are described. In section 4 are presented new developed models for epitopes prediction. The developed models include three new encoding schemes for peptide sequences representation in the form of a vector which is more suitable as input to models based on the data mining techniques. Section 5 reports results of presented new classi cation and regression models. The new models are compared with each other as well as with currently existing methods for T cell epitope prediction. Section 6 presents the research results of the T - cell epitopes relationship with ordered and disordered regions in proteins. In the context of this chapter summary results are presented which are shown in more detail in the published works [71][82][45][44]. Section 7 concludes the dissertation with some discussion of the potential signi cance of obtained results and some directions for future work. URI: http://hdl.handle.net/123456789/4457 Files in this item: 1
doktorskaTezaDavorkaJandrlic.pdf ( 7.938Mb ) -
Karapandžić, Đorđe (Belgrade)[more][less]
URI: http://hdl.handle.net/123456789/142 Files in this item: 1
phdDjordjeKarapandzic.pdf ( 3.246Mb ) -
Stokić, Dušan (Belgrade , 1975)[more][less]
-
Pavlović, Miroljub (Belgrade)[more][less]
-
Doder, Dragan (Beograd , 2011)[more][less]
-
Kartelj, Aleksandar (Beograd , 2014)[more][less]
Abstract: This work investigates the potential of improving the classi cation process through solving three classi cation-related problems: feature selection, feature weighting and parameter selection. All three problems are challenging and currently in the focus of scienti c researches in the eld of machine learning. Each problem is solved by using population-based metaheruistic method called electromagnetismlike method. This method is used for combinatorial and global optimization. It is inspired by laws of attraction and repulsion among charged particles. Each particle is represented by a vector of real values. The solution of the problem of interest is then obtained by mapping these real-valued vectors to the feasible solution domain. Particles representing better solutions achieve higher level of charge, which consequently produces greater impact on other particles. The search process is performed by iterating the particle movement, induced by charges. Through implementing the methods, two key aspects are managed: 1) the classi cation quality obtained after applying the optimization method and 2) the e ciency of the proposed methods from the perspective of time and space resources. All methods are equiped with problem-speci c local search procedures which tend to increase the solution quality. The bene t of applying feature selection for the classi cation process is twofold. Firstly, the elimination of unnecessary features decreases the data set noise, which degrades the quality of the classi cation model. Secondly, the problem dimension is decreased, thus the e ciency is increased. Feature selection problem is very e - ciently solved by the proposed method. The classi cation quality is in the majority of cases (instances) improved relative to the methods from literature. For some of the instances, computational times are up to several hundred times smaller than those of the competing methods. Feature weighting and parameter selection problem share similar underlying solution representation, based on the vectors of real values. Since the representation of charged particles is based on the same underlying domain, the transition from the particle to the solution domain behaves smoothly. The quality of the method for iv feature weighting is demonstrated through nearest neighbors classi cation model. The testing of the method is conducted on di erent collection of instances, and after that, the comparison to several methods from literature is made. In the majority of cases, the proposed method outperformed the comparison methods. The parameter selection, in classi cation, has a great impact on the classi cation quality. The proposed method for parameter selection is applied on the support vector machihe, which has a complex parametric structure when the number of parameters and the size of their domains is in question. By using heuristic initialization procedure, the detection of high quality regions for parameter combinations is accelerated. Exhaustive tests are performed on various instances in terms of their dimension and feature structure: homogenous and heterogeneous. Single kernel learning is adopted for homogenous, and multiple kernel learning for heterogeneous instances. The comparison with methods from literature showed superiority of the proposed method when single and multiple kernel learning based on radial basis function is considered. The method shows to be competitive in other cases. All proposed methods improved the classi cation quality. Because of the way, the problem is being solved, all three methods can be generalized and applied to a wide class of classi cation models and/or classi cation problem. URI: http://hdl.handle.net/123456789/4234 Files in this item: 1
phdAleksandarKartelj.pdf ( 2.121Mb ) -
Andrejić, Vladica (Beograd , 2010)[more][less]
Abstract: U ovom radu posmatramo princip dualnosti (i jake dualnosti) za Osermanove mnogostrukosti i uopxtavamo ga za pseudo-Rimanov sluqaj. Osnovni ci je dokazati princip dualnosti za Osermanove mnogostrukosti u opxtem sluqaju ili konstrukcija eventualnih kon- traprimera. Za sada smo u sta u da damo samo rezultate pod speci- fiqnim dodatnim uslovima. Prva mogu nost je mali indeks pseudo- Rimanove mnogostrukosti, gde dokazujemo da jaka dualnost va i za Rimanove i Lorencove prostore. Druga mogu nost su prostori malih dimenzija gde dokazujemo da jaka dualnost va i kad dimenzija nije ve a od qetiri. Posled a olakxavaju a okolnost sa kojom radimo tiqe se malog broja sopstvenih vrednosti redukovanog Jakobijevog operatora, gde posmatramo dvolisno-Osermanove tenzore krivine. U tom sluqaju radimo sa jakim uslovima iz definicije kvazi-specijalnih Osermanovih tenzora krivine i elimo da doka emo da pod ima va i princip dualnosti. Konaqan rezultat je da skoro-specijalan Oser- manov tenzor krivine mora biti specijalan Osermanov. U nastavku postav amo obratan problem, te pokuxavamo da istra imo pod kojim uslovima algebarski tenzor krivine za koji va i princip dualnosti mora biti Osermanov. Potvrdan rezultat dobili smo u dimenziji tri, kao i u sluqaju kada se Fidlerova suma sastoji od samo jednog qlana. URI: http://hdl.handle.net/123456789/2479 Files in this item: 1
phdAndrejicVladica.pdf ( 513.6Kb ) -
Dajović, Slobodan (Belgrade)[more][less]
-
Đorđević, Radosav (Kragujevac , 1991)[more][less]
Abstract: The thesis consists of six chapters. Chapter 1 contains the structures, in which the probability logics are realized, and the basic methods of nonstandard analysis which are used in the other chapters. In Chapter 2 the syntax and semantics of the following probability logics are presented: the logic with the probability quantifiers L_Ap, the logic with the integral operators L_A_∫ , the logic with the operator of conditional expectation L_AE and adapted probability logic L_ad. Moreover, the certain important results about these logics are given. The problems of Barwise’s completeness, completeness, compactness, the existence of analytic and hyperfinite models for biprobability logics LA_P1_P2, LA_∫_1_∫_2 and L_ad in absolute continuous and singular cases are solved in Chapter 3. The many-probability logic BC{L_AP_i:i∊I}, I∊A obtained by Boolean combinations of probability logics L_AP is introduced and some model-theoretical properties of that logic are given in Chapter 4. In Chapter 5 the probability logic L^2AP∀ of second order is introduced, which is motivated by Keisler’ s problems with L_AP∀ and some topological logics. The problem of completeness for the logic L^2AP∀ is proved. In Chapter 6 cylinder probability algebras are introduced and some possibilities to solve problems for these algebras (which are characteristics of standard cylinder algebras, as the representation, axiomatization and decidability) are presented. URI: http://hdl.handle.net/123456789/189 Files in this item: 1
phdRadosavSDjordjevic.pdf ( 2.407Mb ) -
Djerasimović, Božidar (Belgrade)[more][less]
URI: http://hdl.handle.net/123456789/140 Files in this item: 1
phdBozidarPDjerasimovic.pdf ( 2.343Mb ) -
Stančić, Olivera (Beograd , 2018)[more][less]
Abstract: Hub Location Problems (HLP) represent an important class of optimiza- tion problems due to their numerous applications in many areas of real life. They often arise from practical situations that require routing of the flow from origin node (supplier) to the destination node (customer) under given conditions, such that the value of considered objective function is optimal. Hubs are special objects (nodes in the network) that represent centres for consolidation and flow collection between two selected locations - suppliers and customers. As transportation costs (per unit of flow) along the links that connect hub nodes are lower compared to other links in the network, directing the flow to hubs may lead to significant reductions of transportation cost in the network. The subject of this doctoral dissertation is one class of hub location problems, denoted as Hub Maximal Covering Problems (HMCPs) in the literature. The goal of HMCPs is to determine optimal locations for establishing certain number of hubs in order to maximize the total flow between all the covered origin-destination pairs, under the assumption of binary or partial covering. Three variants of the hub maximal covering problem are considered: uncapacitated single allocation p -hub maximal covering problem (USApHMCP), uncapacitated multiple allocation p -hub maximal covering problem (UMApHMCP) and uncapacitated r -allocation p -hub maximal covering problem (UrApHMCP). Note that the UrApHMCP has not been studied in the literature so far. All three considered problems are proven to be NP- hard. In case of USApHMCP, for the given set of hubs, the obtained sub-problem of optimal allocation of non-hub nodes by established hubs is also NP-hard. In this dissertation, new mathematical models for USApHMCP with binary and partial covering are proposed. The main advantage of the newly proposed models, in respect to existing ones from the literature, is the fact that small modifications of the new models enable their transformation to new models for p -hub maximal covering problems with different allocation schemes. More precisely, new models for UMApHMCP and UrApHMCP can be obtained from the newly proposed mod- els for USApHMCP in both coverage cases. All proposed models for USApHMCP and UMApHMCP are compared with the existing ones from the literature in the terms of efficiency within the framework of exact CPLEX 12.6 solver. Several hub data sets from the literature are used in numerical experiments when comparing the formulations. The obtained experimental results indicate that new models for UMApHMCP with both binary and partial coverage show the best performance in terms of solutions’ quality and execution times. For UrApHMCP and both coverage criteria, three mathematical models are proposed, and compared in terms of effi- ciency using the exact CPLEX 12.6 solver. It turns out that the exact solver finds optimal or feasible solutions only for small-size problem instances. Having in mind the complexity of all three problems under consideration and the results obtained by CPLEX 12.6 solver, the conclusion is that, in practice, exact methods can not provide solutions for large problem dimensions. For this reason, it was necessary to implement adequate heuristic or metaheuristic methods, in order to obtain high-quality solutions in short execution times, even in the case of large problem dimensions. Up to now, only simple but insufficiently effective heuris- tic methods for solving USApHMCP and UMApHMCP with binary coverage have been proposed in the literature, while the HMCP variants with partial coverage have not been previosly solved by using metaheuristic methods. As UrApHMCP with binary and partial coverage has not been previously considered in the litera- ture, no solution methods suggested for this problem existed up to now. Inspired by previous successful applications of variable neighborhood search method (VNS) to other hub location problems from the literature, this metaheuristic approach is applied to the considered HMCP problems. In this dissertation, several variants of VNS metaheuristic are designed and implemented: General Variable Neighborhood Search (GVNS) for USApHMCP, Basic Variable Neighborhood Search (BVNS) for UMApHMCP and a variant of General Variable Neighborhood Search (GVNS-R) for UrApHMCP. In the case of UrApHMCP, two additional metaheuristic meth- ods are proposed: Greedy Randomized Adaptive Search Procedure with Variable Neighborhood Descent (GRASP-VND) and Genetic Algorithm (GA). Constructive components of all proposed metaheuristics are adapted to the characteristics of the considered problems. Experimental study was conducted on the existing hub data sets from the lit- erature, which include instances with up to 1000 nodes in the network. The ob- tained results show that the proposed metaheuristics for the considered problems reach all known optimal solutions previously obtained by CPLEX 12.6 solver or establish new best-known solutions in significantly shorter CPU time compared to CPLEX 12.6. The proposed GVNS and BVNS metaheuristics quickly reach all known optimal solutions on small-size problem instances when solving USApHMCP and UMApHMCP, respectively. In the case of large-size problem instances, which have not been previously used for testing purposes for these problems, the proposed GVNS and BVNS return their best solutions in short execution times. The results obtained by the proposed GVNS-R and GRASP-VND for UrApHMCP on large-size problem instances indicate their effectiveness in both coverage cases. The proposed GA method showed to be successful only for UrApHMCP in binary covering, on instances up to 200 nodes. The variants of hub maximal covering problems considered in this dissertation are important from both theoretical and practical points of view. The new mathe- matical models proposed in this dissertation for the considered variants of HMCP, represent a scientific contribution to the theory of hub location problems, mathemat- ical modeling and optimization. Designed and implemented metaheuristic methods for solving the studied variants of HMCP are the scientific contribution to the field of optimization methods for solving location problems, as well as the development of software. The considered variants of HMCP have numerous applications in the optimization of telecommunication and transport systems, air passenger and goods transport, emergency services, postal and other delivery systems, so that the results obtained in this doctoral dissertation can be applied in practice, partially or com- pletely. URI: http://hdl.handle.net/123456789/4750 Files in this item: 1
StancicOliveradisertacija.pdf ( 1.688Mb )