A novel dynamic model of pseudo random number generator

An interesting hierarchy of random number generators is introduced in this paper based on the review of random numbers characteristics and chaotic functions theory. The main objective of this paper is to produce an ergodic dynamical system which can be implemented in random number generators. In order to check the efficacy of pseudo random number generators based on this map, we have carried out certain statistical tests on a series of numbers obtained from the introduced hierarchy. The results of the tests were promising, as the hierarchy passed the tests satisfactorily, and offers a great capability to be employed in a pseudo random number generator.     

A novel fuzzy C-means algorithm to generate diverse and desirable cluster solutions used by genetic-based clustering ensemble algorithms

One of the most significant discussions in the field of machine learning today is on the clustering ensemble. The clustering ensemble combines multiple partitions generated by different clustering algorithms into a single clustering solution. Genetic algorithms are known for their high ability to solve optimization problems, especially the problem of the clustering ensemble. To date, despite the major contributions to find consensus cluster partitions with application of genetic algorithms, there has been little discussion on population initialization through generative mechanisms in genetic-based clustering ensemble algorithms as well as the production of cluster partitions with favorable fitness values in first phase clustering ensembles. In this paper, a threshold fuzzy C-means algorithm, named TFCM, is proposed to solve the problem of diversity of clustering, one of the most common problems in clustering ensembles. Moreover, TFCM is able to increase the fitness of cluster partitions, such that it improves performance of genetic-based clustering ensemble algorithms. The fitness average of cluster partitions generated by TFCM are evaluated by three different objective functions and compared against other clustering algorithms. In this paper, a simple genetic-based clustering ensemble algorithm, named SGCE, is proposed, in which cluster partitions generated by the TFCM and other clustering algorithms are used as the initial population used by the SGCE. The performance of the SGCE is evaluated and compared based on the different initial populations used. The experimental results based on eleven real world datasets demonstrate that TFCM improves the fitness of cluster partitions and that the performance of the SGCE is enhanced using initial populations generated by the TFCM.     

A true random number generator based on mouse movement and chaotic cryptography

True random number generators are in general more secure than pseudo random number generators. In this paper, we propose a novel true random number generator which generates a 256-bit random number by computer mouse movement. It is cheap, convenient and universal for personal computers. To eliminate the effect of similar movement patterns generated by the same user, three chaos-based approaches, namely, discretized 2D chaotic map permutation, spatiotemporal chaos and “MASK” algorithm, are adopted to post-process the captured mouse movements. Random bits generated by three users are tested using NIST statistical tests. Both the spatiotemporal chaos approach and the “MASK” algorithm pass the tests successfully. However, the latter has a better performance in terms of efficiency and effectiveness and so is more practical for common personal computer applications.     

Scatter Search for the 0–1 Multidimensional Knapsack Problem

The evolutionary metaheuristic called scatter search has been applied successfully to optimization problems for several years. In this paper, we apply the scatter search technique to the well-known 0–1 multidimensional knapsack problem. We propose a new relaxation-based diversification generator, which produces an initial population with elite solutions. The computational results obtained for a set of classic and correlated instances clearly show that (1) this generator can also be used as a heuristic for solving the multidimensional knapsack problem; (2) using the population produced by our generator as a starting point for the scatter search algorithm leads to better performance. We also enhance the scatter search algorithm by integrating memory and by using adapted intensification phases. Overall, the results are interesting and competitive compared to other population-based algorithms, such as genetic algorithms.      

On a Feasible–Infeasible Two-Population (FI-2Pop) genetic algorithm for constrained optimization: Distance tracing and no free lunch

We explore data-driven methods for gaining insight into the dynamics of a two-population genetic algorithm (GA), which has been effective in tests on constrained optimization problems. We track and compare one population of feasible solutions and another population of infeasible solutions. Feasible solutions are selected and bred to improve their objective function values. Infeasible solutions are selected and bred to reduce their constraint violations. Interbreeding between populations is completely indirect, that is, only through their offspring that happen to migrate to the other population. We introduce an empirical measure of distance, and apply it between individuals and between population centroids to monitor the progress of evolution. We find that the centroids of the two populations approach each other and stabilize. This is a valuable characterization of convergence. We find the infeasible population influences, and sometimes dominates, the genetic material of the optimum solution. Since the infeasible population is not evaluated by the objective function, it is free to explore boundary regions, where the optimum is likely to be found. Roughly speaking, the No Free Lunch theorems for optimization show that all blackbox algorithms (such as Genetic Algorithms) have the same average performance over the set of all problems. As such, our algorithm would, on average, be no better than random search or any other blackbox search method. However, we provide two general theorems that give conditions that render null the No Free Lunch results for the constrained optimization problem class we study. The approach taken here thereby escapes the No Free Lunch implications, per se.     

常见随机数发生器的缺陷及组合随机数发生器的理论与实践

