Šiame darbe tiriama sritis yra kompiuteriniuose žaidimuose naudojamas dirbtinis intelektas. Konkrečiai gilinamasi į metodus, kurie valdo daugybę veikėjų žaidime, siekiančių tam tikro tikslo. Dėl konkretiems žaidimams unikalių mechanikų, šie metodai paprastai būna labai glaudžiai susiję su žaidimo aplinka ir taisyklėmis. Tyrimo tikslas yra sukurti ir ištirti metodą, skirtą daugybės veikėjų pajėgų valdymui ir jų veiksmų modeliavimui virtualioje aplinkoje. Analizuojami metodai skirti pavienių veikėjų veiksmų įvertinimui ir modeliavimui, metodai skirti optimalių sprendimų žinių bazei sudaryti ir metodai toms žinioms pritaikyti paskirstant veikėjus aplinkoje. Pagal analizės rezultatus sukuriamas projektas daugelio veikėjų valdymui realiu laiku virtualioje aplinkoje. Lokalių veikėjų veiksmų modeliavimui naudojamas procedūrinis taktinių veiksmų parinkimo metodas. Veikėjų judėjimui aplinkoje modeliuoti naudojamas neuroninis tinklas. Jis apmokomas pagal genetiniu algoritmu sudarytus optimalius sprendimus. Suprojektuota sistema realizuojama ir testuojama. Atliekamas eksperimentas su sistemos veikimo metu gautais rezultatais. Eksperimente nustatoma, kad šis sprendimo būdas gali tikslingai reaguoti į situacijas, susidarančias realaus laiko virtualioje aplinkoje, ir modeliuoti veikėjų veiksmus joje. / The research area of this paper is artificial intelligence used in computer games. Specifically it is focused on methods for controlling a group of agents with a specific goal. Because of the uniqueness of individual game mechanics, those kinds of methods are usually closely related to that games environment and rules. The goal of this study is to design and test a method that could control a group of multiple agents in a virtual environment. Methods for evaluating and selecting individual agent actions in a local environment, for gathering a database of optimal solutions and for applying that knowledge in distributing agents across the environment are analyzed. A design for controlling the actions of multiple agents in a real time virtual environment is designed, based on the results. Dynamic procedural combat tactics is used to model individual agent actions in a local environment. A neural network is used to model the movement of multiple agents in an environment. It is trained using optimal solutions, generated by a genetic algorithm. Designed system is implemented and tested. Using data that the system generates, an experiment is conducted. It shows that this solution is capable of correctly reacting to situations, occurring in a real time virtual environment, and of modeling multiple agent actions in it.

Portfelio parinkimo uždavinys yra viliojantis technikos moksluose, tiesioginiuose („online“) algoritmuose ir žinoma financiniuose skaičiavimuose. Šiame darbe buvo naudotas algoritmas, kuris nebando atspėti laimėtojus. ANTICOR algoritmo optimizavimui buvo naudotas genetinis algoritmas ir algoritmo stabdymas. / The portfolio selection problem is a challenging problem for machine learning, online algorithms and of course, computational finance. In this work was used a portfolio selection algorithm, which does not try to predict winners. There were used a genetic algorithm and algorithm stopping, trying to optimize the ANTICOR algorithm.

To understand evolution, and to discover how different species are related, gene order analysis is a useful tool. Problems in this area can usually be formulated in a combinatorial language. We regard genomes as signed, or unsigned permutations, and thus evolutionary operations like inversions (reversing the order of a segment of genes) are easy to describe combinatorially. A commonly studied problem is to determine the evolutionary distance between two species. This is estimated by several combinatorial distances between gene order permutations, for instance the inversion distance. The main objective of this work was to survey the existing algorithms for genome comparison and to present new approach for solving this problem. The work led to these results: - We have surveyed existing approaches of genome comparison, namely comparison by inversion distance in signed and unsigned cases. It appeared that sorting signed genomes by inversions is done in quadratic time, but sorting unsigned genomes by inversions is NP-hard. - We have proposed the method of how to apply heuristic algorithms for sorting unsigned genomes by inversions. - We have applied tabu search and genetic algorithm to solve the sorting unsigned genomes by inversions problem. - We have experimentally proven, that the worst case solutions to sorting unsigned genomes by inversions found by heuristics (tabu search and genetic algorithm) are better then ones expected from best known approximating algorithm used for... [to full text]

