基于并行处理的蚁群聚类算法的研究 -

硕士学位论文

基于并行处理的聚类蚁群算法的研究 Based on parallel processing of the ant clustering algorithm of flocking

1

摘 要

聚类就是将数据对象划分到不同组（或簇）中，使得属于同簇内的数据对象具有相似性，而不同簇的数据对象具有相异性。聚类分析又称群分析，它是研究样品或指标分类问题的一种统计分析方法，它是由若干模式组成的，以相似性为基础，在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性，是重要的数据挖掘技术。近几十年来，国内外的学术者提出了诸多的聚类算法，力图寻找最优方案。随着蚁群算法研究的兴起，人们发现采用蚁群模型进行聚类能够更加有力的解决现实问题。

本文主要先研究了业界一些蚁群算法和聚类算法，充分深入了解了有关聚类蚁

群算法的基本原理和特性。而通过研究发现人工蚁群算法本质上是一个并行系统，因此，研究并行蚁群算法对于提高运算速度具有重要的意义，在归纳总结的基础上，本文了将并行算法和聚类蚁群算法相结合，提出了一种新的聚类蚁群优化算法，同时将改良后的优化算法针对传统的TSP问题、二次分配问题进行了对比，实验结果表明该算法不仅是有效的，而且其性能更加的优越。

本文提出了并行性和聚类蚁群相结合的方法，给出了一种并行蚁群算法，该算法使用并行搜索，并且采用根据目标函数值自动调整蚂蚁搜索路径和基于目标函数值的启发式信息素分配策略。为人们研究聚类提供了新思路和新途径，因此本文的研究具有一定的理论和实践意义。

关键词：并行性；聚类蚁群；优化

2

Abstract

Clustering is dividing data object into different groups (or cluster), make belong to same cluster the data objects with the similarity. However different data objects in clusters have different attribute. Clustering analysis, also called study of analysis, it studies a statistical analysis method of sample or index classification problem. It is composed by several mode based on similarity, and in mode of cluster has more similarity than that in the different clusters between. It is an important data mining technology. In recent decades, the domestic and international academic proposed many clustering algorithms, and tries to find the optimal scheme. With the rise of ant colony algorithm, people found using ant colony optimization model clustering can solve practical problem more powerfully

Firstly this paper studied some ant colony algorithm and clustering algorithm, fully understanding the basic principle of flocking and characteristics of ant clustering algorithm. And through the researches show that people ants swarm algorithm is essentially a parallel system, therefore, Studying the parallel ant colony algorithm has an important meaning to improve speed. On the basis of summarization, combining industrial scheduling problem, this paper will combine the parallel algorithm and ant clustering algorithm, and proposes a new ant algorithm. What is more, the kind of optimization will improved algorithm for traditional TSP problem, quadratic assignment problem and industrial scheduling problem of comparison, the experimental results show that the algorithm is not only effective but also with its more superior performance.

This paper puts forward such parallelism and ant cluster method combining, and presents a parallel ant colony algorithm, which use parallel search, and based on the objective function values automatically adjust the ant search path and based on the objective function value heuristic pheromone distribution strategy. It provides some new ideas and new ways for people to study clustering, thus this study has certain theoretical and practical significance.

Key words: Parallelization; Clustering；Ant Colony Optimization

3

目 录

摘 要 ........................................................................................................... 2 Abstract ............................................................................................................. 3 绪论： ............................................................................................................... 6

1.1 研究背景 ............................................................................................. 6 1.2 蚁群基本习性与觅食行为策略 ........................................................... 6 1.3 聚类蚁群算法的思想与特点 ............................................................... 9 1.4 蚁群优化算法的意义及应用 ............................................................. 10 1.5 本文主要研究的内容及论文组织 ...................................................... 11 2 聚类蚁群算法 .............................................................................................. 12

2.1基本蚁群算法的模型特征 .................................................................. 12 2.2 聚类算法 ........................................................................................... 17 2.3 主要聚类蚁群算法 ............................................................................ 20 2.3.1 K均值混合聚类算法 ....................................................................... 21 2.3.2 基于蚂蚁觅食原理的聚类算法....................................................... 22 2.3.3 基于化学识别系统的聚类蚁群算法 ............................................... 24 2.4 小结 .................................................................................................. 25 3 并行算法概述 ............................................................................................ 27

3.1 并行计算机 ....................................................................................... 27 3.2 并行算法 ........................................................................................... 27 3.3 MPI与OPENMP并行编程 ................................................................ 28 4 并行的聚类蚁群优化算法PACOA .............................................................. 30

4.1 PACOA算法的基本思想产生的背景 ................................................. 30 4.2 PACOA基本思想与策略 ................................................................... 30 4.3 PACOA算法步骤和基本实现 ............................................................ 33 5 PACOA性能的仿真研究 ........................................................................... 40

5.1 实验介绍 ........................................................................................... 40 5.2 仿真实验结果与数据分析 ................................................................. 40 5.3 小结与参数分析 ................................................................................ 44

