MOEAD

MOEAD#

Background#

MOEA/D (Multi-Objective Evolutionary Algorithm based on Decomposition) is a classical multi-objective optimization algorithm that decomposes a multi-objective problem into a set of single-objective subproblems using scalarizing functions. Originally proposed by Zhang and Li in 2007, MOEA/D has become one of the most influential multi-objective evolutionary algorithms.

In the context of LLM4AD, MOEAD adapts the MOEA/D framework for automatic algorithm design. Instead of using traditional genetic operators, it employs Large Language Models as the variation operator to generate new candidate algorithms. Each subproblem in the decomposition is associated with a weight vector representing different trade-offs between objectives, and the LLM generates new heuristics based on the solutions stored in neighboring subproblems.

Reference paper:

  • Shunyu Yao, Fei Liu, Xi Lin, Zhichao Lu, Zhenkun Wang, and Qingfu Zhang. “Multi-objective evolution of heuristic using large language model.” In Proceedings of the AAAI Conference on Artificial Intelligence, 2025.

Algorithm Overview#

The MOEAD method in LLM4AD combines the decomposition-based multi-objective optimization framework with LLM-based heuristic generation. The key components are:

  1. Decomposition: The population is organized according to weight vectors that represent different Pareto-optimal regions. Each weight vector defines a subproblem with a scalarizing function (Tchebycheff approach).

  2. Evolutionary Operators: Four LLM-based operators are used: - I1 (Initialization): Generate new heuristics from scratch based on task description - E1 (Crossover - Different): Generate a new heuristic completely different from parent heuristics - E2 (Crossover - Inspired): Generate a new heuristic inspired by the common backbone of parent heuristics - M1 (Mutation): Modify an existing heuristic to create a new variant - M2 (Parameter Tuning): Adjust parameters of an existing heuristic

  3. Selection: Uses weight vector-based selection - individuals are selected based on their compatibility with the subproblem’s weight vector using the Tchebycheff scalarizing function.

  4. Update Strategy: When a new solution is generated, it updates its neighboring subproblems if it improves their objective values.

Pseudocode#

Input: LLM, Evaluation, Population Size N, Max Generations G, Max Samples M
Output: Population of evolved heuristics

// Initialize
Initialize weight vectors W = {w1, w2, ..., wN}
Initialize population P = empty

// Initialize population using I1 operator
while |P| < N and samples < M:
    prompt = generate_init_prompt(task_description)
    h = LLM.generate(prompt)           // I1 operator
    score = evaluate(h)
    P.add(h)
    register_to_profiler(h)

// Evolution
while continue_sampling(G, M):
    for each weight vector wi in W:
        // Select parents based on weight vector
        parents = select_parents(P, wi, selection_num)

        // E1: Crossover (different)
        if use_e1_operator:
            prompt = generate_crossover_prompt(parents, task)
            h = LLM.generate(prompt)
            score = evaluate(h)
            P.update_with_new_solution(h, wi)

        // E2: Crossover (inspired)
        if use_e2_operator:
            prompt = generate_inspired_prompt(parents, task)
            h = LLM.generate(prompt)
            score = evaluate(h)
            P.update_with_new_solution(h, wi)

        // M1: Mutation
        if use_m1_operator:
            parent = select_one(P, wi)
            prompt = generate_mutation_prompt(parent, task)
            h = LLM.generate(prompt)
            score = evaluate(h)
            P.update_with_new_solution(h, wi)

        // M2: Parameter tuning
        if use_m2_operator:
            parent = select_one(P, wi)
            prompt = generate_param_tuning_prompt(parent, task)
            h = LLM.generate(prompt)
            score = evaluate(h)
            P.update_with_new_solution(h, wi)

return P

Usage#

To use the MOEAD class, initialize it with the required parameters and call the run method to start the evolutionary optimization process.

Constructor#

class MOEAD#

Parameters

  • llm (LLM): An instance of llm4ad.base.LLM for querying the LLM.

  • evaluation (Evaluation): An instance of llm4ad.base.Evaluation to calculate scores of generated functions.

  • profiler (MOEADProfiler, optional): An instance of llm4ad.method.moead.MOEADProfiler. Pass None if profiling is not needed. Defaults to None.

  • max_generations (int | None, optional): Maximum number of generations to evolve. Defaults to 10.

  • max_sample_nums (int | None, optional): Maximum number of functions to evaluate. Defaults to 100.

  • pop_size (int, optional): Population size. Defaults to 20.

  • selection_num (int, optional): Number of selected individuals for crossover. Defaults to 5.

  • use_e2_operator (bool, optional): Whether to use the E2 evolutionary operator (crossover inspired). Defaults to True.

  • use_m1_operator (bool, optional): Whether to use the M1 evolutionary operator (mutation). Defaults to True.

  • use_m2_operator (bool, optional): Whether to use the M2 evolutionary operator (parameter tuning). Defaults to True.

  • num_samplers (int, optional): Number of sampler threads. Defaults to 1.

  • num_evaluators (int, optional): Number of evaluator threads. Defaults to 1.

  • num_objs (int, optional): Number of objectives. Defaults to 2.

  • resume_mode (bool, optional): If True, skips initial evaluation and initialization. Defaults to False.

  • initial_sample_num (int | None, optional): Initial sample count. Defaults to None.

  • debug_mode (bool, optional): If True, prints detailed information. Defaults to False.

  • multi_thread_or_process_eval (str, optional): Use ‘thread’ or ‘process’ for evaluation. Defaults to ‘thread’.

  • kwargs: Additional arguments passed to llm4ad.base.SecureEvaluator.

