计算机科学技术

相关性粒子群优化模型

申元霞，王国胤，曾传华

摘要：目的：粒子群优化算法因概念简洁、优化性能良好等特点在诸多工程领域得到了成功地应用。但是在求解复杂优化问题时，算法易陷入早期收敛。如何克服早期收敛并提高优化性能是粒子群优化研究的热点问题。针对这个问题，本文从如何合理利用自身经验信息和群体共享信息的角度进行探讨。方法：首先基于认知论的观点对速度更新公式中的随机因子进行了分析，建立了粒子对自身经验信息和群体共享信息认知的内在联系，提出了相关性粒子群优化模型。该模型采用Copula函数去刻画随机因子间的相关结构，通过不同的相关结构和相关性程度反映粒子对自身经验信息和群体共享信息利用策略的差异；接着给出了基于Gaussian copula的相关性粒子群优化模型的实现方法。最后从理论上给出了随机因子间相关程度与群体多样性的关系式；证明了随机因子间相关程度与算法收敛性的关系，同时给出了相关性粒子群优化模型的收敛条件。结果：从随机因子相关系数与种群多样性的关系式分析可以看出，在相关性粒子群优化模型中群体预期多样性的期望随着相关系数的变化而变化。当随机因子间呈正线性相关时群体预期多样性的期望为最大；当随机因子间呈负线性相关时群体预期多样性的期望为最小。从随机因子间相关程度与算法收敛性的关系分析可知：（1）对于不同的相关程度，当惯性权重ω、加速系数满足给出的条件时，粒子位置期望均收敛于粒子自身最优位置和群体最优位置的算术均值。（2）从给出的粒子位置方差极限与随机因子相关系数的关系表达式可知，在粒子收敛的过程中，粒子位置的波动幅度与随机因子的相关程度有关。当随机因子间呈完全正线性相关时，粒子位置变量均方收敛于粒子自身最优位置和群体最优位置的算术均值。Gaussian copula相关性粒子群优化模型的相关系数方差分析可知，随机因子间相关程度的水平设置对模型的优化性能有特别显著的影响；数值仿真实验结果表明，当相关系数为1时，基于Gaussian copula相关性粒子群优化模型不仅具有高的收敛精度，同时具有快的收敛速度；当相关系数为-1时，该模型易陷入局部最优。结论：在随机因子认知分析的基础上，本文给出了随机因子的相关性假设，提出了相关性PSO模型。该模型采用Copula函数描述了粒子对自身经验信息和群体共享信息持有态度的关联性，通过分析Gaussian copula的概率特性解释了相关性粒子群优化模型的认知行为。当惯性权重、加速系数都保持固定策略的前提下，群体预期的多样性随着相关系数的增加而增大；粒子位置的波动幅度随随机因子相关程度的变化而变化。随着相关系数的增加，模型的优化性能有明显提高的趋势；当随机因子成完全正线性相关时，模型的综合优化性能达最高。

来源出版物：软件学报, 2011, 22(4): 695-708

入选年份：2016

支持大数据管理的NoSQL系统研究综述

申德荣，于戈，王习特，等

