logo

SCIENTIA SINICA Informationis, Volume 50 , Issue 3 : 396-407(2020) https://doi.org/10.1360/SSI-2019-0154

A hybrid swarm intelligence with improved ring topology for nonlinear equations

More info
  • ReceivedJul 20, 2019
  • AcceptedAug 23, 2019
  • PublishedFeb 26, 2020

Abstract

Solving nonlinear equations (NEs) is one of the most important yet challenging tasks in numerical computation, especially for the simultaneous location of multiple roots in a single run. In this paper, a hybrid swarm intelligence approach with improved ring topology is proposed to tackle this problem. It has three main features: (i) the improved ring topology is developed to effectively use the neighborhood knowledge; (ii) the hybrid swarm intelligence enhances the search efficiency; and (iii) an individual reinitialization mechanism is proposed to enrich the population diversity. The performance of this approach is tested on eight NE problems with multiple roots, experimentally confirming that it can simultaneously locate multiple roots in a single run. In addition, it can provide better results than conventional methods in terms of both root and success rates.


Funded by

国家自然科学基金(61573324,61873328)

国家杰出青年基金(61525304)


References

[1] Kastner M. Phase transitions and configuration space topology. Rev Mod Phys, 2008, 80: 167-187 CrossRef ADS Google Scholar

[2] Guo D, Nie Z, Yan L. The Application of Noise-Tolerant ZD Design Formula to Robots' Kinematic Control via Time-Varying Nonlinear Equations Solving. IEEE Trans Syst Man Cybern Syst, 2018, 48: 2188-2197 CrossRef Google Scholar

[3] Facchinei F, Kanzow C. Generalized Nash Equilibrium Problems. Ann Oper Res, 2010, 175: 177-211 CrossRef Google Scholar

[4] Mehta D, Grosan C. A collection of challenging optimization problems in science, engineering and economics. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC), 2015, 2697--2704. Google Scholar

[5] Darvishi M T, Barati A. A third-order Newton-type method to solve systems of nonlinear equations. Appl Math Computation, 2007, 187: 630-635 CrossRef Google Scholar

[6] Knoll D A, Keyes D E. Jacobian-free Newton-Krylov methods: a survey of approaches and applications. J Comput Phys, 2004, 193: 357-397 CrossRef ADS Google Scholar

[7] Qu B Y, Suganthan P N, Liang J J. Differential Evolution With Neighborhood Mutation for Multimodal Optimization. IEEE Trans Evol Computat, 2012, 16: 601-614 CrossRef Google Scholar

[8] Gong W Y, Wang Y, Cai Z H, et al. Finding multiple roots of nonlinear equation systems via a repulsion-based adaptive differential evolution. IEEE Trans Syst Man Cybern Syst, 2018. doi: 10.1109/TSMC.2018.2828018. Google Scholar

[9] Liao Z W, Gong W Y, Yan X S, et al. Solving nonlinear equations system with dynamic repulsion-based evolutionary algorithms. IEEE Trans Syst Man Cybern Syst, 2018. doi: 10.1109/TSMC.2018.2852798. Google Scholar

[10] He W, Gong W, Wang L. Fuzzy neighborhood-based differential evolution with orientation for nonlinear equation systems. Knowledge-Based Syst, 2019, 182: 104796 CrossRef Google Scholar

[11] Grosan C, Abraham A. A New Approach for Solving Nonlinear Equations Systems. IEEE Trans Syst Man Cybern A, 2008, 38: 698-714 CrossRef Google Scholar

[12] Song W, Wang Y, Li H X. Locating Multiple Optimal Solutions of Nonlinear Equation Systems Based on Multiobjective Optimization. IEEE Trans Evol Computat, 2015, 19: 414-431 CrossRef Google Scholar

[13] Gong W, Wang Y, Cai Z. A Weighted Biobjective Transformation Technique for Locating Multiple Optimal Solutions of Nonlinear Equation Systems. IEEE Trans Evol Computat, 2017, 21: 697-713 CrossRef Google Scholar

[14] Karaboga D, Basturk B. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Glob Optim, 2007, 39: 459-471 CrossRef Google Scholar

[15] Zhou F, Zhang X F, Zhang G B. The effects of parameters settings of ant colony algorithm on the performance of ultrasonic echo estimation. Sci Sin Inform, 2013, 43: 243-253 CrossRef Google Scholar

[16] Duan H B, Ye F. Progresses in pigeon-inspired optimization algorithms. J Beijing Univ Technol, 2017, 43: 1--7. Google Scholar

[17] Kennedy J. Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, Piscataway, 1995. 1942--1948. Google Scholar

[18] Duan H, Zhang D, Fan Y. From wolf pack intelligence to UAV swarm cooperative decision-making. Sci Sin Inform, 2019, 49: 112-118 CrossRef Google Scholar

[19] Zhu G, Kwong S. Gbest-guided artificial bee colony algorithm for numerical function optimization. Appl Math Computation, 2010, 217: 3166-3173 CrossRef Google Scholar