Methods#

run()#

Starts the MOEA/D optimization process. If resume_mode is False, initializes the population before evolution.

The run method performs the following steps:

  1. If resume_mode is False: - Initialize population using I1 operator (generate from task description) - Ensure at least selection_num valid individuals exist

  2. Execute evolutionary process using E1, E2, M1, M2 operators

  3. Return the final population

Private Methods#

_sample_evaluate_register(prompt)#

Samples a function using the given prompt, evaluates it, and registers it to the population.

Parameters:

  • prompt (str): The prompt to send to the LLM

_continue_sample() → bool#

Checks if sampling should continue based on generation and sample count limits.

Returns:

  • bool: True if sampling should continue, False otherwise

_thread_do_evolutionary_operator()#

Thread worker for performing evolutionary operations. Each thread processes operators based on weight vectors.

_thread_init_population()#

Thread worker for initializing the population using the I1 operator.

_init_population()#

Initializes the population using multiple threads.

_do_sample()#

Performs the evolutionary sampling process using multiple threads.

Attributes#

  • _template_program_str (str): The template program string.

  • _task_description_str (str): The task description string.

  • _num_objs (int): Number of objectives.

  • _max_generations (int | None): Maximum generations.

  • _max_sample_nums (int | None): Maximum samples.

  • _pop_size (int): Population size.

  • _selection_num (int): Selection number for crossover.

  • _use_e2_operator (bool): E2 operator flag.

  • _use_m1_operator (bool): M1 operator flag.

  • _use_m2_operator (bool): M2 operator flag.

  • _num_samplers (int): Number of samplers.

  • _num_evaluators (int): Number of evaluators.

  • _resume_mode (bool): Resume mode flag.

  • _debug_mode (bool): Debug mode flag.

  • _function_to_evolve (Function): Function being evolved.

  • _function_to_evolve_name (str): Name of function being evolved.

  • _template_program (Program): Template program instance.

  • _population (Population): Population instance.

  • _sampler (MOEADSampler): Sampler instance.

  • _evaluator (SecureEvaluator): Evaluator instance.

  • _profiler (MOEADProfiler): Profiler instance.

  • _tot_sample_nums (int): Total number of samples evaluated.

  • _evaluation_executor (concurrent.futures.Executor): Executor for parallel evaluation.

Example#

from llm4ad.method import MOEAD
from llm4ad.base import LLM, Evaluation
from llm4ad.method.moead import MOEADProfiler

# Define task
task_description = "Design a heuristic for the bin packing problem that minimizes the number of bins used."

template_program = '''
def bin_packing_heuristic(items, bin_capacity):
    """
    A heuristic for the bin packing problem.

    Args:
        items: List of item weights
        bin_capacity: Maximum capacity of each bin

    Returns:
        List of bins, where each bin is a list of item indices
    """
    # TODO: Implement your heuristic here
    bins = []
    return bins
'''

# Initialize LLM (e.g., OpenAI GPT-4)
llm = LLM(
    model_name='gpt-4',
    api_key='your-api-key'
)

# Define evaluation
evaluation = Evaluation(
    task_description=task_description,
    template_program=template_program,
    num_test_cases=100,
    objective_functions=['efficiency', 'simplicity']
)

# Initialize profiler
profiler = Profiler(
    log_dir='./logs/moead',
    save_frequency=10
)

# Create MOEAD optimizer
optimizer = MOEAD(
    llm=llm,
    evaluation=evaluation,
    profiler=profiler,
    max_generations=20,
    max_sample_nums=200,
    pop_size=20,
    num_samplers=2,
    num_evaluators=4
)

# Run optimization
result = optimizer.run()

# Get best solutions
best_solutions = result.get_pareto_front()

Exceptions#

  • RuntimeError: Raised if the initial population cannot be properly initialized (less than selection_num valid individuals).

  • ValueError: Raised if invalid parameters are provided (e.g., invalid multi_thread_or_process_eval value).

  • AssertionError: Raised if the multi_thread_or_process_eval parameter is neither ‘thread’ nor ‘process’.

References#

  1. Zhang, Q., & Li, H. (2007). MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on evolutionary computation, 11(6), 712-731.

  2. Shunyu Yao, Fei Liu, Xi Lin, Zhichao Lu, Zhenkun Wang, and Qingfu Zhang. “Multi-objective evolution of heuristic using large language model.” In Proceedings of the AAAI Conference on Artificial Intelligence, 2025.

  3. Fei Liu, Rui Zhang, Zhuoliang Xie, Rui Sun, Kai Li, Xi Lin, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang, “LLM4AD: A Platform for Algorithm Design with Large Language Model,” arXiv preprint arXiv:2412.17287 (2024).