MetaTrader 5 / 交易系统
English Русский Español Deutsch 日本語 Português
preview
回溯搜索算法（BSA）

回溯搜索算法（BSA）

MetaTrader 5 — 交易系统 |
39 0
Andrey Dik
Andrey Dik


内容

  1. 引言
  2. 算法实现
  3. 测试结果


引言

在无穷无尽的可能性迷宫中，每一次转弯都可能通向成功或死胡同。明智的行者会留下无形的痕迹 —— 某种短暂却更为可靠的标记：对已走过路径的记忆。这一理念（回望过去，预见未来）正是该优化算法的核心。每一步踏入未知，都以过往经验为参照 —— 历史成为罗盘，记忆化作地图。

在本文中，我将介绍一个我认为搜索思路非常有趣的算法。回溯搜索算法（BSA）是由Pinar Civicioglu于2013年提出的一种新型进化算法（EA），用于求解实数域数值优化问题。它是一种能够“从过往经验中学习”的最优解搜索方法。 


算法实现

BSA遵循进化算法的基本原理，但具备独特机制，使用两个种群：
  • 当前种群（P）：正在积极进化的种群；
  • 历史种群（oldP）：由先前种群保留下来的历史副本，并在后续过程中随机打乱使用。

BSA采用随机变异策略，为每个目标个体仅生成一个定向解。变异公式：

Mutant = P + F × (oldP - P)

其中，F为幅值系数，用于控制搜索步长。

BSA的交叉过程分为两步：第一种策略使用“混合率”（mixrate）；第二种策略允许在每个试验向量中仅修改一个随机选中的坐标。想象一下，您和朋友们（也就是种群）正在寻找全城最好的披萨店。 

初始状态：

  • 您有10个朋友（种群大小），
  • 每个人从城市的随机区域开始搜索，
  • 每个人都有一部手机，里面保存着过去出行路线的地图（即历史记忆）。

第一天：大家分头出发寻找披萨店，第一个朋友找到评分7/10的店，第二个找到评分5/10的店，第三个找到评分8/10的店…… 依此类推。

第二天：利用积累的经验

步骤1：“回忆过去”（选择阶段I）。算法像抛硬币一样随机决定：正面为“记住大家昨天的位置”（更新历史）；反面为“沿用旧记忆”（不更新），然后“打乱记忆顺序”（像洗牌一样）。

步骤2：“循着轨迹前进”（变异）。每个人都会思考：我现在在哪？（当前位置）和我之前在哪？（历史位置）。移动公式：新位置 = 当前位置 + 随机步长 ×（历史位置 − 当前位置）。举个例子：朋友现在在A街10号，他“过去的位置映像”在B街20号，随机步长 = 2。新位置 = A街10号 + 2 ×（B街20号 − A街10号），相当于向B街方向移动，并且是两倍距离！

步骤3：“修正路线（交叉）”。算法再次随机选择策略。策略A：“部分修改”。原本要去某个地址，算法要求：“保留原来的门牌号，只修改街道地址”。结果：我们只替换地址中的一部分信息。策略B：“最小修改”。第一个朋友原本要去某个地址，算法要求：“保留原来的街道，只修改门牌号”。结果：我们保留原地址，仅修改一个坐标。

步骤4：“评估最终结果”（选择阶段II）。第一个朋友到达新地点后：

  • 如果新披萨店更好（评分9/10）：“太棒了，就待在这！”
  • 如果更差（评分4/10）：“不行，我回去！”

下图展示了该算法的运行流程。

BSA

图例1. BSA算法阶段

此示意图展示了BSA在二维空间中寻找最优解的过程。您可以把它看作一张俯视的地形图，我们的目标是找到最高点（中心红点）。

示意图分为三个部分，展示搜索的进化过程：迭代1 —— 随机初始化。带等高线的方形搜索区域（类似地形图）中心有一个红点，代表全局最优解（最佳方案）。四个蓝点（P1、P2、P3、P4）是“探索者”的初始随机位置。算法在整个搜索空间内随机放置四个智能体。在这一步，历史种群等于当前种群：oldP = P，这是搜索的起点。

迭代2 —— 变异步骤。蓝点为智能体的当前位置；半透明绿点为来自历史记忆的位置（已打乱）；红色箭头为变异时的移动方向。

核心要点：红色箭头体现了变异公式的实际效果：M=P+F×(oldP−P)。每个智能体都相对于自己的“历史对应位置”进行移动。部分箭头指向历史位置，另一部分则背离历史位置（取决于 F 的符号）。红框内公式：F = 3 × randn(); M = P + F × (oldP - P)。这是BSA变异操作的核心公式。

迭代 3 —— 交叉与选择之后。 紫点为交叉后的新位置（试验种群）；半透明蓝点为先前位置（用于对比）；绿色箭头显示仅保留更优的移动（新位置优于旧位置）。交叉：算法融合了变异种群与当前种群的信息。贪婪选择：只保留能提升解质量的移动，种群整体向最优点（中心红点）靠近。

BSA流程总结（用彩色圆圈表示完整算法循环）：
  1. 初始化（蓝色）—— 随机起点
  2. 选择I（绿色）—— 以50%概率更新记忆
  3. 变异（红色）—— 执行变异公式
  4. 交叉（紫色）—— 解的信息融合
  5. 评估（橙色）—— 计算适应度
  6. 选择II（青绿色）—— 贪婪择优

虚线箭头表示过程会不断重复，直至算法收敛。此图清晰地说明了BSA为何高效：它会“记住”曾经到过的位置，并利用这些信息进行更智能的搜索，而非简单的随机游走。

我们现在进入BSA的伪代码部分。

运行准备

参数初始化：

  • 设置种群大小； 
  • 设置交叉参数mixrate； 
  • 创建空容器用于存储：
    • 当前种群
    • 历史种群
    • 变异种群
    • 试验种群
    • 每个个体的交叉映射图

