logo

SCIENCE CHINA Information Sciences, Volume 62, Issue 7: 070206(2019) https://doi.org/10.1007/s11432-018-9754-6

A self-organizing multimodal multi-objective pigeon-inspired optimization algorithm

More info
  • ReceivedAug 15, 2018
  • AcceptedNov 30, 2018
  • PublishedMay 31, 2019

Abstract

Multi-objective optimization algorithms have recently attracted much attention as they can solve problems involving two or more conflicting objectives effectively and efficiently. However, most existing studies focus on improving the performance of the solutions in the objective spaces. This paper proposes a novel multimodal multi-objective pigeon-inspired optimization (MMOPIO) algorithm where some mechanisms are designed for the distribution of the solutions in the decision spaces. First, MMOPIO employs an improved pigeon-inspired optimization (PIO) based on consolidation parameters for simplifying the structure of the standard PIO. Second, the self-organizing map (SOM) is combined with the improved PIO for better control of the decision spaces, and thus, contributes to building a good neighborhood relation for the improved PIO. Finally, the elite learning strategy and the special crowding distance calculation mechanisms are used to prevent premature convergence and obtain solutions with uniform distribution, respectively. We evaluate the performance of the proposed MMOPIO in comparison to five state-of-the-art multi-objective optimization algorithms on some test instances, and demonstrate the superiority of MMOPIO in solving multimodal multi-objective optimization problems.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61473266, 61673404, 61305080, 61806179, 61876169, U1304602), China Postdoctoral Science Foundation (Grant Nos. 2014M552013, 2017M622373), Project Supported by the Research Award Fund for Outstanding Young Teachers in Henan Provincial Institutions of Higher Education of China (Grant No. 2014GGJS-004), Program for Science and Technology Innovation Talents in Universities of Henan Province in China (Grant Nos. 16HASTIT041, 16HASTIT033), and Scientific and Technological Project of Henan Province (Grant No. 152102210153).


References

[1] Ali M Z, Awad N H, Duwairi R M. Multi-objective differential evolution algorithm with a new improved mutation strategy. Int J Artif Intell, 2016, 14: 23--41. Google Scholar

[2] Gong D W, Qin N N, Sun X Y. Evolutionary algorithms for optimization problems with uncertainties and hybrid indices. Inf Sci, 2011, 181: 4124-4138 CrossRef Google Scholar

[3] Guan X M, Zhang X J, Lv R L. A large-scale multi-objective flights conflict avoidance approach supporting 4D trajectory operation. Sci China Inf Sci, 2017, 60: 112202 CrossRef Google Scholar

[4] Qu B Y, Zhou Q, Xiao J M. Large-Scale Portfolio Optimization Using Multiobjective Evolutionary Algorithms and Preselection Methods. Math Problems Eng, 2017, 2017: 1-14 CrossRef Google Scholar

[5] Tian Y, Cheng R, Zhang X. An Indicator-Based Multiobjective Evolutionary Algorithm With Reference Point Adaptation for Better Versatility. IEEE Trans Evol Computat, 2018, 22: 609-622 CrossRef Google Scholar

[6] Liang J J, Zheng B, Qu B Y, et al. Multi-objective differential evolution algorithm based on fast sorting and a novel constraints handling technique. In: Proceedings of IEEE Congress on Evolutionary Computation, Beijing, 2014. 445--450. Google Scholar

[7] Gong D W, Sun J, Ji X. Evolutionary algorithms with preference polyhedron for interval multi-objective optimization problems. Inf Sci, 2013, 233: 141-161 CrossRef Google Scholar

[8] Rong M, Gong D W, Zhang Y, et al. Multidirectional prediction approach for dynamic multiobjective optimization problems. IEEE Trans Cybern, 2018. doi: 10.1109/TCYB.2018.2842158. Google Scholar

[9] Zhang X, Zheng X, Cheng R. A competitive mechanism based multi-objective particle swarm optimizer with fast convergence. Inf Sci, 2018, 427: 63-76 CrossRef Google Scholar

[10] Liu Y P, Gong D W, Sun J. A Many-Objective Evolutionary Algorithm Using A One-by-One Selection Strategy.. IEEE Trans Cybern, 2017, 47: 2689-2702 CrossRef PubMed Google Scholar

[11] Liu Y P, Gong D W, Sun X. Many-objective evolutionary optimization based on reference points. Appl Soft Computing, 2017, 50: 344-355 CrossRef Google Scholar

[12] Gong D W, Sun J, Miao Z. A Set-Based Genetic Algorithm for Interval Many-Objective Optimization Problems. IEEE Trans Evol Computat, 2018, 22: 47-60 CrossRef Google Scholar

