The time complexity analysis of a class of gene expression programming

Xin DU; Youcong NI; Datong XIE; Xin YAO; Peng YE; Ruliang XIAO

doi:10.1007/s00500-014-1551-y

The time complexity analysis of a class of gene expression programming

Xin DU, Youcong NI, Datong XIE, Xin YAO, Peng YE, Ruliang XIAO

Research output: Journal Publications › Journal Article (refereed) › peer-review

7 Citations (Scopus)

Abstract

This paper studies the time complexity of gene expression programming based on maintaining elitist (ME-GEP). Using the theory of Markov chain and the technique of artificial fitness level, the properties of transition matrices of ME-GEP are analyzed. Based on the properties, the upper and lower bounds of the average time complexity of ME-GEP are obtained. Furthermore, the upper bound is estimated, which is determined by the parameters of ME-GEP algorithm. And the theoretical results acquired in this paper are used to analyze ME-GEP for solving function modeling and clustering problem. At last, a set of experiments are performed on these problems to illustrate the effectiveness of theoretical results. The results show that the upper bound of expected first hitting time can be used to direct the algorithm design of ME-GEP. © 2014, Springer-Verlag Berlin Heidelberg.

Original language	English
Pages (from-to)	1611-1625
Number of pages	15
Journal	Soft Computing
Volume	19
Issue number	6
Early online date	12 Dec 2014
DOIs	https://doi.org/10.1007/s00500-014-1551-y
Publication status	Published - Jun 2015
Externally published	Yes

Bibliographical note

This work was supported by the National Natural Science Foundation of China (No. 61305079, 61305086, 61203306), the project of preeminent youth fund of Fujian province (JA12471), outstanding young teacher training fund of Fujian Normal University (No. fjsdjk2012083), the open fund of State Key Laboratory of Software Engineering (No. SKLSE2012-09-28). Finally, we thank Prof. Jinghu Yu for discussing some issues about this paper.

Keywords

Artificial fitness level
Average time complexity
GEP
Markov chain
ME-GEP

Access to Document

10.1007/s00500-014-1551-y

Cite this

@article{ecee09720e28437dbccb345bb68a312e,

title = "The time complexity analysis of a class of gene expression programming",

abstract = "This paper studies the time complexity of gene expression programming based on maintaining elitist (ME-GEP). Using the theory of Markov chain and the technique of artificial fitness level, the properties of transition matrices of ME-GEP are analyzed. Based on the properties, the upper and lower bounds of the average time complexity of ME-GEP are obtained. Furthermore, the upper bound is estimated, which is determined by the parameters of ME-GEP algorithm. And the theoretical results acquired in this paper are used to analyze ME-GEP for solving function modeling and clustering problem. At last, a set of experiments are performed on these problems to illustrate the effectiveness of theoretical results. The results show that the upper bound of expected first hitting time can be used to direct the algorithm design of ME-GEP. {\textcopyright} 2014, Springer-Verlag Berlin Heidelberg.",

keywords = "Artificial fitness level, Average time complexity, GEP, Markov chain, ME-GEP",

author = "Xin DU and Youcong NI and Datong XIE and Xin YAO and Peng YE and Ruliang XIAO",

note = "This work was supported by the National Natural Science Foundation of China (No. 61305079, 61305086, 61203306), the project of preeminent youth fund of Fujian province (JA12471), outstanding young teacher training fund of Fujian Normal University (No. fjsdjk2012083), the open fund of State Key Laboratory of Software Engineering (No. SKLSE2012-09-28). Finally, we thank Prof. Jinghu Yu for discussing some issues about this paper.",

year = "2015",

month = jun,

doi = "10.1007/s00500-014-1551-y",

language = "English",

volume = "19",

pages = "1611--1625",

journal = "Soft Computing",

issn = "1432-7643",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "6",

}

TY - JOUR

T1 - The time complexity analysis of a class of gene expression programming

AU - DU, Xin

AU - NI, Youcong

AU - XIE, Datong

AU - YAO, Xin

AU - YE, Peng

AU - XIAO, Ruliang

N1 - This work was supported by the National Natural Science Foundation of China (No. 61305079, 61305086, 61203306), the project of preeminent youth fund of Fujian province (JA12471), outstanding young teacher training fund of Fujian Normal University (No. fjsdjk2012083), the open fund of State Key Laboratory of Software Engineering (No. SKLSE2012-09-28). Finally, we thank Prof. Jinghu Yu for discussing some issues about this paper.

PY - 2015/6

Y1 - 2015/6

N2 - This paper studies the time complexity of gene expression programming based on maintaining elitist (ME-GEP). Using the theory of Markov chain and the technique of artificial fitness level, the properties of transition matrices of ME-GEP are analyzed. Based on the properties, the upper and lower bounds of the average time complexity of ME-GEP are obtained. Furthermore, the upper bound is estimated, which is determined by the parameters of ME-GEP algorithm. And the theoretical results acquired in this paper are used to analyze ME-GEP for solving function modeling and clustering problem. At last, a set of experiments are performed on these problems to illustrate the effectiveness of theoretical results. The results show that the upper bound of expected first hitting time can be used to direct the algorithm design of ME-GEP. © 2014, Springer-Verlag Berlin Heidelberg.

AB - This paper studies the time complexity of gene expression programming based on maintaining elitist (ME-GEP). Using the theory of Markov chain and the technique of artificial fitness level, the properties of transition matrices of ME-GEP are analyzed. Based on the properties, the upper and lower bounds of the average time complexity of ME-GEP are obtained. Furthermore, the upper bound is estimated, which is determined by the parameters of ME-GEP algorithm. And the theoretical results acquired in this paper are used to analyze ME-GEP for solving function modeling and clustering problem. At last, a set of experiments are performed on these problems to illustrate the effectiveness of theoretical results. The results show that the upper bound of expected first hitting time can be used to direct the algorithm design of ME-GEP. © 2014, Springer-Verlag Berlin Heidelberg.

KW - Artificial fitness level

KW - Average time complexity

KW - GEP

KW - Markov chain

KW - ME-GEP

UR - http://www.scopus.com/inward/record.url?scp=84939938265&partnerID=8YFLogxK

U2 - 10.1007/s00500-014-1551-y

DO - 10.1007/s00500-014-1551-y

M3 - Journal Article (refereed)

SN - 1432-7643

VL - 19

SP - 1611

EP - 1625

JO - Soft Computing

JF - Soft Computing

IS - 6

ER -

The time complexity analysis of a class of gene expression programming

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this