求解最小支配集问题的禁忌遗传混合算法

将最小支配集问题转换为一系列判定问题k支配集问题,并提出一种禁忌遗传混合算法对k-DS问题进行求解。此算法将禁忌搜索算法和遗传算法两种启发式算法结合起来,互补不足。高效的邻域结构保证了算法的运行效率,禁忌策略防止算法过早陷入局部最优陷阱,遗传算法框架进一步增强了算法的疏散性。经过与现有求解最小支配集算法的结果进行分析比较,禁忌遗传混合算法的结果较其它算法更优。

基于改进K支配排序的高维多目标进化算法

为提高4目标以上高维多目标优化问题的求解性能,提出一种基于改进K支配排序的高维多目标进化算法(KS-MODE).该算法针对K支配的支配关系和排序方法进行改进,避免循环支配并增强选择压力;设计新的全局密度估计方法提高局部密度估计精确性;设计新的精英选择策略和适应度值评价函数;采用CAO局部搜索算子加速收敛.在4～30个目标标准测试函数上的实验结果表明,KS-MODE能够在保证解集分布性的同时大幅提升收敛性和稳定性,能够有效求解高维多目标优化问题.

k~*-支配Skyline查询在实验数据检索中的应用

利用多关键字查询技术可以从大量的实验数据中检索表现突出的数据,Skyline查询是多关键字查询的经典方法之一。在高维空间中,Skyline查询返回的结果集较大,往往没有实际意义。而k-支配Skyline查询虽然可控制结果集的规模,但有可能产生循环支配,导致结果集为空。上述方法都没有考虑用户偏好。在k-支配Skyline查询的基础上,在支配关系中引入用户偏好的优先级,提出了k~*-支配Skyline查询。该查询既可控制结果集的规模,又消除了循环支配的可能性,保证了查询结果集不为空,还能使结果集尽可能满足用户偏好。通过实验,研究并验证了k~*-支配Skyline查询用于实验数据检索系统是可行性的。

多时间序列k′/k-支配Skyline查询处理

时间序列是各个领域中大量存在的一类数据,有着极广泛的应用.多时间序列是其中常见的一种数据类型,它从多个角度以单时间序列的形式去描述同一个对象.目前关于时间序列的研究主要集中于单时间序列,而多时间序列的研究工作则相对较少,如多时间序列的查询处理等,但是在实际生活中多时间序列的查询却有着非常广泛的应用.首先定义了多时间序列的支配关系,然后在此基础上给出多时间序列k′/k-支配Skyline查询的定义,并提出了GMS和GMI两种查询算法,对算法的正确性和复杂性也进行了证明和分析.合成数据和真实数据上的大量实验表明,两种算法都可以得到较好的查询结果,而GMI算法的查询效率较GMS算法有很大程度地提升.

无线传感器网络中一种能量高效的skyline查询算法

针对分布式无线传感器网络环境下的skyline查询问题,提出了KSkySenor算法,有效地从传感器网络中获取更有意义的skyline结果;KSkySenor算法对感知数据进行预处理计算每个元组的支配能力,按照支配能力与各维度值之和对其进行排序,设计了一个基于聚簇的结构用于收集所有传感器读数,提出了一个剪枝方法用于渐进的从传感器网中获取skyline结果集;实验中分别改变传感器网络规模大小、数据维度、支配属性个数k,对KSkySensor算法进行测试,实验结果表明KSkySenor算法与先前的skyline查询处理算法相比具有很高效率,减少了无线传感器网络中的数据传输量,延长了网络生命周期。

无线传感器网络延迟约束的MDC分布式轨道规划算法

针对引入移动元素后无线传感器网络数据面临的收集延时问题,提出了一种分布式的移动数据收集器(MDC)轨道规划算法。首先给出基于k跳支配集的MDC最小时延规划问题定义,并证明它是NP-hard。在基于集结的数据收集模式汇总,k跳支配节点作为集结点缓存传感节点收集的数据并在MDC到达时上传。然后,提出了一种高效的基于k跳支配集的MDC轨迹构建算法。算法通过分布式的k-跳支配集算法找出网络中的支配节点,进而通过Prim算法和Christofides近似算法对MDC的移动轨道进行规划。算法的正确性、k-跳支配集的界、时间复杂性和消息交换复杂性通过理论进行分析。最后,通过仿真实验验证了算法的有效性。仿真结论表明,与同类算法相比,所提出算法能够显著缩短MDC的移动轨迹,因而可以降低网络延迟。