Algorithme génétique en santé (3/5)

🩺 Le problème#

Dans la deuxième partie de cet article nous avons vu comment on pouvait utiliser de l’optimisation linéaire pour trouver une bonne distribution du temps afin d’aider notre ami médecin.

Le problème est que cette distribution ne tenait compte que des consultations individuelles et du temps de travail total pour être formulé. Or nous souhaiterions trouver une méthode plus générale pour resoudre ce problème.

Pour cela on aimerait trouver un moyen pour maximiser : Le taux horaire moyen multiplié par le nombre de patients moyen vus / heure.

Si on reprend notre tableau initial :

Cela correspond à la valeur dans € pondéré, qui est le fruit de la multiplication de la valeur de chaque acte par le pourcentage que cet acte représente sur le nombre total (14%). Cette valeur est le résultat de ce qu’on appelle le produit scalaire entre les 2 colonnes.

$$ \sum_{i=1}^{n} a_{i}b_{i} $$

où $ a_{i} $ sont les cotations des actes et $ b_{i} $ les pourcentages. Dans notre exemple la valeur est de 39,53 €, comme on peut voir à droite.

Il s’avère que le nombre de patients vu par heure suit la même logique. Dans ce cas cela dépend du temps que cet acte requiert. Donc si on voit un patient toutes les 15 minutes, on verra 4 patients par heure.

On a donc que le nombre de patients vus en moyenne par heure est :

$$ \sum_{i=1}^{n} c_{i}b_{i} $$

où $ c_{i} $ est le nombre de patients vu par heure pour chaque acte et $ b_{i} $ les pourcentages. Dans notre exemple cela est 3 patients par heure, comme on peut voir dans la ligne P/H à droite du tableau.

Donc le montant total moyen par heure chez notre ami médecin est :

$$ \sum_{i=1}^{n} a_{i}b_{i} * \sum_{i=1}^{n} c_{i}b_{i} $$

Dans notre tableau, cela correspond à 118,44€, ce qui est le résultat de $ 39,53 € * 3 $

Notre volonté est donc de maximiser ce résultat.

$$ \max \sum_{i=1}^{n} a_{i}b_{i} * \sum_{i=1}^{n} c_{i}b_{i} $$

On a les valeurs de $ a_{i} $ et de $ c_{i} $, il faut donc trouver les valeurs de $ b_{i} $.

🤔 Comment faire ?#

Comme on le sait les multiplications sont des opérations commutatives, c’est à dire qu’on peut inverser l’ordre des opérations sans affecter le résultat. Cela rend la recherche d’une solution particulièrement difficile. On doit donc le faire par tatonnement.

  • 👤 Vous : Comment ça par “tatonnement” ?
  • 👨 Moi : Oui, c’est une méthode de résolution de problèmes. Voici un article sur le sujet.
  • 👤 Vous : Ok mais il faut choisir des numéros au hasard et voir si on arrive au résultat ?
  • 👨 Moi : Oui. Mais on peut faire ça de manière un peu intelligente. Donc c’est un hasard de plus en plus proche du résultat final.
  • 👤 Vous : D’accord. Et comment on fait ça ?
  • 👨 Moi : On utilise ce qu’on appelle un algorithme génétique.

En quoi cela consiste ?

Ce système s’inspire de l’évolution biologique. On va reprendre notre exemple des chats. Les chats ne peuvent pas produire de la taurine, un acide aminé nécessaire à la production des protéines. Pour la récupérer, ils doivent l’ingérer. Or, pour ce faire, ils doivent chasser d’autres animaux, ce sont donc des prédateurs.

Donc imaginons qu’il y a des milliers d’années on avait un groupe de chats qui n’arrivait pas à chasser la nuit. Ceux qui ont reçu de leurs parents une mutation leur permettant de voir la nuit ont pu le faire et manger ainsi plus de viande (sélection) au total. Ils étaient donc plus forts que leurs frères et soeurs ou cousin(e)s qui ne pouvaient pas le faire et donc avaient plus de probabilités de se reproduire (croisement) et ainsi consolider la mutation pour les générations futures.

En résumé cela se fait comme ça :

👨‍💻 En pratique#

Un algorithme génétique suit exactement les mêmes étapes que la figure du paragraphe précédent.

🏁 Initialization#

  • Ici on détermine par exemple une matrice (chromosome) avec plein de valeurs au hasard. La taille de cette matrice est de 7, puisque dans notre cas on cherche 7 pourcentages différents (les valeurs $b_{i}$). On détermine une grande quantité X de matrices de même taille, par exemple 150. Cela correspond à notre population.

👍 Selection#

  • Pour chaque matrice on calcule le résultat de l’équation $\sum_{i=1}^{n} a_{i}b_{i} * \sum_{i=1}^{n} c_{i}b_{i}$
  • Cela nous permet de voir parmi toutes les matrices, celles qui ont les valeurs les plus élevées (Preserved dans le schéma) et on enlève toutes les matrices qui ont des valeurs en dessous de celles-là (Discarded dans le schéma). On peut définir combien de matrices on préserve sur le total. Imaginons que nous prenons les 75 meilleures.

🔄 Croisement#

  • Afin de maintenir une population homogène de 150 membres, on récupère les 75 meilleures matrices de l’étape précédente (parents) et on croise les valeurs entre elles pour créer 75 nouvelles matrices qui sont le fruit de ce croisement. On peut déterminer si on croise à 1 seul endroit ou à plusieurs etc. Sur l’image il y a un croisement sur un seul point.

