近年算法的发展

⑴ 卡尔曼滤波算法的发展历史如何

全球定位系统（GPS）是新一代的精密卫星导航定位系统。由于其全球性、全天候以及连续实时三维定位等特点，在军事和民用领域得到了广泛的发展。近年来，随着科学技术的发展，GPS导航和定位技术已向高精度、高动态的方向发展。但是由于GPS定位包含许多误差源，尤其是测量随机误差和卫星的几何位置误差，使定位精度受到影响。利用传统的方法很难消除。而GPS动态滤波是消除GPS定位随机误差的重要方法，即利用特定的滤波方法消除各种随机误差，从而提高GPS导航定位精度。 经典的最优滤波包括：Wiener滤波和Kalman滤波。由于Wiener滤波采用频域法，作用受到限制；而Kalman滤波采用时域状态空间法，适合于多变量系统和时变系统及非平稳随机过程，且由于其递推特点容易在计算机上实现，因此得到了广泛的应用。为此，本文对Kalman滤波方法进行了深入的研究，并取得了一些成果。 本文首先概述了GPS的组成、应用及最新动态。在此基础上介绍了GPS的导航定位原理，给出了卫星可见性算法、选星算法及定位算法。然后介绍了卡尔曼滤波的基本原理，在此基础上对动态用户的飞行轨迹进行了仿真，对“singer”模型下的8状态和11状态卡尔曼滤波算法进行了仿真分析，同时对“当前”统计模型下11状态卡尔曼滤波算法进行了仿真分析，并对滤波前后的定位精度进行了比较。在此基础上，就如何提高滤波器的动态性能作者提出了改进算法，即自适应卡尔曼滤波算法、带渐消因子的优化算法及改进的优化算法，并分别进行了仿真分析。最后作者将卡尔曼滤波算法分别应用于GPS/DR和GPS/INS组合导航定位系统中，并分别对这两种系统进行了建模和仿真分析，取得了较理想的结果。 本文的研究工作，对改进传统的滤波方法有一定的参考和应用价值，并对卡尔曼滤波方法在提高GPS动态导航定位精度方面的应用起到积极的促进作用。

⑵ 粒子群算法国内发展

粒子群算法介绍（摘自http://blog.sina.com.cn/newtech）
优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题. 为了解决各种各样的优化问题,人们提出了许多优化算法,比较着名的有爬山法、遗传算法等.优化问题有两个主要问题:一是要求寻找全局最小点,二是要求有较高的收敛速度. 爬山法精度较高,但是易于陷入局部极小. 遗传算法属于进化算法( Evolutionary Algorithms) 的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子:选择、交叉和变异. 但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验.1995 年Eberhart 博士和kennedy 博士提出了一种新的算法;粒子群优化(Partical Swarm Optimization -PSO) 算法 . 这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视,并且在解决实际问题中展示了其优越性.

粒子群优化(Partical Swarm Optimization - PSO) 算法是近年来发展起来的一种新的进化算法( Evolu2tionary Algorithm - EA) .PSO 算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质. 但是它比遗传算法规则更为简单,它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作. 它通过追随当前搜索到的最优值来寻找全局最优 .

粒子群算法

1. 引言

粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，有Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究

PSO同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。详细的步骤以后的章节介绍

同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域

2. 背景: 人工生命

"人工生命"是来研究具有某些生命基本特征的人工系统. 人工生命包括两方面的内容

1. 研究如何利用计算技术研究生物现象
2. 研究如何利用生物技术研究计算问题

我们现在关注的是第二部分的内容. 现在已经有很多源于生物现象的计算技巧. 例如, 人工神经网络是简化的大脑模型. 遗传算法是模拟基因进化过程的.

现在我们讨论另一种生物系统- 社会系统. 更确切的是, 在由简单个体组成的群落与环境以及个体之间的互动行为. 也可称做"群智能"(swarm intelligence). 这些模拟系统利用局部信息从而可能产生不可预测的群体行为

例如floys 和 boids, 他们都用来模拟鱼群和鸟群的运动规律, 主要用于计算机视觉和计算机辅助设计.