初始化：

  • 将历史种群中的所有个体随机放置在搜索空间内；
  • 如果已设定步长，则考虑离散化处理；
  • 将“需要选择”标识位设置为“否”。

算法主循环：

步骤1：首次初始化

如果是第一次迭代：

  • 随机初始化当前的种群；
  • 对坐标进行离散化处理；
  • 标记初始化已完成；
  • 退出当前步骤，等待计算适应度。

步骤2：贪婪选择（如需执行）

如果“需要选择”标志位为true：

  • 对于每个个体，比较：
    • 如果新解劣于已保存的解，则恢复原坐标与适应度；
    • 如果新解更优，则保留新解。
  • 重置选择标识位。

步骤3：保存当前状态

对于每个个体：

  • 保存当前适应度；
  • 保存当前坐标副本。

步骤4：更新历史记忆（选择阶段I）

  • 随机抛硬币（50%概率），
  • 如果硬币为正面：
    • 将整个当前种群复制到历史记忆中；
    • 保留其适应度值；
  • 对历史种群进行洗牌操作：
    • 从最后一个个体遍历至第一个；
    • 为每个个体随机选取一个位置进行交换；
    • 执行交换。

步骤5：变异

  • 从正态分布中生成移动因子F：
    • 均值为0，取值范围为[-3, +3]；
    • 类似掷骰子，但服从钟形分布。
  • 对每个个体的每一维坐标：
    • 新位置 = 当前位置 + F ×（历史位置 − 当前位置）。
    • 如果F大于0 → 向历史位置方向移动；
    • 如果F小于0 → 背离历史位置移动。

步骤6：交叉

  • 将变异种群复制到试验种群，
  • 抛加权硬币（40%/60%）：

如果选中40%分支（策略1）： 

对于每个个体：

  • 确定需要修改的坐标数量（从0个到全部，依据混合率mixrate）；
  • 随机选中这些坐标；
  • 对于选中的坐标，从当前种群中取值；
  • 其余坐标保留变异种群的值。

如果选中60%分支（策略2）：

对于每个个体：

  • 仅随机选择一个坐标；
  • 用当前种群中的对应值替换它；
  • 其余所有坐标保留变异种群的值。

步骤7：边界约束处理

对试验种群中的每个个体：

  • 检查每一维坐标
  • 如果超出搜索边界：
    • 抛硬币（50%/50%）
    • 如果为“正面” → 在边界范围内重新生成随机值；
    • 如果为“反面” → 将坐标设为最近的边界点。
  • 如果已指定步长，则执行离散化处理。

步骤8：评估准备

  • 将试验种群复制到主种群以待评估；
  • 将“需要选择”标识位设置为“是”；
  • 移交控制权至适应度计算模块。

适应度计算完成后： 

  • 找出适应度最优的个体。
  • 如果找到优于全局最优记录的解：
    • 更新全局最优记录；
    • 保存最优解的坐标。

循环迭代

返回步骤2继续执行，直至：

  • 算法达到收敛条件，
  • 或达到最大迭代次数上限。

在理清核心逻辑后，我们开始编写算法代码。CAOBSABacktracking类是BSA回溯搜索算法的一种实现，用于求解优化问题。该类继承自优化算法通用接口基类C_AO。 

主要特性与用途：

优化参数：
  • popSize —— 种群规模，即算法同时优化的“智能体”或“解”的数量。 
  • mixrate —— 交叉参数，用于控制生成新解时，不同智能体之间信息“混合”的程度。 
初始化：
  • 类构造函数初始化基础参数，并将popSize和mixrate添加到参数数组params中，用于统一管理算法参数。
  • SetParams方法支持根据params数组更新算法内部参数，并包含基础的数值合法性校验。
算法生命周期（方法）：
  • Init —— 算法初始化设置，包括变量取值范围（最小值、最大值、步长）及优化迭代轮数。
  • Moving —— 描述算法主迭代逻辑，基于当前种群生成新的候选解，完成解的“移动”更新。
  • Revision —— 评估生成的解，并根据解的质量更新种群。
算法内部的数据结构：
  • oldP —— 存储“历史”或上一代智能体种群的数组。
  • M —— 存储变异后种群的数组。
  • T —— “试验”种群数组，用于与当前种群对比，为种群更新决策提供依据。
  • F —— 变异幅值系数，控制变异操作的变化幅度。
  • needSelection —— 标记是否需要执行第二阶段选择的标识位。
  • prevFitness —— 存储上一代智能体适应度值的数组。
  • S_Map —— 包含二进制映射表的辅助结构，在交叉阶段用于确定哪些智能体变量需要从不同父代中“混合”。
  • map —— 二进制映射表数组，每个智能体对应一张映射表。
算法核心步骤（内部方法）：
  • SelectionI —— 第一阶段选择，用于更新并打乱历史种群，以供后续变异使用。
  • Mutation —— 对选中的智能体执行变异操作。
  • Crossover —— 对智能体执行交叉（信息混合）操作，生成新的“试验”解。
  • BoundaryControl —— 校验智能体参数是否在设定的上下限范围内。
  • ShufflePopulation —— 种群随机打乱方法。

因此，C_AO_BSA_Backtracking类实现了一种进化优化算法，结合种群、变异、交叉机制，以及BSA特有的回溯记忆机制，用于求解各类优化问题。

//————————————————————————————————————————————————————————————————————
class C_AO_BSA_Backtracking : public C_AO
{
  public: //----------------------------------------------------------
  ~C_AO_BSA_Backtracking () { }
  C_AO_BSA_Backtracking ()
  {
    ao_name = "BSA";
    ao_desc = "Backtracking Search Algorithm";
    ao_link = "https://www.mql5.com/en/articles/18568";

    popSize = 10;     // population size
    mixrate = 1.0;    // crossover parameter

    ArrayResize (params, 2);

    params [0].name = "popSize"; params [0].val = popSize;
    params [1].name = "mixrate"; params [1].val = mixrate;
  }

