Building an Experiment with MEGA

Experimenting with MEGA: A Tutorial on Mutable Encoding Genetic Algorithms

MEGA (Mutable Encoding Genetic Algorithm) offers a unique approach to evolutionary computation by allowing the encoding of solutions to evolve alongside the solutions themselves. In this tutorial, we’ll walk through creating an experiment with MEGA and explore its capabilities.

Prerequisites

  • The only requirement is an installation of the MEGA framework by following the instructions on the MEGA Git Repo.

Overview of the Framework

This GA framework works with a highly flexible genome representation. It uses an Encoding Manager to handle “genes,” encodings, captured segments, and delimiters (Start and End). It supports complex mutations, crossover, and logging.

Key features include:

  • Dynamic encoding evolution alongside solutions
  • Pattern capture and reuse capabilities
  • Flexible genome length
  • Support for nested genetic structures

Creating a Basic Experiment

Let’s create an experiment to solve a classic optimization problem: maximizing the number of consecutive ones at the start of a binary string (the LeadingOnes problem). This will demonstrate MEGA’s core features while remaining easy to understand.

import random
from M_E_GA import M_E_GA_Base
from M_E_GA_fitness_funcs import LeadingOnesFitness

# Set global parameters
MAX_LENGTH = 300
GLOBAL_SEED = None
random.seed(GLOBAL_SEED)

# Track the best organism found
best_organism = {
    "genome": None,
    "fitness": float('-inf')
}

# Callback function to update best organism
def update_best_organism(current_genome, current_fitness, verbose=False):
    global best_organism
    if current_fitness > best_organism["fitness"]:
        best_organism["genome"] = current_genome
        best_organism["fitness"] = current_fitness
        if verbose:
            print(f"New best organism found with fitness {current_fitness}")

# Initialize fitness function
fitness_function = LeadingOnesFitness(
    max_length=MAX_LENGTH, 
    update_best_func=update_best_organism
)
genes = fitness_function.genes

Configuration Parameters

The heart of any MEGA experiment lies in its configuration. Here’s a detailed breakdown of the key parameters:

config = {
    # Mutation Parameters
    'mutation_prob': 0.10,        # Base mutation probability
    'delimited_mutation_prob': 0.08,  # Probability of mutating within delimiters
    'open_mutation_prob': 0.002,  # Probability of opening captured segments
    'capture_mutation_prob': 0.009,  # Probability of capturing new segments
    'delimiter_insert_prob': 0.01,  # Probability of inserting new delimiters
    
    # Crossover and Selection
    'crossover_prob': 0.90,       # Probability of crossover occurring
    'elitism_ratio': 0.7,         # Proportion of best individuals to keep
    'base_gene_prob': 0.44,       # Probability of selecting base genes
    'capture_gene_prob': 0.04,    # Probability of using captured segments
    
    # Population Parameters
    'max_individual_length': 90,   # Maximum length of an individual
    'population_size': 700,       # Size of the population
    'num_parents': 100,           # Number of parents for next generation
    'max_generations': 900,       # Maximum number of generations
    
    # Additional Features
    'delimiters': False,          # Whether to use delimiter markers
    'delimiter_space': 2,         # Minimum space between delimiters
    
    # Logging Options
    'logging': False,             # Enable general logging
    'generation_logging': False,  # Log generation statistics
    'mutation_logging': False,    # Log mutation operations
    'crossover_logging': False,   # Log crossover operations
    'individual_logging': False,  # Log individual details
    
    'seed': GLOBAL_SEED          # Random seed for reproducibility
}

Running the Experiment

With our configuration set up, we can initialize and run the genetic algorithm:

# Initialize the GA
ga = M_E_GA_Base(
    genes, 
    lambda ind, ga_instance: fitness_function.compute(ind, ga_instance), 
    **config
)

# Run the algorithm
ga.run_algorithm()

# Extract and analyze results
best_genome = best_organism["genome"]
best_fitness = best_organism["fitness"]
best_solution_decoded = ga.decode_organism(best_genome, format=True)

# Print results
print('Length of best solution:', len(best_solution_decoded))
print(f"Best Solution (Decoded): {best_solution_decoded}")
print(f"Fitness: {best_fitness}")
print('Length of best genome:', len(best_organism["genome"]))
print(f"Best Genome (Encoded): {best_genome}")

Taking It Further

MEGA’s flexibility allows for much more sophisticated experiments. Here are some advanced directions you might explore:

  1. Custom Fitness Functions: Create problem-specific fitness functions by subclassing the base fitness class and implementing custom evaluation logic.
  2. Dynamic Parameter Adjustment: Implement adaptive parameter control by monitoring the population’s diversity and adjusting parameters like mutation rates accordingly.
  3. Multi-objective Optimization: Extend the fitness function to handle multiple objectives, using MEGA’s encoding capabilities to evolve solutions that balance different goals.
  4. Complex Encodings: Experiment with different gene sets and encoding schemes, such as:
    • Real-valued parameters
    • Tree-like structures
    • Graph representations
    • Mixed-type encodings
  5. Hierarchical Evolution: Use MEGA’s nested structure capability to evolve hierarchical solutions, where higher-level patterns emerge from combinations of lower-level patterns.
  6. Coevolution: Set up experiments where multiple populations evolve simultaneously, interacting through their fitness evaluations.

Best Practices

  • Start with simple experiments to understand the system’s behavior
  • Monitor the evolution of both solutions and their encodings
  • Adjust parameters based on observed results
  • Document unexpected or interesting emergent behaviors

Conclusion

MEGA provides a powerful framework for evolutionary computation that goes beyond traditional genetic algorithms. By allowing the encoding itself to evolve, it can discover and preserve beneficial patterns in solutions, potentially leading to more efficient and effective optimization.

The example provided here is just a starting point. The true power of MEGA lies in its flexibility and adaptability to a wide range of problems. Whether you’re working on optimization, design, or discovery problems, MEGA’s mutable encoding approach offers new possibilities for evolutionary computation.