10.4　蚁群算法在科学研究中的应用

例10.1　已知n个城市之间的相互距离，现有一个推销员必须遍访31个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短，即旅行商问题（TSP）。

31个城市坐标为：

解：

得到如图10.3所示的结果，函数anttsp的源程序如下。

图10.3　最佳路线

例10.2　有一个货物配送中心需要用车辆向8个配送点进行配货。设每辆车出车的单位成本为a₀，行驶的单位成本为a，每辆车限重8t，行驶最长距离为450km，每个配送点的货物需要量及配送中心与各配送点的距离分别见表10.1和表10.2，其中0代表配送中心，其余为各配送点。请设计最佳的配送方案，要求车辆从配送中心出发最后又回到配送中心。

表10.1　各配送点的货物需要量

表10.2　配送中心及各个配送点之间的距离（x，y）　km

解：首先建立数学模型，设出车的单位成本用a₀表示；车辆行驶的单位成本用a表示；第i个配送点的货物需求量用q_i表示；配送点i与j之间的距离用d_i表示；车辆到达第i个配送点的时间用t_i表示；配送货物所需的车辆数目用m表示；单辆运输车的最大载重量用Q表示；极限行驶路程用L表示。配送中心与n个配送点的编号分别为1，1，2，…，i，…，n＋1，配送的目标函数为

，即要求车辆从配送点出发，最后又回到配送点

，　　k＝1，2，…，m，即每辆车的货不能超过载重量

，即每辆的行驶距离不超过极限

不失一般性，此问题实际上就是求在满足条件下车辆行驶的最短路径。现用蚁群进行求解。如果用一辆车配送，其他参数m＝30，Alpha＝1，Beta＝5，Rho＝0，Q＝100，iter_max＝100，则对例10.1中的程序稍作修改，便可进行计算，结果如下：

图10.4所示为最佳路径：1—4—6—8—1—3—1—2—1—7—1—5—1—9—1，共为1115km。

图10.4　一次配送路径图

程序主要修改处：

①计算已配送点的总路径

②从未配送点中找出符合条件的配送点

③如果没有符合条件的配送点，则回到配送中心，并准备下一次配送

如果有两车辆配送，则结果为：1—3—5—1—7—1—9—1，1—2—4—6—1—8—1，共为1260km。

当然在实际中，要比本例设定的情况复杂，比如对货物时间限制、剩余的货物可以在回来的路上卸下等。对这些问题都可以根据本例的思路进行计算。

例10.3　蚁群算法也可以用于函数的优化。试用蚁群算法优化下列函数：

maxf（x）＝∣（1－x）x²sin（200πx）∣，　　x∈［0，1］

解：此函数有许多局部极值，其图像见图10.5。

图10.5　所求函数的图像

利用蚁群算法求解问题的关键是设计好蚁群系统。假设本例中优化结果要达到自变量的小数点后第7位。设计9层城市，其中第一层、末层分别为起始和终止城市，而中间的7层城市，每层城市分别有10个城市，分别代表数字0～9，而每层从左到右代表小数点后的十分位，百分位，…，并且让每只蚂蚁只能从左往右移动，这样，从起始城市到终止城市的一次游走，就可以找到小位点后的各位数字。让m只蚂蚁经过一定次数循环寻找，就可以找到符合要求的结果。其中城市选择的概率计算公式为

其中，a为当前城市；b为下次选择城市，为这两个城市的信息素；为当前城市与下一层所有10个城市间的信息素。除了起始城市与下一层之间只有10个信息素，每层间的信息素为10×10的矩阵，并且蚂蚁在游走的过程中，要不断地在经过的路径上减弱所留下的信息素，其计算公式为

其中，k代表层数；ρ为（0，1）间的常数，代表信息素减弱的速度；τ₀为初始信息素。这个过程称为信息素的局部更新。当所有m只蚂蚁按上述过程完成一次循环后，就对信息素进行全局更新。首先对每只蚂蚁经过的过程解码，得到自变量的值，然后计算函数值，并得到其中的最小值，再按下列公式更新信息素：

其中，α为（0，1）的常数；为最小函数值的倒数。

