Algorithme génétique et régression linéaire de l’accélération

Cet article présente l’utilisation d’un algorithme génétique pour effectuer une régression linéaire soumise à des contraintes particulières de l’accélération linéaire retournée par un smartphone.J’y explique comment j’essaye d’en améliorer la cohérence à l’aide d’un algorithme génétique, pertinent pour son adaptation.

Vous pouvez visualiser directement le résultat de cette implémentation via JSFiddle.

L’accélération linéaire d’un mouvement est équivalente à l’accélération excluant la composante de gravité. Ce résultat est obtenu à l’aide de fusion de capteurs (accéléromètre, gyroscope, magnétomètre, etc.) et en mettant en place différentes techniques (filtre de Kalman, filtre particulaire, etc.). Sous Android, l’accélération linéaire est directement disponible auprès du SensorManager à l’aide du capteur Sensor.TYPE_LINEAR_ACCELERATION.

Le postulat de départ : l’accélération linéaire n’est pas cohérente

L’accélération linéaire est imprécise, souvent bruitée à cause des opérations effectuées sur les valeurs des autres capteurs pour la trouver, et surtout est incohérente. Prenons l’exemple suivant qui représente un mouvement simple d’un téléphone à bout de bras :

Set de données d'accélérations linéaires — Exemple d’accélération linéaire d’un mouvement rectiligne : un même motif apparaît deux fois

On peut y identifier un même motif (pattern) répété représenté par les deux zones turquoise, qui correspond au début du mouvement (zone 1 – le téléphone obtient une certaine vitesse et se déplace) puis à sa fin (zone 2 – le téléphone perd sa vitesse). Cependant voici les incohérences suivantes :

La somme des accélérations positives et négatives ne s’annule pas: nous allons donc chercher à construire un modèle où l’accélération est nulle.
La courbe est parsemée de valeurs extrêmes très rapprochées : nous devons modéliser l’accélération de façon constante sur un laps de temps pour mieux travailler avec.

Construction du modèle

En quelque sorte, je veux transformer mon mouvement complexe en un mouvement rectiligne uniformément accéléré :

Schématisation de l'accélération et de notre modèle — L’accélération ressemblera à un signal carré. `a1` et `a2` sont les aires sous le signal.

Ainsi j’obtiendrai une accélération constante sur une période de temps plus importante et plus simple à exploiter, avec cependant des contraintes additionnelles (suivant les deux incohérences citées ci-dessus) :

a1 = a2 car la somme des accélérations doit être nulle,
a1 et a2 doivent approcher au plus possible la somme des accélérations entre les bornes.

Soit h1 la hauteur de la première aire et h2 respectivement la deuxième, nous avons
a1 = h1*(x2-x1) = h2*(x3-x2) = a2. Il y a alors une infinité de combinaisons possibles en fonction des variables x1, x2, x3, h1 et h2 et de ce fait, il n’y a pas d’algorithme déterministe adapté et qui ait un coût de calcul raisonnable.

C’est pour cette raison qu’il est intéressant d’utiliser un algorithme génétique pour déterminer la meilleure solution. Additionnellement, sa capacité d’adaptation sera très appréciée pour prendre en compte les accélérations provenant de différents capteurs de différents téléphones, ou encore pour être plus souple face à la détection du motif.

Un algorithme génétique pour trouver la meilleure solution

Pour rappel, le but d’un algorithme génétique est d’apporter une solution inspirée de l’évolution naturelle pour apporter une solution à un problème d’optimisation difficile à aborder et qui dépend de nombreux paramètres. On sélectionne les individus (chromosomes) d’une population les plus aptes à survivre et au fur et à mesure des générations on s’approche d’une solution proche du résultat désiré.

Génération aléatoire

Chaque génération est composée de 15 individus. En reprenant le schéma ci-dessus, j’ai modélisé l’ADN des invididus de l’algorithme génétique de la manière suivante :

DNA: {
    pivots: [x1: float, x2: float, x3: float],
    h1: float,
    h2: float,
}

Lors de la création d’un nouvel individu, on tire aux hasards les trois pivots avec 0 <= x1 < x2 < x3 <= size-1 (où size est la taille du jeu de données) ainsi que h1 tel que -max <= h1 <= max, h1 != 0 et h2 = -h1 * (x2 - x1) / (x1 - x0) étant donné max la valeur maximum absolue du jeu de donnée.

Sélection

La sélection est cruciale pour rapidement tendre vers une bonne solution :

Croisement (crossover) des deux meilleurs individus s’ils ne sont pas (ou quasiment pas) équivalents (sélection par rang), sinon croisement du meilleur et d’un deuxième aléatoirement (sélection quasi uniforme).
Suppression des deux plus mauvais individus.
Insertion de deux nouveaux individus générés aléatoirement.

L’insertion de deux nouveaux individus complètement aléatoires est importante pour ne pas que l’algorithme converge vers une mauvaise solution et se retrouve piégé dans un extremum local (en plus de la mutation).

Mutation

Graphe des probabilités pour un individu de muter pour 15 individus — Probabilités de muter pour 15 individus

La probabilité de mutation d’un individu est calculée en fonction de son rang sachant que le rang le plus faible est le meilleur : p = (n/nmax)² avec n le rang et nmax le rang maximum.

