基于蚂蚁算法的物流平面选址问题研究
来源:用户上传
作者: 程秀彬 许晓兵 尚 洁
[摘要] 文章把蚂蚁算法引入到物流平面选址问题中，并获得满意解。通过实例证明其比混沌优化算法与Dixon算法相结合的混合算法及模拟褪火算法在平面选址问题中更为精确和有效。
[关键词] 蚂蚁算法平面选址问题混合算法模拟褪火算法
一、引言
物流选址是生产运作战略的一个重要内容。人们对于选址问题的研究由来已久，德国经济学家Weber是第一个研究制造活动选址的学。到了20世纪80年代和90年代，特别是随着经济全球化的发展，全球化范围的选址问题受到了人们的重视。
二、物流平面选址问题
给定平面上的个点:,现要确定一点，使得：
（1)最小
（2)最小
这一类物流平面选址问题是一类较为困难的优化问题。文献[3]给出了一种把混沌优化算法与Dixon算法相结合的混合算法。其基本思想是利用混沌搜索得到新的迭代点以克服在局部极小点的搜索。同时在用Dixon法搜索时，一旦在目标函数值改进不大时，则用混沌变换产生新的迭代点。但该算法不够精确。为此，本文提出利用蚂蚁算法来解决这类物流平面选址问题。
三、蚂蚁算法原理
蚂蚁算法(ant algorithm)是一种源于生物界的新的仿生类算法，据昆虫学家的观察和研究发现，蚂蚁有能力在没有任何可见提示下找出从其窝巢至食物源的最短路径，并能随环境的变化而变化，适应性地搜索新的路径，产生新的选择.蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物──信息激素(pheromone),使得一定范围内的其他蚂蚁能够察觉到并由此影响它们以后的行为.当一些路径上通过的蚂蚁越来越多时，其留下的信息激素轨迹(trail)也越来越多，以致信息素强度增大(当然，随时间的推移信息素会逐渐减弱),后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，这种选择过程被称之为蚂蚁的自催化行为(autocatalytic behavior）。
四、算法设计及算例
我们假设有只蚂蚁，对于任意一只蚂蚁，定义其评价函数值为相应的目标函数值（或），其中是第只蚂蚁的当前位置。记
转移概率
其中是蚂蚁邻域内的信息素强度，为体现相对重要性的非负参数。
优化过程可借助个蚂蚁从其初始状态开始的不断移动来进行：
当时，蚂蚁按照概率从其邻域移至蚂蚁的邻域；
否则，蚂蚁作邻域搜索，搜索半径为r。
即每个蚂蚁在运动过程中，转移到其他蚂蚁处，或者进行其邻域搜索。不难看出，只要蚂蚁个数足够的多，这种搜索方法可渐进收敛到问题的全局最优解。
通过不断地重复上述过程，使算法能找到问题的最优解或较好解。
解物流平面选址问题的蚂蚁算法流程可简述为
Begin
;（为迭代步数或搜索次数）
初始化;
Repeat
将各蚂蚁置于定义域的等分点处;
按转概率转移各蚂蚁;
更新信息素轨迹;
纪录当前的最佳蚂蚁位置;
Until大于预定的迭代次数;
End.
笔者用蚂蚁算法计算了文献[3]中的例子
例：给定平面上3个点，则文献[3]中的结果与蚂蚁算法的计算结果如下表所示。
计算结果表明，蚂蚁算法得到的结果优于文献[3]中的混合算法和模拟退火算法得到的结果。
五、结束语
自从蚂蚁算法在著名的旅行商问题(TSP) 和二次分配问题(QAP) 上取得成效以来，已陆续渗透到其它问题领域中，如：车辆调度问题、机器人、电子通信网络问题等等。这种来自自然界的随机搜索寻优方法目前已在许多方面表现出良好的性能，它的正反馈性和协同性使之可用于分布式系统，其隐含的并行性更是具有极强的发展潜力，其求解的问题领域也在进一步扩大，如一些约束型问题和多目标问题等。自1998年于比利时布鲁塞尔召开了第一届蚂蚁优化国际研讨会以来，该主题已常常被列入一些国际性学术会议（尤其是人工智能领域）的专题研讨中，并由此使得这种带有构造性特征的搜索方法产生了广泛的影响和应用。
参考文献:
[1]马良:来自昆虫世界的寻优策略――蚂蚁算法[J].自然杂志, 1999,21(3):161-163
[2]陈荣秋马市华:生产与运作管理[M].北京:高等教育出版社, 1999
[3]蒋良奎:平面选址问题的一种混合算法[J].上海海运学院学报, 1999,20(4): 98-102
[4] Kirkpatric S, et al.. Optimization by Simulated Annealing[J]. Science, 1983, 220 (4598): 671-679
[5]路青汤齐:基于神经网络的物流中心选址模型研究, 商场现代化[J]2006,(484):148
转载注明来源:https://www.xzbu.com/3/view-1495305.htm
