Nouvelle manière de générer des instances

[SarahMinich]

Je réfléchis à un nouveau moyen de créer des instances pour répondre à la proposition de Imed faite dans le dernier échange de mails. (Pour rappel, il y proposait de créer des instances en paramétrant directement les M(i,j) / costs d'une instance.)

Pour ce faire, mon idée est de générer aléatoire un ensemble de valeurs ayant une certaine moyenne et un certain écart-type. J'ai trouvé cette fonction numpy.random.normal(loc=0.0, scale=1.0, size=None) dans numpy qui me semblait parfaite (lien vers la doc ici) puisque loc est la moyenne souhaitée et scale est l'écart type voulu. Cependant dans l'article concernant cette fonction, il y a une note qui m'embrouille. La voici :

New code should use the normal method of a default_rng() instance instead; see random-quick-start.

Je me suis dit, puisque j'écris du nouveau code, je vais suivre cette nouvelle façon de faire mais... je ne trouve pas d'article concernant random-quick-start dans la doc et j'ai l'impression que la fonction default_rng() ne fait pas ce que je voudrais (doc ici) alors je suis un peu perdue. Est-ce que j'ai mal compris la note dans le paragraphe de la fonction numpy.random.normal ? Avez-vous une idée ?

[laowantong]

J'ai utilisé une distribution uniforme jusqu'ici, mais pourquoi pas une distribution normale, c'est d'ailleurs ce que j'avais fait pour générer les instances de Pagination.

Mais ici, je pense que le plus simple est de continuer à générer des instances aléatoires et rejeter a posteriori celles qui ne satisfont pas aux critères donnés en paramètres. L'infrastructure est en place dans generate_instances.py avec déjà pas mal d'autres critères, donc ça devrait être facile à étendre.

Attention, tu dois exprimer les bornes des intervalles des nouveaux critères en pourcentage d'autres valeurs et pas en valeur absolue, sinon tu risques de devoir rejeter toutes ou la plupart des instances générées.

Concernant le lien manquant dans la doc, je ne sais pas.

[SarahMinich]

Je vais y réfléchir alors, merci du conseil!

[SarahMinich]

Pour mémoire, je remets les différents paramètre à notre disposition pour générer une instance :

{
    "output_directory": "instances/sarah/test",
    "instance_count": 1,
    "min_height": 3,
    "max_height": 4,
    "min_tile_percentage": 20,
    "max_tile_percentage": 40,
    "min_kill_percentage": 20,
    "max_kill_percentage": 60,
    "min_symbol_weight_bound": 1 ,
    "max_symbol_weight_bound": 10,
    "tile_min_size": 2,
    "common_symbol_min_count": 1,
    "common_symbol_max_count": 1,
    "arity": 2,
    "seed": 16
}

Je ne vois pas vraiment en fonction de quel autre paramètre je pourrais exprimer la moyenne et l'écart type désirés alors est-ce que je pourrais plutôt créer quatre nouveaux paramètres en entrée : un pour la moyenne et un pour l'écart-type et deux autres pour exprimer, en pourcentage cette fois, l'écart autorisé à ces deux paramètres ? Est-ce que c'est sensé ?

Par exemple, je donne une moyenne de 56 et je dis que j'ai le droit de m'en écarter de 10%, ça veut dire que si une instance a une moyenne entre 51 (si on arrondit à l'entier inférieur) et 62 (si on arrondit à l'entier supérieur), elle sera acceptée. Sinon elle sera rejetée et on lance une nouvelle création.

[laowantong]

Dans la matrice des coûts, les valeurs dépendent des poids, non ? Donc c'est en fonction des poids. Si tu mets une valeur absolue de 56 ça veut dire que si ton poids minimal est de 100, tout sera rejeté.

[SarahMinich]

J'ai conscience que ça veut dire qu'il faudra faire attention aux valeurs qu'on mettra pour quelles soient compatibles entre elles mais ça ne me choque pas.

De plus, c'est vrai que la moyenne dépendra des valeurs dans la matrice mais nous ne les avons pas, nous n'avons que des bornes pour le poids min et le poids max que nous ne sommes pas sûrs d'atteindre.

[laowantong]

Le but est que le programme « fasse attention » pour toi. J'ai fait ce travail pour pas mal d'autres paramètres. C'est sûr que ça demande un peu plus de réflexion lors de la conception. Mais c'est sûr aussi que tu en es capable. Il suffit juste d'exprimer sous forme d'algorithme ce que veut dire « faire attention ».

Les poids sont tirés aléatoirement de façon uniforme, donc tu peux exprimer ça en fonction de la moyenne des bornes, ça n'est pas un problème.

[SarahMinich]

J'ai réfléchi et j'ai trois propositions à faire.

Première proposition :

On suppose qu'on ne touche presque pas au code déjà écrit, les poids sont tirés aléatoirement entre deux bornes (min_symbol_weight_bound et max_symbol_weight_bound). Cependant, on sait que ces bornes ne sont pas forcément atteintes, je vais donc appeler w_min et w_max les poids min et max dans l'instance.

Puisque je n'ai aucun contrôle sur les poids, il n'est pas réaliste de demander une moyenne précise, je vais donc donner un intervalle de valeurs dans lequel cette moyenne devra se trouver. Bien sûr, le début et la fin de cet intervalle doivent être exprimés en fonction des valeurs déjà données à l'algorithme.

Puisque nous avons w_min, w_max ainsi que le nombre minimal de symboles dans une tuile (tile_min_size) et le nombre maximal de symboles dans une tuile (height), on peut calculer deux bornes pour la moyenne. Si une tuile est composée du plus petit nombre possible de symboles et que tous ses symboles ont le plus petit poids possible, le poids de cette tuile sera égal à tile_min_size * w_min. Ceci est le plus petit poids possible pour une tuile. Si toutes les tuiles ont ce poids minimal, cela veut dire que la moyenne des poids des tuiles sera égale à w_min * tile_min_size. Cette valeur est donc une borne inférieure pour la moyenne des valeurs de la matrice costs. On appelle celle ci m_min. Avec un raisonnement similaire, on obtient m_max = w_max * height.

On pourrait donc ajouter deux paramètres au fichier de configuration qui seraient l'écart en pourcentage à une des deux bornes et on n'accepterait que les instances dont la moyenne est dans l'intervalle demandé. Par exemple, si on veut que la moyenne soit dans un intervalle entre 30 et 40% de la borne minimale, on pourrait avoir le déroulement suivant :

Tant qu'on n'a pas suffisamment d'instances :
    1/ Générer aléatoirement un ensemble de poids
    2/ Vérifier si m in [m_min + 0.3 (m_max - m_min) ; m_min + 0.4 (m_max - m_min) ]
        Si oui, on stocke l'instance
        Si non, on jette l'instance à la poubelle
    3/ On revient à l'étape 1

Cependant je ne sais pas si cette approche est réaliste car je ne sais pas si qu'on pourra effectivement avoir des instances avec des moyennes très petites ou très grandes.

Deuxième proposition :

Je choisis une valeur pour la moyenne qui devient un paramètre dans le fichier de configuration. Les poids sont toujours choisis aléatoirement mais de façon à respecter la moyenne demandée. Variante : on ne vise pas une moyenne précise, on ne donne qu'un intervalle de moyennes

Troisième proposition

On crée plusieurs dossiers destinés à trier et stocker les instances dans différents groupes (petite moyenne / grand écart-type, petite moyenne / petit écart-type, moyenne moyenne / petit écart-type, etc). Ensuite, on génère aléatoirement un très grand nombre d'instances. A chaque fois que l'une d'entre elles est générée, on calcule sa moyenne et son écart-type et de là on déduit dans quel dossier la ranger. On arrête d'enregistrer les instances à chaque fois qu'un dossier contient suffisamment d'instances.

Cependant, je pense que cette approche a le même désavantage que la première proposition.

[laowantong]

Je ne comprends pas trop quel est ton problème, mais je ne suis pas dedans. C'est à toi d'implanter tes différentes idées, de les tester et de les comparer.