4

6 结论与展望 .................................................................................................. 45 参考文献 ......................................................................................................... 46

5

不过是更多的神经元连接（人脑）通过互联网相互作用的结果，光缆和路由器不过是轴突和突触的延伸。从自组织现象的角度上看，人脑的智能和蚁群也没有本质上的区别，单个神经元没有智能可言，单个蚂蚁也没有，但是通过连接形成的体系，是一个智能体。

1.5 本文主要研究的内容及论文组织

本文首先介绍了现今主要的聚类蚁群算法，从介绍蚂蚁的习性到觅食策略然后引出对蚁群算法的研究，从基本思想和聚类原理上进行论述与分析，针对这种聚类蚁群的本质是一种并行系统，故在归纳总结的基础上将并行算法和聚类蚁群算法的的相结合，提出了一种新的聚类蚁群优化算法，同时将改良后的优化算法针对传统的TSP问题、二次分配问题进行了对比， 针对传统层次聚类方法效率不高的情况，并在这个思想的指导下，提出基于PACOA的聚类蚁群优化方法。并通过大量实验从各方面进行研究，实验表明PACOA算法不仅是有效的，而且其性能优于之前的聚类蚁群算法。

本文的余下具体组织结构如下：第二部分介绍主要的聚类蚁群算法；第三部分提出基于并行的聚类蚁群优化算法；第四部分通过仿真实验研究并行的聚类蚁群算法的性能；最后总结本文工作，并指出下一步的研究方向。

11

2 聚类蚁群算法

2.1基本蚁群算法的模型特征

一只蚂蚁的智力是很有限的，但很多蚂蚁之间通过一些信息激素进行协同作用，实现蚂蚁之间的信息交流，其效果往往令人惊讶。下面将简单的介绍一下蚂蚁群是怎样通过信息素进行协同作用的，并如何最终找到从蚁穴到食物的最短路径。

在图2.1中，A为出发点（即蚁穴），B为食物源，从图上可见蚂蚁要获得食物有两条路可走，我们可以很容易的比较出路径A-C-B较路径A-D-B长，然而蚂蚁是不知道这一点的。现在假设有两只蚂蚁1和2，在蚂蚁1和2向食物移动的方向上有两条路径可以选择，在初始条件下，两条路径上的信息素量都为零，因此两只蚂蚁选择两条路径的概率均为0.5，在这里，假设蚂蚁1选择了路径A-C-B，蚂蚁2选择了路径A-D-B，在此强调两只蚂蚁的行走速度是一样的。很明显，选择短路径的蚂蚁2将先到达B点，当蚂蚁2要返回时，要选择信息素气味重的路径，由于此时蚂蚁1还在路上，故蚂蚁2选择了原路返回，当蚂蚁2到达A点时，假设的蚂蚁3出发，根据蚂蚁会选择信息素气味较重的路径这一原理，蚂蚁3选择路径A-D-B，因为此路径已经有两次蚂蚁通过的经历，如此由大量的蚂蚁组成的群体便表现出一种信息正反馈现象，即随着路径A-D-B上通过蚂蚁数量的增加，后来的蚂蚁选择此路径的概率就越大，而这正是两点之间的最短路径。

以上通过模仿正真的蚂蚁对其行为进行了研究，为路径规划给出了启示。在自然界中蚂蚁的这种寻径过程表现为正反馈的过程，与人工蚁群的寻优过程非常一致。

12

图2.1 蚂蚁寻径模型

该算法的主要步骤：

1)初始化，设时间t和循环次数N为0，设置蚂蚁数量M和最大循环次数Nmax，初始化环境信息，初始化各个栅格点上的信息素，并将所有蚂蚁都置于起点S。

2)启动蚁群，按式(2.13)计算的概率随机选择下一个路径点，若此栅格到其相邻栅格的路径上的信息素值均为0，则回馈到上一个搜索的路径点，并将其置为威胁栅格。

3)重复2)，直到蚁群到达终点G。

4)对蚁群搜索到的路径进行交叉运算，记录全局最优蚂蚁的路径信息。 5)令t=t+1；N=N+1，根据式(2.14)和式(2.15)更新各条路径上的信息素。 6)若蚁群全部收敛到一条路径或达到最大循环次数，则循环结束，输出最佳路径，否则到2)。

图2.2为蚁群算法的流程图：

13

图2.2 蚁群算法流程图

2.1.1算法实现过程

（1）环境划分

设飞机的起点为S，目标点为G，S、G之间存在一些威胁源，如图2.8所示，左下角的圆点代表起始点，右上角的圆点代表目标点。规划任务为搜索一条由S点到G点的最优路径，其目标函数可由式（2.11）表示，

nF?i?2x??(x??i22)?(y??y) （2.11） i??1ii??1式中：xi、yi为路径点的坐标信息，n为路径点的个数。

