改进快速单亲遗传算法解均衡多旅行商问题

均衡多旅行商问题(Balanced Multiple Traveling Salesman Problem,BMTSP)被广泛应用在诸如多人协作、任务分担等情形中。针对该问题提出一种改进快速单亲遗传算法(Improved Fast Partheno-Genetic Algorithm,IFPGA)进行求解。首先,基于图论知识完善了BMTSP问题的数学模型;其次,强化和改进了单亲遗传变异策略,将四种常用变异算子“移位、倒序、左移、右移”与随机插入操作相结合,以此大幅增加种群多样性和迭代后期的局部寻优能力;经过精英策略优选后,基于最近邻点策略对种群每一个个体中路程最长的旅行商回路进行局部优化,增强了算法的全局寻优能力。实验结果表明,IFPGA算法设置的策略对算法的性能提升明显,求解算例时IFPGA算法的收敛速度和求解精度得到了很大的提高。

Monitoring nearest neighbor queries with cache strategies

The problem of continuously monitoring multiple K-nearest neighbor (K-NN) queries with dynamic object and query dataset is valuable for many location-based applications. A practical method is to partition the data space into grid cells, with both object and query table being indexed by this grid structure, while solving the problem by periodically joining cells of objects with queries having their influence regions intersecting the cells. In the worst case, all cells of objects will be accessed once. Object and query cache strategies are proposed to further reduce the I/O cost. With object cache strategy, queries remaining static in current processing cycle seldom need I/O cost, they can be returned quickly. The main I/O cost comes from moving queries, the query cache strategy is used to restrict their search-regions, which uses current results of queries in the main memory buffer. The queries can share not only the accessing of object pages, but also their influence regions. Theoretical analysis of the expected I/O cost is presented, with the I/O cost being about 40% that of the SEA-CNN method in the experiment results.

基于混合相似度的反导作战案例检索方法

针对反导作战预案属性种类繁多、元素复杂等特性,为了更好地将作战预案与作战问题进行匹配,分析了反导作战预案各属性的差异,设计了一种先局部后整体的相似度量策略,将反导作战预案属性划分为关键类属性、裕度值属性、确定性数值属性、区间性数值属性、模糊属性和文本类属性6类,并给出了相应的相似度量算法。基于最近邻策略,提出了一种基于混合相似度的反导作战案例检索方法,并对该方法进行了实例验证,结果表明:该方法能有效提高反导作战案例检索的速度和正确率,可为反导指挥控制系统的建设提供技术支持。