科学技术与工程

ILS 台站	LOC 纬度/ °N	LOC 经度/ °E	LOC频率/ MHz	GS频率/ MHz	DME频率/ MHz
ILS-1	28.45	104.35	108.30	334.10	1 044
ILS-2	31.10	104.21	111.15	331.55	1 072
ILS-3	29.34	106.32	111.55	332.75	1 076
ILS-4	25.31	103.46	108.90	329.30	1 050
ILS-5	34.22	108.42	108.30	334.10	1 044

ILS 台站	LOC 纬度/ °N	LOC 经度/ °E	LOC频率/ MHz	GS频率/ MHz	DME频率/ MHz
ILS-1	28.45	104.35	108.30	334.10	1 044
ILS-2	31.10	104.21	111.15	331.55	1 072
ILS-3	29.34	106.32	111.55	332.75	1 076
ILS-4	25.31	103.46	108.90	329.30	1 050
ILS-5	34.22	108.42	108.30	334.10	1 044

VOR台站	VOR纬度/ °N	VOR经度/ °E	VOR频率/ MHz	DME频率/ MHz
VOR-1	24.26	118.07	108.20	1 043
VOR-2	25.05	102.41	108.40	1 045
VOR-3	25.33	100.12	109.40	1 055
VOR-4	26.03	119.17	109.65	1 057
VOR-5	26.35	101.44	109.80	1 059
VOR-6	26.34	106.41	113.20	1 103
VOR-7	26.34	104.51	109.65	1 057
VOR-8	27.41	106.54	112.60	1 097
VOR-9	28.55	105.23	108.40	1 045
VOR-10	29.17	106.17	109.40	1 055
VOR-11	29.34	106.32	111.20	1 073
VOR-12	29.60	102.60	110.80	1 069
VOR-13	30.41	104.05	108.40	1 045
VOR-14	31.51	117.18	109.80	1 059
VOR-15	34.21	107.10	110.85	1 069
VOR-16	36.03	103.52	108.60	1 047
VOR-17	36.37	101.49	108.40	1 045
VOR-18	36.41	117.01	108.40	1 045
VOR-19	39.56	116.25	108.20	1 043

VOR台站	VOR纬度/ °N	VOR经度/ °E	VOR频率/ MHz	DME频率/ MHz
VOR-1	24.26	118.07	108.20	1 043
VOR-2	25.05	102.41	108.40	1 045
VOR-3	25.33	100.12	109.40	1 055
VOR-4	26.03	119.17	109.65	1 057
VOR-5	26.35	101.44	109.80	1 059
VOR-6	26.34	106.41	113.20	1 103
VOR-7	26.34	104.51	109.65	1 057
VOR-8	27.41	106.54	112.60	1 097
VOR-9	28.55	105.23	108.40	1 045
VOR-10	29.17	106.17	109.40	1 055
VOR-11	29.34	106.32	111.20	1 073
VOR-12	29.60	102.60	110.80	1 069
VOR-13	30.41	104.05	108.40	1 045
VOR-14	31.51	117.18	109.80	1 059
VOR-15	34.21	107.10	110.85	1 069
VOR-16	36.03	103.52	108.60	1 047
VOR-17	36.37	101.49	108.40	1 045
VOR-18	36.41	117.01	108.40	1 045
VOR-19	39.56	116.25	108.20	1 043

拟建VOR台站	VOR纬度/°N	VOR经度/°E
ProVOR-1	28.11	112.60
ProVOR-2	30.36	114.18
ProVOR-3	21.38	108.21
ProVOR-4	22.49	108.20

拟建VOR台站	VOR纬度/°N	VOR经度/°E
ProVOR-1	28.11	112.60
ProVOR-2	30.36	114.18
ProVOR-3	21.38	108.21
ProVOR-4	22.49	108.20

算法	最小干扰数	最大频率复用因子
传统多目标遗传算法	2	75
优化权重指配的多目标遗传算法	1	77
多目标遗传局部搜索算法	0	91

算法	最小干扰数	最大频率复用因子
传统多目标遗传算法	2	75
优化权重指配的多目标遗传算法	1	77
多目标遗传局部搜索算法	0	91

基于多目标遗传局部搜索算法的航空导航台频率指配

PDF下载

徐亚军 , 郝博扬 ^* , 高田露 , 张强 , 鲁合德 , 曾葆鸿

科学技术与工程 | 论文·航空、航天 2025,25(15): 6530-6537

收起

科学技术与工程 | 论文·航空、航天 2025, 25(15): 6530-6537

基于多目标遗传局部搜索算法的航空导航台频率指配

全屏

徐亚军, 郝博扬^*, 高田露, 张强, 鲁合德, 曾葆鸿

作者信息

中国民用航空飞行学院空中交通管理学院, 德阳 618307

徐亚军(1970—),女,汉族,四川成都人,硕士,教授。研究方向:航空电子、航空通信/导航。E-mail:genius98@126.com。

通讯作者:

* 郝博扬(2001—),男,汉族,河北保定人,硕士研究生。研究方向:民航导航台频率指配。E-mail:13733392915@163.com。

Frequency Assignment of Air Navigation Station Based on Multi-objective Genetic Local Search Algorithm

