An efficient hybrid Taguchi-genetic algorithm for protein folding simulation

Given the amino-acid sequence of a protein, the prediction of a protein’s tertiary structure is known as the protein folding problem. The protein folding problem in the hydrophobic–hydrophilic lattice model is to find the lowest energy conformation. In order to enhance the performance of predicting protein structure, in this paper we propose an efficient hybrid Taguchi-genetic algorithm that combines genetic algorithm, Taguchi method, and particle swarm optimization (PSO). The GA has the capability of powerful global exploration, while the Taguchi method can exploit the optimum offspring. In addition, we present the PSO inspired by a mutation mechanism in a genetic algorithm. We demonstrate that our algorithm can be applied successfully to the protein folding problem based on the hydrophobic-hydrophilic lattice model. Simulation results indicate that our approach performs very well against existing evolutionary algorithm.     

Genetic algorithms for sequencing problems in mixed model assembly lines

Mixed model assembly lines are a type of production line where a variety of product models similar in product characteristics are assembled. The effective utilisation of these lines requires that a schedule for assembling the different products be determined. In this paper, the performance of genetic algorithms for sequencing problems in mixed model assembly lines is investigated. The problem first considered is a comparison between a existing heuristic and the proposed genetic algorithm to get the constant usage of every part used by the line considering variation at multi levels (Number of levels fixed as four. level 1—product, level 2—subassembly, level 3—component, level 4—raw-materials) for various test-bed problems. The algorithms proposed by Miltenburg and Sinnamon hereafter referred to as MS 1992 [IIE Trans. 24 (1992) 121] and the proposed genetic algorithm (GA) applied to mixed model assembly line are compared. Results of evaluation indicate that the GA performs better over MS1992 on 25 of the 40 problems investigated.

The other problem solved is a multiple objective sequencing problem in mixed model assembly lines. Three practically important objectives are minimizing total utility work keeping a constant rate of part-usage, minimizing the variability in parts usage and minimizing total setup cost. In this paper, the performance of the selection mechanisms, the Pareto stratum-niche cubicle and the selection based on scalar fitness function value are compared with respect to the objective of minimising variation in part-usage, minimising total utility work and minimising the setup cost. Results of evaluation indicate that the genetic algorithm that uses the Pareto stratum-niche cubicle performs better than the genetic algorithm with the other selection mechanisms.     

How to predict very large and complex crystal structures

Evolutionary crystal structure prediction proved to be a powerful approach in discovering new materials. Certain limitations are encountered for systems with a large number of degrees of freedom (“large systems”) and complex energy landscapes (“complex systems”). We explore the nature of these limitations and address them with a number of newly developed tools.For large systems a major problem is the lack of diversity: any randomly produced population consists predominantly of high-energy disordered structures, offering virtually no routes toward the ordered ground state. We offer two solutions: first, modified variation operators that favor atoms with higher local order (a function we introduce here), and, second, construction of the first generation non-randomly, using pseudo-subcells with, in general, fractional atomic occupancies. This enhances order and diversity and improves energies of the structures. We introduce an additional variation operator, coordinate mutation, which applies preferentially to low-order (“badly placed”) atoms. Biasing other variation operators by local order is also found to produce improved results. One promising version of coordinate mutation, explored here, displaces atoms along the eigenvector of the lowest-frequency vibrational mode. For complex energy landscapes, the key problem is the possible existence of several energy funnels - in this situation it is possible to get trapped in one funnel (not necessarily containing the ground state). To address this problem, we develop an algorithm incorporating the ideas of abstract “distance” between structures. These new ingredients improve the performance of the evolutionary algorithm USPEX, in terms of efficiency and reliability, for large and complex systems.     

Evolutionary neural network modeling for forecasting the field failure data of repairable systems

An accurate product reliability prediction model can not only learn and track the product’s reliability and operational performance, but also offer useful information for managers to take follow-up actions to improve the product’ quality and cost. This study proposes a new method for predicting the reliability for repairable systems. The novel method constructs a predictive model by employing evolutionary neural network modeling approach. Genetic algorithms are used to globally optimize the number of neurons in the hidden layer and learning parameters of the neural network architecture. Moreover, two case studies are presented to illustrate the proposed method. The prediction accuracy of the novel method is compared with that of other methods to illustrate the feasibility and effectiveness of the proposed method.     

