基本的算法策略

蚁群算法浅析

摘要：介绍了什么是蚁群算法，蚁群算法的种类，对四种不同的蚁群算法进行了分析对比。详细阐述了蚁群算法的基本原理，将其应用于旅行商问题，有效地解决了问题。通过对旅行商问题C++模拟仿真程序的详细分析，更加深刻地理解与掌握了蚁群算法。

关键词：蚁群算法；旅行商问题；信息素；轮盘选择

一、引言

蚁群算法（Ant Colony Optimization, ACO），是一种用来在图中寻找优化路径的算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。

蚁群算法成功解决了旅行商问题（Traveling Salesman Problem, TSP）：一个商人要到若干城市推销物品，从一个城市出发要到达其他各城市一次而且最多一次最后又回到第一个城市。寻找一条最短路径，使他从起点的城市到达所有城市一遍，最后回到起点的总路程最短。若把每个城市看成是图上的节点，那么旅行商问题就是在N个节点的完全图上寻找一条花费最少的回路。

最基本的蚁群算法见第二节。目前典型的蚁群算法有随机蚁群算法、排序蚁群算法和最大最小蚁群算法，其中后两种蚁群算法是对前一种的优化。本文将终点介绍随机蚁群算法。

二、基本蚁群算法

（一）算法思想

各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素。因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就找到了。

实 验 报 告

（2016/2017学年 第二学期）

课程名称 算法分析与设计

实验名称 分治策略

实验时间 2017 年 3 月 30 日

指导单位 计算机学院 软件工程系

指导教师 张怡婷

学生姓名 霍淇滨 班级学号 B********

学院(系) 计算机学院 专 业 软件工程

实 验 报 告

实验名称 分治策略 指导教师 张怡婷

实验类型 验证型（第4个实验密码算法是“设计型”） 实验学时 2 实验时间 2017-3-30

一、 实验目的和任务

理解分治法的算法思想，阅读实现书上已有的部分程序代码并完善程序，加深对分治法 的算法原理及实现过程的理解

二、 实验环境(实验设备)

Visual Studio 2015 三、实验原理及内容（包括操作过程、结果分析等）

一、用分治法实现一组无序序列的两路合并排序和快速排序。要求清楚合并排序及快速排 序的基本原理，编程实现分别用这两种方法将输入的一组无序序列排序为有序序列后输出。

标头.h

#include

using namespace std;

class SortableList

{

public:

SortableList(int mSize);

~SortableList();

void Input();//输入数组

void Output();//输出数组

void MergeSort();//两路合并排序

void QuickSort();//快速排序

private:

int *l;//数组指针

int maxSize;//数组最大长度

int n;//数组已有元素个数

void MergeSort(int left, int right);

void Merge(int left, int mid, int right);

void Swap(int i, int j);//交换函数

void QuickSort(int left, int right);

第四章 控制算法与策略

按偏差的比例、积分和微分进行控制的控制器（简称为PID控制器、也称PID调节器），是过程控制系统中技术成熟、应用最为广泛的一种控制器。它的算法简单，参数少，易于调整，并已经派生出各种改进算法。特别在工业过程控制中，有些控制对象的精确数学模型难以建立，系统的参数不容易确定，运用控制理论分析综合要耗费很大代价，却不能得到预期的效果。所以人们往往采用PID控制器，根据经验进行在线整定，一般都可以达到控制要求。随着计算机特别是微机技术的发展，PID控制算法已能用微机简单实现。由于软件系统的灵活性，PID算法可以得到修正而更加完善[14]。在本章中，将着重介绍基于数字PID控制算法的系统的控制策略。

4．1 采用周期T的选择

采样周期T在微机控制系统中是一个重要参数，它的选取应保证系统采样不失真的要求，而又受到系统硬件性能的限制。采样定理给出了采样频率的下限，据此采样频率应满足，mS2，其中m是原来信号的最高频率。从控制性能来考虑，采样频率应尽可能的高，但采样频率越高，对微机的运行速度要求越高，存储容量要求越大，微机的工作时间和工作量随之增加。另外，当采样频率提高到一定程度后，对系统性能的改善已不明显[14]。因此采样频率即采样周期的选择必须综合考虑下列诸因素：

（1） 作用于系统的扰动信号频率。扰动频率越高，则采样频率也越高，即采样周期越小。

（2） 对象的动态特性。采样周期应比对象的时间参数小得多，否则采样信号无法反映瞬变过程。

（3） 执行器的响应速度。如果执行器的响应速度比较缓慢，那么过短的采样周期和控制周期将失去意义。

（4） 对象的精度要求。在计算机速度允许的情况下，采样周期越短，系统调节的品质越好。 （5） 测量控制回路数。如果控制回路数多，计算量大，则采样周期T越长，否则越小。

（6） 控制算法的类型。当采用PID算式时，积分作用和微分作用与采样周期T的选择有关。选择采样周期T太小，将使微分积分作用不明显。因为当T小到一定程度后，由于受到计算精度的限制，偏差e(k)始终为零。另外，各种控制算法也需要计算时间。

2.1 蚁群算法的基本原理

蚁群优化算法是模拟蚂蚁觅食的原理，设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的几率也就越高，由此构成的正反馈过程，从而逐渐的逼近最优路径，找到最优路径。

蚂蚁在觅食过程时，是以信息素作为媒介而间接进行信息交流，当蚂蚁从食物源走到蚁穴，或者从蚁穴走到食物源时，都会在经过的路径上释放信息素，从而形成了一条含有信息素的路径，蚂蚁可以感觉出路径上信息素浓度的大小，并且以较高的概率选择信息素浓度较高的路径。

蚁穴食物源AB15cm(a) 蚁穴 12 食物源AB(b)

人工蚂蚁的搜索主要包括三种智能行为：

（1）蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选择，因此在蚁群算法中建立禁忌表进行模拟。

（2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素的物质，当其他蚂蚁进行路径选择时，会根据路径上的信息素浓度进行选择，这样信息素就成为蚂蚁之间进行通信的媒介。

（3）蚂蚁的集群活动。通过一只蚂蚁的运动很难达到事物源，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，路径上留下的信息素数量也就越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度，而通过的蚂蚁比较少的路径上的信息素会随着时间的推移而挥发，从而变得越来越少。3.3.1蚂蚁系统

蚂蚁系统是最早的蚁群算法。其搜索过程大致如下：

在初始时刻，m只蚂蚁随机放置于城市中，各条路径上的信息素初始值相等，设为：0(0)ij为信息素初始值，可设0mmL，mL是由最近邻启发式方法构造的路径长度。其次，蚂蚁(1,2,)kkm，按照随机比例规则选择下一步要转移的城市，其选择概率为：