Metaheuristics for optimization in continuous variables: application to the development of a calculation engine for the measurement of orthodontic movements.
Métaheuristiques pour l'optimisation en variables continues : application au développement d'un moteur de calcul pour la mesure de mouvements orthodontiques.
Résumé
This thesis was prepared in cooperation with Dental Monitoring, a company that has developed a tool permitting the orthodontists to remotely monitor the evolution of the treatment of their patients. This tool uses photographs of the dentition of the patients, sent to the clinician by smartphone. Then, the goal is to match the characteristics of the dental images with the 2D projection of the 3D dental model of the patient. The process used is carried out in two steps: the extraction of the primitives (mainly, the apparent outline of the teeth), then the matching of the 2D projection of the model on each image. Dental Monitoring is currently addressing the matching problem using a simulated annealing algorithm.
The purpose of the thesis was to develop a new optimization method, ensuring at the same time automation, accuracy and speed of the calculations. The problem to be solved being with continuous variables, we used the particle swarm optimization algorithm. However, this algorithm has two main weaknesses: on the one hand, its premature convergence, generally related to the particle velocity parameters, which are difficult to set, and on the other hand, its poor performance in local search. To overcome these two difficulties, we have developed an algorithmic variant called QUAPSO (QUAntum Particle Swarm Optimization). This algorithm is based on quantum features, in order to improve the convergence of the swarm, by constantly adapting the particle velocity parameters to the local landscape of the solution space. In addition, the local search of QUAPSO is enhanced thanks to a hybridization with a local search method, the kangaroo algorithm. Lastly, QUAPSO implements a new neighborhood topology, called ""single file"", which offers a better balance between exploration and exploitation of an area of the solution space.
QUAPSO has been tested on a large set of benchmark functions, before being successfully applied to cases of the problem described above. A statistical analysis of the performances, as well as a study of the behaviour of the swarm and the algorithmic complexity, made it possible to highlight the features of this new method. Furthermore, various complementary works were carried out on the characterization of the calculation engine and on the study of the accuracy of the cost function.
Cette thèse a été préparée sous contrat Cifre avec la société Dental Monitoring, qui a développé un outil pour les orthodontistes, leur permettant de suivre à distance l’évolution du traitement de leurs patients. Cet outil repose sur l’envoi par ces derniers de photographies de leur dentition ; il s’agit alors de superposer les caractéristiques de ces images dentaires et de la projection 2D d’un modèle 3D préexistant de la dentition du patient. Le procédé utilisé se déroule en deux étapes : l’extraction des primitives (principalement, le contour apparent des dents), puis le recalage de la projection 2D du modèle sur chaque photographie. Dental Monitoring traite actuellement le problème de recalage à l’aide d’un algorithme de recuit simulé.
L’objet de la thèse était de développer une méthode de recalage plus performante, qui améliore la précision et la rapidité des calculs, et qui assure leur automatisation. Le problème à résoudre étant par nature à variables continues, nous avons fait appel à l’algorithme d’optimisation par essaim particulaire. Cependant, cet algorithme présente deux principaux défauts : d’une part, sa convergence prématurée, liée généralement aux paramètres de déplacement des particules, qui sont difficiles à régler, et d’autre part ses faibles performances en recherche locale. Pour pallier ces deux difficultés, nous avons développé une variante algorithmique dénommée QUAPSO (QUAntum Particle Swarm Optimization). Cet algorithme est doté d’attributs quantiques, afin d’améliorer la convergence de l’essaim, en adaptant en permanence les paramètres de déplacement des particules au paysage local de l’espace des solutions. En outre, la recherche locale de QUAPSO est perfectionnée grâce à une hybridation avec une technique de voisinage, l’algorithme kangourou. Enfin, QUAPSO met en œuvre une nouvelle topologie de voisinage, nommée ""file indienne"", qui offre un meilleur équilibre entre exploration et exploitation d’une zone de l’espace de recherche des solutions.
QUAPSO a été d'abord testé sur un large panel de fonctions de coût académiques et, ensuite, appliqué avec succès à des instances du problème d'orthodontie décrit plus haut. Une analyse statistique des performances, ainsi qu’une étude du comportement de l’essaim et de la complexité algorithmique, ont permis de mettre en évidence les caractéristiques de cette nouvelle méthode. En outre, différents travaux annexes ont été menés, qui ont porté sur la caractérisation du moteur de calculs et sur l’étude de la précision de la fonction de coût.