[13] Preuss M, Kausch C, Bouvy C, et al. Decision space diversity can be essential for solving multiobjective real-world problems. In: Proceedings of the 19th International Conference on Multiple Criteria Decision Making, Auckland, 2010. 367--377. Google Scholar

[14] Liang J J, Yue C T, Qu B Y. Multimodal multi-objective optimization: A preliminary study. In: Proceedings of IEEE Congress on Evolutionary Computation, Vancouver, 2016. 2454--2461. Google Scholar

[15] Liang J J, Qu B Y, Mao X B. Differential evolution based on fitness Euclidean-distance ratio for multimodal optimization. Neurocomputing, 2014, 137: 252-260 CrossRef Google Scholar

[16] 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

[17] Liang J J, Ma S T, Qu B Y, et al. Strategy adaptative memetic crowding differential evolution for multimodal optimization. In: Proceedings of IEEE Congress on Evolutionary Computation, Brisbane, 2012. 1--7. Google Scholar

[18] Deb K, Tiwari S. Omni-optimizer: a procedure for single and multi-objective optimization. In: Proceedings of International Conference on Evolutionary Multi-Criterion Optimization, Guanajuato, 2005. 47--61. Google Scholar

[19] Yue C T, Qu B Y, Liang J J. A Multiobjective Particle Swarm Optimizer Using Ring Topology for Solving Multimodal Multiobjective Problems. IEEE Trans Evol Computat, 2018, 22: 805-817 CrossRef Google Scholar

[20] Liang J, Guo Q Q, Yue C T, et al. A self-organizing multi-objective particle swarm optimization algorithm for multimodal multi-objective problems. In: Proceedings of International Conference on Swarm Intelligence, Shanghai, 2018. 550--560. Google Scholar

[21] Liang J J, Chan C C, Huang V L, et al. Improving the performance of a FBG sensor network using a novel dynamic multi-swarm particle swarm optimizer. In: Proceedings of SPIE - The International Society for Optical Engineering, Boston, 2005. 373--378. Google Scholar

[22] Liang J J, Pan Q K, Chen T J. Solving the blocking flow shop scheduling problem by a dynamic multi-swarm particle swarm optimizer. Int J Adv Manuf Technol, 2011, 55: 755-762 CrossRef Google Scholar

[23] Liang J J, Song H, Qu B Y. Comparison of Three Different Curves Used in Path Planning Problems Based on Particle Swarm Optimizer. Math Problems Eng, 2014, 2014: 1-15 CrossRef Google Scholar

[24] Liu S, Xian N, Duan H B. Voronoi diagram and ACO approach to Three-Dimension path planning for uninhabited combat air vehicle with situation assessment. Sci China Inf Sci, in press. doi: 10.1007/s11432-016-9100-5. Google Scholar

[25] Duan H, Qiao P. Pigeon-inspired optimization: a new swarm intelligence optimizer for air robot path planning. Int Jnl Intel Comp Cyber, 2014, 7: 24-37 CrossRef Google Scholar

[26] Xin L, Xian N. Biological object recognition approach using space variant resolution and pigeon-inspired optimization for UAV. Sci China Technol Sci, 2017, 60: 1577-1584 CrossRef Google Scholar

[27] Lei X, Ding Y, Wu F X. Detecting protein complexes from DPINs by density based clustering with Pigeon-Inspired Optimization Algorithm. Sci China Inf Sci, 2016, 59: 070103 CrossRef Google Scholar

[28] Qiu H X, Duan H B. Multi-objective pigeon-inspired optimization for brushless direct current motor parameter design. Sci China Technol Sci, 2015, 58: 1915-1923 CrossRef Google Scholar

[29] Kohonen T. Automatic formation of topological maps of patterns in a self-organizing system. In: Proceedings of the 2nd Scandinavian Conference on Image Analysis, Simula, 1981. 214--220. Google Scholar

[30] Liu G, Yang H. Self-organizing network for variable clustering. Ann Oper Res, 2018, 263: 119-140 CrossRef Google Scholar

[31] Jin H, Shum W H, Leung K S. Expanding Self-Organizing Map for data visualization and cluster analysis. Inf Sci, 2004, 163: 157-173 CrossRef Google Scholar

[32] Tsai W P, Huang S P, Cheng S T. A data-mining framework for exploring the multi-relation between fish species and water quality through self-organizing map.. Sci Total Environ, 2017, 579: 474-483 CrossRef PubMed Google Scholar

[33] Zhang H, Zhou A, Song S. A Self-Organizing Multiobjective Evolutionary Algorithm. IEEE Trans Evol Computat, 2016, 20: 792-806 CrossRef Google Scholar

[34] Chen J H, Su M C, Cao R. A self organizing map optimization based image recognition and processing model for bridge crack inspection. Automation Construction, 2017, 73: 58-66 CrossRef Google Scholar

