1.基于遗传算法的消息传递接口程序分支覆盖测试套件生成方法，其特征在于，该方法包括如下步骤：步骤1：记一个消息传递接口程序为P＝{p0,p1,...,pm-1}，其中，pi(i＝0,1,...,m-1)表示P中的第i个进程，m表示进程数。将用于收集覆盖信息的探针插入到进程pi的所有分支中，并基于这些探针，定义如式(1)所示的最小归一化分支距离。

上式中， 表示进程pi中第j个分支，T＝{t1,t2,...,tN}表示包含N个测试数据tk(k＝

1,2,...,N)的候选测试套件(即一个进化个体)，用于覆盖进程pi中所有分支，以及表示T覆盖 的最小分支距离。

步骤2：基于公式(1)，进程pi中的分支总数，以及候选测试套件T实际覆盖的进程pi中分支数，设计如公式(2)所示的目标函数，用于评价种群中个体的目标函数值。

上式中，Mi是指进程pi中所有分支总数， 是指以T执行程序时进程pi中被覆盖的分支i数，以及 为进程p的分支集合。

步骤3：使用遗传算法生成进化个体，并基于设计的目标函数，计算这些个体的目标函数值，以此引导后续种群按照如下操作进行交叉与变异。

交叉鉴于每一进化个体由N个测试数据组成，基于两个父进化个体P1与P2，这里给出生成两个后代O1和O2的步骤。生成介于[0,1]之间的伪随机数α，如果α小于交叉概率，那么执行以下操作：一方面，生成介于[0,1]之间的伪随机数λ，并将P1中前λ·N个测试数据，以及P2中最后(1-λ)·N个测试数据遗传给O1；另一方面，将P2中前λ·N个测试数据，以及P1中最后(1-λ)·N个测试数据遗传给O2。

变异针对进化个体包含的每一测试数据，生成介于[0,1]之间的伪随机数β，如果β小于变异概率，那么任选该测试数据的一个基因位，并反转该位值。