  void SetParams ()
  {
    popSize = (int)params [0].val;
    mixrate = params      [1].val;

    // Check the parameters validity
    //if (popSize < 2) popSize = 2;
    if (mixrate < 0.0) mixrate = 0.0;
    if (mixrate > 1.0) mixrate = 1.0;
  }

  bool Init (const double &rangeMinP  [],  // minimum values
             const double &rangeMaxP  [],  // maximum values
             const double &rangeStepP [],  // step change
             const int     epochsP = 0);   // number of epochs

  void Moving   ();
  void Revision ();

  //------------------------------------------------------------------
  double mixrate;        // crossover parameter

  private: //---------------------------------------------------------
  S_AO_Agent oldP [];    // historical population
  S_AO_Agent M    [];    // mutant population (Mutant)
  S_AO_Agent T    [];    // trial population (Trial)

  double F;              // amplitude factor for mutation
  bool   needSelection;  // flag for the necessity of executing Selection-II
  double prevFitness []; // array for storing previous fitness

  // Auxiliary structures for crossover
  struct S_Map
  {
      int val [];      // binary map for crossover

      void Init (int size)
      {
        ArrayResize (val, size);
        ArrayInitialize (val, 0);
      }
  };

  S_Map map [];        // array of binary maps for each agent

  // Algorithm methods
  void SelectionI        ();
  void Mutation          ();
  void Crossover         ();
  void BoundaryControl   (S_AO_Agent &agent);
  void ShufflePopulation (S_AO_Agent &pop []);
};
//————————————————————————————————————————————————————————————————————

Init方法负责在优化开始前完成算法的初始化准备工作。首先，调用基础初始化函数，设置与变量取值范围相关的基础参数（最小值、最大值及变动步长）。如果该基础步骤执行失败，则方法立即终止并返回失败。

接下来，为BSA算法特有的内部数据结构分配内存并完成初始化。具体包括创建并设置为所需大小的各类种群数组：历史种群oldP、变异种群M、试验种群T，以及用于交叉操作的二进制映射数组“map”和用于存储每个智能体上一代适应度值的prevFitness数组。附加选择需求的标识位初始设置为false。

之后调用种群中每个智能体的初始化方法，根据任务参数数量完成各智能体内部结构的准备。

接下来，对历史种群填充初始数值。对于每个智能体的每一项参数，在指定范围内生成随机值，再按照设定的变动步长进行规整。如果所有步骤均顺利完成，该方法将返回成功标识，表明算法对象已初始化完毕，可进入后续优化流程。

