PaperlayerView exact revision on arXiv

Source-linked AI summary

Evolutionary Multiobjective Optimization Driven by Generative Adversarial Networks (GANs)

Cheng He, Shihua Huang, Ran Cheng, Kay Chen Tan, Yaochu Jin

arXiv:1910.04966v2cs.NEcs.LG

TL;DR

Model-based evolutionary algorithms use candidate solutions as training data, motivating methods that can operate with limited data in high-dimensional spaces. GMOEA uses GAN-driven reproduction with real/fake sample classification, hybrid offspring generation, and GAN training; it performs best overall on ten IMF problems and handles problems with up to 200 decision variables.

  • Problem

    Model-based evolutionary algorithms use candidate solutions as training data, creating a need for data augmentation in high-dimensional decision spaces.

  • Method

    GMOEA classifies candidate solutions into real and fake datasets, trains GANs with these data and generated samples, and hybridizes GAN sampling with classic stochastic reproduction.

  • Results

    GMOEA performed best on IMF1 to IMF10 overall and showed better performance than model-free MOEAs, with effectiveness demonstrated for problems with up to 200 decision variables.

  • Takeaways & Limitations

    GAN-driven reproduction can generate promising offspring with relatively small training datasets while balancing exploitation and exploration through hybrid reproduction.

Abstract

from arXiv · show

Recently, increasing works have proposed to drive evolutionary algorithms using machine learning models. Usually, the performance of such model based evolutionary algorithms is highly dependent on the training qualities of the adopted models. Since it usually requires a certain amount of data (i.e. the candidate solutions generated by the algorithms) for model training, the performance deteriorates rapidly with the increase of the problem scales, due to the curse of dimensionality. To address this issue, we propose a multi-objective evolutionary algorithm driven by the generative adversarial networks (GANs). At each generation of the proposed algorithm, the parent solutions are first classified into real and fake samples to train the GANs; then the offspring solutions are sampled by the trained GANs. Thanks to the powerful generative ability of the GANs, our proposed algorithm is capable of generating promising offspring solutions in high-dimensional decision space with limited training data. The proposed algorithm is tested on 10 benchmark problems with up to 200 decision variables. Experimental results on these test problems demonstrate the effectiveness of the proposed algorithm.

I. INTRODUCTION

Multiobjective evolutionary algorithms address conflicting objectives, but conventional and model-based methods face limits in learning from high-dimensional decision spaces. The paper motivates GAN-driven reproduction to reuse generated data and improve offspring generation with limited training data.

  • Multiobjective optimization: MOPs optimize multiple conflicting objectives, seeking solutions that approximate the Pareto front in both convergence and diversity.
  • Conventional MOEAs: Conventional MOEAs combine offspring reproduction, fitness assignment, and environmental selection, but stochastic reproduction does not explicitly learn from fitness landscapes.
  • Model-based evolutionary algorithms: Model-based evolutionary algorithms replace heuristic operations or objective functions with machine learning models trained on candidate solutions.
  • Challenges: Existing model-based evolutionary algorithms deteriorate rapidly as decision variables increase because training-data requirements grow exponentially and multiple objectives may require multiple models.
  • GAN motivation: GANs are motivated for reproduction because they can model solution-set distributions and classify samples as real or fake, paralleling distinctions among candidate solutions.
  • Proposed direction: GMOEA reuses GAN-generated data as training data and samples multivariate normal inputs learned from promising candidate solutions approximating the non-dominated front.

II. BACKGROUND

GANs learn a model distribution that imitates target data through adversarial training between a generator and discriminator. The training alternates discriminator and generator updates using Gaussian noise and given data.

  • GAN structure: A GAN consists of a generator mapping Gaussian noise to generated samples and a discriminator outputting the probability that an input is real.
  • Adversarial training: The discriminator favors real samples and rejects generated samples, while the generator seeks samples that the discriminator recognizes as real.
  • Training procedure: GAN training samples batches from Gaussian noise and the target data before updating the discriminator by gradient descent.
  • Training procedure: The generator is then updated by gradient descent, and these discriminator-generator updates repeat for multiple iterations.

B. Improved Strength Pareto Based Selection

