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.

Keywords:Combinatorial Optimization, Ant Colony Algorithm, Submodular Function, Materials Procurement

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

罗亮¹，罗明²，李小平¹，张馨文¹，周瑞¹

¹西安邮电大学理学院，陕西 西安

²甘肃临夏市实验小学，甘肃 临夏

收稿日期：2018年4月6日；录用日期：2018年4月18日；发布日期：2018年4月25日

摘 要

物资采购流行性预测是现代物流中的一个重要环节，是一种典型的组合优化问题。为使物流生产达到最佳效果，提出了一种基于下模函数下的蚁群算法，对物资采购中的流行性预测问题作出解答。该蚁群算法结合了贪婪算法是对一般蚁群算法的改进，最后以实验表明该算法在解决物资采购流行性预测问题是有效的。

关键词 :组合优化，蚁群算法，下模函数，物资采购

Copyright © 2018 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

物资采购是现代物流环节中非常重要的一环，而在物资采购环节中起决定性作用是物资采购流行性预测问题。为使物流生产达到最佳配置，本文提出如下物资采购流行性预测问题：来自不同地区不同城市或地域的采购商对某一集团公司的物资进行采购，对于不同的采购商要在某一特定的销季用最畅销的物资获得最大的利益，而对于集团公司，对不同的采购商采购的物资种类进行预测从而有计划有侧重的生产，致使生产出来的产品种类更大限度的满足采购商的需求，同时生产出的产品得到最小化浪费。此问题可进一步描述如下：

有来自n个地区的采购商对某集团公司的m中物资进行多次预选购，从预选购的n个集合选出最受欢迎，最流行的一种或q种产品进行重点生产，使达到最大化产销平衡，双方获得最大利益的状态。

需要说明的是本文所提出的问题可以应用文献 [1] 中提出一种近似算法(其中主要用了贪婪算法)对每个采购商根据自己的条件对m种物资分别选购，从而在其每个采购集合 $S_i$ 中重叠最多的元素作为重点产品生产。但是若要采取此算法来解决本文提出的问题会产生以下负面影响：

时间跨度过小，起不到预测效果，造成很大偏差；

采购商之间没有参照，造成对每种物资生产规模过小，产品种类过多，形不成大批量生产，造成资源浪费，资金得不到很快的回轮。

因此在本文将文献 [1] 中提出的算法作为解决。

整体问题的算法的一部分具体体现为贪心算法的结果作为初始预测结果，而更多的采用蚁群算法作为问题解决的主体算法对贪心结果进行优化，在整个过程中联合下模函数对算法中对应参数给予修正。

本文结构作如下安排。引言部分主要介绍物资采购流行性预测问题的背景及其问题阐述。第1节对本文主要涉及到的相关概念进行说明。第2节提出解决问题的蚁群算法并进行分析同时对问题的解决得出蚁群算法。第3部分为实验部分。第4部分为结论。

2. 预备知识

蚂蚁算法(ant algorithm)是一种源于大自然中生物世界的新的仿生类算法作为通用型随机优化算法，它吸收了昆虫王国中蚂蚁的行为特性通过其内在的搜索机制，在一系列困难的组合优化问题求解中取得了成效。

蚂蚁算法在著名的旅行商问题(TSP) [2] 信息融合 [3] 和工件排序问题 [4] ，制造业 [5] 以及在交通运输领域中 [6] [7] [8] [9] 取得成效以来，已陆续渗透到其它问题。本文进一步将这种新型的生物优化思想扩展到物资采购流行性预测问题中。

在应用蚂蚁算法求解物资采购流行性预测问题中还要用到非减下模获利函数，在微观经济学中认为买方的物品估价函数满足边际效用递减法则，而这一观点是被广泛接受的，而边际效用递减规律的理论基础则是非减下模函数。其主要用于初值的设定以及在蚂蚁算法中相关信息素的调整。非减下模函数定义如下：

定义 [10] ：设 $V=\left\{1,2,\cdots ,n\right\}$ 为一有限集， $\Omega =\left\{X|X\subseteq V\right\}$ 表示由N的所有子集组成的集合，若集函数f是 $\Omega \to R$ 满足：

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);$

则称f为 $\Omega \to R$ 的非减下模函数。

3. 问题的解决

3.1. 蚁群算法设计

在算法设计之前必须对算法初始状态以及相关数据进行设定：1) 要对参数初始化(包括时间，最大循环次数，蚂蚁个数，节点个数，初始节点信息素等)，2) 蚂蚁状态转移公式。

3.1.1. 参数初始化

