Approximate solutions

Reading time25 min

En bref

Résumé de l’article

Comme mentionné dans d’autres articles, les heuristiques fournissent des solutions approximatives. Ici, nous donnons plus de détails sur la manière de caractériser la qualité d’une solution approximative. En particulier, nous nous concentrons sur la rapidité et la justesse.

Points clés

  • Une solution approximative est un compromis entre qualité et temps requis.

  • Les solutions qui sont un compromis optimal sont appelées Pareto-optimales.

Contenu de l’article

1 — Vidéo

Veuillez regarder la vidéo ci-dessous. Vous pouvez également lire la transcription si vous préférez.

Information

Alors, nous y revoilà. Content de voir que vous êtes arrivés à la semaine 5 !

Aujourd’hui, nous allons parler de la comparaison des implémentations. Face à des problèmes pratiques comme le problème du voyageur de commerce, le TSP, nous préférerions évidemment la solution à la fois rapide et correcte.

Frontière de Pareto et Pareto optimal

Dans le cas des problèmes NP-Complets, ce qui est le cas pour le TSP, nous savons que cela n’est tout simplement pas possible. Nous devons sacrifier la rapidité, la justesse, ou un peu des deux.

Ce type de compromis est souvent appelé "frontière de Pareto", que nous pouvons définir de la manière suivante : "quel est l'algorithme le plus rapide que nous pouvons trouver pour résoudre un problème avec un certain niveau de justesse ?".

Nous appelons "Pareto optimal" un point qui se trouve sur une frontière de Pareto, ce qui signifie qu'il correspond à un compromis optimal entre rapidité et justesse.

Un Pareto optimal est typiquement un optimal qui dépend de l’importance relative de deux paramètres ou plus, tels que la taille du problème que nous traitons.

Mesurer la rapidité et la justesse

Définissons quelques notions liées à la mesure de la rapidité et de la justesse. Nous pouvons mesurer la rapidité d'un algorithme en utilisant la complexité ou des mesures de temps d'exécution. Mais la justesse d'un algorithme est difficile à définir, ce qui rend sa mesure compliquée.

Pour le TSP, nous savons que nous voulons trouver un chemin le plus court, donc la justesse pourrait simplement être mesurée comme une déviation par rapport à la longueur du chemin le plus court.

Mais en pratique, ce n'est pas toujours aussi simple. Trouver le chemin le plus court réel peut être impossible s'il y a plus d'une trentaine de sommets, comme nous l'avons vu que la complexité d'une recherche exhaustive croît exponentiellement. Cela signifie que la justesse d'un algorithme approchant une solution pour le TSP est très difficile à estimer.

Comparer les algorithmes

Ce que nous savons, c'est que plus la complexité que nous devons gérer est grande, meilleure la solution devrait être en termes de justesse. Dans le pire des cas, nous pouvons toujours nous appuyer sur une solution moins complexe qui a déjà été proposée.

Prenons à nouveau le TSP comme exemple. Il existe de nombreuses étapes intermédiaires entre l'algorithme glouton, qui consiste à toujours cibler la ville la plus proche suivante, et la force brute, qui examine exhaustivement tous les chemins possibles pour visiter chaque ville. Trouver un intermédiaire entre ces deux extrêmes ne devrait être envisagé que s'il apporte réellement des améliorations en termes de complexité.

Pour déterminer si une solution proposée est efficace, vous devriez toujours la comparer avec une approche simple, à la fois en termes de justesse et de complexité. Si votre solution doit être 10 fois plus complexe pour fournir une amélioration de 1 % en termes de justesse, peut-être que cela ne vaut pas l’effort, sauf si cette amélioration de 1 % fait une différence significative par rapport aux autres solutions.

Mots de conclusion

Voilà, c’est tout pour aujourd’hui, merci de votre attention ! C’est ma dernière vidéo. J’ai vraiment apprécié enseigner pour vous ! Je vous laisse entre de bonnes mains pour la semaine 6, durant laquelle Patrick et Vincent vous parleront de la théorie des jeux combinatoires. Au revoir !

