第二章_蚁群算法.ppt

《第二章_蚁群算法.ppt》由会员分享，可在线阅读，更多相关《第二章_蚁群算法.ppt（79页珍藏版）》请在三一办公上搜索。

1、第二章 蚁群算法,智能优化计算,2.1 群智能,智能优化计算,群智能（Swarm Intelligence,SI）人们把群居昆虫的集体行为称作“群智能”（“群体智能”、“群集智能”、“集群智能”等）特点 个体的行为很简单，但当它们一起协同工作时，却能够突现出非常复杂（智能）的行为特征。,2.1.1 群智能的概念,2.1 群智能,智能优化计算,描述 群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。特性 指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。,2.1.

2、2 群智能算法,2.1 群智能,智能优化计算,优点 灵活性：群体可以适应随时变化的环境；稳健性：即使个体失败，整个群体仍能完成任务；自我组织：活动既不受中央控制，也不受局部监管。典型算法 蚁群算法（蚂蚁觅食）粒子群算法（鸟群捕食）,2.1.2 群智能算法,2.2 蚁群优化算法原理,智能优化计算,蚁群的自组织行为“双桥实验”通过遗留在来往路径 上的信息素（Pheromone）的挥 发性化学物质来进行 通信和协调。,2.2.1 蚁群算法的起源,2.2 蚁群优化算法原理,智能优化计算,蚁群的自组织行为“双桥实验”,2.2.1 蚁群算法的起源,2.2 蚁群优化算法原理,智能优化计算,提出蚁群系统 19

3、92年，意大利学者M.Dorigo在其博士论文中提出 蚂蚁系统（Ant System）。近年来，M.Dorigo等人进一步将蚂蚁算法发展为一种通用的优化技术蚁群优化（ant colony optimization,ACO）。,2.2.1 蚁群算法的起源,蚂蚁从A点出发，随机选择路线ABD或ACD。经过9个时间单位时：走ABD的蚂蚁到达终点，走ACD的蚂蚁刚好走到C点。,2.2 蚁群优化算法原理,智能优化计算,2.2.2 蚁群算法的原理分析,蚁巢,食物,2.2 蚁群优化算法原理,智能优化计算,经过18个时间单位时：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。,2

4、.2.2 蚁群算法的原理分析,蚁巢,食物,最后的极限是所有的蚂蚁只选择ABD路线。（正反馈过程）,2.2 蚁群优化算法原理,智能优化计算,2.2.2 蚁群算法的原理分析,蚁巢,食物,假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继

5、续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。,2.2 蚁群优化算法原理,智能优化计算,2.2.2 蚁群算法的原理分析,基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例

6、如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。,2.2 蚁群优化算法原理,智能优化计算,2.2.2 蚁群算法的原理分析,TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离目标函数为其中 为城市1,2，n的一个排列，。,2.2.2 蚁群算法与TSP问题,2.2.2 蚁群算法与TSP问题,TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1 信息素值 也称信息素痕迹。2 可见度，即先验值。信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自

7、然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。,2.2.2 蚁群算法与TSP问题,蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。,2.2.3 初始的蚁群优化算法基于图的蚁群系统（GBAS）,初始的蚁群算法是基于图的蚁群算法，graph-based ant system,简称为GBAS，是由Gutjahr W J在2000年的Futu

8、re Generation Computing Systems提出的.算法步骤如下：STEP 0 对n个城市的TSP问题，城市间的距离矩阵为，给TSP图中的每一条弧 赋信息素初值，假设m只蚂蚁在工作，所有蚂蚁都从同一城市 出发。当前最好解是。,2.2.3 初始的蚁群优化算法基于图的蚁群系统（GBAS）,STEP 1（外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点 出发，用 表示蚂蚁s行走的城市集合，初始 为空集，。STEP 2(内循环)按蚂蚁 的顺序分别计算。当蚂蚁在城市i，若 完成第s只蚂蚁的计算。否则，若，则以概率，到达j，；若则到达重复STEP 2。

9、,2.2.3 初始的蚁群优化算法基于图的蚁群系统（GBAS）,STRP 3 对，若，按 中城市的顺序计算路径程度；若，路径长度置为一个无穷大值（即不可达）。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t。若，则。用如下公式对W路径上的信息素痕迹加强，对其他路径上的信息素进行挥发。得到新的，重复步骤STEP 1。,2.2.3 初始的蚁群优化算法基于图的蚁群系统（GBAS）,在STEP 3 中，挥发因子 对于一个固定的，满足并且 经过k次挥发，非最优路径的信息素逐渐减少至消失。,2.2.3初始的蚁群优化算法基于图的蚁群系统（GBAS）,以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城

