当前位置：文档之家 › On the Virtues of Parameterized Uniform Crossover

On the Virtues of Parameterized Uniform Crossover

  • 格式：pdf
  • 大小：51.56 KB
  • 文档页数：7

OntheVirtuesofParameterizedUniformCrossoverWilliamM.SpearsKennethA.DeJongNavalResearchLaboratoryGeorgeMasonUniversityWashington,D.C.20375USAFairfax,VA22030USAspears@aic.nrl.navy.milkdejong@aic.gmu.edu

AbstractTraditionally,geneticalgorithmshavereliedupon1and2-pointcrossoveroperators.Manyrecentempir-icalstudies,however,haveshownthebenefitsofhighernumbersofcrossoverpoints.Someofthemostintriguingrecentworkhasfocusedonuniformcrossover,whichinvolvesontheaverageL/2cross-overpointsforstringsoflengthL.Theoreticalresultssuggestthat,fromtheviewofhyperplanesamplingdisruption,uniformcrossoverhasfewredeemingfeatures.However,agrowingbodyofexperimentalevidencesuggestsotherwise.Inthispaper,weattempttoreconciletheseopposingviewsofuniformcrossoverandpresentaframeworkforunderstandingitsvirtues.

1IntroductionOneoftheuniqueaspectsoftheworkinvolvinggeneticalgorithms(GAs)istheimportantrolethatrecombinationplays.InmostGAs,recombinationisimplementedbymeansofacrossoveroperatorwhichoperatesonpairsofindividuals(parents)toproducenewoffspringbyexchangingsegmentsfromtheparents’geneticmaterial.Traditionally,thenumberofcrossoverpoints(whichdetermineshowmanysegmentsareexchanged)hasbeenfixedataverylowconstantvalueof1or2.Supportforthisdecisioncamefromearlyworkofbothatheoreticalandempiricalnature[Holland,1975;DeJong,1975].However,therecontinuetobeindicationsthattherearesituationsinwhichhavingahighernumberofcrossoverpointsisbeneficial[Syswerda,1989;Eschelman,1989].Perhapsthemostsurprisingresult(fromatraditionalper-spective)istheeffectivenessonsomeproblemsofuni-formcrossover,anoperatorwhichproducesontheaver-ageL/2crossingsonstringsoflengthL[Syswerda,1989].

Recentworkby[SpearsandDeJong,1990]hasextendedthetheoreticalanalysisofn-pointanduniformcrossoverwithrespecttodisruptionofsamplingdistributions.

However,theypointedoutthatdisruptionanalysisaloneisnotsufficientingeneraltopredictand/orselectoptimalformsofcrossover.Inparticular,theyhaveshownthatthepopulationsizemustalsobetakenintoaccount[DeJongandSpears,1990].Thispaperextendsthatworkbylookingatthepropertiesofaparameterizeduniformcrossoveroperatorandbyconsideringtwootheraspectsofcrossoveroperators,namely,theirrecombinationpotentialandtheirexploratorypower.Inthiscontext,asurprisinglypositiveviewofuniformcrossoveremerges.

2DisruptionAnalysisHollandprovidedtheinitialformalanalysisofthebehaviorofGAsbyshowinghowtheyallocatetrialsinanearoptimalwaytocompetingloworderhyperplanesifthedisruptiveeffectsofthegeneticoperatorsusedisnottoosevere[Holland,1975].Sincemutationistypicallyrunataverylowrate,itisgenerallyignoredasasignificantsourceofdisruption.However,crossoverisusuallyappliedataveryhighrate.So,considerableattentionhasbeengiventoestimatingPd,theprobabilitythataparticularapplicationofcrossoverwillbedisrup-tive.

Holland’sinitialanalysisofthesamplingdisruptionof1-pointcrossover[Holland,1975]hasbeenextendedton-pointanduniformcrossover[DeJong,1975;SpearsandDeJong,1990].Theseresultsareintheformofestimatesofthelikelihoodthatthesamplingofakthorderhyper-plane(Hk)willbedisruptedbyaparticularformofcross-over.Itturnsouttobeeasiermathematicallytoestimatethecomplementofdisruption:thelikelihoodofasamplesurvivingcrossover(whichwedenoteasPs).Asonemightexpect,theresultsareafunctionofboththeorderkofthehyperplaneanditsdefininglength(seetheAppen-dixand[SpearsandDeJong,1990]formoreprecisedetails).