SPEA2 uses dominance strength, raw fitness, density estimation, and truncation to select a diverse population. GMOEA adopts this selection machinery for solution classification and environmental selection.

  • Fitness assignment: SPEA2 assigns strength from pairwise dominance relationships, where strength indicates how many candidate solutions each solution dominates.
  • Fitness assignment: Raw fitness is computed from the strengths associated with the population's candidate solutions.
  • Density estimation: Density information discriminates candidates with identical raw fitness values using nearest-neighbor distance information.
  • Environmental selection: Environmental selection first retains candidates with Fit<1, then fills or truncates the set to N solutions using fitness and Euclidean-distance criteria.
  • Use in GMOEA: GMOEA adopts SPEA2's density-aware machinery for solution classification and environmental selection to maintain diverse candidate solutions.

III. THE PROPOSED ALGORITHM

GMOEA repeatedly classifies a population into real and fake datasets, trains GANs, generates offspring through hybrid reproduction, and selects the next population. This loop continues until termination.

  • Initialization and training: GMOEA initializes a population of size N and a pair of GANs, then divides population candidates into equally sized real and fake datasets for training.
  • Offspring reproduction: At each iteration, GMOEA generates N offspring using its hybrid reproduction strategy after model training.
  • Environmental selection: Environmental selection chooses N solutions from the combined parent and offspring populations.
  • Algorithm loop: Solution classification, model training, offspring reproduction, and environmental selection repeat until the termination criterion is satisfied.

A. Solution Classification

GMOEA classifies population candidates into real and fake datasets for GAN training, selecting real samples to promote convergence and diversity.

  • The classification divides population candidates into equal-sized real and fake datasets for GAN training.Real solutions are better converged and evenly distributed, while fake solutions have relatively poor quality.
  • Environmental selection chooses half of the current population as real samples and the remainder as fake samples.
  • The classification procedure calculates fitness values, selects candidate solutions, removes excess candidates, and returns labeled decision vectors.
  • Selecting candidates by convergence and diversity increases selection pressure toward the Pareto front and supports the GANs’ identity-independent distribution assumption.

B. Model Training

GMOEA trains GANs using classified population data and samples from a Gaussian distribution estimated from real solutions. The model uses a deliberately simple architecture and updates discriminator and generator losses iteratively.

  • The generator and discriminator use feedforward neural networks with two and one hidden layers, respectively, each layer containing D neurons.The simple structure limits training-data requirements and computational cost for the investigated problems.
  • The model-training procedure is presented as the general training scheme for the proposed GMOEA.
  • The training data include real samples, fake samples, and samples generated by the generator.
  • At each iteration, the discriminator is updated with minibatches from the classified data, and the generator is updated using newly generated samples.
  • The Gaussian input distribution is specified by the mean vector and covariance matrix of the real samples.The covariance captures correlations between variables, while the mean identifies where samples are most likely to occur.

C. Offspring Reproduction

GMOEA uses a hybrid offspring strategy that combines GAN-generated candidates with crossover and mutation, balancing exploitation and exploration while constraining generated solutions to the decision-space boundaries.

  • Each generation produces offspring either with the GAN model or with genetic operators, using equal probability.The hybrid strategy combines model-based generation with crossover and mutation.
  • Mixing GAN-generated candidates with genetic-operator offspring addresses the risk that GAN mode collapse may produce poor solutions.
  • The Gaussian sampling procedure generates a D-dimensional input for the GAN from a distribution estimated using real samples.
  • The generator output is restricted using the lower and upper boundaries of the decision space.The resulting vector x′ is the candidate solution generated by the GANs.

IV. EXPERIMENTAL STUDY

The experimental study evaluates GMOEA through training-method, overall-performance, and operator analyses against six multiobjective evolutionary algorithms. Tests cover ten IMF problems, including cases with up to 200 decision variables, using repeated runs and statistical comparisons.

  • The experiments examine GAN offspring quality under different training methods, overall GMOEA performance, and the GAN operator and hybrid strategy.
  • GMOEA is compared with six algorithms across ten IMF problems with up to 200 decision variables.The compared methods are NSGA-II, MOEA/D-DE, MOEA/D-CMA, IM-MOEA, GDE3, and SPEA2.
  • Each algorithm is run 20 times per test problem, and Wilcoxon rank-sum tests compare results at significance level 0.05.
  • The population size is 100 for two-objective instances and 105 for three-objective instances.
  • GMOEA uses fixed GAN training settings, including batch size 32 and 200 training iterations.
  • Function-evaluation termination limits increase from 5000 at 30 variables to 30000 at 200 variables.