飞行空间用栅格进行划分，用0和1分别表示自由可飞栅格和威胁栅格，栅格点用序号表示，按照从左至右，从上到下的顺序依次编序。对于威胁源模型，映射到栅格化的环境中如图2.3所示：

14

图2.3 环境映射

（2）信息素

信息素分布在两相邻栅格之间的路径上，从S点蚂蚁开始搜索，每一步搜索范围是与其当前所在栅格相邻的8个栅格，每一栅格点i到其相邻栅格点j的“信息素”值依式（2.12）进行初始化。

??a, 若j为可飞栅格??????ij??? （2.12） ????0， 其他 ????式中：a为一常数，j为与i相邻的栅格。

设di表示栅格i到终点G的距离。定义与i相邻的左、右、上、下4个栅格为直接相邻栅格，左上、左下、右上、右下4个栅格为间接相邻栅格，可达栅格的判别规则如下：

1)若dj?di,j与i直接相邻且为自由可飞栅格；

2)若dj?di,j与i间接相邻且j及趋向j的与i相邻的两个直接相邻栅格均为自由可飞栅格。边界的搜索只须考虑与其相邻的3个栅格，这样，就把蚂蚁每一

15

题求解中，能解决无人监督的聚类问题，具有广阔的前景。下一节将重点研究基本并行性的聚类蚁群算法

26

3 并行算法概述

3.1 并行计算机

并行计算机是能在同一时间内执行多条指令或处理多条数据的计算机，并行计算机是并行计算的物理载体根据指令流和数据流不同，通常把并行计算机系统分为4类：

（1）单指令流单数据流(SISD)； （2）单指令流多数据流(SIMD)； （3）多指令流单数据流(MISD)； （4）多指令流多数据流(MIMD)。

SISD实际上是普通的顺序执行的串行计算机，SIMD和MIMD是2种典型的并行计算机，而MISD在实际上代表何种并行计算机在学术上没有一致的意见。并行计算机系统除了少数的专用SIMD系统外，绝大部分是MIMD系统。（MI～f1)结构的并行计算机包括并行向量处理机(PVP)、对称多处理机(SMP)、大规模并行处理机(MPP)、机群(Cluster)、分布式共享存储器计算机(DSM)。

3.2 并行算法

并行算法是指适合做各种并行计算机上求解问题的算法。并行算法是可同时

执行的进程的集合，这些进程相互作用，协调处理，从而实现对给定问题的求解。并行算法可以分为数值并行算法和非数值并行算法，或同步并行算法以及异步并行算法和分布式并行算法，或SI肋／MI如并行算法和VLSI并行算法等。

数值并行算法是指基于代数运算的问题的求解算法(如矩阵运算、多项式求值、解线性方程组等)。非数值并行算法是指基于关系运算的问题的求解算法(如排序、查找、遍历等)。同步并行算法是指某些进程必须等待其它进程的并行算法，全部进程均同步在一个给定的时钟上，以等待最慢的进程结束。运行在SIMD机器模型上的并行算法属于同步并行算法，其处理机之间的同步由硬件实现。异步并行算法是指各进程之间不必相互等待的并行算法，其进程之间的通信由软件实现。分布式并行算法是指通过通信链路连接起来的多个节点协同完成某个计算任务的一类并行算法。SIMD／MIMD并行算法和VLSI并行算法是指在SIMD／MIMD和VLSI计算模型上设计出来的一类并行算法。

27

3.3 MPI与OPENMP并行编程

3.3.1 MPI介绍

MPI(Message Passing Interface)是一个工业标准，该标准是为统一不同的大规模并行处理机制造商的消息传递接口而制订的。MPI的内涵和外延：(1)MPI是一个库，不是一门语言。(2)MPI是一种标准或规范的代表，而不特指某一个对它的具体实现；并行机制造商对MPl支持较强，可免费下载MPI在不同并行机上的实现。(3)艘I是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准。MPI最终目的是为进程间通信服务。

MPICH是MPI标准的一种可移植的免费的实现，MPICH库可以被C／C++语言和Fortran语言调用。MPICH库支持多种操作系统，包括Unix操作系统下的版本和Windows操作系统下的版本等。

MPICH库中有一百多个函数，但是其中最基本的函数只有6个。它们构 成了MPICH库的最小子集，利用这6个函数就可以编写出基本的并行程序。 它们是：

int MPI_Init(int*argc，int**argv)： int EPI_Final ize(void)： ‘

int MPI_Comm_rank(MPI COH comm，int*rank)： int MPI_Comm_size(MPI_COm COmm，int*size)：

int MPI_Send(void*buf，int count，MPI_Datatype datatype， int dest，int tag，MPI_Comm comm)：

int MPI_Recv(void*buf，int count，MPI_Datatype datatype， int source，int tag， MPI_Comm COlllm，MPI_Status*status)： MPI_Init（）函数完成程序的初始化，必须作为程序的第一条执行语句。 MPI_Final ize （）函数完成程序的结束处理，必须作为最后一条执行语句。 MPI_Comm_rank （）函数获取本进程的标识，由rank返回。 MPI Comm_size（）函数获取通信域中的进程个数，由size返回。 MPI_Send（）函数发送消息。 MPI_Recv （）函数接收消息。

