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.     

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.     

Enhanced Van der Waals calculations in genetic algorithms for protein structure prediction

Several ab initio computational methods for protein structure prediction have been designed using full‐atom models and force field potentials to describe interactions among atoms. Those methods involve the solution of a combinatorial problem with a huge search space. Genetic algorithms (GAs) have shown significant performance increases for such methods. However, even a small protein may require hundreds of thousands of energy function evaluations making GAs suitable only for the prediction of very small proteins. We propose an efficient technique to compute the van der Waals energy (the greatest contributor to protein stability) speeding up the whole GA. First, we developed a Cell‐List Reconstruction procedure that divides the tridimensional space into a cell grid for each new structure that the GA generates. The cells restrict the calculations of van der Waals potentials to ranges in which they are significant, reducing the complexity of such calculations from quadratic to linear. Moreover, the proposal also uses the structure of the cell grid to parallelize the computation of the van der Waals energy, achieving additional speedup. The results have shown a significant reduction in the run time required by a GA. For example, the run time for the prediction of a protein with 147,980 atoms can be reduced from 217 days to 7 h. Copyright © 2012 John Wiley & Sons, Ltd.     

A genetic algorithm for multiple sequence alignment

Multiple sequence alignment is an important tool in molecular sequence analysis. This paper presents genetic algorithms to solve multiple sequence alignments. Several data sets are tested and the experimental results are compared with other methods. We find our approach could obtain good performance in the data sets with high similarity and long sequences.The software can be found in http://rsdb.csie.ncu.edu.tw/tools/msa.htm.     

预测蛋白质结构拟物算法的研究与改进

研究了具有两种氨基酸（疏水氨基酸和亲水氨基酸）的三维非格点的蛋白质模型。给出了该模型蛋白质结构预测问题改进的拟物算法。氨基酸链的初始设置由完全随机改为随机线形结构,并找到了更优的计算参数。结果对于三个氨基酸链都找到了更好的最低势能值。     

A coprocessor architecture for fast protein structure prediction

Predicting the protein structure from an amino acid sequence is computationally very intensive. In order to speed up protein sequence matching and processing, we present a novel coprocessor architecture for fast protein structure prediction. The architecture consists of systolic arrays to speed up the data intensive sequence alignment and structure prediction steps, and finite state machines for the control dominated steps. The architecture has been synthesized using Synopsys DC Compiler in 0.18 micron CMOS technology and details of its area and timing performance have been provided. A procedure to develop architectures with area-time trade-offs has also been presented.     

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.     

A genetic algorithm approach for SMEs bankruptcy prediction: Empirical evidence from Italy

Bankruptcy prediction is a topic, which affect the economic well being of all countries. Having an accurate company default prediction model, which can pick up on time the signs of financial distress, is vital for all firms, especially for small and medium-sized enterprises (SMEs). These firms represent the backbone of the economy of every country. Therefore, they need a prediction model easily adaptable to their characteristics. For this purpose, this study explores and compares the potential of genetic algorithms (GAs) with those of logistic regression (LR) and support vector machine (SVM). GAs are applied to a large sample of 3.100 Italian manufacturing SMEs, three, two and one year prior to bankruptcy. The results indicate that GAs are a very effective and promising instrument in assessing the likelihood of SMEs bankruptcy compared with LR and SVM, especially in reducing Type II misclassification rate. Of particular interest, results show that GAs prediction accuracy rate increases when the model is applied according to size and geographical area, with a marked improvement in the smallest sized firms and in the firms operating in north Italy.     

Genetic algorithm with advanced mechanisms applied to the protein structure prediction in a hydrophobic-polar model and cubic lattice

This paper presents a genetic algorithm applied to the protein structure prediction in a hydrophobic-polar model on a cubic lattice. The proposed genetic algorithm is extended with crowding, clustering, repair, local search and opposition-based mechanisms. The crowding is responsible for maintaining the good solutions to the end of the evolutionary process while the clustering is used to divide a whole population into a number of subpopulations that can locate different good solutions. The repair mechanism transforms infeasible solutions to feasible solutions that do not occupy the lattice point for more than one monomer. In order to improve convergence speed the algorithm uses local search. This mechanism improves the quality of conformations with the local movement of one or two consecutive monomers through the entire conformation. The opposition-based mechanism is introduced to transform conformations to the opposite direction. In this way the algorithm easily improves good solutions on both sides of the sequence. The proposed algorithm was tested on a number of well-known hydrophobic-polar sequences. The obtained results show that the mechanisms employed improve the algorithm's performance and that our algorithm is superior to other state-of-the-art evolutionary and swarm algorithms.     