摘要：目的：随着云计算、互联网等技术的发展，大数据广泛存在。分析大数据的特点以及支持大数据管理系统面临的关键技术，探索大数据管理的前沿研究和研究挑战，主要包括数据存储模型和查询处理策略，支持事务处理的分布式事务，提高系统性能的负载动态均衡和副本管理策略。方法：依据大数据特点和大数据管理需求，结合分布式数据库、NoSQL数据库和云计算等技术，研究大数据管理技术。首先，基于key-value的数据模型和基于hash的分布索引策略；其次，将数据一致性维护交由用户管理或回避两段提交协议（2PC）的分布式事务管理技术；第三，多模式的负载动态均衡策略；第四，自适应的副本管理策略和多种一致性维护方法共存；第五，基于MapReduce分布式框架的复杂查询处理与优化策略。结果：key-value数据模型满足海量数据管理的可扩展性、简单查询的高效率等应用需求。key-value数据存储系统典型采用基于key哈希存储或范围存储，基于BloomFilter局部过滤技术以及多种索引共存的数据索引策略，但只支持简单的查询操作和单key的事务特性，限制了 key-value存储系统的应用。key-value数据存储系统典型，一种方法是将一致性检查交给应用层处理，但增加了开发者负担；另一种是实现多key的本地事务或将事务限制在同组内的分布式事务，虽然可避开两段提交协议（2PC），但并不能灵活而低代价地支持真正的分布式事务。针对资源负载、数据负载和任务负载（用户负载、事务负载、操作负载等），分别侧重资源负载均衡分配、数据动态迁移、任务动态迁移的动态负载平衡模型，能够有效提高系统资源利用率、系统吞吐率和系统整体性能，但没有综合考虑多类型负载均衡的影响作用。自适应的副本管理策略对系统弹性、动态负载均衡和改善系统性能等方面具有重要作用，需要有可行的均衡副本策略的利益和代价模型，提高副本对系统的贡献度；根据应用需求，采用多种一致性策略共存模式，如面向事务处理的强一致性和弱一致性数据维护策略，并通过多策略相互作用来提升系统的性能和可扩展性。将复杂查询交由应用层处理，或基于MapReduce模型组件定义查询视图并应用MapReduce架构并行地处理，后者是当前流行的用于复杂查询和大数据分析的分布式并行处理架构。结论：大数据带来了大机遇，key-value数据存储系统已成为了研究者关注的热点问题。为有效地支持大数据管理，有关key-value数据存储系统及其相关研究还有许多挑战性问题，需要研究者去研究和探讨，典型研究包括海量数据分布存储与局部性、分布式事务管理模型、负载均衡的自适应性、灵活支持复杂查询、自适应的的副本管理策略以及有关key-value数据模型的支持理论等。

来源出版物：软件学报, 2013, 24(8): 1786-1803

入选年份：2016

知识图谱构建技术综述

刘峤，李杨，段宏，等

摘要：目的：知识图谱技术在人工智能领域的成功应用引起了业界和学术界的广泛关注。知识图谱是一个结构化的语义知识库，其基本组成单位是（实体，关系，实体）三元组，及相关的属性信息。实体间通过关系相互联结，构成网状的知识结构，形成对物理世界中的概念、对象及其相互关系的一种符号表达。知识图谱构建是一个热点集中的交叉研究领域，仍有许多值得长期研究和关注的突出问题，具有技术复杂度高、构建难度大的特点。本文从知识图谱的定义和技术架构出发，对构建知识图谱涉及的关键技术进行了自底向上的解析。目的是宣传该技术，吸引更多的关注和科研投入。方法和结果：知识图谱的构建过程是一个数据驱动的持续迭代更新过程。本文首先对知识图谱构建相关的关键技术进行了全面调研和分类整理，然后对跨语种知识图谱构建技术和知识图谱典型应用的发展现状进行了简述，最后总结了知识图谱构建技术当前面临的主要问题和挑战。其中，重点介绍了知识图谱系统的逻辑构成和核心构建技术。知识图谱的典型逻辑构成包括数据层（知识库）和模式层（本体库）等两大功能组件。本文介绍的知识图谱构建技术专指从原始数据出发，采用一系列自动化或半自动化的技术手段，迭代地从原始数据中提取出知识元素（事实、属性、本体等），并将其分别存入数据层和模式层的过程。按照自底向上的构建逻辑，从信息抽取到知识入库，将涉及的关键技术进一步划分为3个层次，（1）信息抽取层，择要介绍了开放域信息抽取领域近年来取得的新进展。（2）知识融合层，主要介绍实体链接技术和知识合并技术的发展现状及其在知识图谱构建领域的应用。（3）知识加工层，对本体抽取、知识推理和知识质量评估等知识图谱扩容关键技术进行了归纳和总结。结论：可以预见，随着Google Now，Microsoft Cortana，Apple Siri，IBM Watson等基于知识图谱的商业智能产品的社会渗透程度不断提高，知识图谱技术将迎来新的发展机遇。例如，Siri已成为美国第二大移动搜索引擎和排名第一的移动语音服务应用，影响和改变了许多人的观念和生活模式。而在2016年美国大选中，通过Xkeyscore项目采集并存放在Spy Cloud上的希拉里私人邮件，成为了导致选情反转的关键，该项目本身也是一个知识图谱项目。因此，知识图谱技术正在对人类生活和社会发展产生深刻的影响，值得投入更多的研究努力。

来源出版物：计算机研究与发展, 2016, 53(3): 582-600入选年份：2016

