EGO (Efficient Global Optimization)#

Layer 2: Compose

Overview#

EGO is a sequential optimization method for expensive-to-evaluate objective functions, combining a surrogate model built from Gaussian Process (GP) regression with the Expected Improvement (EI) acquisition function.

A GP’s predictive variance grows larger in regions farther from the training data. Because EI is a scalar value computed from both this predictive mean and predictive variance, it naturally covers both “regions that look promising” and “regions with high predictive uncertainty,” balancing exploration and exploitation.

The source is [24]. The concrete procedure is shown in the pseudocode below.

Pseudocode#

Algorithm 1 (EGO)

Inputs objective function \(f\), search domain, initial sample count \(n_0\), evaluation budget \(N\) Output best solution \(x^*\)

  1. Sample an initial population of \(n_0\) points, evaluate them with the true function \(f\), and add them to the archive

  2. Fit a GP to the entire archive, obtaining the predictive mean \(\mu(x)\) and predictive standard deviation \(\sigma(x)\) at any point

  3. Find the point \(x^*\) that maximizes the Expected Improvement \(\mathrm{EI}(x) = (f_{\min} - \mu(x) - \xi)\,\Phi(z) + \sigma(x)\,\phi(z)\) (where \(z = (f_{\min} - \mu(x) - \xi) / \sigma(x)\))

  4. Evaluate \(x^*\) with the true function and add it to the archive

  5. Return to step 2 until the evaluation budget \(N\) is reached

Flowchart#

        flowchart TD
    INIT["Initializer<br/>Sample initial population<br/>via LHS etc. → true evaluation<br/>(L1)"] --> ASK
    subgraph GEN["One generation (IndividualBasedStrategy.step)"]
        direction TB
        ASK["GA.ask()<br/>Generate candidates"] --> SCORE["SurrogateManager<br/>Fit GP (L2)<br/>→ Score with EI (L3)"]
        SCORE --> SORT["Select top<br/>evaluation_ratio fraction by EI<br/>(approximates argmax EI)"]
        SORT --> EVAL["True evaluation →<br/>add to archive<br/>(L4)"]
        EVAL --> TELL["GA.tell()<br/>Update population"]
    end
    GEN --> TERM{"Evaluation budget N<br/>reached?"}
    TERM -- "Not yet (L5)" --> ASK
    TERM -- "Reached" --> RESULT(["Best solution x*"])

Configuration in saealib#

Role

saealib implementation

Corresponding step

Search algorithm

GA (the specific combination of crossover, mutation, and selection is not part of EGO’s definition)

L3

Surrogate model

SklearnGPRSurrogate (GP regression; requires the sklearn extra)

L2

Acquisition function

ExpectedImprovement

L3

Surrogate management

GlobalSurrogateManager (fits the GP over the entire archive)

L2-3

Evaluation strategy

IndividualBasedStrategy (truly evaluates only the individuals with the top EI scores)

L3-4

 
import numpy as np
from saealib import (
    GA,
    Optimizer,
    Problem,
    IndividualBasedStrategy,
    SklearnGPRSurrogate,
    ExpectedImprovement,
)
from saealib.operators.crossover import CrossoverBLXAlpha
from saealib.operators.mutation import MutationUniform
from saealib.operators.selection import SequentialSelection, TruncationSelection
from saealib.surrogate import GlobalSurrogateManager
from saealib.termination import Termination, max_fe


def sphere(x: np.ndarray) -> float:
    return np.sum(x**2)


problem = Problem(sphere, dim=5, lb=[-5] * 5, ub=[5] * 5, n_obj=1, direction=[-1])

algorithm = GA(
    CrossoverBLXAlpha(prob=0.7, alpha=0.4),
    MutationUniform(prob_var=0.3),
    SequentialSelection(),
    TruncationSelection(),
)
surrogate_manager = GlobalSurrogateManager(SklearnGPRSurrogate())
strategy = IndividualBasedStrategy(evaluation_ratio=0.2)

opt = (
    Optimizer(problem)
    .set_algorithm(algorithm)
    .set_surrogate_manager(surrogate_manager)
    .set_acquisition(ExpectedImprovement())
    .set_strategy(strategy)
    .set_termination(Termination(max_fe(200)))
)
ctx = opt.run()

Differences from the source#

The original EGO finds the acquisition-function maximizer one point at a time, whereas saealib approximates argmax EI by selecting the highest-EI candidates from the pool generated by GA. IndividualBasedStrategy.evaluation_ratio also allows several selected candidates to receive true evaluations together. The crossover, mutation, parent-selection, and environmental-selection combination in the example is an saealib configuration choice, not part of the EGO definition.

Parameters and variants#

ξ (exploration–exploitation trade-off): Adjusted via ExpectedImprovement(xi=...). The default is 0.01, a practical heuristic rather than a value prescribed by the original EGO formulation. Brochu et al. (2010) discuss prior experimental use of this value [36]. \(\xi=0\) leans toward exploitation, and larger values lean toward exploration.