A genetic algorithm for the minimum generating set problem

Given a set of positive integers S, the minimum generating set problem consists in finding a set of positive integers T with a minimum cardinality such that every element of S can be expressed as the sum of a subset of elements in T. It constitutes a natural problem in combinatorial number theory and is related to some real-world problems, such as planning radiation therapies.We present a new formulation to this problem (based on the terminology for the multiple knapsack problem) that is used to design an evolutionary approach whose performance is driven by three search strategies; a novel random greedy heuristic scheme that is employed to construct initial solutions, a specialized crossover operator inspired by real-parameter crossovers and a restart mechanism that is incorporated to avoid premature convergence. Computational results for problem instances involving up to 100,000 elements show that our innovative genetic algorithm is a very attractive alternative to the existing approaches.     

A FORTRAN 90 genetic algorithm module for composite laminate structure design

The design of the stacking sequence for a composite laminate involves a set of discrete variables (plymaterial and ply orientation), and is thus well-suited to genetic algorithms for design optimization. Such algorithms have typically been custom-designed in FORTRAN 77 to suit specific optimization problems. Fortran 90 is a modern, powerful language with features that support important programming concepts, including those used in object-oriented programming. The Fortran 90 genetic algorithm module is used to define genetic data types, the functions which use these data types, and to provide a general framework for solving composite laminate structure design problems. The language's support of abstract data types is used to build genetic structures such as populations, subpopulations, individuals, chromosomes, and genes, and these data types are combined and manipulated by module subroutines. The use of abstract data types and long variable names makes the code useful and easily understood, while dynamic memory allocation makes the module flexible enough to be used in design problems of varying size and specification.     

一种快速逃离局部极小点的BP算法

针对反向传播(BP)算法容易陷入局部极小点的问题,提出了一种改进价值函数,使其快速收敛到全局最小点的方法。对扩展的异或问题正弦函数模拟进行了仿真实验,结果对比表明,改进的BP算法能快速逃离局部极小点,收敛到全局最小点,达到了期望的效果。     

G3P-MI: A genetic programming algorithm for multiple instance learning

This paper introduces a new Grammar-Guided Genetic Programming algorithm for resolving multi-instance learning problems. This algorithm, called G3P-MI, is evaluated and compared to other multi-instance classification techniques in different application domains. Computational experiments show that the G3P-MI often obtains consistently better results than other algorithms in terms of accuracy, sensitivity and specificity. Moreover, it makes the knowledge discovery process clearer and more comprehensible, by expressing information in the form of IF-THEN rules. Our results confirm that evolutionary algorithms are very appropriate for dealing with multi-instance learning problems.     

Neuro-fuzzy and genetic algorithm in multiple response optimization

Optimization of a multiple output system, whose function is only approximately known and is represented in tabular form, is modeled and optimized by the combined use of a neuro-fuzzy network and optimization techniques which do not require the explicit representation of the function. Neuro-fuzzy network is useful for learning the approximate original tabular system. However, the results obtained by the neuro-fuzzy network are represented implicitly in the network. The MANFIS neuro-fuzzy network, which is an extension of the ANFIS network, is used to model the multiple output system and a genetic algorithm is used to optimize the resulting multiple objective decision making problem. A chemical process whose function is represented approximately in tabular form is solved to illustrate the approach.     

A genetic algorithm approach for group formation in collaborative learning considering multiple student characteristics

Considering that group formation is one of the key processes in collaborative learning, the aim of this paper is to propose a method based on a genetic algorithm approach for achieving inter-homogeneous and intra-heterogeneous groups. The main feature of such a method is that it allows for the consideration of as many student characteristics as may be desired, translating the grouping problem into one of multi-objective optimization. In order to validate our approach, an experiment was designed with 135 college freshmen considering three characteristics: an estimate of student knowledge levels, an estimate of student communicative skills, and an estimate of student leadership skills. Results of such an experiment allowed for the validation, not only from the computational point of view by measuring the algorithmic performance, but also from the pedagogical point of view by measuring student outcomes, and comparing them with two traditional group formation strategies: random and self-organized.     

Constraint-handling through multi-objective optimization: The hydrophobic-polar model for protein structure prediction