Ya-jun XU, Bo-yang HAO^*, Tian-lu GAO, Qiang ZHANG, He-de LU, Bao-hong ZENG

Affiliations

College of Air Traffic Management, Civil Aviation Flight University of China, Deyang 618307, China

出版时间: 2025-05-28 doi: 10.12404/j.issn.1671-1815.2405282

文章导航

摘要

收起

随着运输航空和通用航空的快速发展,航空导航台站的频率指配问题变得越来越重要。首先提出了目前单个航空导航台站频率指配的一般算法。然后针对多个航空导航台频率率指配问题,建立了民航导航台频率指配模型。最后根据传统多目标遗传算法所存在的收敛速度慢,易陷入局部最优解等缺陷,提出了优化权重分配的多目标遗传算法和基于多目标遗传局部搜索算法来解决航空导航台频率指配问题。该问题涉及多个目标,包括最小化频率干扰和最小使用频率个数指配。仿真结果表明,所提出的多目标遗传局部搜索算法能够有效地解决航空导航台频率指配问题,与传统多目标遗传算法和优化权重分配的多目标遗传算法相比,本算法在解的质量、收敛速度和稳定性方面都有显著提升。

关键词

多目标遗传算法 / 局部搜索 / 航空导航台 / 频率指配 / 禁忌搜索算法

Abstract

收起

With the rapid advancement of air transport aviation and general aviation, the frequency assignment of air navigation stations has become increasingly crucial. A comprehensive algorithm was presented for assigning frequencies to individual air navigation stations. Subsequently, in order to address the issue of frequency assignment for multiple aviation navigation stations, a model was established specifically for civil aviation navigation stations. Finally, considering the limitations of traditional multi-objective genetic algorithms such as slow convergence speed and susceptibility to local optimal solutions, a multi-objective genetic algorithm along with a multi-objective genetic local search algorithm based on optimal weight allocation was proposed to effectively solve the frequency assignment problem faced by aviation navigation stations. The problem encompasses several objectives including minimizing frequency interference and utilizing the minimum number of frequencies required. Simulation results demonstrate that our proposed multi-objective genetic local search algorithm successfully resolves the frequency assignment problem encountered by air navigation stations. In comparison with traditional multi-objective genetic algorithms and those incorporating optimized weight allocation, our proposed algorithm significantly enhances solution quality, convergence speed, and stability.

Key words

multi-objective genetic algorithm / local search / aeronautical navigation station / frequency assignment / tabu search algorithm

引用本文

徐亚军, 郝博扬, 高田露, 张强, 鲁合德, 曾葆鸿. 基于多目标遗传局部搜索算法的航空导航台频率指配. 科学技术与工程, 2025 , 25 (15) : 6530 -6537 . DOI: 10.12404/j.issn.1671-1815.2405282

Ya-jun XU, Bo-yang HAO, Tian-lu GAO, Qiang ZHANG, He-de LU, Bao-hong ZENG. Frequency Assignment of Air Navigation Station Based on Multi-objective Genetic Local Search Algorithm[J]. Science Technology and Engineering, 2025 , 25 (15) : 6530 -6537 . DOI: 10.12404/j.issn.1671-1815.2405282

正文

收起

航空无线电导航是国际民航组织空中航行系统的重要组成部分,为航空器提供飞行引导信息,使航空器可以安全准确地沿选定航线、准时到达目的地。随着运输航空和通用航空的快速发展,导航频率的需求也在不断增加,导航设备频率的指配日益困难,成为国际民航无线电管理遇到的首要问题,如何提高频率利用率、加强频率资源的管理和指配,是国际民航无线电管理急需解决的问题。

根据频率指配策略的不同,频率指配问题(frequency assignment problem,FAP)通常被划分为静态频率指配问题和动态频率指配问题^[1]。静态频率指配问题是一种在特定时间和空间内,将有限的频率资源预先指配给不同的无线电台站,且这些指配的频率在一段时间内保持不变的频率管理策略。这种指配方式适用于对频率指配变化需求不高的场景。动态频率指配问题是指在无线电通信系统中,根据实际通信需求和电磁环境的实时变化,动态地调整和优化频率资源的指配方式,这种指配方式适用于通信需求和电磁威胁动态变化的环境。

尽管频率指配在多个领域中得到了广泛的研究和应用,且现有的研究大多集中在军事^[1]、移动通信、广播电台等领域,而对于民用航空导航台的频率管理,尤其是在频率资源有限和频率干扰日益严重的背景下,相关的研究相对较少。

对于民用航空导航台频率指配而言,由于相对稳定的电磁环境,采用静态频率指配的方式。因此,针对上述无线电台频率指配提出的问题及指配的技术方法,首先总结民航导航台频率指配的约束条件,以最小干扰频率指配和最小使用频率个数指配为目标,提出指配准则,然后介绍使用传统多目标遗传算法的航空导航台频率指配问题,并根据传统多目标遗传算法存在的问题进一步优化并提出多目标遗传局部搜索算法。最后仿真实验结果表明,多目标遗传局部搜索算法在解决大量导航台站频率指配问题中相较于传统多目标频率指配算法具有更好的稳定性和收敛速度。

1 频率指配模型

收起

民用航空领域中,无线电导航系统主要包括仪表着陆系统(instrument landing system,ILS)、甚高频全向信标(very high frequency omnidirectional range,VOR)以及测距仪(distance measuring equipment,DME)等。在这些系统中,ILS的两个主要组成部分——航向信标(localizer,LOC)和下滑信标(glide slope,GS)分别使用甚高频(108.10~111.95 MHz)和特高频(329.15~335 MHz)频段。与此同时,VOR系统同样采用甚高频进行工作,而DME则使用L频段(962~1 213 MHz)进行信号传输^[2]。

根据国际电信联盟的国家频谱管理手册^[3]可知促进频率调配的技术方法包括:频率间隔和空间间隔,且适用于中国目前无线电台频率指配的一般程序如图1所示。

由图1可知该一般算法不利于大规模的台站频率指配,指配效率低,且频率利用率也有待提高。因此,针对此问题建立了如下频率指配模型。

1.1 干扰约束

频率指配问题中的干扰约束一般分为同频干扰约束、邻频干扰约束和互调干扰约束,而互调干扰中通常考虑的是三阶互调。由于考虑该算法的实用性,在本文的干扰约束中,不仅需要考虑拟建导航台站与已建导航台站之间的干扰约束,还需要考虑拟建导航台站之间的干扰约束,同时还需要考虑VOR、LOC与DME之间的频率配对干扰约束,在这里需要注意的是无论拟建VOR或LOC是否需要DME台站,都要考虑其配对问题。本节根据美国联邦航空管理局(Federal Aviation Administration,FAA) 的频谱管理规范^[4]总结出干扰约束条件,并计算出每一类型干扰的总干扰数。

1.1.1 同频干扰约束

同频约束主要是指在无线电台中,为了避免不同发射器之间发生干扰,对同一频率的使用进行限制。美国联邦航空管理局(FAA) 的频谱管理规范的附录3给出了两个同频VOR或LOC之间根据功率差的最小保护距离D₁,以及与之配对的两个DME台站之间的最小保护距离D₂。(这里的DME台站第一邻频指的是DME的应答频率)当两个台站的地理间隔小于最小保护距离间隔时,则认为两个台站之间可能存在干扰,具体干扰数的计算如下。

(1)VOR或LOC台站之间的同频干扰数计算:

(1)C₁=

1, f i 与 f j 同 频 且 地 理 间 隔 小 于 D 1 0, 其 他

式(1)中:f_i、f_j为不同的VOR台站(或LOC台站)的频率。包括拟建台站指配的频率和已建台站正在使用的频率。当存在干扰时则C₁=1,否则C₁=0。

(2)配对DME台站之间干扰数计算:

(2)C₂=

1, f i 与 f j 同 频 且 地 理 间 隔 小 于 D 2 0, 其 他

式(2)中:f_i、f_j为与不同的VOR台站(或LOC台站)配对的DME应答频率。包括拟建台站指配的频率和已建台站正在使用的频率。当存在干扰时则C₂=1,否则C₂=0。

1.1.2 邻频干扰约束

邻频约束主要是指为了避免相邻或邻近信道信号之间产生的相互干扰而设定的约束条件。

在民航VOR导航台频率指配过程中需要考虑的邻频干扰有:①两个VOR台站的第一邻频和第二邻频干扰;②VOR台站与LOC的第一邻频干扰。

LOC导航台频率指配过程中需要考虑的邻频干扰有:①两个LOC台站的第一邻频干扰;②VOR台站与LOC的第一邻频干扰。

美国联邦航空管理局(FAA) 的频谱管理规范的附录3给出了台站之间根据功率差的最小保护距离:①两个第一邻频VOR台站(或两个第一邻频LOC台站)之间的最小保护距离D₃;②两个第二邻频VOR台站(或两个第二邻频LOC台站)之间的最小保护距离D₄;③VOR台站与LOC台站之间第一邻频的最小保护距离D₅;④与VOR(或LOC)配对的DME台站第一邻频的最小保护距离D₆(这里的DME台站第一邻频指的是DME的应答频率)。与上述同理,当两个台站的地理间隔小于最小保护距离间隔时,则认为两个台站之间可能存在干扰,具体干扰数的计算如下:

(1)VOR台站(或LOC)之间的邻频干扰数计算:

(3)C₃=

2, f i 与 f j 为 第 一 邻 频 且 地 理 间 隔 小 于 D 3 0, 其 他

式(3)中:f_i、f_j为不同的VOR台站(或LOC台站)的频率。包括拟建台站指配的频率和已建台站正在使用的频率。当存在干扰时则C₃=2,否则C₃=0。

(4)C₄=

2, f i 与 f j 为 第 二 邻 频 且 地 理 间 隔 小 于 D 4 0, 其 他

式(4)中:f_i、f_j为拟建和已建VOR台站(或LOC台站)的频率。包括拟建台站指配的频率和已建台站正在使用的频率。当存在干扰时则C₄=2,否则C₄=0。

(2)VOR与LOC台站之间邻频干扰数计算:

(5)C₅=

2, f v 与 f i 为 第 一 邻 频 且 地 理 间 隔 小 于 D 5 0, 其 他

式(5)中:f_v为拟建VOR台站指配的频率;f_i为已建LOC台站(或f_i为拟建LOC台站指配的频率;f_v为已建VOR台站正在使用的频率)当存在干扰时则C₅=2,否则C₅=0。

(3)配对DME台站之间邻频干扰数计算:

(6)C₆=

2, f i 与 f j 为 第 一 邻 频 且 地 理 间 隔 小 于 D 6 0, 其 他

式(6)中:f_i、f_j为与不同的VOR台站(或LOC台站)配对的DME应答频率。包括拟建台站指配的频率和已建台站正在使用的频率。当存在干扰时则C₆=2,否则C₆=0。

1.1.3 三阶互调干扰约束

互调干扰是指配给某两个台站的频率f_i和f_j乃经过非线性作用后出现的新频率f_k,与其台站本身或相邻台站频率相同时时产生的干扰。可以分为阶互调干扰、三阶互调干扰等等,其中三阶互调干扰是最严重的互调干扰^[5]。根据美国联邦航空管理局(FAA) 的频谱管理规范附录3可知两个VOR台站之间最大的保护距离为406海里,以及两个LOC台站之间的最大保护距离为157海里,所以在每个拟建VOR台站406海里范围内检查三阶互调干扰或在每个拟建LOC台站157海里范围内检查三阶互调干扰。具体干扰数计算公式如下:

(1)三阶Ⅰ型互调:

(7)C₇=

3, 2 f i + f j = f k 0, 其 他

式(7)中:f_i、f_j、f_k为每个拟建VOR台站406海里范围内(或f_i、f_j、f_k为每个拟建LOC台站157海里范围内)的所有VOR、LOC台站频率。当存在干扰时则C₇=3,否则C₇=0。

(2)三阶Ⅱ型互调:

(8)C₈=

3, 2 f i + f j - f m = f k 0, 其 他

式(8)中:f_i、f_j、f_m、f_k为每个拟建VOR台站406海里范围内(或f_i、f_j、f_m、f_k为每个拟建LOC台站157海里范围内)的所有VOR、LOC台站频率。当存在干扰时则C₈=3,否则C₈=0。

1.1.4 GS台站之间的干扰约束

尽管LOC台站的保护范围已经避免了GS台站之间的干扰,但在两个LOC台站最大保护范围157海里之内,仍应避免相邻频率的GS台站,从而进一步避免GS台站之间发生干扰。

(9)C₉=

3, f i, g - f v, g ≤ 150 k H z 0, 其 他

式(9)中:f_i_,g和f_v_,g分别为拟建LOC台站第i个LOC配对的GS频率和与第v个LOC配对的GS频率。当存在干扰时则C₉=3,否则C₉=0。

综上所述,总干扰数为

(10)

I = C 1 + C 2 + C 3 + C 4 + C 5 + C 6 + C 7 + C 8, 拟 建 V O R 台 站 I = C 1 + C 2 + C 3 + C 5 + C 6 + C 7 + C 8 + C 9, 拟 建 I L S 台 站

1.2 频率复用

频率复用可以有效地提高频率资源的利用率,为了实现最小使用频率个数这一指配目标,定义频率复用因子^[6]为

(11)S_t=

∑ p = 1 q (N p, t) 2

式(11)中:t为台站类型;N_p_,_t为该类台站的第p个已用频率的复用次数;q为该类台站已用频点的个数。S_t越大,表明使用的频率个数越少。

2 多目标遗传局部搜索算法

收起

遗传算法是一种智能优化技术,它模仿自然界生物的进化和遗传机制,通过计算机实现。这一算法遵循“适者生存,优胜劣汰”的自然法则^[7],确保那些适应环境的个体得以保留,而不适宜的个体则逐渐被淘汰。遗传算法的灵感来源于两位科学巨匠的理论:英国生物学家查尔斯·达尔文的进化论,以及奥地利遗传学家格雷戈尔·孟德尔的遗传学研究。这些理论为遗传算法提供了生物学和遗传学的基础,使其成为一种强大的问题求解工具。

2.1 群体初始化

在论述算法是以拟建VOR台站为例,拟建ILS台站同理。遗传算法中通常有符号编码和二进制编码两种方式^[8]。

符号编码:在符号编码中,染色体的每个基因对应一个具体的值,这些值直接对应于问题域中的实体或参数。在导航台频率指配问题中,每个基因可以代表一个特定的频率值。

二进制编码:二进制编码使用二进制数来表示每个基因,这种方法易于实现,并且可以方便地进行交叉和变异操作,但可能需要更多的二进制位来精确表示问题域中的值。

本文中选择使用符号编码方式,这种编码方式更适合于处理那些基因值直接对应问题域参数的情况。符号编码允许算法直接操作问题域中的实体,从而可能更容易地找到问题的可行解,本文中每个染色体代表对多个拟建台站的解,每个基因代表一个具体的频率值。相较于传统多目标遗传算法随机生成初始化种群的方式,本文中采用启发式方法,即利用先验知识来指导种群的初始化过程。这种启发式初始化方法可以帮助算法更快地接近最优解。由于最小使用频率个数是问题的一个指配目标,启发式初始化将从已建的VOR台站的已使用频率中选择频率值,以构建初始种群。

2.2 适应度函数

通过上述对该问题频率指配模型的描述,适应度函数的设计需要同时考虑到最小干扰指配和最小使用频率个数指配的多目标要求,即寻求最小干扰数和最大频率复用因子。这种多目标适应度函数不仅评估指配频点时违反的干扰约束和频率复用因子,而且还试图最大化适应度函数值,以指导算法寻找最优解。

(1)多目标适应度函数的设计:由式(10)和式(11)可知该适应度函数为

(12)F_i=W_a

1 A + I

+W_bS_t

式(12)中:i为个体,为了防止出现I=0时导致公式无效的情况,设置1个大于0的数A;W_a和W_b为两个目标函数所占的权重且W_a+W_b=1,W_a、W_b>0。

(2)权重分配的动态调整:由于各个地区导航台建设密度不同,导致各个地区频率拥挤程度不同,所以在对个体进行适应度评估时,权重的分配需要根据不同地区的情况进行指配。在传统多目标函数中,不同目标之间的权值分配往往是固定的^[9],这使得算法在进行迭代时搜索方向是不会发生改变的如图2所示。

图2中W_a、W_b、W_c表示三个不同的权重固定值,例如,按照W_b=(0.5,0.5)的权重来进行搜索,则B、C这两个最优解很容易被找到但A、D这两个解需通过改变权重分配进而改变搜索方向来找到,所以本文中权重使用随机分配,试图在迭代过程中改变搜索方向找到适合不同地区的最优解,增加了算法的实用性。

2.3 选择操作

采用的选择方式为轮盘赌选择方式,这种选择方法的名称来源于轮盘赌游戏,其中每个个体被指配一个概率,这个概率与其适应度成比例。适应度越高的个体,被选中的概率越大。具体步骤如下:

(1)计算总适应度:计算种群中所有个体的适应度总和并将其作为轮盘赌选择的基准,即

(13)E=

∑ i = 1 q

F_i

式(13)中:q代表总个体数。

(2)确定选择概率:对于每个个体i,被选中的概率P_i为

(14)P_i=

F i E

(3)选择个体:生成一个在 (0, 1] 范围内的随机数。根据生成的随机数,按照个体的适应度比例在轮盘上“旋转”,直到随机数落在某个个体的适应度范围内,该个体即被选中。重复上述过程,直到选出所需数量的个体用于繁殖,本文中选出和种群规模M相同的数量。

2.4 交叉操作

在遗传算法中交叉操作,是一种用于产生新一代个体的操作。采用单点交叉方式,它具有简单易实现,能够有效地重组父代的遗传信息,创造出具有新特征的后代的优点。交叉概率P_c的经验取值范围为0.4~0.99。具体步骤如下:

(1)确定交叉点: 在父代染色体上随机选择一个交叉点。这个点是染色体上的一个基因。

(2)执行交叉: 在选定的交叉点处,交换切割点的基因片段。这样,每个父代染色体的一部分基因被传递给后代,而另一部分则来自另一个父代染色体。通过上述交叉操作,生成两个新的后代个体。这些后代个体结合了两个父代的部分遗传特征,可能具有比父代更优秀的适应度。

(3)交叉概率P_c的作用:交叉概率P_c是决定交叉操作是否执行的一个关键参数。它决定了在遗传算法的每次迭代中,任意两个父代个体进行交叉的可能性。较高的P_c值增加了交叉操作的频率,有助于快速搜索解空间;而较低的P_c值则减少了交叉操作,合适的P_c值有助于保持种群的多样性,避免过早收敛。

2.5 变异操作

变异是遗传算法中的一个关键操作,其本身是一种局部随机搜索^[10],在遗传算法的迭代过程中,由于选择和交叉操作,可能会导致某些基因频率的集中。变异有助于引入新的基因,从而维持种群的遗传多样性^[11]。适当的变异可以防止算法过早地收敛到次优解,确保算法有足够的机会探索全局解空间。变异概率P_m 的选取需要慎重考虑。如果变异概率设置得过高,虽然能够产生大量的新个体,但同时也可能破坏许多优秀的遗传模式,导致遗传算法的性能降低。相反,如果变异概率过低,则会减弱算法通过变异产生新解的能力,以及避免算法过早收敛到局部最优解的能力。变异概率P_m的经验取值范围为0.01~0.1。

本文中问题的变异策略如下:

(1)基因来源的限制:变异时随机选择的新基因必须来自文献[12]中给出的民航导航台频率库。这样可以保证变异后的解不仅在遗传上是多样的,而且在实际应用中也是可行的。

(2)频率范围的遵守:在变异过程中,必须确保新的基因不会使整体频率超出导航台的使用范围,从而避免产生无效解。

(3)变异策略的定制:随机选取染色体中任意一个基因,将民航导航台频率库中选取的基因对其进行替换。

2.6 局部搜索

遗传算法在迭代过程中可能会过早地收敛到局部最优解^[13],而找不到全局最优解,搜索效率可能降低,为了提升遗传算法在局部搜索方面的效率,本研究将禁忌搜索算法融合在变异操作之后^[14](图3)。为了减少无效搜索和循环,促进算法向全局最优解的收敛,引入一个禁忌列表,该列表用于记录并避免重复探索已经访问过的解(图4)。这种方法有助于实现更有效的全局优化过程。主要步骤如下:

(1)初始化阶段。禁忌搜索算法的种群初始化是选取变异操作后种群中适应度最优的个体作为初始解的。初始化禁忌列表,设置禁忌表的长度为t=4,设置迭代次数,当迭代达到50次时,终止循环。

(2)迭代阶段。在每次迭代中,首先检查是否满足结束条件。如果满足,则输出当前找到的最佳解决方案并结束搜索。如果不满足结束条件,继续进行迭代。

(3)邻域搜索。基于当前解的特定领域特征,生成一系列邻域解,本文中邻域解是通过在文献[12]中随机选取的多个频率,将其频率随机替换初始解中的频率,而生成的多个邻域解。

(4)候选解的筛选与更新。从筛选后的邻域解中,选择适应度值最优的解作为候选解。检查候选解是否在禁忌表中。如果候选解在禁忌表中,但满足解禁条件^[15],则忽略禁忌限制,允许候选解作为当前解。这里解禁条件是指候选解优于当前最优解。若候选解在禁忌表中且不满足解禁条件,则重新选择其他候选解。若候选解不在禁忌表中,则将候选解作为当前解。如果候选解的目标函数值优于当前最优解,则更新最优解为候选解。

(5)终止准则检查。在每次迭代结束时,检查是否满足终止准则。如果满足,则停止搜索并输出最优解。

如果禁忌搜索找到了适应度更高的个体,那么这个个体将替代变异后的原始个体成为新的当前最优解。如果没有找到更高的适应度个体,则保持原始个体不变^[16]。

3 仿真结果与分析

收起

仿真的参数均为虚拟参数,台站的信息如表1~3所示。

图5所示为各台站距离信息,距离计算采用WGS84 模型^[17]。

针对本文中为民航导航台指配频率的问题,采用三种遗传算法进行计算工作,并将计算结果进行比对。具体介绍如下:

传统多目标遗传算法:传统多目标遗传算法指没有进行任何优化的多目标遗传算法,如启发式初始化、动态权值分配、局部搜索等。使用该算法作为基准,用于评价没有针对性优化的情形下对解决本文问题的基础性能。

优化权重分配的多目标遗传算法:该算法对传统多目标遗传算法进行了针对性优化,根据各地区频率拥挤程度的不同,将适应度函数中的固定权值分配改为动态权值分配。旨在与传统多目标遗传算法对比,探究动态权值分配对频率指配结果的影响。

多目标遗传局部搜索算法:该算法对优化权重分配的多目标遗传算法进行了进一步优化,即根据频率指配目标进行启发式种群初始化,并在变异操作后进行局部禁忌搜索,本文采用多目标遗传局部搜索算法,并将该算法与优化权重分配的多目标遗传算法进行对比,探究启发式初始化和局部搜索对频率指配结果的影响。

为验证所提算法的性能,在Windows11操作系统上,使用Matlab2020软件对改进前后的算法进行仿真。假设某区域有4个已建LOC台站和19个已建VOR台站,现需要拟建4个VOR台站,具体信息如表1~3所示。除了传统多目标遗传算法中W_a=0.8、W_b=0.2,三种算法其余参数设置相同。种群规模M=20,交叉概率P_c=0.8,变异概率P_m=0.09,适应度函数中A=0.014,当遗传算法迭代到200次时停止迭代。三种算法的性能比较如图6和表4所示。

由图6和表4可知多目标遗产局部搜索算法在收敛速度以及频率指配性能方面更有利于跳出局部最优解找到全局最优解。并且可以根据不通过地区的指配需要,选择合适的最优解。

4 结论

收起

为解决多个民航导航台频率指配问题,首先建立了根据功率查VOR台站和ILS台站频率指配模型,然后针对不同环境下指配需求的不同对传统多目标遗传算法进行权值分配优化,又由于其易陷入局部最优且收敛速度慢的缺点,进一步优化,提出多目标遗传局部搜索算法,最后对三种算法进行仿真实验。结果表明,多目标遗传局部搜索算法能更好地解决民航导航台频率指配问题。

基金

收起

中央高校基本科研业务费项目(ZHMH2022-007)
四川省科技计划重点研发项目(2022YFG0353)
中央高校基本科研业务费专项(ZJ2023-007)

参考文献

收起

文献

收起

参考文献引证文献

排序方式：

[1]

高航, 查淞, 黄纪军, 等. 战场频率指配问题研究综述及展望[J]. 电波科学学报, 2024, 39(3): 413-431.

Gao

Hang

, Zha

Song

, Huang

Jijun

, et al. Review and prospect of battlefield frequency assignment[J]. Journal of Radio Science, 2024, 39(3): 413-431.

[2]

International Civil Aviation Organization. ICAO handbook on radio frequency spectrum requirements for civil aviation[S]. Montreal, Canada: International Civil Aviation Organization, 2013: 1-7.

[3]

International Telecommunication Union. Handbook on national spectrum management[S]. Hasan Sharif, United Arab Emirates: International Telecommunication Union, 2015: 76-84.

[4]

Department of Transportaion Federal Aviation Administration. 32b spectrum management regulations and procedures manual: FAA order 6050[S]. Montreal: International Civil Aviation Organization, 2008.

[5]

佈仁巴图. 基于遗传算法的固定频率指配问题研究[D]. 呼和浩特: 内蒙古大学, 2014.

Renbatu

. Research on fixed frequency assignment based on genetic algorithm[D]. Hohhot: Inner Mongolia University, 2014.

[6]

李锐, 周自力, 刘松淘, 等. 一种提高频谱利用率的航空导航台站频率指配算法[J]. 电讯技术, 2016, 56(12): 1359-1364.

Rui

, Zhou

Zili

, Liu

Songtao

, et al. A frequency assignment algorithm for aeronautical navigation stations to improve Spectrum utilization[J]. Telecommunication Technology, 2016, 56(12): 1359-1364.

[7]

郭缙烨, 胡军红, 傅文陵, 等. 基于累积前景理论的共享停车泊位匹配模型[J]. 科学技术与工程, 2024, 24(28): 12357-12365.

Guo

Jinye

, Hu

Junhong

, Fu

Wenling

, et al. Shared parking space matching model based on cumulative prospect theory[J]. Science Technology and Engineering, 2024, 24(28): 12357-12365.

[8]

陈浩. 遗传算法在频率指配问题中的应用研究[D]. 北京: 北京交通大学, 2009: 5-37.

Chen

Hao

. Application research of genetic algorithm in frequency assignment problem[D]. Beijing: Beijing Jiaotong University, 2009: 5-37.

[9]

王玥玥, 魏延辉, 马天宇, 等. 基于动态权值分配的登乘系统运动规划方法[J]. 华中科技大学学报(自然科学版), 2023, 51(8): 102-108.

Wang

Yueyue

, Wei

Yanhui

, Ma

Tianyu

, et al. Embarkation system based on dynamic weighting allocation motion planning method[J]. Journal of Huazhong University of Science and Technology (Natural Science Edition), 2023, 51(8): 102-108.

[10]

屈文涛, 谢韩彧, 刘鑫, 等. 基于改进遗传算法的油气管道无人机航迹规划[J]. 科学技术与工程, 2024, 24(27): 11901-11908.

Wentao

, Xie

Hanyu

, Liu

Xin

, et al. Flight path planning of oil and gas pipeline UAV based on improved genetic algorithm[J]. Science Technology and Engineering, 2024, 24(27): 11901-11908.

[11]

倪超, 胡钟骏, 霍忻, 等. 基于“分类-调度”优化的应急物资动态调度-重调度算法[J]. 科学技术与工程, 2024, 24(24): 10356-10361.

Chao

, Hu

Zhongjun

, Huo

Xin

, et al. Dynamic scheduling and rescheduling algorithm of emergency materials based on “classification-scheduling” optimization[J]. Science Technology and Engineering, 2024, 24(24): 10356-10361.

[12]

International Civil Aviation Organization. Aeroautical tele-communication Volume V[S]. Montreal, Canada: International CivilAviation Organization, 2013: 4-12.

[13]

史郑延慧, 何刚. 基于遗传-蚁群优化算法的QoS组播路由算法设计[J]. 科学技术与工程, 2024, 24(11): 4626-4632.

Shi

Zhengyanhui

, He

Gang

. QoS multicast routing algorithm design based on gene-antcolony optimization algorithm[J]. Science Technology and Engineering, 2024, 24(11): 4626-4632.

[14]

周航, 秦实宏, 方泾丞. 基于混合遗传禁忌搜索算法的多机器人任务指配[J]. 自动化与仪表, 2023, 38(11): 35-39.

Zhou

Hang

, Qin

Shihong

, Fang

Jingcheng

. Multi-robot task assignment based on hybrid genetic tabu search algorithm[J]. Automation & Instrumentation, 2023, 38(11): 35-39.

[15]

Akbar

M D

, Aurachmana

. Hybrid genetic-tabu search algorithm to optimize the route for capacitated vehicle routing problem with time window[J]. International Journal of Industrial Optimization, 2020, 1(1): 15-28.

[16]

刘利甲. 一类并行机实时调度问题的混合遗传算法研究[J]. 工业控制计算机, 2019, 32(7): 95-98.

Liu

Lijia

. Research on hybrid genetic algorithm for real-time scheduling of parallel machines[J]. Industrial Control Computers, 2019, 32(7): 95-98.

[17]

黎珍惜, 黎家勋. 基于经纬度快速计算两点间距离及测量误差[J]. 测绘与空间地理信息, 2013, 36(11): 235-237.

Zhenxi

, Li

Jiaxun

. Fast calculation of distance between two points and measurement error based on latitude and longitude[J]. Surveying, Mapping and Spatial Geographic Information, 2013, 36(11): 235-237.

2025年第25卷第15期

PDF下载

274

引用本文

BibTeX

文章信息

doi: 10.12404/j.issn.1671-1815.2405282

接收时间：2024-07-13
首发时间：2025-07-09
出版时间：2025-05-28

补充材料

相关文章

文章信息

作者

出版历史

收稿日期：2024-07-13
修回日期：2024-11-24

基金

中央高校基本科研业务费项目(ZHMH2022-007)

四川省科技计划重点研发项目(2022YFG0353)

中央高校基本科研业务费专项(ZJ2023-007)

作者信息

中国民用航空飞行学院空中交通管理学院, 德阳 618307

通讯作者:

* 郝博扬(2001—),男,汉族,河北保定人,硕士研究生。研究方向:民航导航台频率指配。E-mail:13733392915@163.com。

参考文献

分享链接

https://castjournals.cast.org.cn/joweb/kxjsygc/CN/10.12404/j.issn.1671-1815.2405282

分享至

全文二维码

扫描看全文

引用本文

BibTeX

本文的引用情况

2种不同金属材料的力学参数

科 Family	属数 Number of genus	种数 Number of species	占总种数比例 Percentage of total species (%)	属 Genus	种数 Number of species	占总种数比例 Percentage of total species (%)
鹅膏菌科Amanitaceae	2	11	5.26	鹅膏菌属 Amanita	10	4.78
小菇科 Mycenaceae	2	12	5.74	丝盖伞属 Inocybe	5	2.39
多孔菌科 Polyporaceae	8	14	6.70	蜡蘑属 Laccaria	5	2.39
红菇科 Russulaceae	3	23	11.00	小皮伞属 Marasmius	6	2.87
				小菇属 Mycena	11	5.26
				光柄菇属 Pluteus	5	2.39
				红菇属 Russula	17	8.13
				栓菌属 Trametes	5	2.39

关闭全屏

BibTeX
EndNote
RefWorks
TxT

ILS 台站	LOC 纬度/ °N	LOC 经度/ °E	LOC频率/ MHz	GS频率/ MHz	DME频率/ MHz
ILS-1	28.45	104.35	108.30	334.10	1 044
ILS-2	31.10	104.21	111.15	331.55	1 072
ILS-3	29.34	106.32	111.55	332.75	1 076
ILS-4	25.31	103.46	108.90	329.30	1 050
ILS-5	34.22	108.42	108.30	334.10	1 044

ILS
台站

LOC 纬度/
°N

LOC 经度/
°E

LOC频率/
MHz

GS频率/
MHz

DME频率/
MHz

ILS-1

28.45

104.35

108.30

334.10

1 044

ILS-2

31.10

104.21

111.15

331.55

1 072

ILS-3

29.34

106.32

111.55

332.75

1 076

ILS-4

25.31

103.46

108.90

329.30

1 050

ILS-5

34.22

108.42

108.30

334.10

1 044

VOR台站	VOR纬度/ °N	VOR经度/ °E	VOR频率/ MHz	DME频率/ MHz
VOR-1	24.26	118.07	108.20	1 043
VOR-2	25.05	102.41	108.40	1 045
VOR-3	25.33	100.12	109.40	1 055
VOR-4	26.03	119.17	109.65	1 057
VOR-5	26.35	101.44	109.80	1 059
VOR-6	26.34	106.41	113.20	1 103
VOR-7	26.34	104.51	109.65	1 057
VOR-8	27.41	106.54	112.60	1 097
VOR-9	28.55	105.23	108.40	1 045
VOR-10	29.17	106.17	109.40	1 055
VOR-11	29.34	106.32	111.20	1 073
VOR-12	29.60	102.60	110.80	1 069
VOR-13	30.41	104.05	108.40	1 045
VOR-14	31.51	117.18	109.80	1 059
VOR-15	34.21	107.10	110.85	1 069
VOR-16	36.03	103.52	108.60	1 047
VOR-17	36.37	101.49	108.40	1 045
VOR-18	36.41	117.01	108.40	1 045
VOR-19	39.56	116.25	108.20	1 043

VOR台站

VOR纬度/
°N

VOR经度/
°E

VOR频率/
MHz

DME频率/
MHz

VOR-1

24.26

118.07

108.20

1 043

VOR-2

25.05

102.41

108.40

1 045

VOR-3

25.33

100.12

109.40

1 055

VOR-4

26.03

119.17

109.65

1 057

VOR-5

26.35

101.44

109.80

1 059

VOR-6

26.34

106.41

113.20

1 103

VOR-7

26.34

104.51

109.65

1 057

VOR-8

27.41

106.54

112.60

1 097

VOR-9

28.55

105.23

108.40

1 045

VOR-10

29.17

106.17

109.40

1 055

VOR-11

29.34

106.32

111.20

1 073

VOR-12

29.60

102.60

110.80

1 069

VOR-13

30.41

104.05

108.40

1 045

VOR-14

31.51

117.18

109.80

1 059

VOR-15

34.21

107.10

110.85

1 069

VOR-16

36.03

103.52

108.60

1 047

VOR-17

36.37

101.49

108.40

1 045

VOR-18

36.41

117.01

108.40

1 045

VOR-19

39.56

116.25

108.20

1 043

拟建VOR台站	VOR纬度/°N	VOR经度/°E
ProVOR-1	28.11	112.60
ProVOR-2	30.36	114.18
ProVOR-3	21.38	108.21
ProVOR-4	22.49	108.20

拟建VOR台站

VOR纬度/°N

VOR经度/°E

ProVOR-1

28.11

112.60

ProVOR-2

30.36

114.18

ProVOR-3

21.38

108.21

ProVOR-4

22.49

108.20

算法	最小干扰数	最大频率复用因子
传统多目标遗传算法	2	75
优化权重指配的多目标遗传算法	1	77
多目标遗传局部搜索算法	0	91

算法

最小干扰数

最大频率复用因子

传统多目标遗传算法

优化权重指配的多目标遗传算法

多目标遗传局部搜索算法