New ant colony optimization for searching the minimum distance for linear codes

Abstract

In coding theory, finding minimum distance remains one of the most open problems, actually it was proven to be an NP-hard type. Therefore classical algorithms become impracticable for large codes. Metaheuristic approaches come out to tackle this kind of problems by producing “good” solutions but eventually not the best at reasonable computational cost. In this paper we will attack this problem using Ant Colony Optimization (ACO), one of the successful swarm intelligence metaheuristic methods, derived from nature, especially the collective behavior of ants to find the best path to food, our implementation tested on linear codes then compared with previous works. The obtained results show an improvement in solution accuracy and computational cost.