[35] Gu F, Cheung Y M. Self-Organizing Map-Based Weight Design for Decomposition-Based Many-Objective Evolutionary Algorithm. IEEE Trans Evol Computat, 2018, 22: 211-225 CrossRef Google Scholar

[36] Haykin S S. Neural Networks and Learning Machines. Beijing: China Machine Press, 2009. Google Scholar

[37] Rudolph G, Naujoks B, Preuss M. Capabilities of EMOA to detect and preserve equivalent pareto subsets. In: Proceedings of International Conference on Evolutionary Multi-Criterion Optimization, Matsushima, 2007. 36--50. Google Scholar

[38] Tang L, Wang X. A Hybrid Multiobjective Evolutionary Algorithm for Multiobjective Optimization Problems. IEEE Trans Evol Computat, 2013, 17: 20-45 CrossRef Google Scholar

[39] Zhou A M, Zhang Q F, Jin Y C. Approximating the Set of Pareto-Optimal Solutions in Both the Decision and Objective Spaces by an Estimation of Distribution Algorithm. IEEE Trans Evol Computat, 2009, 13: 1167-1189 CrossRef Google Scholar

  • Figure 1

    (Color online) Example of multimodal multi-objective problem.

  • Figure 2

    (Color online) Illustration of improved PIO.

  • Figure 3

    (Color online) Illustration of a two-dimensional SOM.

  • Figure 4

    (Color online) The process of finding nbest.

  • Figure 5

    (Color online) PSP values obtained by MMOPIO with different $~\lambda~$ values.

  • Figure 6

    (Color online) PSs of MM4 obtained by different algorithms. (a) PS of Omni-Optimizer; (b) PS of MPIO; protectłinebreak (c) PS of DN-NSGA-II; (d) PS of MO-Ring-PSO-SCD; (e) PS of SMPSO-MM; (f) PS of MMOPIO.

  • Figure 7

    (Color online) PFs of MM4 obtained by different algorithms. (a) PF of Omni-Optimizer; (b) PF of MPIO; protectłinebreak (c) PF of DN-NSGA-II; (d) PF of MO-Ring-PSO-SCD; (e) PF of SMPSO-MM; (f) PF of MMOPIO.

  • Figure 8

    (Color online) PSP value box-plots of 11 test functions under six different algorithms. In each plot, the horizontal axis numbers indicate different algorithms: 1=Omni-Optimizer, 2=MPIO, 3=DN-NSGA-II, 4=MO-Ring-PSO-SCD, 5=SMPSO-MM, and 6=MMOPIO. (a) MMF1; (b) MMF2; (c) MMF3; (d) MMF4; (e) MMF5; (f) MMF6; (g) MMF7; (h) MMF8; (i) SYM-PART-simple; (j) SYM-PART-rotated; (k) Omni-test.

  • Figure 9

    (Color online) Achieved PSP values of different algorithms with different population sizes. (a) PSP values on MMF1; (b) PSP values on MMF3; (c) PSP values on MMF7; (d) PSP values on MMF8; (e) PSP values on SYM-PART-simple; (f) PSP values on Omni-test.

  • Table 1   PSP values achieved by different algorithms
    crcrrrcMean (Std dev) specialrule0em
    1pt
    0.5pt
    MMF1 36.93(5.51) MMF2 56.17(25.93) $~\circleddash~$ 1.89(1.02) $~\circleddash~$ 49.68(18.52) $~\circleddash~$ 74.99(13.72) $~\circleddash~$ MMF3 64.36(22.41) $~\circleddash~$ 2.98(1.72) $~\circleddash~$ 52.06(19.85) $~\circleddash~$ 99.17(14.21) $~\circleddash~$ MMF4 38.22(8.78) MMF5 13.15(1.34) MMF6 15.74(1.43) MMF7 82.64(16.29) $~\circleddash~$ MMF8 14.16(5.19) SYM-PART-simple 1.85(5.01) SYM-PART-rotated 2.64(4.22) Omni-test 0.87(0.13) $~\circledast~$/ $~\circleddash~$ /$~\circledcirc~$ 0/11/0
  •   

    Algorithm 1 Framework of MMOPIO

    Require:$~N~$ (pigeon size), x (current positions of pigeons),v (current velocities of pigeons), $~\delta^{e}~$ (standard deviation)

    P (test data);

    (x, v, A, D) $~\leftarrow~{\rm~Initialize}(N)~$;

    while termination criterion not fulfilled do

    nbest $~\leftarrow$ Self-OrganizingBasedLearning$(\textbf{\textit{x}},~\textbf{\textit{v}})$;

    x $~\leftarrow$ Inversemap(nbest , find the pigeon particle corresponding to nbest according to (14);

    Sortedtextunderscorex $~\leftarrow~$ non-dominated-SCD-sort(x);

    for each $~\textit{\textbf{x}}_{i}~\in~$ Sortedtextunderscorex

    $~(\textbf{\textit{x}}_{i},~\textbf{\textit{v}}_{i})~$ $~\leftarrow~$ Update positions and velocities of pigeons by (9) and (10);

    $~\textit{\textbf{x}}_{i}~$ $~\leftarrow~$ Generate offspring by the elite learning strategy according to (11);

    TemptextunderscoreA $~\leftarrow~$ A $~\cup~$ $~\left\lbrace~\textbf{\textit{x}}_{i}~\right\rbrace~$, i is the current iteration;

    SortedtextunderscoreA $~\leftarrow~$ non-dominated-SCD-sort(TemptextunderscoreA);

    D $~\leftarrow~$ SortedtextunderscoreA $~\backslash~$ A;

    end for

    end while

    Output:$~\textbf{\textit{x}}~$ (final positions of pigeons).

  •   

    Algorithm 2 Self-OrganizingBasedLearning(x, v)

    Require:x (current positions of pigeons), v (current velocities of pigeons), $~\textbf{\textit{w}}^{u}~$ (neuron weight vectors) $~\eta_{0}~$ (learning rate), $~\sigma_{0}~$ (learning radius), R (the map-and-compass operator parameter) $~\lambda~$ (the consolidation parameter);

    $~\textbf{\textit{w}}^{u}$ $~\leftarrow~{\rm~Initialize}(\textbf{\textit{x}})~$;

    ($~\eta~$, $~\sigma~$) $~\leftarrow~$ Calculate values of learning rate and radius by (12) and (13);

    Find the best neuron in D by (14);

    Find the neighboring neurons of $~\textit{u}{'}~$ by (15);

    Update the neuron weight vectors $~\textbf{\textit{w}}^{u}$ according to (16);

    Map the pigeons of P to the updated SOM latent space and record the best neuron to the archive AA. The best neuron is found according to (14);

    Map the pigeons of A to the updated SOM latent space and record nbest to the archive BA, nbest=BA $~\left\lbrace~I^{u}_{m}~\right\rbrace~$, $~I^{u}_{m}~$ indicates the index of the $~m$-th nearest neuron to neuron u in the latent space;

    Output:nbest (the neighborhood pigeons).

  • Table 2   IDGf values achieved by different algorithms
    cccccccMean (Std dev) Omni-Optimizer MPIO DN-NSGA-II MO-Ring-PSO-SCD SMPSO-MM MMOPIO
    specialrule0em
    0pt
    1pt
    MMF1 (5.62E-05) (1.16E-01) (7.37E-05) (6.40E-05) (3.89E-05) (3.99E-05)
    specialrule0em
    0pt
    1pt
    MMF2 (1.11E-03) (2.68E-01) (6.74E-04) (8.19E-04) (4.77E-04) (2.83E-04)
    specialrule0em
    0pt
    1pt
    MMF3 (1.63E-04) (3.21E-01) (1.79E-03) (5.86E-04) (3.01E-04) (1.78E-04)
    specialrule0em
    0pt
    1pt
    MMF4 (6.52E-05) (4.37E-01) (6.87E-05) (7.30E-05) (3.49E-05) (3.79E-05)
    specialrule0em
    0pt
    1pt
    MMF5 specialrule0em
    0pt
    1pt
    (2.97E-05) (4.36E-02) (4.19E-05) (4.10E-05) (2.18E-05) (2.88E-05)
    MMF6 specialrule0em
    0pt
    1pt
    (3.14E-05) (2.40E-01) (5.86E-05) (3.75E-05) (2.50E-05) (2.83E-05)
    MMF7 specialrule0em
    0pt
    1pt
    (3.21E-05) (2.38E-01) (6.32E-05) (4.76E-05) (2.11E-05) (2.39E-05)
    MMF8 specialrule0em
    0pt
    1pt
    (3.20E-05) (4.50E-01) (6.65E-05) (8.41E-05) (5.83E-05) (4.49E-05)
    SYM-PART-simple specialrule0em
    0pt
    1pt
    (4.07E-04) (3.45E-01) (4.59E-04) (1.52E-03) (1.59E-03) (4.76E-04)
    SYM-PART-rotated specialrule0em
    0pt
    1pt
    (4.78E-04) (3.63E-01) (6.70E-04) (2.17E-03) (2.21E-03) (8.12E-04)
    Omni-test (2.13E-04) (6.13E-01) (3.03E-04) (3.03E-03) (2.50E-03) (3.58E-04)
    specialrule0em
    0pt
    1pt
    $~\circledast~$/ $~\circleddash~$ /$~\circledcirc~$ 3/7/1 0/11/0 2/7/2 1/10/0 1/8/2

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1