玄学,从入门到炼丹 — 初识遗传算法

0 说在之前

正常来说,一个正常的 Oier 是不会碰这种东西

但是我们综合实践小组的组长不知道为啥对这东西出奇的感兴趣, 我就试着理解一下

因为也仅仅是试着理解,如有理论错误还往各位在评论区斧正

本文的代码实现可以在 https://gitee.com/yingziyu/task 看到

1 什么是遗传算法

先来搬运维基百科

遗传算法(英語:genetic algorithm (GA) )是计算数学中用于解决最佳化的搜索算法,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传突变自然选择以及杂交等等。

Wikipedia – 遗传算法

2 使用遗传算法求得旅行商问题近似解

旅行商问题(最短路径问题)(英語:travelling salesman problem, TSP)是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学理论计算机科学中非常重要。

Wikipedia – 旅行推销员问题

首先明确遗传算法要做什么

  1. 生成数个随机生物,形成环境
  2. 交配突变产生新的随机生物
  3. 计算适应度,筛选掉不合适生物
  4. 回到第 2 步

那么这样就会有几个变量

  • 环境中初始生物个数,我们令其为 pn
  • 突变概率,我们令其为 pm
  • 交配概率,我们令其为 pn

在一些算法实现中会加权交配,但是这东西实在是不想写……

2.1 理论实现

如何计算适应度?

这个倒是简单,路径长度的倒数就是其适应度

那么算法就是

  1. 随机生成 pn 条路径
  2. 路径之间随机交叉,生成预备进入下一代环境的生物
  3. 生物根据概率突变
  4. 排序,去除 pn 名后的路径
  5. 回到第 2 步
  • 如何交叉?

随机确定第一个路径中的 $\frac{n}{2}$ 个位置,剩下位置按照第二个路径顺序合并

  • 如何突变?

随机交换路径中两个点就行

2.2 代码实现

一开始是用 cpp 写的,但是把自己写吐了 — 鬼知道他是哪里泄漏的

后来就用 Rust 写了,具体可以看代码里的注释

3 结

这种算法出乎意料的稳定。除去极端情况,都可以生成一个较优的解。

随机化算法中,调参就和炼丹一样,难以知晓结果。在这个算法中也同样体现出来。

但无论如何,这个算法能在极端时间内求出一类问题的较优解是毋庸置疑的。

One thought on “玄学,从入门到炼丹 — 初识遗传算法

  • 魔法师\Woshiluo/

  • 发表回复

    您的电子邮箱地址不会被公开。 必填项已用 * 标注

    message
    account_circle
    Please input name.
    email
    Please input email address.
    links