Pour aller plus loin

2 — Exemple – coloration de graphes

2.1 — L’algorithme exact

Considérons l’exemple suivant : nous appelons “coloration d’un graphe” un vecteur d’entiers, chacun associé à un de ses sommets. Ces entiers sont appelés couleurs des sommets, et peuvent être identiques.

Une coloration est dite “propre” si tous les sommets reliés par une arête ont des couleurs différentes. Le “nombre chromatique d’un graphe” est le nombre minimum de couleurs apparaissant dans une coloration donnée.

Ce problème est un exemple connu de problème NP-Complet. Une façon de le résoudre précisément est de lister toutes les colorations possibles avec 1 couleur, puis 2 couleurs, etc. jusqu’à trouver une coloration propre.

Le code Python suivant résout le problème comme décrit ci-dessus :

​
# Easy iteration over permutations
import itertools

# Function to check if a coloring is correct
# A coloring is correct if no neighbors share a color
def check_coloring (graph, colors):
    for vertex in range(len(graph)):
        for neighbor in graph[vertex]:
            if colors[vertex] == colors[neighbor]:
                return False
    return True

# This function returns a coloring of the given graph using a minimum number of colors
# We gradually increase the number of available colors
# For each number, we test all possible arrangements of colors
def exhaustive_coloring (graph):
    for nb_colors in range(len(graph)):
        for coloring in itertools.product(range(nb_colors), repeat=len(graph)):
            print("Nb colors:", nb_colors, "- Candidate coloring:", coloring)
            if check_coloring(graph, coloring):
                return coloring
    
# Test graph
# Here, we represnt graphs as an adjacency list
graph = [[1, 2, 5], [0, 2, 5], [0, 1], [4, 5], [3, 5], [0, 1, 3, 4]]
result = exhaustive_coloring(graph)
print(result)

Dans cet exemple, un graphe est implémenté sous forme d’une liste de listes. Il contient 6 sommets (nommés $v_1$ à $v_6$), et 8 arêtes (symétriques). La solution retournée par l’algorithme est :

Sortie
[0, 1, 2, 0, 1, 2]

Cela indique que trois couleurs suffisent pour avoir une coloration propre du graphe, avec :

  • $v_1$ et $v_4$ partageant la couleur 0.
  • $v_2$ et $v_5$ partageant la couleur 1.
  • $v_3$ et $v_6$ partageant la couleur 2.

2.2 — L’approche gloutonne

Cet algorithme est très complexe et une solution approximative bien connue est de trier les sommets par nombre décroissant de voisins, en les coloriant dans cet ordre en choisissant la plus petite couleur positive qui maintient la coloration propre. Cet algorithme approximatif est décrit ci-dessous :

​
# For min-heaps
import heapq

# Function to check if a coloring is correct
# A coloring is correct if no neighbors share a color
def check_coloring (graph, colors):
    for vertex in range(len(graph)):
        if colors[vertex] is not None:
            for neighbor in graph[vertex]:
                if colors[neighbor] is not None:
                    if colors[vertex] == colors[neighbor]:
                        return False
    return True

# This function greedily tries to color the graph from highest degree node to lowest degree one
# First, we sort nodes in descending degree order using a max-heap (negative min-heap)
# Then we color nodes using that heap
def greedy_coloring (graph):
    heap = []
    for vertex in range(len(graph)):
        heapq.heappush(heap, (-len(graph[vertex]), vertex))
    colors = [None] * len(graph)
    while len(heap) > 0:
        degree, vertex = heapq.heappop(heap)
        for color in range(len(graph)):
            colors[vertex] = color
            if check_coloring(graph, colors):
                break
    return colors

# Test graph
graph = [[1, 2, 5], [0, 2, 5], [0, 1], [4, 5], [3, 5], [0, 1, 3, 4]]
result = greedy_coloring(graph)
print(result)

