---
primary_layer: layer2
related_layers: []
page_type: concept
---

# EGO (Efficient Global Optimization)

## 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 {cite}`jones1998ego`. The concrete procedure is shown in the pseudocode below.

## Pseudocode

```{prf:algorithm} EGO
:label: alg-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

```{mermaid}
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 |

```python
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 {cite}`brochu2010tutorial`.
$\xi=0$ leans toward exploitation, and larger values lean toward exploration.

## Related

- [References](../references.md): Full bibliographic details for the source, and a list of sources for acquisition functions other than EI
- [SurrogateManager](../concepts/surrogate_modeling/surrogate_manager.md): Detailed usage of `GlobalSurrogateManager`
- [AcquisitionFunction](../concepts/surrogate_modeling/acquisition_functions.md): List of acquisition functions including `ExpectedImprovement`
- [Surrogate](../concepts/surrogate_modeling/surrogate.md): List of surrogate models including `SklearnGPRSurrogate`, and an explanation of the `sklearn` extra
- [OptimizationStrategy](../concepts/execution_and_evaluation/strategies.md): List of strategies including `IndividualBasedStrategy`'s `evaluation_ratio`