求解虚拟企业资源结盟博弈的启发式群智能优化算法①

崔 莹

(南京财经大学 信息工程学院,南京 210023)

求解虚拟企业资源结盟博弈的启发式群智能优化算法①

崔 莹

(南京财经大学 信息工程学院,南京 210023)

通过对求解虚拟企业资源结盟博弈问题与求解经典SAT问题相似性的分析,提出了一种求解虚拟企业资源结盟博弈的启发式群智能优化算法.算法融合萤火虫优化算法与布谷鸟优化算法部分原理,并设计可行的交叉算子以及变异优化算子,能够修复不可行解并保持种群多样性.实验结果表明本文算法的迭代次数与搜索到的稳定联盟数成线性增长,较启发式遗传算法有着更好的爬山性能和搜索能力.

资源结盟博弈;虚拟企业;SAT问题;群智能优化算法

虚拟企业是指分布在不同地区的常规企业,利用网络信息技术,为快速响应环境需求和变化而组织起来的动态联盟[1-2].在虚拟企业中,经常出现企业持有资源不能满足生产需求的问题,而建立企业资源结盟可有效解决该问题,因此虚拟企业结盟问题越来越受到关注.

文献[3]结合任务导向性和间续式结盟特征对虚拟企业治理机制进行了研究,文献[4]讨论了电子市场买方结盟问题.文献[5]提出了资源约束和目标约束下企业的结盟问题,可能的结盟数随企业数后的增长呈指数增长,是NP-hard问题.虚拟企业资源结盟博弈问题的目标是搜索稳定联盟并非优化联盟结构,即解具有可满足性即可,与经典SAT问题有着相似之处.文献[6]提出了一种利用近似解的求解SAT问题的算法,将近似解原理与多种群智能算法融合设计出一种可用于搜索虚拟企业资源结盟博弈的可行解的启发式群智能优化算法.

本文结合萤火虫优化算法与布谷鸟优化算法的部分理念设计,提出求解虚拟企业资源结盟博弈的启发式群智能优化算法,同时基于联盟及其目标之间的约束关系,设计交叉算子以及变异优化算子.

1 问题描述及分析

资源结盟博弈问题可以看做是资源的分配问题,本节主要对资源结盟博弈进行了形式化描述.

其中,Gi为企业ai所对应的目标.

联盟的稳定性是解决资源结盟博弈问题的核心,虚拟企业资源结盟问题的求解是资源结盟博弈的重要应用问题,实际上也是依赖于求解稳定联盟及其可达目标而实现的.

2 应用启发式群智能优化算法求解资源结盟博弈问题

本节具体地介绍了采用启发式群智能优化算法求解资源结盟博弈的稳定联盟,基于可行及相容的概念,分别定义评价函数,设计交叉算子和变异优化算子.

2.1 编码问题

求解虚拟企业资源结盟博弈中的稳定联盟,可以转化为在两个幂集中分布搜索联盟和目标子集在联盟C下可达.搜索空间为两个幂集的笛卡尔积.将一个解表示为一个二进制串且满足:

2.2 解之间的距离

随机从种群中选出要进行交叉的个体,形成交叉配对池,然后对配对池中的每个对解搜索与其距离最近的个体进行交叉操作得出一个新解.对解表示成二进制串,本文选择通过计算海明距离获得两个对解之间的距离.

2.3 评价函数

在虚拟企业资源结盟博弈的问题中,需要通过评价函数对对解进行判定.一个解可宏观定义为可行解与不可行解.可行解只有一种即在联盟C下可达,不可行解可以根据资源约束和目标约束具体分为四种,本文根据不可行解类型设置评价函数如下:

2.4 近似解交叉算子

