On the evolution of recombination in haploids and diploids: I. Deterministic models

In population genetic theory, most analytical and numerical studies of the evolution of recombination have focused on diploid genetics. In studies of the foundations and applications of genetic algorithms (GA's), however, the bit-strings are usually treated as haploid genotypes. In this paper and its companion paper (Bergman et al., 1995), we compare results for the evolutionary dynamics of modifiers of recombination in haploids with results derived for diploids. In this paper, we study the evolution of an allele that controls the rate of recombination between two loci subject to directional selection. It is shown analytically that the fate of a recombination modifier in both haploids and diploids is determined in a complicated way by the sign of the epistasis (interaction in fitness) between the loci, the sign of the initial linkage disequilibrium, and the amount of recombination between the modifier and the genes under selection. This theory is deterministic in that the population is regarded as infinite and no sampling occurs to produce offspring from parents. In the companion paper (Bergman et al., Complexity, 1(2) 1995), we expand upon this work by addressing epistatic interactions among several loci in finite populations.     

Product formulas,nonlinear semigroups,and accretive operators

A special case of our main theorem, when combined with a known result of Brezis and Pazy, shows that in reflexive Banach spaces with a uniformly Gâteaux differentiable norm, resolvent consistency is equivalent to convergence for nonlinear contractive algorithms. (The linear case is due to Chernoff.) The proof uses ideas of Crandall, Liggett, and Baillon. Other applications of our theorem include results concerning the generation of nonlinear semigroups (e.g., a nonlinear Hille-Yosida theorem for “nice” Banach spaces that includes the familiar Hilbert space result), the geometry of Banach spaces, extensions of accretive operators, invariance criteria, and the asymptotic behavior of nonlinear semigroups and resolvents. The equivalence between resolvent consistency and convergence for nonlinear contractive algorithms seems to be new even in Hilbert space. Our nonlinear Hille-Yosida theorem is the first of its kind outside Hilbert space. It establishes a biunique correspondence between m-accretive operators and semigroups on nonexpansive retracts of “nice” Banach spaces and provides affirmative answers to two questions of Kato.     

Theoretical and Empirical Properties of the Genetic Algorithm as a Numerical Optimizer

Abstract

We investigate the basic form of the genetic algorithm as an optimization technique. Its failure to maximize a simple function of a string of 50 binary variables prompts a closer study of Holland's “schema theorem” and we find the implications of this result to be much weaker than are often claimed. Further theoretical results and exact calculations for simple problems provide an understanding of how the genetic algorithm works and why it failed in our original application. We show that the algorithm can be fine tuned to succeed in that problem but only by introducing features that could cause serious difficulties in harder problems.     

Some extremal problems arising from discrete control processes

We consider a simple abstract model for a class of discrete control processes, motivated in part by recent work about the behavior of imperfect random sources in computer algorithms. The process produces a string ofn bits and is a “success” or “failure” depending on whether the string produced belongs to a prespecified setL. In an uninfluenced process each bit is chosen by a fair coin toss, and hence the probability of success is ¦L¦/2 ⁿ . A player called the controller, is introduced who has the ability to intervene in the process by specifying the value of some of the bits of the string. We answer the following questions for both worst and average case: (1) how much can the player increase the probability of success given a fixed number of interventions? (2) in terms of ¦L¦what is the expected number of interventions needed to guarantee success? In particular our results imply that if ¦L¦/2 ⁿ =1/Ω(n) where Ω(n) tends to infinity withn (so the probability of success with no interventions is 0(1)) then withO(√n logΩ(n)) interventions the probability of success is 1?0(1). Our main results and the proof techniques are related to well-known results of Kruskal, Katona and Harper in extremal set theory.     

On the evolution of recombination in haploids and diploids: II. Stochastic models

In this article, we continue an investigation into the evolution of modifiers of recombination, comparing haploid and diploid models begun in Vol. 1, Issue 1, of Complexity. Here, we examine selection schemes that have been used recently in numerical studies of finite diploid populations and ask how recombination evolves in haploid versions of these models. Although the analysis keeps track of the recombination controlling locus rather than the time until a desired bit-string appears, our result may be of use to the practitioners of genetic algorithms (GA's). We find that as a rule high recombination evolves more easily when selection is on haploids than it does in the diploid case. This is especially true of Gaussian selection schemes with high recombination recessive to low recombination. When the fitness regime is more jagged, however, the results depend on the level of jaggedness, with high recombination favored under smoother regimes. We also find that the direction of mutation and dominance relationships among the modifying alleles affect the results. Although there remains much to be done in reconciling population genetic theory with the properties of genetic algorithms, many new and interesting questions have emerged from, and will continue to be stimulated by, interactions between practitioners of each approach.     

A model of concept formation

At first we model the way an intelligence “I” constructs statements from phrases, and then how “I” interlocks these statements to form a string of statements to attain a concept. These strings of statements are called progressions. That is, starting with an initial stimulating relation between two phrases, we study how “I” forms the first statement of the progression and continues from this first statement to form the remaining statements in these progressions to construct a concept. We assume that “I” retains the progressions that it has constructed. Then we show how these retained progressions provide “I” with a platform to incrementally constructs more and more sophisticated conceptual structures. The reason for the construction of these conceptual structures is to achieve additional concepts. Choice plays a very important role in the progression and concept formation. We show that as “I” forms new concepts, it enriches its conceptual structure and makes further concepts attainable. This incremental attainment of concepts is a way in which we humans learn, and this paper studies the attainability of concepts from previously attained concepts. We also study the ability of “I” to apply its progressions and also the ability of “I” to electively manipulate its conceptual structure to achieve new concepts. Application and elective manipulation requires of “I” ingenuity and insight. We also show that as “I” attains new concepts, the conceptual structures change and circumstances arise where unanticipated conceptual discoveries are attainable. As the conceptual structure of “I” is developed, the logical and structural relationships between concepts embedded in this structure also develop. These relationships help “I” understand concepts in the context of other concepts and help “I₁” communicate to another “I₂” information and concept structures. The conceptual structures formed by “I” give rise to a directed web of statement paths which is called a convolution web. The convolution web provides “I” with the paths along which it can reason and obtain new concepts and alternative ways to attain a given concept.This paper is an extension of the ideas introduced in [1]. It is written to be self-contained and the required background is supplied as needed.     

Stock exchange modeling with a price model involving variable variance and correlation coefficients

A price model with variance and correlation coefficients as random processes is analyzed. Parametric analysis is realized by means of “direct” and “inverse” trade algorithms. Results of numerical experiments are obtained on a computer using an INVERT program.     

New reals: Can live with them,can live without them

We give a self‐contained proof of the preservation theorem for proper countable support iterations known as “tools‐preservation”, “Case A” or “first preservation theorem” in the literature. We do not assume that the forcings add reals. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Loop quantum mechanics and the fractal structure of quantum spacetime

We discuss the relation between string quantization based on the Schild path integral and the Nambu-Goto path integral. The equivalence between the two approaches at the classical level is extended to the quantum level by a saddle-point evaluation of the corresponding path integrals. A possible relationship between M-Theory and the quantum mechanics of string loops is pointed out. Then, within the framework of “loop quantum mechanics”, we confront the difficult question as to what exactly gives rise to the structure of spacetime. We argue that the large scale properties of the string condensate are responsible for the effective Riemannian geometry of classical spacetime. On the other hand, near the Planck scale the condensate “evaporates”, and what is left behind is a “vacuum” characterized by an effective fractal geometry.     

Kronecker’s density theorem and irrational numbers in constructive reverse mathematics

To prove Kronecker’s density theorem in Bishop-style constructive analysis one needs to define an irrational number as a real number that is bounded away from each rational number. In fact, once one understands “irrational” merely as “not rational”, then the theorem becomes equivalent to Markov’s principle. To see this we undertake a systematic classification, in the vein of constructive reverse mathematics, of logical combinations of “rational” and “irrational” as predicates of real numbers.     

On n-term approximation with positive coefficients

In this paper, we consider algorithms for constructing n-terms approximations with nonnegative coefficients. The convergence theorem is proved for a “positive” analog of the Pure Greedy Algorithm. We establish a condition on the sequence of weakness coefficients which is sufficient for the convergence of the Positive Weak Greedy Algorithm. This condition is also necessary for the class of monotone sequences.     

A New Approach to Cycling in a 2-locus 2-allele Genetic Model

In the reproductive process new genetic types arise due to crossing over and recombination at the meiotic stage. A simplified biological model will be developed which incorporates this effect and the effect of selection. Although a chromosome may contain thousands of genes we will consider a simplified model consisting of two genetic loci, each containing two alleles of some gene.

The model will be then turned into a difference equation or mapping model x* = G(x,r) where x represents the frequency distribution of genotypes in a certain infinite population, x* is this distribution one generation later and r is the recombination parameter. For a certain choice of fitness and recombination parameters the mapping exhibits several fixed points. As r is varied one of the fixed points of the mapping loses its stability due to a conjugate pair of eigenvalues of the linearized mapping leaving the unit disk. It is shown that the required non-resonance conditions and “nonlinear damping” condition are satisfied and thus the fixed point undergoes a Neimark–Sacker bifurcation to a cycling or oscillatory state.

Once a cycling orbit is established one can conclude that genetic variation (over time) of the population can be maintained. This work reformulates and proves earlier observations of Alan Hastings in a way that makes the treatment of chromosomes with more genetic loci more straightforward.     

关于Lagrange微分中值定理的逆问题

近年来,若干文章对“Lagrange微分中值定理的逆问题”进行了讨论,但其表述均不完整,且证明也较繁琐。本文使用严格凸（严格凹）函数的性质,给出该问题一个条件较弱且表述较完整的结果,其证明也较简洁。     

The affine representation theorem for abstract convex geometries

A convex geometry is a combinatorial abstract model introduced by Edelman and Jamison which captures a combinatorial essence of “convexity” shared by some objects including finite point sets, partially ordered sets, trees, rooted graphs. In this paper, we introduce a generalized convex shelling, and show that every convex geometry can be represented as a generalized convex shelling. This is “the representation theorem for convex geometries” analogous to “the representation theorem for oriented matroids” by Folkman and Lawrence. An important feature is that our representation theorem is affine-geometric while that for oriented matroids is topological. Thus our representation theorem indicates the intrinsic simplicity of convex geometries, and opens a new research direction in the theory of convex geometries.     

Computer Literacy: An Evolving Concept

The term “computer literacy” became very popular in the 1980s as a catch phrase describing a new type of understanding. Prior to the phrase's popularity, “literacy” was reserved for the knowledge of basic skills in reading and writing and familiarity with the classical works and great books of ancient and modern cultures. To be literate means to be educated regarding the fundamental or basic ideas, beliefs and methods of communication in society. By applying the term “literacy” to the knowledge of computers, society is signifying that this sort of knowledge is as important to a person's education in contemporary society as knowledge of reading and writing has been in the past (Ringle, 1981). While many people seem to agree that the proliferation of computers and their application in extensive areas of human endeavor require us to take the notion of literacy seriously, there is still no consensus as to how this educational goal should be achieved. The difficulty stems from the fact that there is no universally accepted definition of computer literacy. Until educators are clear about the goal, effective ways to attain the objective of computer literacy will be clouded by confusion. The purpose of this research is to examine the historical evolution of the phrase “computer literacy,” to develop a chronological continuum of computer literacy, and to identify several competencies that will likely characterize the computer literate teacher in the 1990s.     

PLF.sets的实证研究及其高质量仿真应用

为高效率与高质量仿真城市人口迁移与演变趋势, 基于Zadeh模糊集的基础知识, 引入哲学否定与计算机逻辑中对立否定、中介否定和矛盾否定的概念。在反复研究和论证了三种逻辑否定之间的内在关系、基本特征和融合条件后, 创新性地提出了PLF.sets泛逻辑性模糊集, 形成可直接参与计算的多种逻辑变量及其演变形式的评价因数集。PLF.sets在饱和验证其运算规则和逻辑转化可行性的前提下, 通过已知局部隶属函数g(x)构建出逼近性能良好的整体隶属度函数f(x)。它能够在确定的值域U[a, b]内, 使得任意的x(x∈U)映射于f(x)值。并在高度仿真和逼近原始系统规律的同时, 逻辑简化系统函数产生的复杂性计算。PLF.Sets于《管理信息系统》教学质量评价的实证研究结果充分证明, PLF.sets方法可以化繁为简, 简化运算方法和步骤;显示出高效性、准确性、普适性和简洁性的特点。PLF.sets方法在对北京城市人口迁移与演变趋势仿真的应用表明:(1)北京城市人口流动变化净增加值的定位均是“多”的等级;(2)北京城市人口流动网络及其关联度特征的定性等级均是“高”级别。最终高质量地评估了正向迁移城市的人口流动格局、人口迁移与演变趋势。     

How real are virtual realities,how virtual is reality?—Constructive re-interpretation of physical undecidability

Throughout the ups and downs of scientific world conception there has been a persistent vision of a world which is understandable by human reasoning. In a contemporary, recursion theoretic, comprehension, the term “reasoning” is interpretable as “constructive” or, more specifically, “mechanically computable.” An expression of this statement is the assumption that our universe is generated by the action of some deterministic computing agent; or, stated pointedly, that we are living in a computer-generated universe. Physics then reduces to the investigation of the intrinsic, “inner view” of a particular virtual reality which happens to be our universe. In this interpretation, formal logic, mathematics and the computer sciences are just the physical sciences of more general “virtual” realities, irrespective of whether they are “really” realized or not. We shall study several aspects of this conception, among them the conjecture that randomness in physics can be constructively reinterpreted to correspond to uncomputability and undecidability in mathematics. We shall also attack the nonconstructive feature of classical physics by showing its inconsistency. Another concern is the modeling of interfaces, i.e., the means and methods of communication between two universes. On a speculative level, this may give some clue on such notorious questions such as the occurrence of “miracles” or on the “mind-body problem.”     

Some Computational Aspects of Geodesic Convex Sets in a Simple Polygon

In this article, we deal with some computational aspects of geodesic convex sets. Motzkin-type theorem, Radon-type theorem, and Helly-type theorem for geodesic convex sets are shown. In particular, given a finite collection of geodesic convex sets in a simple polygon and an “oracle,” which accepts as input three sets of the collection and which gives as its output an intersection point or reports its nonexistence; we present an algorithm for finding an intersection point of this collection.