Šiame darbe nagrinėjama negiljotininio, dvimačio, stačiakampių pjaustymo uždavinio atliekų minimizavimo problema ir jos sprendimo metodai. Dėl uždavinio kombinatorinio sudėtingumo neįmanoma tiksliai ir visais atvejais pateikti optimalų jo sprendinį, todėl pasirinkti apytiksliai sprendimo metodai. Uždavinys sprendžiamas metaeuristiniais hibridiniais genetiniu ir modeliuojamo atkaitinimo algoritmais apjungtais su euristiniais „Žemiausio kairėn užpildymo“ ir „Žemiausio tarpo“, kuris yra originali „Geriausiai tinkamo“ metodo modifikacija. Taip pat realizuojami minėti euristiniai algoritmai atskirai nuo hibridinių. Atliekama šių metodų lyginamoji analizė bei jų parametrų ir pradinių sąlygų parinkimo įtakos tyrimas sprendinio kokybei. Suformuojama ir pateikiama metodika pjaustymo uždavinių sprendimui. / A non – guillotinable, two – dimensional, rectangular cutting stock problem is being introduced in this paper and its solving methods either. Due to the combinatorial complexity of a problem, it is impossible to solve it optimally for every instance. Consequently an aproximate methods have been chosen. The problem is solved by metaheuristic genetic and simulated annealing methods hybridised with heuristic „Bottom Left Fill“ and „Lowest Gap“, which is an originally modified version of „Best Fit“ algorithm. The same heuristic algorithms are implemented separately from hybridised ones. A comparation analysis of these methods is done and the influence on solution quality depending on the selection of algorithms parameters and its initial conditions is considered. The methodology of solving cutting stock problems is being formulated and presented.

Darbe nagrinėjami euristiniai algoritmai NPC aibės uždaviniams spręsti ir jų taikymas lygiagrečiųjų ir paskirstytųjų skaičiavimų (angl. GRID) tinkle. NPC aibės uždaviniai, taikant įprastus algoritmus, nėra išsprendžiami per polinominį laiką, todėl jiems taikomi euristiniai algoritmai, kurie pasižymi gebėjimu, per priimtiną laiko tarpą, rasti geros kokybės sprendinius, bet didėjant uždavinių apimtims, euristinių algoritmų vykdymo laikas taip pat sparčiai ilgėja. Norint gauti geresnės kokybės sprendinius, reikia daugiau kompiuterinių išteklių. Darbe detaliau nagrinėjami trys populiarūs euristiniai algoritmai: genetinis, modeliuoto atkaitinimo ir skruzdžių kolonijų. Visi šie algoritmai buvo pritaikyti keliaujančio prekeivio uždaviniui (angl. Traveling salesman problem) spręsti GRID skaičiavimo tinkle. Atlikti bandymai su 20 didelės apimties TSPLIB bibliotekos testinių pavyzdžių leidžia teigti, kad kompiuterinių išteklių problemą, sėkmingai galima išspręsti euristinius algoritmus vykdant GRID skaičiavimo tinkle. Gauti rezultatai rodo, kad euristinių algoritmų efektyvumas, juos vykdant GRID skaičiavimo tinkle yra labai aukštas. Daugelyje bandymų pavyko rasti optimalius sprendinius, o kitais atvejais rasti sprendiniai nedaug skyrėsi nuo optimalių. Darbo autorius euristinių algoritmų bandymams siūlo naudoti „DAG“ tipo GRID užduotis. Tokio tipo užduotys leidžia ta patį bandymą atlikti skirtinguose skaičiavimo klasteriuose tuo pačiu metu, tokiu būdu galima įvykdyti daug pakartotinų... [toliau žr. visą tekstą] / The main goal of this work is to implement and test heuristic algorithms for GRID computing network to solve NP-complete problems. The problems of NP-complete set are not solved in polynomial time. To solve such problems, researchers have to use heuristic algorithms. Heuristic algorithms always give result in polynomial time, but it doesn’t mean that result is optimal, also computing time grows together with problem scope, and in this case bigger computing recourses are needed. Three popular heuristic algorithms are included in this works: genetic, simulated annealing and ant colony. All of them were implemented to solve traveling salesman problem in GRID computing network. With mentioned heuristic algorithms 20 TSP instances of TSPLIB library were solved. Experiential results shows that efficiently of heuristic algorithms are high and with 12 tested instances optimal solution was found. Author of this work recommends to use “DAG” type GRID tasks. Such type tasks allows to execute algorithms in different clusters at same time, so in same time researcher can execute a lot of tests and final test will give best results.

Neural networks are one of the most efficient classifier methods. One of such classifying neural networks we are trying to teach in this work by using genetic algorithms. In this work we test two types of genetic algorithms. One may be called parameterized genetic algorithm. It is built on the basic ideas of genetic algorithms. The other one is called parameter less genetic algorithm. It was presented by F. G. Lobo and D. E. Goldberg. Both genetic algorithms are tested and compared to the other well known optimization methods such as Bayes and Monte Carlo search. Experiments show the relevance of use genetic algorithms in teaching classifying neural network. Also stated that parameter less genetic algorithm works more efficient than parametric genetic algorithm in general cases. Created programs will be used in future studies.

