Ordre de construction de mines

**Baruch** · 06/08/2011, 11h29

On a vu qu'on arrive à de très bonnes performances par ces approches.
Mais pour trouver un algo exact, il faut être sûr de passer par toutes les listes optimales 2 à 2... et jusque là je ne vois pas bien comment faire avec une approche par permutations ??

Oui oui je ne cherche pas là un algo exact.

Mais comme comme l'algo par permutations est très rapide mais commet pas mal d'erreurs, j'essaye de le modifier pour sacrifier de la vitesse, mais gagner en précision.

... donc le truc est de savoir ce qui coute le moins et de ce que j'ai pu tester, c'est NDO !

Ok !

**Alikendarfen** · 06/08/2011, 13h26

Un petit bench ci-dessous.

Le tableau compare les performances (temps et qualité du résultat) pour 4 algos :
- Combinaisons avec dominances et optimalité 2 à 2 (exact)
- Naïf avec dominance et optimalité 2 à 2 (exact)
- Insertion (non exact, le dernier donné dans l'un des posts précédents)
- Permutation (non exact, le premier donné par Baruch)

En lignes :
- Le nombre de mines
- (edit) Tirage aléatoire de p, ci, pi, chacun entre 0 et 1
- Pour chaque ligne 1000 tests ont été lancés

En colonnes et par algo :
- Le temps total (pour les 1000) en ms
- Le temps total en ticks (car en ms, les écarts ne sont pas toujours visibles)
- Le nombre d'erreurs (toujours pour 1000)
- Le pourcentage cumulé des erreurs (somme des "(datefin - meilleuredatefin) / meilleuredatefin")

Dans excel, c'est beaucoup plus lisible...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
x1000	Combinaisons + dominance				NDO				Insertion				Permutation			
NbMines	Temps	Ticks	Erreurs	Delta	Temps	Ticks	Erreurs	Delta	Temps	Ticks	Erreurs	Delta	Temps	Ticks	Erreurs	Delta
5	21	133157	0	0	1	83462	0	0	6	42199	0	0	1	15000	20	2,678343874
6	0	134689	0	0	0	115164	0	0	0	38914	0	0	0	15840	23	7,258934856
7	1	186904	0	0	0	156897	0	0	0	46304	0	0	0	17592	21	1,588905408
8	0	256193	0	0	0	223787	0	0	0	55158	0	0	0	20190	35	2,419105701
9	0	328674	0	0	0	285838	0	0	0	62661	0	0	0	22641	26	2,155690092
10	2	360153	0	0	1	315571	0	0	0	59779	0	0	0	20716	21	0,812632761
11	8	512249	0	0	6	457050	0	0	0	74092	0	0	0	24876	22	1,664480082
12	31	704615	0	0	15	622543	0	0	0	88689	0	0	0	29794	28	1,972811875
13	66	850664	0	0	48	754100	0	0	0	91937	0	0	0	28939	23	1,993245378
14	254	1218211	0	0	180	1087137	0	0	0	113245	0	0	0	34693	25	0,492861797
15	421	1510639	0	0	326	1353618	0	0	0	121937	0	0	0	36848	22	1,459334433
16	651	1868930	0	0	542	1691733	0	0	0	132376	0	0	0	37740	35	0,751707951
17	1024	2406626	0	0	863	2158986	0	0	0	147128	0	0	0	42035	24	1,331232762
18	1444	3028089	0	0	1240	2745510	0	0	0	165027	0	0	0	44761	35	1,145624704
19	2131	4059315	0	0	1897	3726676	0	0	0	193042	0	0	0	51747	34	1,316424289
20	2711	4995397	0	0	2426	4527694	0	0	2	200919	0	0	0	52713	30	1,155776425
21	3500	6214556	0	0	3129	5693020	0	0	0	220018	0	0	0	57692	33	0,889941535
22	4488	7770865	0	0	4036	7093729	0	0	3	245305	0	0	0	60197	36	1,559194576
23	6357	10673298	0	0	5571	9463505	0	0	0	266543	0	0	0	68463	24	0,137999755
24	7152	11948388	0	0	6331	10658172	0	0	0	272709	1	9,41E-07	0	66872	34	1,803677785
25	9380	15385837	0	0	8165	13493865	0	0	0	297331	0	0	0	72446	25	0,319710368
26	12295	19955866	0	0	10571	17255077	0	0	0	316576	0	0	0	76046	16	0,55952243
27	13694	22132714	0	0	11920	19355000	0	0	1	327870	0	0	0	78090	23	1,105504607
28	17468	28008389	0	0	15245	24520492	0	0	1	355724	0	0	0	83595	27	1,716384786
29	20561	32785329	0	0	17960	28799803	0	0	1	369354	0	0	0	85795	30	1,056198968
30	25282	40177123	0	0	21464	34252529	0	0	1	394141	0	0	0	89307	30	3,088343307

**Alikendarfen** · 06/08/2011, 13h56

Pour des valeurs plus grandes (40, 50 et 60 mines), voici quelques résultats permettant de comparer les perf : mais cette fois je n'ai fait qu'un seul tirage (il ne s'agit pas de voir les erreurs).

voici le nombre de ticks de chaque algo

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Mines	Comb	NDO	Insertion	Permutation
40	389012	264222	9024	1633
50	7130986	2733735	8433	1438
60	16463207	7795074	9935	1744

On voit que les écarts se creusent significativement entre les algo exacts.
Les deux derniers (non exacts) restant stables.

**Alikendarfen** · 07/08/2011, 11h08

Dans la démo qu'a publié Baruch sur la dominance absolue (pdf partagé précédemment), on arrive à ce résultat, à une étape de la démonstration :

Ma domine Mb
<=>
(1) pa >= pb
et
(2) V p, V p*, ca/p + cb / (p + pa + p*) <= cb/p + ca / (p + pb + p*)

Note : ici p* désigne somme(pj), la productivité cumulée pour toutes combinaisons des mines entre Ma et Mb

J'espère ne pas faire d'erreur de logique, mais on pourrait peut être exploiter la démarche suivante. L'idée est d'utiliser le "V p, V p*" dans un cadre concret d'application : celui où l'on traite un ensemble de mines connues.

Si (2),
alors en particulier, le résultat est vrai pour p = pTot
où pTot = p0 + somme( pi )

Mais si p = pTot, alors p* = 0 (car p* = somme( pj ) pour les mines restantes et il ne reste plus de mines si p=pTot)

Donc pour que Ma domine Mb, il est nécessaire que :
(1) pa >= pb
et
(2') p=pTot, p*=0, ca/p + cb / (p + pa + p*) <= cb/p + ca / (p + pb + p*)

(2') peut se traduire par :

ca/cb <= (papb + papTot) / (papb / pbpTot)

Dites moi ce que vous en pensez ?

De mon côté, je vais faire quelques tests pour vérifier qu'avec ça on améliore dans les cas concrets la notion de dominance actuelle (ca <= cb et pa >= pb).

**Alikendarfen** · 07/08/2011, 12h16

Résultats (!?)

J'ai donc repris la formule :

(2) V p, V p*, ca/p + cb / (p + pa + p*) <= cb/p + ca / (p + pb + p*)

Avec deux conditions nécessaires :

- p = p0 + pTot et donc p* = 0
- p = p0 et p* = pTot

où pTot = somme( pi ) des mines hors pa et pb.

En l'appliquant sur les 100 premières mines du jeu d'essai d'Elentarion... pas d'amélioration !
C'est à dire que l'algo calcule autant (exactement autant) de chemins intermédiaires qu'avec la condition ca <= cb et pa >= pb.

On est certes dans un cas particulier où ces deux conditions nécessaires apportent un résultat... mais ça ne présume rien de très bon pour améliorer significativement la condition de dominance...

**Baruch** · 08/08/2011, 16h20

ca/cb <= (papb + papTot) / (papb / pbpTot)

C'est plutôt : ca/cb <= (papb + papTot) / (papb + pbpTot)

Mais tu peux écrire simplement :

ca (1+ptot/pa) <= cb (1+ptot/pb)

C'est normal qu'il n'y ait pas d'amélioration, puisque tes conditions nécessaires sont déduites de la condition de dominance absolue, non ?

Sinon, merci pour tes comparatifs, ça permet de bien se rendre compte.

Tu pourrais essayer de faire ces tests s'il-te-plaît ?

- Lancer l'algorithme par permutations sans trier la liste auparavant, et voir si sur des listes aléatoires on a de meilleurs résultats. Ca peut paraître contre productif, mais je ne crois pas que ce soit évident.

- Modifier l'algorithme par permutations comme ceci :

Au lieu de calculer à chaque fois le gain pour les couples de mines adjacentes (distantes de 1), on calcule le gain pour les couples de mines distantes de k.
Pour le gain, on n'utilise pas la fonction qui évalue le temps de toute la liste, sinon c'est trop lent, mais plutôt un For sur les mines entre les 2 mines du couple.
Appelons cela l'algorithme par permutations k.

Tester si on a de meilleurs résultats en effectuant d'abord un tri par permutations k, avec k supérieur ou égal à 2, puis le tri par permutations original (k=1).
Par exemple, k=2 puis k=1.

Je pense que ça peut marcher, je vais essayer de faire ça en Caml.

De mon côté, j'ai réfléchi à ça :

Supposons qu'on ait un ensemble E de n mines, sa liste idéale est L.
Supposons qu'on modifie légèrement une caractéristique d'un mine de E.

Il existe un intervalle, dans lequel cette variation n'entraîne pas la modification de l'ordre des mines dans la liste idéale (je ne sais pas vraiment comment le prouver).

Donc étant donné un ensemble E de mines, il existe une multitude d'ensembles E', tels que E' est "similaire" à E. C'est-à-dire qu'on a une similitude qui établit une bijection entre E et E'. Donc si on connaît la liste idéale de L de E, il reste à appliquer la similitude à L pour obtenir la liste idéale L' de E'.

Ca permettrait de faire une sorte de retour d'expérience à l'intérieur d'un algorithme de tri : si on arrive à établir une similitude entre l'ensemble qu'on veut trier, et un ensemble déjà trié, le travail est déjà fait. Sinon, on trie l'ensemble, et on retient sa liste idéale pour l'expérience.

**Alikendarfen** · 08/08/2011, 16h54

Envoyé par Baruch

ca (1+ptot/pa) <= cb (1+ptot/pb)

C'est normal qu'il n'y ait pas d'amélioration, puisque tes conditions nécessaires sont déduites de la condition de dominance absolue, non ?

? Je ne crois pas ?

Si on prend l'exemple pour pTot, on a deux conditions :
- pa >= pb
- et ca (1+ptot/pa) <= cb (1+ptot/pb) : ce qui est bien différent de ca <= cb

... dans la pratique, ça peut donner :
- pa >= pb
- ca <= 5 * cb (par exemple)

Envoyé par Baruch

Tu pourrais essayer de faire ces tests s'il-te-plaît ?
... etc

Pourquoi pas... mais une remarque : l'implémentation avec la distance k nous rapproche de la démarche par algo génétiques déjà vu précédemment.

Je ne sais si tu as suivi cela ? Voici ce qui avait été fait :

- On prend un ensemble E de chemins au hasard (par ex 200 chemins)
- On calcule les dates pour chaque chemin
- On prend garde les 100 meilleurs
- et pour chacun des 100 meilleurs, on génère un nouveau chemin en appliquant 1 permutation sur n couples de mines pris aléatoirement (où n est lui-même un nombre aléatoire)
- Le nouvel ensemble E est alors constitué des 100 meilleurs et des nouveaux chemins
- etc.

Enfin, concernant :

Envoyé par Baruch

Supposons qu'on ait un ensemble E de n mines, sa liste idéale est L.
Supposons qu'on modifie légèrement une caractéristique d'un mine de E.
... etc

,

si je comprends bien, il faudrait en quelque sorte constituer par expérience une famille de chemins et identifier qu'un nouveau chemin appartient à une "enveloppe" constituée de certains chemins de la famille ?

Mais la variation d'une mine Mi en M'i (celle modifiée pour obtenir E' depuis E tel que L'=L) est elle-même dépendante des autres mines, non ?

**Baruch** · 11/08/2011, 16h45

Yiha !

J'ai trouvé un algorithme qui me paraît très bien

Au lieu de générer une liste idéale 2 à 2, on génère une liste idéale 3 à 3 !

Ca peut paraître étrange, mais en pratique c'est très rapide, et ça fait peu d'erreurs (mais il reste à faire un test rigoureux).

L'idée est la suivante :

Avant tout, trier la liste par rendements décroissants, et pour les rendements égaux, par coût croissant.

Pour chaque triplet (a,b,c) de mines adjacentes rencontré :

- Si on est arrivé à la fin de la liste, on arrête l'algorithme, sinon :
- On trie [a;b;c] dans la liste (cf après)
- Si [a;b;c] était la liste idéale, on passe au triplet suivant (b,c,d)
- Si on obtient un ordre différent (ie si [a;b;c] n'était pas la liste idéale), on recommence au début de la liste

En Caml ça donne ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
let ideal3a3 list p0 =
	let tri a b c p = tri_naif [|a;b;c|] p in
	let rec boucle chemin l p = match l with
		| a::b::c::l' -> let triabc = tri a b c p in
					if triabc = [a;b;c] then boucle (chemin @ [a]) (b::c::l') (p +. a.prod) else boucle [] (chemin @ triabc @ l') p0
		| _ -> chemin @ l
	in
	boucle [] list p0 ;;

Ici, pour le tri de 3 mines, j'utilise le tri naïf, mais c'était juste par commodité. Il faudrait trouver le moyen le plus rapide de trier 3 mines. Est-ce que le NDO n'est pas trop lourd pour juste 3 mines ?

Le tri auparavant par rendement décroissant est absolument nécessaire, sinon le temps explose.

En terme de vitesse : je trie 1000 mines en ~7 sec (mais mon pc n'est pas performant, à tester).

Pour les erreurs : sur 1000 essais, pas d'erreurs pour des listes jusqu'à 6 mines. Il faut que je code le NDO pour voir plus loin.

**Alikendarfen** · 11/08/2011, 18h30

Envoyé par Baruch

Ici, pour le tri de 3 mines, j'utilise le tri naïf, mais c'était juste par commodité. Il faudrait trouver le moyen le plus rapide de trier 3 mines. Est-ce que le NDO n'est pas trop lourd pour juste 3 mines ?

Sans doute si ! il est sans doute trop lourd... du fait qu'appliquer les dominances pour 3 mines, ça ne vaut sans doute pas le cout.

Donc, plutôt simplement une approche naïve mais avec optimalité 2 à 2...

**Baruch** · 11/08/2011, 19h41

Ah d'accord. Bon de toute façon je vais tester dans différents cas, et puis il faut que je code le NDO pour faire les tests d'erreurs.

**Alikendarfen** · 11/08/2011, 19h48

Dans tous les cas, très bonne idée

de prendre la liste par 3 !

**Baruch** · 12/08/2011, 12h04

Pour tes tests, tu as utilisé des mines aléatoire entre 0 et 1, pour une production initiale de 1 ?

Parce-que cette configuration favorise les algorithmes par insertions et par permutations au niveau des erreurs. Si tu prends des mines aléatoires entre 10 et 20, avec une production initiale de 1, il y a normalement plus d'erreurs.

**Baruch** · 13/08/2011, 17h34

Trop déçu !

J'ai codé l'algorithme naïf avec dominances et optimalité 3 par 3 cette fois... et c'est moins bien que 2 par 2

**Alikendarfen** · 15/08/2011, 09h00

Envoyé par Baruch

Trop déçu !

J'ai codé l'algorithme naïf avec dominances et optimalité 3 par 3 cette fois... et c'est moins bien que 2 par 2

Ah... c'est moins bien en quoi ??

**Baruch** · 15/08/2011, 11h10

C'est plus lent... Disons que pour le même temps je trie avec le NDO 50 mines, alors qu'avec le "NDO3" j'en trie 30.

L'avantage du NDO3, c'est qu'il réduit le nombre de chemins possibles à chaque itération.
Mais l'inconvénient, c'est que le tri de 3 mines est trop lent (j'ai testé avec le NDO, et avec l'algo naïf).

Je vais poster le code que j'ai fait.

D'autre part, je ne crois plus en l'algo par permutations ^^. Il semble que même quand on génère une liste idéale 3 par 3, 4 par 4, etc., il reste toujours beaucoup d'erreurs. De plus, j'ai l'impression que les erreurs commises peuvent être vraiment très importantes (j'ai trié une liste de 6 mines par un algo permutations 5 par 5 et... 42% d'écart relatif avec la solution idéale ^^).

Pour les tests, il ne faut pas prendre des mines entre 0 et 1 pour une production initiale de 1. Essaye de prendre des mines entre 0 et 1000, pour une production initiale de 1, et tu verras qu'il y a beaucoup plus d'erreurs.

**Baruch** · 15/08/2011, 18h36

Au fait, je reviens sur ton post sur la dominance.

Ma domine Mb
<=>
(1) pa >= pb
et
(2) V p, V p*, ca/p + cb / (p + pa + p*) <= cb/p + ca / (p + pb + p*)

Note : ici p* désigne somme(pj), la productivité cumulée pour toutes combinaisons des mines entre Ma et Mb

J'espère ne pas faire d'erreur de logique, mais on pourrait peut être exploiter la démarche suivante. L'idée est d'utiliser le "V p, V p*" dans un cadre concret d'application : celui où l'on traite un ensemble de mines connues.

Si (2),
alors en particulier, le résultat est vrai pour p = pTot
où pTot = p0 + somme( pi )

Mais si p = pTot, alors p* = 0 (car p* = somme( pj ) pour les mines restantes et il ne reste plus de mines si p=pTot)

Donc pour que Ma domine Mb, il est nécessaire que :
(1) pa >= pb
et
(2') p=pTot, p*=0, ca/p + cb / (p + pa + p*) <= cb/p + ca / (p + pb + p*)

Ce que j'ai montré, c'est :

A domine absolument B <=> (1) et (2)

Toi tu parles de la dominance relative à l'ensemble de mines donné et à p0 (dominance simple).

En quoi as-tu prouvé que ((1) et (2')) implique la dominance simple ?

A propos de dominance simple, dans le (2) :

V p, V p*, ca/p + cb / (p + pa + p*) <= cb/p + ca / (p + pb + p*)

Au lieu de prendre p réel positif non nul et p* réel positif, j'ai essayé de voir ce que ça donnait de prendre p dans [p0,P] et p* dans [0,P], où P est la somme des productions des n autres mines.

Eh bien ça donne quand même cA <= cB et pA >= pB !

**Alikendarfen** · 16/08/2011, 07h37

Envoyé par Baruch

En quoi as-tu prouvé que ((1) et (2')) implique la dominance simple ?

Je ne l'ai pas prouvé (edit : j'ai bien parlé de condition nécessaire) !! L'idée était de voir l'apport d'une condition a priori plus forte... et ça n'a pas augmenté le nombre de dominantes.

Mais c'est normal apparemment, car :

Envoyé par Baruch

A propos de dominance simple, dans le (2) :

V p, V p*, ca/p + cb / (p + pa + p*) <= cb/p + ca / (p + pb + p*)

Au lieu de prendre p réel positif non nul et p* réel positif, j'ai essayé de voir ce que ça donnait de prendre p dans [p0,P] et p* dans [0,P], où P est la somme des productions des n autres mines.

Eh bien ça donne quand même cA <= cB et pA >= pB !

Donc on est bien d'accord qu'on ne peut améliorer l'axe de recherche dominance absolue ou simple ?

**Alikendarfen** · 16/08/2011, 08h08

Un autre algo :

On part de p, d'une mine M0 et de E' l'ensemble des autres mines Mi.

Existe-t-il une suite de mines [Mj] prises dans E' telle que :
1- dateFin([Mj]) < dateFin([M0])
2- cout([Mj]) >= cout([M0])
3- production([Mj]) >= production([M0])

ou pour le dire autrement : peut on finir plus tôt en ayant dépensé au moins autant et pour obtenir une production au moins égale ?

Si oui : [Mj] est meilleur que [MO], donc on peut recommencer avec [M1] où M1 est la première mine de [Mj], et on sait que [M0] n'est pas une solution.
Si non : [M0] reste une bonne hypothèse

Note : M0 et M1 sont nécessairement dominantes (absolue)

C'est sans doute améliorable (jouer sur les conditions 1,2,3 ou bien trier convenablement les mines, etc.).

Qu'en pensez-vous ?

**Baruch** · 16/08/2011, 12h40

Je ne l'ai pas prouvé (edit : j'ai bien parlé de condition nécessaire) !! L'idée était de voir l'apport d'une condition a priori plus forte... et ça n'a pas augmenté le nombre de dominantes.

Euh si on veut augmenter le nombre de relations de dominance, il faut trouver des conditions moins fortes plutôt non ?

Donc on est bien d'accord qu'on ne peut améliorer l'axe de recherche dominance absolue ou simple ?

Non pas d'accord ^^. Si tu sais résoudre des polynômes de degré n, il y a de l'espoir xD. Et puis dans ma démonstration, je compare les listes avec les extrémités permutées. Pour être plus clair :

Je montre que si A domine absolument B, alors pour toute liste où B est avant A, elle ne peut pas être idéale car il existe une autre liste, où A et B sont permutés, qui est meilleure.
J'ai choisi d'étudier la liste dans laquelle on permute A et B, parce-que ça fournit une relation sympathique. Mais rien n'empêche d'étudier une liste différente.

Enfin bref je ne fermerais pas la porte sur les relations de dominances.