基于微分进化算法的消息传播网构建 邓柯+闫述摘 要：某事件发生时，除消息以广播的方式通知相关人员外，还需依赖个体之间的责任关系传播，消除信息孤岛问题社会网络（Social Network）中的个体之间存在复杂的责任关系，针对该问题，以滑坡事件发生时为例，创建带责任制的消息传播网模型，并采用微分进化算法评估关系属性和来往交流等因素对责任关系的影响权重，同时加入责任弱化（Responsibility Decline，RD）效应模拟消息传播过程结果表明，关系属性和面对面交流对责任关系的影响较大，紧急消息的传播过程也会受距离的影响实现了一对多的责任分派机制，多对多的责任分派方式则有待进一步研究Key：消息传播网；责任关系；影响权重；微分进化算法DOIDOI：10.11907/rjdk.162758：TP301：A ：1672-7800（2017）007-0005-060 引言滑坡是我国多发的地质灾害在面向区内全体人员的WSN（Wireless Sensor Network）滑坡监测预警系统[1-2]方面，作为配备最普遍的个人通信工具，是监测系统信息传递与接收的理想节点但在事关生命安全的紧急情况下，必须使撤离警报无遗漏地传达到每一个人，包括老人、病人、婴幼儿等无行为能力的人员。
由于人机分离、遗漏等造成的信息孤岛问题是监测系统中需要解决的问题因此，除以消息广播的方式传播紧急预警信息给具有接收信息能力的移动设备外，为解决信息孤岛的问题还需将消息传播的责任划分到个体，这意味着收到消息的责任个体需要将消息传播给被负责对象传统的消息传播网以网络社交平台为传输媒介，研究节点、边的特征及信息特征对消息传播的影响，强调消息的扩散性[3]，但滑坡紧急事件发生时的报警消息传达强调及时性和知晓性滑坡监测系统将区域中的居民依据责任关系构造成一个消息传播网，责任关系主要受关系属性和来往交流等因素的影响，且影响权重不同针对多属性决策问题有主观赋权法、客观赋权法[4-5]，解决该问题的采纳率达到了85.8%[1]为实现滑坡报警消息无遗漏地通知，这里引入主要解决实参数优化问题的微分进化算法[6-8]，确立了影响因子的权重，使得模拟消息传播过程中采纳率在居民之间的百米范围内达到97.8%，同时这种方案考虑了滑坡事件的紧急特殊性，加入受传播距离影响的RD效应，使消息在传播和走动传递两种方式中自由切换，与实际情况结合更灵活根据自定义的目标函数解决优化与责任关系相关的权重组合问题，能够实现一对多的责任分派问题。
结果显示，关系属性和各种交流方式对责任关系的影响各占一定比重，但关系属性和面对面交流方式影响更大同时解决该问题的方案可以运用到其它紧急事件发生并需要传播紧急消息的场景，具有应用拓展性1 消息传播网模型构建1.1 问题描述滑坡监测系统中的消息传播网由具有信息传播能力的正常人和无知晓能力的老人、病人、婴幼儿等责任关系构成，责任关系主要考虑由关系属性和来往交流频数综合决定若收到紧急消息的居民不能以的方式传播消息给未收到紧急消息的居民，則以走动的方式传递消息，走动传递消息会受到距离的影响依据以上问题构建网络模型如下：（1）建立消息传播网络滑坡区的居民依据责任关系构建一个带权有向的消息传播网络G（V，E，W），V是网络中的节点集合，V={v1，v2，v3，…，vN}，W是边的权值集合，W={wij|i≠j，1≤i≤N，1≤j≤N }，wij表示节点vi与节点vj之间的相互权值，代表居民之间的责任关系强度，其中wij≠wji2）加入RD效应假设传播信息失败，则需要个体移动传播信息给被负责对象这时需要考虑与距离相关的传播时间，存在随时间延迟的RD效应假设有正常居民A、B、C，其中居民A、B收到紧急信息，居民C没有收到紧急信息且联系不上，wAC>wBC，理应由A负责通知C，但A到C的距离远大于B到C 的距离，在紧急事件发生时需要考虑消息传达的及时性，应由距离C较近的B负责传递消息给C，传播时间更短。
因此，A的责任因消息传播时间间隔变大而弱化了3）网络中存在普通节点和特殊节点以居民为节点构成的网络图G（V，E，W），存在老人、病人、婴幼儿等无知晓能力的个体形成的节点，可以视为特殊节点（vs），其余视为普通节点（vg）1.2 特征提取信息传播以责任制的要求进行，对于任意用户u（假设该用户没有收到广播消息），存在wuv=max{wui|u≠i，1≤i≤N }，与其责任关系最强的用户v负责传播信息给用户uwuv受居民u与居民v之间关系属性以及来往交流频数的影响1）关系属性任何两个有关联的用户之间存在某种关系属性，这些关系可以分为家庭关系、朋友关系、情侣关系、邻里关系等这里可以用情感系数来表示情感的强弱，4种情感系数表示为Rfamily、Rfriend、Rflover、Rneighbor这几种系数一般存在以下大小关系：（2）来往交流频数居民之间存在走访（视为一种面对面的交流方式）、短信通话、、等多种交流方式，交流会影响人与人之间的关系，因此来往交流频数在影响责任关系中占有一定的权重走访频数（visits）：统计居民之间一年内的走访频数，用集合Fvisits表示v_fuv表示居民u与居民v之间的走访频数。
短信通话频数（calls）：统计居民之间一年内的短信通话频数，用集合Fcalls表示c_fuv表示居民u与居民v之间的短信通话频数和交流频数（s）：统计居民之间在一年内用或者通信的总频数，用集合Fs表示q_fuv表示居民u与居民v之间的交流频数 以上几种特征所占的影响比重不同，各个特征取值范围不一，需要作进一步的标准化处理这里采用Min-Max标准化方法，将以上特征集合的取值分别映射到[0，1]区间：其中，fuv和f′uv分别表示标准化处理前后的特征值1.3 模型建立关系属性和来往交流对责任关系各有一定的影响权重，设定关系属性所占权重为wR，来往交流中走访方式所占权重为wvisits，短信通话所占权重为wcalls，交流所占权重为ws，用户u与用户v的责任关系强度wuv可以表示如下：节点之间的影响力或信息传播能力随着时间间隔增大存在指数衰减规律[9]假设居民u在tu时刻收到紧急信息，在tv时刻居民v才收到居民u传来的紧急信息居民v在时刻tv收到居民u紧急信息的概率为fp（（v，tv）|（u，tu）），这个概率会随着时间间隔Δt=tv-tu的增大而降低同时wuv越大代表居民之间的责任关系越强，传播概率p（u，v，c）越大，居民之间紧急消息的初始传播概率p（u，v，c）与wuv成正比关系。
C为不大于1的常量，c为传播信息，设定：RD效应可以视为传播概率随时间衰减融合时间衰减因素的传播概率模型通常有3种表示方法，如表1所示的3种传播概率模型，分别是指数模型[10-11]、幂率模型和瑞利模型指数模型和幂率模型中的传播概率随着Δt的增大单调递减，幂率模型中传播概率的演化还具有长尾特征瑞利模型中传播概率先是随Δt增大而增加，到达峰值后开始缓慢降低，该模型研究传染病传播概率增长和衰退的演化规律[12]初始传播概率与责任关系强度正相关，随着传播时间增大会产生RD效应，这里选择指数模型来刻画传播概率随Δt的衰减规律在指数模型中τ（u，v，c）代表传播延迟，传播延迟受传播主体、传播客体、传播内容等因素的影响当紧急事件发生时，传播主体需立即将紧急消息传递给传播客体，在居民之间传播延迟无差别（忽略通话时延），因此τ（u，v，c）可以视为一个常量Llatency变换指数模型后，随时间变化的传播概率fp（（v，tv）|（u，tu））表示为：其中，Suv表示u与v之间的传播距离，人员行动平均速率为v在1.1问题描述中，问题（1）和问题（2）是预选的两种消息传播方式，传播主体首选传播方式，当传播方式失败时再选择人员走动传播方式。
设传播方式成功的概率为P，采用人员走动传播方式的概率为1-P，若普通节点vg收到紧急消息概率Pr（vg，par（vg）），par（vg）表示传递消息给vg的父节点，有：问题（3）考虑到消息传播网中老人、病人、婴幼儿等这些无知晓能力的信息孤岛点，针对这类节点选择采用人员走动的方式传递消息，则：将式（4）、式（5）分别带入式（6）、式（7），得到式（8）、式（9）：从式（3）、式（8）、式（9）可以看出，在确定父节点收到消息的情况下，节点收到消息的概率与父节点之间的关系属性以及来往交流频度相关，同时受节点之间距离的影响2 权重评估权重值是责任划分的重要因素，责任划分主要受关系属性和来往交流的影响，需确定wR、wvisits、wcalls、ws的最佳值找出最佳权重值有两种方法可以选择，一种是典型的确定性最优算法，比喻穷举搜索，可以返回最优解但这种方法需要搜索整个解空间，时间复杂度太大为了减少计算量，且4个权重值之和为1，权重的取值范围限制在0.000 001～0.999 997这些权重值的组合就有999 9973种情况，即需要从9.999 91×1017个权值组合中评估最佳权重组合穷举算法找出这4个权重值，在时间上代价太高，不利于快速决策。
另一种是选择一种元启发式方法搜索最佳权重组合这种智能技术能够搜索解空间并减少评估次数，且在能接受的合理时间内完成，针对目标函数，元启发式方法往往获得近似最优解微分进化（Differential Evolution）搜索算法，这种元启发式算法非常适用于寻找最优值问题[13-14]微分进化算法是一种以人群为基础的算法，人群中的个体对应于目标问题的一个候选解，每个个体是一个存放实际值的向量[15]设xi表示人群中一个个体，xi[j]元素存放影响因素的权重值，有：微分进化算法首先随机产生有N个个体的人群，个体中元素的初始值从区间[0.000 01，0.999 97]中选择参数组在G次换代中不断变化和重组，获得最优解算法伪代码如下：//F代表突变因子，CR代表重组因子popl=N；Evaluate（popl）；g=0；while（g表2為实验中微分进化算法的参数配置，这些值是在调试和测试之后选定的针对该问题确定了一个目标函数F（xi），微分进化算法需要实现该函数的最小化目标函数F（xi）由两部分组成： （1）本实验需要收集与每个居民有责任关系的人员信息根据居民u的主观判断将这些人员按与自己的责任强弱降序排列，设这个主观序列为Au={y1，y2，y3，…，yn}。
求出式（3）在xi组合条件下有责任关系的人员与u的综合权值wuv（v表示与u有责任关系的其他居民），依据综合权值的大小降序排列，设该理论序列为Bu={z1，z2，z3，…，zn}求序列Bu相对于序列Au的逆序数Inversion_Count（u，xi）2）求xi中超出允许范围的变量数Invalid_Params（xi）：F（xi）需要考虑（1）和（2）两部分：为方便采集实验数据，以长咀村为实验基地，约980人长咀村分7个小区，为便捷调查人员关系，以太子庙小区作为调查代表，调查中病人、幼儿、老人、外出、正常人的人数各为1、3、19、36、33收集居民之间的日常情感关系属性和来往交流信息，经标准化后带入模型求解最小F（xi），并获取最优权重组合表3、表4为实验在Visual C++ 6.0 Win32环境下运行出的部分结果在实验中依据式（1）设置不同的日常情感关系属性，本次实验设置了4组不同关系属性值进行了4组模拟，表1中的两张子表分别为4组模拟的候选解，选取最小F（xi）值为最优解，对应的权重组合为最优权重组合从两张子表可以看出，不同关系属性值的设定会影响最优解。