论文标题
具有基于置换的表示线性代码距离的遗传算法
Genetic algorithms with permutation-based representation for computing the distance of linear codes
论文作者
论文摘要
找到线性代码的最小距离是一个NP硬性问题。传统上，通过算法的设计来解决该计算，这些算法通过巧妙的详尽搜索发现了一些生成矩阵行的线性组合，该组合可提供最小重量的代码字。因此，随着代码的尺寸或基础有限字段的大小增加，因此它的运行时间为指数。在这项工作中，我们证明，在生成矩阵的情况下，存在一个列置换，该列置换导致降低的行echelon形式，其中包含一排，其权重为代码距离。与通常的离散表示形式相反，该结果可以将置换用作表示方案，这使得搜索从基本场上依赖最佳的多项式时间。特别是，我们使用此表示形式作为概念证明实施了遗传和CHC算法。实验结果是通过在具有两个和八个要素的字段上使用的代码进行的，这表明使用我们提出的置换编码的进化算法在文献中现有方法方面具有竞争力。作为副产品，我们在岩浆计算代数系统中发现并修改了有关某些线性代码储存距离的一些不准确性。
Finding the minimum distance of linear codes is an NP-hard problem. Traditionally, this computation has been addressed by means of the design of algorithms that find, by a clever exhaustive search, a linear combination of some generating matrix rows that provides a codeword with minimum weight. Therefore, as the dimension of the code or the size of the underlying finite field increase, so it does exponentially the run time. In this work, we prove that, given a generating matrix, there exists a column permutation which leads to a reduced row echelon form containing a row whose weight is the code distance. This result enables the use of permutations as representation scheme, in contrast to the usual discrete representation, which makes the search of the optimum polynomial time dependent from the base field. In particular, we have implemented genetic and CHC algorithms using this representation as a proof of concept. Experimental results have been carried out employing codes over fields with two and eight elements, which suggests that evolutionary algorithms with our proposed permutation encoding are competitive with regard to existing methods in the literature. As a by-product, we have found and amended some inaccuracies in the MAGMA Computational Algebra System concerning the stored distances of some linear codes.