B. Test Problems and Performance Indicators

The study evaluates ten IMF benchmark problems using IGD and HV, then compares offspring quality and training-loss trajectories for original and modified GANs. The modified GANs produce more diverse, better-converged offspring, including on problems with up to 200 decision variables.

  • Test problems: Ten IMF benchmark problems are used; IMF4, IMF8, and the remaining problems have three, three, and two objectives, respectively.The passage states that IMF4 and IMF8 are tri-objective, while the other selected problems have two objectives.
  • Performance indicators: IGD assesses convergence and distribution using distances from reference points on the Pareto front.The reference set contains relatively evenly distributed points, with a size closest to 10000.
  • Performance indicators: HV measures the area covered by a solution set relative to predefined objective-space reference points, capturing closeness and spread in one scalar.Higher HV indicates better performance, whereas lower IGD indicates better performance.
  • Model-training effectiveness: On tri-objective IMF4, modified GANs generate widely spread offspring with better convergence in most iterations, unlike original GANs concentrated near a smaller objective-space region.The comparison uses IMF4 because its Pareto set is complicated and difficult for existing MOEAs to maintain diversity.
  • Model-training effectiveness: On IMF7 with 200 decision variables, modified GANs generate better-converged, spreading offspring, whereas original GANs concentrate solutions mostly in the left corner.The comparison examines whether the training method remains effective in a high-dimensional decision space.
  • Model-training effectiveness: Across the comparisons, the proposed training method improves diversity maintenance and convergence, including problems with complicated Pareto sets and up to 200 decision variables.The training-loss trajectories are also examined during GMOEA evolution on IMF1 with 30 decision variables.

D. General Performance

GMOEA achieved the best overall IGD and HV performance across the IMF test problems and converged faster than the compared algorithms on most high-dimensional problems. Its hybrid GAN and genetic-operator strategy also outperformed the pure genetic and pure GAN variants on most test instances, though runtime was higher than standard IBEA.

  • Overall performance: GMOEA performed best overall on the ten IMF problems, outperforming model-free MOEAs and remaining competitive with MOEA/D-CMA and IM-MOEA.The comparison used IGD and HV across 40 IMF test instances.
  • Solution quality: GMOEA obtained the best-converged final non-dominated solutions on bi-objective IMF3 and tri-objective IMF8 with 200 decision variables.The plotted runs corresponded to the median IGD value.
  • Convergence speed: GMOEA converged faster than the other six algorithms on most IMF problems with 200 decision variables.The results support superiority in convergence speed on problems with up to 200 decision variables.
  • Runtime: GMOEA required about five times the runtime of IBEA in a Python comparison on three IMF problems with 30 decision variables.The authors note that the cross-implementation comparison with Matlab algorithms could be unfair.
  • Ablation study: The hybrid GMOEA and pure GAN operator significantly outperformed pure genetic operators on almost all ablation test instances, while GMOEA beat the pure GAN variant on most instances.The ablation compared GMOEA*, GMOEA−, and the original hybrid GMOEA.

V. CONCLUSION

The paper concludes that GMOEA uses GANs to generate offspring for multiobjective optimization with up to 200 decision variables. Its training method reuses real, fake, and generated data, while hybrid reproduction balances exploitation and exploration; experiments report superior performance on relatively high-dimensional problems, with broader generative models, many-objective settings, and real-world applications left for future work.

  • Conclusion: GMOEA is a GAN-driven multiobjective evolutionary algorithm designed for MOPs with up to 200 decision variables.The authors attribute its effectiveness to the learning and generative abilities of GANs.
  • Method: GMOEA classifies current candidate solutions into real and fake datasets so GAN training can consider training-data diversity and convergence.The real samples are high-quality candidates, while the remaining candidates are labeled fake.
  • Method: The proposed training method uses real, fake, and generator-produced data for discriminator training with 100 samples for two objectives and 105 for three objectives.The method is presented as using a relatively small amount of training data.
  • Results: Experiments compared GMOEA with six representative MOEAs, and statistical results demonstrated its superiority on MOPs with relatively high-dimensional decision variables.The compared algorithms were NSGA-II, MOEA/D-DE, MOEA/D-CMA, IM-MOEA, GDE3, and SPEA2.
  • Future work: The authors identify more efficient generative models, extensions beyond three objectives, and real-world applications as desirable future directions.These directions define the stated scope for further work.
Loading 1910.04966v2…