异构延迟容忍移动传感器网络中基于转发概率的数据传输

刘唐，彭舰，杨进

摘要：目的：近年来，将无线传感器网络应用于面向移动对象的数据收集成为研究的热点。在允许移动节点间的数据传递存在延迟的容忍延迟移动传感器网络DTMSN（delay tolerant mobile sensor network）中，如何以尽可能低的能量能耗和尽可能小的数据传输延迟来达到尽可能高的传输可靠性，成为了DTMSN要解决的首要问题。本文针对由不同类型的移动传感器节点构成的异构延迟容忍传感器网络 HDTMSN（heterogeneous delay tolerant mobile sensor network），提出了一种基于转发概率的动态数据传输算法 FPAD（forwarding probability-based adaptive data delivery algorithm）。方法：在由异构移动传感器节点构成的 HDTMSN中，FPAD算法由数据传输和队列管理两个主要部分组成。数据传输机制的基本思想是，网络中的节点有消息等待发送时首先计算出自身的消息传输概率，然后获得通信范围内其他节点的消息转发概率。节点随后将消息转发到所有转发概率大于自身传输概率的节点。针对异构环境下消息大小不同且传输延迟要求不同的特点，节点的传输概率和转发概率的计算均由能量消耗因子和传输延迟因子构成，以保证消息能以更低的能量消耗和更小的传输延迟发送到汇聚点。队列管理机制则是根据消息不同的传输延迟要求作为消息丢弃的依据，使得在尽量增大传输成功率的同时有效控制消息副本数量，降低网络传输能耗，延长网络寿命。结果：为验证FPAD算法的性能，在不同的网络环境下，对FPAD、SRAD（selective replication-based adaptive data delivery scheme）、DT（直接传递）和 Floating（泛洪）算法的网络寿命、消息传输成功率、消息平均副本数及消息平均传输延迟进行实验对比。（1）首先在默认网络环境下对4个算法进行性能对比。FPAD算法的寿命达到了 1.908天，高于要进行消息转发的SRAD算法和Floating算法。由于FPAD算法通过比较传输概率和转发概率进行数据分发，从而数据传输成功率到达了最高的89%。对于消息平均副本数，FPAD算法为所有数据转发算法中最低的 7.27。此外，FPAD算法的消息平均传输延迟为130.5 s，低于其他3个算法。（2）改变异构节点占网络中总节点数的比例，观察各种算法在不同异构节点比例下的性能。由于FPAD算法充分考虑到了网络的异构性，在不同的异构节点比例下，FPAD算法均有着最优的消息平均传输成功率、平均副本数（除不进行消息转发的DT算法）、消息平均传输延迟。（3）改变节点的通信半径，FPAD同样有着最高的消息平均传输成功率、比SARD和Floating算法更少的消息平均副本数、以及最低的消息平均传输延迟。（4）改变节点的运动速度，FPAD算法随着节点运动速度的增大，消息传输成功率也不断提升。同时，FPAD算法在不同的节点运动速度下保持了低于 SARD和Floating算法的消息平均副本数和最低的消息平均传输延迟。（5）增大节点的消息队列长度，使得节点能容纳更多的消息，此时FPAD算法的消息传输成功率持续上升且明显高于其他算法。由于FPAD始终能较好地控制消息副本数量，因此FPAD的消息平均副本数一直低于SARD和Floating算法。此外，节点存储队列的变化对4种算法的传输延迟没有显著影响。结论：面向由不同传感器节点构成的可以监测不同对象的异构延迟容忍移动传感器网络中的数据传输，提出了一种适用异构环境下的基于转发概率的动态数据传输策略 FPAD。与已有工作相比，FPAD的主要贡献表现在于以下2个方面。（1）在FPAD算法中，消息的转发根据消息所在节点的传输概率及通信范围内其他节点的转发概率确定。根据异构网络的特点，传输概率和转发概率均由能量消耗因子和传输延迟因子计算得出，使节点获取的消息能够以尽可能低的能量消耗和尽可能小的传输延迟发送到汇聚点。（2）FPAD引入适应于异构环境的消息队列管理机制，以消息当前的延迟容忍度作为消息丢弃的依据，使得在尽量增大传输成功率的同时有效控制了消息副本数量，降低了网络能耗，延长了网络寿命。

来源出版物：软件学报, 2013, 24(2): 215-229

入选年份：2016