WeprovideinFigure1agraphicalsummaryofatypicalinstanceoftheseresultsforthecaseof3rdorderhyper-planes.Thenon-horizontalcurvesrepresentthesurvival

1of3rdorderhyperplanesundern-pointcrossover(n = 1...6).Thehorizontallinerepresentstheprobabilityofsurvivalunderuniformcrossover.Figure1highlightstwoimportantpoints.First,ifweinterprettheareaaboveaparticularcurveasameasureofthecumulativedisrup-tionpotentialofitsassociatedcrossoveroperator,thenthesecurvessuggestthat2-pointcrossoveristheleastdisruptiveofthen-pointcrossoverfamily,andlessdis-ruptivethanuniformcrossover.Finally,unliken-pointcrossover,uniformcrossoverdisruptsallhyperplanesoforderkwithequalprobability,regardlessofhowlongorshorttheirdefininglengthsare.3APositiveViewofCrossoverDisruptionArecurringthemeinHolland’sworkistheimportanceofaproperbalancebetweenexplorationandexploitationwhenadaptivelysearchinganunknownspaceforhighperformancesolutions[Holland,1975].Thedisruptionanalysisoftheprevioussectionimplicitlyassumesthatdisruptionofthesamplingdistributionsisabadthingandtobeavoided(e.g.,ahighdisruptionmaystressexplora-tionattheexpenseofexploitation).However,thisisnotalwaysthecase.Thereareimportantsituationsinwhichminimizingdisruptionhinderstheadaptivesearchpro-cessbyoveremphasizingexploitationattheexpenseofneededexploration.Oneoftheclearestexamplesofthisiswhenthepopulationsizeistoosmalltoprovidethenecessarysamplingaccuracyforcomplexsearchspaces[DeJongandSpears,1990].Toillustratethiswehaveselecteda30bitproblemwith6peaksfrom[DeJongandSpears,1990].Themeasureofperformanceissimplythebestindividualfoundbythegeneticalgorithm.Thisisplottedevery100evaluations.Sincewearemaximizing,highercurvesrepresentbetterPsDefiningLength0.50.60.70.80.910.50.60.70.80.91L/2L2pt1pt1ptuniformFigure1.Survivalof3rdOrderHyperplanesperformance.Figures2and3illustratetheeffectofpopulationsizeonGAperformance.Noticehowuniformcrossoverdominates2-pointcrossoveronthe6-Peakproblemwithasmallpopulation,butjusttheoppositeistruewithalargepopulation.

合集下载

2013年全国硕士研究生招生考试英语(一)答案详解

2013年全国硕士研究生招生考试英语(一)答案详解

2013年全国硕士研究生招生考试英语（一）答案详解Section I Use of English一、文章题材结构分析本文选自2012年6月16日The Economist《经济学人》，原文标题是A question of judgment(《判断上的一个问题》)的文章。

本文对“作决定时不考虑背景因素是优势”这一传统观点提出异议。

文章第一段先扬后抑，由Dr.Uri Simonsohn指出，这种优势有可能是劣势。

他认为不考虑外界因素容易受片面信息影响，无法做出客观判断，并通过法官判案这个例子来支撑这一观点。

第二段Dr.Simonsohn进一步通过大学招生程序，来验证自己的观点。

针对当前面试者不受其他面试者影响这一观点，提出怀疑。

第三段具体介绍了面试过程的安排。

第四段Dr. Simonsoho分析了面试的结果，他指出面试官给面试者打分的时候，容易受到之前面试者的分数影响，验证了自己的观点。

二、试题解析1.[A]grants赋予，授予[B]submits服从，提交[C]transmits传输，发射[D]delivers传递【答案】A【考点】动词搭配【解析】第一句提到“总体而言，当人们自己做决定时，并不擅长考虑背景信息。

”第二句顺接上文，“乍一看这是一种优势”，that引导定语从句，这种优势使人们具有一种能力，即能够做出不受外界因素影响的不带偏见的决定。

B选项submit“服从，提交”，不能与ability连用，C选项transmit“传输，发射”，也不能与ability搭配，D 选项deliver“传递”，同样不能与ability搭配。