MOTGA: A multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem

This paper presents a new multiobjective genetic algorithm based on the Tchebycheff scalarizing function, which aims to generate a good approximation of the nondominated solution set of the multiobjective problem. The algorithm performs several stages, each one intended for searching potentially nondominated solutions in a different part of the Pareto front. Pre-defined weight vectors act as pivots to define the weighted-Tchebycheff scalarizing functions used in each stage. Therefore, each stage focuses the search on a specific region, leading to an iterative approximation of the entire nondominated set.     

多目标遗传算法在混流装配线排序中的应用

混流装配线实现在一条流水线上装配多种不同类型的产品。该文在总结混流装配线排序问题的基础上建立了二种排序的目标函数：最小化工作站的闲置与超载时间和保持均匀的零部件消耗速率。引入了基于Pareto理论和小生镜单元技术的适应度函数及选择算子构建了多目标遗传算法用于混流装配线的排序优化问题。通过一个混流装配线的多目标排序实验,验证了该方法的有效性。     

基于强化学习的HP模型优化方法研究

蛋白质结构预测问题一直是生物信息学中的重要问题。基于疏水极性模型的蛋白质二维结构预测问题是一个典型的NP难问题。目前疏水极性模型优化的方法有贪心算法、粒子群算法、遗传算法、蚁群算法和蒙特卡罗模拟方法等,但这些方法成功收敛的鲁棒性不高,容易陷入局部最优。由此提出一种基于强化学习的HP模型优化方法,利用其连续马尔可夫最优决策与最大化全局累计回报的特点,在全状态空间中,构建基于能量函数的奖赏函数,引入刚性重叠检测规则,充分挖掘生物序列中的全局进化关系,从而进行有效与稳定的预测。以3条经典论文序列和5条Uniref50序列为实验对象,与贪心算法和粒子群算法分别进行了鲁棒性、收敛性与运行时间的比较。贪心算法只能在62.5%的序列上进行收敛,该文方法能在5万次训练后稳定的在所有序列上达到了收敛。与粒子群算法相比,两者都能找到最低能量结构,但该文的运行时间较粒子群算法降低了63.9%。     

一种禁忌搜索算法在二维HP非格模型中的应用

禁忌搜索算法是一种启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题,本文探讨将一种记忆的禁忌搜索算法应用于求解蛋白质结构预测问题。文中首先介绍了一种二维HP非格模型,此模型最后可以归结为一个全局优化问题,然后介绍了记忆的禁忌搜索算法在其中的应用,通过与PERM（Pruned—Enriched—Rosenbluth Method）比较,发现禁忌算法能得到较好的实验结果,经分析发现虽然二维HP非格模型很简单,但却能反映蛋白质结构的一些简单的性质,即在蛋白质结构中,疏水性氨基酸形成束,总是被极性氨基酸包围。数值实验表明该算法对于蛋白质结构预测是可行有效的。     

The discovery of experts'' decision rules from qualitative bankruptcy data using genetic algorithms

Numerous studies on bankruptcy prediction have widely applied data mining techniques to finding out the useful knowledge automatically from financial databases, while few studies have proposed qualitative data mining approaches capable of eliciting and representing experts' problem-solving knowledge from experts' qualitative decisions. In an actual risk assessment process, the discovery of bankruptcy prediction knowledge from experts is still regarded as an important task because experts' predictions depend on their subjectivity. This paper proposes a genetic algorithm-based data mining method for discovering bankruptcy decision rules from experts' qualitative decisions. The results of the experiment show that the genetic algorithm generates the rules which have the higher accuracy and larger coverage than inductive learning methods and neural networks. They also indicate that considerable agreement is achieved between the GA method and experts' problem-solving knowledge. This means that the proposed method is a suitable tool for eliciting and representing experts' decision rules and thus it provides effective decision supports for solving bankruptcy prediction problems.     

A massively parallel genetic algorithm for RNA secondary structure prediction

