文章基本信息

标题：Maximally Distant Codes Allocation Using Chemical Reaction Optimization and Ant Colony Optimization Algorithms
本地全文：下载
作者：Taisir Eldos ; Waleed Nazih ; Aws Kanan 等
期刊名称：Journal of Computer Science
印刷版ISSN：1549-3636
出版年度：2015
卷号：11
期号：8
页码：892-901
DOI：10.3844/jcssp.2015.892.901
出版社：Science Publications
摘要：Error correcting codes, also known as error controlling codes, are set of codes with redundancy that allows detecting errors. This is quite useful in transmitting data over a noisy channel or when retrieving data from a storage with possible physical defects. The idea is to use a set of code words that are maximally distant from each other, hence reducing the chance of changing a valid codeword to another valid codeword by flipping bits. The problem can be viewed as picking m codes out of 2ⁿ available n-bit combinations, such that the aggregate hamming distance among those codewords is maximized. Due to the large solution spaces of such problems, greedy algorithms are sometimes used to generate quick and dirty solutions. However, modern evolutionary search algorithms like genetic algorithms, swarm particles, gravitational search and others, offer good alternatives, yielding near optimal solutions in exchange for some time. Chemical Reaction Optimization (CRO) has emerged as a new evolutionary algorithm to solve complex optimization problems. This algorithm mimics the molecular interactions towards finding a minimal energy state, which corresponds to an optimal solution for the problem in hand. In this research, we proposed a solution for the maximally distant codes allocation problem, through a binary knapsack mapping and compared the performance with the well established Ant Colony Optimization (ACO) algorithm, which is inspired by the ant’s capability to find the shortest path between the nest and source of food. The binary knapsack mapping was used in the two algorithms. Test results showed that the CRO outperformed the ACO in every metric given any time budget.
关键词：Maximally Distant Codes; Evolutionary Algorithms; Chemical Reaction Optimization; Ant Colony Optimization