标准MPI虽然很庞大，但是它的最终目的是服务于进程间通信这一目标的。

3.3.2 OpenMP产生背景

OpenMP是国际上继MPI之后于I998年推出的工业标准。由DEC、IBM、lntel、Kuck&Assiciates、SGI等公司共同定义。它解决了不同并行计算机系统上应用系

28

统难以移植的问题，将可移植性带到可缩放的、共享主存的程序设计之中。对不同的语言，有不同的OpenMP标准，现在基于C/C++和Fortran语言都已经更新至3.0版本。

OpenMP推出后，基本上每个包含共享体系结构的并行计算机的推出，都配置了该语言，而且多家厂商针对自己的体系结构特点还对OpenMP做了扩充，例如：COMPAQ公司扩充了分布、重分布、亲缘性调度等指标。OpenMP则应用于共享内存的并行计算平台，它是一组编译指导语句和可调用运行时库函数的集合，可被直接嵌入源程序而无需作较大的修改，编程简单，为任一现有软件的并行转换提供了一条渐进路径。

3.3.3 OpenMP原理与特征

OpenMP是一个为在共享存储的多处理机上编写并行程序而设计的应用编程接口，由一个小型的编译器命令集组成，包括一套编译制导语句和一个用来支持它的函数库。OpenMP是通过与标准Fortran，C和C++结合进行工作的，对于同步共享变量、合理分配负载等任务，都提供了有效的支持，具有简单通用、开发快速的特点。

OpenMP是可移植多线程应用程序开发的行业标准，在细粒度(循环级别)与粗粒度(函数级别)线程技术上具有很高的效率。对于将串行应用程序转换成并行应用程序，OpenMP指令是一种容易使用且作用强大的工具，它具有使应用程序因为在对称多处理器或多核系统上并行执行而获得大幅性能提升的潜力。OpmMP自动将循环线程化，提高多处理器系统上的应用程序性能。用户不必处理迭代划分、数据共享、线程调度及同步等低级别的细节。

图3.1 OpenMP执行模型

OpenMP采用了共享存储中标准的并行模式fork_join，当程序开始执行时只有主线程存在，主线程执行程序的串行部分，通过派生出其他的线程来执行其他的并行部分。当重新执行程序的串行部分时，这些线程将终止。如图1所示。

29

4 并行的聚类蚁群优化算法PACOA

4.1 PACOA算法的基本思想产生的背景

在很多工业调度问题的环境中，某些优化的算法需要相当长的时间周期，并且甚至在有限的时间内不能产生出一个令人满意的结果和可行的解决方案，对于这类问题，用元启发模型已经能够提供有效的解决方案，而基于聚类蚁群优化的元启发算法已经运行到这类的工业调度的问题。然后，尽管它被证明是一种可行的解决方案，但是它对计算的时间和资源要求依然非常高，特别是当问题的规模变的更加庞大的时候，更有，对于蚁群规模的估计，仍然是算法和主要计算资源利用的主要部分。但是欣慰的是，这种类型的问题能够很好的移植到并行执行的环境中，基于这些原因，我们将研究出一种基于并行性的聚类蚁群优化算法来解决这类的工业调度问题，并且通过仿真实验获得了算法性能的证明。

蚁群算法并行化的可行性与必要性

蚁群算法本质上是一个并行系统。现实中的蚂蚁是并行的搜寻食物，并逐渐形成一条从蚁穴到食物的最短路径，蚁群算法继承了真实蚂蚁的这种并行机制。蚁群算法在每一轮迭代中，每支蚂蚁都是独立的进行解的构建，蚂蚁之间通过信息素进行间接的通信。蚁群算法所具有的这种天然的并行性为算法的并行实现提供了良好的基础。因此，把串行蚁群算法改造为并行蚁群算法是可行的。

蚁群算法是一种智能优化算法，已经成功解决了多种优化问题。但是现有的研究与应用大部分仅针对较小规模的问题，针对大规模问题的蚁群优化算法的研究和应用不多。在很多领域，实际应用问题往往是大规模问题甚至是超大规模问题，对于这样的问题就必须用并行计算的方法去解决。研究优化算法的最终目的是为了解决现实中的各种优化问题，因此，实现蚁群算法的并行化，并使之能够解决各种大规模优化问题是非常必要的。

4.2 PACOA基本思想与策略

思想：

蚁群算法并行化的基本思想是把原来的串行算法中的1个蚁群(m只蚂蚁)分

为P个子蚁群，每个子蚁群分配1个处理机。每个子蚁群中的蚂蚁个数可以相等，也可以不相等，如果处理机性能相同，一般令各子蚁群的蚂蚁个数相等。初始化完成后，由每个子蚁群分别进行解的搜索，根据并行策略进行子蚁群之间的通信，每个子蚁群根据从其它子蚁群获取的有关信息，对本子蚁群的状态进行修改。当