Cet algorithme est beaucoup moins complexe que le précédent, et permet donc de considérer des graphes avec beaucoup plus de sommets. Ici, nous obtenons le résultat suivant :

Sortie
[0, 1, 2, 0, 1, 2]

Notez qu’ici, nous trouvons le même résultat que l’algorithme exhaustif. Cependant, ce n’est pas toujours le cas.

2.3 — Simulations

Afin d’évaluer la qualité de notre algorithme approximatif, nous allons nous concentrer sur deux choses : le temps de calcul et la précision. Pour tester ces deux quantités, nous allons faire la moyenne des résultats sur un grand nombre de graphes aléatoires.

Pour automatiser un peu les choses, nous allons adapter nos codes pour prendre des arguments en ligne de commande et produire un fichier traitable. Créons deux fichiers Python.

Le programme suivant, measure_greedy.py, retourne le temps moyen d’exécution de l’approche gloutonne pour résoudre le problème considéré, ainsi que le nombre moyen de couleurs nécessaires pour un graphe de taille fixe :

​
# Various imports
import math
import random
import heapq
import time
import sys

# Arguments
NB_NODES = int(sys.argv[1])
EDGE_PROBABILITY = math.log(NB_NODES) / NB_NODES
NB_TESTS = int(sys.argv[2])

# Set a fixed random seed for comparing scripts on same graphs
random.seed(NB_NODES)

# Generates an Erdos-Renyi random graph
def generate_graph ():
    graph = [[] for i in range(NB_NODES)]
    for i in range(NB_NODES):
        for j in range(i + 1, NB_NODES):
            if random.random() < EDGE_PROBABILITY:
                graph[i].append(j)
                graph[j].append(i)
    return graph

# Function to check if a coloring is correct
# A coloring is correct if no neighbors share a color
def check_coloring (graph, colors):
    for vertex in range(len(graph)):
        if colors[vertex] is not None:
            for neighbor in graph[vertex]:
                if colors[neighbor] is not None:
                    if colors[vertex] == colors[neighbor]:
                        return False
    return True

# This function greedily tries to color the graph from highest degree node to lowest degree one
# First, we sort nodes in descending degree order using a max-heap (negative min-heap)
# Then we color nodes using that heap
def greedy_coloring (graph):
    heap = []
    for vertex in range(len(graph)):
        heapq.heappush(heap, (-len(graph[vertex]), vertex))
    colors = [None] * len(graph)
    while len(heap) > 0:
        degree, vertex = heapq.heappop(heap)
        for color in range(len(graph)):
            colors[vertex] = color
            if check_coloring(graph, colors):
                break
    return colors

# Tests
average_time = 0.0
average_solution_length = 0.0
for i in range(NB_TESTS):
    graph = generate_graph()
    time_start = time.time()
    solution = greedy_coloring(graph)
    average_solution_length += len(set(solution)) / NB_TESTS
    average_time += (time.time() - time_start) / NB_TESTS

# Print average time as a function of problem size
print(NB_NODES, ";", average_time, ";", average_solution_length)

De même, le programme suivant measure_exhaustive.py évalue la solution exhaustive :

​
# Various imports
import math
import random
import time
import sys
import itertools

# Arguments
NB_NODES = int(sys.argv[1])
EDGE_PROBABILITY = math.log(NB_NODES) / NB_NODES
NB_TESTS = int(sys.argv[2])

# Set a fixed random seed for comparing scripts on same graphs
random.seed(NB_NODES)

# Generates an Erdos-Renyi random graph
def generate_graph ():
    graph = [[] for i in range(NB_NODES)]
    for i in range(NB_NODES):
        for j in range(i + 1, NB_NODES):
            if random.random() < EDGE_PROBABILITY:
                graph[i].append(j)
                graph[j].append(i)
    return graph

