遗传算法

遗传算法的基本思想受到查尔斯·达尔文的自然选择生物进化论的启发。其基本思想是通过从一组完全随机的猜测中进化出最佳解决方案来解决优化问题。理论模型提供了进化发生的框架,而控制它的各个参数则作为遗传构建块。观察结果提供了选择压力。

并行遗传算法图表

最初,参数空间被均匀地填充着试验,这些试验由每个参数的随机选择的值组成,这些值在一个基于参数应该描述的物理范围之内。对每个试验评估模型,并将结果与观察到的数据进行比较,并分配一个与方差成反比的适应度。通过从该种群中随机选择来创建新一代的试验,选择时会根据适应度进行加权。

为了将遗传操作应用于新一代的试验,必须以某种方式对它们的特征进行编码。最直接的编码方式是将参数的数值转换为长字符串。该字符串类似于染色体,每个数字代表一个基因。例如,一个具有数值 x1=1.234 和 y1=5.678 的双参数试验将被编码为单个字符串12345678.

接下来,将编码后的试验配对并修改,以便探索参数空间的新区域。如果没有这一步,最终的解决方案最终可能不会比初始种群中包含的单个最佳试验更好。两个基本操作是交叉,它模拟有性繁殖,以及突变,它模拟偶然事件和宇宙射线。

举例来说,假设上述编码试验与另一个具有 x2=2.468 和 y2=3.579 的试验配对,该试验编码为字符串24683579。交叉程序选择字符串上两个数字之间的随机位置,并将两个字符串从该位置交换到末尾。因此,如果选择第三个位置,则字符串变为

123|45678 -> 123|83579
246|83579 -> 246|45678
虽然交叉的可能性很高,但并非所有配对都应用此操作;这有助于防止有利的特征过快地被消除或损坏。为了达到同样的目的,突变率被赋予相对较低的概率。此操作允许字符串上任何特定位置自发转换为新的随机选择的值。因此,如果将突变操作应用于第二个试验的第六个位置,则结果可能是
24645|6|78 -> 24645|0|78
在应用这些操作之后,这些字符串被解码回参数的数值集。在此示例中,新的第一个字符串12383579变为 x1=1.238 和 y1=3.579,新的第二个字符串24645078变为 x2=2.464 和 y2=5.078。这个新一代取代了旧一代,这个过程再次开始。进化一直持续到参数空间的一个区域保持填充状态,而其他区域基本上变为空。

它的效果比我们尝试之前预期的要好得多。

© . All rights reserved.