Error thresholds for quasispecies on dynamic fitness landscapes

In this paper we investigate error thresholds on dynamic fitness landscapes. We show that there exists both a lower and an upper threshold, representing limits to the copying fidelity of simple replicators. The lower bound can be expressed as a correction term to the error threshold present on a static landscape. The upper error threshold is a new limit that only exists on dynamic fitness landscapes. We also show that for long genomes and/or highly dynamic fitness landscapes there exists a lower bound on the selection pressure required for the effective selection of genomes with superior fitness independent of mutation rates, i.e. there are distinct nontrivial limits to evolutionary parameters in dynamic environments.     

Dynamic fitness landscapes in molecular evolution

We study self-replicating molecules under externally varying conditions. Changing conditions such as temperature variations and/or alterations in the environment's resource composition lead to both non-constant replication and decay rates of the molecules. In general, therefore, molecular evolution takes place in a fluctuating rather than a static fitness landscape. We incorporate dynamic replication and decay rates into the standard quasispecies theory of molecular evolution, and show that for periodic time-dependencies, a system of evolving molecules enters a limit cycle for t→∞. For fast periodic changes, we show that molecules adapt to the time-averaged fitness landscape, whereas for slow changes they track the variations in the landscape arbitrarily closely. We derive a general approximation method that allows us to calculate the attractor of time-periodic landscapes, and demonstrate using several examples that the results of the approximation and the limiting cases of very slow and very fast changes are in perfect agreement. We also discuss landscapes with arbitrary time dependencies, and show that very fast changes again lead to a system that adapts to the time-averaged landscape. Finally, we analyze the dynamics of a finite population of molecules in a dynamic landscape, and discuss its relation to the infinite population limit.     

Evolutionary Accessibility in Tunably Rugged Fitness Landscapes

The adaptive evolution of a population under the influence of mutation and selection is strongly influenced by the structure of the underlying fitness landscape, which encodes the interactions between mutations at different genetic loci. Theoretical studies of such landscapes have been carried out for several decades, but only recently experimental fitness measurements encompassing all possible combinations of small sets of mutations have become available. The empirical studies have spawned new questions about the accessibility of optimal genotypes under natural selection. Depending on population dynamic parameters such as mutation rate and population size, evolutionary accessibility can be quantified through the statistics of accessible mutational pathways (along which fitness increases monotonically), or through the study of the basin of attraction of the optimal genotype under greedy (steepest ascent) dynamics. Here we investigate these two measures of accessibility in the framework of Kauffman’s LK-model, a paradigmatic family of random fitness landscapes with tunable ruggedness. The key parameter governing the strength of genetic interactions is the number K of interaction partners of each of the L sites in the genotype sequence. In general, accessibility increases with increasing genotype dimensionality L and decreases with increasing number of interactions K. Remarkably, however, we find that some measures of accessibility behave non-monotonically as a function of K, indicating a special role of the most sparsely connected, non-trivial cases K=1 and 2. The relation between models for fitness landscapes and spin glasses is also addressed.     

应用遗传算法和序列锥规划进行圆阵的方向图综合

为了解决圆阵方向图旁瓣电平较高的问题,提出了一种圆阵方向图综合方法。该方法将圆阵方向图的峰值旁瓣电平作为目标函数,首先采用改进遗传算法对阵元位置和阵元权值进行联合优化,不仅避免了算法的早熟收敛,而且符合理论意义上的全局最优。其次将遗传算法的优化结果作为初始迭代点,在其附近利用一阶泰勒级数将非凸的圆阵方向图综合问题转化为序列锥规划问题,以便采用凸优化理论进行高效求解。由于该算法增加了寻优操作的后期变异能力,因而有效提高了优化性能。最后仿真表明,阵元数一定的情况下,算法在进一步降低峰值旁瓣电平的同时,可有效减小其动态变化范围,使得圆阵方向图综合性能更优。      

Adaptive walks with noisy fitness measurements

Summary Adaptive walks constitute an optimization technique for searching a space of possible solutions, for example, a space of different molecules. The goal is to find a point in space (a molecule) that is optimal or near-optimal in some property, generally referred to as the fitness, such as its ability to bind to a given receptor. Adaptive walking, an analog of natural selection, is a powerful technique for searching landscapes. However, errors in the measurements will cause errors in the adaptive walks. Mutant molecules of higher fitness may be ignored or mutants of lower fitness may be accepted. To examine the effect of measurement error on adaptive walks, we simulate single-agent hill-climbing walks on NK landscapes of varying ruggedness where Gaussian noise is added to the fitness values to model measurement error. We consider both constant measurement noise and noise whose variance decays exponentially with fitness. We show that fitness-independent noise can cause walks to melt off the peaks in a landscape, wandering in larger regions as the noise increases. However, we also show that a small amount of noise actually helps the walk perform better than with no noise. For walks in which noise decreases exponentially with fitness, the most characteristic behavior is that the walk meanders throughout the landscape until it stumbles across a point of relatively high fitness, then it climbs the landscape towards the nearest peak. Finally, we characterize the balance between selection pressure and noise and show that there are several classes of walk dynamic behavior.     

TOPOLOGY DESIGN OF STRUCTURES SUBJECTED TO PERIODIC LOADING

Although a lot of attention in the topology optimization literature has focused on the optimization of eigenfrequencies in free vibration problems, relatively little work has been done on the optimization of structures subjected to periodic loading. In this paper, we propose two measures, one global and the other local, for the minimization of vibrations of structures subjected to periodic loading. The global measure which we term as the “dynamic compliance” reduces the vibrations in an overall sense, and thus has important implications from the viewpoint of reducing the noise radiated from a structure, while the local measure reduces the vibrations at a user-defined point. Both measures bring about a reduction in the vibration level by moving the natural frequencies which contribute most significantly to the measures, away from the driving frequencies, although, as expected, in different ways. Quite surprisingly, the structure of the dynamic compliance optimization problem turns out to be very similar to the structure of the static compliance optimization problem. The availability of analytical sensitivities results in an efficient algorithm for both measures. We show the effectiveness of the measures by presenting some numerical examples.     

Adaptive extremal optimization by detrended fluctuation analysis

Global optimization is one of the key challenges in computational physics as several problems, e.g. protein structure prediction, the low-energy landscape of atomic clusters, detection of community structures in networks, or model-parameter fitting can be formulated as global optimization problems. Extremal optimization (EO) has become in recent years one particular, successful approach to the global optimization problem. As with almost all other global optimization approaches, EO is driven by an internal dynamics that depends crucially on one or more parameters. Recently, the existence of an optimal scheme for this internal parameter of EO was proven, so as to maximize the performance of the algorithm. However, this proof was not constructive, that is, one cannot use it to deduce the optimal parameter itself a priori. In this study we analyze the dynamics of EO for a test problem (spin glasses). Based on the results we propose an online measure of the performance of EO and a way to use this insight to reformulate the EO algorithm in order to construct optimal values of the internal parameter online without any input by the user. This approach will ultimately allow us to make EO parameter free and thus its application in general global optimization problems much more efficient.     

A Family of Fitness Landscapes Modeled through Gene Regulatory Networks

Fitness landscapes are a powerful metaphor for understanding the evolution of biological systems. These landscapes describe how genotypes are connected to each other through mutation and related through fitness. Empirical studies of fitness landscapes have increasingly revealed conserved topographical features across diverse taxa, e.g., the accessibility of genotypes and “ruggedness”. As a result, theoretical studies are needed to investigate how evolution proceeds on fitness landscapes with such conserved features. Here, we develop and study a model of evolution on fitness landscapes using the lens of Gene Regulatory Networks (GRNs), where the regulatory products are computed from multiple genes and collectively treated as phenotypes. With the assumption that regulation is a binary process, we prove the existence of empirically observed, topographical features such as accessibility and connectivity. We further show that these results hold across arbitrary fitness functions and that a trade-off between accessibility and ruggedness need not exist. Then, using graph theory and a coarse-graining approach, we deduce a mesoscopic structure underlying GRN fitness landscapes where the information necessary to predict a population’s evolutionary trajectory is retained with minimal complexity. Using this coarse-graining, we develop a bottom-up algorithm to construct such mesoscopic backbones, which does not require computing the genotype network and is therefore far more efficient than brute-force approaches. Altogether, this work provides mathematical results of high-dimensional fitness landscapes and a path toward connecting theory to empirical studies.     

Adaptive extremal optimization by detrended fluctuation analysis

Global optimization is one of the key challenges in computational physics as several problems, e.g. protein structure prediction, the low-energy landscape of atomic clusters, detection of community structures in networks, or model-parameter fitting can be formulated as global optimization problems. Extremal optimization (EO) has become in recent years one particular, successful approach to the global optimization problem. As with almost all other global optimization approaches, EO is driven by an internal dynamics that depends crucially on one or more parameters. Recently, the existence of an optimal scheme for this internal parameter of EO was proven, so as to maximize the performance of the algorithm. However, this proof was not constructive, that is, one cannot use it to deduce the optimal parameter itself a priori. In this study we analyze the dynamics of EO for a test problem (spin glasses). Based on the results we propose an online measure of the performance of EO and a way to use this insight to reformulate the EO algorithm in order to construct optimal values of the internal parameter online without any input by the user. This approach will ultimately allow us to make EO parameter free and thus its application in general global optimization problems much more efficient.     