在计算智能(computational intelligence)领域有两种基于群智能的算法. 蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization). 前者是对蚂蚁群落食物采集过程的模拟. 已经成功运用在很多离散优化问题上.

粒子群优化算法(PSO) 也是起源对简单社会系统的模拟. 最初设想是模拟鸟群觅食的过程. 但后来发现PSO是一种很好的优化工具.

3. 算法介绍

如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索

PSO 初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest. 另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。

在找到这两个最优值时, 粒子根据如下的公式来更新自己的速度和新的位置

v[] = v[] + c1 * rand() * (pbest[] - present[]) + c2 * rand() * (gbest[] - present[]) (a)
present[] = persent[] + v[] (b)

v[] 是粒子的速度, persent[] 是当前粒子的位置. pbest[] and gbest[] 如前定义 rand () 是介于（0， 1）之间的随机数. c1, c2 是学习因子. 通常 c1 = c2 = 2.

程序的伪代码如下

For each particle
____Initialize particle
END

Do
____For each particle
________Calculate fitness value
________If the fitness value is better than the best fitness value (pBest) in history
____________set current value as the new pBest
____End

____Choose the particle with the best fitness value of all the particles as the gBest
____For each particle
________Calculate particle velocity according equation (a)
________Update particle position according equation (b)
____End
While maximum iterations or minimum error criteria is not attained

在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被限定为Vmax

4. 遗传算法和 PSO 的比较

大多数演化计算技术都是用同样的过程
1. 种群随机初始化
2. 对种群内的每一个个体计算适应值(fitness value).适应值与最优解的距离直接有关
3. 种群根据适应值进行复制
4. 如果终止条件满足的话，就停止，否则转步骤2

从以上步骤，我们可以看到PSO和GA有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解

但是，PSO 没有遗传操作如交叉(crossover)和变异(mutation). 而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。

与遗传算法比较, PSO 的信息共享机制是很不同的. 在遗传算法中，染色体(chromosomes) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动. 在PSO中, 只有gBest (or lBest) 给出信息给其他的粒子，这是单向的信息流动. 整个搜索更新过程是跟随当前最优解的过程. 与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解

5. 人工神经网络 和 PSO

人工神经网络(ANN)是模拟大脑分析过程的简单数学模型，反向转播算法是最流行的神经网络训练算法。进来也有很多研究开始利用演化计算(evolutionary computation)技术来研究人工神经网络的各个方面。

演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构(网络拓扑结构，传递函数)，网络学习算法。

不过大多数这方面的工作都集中在网络连接权重，和网络拓扑结构上。在GA中，网络权重和/或拓扑结构一般编码为染色体(Chromosome)，适应函数(fitness function)的选择一般根据研究目的确定。例如在分类问题中，错误分类的比率可以用来作为适应值

演化计算的优势在于可以处理一些传统方法不能处理的例子例如不可导的节点传递函数或者没有梯度信息存在。但是缺点在于：在某些问题上性能并不是特别好。2. 网络权重的编码而且遗传算子的选择有时比较麻烦

最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。研究表明PSO 是一种很有潜力的神经网络算法。PSO速度比较快而且可以得到比较好的结果。而且还没有遗传算法碰到的问题

这里用一个简单的例子说明PSO训练神经网络的过程。这个例子使用分类问题的基准函数(Benchmark function)IRIS数据集。(Iris 是一种鸢尾属植物) 在数据记录中，每组数据包含Iris花的四种属性：萼片长度，萼片宽度，花瓣长度，和花瓣宽度，三种不同的花各有50组数据. 这样总共有150组数据或模式。

