Search

Global optimization problems are relevant in various fields of research and industry, such as chemistry, biology, biomedicine, operational research, etc. Normally it is easier to solve optimization problems having some specific properties of objective function such as linearity, convexity, differentiability, etc. However, there are a lot of practical problems that do not satisfy such properties or even cannot be expressed in an adequate mathematical form. Therefore, it is popular to use random search optimization methods in solving such optimization problems. The dissertation deals with investigation of random search global optimization algorithms, their parallelization and application to solve practical problems. The work is focused on modification and parallelization of particle swarm optimization and genetic algorithms. The modification of particle swarm optimization algorithm, based on reduction of the search area is proposed, and several strategies to parallelize the algorithm are investigated. The algorithm is applied to solve Multiple Gravity Assist problem using parallel computing system. A hybrid global multi-objective optimization algorithm is developed by modifying single agent stochastic search strategy, and incorporating it into multi-objective optimization genetic algorithm. Several strategies to parallelize multi-objective optimization genetic algorithm is proposed. Parallel algorithms are experimentally investigated by solving competitive facility location... [to full text] Optimizavimo uždaviniai sutinkami įvairiose mokslo ir pramonės srityse, tokiose kaip chemija, biologija, biomedicina, operacijų tyrimai ir pan. Paprastai efektyviausiai sprendžiami uždaviniai, turintys tam tikras savybes, tokias kaip tikslo funkcijų tiesiškumas, iškilumas, diferencijuojamumas ir pan. Tačiau ne visi praktikoje pasitaikantys optimizavimo uždaviniai tenkina šias savybes, o kartais iš vis negali būti išreiškiami adekvačia matematine išraiška. Tokiems uždaviniam spręsti yra populiarūs atsitiktinės paieškos optimizavimo metodai. Disertacijoje yra tiriami atsitiktinės paieškos optimizavimo metodai, jų lygiagretinimo galimybės ir taikymas praktikoje pasitaikantiems uždaviniams spręsti. Pagrindinis dėmesys skiriamas dalelių spiečiaus optimizavimo ir genetinių algoritmų modifikavimui ir lygiagretinimui. Disertacijoje yra siūloma dalelių spiečiaus optimizavimo algoritmo modifikacija, grįsta pieškos srities siaurinimu, ir tiriamos kelios algoritmo lygiagretinimo strategijos. Algoritmas yra taikomas erdvėlaivių skrydžių trajektorijų optimizavimo uždaviniui spręsti lygiagrečiųjų skaičiavimų sistemose. Taip pat yra siūlomas hibridinis globaliojo daugiakriterio optimizavimo algoritmas, gautas modifikuojant vieno agento stochastinės paieškos algoritmą ir įkomponuojant į daugiakriterio optimizavimo genetinį algoritmą. Siūlomos kelios daugiakriterio genetinio algoritmo lygiagretinimo strategijos. Jų pagrindu gauti lygiagretieji algoritmai eksperimentiškai tiriami sprendžiant... [toliau žr. visą tekstą]

Perfomance of stochastic algorithms for global optimization crucially depends on generation of random numbers. Random number generation methods may vary on features as independence of the generated random numbers, fit to the required distribution, and speed of generation. This paper reviews the main idea and several algorithms for generation of pseudo random numbers. Evaluation criteria of pseudo random numbers generators are also reviewed. Seven widely used random numbers generators (Linear Congruential Generator, Mersenne Twister, Mother At All, C++, Pascal, Matlab and Fortran) are experimentally compared evaluating the distribution of random numbers, correlation of sequences and speed of generation. In parallel computations correlation of sequences may depend on the seed of pseudo random numbers generators. Therefore several ways for construction of the seeds are compared considering correlation of generated sequences of random numbers when computations are performed in parallel computers.

Bendrojo optimizavimo stochastinių algoritmų efektyvumas itin priklauso nuo atsitiktinių skaičių generavimo. Atsitiktinių skaičių generavimo metodai gali skirtis tokiais bruožais, kaip sugeneruotų atsitiktinių skaičių nepriklausomumas, tinkamumas reikiamam skirstiniui ir generavimo greitis. Šiame straipsnyje apžvelgiama pagrindinė idėja ir keletas pseudoatsitiktinių skaičių generavimo algoritmų. Taip pat apžvelgiami pseudoatsitiktinių skaičių generatorių vertinimo kriterijai. Eksperimentiškai lyginami septyni plačiai naudojami atsitiktinių skaičių generatoriai (Linear Congruential Generator, Mersenne Twister, Mother At All, C++, Pascal, Matlab ir Fortran) vertinant atsitiktinių skaičių distribuciją, sekų koreliaciją ir generavimo greitį. Lygiagrečiuosiuose skaičiavimuose sekų koreliacija gali priklausyti nuo pseudoatsitiktinių skaičių generatorių pradinių skaičių. Todėl lyginami keli būdai sudaryti pradinius skaičius atsižvelgiant į sugeneruotų atsitiktinių skaičių sekų koreliaciją skaičiuojant paraleliais kompiuteriais. Performance of stochastic algorithms for global optimization crucially depends on generation of random numbers. Random number generation methods may vary on features as independence of the generated random numbers, fit to the required distribution, and speed of generation. This paper reviews the main idea and several algorithms for generation of pseudo random numbers. Evaluation criteria of pseudo random numbers generators are also reviewed. Seven widely used random numbers generators (Linear Congruential Generator, Mersenne Twister, Mother At All, C++, Pascal, Matlab and Fortran) are experimentally compared evaluating the distribution of random numbers, correlation of sequences and speed of generation. In parallel computations correlation of sequences may depend on the seed of pseudo random numbers generators. Therefore several ways for construction of the seeds are compared considering correlation of generated sequences of random numbers when computations are performed in parallel computers.

