Simulated Annealing for Covering Arrays

A Python implementation of Simulated Annealing (SA) to generate optimal Covering Arrays for combinatorial software testing. The goal is to minimize the number of test cases needed to cover all pairwise parameter combinations.

---

🧪 What Are Covering Arrays?

A Covering Array CA(N; t, k, v) is a combinatorial test matrix where:

• N = number of test cases (rows) — minimize this
• t = strength (coverage level) — pairwise = t=2
• k = number of parameters
• v = number of values per parameter

For a system with 3 parameters (OS, Browser, Database) each with 2 values, there are 2³ = 8 possible combinations. A covering array ensures all pairwise combinations appear at least once — with far fewer than 8 test cases.

Why it matters: Exhaustive testing of all combinations is exponential. Covering arrays reduce test suite size while maintaining fault detection capability.

---

🔬 Experiment Setup

System under test: 3-parameter software configuration

• Operating System: Linux, Windows
• Web Browser: Firefox, Chrome
• Database: MySQL, Oracle

Algorithm parameters:

• Strength: t = 2 (all pairwise combinations covered)
• Values per parameter: v = 2
• Variable parameters: k = 5, 6, 7
• Initial Temperature: T = k
• Cooling Rate: 0.99 (geometric decay)
• Total runs: 90 (30 per k value)

---

📊 Results

k	N (rows)	Runs	Max Iterations	Freeze Limit
5	13	30	1000	10
6	15	30	1000	10
7	18	30	1000	10

Each run outputs: the generated covering array, iteration count, and stopping criterion (solution or frozen).

Key observations:

• SA successfully generated covering arrays for most test cases
• Higher k values required longer execution to find optimal solutions
• Increasing N marginally improved results when algorithm froze
• Smaller k values achieved higher convergence rates

---

🧠 Algorithm — Simulated Annealing

SA is a metaheuristic inspired by the annealing process in metallurgy. It escapes local optima by occasionally accepting worse solutions — controlled by a temperature parameter.

Formula for N (rows required):

N = 2.5 × k

Steps:

1. Initialization — generate random N×k binary matrix
2. Objective function — count missing pairwise combinations across all N×t subarrays
3. Neighborhood exploration — randomly select column j, flip all bits in that column to generate N neighbors
4. Acceptance — accept if improvement; otherwise accept with probability e^(-ΔE/T)
5. Cooling — T = T × 0.99 after each iteration
6. Termination — stop when optimal found, frozen (no improvement after φ consecutive steps), or T < threshold

Stopping criteria tracked:

• solution — optimal covering array found
• frozen — no improvement after freeze limit reached

---

🔧 Tech Stack

• Language: Python 3
• Algorithm: Simulated Annealing (metaheuristic optimization)
• Application: Combinatorial software testing

---

🚀 How to Run

git clone https://github.com/yukta31/simulated-annealing-covering-arrays.git
cd simulated-annealing-covering-arrays
python covering_array_sa.py

---

📁 Files

File	Description
covering_array_sa.py	Full Python implementation of SA algorithm
project_report.pdf	Complete analysis — methodology, experiments, results

---

🔮 Future Work

• Adaptive cooling — dynamically adjust temperature decay
• Hybrid approaches — combine SA with genetic algorithms
• Scalability testing — evaluate on larger parameter spaces (k > 10)

---

👩‍💻 Author

Yukta Batra — MS Computer Science, George Mason University

Portfolio · LinkedIn · GitHub