A DNA based evolutionary algorithm for the minimal set cover problem

Liu, W; Zhu, X; Xu, G; Zhang, Q; Gao, L

A DNA based evolutionary algorithm for the minimal set cover problem

Liu, W Zhu, X Xu, G

Zhang, Q Gao, L

Permalink

Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science, 2005, 3645 (PART II), pp. 80 - 89
Issue Date:: 2005-10-31

Closed Access

	Filename	Description	Size
	chp%3A10.1007%2F11538356_9.pdf	Published version	192.01 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Liu, W	en_US
dc.contributor.author	Zhu, X	en_US
dc.contributor.author	Xu, G https://orcid.org/0000-0003-4493-6663	en_US
dc.contributor.author	Zhang, Q	en_US
dc.contributor.author	Gao, L	en_US
dc.date.issued	2005-10-31	en_US
dc.identifier.citation	Lecture Notes in Computer Science, 2005, 3645 (PART II), pp. 80 - 89	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://hdl.handle.net/10453/33800
dc.description.abstract	With the birth of DNA computing, Paun et al. proposed an elegant algorithm to this problem based on the sticky model proposed by Roweis. However, the drawback of this algorithm is that the "exponential curse" is hard to overcome, and therefore its application to large instance is limited. In this s paper, we present a DNA based evolutionary algorithm to solve this problem, which takes advantage of both the massive parallelism and the evolution strategy by traditional EAs. The fitness of individuals is defined as the negative value of their length. Both the crossover and mutation can be implemented in a reshuffle process respectively. We also present a short discussion about population size, mutation probability, crossover probability, and genetic operations over multiple points. In the end, we also present some problems needed to be further considered in the future. © Springer-Verlag Berlin Heidelberg 2005.	en_US
dc.relation.ispartof	Lecture Notes in Computer Science	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.title	A DNA based evolutionary algorithm for the minimal set cover problem	en_US
dc.type	Conference Proceeding
utslib.citation.volume	PART II	en_US
utslib.citation.volume	3645	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
pubs.organisational-group	/University of Technology Sydney/Strength - AAI - Advanced Analytics Institute Research Centre
utslib.copyright.status	closed_access
pubs.issue	PART II	en_US
pubs.publication-status	Published	en_US
pubs.volume	3645	en_US

Abstract:

With the birth of DNA computing, Paun et al. proposed an elegant algorithm to this problem based on the sticky model proposed by Roweis. However, the drawback of this algorithm is that the "exponential curse" is hard to overcome, and therefore its application to large instance is limited. In this s paper, we present a DNA based evolutionary algorithm to solve this problem, which takes advantage of both the massive parallelism and the evolution strategy by traditional EAs. The fitness of individuals is defined as the negative value of their length. Both the crossover and mutation can be implemented in a reshuffle process respectively. We also present a short discussion about population size, mutation probability, crossover probability, and genetic operations over multiple points. In the end, we also present some problems needed to be further considered in the future. © Springer-Verlag Berlin Heidelberg 2005.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/33800