In this work, the Traveling Salesman Problem (TSP) is discussed. The Hybrid Genetic Algorithm for solving the TSP is presented. The traveling salesman problem is formulated as follows: given matrix D=(dij)nxn of distances between n objects and the set P of permutations of the integers from 1 to n, find a permutation p=(p(1), p(2), ..., p(n)) P that minimizes. Many heuristic algorithms can be applied for the TSP. Recently, genetic algorithms (GAs) are among the advanced heuristic techniques for the combinatorial problems, like the TSP. genetic algorithms are based on the biological process of natural selection. The original concepts of GAs were developed in 1970s. Many simulations have demonstrated the efficiency of GAs on different optimization problems, among them, bin–packing, generalized assignment problem, graph partitioning, job–shop scheduling problem, set covering problem, vehicle routing. One of the main operators in GAs is the crossover (i.e. solution recombination). This operator plays a very important role by constructing competitive GAs. In this work, we investigate several crossover operators for the TSP, among them, CX (cycle crossover), PMX (partialy mapped crossover), POS (position based crossover), ER (edge recombination crossover), edge-NN (edge recombination crossover, nearest neighbour) and AP (alternating-positions crossover). Comparison of these crossover operators was performed. The results show high efficiency of the edge-NN, ER and PMX crossovers.

Darbo pradžioje supažindinsiu su gamybinių tvarkaraščių sudarymo uždaviniu. Jo tikslas rasti tvarkaraštį tam tikrai gamybinei situacijai. Uždavinys turi pilnai nusakyti kas ir kur turi įvykti ir apibrėžti visus apribojimus, o gautas sprendinys turi tenkinti šiuos reikalavimus ir vienareikšmiškai nusakyti operacijų vykdymą. Ši problema aktuali gamyklose, personalo valdyme, krovinių gabenime, oro uostuose, traukinių stotyse ir daugelyje kitų. Kadangi matematinis gamybinių tvarkaraščių sudarymo apibūdinimas sudaromas atsižvelgiant į realaus pasaulio problemas, egzistuoja daug šio uždavinio variantų. Dėl to teko pasirinkti kurį konkretų uždavinį nagrinėti. Pirmajame skyriuje supažindinu su šiuo konkrečiu uždaviniu, pateikiu apibrėžimus, s��vokas ir egzistuojančias problemas sprendžiant gamybinių tvarkaraščių uždavinį. Galiausiai parodysiu, kad tai yra sunkiai sprendžiamas ir dėl to vienas iš aktualių kombinatorinio optimizavimo uždavinių. Tuomet plačiau apibūdinu genetinį ir skruzdžių kolonijos optimizavimo algoritmus. Šie algoritmai ir naudojami sprendžiant mano konkret�� gamybinių tvarkaraščių sudarymo uždavinį. Aš apibūdinu visus parametrus ir koeficientus. Vėliau aš pristatau sukurtą programinę įrangą, skirtą rasti spręsti gamybinių tvarkaraščių sudarymo uždavinį ir vaizdžiai pateikti gautus sprendinius. Taip pat grafikų lentelių ir kitų priemonių pagalba pateikiu atliktų eksperimentų rezultatus. Tuomet apžvelgiu gautus rezultatus ir aptariu pastebėtas tendencijas ir... [toliau žr. visą tekstą] / At the begining of this work introduction to the scheduling problem and its basics is given. The goal of a scheduling problem is to make a schedule for a certain production situation. In the problem it is stated what must take place, and the solution describes exactly what should happen at what time. These problems occur in factories, personnel planning, transportation, airfields, railroad stations etcetera. Since mathematical descriptions of scheduling problems are often distilled from practical situations there are many variants of scheduling problems. A selection had to be made which problem is going to be a target of the study. The job shop scheduling problem was chosen. In the first chapter there is definitions of the problems we are trying to solve, introduction of important concepts (properties, bounds, definitions) from the field of scheduling. The last section takes a small detour into theoretical computer science in order to make precise that scheduling problems are hard to solve. In the second chapter introduction of genetic and ant colony optomization algorithms and its basius is given. It is used to solve scheduling problem, which was mentioned before. Introduction of all genetic and ant colony optimization algorithm operators and settings are given here. Then follows the introduction to software witch was made to solve and visualize solutions of scheduling problem. A great number of plots and figures are used in the experimental chapter to explain what... [to full text]

