Algorithme génétique sur un problème d'optimisation similaire à un sac à dos

Question

J'ai un problème d'optimisation que j'essaie de résoudre en utilisant un algorithme génétique. Fondamentalement, il y a une liste de 10 variables réelles bornées (-1 <= x <= 1), et je dois maximiser une certaine fonction de cette liste. La difficulté est que seules jusqu'à 4 variables de la liste peuvent être != 0 (condition de sous-ensemble).

Mathématiquement parlant: Pour une fonction f: [-1, 1]^10 -> R min f(X) s.t. |{var in X avec var != 0}| <= 4

Quelques informations sur f: La fonction n'est PAS similaire à n'importe quel type de fonction objectif de type knapsack comme Sum x*poids ou quelque chose comme ça.

Ce que j'ai essayé jusqu'à présent:

Juste un algorithme génétique de base sur le génome [-1, 1]^10 avec un croisement en un point et une certaine mutation gaussienne sur les variables. J'ai essayé d'encoder la condition de sous-ensemble dans la fonction de fitness en utilisant simplement les 4 premières valeurs non nulles (nulles au sens de suffisamment proches de 0). Cette approche ne fonctionne pas très bien et l'algorithme reste bloqué sur les 4 premières variables et n'utilise jamais les valeurs au-delà de cela. J'ai vu une sorte d'AG pour le problème du 01-knapsack où cette approche a bien fonctionné, mais apparemment cela fonctionne juste avec des variables binaires.

Que me recommanderiez-vous d'essayer ensuite?

Answer 1

Si votre fonction de fitness est rapide et simple à évaluer, il est bon marché d'augmenter la taille de votre population totale.

Le problème auquel vous êtes confronté est que vous essayez de sélectionner deux choses complètement différentes simultanément. Vous voulez sélectionner les 4 génomes qui vous intéressent, puis déterminer quels sont les valeurs optimales.

Je vois deux façons de faire cela.

1. Vous créez 210 "espèces" différentes. Chaque espèce est définie par les 4 des 10 génomes qu'elle est autorisée à utiliser. Ensuite, vous pouvez exécuter un algorithme génétique sur chaque espèce séparément (en série ou en parallèle dans un cluster).

2. Chaque organisme n'a que 4 valeurs génomiques (lors de la création de descendants aléatoires, choisissez les génomes au hasard). Lorsque deux organismes se reproduisent, vous ne croisez que les génomes qui correspondent. Si votre paire d'organismes contient 3 génomes communs, vous pouvez choisir aléatoirement lequel des génomes vous préférez comme le 4e. Vous pouvez également, en tant que heuristique, éviter de faire se reproduire des organismes qui semblent être trop génétiquement différents (c'est-à-dire qu'une paire qui partage deux génomes ou moins pourrait produire une mauvaise descendance).

J'espère que cela vous donnera des idées sur lesquelles travailler.

Answer 2

Vous pourriez essayer une étape de style "pivot" : choisissez l'une des valeurs non nulles existantes pour devenir zéro, et remplacez-la en définissant l'une des valeurs zéro existantes pour devenir non nulle. (Mon terme "pivot" vient de la programmation linéaire, dans laquelle un pivot est l'étape de base dans la méthode du simplexe).

Le cas le plus simple serait d'être aléatoire de manière impartiale dans la sélection de chacune de ces valeurs; vous pouvez choisir une valeur aléatoire, ou plusieurs valeurs, pour la nouvelle variable non nulle. Une étape plus locale consisterait à utiliser une étape gaussienne uniquement sur les variables non nulles existantes, mais si l'une de ces variables traverse zéro, générez des variations qui pivotent vers l'une des valeurs zéro. (Notez que ces étapes ne sont pas mutuellement exclusives, car vous pouvez facilement ajouter les deux types d'étapes).

Si vous avez des informations sur le comportement local de votre score de fitness, vous pouvez essayer de les utiliser pour guider votre choix. Juste parce que l'évolution réelle ne regarde pas la fonction de fitness, ne signifie pas que vous ne pouvez pas le faire...

Answer 3

Votre algorithme génétique résout-il bien le problème sans contrainte de sous-ensemble? Si ce n'est pas le cas, vous voudrez peut-être commencer par traiter cela en premier.

Deuxièmement, vous pouvez rendre votre contrainte souple au lieu d'être stricte : Pénalisez la qualité d'une solution pour chaque variable à valeur nulle qu'elle contient, au-delà de 4. (Vous pouvez commencer par assouplir la contrainte encore plus en permettant 9 variables à valeur nulle, puis 8, etc., et vous assurer que l'algorithme génétique est capable de gérer ces variantes du problème avant de le rendre plus difficile.)

Troisièmement, essayez peut-être le croisement à 2 points ou multi-points au lieu du croisement à 1 point.

J'espère que cela vous aidera.

-Ted