基于注记关联组的蚁群算法对点要素注记配置的实现方法

摘要

一种基于注记关联组的蚁群算法对点要素注记配置的实现方法，包括如下步骤：聚类分组、筛选单点注记关联组、蚁群构建、蚂蚁搜索、计算转移概率修改tabu_c、注记适应度评价。本发明的有益效果为：适用于点规模大、点簇疏密变化差异大的地图，能有效的降低算法迭代计算所耗费的时间和提升注记结果质量。

主权项

一种基于注记关联组的蚁群算法对点要素注记配置的实现方法，其特征在于，包括如下步骤：步骤(1)、聚类分组；各个需要的参数进行初始化，点注记待选方位生成，方位优先级值赋值，对不同方位的注记进行赋值，以正东方向为最高分，逆时针方向进行降分，注记关联组生成，设有K个注记关联组；步骤(2)、筛选单点注记关联组；判断每个注记关联组中点要素数目是否大于1，若是则为多点注记关联组，随后进行第(3)步；若不是则表明该注记关联组为单点注记关联组，无需进行蚁群算法迭代，只需根据该点注记方位优先级值，选取优先级值最大的方位存入最终结果集FinalResultList中；步骤(3)、蚁群构建；设有N(N<＝K)个多点注记关联组，则有N个蚁群，设第α(α∈[1,N])个多点注记关联组中有Q_a个点要素，对应的蚁群中有P_a个蚂蚁；步骤(4)、蚂蚁搜索；对各蚁群开始进行搜索，进入第一个蚁群针对的点注记关联组，要求每只蚂蚁需将其所在的多点注记关联组中的所有点要素随机搜索一遍，搜索出每个点要素中最优待选注记方位；设第c(c∈[1,P_a])只蚂蚁，随机的选取一个点要素，记为i(i∈[1,Q_a])；步骤(5)、计算转移概率根据i所对应的点要素待选注记优先级值η_ij和信息值τ_ij通过公式(3)计算转移概率选取注记方位，判断冲突情况，更新该注记方位信息值，并存入第α个蚁群的结果TempResultList_α；$P_{\mathrm{ij}}^c=\frac{{\left[{\tau }_{\mathrm{ij}}\right]}^{\alpha }·{\left[{\eta }_{\mathrm{ij}}\right]}^{\beta }}{\underset{j=1}{\overset{{\mathrm{SumL}}_d}{\Sigma }}{\left[{\tau }_{\mathrm{ij}}\right]}^{\alpha }·{\left[{\eta }_{\mathrm{ij}}\right]}^{\beta }}---\left(3\right)$其中，SumL_d为i点要素的待选注记方位总数，η_ij为i点要素的第j个方位的优先值，τ_ij为i点要素的第j个方位的信息值，α、β用于反映优先值、信息值的相对重要性，α+β＝1；步骤(6)、修改tabu_c；设tabu_c存储第c只蚂蚁已经过的点要素，从而Q_a‑tabu_c表明第c只蚂蚁下一步允许选择的点要素；步骤(7)、注记适应度评价；本发明的适应度评价函数，如公式(4)所示；评价第a个蚁群每个蚂蚁所搜索得到的注记方位集合的优劣程度，选取评价函数结果值大的作为结果注记，存入FinalResultList中；完成一个蚁群遍历循环后，进入下一个蚁群循环，直至遍历完所有的蚁群；$E_{\left(i\right)}=\underset{c=1}{\overset{Q_a}{\Sigma }}{E}_{\left(\mathrm{ci}\right)}---\left(4\right)$其中，E_(c)表示c蚂蚁在该多点注记关联组中所选取的点要素适应度函数，E_(ci)表示c蚂蚁在i点要素上的适应度函数，E_(ci)＝w_冲突E_冲突(ci)+w_位置E_位置(ci)+w_关联度E_{关联度(ci)}，权重取值w_冲突＝100、w_位置＝1、w_关联度＝10；E_位置(ci)＝η_iMax‑η_iSelected，η_iMax为i点要素的待选注记优先级最大值，η_iSelected为i点要素的选定的注记优先级值，Distance_{(SelectedLabelToFuture)}为i点要素的选定的注记与i点要素的距离，Distance_(max)为i点要素的待选注记与对应i点要素的最大距离。