Fenglielie

遗传算法虽然相比于深度学习，神经网络等新兴的人工智能算法过于原始，相比于有严格数学理论的优化算法又显得那么粗糙，但是作为一类思路独特的算法还是值得了解一下的。 介绍 遗传算法（Genetic Algorithm）是美国J.Holland教授于1975年首先提出的一种启发式优化方法，灵感来自于进化理论：它模拟了生物进化过程中的自然选择、遗传机制和变异规律，用于解决搜索和优化问题。 遗传算法的基本思想是将问题的解表示为一组基因序列，然后使用遗传操作（如选择、交叉和变异）对这些基因序列进行进化（迭代），使优秀的解逐渐从种群中浮现出来。 遗传算法作为一种启发式优化方法，具有如下特点： 适用性：遗传算法的计算框架是普适性的，可以应用于求解各种优化问题，特别是对于搜索空间庞大、复杂的优化问题，如组合优化、参数优化等 并行性：可以并行处理多个解决方案，提高搜索效率 全局或局部最优：由于具有随机性和多样性，遗传算法有助于跳出局部最优解，更有可能找到全局最优解，但是这依赖于初始种群的生成和参数的设置 灵活性/复杂性： 包含很多待定参数，需要根据问题的特点进行调整和改进，这既是算法的灵活性体现，也是算法 ...

包括三种配置文件： .gitconfig .gitattributes .gitignore .gitconfig .gitignore是Git的忽略规则配置文件，Git 会在如下位置依次进行检查（优先级由高到低）： 第一层是仓库级，在仓库目录下，文件为.git/config 第二层是用户级，在用户主目录下，文件为~/.gitconfig（主要修改的是用户级配置） 第三层是系统级，在安装目录下，安装时的选项会保存在这里 Git也可以使用符合XDG规范的配置文件：~/.config/git/config。 123456789101112131415161718192021[user] name = xxx email = xxx@xx.com[init] # 默认主分支名称 defaultBranch = main[core] # 默认编辑器 editor = vim # 确保git正确显示中文信息 quotepath = false # 在提交时将所有文本的换行符转换为LF，检出时不转换 autocrlf = in ...

生命游戏，如果我小时候能做出这玩意，我能自己玩一整天，看着各种复杂混沌的演化过程，最终归于寂静。 介绍 生命游戏（Game of Life）是由数学家 John Conway 在 1970 年创造的一种细胞自动机。 它是一种零玩家游戏，意味着其演化是由初始状态决定的，无需玩家干预。 游戏设定在一个二维的网格世界中，每个格子代表一个存活（标记为1）或死亡（标记为0）的细胞。 基于一组简单的规则，所有细胞会在每个时刻进行同步更新，从一个状态转变到另一个状态，象征着时间推进中生命的演化。 这些规则根据细胞周围的存活细胞数量来确定：（一个细胞受到周围八个细胞的影响） 对于活细胞： 如果周围有两个或三个活细胞，则它在下一个时刻仍然存活 如果周围的活细胞数量少于两个，它在下一个时刻会死亡（孤立） 如果周围的活细胞数量超过三个，它在下一个时刻也会死亡（拥挤） 对于死细胞： 如果周围有三个活细胞，它在下一个时刻会成为活细胞（繁殖） 生命游戏的演化是由给定或随机生成的初始状态开始，并按照这些简单规则不断迭代。即使这些规则非常简单，但它们可以产生出极其复杂和不可预测的行为，包括静态、振荡和移动 ...

MPDE方法是一类用来分析数值格式的耗散色散性质的方法，它的思路为： 对于求解问题PDE(a)，我们通过离散设计得到了数值格式， 现在反过来，找出一个与数值格式最契合的PDE(b)，通常是原本的PDE(a)加上一些高阶余项，分析PDE(b)的耗散和色散性质，尤其关注它相比于PDE(a)多出来的高阶项，就可以得到数值格式的耗散和色散性质。 准备 MPDE的分析依赖于下面的结论：对于PDE \[ 0 = u_t - P u = u_t - \sum_{j=1}^n a_j \frac{\partial^j u}{\partial x^j} \] 其中 \(a_i \in \mathbb{R}\) 。一般性的结论如下： \(u_x\)：不会对耗散和色散做出任何贡献 \(u_{xx}\) 或者更高的偶数阶导数项：对耗散性有贡献，对色散性无贡献 \(u_{xxx}\) 或者更高的奇数阶导数项：对色散性有贡献，对耗散性无贡献 低阶项的贡献是主要的，因此通常可以忽略高阶项，只关注最低阶的系数非零的一个偶数阶导数项和一个奇数阶导数项（不含 \(u_x\) ）。 这里要求系数都是实值，如果系数是复 ...