随机数是蒙特卡罗 Monte- Carlo方法的基础 .本文首先指出线性同余法和移位寄存器 (亦称 Tausworthe)序列等常见随机数发生器的一些缺陷 ;在此基础上介绍可产生具有优良品质随机数的组合发生器。本文既介绍理论结果 ,用以证明组合发生器确实可以优于单个发生器 ;也具体构造了几个可供实际使用的组合随机数发生器。严格而全面的统计检验表明 ,它们可以产生具有优良品质的随机数     

Re-seeding invalidates tests of random number generators

Kim et al. [C. Kim, G.H. Choe, D.H. Kim, Test of randomness by the gambler’s ruin algorithm, Applied Mathematics and Computation 199 (2008) 195-210] recently presented a test of random number generators based on the gambler’s ruin problem and concluded that several generators, including the widely used Mersenne Twister, have hidden defects. We show here that the test by Kim et al. suffers from a subtle, but consequential error: re-seeding the pseudorandom number generator with a fixed seed for each starting point of the gambler’s ruin process induces a random walk of the test statistic as a function of the starting point. The data presented by Kim et al. are thus individual realizations of a random walk and not suited to judge the quality of pseudorandom number generators. When generating or analyzing the gambler’s ruin data properly, we do not find any evidence for weaknesses of the Mersenne Twister and other widely used random number generators.     

Design of Practical and Provably Good Random Number Generators

We present a construction for a family of pseudo-random generators that are very fast in practice, yet possess provable statistical and cryptographic unpredictability properties. Such generators are useful for simulations, randomized algorithms, and cryptography.Our starting point is a slow but high quality generator whose use can be mostly confined to a preprocessing step. We give a method of stretching its outputs that yields a faster generator. The fast generator offers smooth memory–time–security trade-offs and also has many desired properties that are provable. The slow generator can be based on strong one-way permutations or block ciphers. Our implementation based on the block cipher DES is faster than popular generators.     

A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem

This paper deals with a general job shop scheduling problem with multiple constraints, coming from printing and boarding industry. The objective is the minimization of two criteria, the makespan and the maximum lateness, and we are interested in finding an approximation of the Pareto frontier. We propose a fast and elitist genetic algorithm based on NSGA-II for solving the problem. The initial population of this algorithm is either randomly generated or partially generated by using a tabu search algorithm, that minimizes a linear combination of the two criteria. Both the genetic and the tabu search algorithms are tested on benchmark instances from flexible job shop literature and computational results show the interest of both methods to obtain an efficient and effective resolution method.     

Solving the Graphical Steiner Tree Problem Using Genetic Algorithms

We develop a genetic algorithm (GA) to solve the Steiner Minimal Tree problem in graphs. To apply the GA paradigm, a simple bit string representation is used, where a 1 or 0 corresponds to whether or not a node is included in the solution tree. The standard genetic operators — selection, crossover and mutation — are applied to both random and seeded initial populations of representations. Various parameters within the algorithm have to be set and we discuss how and why we have selected the values used. A standard set of graph problems used extensively in the comparison of Steiner tree algorithms has been solved using our resulting algorithm. We report our results (which are encouragingly good) and draw conclusions.     

An effective architecture for learning and evolving flexible job-shop schedules

In recent years, the interaction between evolution and learning has received much attention from the research community. Some recent studies on machine learning have shown that it can significantly improve the efficiency of problem solving when using evolutionary algorithms. This paper proposes an architecture for learning and evolving of Flexible Job-Shop schedules called LEarnable Genetic Architecture (LEGA). LEGA provides an effective integration between evolution and learning within a random search process. Unlike the canonical evolution algorithm, where random elitist selection and mutational genetics are assumed; through LEGA, the knowledge extracted from previous generation by its schemata learning module is used to influence the diversity and quality of offsprings. In addition, the architecture specifies a population generator module that generates the initial population of schedules and also trains the schemata learning module. A large range of benchmark data taken from literature and some generated by ourselves are used to analyze the efficacy of LEGA. Experimental results indicate that an instantiation of LEGA called GENACE outperforms current approaches using canonical EAs in computational time and quality of schedules.     

Entropy-based evaluation function in a multi-objective approach for the investigation of the genetic code robustness

The genetic code is the interface between the genetic information stored in DNA molecules and the proteins. Considering the hypothesis that the genetic code evolved to its current structure, some researches use optimization algorithms to find hypothetical codes to be compared to the canonical genetic code. For this purpose, a function with only one objective is employed to evaluate the codes, generally a function based on the robustness of the code against mutations. Very few random codes are better than the canonical genetic code when the evaluation function based on robustness is considered. However, most codons are associated with a few amino acids in the best hypothetical codes when only robustness is employed to evaluate the codes, what makes hard to believe that the genetic code evolved based on only one objective, i.e., the robustness against mutations. In this way, we propose here to use entropy as a second objective for the evaluation of the codes. We propose a Pareto approach to deal with both objectives. The results indicate that the Pareto approach generates codes closer to the canonical genetic code when compared to the codes generated by the approach with only one objective employed in the literature.     

