Heuristic optimisation for the minimum distance problem

Chan, EY-S, 2000. Heuristic optimisation for the minimum distance problem. PhD, Nottingham Trent University.

Preview

Text 10183000.pdf - Published version Download (22MB) | Preview

Abstract

In this thesis two heuristic optimisation techniques are investigated, with the aim of obtaining minimum distance estimates of particular error-correcting codes.

Minimum distances are important in Coding Theory because the error-correcting capability of codes is dependent upon them. However, the exact minimum distances of many practically important codes are still unknown and so, for codes such as quadratic residue (QR) codes, the minimum distance problem (MDP) remains open. In this thesis the mathematical development of QR codes is presented and the MDP for particular QR codes is then investigated using heuristic optimisation techniques.

Heuristic techniques are necessary due to the combinatorial nature of the problem and the non-convex nature of the solution-space. In this thesis the particular heuristic optimisation techniques applied to the MDP are tabu search (TS) and ant colony optimisation (ACO). TS uses a neighbourhood search procedure in which use is made of a memory facility, called the tabu list, which enables the search to progress beyond local optima in the quest for a global optimum. Recently TS has been successfully applied to Bose-Chaudhuri-Hocquengham codes using a short-term memory approach. In this thesis longer-term strategies and a number of 'memory' lists are developed within a TS algorithm, to find minimum distance estimates for large QR codes.

Recently several discrete optimisation techniques have been developed by analogy with physical and biological processes (for example, simulated annealing and genetic algorithms). Because analogies with natural phenomena have been used to successfully derive non-deterministic heuristic methods which can be applied to NP-complete combinatorial optimisation problems, there is a growing interest in this approach to problem solving. ACO is a population-based method which was inspired by the behaviour of a colony of ants and their ability to 'optimise' their collective endeavours. In this thesis ACO is formulated in an error-correcting code context. A basic ACO algorithm is first presented and then developed to incorporate the co-operation amongst members of the colony. The developed ACO algorithm, together with TS as a local improvement phase, is then applied to large QR codes to obtain minimum distance estimates.

Item Type:	Thesis
Creators:	Chan, E.Y.-S.
Date:	2000
ISBN:	9781369312980
Identifiers:	Number Type PQ10183000 Other
Divisions:	Schools > School of Science and Technology
Record created by:	Jeremy Silvester
Date Added:	28 Aug 2020 10:21
Last Modified:	14 Jun 2023 09:38
URI:	https://irep.ntu.ac.uk/id/eprint/40563

Actions (login required)

Edit View

Statistics

Views

Downloads