10、市i到城市j的转移。算法中包括信息素更新的过程 1 信息素挥发（evaporation）信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，由 表示，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。2 信息素增强（reinforcement）增强过程是蚁群优化算法中可选的部分，称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群（m只蚂蚁）中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，挥发过程是所有弧都进行的，不于蚂蚁数量相关。这种增强过程中进行的信息素更新称为离线

11、的信息素更新。在STEP 3中，蚁群永远记忆到目前为止的最优解。,图的蚁群系统（GBAS）,可以验证，下式满足：即 是一个随机矩阵。,四个城市的非对称TSP问题，距离矩阵和城市图示如下：,2023/2/20,22,2.2.3 初始的蚁群优化算法基于图的蚁群系统（GBAS）,假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子。此时，观察GBAS的计算过程。矩阵共有12条弧，初始信息素记忆矩阵为：,2023/2/20,23,2.2.3 初始的蚁群优化算法基于图的蚁群系统（GBAS）,执行GBAS算法的步骤2，假设蚂蚁的行走路线分别为：当前最优解为，这个解是截止到当前的最优解，碰巧是实际最优解,2.2

12、.3 初始的蚁群优化算法基于图的蚁群系统（GBAS）,按算法步骤3的信息素更新规则，得到更新矩阵这是第一次外循环结束的状态。,2.2.3 初始的蚁群优化算法基于图的蚁群系统（GBAS）,重复外循环，由于上一次得到的W2已经是全局最优解，因此按算法步骤3的信息素更新规则，无论蚂蚁如何行走，都只是对W2路线上的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵这是第一次外循环结束的状态。,2.2.3 初始的蚁群优化算法基于图的蚁群系统（GBAS）,重复外循环，由于W2全局最优解，GBAS只记录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优

13、路线的信息素，同时进行挥发。第三次外循环后得到的信息素矩阵为：,2.2.3 初始的蚁群优化算法基于图的蚁群系统（GBAS）,蚂蚁以一定的概率从城市i到城市j进行转移，信息素的更新在STEP 3 完成，并随K而变化。假设第K次外循环后得到信息素矩阵，得到当前最优解。第K次循环前的信息素和最优解为，经过第K次外循环后，得到。由于蚂蚁的一步转移概率是随机的，从 到 也是随机的，是一个马尔可夫过程。,2.2.3 一般蚁群算法的框架,一般蚁群算法的框架和GBAS基本相同，有三个组成部分：蚁群的活动；信息素的挥发；信息素的增强；主要体现在前面的算法中步骤2和步骤3中的转移概率公式和信息素更新公式。,2.3

14、 基本蚁群优化算法,智能优化计算,解决TSP问题 在算法的初始时刻，将m只蚂蚁随机放到n座城市;将每只蚂蚁 k的禁忌表tabuk(s)的第一个元素tabuk(1)设置为它当前所在城市;设各路径上的信息素ij(0)=C（C为一较小的常数）;,2.3.1 蚂蚁系统的模型与实现,2.3 基本蚁群优化算法,智能优化计算,解决TSP问题 每只蚂蚁根据路径上的信息素和启发式信息（两城市间距离）独立地选择下一座城市：在时刻t，蚂蚁k从城市i转移到城市j的概率为、分别表示信 息素和启发式因子 的相对重要程度。,2.3.1 蚂蚁系统的模型与实现,下一步允许的城市的集合,2.3 基本蚁群优化算法,智能优化计算,解

15、决TSP问题 当所有蚂蚁完成一次周游后，各路径上的信息素将进行更新：其中，（0 1）表示路径上信息素的蒸发系数，Q为正常数，Lk表示第k只蚂蚁在本次周游中所走过路径的长度。,2.3.1 蚂蚁系统的模型与实现,2.3 基本蚁群优化算法,智能优化计算,算法流程,2.3.1 蚂蚁系统的模型与实现,2.3 基本蚁群优化算法,智能优化计算,初始参数 城市数30;蚂蚁数30；=1;=5;=0.1;最大迭代代数200;Q=1;,2.3.1 蚂蚁系统的模型与实现,2.3 基本蚁群优化算法,智能优化计算,%清空环境变量clear allclc%导入数据load citys_data.mat%计算城市间相互距离n

16、=size(citys,1);D=zeros(n,n);for i=1:n for j=1:n if i=j D(i,j)=sqrt(sum(citys(i,:)-citys(j,:).2);else D(i,j)=1e-4;end end end,程序分析,2.3 基本蚁群优化算法,智能优化计算,%初始化参数m=30;%蚂蚁数量alpha=1;%信息素重要程度因子beta=5;%启发函数重要程度因子rho=0.1;%信息素挥发因子Q=1;%常系数Eta=1./D;%启发函数Tau=ones(n,n);%信息素矩阵Table=zeros(m,n);%路径记录表iter=1;%迭代次数初值ite

17、r_max=200;%最大迭代次数 Route_best=zeros(iter_max,n);%各代最佳路径 Length_best=zeros(iter_max,1);%各代最佳路径的长度 Length_ave=zeros(iter_max,1);%各代路径的平均长度,2.3 基本蚁群优化算法,智能优化计算,%迭代寻找最佳路径while iter=iter_max%随机产生各个蚂蚁的起点城市 start=zeros(m,1);for i=1:m temp=randperm(n);start(i)=temp(1);end Table(:,1)=start;%构建解空间 citys_index=

18、1:n;%在iter循环中还有以下三个重要步骤：%1、逐个蚂蚁路径选择%2、计算各个蚂蚁路径距离及最短距离%3、更新信息素end,2.3 基本蚁群优化算法,智能优化计算,%逐个蚂蚁路径选择 for i=1:m%逐个城市路径选择 for j=2:n tabu=Table(i,1:(j-1);%已访问的城市集合(禁忌表)allow_index=ismember(citys_index,tabu);allow=citys_index(allow_index);%待访问的城市集合 P=allow;%计算城市间转移概率 for k=1:length(allow)P(k)=Tau(tabu(end),al

19、low(k)alpha*Eta(tabu(end),allow(k)beta;end P=P/sum(P);%轮盘赌法选择下一个访问城市 Pc=cumsum(P);target_index=find(Pc=rand);target=allow(target_index(1);Table(i,j)=target;end end,2.3 基本蚁群优化算法,智能优化计算,%计算各个蚂蚁的路径距离 Length=zeros(m,1);for i=1:m Route=Table(i,:);for j=1:(n-1)Length(i)=Length(i)+D(Route(j),Route(j+1);end

20、 Length(i)=Length(i)+D(Route(n),Route(1);end,2.3 基本蚁群优化算法,智能优化计算,%计算最短路径距离及平均距离 if iter=1 min_Length,min_index=min(Length);Length_best(iter)=min_Length;Length_ave(iter)=mean(Length);Route_best(iter,:)=Table(min_index,:);else min_Length,min_index=min(Length);Length_best(iter)=min(Length_best(iter-1),

21、min_Length);Length_ave(iter)=mean(Length);if Length_best(iter)=min_Length Route_best(iter,:)=Table(min_index,:);else Route_best(iter,:)=Route_best(iter-1),:);end end,2.3 基本蚁群优化算法,智能优化计算,%更新信息素 Delta_Tau=zeros(n,n);%逐个蚂蚁计算 for i=1:m%逐个城市计算 for j=1:(n-1)Delta_Tau(Table(i,j),Table(i,j+1)=Delta_Tau(Tabl

22、e(i,j),Table(i,j+1)+Q/Length(i);end Delta_Tau(Table(i,n),Table(i,1)=Delta_Tau(Table(i,n),Table(i,1)+Q/Length(i);end Tau=(1-rho)*Tau+Delta_Tau;,2.3 基本蚁群优化算法,智能优化计算,运行结果,2.3.1 蚂蚁系统的模型与实现,2.3 基本蚁群优化算法,智能优化计算,运行结果,2.3.1 蚂蚁系统的模型与实现,2.3 基本蚁群优化算法,智能优化计算,运行结果,2.3.1 蚂蚁系统的模型与实现,2.3 基本蚁群优化算法,智能优化计算,运行结果,2.3.1

23、蚂蚁系统的模型与实现,2.3 基本蚁群优化算法,智能优化计算,运行结果,2.3.1 蚂蚁系统的模型与实现,2.3 基本蚁群优化算法,智能优化计算,运行结果,2.3.1 蚂蚁系统的模型与实现,智能优化计算,三种模型 ant-cycle：（蚁周）ant-quantity：（蚁量）ant-density:（蚁密）,2.3 基本蚁群优化算法,2.3.1 蚂蚁系统的模型与实现,智能优化计算,三种模型 在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素（局部信息），而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后（全局信息）才对信息素进行更新。,2.3

24、 基本蚁群优化算法,2.3.1 蚂蚁系统的模型与实现,智能优化计算,三种模型的比较模型ant-density,ant-quantity,ant-cycle的比较(M.Dorigo,1996),2.3 基本蚁群优化算法,2.3.1 蚂蚁系统的模型与实现,智能优化计算,信息素的分布,2.3 基本蚁群优化算法,2.3.2 蚂蚁系统的参数设置和基本属性,智能优化计算,信息素的分布 蒸发系数的影响：,2.3 基本蚁群优化算法,2.3.2 蚂蚁系统的参数设置和基本属性,0.05,0.95,智能优化计算,参数、对算法性能的影响 停滞现象（Stagnation behavior）：所有蚂蚁都选择相同的路径，即

25、系统不再搜索更好的解。原因在于较好路径上的信息素远大于其他边上的，从而使所有蚂蚁都选择该路径。,2.3 基本蚁群优化算法,2.3.2 蚂蚁系统的参数设置和基本属性,智能优化计算,参数、对算法性能的影响 取较大值时，意味着在选择路径时，路径上的信息素非常重要；当取较小值时，变成随机的贪婪算法。,2.3 基本蚁群优化算法,2.3.2 蚂蚁系统的参数设置和基本属性,智能优化计算,参数、对算法性能的影响 0，蚂蚁之间无协同作用；1，有协同作用,2.3 基本蚁群优化算法,2.3.2 蚂蚁系统的参数设置和基本属性,0,1,智能优化计算,蚂蚁数m对算法的影响 mn时，ant-cycle可以在最少迭代次数内找

26、到最优解。,2.3 基本蚁群优化算法,2.3.2 蚂蚁系统的参数设置和基本属性,m15,m150,m30,智能优化计算,蚂蚁的初始分布 两种情况实验：（1）所有蚂蚁初始时刻放在同一城市；（2）蚂蚁分布在不同城市中。第（2）中情况可获得较高性能。（3）在不同城市分布时，随机分布与统一分布的差别不大。,2.3 基本蚁群优化算法,2.3.2 蚂蚁系统的参数设置和基本属性,智能优化计算,优点 较强的鲁棒性；分布式计算；易于与其他方法结合。缺点 搜索时间较长；容易出现停滞现象。,2.4 改进的蚁群优化算法,2.4.1 蚂蚁系统的优点与不足,智能优化计算,最优解保留策略（Ant System with E

27、litist,ASelite）每次迭代完成后，对全局最优解更进一步地进行利用；信息素更新策略 为最优蚂蚁数，Lgb为全局最优解。,2.4 改进的蚁群优化算法,2.4.2 最优解保留策略蚂蚁系统,智能优化计算,最优解保留策略（Ant System with Elitist,ASelite）该策略能够以更快的速度获得最好解，但是如果选择的精英过多则算法会由于较早收敛于局部次优解而导致搜索的过早停滞。,2.4 改进的蚁群优化算法,2.4.2 最优解保留策略蚂蚁系统,智能优化计算,蚁群系统（Ant Colony System,ACS）的改进之处（1）在选择下一城市时，更多地利用了当前最好解；（2）只在

28、全局最优解所属边上增加信息素；（3）每次蚂蚁从城市 i 转移到城市 j 时，边 ij 上的信息素将会适当减少，从而实现一种信息素的局部调整以减少已选择过的路径再次被选择的概率。,2.4 改进的蚁群优化算法,2.4.3 蚁群系统,智能优化计算,可行解的构造 伪随机比率选择规则：蚂蚁以概率q0（01间的常数）移动到最大可能的城市 q为01的随机数，S为一随机变量，当q q0时，S以以下概率来选择：,2.4 改进的蚁群优化算法,2.4.3 蚁群系统,智能优化计算,局部信息素更新 使已选的边对后来的蚂蚁具有较小的影响力，从而使蚂蚁对没有选中的边有更强的探索能力。当蚂蚁从城市i转移到城市j后，边ij上的

29、信息素更新为：其中，0为常数，(0,1)为可调参数。,2.4 改进的蚁群优化算法,2.4.3 蚁群系统,智能优化计算,全局信息素更新 只针对全局最优解进行更新：,2.4 改进的蚁群优化算法,2.4.3 蚁群系统,智能优化计算,最大最小蚂蚁系统（max-min ant system,MMAS）的改进之处（1）每次迭代后，只有最优解（最优蚂蚁）所属路径上的信息被更新；（2）为了避免过早收敛，将各条路径可能的信息素限制于min,max；（3）初始时刻，各路径上信息素设置为max，在算法初始时刻，取较小值时算法有更好的发现较好解的能力。,2.4 改进的蚁群优化算法,2.4.4 最大最小蚂蚁系统,智能优

30、化计算,信息素的全局更新 使所有蚂蚁完成一次迭代后，进行信息素更新：,2.4 改进的蚁群优化算法,2.4.4 最大最小蚂蚁系统,智能优化计算,基于排序的蚂蚁系统（rank-based version of ant system,ASrank）每次迭代完成后，蚂蚁所经路径按从小到大的顺序排列，并对它们赋予不同权值，路径越短权值越大。全局最优解权值为w，第r个最优解的权值为max0,w-r。,2.4 改进的蚁群优化算法,2.4.5 基于排序的蚂蚁系统,智能优化计算,基于排序的蚂蚁系统（rank-based version of ant system,ASrank）信息素更新：,2.4 改进的蚁群优

31、化算法,2.4.5 基于排序的蚂蚁系统,智能优化计算,优化结果比较 对对称TSP各迭代10000次，对非对称TSP各迭代20000次：,2.4 改进的蚁群优化算法,2.4.6 各种蚁群优化算法的比较,智能优化计算,典型应用列表,2.5 蚁群优化算法的应用,2.5.1 典型应用,智能优化计算,如何应用 用蚁群算法解决数据分类（数据挖掘任务中的一种）的问题：预先定义一组类，然后把数据系中的每一个数据根据该数据的属性，归入这些类中的一个。当数据量很大时，难以人为判别分类。,2.5 蚁群优化算法的应用,2.5.2 医学诊断的数据挖掘,智能优化计算,如何应用 分类的规则：IF THEN 每个term是一

32、个三元组（属性、关系符、属性取值）希望在一个规则中使用最少的判别语句，采用蚁群优化算法达到最优的选择。,2.5 蚁群优化算法的应用,2.5.2 医学诊断的数据挖掘,智能优化计算,例：非典型肺炎 考虑如下因素：,2.5 蚁群优化算法的应用,2.5.2 医学诊断的数据挖掘,智能优化计算,例：非典型肺炎 结构图：一个蚂蚁从始点行走至终点，得到一条路径0,2,1,0，其对应的规则为 IF（职业其他人员）AND（胸部阴影无）THEN（非典型肺炎）对此路径，应给予非常差的评价。,2.5 蚁群优化算法的应用,2.5.2 医学诊断的数据挖掘,智能优化计算,蚁群算法的实现 假设a表示属性的总个数，第i个属性的取

33、值域中可取bi个数值。一只蚂蚁的行走k步的路径可以表示为 routek=(y1,y2,ya)yi=0表示不包含属性i。,2.5 蚁群优化算法的应用,2.5.2 医学诊断的数据挖掘,智能优化计算,评价函数 解的评价函数定义为：Q的数值越接近1，说明对该 类的判断越准确。TPtrue positives TNtrue negatives FPfalse positives FNfalse negatives,2.5 蚁群优化算法的应用,2.5.2 医学诊断的数据挖掘,True：判断结果，正确False：判断结果，失误Positives：真实属性，属于Negatives：真实属性，不属于,智能优化计算,转移概率 ij表示每个条件项的启发式参数值（信息熵），ij(t)表示第 i 个属性的第 j 个取值在 t 时刻的信息素。,2.5 蚁群优化算法的应用,2.5.2 医学诊断的数据挖掘,智能优化计算,信息素增加 R是当前规则中所有包含的条件项；信息素挥发 减少没被选中的三元组的信息量。,2.5 蚁群优化算法的应用,2.5.2 医学诊断的数据挖掘,智能优化计算,结果分析 诊断准确度比较,2.5 蚁群优化算法的应用,2.5.2 医学诊断的数据挖掘,智能优化计算,结果分析 诊断规则数比较,2.5 蚁群优化算法的应用,2.5.2 医学诊断的数据挖掘,