# Function to check if a coloring is correct
# A coloring is correct if no neighbors share a color
def check_coloring (graph, colors):
    for vertex in range(len(graph)):
        for neighbor in graph[vertex]:
            if colors[vertex] == colors[neighbor]:
                return False
    return True

# This function returns a coloring of the given graph using a minimum number of colors
# We gradually increase the number of available colors
# For each number, we test all possible arrangements of colors
def exhaustive_coloring (graph):
    for nb_colors in range(len(graph)):
        for coloring in itertools.product(range(nb_colors), repeat=len(graph)):
            print("Nb colors:", nb_colors, "- Candidate coloring:", coloring)
            if check_coloring(graph, coloring):
                return coloring

# Tests
average_time = 0.0
average_solution_length = 0.0
for i in range(NB_TESTS):
    graph = generate_graph()
    time_start = time.time()
    solution = exhaustive_coloring(graph)
    average_solution_length += len(set(solution)) / NB_TESTS
    average_time += (time.time() - time_start) / NB_TESTS

# Print average time as a function of problem size
print(NB_NODES, ";", average_time, ";", average_solution_length)

Nous pouvons maintenant exécuter les commandes suivantes pour lancer les deux algorithmes sur des graphes aléatoires (100 graphes par ordre de graphe). La recherche exhaustive ne sera évaluée que sur un sous-ensemble des ordres de graphe pour des raisons de temps :

​
@echo off
for /l %%n in (5,1,100) do (
    python measure_greedy.py %%n 100 >> results_greedy.csv
)
for ($n = 5; $n -le 100; $n++) {
    python measure_greedy.py $n 100 >> results_greedy.csv
}
for n in {5..100}; do
    python3 measure_greedy.py $n 100 >> results_greedy.csv
done
for n in {5..100}; do
    python3 measure_greedy.py $n 100 >> results_greedy.csv
done
​
@echo off
for /l %%n in (5,1,20) do (
    python measure_exhaustive.py %%n 100 >> results_exhaustive.csv
)
for ($n = 5; $n -le 20; $n++) {
    python measure_exhaustive.py $n 100 >> results_exhaustive.csv
}
for n in {5..20}; do
    python3 measure_exhaustive.py $n 100 >> results_exhaustive.csv
done
for n in {5..20}; do
    python3 measure_exhaustive.py $n 100 >> results_exhaustive.csv
done

Comparons les temps d’exécution avec Libreoffice :

Clairement, le gain en temps d’exécution est significatif. De même, comparons les nombres chromatiques moyens trouvés pour les deux algorithmes :

En regardant la courbe de précision, il semble que la perte de précision ne soit pas très élevée, du moins pour les tailles de problème qui ont pu être calculées avec l’approche exhaustive. Pour des graphes plus grands, nous ne pouvons pas calculer la solution exacte en raison de la complexité de sa recherche.

Pour évaluer un peu plus cet aspect, nous allons évaluer les solutions trouvées avec l’approche gloutonne sur des graphes bipartis, pour lesquels nous savons que le nombre chromatique est toujours 2 :

​
# Generates a bipartite Erdos-Renyi random graph
def generate_bipartite_graph ():
    graph = [[] for i in range(NB_NODES)]
    for i in range(NB_NODES):
        for j in range(i + 1, NB_NODES):
            if i % 2 != j % 2 and random.random() < EDGE_PROBABILITY:
                graph[i].append(j)
                graph[j].append(i)
    return graph

Nous obtenons les résultats suivants :

Là encore, le résultat semble raisonnable, ce qui nous fait penser que cette heuristique est bien adaptée au problème.

Vous devez cependant noter que pour de petites tailles de problème, le nombre chromatique trouvé est parfois inférieur à 2, ce qui semble incorrect. Cependant, remarquez que le générateur de graphes aléatoires ne vérifie pas la connectivité du graphe, ce qui peut conduire à des graphes déconnectés pour un faible nombre de sommets.

Pour aller au-delà