Computation rate maximization for IRS-enhanced dynamic spectrum access assisted MEC system

Intelligent reflecting surface (IRS)-enhanced dynamic spectrum access (DSA) is a promising technology to enhance the performance of the mobile edge computing (MEC) system. In this paper, we consider the integration of the IRS enhanced DSA technology to a MEC system, and study the pertinent joint optimization of the phase shift coefficients of the IRS, the transmission powers, the central processing unit (CPU) frequencies, as well as the task offloading time allocations of the secondary users (SUs) to maximize the average computation bits of the SUs. Due to the non-convexity, the formulated problem is difficult to solve. In order to tackle this difficulty, we decompose the optimization problem into tractable subproblems and propose an alternating optimization algorithm to optimize the optimization variables in an iterative fashion. Numerical results are provided to show the effectiveness and the correctness of the proposed algorithm.     

基于混合群智能优化算法的混沌系统参数估计

混沌系统的未知系统参数估计是实现混沌控制和同步的首要问题,通过构造一个合理的适应度函数,可将其转化为一个多维搜索空间的优化问题.提出一种融合改进骨干粒子群算法与改进差分进化算法的混合群智能优化方法来解决上述优化问题.对骨干粒子群算法中的粒子位置更新机制以及差分进化算法中的变异操作、交叉操作、交叉概率因子的设计等进行改进,有效兼顾了种群的多样性与算法的收敛性.在此基础上,讨论骨干粒子群优化算法与差分进化的融合优化策略,实现两个算法的协同进化,进一步提高算法的综合优化性能.用6个基准测试函数以及Lorenz混沌系统为例进行仿真实验,结果表明该方法具有全局寻优能力强、收敛速度快、搜索精度高、稳健性好等优点.     

一种求解级联拉曼光纤激光器的方法

 根据适应度函数的具体情况改进了微粒群算法,与基本微粒群算法相比,其复杂函数的寻优能力得到了提高。利用改进的微粒群算法对不同结构的拉曼光纤激光器理论模型对应的适应度函数进行了算法测试,保证适应度函数精度(10^-5)的情况下,计算时间不超过15 s。与Newton-Raphson打靶算法配合时,有效地缩短计算时间、提高打靶算法稳定性和计算精度。最后,利用该算法数值分析了二阶掺磷拉曼光纤激光器输出端反射率、光纤长度和泵浦功率对输出功率的影响。     

Error Thresholds in Single-Peak Gaussian Distributed Fitness Landscapes

Based on the Eigen and Crow-Kimura models with a single-peak fitness landscape, we propose the fitness values of all sequence types to be Gausslan distributed random variables to incorporate the effects of the fluctuations of the fitness landscapes （noise of environments） and investigate the concentration distribution and error threshold of quasispecies by performing an ensemble average within this theoretical framework. We find that a small fluctuation of the fitness landscape causes only a slight change in the concentration distribution and error threshold, which implies that the error threshold is stable against small perturbations. However, for a sizable fluctuation, quite different from the previous deterministic models, our statistical results show that the transition from quasi-species to error catastrophe is not so sharp, indicating that the error threshold is located within a certain range and has a shift toward a larger value. Our results are qualitatively in agreement with the experimental data and provide a new implication for antiviral strategies.     

Influence of rounding errors on the quality of heuristic optimization algorithms

Search space smoothing and related heuristic optimization algorithms provide an alternative approach to simulated annealing and its variants: while simulated annealing traverses barriers in the energy landscape at finite temperatures, search space smoothing intends to remove these barriers, so that a greedy algorithm is sufficient to find the global minimum. Several formulas for smoothing the energy landscape have already been applied, one of them making use of the finite numerical precision on a computer. In this paper, we thoroughly investigate the effect of finite numerical accuracy on the quality of results achieved with heuristic optimization algorithms. We present computational results for the traveling salesman problem.     

Joint optimization of component carrier selection and resource allocation in 5G carrier aggregation system

In this paper, we consider joint optimization of Component Carrier (CC) selection and resource allocation in 5G Carrier Aggregation (CA) system. Firstly, the upper-bound system throughput with determined number of CCs is derived and it is proved by using graph theory that the throughput optimization problem is NP hard. Then we propose a greedy based algorithm to solve this problem and prove that the proposed algorithm can achieve at least 1/2 of the optimal performance in the worst case. At last, we evaluate the throughput and computational complexity performance through a variety of simulations. Simulation results show that the proposed algorithm can obtain better performance comparing with existing schemes while keeping the computation complexity at an acceptable level.     

