摘 要

最优哥伦布尺（Golomb Ruler，也译作哥隆尺）问题属于一类尚未解决的疑似NP-hard问题，在雷达脉冲编码、射电天文学、导弹制导码、射频分配等诸多工程领域中有着广泛的应用。由于用一般方法求解最优哥伦布尺的时间复杂度是呈几何增长的，并且目前还没有任何能够求解任意刻度的最优哥伦布尺的有效算法，因此寻求一种高效的、能够在有限的时间内求得近似最优哥伦布尺方法不失为一种正确的选择。

本文在介绍了哥伦布尺的概念和特点、遗传算法的思想与过程的基础上，讨论了求解最优哥伦布尺的改进遗传算法，并在编码实验后，在可观的时间内求得了刻度规模在[4，40]内的近似最优哥伦布尺。在得出实验数据之后，对数据本身以及和最优哥伦布尺的对比作了详细的分析，并对此算法的效率和精确度作了一定的探讨。本文还列举了求解最优哥伦布尺的其它方法，并对它们在各个刻度区间的精度作了比较与分析。本文最后就哥伦布尺在射电天文学方面的应用作了建模研究，还简要说明了哥伦布尺在信道分配等众多领域的应用，体现了哥伦布尺巨大的应用价值。

关键词：哥伦布尺；遗传算法；近似最优；射电天文学

Abstract

The optimal Golomb ruler belongs to a kind of suspected NP-hard problem that has not been solved yet, which is widely used in many engineering fields, such as radar pulse code, radio astronomy, missile guidance code, radio frequency distribution and so on. Because the time complexity of the general method to solve the optimal Golomb ruler is increasing geometrically, and there is no effective algorithm to solve the optimal Golomb ruler with any scale at present, it is a correct choice to find an effective method to obtain the approximate optimal Golomb ruler in a limited time.

Based on the introduction of the concept and characteristics of Cologne ruler, the idea and process of genetic algorithm, this paper discusses the improved genetic algorithm for solving the optimal Golomb ruler, and after the coding experiment, the approximate optimal Golomb ruler with scale in [4,40] is obtained in considerable time. After obtaining the experimental data, the data itself and the comparison with the optimal Cologne scale are analyzed in detail, and the efficiency and accuracy of the algorithm are discussed. In this paper, other methods for solving the optimal Golomb ruler are also listed, and their accuracy in each scale interval is compared and analyzed. At the end of this paper, the application of Golomb ruler in radio astronomy is studied, and the application of Golomb ruler in many fields, such as channel assignment, is briefly explained, which shows the great application value of Golomb ruler.

Key Words： Golomb ruler； Genetic Algorithm；Approximately optimal；Radio astronomy

目 录

第1章 绪论 1

1.1 研究背景与意义 1

1.2 国内外研究现状 1

1.3 研究内容与结构 2

第2章 哥伦布尺与遗传算法的理论基础 3

2.1 哥伦布尺相关介绍 3

2.1.1 哥伦布尺相关概念 3

2.1.2 哥伦布尺的理论知识 4

2.2 遗传算法理论基础 5

2.2.1 遗传算法的原理与过程 6

2.2.2 遗传算法的特点与现状 7

第3章 基于遗传算法的哥伦布尺搜索设计 9

3.1适用于解决哥伦布尺问题的遗传算法 9

3.1.1算法伪码 9

3.1.2 算法说明 10

3.2 算法分析与流程图 11

第4章 基于遗传算法的哥伦布尺的求解结果与分析 14

4.1 实验求得哥伦布尺序列的结果展示 14

4.2 实验求得哥伦布尺序列的对比分析 16

4.2.1 实验结果与最优哥伦布尺的对比 16

4.2.2 实验结果与其它算法所得结果的对比 17

4.2.3 由实验结果分析算法 18

第5章 哥伦布尺的应用 21

5.1 哥伦布尺在无线通信中应用 21

5.1.1 案例背景 21

5.1.2 案例模型与分析 21

5.2 哥伦布尺在射电天文学中的应用 22

5.2.1 案例背景 22

5.2.2 案例模型 22

第6章 总结与展望 24

6.1 本文工作总结 24

6.2 本文工作展望 24

参考文献 26

致 谢 28

第1章 绪论

本章主要从哥伦布尺在无线通信中的应用出发，简要地解释了哥伦布尺在众多工程领域方面重要的应用价值，介绍了哥伦布尺的由来，列举了目前求解最优哥伦布尺常用的一些算法，说明了近似最优哥伦布尺在国内外的研究现状，简略地介绍了本文研究的内容和文章的脉络结构。

1.1 研究背景与意义

进入21世纪，随着科学技术的飞速发展，信息传递已经成为了人们生活中不可或缺的交流形式。在通信领域中，无线通信发展最快、应用最广，是一种利用电磁波信号在空间中传递信息的通信技术。无线通信涉及军事领域、卫星系统、无线电话等多个领域，已经与人们的生活息息相关。然而，在人们享受无线通信带来的方便快捷的同时，无线通信的缺点也暴露出来了。由于信号干扰问题，导致设备接收和发送的信号会出现信号波动、不可靠性的特点。

信号干扰中，互调干扰对电波的稳定性影响最大，它具有非线性结构，能够明显增加信噪比，严重紊乱了信号的频谱。事实证明，互调干扰是无法避免的，因此，国内外的许多科学家对如何减少互调干扰对信息传递的影响做了大量的研究工作。1953年，一位学者在研究互调干扰的过程中发现，在信号的相同频带内选择不同距离的通道能有效减少互调干扰，后来对该发现进行详细研究，恰好抽象为以数学家Golomb.S.W命名的哥伦布尺问题。