考虑数值格式的色散耗散性质分析，我们希望数值格式所表现出的性质尽可能与精确满足PDE的波函数一致。下面的基本概念是针对一般的数值格式的，但是例子主要是对流方程的数值格式，因为对它的分析非常典型。 基本概念 取一个离散的谐波解 \[ v_j^n = e^{i(k x_j + \widetilde{w} t^n)} = e^{i( k j \Delta x + \widetilde{w} n \Delta t)} \] 代入离散后的差分系统，可以得到差分系统所对应的广义色散关系（复值） \[ \widetilde{w} = \widetilde{w}(k) \] 实部对应的是波数，虚部对应的是振幅，即 \[ \widetilde{w} = \text{Re} \widetilde{w}(k) + i\, \text{Im} \widetilde{w}(k) \Rightarrow \left\{ \begin{aligned} w(k) &= \text{Re} \widetilde{w}(k)\\ A &= e^{- \text{Im} \widetilde{w}(k) ...

写一点基础的关于简谐波的基础知识，这部分的内容和记号很混乱，有必要整理一下。 这里不涉及到数值格式的色散耗散分析。 波函数 称定义在时空中的函数 \[ u(x,t) = A e^{i\phi(x,t)} \] 为波函数，其中\(\phi=\phi(x,t)\)是定义在时空中的相位函数：\(\phi: \mathbb{R}\times \mathbb{R}^+ \to \mathbb{R}\)。 对于一般的相位函数，我们关注它对时空的偏导数： \(k=k(x,t) := \phi_x \in \mathbb{R}\)称为波数，反映的是波在空间中的周期规律，可能与\((x,t)\)有关 \(w=w(x,t) := \phi_t \in \mathbb{R}\)称为相位速度，反映的是波在时间中的周期规律，可能与\((x,t)\)有关 \(c=c(x,t) := -\phi_t/\phi_x = - w/k \in \mathbb{R}\)称为波速，反应的是波在时空中的传播规律，可能与\((x,t)\)有关 \(A=A(x,t)\)是定义在时空中的复值函数：\(A: \mathbb{R}\ ...

问题介绍 八皇后问题是以国际象棋为背景的经典问题： 如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？（皇后可以攻击与它处于同一条横行，纵列或者斜线上的其它棋子） 我们考虑的是一般化的\(n\times n\)的棋盘上放置\(n\)个皇后的问题（\(n > 1\)），理论分析表明当且仅当\(n \ge 4\)时问题有解： 对于\(n=4\)的最简问题，有2个解 对于\(n=8\)的原始问题，有92个解 回溯求解 回溯算法又称为试探法，算法思路主要为：每进行一步，都是抱着试试看的态度，如果发现当前选择并不是最好的，或者这么走下去肯定达不到目标，立刻做回退操作重新选择。这种走不通就回退再走的方法就是回溯法，属于递归求解。 对于八皇后问题可以采用回溯法进行逐步求解：逐行进行放置，假设当前考虑在第m行的放置问题，遍历第m行的所有位置，检查是否与前m-1行已放置的皇后冲突（整列检查，两个斜线检查），如果位置仍然可行，则进行临时放置，并进入下一层的放置问题，在子问题退出之后，撤销第m行的临时放置，并考虑m行的下一个位置，直到最后一行放置完成得到一个 ...

Hanoi塔是经典的递归算法的应用，但是有意思的是我之前学习的算法或数据结构的课都漏掉了这个例子，补一下吧，包括两类三种算法实现。 问题介绍 Hanoi塔问题为：考虑三根杆子A，B，C，A杆上有 N 个 (N>1) 穿孔圆盘，圆盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 问：如何移动？最少要移动多少次？ 递归分析 重点关注最大的圆盘，它是整个任务的核心：虽然它在最底层不会影响别的圆盘的操作，但是将它从A移动到C时，必然其他N-1个盘都处于B。 据此可以把问题分解为三个子任务： 将N-1个圆盘从A移动到B，此时C可以用作临时存放区 将最大的圆盘从A直接移动到C 将N-1个圆盘从B移动到C，此时A可以用作临时存放区（和第一步的任务是等价的） 记\(f(n)\)为n个圆盘时最少的移动次数，显然有初值\(f(1)=1\)，以及递推关系 \[ f(n) = 1 + 2f(n-1) \] 因此解得\(f(n)=2^n-1\)为最少移动次数。 这里的理论分析直接提供了递归算法的思路，但是理论分析的结果并非仅仅对递归 ...

问题模型 考虑周期边界的线性常系数扩散方程的求解 \[ u_t = c u_{xx} \] 其中\(c > 0\)为常数，记网格比\(\mu = \frac{\Delta t}{(\Delta x)^2}\)并固定。 显格式 FTCS 直接显式离散可得 \[ v_j^{n+1} = v_j^n + a \mu (v_{j+1}^n - 2 v_j^n + v_{j-1}^n) \] FTCS格式的局部截断误差为\(O(\Delta t + (\Delta x)^2)\)。最大模稳定性要求：\(\mu a \le \frac12\)。 Richardson格式（CTCS，反面示例） 对时间采用中心差分可以得到三层显格式——Richardson格式 \[ v_j^{n+1} = v_j^{n-1} + 2 a \mu (v_{j+1}^n - 2v_j^n + v_{j-1}^n) \] CTCS格式的局部截断误差为\(O((\Delta t)^2+(\Delta x)^2)\)。但这个格式是无条件\(L^2\)模不稳定的！ 基于CTCS格式进行修改，可以得到可用的格式。 Du Fo ...

问题模型 考虑周期边界的线性常系数对流方程的求解 \[ u_t + a u_x = 0 \] 其中风向\(a \neq 0\)为常数，记网格比\(\lambda = \frac{\Delta t}{\Delta x}\)并固定。 显格式 迎风格式（FTFS/FTBS） 对\(u_x\)采用单侧离散可以得到 FTFS（左偏心格式） \[ v_j^{n+1} = v_j^n - a \lambda(v_{j+1}^n - v_j^n) \] FTBS（右偏心格式） \[ v_j^{n+1} = v_j^n - a \lambda(v_{j}^n - v_{j-1}^n) \] 两种格式都具有\(O(\Delta t + \Delta x)\)的局部截断误差。 根据\(a\)的正负性： \(a>0\)：风向从左往右，FTBS是迎风格式，FTFS是逆风格式 \(a<0\)：风向从右往左，FTFS是迎风格式，FTBS是逆风格式 其中迎风格式是有条件\(L^2\)模稳定的，要求：\(|\lambda a| \le 1\)，而逆风格式是无条件\(L^2\)模不稳定的。 迎风格式的 ...