﻿ 物资采购流行性预测问题的蚁群算法

# 物资采购流行性预测问题的蚁群算法A Colony Algorithm for Commodity Purchase Epidemic Forecast Problem

Abstract: Material procurement epidemic of modern logistics in the forecast is an important topic, and is a typical combinatorial optimization problem. To make the logistics of production to achieve the best results, a colony algorithm solving the problem of purchasing epidemic forecast is presented. This colony algorithm is an improved algorithm that is combined with the greedy algorithm. Finally, experimental results show that algorithm in solving the problem of purchasing epidemic forecast is valid.

1. 引言

2. 预备知识

1) $\forall X,Y\subseteq N$ ，若 $X\subseteq Y$ ，则有

$f\left(X\right)\le f\left(Y\right);$

2) $\forall X,Y\subseteq N$ ，总有

$f\left(X\right)+f\left(Y\right)\le f\left(X\cup Y\right)+f\left(X\cap Y\right);$

3. 问题的解决

3.1. 蚁群算法设计

3.1.1. 参数初始化

Step1 令 ${S}_{i}=0,i=1,2,\cdots ,n$

Step2 取 $k\in C$ ，使 ${\theta }_{ik}=f\left(S{}_{i}\cup \left\{{c}_{ki}\right\}\right)-f\left(S{}_{i}\right)=\underset{j\in C}{\mathrm{max}}\left\{f\left(S{}_{i}\cup \left\{{c}_{j}\right\}\right)-f\left(S{}_{i}\right)\right\}$

Step3 令 ${S}_{i}=S{}_{i}\cup \left\{{c}_{k}\right\}$$\underset{k\in {S}_{i}}{\sum }{p}_{k}{c}_{k}<{L}_{i}$ 转step2，否则转step5。

Step5 对于物资集C中的元素初始信息量按如下算法进行

for j = 1 to m

${t}_{0}=0$${\tau }_{j}\left({t}_{0}\right)=0$

for i = 1 to n

$j\in {S}_{i}$ ，则 ${\tau }_{j}\left({t}_{0}\right)={\tau }_{j}\left({t}_{0}\right)+1$

next i

output ${\tau }_{j}\left(t0\right)$

next j

3.1.2. 设定蚂蚁状态转移概率公式:

$P={\left[{p}_{j}^{\left(i\right)}\right]}^{\alpha }{\left[{\eta }_{j}^{\left(i\right)}\right]}^{\beta }/\underset{s\in c-tabu\left(i\right)}{\sum }\left[{\tau }_{s}^{\left(i\right)}\right]{\left[{\eta }_{s}^{\left(i\right)}\right]}^{\beta }$

(其中 ${c}_{j}^{\left(i\right)}$ 为i蚂蚁在j节点的市场价格)，由于 ${c}_{j}^{\left(i\right)}$ 的考虑要受到区域的限制，一般情况下在一个欠发达地

${\tau }_{j}\left(t+n\right)=\left(1-\rho \right){\tau }_{j}\left(t\right)+\Delta \tau \left(t+n\right)$ (1)

$\Delta {\tau }_{j}\left(t\right)=1/M,\text{\hspace{0.17em}}\Delta {\tau }_{j}^{\left(i\right)}\left(t\right)=l\left[f\left({S}_{i}\right)-f\left({S}_{i}/j\right)\right]$ (2)

3.1.3. 求解物资采购流行性预测问题的蚁群算法步骤

Step1: 参数初始化，令时间 $t=0$ ，设置最大循环次数 ${N}_{c\mathrm{max}}$ ，将蚂蚁置于n个节点上，其中j节点的初始信息量由1.11节中的贪婪算法求得；

Step2: 循环次数 ${N}_{c}={N}_{c}+1$

Step3: 蚂蚁的初始禁忌表索引号 $k=1$

Step4: 蚂蚁数目 $k=k+1$

Step5: 蚂蚁个体根据2.1.2中设定的状态转移概率公式计算概率选择元素 $j\in c-tabu\left(i\right)$ ，并进行禁忌表修改：

$j\in \left\{c-tabu\left(i\right)\right\}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}{p}_{j}^{\left(i\right)}>{p}_{0}$ ，则

$\left\{tabu\left(i\right)\right\}=\left\{tabu\left(i\right)\right\}+j$

