检索结果-内蒙古大学图书馆

Improved time complexity analysis of the simple genetic algorithm

THEORETICAL COMPUTER SCIENCE 2015年 605卷 21-41页

作者： Oliveto, Pietro S. Witt, Carsten Univ Sheffield Dept Comp Sci Sheffield S10 2TN S Yorkshire England Tech Univ Denmark DTU Compute Copenhagen Denmark

A runtime analysis of the simple genetic algorithm (SGA) for the ONEMAX problem has recently been presented proving that the algorithm with population size mu <= n(1/8-epsilon) requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of the previous one. Firstly, the new result holds for population sizes up to mu <= n(1/4-epsilon) which is an improvement up to a power of 2 larger. Secondly, we present a technique to bound the diversity of the population that does not require a bound on its bandwidth. Apart from allowing a stronger result, we believe this is a major improvement towards the reusability of the techniques in future systematic analyses of GAs. Finally, we consider the more natural SGA using selection with replacement rather than without replacement although the results hold for both algorithmic versions. Experiments are presented to explore the limits of the new and previous mathematical techniques. Crown Copyright (C) 2015 Published by Elsevier B.V. All rights reserved.

关键词： simple genetic algorithm Crossover Runtime analysis

来源：评论

学校读者我要写书评

暂无评论

On the runtime analysis of the simple genetic algorithm

引用

THEORETICAL COMPUTER SCIENCE 2014年第C期545卷 2-19页

作者： Oliveto, Pietro S. Witt, Carsten Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England Tech Univ Denmark DTU Informat Lyngby Denmark

For many years it has been a challenge to analyze the time complexity of genetic algorithms (GAS) using stochastic selection together with crossover and mutation. This paper presents a rigorous runtime analysis of the well-known simple genetic algorithm (SGA) for ONEMAx. It is proved that the SGA has exponential runtime with overwhelming probability for population sizes up to mu <= n(1/8-epsilon) for some arbitrarily small constant epsilon and problem size n. To the best of our knowledge, this is the first time non-trivial lower bounds are obtained On the runtime of a standard crossover-based GA for a standard benchmark function. The presented techniques might serve as a first basis towards systematic runtime analyses of GAS. Crown Copyright (C) 2013 Published by Elsevier B.V. All rights reserved.

关键词： simple genetic algorithm Crossover Runtime analysis

来源：评论

学校读者我要写书评

暂无评论

Affine invariant matching of broken boundaries based on simple genetic algorithm and contour reconstruction

引用

PATTERN RECOGNITION LETTERS 2010年第9期31卷 771-780页

作者： Tsang, P. W. M. Situ, W. C. City Univ Hong Kong Dept Elect Engn Hong Kong Hong Kong Peoples R China

Viewpoint independent identification of fragmented object contours can be accomplished by matching them against a collection of known reference models. For the class of near-planar objects, the matching process can be posed as the search for the existence of an affine transform between a pair of contours. Recently, it has been demonstrated that the search process can be accomplished with the integration of a simple genetic algorithm (SGA) and a quality migrant injection (QMI) operation. The performance is superior to prior arts based on the use of SGA alone in terms of success rates and computation speed. The downside of such approach is the need of more computation time for generating quality migrants in the course of evolution. In this paper, we have proposed a solution to overcome this problem. Our method has two major contributions. The first one is a scheme which enables a closed boundary to be extracted from a set of fragmented object points, and represented as a one-dimensional (1 - D) sequence. Second, we have applied SGA to determine the similarity between a pair of closed boundaries by searching the existence of three correspondence point pairs in their I - D sequences. As a result of these two contributions, the proposed method is substantially faster than the SGA-QMI scheme, and also capable of attaining close to 100% success rate in identifying matched contours. (c) 2010 Elsevier B.V. All rights reserved.

关键词： Affine invariant matching Fragmented contours Contour reconstruction simple genetic algorithm Migrant principle Quality migrants

来源：评论

学校读者我要写书评

暂无评论

Protein refolding in silico with atom-based statistical potentials and conformational search using a simple genetic algorithm

引用

JOURNAL OF MOLECULAR BIOLOGY 2006年第5期359卷 1456-1467页