Darbo tikslas – sukurti bendrą prieigos tinklo modeliavimo metodiką bei jos programinę realizaciją, atitinkančią šiuos reikalavimus: • n užduotų prieigos tinklo parametrų reikšmių optimalus nustatymas pagal m užduotų prieigos tinklo kokybės apribojimų, kai n ≥ 1, o m ≥ 0; • optimalus stočių koordinačių nustatymas mobiliojo telefono ryšio tinklui; • optimalus stočių koordinačių nustatymas laidinio telefono ryšio tinklui; Darbo pradžioje apžvelgiamos telekomunikacijų sektoriaus užduotys, kurios gali būti sprendžiamos kombinatorinio optimizavimo metodais. Taipogi pristatomi ir suklasifikuojami galimi šių užduočių sprendimo metodai. Tiriamojoje darbo dalyje pristatomas daugiaparametrinis prieigos tinklo optimizavimo algoritmas integruotas su stočių išdėstymo algoritmais. Stočių išdėstymui pateikiami du meta-euristiniai algoritmai: • Skruzdžių kolonijos algoritmas, papildytas lokalios paieškos procedūra; • Genetinis algoritmas, papildytas lokalios paieškos procedūra. Minėtų algoritmų realizacijos skirstomos pagal šias prieigos tinklo ryšio topologijas: • Mobiliojo telefono ryšio tinklui; • Fiksuoto telefono ryšio tinklui. Esminiai darbe pasiekti rezultatai: • Sukurta universali metodika, leidžianti kurti realius prieigos tinklo modelius; • Sukurta šios metodikos programinė realizacija. Darbe nagrinėjamų uždavinių ir algoritmų pagrindu buvo paskelbti ir pristatyti šie straipsniai: • „Prieigos tinklo parametrų optimalaus... [toliau žr. visą tekstą] / The objective of this work is creation of telecommunication network approach algorithm and its realization. The created algorithm must fulfill following requirements: • optimal values evaluation of n given network approach parameters with m given network approach quality constrains, where n ≥ 1, o m ≥ 0; • optimal solution for transmitters placement problem in mobile phone network; • optimal solution for transmitters placement problem in fixed phone network; In the beginning of this paper we present a set of telecommunication segment problems which can be solved using combinatorial optimization methods. Also we present a set of combinatorial optimization methods which can be used for solving these problems. Finally we present a graphical classification of analyzed problems and connect it with algorithms which are capable for solving it. In the research part of this paper we present a multi parametric network approach optimization algorithm united with algorithms for placing transmitters. Next we present two Meta heuristics based optimization algorithms: • Ant Colony Optimization algorithm with local search procedure; • Genetic algorithm with local search procedure. The realization of these two algorithms depends on the topology of the network approach being analyzed. In this paper we analyze two most common types of network approaches: • Mobile phone network approach; • Fixed phone network approach. The two main achievements of... [to full text]

Baigiamajame darbe nagrinėjami nekilnojamojo turto kadastro žemėlapio žemės sklypų ribų topologiniai nesutapimai, atsirandantys dėl riboženklių koordinačių netikslumų. Nagrinėjama bendras ribas turinčių 5 žemės sklypų grupė, kurios ribos nustatytos kadastrinių matavimu metu, valstybinėje koordinačių sistemoje. Matavimais gautos tų pačių riboženklių koordinačių reikšmės nesutapma dydžiu, kuris yra ne didesnis kaip teisės aktais reglamentuojamas leistinas riboženklių nesutapimas. Nesutapimams panaikinti atliekamas žemės sklypų koordinčių optimizavimas genetinio algoritmo metodu. Optimizavimo uždavinui suformuluoti pasirinkta optimizavimo sąlygą ir ribojimų sistema, paremti teisės aktų reikalavimais. Atliekamas nesutampančių koordinačių optimizavimas, rezultatai analizuojami pagal žemės sklypų plotų pokyčius. Darbe pateikiami tyrimo rezultatai ir išvados. Darbą sudaro: įvadas, keturi skyriai, išvados, literatūros sąrašas. Darbo apimtis - 82 p. Teksto be priedų, 25 iliustr., 33 lent., 25 bibliografiniai šaltiniai. Atskirai pridedami darbo priedai. / In the final work of Master’s degree are analysed topological misalignments between Real Estate Cadastral Map parcel boundaries, that occures due to imprecision of landmark coordinates. The investigation involves a group of 5 parcels with common boundaries, whose cadastral measurements were carried out in the national system of geodetic coordinates. Measured same landmark coordinates, satisfies the required juridical difference between the coordinates of common boundary marks. In order to liquidate misalignments of parcel boundaries, genetic algorithm optimization method of land coordinates is performed. On purpose to develop optimization task, the optimization condition and limitation system were chosen, according to the juridical requirements. The optimization of misaligned coordinates is performed, results of this investigation are analysed by differences of parcel area. Structure: introduction, four sections, conclusions, references. Final work consist of 82 p. text without extras, 25 pictures, 33 tables, 25 bibliographical entries. Appendixes included.