search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
32 stars 15 forks source link

S-Metric Selection Evolutionary Multi-objective Optimization Algorithm (SMS-EMOA) #3055

Open HeuristicLab-Trac-Bot opened 4 years ago

HeuristicLab-Trac-Bot commented 4 years ago

Issue migrated from trac ticket # 3055

component: Algorithms | priority: medium | keywords: MOO, Hypervolume Contribution, indicator-based

2020-02-06 13:10:07: @kfyang created the issue

  • This algorithm is SMS-EMOA implementation on HL. The main structure and interfaces with HL are copied from MOEA/D on HL, which was written by Dr. Bogdan Burlacu. The S-metric (hypervolume contribution, HVC) selection operator was adapted from Kaifeng's MATLAB toolbox in SMS-EMOA. The computational complexity of HVC is AT LEAST $O (n^2 \log n)$ in 2-D and 3-D cases. HVC should definitely be reduced to $\Theta (n \times \log n)$.
    • This algorithm assumes:
      1. minimization problems. For maximization problems, it is better to add "-" symbol.
    • This algorithm works on:
      1. continuous, discrete, mixed-integer MOO problems. For different types of problems, the operators should be adjusted accordingly.
      1. both multi-objective and many-objective problems. For many-objective problems, the bottleneck is the computational complexity of HV.
    • This algorithm is the basic implementation of SMS-EMOA, proposed by Michael Emmerich et. al. Some potential improvements can be:
      1. Dynamic reference point strategy
      1. Normalized fitness value strategy ---- desirability function. See, Yali, Longmei, Kaifeng, Michael Emmerich CEC paper.
      1. HVC calculation should definitely be improved, at least in the 2D and 3D cases.
      1. multiple point strategy when $\lambda>1$
      1. multiple reference points strategy, in ICNC 2016, Zhiwei Yang et. al.
      1. HVC approximation by R2 for MANY OBJECTIVE cases, by Ishibushi 2019, IEEE TEC
      1. Maybe: See maps
    • Global parameters:
      1. population
    • Many thanks for Bogdan Burlacu and Johannes Karder, especially Bogdan for his explanation, help, and supports.
HeuristicLab-Trac-Bot commented 4 years ago

2020-02-06 13:21:35: @kfyang changed status from new to accepted

HeuristicLab-Trac-Bot commented 4 years ago

2020-02-06 13:23:27: @kfyang commented

r17424: created branch for SMS-EMOA

HeuristicLab-Trac-Bot commented 4 years ago

2020-02-06 13:30:32: @kfyang commented

r17425: Added the first version of SMS-EMOA

HeuristicLab-Trac-Bot commented 4 years ago

2020-02-17 16:32:01: @kfyang commented

r17440: Fixed the bug of "no reference point" on non-scientific benchmarks (e.g., MOPs of symbolic regression).