作者： Fang, Qiaojun Shortle, David Johns Hopkins Univ Sch Med Dept Biol Sci Baltimore MD 21205 USA

A distance-dependent atom-pair potential that treats long range and local interactions separately has been developed and optimized to distinguish native protein structures from sets of incorrect or decoy structures. Atoms are divided into 30 types based on chemical properties and relative position in the amino acid side-chains. Several parameters affecting the calculation and evaluation of this statistical potential, such as the reference state, the bin width, cutoff distances between pairs, and the number of residues separating the atom pairs, are adjusted to achieve the best discrimination. The native structure has the lowest energy for 39 of the 40 sets of original ROSETTA decoys (1000 structures per set) and 23 of the 25 improved decoys (similar to 1900 structures per set). Combined with the orientation-dependent backbone hydrogen bonding potential used by ROSETTA and a statistical solvation potential based on the solvent exclusion model of Lazaridis & Karplus, this potential is used as a scoring function for conformational search based on a genetic algorithm method. After unfolding the native structure by changing every phi and psi angle by either 3, 5 or 7 degrees, five small proteins can be efficiently refolded, in some cases to within 0.5 angstrom C-alpha distance matrix error (DME) to the native state. Although no significant correlation is found between the total energy and structural similarity to the native state, a surprisingly strong correlation exists between the radius of gyration and the DME for low energy structures. (c) 2006 Elsevier Ltd. All rights reserved.

关键词： statistical potentials atom-pair potential decoy discrimination implicit solvation simple genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Analysis of the simple genetic algorithm 12

On the Analysis of the Simple Genetic Algorithm

引用

14th International Conference on genetic and Evolutionary Computation Conference (GECCO)

作者： Oliveto, Pietro S. Witt, Carsten Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England

ISBN: (纸本)9781450311779

For many years it has been a challenge to analyze the time complexity of genetic algorithms (GAs) using stochastic selection together with crossover and mutation. This paper presents a rigorous runtime analysis of the well-known simple genetic algorithm (SGA) for OneMax. It is proved that the SGA has exponential runtime with overwhelming probability for population sizes up to mu <= n(1/8-epsilon) for some arbitrarily small constant e and problem size n. To the best of our knowledge, this is the first time non-trivial lower bounds are obtained on the runtime of a standard crossover-based GA for a standard benchmark function. The presented techniques might serve as a first basis towards systematic runtime analyses of GAs.

关键词： simple genetic algorithm Crossover Runtime Analysis

来源：评论

学校读者我要写书评

暂无评论

Improved Runtime Analysis of the simple genetic algorithm 13

Improved Runtime Analysis of the Simple Genetic Algorithm

引用

15th genetic and Evolutionary Computation Conference (GECCO)

作者： Oliveto, Pietro S. Witt, Carsten Univ Birmingham Sch Comp Sci Birmingham B15 2TT W Midlands England Tech Univ Denmark Lyngby Denmark

ISBN: (纸本)9781450319638

A runtime analysis of the simple genetic algorithm (SGA) for the On e M a x problem has recently been presented proving that the algorithm requires exponential time with overwhelming probability. This paper presents an improved analysis which overcomes some limitations of our previous one. Firstly, the new result holds for population sizes up to mu <= n(1/4-epsilon) which is an improvement up to a power of 2 larger. Secondly, we present a technique to bound the diversity of the population that does not require a bound on its bandwidth. Apart from allowing a stronger result, we believe this is a major improvement towards the reusability of the techniques in future systematic analyses of GAs. Finally, we consider the more natural S G A using selection with replacement rather than without replacement although the results hold for both algorithmic versions. Experiments are presented to explore the limits of the new and previous mathematical techniques.

关键词： simple genetic algorithm Crossover Runtime Analysis

来源：评论

学校读者我要写书评

暂无评论

genetic Operators Significance Assessment in simple genetic algorithm

Genetic Operators Significance Assessment in Simple Genetic ...

引用

9th International Conference on Large-Scale Scientific Computations (LSSC)

