基于混合进化算法的子结构发现研究

《基于混合进化算法的子结构发现研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、4[r[1[irlrl[,r[,,ffj,rpijrlllrlf[r![![1[1lllrlll』Y1531691博士学位论文基于混合进化算法的子结构发现研究ResearchonSubstructureDiscoveryBasedonHybridEvolutionaryAlgorithms一级学科筻堡型堂生王猩学科专业笪堡抖堂皇工捏作者姓名鲎堑功指导教师童缉滥天津大学管理学院二零零八年一月AbstractRelationshipsareubiquitous．Recently,structureddataminingwhic

2、hleamsvariousrelationshipsbetweenentitieshasbeenbroughtintofocusandbecomeamainbranchofdataminingandmachinelearning．structuredrepresentationscangiveamoreinformativeandessentialviewoftheproblemathand，butoften1eadtolargeandcomplexhypothesisspaces，andhenceprovideanewc

3、hallengeoverthedomainsofdataminingandmachinelearning．Inthispaperwehaveusedtheevolutionaryalgorithmwhichisgoodatsolvingmanycomplexoptimizationproblemstothesubstructurediscovery,oneofthecentraltasksofstructureddatamining，andachievedbetterexperimentalresults．Themainc

4、ontentsareasfollows．一1．AnalgorithmHEASDisproposedbasedonthetheoryofhybfidevolutionaryalgorithmstodiscoversubstructuresfromgraphicaldatabases．InHEASD，wegivenewgraph．basedindividualrepresentationandgeneticoperatorswhichareintegratedwiththehill．climbing．Theexperiment

5、alresultsshowitseffectiveness．Inaddition，anewwayofsubstructureextending，single．1abelextending，ispresentedandjustifiedthroughtheoreticalproofandexperiments．2．Beingabottleneckproblemofgraphicaldatamining，subgraphisomorphismiSconsideredastherootofa11complexities．Itma

6、kestheevolutionarysearchingaone．waysearch，whichisactuallyanincompletesearch．Todealwiththeincompleteness，weproposeHEASDBTwhichCallfocusthesearchonsomeregionsofhypothesisspacewithbacktrackingstrategy．Theexperimentalresultsshowitseffectiveness．3．Toovercometheproblemt

7、hatqualitiesofsolutionsareoftenreducedbythephenomenonoflosinginstances，weproposetwoalgorithms，HEASDFIandHEASDCI．Whiletheformerusesapreventionstrategytoavoidlosinginstances，thelatteremploysacuringstrategythatcangetbackthelostinstances．Theireffectivenessisillustrate

8、dinexperiments．Atthesametime，inHEASDCI，anewgeneticoperator，calledindividualscooperationoperator,whichenablesthesearchingofdifferentindividualsthatrepres