[20] Li S T, Duan H B. Arti cial bee colony approach to online parameters identification for hypersonic vehicle. Sci Sin Inform, 2012, 42: 1350-1363 CrossRef Google Scholar

[21] Zhang X, Wan Q, Fan Y. Applying modified cuckoo search algorithm for solving systems of nonlinear equations. Neural Comput Applic, 2019, 31: 553-576 CrossRef Google Scholar

[22] Ariyaratne M K A, Fernando T G I, Weerakoon S. Solving systems of nonlinear equations using a modified firefly algorithm (MODFA). Swarm Evolary Computation, 2019, 48: 72-92 CrossRef Google Scholar

[23] Li X D. Niching Without Niching Parameters: Particle Swarm Optimization Using a Ring Topology. IEEE Trans Evol Computat, 2010, 14: 150-169 CrossRef Google Scholar

[24] Wnag K, Gong W Y. Solving nonlinear equations system with an improved differential evolution. Control Decis, 2019. doi: 10.13195/j.kzyjc.2018.1739. Google Scholar

  • Figure 1

    Comparison between subscript-based ring topology and improved ring topology

  • Figure 2

    (Color online) Comparison of RR convergence curves of different algorithms. (a) F04; (b) F07.

  • Table 1   Parameter settings of different algorithms
    Algorithm Parameter settings
    IHABC ${\rm~NP}=100$, $c1=c2=2.05$, $F=0.5$, ${\rm~CR}=0.9$, $\rm~{limit}=50$
    CADE [24] $~{\rm~NP}=100$, $F=0.5$, ${\rm~CR}=0.9$, $T=10$
    MONES [12] ${\rm~NP}=100$, $H_m~=~{\rm~NP}$
    A-WeB [13] ${\rm~NP}=100$, $H_m~=~{\rm~NP}$
    RADE [8] ${\rm~NP}=100$, $H_m~=~200$
    DREA [9] ${\rm~NP}=10$, $u_{\rm~CR}=0.5$, $u_F=0.5$, $c=0.1$
    MODFA [22] ${\rm~NP}=100$, $\alpha=0.23$, $\beta_0=1$, $\delta=0.98$, $\gamma=1$
    FONDE [10] ${\rm~NP}=100$, $F=0.5$, ${\rm~CR}=0.9$, $m=11$
  •   

    Algorithm 1 The improved ring topology

    Input:Initial population $\mathcal{P}$.

    Select the best nectar source, set it as the first node of the ring topology, and remove it from $\mathcal{P}$;

    for $i=2$ to NP

    Find the nectar source in $\mathcal{P}$ nearest to node ${\boldsymbol~x}_{i-1}$ in the topological structure of the ring topology, set it as ${\boldsymbol~x}_i$, and remove it from $\mathcal{P}$;

    end for

    Output: the improved ring topology.

  • Table 2   Comparison of different algorithms with respect to root ratio (RR)
    Problem IHABC CADE MONES A-WeB RADE DREA MODFA FONDE
    F01 0.97 0.93 0.59 1.00 0.90 0.72 0.90 0.96
    F02 0.99 1.00 1.00 0.94 0.99 1.00 0.59 0.99
    F03 1.00 1.00 0.77 0.83 0.99 1.00 0.95 1.00
    F04 0.89 0.70 0.43 0.88 0.63 0.84 0.82 0.86
    F05 1.00 1.00 0.19 0.97 0.98 0.77 0.86 1.00
    F06 1.00 1.00 1.00 1.00 0.99 1.00 1.00 1.00
    F07 0.98 0.93 0.14 0.15 0.56 0.87 0.00 0.91
    F08 0.98 0.95 0.31 0.23 0.83 1.00 0.00 1.00
    Average 0.97 0.94 0.55 0.75 0.86 0.90 0.64 0.96
  •   

    Algorithm 2 A hybrid swarm intelligence algorithm with improved ring topology

    Initialize population $\mathcal{P}$ and evaluate the fitness;

    ${\rm~localBest}={\rm~nBest}=\mathcal{P}$, ${\rm~Iter}=1$;

    while ${\rm~FEs}<{\rm~FEs}_{\max}$ do

    Create a ring topology ${\boldsymbol~x}$ via Algorithm 1;

    for $i=1$ to NP

    Find the nearest nectar source ${\rm~localBest}({\rm~index})$ to ${\boldsymbol~x}_i$ in ${\rm~localBest}$;

    if ${\rm~fit}({\boldsymbol~x}_i)<{\rm~fit}({\rm~localBest}({\rm~index}))$ then

    ${\rm~localBest}({\rm~index})={\boldsymbol~x}_i$;

    end if

    end for

    for $i=1$ to NP

    ${\rm~nBest}(i)~\leftarrow~{\rm~neighborhoodBest}({\rm~localBest}(i-1),{\rm~localBest}(i),{\rm~localBest}(i+1))~$;

    end for

    for $i=1$ to NP

    Update nectar source location via Eq. (6);

    ${\rm~FEs}={\rm~FEs}+{\rm~NP}$;

    end for

    for $j=1$ to NP

    Generate a new position via Eq. (6), and calculate its fitness;

    ${\rm~FEs}={\rm~FEs}+1$;

    if the root is found then

    Store the root to an archive;

    Generate a new nectar source via Eq. (3) and calculate the fitness;

    ${\rm~FEs}={\rm~FEs}+1$;

    end if

    end for

    If nectar source has not been updated for more than limit, generate a new nectar source via Eq. (3);

    ${\rm~FEs}={\rm~FEs}+1$;

    ${\rm~Iter}={\rm~Iter}+1;$

    end while

    Return all the found roots.

  • Table 3   Comparison of different algorithms with respect to success rate (SR)
    Problem IHABC CADE MONES A-WeB RADE DREA MODFA FONDE
    F01 0.73 0.46 0.00 1.00 0.31 0.00 0.06 0.52
    F02 0.96 1.00 1.00 0.60 0.93 1.00 0.00 0.98
    F03 1.00 1.00 0.00 0.12 0.98 1.00 0.80 1.00
    F04 0.43 0.06 0.00 0.28 0.00 0.20 0.20 0.28
    F05 1.00 1.00 0.00 0.76 0.89 0.00 0.40 1.00
    F06 1.00 1.00 1.00 1.00 0.94 1.00 1.00 1.00
    F07 0.80 0.40 0.00 0.00 0.00 0.00 0.00 0.28
    F08 0.96 0.90 0.07 0.02 0.67 1.00 0.00 1.00
    Average 0.86 0.72 0.25 0.47 0.59 0.53 0.30 0.75
  • Table 4   Comparison of different components in IHABC with respect to root ratio (RR)
    Problem IHABC-1 IHABC-2 IHABC-3 IHABC-4 IHABC-5 IHABC-6 IHABC-7 IHABC
    F01 0.65 0.77 0.06 0.83 0.98 0.87 0.68 0.97
    F02 0.57 0.81 0.00 0.97 0.98 0.99 0.80 0.99
    F03 0.60 0.84 0.00 0.95 1.00 1.00 0.93 1.00
    F04 0.69 0.64 0.18 0.63 0.71 0.60 0.51 0.88
    F05 0.67 0.97 0.16 0.98 1.00 1.00 1.00 1.00
    F06 0.69 0.72 0.10 0.73 1.00 1.00 0.99 1.00
    F07 0.13 0.14 0.05 0.45 0.56 0.83 0.56 0.98
    F08 0.91 0.90 0.00 0.93 0.78 0.98 0.58 0.98
    Average 0.61 0.72 0.07 0.81 0.87 0.91 0.76 0.97
  • Table 5   Comparison of different components in IHABC with respect to success rate (SR)
    Problem IHABC-1 IHABC-2 IHABC-3 IHABC-4 IHABC-5 IHABC-6 IHABC-7 IHABC
    F01 0.00 0.00 0.00 0.00 0.76 0.10 0.00 0.73
    F02 0.03 0.06 0.00 0.76 0.90 0.96 0.06 0.96
    F03 0.00 0.20 0.00 0.70 1.00 1.00 0.56 1.00
    F04 0.06 0.06 0.00 0.03 0.06 0.00 0.00 0.43
    F05 0.00 0.73 0.00 0.90 1.00 1.00 1.00 1.00
    F06 0.00 0.00 0.00 0.00 1.00 1.00 0.96 1.00
    F07 0.00 0.00 0.00 0.00 0.00 0.03 0.00 0.80
    F08 0.86 0.80 0.00 0.86 0.57 0.96 0.16 0.96
    Average 0.12 0.23 0.00 0.40 0.66 0.63 0.34 0.86
  • Table 6   Influence of different neighborhood sizes on IHABC
    Problem RR SR
    $n=5$ $n=10$ $n=15$ $n=20$ $n=25$ $n=5$ $n=10$ $n=15$ $n=20$ $n=25$
    F01 0.97 0.99 0.98 0.97 0.94 0.73 0.87 0.80 0.67 0.40
    F02 0.99 1.00 1.00 1.00 1.00 0.96 1.00 1.00 1.00 1.00
    F03 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00
    F04 0.88 0.91 0.70 0.76 0.81 0.43 0.60 0.07 0.20 0.33
    F05 1.00 1.00 1.00 1.00 0.99 1.00 1.00 1.00 1.00 0.93
    F06 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00 1.00
    F07 0.98 0.96 0.86 0.75 0.69 0.80 0.47 0.00 0.00 0.00
    F08 0.98 0.90 0.93 0.90 0.87 0.96 0.80 0.87 0.80 0.73
    Average 0.97 0.96 0.94 0.92 0.91 0.86 0.84 0.72 0.71 0.68

Copyright 2020  CHINA SCIENCE PUBLISHING & MEDIA LTD.  中国科技出版传媒股份有限公司  版权所有

京ICP备14028887号-23       京公网安备11010102003388号