文献[7]利用近似解加速求解SAT问题,有效地结合了局部搜索算法和完全算法的优点,首先利用局部搜索算法在较短的时间内得到一个近似解,然后将其作为初始输入导算子优先搜索近似解所在子空间可能存在的近似解,使得效率有了很大的提高[7].虚拟企业资源结盟博弈问题的基本思路与其解决SAT问题的基本思路具有很高的相似性,本文根据SAT问题的解决思路,同时结合萤火虫优化算法[7]以及其应用[8]设计出近似解交叉算子.本文提出的近似解交叉算子主要是将一个解与在空间距离中距离最近的解进行交叉更新,获得新的解,而新的解即有可能为潜在的可行解.假设一个解为在交叉配对池中与其距离最近的解为,在区间(0,1)内获取两个随机数a和概率阈值p,根据随机数a与概率阈值p的大小进行交叉更新,所得到的新解为,其更新式如下:

在对种群中的对解进行交叉操作,即实现通过优先搜索在可行解附近的空间找出潜在的可行解,可以保证搜索到的联盟数量稳定增长.

2.5 启发式变异优化算子

不可行解包含多种类型,每一类型反映着资源、企业及目标子集之间的需求供应关系.因此针对不同的类型的不可行解需要通过不同的方法进行优化,获取潜在的可行解,从而增加种族中可行解的数量.本文详细地分析了不同类型的不可行解的特点,分别设计了不同的变异优化算子以更好地适应具有差异的不可行解的问题的解决,达到“对症下药”的效果.启发式变异优化算子应用到的概念如下.

并将Gwait中频繁度计数最大的目标定义为则待变异频繁目标记做gfreq:

根据不可行解的类型进行了分析,针对不同类型的不可行解设计的变异优化算子具体内容如下:

2.6 联盟企业反置算子

在布谷鸟算法[9]设计中提出有鸟窝主人有一定概率发现鸟蛋并随机改变鸟窝的位置,该做法可理解为增加种群多样性.受此原理启发,本文将布谷鸟算法应用到联盟企业反置算子中,用来找到潜在的更优解.具体方法为:将每一个鸟巢里的鸟蛋看做是一个解,那么随机选择计生在鸟巢里的布谷鸟蛋则代表了一个新的解,可以利用新的以及潜在的可行解来取代一个在鸟巢里并不那么好的解.假设一个解的联盟企业反置算子为若xi=1则令xi=0,若xi=0则令xi=1.

2.7 求解资源结盟博弈问题的启发式智能优化算法

算法步骤如下:

Step 1.设置种群数后pop_size,(种群中的每一个个体对应着资源结盟博弈问题的一个解),企业数后n,最大目标数m,资源数t,交叉式子概率阈值p,最大迭代次数ItMax,稳定联盟计数count.

Step 2.随机从种群中选出要进行交叉的个体,形成交叉配对池,然后对配对池中的每个对解搜索与其距离最近的个体进行近似解交叉得出一个新解

Step4.判断是否到达最大迭代次数ItMax.若到达,停止迭代,输出稳定联盟计数count;否则重复Step 2～Step 3.

3 仿真实验与结果分析

3.1 实验 1

设置实验参数:种群数后pop_sizem=300,企业数后n=12,最大目标数m=4,资源数t=8,交叉式子概率阈值0.5,最大迭代次数ItMax=1000.随机生成仿真数据如表1、表2、表3所示.图1为实验结果图.

表1 企业资源持有表

3.2 实验 2

设置实验参数:种群数后pop_sizem=300,企业数后n=14,最大目标数m=6,资源数t=8,交叉式子概率阈值p=0.5,最大迭代次数ItMax=1000.随机生成仿真数据如表4、表5、表6所示.图2为实验结果图.

表2 企业目标需求表

表3 目标需求资源表

图1 本文算法与启发式遗传算法[5]对比结果图

表4 企业资源持有表

表5 企业目标需求表

表6 目标需求资源表

图2 本文算法与启发式遗传算法[5]对比结果图

3.3 结果分析