//————————————————————————————————————————————————————————————————————
//--- Initialization
bool C_AO_BSA_Backtracking::Init (const double &rangeMinP  [],
                                  const double &rangeMaxP  [],
                                  const double &rangeStepP [],
                                  const int epochsP = 0)
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //------------------------------------------------------------------
  // Initialize additional BSA structures
  ArrayResize (oldP, popSize);
  ArrayResize (M,    popSize);
  ArrayResize (T,    popSize);
  ArrayResize (map,  popSize);
  ArrayResize (prevFitness, popSize);

  needSelection = false;

  for (int i = 0; i < popSize; i++)
  {
    oldP [i].Init (coords);
    M    [i].Init (coords);
    T    [i].Init (coords);
    map  [i].Init (coords);
  }

  // Initialize oldP historical population
  for (int p = 0; p < popSize; p++)
  {
    for (int c = 0; c < coords; c++)
    {
      oldP [p].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
      oldP [p].c [c] = u.SeInDiSp (oldP [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }

  return true;
}
//————————————————————————————————————————————————————————————————————

Moving方法描述了BSA优化算法的主迭代步骤，负责在种群中生成新的候选解。当方法第一次被调用且"revision"标识为false时，会先初始化活跃种群"a"：对种群中每个智能体的每一项参数，在设定的上下界范围内生成随机值；再按指定的参数步长对随机值进行规整。初始化完成后，将"revision"标识设置为true（避免后续重复执行），并清空needSelection标识，该方法终止。

执行贪婪选择（选择阶段II，按需执行）：如果needSelection为true，表示上一步已生成新种群，需要将其适应度与旧解对比。遍历种群中的每个智能体：将当前智能体"a[i].f"的适应度（对应“试验”解）与保存在prevFitness[i]中的上一代适应度对比，如果“试验”解a[i]更差，则从"a [i].cP"（上一步坐标）恢复当前坐标"a [i].c"，并将适应度"a [i].f"恢复为prevFitness[i]。这样保证种群性能不会退化。选择完成后，重置needSelection标识。

BSA算法基本步骤（初始化或选择之后）：在生成新解之前，将所有智能体的当前适应度"a"保存至prevFitness，供后续选择阶段II使用，并且将智能体当前坐标"a [i].c"复制到"a [i].cP"中，以便新解变差时可以回滚。

调用内部SelectionI方法：这一步负责选择或准备用于变异的“存档”历史种群oldP。调用内部Mutation方法：在此步骤中，基于当前种群和/或历史种群生成“变异”种群M。调用内部Crossover方法：在此步骤中，将变异种群M与当前活跃种群a进行信息混合，生成“试验”种群T。

将生成的试验种群T中智能体的坐标复制到当前活跃种群a中。此时a包含了需要计算适应度的新试验解。将needSelection标识设置为true，表示下次调用Moving时（a中的新解适应度计算完成后），需要执行贪婪选择（选择阶段II）。

    因此，Moving方法封装了BSA算法的一次完整迭代或“周期”，包括初始化、选择、变异、交叉，以及结果对比的准备工作。

    //————————————————————————————————————————————————————————————————————
//--- The main step of the algorithm
void C_AO_BSA_Backtracking::Moving ()
{
  // Initial population setup
  if (!revision)
  {
    for (int p = 0; p < popSize; p++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [p].c  [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        a [p].c  [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision      = true;
    needSelection = false;
    return;
  }

  // If you want to perform greedy selection after calculating fitness
  if (needSelection)
  {
    // Selection-II: Greedy selection
    for (int i = 0; i < popSize; i++)
    {
      // If the current solution (from T) is worse than the previous one, return the previous one
      if (a [i].f < prevFitness [i])
      {
        ArrayCopy (a [i].c, a [i].cP, 0, 0, WHOLE_ARRAY);
        a [i].f = prevFitness [i];
      }
    }

    needSelection = false;
  }

  //--- BSA basic steps:

  // Save current fitness before generating a new population 
  for (int i = 0; i < popSize; i++)
  {
    prevFitness [i] = a [i].f;
    ArrayCopy (a [i].cP, a [i].c, 0, 0, WHOLE_ARRAY);
  }

  // 1. Selection-I
  SelectionI ();

  // 2. Mutation
  Mutation ();

  // 3. Crossover
  Crossover ();

  // 4. Copy the trial population T into the 'a' main population to calculate fitness
  for (int i = 0; i < popSize; i++)
  {
    ArrayCopy (a [i].c, T [i].c, 0, 0, WHOLE_ARRAY);
  }

  // Set the flag to execute Selection-II after calculating fitness
  needSelection = true;
}
//————————————————————————————————————————————————————————————————————

    SelectionI方法实现了BSA算法的第一阶段选择，负责确定后续用于变异操作的历史种群。

    历史种群的概率更新：以50%的概率（或者简言之以等概率），用当前种群a覆盖更新历史种群oldP。 如果生成的随机数小于阈值（0.5），则将当前种群a中每个个体的坐标c和适应度f，完整复制到历史种群oldP对应的智能体中。

    打乱历史种群：无论上一步是否更新了历史种群，都会调用ShufflePopulation(oldP)方法对历史种群内的智能体进行随机打乱。这一步是为了在变异过程中引入随机性，确保历史种群中的智能体按随机顺序参与计算，而非保持原有顺序。

      因此，SelectionI会以一定概率用当前解更新历史种群，或保留原有状态，并在两种情况下均对历史种群进行打乱，从而在后续变异中实现搜索的多样化。

      //————————————————————————————————————————————————————————————————————
//--- Selection-I: select a historical population
void C_AO_BSA_Backtracking::SelectionI ()
{
  // Update the historical population with a 50% probability 
  if (u.RNDprobab () < 0.5) // equivalent to if (a < b) where a,b ~ U(0,1)
  {
    // Copy the current population to the historical one
    for (int i = 0; i < popSize; i++)
    {
      ArrayCopy (oldP [i].c, a [i].c, 0, 0, WHOLE_ARRAY);
      oldP [i].f = a [i].f;
    }
  }

  // Shuffle the historical population
  ShufflePopulation (oldP);
}
//————————————————————————————————————————————————————————————————————

      ShufflePopulation方法用于对指定的智能体种群（由S_AO_Agent结构体表示）进行随机打乱。它接收智能体数组pop[]并执行原地洗牌，即直接修改传入数组中元素的顺序。

      打乱算法：该方法使用Fisher–Yates洗牌算法对种群元素随机打乱，此算法可保证元素的每种排列出现概率均等。

      "for"循环从数组最后一个元素（popSize - 1）开始，倒序遍历到第二个元素（索引1）。第一个元素（索引0）无需处理，因为在算法执行到它之前已被移动过。对每个索引为i的元素，在区间0至1内随机选取一个索引j。通过u.RNDminusOne(i+1)函数实现，该函数返回一个指定范围内的随机整数（包含0，但不包含i+1）。

      交换索引i和j对应的元素。使用S_AO_Agent类型的临时变量temp完成交换。由于S_AO_Agent包含坐标数组c，交换时会完整复制数组，同时会一并复制适应度值f。先将pop[i]的坐标与适应度存入临时变量temp中，再将pop[j]的值复制到pop[i]中，最后将temp中保存的原pop[i]复制到pop[j]中。循环结束后，pop[]数组内的元素顺序即为随机排列。

      //————————————————————————————————————————————————————————————————————
//--- Shuffle population
void C_AO_BSA_Backtracking::ShufflePopulation (S_AO_Agent &pop [])
{
  for (int i = popSize - 1; i > 0; i--)
  {
    int j = u.RNDminusOne (i + 1);

    // Swap i and j elements
    S_AO_Agent temp;
    temp.Init (coords);

    ArrayCopy (temp.c, pop [i].c, 0, 0, WHOLE_ARRAY);
    temp.f = pop [i].f;

    ArrayCopy (pop [i].c, pop [j].c, 0, 0, WHOLE_ARRAY);
    pop [i].f = pop [j].f;

    ArrayCopy (pop [j].c, temp.c, 0, 0, WHOLE_ARRAY);
    pop [j].f = temp.f;
  }
}
//————————————————————————————————————————————————————————————————————

      Mutation方法负责生成变异种群，这是BSA算法中的关键步骤。其核心思想是利用当前种群与历史种群的差值进行变异。

      首先，生成一个随机的幅值系数F，用于控制历史种群对当前种群的影响幅度。随后，对种群中的每个智能体、以及智能体的每一维坐标，计算变异种群中对应坐标的新值：变异坐标 = 当前坐标 + F ×（历史种群对应坐标 − 当前坐标）。因此，变异种群由当前种群向历史种群方向偏移形成，偏移幅度由系数 F 决定。

      //————————————————————————————————————————————————————————————————————
//--- Mutation: generation of a mutant population
void C_AO_BSA_Backtracking::Mutation ()
{
  // Generate the amplitude factor
  F = u.GaussDistribution (0.0, -3.0, 3.0, 2);

  // Apply mutation: M = P + F * (oldP - P)
  for (int i = 0; i < popSize; i++)
  {
    for (int j = 0; j < coords; j++)
    {
      M [i].c [j] = a [i].c [j] + F * (oldP [i].c [j] - a [i].c [j]);
    }
  }
}
//————————————————————————————————————————————————————————————————————

      Crossover方法用于在当前变异种群的基础上，通过选定的交叉策略生成试验种群。该过程旨在融合不同父代解的特征，以寻找更优的解。

      首先，将变异种群完整复制为试验种群，作为后续修改的基础。随后随机选择交叉策略：40%概率使用策略一，其余情况使用策略二。

      如果选中策略一，则执行mixrate混合策略，对于每个智能体，根据设定的混合系数mixrate，确定需要从当前种群中取用的坐标维度数量。通过随机且不重复地选出这些维度，然后将试验种群对应位置的坐标替换为当前种群的坐标值。

      如果选中策略二，则对每个智能体，仅随机选取一个坐标维度，并将试验种群中该位置的值替换为当前种群的对应值。

      交叉完成后，对试验种群中的每个个体执行边界校验，确保所有解均合法且在允许的取值范围内。

      //————————————————————————————————————————————————————————————————————
//--- Crossover: trial population generation
void C_AO_BSA_Backtracking::Crossover ()
{
  // Initialize the trial population as a copy of the mutant one
  for (int i = 0; i < popSize; i++)
  {
    ArrayCopy (T [i].c, M [i].c, 0, 0, WHOLE_ARRAY);
  }

  // Select a crossover strategy
  if (u.RNDprobab () < 0.4)
  {
    //--- STRATEGY 1: Using mixrate
    for (int i = 0; i < popSize; i++)
    {
      // Reset the map
      ArrayInitialize (map [i].val, 0);

      // Define the number of elements for the crossover
      int numElements = (int)MathCeil (mixrate * u.RNDprobab () * coords);

      // Generate unique indices for the crossover
      for (int n = 0; n < numElements; n++)
      {
        int idx;
        do
        {
          idx = u.RNDminusOne (coords);
        }
        while (map [i].val [idx] == 1); // until we find an unused index

        map [i].val [idx] = 1;
      }

      // Apply crossover
      for (int j = 0; j < coords; j++)
      {
        if (map [i].val [j] == 1)
        {
          T [i].c [j] = a [i].c [j];
        }
      }
    }
  }
  else
  {
    //--- STRATEGY 2: Mutation of only one element
    for (int i = 0; i < popSize; i++)
    {
      // Select one random element
      int randomIndex = u.RNDminusOne (coords);
      T [i].c [randomIndex] = a [i].c [randomIndex];
    }
  }

  // Boundary control for all agents in the trial population
  for (int i = 0; i < popSize; i++)
  {
    BoundaryControl (T [i]);
  }
}
//————————————————————————————————————————————————————————————————————

      BoundaryControl方法用于检查并修正智能体的参数值，使其保持在允许范围内，同时将解规整为指定的离散格式。

      对智能体坐标中的每一个分量进行检查：如果数值超出设定的最小值或最大值，则按选定策略处理，如果随机概率小于50%，则在合法范围内重新随机生成一个值；否则，将该值设为最近的边界值（最小值或最大值）。

      之后，对每个坐标值进行离散化处理，即根据指定的取值范围和离散步长，将数值舍入到最接近的合法值。这一步确保最终解符合数据类型与范围约束。

      //————————————————————————————————————————————————————————————————————
//--- Boundary control
void C_AO_BSA_Backtracking::BoundaryControl (S_AO_Agent &agent)
{
  for (int j = 0; j < coords; j++)
  {
    if (agent.c [j] < rangeMin [j] || agent.c [j] > rangeMax [j])
    {
      // Select a boundary handling strategy
      if (u.RNDprobab () < 0.5)
      {
        // Random regeneration
        agent.c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]);
      }
      else
      {
        // Set to the boundary
        if (agent.c [j] < rangeMin [j]) agent.c [j] = rangeMin [j];
        else agent.c [j] = rangeMax [j];
      }
    }

    // Discretization
    agent.c [j] = u.SeInDiSp (agent.c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
  }
}
//————————————————————————————————————————————————————————————————————

      Revision方法负责筛选并更新当前种群中的最优解。通过遍历所有解，寻找评估函数（适应度）值最大的那个解。如果找到更优解，就将其保存为当前最优结果，并把该解的坐标复制到专门用于存储当前最优解的数组中。该方法实现了在算法迭代过程中，对最优解的持续追踪与更新。

      //————————————————————————————————————————————————————————————————————
//--- Selection-II and updating the best solution
void C_AO_BSA_Backtracking::Revision ()
{
  int bestIND = -1;

  for (int i = 0; i < popSize; i++)
  {
    // Update the global best solution
    if (a [i].f > fB)
    {
      fB = a [i].f;
      bestIND = i;
    }
  }

  // Copy the coordinates of the best solution
  if (bestIND != -1)
  {
    ArrayCopy (cB, a [bestIND].c, 0, 0, WHOLE_ARRAY);
  }
}
//————————————————————————————————————————————————————————————————————

      GaussDistribution方法用于生成服从高斯（正态）分布的随机数，分布以指定输入值为中心，并限定在一定范围内。该方法采用Box-Muller算法生成正态分布随机变量。

      首先，生成两个均匀分布的随机变量。基于这两个值，计算出一个标准正态分布随机变量，以此作为高斯分布的基础。

      随后检查生成的值是否落在由参数sigma定义的标准差范围内。如果超出限制，则递归调用本方法重新生成，直到数值落在允许区间内。

      最后，将生成的正态分布变量以输入值In作为基准，进行缩放与平移，使其落在指定输出范围[outMin, outMax]内。这样可以对分布进行平移与缩放，以匹配所需参数。最终得到的是以In为中心、同时受最小/最大值约束的高斯分布随机数。

      //——————————————————————————————————————————————————————————————————————————————
double C_AO_Utilities :: GaussDistribution (const double In, const double outMin, const double outMax, const double sigma)
{
  double logN = 0.0;
  double u1   = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0);
  double u2   = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0);

  logN = u1 <= 0.0 ? 0.000000000000001 : u1;

  double z0 = sqrt (-2 * log (logN)) * cos (2 * M_PI * u2);

  double sigmaN = sigma > 8.583864105157389 ? 8.583864105157389 : sigma;
  
  // If z0 is outside the range [-sigmaN, sigmaN], generate anew
  if (z0 >= sigmaN || z0 <= -sigmaN) 
  {
    return GaussDistribution(In, outMin, outMax, sigma); // Recursive call
  }

  if (z0 >= 0.0) z0 =  Scale (z0,        0.0, sigmaN, 0.0, outMax - In, false);
  else           z0 = -Scale (fabs (z0), 0.0, sigmaN, 0.0, In - outMin, false);
  
  return In + z0;
}
//——————————————————————————————————————————————————————————————————————————————


      测试结果

      BSA算法呈现出非常优异的效果。

      BSA|回溯搜索算法|10.0|1.0|
      =============================
      5 Hilly's；函数运行次数：10000；结果：0.9730917210619289
      25 Hilly's；函数运行次数：10000；结果：0.5453406317593932
      500 Hilly's；函数运行次数：10000；结果：0.2909827609772065
      =============================
      5 Forest's；函数运行次数：10000；结果：0.9999986842258451
      25 Forest's；函数运行次数：10000；结果：0.5854340780208712
      500 Forest's；函数运行次数：10000；结果：0.21747482800959225
      =============================
      5 Megacity's；函数运行次数：10000；结果：0.8476923076923077
      25 Megacity's；函数运行次数：10000；结果：0.3695384615384615
      500 Megacity's；函数运行次数：10000；结果： 0.12978461538461658
      =============================
      总分：4.95934（55.10%）

      根据BSA算法的可视化结果，在低维和中维函数上，优化结果存在一定的离散波动；然而，随着种群规模参数的增大，波动会减小；但要获得更好的收敛效果，需要相应增加迭代次数。

      Hilly值

      BSA在Hilly测试函数上

      Forest值

      BSA在Forest测试函数上

      Megacity值

      BSA在Megacity测试函数上

      BSA算法在基于种群优化算法排行榜中位列第20位。

      # AO 描述 Hilly值 Hilly
      最终       		Forest值 Forest
      最终       		Megacity (离散) Megacity
      最终       		最终
      结果       		% of
      最大
      10 p (5 F) 50 p (25 F) 1000 p (500 F) 10 p (5 F) 50 p (25 F) 1000 p (500 F) 10 p (5 F) 50 p (25 F) 1000 p (500 F)
      1 ANS 跨邻域搜索 0.94948 0.84776 0.43857 2.23581 1.00000 0.92334 0.39988 2.32323 0.70923 0.63477 0.23091 1.57491 6.134 68.15
      2 CLA 密码锁算法（joo） 0.95345 0.87107 0.37590 2.20042 0.98942 0.91709 0.31642 2.22294 0.79692 0.69385 0.19303 1.68380 6.107 67.86
      3 AMOm 动物迁徙优化M 0.90358 0.84317 0.46284 2.20959 0.99001 0.92436 0.46598 2.38034 0.56769 0.59132 0.23773 1.39675 5.987 66.52
      4 (P+O)ES (P+O) 进化策略 0.92256 0.88101 0.40021 2.20379 0.97750 0.87490 0.31945 2.17185 0.67385 0.62985 0.18634 1.49003 5.866 65.17
      5 CTA 彗星尾算法（joo） 0.95346 0.86319 0.27770 2.09435 0.99794 0.85740 0.33949 2.19484 0.88769 0.56431 0.10512 1.55712 5.846 64.96
      6 TETA 时间演化旅行算法（joo） 0.91362 0.82349 0.31990 2.05701 0.97096 0.89532 0.29324 2.15952 0.73462 0.68569 0.16021 1.58052 5.797 64.41
      7 SDSm 随机扩散搜索 M 0.93066 0.85445 0.39476 2.17988 0.99983 0.89244 0.19619 2.08846 0.72333 0.61100 0.10670 1.44103 5.709 63.44
      8 BOAm 台球优化算法M 0.95757 0.82599 0.25235 2.03590 1.00000 0.90036 0.30502 2.20538 0.73538 0.52523 0.09563 1.35625 5.598 62.19
      9 AAm 射箭算法M 0.91744 0.70876 0.42160 2.04780 0.92527 0.75802 0.35328 2.03657 0.67385 0.55200 0.23738 1.46323 5.548 61.64
      10 ESG 社会群体的进化（joo） 0.99906 0.79654 0.35056 2.14616 1.00000 0.82863 0.13102 1.95965 0.82333 0.55300 0.04725 1.42358 5.529 61.44
      11 SIA 模拟各向同性退火（joo） 0.95784 0.84264 0.41465 2.21513 0.98239 0.79586 0.20507 1.98332 0.68667 0.49300 0.09053 1.27020 5.469 60.76
      12 BBO 生物地理学优化算法 0.94912 0.69456 0.35031 1.99399 0.93820 0.67365 0.25682 1.86867 0.74615 0.48277 0.17369 1.40261 5.265 58.50
      13 ACS 人工协同搜索 0.75547 0.74744 0.30407 1.80698 1.00000 0.88861 0.22413 2.11274 0.69077 0.48185 0.13322 1.30583 5.226 58.06
      14 DA 辩证算法 0.86183 0.70033 0.33724 1.89940 0.98163 0.72772 0.28718 1.99653 0.70308 0.45292 0.16367 1.31967 5.216 57.95
      15 BHAm 黑洞算法M 0.75236 0.76675 0.34583 1.86493 0.93593 0.80152 0.27177 2.00923 0.65077 0.51646 0.15472 1.32195 5.196 57.73
      16 ASO 无序社会优化 0.84872 0.74646 0.31465 1.90983 0.96148 0.79150 0.23803 1.99101 0.57077 0.54062 0.16614 1.27752 5.178 57.54
      17 RFO 皇家同花顺优化（joo） 0.83361 0.73742 0.34629 1.91733 0.89424 0.73824 0.24098 1.87346 0.63154 0.50292 0.16421 1.29867 5.089 56.55
      18 AOSm 原子轨道搜索M 0.80232 0.70449 0.31021 1.81702 0.85660 0.69451 0.21996 1.77107 0.74615 0.52862 0.14358 1.41835 5.006 55.63
      19 TSEA 龟壳演化算法（joo） 0.96798 0.64480 0.29672 1.90949 0.99449 0.61981 0.22708 1.84139 0.69077 0.42646 0.13598 1.25322 5.004 55.60
      20 BSA 回溯搜索算法 0.97309 0.54534 0.29098 1.80941 0.99999 0.58543 0.21747 1.80289 0.84769 0.36953 0.12978 1.34700 4.959 55.10
      21 DE 差分进化 0.95044 0.61674 0.30308 1.87026 0.95317 0.78896 0.16652 1.90865 0.78667 0.36033 0.02953 1.17653 4.955 55.06
      22 SRA 成功餐饮经营者算法 (joo) 0.96883 0.63455 0.29217 1.89555 0.94637 0.55506 0.19124 1.69267 0.74923 0.44031 0.12526 1.31480 4.903 54.48
      23 CRO 化学反应优化 0.94629 0.66112 0.29853 1.90593 0.87906 0.58422 0.21146 1.67473 0.75846 0.42646 0.12686 1.31178 4.892 54.36
      24 BIO 血液遗传优化算法（joo） 0.81568 0.65336 0.30877 1.77781 0.89937 0.65319 0.21760 1.77016 0.67846 0.47631 0.13902 1.29378 4.842 53.80
      25 BSA 鸟群算法 0.89306 0.64900 0.26250 1.80455 0.92420 0.71121 0.24939 1.88479 0.69385 0.32615 0.10012 1.12012 4.809 53.44
      26 DEA 海豚回声定位算法 0.75995 0.67572 0.34171 1.77738 0.89582 0.64223 0.23941 1.77746 0.61538 0.44031 0.15115 1.20684 4.762 52.91
      27 HS 和声搜索 0.86509 0.68782 0.32527 1.87818 0.99999 0.68002 0.09590 1.77592 0.62000 0.42267 0.05458 1.09725 4.751 52.79
      28 SSG 树苗播种和生长 0.77839 0.64925 0.39543 1.82308 0.85973 0.62467 0.17429 1.65869 0.64667 0.44133 0.10598 1.19398 4.676 51.95
      29 BCOm 细菌趋化性优化算法M 0.75953 0.62268 0.31483 1.69704 0.89378 0.61339 0.22542 1.73259 0.65385 0.42092 0.14435 1.21912 4.649 51.65
      30 ABO 非洲水牛优化 0.83337 0.62247 0.29964 1.75548 0.92170 0.58618 0.19723 1.70511 0.61000 0.43154 0.13225 1.17378 4.634 51.49
      31 (PO)ES (PO) 进化策略 0.79025 0.62647 0.42935 1.84606 0.87616 0.60943 0.19591 1.68151 0.59000 0.37933 0.11322 1.08255 4.610 51.22
      32 FBA 基于分形的算法 0.79000 0.65134 0.28965 1.73099 0.87158 0.56823 0.18877 1.62858 0.61077 0.46062 0.12398 1.19537 4.555 50.61
      33 TSm 禁忌搜索M 0.87795 0.61431 0.29104 1.78330 0.92885 0.51844 0.19054 1.63783 0.61077 0.38215 0.12157 1.11449 4.536 50.40
      34 BSO 头脑风暴优化 0.93736 0.57616 0.29688 1.81041 0.93131 0.55866 0.23537 1.72534 0.55231 0.29077 0.11914 0.96222 4.498 49.98
      35 WOAm 鲸鱼优化算法M 0.84521 0.56298 0.26263 1.67081 0.93100 0.52278 0.16365 1.61743 0.66308 0.41138 0.11357 1.18803 4.476 49.74
      36 AEFA 人工电场算法 0.87700 0.61753 0.25235 1.74688 0.92729 0.72698 0.18064 1.83490 0.66615 0.11631 0.09508 0.87754 4.459 49.55
      37 AEO 基于人工生态系统的优化算法 0.91380 0.46713 0.26470 1.64563 0.90223 0.43705 0.21400 1.55327 0.66154 0.30800 0.28563 1.25517 4.454 49.49
      38 CAm 骆驼算法M 0.78684 0.56042 0.35133 1.69859 0.82772 0.56041 0.24336 1.63149 0.64846 0.33092 0.13418 1.11356 4.444 49.37
      39 ACOm 蚁群优化M 0.88190 0.66127 0.30377 1.84693 0.85873 0.58680 0.15051 1.59604 0.59667 0.37333 0.02472 0.99472 4.438 49.31
      40 CMAES 协方差矩阵自适应进化策略 0.76258 0.72089 0.00000 1.48347 0.82056 0.79616 0.00000 1.61672 0.75846 0.49077 0.00000 1.24923 4.349 48.33
      41 BFO-GA 细菌觅食优化 - ga 0.89150 0.55111 0.31529 1.75790 0.96982 0.39612 0.06305 1.42899 0.72667 0.27500 0.03525 1.03692 4.224 46.93
      42 SOA 简单优化算法 0.91520 0.46976 0.27089 1.65585 0.89675 0.37401 0.16984 1.44060 0.69538 0.28031 0.10852 1.08422 4.181 46.45
      43 ABHA 人工蜂巢算法 0.84131 0.54227 0.26304 1.64663 0.87858 0.47779 0.17181 1.52818 0.50923 0.33877 0.10397 0.95197 4.127 45.85
      44 ACMO 大气云模型优化 0.90321 0.48546 0.30403 1.69270 0.80268 0.37857 0.19178 1.37303 0.62308 0.24400 0.10795 0.97503 4.041 44.90
      45 ADAMm 群体自适应矩估计M 0.88635 0.44766 0.26613 1.60014 0.84497 0.38493 0.16889 1.39880 0.66154 0.27046 0.10594 1.03794 4.037 44.85
      RW 随机游走 0.48754 0.32159 0.25781 1.06694 0.37554 0.21944 0.15877 0.75375 0.27969 0.14917 0.09847 0.52734 2.348 26.09


      总结

      BSA在易于实现与搜索效率之间取得了很好的平衡，在基于种群的优化算法排行榜中处于相对稳定的中游位置。它的核心优势在于别具一格的历史记忆机制，既能避免算法过早收敛，又不会使计算结构变得复杂。与许多参数繁多、算子复杂的现代元启发式算法不同，BSA仅需极少的参数设置，对于不愿花费大量时间精调外部参数的工程实践者而言极具吸引力。

      唯一重要的参数（混合率mixrate）直观易懂，无需深入理解算法内部机理即可使用。同时，BSA在各类问题上均表现稳定—— 从简单的单峰函数，到存在多个局部最优的复杂多峰优化问题，都能稳定运行。该算法虽不追求收敛速度或求解精度上的极致领先，但其可靠性与稳定性使其成为实用而可靠的工作型算法。尤为可贵的是，随着种群规模增大，BSA不易陷入停滞 —— 历史种群的随机更新机制，即使在搜索后期也能持续保持种群多样性。

      它处于算法排行榜中的中游位置，并非平庸的体现，反而证明了其通用性与实用性。因为在解决实际问题时，并不总是需要最复杂、最前沿的算法。很多时候，一个逻辑清晰、运行稳健、无需专家调参就能取得良好效果的算法便已足够，而BSA恰好完美契合这一定位。

      tab

      图例2. 算法在相应测试中的颜色渐变表示

      图表

      图例3. 算法测试结果的直方图（评分范围为0到100，越高越好，其中100为理论上的最高可能得分，档案中附有计算排名表的脚本）

      BSA的优缺点：

      优点：

      1. 在所有测试函数上均表现出良好的收敛性。
      2. 除种群规模外，仅需设置一个附加的外部参数。

      缺点：

      1. 在低维问题且种群规模较小时，算法存在一定的过早收敛停滞倾向。

      文章附有一个包含当前版本算法代码的归档文件。本文作者不保证文中对经典算法规范形式的描述绝对准确。为提升搜索能力，已经对其中的许多算法进行了修改。文章中表述的结论和论断都是基于实验的结果。


      文中所用的程序

      # 名称 类型 描述
      1 #C_AO.mqh
      		 库
      		 种群优化算法的基类
      2 #C_AO_enum.mqh
      		 库
      		 种群优化算法的枚举说明
      3 TestFunctions.mqh
      		 库
      		 测试函数库
      4
      		 TestStandFunctions.mqh
      		 库
      		 测试台函数库
      5
      		 Utilities.mqh
      		 库
      		 辅助函数库
      6
      		 CalculationTestResults.mqh
      		 库
      		 用于计算比较表结果的脚本
      7
      		 Testing AOs.mq5
      		 脚本 面向所有种群优化算法的统一测试平台
      8
      		 Simple use of population optimization algorithms.mq5
      		 脚本
      		 种群优化算法非可视化简易使用案例
      9
      		 Test_AO_BSA.mq5
      		 脚本 BSA测试

      本文由MetaQuotes Ltd译自俄文
      原文地址： https://www.mql5.com/ru/articles/18568

      附加的文件 |
      下载ZIP
      BSA.zip (239.66 KB)

      注意: MetaQuotes Ltd.将保留所有关于这些材料的权利。全部或部分复制或者转载这些材料将被禁止。

      本文由网站的一位用户撰写，反映了他们的个人观点。MetaQuotes Ltd 不对所提供信息的准确性负责，也不对因使用所述解决方案、策略或建议而产生的任何后果负责。

      Andrey Dik
      Andrey Dik
      I WILL CONSIDER PROPOSALS FOR THE PUBLICATION OF A BOOK (TEXTBOOK) ON OPTIMIZATION ALGORITHMS.
      A group for communication on optimization and free product testing://t.me/+vazsAAcney4zYmZi
      Attention! My Telegram doppelgangers have appeared, my real nickname is @JQS_aka_Joo
      My github with optimization algorithms: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5
      All my publications: https://www.mql5.com/en/users/joo/publications
      I have been developing systems based on machine learning technologies since 2007 and in the field of artificial
      intelligence, optimization and forecasting.

      该作者的其他文章

      前往讨论
      交易策略 交易策略
      各种交易策略的分类都是任意的，下面这种分类强调从交易的基本概念上分类。
      市场模拟（第 20 部分）：SQL 入门（三） 市场模拟（第 20 部分）：SQL 入门（三）
      尽管我们可以在包含约 10 条记录的数据库上执行操作，但当我们处理包含超过 15000 条记录的文件时，这样学习效果会更好。也就是说，如果我们试图手动创建这样一个数据库，这项任务将十分艰巨。然而，即便出于教育目的，也很难找到这样一个可供下载的数据库。但实际上，我们无需采取这种手段 — 我们可以用 MetaTrader 5 为自己创建一个数据库。在今天的文章中，我们将探讨如何做到这一点。
      新手在交易中的10个基本错误 新手在交易中的10个基本错误
      新手在交易中会犯的10个基本错误: 在市场刚开始时交易, 获利时不适当地仓促, 在损失的时候追加投资, 从最好的仓位开始平仓, 翻本心理, 最优越的仓位, 用永远买进的规则进行交易, 在第一天就平掉获利的仓位,当发出建一个相反的仓位警示时平仓, 犹豫。
      MQL5中的时间缺口分析（第一部分）：构建基础指标 MQL5中的时间缺口分析（第一部分）：构建基础指标
      时间缺口分析可以帮助交易者识别潜在的市场反转点位。本文将阐述时间缺口的定义、解读方法，以及如何利用其探测市场中大资金的入场信号。