A DNA based evolutionary algorithm for the minimal set cover problem

Publication Type:
Conference Proceeding
Lecture Notes in Computer Science, 2005, 3645 (PART II), pp. 80 - 89
Issue Date:
Filename Description Size
chp%3A10.1007%2F11538356_9.pdf Published version192.01 kB
Adobe PDF
Full metadata record
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: