一种新的遗传算法交叉算子及其在GNSS星座选择中的应用

A Novel Crossover Operator of Genetic Algorithm and Its Application in Satellite Selection of GNSS

摘要:

针对全球导航卫星系统（GNSS）星座选择的需要，分析了多星座卫星导航定位系统选星问题的数学描述形式，根据选星问题的实质要求，将选星问题转换为单约束组合优化问题。而在采用遗传算法求解诸如选星求解类组合优化问题时，由于其对1基因（或0基因）的数量有特别的约束要求，已有的一些交叉算子不能满足该约束要求。针对基因数约束条件，提出了一种新的交叉算子——变异交叉，新的交叉算子仅以1基因或0基因为交换对象实现交叉操作来产生原始后代、以变异作为辅助方式来实现后代的合法化。实验结果表明，所提出的交叉算子能有效应用于遗传算法实现多星座卫星导航定位系统选星求解，且运算量较少，可以实现简单、快速求解，满足实时选星要求。

关键词:遗传算法;交叉算子;全球导航卫星系统;选星

Abstract:

In some combinatorial optimization problems, a specified number of the 0-gene or the 1-gene is one of the constrained conditions based on genetic algorithm (GA). And it is difficult to adapt the constrained demand of genes’ number for some existing crossover operators. A novel crossover operator, called mutation crossover (MX), is proposed for the demand of the genes’ number. In the new crossover operator, firstly, the initial offspring are generated only by interchanging 1-gene or 0-gene, and then, the legalize offspring, namely the offspring which meet the constrained condition, are obtained by the mode of mutation. The validity and efficiency of the new crossover operator are validated by the application of satellite selection of Global Navigation Satellite System (GNSS).

Key words:genetic algorithm (GA); crossover operator; GNSS; satellite selection