🧑‍🔬 Mutation#

  • Sur le schéma ce n’est pas visible, mais il est possible de faire des modifications dans des gènes particuliers de chaque matrice une fois le croisement fait.
  • Nous pouvons déterminer combien de gènes on souhaite modifier et quelle est l’importance de cette modification. Par exemple on peut dire qu’on souhaite muter de manière aléatoire 50% des gènes (donc 50% des valeurs) en augmentant ledites valeurs de manière aléatoire entre -3 et +3.

♻️ Cycle#

  • Une fois que ce cycle est fini, on passe à nouveau à l’étape d’évaluation et sélection, redémarrant ainsi tout le cycle. On peut définir en amont combien de cycles on souhaite réaliser.

📝 Exemple#

Imaginons que nous avons une fonction : $$ y = f(w1…w6) = w1x1 + w2x2 + w3x3 + w4x4 + w5x5 + 6wx6 $$ Où $$(x1,x2,x3,x4,x5,x6)=[4,-2,3.5,5,-11,-4.7]$$ Et $$ y=44 $$

Quelles sont les valeurs des coefficients w1 à w6 pour obtenir ce résultat ? Ceci est l’équivalent à avoir une équation à 6 inconnues sans avoir les 5 autres équations nécessaires à pouvoir trouver toutes les inconnues.

Pour résoudre ce problème on utilisera 2 librairies en Python : PyGAD et Numpy

Voici le code (source ):

import pygad
import numpy

"""
Given the following function:
    y = f(w1:w6) = w1x1 + w2x2 + w3x3 + w4x4 + w5x5 + 6wx6
    where (x1,x2,x3,x4,x5,x6)=(4,-2,3.5,5,-11,-4.7) and y=44
What are the best values for the 6 weights (w1 to w6)? We are going to use the genetic algorithm to optimize this function.
"""

function_inputs = [4,-2,3.5,5,-11,-4.7] # Function inputs.
desired_output = 44 # Function output.

def fitness_func(solution, solution_idx):
    # Calculating the fitness value of each solution in the current population.
    # The fitness function calulates the sum of products between each input and its corresponding weight.
    output = numpy.sum(solution*function_inputs)
    fitness = 1.0 / numpy.abs(output - desired_output)
    return fitness

fitness_function = fitness_func

num_generations = 100 # Number of generations.
num_parents_mating = 7 # Number of solutions to be selected as parents in the mating pool.

# To prepare the initial population, there are 2 ways:
# 1) Prepare it yourself and pass it to the initial_population parameter. This way is useful when the user wants to start the genetic algorithm with a custom initial population.
# 2) Assign valid integer values to the sol_per_pop and num_genes parameters. If the initial_population parameter exists, then the sol_per_pop and num_genes parameters are useless.
sol_per_pop = 50 # Number of solutions in the population.
num_genes = len(function_inputs)

init_range_low = -2
init_range_high = 5

parent_selection_type = "sss" # Type of parent selection.
keep_parents = 7 # Number of parents to keep in the next population. -1 means keep all parents and 0 means keep nothing.

crossover_type = "single_point" # Type of the crossover operator.

# Parameters of the mutation operation.
mutation_type = "random" # Type of the mutation operator.
mutation_percent_genes = 10 # Percentage of genes to mutate. This parameter has no action if the parameter mutation_num_genes exists or when mutation_type is None.

last_fitness = 0
def callback_generation(ga_instance):
    global last_fitness
    print("Generation = {generation}".format(generation=ga_instance.generations_completed))
    print("Fitness    = {fitness}".format(fitness=ga_instance.best_solution()[1]))
    print("Change     = {change}".format(change=ga_instance.best_solution()[1] - last_fitness))
    last_fitness = ga_instance.best_solution()[1]

# Creating an instance of the GA class inside the ga module. Some parameters are initialized within the constructor.
ga_instance = pygad.GA(num_generations=num_generations,
                       num_parents_mating=num_parents_mating, 
                       fitness_func=fitness_function,
                       sol_per_pop=sol_per_pop, 
                       num_genes=num_genes,
                       init_range_low=init_range_low,
                       init_range_high=init_range_high,
                       parent_selection_type=parent_selection_type,
                       keep_parents=keep_parents,
                       crossover_type=crossover_type,
                       mutation_type=mutation_type,
                       mutation_percent_genes=mutation_percent_genes,
                       callback_generation=callback_generation)

# Running the GA to optimize the parameters of the function.
ga_instance.run()

# After the generations complete, some plots are showed that summarize the how the outputs/fitenss values evolve over generations.
ga_instance.plot_result()

# Returning the details of the best solution.
solution, solution_fitness, solution_idx = ga_instance.best_solution()
print("Parameters of the best solution : {solution}".format(solution=solution))
print("Fitness value of the best solution = {solution_fitness}".format(solution_fitness=solution_fitness))
print("Index of the best solution : {solution_idx}".format(solution_idx=solution_idx))

prediction = numpy.sum(numpy.array(function_inputs)*solution)
print("Predicted output based on the best solution : {prediction}".format(prediction=prediction))

if ga_instance.best_solution_generation != -1:
    print("Best fitness value reached after {best_solution_generation} generations.".format(best_solution_generation=ga_instance.best_solution_generation))

# Saving the GA instance.
filename = 'genetic' # The filename to which the instance is saved. The name is without extension.
ga_instance.save(filename=filename)

# Loading the saved GA instance.
loaded_ga_instance = pygad.load(filename=filename)
loaded_ga_instance.plot_result()

Voici l’évolution de la performance avec le temps :

Les poids de $w1…w6$ sont : $[ 3.17255718,-0.58570363,5.00037482,-1.7099189,-1.31901385,-1.42063254]$

Maintenant qu’on a compris ce que c’est un algorithme génétique, on verra lors du prochain article comme répondre à notre problème à nous.

comments powered by Disqus

© 2021