La probabilité est quadratique pour insister sur la nécessité de muter les individus qui ont un mauvais score.

La mutation de l’ADN présente 4 possibilités, d’égale probabilité chacune :

x1 prend une nouvelle valeur dans l’intervalle [0 ; x2[
x2 prend une nouvelle valeur dans l’intervalle ]x1 ; x2[
x3 prend une nouvelle valeur dans l’intervalle ]x2 ; size-1]
h1 est re-tiré aléatoirement de la même manière qu’à la création (et donc h2 se voit modifié aussi)

Fitness fonction

La fitness fonction détermine à quel point un individu rempli les conditions requises et lui attribue son score, ce qui par la suite détermine son rang. La fitness fonction doit pouvoir être calculée rapidement tout en étant pertinente pour déterminer quelles sont les bonnes solutions.

Soit inPercentage le pourcentage d’aire sous la courbe compris entre les pivots x1 et x3 (les bornes), voidPercentage le pourcentage de « vide » dans les aires a1 et a2 entre les bornes :

fitness = (100 - inPercentage)^inAreaImportance + voidPercentage^2

Calcul des composantes `inPercentage` et `voidPercentage`

Ainsi, un bon individu est un individu qui possède un fitness score faible. Ainsi, plus inPercentage tend vers 100 et voidPercentage tend vers 0 plus le score diminue, plus l’individu obtient un meilleur rang. Plus inAreaImportance est grand plus inPercentage devient crucial dans le score total : cela permet de donner plus d’importance aux valeurs correctement comprises entre les bornes (inPercentage) malgré la proportion de vide (voidPercentage) que cela entraîne.

Cela permet de prendre en compte des courbes très incohérentes avec des valeurs manquantes mais qui représentent tant bien que mal un mouvement important. Globalement, mes tests m’ont fait remarquer que inAreaImportance = 6 était une valeur qui permettait de bons résultats.

Additionnellement, j’applique un malus sur le score tel que fitness *= _UNFIT_COEFF ainsi qu’un attribut de non-éligibilité si l’individu ne remplit pas les conditions suivantes :

a1 = 0 ou a2 = 0,
x3 - x1 < _MIN_WIDTH où _MIN_WIDTH est la largeur minimum acceptable,
|h1| > max ou |h2| > max où max est la valeur absolue maximale de jeu de données.

Pourquoi ne pas éliminer directement l’individu plutôt qu’attribuer un malus ? Il est possible que d’un croisement avec un autre individu ou de sa mutation en résulte un individu qui lui possède un bon score et remplisse les critères.

Choix du meilleur

Ne reste plus qu’à déterminer quand il n’est plus nécéssaire de continuer à chercher une solution ou en d’autres termes, quand le meilleur individu (l’élite) a de grandes chance d’être la meilleure solution obtenable. Pour cela, j’utilise plusieurs paramètres dont les valeurs ont été déterminées après tâtonnement :

L’élite rempli les critères additionnels décrits plus haut (éligibilité)
L’élite a traversé plus de 15 générations (pertinence dans le temps),
L’élite possède des valeurs inPercentage et voidPercentage suffisantes (respectivement au-dessus de 65 % et en dessous de 80 % – pertinence du résultat).

Résultat obtenu

J’ai construit une web-app qui permet de simuler en temps réel (néanmoins à fréquence ralentie) le flux retourné par l’accéléromètre d’un smartphone et d’y appliquer l’algorithme génétique. Ci-dessous un exemple de ce que j’obtiens pour un certain jeu de donnée :

Vous pouvez visualiser la simulation via JSFiddle. Il est également possible de modifier dynamiquement certains paramètres via l’encart de contrôles qui déterminent le comportement de l’algorithme comme expliqué plus haut.

Bénéfices / Conclusion

Globalement, l’algorithme donne de bons résultats lorsqu’il y a matière à avoir de bons résultats, c-à-d quand les accélérations sont exploitables (vrais positifs). Dans le cas contraire, les résultats sont très hasardeux et ne correspondent à rien (faux positifs).

L’avantage est qu’en répétant plusieurs fois l’algorithme sur le même jeu de données, on obtient alors plusieurs fois les mêmes vrais positifs tandis que les faux positifs apparaissent de façon sporadique. La répétition nous permettrait alors d’isoler les vrais positifs et d’appuyer la certitude d’avoir obtenu un résultat correct.

Je ne suis pas sûr qu’un algorithme génétique soit vraiment complètement pertinent pour effectuer une régression linéaire, je pense que d’autres heuristiques à base de moyenne peuvent être tout autant performantes en nécessitant moins de temps de calcul. Néanmoins, comme expliqué plus haut, le côté probabiliste de l’algorithme génétique nous permet d’isoler les vrais positifs des faux positifs.

Enfin, l’algorithme génétique tel que je l’ai conçu fait double travail : régression linéaire mais aussi sélection des données qui en valent la peine, et cela serai plus compliqué étant donné la complexité des motifs à détecter dans l’accélération. On pourrait en revanche imaginer un système au but similaire qui effectuerait une classification au préalable pour sélectionner les données puis appliquerait un algorithme heuristique sur celles-ci.