{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Permutation Crossover Laboratory\n",
    "Compare **ERX, CX, PMX, MX, OBX, PBX, UOX, OX, and LOX** under the same GA, seed, population, mutation, and evaluation budget. The central question is not simply *which crossover wins?* but *which representation matches the problem?*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run once in a clean notebook environment.\n",
    "%pip install -q git+https://github.com/WarinWatt/COINCIDENCE_algorithms_suite.git@agent/publish-coin-library pandas matplotlib"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "from pymoo.algorithms.soo.nonconvex.ga import GA\n",
    "from pymoo.core.problem import Problem\n",
    "from pymoo.optimize import minimize\n",
    "from pymoo.operators.crossover.ox import OrderCrossover\n",
    "from pymoo.operators.crossover.erx import EdgeRecombinationCrossover\n",
    "from pymoo.operators.mutation.inversion import InversionMutation\n",
    "from pymoo.operators.sampling.rnd import PermutationRandomSampling\n",
    "from coin.adapters.pymoo.permutation_crossovers import PermutationCrossover\n",
    "\n",
    "OPERATORS = ['erx', 'cx', 'pmx', 'mx', 'obx', 'pbx', 'uox', 'ox', 'lox']\n",
    "REPRESENTATION = {\n",
    " 'erx':'adjacent edges', 'cx':'absolute positions / cycles',\n",
    " 'pmx':'position mapping', 'mx':'one-point prefix + relative order',\n",
    " 'obx':'order among selected jobs', 'pbx':'fixed positions + remaining order',\n",
    " 'uox':'uniform positions + remaining order', 'ox':'segment + cyclic order',\n",
    " 'lox':'segment + linear order'}\n",
    "pd.Series(REPRESENTATION, name='transmitted structure').to_frame()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class PermutationFixture(Problem):\n",
    "    def __init__(self, n, evaluate):\n",
    "        super().__init__(n_var=n, n_obj=1, xl=0, xu=n-1, vtype=int)\n",
    "        self.evaluate_permutation = evaluate\n",
    "    def _evaluate(self, X, out, *args, **kwargs):\n",
    "        out['F'] = np.asarray([self.evaluate_permutation(p) for p in X])[:, None]\n",
    "\n",
    "def crossover(name, probability=.9):\n",
    "    if name == 'ox': return OrderCrossover(prob=probability)\n",
    "    if name == 'erx': return EdgeRecombinationCrossover(prob=probability)\n",
    "    return PermutationCrossover(name, prob=probability)\n",
    "\n",
    "def run_ga(name, fixture, seed=42, population=100, generations=400):\n",
    "    algorithm = GA(pop_size=population, sampling=PermutationRandomSampling(),\n",
    "        crossover=crossover(name), mutation=InversionMutation(prob=.2),\n",
    "        eliminate_duplicates=True)\n",
    "    started = time.perf_counter()\n",
    "    result = minimize(fixture, algorithm, ('n_gen', generations), seed=seed,\n",
    "                      save_history=True, verbose=False)\n",
    "    return {'operator':name.upper(), 'best':float(result.F[0]),\n",
    "            'runtime_s':time.perf_counter()-started,\n",
    "            'history':[float(s.pop.get('F').min()) for s in result.history]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def classic_problem(kind, n=20, seed=42):\n",
    "    rng = np.random.default_rng(seed)\n",
    "    if kind == 'TSP':\n",
    "        xy = rng.random((n,2))\n",
    "        return PermutationFixture(n, lambda p: sum(np.linalg.norm(xy[p[i]]-xy[p[(i+1)%n]]) for i in range(n)))\n",
    "    if kind == 'Flow Shop':\n",
    "        times = rng.integers(1,100,(n,5))\n",
    "        def makespan(p):\n",
    "            c=np.zeros(5);\n",
    "            for job in p:\n",
    "                c[0]+=times[job,0]\n",
    "                for m in range(1,5): c[m]=max(c[m],c[m-1])+times[job,m]\n",
    "            return c[-1]\n",
    "        return PermutationFixture(n,makespan)\n",
    "    if kind == 'QAP':\n",
    "        flow=rng.integers(0,20,(n,n)); distance=rng.integers(0,30,(n,n))\n",
    "        flow=(flow+flow.T)//2; distance=(distance+distance.T)//2\n",
    "        return PermutationFixture(n,lambda p: float((flow*distance[np.ix_(p,p)]).sum()))\n",
    "    if kind == 'N-Queens':\n",
    "        return PermutationFixture(n,lambda p: sum(abs(i-j)==abs(int(p[i])-int(p[j])) for i in range(n) for j in range(i+1,n)))\n",
    "    if kind == 'Linear Ordering':\n",
    "        weight=rng.integers(0,20,(n,n)); weight=np.triu(weight,1)\n",
    "        def violations(p):\n",
    "            pos=np.argsort(p); return sum(weight[i,j] for i in range(n) for j in range(i+1,n) if pos[i]>pos[j])\n",
    "        return PermutationFixture(n,violations)\n",
    "    side=int(np.ceil(np.sqrt(n))); xy=np.array([(i%side,i//side) for i in range(n)])\n",
    "    def knight_loss(p):\n",
    "        delta=np.abs(np.diff(xy[p],axis=0)); return int(sum(not tuple(d) in {(1,2),(2,1)} for d in delta))\n",
    "    return PermutationFixture(n,knight_loss)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Teaching-sized comparison. Increase to population=100, generations=400 for the measured protocol.\n",
    "problem_names=['TSP','Flow Shop','QAP','N-Queens','Linear Ordering',\"Knight's Tour\"]\n",
    "records=[]\n",
    "for problem_name in problem_names:\n",
    "    fixture=classic_problem(problem_name,n=16,seed=42)\n",
    "    for operator in OPERATORS:\n",
    "        records.append({'problem':problem_name, **run_ga(operator,fixture,population=50,generations=100)})\n",
    "results=pd.DataFrame(records)\n",
    "results['rank']=results.groupby('problem')['best'].rank(method='min')\n",
    "results.sort_values(['problem','rank'])[['problem','operator','best','rank','runtime_s']]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pivot=results.pivot(index='operator',columns='problem',values='rank')\n",
    "ax=pivot.plot.bar(figsize=(13,5),width=.85)\n",
    "ax.set_ylabel('Rank (lower is better)'); ax.set_title('Crossover × problem structure')\n",
    "plt.tight_layout(); plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises\n",
    "1. Run at least 5 independent seeds and report paired ranks—not only the best run.\n",
    "2. Compare OX and LOX: when does cyclic filling help a path that is not cyclic?\n",
    "3. Compare PBX and UOX: does fixed inheritance reduce variance?\n",
    "4. Plot convergence. ERX may still improve after order-based methods have stopped.\n",
    "5. Replace synthetic fixtures with TSPLIB, QAPLIB, Taillard PFSP, or another declared benchmark."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"},
  "language_info": {"name": "python", "version": "3.10"}
 },
 "nbformat": 4,
 "nbformat_minor": 5
}