Long Luo's Life Notes

每一天都是奇迹

By Long Luo

这篇文章部分内容还在优化,Demo 还在继续开发,大概还需要 7 - 8 小时写作时间。

无限猴子定理(英语:Infinite monkey theorem)

让一只猴子在打字机上随机地按键,当按键时间达到无穷时,几乎必然能够打出任何给定的文字,比如莎士比亚的全套著作。

在这里,几乎必然是一个有特定含义的数学术语,“猴子”也不是一只真正意义上的猴子,它被用来比喻成一个可以产生无限随机字母序列的抽象设备。这个理论说明把一个很大但有限的数看成无限的推论是错误的。猴子精确地通过键盘敲打出一部完整的作品比如说莎士比亚的哈姆雷特,在宇宙的生命周期中发生的概率也是极其低的,但并不是零。

遗传算法(Genetic Algorithm) [1] 是一种元启发式搜索和优化技术,借鉴了生物进化中的自然选择和遗传机制。它已经在各个领域展示出了强大的应用潜力。本文将介绍遗传算法的发展历史、原理、示例,以及其广泛应用和不足之处。

发展历史

遗传算法的发展可以追溯到上世纪60年代的约翰·荷兰德(John Holland)和他的同事们的工作。他们首先提出了基因型与表现型之间的映射关系,并通过模拟生物进化过程来解决复杂的优化问题。

原理

遗传算法的核心原理是模拟自然进化的过程。它通过定义适应度函数来评估候选解的质量,并利用遗传操作(选择、交叉和变异)对候选解进行迭代改进。具体而言,算法从一个初始种群开始,通过选择适应度较高的个体作为父代,进行交叉和变异操作产生新的后代个体,然后通过评估适应度来选择出下一代个体。这个过程不断迭代,直到找到满足特定条件的优秀解。

It’s never too late

举个例子

目前参考网络资源写了一个简单的Demo,地址:http://longluo.me/projects/genetic

这个例子还有待完善!

Genetic Algorithm

阅读全文 »

By Long Luo

任何一款科学计算器上都可以计算三角函数,三角函数应用于生活工作中的方方面面,但计算机是如何计算三角函数值的呢?

三角函数本质上是直角三角形的3条边的比例关系,计算并没有很直观,那么计算机是如何计算三角函数值的呢?

在微积分中我们学习过 泰勒公式 ,我们知道可以使用泰勒展开式来对某个值求得其近似值,例如:

sin18=5140.3090169943\sin \angle 18^{\circ} = \frac{\sqrt {5} - 1}{4} \approx 0.3090169943

利用泰勒公式,取前 44 项:

sinxxx33!+x55!x77!\sin x \approx x - \frac{x^3}{3!} + \frac{x^5}{5!} - \frac{x^7}{7!}

代入可得:

sin18=sinπ10=π1016(π10)3+1120(π10)515040(π10)70.30903399538\sin \angle 18^{\circ} = \sin \frac{\pi}{10} = \frac{\pi}{10} - \frac{1}{6} (\frac{\pi}{10})^3 + \frac{1}{120} (\frac{\pi}{10})^5 - \frac{1}{5040} (\frac{\pi}{10})^7 \approx 0.30903399538

可见取前 44 项时精度已经在 10510^{-5} 之下,对于很多场合精度已经足够高了。

在没有了解 CORDIC(Coordinate Rotation Digital Computer) Algorithm [1] 算法之前,我一直以为计算器是利用泰勒公式去求解,最近才了解到原来在计算机中,CORDIC 算法远比泰勒公式高效。

下面我们就来了解下泰勒公式的不足之处和 CORDIC 算法是怎么做的。

泰勒公式的缺点

上一节我们使用泰勒公式去计算三角函数值时,需要做很多次乘法运算,而计算器中乘法运算是很昂贵的,其缺点如下所示:

  1. 展开过小则会导致展开精度不够,展开过大则会导致计算量过大;
  2. 幂运算需要使用乘法器,存在很多重复计算;
  3. 需要很多变量来存储中间值。

在之前的文章 矩阵乘法的 Strassen 算法 ,就是通过减少乘法,多做加法,从而大大降低了运算量,那么我们可以用相同的思想来优化运算吗?