30

达到算法的终止条件时，由其中1个处理机收集各子蚁群的最优解，并输出所找到的全局最优解。

策略：

并行策略的选择对于蚁群算法的并行实现至关重要。选择不同的并行策略，算法的性能差别很大。目前，蚁群算法的并行策略有5种：

(1)并行独立蚁群

对于这种方法，一系列有序的ACO搜索在通用处理器上交叉运行。各个蚁群的主参数值是有差别的。任何参数都可以经过处理器加以更改。这种方一法的优点在于处理器之间不需要任何通信。这种简单的方法可以作为一系列有序程序在一台MIMD机器／工作站机群是运行。

(2)并行交互蚁群

该方法与上面的方法类似，不同点是在特定的迭代中，蚁群之间进行信息交换，将表现最好的蚁群的信息素矩阵复制到其它蚁群。如何定义表现最好的蚁群是一个问题，因为有许多可供使用的不同的度量标准。这种方法代价很高，因为需要传输整个信息素矩阵。

(3)并行蚂蚁

在这种方法中，给每个蚂蚁分配一个独立的处理器，用来它的构建解决方案。当蚂蚁数大于处理器个数时，需要在每个处理器上聚集多个蚂蚁。主处理器负责接收用户输入，将蚂蚁放在随机的的路径起点，并执行全局信息素更新和产生输出。这种方法的通信量适中，其中最大的组件是对独立信息素矩阵加以维护。算法的每个步骤完成后，每个蚂蚁必须更新它的f值，以满足局部信息素更新规则。

(4)解决方案元素的并行评估

在算法的每一步，每只蚂蚁需要检查所有可用的解决方案元素，然后才做出选择。这个操作的计算量非常大，尤其是需要访问约束条件时。由于各元素间是独立的，它们的评估可以并行，所以，为每个奴隶处理器分配等量的元素来评估，这适用于高约束的问题。

(5)蚂蚁和解决方案元素的并行结合

如果有足够多的处理器，那么前述两种方法可以结合起来。者这种情况下，为每只蚂蚁分配了数量相等的一组处理器。在每组中，一个处理器负责构建蚂蚁的行程，并代表组内每个奴隶评估解决方案的元素。 机群系统下并行策略的选择

由于本文的实验环境是机群系统，并将研究大规模的优化问题，所以需要根据机群系统的特点来选择和确定并行策略。

（1）子蚁群间的通信内容

独立并行蚁群是一种极端的情况，各个子蚁群之间不需要进行任何通信。但

31

是为了提升并行蚁群算法的求解性能，充分利用各个子蚁群的搜索能力，一般因该进行子蚁群之间的通信。在已有的并行蚁群算法中，通信的内容大致有3种：问题的解、信息素矩阵、与问题相关的某种特征模式。

在机群系统下，没有统一内存地址空间，各处理机之间用消息传递方式进行通信，因此通信开销是算法性能的一个瓶颈因素。对于大规模问题，信息素矩阵是非常巨大的(例如，信息素矩阵规模为1024X 1024，其大小为8MB)，如果在各个子蚁群之间传输这样的信息素矩阵，通信开销将非常巨大，那么结果将是灾难性的。所以，信息素矩阵不宜作为子蚁群之间的通信内容。特征模式是与问题相关的。例如TSP问题(设有N个城市)的解中，一些次优解和最优解的某些局部路径排列是相同的。如果把这个局部路径排列视为一个整体(含k个城市)，那么剩余的路径就变换为规模为N-k的TSP问题，如果存在多个这样的局部最优解，则计算规模会降低很多，而且更加容易获得全局最优解。在机群系统下，以特征模式为通信内容，通信开销比较小，但是特征模式的发现与定义与特定的问题相联系，不是所有的问题都适用，通用性欠佳。因此，本文暂不选取特征模式作为子蚁群之间的通信内容。

本文所研究的问题的解(解决方案)所占的存储空间为0(N)，其中N为问题的规模，相对于信息素矩阵来说，问题的解所占的存储空间是非常小的。例如，对于TSP问题，当N=1000时，问题的解可以仅占用2000字节。因此，从通信开销上分析，问题的解是完全可以作为子蚁群之间的通信内容。另一方面，蚁群算法在进行信息素更新时，要依赖于问题的解，即对信息素矩阵中问题的解所对应的元素进行信息素的增强。所以，本文选择问题的解作为子蚁群之间的通信内容。

（2）子蚁群间的通信周期

子蚁群间通信周期是指各个子蚁群之间进行通信的时间间隔，即迭代次数的间隔。一种特别的情况是在每次迭代完成后都进行各个子蚁群之间的通信，此时子蚁群间通信周期=l，一般情况下，子蚁群间通信周期=T，即每隔T次迭代进行一次子蚁群之间的通信。当T比较小时，通信开销较大，不利于提高算法的加速比，而且可能导致子蚁群搜索过早趋向于同一区域，失去了子蚁群的多样性，当T较大时，通信开销减少，而且可能实现计算与通信的重叠，提高加速比，但如果T过大，子蚁群不能及时交流相关信息，会使并行蚁群的优势弱化。在机群系统下，各处理机依赖消息传递进行通信，因此，通信开销是提高性能的一个瓶颈，所以子蚁群间通信周期不宜过小，以保证算法有一定的加速比。