The Absolute of Finitely Generated Groups: II. The Laplacian and Degenerate Parts

The article continues a series of papers on the absolute of finitely generated groups. The absolute of a group with a fixed system of generators is defined as the set of ergodic Markov measures for which the system of cotransition probabilities is the same as for the simple (right) random walk generated by the uniform distribution on the generators. The absolute is a new boundary of a group, generated by random walks on the group.We divide the absolute into two parts, Laplacian and degenerate, and describe the connection between the absolute, homogeneous Markov processes, and the Laplace operator; prove that the Laplacian part is preserved under taking certain central extensions of groups; reduce the computation of the Laplacian part of the absolute of a nilpotent group to that of its abelianization; consider a number of fundamental examples (free groups, commutative groups, the discrete Heisenberg group).     

Genetic algorithms in random environments: two examples

We study the asymptotic behavior of two mutation-selection genetic algorithms in random environments. First, the state space is a supercritical Galton-Watson tree conditioned upon non-extinction and the objective function is the distance from the root. In the second case, the state space is a regular tree and the objective function is a sample of a tree-indexed random walk. We prove that, after n steps, the algorithms find the maximum possible value of the objective function up to a finite random constant.     

On Dual Gabor Frame Pairs Generated by Polynomials

We provide explicit constructions of particularly convenient dual pairs of Gabor frames. We prove that arbitrary polynomials restricted to sufficiently large intervals will generate Gabor frames, at least for small modulation parameters. Unfortunately, no similar function can generate a dual Gabor frame, but we prove that almost any such frame has a dual generated by a B-spline. Finally, for frames generated by any compactly supported function φ whose integer-translates form a partition of unity, e.g., a B-spline, we construct a class of dual frame generators, formed by linear combinations of translates of φ. This allows us to chose a dual generator with special properties, for example, the one with shortest support, or a symmetric one in case the frame itself is generated by a symmetric function. One of these dual generators has the property of being constant on the support of the frame generator.     

An efficient lattice reduction method for F2-linear pseudorandom number generators using Mulders and Storjohann algorithm

Recent simulations often use highly parallel machines with many processors, and they need many pseudorandom number generators with distinct parameter sets, and hence we need an effective fast assessment of the generator with a given parameter set. Linear generators over the two-element field are good candidates, because of the powerful assessment via their dimensions of equidistribution. Some efficient algorithms to compute these dimensions use reduced bases of lattices associated with the generator. In this article, we use a fast lattice reduction algorithm by Mulders and Storjohann instead of Schmidt’s algorithm, and show that the order of computational complexity is lessened. Experiments show an improvement in the speed by a factor of three. We also report that just using a sparsest initial state (i.e., consisting of all 0 bits except one) significantly accelerates the lattice computation, in the case of Mersenne Twister generators.     

基于遗传算法的二层线性规划问题的求解算法

本研究了下层以最优解返回上层的二层线性规划问题的遗传算法。在提出可行度概念的基础上，构造了二层线性规划上层规划问题的适应度函数，由此设计了求解二层线性规划问题遗传算法。为了提高遗传算法处理约束的能力，在产生初始种群时将随机产生的初始种群变为满足约束的初始种群，从而避免了使用罚函数处理约束带来的困难，最后用实例验证了本提出的二层线性规划的遗传算法的有效性。     

A stochastic population projection system based on general age-dependent branching processes

"Algorithms for a stochastic population process, based on assumptions underlying general age-dependent branching processes in discrete time with time inhomogeneous laws of evolution, are developed through the use of a new representation of basic random functions involving birth cohorts and random sums of random variables. New algorithms provide a capability for computing the mean age structure of the process as well as variances and covariances, measuring variation about means. Four exploratory population projections, testing the implications of the algorithms for the case of time-homogeneous laws of evolution, are presented. Formulas extending mean and variance functions for unit population projections...are also presented. These formulas show that, in population processes with non-random laws of evolution, stochastic fluctuations about the mean function are negligible when initial population size is large. Further extensions of these formulas to the case of randomized laws of evolution suggest that stochastic fluctuations about the mean function can be significant even for large initial populations."     

Uniform Uniform Exponential Growth of Subgroups of the Mapping Class Group

Let Mod(S) denote the mapping class group of a compact, orientable surface S. We prove that finitely generated subgroups of Mod(S) which are not virtually abelian have uniform exponential growth with minimal growth rate bounded below by a constant depending only, and necessarily, on S. For the proof, we find in any such subgroup explicit free group generators which are “short” in any word metric. Besides bounding growth, this allows a bound on the return probability of simple random walks.