为更准确预测，对每个采购商限定资金上限，对于第i个采购商，他的采购资金上限为 $L_i$ ，同时为确定每个节点初始信息量，第一次采购中采取贪心算法，令 $S_i$ 为第i个采购商的物资集。令时间 $t=0$ 和循环次数 $N_0=0$ ，设置最大循环次数 $N_{c\max }$ ，将m个蚂蚁置于n个节点上，这时我们将不同地区的采购商作为节点构造二部图(令有向图的每条(i,j)表示第j种物资被第i个蚂蚁采购。)初始化信息量由第一次的采购中采用边际效益最大的贪婪原则按照如下算法进行初值的确定：

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}{\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\}$ 。 ${\displaystyle \sum _{k\in S_i}{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(t0)$

next j

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

将蚂蚁状态转移概率公式定义为：

$P={\left[p_j^{\left(i\right)}\right]}^{\alpha }{\left[{\eta }_j^{\left(i\right)}\right]}^{\beta }/{\displaystyle \sum _{s\in c-tabu\left(i\right)}\left[{\tau }_s^{\left(i\right)}\right]{\left[{\eta }_s^{\left(i\right)}\right]}^{\beta }}$

其中C为物资集，tabu(i)为第i个蚂蚁的禁忌表;a为信息启发式因子，表示轨迹的相对重要性即积累信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁倾向于选择其它蚂蚁经过的路径，从侧面又反映了流行趋势。在本例中由于是不同地域之间的相互参考，a为相对敏感的参数；b为期望启发式因子，在本例中

与价值有很大关系，反映了蚂蚁对价格的受重视程度； ${\eta }_j^{\left(i\right)}\left(t\right)$ 表示蚂蚁对于j物资的能见度且 ${\eta }_j^{\left(i\right)}\left(t\right)=\frac{1}{c_j^{(i)}}$

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

区， $c_j^{\left(i\right)}$ 越小，则 ${\eta }_j^{\left(i\right)}\left(t\right)$ 越大，而在一个经济较发达地区，的影响程度要比欠发达地区显得迟钝一些，所以对于参数b在该地区稍小一点。 ${\tau }_j\left(t\right)$ 表示t时刻j节点的信息量，具体计算公式为

${\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+n\right)$ 表示对每只蚂蚁对c中的物资做完选择后 $t+n$ 时刻j节点处的信息素的改变量。具体计算公式为

$\Delta {\tau }_j\left(t\right)=1/M,\Delta {\tau }_j^{\left(i\right)}\left(t\right)=l\left[f\left(S_i\right)-f\left(S_i/j\right)\right]$ (2)

其中 $M={\displaystyle \sum _{k=1}^n\Delta {\tau }_j^{\left(k\right)}\left(t\right)}$ ，M表示边际效益之和， $f(·)$ 为单调下模获利函数，r为挥发因子。

根据以上分析给出求解物资采购流行性预测问题的蚁群算法。

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

Step1: 参数初始化，令时间 $t=0$ ，设置最大循环次数 $N_{c\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{and}{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{and}{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\max }$ 转入step2，否则结束。

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

1) 流行元素的产生

$\begin{array}{l}Do{N}_c<n_{c\max }\\ forj=1tom\\ tabu(i)=0\\ fori=1ton\\ ifj\in \{c-tabu(i)\}and{p}_j^{(i)}>p_{0}then\\ \{tabu(i)\}=\{tabu(i)\}+j\\ ifj\notin S_{i}then{S}_i=S_i\cup j\\ ifj\in S_{i}then{S}_i/j\end{array}$

$\begin{array}{l}ifj\in S_{i}then{\tau }_j^{(i)}((t_0+j)=(1-\xi ){\tau }_j^{(i)}((t_0+i-1)+\Delta {\tau }_j^{(i)}((t_0+i-1)\\ else{\tau }_j^{(i)}((t_0+j)={\tau }_j^{(i)}((t_0+i-1)-{\tau }_j^{(i)}((t_0+i-1)\\ nexti\\ {\tau }_j^{(i)}((t_0+j)=(1-\rho ){\displaystyle \sum _{i=1}^n{\tau }_j^{(i)}((t_0+j)+\rho \Delta {\tau }_j^{(i)}((t_0+j)}\\ nextj\\ N_c=N_c+1\\ EndDo\end{array}$

2) 对流行元素的排序

$\begin{array}{l}forj=1tom\\ fori=1ton\\ ifj\in S_{i}thenP(j)=P(j)+1\\ nexti\\ putoutP(j)\\ nextj\end{array}$

对于 $P\left(j\right),j=1,2,\cdots ,m$ 从大到小排序，设为 $P_1,P_2,\cdots ,P_m$ 得最流行元素 $P_{\max }=P_1$ 。前r个流行元素为 $P_1,P_2,\cdots ,P_r$ 。

4. 实验

在初始成本的选取过程中随机产生了23到34之间的数，作为市场物资价值矩阵。

物资价值矩阵

$\begin{array}{l}\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 =\mathrm{0.2.}$

最终结果为：

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

5. 结论

通过蚁群算法在对某一销季物资的流行元素做出判断来有计划的进行生产，而对于购买商，没有盲目的购进物资，而是参照了其他人或地域商人的意见看法，销售趋势，有取有舍最大限度的利用销售旺季抓住商机赢得最大的利润。在整个过程中表现出了很大的可行性和优点。第一初始阶段考虑到购买商的利益关系，用下模函数为获利函数结合贪婪算法，初步得到总的物资种类以及物资储备；第二在蚁群算法过程中考虑到了商家的让利举动对应了蚁群选购活动中信息素的改变，很大程度上模拟了现代商业活动。

资助信息

国家自然科学基金–数学天元基金(11626187)；陕西省教育厅科研专项基金(16JK1708, 16JK1694)。

文章引用

罗 亮,罗 明,李小平,张馨文,周 瑞. 物资采购流行性预测问题的蚁群算法
A Colony Algorithm for Commodity Purchase Epidemic Forecast Problem[J]. 应用数学进展, 2018, 07(04): 328-333. https://doi.org/10.12677/AAM.2018.74040

参考文献