A Meta Heuristic Solution for Closest String Problem Using Ant Colony System

被引：0

作者：

Bahredar, Faranak ^{[1
]}

Erfani, Hossein ^{[2
]}

Javadi, H. Haj Seyed ^{[3
]}

Masaeli, Nafiseh ^{[1
]}

机构：

[1] Payam Noor Univ, Dept Informat Technol, Tehran, Iran

[2] Islamic Azad Univ, Comp Engn Dept, Sci & Res Branch, Tehran, Iran

[3] Shahed Univ, Dept Math & Comp Sci, Tehran, Iran

来源：

DISTRIBUTED COMPUTING AND ARTIFICIAL INTELLIGENCE | 2010年 / 79卷

关键词：

Closest string; Ant colony system; Meta heuristic; OPTIMIZATION; ALGORITHMS; DESIGN;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Suppose Sigma is the alphabet set and S is the set of strings with equal length over alphabet Sigma. The closest string problem seeks for a string over Sigma that minimizes the maximum hamming distance with other strings in S. The closest string problem is NP-complete. This problem has particular importance in computational biology and coding theory. In this paper we present an algorithm based on ant colony system. The proposed algorithm can solve closest string problem with reasonable time complexity. Experimental results have shown the correctness of algorithm. At the end, a comparison with one Meta heuristic algorithm is also given.

引用

页码：549 / +

页数：3

共 16 条

[1] Genetic design of drugs without side-effects [J].

Deng, X ;

Li, G ;

Li, Z ;

Ma, B ;

Wang, LS .

SIAM JOURNAL ON COMPUTING, 2003, 32 (04) :1073-1090

[2]

DOPAZO J, 1993, COMPUT APPL BIOSCI, V9, P123

[3] Ant system: Optimization by a colony of cooperating agents [J].

Dorigo, M ;

Maniezzo, V ;

Colorni, A .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS PART B-CYBERNETICS, 1996, 26 (01) :29-41

[4]

Evans PA, 2003, LECT NOTES COMPUT SC, V2751, P210

[5]

Faro S, 2010, LECT NOTES COMPUT SC, V5901, P370

[6]

Frances M, 1997, THEOR COMPUT SYST, V30, P113

[7] A parallel multistart algorithm for the closest string problem [J].

Gomes, Fernando C. ;

Meneses, Claudio N. ;

Pardalos, Panos M. ;

Viana, Gerardo Valdisio R. .

COMPUTERS & OPERATIONS RESEARCH, 2008, 35 (11) :3636-3643

[8] Fixed-parameter algorithms for CLOSEST STRING and related problems [J].

Gramm, J ;

Niedermeier, R ;

Rossmanith, P .

ALGORITHMICA, 2003, 37 (01) :25-42

[9]

Gramm J., 2002, Currents in Computational Molecular Biology, P74

[10]

Lanctot JK, 1999, PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P633

← 1 2 →