A high-performance, modular, and memory-optimized implementation of a Genetic Algorithm (GA) designed natively in MeTTa (Meta-Type Template) to solve the classic 0-1 Knapsack combinatorial optimization problem.

The 0-1 Knapsack problem involves selecting a subset of items with predefined weights and values to maximize the total value payload in a knapsack without exceeding its maximum weight capacity limit.

This project utilizes evolutionary computing principles—Tournament Selection, Single-Point Crossover, and Bit Mutation—implemented through space-efficient native MeTTa pattern matching. It is specifically optimized to prevent recursive stack accumulation and memory overflows (Not enough resources: memory) inside Prolog-backed interpreters like PeTTa.

The workspace is split into separate, highly decoupled logical files to ensure clean modularity:

• knapsack.metta: The data warehouse storing static item configurations and threshold constraints.
• operators.metta: The core execution engine containing structural fitness math, genetic variations, and selector rules.
• main.metta: The orchestration entry point that drives the evolution pipeline transformations line-by-line.

Defines available items using the layout structure (= (item id) (value weight)), alongside the maximum threshold constraint.

Handles tuple decomposition, inline mathematical payload calculations, single-point mid-splits, and elite parent tournament filters.

Drives reproductive pipelining states without recursive accumulation overhead to run completely stack-safe.

;; Target queries Execution !(max-weight) !(ultimate-winner) !(get-fitness (ultimate-winner))

---

## ⚡ Execution Instructions

1. Open your terminal workspace directory.
2. Navigate directly into your environment runtime folder:
   ```bash
   cd PeTTa

1. Run the compiler target cleanly:

   sh run.sh ../main.metta

true
15
(0 0 1 1 1 0)
85

• Tuple Substitution Pattern Matching: Transitioning from linear recursive Cons scanning lists over to explicitly sized (N1 N2 N3 ...) tuples eliminated repetitive list traversal operations.
• Flattening Scoped Let Blocks: Replacing Lisp-style sequential variable accumulation bindings (let*) with straightforward functional pipelines ensures the runtime interpreter drops historical variable trace assignments instantly, maintaining O(1) memory safety.