通过观察图1和图2可以发现启发式遗传算法[5]在迭代前期收敛较快,原因是启发式遗传算法采用的启发式交叉修正算子每次可以修复2个子代个体,而本文采用的启发式群智能优化算法每次交叉修复1个子代个体.但是,随着迭代次数的增加,启发式遗传算法容易出现“早熟”现象,而本文的算法通过对种群中的解进行变异优化之后,种群中可行解数后增多,近似解交叉算子的优势逐渐体现,优先搜索到可行解附近的潜在可行解,保证搜索到的联盟数量可以稳步增长,并设置联盟企业反置算子以保证种群的多样性,防止算法过早停滞,从而避免“早熟”现象的发生.另外,当问题规模增加,搜索空间扩大时,启发式群智能优化算法搜索到的稳定联盟数后与迭代次数几乎呈线性增长,相比于启发式遗传算法具有更强的爬山性能和搜索性能,所以本文提出的启发式遗传算法可用于求解虚拟企业资源结盟博弈问题,且具有较强的鲁棒性.

4 结语

制造企业联合生产产品问题可以归结为一类企业资源结盟博弈问题,从资源约束角度讨论企业的结盟问题具有重要应用价值.本文通过对比虚拟企业资源结盟博弈问题与SAT问题的相似性,结合了多种新型群智能优化算法的部分原理,设计出一种可用于求解资源结盟博弈问题的启发式群智能优化算法,为此类资源结盟的大规模问题提出一种可行的数学模型.接下来进一步的工作是对算法的精确度进行进一步的提高.

1 Mowshowitz A.Virtual organization.Communications of the ACM,1997,40(9):30–37.[doi:10.1145/260750.260759]

2 O’Leary DE,Kuokka D,Plant R.Artificial intelligence and virtual organizations.Communications of the ACM,1997,40(1):52–59.[doi:10.1145/242857.242871]

3 胡欣悦,汤勇力,李从东.任务导向的虚拟企业间续式结盟治理机制.系统工程理论与实践,2007,(11):34–42.[doi:10.3321/j.issn:1000-6788.2007.11.005]

4 韩伟,陈优广.电子市场买方结盟的利益分配及其结盟策略.计算机集成制造系统,2007,13(12):2487–2491.[doi:10.3969/j.issn.1006-5911.2007.12.030]

5 韩伟,吕捷,陈优广.虚拟企业资源结盟博弈的启发式遗传算法.计算机集成制造系统,2008,14(4):744–748,756.

6 荆明娥,周电,唐璞山,等.利用近似解加速求解SAT问题的启发式完全算法.计算机辅助设计与图形学学报,2007,19(9):1184–1189.

7 Krishnanand KN,Ghose D.Detection of multiple source locations using a glowworm metaphor with applications to collective robotics.Proc.of 2005 IEEE Swarm Intelligence Symposium.Pasadena,CA,USA.2005.84–91.

8 周永权,黄正新,刘洪霞.求解TSP问题的离散型萤火虫群优化算法.电子学报,2012,40(6):1164–1170.

9 李煜,马良.新型元启发式布谷鸟搜索算法.系统工程,2012,30(8):64–69.

Heuristic Swarm Intelligent Optimization Algorithm for Coalitional Resources Games in Virtual Enterprises

CUI Ying
(College of Information and Engineering,Nanjing University of Finance and Economics,Nanjing 210023,China)

A heuristic swarm intelligent optimization algorithm for coalitional resources games in virtual enterprises is proposed by comparing the similarity of coalitional resources games in virtual enterprises with the classic SAT problem.The algorithm fuses portions of the principles of Glowworm swarm optimization algorithm and Cuckoo Search optimization algorithm.It designs the feasible cross operator and the mutational operator,which can repair infeasible solution and maintain diversity.Experimental results indicate that the algorithm’s iterations linearly increase with the stable coalitions ever found.Compared with the heuristic genetic algorithm,it performs better in hill-climbing performance and searching efficiency.

coalitional resources;virtual enterprises;SAT problem;swarm intelligent optimization algorithm

崔莹.求解虚拟企业资源结盟博弈的启发式群智能优化算法.计算机系统应用,2017,26(9):195–199.http://www.c-s-a.org.cn/1003-3254/5976.html

① 基金项后:科技部科技支撑项后(BAH29F01);江苏省农业科技自主创新资金项后(CX(15)1051);国家自然科学基金(71372188)

2017-01-02;采用时间:2017-02-13