Adaptation dynamics of the quasispecies model

We study the adaptation dynamics of an initially maladapted population evolving via the elementary processes of mutation and selection. The evolution occurs on rugged fitness landscapes which are defined on the multi-dimensional genotypic space and have many local peaks separated by low fitness valleys. We mainly focus on the Eigen’s model that describes the deterministic dynamics of an infinite number of self-replicating molecules. In the stationary state, for small mutation rates such a population forms a quasispecies which consists of the fittest genotype and its closely related mutants. The quasispecies dynamics on rugged fitness landscape follow a punctuated (or steplike) pattern in which a population jumps from a low fitness peak to a higher one, stays there for a considerable time before shifting the peak again and eventually reaches the global maximum of the fitness landscape. We calculate exactly several properties of this dynamical process within a simplified version of the quasispecies model.      

基于文化遗传算法的水浴温度模糊控制器设计

水浴温度控制普遍存在滞后、超调、波动性大等特点,且难以建立精确的数学模型,一般采用模糊控制器实现对水浴温度的控制,但模糊控制规则具有较强的主观性,其控制性能往往达不到客观要求。研究遗传算法在模糊控制规则寻优上的应用,将其和文化算法相结合,构成一种具有双层协同进化机制的文化遗传算法,采用专家经验的知识信息构成信仰空间作为指导方向,然后在群体空间中进行遗传算法操作,选取群体中适应度值较高的个体更新信仰空间,再通过迭代优化,得到适应度值高的个体,将其作为优化的模糊控制规则。仿真实验表明,优化后的规则在控制过程中的动态温度跟踪和稳态误差方面均具有较好的效果。     

无人机姿态控制器设计及仿真

由于无人机模型的非线性和参数的时变性,传统PID方法设计的控制器动静态性能可能会变得很差,针对这种问题,设计了适合于某型无人机的模糊自适应姿态控制器。对于模糊控制器的隶属函数选择中盲目性的问题,利用粒子群优化算法对隶属函数进行智能寻优,降低设计过程中专家主观意向对控制器性能不确定性的影响。仿真结果表明,本文设计的控制器相对传统PID有更好的动静态性能,并且对于模型参数的时变性具有一定的鲁棒性。     

Optimization of ultra-fast interactions using laser pulse temporal shaping controlled by a deterministic algorithm

Femtosecond laser pulse temporal shaping techniques have led to important advances in different research fields like photochemistry, laser physics, non-linear optics, biology, or materials processing. This success is partly related to the use of optimal control algorithms. Due to the high dimensionality of the solution and control spaces, evolutionary algorithms are extensively applied and, among them, genetic ones have reached the status of a standard adaptive strategy. Still, their use is normally accompanied by a reduction of the problem complexity by different modalities of parameterization of the spectral phase. Exploiting Rabitz and co-authors’ ideas about the topology of quantum landscapes, in this work we analyze the optimization of two different problems under a deterministic approach, using a multiple one-dimensional search (MODS) algorithm. In the first case we explore the determination of the optimal phase mask required for generating arbitrary temporal pulse shapes and compare the performance of the MODS algorithm to the standard iterative Gerchberg–Saxton algorithm. Based on the good performance achieved, the same method has been applied for optimizing two-photon absorption starting from temporally broadened laser pulses, or from laser pulses temporally and spectrally distorted by non-linear absorption in air, obtaining similarly good results which confirm the validity of the deterministic search approach.     

Comparing extremal and thermal explorations of energy landscapes

Using a non-thermal local search, called Extremal Optimization (EO), in conjunction with a recently developed scheme for classifying the valley structure of complex systems, we analyze a short-range spin glass. In comparison with earlier studies using a thermal algorithm with detailed balance, we determine which features of the landscape are algorithm dependent and which are inherently geometrical. Apparently a characteristic for any local search in complex energy landscapes, the time series of successive energy records found by EO is also characterized approximately by a Poisson statistic with logarithmic time arguments. Differences in the results provide additional insights into the performance of EO. In contrast with a thermal search, the extremal search visits dramatically higher energies while returning to more widely separated low-energy configurations. Two important properties of the energy landscape are independent of either algorithm: first, to find lower energy records, progressively higher energy barriers need to be overcome. Second, the Hamming distance between two consecutive low-energy records is linearly related to the height of the intervening barrier.