We present a new method for predicting RNA secondary structure based on a genetic algorithm. The algorithm is designed to run on a massively parallel SIMD computer. Statistical analysis shows that the program performs well when compared to a dynamic programming algorithm used to solve the same problem. The program has also pointed out a long-standing simplification in the implementation of the original dynamic programming algorithm that sometimes causes it not to find the optimal secondary structure.     

Towards probabilistic footy tipping: a hybrid approach utilising genetically defined neural networks and linear programming

Using readily available data from the 1992–1995 Australian Football League season, we have developed a model that will readily predict the winner of a game, together with the probability of that win. This model has been developed using a genetically modified neural network to calculate the likely winner, combined with a linear program optimisation to determine the probability of that occurring in the context of the tipping competition scoring regime. This model has then been tested against 484 tippers in a probabilistic tipping competition for the 2002 season. We have found that the performance of the combined neural network, linear program model compared most favorably with other model based tipping programs and human tippers.     

求解HP模型蛋白质折叠问题的启发式算法

构造了一个新的数学模型,把三维HP模型的蛋白质折叠问题由一个有约束的优化问题转化为无约束的优化问题,通过建立相对坐标和邻域结构,提出了一个局部搜索算法,并对文献中的链长不同的7个算例进行了测试。结果表明,该算法能在较短时间内找到其中5个算例的最优能量枸形,对另外2个难例,则可以找到能量仅比最优构形高一个单位的次优构形。     

Genetic algorithms (GAs) to evolve multiple-agent cooperative systems

In this paper, a microrobot soccer-playing game, such as that of MIROSOT (Microrobot World Cup Soccer Tournament), is adopted as a standard test bed for research on multiple-agent cooperative systems. It is considerably complex and requires expertise in several difficult research topics, such as mobile microrobot design, motor control, sensor technology, intelligent strategy planning, etc., to build up a complete system to play the game. In addition, because it is an antagonistic game, it appears ideal to test whether one method is better than other. To date there have been two different kinds of architecture for building such system. One is called vision-based or centralized architecture, and the other is known as robot-based or decentralized architecture. The main difference between them lies in whether there exists a host computer system which responds to data processing and strategy planning, and a global vision system which can view the whole playground and transfer the environment information to the host computer in real time. We believe that the decentralized approach is more advanced, but in the preliminary step of our study, we used the centralized approach because it can lighten any overload of the microrobot design. In this paper, a simplified layer model of the multiple-agent cooperative system is first proposed. Based on such a model, a system for a microrobot soccer-playing game is organized. At the same time a simple genetic algorithm (SGA) is used for the autonomous evolution of cooperative behavior among microrobots. Finally, a computer simulation system is introduced and some simulated results are explained. This work was presented, in part, at the Third International Symposium on Artificial Life and Robotics, Oita, Japan, January 19–21, 1998.     

Fast algorithms for finding disjoint subsequences with extremal densities

We derive fast algorithms for the following problem: given a set of n points on the real line and two parameters s and p, find s disjoint intervals of maximum total length that contain at most p of the given points. Our main contribution consists of algorithms whose time bounds improve upon a straightforward dynamic programming algorithm, in the relevant case that input size n is much bigger than parameters s and p. These results are achieved by selecting a few candidate intervals that are provably sufficient for building an optimal solution via dynamic programming. As a byproduct of this idea we improve an algorithm for a similar subsequence problem of Chen et al. [Disjoint segments with maximum density, in: International Workshop on Bioinformatics Research and Applications IWBRA 2005, (within ICCS 2005), Lecture Notes in Computer Science, vol. 3515, Springer, Berlin, pp. 845–850]. The problems are motivated by the search for significant patterns in biological data. Finally, we propose several heuristics that further reduce the time complexity in typical instances. One of them leads to an apparently open subsequence sum problem of independent interest.     

混合遗传算法和蚁群算法在HP模型中的应用

遗传算法和蚁群算法在HP模型中已经有了大量的研究及成果,蚁群算法具有分布式并行全局搜索能力,通过信息素的积累和更新收敛于最优路径上,但初期信息素匮乏,求解速度慢。提出了一种先用遗传算法生成信息素分布,再利用蚁群算法求优化解的新的混合算法。将该算法用于二维HP模型中,计算结果显示该算法在寻优能力和收敛速度上都比单一的遗传算法和蚁群算法有所提高。     

