针对数值优化问题的边界约束处理方法
[English version]


在求解数值优化问题 (Numerical Optimization Problem, NOP)时。通常的搜索算法,比如演化策略 (Evolution Strategy, ES), 社会认知优化算法 (Social Cognitive Optimization, SCO), 粒子群优化算法 (Particle Swarm Optimization, PSO), 差分进化算法 (Differential Evolution DE), DEPSO, 遗传算法 (Genetic Algorithm, GA) 等,都会遇到边界约束问题。

为简单起见,这里只考虑一维情形,即在连续区间 [a, b] 中搜索 x,其中a, b 分别为区间的上下界。边界约束问题即指处理当搜索算子新产生的 x 值为无效值,即不在区间 [a, b] 中的情形。以下总结了一些已有的处理方式:

  • 重试法 [1]: 本处理方法重新运行搜索算子产生n次x,直至x落在区间 [a, b] 时返回 x,否则宣布搜索算子尝试无效。
    * 优点:产生的解受边界影响的 sampling bias 不明显。
    * 缺点:需要重新运行搜索算子数次,而且仍有可能返回无效值。
  • 随机法 [2]: 本方法直接返回一个在区间 [a, b] 中的随机值。
  • 边界法 [2]: 本方法直接返回一个边界值,即如果 x<a, 则返回 x=a; 如果 x>b, 则返回 x=b。
  • * 优点:两种方式都处理简单。
    * 缺点:产生的解受边界影响使得 sampling bias 明显。随机法有可能导致过多的随机变异,而边界法有可能使得搜索过于偏向边界处。

  • 周期法 [2]: 在本方法中,搜索空间 [a, b] 被转换为无限空间 (即从负无穷到正无穷),而且适应度函数 f(x) 转化为周期形式: 如果x<a,则有f(x)=f(b-(a-x)%c); 如果x>b,则有f(x)=f(a+(x-b)%c)。其中"%"为求模算子,c=b-a 为区间范围。在运行时搜索过程中,搜索算子立刻返回所得到的x值。只有在最后输出解时,再将 x 值转化后输出:如果x<a,则有输出x=b-(a-x)%c; 如果x>b,则输出x=a+(x-b)%l; 否则直接输出 x。
  • * 优点:由于在无限空间中搜索,边界的影响不会导致 sampling bias。另外,对于某些适应度函数,如果有次优解靠近一个边界,而最优解靠近另外一个边界时,周期形式可以使得它们很靠近,从而降低从该次优解到最优解的搜索难度。
    * 缺点:由于在无限空间中搜索,搜索过程一旦发散则有可能使得已有的搜索点占用的搜索区间过大而使得搜索无效。因为有效搜索区间仍需在大约为 c=b-a 的范围内,虽然区间边界可以变化。所以要求搜索算子本身不容易发散。

  • 环状法 [3]: 本方法中,搜索空间 [a, b] 可以被看作卷成一个环,其中a和b被叠到重合。这样搜索算子有两个改变。1) 在求解区间中任意两点 x1 到 x2 的距离dx时,计算方式不再为简单的 dx=x1-x2,而是按环上面较短的一个方向来计算,即:如果 dx<-c/2, 则有 dx=dx+c; 如果 dx>c/2, 则有 dx=dx-c;否则dx值不变。2) 最后搜索算子求得的 x 值仍有可能越界,须按周期方式映射回搜索区间,即:如果x<a,则有输出x=b-(a-x)%c; 如果x>b,则输出x=a+(x-b)%c; 否则直接输出 x。
  • * 优点:和周期法类似,因为本方法可以看做在准无限空间中搜索。而且本方法不容易导致搜索发散,因为所有搜索点都保持在原搜索空间内。
    * 缺点:比周期法多一个运行时搜索过程的越界处理,但是和适应度函数本身的计算量比大多数情况下可以忽略。

    相关论文

    1. T. P. Runarsson, X. Yao. Stochastic ranking for constrained evolutionary optimization. IEEE Transactions on Evolutionary Computation (CEC), , 2000, 4(3): 284-294
    2. Wen-Jun Zhang, Xiao-Feng Xie, De-Chun Bi. Handling boundary constraints for numerical optimization by particle swarm flying in periodic search space. Congress on Evolutionary Computation (CEC), Oregon, USA, 2004: 2307-2311
    3. Xiao-Feng Xie, Jiming Liu. A compact multiagent system based on autonomy oriented computing, IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT), Compiégne, France, 2005: 38-44 [DOI]

    Return to homepage

    Maintained by AdaptiveBox StUdIo, under a Creative Commons Attribution 3.0 License.