Heuristique d'équilibrage (pour le problème d'horaires)

Question

J'écris un algorithme génétique pour générer des horaires.

En ce moment je suis en utilisant ces deux heuristiques:

1. Nombre de trous entre des conférences en une journée (related) (moins de trous -> plus grand score)
2. Chaque heure a une certaine valeur, donc pour chaque emploi du temps, je calcule les valeurs pour les heures d'ouverture des cours. (conférences à des heures plus appropriées -> plus grand score)

Je veux équilibrer ces deux heuristiques, donc l'algorithme ne favoriserait ni l'un ni l'autre. Quel serait le meilleur moyen d'y parvenir?

Answer 1

Une approche très simple serait simplement d'ajouter les scores ensemble. À la fin de la journée, vous voulez un score composé qui augmente lorsque l'un ou l'autre score indépendant augmente. Vous pouvez également utiliser la multiplication (se méfier des dépassements de nombre en fonction de la taille de vos scores). Avec chaque approche, vous pouvez pondérer les scores individuels, par ex.

total_score = 0.4 * hours_score + 0.7 * holes_score 

Vous pouvez même configurer les poids en fonction de l'utilisateur.

Answer 2

1. Développer une fonction de notation pour évaluer la qualité des horaires générés. Vous en avez l'idée dans vos deux heuristiques.

2. Générez des problèmes d'horaires aléatoires. Choisissez quelques valeurs pour équilibrer les deux heuristiques, générer des solutions et évaluer celles qui vous semblent les meilleures (si vous ne parvenez pas à créer une fonction de notation, regardez-la).

3. choisir un nouveau jeu de pondérations d'équilibre (à savoir dans un quartier du meilleur choix de la dernière fois) et répéter