我们将通过用一种基于共享内存的一种编程模型OPENMP来实现对算法的并行化。

32

4.3 PACOA算法步骤和基本实现

在本文研究的基于多目标调度问题的过程中，我们应该明白对于这些设立这

些独立序列的指令集的过程序列。本文的模型是基于著名的旅行商问题（TSP），旅行商问题（Traveling Salesman Problem, 简称 TSP）可描述如下：设C = {c1，c2，…，cn}为 n 个城市的集合，L = {lij |ci,cj ∈C }是 C 中元素两两连接的集合，G = (C，L)是一个图，TSP 问题的目的是从 G 中找出长度最短的Hamiltonian 圈，即找出对C = {c1，c2，…，cn}中 n 个城市访问且只访问一次的最短的一条封闭曲线。目前TSP 问题分为对称型和非对称型。在对称型 TSP 问题中，有dij = d ji， νci,cj ∈C(1，2，L，n)，dij 是lij 的长度，问题文件的后缀名为.tsp；而在非对称型 TSP 问题中，至少存在一对ci,cj ∈C ，使dij ≠ dji ，问题文件的后缀名为.atsp，对于部分对称型 TSP 问题和非对称型 TSP 问题。

4.3.1数据结构

首先要定义一些最基本的数据结构，包括TSP问题的描述数据、各边上的信息素及蚂蚁结构等。图4．2列出了几个主要的数据结构并予以详细解释。

long int distance[n][n] 城市间的距离矩阵

long int nn_list[n][nn] 每个城市最近的前nn个邻居矩阵 double pheromone[n][n] 多个蚁群共享的信息素矩阵 double total[e][n][n] 蚁群的信息素与启发信息组合

struet ant_struct{

long int tour_length； 此蚂蚁找到的路径的长度 long int tour[n+1]； 蚂蚁的路径中节点的编号 int visited[n]； 蚂蚁是否访问过某个城市节点 }

ant_struct ant[c][m] 并行的c个有m只蚂蚁的蚁群

城市间的距离。一般对TSP问题实例的描述为n个节点的坐标，这里当然也可以把这些坐标存储在两个数组中，但会增加算法执行过程中的运算量，所以提前计算出城市间的距离并放到一个n阶对称矩阵里更合理一些。事实上对于对称的TSP问题，我们真正用到的只有n(n-1)12个不同元素，但这里仍然使用n阶矩阵存储原因在于其访问的快捷和方便。

最近邻居表。引入这一结构的目的在于加速蚂蚁构造解的速度。该表存储了

33

每个城市距离最近的前1111个邻居节点。在城市i的蚂蚁优先选择i的邻居作为候选节点。这使得蚂蚁选择下一个城市的时间复杂度降为o(1)，除非i的所有邻居均已被该蚂蚁访问过。

信息素结构