A GA-based movie-on-demand platform using multiple distributed servers

In this paper we present the design and explore the performance of a unicast-based distributed system for Movie-on-Demand applications. The operation of multiple servers is coordinated with the assistance of an analytical framework that provides closed-form solutions to the content partitioning and scheduling problem, even under the presence of packet losses. The problem of mapping clients to servers is solved with a genetic algorithm, that manages to provide adequate, near-optimum solutions with a minimum of overhead. While previous studies focused on the static behavior of such a system, i.e. fixed a-priori known number of N servers and K clients commencing operation at the same time instance, this paper focuses on the dynamic behavior of such a system over a period of time with clients coming and going at random intervals. The paper includes a rigorous simulation study that shows how the system behaves in terms of a variety of metrics, including the average access time over all the requested media, in response to differences in the client arrival rate or the consumed server bandwidth. As it is shown, the proposed platform exhibits excellent performance characteristics that surpass traditional approaches that treat clients individually. This has been verified to be true up to extreme system loads, proving the scalability of the proposed content delivery scheme. The significance of our findings also stems from the assumption of unreliable communications, a first for the study of complete systems in this domain.

Multiple Objective Genetic Algorithms for Path-planning Optimization in Autonomous Mobile Robots

This paper describes the use of a genetic algorithm (GA) for the problem of offline point-to-point autonomous mobile robot path planning. The problem consists of generating “valid” paths or trajectories, for an Holonomic Robot to use to move from a starting position to a destination across a flat map of a terrain, represented by a two-dimensional grid, with obstacles and dangerous ground that the Robot must evade. This means that the GA optimizes possible paths based on two criteria: length and difficulty. First, we decided to use a conventional GA to evaluate its ability to solve this problem (using only one criteria for optimization). Due to the fact that we also wanted to optimize paths under two criteria or objectives, then we extended the conventional GA to implement the ideas of Pareto optimality, making it a multi-objective genetic algorithm (MOGA). We describe useful performance measures and simulation results of the conventional GA and of the MOGA that show that both types of GAs are effective tools for solving the point-to-point path-planning problem.     

基于混合SVM方法的蛋白质二级结构预测算法

预测蛋白质二级结构,是当今生物信息学中一个难以解决的问题。由于预测蛋白质二级结构的精度在蛋白质结构研究中起到非常重要的作用,因此在基于KDTICM理论基础上,提出一种基于混合SVM方法的蛋白质二级结构预测算法。该算法有效地利用蛋白质的物化属性和PSI-SEARCH生成的位置特异性打分矩阵作为双层SVM的输入,从而大大地提高了蛋白质二级结构预测的精度。实验比较分析表明,新算法的预测精度和普适性明显优于目前其他典型的预测方法。     

求解蛋白质结构预测问题的局部搜索算法

蛋白质结构预测问题是计算生物学领域的核心问题之一。通过理论计算的方法根据蛋白质氨基酸序列直接预测其空间结构是解决这一问题的有效途径。构造了新的邻域结构,采用了部分随机跳坑策略,对此问题提出了新的局部搜索算法。计算结果表明,该算法计算效率要优于传统的遗传算法和Monte Carlo方法。对于链长为50的算例还找到了文献中所没有的全新的最低能量构形。     

Modeling external network behavior by using internal measurements

Network behavior is the set of observations or measurements that can be made about a network over time. The growth of network-based computing and the Internet have ensured that networks can no longer be considered in isolation, as events external to a particular network increasingly impact its behavior. Network management requires that information be known about these events, a task that is not always possible. We present a modeling strategy that takes partial information about a network and uses it to predict the behavior in unmonitored areas. This implementation is based on a meta-heuristic (genetic algorithm), and uses IP-packet information as well as a limited understanding of the external topology. This is then used to model the full topology, routing tables and traffic for the entire network at periodic intervals. The system was tested using the ns-2 network simulator and a Java implementation on a series of cases. The results showed a reasonable level of accuracy in predicting traffic and topology. Performance increased under system load, and at no point did the system generate any additional network traffic. This provides an efficient and effective strategy for network management.