基于LSH的进化计算代理模型高效邻域查询研究

发布时间：2018-05-01 00:03

本文选题：CPLSH + 邻域查询　；参考：《太原科技大学》2017年硕士论文

【摘要】：近年来,进化算法逐步成为解决传统优化算法难以克服的复杂问题的有效手段。但是适应值的计算需要消耗大量的时间成本,为了减少计算消耗的时间,其中一种解决办法是通过代理模型来估算适应值。代理模型一般需要查找个体的邻域数据,通常需要经过目标数据和其他数据一一进行位置距离比较而得到,时间复杂度很大。为了减少代理模型中查找邻域数据所需的时间,本文利用了局部敏感哈希技术(LSH)。在基于p-稳定分布的局部敏感哈希索引的基础上进行改进,提出了基于碰撞的p-稳定分布的LSH算法(CPLSH),该算法减少了使用哈希函数的个数,并选择碰撞率高的数据作为候选集,从而更高效地找到邻域数据。为了验证改进后的算法,使用两个高维数据集进行实验,然后与代理模型结合起来,将其加入到微粒群算法中,利用四种测试函数,通过实验验证该算法在进化算法代理模型中的有效性。基于以上的研究,设计实现了进化计算历史数据的key-value数据库原型系统。除了基本的增删改查功能外,该系统还增加了邻域查询功能,以便有效提高代理模型邻域查询的效率。邻域数据的查询使用基于碰撞的p-稳定分布的LSH算法实现。此外,当内存数据过大时,定期将内存数据存入磁盘,并构建多级结构区分热数据和冷数据,实现持久化存储和外存上的高效查询。
[Abstract]:In recent years, evolutionary algorithm has gradually become an effective means to solve complex problems which are difficult to overcome by traditional optimization algorithms. However, the computation of fitness requires a lot of time cost. In order to reduce the computation time, one of the solutions is to estimate the fitness by proxy model. The agent model usually needs to find the neighborhood data of the individual, and usually needs to compare the location distance between the target data and other data one by one, so the time complexity is very large. In order to reduce the time required to find neighborhood data in the proxy model, a local sensitive hashing technique is used in this paper. Based on the improvement of the locally sensitive hash index based on p-stable distribution, a p-stable LSH algorithm based on collision is proposed. The algorithm reduces the number of hash functions and selects the data with high collision rate as candidate set. Thus, the neighborhood data can be found more efficiently. In order to verify the improved algorithm, two high-dimensional data sets are used to experiment, and then combined with the agent model, the improved algorithm is added to the particle swarm optimization algorithm, and four test functions are used. The effectiveness of the proposed algorithm in the evolutionary agent model is verified by experiments. Based on the above research, a prototype system of key-value database for evolutionary computing history data is designed and implemented. In addition to the basic function of adding, deleting and checking, the system also adds the function of neighborhood query in order to improve the efficiency of neighborhood query of agent model effectively. Neighborhood data query is implemented by LSH algorithm based on collision-stable distribution. In addition, when the memory data is too large, the memory data is stored on disk periodically, and the multi-level structure is constructed to distinguish the hot data from the cold data, so as to realize the efficient query on persistent storage and external memory.
【学位授予单位】：太原科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】