作者： Angelova, Maria Pencheva, Tania Bulgarian Acad Sci Inst Biophys & Biomed Engn BU-1113 Sofia Bulgaria

ISBN: (纸本)9783662438800;9783662438794

genetic algorithms, proved as successful alternative to conventional optimization methods for the purposes of parameter identification of fermentation process models, search for a global optimal solution via three main genetic operators, namely selection, crossover, and mutation. In order to determine their importance for finding the solution, a procedure for significance assessment of genetic algorithms operators has been developed. The workability of newly elaborated procedure has been tested when simple genetic algorithm is applied to parameter identification of S. cerevisiae fed-batch cultivation. According to obtained results the most significant genetic operator has been distinguished and its influence for finding the global optimal solution has been evaluated.

关键词： simple genetic algorithm genetic operators Parameter identification S. cerevisiae fed-batch cultivation

来源：评论

学校读者我要写书评

暂无评论

A METHOD TO ESTIMATE DYNAMIC CHARACTERISTICS OF PROCESS BY simple genetic algorithm

引用

KAGAKU KOGAKU RONBUNSHU 1994年第3期20卷 382-386页

作者： HANAKUMA, Y SASAKI, T NAKAYA, K IWASE, H NAKANISHI, E KOBE UNIV DEPT CHEM ENGNKOBE 657JAPAN

A method to estimate dynamic characteristics of a process in control design by a simple genetic algorithm is developed. The method proposed in this study has the advantage of simultaneous determination of the dead time, which cannot be realized in the usual statistical modeling method. This method was applied to the reaction temperature of a catalyst synthesis column in a polypropylene plant to confirm the design philosophy. The result indicates that the proposed method is effective in identifying dynamic characteristics-of the process.

关键词： IDENTIFICATION PARAMETER ESTIMATION PROCESS CONTROL PROCESS DYNAMICS simple genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Using genetic algorithm optimizing stack filters based on MMSE criterion

引用

IMAGE AND VISION COMPUTING 2005年第10期23卷 853-860页

作者： Zhao, CH Zhang, WC Harbin Engn Univ Coll Informat & Commun Engn Harbin 150001 Peoples R China

In this paper, the problem of optimizing stack filters is changed into a one-zero knapsack problem based on the minimum mean square error (MMSE) criterion. The optimization of stack filters is realized by solving this knapsack problem with genetic algorithm (GA). Optimal stack filters are designed to process the images corrupted by impulsive noise in this paper. The computer simulated experiments show that the suppressing noise capability of the optimal stack filters based on the MMSE criterion is better than that of the optimal stack filters based on the minimum mean absolute error (MMAE) criterion. Moreover, the optimizing performances of simple genetic algorithm and adaptive genetic algorithm are discussed in this paper. (c) 2005 Elsevier B.V. All rights reserved.

关键词： minimum mean square error criterion (MMSE) nonlinear filter simple genetic algorithm adaptive genetic algorithm stack filters image processing

来源：评论

学校读者我要写书评

暂无评论

Control model of neural network based on novel genetic algorithm for PEMFC

引用

Journal of Systems Engineering and Electronics 2004年第4期15卷 649-655页

作者： WeiDong CaoGuangyi ZhuXinjian CollegeofMetrologicalTechnology&Engineering ChinaJiliangUniversityHangzhou310018P.R.China InstituteofFuelCell ShanghaiJiaotongUniversityShanghai200030P.R.China

The operating temperature of PEMFC stack is a very important control parameter. In operating process, electro-chemical reaction and the humidity of proton exchange membrane vary sensibly with it, the variation of operating temperature has a significant influence on the output performance and lifespan of fuel cells. The most existing PEMFC mathematical models are too complicated to apply in on-line control process, so it is necessary to find a simple accurate stable control method. In this paper, a novel genetic algorithm (NGA) is presented, which possesses stronger global searching and local optimizing capacities than SGA. NGA is applied to optimize rapidly the weights of neural network according to the population of excellent individuals, neural networks technique is used to establish a self-adjusted control model for PEMFC system. The results of simulation and experiment are given in the end.

关键词： novel genteic algorithm proton exchange membrane fuel cell self-adjusted control simple genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：