Intelligence artificielle Recherche

Question

tout le monde. Je travaille sur un projet d'ordonnanceur d'horaires universitaires. Principalement, j'utilise la recherche tabou, mais je veux demander:

En recherche générale, vous pouvez explorer tous les voisins de l'état actuel et ensuite prendre le meilleur état - selon une fonction de fitness ou d'évaluation, - mais dans un tel un projet, générant tous les voisins va faire baisser les performances, alors y a-t-il un moyen de me faire passer ce problème? Par exemple, puis-je générer des enfants pour un seul état et bénéficier de cette génération pour tous les autres états pendant le processus de recherche?

S'il vous plaît, si quelqu'un a un expert dans ces algorithmes, s'il vous plaît dites-moi, parce que j'ai travaillé dur sur ces questions.

Answer 1

Je ne suis pas un expert, mais il n'est généralement pas difficile de penser à l'optimisation pour de tels calculs.
Cela dépend vraiment de la fonction de fitness que vous utilisez. Habituellement, connaissant la forme physique d'un nœud, vous pouvez en déduire la portée ou même le pire dans la meilleure gamme de condition physique des enfants.
Avec une fonction assez simple, vous pourriez effectivement être en mesure de calculer la condition physique des enfants, même sans les générer explicitement et ensuite seulement les générer si cela vaut la peine.

Answer 2

Addendum aux commentaires de shoosh: Vous cherchez pruning? De nombreuses stratégies de ce type existent, y compris this. Rappelez-vous, une taille ne convient pas à tous. Donc, vous devrez probablement concevoir une heuristique pour répondre à vos besoins.

Answer 3

Addenda aux commentaires précédents: l'élagage peut également être effectué à plusieurs niveaux, en fonction de vos performances et des contraintes de mémoire. Par exemple:

1. Mettez l'état initial dans une file d'attente de priorité.

2. jusqu'à la fin (par exemple la file d'attente est vide, solution appropriée trouvée, délai expiré, ...), répéter les éléments suivants:

   2.1. Prenez l'entrée supérieure de la file d'attente.

   2.2. Générer ses enfants (en utilisant un estimateur pour obtenir les enfants ayant la plus grande valeur en premier, si possible).

   2.3. Lorsque chaque enfant est généré, placez-le dans la file d'attente prioritaire. Une fois que la file d'attente atteint une limite de taille (que vous déterminez probablement empiriquement par essais et erreurs), chaque insertion dans la file d'attente doit être accompagnée de la suppression de l'élément de plus faible valeur dans la file d'attente.

De toute évidence, avoir de bonnes fonctions d'estimation/évaluation est important pour que cela fonctionne. Votre fonction d'évaluation de file d'attente peut être ajustée pour tenir compte de la «génération» (par exemple donner un bonus pondéré aux états proches de l'état initial, à une profondeur moindre) pour ajuster son biais entre les préférences de profondeur et la largeur.