1.一种基于快收敛式蚁群算法的学校选址方法,其特征在于,包括:对学校进行初选址,得到多个备选学校地址,对每个备选学校地址设置对应的学校服务区域,在学校服务区域内生成样本居民;
通过快收敛式蚁群算法,计算学校服务区域内每一个样本居民与对应备选学校地址之间的最佳路径,根据每个学校服务区域的最佳路径分布,从多个备选学校地址中选取实际学校地址;
所述快收敛式蚁群算法,包括:
以学校服务区域内的路口作为节点,连接路口的道路作为边得到无向图;以无向图上的样本居民所在位置作为起点,将备选学校地址作为终点;
经过多轮迭代,在满足停止条件时,输出起点与终点之间距离最短的路径作为最佳路径;每一轮迭代包括状态转移阶段和信息素更新阶段,其中:状态转移阶段中,设置蚂蚁从起点出发向终点移动;在移动过程中,引入距离引导因子和方向耦合因子计算蚂蚁移动至下一个节点的转移概率;所述距离引导因子表征节点与终点之间的直线距离;当前节点朝向下一个节点的方向为第一方向,当前节点朝向终点的方向为第二方向,所述方向耦合因子表征第一方向和第二方向之间的偏差程度;
信息素更新阶段中,引入概率函数计算被选中的蚂蚁在无向图中的边留下的信息素浓度,边的信息素浓度越高,蚂蚁移动通过相应的边移动至下一节点的转移概率越高;所述概率函数中引入贪婪因子,所述贪婪因子表征随着迭代轮数的增加,信息素浓度的衰减程度。
2.根据权利要求1所述的基于快收敛式蚁群算法的学校选址方法,其特征在于,所述对每个备选学校地址设置对应的学校服务区域,包括:以备选学校地址为圆心,以标准距离为半径形成的区域为学校服务区域。
3.根据权利要求1所述的基于快收敛式蚁群算法的学校选址方法,其特征在于,所述在学校服务区域内生成样本居民,包括:样本居民的位置分布,与学校服务区域内的实际居民的分布一致,样本居民的数量与学校服务区域内的实际居民的数量成正比。
4.根据权利要求1所述的基于快收敛式蚁群算法的学校选址方法,其特征在于,所述引入距离引导因子和方向耦合因子计算蚂蚁移动至下一个节点的转移概率,包括:所述转移概率,采用如下公式计算:
α β α β
Pij=(τijηijρjσij)/(∑k∈Kτikηikρk),其中,Pij表示蚂蚁从节点i移动至节点j的转移概率,τij表示节点i和节点j之间的边上的信息素浓度,α表示信息启发因子,ηij表示从节点i移动至节点j的期望值,β表示期望值启发因子,ρj表示节点j对应的距离引导因子,σij表示从节点i移动至节点j对应的方向耦合因子,K表示蚂蚁在节点i时下一个可移动的节点k的集合,集合K中不包括蚂蚁已经移动过的节点;ηij=1/Cij,Cij=dij/vij,Cij表示节点i和节点j之间的边的成本值,dij表示节点i和节点j之间的边的长度,vij表示样本居民经过节点i和节点j之间的边的移动速度,与节点i和节点j之间的边的通畅程度正相关。
5.根据权利要求4所述的基于快收敛式蚁群算法的学校选址方法,其特征在于,所述距离引导因子,采用如下公式计算:j≠t时,采用:ρj=1/Ljt;
j=t时,采用:ρj=1,
其中,Ljt表示从节点j至终点t的直线距离;
所述方向耦合因子,采用如下公式计算:
0.5 0.5
σij=e^(xi,jxi,t/||xi,j|| ||xi,t|| ),其中,e表示自然对数,xi,j表示从节点i指向节点j的向量,xi,t表示从节点i指向终点t的向量。
6.根据权利要求4所述的基于快收敛式蚁群算法的学校选址方法,其特征在于,所述引入概率函数计算被选中的蚂蚁在无向图中的边留下的信息素浓度,包括:所述信息素浓度,采用如下公式计算:
τij(s+1)=(1‑r) τij(s+1)+△τij(s),其中,τij(s+1)表示第s+1轮迭代中节点i和节点j之间的边上的信息素浓度,r表示信息素挥发系数,△τij(s)表示在第s轮迭代中被选中的蚂蚁在节点i和节点j之间的边上留下的信息素浓度。
7.根据权利要求6所述的基于快收敛式蚁群算法的学校选址方法,其特征在于,被选中的蚂蚁m在节点i和节点j之间的边上留下的信息素浓度,采用如下公式计算:m
△τij(s)=Q/Cm(s),
m
其中,△τij (s)表示第s轮迭代中蚂蚁m在节点i和节点j之间的边上留下的信息素浓度,Q表示信息素总量,Cm(s)表示第s轮迭代中蚂蚁m在无向图上的完整移动路径的成本值之和,采用如下公式计算:C=d/v,
其中,C表示成本值,d表示一轮迭代中蚂蚁在无向图上的完整移动路径的长度,v表示样本居民的移动速度。
8.根据权利要求7所述的基于快收敛式蚁群算法的学校选址方法,其特征在于,所述概率函数,采用如下公式:蚂蚁m到达终点且移动路径最短时,采用:Zm(s)=1;
s
蚂蚁m到达终点且移动路径不是最短时,采用:Zm(s)=ελ,s
其中,Zm(s)表示第s轮迭代中蚂蚁m被选中的概率,ε表示贪婪因子初始系数,λ 表示贪婪因子衰减系数。
9.根据权利要求1所述的基于快收敛式蚁群算法的学校选址方法,其特征在于,所述以无向图上的样本居民所在位置作为起点,将备选学校地址作为终点,还包括:以无向图上的样本居民所在位置作为起点,将备选学校地址作为第一终点,将样本居民的工作地点作为第二终点;所述无向图包括样本居民的工作地点,样本居民的工作地点与学校服务区域内的实际办公楼宇的分布一致,工作地点的数量与样本居民的数量一致;
所述输出起点与终点之间距离最短的路径作为最佳路径,还包括:起点与第一终点之间的路径作为第一段路径,第一终点与第二终点之间的路径作为第二段路径,将第一段路径和第二段路径之和最短的路径作为最佳路径;
所述状态转移阶段中,设置蚂蚁从起点出发向第一终点移动,到达第一终点后出发向第二终点移动。
10.一种基于快收敛式蚁群算法的学校选址装置,其特征在于,包括:选址单元、筛选单元和蚁群算法单元,其中:所述选址单元,用于对学校进行初选址,得到多个备选学校地址,对每个备选学校地址设置对应的学校服务区域,在学校服务区域内生成样本居民;
所述筛选单元,用于通过快收敛式蚁群算法,计算学校服务区域内每一个样本居民与对应备选学校地址之间的最佳路径,根据每个学校服务区域的最佳路径分布,从多个备选学校地址中选取实际学校地址;
所述蚁群算法单元,用于执行所述快收敛式蚁群算法,包括:
以学校服务区域内的路口作为节点,连接路口的道路作为边得到无向图;以无向图上的样本居民所在位置作为起点,将备选学校地址作为终点;
经过多轮迭代,在满足停止条件时,输出起点与终点之间距离最短的路径作为最佳路径;每一轮迭代包括状态转移阶段和信息素更新阶段,其中:状态转移阶段中,设置蚂蚁从起点出发向终点移动;在移动过程中,引入距离引导因子和方向耦合因子计算蚂蚁移动至下一个节点的转移概率;所述距离引导因子表征节点与终点之间的直线距离;当前节点朝向下一个节点的方向为第一方向,当前节点朝向终点的方向为第二方向,所述方向耦合因子表征第一方向和第二方向之间的偏差程度;
信息素更新阶段中,引入概率函数计算被选中的蚂蚁在无向图中的边留下的信息素浓度,边的信息素浓度越高,蚂蚁移动通过相应的边移动至下一节点的转移概率越高;所述概率函数中引入贪婪因子,所述贪婪因子表征随着迭代轮数的增加,信息素浓度的衰减程度。