基于分形的算法(FBA)
引言
元启发式算法已被证实是求解复杂优化问题的有力工具,因其能够在合理时间内找到可行解。在过去几十年中,研究者受各类自然与社会过程启发,提出了众多元启发式方法:遗传算法、粒子群优化、差分进化、蚁群优化等,我们在先前的文章中已讨论过。
本文将介绍一种用于求解连续优化问题的新型元启发式算法 —— 由马尔詹・卡迪(Marjan Kaedi )于2017年提出的基于分形的算法(FBA)。该方法基于分形的几何特性,利用自相似性概念对搜索空间进行自适应勘探。算法核心为一种创新启发式规则,通过有前景解在各搜索区域内的分布密度评估区域前景。
该方法的关键在于,通过迭代将搜索空间划分为若干子空间,识别出最具前景的区域并进行更精细地搜索。算法运行过程中会形成朝向最优解的自相似分形结构,从而在全局勘探与对已发现解的局部精细化搜索之间实现平衡。本文将详细阐述该算法的理论基础、实现细节、关键参数设置,并在标准测试函数上与其他主流优化方法进行对比分析,呈现实验结果。
算法实现
想象一下,您要在一片广阔的田野里寻找宝藏。您会怎么做?您大概不会把每一寸土地都挖一遍,因为那样太耗时了。而这正是分形算法(FBA)所要解决的问题 —— 它能在巨大的解空间中找到 “宝藏”(最优解),而无需逐一检查每一个点。
首先,我们把整个搜索区域划分成大小相等的方格,就像棋盘一样。然后在整片区域内撒下 “探索者”(随机点),初步了解这片区域。每个探索者会反馈其所在位置的优劣。算法筛选出表现最好的探索者(即最优的60%点位),并观察它们集中在哪些方格中。这些方格会被标记为 “有前景区域”(排名前30%的方格)。
现在我们将注意力集中在这些有前景区域。每个区域会被继续细分为更小的方格,形成分形结构。大部分新的探索者会被派往这些有前景区域;而为了避免遗漏已探索区域之外的宝藏,算法还会让一小部分探索者进行随机游走 —— 它们从当前位置向任意方向漫游,探索未知区域。
这一过程不断重复。每一步,算法都会更精准地定位宝藏可能存在的位置,并向那里派遣更多探索者。最终会形成一个由不同大小方格构成的层级结构,形态类似分形 —— 该算法也因此得名。

图例1. FBA算法运行过程可视化
FBA算法的核心理念如上图所示,以分形方式将搜索空间逐步划分为越来越小的子区域,将计算资源集中在最具前景的区域上。由此形成一种自相似结构,实现对解空间的有效搜索。下面我们开始编写FBA算法的伪代码。
- 将整个搜索空间划分为大小相等的子空间
- 在整个空间内均匀生成初始种群
- 评估每个点的适应度值
- 筛选有前景点:选取适应度最优的P1%个体作为有前景点
- 计算子空间排名:统计每个子空间内落入的有前景点的数量
- 选取有前景子空间:选取排名最高的P2%子空间作为有前景子空间
- 细分有前景子空间:将选中的有前景区域进一步划分为更小的子空间
- 生成新种群:在有前景区域以更高密度生成新的搜索点
- 执行变异操作:对P3%的个体添加高斯噪声(全局探索机制)
- 种群融合:合并当前种群与新种群,并保留最优个体
- 重复迭代直至满足停止条件(达到最大迭代次数、适应度阈值等)
- 返回找到的最优解
现在我们已经理解了算法的核心理念,可以开始编写代码。C_AO_FBA类是基于分形原理的优化算法的专用实现,继承自通用基类C_AO。
该类包含用于算法配置与核心执行的公有方法与参数。构造函数用于初始化参数,包括:种群规模、有前景点与有前景子空间的占比、随机变异点比例,以及将各维度划分为区间的分段数量。SetParams方法支持根据外部动态更新参数。Init方法以及后续的Moving和Revision函数控制算法的执行阶段与迭代过程。
该类还声明了内部结构体S_Subspace,用于描述搜索子空间。每个子空间的属性包括:各维度的上下边界、子空间前景值、层级结构中的层级,以及与父空间的关联关系。
类中的核心方法实现以下功能:
- 检查一个点是否位于指定子空间内。
- 构建空间的初始划分结构,并执行后续细分操作。
- 识别有前景点、计算子空间排名,并筛选最优子空间用于进一步细分。
- 通过融合、变异、按效率或适应度排序生成新种群。
因此,C_AO_FBA类实现了一种自适应、层次化、基于分形的优化算法,用于求解复杂高维问题的最优解。该算法通过动态空间划分、前景区域评估以及启发式算子,显著提升搜索效率。
//—————————————————————————————————————————————————————————————————————————————— class C_AO_FBA : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_FBA () { } C_AO_FBA () { ao_name = "FBA"; ao_desc = "Fractal-Based Algorithm"; ao_link = "https://www.mql5.com/en/articles/17458"; popSize = 50; // population size P1 = 60; // percentage of promising points P2 = 30; // percentage of promising subspaces P3 = 0.8; // percentage of points for random modification m_value = 10; // number of intervals to split each dimension into ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "P1"; params [1].val = P1; params [2].name = "P2"; params [2].val = P2; params [3].name = "P3"; params [3].val = P3; params [4].name = "m_value"; params [4].val = m_value; } void SetParams () { popSize = (int)params [0].val; P1 = (int)params [1].val; P2 = (int)params [2].val; P3 = params [3].val; m_value = (int)params [4].val; } 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 (); //---------------------------------------------------------------------------- int P1; // percentage of promising points int P2; // percentage of promising subspaces double P3; // share of points for random modification int m_value; // number of intervals to split each dimension into private: //------------------------------------------------------------------- // Structure for representing a subspace struct S_Subspace { double min []; // minimal boundaries of the subspace double max []; // maximum boundaries of the subspace double promisingRank; // potential rank (normalized value) bool isPromising; // flag of potential int parentIndex; // index of the parent subspace (-1 for root ones) int level; // level in hierarchy (0 for original space) void Init (int coords) { ArrayResize (min, coords); ArrayResize (max, coords); promisingRank = 0.0; isPromising = false; parentIndex = -1; level = 0; } }; S_Subspace subspaces []; // array of subspaces // Auxiliary methods bool IsPointInSubspace (const double &point [], const S_Subspace &subspace); void CreateInitialSpacePartitioning (); void DivideSubspace (int subspaceIndex); void IdentifyPromisingPoints (int &promisingIndices []); void CalculateSubspaceRanks (const int &promisingIndices []); void SelectPromisingSubspaces (); void DividePromisingSubspaces (); void GenerateNewPopulation (); void MutatePoints (); void SortByFitness (double &values [], int &indices [], int size, bool ascending = false); void QuickSort (double &values [], int &indices [], int low, int high, bool ascending); int Partition (double &values [], int &indices [], int low, int high, bool ascending); }; //——————————————————————————————————————————————————————————————————————————————
Init初始化方法用于配置算法运行的初始条件。该方法接收包含各参数最小值、最大值边界、步长的数组,以及迭代总次数。在方法内部,首先执行基础初始化,随后对搜索空间进行初始划分 —— 即根据指定的范围和步长,构建初始的子空间结构。如果成功执行所有操作,该方法返回"true";否则返回"false"。
基础的Moving方法通过连续迭代执行解搜索循环。首次迭代是在整个搜索空间内均匀初始化点集,每个变量值在边界范围内随机选取,并且按照给定的步长进行调整。
接下来,进入算法的主流程,依次执行以下步骤:筛选有前景点:根据适应度函数值,选取表现最优的一小部分点。计算有前景子空间的排名:基于有前景点的分布,统计并计算各子空间的前景排名。选取有前景的子空间:根据排名筛选出最具前景的子空间,用于进一步细分。细分有前景的区域:将选中的有前景的区域分割为更小、更精细的搜索区域。生成新种群:结合子空间的前景排名生成新的点集,使搜索资源集中在最有前景的区域。执行变异操作:对部分点进行随机修改,以提升种群多样性,避免算法早熟收敛。
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_FBA::Init (const double &rangeMinP [], // minimum values const double &rangeMaxP [], // maximum values const double &rangeStepP [], // step change const int epochsP = 0) // number of epochs { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- // Create an initial partition of the search space CreateInitialSpacePartitioning (); return true; } //—————————————————————————————————————————————————————————————————————————————— //+----------------------------------------------------------------------------+ //| Basic optimization method | //+----------------------------------------------------------------------------+ void C_AO_FBA::Moving () { // First iteration - initialization of the initial population if (!revision) { // Initialize the initial population uniformly throughout the space for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } // Main optimization // 1. Identifying promising points (P1% of points with the best function values) int promisingIndices []; IdentifyPromisingPoints (promisingIndices); // 2. Calculation of potential ranks for each subspace CalculateSubspaceRanks (promisingIndices); // 3. Selecting the P2% most promising subspaces SelectPromisingSubspaces (); // 4. Dividing promising subspaces into smaller ones DividePromisingSubspaces (); // 5. Generating new points taking into account potential ranks GenerateNewPopulation (); // 6. Random modification (mutation) MutatePoints (); } //——————————————————————————————————————————————————————————————————————————————
Revision方法负责在算法运行过程中更新当前找到的最优解。该方法遍历当前种群中的所有个体,将每个个体的目标函数值与当前最优值进行比较。如果某个个体的表现更优,则更新存储最优结果的变量,并将其对应的变量(坐标)数组复制保存,以记录该最优解。因此,该方法确保对于给定时刻找到的最优解进行持续跟踪和存储。
//+----------------------------------------------------------------------------+ //| Update the best solution | //+----------------------------------------------------------------------------+ void C_AO_FBA::Revision () { // Search for the best solution for (int i = 0; i < popSize; i++) { // Update the best solution if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY); } } } //——————————————————————————————————————————————————————————————————————————————
该方法用于创建初始子空间结构,实现对最优解搜索的区域定位。它会根据指定的分割粒度与空间维度,计算子空间的总数量。如果空间维度极高,则会按照预设的最大值进行限制,避免资源过度消耗。
接下来,初始化子空间数组,为每个子空间分配初始层级与各维度坐标边界参数。根据空间维度自动选择适配的划分方式:
- 对于一维空间,将其划分为均匀区间,每个子空间占据范围的一段区域。
- 对于二维空间,沿两个坐标轴进行分割,形成矩形网格区域。
- 对于高维空间,采用迭代方式生成各维度的索引组合(其原理类似计数器),并根据对应区间为每个子空间设置边界。
将每个维度的取值范围等比例分割,并根据当前索引为每个子空间设置最小值与最大值边界,以此计算边界。迭代持续执行,直至所有子空间创建完成,或达到数量上限。最终生成搜索空间初始划分结构,为后续的精细化搜索与求解做好准备。
//+----------------------------------------------------------------------------+ //| Create the initial partition of the search space | //+----------------------------------------------------------------------------+ void C_AO_FBA::CreateInitialSpacePartitioning () { // Create an initial partition of space int totalSubspaces = (int)MathPow (m_value, coords); // For very large dimensions, limit the number of subspaces if (totalSubspaces > 10000) totalSubspaces = 10000; ArrayResize (subspaces, totalSubspaces); // Initialize all subspaces for (int i = 0; i < totalSubspaces; i++) { subspaces [i].Init (coords); subspaces [i].level = 0; // Initial level } // Divide the initial space into equal subspaces int index = 0; // Select the division method depending on the dimensionality of the space if (coords == 1) { // One-dimensional case double intervalSize = (rangeMax [0] - rangeMin [0]) / m_value; for (int i = 0; i < m_value && index < totalSubspaces; i++) { subspaces [index].min [0] = rangeMin [0] + i * intervalSize; subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize; index++; } } else if (coords == 2) { // Two-dimensional case double intervalSize0 = (rangeMax [0] - rangeMin [0]) / m_value; double intervalSize1 = (rangeMax [1] - rangeMin [1]) / m_value; for (int i = 0; i < m_value && index < totalSubspaces; i++) { for (int j = 0; j < m_value && index < totalSubspaces; j++) { subspaces [index].min [0] = rangeMin [0] + i * intervalSize0; subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize0; subspaces [index].min [1] = rangeMin [1] + j * intervalSize1; subspaces [index].max [1] = rangeMin [1] + (j + 1) * intervalSize1; index++; } } } else { // Multidimensional case - use an iterative approach int indices []; ArrayResize (indices, coords); for (int i = 0; i < coords; i++) indices [i] = 0; while (index < totalSubspaces) { // Calculate the boundaries of the current subspace for (int c = 0; c < coords; c++) { double intervalSize = (rangeMax [c] - rangeMin [c]) / m_value; subspaces [index].min [c] = rangeMin [c] + indices [c] * intervalSize; subspaces [index].max [c] = rangeMin [c] + (indices [c] + 1) * intervalSize; } // Move on to the next subspace int c = coords - 1; while (c >= 0) { indices [c]++; if (indices [c] < m_value) break; indices [c] = 0; c--; } // If the full loop completed, exit if (c < 0) break; index++; } } } //——————————————————————————————————————————————————————————————————————————————
以下方法用于判断一个给定点是否位于指定的子空间内。它会逐一遍历检查点的每一个坐标,并将其值与对应子空间的边界进行比较。如果任意一个坐标超出了允许范围(小于最小值,或大于等于最大值),该方法将返回"false",表示该点不位于当前子空间内。如果所有坐标均满足边界条件,方法则确认该点属于当前子空间,并返回"true"。
//+----------------------------------------------------------------------------+ //| Determine whether a point belongs to a subspace | //+----------------------------------------------------------------------------+ bool C_AO_FBA::IsPointInSubspace (const double &point [], const S_Subspace &subspace) { // Check if the point is in the specified subspace for (int c = 0; c < coords; c++) { if (point [c] < subspace.min [c] || point [c] >= subspace.max [c]) { return false; } } return true; } //——————————————————————————————————————————————————————————————————————————————
有前景点筛选方法用于从当前种群中选取最具前景的解。该方法首先创建临时数组,用于存储每个个体的适应度函数值及其索引。接下来,将种群中对应个体的函数值与索引填入这些数组。
再将所有个体按适应度函数值降序排列。排序完成后,选取指定比例(P1%)的最优解,并基于这些解构建有前景点索引列表。筛选出的点数量至少为1个,且不超过种群总规模。最终,函数返回有前景解的索引数组。
//+----------------------------------------------------------------------------+ //| Identify promising points | //+----------------------------------------------------------------------------+ void C_AO_FBA::IdentifyPromisingPoints (int &promisingIndices []) { // Select P1% points with the best function values // Create arrays for sorting double values []; int indices []; ArrayResize (values, popSize); ArrayResize (indices, popSize); // Fill in the arrays for (int i = 0; i < popSize; i++) { values [i] = a [i].f; indices [i] = i; } // Sort in descending order (for the maximization problem) SortByFitness (values, indices, popSize); // Select P1% best points int numPromisingPoints = (int)MathRound (popSize * P1 / 100.0); numPromisingPoints = MathMax (1, MathMin (numPromisingPoints, popSize)); ArrayResize (promisingIndices, numPromisingPoints); for (int i = 0; i < numPromisingPoints; i++) { promisingIndices [i] = indices [i]; } } //——————————————————————————————————————————————————————————————————————————————
此外,该方法还用于对子空间进行前景评估与排序。首先重置所有子空间当前的评分值。接下来,通过对比每个有前景点的坐标与各子空间的边界,统计落入每个子空间内的有前景点的数量,匹配时对应计数器加1。
需要注意的是,一个点仅归属唯一的一个子空间。在统计出数量指标后,将各子空间的评分数值标准化:用子空间内有前景点的数量除以全部有前景点的总数,得到各子空间的相对前景得分。此分值在0到1之间,表示该子空间内的有前景点占全部有前景点的比例。由此得到子空间的前景排名。
//+----------------------------------------------------------------------------+ //| Calculate potential ranks of subspaces | //+----------------------------------------------------------------------------+ void C_AO_FBA::CalculateSubspaceRanks (const int &promisingIndices []) { // Reset the ranks of subspaces for (int i = 0; i < ArraySize (subspaces); i++) { subspaces [i].promisingRank = 0.0; } // Calculate promising points in each subspace for (int i = 0; i < ArraySize (promisingIndices); i++) { int pointIndex = promisingIndices [i]; for (int j = 0; j < ArraySize (subspaces); j++) { if (IsPointInSubspace (a [pointIndex].c, subspaces [j])) { subspaces [j].promisingRank++; break; // A point can only be in one subspace } } } // Normalize the potential ranks according to the article // PromisingRank = Number of promising points in s / Total promising points int totalPromisingPoints = ArraySize (promisingIndices); if (totalPromisingPoints > 0) { for (int i = 0; i < ArraySize (subspaces); i++) { subspaces [i].promisingRank = subspaces [i].promisingRank / totalPromisingPoints; } } } //——————————————————————————————————————————————————————————————————————————————
SelectPromisingSubspaces方法根据子空间的评分,判定哪些子空间可被视为有前景区域。首先创建临时的“ranks”(评分值)与“indices”(索引)数组,用于存储各子空间的评分及其对应索引。随后将所有子空间的评分与索引复制到临时数组中。对于每个子空间,将"isPromising"标识初始化为"false"。这一步用于清空历史迭代结果,保证从头开始计算。再对"ranks"数组按评分降序排序,同时同步调整"indices"数组的顺序,确保索引与评分始终一一对应。
排序完成后,"indices"数组中存储的即为按评分从高到低排列的子空间索引。有前景子空间的数量由参数P2(最优子空间占比)计算得出。最终数量会被限制在1至子空间总数的有效范围内。遍历"indices"数组的前numPromisingSubspaces个元素。将每个索引对应子空间的isPromising标识设置为"true",表示该子空间被判定为有前景区域。
该方法中同时包含索引越界检查,以避免访问子空间数组时出现错误。执行该方法后,排名最高的P2%子空间的isPromising标识被设置为“true”。
//+----------------------------------------------------------------------------+ //| Select promising subspaces | //+----------------------------------------------------------------------------+ void C_AO_FBA::SelectPromisingSubspaces () { // Select P2% subspaces with the highest ranks as promising ones // Create arrays for sorting double ranks []; int indices []; int numSubspaces = ArraySize (subspaces); ArrayResize (ranks, numSubspaces); ArrayResize (indices, numSubspaces); // Fill in the arrays for (int i = 0; i < numSubspaces; i++) { ranks [i] = subspaces [i].promisingRank; indices [i] = i; // Reset the potential flag subspaces [i].isPromising = false; } // Sort by descending ranks SortByFitness (ranks, indices, numSubspaces); // Select P2% most promising subspaces int numPromisingSubspaces = (int)MathRound (numSubspaces * P2 / 100.0); numPromisingSubspaces = MathMax (1, MathMin (numPromisingSubspaces, numSubspaces)); // Mark promising subspaces for (int i = 0; i < numPromisingSubspaces && i < ArraySize (indices); i++) { // Protection against exceeding the array size if (indices [i] >= 0 && indices [i] < ArraySize (subspaces)) { subspaces [indices [i]].isPromising = true; } } } //——————————————————————————————————————————————————————————————————————————————
DividePromisingSubspaces方法用于将已标记的有前景子空间进一步分割为更小的区域。该方法首先通过检查isPromising标识,识别出所有被判定为有前景区域的子空间。将这些子空间的索引收集到临时数组promisingIndices中。接下来,对于promisingIndices数组中的每一个子空间索引,调用DivideSubspace函数并传入该子空间索引。
因此,该方法可遍历所有识别出的有前景子空间,并通过DivideSubspace函数依次对每个有前景子空间执行分割操作。
//+----------------------------------------------------------------------------+ //| Separate promising subspaces | //+----------------------------------------------------------------------------+ void C_AO_FBA::DividePromisingSubspaces () { // Collect indices of promising subspaces int promisingIndices []; int numPromising = 0; for (int i = 0; i < ArraySize (subspaces); i++) { if (subspaces [i].isPromising) { numPromising++; ArrayResize (promisingIndices, numPromising); promisingIndices [numPromising - 1] = i; } } // Divide each promising subspace for (int i = 0; i < numPromising; i++) { DivideSubspace (promisingIndices [i]); } } //——————————————————————————————————————————————————————————————————————————————
DivideSubspace方法用于将指定的子空间分割为更小的区域。首先,根据传入的索引定位父子空间。为确保子空间总数不超过预设上限(10,000),在将每个维度划分为"m_value"等份后,新子空间的总数量为m_value的维度数次方。
存储所有子空间的数组会扩容,扩容大小为新增子空间的数量。对于每个新的子空间,初始化给定的参数,如层级、父子空间索引,以及各维度坐标边界,边界由父子空间范围等比例分割计算得到。
针对每个维度,计算区间大小,并根据当前索引设置子空间的边界。每创建一个新子空间,按照多索引计数规则递增维度索引,以切换到下一个分区。当某一维的索引达到m_value时,该索引归零,并对下一维索引执行递增,遍历所有组合。
持续执行此流程,直至所有新子空间创建完成,或达到数量上限。通过计数器遍历完所有组合后,流程自动终止。执行该方法后,父子空间被分割为多个更小的子空间,每个子空间均覆盖原范围在各维度上的对应分区。
//+----------------------------------------------------------------------------+ //| Partition a specific subspace | //+----------------------------------------------------------------------------+ void C_AO_FBA::DivideSubspace (int subspaceIndex) { // Divide the specified subspace into m_value^coords subspaces S_Subspace parent = subspaces [subspaceIndex]; // Limit the maximum number of subspaces if (ArraySize (subspaces) > 10000) return; // For each dimension, divide by m_value parts int totalNewSubspaces = (int)MathPow (m_value, coords); int currentSize = ArraySize (subspaces); ArrayResize (subspaces, currentSize + totalNewSubspaces); // Create new subspaces int newIndex = currentSize; int indices []; ArrayResize (indices, coords); for (int i = 0; i < coords; i++) indices [i] = 0; for (int idx = 0; idx < totalNewSubspaces && newIndex < ArraySize (subspaces); idx++) { subspaces [newIndex].Init (coords); subspaces [newIndex].level = parent.level + 1; subspaces [newIndex].parentIndex = subspaceIndex; // Calculate the boundaries of the current subspace for (int c = 0; c < coords; c++) { double intervalSize = (parent.max [c] - parent.min [c]) / m_value; subspaces [newIndex].min [c] = parent.min [c] + indices [c] * intervalSize; subspaces [newIndex].max [c] = parent.min [c] + (indices [c] + 1) * intervalSize; } // Move on to the next subspace int c = coords - 1; while (c >= 0) { indices [c]++; if (indices [c] < m_value) break; indices [c] = 0; c--; } // If the full loop completed, exit if (c < 0) break; newIndex++; } } //——————————————————————————————————————————————————————————————————————————————
GenerateNewPopulation方法用于生成新的点集,并按照各子空间的前景评分(promisingRank)值进行分布。
首先,计算所有子空间的前景评分总和。该值用于确定每个子空间中应生成的点的比例数量。如果评分总和接近0(小于0.0001,即所有子空间评分均为0),则为所有子空间分配最小正评分(1.0),以确保点的均匀分布。接下来,根据每个子空间的前景评分占总评分的比例,计算该子空间内应生成的点数量。
我们使用计算公式:(subspaces[i].promisingRank / totalRank) * popSize,其中popSize为目标种群规模。对计算结果四舍五入取整,且点数量上限不超过popSize。在每个子空间内部,按计算出的数量生成点;每个点的"coords"(坐标)在子空间边界内均匀随机生成。对于每个维度,坐标值受预设最小值、最大值约束,并且根据rangeStep[c]步长形成网格。
如果按子空间分配后,总生成点数小于popSize,则在整个搜索空间内均匀生成剩余点(使用全局上下界rangeMin [c]和rangeMax [c]),同样按rangeStep [c]步长生成网格。这样确保最终种群规模始终严格等于popSize。
//+----------------------------------------------------------------------------+ //| Generate a new population | //+----------------------------------------------------------------------------+ void C_AO_FBA::GenerateNewPopulation () { // Calculate the sum of the ranks of all subspaces double totalRank = 0.0; for (int i = 0; i < ArraySize (subspaces); i++) { totalRank += subspaces [i].promisingRank; } // If all ranks are 0, set the uniform distribution if (totalRank <= 0.0001) // Check for approximate equality to zero { for (int i = 0; i < ArraySize (subspaces); i++) { subspaces [i].promisingRank = 1.0; } totalRank = ArraySize (subspaces); } int points = 0; for (int i = 0; i < ArraySize (subspaces) && points < popSize; i++) { // Calculate the number of points for this subspace according to the equation int pointsToGenerate = (int)MathRound ((subspaces [i].promisingRank / totalRank) * popSize); // Limitation against exceeding the limits pointsToGenerate = MathMin (pointsToGenerate, popSize - points); // Generate points in this subspace for (int j = 0; j < pointsToGenerate; j++) { // Create a new point uniformly within the subspace for (int c = 0; c < coords; c++) { a [points].c [c] = u.RNDfromCI (subspaces [i].min [c], subspaces [i].max [c]); a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } points++; if (points >= popSize) break; } } // If not all points were generated, fill the remaining ones uniformly throughout the space while (points < popSize) { for (int c = 0; c < coords; c++) { a [points].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } points++; } } //——————————————————————————————————————————————————————————————————————————————
C_AO_FBA类的MutatePoints方法用于对种群中的点执行变异操作,是算法提升解的多样性、避免陷入局部最优陷阱的核心步骤。
该方法的原始版本沿用了标准FBA算法的理念,对随机选取的点坐标添加高斯噪声。然而,这种变异策略效果极差,算法表现与随机搜索算法几乎无差异,因此该部分代码已被注释,替换为更优的实现方案。
方法的核心实现逻辑:遍历整个种群,对于每个个体(搜索点)的每一维坐标,进行变异概率判断。如果满足预设的变异概率条件,则通过幂律分布函数修改该坐标值,幂次参数可灵活控制变异幅度。变异完成后,对数值进行规整与边界约束,确保其落在合法取值范围内,并符合预设的采样步长。
最终,该方法实现了种群个体的随机变异,有效地提升解的多样性,增强算法全局最优搜索能力。
//+----------------------------------------------------------------------------+ //| Mutation of points in the population | //+----------------------------------------------------------------------------+ void C_AO_FBA::MutatePoints () { // Add Gaussian noise to P3% of randomly selected points from the new population /* int numToMutate = (int)MathRound (popSize * P3 / 100.0); numToMutate = MathMax (1, MathMin (numToMutate, popSize)); for (int i = 0; i < numToMutate; i++) { int index = u.RNDminusOne (popSize); // Add noise to each coordinate for (int c = 0; c < coords; c++) { // Standard deviation of 10% of the range //double stdDev = (rangeMax [c] - rangeMin [c]) * 0.1; // Gaussian noise using the Box-Muller method //double noise = NormalRandom (0.0, stdDev); // Add noise and limit the value a [index].c [c] += noise; a [index].c [c] = u.SeInDiSp (a [index].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } */ for (int p = 0; p < popSize; p++) { for (int c = 0; c < coords; c++) { if (u.RNDprobab () < P3) { a [p].c [c] = u.PowerDistribution (cB [c], rangeMin [c], rangeMax [c], 20); a [p].c [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } } //——————————————————————————————————————————————————————————————————————————————
SortByFitness方法用于对两个数组进行同步排序,一个存储适应度函数值,另一个存储对应元素的索引。该方法接收以下参数:适应度值数组、索引数组、数组长度,以及一个用于指定排序顺序的可选标识。
如果数组长度大于1,该方法将调用内部QuickSort函数执行快速排序。排序过程中,两个数组保持同步更新,确保适应度值与索引的对应关系不被破坏。执行该方法后,所有元素将按照指定的排序方式,依据适应度函数值完成有序排列。
//+----------------------------------------------------------------------------+ //| Sort by fitness function value | //+----------------------------------------------------------------------------+ void C_AO_FBA::SortByFitness (double &values [], int &indices [], int size, bool ascending = false) { if (size > 1) QuickSort (values, indices, 0, size - 1, ascending); } //——————————————————————————————————————————————————————————————————————————————
QuickSort方法为关联数组("values"数组与"indices"数组)实现快速排序算法。它采用递归方式对数组进行分割与排序,并严格保持数值与其原始索引的对应关系不变。参数包括:待排序的数组、排序区间的边界(起始位置low 和结束位置high)和用于指定排序方向的"ascending"标识。
//+----------------------------------------------------------------------------+ //| Quick sort algorithm | //+----------------------------------------------------------------------------+ void C_AO_FBA::QuickSort (double &values [], int &indices [], int low, int high, bool ascending) { if (low < high) { int pi = Partition (values, indices, low, high, ascending); QuickSort (values, indices, low, pi - 1, ascending); QuickSort (values, indices, pi + 1, high, ascending); } } //——————————————————————————————————————————————————————————————————————————————
Partition方法是快速排序算法的核心部分。它的作用是选取一个基准元素,并对"indices"数组中的元素进行重新排列:使得所有“小于”基准值(或“大于”,取决于排序顺序)的元素位于基准左侧,而“大于”(或“小于”)基准值的元素位于基准右侧。这里的“小于”和“大于”,是根据"indices"数组中索引所指向的"values"数组中的数值来判定的。
//+----------------------------------------------------------------------------+ //| Partition function for QuickSort | //+----------------------------------------------------------------------------+ int C_AO_FBA::Partition (double &values [], int &indices [], int low, int high, bool ascending) { double pivot = values [indices [high]]; int i = low - 1; for (int j = low; j < high; j++) { bool condition = ascending ? (values [indices [j]] < pivot) : (values [indices [j]] > pivot); if (condition) { i++; // Exchange values int temp = indices [i]; indices [i] = indices [j]; indices [j] = temp; } } // Exchange values int temp = indices [i + 1]; indices [i + 1] = indices [high]; indices [high] = temp; return i + 1; } //——————————————————————————————————————————————————————————————————————————————
测试结果
该算法整体表现良好。FBA|Fractal-Based Algorithm|50.0|60.0|30.0|0.8|10.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7900044352090774
25 Hilly's; Func runs: 10000; result: 0.6513385092404853
500 Hilly's; Func runs: 10000; result: 0.2896548031738138
=============================
5 Forest's; Func runs: 10000; result: 0.8715768614282637
25 Forest's; Func runs: 10000; result: 0.5682316842631675
500 Forest's; Func runs: 10000; result: 0.18876552479611478
=============================
5 Megacity's; Func runs: 10000; result: 0.6107692307692306
25 Megacity's; Func runs: 10000; result: 0.46061538461538465
500 Megacity's; Func runs: 10000; result: 0.12398461538461655
=============================
总分:4.55494 (50.61%)
可视化结果展示了该算法如何将搜索空间逐步细分为更小的子空间。结果也表明,该算法在低维函数上具有很强的寻优多样性。

FBA在Hilly测试函数上

FBA在Forest测试函数上

FBA在Megacity测试函数上
根据测试结果,FBA算法在我们的排行榜中位列第29位。
| # | 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 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | (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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | CGO | 混沌博弈优化 | 0.57256 | 0.37158 | 0.32018 | 1.26432 | 0.61176 | 0.61931 | 0.62161 | 1.85267 | 0.37538 | 0.21923 | 0.19028 | 0.78490 | 3.902 | 43.35 |
| 42 | ATAm | 人工部落算法M | 0.71771 | 0.55304 | 0.25235 | 1.52310 | 0.82491 | 0.55904 | 0.20473 | 1.58867 | 0.44000 | 0.18615 | 0.09411 | 0.72026 | 3.832 | 42.58 |
| 43 | CROm | 珊瑚礁优化算法M | 0.78512 | 0.46032 | 0.25958 | 1.50502 | 0.86688 | 0.35297 | 0.16267 | 1.38252 | 0.63231 | 0.26738 | 0.10734 | 1.00703 | 3.895 | 43.27 |
| 44 | CFO | 中央力优化 | 0.60961 | 0.54958 | 0.27831 | 1.43750 | 0.63418 | 0.46833 | 0.22541 | 1.32792 | 0.57231 | 0.23477 | 0.09586 | 0.90294 | 3.668 | 40.76 |
| 45 | ASHA | 人工淋浴算法 | 0.89686 | 0.40433 | 0.25617 | 1.55737 | 0.80360 | 0.35526 | 0.19160 | 1.35046 | 0.47692 | 0.18123 | 0.09774 | 0.75589 | 3.664 | 40.71 |
| RW | 神经Boid优化算法2(joo) | 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 | |
总结
FBA算法的变异改进版本,其效率相比原始版本提升了一倍,结果达到50.61%,
FBA|Fractal-Based Algorithm|50.0|60.0|30.0|5.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.4780639253626462
25 Hilly's; Func runs: 10000; result: 0.3222029113692554
500 Hilly's; Func runs: 10000; result: 0.25720991988937014
=============================
5 Forest's; Func runs: 10000; result: 0.36567166223346415
25 Forest's; Func runs: 10000; result: 0.22043205527307377
500 Forest's; Func runs: 10000; result: 0.15869146061036057
=============================
5 Megacity's; Func runs: 10000; result: 0.2861538461538461
25 Megacity's; Func runs: 10000; result: 0.15015384615384622
500 Megacity's; Func runs: 10000; result: 0.09838461538461622
=============================
总分: 2.33696 (25.97%)
由于变异机制的根本性改进,新方案在搜索空间全局探索与对已发现有前景解的局部开发之间,实现了更为合理的平衡。
其核心突破在于,算法不再采用完全随机的变异方式,而是利用搜索过程中积累的空间分布信息来引导变异。这样更加符合自然优化过程 —— 随机性与确定性以平衡的方式共存。该方法使得算法能更快收敛到全局最优解,尤其在存在大量局部极值的复杂高维空间中效果显著,也是算法性能得到大幅提升的原因。

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

图例3. 算法测试结果的直方图(评分范围为0到100,越高越好,其中100为理论上的最高可能得分,档案中附有计算排名表的脚本)
FBA的优缺点:
优点:
- 在中高维函数上表现稳定。
缺点:
- 在低维函数上的结果离散度较大。
- 该算法的基本理念虽有趣,但相对“偏弱”。
文章附有一个包含当前版本算法代码的归档文件。本文作者对标准算法描述的绝对准确性不承担责任。为提升搜索能力,已经对其中的许多算法进行了修改。文章中表述的结论和论断都是基于实验的结果。
文中所用的程序
| # | 名称 | 类型 | 描述 |
|---|---|---|---|
| 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_FBA.mq5 | 脚本 | FBA测试 |
本文由MetaQuotes Ltd译自俄文
原文地址: https://www.mql5.com/ru/articles/17458
注意: MetaQuotes Ltd.将保留所有关于这些材料的权利。全部或部分复制或者转载这些材料将被禁止。
本文由网站的一位用户撰写,反映了他们的个人观点。MetaQuotes Ltd 不对所提供信息的准确性负责,也不对因使用所述解决方案、策略或建议而产生的任何后果负责。
骆驼算法(CA)
神经网络在交易中的应用:混合图序列模型(GSM++)
新手在交易中的10个基本错误
大逃杀优化器(BRO)