Architecture — BikeOptim

📐 Positionnement

Différences avec HABX

Le moteur BikeOptim s'inspire du papier HABX mais résout un problème fondamentalement différent. Comprendre ces écarts est crucial pour justifier nos choix d'architecture.

HABX — Meubles & Murs

Le papier HABX traite des modules rigides : meubles aux dimensions fixes, murs porteurs, cloisons. Les pièces ont des formes figées et le Constraint Programming (CP) gère le placement.

BikeOptim — Vélos & Circulation

BikeOptim traite des pièces déformables avec des contraintes continues : circulation, accessibilité, entraxes variables. Le constructeur remplace le CP pour le placement.

⚠️

Point clé : Là où HABX optimise un agencement discret de pièces rectangulaires, BikeOptim optimise un continuum de paramètres (profondeur, espacement, nombre de rangées) qui produisent un plan de stationnement vélo.

Conséquences architecturales

Pas de solveur CP → le constructeur déterministe produit la géométrie
Pas de grille discrète → les coordonnées sont continues en mètres
Pas de formes fixes → les emprises dépendent du système choisi et de l'entraxe
Objectifs multiples → le tri utilise NSGA-II (Pareto), pas un score unique

🧬 Encodage

Représentation à deux niveaux

L'optimiseur manipule un génome structurel compact. Le constructeur le décode en un phénotype complet évaluable.

🧬 Génome structurel

Le vecteur de décision manipulé par NSGA-II. Compact, il encode les choix structurants :

Gène	Type	Description
`cut`	float	Position de coupe le long du segment principal
`system_key`	enum	Système de stationnement choisi
`rows_along_s`	bool	Rangées parallèles au segment principal
`reverse`	bool	Inversion de la direction de placement
`depth_reverse`	bool	Inversion de la profondeur
`double_loaded`	bool	Bandes chargées des deux côtés
`reserve_corridor`	bool	Réservation d'un couloir central

🏗️ Phénotype

L'implantation complète produite par le constructeur à partir du génome :

Composant	Description
Emprises	Rectangles au sol de chaque emplacement vélo
Allées	Corridors de desserte entre les rangées
Circulation	Graphe de connectivité portes → vélos
Capacité	Nombre total de places et places accessibles
Coût	Somme des distances de circulation

💡

Le phénotype est déterministe : un même génome produit toujours le même plan.

Génome g → Constructeur(g) → Phénotype p → Fitness(p) → (f₁, f₂)

📦 Organisation

Modules cibles

Le moteur est découpé en 7 modules indépendants avec des responsabilités claires et des dépendances minimales.

Module	Responsabilité	Dépendances
`io`	Chargement JSON, dump Revit — import/export des données de pièces	`stdlib`
`core`	RoomModel, géométrie, analyse — modèle de salle et opérations géométriques	`shapely`, `numpy`
`catalog`	Systèmes de stationnement — catalogue des râteliers, resserres, arceaux	`stdlib`
`solve`	Constructeur, packing, zones — algorithmes de placement	`ortools`
`circulation`	Dijkstra, BFS, couloir — analyse d'accessibilité et coûts	`numpy`
`optimize`	NSGA-II, genome, phénotype — boucle d'optimisation multi-objectif	`random`
`viz`	Rendu matplotlib — visualisation des implantations	`matplotlib`

📌

Principe de conception : chaque module ne dépend que de ses voisins directs dans le pipeline. optimize appelle solve qui appelle core — jamais l'inverse.

# Arbre de dépendances simplifié optimize ├── solve │ ├── core │ │ ├── shapely │ │ └── numpy │ └── ortools ├── circulation │ └── numpy ├── catalog └── viz (optionnel) └── matplotlib

🎯 Objectifs

Objectifs de fitness

Le moteur optimise deux objectifs contradictoires simultanément, formant un front de Pareto.

f₁ — Capacité accessible

f₁ = −capacité_accessible

Maximiser le nombre de vélos accessibles depuis au moins une porte. Le signe négatif convertit la maximisation en minimisation pour NSGA-II.

f₂ — Coût de circulation

f₂ = coût_circulation

Minimiser la somme des distances de parcours entre les portes et les emplacements vélo.

Contraintes dures

chevauchements = 0 — Aucune emprise ne peut en chevaucher une autre.
reconnect = 0 — Tout vélo doit être relié au graphe de circulation.

🚫

Death penalty : un vélo inaccessible reçoit une pénalité infinie. Il est préférable d'avoir 28 vélos 100% accessibles que 35 vélos dont 10 sont injoignables.

🔧 Opérateurs

Opérateurs génétiques

NSGA-II utilise trois opérateurs pour explorer l'espace de solutions.

🔀 Mutation +

La mutation perturbe un individu existant de trois façons possibles :

Flip booléen — Inverse un gène booléen (ex: reverse, double_loaded)
Perturbation float — Ajoute un bruit gaussien au paramètre cut
Changement de système — Remplace system_key par un système aléatoire du catalogue

# Exemple de mutation def mutate(genome, rng): gene = rng.choice(genome.genes) if gene.type == "bool": gene.value = not gene.value elif gene.type == "float": gene.value += rng.gauss(0, 0.1) elif gene.type == "enum": gene.value = rng.choice(catalog.keys())

🔗 Crossover (croisement) +

Le croisement uniforme combine deux parents pour produire un enfant :

Pour chaque gène, on choisit aléatoirement le parent source (50/50)
Produit un enfant qui mélange les caractéristiques des deux parents
Conserve la structure du génome (types et bornes respectés)

enfant[i] = parent_A[i] si coin_flip() sinon parent_B[i]

🏆 Sélection +

La sélection par tournoi binaire avec tri non dominé :

Tri non dominé — Les individus sont classés en fronts de Pareto (F₁, F₂, …)
Crowding distance — Au sein d'un même front, on favorise les individus les plus isolés (diversité)
Tournoi binaire — Deux candidats sont tirés au sort, le meilleur (rang < ou crowding >) gagne

🔬

Le crowding distance empêche la convergence prématurée en préservant la diversité sur le front de Pareto.

⚡ Performance

Performance cible

Le moteur est conçu pour une utilisation interactive. Chaque évaluation doit être rapide.

<50ms / évaluation

200évaluations

~30secondes budget

⚡

Objectif : moins de 50 ms par évaluation du constructeur. Budget total : 200 évaluations × 30 secondes. Cela permet d'explorer le front de Pareto en temps interactif, sans que l'utilisateur n'attende.

Stratégies de performance

Constructeur déterministe — Pas de backtracking, une seule passe
Géométrie vectorisée — Opérations shapely/numpy en batch
Cache de systèmes — Les emprises pré-calculées sont réutilisées
Graphe de circulation léger — Dijkstra sur graphe creux, pas de grille
Filet jamais pire — Exact et glouton évalués en parallèle, on garde le meilleur

T_total = N_pop × N_gen × T_eval ≈ 50 × 4 × 50ms = 10s

← PrécédentUtilisation Suivant →FAQ