我们用3层的神经网络来做分类。现在有四个输入和三个输出。所以神经网络的输入层有4个节点，输出层有3个节点我们也可以动态调节隐含层节点的数目，不过这里我们假定隐含层有6个节点。我们也可以训练神经网络中其他的参数。不过这里我们只是来确定网络权重。粒子就表示神经网络的一组权重，应该是4*6+6*3=42个参数。权重的范围设定为[-100，100] (这只是一个例子，在实际情况中可能需要试验调整).在完成编码以后，我们需要确定适应函数。对于分类问题，我们把所有的数据送入神经网络，网络的权重有粒子的参数决定。然后记录所有的错误分类的数目作为那个粒子的适应值。现在我们就利用PSO来训练神经网络来获得尽可能低的错误分类数目。PSO本身并没有很多的参数需要调整。所以在实验中只需要调整隐含层的节点数目和权重的范围以取得较好的分类效果。

6. PSO的参数设置

从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤: 问题解的编码和适应度函数
PSO的一个优势就是采用实数编码, 不需要像遗传算法一样是二进制编码(或者采用针对实数的遗传操作.例如对于问题 f(x) = x1^2 + x2^2+x3^2 求解, 粒子可以直接编码为 (x1, x2, x3), 而适应度函数就是f(x). 接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过程, 中止条件一般为设置为达到最大循环数或者最小错误

PSO中并没有许多需要调节的参数,下面列出了这些参数以及经验设置

粒子数: 一般取 20 – 40. 其实对于大部分的问题10个粒子已经足够可以取得好的结果, 不过对于比较难的问题或者特定类别的问题, 粒子数可以取到100 或 200

粒子的长度: 这是由优化问题决定, 就是问题解的长度

粒子的范围: 由优化问题决定,每一维可是设定不同的范围

Vmax: 最大速度,决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度,例如上面的例子里,粒子 (x1, x2, x3) x1 属于 [-10, 10], 那么 Vmax 的大小就是 20

学习因子: c1 和 c2 通常等于 2. 不过在文献中也有其他的取值. 但是一般 c1 等于 c2 并且范围在0和4之间

中止条件: 最大循环数以及最小错误要求. 例如, 在上面的神经网络训练例子中, 最小错误可以设定为1个错误分类, 最大循环设定为2000, 这个中止条件由具体的问题确定.

全局PSO和局部PSO: 我们介绍了两种版本的粒子群优化算法: 全局版和局部版. 前者速度快不过有时会陷入局部最优. 后者收敛速度慢一点不过很难陷入局部最优. 在实际应用中, 可以先用全局PSO找到大致的结果,再有局部PSO进行搜索.

另外的一个参数是惯性权重, 由Shi 和Eberhart提出, 有兴趣的可以参考他们1998年的论文(题目: A modified particle swarm optimizer)

⑶ 量子遗传算法的国内外研究现状

当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显着特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。
制造机器智能一直是人类的梦想，人们为此付出了巨大的努力。人工智能技术的出现，就是人们得到的成果。但是，近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对强人工智能提出了强烈批判，对人工智能的可能性提出了质疑。
众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像货朗担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题。遗传算法就是在这种背景下产生并经实践证明特别有效的算法。
遗传算法(Genetic Algorithm, GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darw in的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其学生于1975年创建。此后，遗传算法的研究引起了国内外学者的关注。自1985年以来.国际上已召开了多次遗传算法的学术会议和研讨会.国际遗传算法学会组织召开的ICGA( International Conference on Genetic Algorithms)会议和FOGA( Workshop on Foundation of Genetic Algorithms)会议。为研究和应用遗传算法提供了国际交流的机会。
作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。
近年来，遗传算法已被成功地应用于下业、经济答理、交通运输、工业设计等不同领域.解决了许多问题。例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。本文将从遗传算法的理论和技术两方而概述目前的研究现状。描述遗传算法的主要特点、基木原理以及各种改进算法，介绍遗传算法的程序设计。
遗传程序设计是借鉴生物界的自然选择和遗传机制，在遗传算法的基础上发展起来的搜索算法，它己成为进化计算的一个新分支。在标准的遗传算法中，由定长字符串(问题的可行解)组成的群体借助于复制、交叉、变异等遗传操作不断进化找到问题的最优解或次优解。遗传程序设计运用遗传算法的思想，常采用树的结构来表示计算机程序，从而解决问题。对于许多问题，包括人工智能和机器学习上的问题都可看作是需要发现一个计算机程序，即对特定输入产生特定输出的程序，形式化为程序归纳，那么遗传程序设计提供了实现程序归纳的方法。
把遗传算法和计算机程序结合起来的思想出现在遗传算法中，Holland把产生式语言和遗传算法结合起来实现分类系统，还有一些遗传算法应用领域的研究者将类似于遗传算法的遗传操作施加于树结构的程序上。
近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术它己经与遗传算法并驾齐驱。 1996年，举行了第1次遗传程序设计国际会议，该领域己引起越来越多的相关学者们的兴趣。
1967年，Holland的学生J.D.Bagley在博士论文中首次提出“遗传算法（Genetic Algorithms）”一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年是遗传算法研究历史上十分重要的一年。这一年Holland出版了他的着名专着《自然系统和人工系统的自适应》（Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专着，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schema theory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，K.A.De Jong完成了他的博士论文《一类遗传自适应系统的行为分析》（An Analysis of the Behavior of a Class of Genetic Adaptive System）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。
进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genetic Algorithms ，ISGA），以后每两年举行一次。
1989年，Holland的学生D.E.Goldberg出版了专着《搜索、优化和机器学习中的遗传算法》（Genetic Algorithms in Search , Optimization, and Machine Learning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计( genetic programming, GP)方法，成功地解决了许多问题。
在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。
1991年，L.Davis编辑出版了《遗传算法手册》（Handbook of Genetic Algorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。
1992年，Koza发表了他的专着《遗传程序设计:基于自然选择法则的计算机程序设计》”。1994年，他又出版了《遗传程序设计，第二册:可重用程序的自动发现》深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在《Artificial Intelligence》、《Machine Learning》、《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machines》\《IEEE Transactions on Neural Networks》,《IEEE Transactions on Signal Processing》等杂志上发表。1993年，MIT出版社创刊了新杂志《Evolutionary Computation》。1997年，IEEE又创刊了《Transactions on Evolutionary Computation》。《Advanced Computational Intelligence》杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。

⑷ music算法的理论发展及应用

MUSIC（Multiple Signal Classification多信号分类）算法是1979年由美国人R.O.Schmidt提出的，它标志着空间谱估计测向进入了繁荣发展的阶段。它将“向量空间”的概念引入了空间谱估计领域，经过三十年的发展，可以说其理论已经比较成熟。
自80年代以来，人们对基于特征分解的超分辨率空间谱估计算法进行了广泛深入的研究，并提出了一系列高效的处理方法，其中最经典的是多信号分类（MUSIC）算法，这种算法要经过一维搜索才能求出信源的来向，而相对最大似然（ML）和加权子空间拟合（WSF）等多维搜索算法的运算量已经减少了很多。以MUSIC为代表的算法存在一个缺点，即对相干信号处理的不理想。在针对相干信号源的一系列处理方案中，比较经典的是空间平滑技术，如空间平滑（SS）和修正的空间平滑（MSS）算法。然而，空间平滑技术是以损失阵列有效孔径为代价的，而且只适用于等距均匀线阵（ULA）。
事实上空间谱估计算法都是在已知信号源数目下计算的，而在实际应用中这是不可能的，只能根据观测数据对源数目进行估计。R.O.Schmidt在他的经典之作中提出了依据阵列协方差矩阵特征值的分布来估计信号源的方法。这种方法在理论上是完美的，至少对独立源和部分相关源是正确的，但实际上由于数据长度有限，很大程度上只能依靠主观判断来确定源数。

⑸ 算法的历史

“算法”即算法的大陆中文名称出自《周髀算经》；而英文名称Algorithm 来自于9世纪波斯数学家al-Khwarizmi，因为al-Khwarizmi在数学上提出了算法这个概念。“算法”原为algorism，意思是阿拉伯数字的运算法则，在18世纪演变为algorithm。欧几里得算法被人们认为是史上第一个算法。 第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解伯努利方程的程序，因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机，这个算法未能在巴贝奇分析机上执行。 因为well-defined procere缺少数学上精确的定义，19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了着名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要作用。

⑹ 伪·从零开始学算法 - 1.2 算法的历史

我在写1.1节的时候本来是要写这个的，但是突然就忘了……就作为一节来写吧。

顺便说一下，1946年的今天，世界上第一台通用电脑——电子数值积分计算机在美国宾夕法尼亚大学正式启用，就是那个ENIAC。

别只想着情人节，要不是几十年来科技的进步，你们才没机会在朋友圈、空间什么的大秀恩爱。

中文的“算法”一词至少在唐代就出现了，在此之前也有“术”“算术”等词，最早出现在《周髀算经》《九章算术》。而且，“算法”一词的含义从古到今几乎没有发生变化。

英文的“算法”（algorithm）一词来源于9世纪波斯数学家花拉子米（al-Khwārizmī，780?~850?）——就是那个解决一次方程及一元二次方程的方法的人。花拉子米的拉丁文译名是“Algoritmi”。英文对“算法”原译为“algorism”，意思是花拉子米的运算法则，在18世纪演变为“algorithm”。这个词出现于12世纪，指的是用阿拉伯数字进行算术运算的过程。

对于算筹、算盘的操作的方法，我不知道是否属于算法。

约公元前300年记载于《几何原本》中的辗转相除法（欧几里得算法）被人们认为是史上第一个算法，可以求两数的最大公约数。直到今天，它还有很大的用途。

《九章算术》给出了四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法，线性方程组求解的算法。

三国时代的刘徽给出求圆周率的算法：刘徽割圆术，比阿基米德割圆术得出的结果更加精确。祖冲之使用该方法将圆周率的准确值计算到了3.1415926和3.1415927之间，保持了世界最准确圆周率达900年之久。

唐代以来，历代更有许多专门论述“算法”的专着。宋代的秦九韶提出的秦九韶算法，直到今天仍是多项式求值比较先进的算法。

在9世纪的阿拉伯世界，花拉子米写成《代数学》，其对解决一次方程及一元二次方程的方法催生了代数——大家熟知的求多元（尤其是二元）一次方程和一元二次方程的解法就来源于此。700多年后，三次方程、四次方程的求根公式才被得出。

牛顿于1671年提出的牛顿法，相比于二分法可以更快速地求函数的根或者是函数的极值。

17世纪起，早期的机械计算机出现了。从加法到傅里叶变换，它们的功能越来越强大。

工业革命带来了纺织业的变革，出现了可以自动织出带花纹的布的织布机，它们使用打孔卡输入指令。这种设计也被英国数学家查尔斯·巴贝奇设计的分析机使用。

拜伦的女儿爱达·勒芙蕾丝（Ada Byron；Ada, Countess of Lovelace）于1842年为这个想象中的机器编写求解伯努利微分方程的程序，因此爱达·勒芙蕾丝被大多数人认为是 世界上第一位程序员 。但是，这个机器因为种种原因，直到巴贝奇去世也没有被真正地制造出来。

后来的数学家对算法的贡献大多在于数理逻辑的构建上，在此我因为知识缺乏，看不懂资料，不便讲述。感兴趣的话可以看一下参考资料。

20世纪的英国数学家图灵提出了着名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。图灵机的出现解决了算法定义的难题，图灵的思想对算法的发展起到了重要的作用。

在此之后，算法更偏向于计算机科学领域，各种解决不同问题的算法也层出不穷，涉及排序、统计、线性规划、搜索、压缩等方面。

到了现在，随着人工智能和机器学习的发展，涉及到神经网络的算法变得越发重要。

The Best of the 20th Century: Editors Name Top 10 Algorithms

http://www.uta.e/faculty/rcli/TopTen/topten.pdf

⑺ 算法应用的利弊！（致各平台）

近年来，算法应用在给经济、 社会 发展注入新动能的同时，算法歧视、“大数据杀熟”、诱导沉迷等算法不合理应用也给我们的生活带来烦恼。针对这些问题，国家网信办等四部门联合制定的《互联网信息服务算法推荐管理规定》1月4日正式发布，向各种算法乱象伸出“利剑”。

什么叫“大数据杀熟"！在网络上购物的人，特别是“剁手党"，都应该深有体会！

诱导沉迷，真的只能呵呵呵！就一个

“农药"大家都懂，但南山却假装不懂！

还有一个叫做扭腰女……

算法歧视！知道什么叫做流量就应该懂

或者说最近的

一娅等于多少

一庭等于多少

不公平带来的……

《规定》明确，应用算法推荐技术是指利用生成合成类、个性化推送类、排序精选类、检索过滤类、调度决策类等算法技术向用户提供信息。这意味着各类提供算法推荐服务的互联网公司几乎都在监管范围内，如各类短视频平台、电商平台、社交平台及餐饮外卖平台等。

算法推荐……

类似于一些非常难缠的销售…

我们必须把互联网发展纳入有法可依、有法必依、执法必严、违法必究的轨道，用依法管网的建设意识，培育出趋利避害、生机勃勃、欣欣向荣的网络生态。

企业追求利润无可厚非！

但网络不是无法之地

追求利润的同时也要遵守法律

公平竞争，合法获取

否则让你们尝尝覆舟的感觉！

⑻ 操作系统，数据结构和算法的发展方向

从软件角度来看，可以参考以前服务器级的技术来处理个人电脑环境，更大的空间、更多的处理单元，你其实可以理解为现在的个人电脑是一个十年前的缩小版服务器集群；

多核任务调度、针对有限存储空间而设计的算法（很多算法为了节省空间开销，都是以时间性能为代价的）等，都可以在硬件提升的基础上，让软件也得到进一步提升，不过这些也是很有限的，而且也有不少人在做或者已经做了...；

在空间与计算速度大幅提升的前提下，单纯的考虑性能就很不够了，很多问题比如计算机智能化、信息安全等等，其实很早的时候就已经提出了，只是当时的性能甚至无法满足实验的要求，不过现在，这些都有可能了，所以当下这些领域都是很热门的，或者一些还没有人关注，而你发现的某些领域，都是除了性能之外，很值得研究的。

⑼ 算法研究现状

Farmer以及Deutsch和Journel虽然在1992年就提出了多点地质统计学方法,但其主要是通过在模拟退火中加入多点统计目标函数,然后对模拟图像进行反复迭代达到与输入统计参数匹配。该算法受到数据样板大小、模拟类型值多少的影响,此外迭代收敛也是一个不可避免的问题。受计算机性能以及算法的双重影响,模拟速度极其缓慢。因此对该方法的应用报道很少。1993年,Guardiano et al.提出了一种非迭代算法。它并不通过变差函数及克里金建立条件概率分布,而是直接利用数据样板扫描训练图像,并根据数据样板扫描获得的不同数据事件出现频率,代替数据事件的多点统计概率。即对于每一个未取样点,通过局部条件数据构成的数据事件,扫描训练图像推断局部数据事件联合未知点的条件概率(cpdf)。该方法属于序贯模拟的范畴,但由于每次条件概率的推断都需要重复扫描训练图像,对计算机性能要求相当高,因而该方法也一直停留在实验室阶段。

多点地质统计学得到快速发展,是源于搜索树概念的提出,即一种存储数据事件概率的数据结构。Strebelle(2000)对Guardiano et al.的算法进行了改进,提出将扫描训练图像获得的多点概率保存在“搜索树”里,随后的模拟采用序贯模拟的思路。在每模拟一个未知节点时,条件概率直接从“搜索树”里读取,大大缩短了运算机时,使得多点统计学储层建模真正意义上的推广成为可能。Strebelle将此算法命名为Snesim(Singlenormal equation simulation)。Snesim算法推出后,立刻受到建模界的关注,成为近几年储层建模热点。通过实际研究区建模,有些学者指出Snesim尚存在一些缺陷,表现在以下几个方面:

1)训练图像的平稳性问题。如何将实际储层中的大量非平稳信息表现为训练图像并能应用多点统计方法进行建模;

2)集成软数据(如地震)及评估训练图像或软数据的权重问题,尤其是它们在某种程度上不一致时;

