Algorithmes d'optimisation stochastique

Question

Disons que nous avons 2 algorithmes d'optimisation stochastique (algorithmes génétiques, optimisation de l'essaimage de particules, Cuckoo Search, etc.), A et B, et nous voulons trouver les maxima globaux d'une fonction. Alors, si l'algorithme A fonctionne mieux que l'algorithme B pour optimiser la fonction F sur un espace de recherche unidimensionnel, est-il aussi meilleur que B pour optimiser la fonction F sur un espace de recherche N-dimensionnel?

Je ferai référence à la fonction F dans N dimensions par F_ND. Notez que F_1D et F_ND ont la même fonction, sauf dans un nombre de dimensions différent; le "paysage" est exactement le même, seulement de différentes dimensions.

Ex: pour la fonction DeJong nous avons:

F_1D(x) = x[0]*x[0] 
F_5D(x) = x[0]*x[0] + x[1]*x[1] + x[2]*x[2] + x[3]*x[3] + x[4]*x[4] 

F_1D et F_5D ont le même "aspect" "type"/

... mettre autrement:

Si general_performance (A, F_1D)> general_performance (B, F_1D) puis general_performance (A, F_ND)> general_performance (B, F_ND) (pour un N plus grand, bien sûr) aussi?

Answer 1

On ne sait pas actuellement si une telle propriété serait maintenue. Le théorème de No Free Lunch (NFL) ne s'applique pas entièrement ici puisque vous parlez d'un ensemble très restreint de problèmes. Le problème que vous avez dessiné est toujours indépendant dans les dimensions supérieures (on peut optimiser chaque variable séparément et atteindre l'optimum global). Dans ce cas, on pourrait argumenter que vous pourriez diviser ce problème en 5 problèmes de 1 dimension et résoudre chaque dimension séparément. Cela devrait toujours être moins cher que de les résoudre ensemble (en supposant qu'aucune dimension n'est libre).

Je pense que cela dépend beaucoup du type de problème, mais en général, je ne pense pas qu'une telle propriété existe et que pour certains problèmes et certains N, vous pouvez trouver un algorithme B tel que A est meilleur que B < => dimension < N et B sont meilleurs que A < => dimension> = N.