基于群搜索算法的虚拟企业伙伴选择问题

陈海华，邵亚丽，张莉敏，田小路

（广东理工学院，广东肇庆，526100）

1 群搜索解决伙伴选择问题

1.1 伙伴选择问题

当某企业(盟主)接手大项目，因需要便根据具体情况将大项目分成若干个子项目，并组织VE共同完成项目。投标企业对这些子项目投标，盟主根据各潜在伙伴在投标中提供的指标确定要选择的伙伴。符号如下：

子项目: T={ T 1,T2,...,Tn} 。子项目 Ti的投标企业集合Ei= {eij| j ∈1,Mi } (i = 1,2, …,n)。Mi为投标 Ti的企业个数。eij表示项目 Ti由第j个企业中标。

本文仅对时间 tij质量 qij成本 cij可靠性 rij4个指标进行评估。T、Q、C、R分别为所有子项目的总时间、质量、成本、可靠性。

这是个多目标优化问题,一般地不能使所有的指标都达到最优。故采用公式(2)将其转为单目标优化问题：

1.2 群搜索算法

群搜索算法(GSO)源于动物觅食行为和群居形态的一种模仿。动物觅食策略主要有:①发现食物;②追随并分享食物。为避免陷入局部最优,GSO还添加了游荡者：每轮迭代位置最好的个体为发现者；追随者朝着发现者的位置前进；而游荡者朝任意方向游动，迭代过程中个体角色会发生变换。

每次迭代发现者按以下步骤执行搜索：

1[0,1]间均匀分布的随机数;θmax为最大搜索角度，搜索距离按公式(10)算出。

(2)计算新位置对应的适应值。如果新位置的适应值更好，则跳到新位置，否者不动，并按公式(11)调整搜索角度，准备下一次迭代。

r∈Rn为[0,1]间均匀分布的n维随机数,a 通过公式3(13)计算得到。

a =√ ( n + 1 )(13),n为个体数目

游荡者按公式(14)(15)选择搜索角度和搜索距离，并按公式(16)移动。

1.3 贪心策略的群搜索算法（GGSO）

在GSO中，游荡者的随机搜索行为可以防止算法陷入局部最优，但正是它的随意性会极大影响算法的收敛速度。故针对游荡者的随机行为采用贪心策略进行改进：

游荡者依然随机获取一个方向，算出其搜索到的新位置适应值并与原位置适应值比较，若新位置更优，则跳到新位置，否则不动。这样既能加快搜索速度还能防止群体进入一个含大量坏多样性的局面。

1.4 自适应半径角色分配策略的群搜索算法（ARGSO）

追随者主要影响算法收敛性，游荡者影响群体的多样性。但GSO中追随者和游荡者都是随机选择的，其结果极可能导致偏离搜索者的个体作为追随者，而离搜索者近的个体作为游荡者，显然这不合常理。

以发现者为球心，分布在距球心R范围内的个体均选为追随者，而离球心大于R的个体为游荡者。显然R值直接影响到追随者和游荡者的数目。本文采用球半径自适应策略，即追随者规模随R的变化而变化。

设发现者和追随者的位置向量分别为Xpk和Xsk，则追随者的集合：

先计算每个个体到发现者的距离，求出搜索半径Rt。当群体规模较大且分布极其松散使得落入球内的个体数少，出现离群现象。而当分布极其密集，使得落入球内的个体偏多，出现碰撞现象。K就是为了避免出现这两种现象而设置的。多次试验发现当k =1.23时效果较好。

迭代过程中，个体的分布和角色是动态变化的，个体到发现者的距离也不断变化，所以球的半径大小也应该随迭代次数的变化而重新计算。

1.5 建模

伙伴选择问题涉及到项目的划分和多个投标企业的选择，而群搜索算法主要包含个体的位置和适应度。故可以将项目的个数n映射到个体的位置维数，而将每个项目的投标者总数 mi(i = 1 ,2,...,n )作为个体在第i个位置的最大值，另设置一个 m * c的二维数组 e valuatemc,m = ∑mi,c代表中企业评价指标数。enterprisen 存放各子项目投标企业数。利用公式(2)求出个体的适应值。

表1 实验数据

1.6 实验结果

图1 适应度平均值

图2 适应度均方差

GSO、GGSO和ARGSO对伙伴选择问题执行过程中的每代适应度的平均值和均方差。

2 结论

对比实验效果图可以发现，各算法都能求解伙伴选择问题。两种改进的算法每代求得的平均适应度都比标准群搜索算法小。从图中还能发现GSO大概执行20代后，搜索群体的平均适应度的波动范围变得很小，且改进的群搜索算法求得的平均适应度都更小，说明改进的群搜索算法执行效果都比GSO好。由图1可知GGSO算法能快速的到达一个基本不变的值，由图2更能发现后期个体的均方差基本为0，也就是说群体中每个个体的适应度基本一样。这表明该改进算法的收敛速度比别的算法更快。从图1也能看出ARGSO的收敛速度也比GSO快，但较GGSO慢,这主要是由于算法执行过程中群体中个体的多样性丰富。这说明ARGSO能较好的改善标准群搜索算法的个体多样性问题，且提高了算法的收敛速度。