Modélisation des

réseaux avec

NetLogo

Alvaro GilM.A. ÉconomieÉtudiant M.Sc. Génie Industrielalvaro.gil@polymtl.ca

Jean-Marc Frayret, Ph.D.Professeur agrégéÉcole Polytechnique de Montréaljean-marc.frayret@polymtl.ca

Le 13 mars 2012

Introduction Fréquemment, on se trouve des modèles dans lesquels

l’utilisation des réseaux est indispensable

NetLogo a la possibilité de créer et manipuler des réseaux.

NetLogo permet aussi d’utiliser certains attributs des systèmes d’information géographique pour augmenter la puissance de modélisation.

Il existe aussi d’autres logiciels dédiés aux réseaux. Il faut bien les considérer si le problème à modéliser est très complexe et en conséquence, on devrait plutôt utiliser un logiciel spécialisé.

Cette présentation est sur certains commandes et modèles de base pour la simulation à base d’agents avec réseaux, qui peuvent vous aider dans le cadre de vos projets finaux.

2

Notions de base

La création des réseaux en NetLogo est fait à partir des liens

ou «links» entre tortues ou «turtles».

Ici, les liens sont les arêtes ou arcs et les tortues sont les

sommets ou nœuds.

La fonction de base pour la création d’un lien est CREATE-

LINK. Voici un exemple (copie et collé le code dans la ligne

de commande en NetLogo sans les intra lignes)ca

crt 5

ask turtles [setxy random-xcor random-ycor

create-links-with other turtles]

Ceci nous montre la création d’un réseau complet de 5

nœuds.

3

Notions de base

Si on utilise la fonction CREATE-LINKS-WITH, on créera

plusieurs connexions en même temps (il est nécessaire de

placer un arrangement des tortues après le code).

Pour créer une seule connexion, on utilise CREATE-LINK-

WITH + «nom de tortue»

L’appellation WITH dénote des arêtes indirectes.

Si on veut créer des arcs directs, on utilise TO ou FROM.

Dans les diapositives suivantes se trouvent quelques

exemples.

4

Notions de base

Exemple 1: Création d’un réseau simple avec 5 nœuds (copie ce

code dans l’onglet de CODE et appelle la procédure «simple_net» dans

le centre des commandes de l’interface)

5

To simple_net

ca

crt 5

ask turtles [setxy random-xcor random-ycor]

;; turtle 1 creates links with all other turtles

ask turtle 0 [ create-links-with other turtles ]

;; this does nothing since the link already exists

ask turtle 0 [ create-link-with turtle 1 ]

ask turtle 2 [ create-link-with turtle 1 ]

show count links ;; shows 5

end

Notions de base

Exemple 2: Création d’un arbre simple avec 6 nœuds (copie ce

code dans l’onglet de CODE et appelle la procédure «make-a-tree»

dans le centre des commandes de l’interface)

6

to make-a-tree

set-default-shape turtles "circle"

crt 6

ask turtle 0 [

create-link-with turtle 1

create-link-with turtle 2

create-link-with turtle 3]

ask turtle 1 [

create-link-with turtle 4

create-link-with turtle 5]

; do a radial tree layout, centered on turtle 0

layout-radial turtles links (turtle 0)

End

Notions de base

Remarques sur la topologie des sommets:

Dans les réseaux simples, généralement on a besoin de positions aléatoires. Il est possible d’ordonner le positionnement aléatoire dès le début :

ask turtles [setxy random-xcor random-ycor]

ou on peut créer le réseau et ensuite, demander aux agents de se positionner autour dans une figure particulière ou autour d’un autre agent, en utilisant les commandes*:

layout-radial …

layout-spring …

layout-tutte …

* voir le dictionnaire de NetLogo pour plus de renseignements sur la syntaxe de ces commandes

7

Notions de base

Exemple 3: Création d’un triangle

8

to make-a-triangle

ca

set-default-shape turtles "circle"

crt 3

ask turtle 0

[create-links-with other turtles]

ask turtle 1

[create-link-with turtle 2]

repeat 30 [ layout-spring turtles links 0.2 5 1 ]

end

Notions de base

Attributs dans les arcs (1) : Tel comme les tortues, les liens ont certains attributs par default.End1 (Origine)

End2 (Destination)

Color

Label

Label-color

Hidden?

Breed

Thickness

Shape

Tie-mode

9

Le nom d’un lien est donné par

ces deux attributs

Si un lien connecte les tortues 1 et 4,

le lien s’appellera LINK 1 4

Notions de base

Attributs dans les arcs (2) : En plus, de la même

façon qu’on alloue des attributs additionnels aux

tortues, il est possible aussi d’allouer attributs aux

liens, avec la même notation. links-own [cost]

links-own [capacity]

10

Notions de base

Exemple 4: Création d’un graphe directe

11

directed-link-breed [red-links red-link]

undirected-link-breed [blue-links blue-link]

to direct-graph

ca

crt 5

;; create links in both directions between turtle 0

;; and all other turtles

ask turtle 0 [ create-red-links-to other turtles ]

ask turtle 0 [ create-red-links-from other turtles ]

;; now create undirected links between turtle 0 and other turtles

ask turtle 0 [ create-blue-links-with other turtles ]

layout-radial turtles links (turtle 0)

end

Notions de base

Attributs dans les arcs (3) : Si on veut travailler avec la distance euclidienne, on peut utiliser :

link-length

Par contre, si on veut travailler avec un distance différent (ex. distance routière), on devrait ajouter ce attribut à chaque arête.

Pour connaître le dégrée des sommets (quantité de nœuds entrants et sortants), on peut utiliser:

my-links

Modèle d’exemple: Dans le modèle ci-joint à cette présentation (Mod1.nlogo) se montrent toutes les procédures ici expliquées.

12

Réseaux complexes

Lorsque la topologie du réseau n’est pas triviale ou quand la quantité des nœuds est relativement grande, on parle des réseaux complexes (ex: l’internet, les réseaux routières, les réseaux sociaux, etc.)

De façon générale, il existe 4 différents types des réseaux:

1. Réseaux aléatoires

2. Réseaux complétés

3. Réseaux du petit monde («Small-World»)

4. Réseaux d’escale livre («Free-Scale»)

Pour savoir plus, vous pouvez consulter la présentation ci-jointe sur les réseaux complexes avec son respectif modèle d’exemple en NetLogo aussi annexe.

13

Algorithmes de recouvrement

minimal

Pour la création d’un arbre des coûts minimale

(qui connecte tous les sommets sans cycles

avec le plus bas coût), on peut utiliser les algorithmes de Kruskal et Prim.

Ces algorithmes sont très utilisés dans la

modélisation des réseaux routiers, électriques,

etc., où les nœuds représentent les maisons

(villages, utilisateurs, etc.), et les arcs

représentent les lignes de connexion.

Les arbres de coût minimaux sont aussi le départ

d’autres applications comme l’algorithme de

Christofides pour trouver des solutions approximatives du problème de voyageur de

commerce (TSP).

14

Algorithmes de

recouvrement minimalVoici le pseudo-code de Kruskal

(Cormen et coll. (2001))

À droit se montre un exemple

d’application de cet algorithme

dans un graphe de petite taille.

15

D’autres algorithmes très utiles

dans les réseaux sont les

algorithmes de plus court

chemin.

Il y a plusieurs méthodes avec

différents niveaux de

complexité (Dijkstra, Moore,

Bellman, Ford, Floyd, etc.).

Lorsque le graphe n’est pas

dirigé (arêtes

bidirectionnelles), la méthode

de Dijkstra est efficace.

Modèle d’exemple: Dans le

modèle ci-joint (Mod3.nlogo)

se montre une application de

ces deux algorithmes.

16Algorithmes de plus court chemin

Exemple d’application de l’algorithme de Dijkstradans un graphe de petite taille.

Création des terraines

Il y a trois méthodes pour créer des terrains en NetLogo.

1. Importation simple d’une image

2. Importation d’un vecteur des données

3. Utilisation de l’extension de systèmes d’information

géographique GIS (dernier sujet de cette présentation)

La méthode plus simple est l’importation d’images.

Il y a trois méthodes:

1. import-drawing filename ;seulement l’image

2. import-pcolors filename ;l’image est transformée dans les cellules avec une valeur numérique (0 à 140)

3. import-pcolors-rgb filename ;l’image est transformée dans les cellules avec un vecteur numérique (RGB)

17

Création des terraines

La deuxième méthode corrige cette problématique, néanmoins il est plus difficile, car cela implique la création d’un vecteur d’information avec des données de toutes les cellules qu’on veut inclure dans le terrain.

Modèle d’exemple : Dans le modèle ci-joint (Mod4.nlogo) se montre une application de ces deux méthodes.

18

Dans cet exemple on a 107 * 110

cellules dans la grille (soit 11.770)

Intégration avec GIS

Il est possible aussi d’utiliser certaines fonctionnalités des outils d’information géographique.

Avec l’extension [GIS], on peut importer vecteurs des données géographiques (points, lignes et polygones), ainsi que trames ou grilles («rasters») chez NetLogo.

Cette fonctionnalité nous permet de créer des environnements plus réalistes lors des modèles qui nécessitent réseaux routiers, cartes géographiques et localisation des villes/chantiers/etc., entre autres.

Pour une meilleure compréhension de toutes les fonctions associées à cette extension, vous pouvez consulter le dictionnaire de NetLogo (section GIS http://ccl.northwestern.edu/netlogo/docs/), ainsi que les modèles d’exemple

19

Intégration avec GIS

Modèle d’exemple 5 – Simulation des réseaux électriques et pannes Mod5-Electric.nlogo

Ce modèle utilise les fonctionnalités géographiques pour créer un réseau électrique entre 62 villes des États-Unis et le Canada. Pour créer le réseau avec le coût optimal, le modèle utilise l’algorithme de Kruskal (déjà expliqué).

Il est possible aussi de créer une panne et de mesurer l’impact du débranchement sur la population.

20

Modèles d’exempleCi-joint à cette présentation se trouvent deux modèles d’exemple

Intégration avec GIS

Ce modèle utilise les fonctionnalités

géographiques pour créer un

réseau routier entre 62 villes des

États-Unis et le Canada à partir d’une matrice des connexions

(fichier externe). De plus, il est

possible de simuler le transport d’un

camion de distribution sur le réseau

entre deux villes quelconques. Pour choisir la route de distribution, le

modèle utilise l’algorithme de

Dijkstra (déjà expliqué).

21

Modèle d’exemple 6 –

Simulation d’un réseau routier Mod6-Road.nlogo

Recommandations finales22

Bonne chance dans vos

projets!

Essayez de suivre les tutoriels de

NetLogo.

Il y a bons exemples dans la librairie de NetLogo.

Il y a plusieurs façons de modéliser un

problème, soyez récursive!.

Si le modèle ne marche pas, ne vous découragez pas, consultez le

dictionnaire, écrivez à la communauté

des utilisateurs ou contacte-moi.

Finalement, ça valut la peine de commencer votre modèle dès

maintenant.