This work investigates the tasks of selecting the locations of new objects, mainly emphasizing on reasonable computation time. To solve these types of problems, an algorithm that uses ranking of items of the search area is analyzed. The aim is to create an algorithm which parallel side is as efficient as possible by proposing modifications to the algorithm. These modifications include population of solutions and transferring the logic of search area ranks to the population. The strategies of the two main functions are changed for analyzing the algorithm. The first is the solution generation logic, which is changed between the heuristic solution generation algorithms RDOA and RDOA-D. Second part is the solution evaluation function, which is investigated using the customer selection strategies such as Binary Rule and Partialy Binary Rule. All variants of forementioned strategies are analyzed by comparing the results between sequential and parallel versions with different numbers of processors.

Genetic algorithms are applied to solve different optimization problems, one of them being facility location problem. In this paper, the effectiveness of commonly used strategies such as roulette selection, single point crossover or random mutation, for solving the facility location problem is being studied. Furthermore, a review of the literature on various facility location problems and the principles of genetic algorithms is performed. Based on the review, a specific facility location problem for an entering firm is defined. Moreover, the application of the genetic algorithm strategies for the previously defined facility location problem is described. By applying binary and proportional customer behavior models the previously defined task is used for experimental investigation. After experimentally investigating the effectiveness of different selection, crossover and mutation strategies, two algorithms are constructed from the most effective strategies, which are then tested in the same way. An analytical evaluation of the results obtained from the experiments revealed that different strategies perform best with different client behavior models. In addition, algorithms that are using uniform crossover strategy have displayed the best results and algorithms that consist of best performing strategies did not necessarily demonstrate the best results.

The purpose of this research is to create a novel parallel optimization algorithm while focusing mainly on efficient Pareto ranking strategy. A theoretical background of multi-objective optimization and parallel computing is provided at the first part of the report. Two different Pareto ranking approaches - dominance-rank and dominance-depth - are used for algorithm implementation and hence two separate instances are distinguished. Implementation details of proposed algorithm are comprehensively explained and the performance results of two parallel ranking variants are presented and discussed. The implemented algorithm is applied to solve a facility location problem where two existing companies compete for the market.

Facility location problem is commonly presented as mathematical optimization problem, where different optimization methods are used to solve it. However, some facility location problems cannot be described with an adequate mathematical formula, that is why some of the mathematical optimization methods, e.g. methods which requires fitness function differentiability cannot be used. To solve such problems, in this paper Genetic Algorithm, which is based upon biological knowledge about evolution, Darwin's thoery, where randomly selected generation is able to live freely and by a natural selection process, only the number of best one's survives, is used. Multiple different Genetic Algorithm strategies are tested for their impact to solve the facility location problem.

An obstacle game takes one to two-dimensional space in which three kinds of obstacles exist: walls, flying dragons and abysses. Said obstacles can be avoided by such character's actions as walking, crouching and jumping. The character has an ability to move to a total of four directions (upwards, downwards, left and right). While doing so, it can, but is not obliged to, jump or crouch. Although the only way to avoid walls is by not walking into them (bumping into one results in an instant loss), dragons and abysses can be dodged by jumping or crouching respectively. The goal of the game is to complete levels by reaching objectives in as few moves as possible. Genetic algorithm, applied to a mathematical optimization problem of an obstacle game, looks for an optimal or best available solution by evaluating solutions' fitness values by two criteria: character's distance to an objective and the amount of moves a given solution made. The first population is generated at random. Each individual is evaluated and, with a chance of its fitness value, selected for crossover. Fittest individuals have the highest chance of passing down their genetic information. Fittest parents and children form a population of a new generation. The algorithm is repeated for a set amount of generations. The objective of this work is to construct a Genetic algorithm, capable of efficiently solving an obstacle game.

It is difficult to evaluate a random search algorithms, because regardless of a chosen method of efficiency evaluation, in order to obtain reliable statistical estimates set of experiments and a detailed analysis of the obtained results is required. The work deals with an efficiency evaluation methods of random search algorithms for global optimization. A new algorithm assessment method based on the accuracy of the resulting solution, and the probability of it getting interdependence is proposed in this work. The proposed method has been validated by assessment of well-known random search optimization algorithms efficiency on a set of global optimization test problems. The experimental results showed that the proposed method to obtain estimates show the different algorithms behavioral characteristics such as the ability to find a global solution or attraction of local solutions. The method is also suitable for the efficient comparison of different algorithms efficiency. Thus, this paper presents a new algorithm assessment method, which uses the proposed hypervolume calculation principle and dominance relation. The proposed method provides additional information about the random search algorithms.