Methods for generation of random numbers in parallel stochastic algorithms for global optimization

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.