3)储层形态合理再现问题。在现有算法中,当数据事件稀少时,往往通过去除最远条件节点方法来获得可靠的数据事件,而这种处理方法往往会导致储层构型再现失败;此外,训练图像过小将导致目标不连续,影响建模真实性;而训练图像过大则导致运行机时大,Snesim的实施存在困难;

4)多重网格搜索问题。两点统计学的多重网格搜索方法,不能改变粗网格模拟值,而条件数据重新分配具有相当大的误差,导致实际地质结构特征再现效果较差;

5)由于多点地质统计学仍然是基于像元的算法,所以只能在一定程度上重现目标的形状,对于更复杂的如尖角或者U型目标的应用则效果较差。

对于Snesim存在的问题,不同学者通过研究提出了各自的解决方案或建议。如非平稳性问题,Caers(2002)就采取类似于变差函数套合方式,通过伸缩和旋转变换,将非平稳的地质模式变化为平稳的地质模式,随后采用Snesim进行建模。再如数据样板再现,Liu(2003)就通过赋予不同节点不同权重,在数据事件稀少时,舍弃权重最小数据点以获得可靠的数据事件,而不是Snesim中去除最远条件节点的方式;Stien(2007)则允许删除条件数据点的值,而不是把它从条件数据集中移去。当所有节点被模拟后,再对那些被删掉值的点重新模拟。Suzuki(2007)提出了一种新的方法,即实时后处理方法(PRTT),其主要思想是在某一点上如果条件化失败,不是去掉一些条件数据缩小数据模板,而是返回到上一步,对前面模拟的数据进行修改,以达到数据事件合理化。在储层属性及数据事件多时,Arpat(2003)、Zhang(2003)等提出聚类的思想对相似数据事件进行归类,从而减少运行机时及不合理数据事件的出现概率。

储层建模是对地下沉积储层地质模式的再现。考虑到储层建模过程,实质上是对地下储层特征沉积模式的重建过程。如果将各种地质模式看成是一幅图像的构成单元,对储层预测也就是图像的重建过程。基于此思想,在2003年Stanford油藏预测中心举行的会议上,Arpat提出了Simpat(Simulation with pattenrs)多点地质统计学随机建模方法,即通过识别不同的地质模式,采用相似性判断方法,在建模时再现这些地质模式。Simpat模拟流程采用的也是序贯模拟的思路。由于是对地质模式处理,而地质模式是通过空间多个点构成的数据事件反映的,因此,在模拟实现时以整个数据事件赋值或者数据事件的子集取代了单个模拟网格节点的赋值。也就是说,在模拟过程中,在对某个未知值的预测过程中,除了模拟节点处赋值外,用来预测节点处值的条件数据的值也会有变化。Arpat通过这种数据事件整体赋值,实现储层地质模式再现。在数据事件选择上,Arpat摈弃了传统的概率推断、蒙特卡罗抽样的随机建模方法,而是借鉴计算机视觉及数字图像重建领域的知识,利用数据事件的相似性对数据事件进行选择。Arpat对此方法进行了较详细的论证,表明此方法能够较好再现储层结构特征。在此基础上,基于距离相似度的多点地质统计学(distance-based multiple point geostatistics)开始得到研究和发展(Suzuki et al.,2008;Scheidt et al.,2008;Honarkhah et al.,2010)。与传统基于统计抽样的模拟不同,基于距离相似度的方法直接计算数据事件的相似性,并用最相似的数据进行整体替换。

基于统计抽样以及储层模式分类的考虑,Zhang(2006)提出了Fitlersim(Filter-Based simulation)方法。他认为在训练图像中众多储层模式可以由几个滤波函数进行描述,由滤波函数获得储层模式的统计得分,在此基础上,进行储层模式的聚类,达到降低储层维数、提高运算效率的目的。此外,在聚类过程中考虑相似的储层模式出现的频率,使得储层预测具有统计学的意义。Yin(2009)则从目标骨架提取出发,约束多点统计模式选择,提出了基于储层骨架的多点地质统计学方法。