6533b826fe1ef96bd1284cf5
RESEARCH PRODUCT
Étude de statistiques combinatoires et de leur impact en optimisation évolutionnaire
Carine Khalilsubject
[INFO.INFO-OH] Computer Science [cs]/Other [cs.OH]Genetic algorithmCombinatoricsEvolutionary optimizationOptimisation evolutionaireAlgorithme genetiqueCombinatoireStatistiques combinatoireCombinatorial statisticsdescription
This thesis studies combinatorial objects, with both an algorithmic and a combinatorial point of view. In the combinatorial part, we take care first, the enumeration of Catalan words avoiding pairs of patterns of length three, presenting the proofs of each case with various enumeration methods. Catalan words are particular growth-restricted words counted by the eponymous integer sequence. More precisely, we systematically explore the structural properties of the sets of words under consideration and give enumerating results by constructive bijections or bivariate generating functions with respect to the length and descent number. Then, we study a sorting machine using two stacks in series where the first one avoids a pair of patterns of length three. The process consists of a right-greedy algorithm since we apply at each step the first possible transformation. In this dissertation, we primarily focus on the machines which sort a set of permutations enumerated by Catalan and Schroder numbers. For each class of such permutations, we give a characterization in terms of avoiding patterns which allow us to provide the exact enumeration. In the second part, being more experimental, we studied the optimization of permutation problems with genetic algorithms. Different kinds of encoding of the solutions have been considered to study the transmission of genetic properties in permutation problems. In particular, we used the Lehmer code, inversion table encoding, transposition array encoding, and inverse transposition array encoding during the process. Solution encoding describes the way decision variables are represented. Since indirect encodings are not sensitive to duplicates, they lead to a loss of genetic properties during crossbreeding. This contribution proposes a study of the impact of this loss both in the space of decision variables and in that of objective functions considering the four indirect encodings. In addition, after analyzing that the use of the Lehmer code and inverse transposition array preserve schemata after the recombination process, we proposed an adaptive crossover operator in order to be able to keep the prefix/suffix in order to see its influence on the transmission of genetic properties.
year | journal | country | edition | language |
---|---|---|---|---|
2021-01-01 |