A,C,D无论从搭配上还是意思上都不合适。

A选项grant本身具有赋予，授予的意思。

故答案选A。

2.[A]minor次要的[B]external外部的[C]crucial残酷的[D]objective客观的【答案】B【考点】上下文语义衔接+形容词辨析【解析】external外部因素和上文的background information同义复现，不考虑背景信息，不受外界因素影响。

1、Bagging predictors

1、Bagging predictors


Statistics Department, University qf Cal!'lbrnia. Berkele), CA 94720
Editor: Ross Quinlan Abstract. Bagging predictors is a method for generating multiple versions of a predictor and using these to get an aggregated predictor. The aggregation averages over the versions when predicting a numerical outcome and does a plurality vote when predicting a class. The multiple versions are formed by making bootstrap replicates of the learning set and using these as new learning sets. Tests on real and simulated data sets using classification and regression trees and subset selection in linear regression show that bagging can give substantial gains in accuracy. The vital element is the instability of the prediction method. If perturbing the learning set can cause significant changes in the predictor constructed, then bagging can improve accuracy.
东南大学博士学位论文结果不同重组...

东南大学博士学位论文结果不同重组...

东南大学博士学位论文基因密码子使用和蛋白质结构的生物信息学分析姓名：***申请学位级别：博士专业：生物医学工程指导教师：***20040401东南大学博士学位论文摘要论文题目：基因密码子使，ｑＪ和蛋白质结构的生物信息学分析研究生姓名：顾万君导师姓名：陆祖宏（教授）学校名称：东南人学随着人类基冈组计划雨Ｉ模式生物基因组计划的完成，公共数据库中生物数据的增艮速度越来越快。

如何从海量的生物数据中解读、提取和获得有片；｜的生物信息，己成为基因组计划下一步亟待解决的问题。

本文中，我们利用生物信息学的方法对基因的周义密码子使用进行了统计分析，研究了不局物种中蛋白质结构和基因周义密码子使用间可能存在的相关性，提出了一种基于密码子的氨基酸二级结构偏向性参数。

同时，我们还在蛋白质二级结构预测的神经网络方法中引入了蛋白质编码基因的密码子使用信息．在预测大肠杆菌的蛋白质的二级结构时提高了预测的准确率。

最后，我们还提出了一种根据单倍体数据将基冈组划分成若干很少出现重组现象的块结构的新方法。

论文的主要内容如下：１．在基因组中，基因的同义密码子使用并不是随机选择的。

研究不周物种中基因的密码子使用模式以及形成这种密码子使用模式的内在因素，对于了解基因组的特征和物种的分子进化具有重要作崩。

我们对一些物种的基因密码子使用模式进行了分析，并且进一步分析了这些物种中影响密码子使用的内在因素。

●通过ＳＡＲＳ病毒基因组和进化上相近的病毒基因组的密码子使用偏性的分析，我们发现在这些病毒基冈组中尽管基因的同义密码子使用存在着偏向性，但是偏向性程度并不高。

这些病毒基因组中，影响同义密码子使用的最主要因素是进化中的碱基突变压力。

同时，基冈的功能也在一定程度上决定了这些病毒基因中密码子的选择。

但是，基因长度和基因翻译过程中的选择作用在这些病毒中并不影响基因的密码子使用。

另外，在这些病毒基囡组中，密码子使用模式在进化上是保守的。

基于密码子使用模式的进化分析表明，ＳＡＲＳ冠状病毒在进化上与其它己知的冠状病毒都不是很近。

03-BLAST(生物信息学国外教程2010版)

03-BLAST(生物信息学国外教程2010版)

page 109
BLAST search output: top portion
database query
program
taxonomy
page 112
BLAST search output: taxonomy report summarizes species with matches
BLAST search output: graphical output
page 112
BLAST search output: tabular output
High scores low E values
Cut-off: .05? 10-10?
page 113
BLAST search output: alignment output
Outline of today’s lecture
Step 4: optional parameters
You can... • choose the organism to search • turn filtering on/off • change the substitution matrix • change the expect (e) value • change the word size • change the output format
page 109
(c) Query: human insulin NP_000198 Program: blastp Database: C. elegans RefSeq Option: conditional compositional score matrix adjustment
Note that the bit score, Expect value, and percent identity all change with the compositional score matrix adjustment