当前位置:文档之家› 最大-最小蚁群算法在宿舍优化安排问题中的应用

最大-最小蚁群算法在宿舍优化安排问题中的应用

最大-最小蚁群算法在宿舍优化安排问题中的应用

用于寻找最短路径的蚁群算法来源于蚂蚁寻食的行为。蚁群寻找食物时会派出一些蚂蚁分头在四周游荡,如果一只蚂蚁找到食物,它就返回巢中通知同伴并沿途留下“信息素”作为蚁群前往食物所在地的标记。信息素会逐渐挥发,如果两只蚂蚁同时找到同一食物,又采取不同路线回到巢中,那么比较绕弯的一条路上信息素的气味会比较淡,蚁群将倾向于沿另一条更近的路线前往食物所在地。蚁群算法设计虚拟的“蚂蚁”,让它们摸索不同路线,并留下会随时间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原则,即可选择出最佳路线。

随着学校规模的扩大,学生人数也逐渐增加,在安排学生宿舍方面也越来越复杂。在实现宿舍优化安排时,我们要解决的问题是,把每一个学生分配到宿舍中,同一班级的学生尽量安排在同一宿舍,同一年级或专业的尽量安排在同一层或同一栋,使用的宿舍数量尽可能少且条件较差的宿舍尽量少用。

这是一个具有求解规模大、约束条件复杂以及本质不断变化等特点的问题。蚁群算法是一种模拟进化算法,在求解过程中利用其正反馈的特点,能够加速向较好解收敛。因此我们采用最大-最小蚁群算法来实现。

为了模拟蚂蚁的行为,首先引入如下记号:

m——蚁群中蚂蚁数量;

s——蚂蚁的内部状态中的要求数,即需要分配宿舍的学生数量;n——宿舍数量;

list——依次记录蚂蚁到访过的宿舍编号,即记录蚂蚁的路径,编号不会重复出现;

b——记录蚂蚁到访过的宿舍数量,重复出现的宿舍不会重复记录;

a(t)——蚂蚁的内部状态,即学生情况列表,记录学生的性别、班别、年级、专业、人数;

c(t)——宿舍情况列表,记录各宿舍的硬件情况,即床位数、所处位置、是否带卫浴、新旧程度、安排学生入住情况等内容;

τij——边(i,j)上的信息素轨迹强度;

△τij——蚂蚁k在边(i,j)上留下的单位长度轨迹信息素量;pkij——蚂蚁k的转移概率,i是当前宿舍,j是下一个要访问的宿舍;

每只蚂蚁都是具有如下特征的简单主体:

(1)每只蚂蚁都记忆着所有学生的情况,即拥有学生情况列表;(2)蚂蚁是依据它记忆的学生情况表来选择宿舍的,但满足条件的宿舍可能很多,这种情况下,它以概率的方式选择宿舍,即前进的方向,这个概率受轨迹上的信息素量影响;

(3)为了避免重复安排,蚂蚁必须记忆哪些学生已经安排在哪些宿舍;

(4)当蚂蚁所记忆的学生全都安装完毕,或再无能满足条件的宿舍时,该蚂蚁的搜索结束。区分两种情况:一是蚂蚁记忆的所有学生全部分配完毕,则成功建立一条搜索路径。二是,再无能满足学生条件的宿舍时,蚂蚁建立搜索路径失败,如果在路径上已经留下信息素,则将其全部删除,销毁该蚂蚁。

下面给出简单的流程。

(1)初始化a(t){初始化蚁群}

(2)评价a(t){根据目标函数对每只蚂蚁的适应度做出评价} (3)释放信息素{根据适应度,对蚂蚁所经过的路径按一定的比例释放信息素。适应度越高,所释放的信息素越多}

(4)蚂蚁移动{蚂蚁依据前面蚂蚁所留下的信息素和自己的判断选择路径}

(5)信息素的挥发{信息素会随着时间不断消散}

初始时刻,各条路径上的信息素量相等,设■(c为常数)。蚂蚁■在运动过程中根据各条路径上信息素量决定转移方向。蚂蚁系统所使用的状态转移规则被称为随机比例规则,它给出了位于宿舍i 的蚂蚁k选择移动到宿舍j的概率。根据李士勇在《蚁群算法及其应用》一书的描述(参考文献[5]),在t时刻,蚂蚁k在宿舍i选择宿舍j的转移概率■为

其中■表示蚂蚁k下一步允许选择的宿舍。由上式可知,转移概

下载文档原格式(Word原格式,共5页)
相关文档
  • 蚁群优化算法应用

  • 蚁群优化算法及其应用

  • 蚁群优化算法

  • 最大最小距离算法

相关文档推荐: