Metadata-Version: 2.4
Name: perm_pateda
Version: 0.1.0
Summary: Estimation of Distribution Algorithms for permutation-based optimization problems
Author-email: Roberto Santana <roberto.santana@ehu.eus>
License: MIT License
        
        Copyright (c) 2025 Roberto Santana
        
        Permission is hereby granted, free of charge, to any person obtaining a copy
        of this software and associated documentation files (the "Software"), to deal
        in the Software without restriction, including without limitation the rights
        to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
        copies of the Software, and to permit persons to whom the Software is
        furnished to do so, subject to the following conditions:
        
        The above copyright notice and this permission notice shall be included in all
        copies or substantial portions of the Software.
        
        THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
        IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
        FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
        AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
        LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
        OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
        SOFTWARE.
        
Project-URL: Homepage, https://github.com/rsantana-isg/pateda
Project-URL: Repository, https://github.com/rsantana-isg/pateda
Project-URL: Issues, https://github.com/rsantana-isg/pateda/issues
Keywords: estimation of distribution algorithms,EDA,evolutionary computation,permutations,Mallows model,generalized Mallows model,combinatorial optimization,TSP,QAP,LOP,PFSP
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: Topic :: Scientific/Engineering :: Artificial Intelligence
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.21
Requires-Dist: scipy>=1.7
Requires-Dist: pateda>=0.1.0
Provides-Extra: dev
Requires-Dist: pytest>=7; extra == "dev"
Requires-Dist: pytest-cov>=3; extra == "dev"
Requires-Dist: black>=22; extra == "dev"
Requires-Dist: mypy>=0.950; extra == "dev"
Requires-Dist: ruff>=0.1; extra == "dev"
Provides-Extra: docs
Requires-Dist: sphinx>=7; extra == "docs"
Requires-Dist: sphinx-rtd-theme>=1; extra == "docs"
Requires-Dist: myst-parser>=2; extra == "docs"
Dynamic: license-file

# perm_pateda

**Estimation of Distribution Algorithms (EDAs) for permutation-based combinatorial
optimization problems.**

`perm_pateda` is an independent, permutation-focused companion to
[`pateda`](../pateda). It contributes the model **learning** and **sampling**
methods that are specific to permutation spaces — histogram models and
distance-based **Mallows** / **Generalized Mallows** models — and reuses
`pateda` for everything common to all EDAs (the core EDA engine, selection,
replacement, statistics, and visualization utilities).

It is a Python port of the algorithms in **`perm_mateda`**
(Irurozki, Ceberio, Santamaria & Mendiburu, 2018,
*Algorithm 989: perm_mateda — A Matlab Toolbox of Estimation of Distribution
Algorithms for Permutation-based Combinatorial Optimization Problems*,
ACM TOMS 44(4), Article 47).

---

## Relationship to `pateda`

```
pateda  ─────────────────────────────►  perm_pateda
(core EDA engine, selection,            (permutation learning + sampling,
 replacement, statistics, viz,           Mallows / GMallows models,
 discrete & continuous EDAs)             histogram models, TSP/QAP/LOP)
```

`pateda` is a **dependency** of `perm_pateda`. All permutation-related code has
been removed from `pateda` and now lives here, so the two packages have a clean
separation of concerns:

| Concern | Package |
|---|---|
| Core EDA loop, components, models | `pateda` |
| Selection / replacement / statistics / visualization | `pateda` |
| Discrete & continuous EDAs (UMDA, EBNA, Gaussian, …) | `pateda` |
| Permutation distances (Kendall, Cayley, Ulam) | `perm_pateda` |
| Mallows & Generalized Mallows learning/sampling | `perm_pateda` |
| Edge / Node histogram models | `perm_pateda` |
| Permutation problems (TSP, QAP, LOP) | `perm_pateda` |

---

## Installation

`pateda` is an in-development package (not yet on PyPI), so install it first
from the local checkout, then install `perm_pateda`:

```bash
# from the repository root (…/github/pateda)
pip install -e packages/pateda
pip install -e packages/perm_pateda
```

For development tooling (pytest, ruff, …):

```bash
pip install -e "packages/perm_pateda[dev]"
```

Requires Python ≥ 3.9, `numpy`, `scipy`, and `pateda`.

---

## Quick start

```python
import numpy as np
from perm_pateda import MallowsKendallEDA
from perm_pateda.functions import create_random_lop

# A Linear Ordering Problem instance on 15 items
lop = create_random_lop(15, seed=0)

alg = MallowsKendallEDA(
    n_vars=15,
    fitness_func=lop,        # callable: permutation -> scalar (higher is better)
    pop_size=100,
    n_gen=50,
    selection_ratio=0.3,
    random_seed=0,
)
stats, _ = alg.run()
print("Best fitness:", stats.best_fitness_overall)
print("Best permutation:", stats.best_individual)
```

---

## Available algorithms

Plug-and-play wrappers (import from `perm_pateda`):

| Class | Model | Distance |
|---|---|---|
| `MallowsKendallEDA`   | Mallows               | Kendall's-τ |
| `MallowsCayleyEDA`    | Mallows               | Cayley |
| `GMallowsKendallEDA`  | Generalized Mallows   | Kendall's-τ |
| `GMallowsCayleyEDA`   | Generalized Mallows   | Cayley |
| `EHMEDA`              | Edge Histogram Model  | — |
| `NHMEDA`              | Node Histogram Model  | — |

See [`ROADMAP.md`](ROADMAP.md) for the planned additions (Mallows–Ulam,
`BestPermutation` consensus, the PFSP problem, and real-instance loaders) that
complete the feature set of the `perm_mateda` toolbox.

---

## Package layout

```
perm_pateda/
├── distances.py          # Kendall, Cayley, Ulam distances (+ helpers)
├── consensus.py          # central-permutation estimators (Borda, SetMedian)
├── learning/
│   ├── histogram.py      # LearnEHM, LearnNHM
│   └── mallows.py        # LearnMallows{Kendall,Cayley}, LearnGeneralizedMallows{Kendall,Cayley}
├── sampling/
│   ├── histogram.py      # SampleEHM, SampleNHM
│   └── mallows.py        # SampleMallows{Kendall,Cayley}, SampleGeneralizedMallows{Kendall,Cayley}
├── seeding/
│   └── permutation_init.py   # PermutationInit (random permutations)
├── functions/
│   ├── tsp.py            # Traveling Salesman Problem
│   ├── qap.py            # Quadratic Assignment Problem
│   └── lop.py            # Linear Ordering Problem
└── algorithms/
    └── permutation.py    # plug-and-play EDA wrappers
```

---

## Citation

If you use the distance-based permutation EDAs implemented here, please cite the
original toolbox:

> E. Irurozki, J. Ceberio, J. Santamaria, and A. Mendiburu (2018).
> *Algorithm 989: perm_mateda — A Matlab Toolbox of Estimation of Distribution
> Algorithms for Permutation-based Combinatorial Optimization Problems.*
> ACM Transactions on Mathematical Software, 44(4), Article 47.

## License

MIT — see [LICENSE](LICENSE).