$j\in \left\{c-tabi\left(i\right)\right\}\text{\hspace{0.17em}}\text{and}\text{\hspace{0.17em}}{p}_{j}^{\left(i\right)}<{p}_{0}$ ，则

$\left\{c-tabu\left(i\right)\right\}=\left\{c-tabu\left(i\right)\right\}+j$

Step6: 若集合c中元素每个蚂蚁未遍历完则转入step4，否则跳到step7。

Step7: 根据公式(1) (2)更新每个节点上的信息量；

Step8: 若 ${N}_{c}<{N}_{c\mathrm{max}}$ 转入step2，否则结束。

3.1.4. 蚁群算法具体程序设计

1) 流行元素的产生

$\begin{array}{l}Do\text{\hspace{0.17em}}{N}_{c}<{n}_{c\mathrm{max}}\\ for\text{\hspace{0.17em}}j=1\text{\hspace{0.17em}}to\text{\hspace{0.17em}}m\\ \text{\hspace{0.17em}}tabu\left(i\right)=0\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}for\text{\hspace{0.17em}}i=1\text{\hspace{0.17em}}to\text{\hspace{0.17em}}n\\ \text{\hspace{0.17em}}if\text{\hspace{0.17em}}j\in \left\{c-tabu\left(i\right)\right\}\text{\hspace{0.17em}}and\text{\hspace{0.17em}}{p}_{j}^{\left(i\right)}>{p}_{0}\text{\hspace{0.17em}}then\text{\hspace{0.17em}}\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\left\{tabu\left(i\right)\right\}=\left\{tabu\left(i\right)\right\}+j\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}if\text{\hspace{0.17em}}j\notin {S}_{i}\text{\hspace{0.17em}}then\text{\hspace{0.17em}}{S}_{i}={S}_{i}\cup j\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}if\text{\hspace{0.17em}}j\in {S}_{i}\text{\hspace{0.17em}}then\text{\hspace{0.17em}}{S}_{i}/j\end{array}$