至此就完成了一次循环。反复进行上面的步骤直到达到指定的循环次数或得到的解在一定循环次数后没有改进。

因为对于任何一个连续函数优化问题都可以通过一定的变换而成为一个在［0，1］上的函数最小化问题，所以上述的设计不失一般性，并且也可以用于多元函数的优化问题。

根据以上的思路，编制以下的程序就可以进行计算：

一次计算结果为：x＝0.148057150889282时，有最大值0.667444400000000。

例10.4　为了解耕地的污染状况与水平，从3块由不同水质灌溉的农田里共取16个样品，每个样品均作土壤中铜、镉、氟、锌、汞和硫化物等7个变量的浓度分析，原始数据见表10.3。试用蚁群算法对16个样品进行分类。

表10.3　原始数据　mg/kg

解：首先通过MATLAB中的聚类函数，求出样品间的聚类情况。当用最小距离法时，样品间的聚类树见图10.6。可见根据不同的标准，可以有多种划分方法。

图10.6　样品聚类树

为了简单起见，本例用蚁群算法聚类时分为3类。

与例10.3的思路类似，设计17层城市，其中除了前后两座城市，其余各层均为3个城市，代表类别数。每只蚂蚁从左到右所找到的路径即代表各样品所对应的类别，而每次移动的路径，则受层间信息素和各样品与类之间的信息素的共同作用。每次移动后对路径间的信息素进行局部更新。

当所有m只蚂蚁按上述过程完成一次循环后，就对样品与各类别间的信息素进行全局更新。首先对每只蚂蚁经过的路径解码，得到各样品所对应的类别，由此计算优化函数，并得到最小值。根据函数最小值对应的路径更新样品与类别间的信息素。以上过程所涉及的计算公式与例10.3的类似，就不在列出。

优化函数为类内距离与类间距离的比值为最小，即分类时各类间的距离要大，但类内各样品间的距离要小：

其中

其中，x_ip为第i个样本的第p个属性；c_jp为第j个类中心的第p个属性。

根据蚁群算法的基本原理，可以编制相应的程序计算，结果得到如下的路径：2—2—2—1—1—1—1—1—1—1—1—1—1—3—1—1，所对应的函数值为0.5581。

实际上可以找到更好的分类，即1—1—1—1—1—1—1—1—1—3—3—3—1—2—1—1，所对应的函数值为0.4721。这两者的判别在于1、2、3、10、11、12这六个样本的划分，从分类树也可以看出其差异。

如果事先不知道聚类的数目，则可以根据样本间的距离矩阵确定一个阈值距离。当多个类之间的距离小于此值时，根据概率选择其中两个类的归并，而概率大小与路径的信息素有关，规定当两类之间的距离小于阈值时，信息素为1，否则为0。

计算结果如下：1　1　1　2　2　2　2　2　2　3　3　3　4　5　6　6，即分为6类。

例10.5　试用蚁群算法对下列二元函数进行优化：

minf（x，y）＝（x－1）²＋（y－2.2）²＋1

解：用蚁群算法对连续函数的优化，常规的方法是用多组蚁群，每组蚁群负责寻找一个自变量的最佳值。其步骤如下：

①初始化：根据每个自变量的范围，组成函数解的空间，并将蚁群随机设置在解空间中，设函数值就为信息素。

②蚁群转移规则：每只蚂蚁每次移动都是根据信息素大小来判断的，转移概率p为最大信息素（即最大函数值）与下一转移点的信息素（函数值）之差与最大信息素的比值。

③当p大于某个随机数时，进行全局搜索，即扩大函数值的范围，否则进行局部搜索。

④判断全局或局部搜索的结果是否超过自变量的边界，若超过，则将其置于边界。

⑤判断蚂蚁是否移动，即全局或局部搜索的结果是否比原来的值大，若是，则蚂蚁移动。

⑥更新信息素：←（1－ρ）＋f_i，其中f为函数值。

⑦至此，完成一次循环，直到达到一定的循环次数。

据此，可以编制相应的程序进行计算。限于篇幅不再列出程序，结果如图10.7所示。

图10.7　蚁群搜索结果