摘 要

在实际工程中，人们通常需要从已知的数据中推测出变量间的规律，这种方法就是拟合。最小一乘法是一种曲线拟合的方法，其误差测度函数使用的是残差绝对值之和，而非最小二乘法中的残差平方之和。因此其拟合效果受部分奇异点的影响较小，稳健性更强。但绝对值的存在同时给计算带来了诸多不便，其应用范围不如最小二乘法广。蚁群算法是一种进化仿生算法，该算法通过代码模拟自然界蚂蚁的觅食行为来求解最优化问题。

为了解决最小一乘法本身因不可导的特性而难以求解的问题，本文使用了蚁群算法，同时也保留了最小一乘法受异常点干扰小的优势。本文主要研究内容如下：

1) 讨论了最小一乘法数学模型的优劣，并介绍了以一串十进制数字为城市的连续域蚁群算法的原理。

2) 设置仿真实验，以最小一乘法测度函数准则，使用蚁群算法模型编写的程序对给定的一组样本点进行拟合，得到回归方程。

3) 分析仿真实验结果，评价算法的性能以及相关工作的展望。

从文中的几个仿真实验的结果可以看出，无论从主观还是从客观上来说，本文算法对于预设回归线的还原程度均好于最小二乘拟合法。

关键词：蚁群算法；最小一乘法；最优化；曲线拟合

Abstract

In practical applications, people usually need to speculate the law between variables from the known data. This method is called fitting. Least absolute deviation is a way of curve fitting, which uses the absolute value of the residual error as the standard of the fitting’s guide line, rather than the square of the residual error which is used by least square deviation. Thus, the influence of some singular points to the results of fitting is much lower, and it has a better steadiness. But the absolute value also causes inconvenience in calculation, which makes it not as widely used as the least square deviation. Ant colony algorithm is a bionic-evolution algorithm, which simulates the foraging behavior of the ants in nature by coding to solve an optimization problem.

We use the ant colony algorithm to dispel the inconvenience in calculation caused by non-differentiable, and still holds the advantage of the least absolute deviation which is less likely influenced by the singular points. Here is what we do in this paper:

1) We talk about the advantages and disadvantages of the mathematical model of the least absolute deviation, then we introduce the principle of ant colony algorithm which has a series of decimal numbers as the cities.

2) We set some simulation experiments, and take the measurement functionas the guide line then we use the program coded through the model of ant colony algorithm to fit the sample points and get the regression equation.

3) We analyze the result of the experiments, and discuss the performance of this algorithm and make some prospects of related work.

We can see from the results of the several simulation experiments that the algorithm in this paper has a better accuracy in fitting than the least square deviation on both objective and subjective views.

Key Words: ant colony algorithm; least absolute deviation; optimization; curve fitting

目 录

第1章 绪论 1

1.1 关于本文所用的最小一乘法和蚁群算法的简单介绍 1

1.1.1 最小一乘法的背景及意义 1

1.1.2 蚁群算法的背景及意义 1

1.2 最小一乘法和蚁群算法的相关研究现状 2

1.3课题研究内容 3

1.4 预期目标 3

1.5 本文的行文结构 3

第2章 基本理论 5

2.1 最小一乘法的数学模型 5

2.2 本文所选的技术路线 5

2.2.1 生物学中的蚂蚁群落 5

2.2.2 蚁群算法的种类 6

2.2.3 基本蚁群算法的数学模型 6

2.2.4 连续域蚁群算法的数学模型 7

2.3 本文算法采用的步骤 9

2.4 本文算法的程序结构图 11

第3章 算法仿真实验 12

3.1 实验流程 12

3.2 实验参数 12

3.3 仿真结果 14

3.4 结果评价 20

第4章 算法的评价 22

4.1 算法的评价标准 22

4.2 时间复杂度分析 22

4.3 空间复杂度分析 23

第5章 结论与展望 24

5.1 结论 24

5.2 展望 24

参考文献 26

附录A 28

附录B 32

附录C 33

附录D 34

致 谢 35

第1章 绪论

1.1 关于本文所用的最小一乘法和蚁群算法的简单介绍

本文采用了一种仿生优化算法——蚁群算法来解决最小一乘法这个在实际工程中有重要意义的抽象数学问题。

1.1.1 最小一乘法的背景及意义

最小一乘法最早是由波斯科维奇(B.J Boscovitch)和法国数学家拉普拉斯(P.S Laplace)于1755至1757年间研究直线拟合时提出^[1]，但局限于当时的计算水平，最小一乘法未得到根本性的发展。

最小一乘法以各点到回归线的距离和值最小，即以：

为准则，得到回归线方程。从理论上来说，n维样本数据点的拟合直线会通过至少n个样本点。

在实际工程优化中，常需要对所测得的数据点进行拟合，得到分布状况，以预测相关参数的变化趋势，曲线拟合常用的方法有最小一乘法和最小二乘法。本文选用的是最小一乘法，相对于最小二乘法来说，其优点是，由于只使用了残差的一次方，因此这种方法受异常数据点的干扰更小，稳健性更好^[2]。

1.1.2 蚁群算法的背景及意义

蚁群算法的核心思想是意大利学者Dorigo Marco在其1992年的博士论文中提出^[3]。蚁群算法最初用来处理商旅问题（TSP），1996年Dorigo将蚁群算法的范围延伸到了指派问题（QAP）和车间作业调度问题（JSP）等领域^[4]，并讨论了初始参数的值对算法性能的影响。

人工模拟自然界中的蚂蚁群落觅食的法则，先行的蚂蚁通过信息素的反馈机制指导后来的蚂蚁该如何更容易找到食物来源。