因为是多蚁群共享，所以每条边对应的信息量存放在一个n阶对称矩阵pheromone[n][n]中，即τi= τj。在解的构造过程中，城市j的蚂蚁以某一概率选择城市j，此概率由[τij]^ α和[τij]^ β定，因为这一表达式的值与α和β有关，当然若所有蚁群运行完全相同的算法，则其值也会相同，但考虑到不同蚁群使用不同算法或者相同算法有不同的参数设置时此值会有差异，所以将其存储在c个对称n阶矩阵total[cl[n][n]中，C为蚁群个数。

蚂蚁结构

ACO中蚂蚁是最基本的计算实体，它负责解的构造、释放信息素和目标函数值的计算，因此蚂蚁结构中首先要有存放构成解的所有节点的数组，即tour[n+1]。之所以是n+l，是因为蚂蚁最终要回到出发点，数组的最后一个元素就是初始节点，这样有利于简化路径长度的计算。蚂蚁结构的另外一个成员就是所得路径的长度tour_length。除此之外，蚂蚁在构造解的过程中，选择下一个城市之前首先要判断这个城市有没有走过，因此有数组visited[n]，用以标识该蚂蚁对所有城市访问情况，如已走过置l，否则为0。这里对多蚁群而言，每个蚁群m只蚂蚁，有c个蚁群，所以定义二维数组ant[cl[m]，因为是共享存储，所以每个处理器(负责一个蚁群)都可访问该数组，蚁群g的第i只蚂蚁即ant[g][i]。

4．5．2 空间复杂度

对于上面的数据结构，并行ACO求解对称TSP问题时，需要2+c个n阶矩阵和一个n*rm个元素的邻居表，此外每只蚂蚁有两个大小为n+l和rl的数组来分别存储路径节点和己走过城市，以及一个整型数存放路径长度。通常蚂蚁的数量m的值都比较小，因此总的内存需求为O(nz)。除了这些主要的数据结构，还有一些存放中间结果的变量及关于算法性能的统计信息，不过这些结构占用的内存相对于蚁群和问题的描述数据来说是微乎其微的。更精确的讲，假如长整型数据占4个字节，双精度数据占8个字节，我们在两个处理器上采用2个线程(即c=2)计算，并令m=n则占用内存情况为，距离矩阵4n^2，邻居列表4n^2，信息素矩阵8n^2，信息素与启发信息16n^2，蚁群描述16n^2，这样粗略估计，并行的两个蚁群共需内存48n^2。比如对于5000个城市的TSP问题，就会占用内存1．6G。可见，随着

34

问题规模的增大，算法对内存的消耗会急剧上升，不过这是ACO算法与生俱来的，而不是并行化造成的，并行化也无法解决这一问题。

4.5.3 时间复杂度

从上面的实现过程可以看出，并行求解的多个蚁群在解的构造过程中，每个的计算时间仍为O(n3)，可以说在时间复杂度方面，并行对串行并没有本质的改变，这是蚁群算法的天性。不过，ACO作为一种启发式的不确定算法，对其性能或效率的评价不能仅仅考虑时间因素，更重要的一个因素是解的质量，确切的说是通过在给定时间内算法所得解以及得到此解所需的迭代次数来综合判断算法的好坏。

4.5.4 并行线程的协调

因为多个蚁群共享同一个信息素矩阵，因此多个线程对其访问时必须采取安全的互斥机制，本文中使用传统的加锁方法来满足这种需求，具体到PThread，我们设置一个锁变量，通过调用pthread_mutext_lock和pthread．mutex_unlock函数对来实现多蚁群对信息素矩阵的互斥访问。

此外，对主线程和从线程的协作来说，因为信息素的初始化由主线程来完成，我们的实验均是上述过程执行若干次后取平均值，所以主线程也要负责多次信息素的初始化任务，此外在采用信息素重新初始化机制后，当满足条件时仍然要唤醒主线程做初始化工作，且最后主线程要后于从线程退出。这些对主从线程的安全同步协作的要求非常高。

本文中为解决上述问题采用了PThread库的条件变量pthread_cond_t，在从线程执行计算的过程中，主线程一直等待在一个条件变量上，直到有线程提出重新初始化时，阻塞从线程而唤醒主线程，待其完成初始化后，广播信号唤醒所有等待在这个条件变量上的线程，同时阻塞自己。为此程序中设置了如下变量：

int sum_try_counter //实验总次数控制

int has_init_pheromone //用于判断信息素是否完成初始化 int restart_flag // 控制信息素何时初始化

pthread cond t．cond sync //主从线程同步的条件变量

从线程的等待实现，当主线程初始化信息素矩阵完成后通过广播信号量唤醒所有等待的线程，见图4．10中的master部分。当所有线程都完成一次实验后，通过调用sem post函数来唤醒主线程。

proc waitpheromoneInit while(not has_init pheromone) // 信息素尚未完成初始化

pthread mutex lock(＆mutex)

pthread cond_wait(&cond，&mutex) //等待 pthread mutex lock(＆mutex) end while end proc

35

表5.1 使用的参数表

Parameter Value β -2 γ 0.1 ρ 0.1 m 2??8 Q 100 Iterations 1000

图5.1 并行处理50个任务，100个周期，蚁群数为1000个

图5.2 并行处理50个任务，200个周期，蚁群数为1000个

41

图5.3 并行处理80个任务，100个周期，蚁群数为1000个

图5.4 并行处理80个任务，200个周期，蚁群数为1000个

考虑到蚁群规模的大小，图一和图三表明了在相同的参数下，同时处理80个任务能够获得同时处理50个任务更好的效率，应该相信在并行化的机制下，我们处理更多的任务将会获得更好的效率。当然，还要看在现实的工业调度的情况，将会对规模进行一定的限制，所以一开始第一步就应该对可行性和性能进行研究，故在未来的工作当中，将把问题的规模扩展到多于80个任务。 下面两个图是处理不同个任务的执行时间对比，依然是100个执行周期和1000个蚁群数量。

图5.5 并行处理80个任务，100个周期，1000个蚁群数量执行时间

42

图5.6 用四个处理器，100个周期，1000个蚁群的效率

图5.7 串并行蚁群算法的对比图

可以明显的看出并行化对蚁群算法的优势所在。

为了对不在信息素上的数据也能被聚类，可以通过一下两种方法：（1）确保信息素不断变化，使每个网格至少有一次能含有信息素；（2）不要让蚂蚁时刻沿着信息素轨迹移动，应让蚂蚁频繁的离开信息素痕迹。对方法（1）中控制信息素不断变化是不可能的，因为那需要不断的中断重建信息素，不但麻烦，而且需要不断的修改参数，该方法行不通，因此本文采用方法（2）。试用下面三种措施来考虑：1、蚂蚁的状态与它的运动类型相结合；2、蚂蚁的状态与它向外发射信息素相结合；3、蚂蚁状态、向外发射信息素及运动类型相结合。

43

5.3 小结与参数分析

在上面的仿真实验中，需要设定的参数主要有蚂蚁数量m，全局挥发因子α，

局部挥发因子ρ，启发函数权重β，下面对这几个参数进行仿真研究。

（1）蚂蚁数量m

PACOA算法中蚂蚁的数量越多，全局搜索能力就越强，但是算法的计算量与m成正比，蚂蚁数量越多计算量也就越大，为了寻找最佳的蚂蚁数量，分别选取了m=n/10，n/5， n/2，n，2n，5n，10n等参数进行仿真分析。蚂蚁数量对进化过程的影响是随着m的增大，优化结果越好；m>n时，解的进化状况普遍比较好，基本收敛于m=n时得到的最优解附近，而且m的增大对最优解的影响不明显；当m

（2）参数α，ρ

参数α，ρ分别代表全局更新规则和局部更新规则中信息挥发程度，为了寻找α和ρ的最佳范围，分别对α=ρ=0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9等情况进行了仿真实验，信息挥发程度对进化过程影响的结果是，当参数α=ρ取值在0.4，0.5，0.6时，进行较慢；当α=ρ取值在0.1，0.9时，优化结果较差。在PACOA算法中，优化过程是信息素挥发和信息积累两种过程共同作用的结果，增大α，ρ的值，信息素挥发的越快，可以提高算法的全局搜索能力，但是又会使算法的收敛速度降低；减小α，ρ的值，信息素的挥发较慢，以前搜索过的解被选择的可能性大，影响到算法的全局搜索能力。当信息素挥发和积累的过程基本持平（α=ρ=0.5附近时）时解的进化较为缓慢，但是过多突出任何一方的作用均不能得到很好的解；根据实际结果得出，参数α=ρ在0.2~0.3或者0.7~0.8之间取值比较好

（3）参数β

β的值体现了对信息痕迹和启发搜索相对受重视的程度，下面分别对β取不同参数下的实验结果进行分析，PACOA 的优化过程是信息痕迹和启发函数共同作用的结果。β的值越小，蚂蚁选择以前选过的路由的可能性就越大，其值过小会使搜索过早陷入局部最小点，β值过大启发函数的作用增强，收敛性较慢，同样也很难得到较好的解。因此，β值存在一个合适的范围，在仿真实验中，β的取值在2~3比较合适。

蚁群系统本质上是一个并行系统，可采用并行计算技术提高运算速度。基于MPI消息界面的PACOA并行算法是一种提高算法性能的有效手段，实验证明，使用该算法能够成比例的提高运行速度。

44

6 结论与展望

回顾全文，本文主要做了三项工作： （一）研究了聚类蚁群算法

本文首先从研究蚁群的习性和觅食策略入手，然后过渡到对蚁群算法模型的建立，阐述了蚁群算法的基本思想和特点，然后介绍了在数据挖掘中一种重要的方法和工具，聚类分析，从蚁群算法到聚类蚁群算法的演进过程中，改善了算法的效率。

（二）研究了并行算法和蚁群的并行策略

这部分对并行蚁群算法的基本思想作了阐述。并行策略是实现并行蚁群算法的关键所在，文中对现有的并行策略作了介绍。然后根据机群系统的特点和要求，对机群系统下，并行蚁群算法的并行策略进行了讨论和选择。 （三）提出了PACOA算法并通过仿真实验验证

这部分主要给出了PACOA的算法的详细介绍，包括给出了流程图，算法执行图，还有算法的伪代码，通过大量仿真实验来证明了算法的正确性，同时还研究了一些参数包括蚂蚁个数、参数B、参数p、参数y，分别研究了这些参数对算法的求解性能、时间性能的影响。并通过这些实验，确定出一组最佳的参数组合。

展望：在使用元启发式方法求解现实世界中的优化问题时，需要相当长的计算时间，实现聚类蚁群的并行化，让算法在分布并行的计算硬件中运行显然是一件值得期待的做法，聚类蚁群优化使用了许多独立的局部过程，本质上是一个分布式的方法，这就使得聚类蚁群优化特别适合并行化，尽管已经实现了一些聚类蚁群优化的并行算法并且对它们在受限的设置中进行了测试，但是应该如何实现算法的高效率并行版本，以及相对于顺序版本算法的性能将得到何种程度的改进仍然是两个有待于解决的问题。

发展和测试在并行硬件上的运行的真正的分布式聚类蚁群优化算法将是一个有趣的研究方向，特别是在PC的Beowulf类型集群和GRID计算系统中运行的聚类蚁群优化软件对进行前面所描述的多目标，动态变化和随机性的真实问题的实验非常有意义。

45

本文来源：https://www.bwwdw.com/article/7gq2.html