Graph Coloring with Adaptive Evolutionary Algorithms

This paper presents the results of an experimental investigation on solving graph coloring problems with Evolutionary Algorithms (EAs). After testing different algorithm variants we conclude that the best option is an asexual EA using order-based representation and an adaptation mechanism that periodically changes the fitness function during the evolution. This adaptive EA is general, using no domain specific knowledge, except, of course, from the decoder (fitness function). We compare this adaptive EA to a powerful traditional graph coloring technique DSatur and the Grouping Genetic Algorithm (GGA) on a wide range of problem instances with different size, topology and edge density. The results show that the adaptive EA is superior to the Grouping (GA) and outperforms DSatur on the hardest problem instances. Furthermore, it scales up better with the problem size than the other two algorithms and indicates a linear computational complexity.     

Chaotic Dynamics in an Electronic Model of a Genetic Network

We consider dynamics in a class of piecewise-linear ordinary differential equations and in an electronic circuit that model genetic networks. In these models, gene activity varies continuously in time. However, as in Boolean or discrete-time switching networks, gene activity is driven high or low based only on whether the activities of the regulating genes are high or low (i.e., above or below certain thresholds). Depending on the “regulatory logic”, these models can exhibit simple dynamics, like stable fixed points or oscillation, or chaotic dynamics. The observed qualitative and quantitative differences between the dynamics in the idealized equations and the dynamics in the electronic circuit lead us to focus attention on the analysis of the dynamics as a function of parameter values. We propose new techniques for solving the inverse problem – the problem of inferring the regulatory logic and parameters from time series data. We also give new symbolic and statistical methods for characterizing dynamics in these networks.     

带鳍通道性能的遗传算法优化

与光滑通道相比,带鳍通道有更高的传热系数,附加的鳍,极大地增强了通道的传热.然而,传热的增强又与压降的升高相关联,这又导致泵动力需求的增加,因此应该寻求对该系统的优化设计.该文的主要目的是,通过如下方式来精确地确定鳍的位置和尺寸:利用遗传算法实现最小压降时达到最优传热.鳍的每种布局作为问题(遗传算法中的一个个体)的一个解.通常,首先随机地产生一个初始种群,然后该算法在所有这些解中搜索,利用布局函数迭代出新解,最后得到鳍的优化设计.     

二层线性规划的自适应遗传算法

提出了一种自适应遗传算法来求解二层线性规划问题.该方法克服了难以确定合适的交叉概率和变异概率的困难.另外,在该方法中还采用了其它一些技巧不仅解决了在采用遗传算法经常出现的有些个体不可行的问题,而且还改进了算法的效率.     

一种最短路问题的遗传算法求解

针对最短路径问题,在分析传统遗传算法不足的基础上提出了变长染色体遗传算法(ClvGA),详细论叙了其编码、基因插入(删除、变异)算子的设计,最后通过两个网络对ClvGA进行了实验仿真,结果表明:该方法在最短路径问题上表现出较好的鲁棒性.     

Equilibrium Sampling From Nonequilibrium Dynamics

We present some applications of an Interacting Particle System (IPS) methodology to the field of Molecular Dynamics. This IPS method allows several simulations of a nonequilibrium random process to keep closer to equilibrium at each time, thanks to a selection mechanism based on the relative virtual work induced on the system. It is therefore an efficient improvement of usual nonequilibrium simulations, which can be used to compute canonical averages, free energy differences, and typical transitions paths. AMS: 65C05 65C35 80A10     

遗传算法求解带容量限制的最小费用流问题

研究了带容量限制的带固定费用和可变费用的最小费用流问题,发现该问题是混合0-1整数规划问题,不存在多项式算法.在研究了最优解的结构后,结合最优解的结构特点为之设计了遗传算法,然后构造了一个100个节点的特殊网络,用计算机做了100例计算,验证了该算法具有很好的近似比和很快的收敛速度.     

一个水流问题的遗传算法求解

应用遗传算法(GA)来讨论一个水流问题.这个水流问题曾是不少统计学者用来考察不同试验设计和建模方法的常用案例.通过本例旨在说明遗传算法确为求解复杂系统优化问题的有力工具.     

车辆路径问题的混合优化算法

讨论了一类车辆路径调度问题(VRP)及其数学模型，并且分析了以遗传算法求解该类问题时的染色体表示和有关遗传操作，然后结合2-opt局部优化算法提出了GA with2-opt算法来求解VRP问题，试验结果说明了该算法的有效性和可行性。     

遗传算法的物理解释

提出了一种理想化的模拟仿生搜索算法——扰动算法 ,以此方法为基础 ,分析了遗传算法的搜索过程和效率问题 ,阐明了遗传算法作为一种次优算法的有效性 .相对于遗传算法的生物解释 ,本文给出了相应的物理解释 .同时 ,本文为遗传算法、进化策略和模拟退火算法找到了一种统一的物理解释 ,揭示了这些重要的仿生类算法实质上的相似性 .