📘
回溯搜索算法（BSA）·进阶篇
BSA回溯搜索的类骨架与一次迭代内部机制
CAOBSABacktracking 是回溯搜索算法（BSA）在 MT5 优化框架里的具体实现，继承自通用优化接口 C_AO。它用种群并行搜索解空间，两个对外暴露的参数直接决定搜索形态：popSize 是同时跑的“智能体”数量，默认 10；mixrate 是交叉时的混合强度，默认 1.0，等于每个维度都允许从父代互换。 构造时把这两个参数写进 params 数组，SetParams 能从外部数组回写并做基础合法性校验。内部还维护了 oldP（历史种群）、M（变异种群）、T（试验种群）、F（变异幅值）以及 S_Map 这类二进制映射表——BSA 的“回溯记忆”就靠 oldP 和 prevFitness 实现，而不是像普通进化算法只盯当前代。 Init 先设变量上下界与步长，失败立即返回；随后给 oldP / M / T / map / prevFitness 分配内存，needSelection 置 false。历史种群用指定范围内的随机值按步长规整填充，全部顺利才返回成功，对象进入可迭代状态。 Moving 是主循环载体。首次调用且 revision 为 false 时，先在上下界内随机初始化活跃种群 a 并规整步长，然后把 revision 置 true、清 needSelection。若 needSelection 为 true，则做贪婪回滚：试验解 a[i].f 比 prevFitness[i] 差时，从 a[i].cP 恢复坐标与适应度，保证种群不退化。 每次生成新解前，当前适应度存入 prevFitness，坐标复制到 cP。之后走 SelectionI（50% 概率用 a 覆盖 oldP 再打乱）、Mutation（变异坐标 = 当前 + F×(历史−当前)）、Crossover（40% 用 mixrate 多维混合，其余单维替换），试验种群 T 抄回 a，needSelection 置 true 等下一轮评完适应度再选。 ShufflePopulation 用 Fisher–Yates 原地洗牌，从 popSize-1 倒序到 1，j 由 u.RNDminusOne(i+1) 取含 0 不含 i+1 的随机整数，交换时连坐标数组带适应度一起搬。Mutation 的 F 是随机幅值，BoundaryControl 越界时 50% 概率重随机、否则贴边界，再按步长离散化。Revision 只追踪最大适应度解。GaussDistribution 用 Box-Muller 生成以 In 为中心、受 [outMin,outMax] 约束的正态随机数，超 sigma 就递归重抽。 把这些机制拼起来，你能在 MT5 策略测试器的自定义优化里改 popSize 和 mixrate 做对照：popSize=10 与 30 在同品种外汇回测中，往往前者快但易陷局部、后者慢却更稳，贵金属点差放大时差异更明显，属典型高风险调参。
MQL5 / C++
<span class="comment">class=class="str">"cmt">//————————————————————————————————————————————————————————————————————</span> <span class="keyword">class</span> C_AO_BSA_Backtracking : <span class="keyword">class="kw">public</span> C_AO { <span class="keyword">class="kw">public</span>: <span class="comment">class=class="str">"cmt">//----------------------------------------------------------</span> ~C_AO_BSA_Backtracking() { } C_AO_BSA_Backtracking() { ao_name = <span class="class="type">class="kw">string">"BSA"</span>; ao_desc = <span class="class="type">class="kw">string">"Backtracking Search Algorithm"</span>; ao_link = <span class="class="type">class="kw">string">"[MQL5官方文档] popSize = <span class="number">class="num">10</span>; <span class="comment">class=class="str">"cmt">// population size</span> mixrate = <span class="number">class="num">1.0</span>; <span class="comment">class=class="str">"cmt">// crossover parameter</span> <span class="functions">ArrayResize</span> (params, <span class="number">class="num">2</span>); params [<span class="number">class="num">0</span>].name = <span class="class="type">class="kw">string">"popSize"</span>; params [<span class="number">class="num">0</span>].val = popSize; params [<span class="number">class="num">1</span>].name = <span class="class="type">class="kw">string">"mixrate"</span>; params [<span class="number">class="num">1</span>].val = mixrate; } <span class="keyword">class="type">void</span> SetParams() { popSize = (<span class="keyword">class="type">int</span>)params [<span class="number">class="num">0</span>].val;
「BSA 回跟踪算法的交叉率钳制与种群结构」
在 BSA 回跟踪（Backtracking Search Algorithm）的 EA 封装里，mixrate 作为交叉（crossover）概率参数，从外部传入的 params[1].val 读取，但必须先做边界钳制：小于 0.0 则置 0.0，大于 1.0 则置 1.0。这一行防御很关键，MT5 里若用户误填 1.5，算法不会崩，但交叉逻辑会失真，EURUSD 15M 回测里常表现为种群过早收敛。 类内部用 oldP、M、T 三套 S_AO_Agent 数组分别存历史种群、变异种群和试验种群；F 是变异振幅因子，needSelection 控制是否跑 Selection-II。私有结构 S_Map 用整型数组做二进制交叉掩码，Init 里 ArrayResize 到 size 然后 ArrayInitialize 清 0，这是每个 agent 独立交叉图的底层实现。 Init 函数体先调 StandardInit 做范围与步长校验，失败直接返回 false；epochsP 默认 0 表示由外层循环控制迭代次数。开 MT5 把这段类声明贴进自定义指标或 EA 的 include 头，改 params[1] 的默认输入值，能直接观察 mixrate 越界钳制是否生效。
MQL5 / C++
mixrate = params [class="num">1].val; class=class="str">"cmt">// Check the parameters validity class=class="str">"cmt">//if (popSize < class="num">2) popSize = class="num">2; if (mixrate < class="num">0.0) mixrate = class="num">0.0; if (mixrate > class="num">1.0) mixrate = class="num">1.0; } class="type">bool Init(const class="type">class="kw">double &rangeMinP [], class=class="str">"cmt">// minimum values const class="type">class="kw">double &rangeMaxP [], class=class="str">"cmt">// maximum values const class="type">class="kw">double &rangeStepP [], class=class="str">"cmt">// step change const class="type">int epochsP = class="num">0); class=class="str">"cmt">// number of epochs class="type">void Moving(); class="type">void Revision(); class=class="str">"cmt">//------------------------------------------------------------------ class="type">class="kw">double mixrate; class=class="str">"cmt">// crossover parameter class="kw">private: class=class="str">"cmt">//--------------------------------------------------------- S_AO_Agent oldP []; class=class="str">"cmt">// historical population S_AO_Agent M []; class=class="str">"cmt">// mutant population(Mutant) S_AO_Agent T []; class=class="str">"cmt">// trial population(Trial) class="type">class="kw">double F; class=class="str">"cmt">// amplitude factor for mutation class="type">bool needSelection; class=class="str">"cmt">// flag for the necessity of executing Selection-II class="type">class="kw">double prevFitness []; class=class="str">"cmt">// array for storing previous fitness class=class="str">"cmt">// Auxiliary structures for crossover class="kw">struct S_Map { class="type">int val []; class=class="str">"cmt">// binary map for crossover class="type">void Init(class="type">int size) { ArrayResize(val, size); ArrayInitialize(val, class="num">0); } }; S_Map map []; class=class="str">"cmt">// array of binary maps for each agent class=class="str">"cmt">// Algorithm methods class="type">void SelectionI(); class="type">void Mutation(); class="type">void Crossover(); class="type">void BoundaryControl(S_AO_Agent &agent); class="type">void ShufflePopulation(S_AO_Agent &pop []); }; class=class="str">"cmt">//--- Initialization class="type">bool C_AO_BSA_Backtracking::Init(const class="type">class="kw">double &rangeMinP [], const class="type">class="kw">double &rangeMaxP [], const class="type">class="kw">double &rangeStepP [], const class="type">int epochsP = class="num">0) { if (!StandardInit(rangeMinP, rangeMaxP, rangeStepP)) class="kw">return false; class=class="str">"cmt">//------------------------------------------------------------------
◍ BSA 回溯算法的初始化与主循环骨架
这段 MT5 代码展示了带回溯搜索的进化算法（BSA）在 EA 里的两个核心环节：结构体数组的初始化，以及每代迭代的主步 Moving()。初始化时先对 oldP、M、T、map、prevFitness 五个数组按 popSize 扩容，再把每个个体的坐标维度用随机值铺满，并约束到参数区间与步长内。 Moving() 第一次被调用时 revision 为 false，会直接生成初始种群 a[][] 并置 revision=true 后返回，相当于只做「冷启动」不进化。之后每次调用才进入真正的 BSA 四步：SelectionI → Mutation → Crossover，再把试验种群 T 拷回主种群 a 等适应度计算。 一个容易忽略的细节是 needSelection 标志：每代开始前先把当前适应度存进 prevFitness[] 并备份坐标到 cP[]；等适应度算完，下一轮 Moving() 开头若 needSelection 为真，就做贪婪回退——当新解 a[i].f 小于旧适应度时，用 ArrayCopy 把 cP 还原、f 写回旧值。外汇与贵金属参数优化高风险，回测过拟合概率不低，这套机制只是降低劣解覆盖优解的可能。 直接在 MT5 策略测试器里把 popSize 设成 30 跑一遍，观察老种群 oldP 与当前种群 a 的差异，能验证回溯是否按预期保留历史信息。
MQL5 / C++
class=class="str">"cmt">// Initialize additional BSA structures ArrayResize(oldP, popSize); ArrayResize(M, popSize); ArrayResize(T, popSize); ArrayResize(map, popSize); ArrayResize(prevFitness, popSize); needSelection = false; for (class="type">int i = class="num">0; i < popSize; i++) { oldP [i].Init(coords); M [i].Init(coords); T [i].Init(coords); map [i].Init(coords); } class=class="str">"cmt">// Initialize oldP historical population for (class="type">int p = class="num">0; p < popSize; p++) { for (class="type">int c = class="num">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]); } } class="kw">return true; } class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//--- The main step of the algorithm class="type">void C_AO_BSA_Backtracking::Moving() { class=class="str">"cmt">// Initial population setup if (!revision) { for (class="type">int p = class="num">0; p < popSize; p++) { for (class="type">int c = class="num">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; class="kw">return; } class=class="str">"cmt">// If you want to perform greedy selection after calculating fitness if (needSelection) { class=class="str">"cmt">// Selection-II: Greedy selection for (class="type">int i = class="num">0; i < popSize; i++) { class=class="str">"cmt">// If the current solution(from T) is worse than the previous one, class="kw">return the previous one if (a [i].f < prevFitness [i]) { ArrayCopy(a [i].c, a [i].cP, class="num">0, class="num">0, WHOLE_ARRAY); a [i].f = prevFitness [i]; } } needSelection = false; } class=class="str">"cmt">//--- BSA basic steps: class=class="str">"cmt">// Save current fitness before generating a new population for (class="type">int i = class="num">0; i < popSize; i++) { prevFitness [i] = a [i].f; ArrayCopy(a [i].cP, a [i].c, class="num">0, class="num">0, WHOLE_ARRAY); } class=class="str">"cmt">// class="num">1. Selection-I SelectionI(); class=class="str">"cmt">// class="num">2. Mutation Mutation(); class=class="str">"cmt">// class="num">3. Crossover Crossover(); class=class="str">"cmt">// class="num">4. Copy the trial population T into the &class="macro">#x27;a&class="macro">#x27; main population to calculate fitness for (class="type">int i = class="num">0; i < popSize; i++) { ArrayCopy(a [i].c, T [i].c, class="num">0, class="num">0, WHOLE_ARRAY); } class=class="str">"cmt">// Set the flag to execute Selection-II after calculating fitness needSelection = true; } class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//--- Selection-I: select a historical population
历史种群回写与变异交叉的实现细节
BSA 算法的回溯机制里，历史种群 oldP 不是每代都覆盖，而是以 50% 概率整体拷贝当前种群再打乱。代码里用 u.RNDprobab() < 0.5 做伯努利抽样，等价于两个均匀分布随机数比较大小，MT5 里可直接用 MathRand()/32767 复现。 打乱采用 Fisher–Yates 逆序交换，从 popSize-1 到 1 逐位与 [0,i] 区间随机位互换。注意 temp 代理每次都 Init(coords) 分配坐标内存，若 popSize 很大而 coords 较小，这步开销可忽略，但写成类内复用缓冲会更省。 变异步的振幅因子 F 取自高斯分布，均值为 0、截断区间 [-3.0, 3.0]、参数为 2，公式 M = P + F*(oldP - P) 让历史方向与当前位置耦合。外汇与贵金属参数优化中，F 截断上限若放到 5 以上，搜索可能发散，属高风险调参。 交叉按 40% 概率走 mixrate 策略：numElements = ceil(mixrate * rand * coords)，先对 Trial 种群浅拷贝变异体，再对随机若干维做标记位替换。把 mixrate 从默认 0.5 降到 0.2，EA 在 EURUSD 回测中过拟合概率倾向降低，但收敛代数可能变长。
MQL5 / C++
class="type">void C_AO_BSA_Backtracking::SelectionI() { class=class="str">"cmt">// Update the historical population with a class="num">50% probability if (u.RNDprobab() < class="num">0.5) class=class="str">"cmt">// equivalent to if (a < b) where a,b ~ U(class="num">0,class="num">1) { class=class="str">"cmt">// Copy the current population to the historical one for (class="type">int i = class="num">0; i < popSize; i++) { ArrayCopy(oldP [i].c, a [i].c, class="num">0, class="num">0, WHOLE_ARRAY); oldP [i].f = a [i].f; } } class=class="str">"cmt">// Shuffle the historical population ShufflePopulation(oldP); } class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//--- Shuffle population class="type">void C_AO_BSA_Backtracking::ShufflePopulation(S_AO_Agent &pop []) { for (class="type">int i = popSize - class="num">1; i > class="num">0; i--) { class="type">int j = u.RNDminusOne(i + class="num">1); class=class="str">"cmt">// Swap i and j elements S_AO_Agent temp; temp.Init(coords); ArrayCopy(temp.c, pop [i].c, class="num">0, class="num">0, WHOLE_ARRAY); temp.f = pop [i].f; ArrayCopy(pop [i].c, pop [j].c, class="num">0, class="num">0, WHOLE_ARRAY); pop [i].f = pop [j].f; ArrayCopy(pop [j].c, temp.c, class="num">0, class="num">0, WHOLE_ARRAY); pop [j].f = temp.f; } } class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//--- Mutation: generation of a mutant population class="type">void C_AO_BSA_Backtracking::Mutation() { class=class="str">"cmt">// Generate the amplitude factor F = u.GaussDistribution(class="num">0.0, -class="num">3.0, class="num">3.0, class="num">2); class=class="str">"cmt">// Apply mutation: M = P + F * (oldP - P) for (class="type">int i = class="num">0; i < popSize; i++) { for (class="type">int j = class="num">0; j < coords; j++) { M [i].c [j] = a [i].c [j] + F * (oldP [i].c [j] - a [i].c [j]); } } } class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//--- Crossover: trial population generation class="type">void C_AO_BSA_Backtracking::Crossover() { class=class="str">"cmt">// Initialize the trial population as a copy of the mutant one for (class="type">int i = class="num">0; i < popSize; i++) { ArrayCopy(T [i].c, M [i].c, class="num">0, class="num">0, WHOLE_ARRAY); } class=class="str">"cmt">// Select a crossover strategy if (u.RNDprobab() < class="num">0.4) { class=class="str">"cmt">//--- STRATEGY class="num">1: Using mixrate for (class="type">int i = class="num">0; i < popSize; i++) { class=class="str">"cmt">// Reset the map ArrayInitialize(map [i].val, class="num">0); class=class="str">"cmt">// Define the number of elements for the crossover class="type">int numElements = (class="type">int)MathCeil(mixrate * u.RNDprobab() * coords); class=class="str">"cmt">// Generate unique indices for the crossover for (class="type">int n = class="num">0; n < numElements; n++) { class="type">int idx; do {
「变异与边界处理的收尾实现」
当交叉开关未触发时，算法转入策略2：仅对每个个体的单个随机维度做变异。代码里 randomIndex = u.RNDminusOne(coords) 先抽一个坐标位，再把试验种群 T 中该位直接赋值为原种群 a 的对应值，这种单点变异在参数维度较高时计算开销明显低于全向量交叉。
边界控制放在所有试验个体生成之后统一执行。BoundaryControl 会逐维判断越界情况：以 0.5 的概率随机重生到 [rangeMin, rangeMax] 区间内，否则直接夹到最近边界。越界修复后还会调用 SeInDiSp 做离散化，保证参数落在预设步长网格上——外汇与贵金属参数优化属高风险实验，离散精度会直接影响 EA 在 MT5 实盘中的稳定性。
Revision 函数完成第二代选择：遍历种群找 f 最大者更新全局最优 fB 与 bestIND，命中后用 ArrayCopy 把最优坐标拷进 cB。注意这里比较符号是 >，说明该框架把适应度按越大越好来定义，接你自己的回测目标时要核对方向。
工具函数 GaussDistribution 刚开个头，用 logN 承接对数正态变换的中间量，具体映射公式需看后续实现，但入口参数已暴露了 sigma 控制离散程度的接口，调参时可从 0.3~1.0 区间试起。
MQL5 / C++
idx = u.RNDminusOne(coords); } while (map [i].val [idx] == class="num">1); class=class="str">"cmt">// until we find an unused index map [i].val [idx] = class="num">1; } class=class="str">"cmt">// Apply crossover for (class="type">int j = class="num">0; j < coords; j++) { if (map [i].val [j] == class="num">1) { T [i].c [j] = a [i].c [j]; } } } } else { class=class="str">"cmt">//--- STRATEGY class="num">2: Mutation of only one element for (class="type">int i = class="num">0; i < popSize; i++) { class=class="str">"cmt">// Select one random element class="type">int randomIndex = u.RNDminusOne(coords); T [i].c [randomIndex] = a [i].c [randomIndex]; } } class=class="str">"cmt">// Boundary control for all agents in the trial population for (class="type">int i = class="num">0; i < popSize; i++) { BoundaryControl(T [i]); } } class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//--- Boundary control class="type">void C_AO_BSA_Backtracking::BoundaryControl(S_AO_Agent &agent) { for (class="type">int j = class="num">0; j < coords; j++) { if (agent.c [j] < rangeMin [j] || agent.c [j] > rangeMax [j]) { class=class="str">"cmt">// Select a boundary handling strategy if (u.RNDprobab() < class="num">0.5) { class=class="str">"cmt">// Random regeneration agent.c [j] = u.RNDfromCI(rangeMin [j], rangeMax [j]); } else { class=class="str">"cmt">// Set to the boundary if (agent.c [j] < rangeMin [j]) agent.c [j] = rangeMin [j]; else agent.c [j] = rangeMax [j]; } } class=class="str">"cmt">// Discretization agent.c [j] = u.SeInDiSp(agent.c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//--- Selection-II and updating the best solution class="type">void C_AO_BSA_Backtracking::Revision() { class="type">int bestIND = -class="num">1; for (class="type">int i = class="num">0; i < popSize; i++) { class=class="str">"cmt">// Update the global best solution if (a [i].f > fB) { fB = a [i].f; bestIND = i; } } class=class="str">"cmt">// Copy the coordinates of the best solution if (bestIND != -class="num">1) { ArrayCopy(cB, a [bestIND].c, class="num">0, class="num">0, WHOLE_ARRAY); } } class=class="str">"cmt">//———————————————————————————————————————————————————————————————————— class=class="str">"cmt">//—————————————————————————————————————————————————————————————————————————————— class="type">class="kw">double C_AO_Utilities :: GaussDistribution(const class="type">class="kw">double In, const class="type">class="kw">double outMin, const class="type">class="kw">double outMax, const class="type">class="kw">double sigma) { class="type">class="kw">double logN = class="num">0.0;
常见问题
标准顺序是先按概率回写历史种群，再做导向变异与交叉；交叉率 cr 被钳制在 [0,1] 后再参与运算，避免越界。
要分开存。初始化时生成 oldPop 与 pop 两个矩阵，主循环每代只回写 oldPop 一次，pop 负责进化，结构清晰不易错。
可以。把代码贴给小布，它能对照类骨架指出 cr 钳制缺失、历史种群未回写或越界未映射等细节问题。
常见做法是将越界基因反射或随机重投到定义域；若直接截断可能损失多样性，建议写在变异收尾统一函数里。
可能。回写应按固定小概率而非每代都写；若老种群跟得太紧会削弱回溯效果，可调低回写概率再测几轮。