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 :

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é :

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
eta2
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

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 donch2
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

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
oua2 = 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
etvoidPercentage
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.