进化规划算法的时间复杂度分析

计算机研究与发展ISSN

1000—1239/CNI卜1777/TP

Journal

ofComputerResearchandDevelopment

45(11):1850—1857,2008

进化规划算法的时间复杂度分析

翰1’2

郝志峰2

勇3

1(华南理工大学软件学院

广州

510006)

2(华南理工大学计算机科学与工程学院广州

510006)

3(茂名学院信息与网络中心广东茂名525000)(bssthh@163.corn)

TimeComplexityofEvolutionaryProgramming

HuangHanl“,HaoZhifen92,andQinYon93

1(School

ofSoftwareEngineering,SouthChinaUniversityofTechnology。Guangzhou510006)

2(CollegeofComputerScienceandEngineering,SouthChinaUniversityofTechnology,Guangzhou510006)

3(Center

ofInformationandNetwork,MaomingUniversity,Maoming,Guangdong525000)

AbstractAs

methodofevolutionarycomputation,evolutionaryprogramming(EP)algorithmis

an

evolutionaryalgorithm

for

continuousoptimization

problems.Theconvergence

of

EP

hasbeen

proved,butthere

are

fewstudies

on

thetimecomplexityofEP,whichis

one

ofthehardproblemsin

evolutionarycomputation.EPalgorithm

can

bemodeled

asan

absorbingMarkovprocessbecauseofits

comparisonselection.Theitemcalledaverageconvergencetimeisusedtoproposea

method

tO

analyze

the

time

complexity

of

EPalgorithm

based

on

absorbing

Markov

process

model.The

average

convergence

time

can

becalculatedwiththe

probabilitythattheEPalgorithmattains

theoptimalsolutionin

the

next

iterationbut

not

inthe

current

iteration.Adirectapproach

tO

estimatethe

convergence

timeisgiven

as

theorem.Furthermore,thecorollariesofthetheoremindicatetheway

tO

estimatetheboundsoftheconvergencetime.Theconvergencetimereveals

howmanyiteration

timestheEPalgorithmuses

to

convergeto

theoptimalsolution.Therefore,theproposedtheoremandcorollaries

can

beconsideredas

thetime

complexity

theory

for

the

foundation

of

evolutionary

programming.Finally,theaverageconvergencetimeofGauss—mutationevolutionaryprogrammingisanalyzed

as

an

applicationcase

studyoftheproposedtheory.

Keywords

evolutionary

computation;evolutionary

programming

algorithm;time

complexity;

averageconvergence

time;Gaussmutation

摘要进化规划算法是求解连续优化问题的一类进化算法,是进化计算的一个重要分支.在进化规划算法的理论研究上,已有学者证明了其收敛性.然而,进化规划算法的时间复杂度分析是进化计算领域一大难题,目前相关的研究成果很少.基于吸收态Markov过程模型,以期望收敛时间作为研究进化规划算法时间复杂度的指标,提出了进化规划算法期望收敛时间的估算方法,并以此作为算法时间复杂度分析的理论依据.最后分析了Gauss变异进化规划算法的期望收敛时间,作为提出理论的应用举例.关键词进化计算;进化规划算法;时间复杂度;期望收敛时间;Gauss变异

中图法分类号TPl8

收稿日期:2008—04—30;修回日期:2008—06~26

基金质目:国家自然科学基金项目(60433020,10471045),广东省自然科学基金项目(970472,000463,04020079,05011896),广东省教育部

产学研结合基金项目(20078090400031)

Word文档免费下载Word文档免费下载:进化规划算法的时间复杂度分析 (共9页,当前第1页)

你可能喜欢

  • 时间复杂度的计算
  • 广义逆矩阵
  • 数据结构c语言版复习
  • 数据结构试题及答案
  • 数据结构严蔚敏

进化规划算法的时间复杂度分析相关文档

最新文档

返回顶部