当然可以,让我们请出今天的主角:CORDIC 算法

阅读全文 »

By Long Luo

最近在书店里看到一本 《数学的奥秘》 ,原著是 《The Secret Life of Equations: The 50 Greatest Equations and How They Work》 ,讲的是最伟大的数学方程式起源、构成、含义和应用。书的内容并不多,我看了其中的一部分,里面有讲 墨卡托投影(Mercator projection)[1]

我对地理和地图一直很感兴趣,但之前对原理一直一知半解的,只知道我们常见的地图都是墨卡托投影,由墨卡托[2] 在 1569年创立。但墨卡托投影的原理是什么却并不清楚。书里面只有几页,但具体公式缺乏说明及推导过程,所以这几天通过查找资料掌握了墨卡托投影的原理。

如何绘制地图?

在大航海时代,航海家可以通过六分仪和观察日月星辰获取到经纬度,但在茫茫大海中迷失方向是很可怕的事情,如何才能正确的航行到目的地呢?

地球由于自转是一个两极比赤道略短的扁球体,但扁率约为 1/3001/300 ,非常之低,因为可以视为球体。因为球面不是可展曲面,也就是如果展成平面的话,长度会发生形变,所以也会形变。因为根据高斯绝妙定理(Gauss theorem egregium)[3] ,平面的高斯曲率为 00 ,而球面的高斯曲率为 1R2\frac{1}{R^2} ,其中 RR 为球面半径,所以在保持图形完整性前提下,将球面转化为平面,投影后得到的经纬线网形状必然会产生变形,也就是说,在投影的过程中,变形是必然存在的。

在这种情况下,墨卡托运用等角圆柱投影法绘制了航海图,极大地方便了航海家。有了墨卡托海图,航海家想要到达某个目的地,只需要在出发点和目的地之间连一条直线,量出这条航线和经线的夹角,按照航行路线就能到达目的地。

Map Mercator Projection

什么是墨卡托投影?

设想将地球置于在一中空的圆柱里,如下图所示,其基准纬线(赤道)与圆柱相切。再设想地球中心处放置一灯泡,那么从球心处发射的光线会把球面上的图形投影到圆柱体上,之后再将把圆柱体展开,那么就可以得到一张墨卡托投影绘制出的地图。

阅读全文 »

By Long Luo

待继续完善

引言:

线性回归是一种经典的统计学方法,被广泛应用于数据分析、预测和建模。它的数学原理简单而直观,能够从数据中找到变量之间的线性关系,并通过这种关系进行预测。本文将介绍线性回归的数学原理、应用实例,以及其优点和不足之处。

数学原理

线性回归的基本思想是寻找输入变量(自变量)与输出变量(因变量)之间的线性关系。其数学模型可以表示为:

yi=β0+β1xi+β2xi2++βmxim+εi (i=1,2,,n)y_{i}\,= \,\beta _{0} + \beta _{1}x_{i} + \beta _{2}x_{i}^{2} + \cdots + \beta _{m}x_{i}^{m} + \varepsilon _{i}\ (i = 1, 2, \dots , n)

J(θ)=i=1n(yipm(xi))2J(\theta ) = \sum_{i = 1}^{n} (y_i - p_m (x_i))^2

d(J(θ))dθ=0\frac {d(J(\theta ))}{d \theta} = 0

Aθ=BA \vec {\theta } = B

其中Y表示因变量,Xi表示自变量,βi表示对应自变量的系数,ε表示误差项。线性回归的目标是找到最优的系数β,使得预测值与实际观测值之间的误差最小。

阅读全文 »

By Long Luo

PID 算法[1] 是自动控制领域中很重要的算法。

Simple PID Controller

非常简单的 PID 算法在线互动式模拟器,传送门 →

PID Algorithm

之前这个是 PID v1.0 版本,最近重构了代码,增加了一些新功能:

  1. 增加机器人速度 vv 及加速度 aa 显示;
  2. 增加 2 个图表展示 PID X 轴方向及 Y 轴方向的 P、I、D 33 个分量随时间变化显示;
  3. 之前代码将时间及速度固定了,但这不符合实际,增加随 dtdt 变化积分和微分项;

pid_track

阅读全文 »
0%