Ordre de construction de mines

Version imprimable

Voir 40 message(s) de cette discussion en une page

02/06/2011, 18h24
Alikendarfen

Ben... il faut bien prendre un exemple !! ;)

Justement, je suis en train de voir, si on change l'ordre ou les valeurs... pour le moment il semble toujours qu'une règle soit là quelque part.

Il y a quelque chose... peut être un calcul de pente ou de barycentre, je ne sais pas encore.

Peut être il faut faire le calcul sur x tirages et faire une moyenne ?

Je ne sais pas non plus si, sur des chemins plus longs, on trouverait plusieurs minimaux locaux (sans doute ça sera le cas).

En tout cas pour le moment, ça me semble toujours intéressant : on verra !

... et peut être ça marchera pas (mais ça sera pas la première fois :mrgreen:)
02/06/2011, 20h02
Alikendarfen

En fait, tout semble se passer de la manière suivante (soyez indulgents, cette réflexion n'est basée que sur quelques exemples) :

Le déplacement d'une mine de la première à la dernière position engendre une "onde" sur le temps global.

La forme de cette onde et le fait qu'elle aille vers l'avant ou vers l'arrière semble dépendre de la position de la mine par rapport au chemin idéal.

Il faut voir l'ensemble (les tableaux communiqués précédemment) comme une surface 2d mouvante.

Bien que je n'ai pas de règle concrête, cela semble correspondre à ces gradients dont on parle depuis le retour (assez bref !) de prgasp77.

@prgasp77 : d'ailleurs si tu as un peu de temps, je serais assez intéressé pour connaitre ce que tu penses des croisements dans le cadre d'une résolution par AG dans ce type de problème. Pour moi, seulement des mutations sont possibles, mais je ne suis pas spécialiste.

En tout cas, on pourrait espérer utiliser la notion de gradient pour orienter les mutations (ainsi que les dominances).
05/06/2011, 10h03
Alikendarfen

Un algo en o(n²) qui semble fonctionner très bien (mais n'est peut être pas optimal, voir à la fin de ce post).

Edit : Je propose de l'appeler "algo par insertion".

Soit donc :
- p0 : la production initiale
- E = {Mi(ci,pi)}

Trier E par ci/pi croissant et en cas d'égalité par ci croissant. Ce tri produit la liste L.

Construire un chemin C vide.
Puis pour chaque Mi de L

C = Meilleur( C, Mi, p0 )
Fin

Et Meilleur( C, Mi, p0 ) est défini par :
Début

- C = [M1, M2, ..., Mn]
- Prendre le meilleur (date de fin la plus petite) parmi :

C0 = [Mi, M1, M2, ..., Mn]
C1 = [M1, Mi, M2, ..., Mn]
C2 = [M1, M2, Mi, ..., Mn]
...
Cn = [M1, M2, ..., Mi, Mn]
Cn+1 = [M1, M2, ..., Mn, Mi]
Fin

Je n'ai pas de preuve pour cet algo. Je peux simplement dire qu'il donne les mêmes résultats (ou des résultats ayant le même score) que l'algo par combinaisons en o(2^n) sur les quelques tests que j'ai pu faire.

Intuitivement, c'est probablement seulement une heuristique.

... maintenant, il est peut être possible de démontrer qu'il y a sous certaines conditions une stabilité dans cette construction incrémentale qui conduise au résultat optimal ?
... ou bien trouver un contre exemple ?
05/06/2011, 15h15
Alikendarfen

Bon... je monologue un peu, mais j'ai quelques autres résultats :

L'algo par insertion semble très bien fonctionner.
Comme il est en n², ça permet de monter beaucoup en nombre de mines.

Seulement, pour comparer les résultats de cet algo, il faut une autre méthode : j'ai donc implémenté une approche par algo génétiques.

OK : tout ça n'apportera pas une preuve mathématique mais donnera une tendance sur l'intérêt d'en chercher une pour l'algo par insertion !

Donc l'approche par AG, voici comment j'ai procédé (pour n mines) :

- Un gène est une liste ordonnée des n mines

- Au départ P gènes sont générés au hasard (P=400)

- Puis on va faire progresser cette population en produisant la génération suivante

- A chaque génération : on garde les P/2 meilleurs gènes et chacun de ces gènes produit un gène descendant

- La nouvelle population comprend donc P/2 meilleurs gènes de la génération d'avant et P/2 gènes issus de ceux-ci.

- La génération d'un gène g' par un gène g est faite en effectuant de 1 à 6 fois (tirage aléatoire) une permutation de deux mines de g. En effet, les notions de croisement me semblent inappropriés à ce type de problème.

- Au total, c'est une approche basique : je ne me suis pas embêté à préserver de la diversité ou autre

> Résultats :

L'approche par algo génétiques ne dépasse pas l'algo par insertion.

Exemple :
Pour 52 mines, il faut environ 10000 générations pour atteindre le résultat de l'algo par insertion (ces 10000 générations permettent 230 améliorations du score initial).
Au total, 50000 générations ont été produites, mais sans amélioration après la 10000ième.

> A suivre à la recherche d'une preuve pour l'algo par insertion ? :ccool:
> (ou d'une preuve qu'il n'est pas optimal ! :cry:)
15/06/2011, 12h21
Baruch

Salut !

Pour l'algo par insertion : supposons qu'on ait 3 mines a, b, c à trier.

a est idéale
ab est idéale

On veut insérer c :

supposons que cab > acb et que cab > abc
a priori, rien ne l'empêche

les combinaisons qui n'ont pas été testées sont cba , bac , bca

c'est vrai que si cba ou bac étaient idéales, alors ba le serait, ce qui est absurde.

en revanche, je ne vois pas en quoi bca pourrait ne pas être idéale.

Edit : je n'ai pas pris en compte le fait que L est triée... à voir.
15/06/2011, 12h36
Alikendarfen

Tiens Baruch !
Bon retour !

En fait, depuis la dernière fois, je n'ai pas cherché...

Ce qui s'est passé, c'est que de fil en aiguille avec les histoires de gradient, j'ai fini par avoir l'intuition de cet algo...

... par contre, comme je le disais, je n'ai pas de preuve que ça marche toujours. J'ai seulement comparé les résultats versus une approche par AG afin de voir si une meilleure solution serait trouvée (cf. posts précédents).

Mais bon, si tu es de retour, pour tenter de trouver cette preuve, on s'y remet !!

Edit : je pense que le truc tient à deux éléments :
- Le tri préalable par c/p croissant
- La croissance ou décroissance de (p + p1)/(p + p2) selon p1, p2
(car en fait pour ce second point, j'ai encore des résultats différents de ton p* ...)
15/06/2011, 12h40
Baruch

xD oui désolé j'avais un peu mis ce problème de côté. Là j'ai réappris à code en caml, c'est plus pratique.

Euh gné c'est quoi le second point ?
15/06/2011, 12h45
Alikendarfen

Ben le second point, la croissance ou décroissance de (p + p1)/(p + p2) !
15/06/2011, 12h48
Baruch

Euh mais en quoi l'étude de cette fonction est intéressante ? Quel est le rapport avec "mon" p* ?
15/06/2011, 12h54
Alikendarfen

1 pièce(s) jointe(s)

(je dois y aller là, retour un peu plus tard).

Mais je t'ai traduit un docx en doc pour la démo (c'est un peu dégueu à la conversion mais malgré tout lisible je crois).

cf. PJ

Dis moi ce que tu en penses
15/06/2011, 12h57
Alikendarfen

ah... et ce qui n'est pas indiqué dans le word, c'est que P (grand P) = somme des pi de toutes les mines hors p1, p2.
15/06/2011, 13h17
Baruch

Oui t'obtiens bien ça :

f(p)=0 <=> p = p1p2(c1-c2) / (c2p1 - c1p2)

tu divises en haut et en bas par p1p2, et tu retrouves l'expression de mon p* ^^

Tu te compliques un peu la vie, je cite un post précédent :

Citation:

On part de T(M1M2)<T(M2M1)
<=> c1/p + c2/(p+p1) < c2/p + c1/(p+p2)
on multiplie tout par p(p+p1)(p+p2), on simplifie, on obtient :
p * (c1p2-c2p1) < p1p2(c2-c1)

si c1p2-c2p1 > 0 alors p < p1p2(c2-c1)/(c1p2-c2p1) = (c2-c1)/(c1/p1-c2/p2)
si c1p2-c2p1 < 0 alors p > (c2-c1)/(c1/p1-c2/p2)

on pose p* = (c2-c1)/(c1/p1-c2/p2)

on a alors :
T(M1M2)<T(M2M1) équivaut à

c1p2-c2p1 > 0 et p < p*
ou
c1p2-c2p1 < 0 et p > p*

T'es d'accord sur ça ?

Après on regarde l'équivalence de T12 > T21 :

Citation:

De même, si on permute 1 et 2, p* étant invariant, on a :

T(M1M2)>T(M2M1) équivaut à

c1p2-c2p1 < 0 et p < p*
ou
c1p2-c2p1 > 0 et p > p*

Et enfin on regroupe les cas à partir des 2 systèmes :

Citation:

si p<p*, alors c1p2-c2p1 > 0 et T(M1M2)<T(M2M1), ou alors c1p2-c2p1 < 0 et T(M1M2)>T(M2M1)

Et on peut faire de même pour p>p*

Et puis ça revient à dire :

Citation:

or c1p2-c2p1>0 <=> p1/c1<p2/c2 <=> M1 moins rentable que M2
donc on résume à : si p<p*, alors le moins rentable est avant
et de même, si p>p*, le plus rentable est avant
15/06/2011, 14h20
Alikendarfen

Je suis d'accord avec ce que tu dis.

Sans doute la seule différence réside dans le fait qu'on peut (dès le départ) tester par rapport à P (= somme etc.).

Reste que dans la pratique (je veux dire en implémentation), c'est aussi simple et rapide de calculer directement T(M1M2) vs. T(M2M1)...

... ce qui revient à dire que ça n'apporte pas grand chose (où alors j'ai raté un truc) sauf à exploiter plus loin ce résultat.

Bon sinon, je suis d'accord avec ton post précédent :

Citation:

en revanche, je ne vois pas en quoi bca pourrait ne pas être idéale.

Pour ça, on n'a pas de preuve.

PS : comme tu t'es remis à caml, si tu veux mes codes sources (certes, en C#) dis moi
15/06/2011, 14h51
JeitEmgie

L'ordre optimal dépend de la topologie du problème : càd les rapports entre la production initiale, la valeur totale des mines, le nombre de mines, … et la répartition statistique des mines en termes de coût, production et de rentabilité dans cet espace…

Or chaque fois que l'on choisit une mine la topologie du problème restant change.
C'est pour cela qu'en testant différentes heuristiques vous obtenez des résultats parfois meilleurs parfois moins bons, mais cela ne donnera jamais la "meilleure" heuristique pour tous les cas : parfois c'est par priorité de rendement, parfois par celle de coût…

Il est assez facile de comprendre d'un jeu de données dans lequel P0 > Max(Pi) n'aura pas du tout le même comportement que celui dans lequel P0 < Min(Pi)…
de même si le Max(Pi) est >> Mean(Pi), ou si Max(Pi) et Min(Pi) sont ≈ Mean(Pi), … (bref comment se distribuent les coûts, productions et rendements) on aura encore des résultats différents.

Par exemple une mine ayant un très bon rendement - au moins 2x supérieur à celui de toutes les autres - mais ayant aussi un coût très supérieur (par exemple plus de 5x plus chère) à la moyenne des coûts des autres ne doit pas être produite avant les autres malgré son excellent rendement (mais cela ne veut pas dire pour autant qu'il faille la rejeter tout à la fin… il faut pouvoir détecter quand cela vaut la peine d'attendre pour avoir le budget de la produire).
Par contre si son coût est du même ordre de grandeur que celui des autres alors il est au contraire très intéressant de la produire le vite possible quitte à attendre à avoir le budget suffisant et s'abstenir de produire des mines moins chères - mais moins rentable - en attendant.
15/06/2011, 15h09
Alikendarfen

En fait, de tout ça, je ne sais ce qu'on peut déduire ?

La dernière règle proposée (mais non démontrée) dit à peu près :

- Si, selon p0, M1 doit être avant M2 et qu'on constitue un chemin E=[M1M2]

- Alors tout ajout de mine Mi à E et tel que ci/pi < c1/p1 et ci/pi < c2/p2 ne change pas l'ordre entre M1 et M2 dans le chemin optimal E' comprenant M1 M2 et Mi

Ou encore pour le dire autrement : si E=[M1M2] est optimal, alors soit [MiM1M2], soit [M1MiM2], soit [M1M2Mi] est optimal (avec Mi respectant les conditions ci-dessus)

@JeitEmgie : penses tu que cette règle puisse être vraie ?
15/06/2011, 16h08
Baruch

Ouép JeitEmgie je pense que t'as bien cerné toute la difficulté du problème.

Alikendarfen,

En effet toute l'histoire de p* là ça me paraît inutile. Le seul intérêt que j'y voyais au départ, c'était la rapidité de calcul, avec par exemple des matrices de booléens. Mais on est d'accord que c'est négligeable. Je pense que c'est une fausse piste pour un algo qui trouve la solution optimale. En effet, pourquoi se limiter à des listes de 2 éléments... Par contre, je pense que ça aura peut-être bien un intérêt pour des algos de solutions approchées.

En effet je veux bien voir tes codes. Histoire d'avoir en caml une version propre de l'algo naïf, et de l'algo en 2^n. Il faudrait que je code aussi un algo qui permette de générer toutes les solutions idéales 2 à 2, pour voir si leur temps résultant varie beaucoup (simple curiosité).

Sinon, pour ton algo par insertion, tu pourrais le comparer avec un algo dont on est sûr qu'il marche ? Genre sur 1000 listes aléatoires tu appliques les 2 algorithmes, et tu vérifies que la solution est bien identique ?
15/06/2011, 16h59
Alikendarfen

Citation:

Sinon, pour ton algo par insertion, tu pourrais le comparer avec un algo dont on est sûr qu'il marche ? Genre sur 1000 listes aléatoires tu appliques les 2 algorithmes, et tu vérifies que la solution est bien identique ?

J'y ai bien pensé, mais ça ne donnera une preuve que si l'algo par insertion ne marche pas... du coup, il faudrait avoir une idée de comment orienter ces listes aléatoires pour ne pas piocher pour rien...

Si tu as des idées ?

L'algo en 2^n, je l'ai donné dans les post 43 et 44 : donc voir ces posts.

En post 43, c'est les classes de base avec qq méthodes qui servent aussi pour l'algo naïf (même classes de base).

L'algo naïf est basé sur les arrangements :

Code:

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
 
        public Chemin Traiter( List<Mine> mines, double p )
        {
            List<Chemin> resultats = new List<Chemin>();
 
            mines.Arrangement( lm => EvalMines( lm, mines.Count, p, resultats ) );
 
            resultats.Sort( ( a, b ) =>
                {
                    return a.DateFin.CompareTo( b.DateFin );
                } );
 
            return resultats[0];
        }
 
        void EvalMines( IEnumerable<Mine> mines, int n, double p, List<Chemin> resultats )
        {
            Chemin resultat = new Chemin();
            resultat.Production = p;
 
            foreach ( Mine mine in mines )
                resultat.AjouterMine( mine );
 
            resultats.Add( resultat );
        }

Avec l'arrangement :

Code:

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
30
31
32
33
34
35
36
 
        public static void Arrangement<T>( this List<T> list, Action<IEnumerable<T>> action )
        {
            Dictionary<T, bool> dicoIn = new Dictionary<T, bool>();
            Stack<T> stackOut = new Stack<T>();
 
            list.ForEach( e => dicoIn.Add( e, true ) );
 
            Arrangement( dicoIn, stackOut, action );
        }
 
        static void Arrangement<T>( Dictionary<T, bool> dicoIn, Stack<T> stackOut, Action<IEnumerable<T>> action )
        {
            if ( dicoIn.Count == 0 )
            {
                List<T> resultat = new List<T>( stackOut );
                resultat.Reverse();
 
                action( resultat );
            }
            else
            {
                List<T> list = new List<T>( dicoIn.Keys );
 
                foreach ( T element in list )
                {
                    dicoIn.Remove( element );
                    stackOut.Push( element );
 
                    Arrangement( dicoIn, stackOut, action );
 
                    stackOut.Pop();
                    dicoIn.Add( element, true );
                }
            }
        }

Pas trop camlien comme code (à part les lambdas et continuations), mais pour la traduction, je te laisse voir...

Tant qu'on y est, je mets aussi la version algo génétiques (approche naïve, encore une fois) mais qui marche aussi.

Code:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
        public Chemin Traiter( List<Mine> mines, double p )
        {
// Algo3 c'est l'algo par insertion, pour comparer (cf. un peu plus bas)
            Algo3 algo3 = new Algo3();
 
            Chemin reference = algo3.Traiter( mines, p );
 
 
            List<Mine> minesCourantes = mines;
            List<Gene> population = new List<Gene>();
 
            int demiPopulation = 200;
 
            for ( int i = 0 ; i < 2 * demiPopulation ; i++ )
            {
                Gene gene = new Gene() { ProductionInitiale = p };
 
                minesCourantes = minesCourantes.Random();
 
                gene.Mines = minesCourantes;
 
                population.Add( gene );
            }
 
            population.ForEach( g => g.CalculerScore() );
            population.Sort( ( a, b ) => a.Score.CompareTo( b.Score ) );
 
            double meilleurScore = population[0].Score;
            int nombreDAmeliorations = 0;
            int genDerniereAmelioration = 0;
 
            for ( int gen = 0 ; gen < 50000 ; gen++ )
            {
                for ( int i = 0 ; i < demiPopulation ; i++ )
                    population[i + demiPopulation] = population[i].Muter();
 
                population.ForEach( g => g.CalculerScore() );
                population.Sort( ( a, b ) => a.Score.CompareTo( b.Score ) );
 
                if ( population[0].Score < meilleurScore )
                {
                    meilleurScore = population[0].Score;
                    nombreDAmeliorations++;
                    genDerniereAmelioration = gen;
                }
            }
 
            Chemin meilleur = population[0].Chemin();
 
            double deltaReference = reference.DateFin - meilleur.DateFin;
 
            return meilleur;
        }

Code:

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
        class Gene
        {
            public List<Mine> Mines;
            public double ProductionInitiale;
            public double Score;
 
            public void CalculerScore()
            {
                Score = 0.0;
 
                double p = ProductionInitiale;
 
                foreach ( Mine mine in Mines )
                {
                    Score += mine.Cout / p;
                    p += mine.Production;
                }
            }
 
            public Gene Muter()
            {
                Gene gene = new Gene() { ProductionInitiale = ProductionInitiale, Mines = new List<Mine>( Mines ) };
 
                int limit = 1 + AlgoRandom.Next( 6 );
                for ( int i = 0 ; i < limit ; i++ )
                {
                    int p1 = AlgoRandom.Next( gene.Mines.Count );
                    int p2 = AlgoRandom.Next( gene.Mines.Count );
 
                    Mine m1 = gene.Mines[p1];
                    Mine m2 = gene.Mines[p2];
 
                    gene.Mines[p1] = m2;
                    gene.Mines[p2] = m1;
                }
 
                return gene;
            }
 
            public Chemin Chemin()
            {
                Chemin chemin = new Chemin() { Production = ProductionInitiale };
 
                Mines.ForEach( m => chemin.AjouterMine( m ) );
 
                return chemin;
            }
 
            public override string ToString()
            {
                StringBuilder sb = new StringBuilder();
 
                sb.Append( Score.ToString( "0.00000000000000" ) );
                Mines.ForEach( m => sb.Append( "/" + m.Nom ) );
 
                return sb.ToString();
            }
        }

Bon, c'est confirmé :D
L'algo par insertion ne marche pas :(

Exemple :
Code:

1 2 3 4 5 6 Cout Production A 0,42394709 0,181478475 B 0,874808729 0,625076863 C 0,930540906 0,998728962 (les valeurs sont peut être arrondies via copier/coller, mais peu importe)
Algo naïf : ACB
Algo par insertion (plus mauvais) : ABC

Voir 40 message(s) de cette discussion en une page