Evolutionary Computation Projects: Differential Evolution, Probabilistic Graphical Models, and KL Divergence

A collection of three projects developed for the Evolutionary Computation course, covering constrained optimization, probabilistic graphical models, and divergence analysis between multivariate Gaussian distributions.

---

Assignment 1 — Differential Evolution with Constraint Handling

Implementation of a SHADE-style Differential Evolution (DE) algorithm incorporating two constraint-handling strategies, evaluated on constrained optimization problems from the CEC benchmark suite.

Implemented Strategies

Strategy	Description
Feasibility Tournament	Prioritizes feasible solutions; among feasible candidates, selects the one with the best objective value
Adaptive Penalty Method	Penalizes infeasibility using a coefficient that increases as the optimization progresses

Technical Features

• current-to-pbest/1 mutation strategy with external archive
• SHADE boundary correction via bisection
• Decreasing tolerance for equality constraints (ε-decay)
• 30 independent runs per benchmark problem
• Automatic CSV export of experimental results

Running the Project

pip install numpy pandas
python Tarea1_Evolutivo_MaganaLuisa.py

Generated files:

• resultados_penalizacion_adaptable.csv
• resultados_torneo_factibilidad.csv

---

Assignment 2 — Probabilistic Graphical Models (MIMIC vs. Chow-Liu)

Implementation and comparison of two Estimation of Distribution Algorithms (EDAs) for binary variables.

Implemented Models

Model	Structure	Learning Algorithm
MIMIC	Linear chain	Greedy ordering based on entropy and consecutive mutual information
Dependency Tree	Maximum spanning tree	Chow-Liu algorithm (Kruskal's algorithm over mutual information)

Evaluation Metrics

• Sum of mutual information across model edges
• Estimated KL divergence between the true distribution and the learned model using Monte Carlo sampling

Benchmark Distributions

BD1

Linear chain:

0 → 1 → 2 → 3 → 4 → 5

BD2

Nonlinear tree with a branched dependency structure.

Running the Project

pip install numpy pandas
python Codigo_Tarea2_Evolutivo_MaganaLuisa.py --n 30000 --seed 42

---

Assignment 3 — KL Divergence Between Multivariate Gaussian Models

Comparison of three probabilistic models over 10-dimensional Gaussian data, evaluating how accurately they approximate the target distribution:

[ P = \mathcal{N}(0, \Sigma) ]

Compared Models

Model	Description
Dependency Tree (Chow-Liu)	Maximum spanning tree constructed from correlation coefficients
Independence Model	Diagonal covariance approximation that ignores dependencies
Chain Model (MIMIC)	Greedy variable ordering based on absolute correlations

Evaluation Metrics

• Analytical KL divergence (D_{KL}(P \parallel Q)) between multivariate Gaussian distributions
• Conditional sampling using Breadth-First Search (BFS) traversal from the root of the tree or chain structure

Running the Project

pip install numpy pandas
python Tarea3_MaganaLuisa.py

Generated files:

• kl_summary.csv
• dependency_tree_edges.csv
• chain_order.csv

---

Common Technologies

• Python 3
• numpy
• pandas
• External module: de_restricted (required for Assignment 1 and must be located in the same directory)

---

Academic Context

These projects explore several fundamental topics in evolutionary computation and probabilistic modeling:

• Constrained evolutionary optimization
• Differential Evolution and adaptive parameter control
• Estimation of Distribution Algorithms (EDAs)
• Probabilistic graphical models
• Mutual information and dependency learning
• Kullback–Leibler divergence
• Approximation of high-dimensional probability distributions

Together, they provide practical implementations of optimization and probabilistic learning techniques commonly used in evolutionary computation, machine learning, and statistical modeling research.