基于混合遗传算法的1553B消息传输优化

赵昶宇

（天津津航计算技术研究所，天津 300308）

基于混合遗传算法的1553B消息传输优化

赵昶宇

（天津津航计算技术研究所，天津 300308）

为了提高1553B总线消息传输的实时性，降低总线的通信延迟率，提出了一种改进遗传算法的1553B总线消息传输优化算法。该算法先通过排队论建立1553B总线消息调度数学模型，接着引入遗传算法快速找到1553B总线消息调度可行解，然后将遗传算法找到的可行解转换成蚁群优化算法初始信息素，最后利用蚁群算法的局部寻优和正反馈机制得到1553B总线消息调度最优解。仿真实验结果表明，利用改进后的遗传算法优化1553B总线消息传输，能够在满足每条消息最大延迟时间要求和通讯实时性的前提下，提高总线利用率，有效缓解总线消息拥塞和饱和的情况，解决了总线负载均衡的难题，具有较好的处理异步消息的能力。

遗传算法；蚁群算法；总线消息传输；数学模型

由于武器装备系统对实时性和可靠性的要求很高，所以必须保证1553B总线上消息传输的实时性。当1553B总线上需要处理不同长度、不同周期的多种消息时，并且存在异步消息需要处理时，系统的实时性一般很难保证。目前，比较常见的1553B总线消息优化算法有基于计算量向量算法、RMS调度算法、长释放时间间隔优先算法和HTSF算法等。在这些方法中，基于计算量向量算法和RMS调度算法都是基于静态负载均衡的，没有解决消息的动态负载均衡问题，当总线上有很多非周期性消息时，易导致总线堵塞或饱和；长释放时间间隔优先算法不能保证释放间隔比较小的消息或者突发消息能在截止期前完成调度；HTSF算法没有考虑同一时刻可能有多条消息同时到达的情况，而且算法执行效率比较低。为了避免出现1553B总线堵塞和饱和的情况，提高1553B总线的利用率，降低总线的平均延迟时间，均衡总线负载，本文提出了一种优化1553B总线消息传输的算法。

1 基于排队论建立1553B总线消息传输的数学模型

图1 M|M|1模型发生率图

1553B总线上消息的传输过程可以看作是一种单服务员单队列的排队系统。该模型为一个M|M|1排队模型，排队系统的模型发生率如图1所示，其中，圆圈中的数字代表系统的状态。在图1中，λ为消息的平均到达率，μ为总线的平均服务率，m为消息个数，因此，1/λ为消息的平均时间间隔，1/μ为消息的平均传输时间。

设Ek为排队系统在状态k处的概率，ρ为总线利用率，建立生灭过程的状态平衡方程，即：

如果系统内有k条消息，其中，k-1条消息在排队等候，则排队等候的消息平均数为：

消息传输花费的时间为：

消息排队等候所花费时间的平均值为：

1553B总线传输系统的平均延迟时间为消息传输时间和消息排队等候时间之和。对总线上非周期消息传输进行优化的目标是使平均延迟时间最小，并确定达到最优目标值的最优总线平均服务率μ*。

取目标函数z为消息传输时间与消息在系统中排队等候时间之和的期望值，即：

式（1）中：cs为当μ＝1时总线消息传输所耗费的时间；cw为每条消息在总线中排队等候所耗费的时间。

式（2）为1553B总线消息传输的数学模型。

2 基于遗传算法得到1553B总线消息调度可行解

2.1 染色体编码

设定消息个数为m，消息小周期个数为n，个体染色体上的每个基因位置编号代表消息编号，每个基因位用0～（m-1）之间的整数表示，代表某条消息所在的小周期编号。比如，m＝6，n＝4，染色体编码为（0，1，2，3，3，2），表示第1条消息分配到小周期1上，第2条消息分配到小周期2上，第3条和第6条消息分配到小周期3上，第4条和第5条消息分配到小周期4上。

2.2 确定初始种群

种群的初始化是遗传算法的关键，传统的遗传算法确定初始种群多半采取随机生成法形成染色体方案，以至于迭代开始就可能形成许多不可行的方案，要进行大量的计算后才能得到优化方案。这在很大程度上降低了算法的运算效率。本文改进经典遗传算法，改进后的初始种群的选择算法能有效抑制“早熟”现象，其全局搜索能力和搜索效果都有了明显的提高。改进后的初始种群的产生方式是：随机产生N个体，个体长度为Length，设x和y为2个个体，u是中群内的第1个个体，ν是与u进行相似度比较的个体，它们之间的相似度定义为sim（u，ν）＝1-dist（u，ν），dist（u，ν）是标准的海明距离函数。

通过比较个体相似度，要求规定能够入选初始个体相似度必须满足以下条件，即：

式（3）中：d为调节常数，用于控制期望的相似度。

2.3 适应度函数

适应度函数用于评价染色体的优劣，其函数值越大，表示染色体生存能力越强，对应的解最优。式（2）给出了1553B总线传输系统的平均延迟时间函数，因此，本文采用的适应度函数为：

2.4 交叉操作

常用的交叉方式有一点交叉、两点交叉、多点交叉和一致交叉等。

本文改进了遗传算法，采用多点位单基因交叉的方式，用父代最优解Tmax与子代染色体池交叉操作，该方法能避免算法过早地丧失进化能力，具体步骤如下：①在染色体池T中选择进行交叉操作的染色体Ti和最优染色体Tmax；②随机生成交叉片段和交叉区域；③将Ti的交叉区域加到Tmax前面，将Tmax的交叉区域加到Ti前面；④删除与交叉区域相同的基因，得到2个新的子代。

2.5 变异操作

在变异运算中，变异率通常取0.1，在单个染色体Ti＝（ti1，ti2…tim）上随机选择连续多个基因（m表示消息个数），对多个基因进行重新排列，实现染色体的变异。由于采用了最优个体Tmax保留的策略，所以，在变异运算中，可以加大在当前最优个体附近搜索的概率，不用担心破坏已经存在的优良染色体。

2.6 复制操作

基于适应度函数对染色体个体进行评价，将适应度较高的染色体直接复制到下一代染色体中。

2.7 选择操作

经过上述操作，得到新一代的染色体种群。基于目标函数评估得到的染色体种群，如果对当前调度方案不满意，则重复上述遗传操作过程。当染色体种群进化速率比较小时，终止遗传算法。

3 基于蚁群算法得到1553B总线消息调度最优解

4 结束语

本文利用混合遗传算法合理组织传输的1553B消息块，降低了总线的平均延迟率，使得总线负载达到均衡，并得到了最优的通信效率。

实验证明，在周期消息和非周期消息混合传输的情况下，文中所述算法具有实时性好、可靠性高、异步事件处理能力强等特点。

［1］刘桂山，胡军程.1553B总线信息流设计［J］.北京理工大学学报，2003，23（3）：301-304.

［2］陆传来.排队论［M］.北京：北京邮电大学出版社，2000：20-150.

［3］孙力娟，王汝传.基于蚁群算法和遗传算法融合的QoS组播路由问题求解［J］.电子学报，2006，34（8）：1391-1395.

〔编辑：白洁〕

TP18

A

10.15913/j.cnki.kjycx.2017.13.059

2095-6835（2017）13-0059-03