In the multi-objective approach to constraint-handling, a constrained problem is transformed into an unconstrained one by defining additional optimization criteria to account for the problem constraints. In this paper, this approach is explored in the context of the hydrophobic-polar model, a simplified yet challenging representation of the protein structure prediction problem. Although focused on such a particular case of study, this research work is intended to contribute to the general understanding of the multi-objective constraint-handling strategy. First, a detailed analysis was conducted to investigate the extent to which this strategy impacts on the characteristics of the fitness landscape. As a result, it was found that an important fraction of the infeasibility translates into neutrality. This neutrality defines potentially shorter paths to move through the landscape, which can also be exploited to escape from local optima. By studying different mechanisms, the second part of this work highlights the relevance of introducing a proper search bias when handling constraints by multi-objective optimization. Finally, the suitability of the multi-objective approach was further evaluated in terms of its ability to effectively guide the search process. This strategy significantly improved the performance of the considered search algorithms when compared with respect to commonly adopted techniques from the literature.     

PITAGORAS-PSP: Including domain knowledge in a multi-objective approach for protein structure prediction

Whenever evolutionary algorithms are used to solve certain classes of problems such as those that present a huge search space, the incorporation of problem-specific knowledge is required to achieve adequate levels of performance. In this paper, we propose a multi-objective optimization-based procedure that includes such a domain-specific knowledge to cope with a difficult problem, the protein structure prediction (PSP). This problem is considered to be an open problem as there is no recognized “best” procedure to find solutions. It presents a vast search space and the analysis of each protein conformation requires significant amount of computing time. In our procedure, we provide a reduction of the search space by using the dependent rotamer library and include new heuristics to improve a multi-objective approach to PSP based on the PAES algorithm. As it is shown in the paper, by using benchmark proteins from the CASP8 set, this hybrid PSP procedure provides competitive results when it is compared with some of the better proposals appeared up to now.     

A modified genetic algorithm for distributed scheduling problems

Genetic algorithms (GAs) have been widely applied to the scheduling and sequencing problems due to its applicability to different domains and the capability in obtaining near-optimal results. Many investigated GAs are mainly concentrated on the traditional single factory or single job-shop scheduling problems. However, with the increasing popularity of distributed, or globalized production, the previously used GAs are required to be further explored in order to deal with the newly emerged distributed scheduling problems. In this paper, a modified GA is presented, which is capable of solving traditional scheduling problems as well as distributed scheduling problems. Various scheduling objectives can be achieved including minimizing makespan, cost and weighted multiple criteria. The proposed algorithm has been evaluated with satisfactory results through several classical scheduling benchmarks. Furthermore, the capability of the modified GA was also tested for handling the distributed scheduling problems.     

A genetic algorithm for railway scheduling with environmental considerations

A genetic algorithm is a randomized optimization technique that draws its inspiration from the biological sciences. Specifically, it uses the idea that genetics determines the evolution of any species in the natural world. Integer strings are used to encode an optimization problem and these strings are subject to combinatorial operations called reproduction, crossover and mutation, which improve these strings and cause them to ‘evolve’ to an optimal or nearly optimal solution. In this paper, the general machinations of genetic algorithms are described and a performance-enhanced algorithm is proposed for solving the important practical problem of railway scheduling. The problem under consideration involves moving a number of trains carrying mineral deposits across a long haul railway line with both single and double tracks in either direction. Collisions can only be avoided in sections of the line with double tracks. Constraints reflecting practical requirements to reduce environmental impacts from mineral transport, such as avoidance of loaded trains traversing populated areas during certain time slots, have to be satisfied. This is an NP-hard problem, which usually requires enumerative, as opposed to constructive, algorithms. For this reason, an ‘educated’ random search procedure like the genetic algorithm is an alternative and effective technique. The genetic algorithm is given difficult test problems to solve and the algorithm was able to generate feasible solutions in all cases.     

A genetic algorithm for combined topology and shape optimisations

A method to find optimal topology and shape of structures is presented. With the first the optimal distribution of an assigned mass is found using an approach based on homogenisation theory, that seeks in which elements of a meshed domain it is present mass; with the second the discontinuous boundaries are smoothed. The problem of the optimal topology search has an ON/OFF nature and has suggested the employment of genetic algorithms. Thus in this paper a genetic algorithm has been developed, which uses as design variables, in the topology optimisation, the relative densities (with respect to effective material density) 0 or 1 of each element of the structure and, in the shape one, the coordinates of the keypoints of changeable boundaries constituted by curves. In both the steps the aim is that to find the variable sets producing the maximum stiffness of the structure, respecting an upper limit on the employed mass. The structural evaluations are carried out with a FEM commercial code, linked to the algorithm. Some applications have been performed and results compared with solutions reported in literature.