$\begin{array}{l}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}if\text{\hspace{0.17em}}j\in {S}_{i}\text{\hspace{0.17em}}then\text{\hspace{0.17em}}{\tau }_{j}^{\left(i\right)}\left(\left({t}_{0}+j\right)=\left(1-\xi \right){\tau }_{j}^{\left(i\right)}\left(\left({t}_{0}+i-1\right)+\Delta {\tau }_{j}^{\left(i\right)}\left(\left({t}_{0}+i-1\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}else\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\tau }_{j}^{\left(i\right)}\left(\left({t}_{0}+j\right)={\tau }_{j}^{\left(i\right)}\left(\left({t}_{0}+i-1\right)-{\tau }_{j}^{\left(i\right)}\left(\left({t}_{0}+i-1\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}next\text{\hspace{0.17em}}i\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{\tau }_{j}^{\left(i\right)}\left(\left({t}_{0}+j\right)=\left(1-\rho \right)\underset{i=1}{\overset{n}{\sum }}{\tau }_{j}^{\left(i\right)}\left(\left({t}_{0}+j\right)+\rho \Delta {\tau }_{j}^{\left(i\right)}\left(\left({t}_{0}+j\right)\\ next\text{\hspace{0.17em}}j\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}{N}_{c}={N}_{c}+1\\ End\text{\hspace{0.17em}}\text{\hspace{0.17em}}Do\end{array}$

2) 对流行元素的排序

$\begin{array}{l}for\text{\hspace{0.17em}}j=1\text{\hspace{0.17em}}to\text{\hspace{0.17em}}m\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}for\text{\hspace{0.17em}}i=1\text{\hspace{0.17em}}to\text{\hspace{0.17em}}n\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}if\text{\hspace{0.17em}}j\in {S}_{i}\text{\hspace{0.17em}}then\text{\hspace{0.17em}}P\left(j\right)=P\left(j\right)+1\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}next\text{\hspace{0.17em}}i\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}put\text{\hspace{0.17em}}out\text{\hspace{0.17em}}P\left(j\right)\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}next\text{\hspace{0.17em}}j\end{array}$

4. 实验

$\begin{array}{l}\text{ }\left[\begin{array}{ccccccccccc}23& 24& 26& 28& 30& 30& 32& 23& 25& 29& 限量\end{array}\right]\\ \left[\begin{array}{ccccccccccc}24& 26& 27& 29& 30& 31& 35& 24& 27& 30& 170\\ 26& 24& 27& 32& 33& 32& 34& 25& 26& 29& 180\\ 25& 27& 29& 29& 32& 33& 33& 23& 26& 32& 170\\ 24& 26& 28& 29& 34& 32& 36& 23& 28& 31& 200\\ 23& 26& 27& 28& 31& 34& 33& 24& 25& 31& 170\\ 25& 25& 26& 30& 33& 31& 34& 24& 29& 30& 160\\ 24& 25& 28& 32& 32& 30& 33& 24& 25& 31& 170\\ 25& 29& 27& 28& 33& 30& 34& 23& 26& 31& 190\\ 25& 25& 27& 29& 31& 32& 34& 26& 27& 29& 210\end{array}\right]\end{array}$

$\left[\begin{array}{cccccccccc}{m}_{1}& {m}_{2}& {m}_{3}& {m}_{4}& {m}_{5}& {m}_{6}& {m}_{7}& {m}_{8}& {m}_{9}& {m}_{10}\\ 0& 2& 2& 1& 0& 1& 3& 1& 2& 1\\ 3& 0& 1& 4& 3& 2& 1& 2& 1& 0\\ 2& 3& 3& 1& 2& 3& 2& 0& 1& 3\\ 1& 2& 2& 1& 4& 2& 4& 0& 3& 2\\ 0& 2& 2& 0& 1& 4& 1& 1& 0& 2\\ 2& 1& 0& 2& 3& 1& 2& 1& 4& 1\\ 1& 1& 2& 4& 2& 0& 1& 1& 0& 2\\ 2& 5& 1& 0& 3& 0& 2& 0& 1& 2\\ 2& 1& 1& 1& 1& 2& 2& 3& 2& 0\end{array}\right]$

$\begin{array}{l}\tau \left(1\right)=4,\tau \left(2\right)=5,\tau \left(3\right)=7,\tau \left(4\right)=4,\tau \left(5\right)=7\\ \tau \left(6\right)=5,\tau \left(7\right)=6,\tau \left(8\right)=5,\tau \left(9\right)=6,\tau \left(10\right)=6\end{array}$

${p}_{0}=0.5,\rho =0.4,\alpha =0.8,\beta =0.6,l=\frac{n}{m},\xi =0.2.$

$5\to 7\to 9\to 10\to 3\to 2\to 4\to 8\to 1\to 6.$

5. 结论

[1] 罗亮, 贾欣鑫, 何尚录. 求解组合拍卖问题最大值的贪婪算法[J]. 黑龙江科技学院学报, 2008, 18(5): 382-384.

[2] 王书勤, 黄茜. 蚁群算法参数优化设置研究[J]. 信阳师范学院学报(自然科学版), 2012, 25(2): 262-265.

[3] 李艳灵, 李刚. 基于蚁群算法和粗糙集的信息融合教学评价[J]. 信阳师范学院学报(自然科学版), 2009, 22(4): 624-627.

[4] 陈义保, 姚建初, 钟毅芳, 等. 基于蚁群系统的工件排序问题的一种新算法[J]. 系统工程学报, 2002, 179(5): 476-480.

[5] Sdimanpura, M., Vratb, P. and Shankar, R. (2005) An Ant Algorithm for the Single Row Layout Problem in Flexible Manufacturing Systems. Computers & Operations Research, 32, 583-598.
https://doi.org/10.1016/j.cor.2003.08.005

[6] 崔学丽, 马良, 范炳全. 车辆路径问题(VRP)蚂蚁搜索算法[J]. 系统工程学报, 2004, 19(4): 418-422.

[7] 陈昌富, 龚晓南. 启发式蚂蚁算法及其在高填石路堤稳定性分析中的应用[J]. 数学的实践与认识, 2004, 34(6): 89-92.

[8] 闻育, 吴铁军. 基于蚂蚁算法的城域交通控制实时滚动优化[J]. 控制与决策, 2004, 19(9): 1057-1059.

[9] Chen, C.-H. and Ting, C.-J. (2006) An Improved ant Colony System Algorithm for the Vehicle Routing Problem. Journal of Chinese institute of Industrial Engineers, 23, 115-116.

[10] Sviridenko, M. (2004) A Note on Maximizing a Submodular Set Function Subject to Knapsack Constraint. Operation Rrdrstvhi Lryyrtd, 32, 41-43.

Top