Les défis des golgoths

**Golgotha** · 30/03/2010, 16h46

Merci pseudocode,

il va falloir plusieurs réponse avant de confronter les résultats, je rajoute le tiens en haut, en attendant..

**pseudocode** · 30/03/2010, 16h55

Envoyé par Golgotha

Merci pseudocode,

il va falloir plusieurs réponse avant de confronter les résultats, je rajoute le tiens en haut, en attendant..

Le code qui va avec.

Code java :

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
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
 
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;
 
public class Defi2 {
 
	double[][] planets = {
		{914,9904,1583},{2371,7086,9327},{6266,5886,6028},{4451,7026,7292},{1573,6693,8829},
		{8875,18,5462},{1582,6028,8613},{9426,2272,9831},{6310,2007,903},{6896,5130,8681},
		{4086,6387,991},{2897,2825,9816},{851,5771,2018},{3020,1260,9760},{570,5348,766},
		{3168,1099,5495},{4893,9563,7652},{7634,4480,3935},{5114,1487,7632},{1752,6060,5080},
		{8425,9370,757},{7346,365,640},{6302,8676,3868},{9013,8025,4246},{3444,8561,4769},
		{8853,8857,6923},{9065,3143,909},{5407,2004,5566},{1030,6451,1908},{7055,7782,1339}
	};
 
	// number of planets
	int N=planets.length;
 
	// distance between planets
	double[][] distance = new double[N][N];
 
	// random generator
	Random random = new Random(0);
 
	// return distance between 2 points
	double distance(double[] a, double[] b) {
		return Math.sqrt( Math.pow(a[0]-b[0], 2)+Math.pow(a[1]-b[1], 2)+Math.pow(a[2]-b[2], 2) );
	}
 
	// precompute distance between planets
	void init() {
		for(int i=0;i<N;i++) {
			for(int j=i+1;j<N;j++) {
				distance[i][j] = distance(planets[i],planets[j]);
				distance[j][i] = distance[i][j];
		} }
	}
 
	// DNA Chromosome
	class DNA {
		int[] sequence = new int[N];
		double length = 0;
 
		// new random chromosome
		public DNA() {
			random();
		}
 
		// duplicate existing chromosome
		public DNA(DNA src) {
			length=src.length;
			for(int i=0;i<N;i++)
				sequence[i]=src.sequence[i];
		}
 
		// mutate chromosome
		public void mutate() {
			int i = random.nextInt(N), j=i;
			while(i==j) j = random.nextInt(N);
			int swap = sequence[i]; sequence[i]=sequence[j]; sequence[j]=swap;
			compute();
		}
 
		// crossover chromosome
		public void crossover(DNA other) { // PMX style
			int cut = random.nextInt(N);
			int len = random.nextInt(N-cut);
			for(int i=cut;i<=len;i++) {
				int k = other.sequence[i];
				int j=0;
				while(sequence[j]!=k) j++;
				int swap = sequence[i]; sequence[i]=sequence[j]; sequence[j]=swap;
			}
			compute();
		}
 
		// shift chromosome
		public void shift() {
			int[] shift = new int[N];
			int offset = random.nextInt(N);
			for(int i=0;i<N;i++)
				shift[i]=sequence[(i+offset)%N];
			this.sequence = shift;
			compute();
		}
 
		// genetate random chromosome
		public void random() {
			for(int i=0;i<N;i++) sequence[i]=i;
			for(int i=0;i<N;i++) {
				int j = random.nextInt(N);
				int swap = sequence[i]; sequence[i]=sequence[j]; sequence[j]=swap;
			}
			compute();
		}
 
		// compute fitness
		public void compute() {
			length = 0;
			for(int i=0;i<N;i++) 
				length+=distance[sequence[i]][sequence[(i+1)%N]];
		}
 
		// compare chromosome
		public boolean equals(DNA other) {
			if (this.length!=other.length) return false;
			if (Arrays.hashCode(this.sequence)!=Arrays.hashCode(other.sequence)) return false;
			return true;
		}
	}
 
	// genetic algorithm
	void run() {
		// old populuation array
		int P = 1000;
		DNA[] oldpop = new DNA[P];
 
		// new population array
		int Q = 5*P;
		DNA[] newpop = new DNA[Q];
 
		// create initial population (random)
		for(int i=0;i<P;i++)
			oldpop[i]=new DNA();
 
		// best result so far
		double bestlength=Double.MAX_VALUE;
 
		// evolution loop
		long t0 = System.currentTimeMillis();
		while(true) {
 
			// create new population
			for(int i=0;i<Q;i++)  {
				// duplicate parent
				newpop[i] = new DNA( oldpop[i%P] );
 
				// mutate/crossover
				int r = random.nextInt(100);
				if (r<20) {
					newpop[i].shift();
				} else if (r<50) {
					newpop[i].mutate();
				} else if (r<100) {
					newpop[i].crossover( oldpop[random.nextInt(P)] );
				}
 
				// ignore duplicates (retry)
				for(int j=0;j<i;j++)
					if (newpop[i].equals(newpop[j])) { i--; break; }
			}
 
			// promote the bests chromosomes as old population
			Arrays.sort(newpop, new Comparator<DNA>() {
				public int compare(DNA dna1, DNA dna2) {
					return (int)Math.signum(dna1.length-dna2.length);
				}
			});
			for(int i=0;i<P;i++) 
				oldpop[i]=newpop[i];
 
			// save/display best result
			if (oldpop[0].length<bestlength) {
				long t1 = System.currentTimeMillis();
				System.out.printf("%.2fs : length=%f  circuit=%s\n",
						(t1-t0)/1000.0, oldpop[0].length, Arrays.toString(oldpop[0].sequence)
				);
				bestlength=oldpop[0].length;
			}
		}
	}
 
	public static void main(String[] args) throws Exception {
		Defi2 defi = new Defi2();
		defi.init();
		defi.run();
	}
}

**Bucketpc** · 30/03/2010, 17h06

Pseudocode:

Pour résoudre ton problème avec les circuit fermés, il faut utiliser l'opérateur de mutation. si tu trouve un circuit fermé, cela veut dire que tu n'as pas passé par toutes les points.

pour améliorer, rajoute une fonction Validate(); pour améliorer les solutions.

il faut aussi implémenter une ou deux fonctions de sélection (Sélection par roulette par exemple).

A+

**pseudocode** · 30/03/2010, 17h17

Envoyé par Bucketpc

Pseudocode:

Pour résoudre ton problème avec les circuit fermés, il faut utiliser l'opérateur de mutation. si tu trouve un circuit fermé, cela veut dire que tu n'as pas passé par toutes les points.

Je passe bien par les 30 planètes. La fermeture du circuit est volontaire de ma part.

(Vu l'énoncé du Defi, je suppose que le postier retourne a son point de départ à la fin de sa tournée

)

**Bucketpc** · 30/03/2010, 17h26

Je passe bien par les 30 planètes. La fermeture du circuit est volontaire de ma part.

(Vu l'énoncé du Defi, je suppose que le postier retourne a son point de départ à la fin de sa tournée )

ah ok, j'ai pas remarqué ça.

le problème des méthodes heuristiques c'est qu'ils donnent des solutions optimale, mais rien ne prouve qu'il n y a pas de plus optimal qu'elles.

Essaye de dérouler l'algorithme plusieurs fois et compare les résultats.

**Bucketpc** · 30/03/2010, 17h31

Je propose de rajouter un peu sur le problème

Imaginez qu'on a des obstacles sur les parcours. Ce qui fait, à partir d'un point donner, on ne peut forcément pas y aller vers tous les points.

Exemple: mettre un obstacle entre 1 et 4, donc on peut pas visiter le point 4 à partir du point 1.

**pseudocode** · 30/03/2010, 17h32

Envoyé par Bucketpc

ah ok, j'ai pas remarqué ça.

le problème des méthodes heuristiques c'est qu'ils donnent des solutions optimale, mais rien ne prouve qu'il n y a pas de plus optimal qu'elles.

Essaye de dérouler l'algorithme plusieurs fois et compare les résultats.

C'est déja fait. Meme avec des populations énormes, des roulettes différentes et beaucoup de générations, je ne suis pas arrivé à aller au dela de 89188.

**Bucketpc** · 30/03/2010, 17h38

C'est vrai ça se peut qu'elle soit la solution globale du système, Mais rien ne peut le prouver

, rien ne peut prouver qu'il y a pas de meilleures solutions qu'elles.

**JeitEmgie** · 30/03/2010, 18h06

Envoyé par pseudocode

j'ai codé un petit algo génétique a la va vite. Ca converge vers une solution en moins d'une minute. Je trouve un circuit fermé de longueur 89188. Mais je ne sais pas si c'est l'optimum.

planètes numérotées de 0 à 29

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
30
31
32
33
34
35
36
37
 
Minimum total distance 87607.91 when starting at 7
 
from 7 we go to 9 (3986.42)
from 9 we go to 2 (2829.64)
from 2 we go to 3 (2488.28)
from 3 we go to 16 (2600.26)
from 16 we go to 24 (3378.65)
from 24 we go to 22 (2998.86)
from 22 we go to 29 (2786.05)
from 29 we go to 20 (2176.55)
from 20 we go to 23 (3785.22)
from 23 we go to 25 (2807.87)
from 25 we go to 17 (5438.04)
from 17 we go to 26 (3604.44)
from 26 we go to 8 (2980.03)
from 8 we go to 21 (1959.24)
from 21 we go to 5 (5070.50)
from 5 we go to 27 (3997.75)
from 27 we go to 18 (2149.77)
from 18 we go to 15 (2916.20)
from 15 we go to 13 (4270.60)
from 13 we go to 11 (1570.82)
from 11 we go to 6 (3665.47)
from 6 we go to 4 (699.26)
from 4 we go to 1 (1019.44)
from 1 we go to 19 (4412.80)
from 19 we go to 12 (3204.87)
from 12 we go to 28 (711.72)
from 28 we go to 14 (1652.99)
from 14 we go to 10 (3673.20)
from 10 we go to 0 (4772.98)
from 0 we go to 7 (14097.20)
 
real	0m0.140s
user	0m0.002s
sys	0m0.003s

**Bucketpc** · 30/03/2010, 18h13

Envoyé par JeitEmgie

planètes numérotées de 0 à 29

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
30
31
32
33
34
35
36
37
 
Minimum total distance 87607.91 when starting at 7
 
from 7 we go to 9 (3986.42)
from 9 we go to 2 (2829.64)
from 2 we go to 3 (2488.28)
from 3 we go to 16 (2600.26)
from 16 we go to 24 (3378.65)
from 24 we go to 22 (2998.86)
from 22 we go to 29 (2786.05)
from 29 we go to 20 (2176.55)
from 20 we go to 23 (3785.22)
from 23 we go to 25 (2807.87)
from 25 we go to 17 (5438.04)
from 17 we go to 26 (3604.44)
from 26 we go to 8 (2980.03)
from 8 we go to 21 (1959.24)
from 21 we go to 5 (5070.50)
from 5 we go to 27 (3997.75)
from 27 we go to 18 (2149.77)
from 18 we go to 15 (2916.20)
from 15 we go to 13 (4270.60)
from 13 we go to 11 (1570.82)
from 11 we go to 6 (3665.47)
from 6 we go to 4 (699.26)
from 4 we go to 1 (1019.44)
from 1 we go to 19 (4412.80)
from 19 we go to 12 (3204.87)
from 12 we go to 28 (711.72)
from 28 we go to 14 (1652.99)
from 14 we go to 10 (3673.20)
from 10 we go to 0 (4772.98)
from 0 we go to 7 (14097.20)
 
real	0m0.140s
user	0m0.002s
sys	0m0.003s

Pourriez vous commenter ce que vous avez fait ? pour qu'on puisse commenter aussi

ça donne quoi avec une population initiale de taille 50individus ? et ça donne quoi si vous changez les méthodes de sélection. Ainsi la manière s'insérer les nouveaux individus dans les nouvelles populations.

**pseudocode** · 30/03/2010, 19h05

Envoyé par JeitEmgie

planètes numérotées de 0 à 29

Code :

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

Minimum total distance 87607.91 when starting at 7

A priori, tu n'as pas compté la dernière distance ( 0 to 7 -> 14097.20) dans ta somme globale. Moi j'ai compté la longueur totale de la boucle fermée.

Je ne sais pas qui de nous deux a raison.

Golgotha ?

**Golgotha** · 30/03/2010, 19h41

c'est la boucle, il faut un circuit fermé.

Mais le 0 to 7 ferme bien la boucle a priori

**JeitEmgie** · 30/03/2010, 19h56

Envoyé par Bucketpc

Je propose de rajouter un peu sur le problème

Imaginez qu'on a des obstacles sur les parcours. Ce qui fait, à partir d'un point donner, on ne peut forcément pas y aller vers tous les points.

Exemple: mettre un obstacle entre 1 et 4, donc on peut pas visiter le point 4 à partir du point 1.

"un peu" ?

c'est justement le fait qu'on ne puisse pas aller partout à partir de n'importe quelle étape qui en fera un problème du type voyageur de commerce…

**JeitEmgie** · 30/03/2010, 20h00

Envoyé par pseudocode

A priori, tu n'as pas compté la dernière distance ( 0 to 7 -> 14097.20) dans ta somme globale. Moi j'ai compté la longueur totale de la boucle fermée.

Je ne sais pas qui de nous deux a raison.

Golgotha ?

non, vous avez raison, il manque la dernière addition quand on détecte la fin du circuit…

**Golgotha** · 31/03/2010, 01h27

Bon, j'ai coder un truc

mon meilleurs résultat pour le moment est : 90334

je pense qu'il peux être amélioré.. je vais encore travaillé dessus.

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
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
 
Module Module1
 
 
 
 
 
 
    Public Class Planete
        Implements ICloneable
 
 
        Public Sub New(ByVal pos_x As Integer, ByVal pos_y As Integer, ByVal pos_z As Integer)
            _pos_x = pos_x
            _pos_y = pos_y
            _pos_z = pos_z
        End Sub
 
        Private _pos_x As Integer
        Private _pos_y As Integer
        Private _pos_z As Integer
 
        Public Property pos_x() As Integer
            Get
                Return _pos_x
            End Get
            Set(ByVal value As Integer)
                _pos_x = value
            End Set
        End Property
 
        Public Property pos_y() As Integer
            Get
                Return _pos_y
            End Get
            Set(ByVal value As Integer)
                _pos_y = value
            End Set
        End Property
 
        Public Property pos_z() As Integer
            Get
                Return _pos_z
            End Get
            Set(ByVal value As Integer)
                _pos_z = value
            End Set
        End Property
 
 
        Public Function Distance_to(ByVal sec_planete As Planete) As Double
 
 
            Dim resultat As Double = 0
 
            Dim part1 As Double = Math.Pow((sec_planete.pos_x - Me.pos_x), 2)
 
            Dim part2 As Double = Math.Pow((sec_planete.pos_y - Me.pos_y), 2)
 
            Dim part3 As Double = Math.Pow((sec_planete.pos_z - Me.pos_z), 2)
 
            Dim Radical As Double = part1 + part2 + part3
 
            resultat = Math.Sqrt(Radical)
 
            Return resultat
 
        End Function
 
        Public Overrides Function Equals(ByVal obj As Object) As Boolean
 
            Return CType(obj, Planete).pos_x = Me.pos_x And CType(obj, Planete).pos_y = Me.pos_y And CType(obj, Planete).pos_z = Me.pos_z
 
        End Function
 
        Public Function Clone() As Object Implements System.ICloneable.Clone
 
            Dim newInstance As New Planete(Me.pos_x, Me.pos_y, Me.pos_z)
            Return newInstance
 
        End Function
    End Class
 
 
    Public Class Chemin
        Inherits List(Of Planete)
        Implements IComparable
 
 
 
 
        Private _taille As Double
 
        Public Property taille() As Double
            Get
                Return _taille
            End Get
            Set(ByVal value As Double)
                _taille = value
            End Set
        End Property
 
        Public Function intit() As Integer
 
            Dim lstOriginal As New Chemin
 
            lstOriginal.Add(New Planete(914, 9904, 1583))
            lstOriginal.Add(New Planete(2371, 7086, 9327))
            lstOriginal.Add(New Planete(6266, 5886, 6028))
            lstOriginal.Add(New Planete(4451, 7026, 7292))
            lstOriginal.Add(New Planete(1573, 6693, 8829))
            lstOriginal.Add(New Planete(8875, 18, 5462))
            lstOriginal.Add(New Planete(1582, 6028, 8613))
            lstOriginal.Add(New Planete(9426, 2272, 9831))
            lstOriginal.Add(New Planete(6310, 2007, 903))
            lstOriginal.Add(New Planete(6896, 5130, 8681))
            lstOriginal.Add(New Planete(4086, 6387, 991))
            lstOriginal.Add(New Planete(2897, 2825, 9816))
            lstOriginal.Add(New Planete(851, 5771, 2018))
            lstOriginal.Add(New Planete(3020, 1260, 9760))
            lstOriginal.Add(New Planete(570, 5348, 766))
            lstOriginal.Add(New Planete(3168, 1099, 5495))
            lstOriginal.Add(New Planete(4893, 9563, 7652))
            lstOriginal.Add(New Planete(7634, 4480, 3935))
            lstOriginal.Add(New Planete(5114, 1487, 7632))
            lstOriginal.Add(New Planete(1752, 6060, 5080))
            lstOriginal.Add(New Planete(8425, 9370, 757))
            lstOriginal.Add(New Planete(7346, 365, 640))
            lstOriginal.Add(New Planete(6302, 8676, 3868))
            lstOriginal.Add(New Planete(9013, 8025, 4246))
            lstOriginal.Add(New Planete(3444, 8561, 4769))
            lstOriginal.Add(New Planete(8853, 8857, 6923))
            lstOriginal.Add(New Planete(9065, 3143, 909))
            lstOriginal.Add(New Planete(5407, 2004, 5566))
            lstOriginal.Add(New Planete(1030, 6451, 1908))
            lstOriginal.Add(New Planete(7055, 7782, 1339))
 
 
 
            Randomize()
            Dim lstNew As New Chemin
 
            While lstOriginal.Count > 0
                Dim idx As Integer = rnd.Next(0, lstOriginal.Count - 1)
 
 
                Me.Add(lstOriginal(idx))
                lstOriginal.RemoveAt(idx)
            End While
 
            Me.calc_taille()
 
            Return 0
 
        End Function
 
 
        Public Function calc_taille() As Double
 
 
            Me.taille = 0
 
            For i As Integer = 0 To Me.Count - 2
 
 
                Me.taille = Me.taille + Me(i).Distance_to(Me(i + 1))
 
 
            Next
 
            Me.taille = Me.taille + Me(Me.Count - 1).Distance_to(Me(0))
 
        End Function
 
 
        Public Function mute(ByVal pere As Chemin) As Chemin
 
            Dim enfant As New Chemin()
 
 
            Dim break_1 As Integer = rnd.Next(0, pere.Count - 1)
            Dim break_2 As Integer = rnd.Next(break_1, pere.Count - 1)
 
            For index As Integer = 0 To break_1
 
                enfant.Add(pere(index).Clone)
 
            Next
 
            Dim i As Integer = enfant.Count - 1
 
            While enfant.Count < break_2
 
                If Not enfant.Contains(Me(i)) Then
                    enfant.Add(Me(i).Clone)
                End If
 
 
                If i < Me.Count - 1 Then
 
                    i = i + 1
 
                Else
 
                    i = 0
 
 
                End If
 
            End While
 
            While enfant.Count < pere.Count
 
                If Not enfant.Contains(pere(i)) Then
                    enfant.Add(pere(i).Clone)
                End If
 
 
                If i < pere.Count - 1 Then
 
                    i = i + 1
 
                Else
 
                    i = 0
 
 
                End If
 
            End While
 
 
            Return enfant
 
 
        End Function
 
 
        Public Function CompareTo(ByVal obj As Object) As Integer Implements System.IComparable.CompareTo
            Return Me.taille.CompareTo(CType(obj, Chemin).taille)
        End Function
    End Class
 
 
    Public rnd As New Random
 
 
    Public Class population
        Inherits List(Of Chemin)
 
        Private nb_pop
 
        Public Sub New(ByVal nb_individu As Integer)
 
            For index As Integer = 0 To nb_individu
 
                nb_pop = nb_individu
                Randomize()
                Me.Add(New Chemin())
                Me(index).intit()
 
 
            Next
 
        End Sub
 
 
        Public Function darwin_go(ByVal nb_gene) As Integer
            Dim best As Double = 0
            Dim _old_best As Double = 0
 
            Console.Write("---début----")
            Console.Write(vbCrLf)
            For i As Integer = 1 To nb_gene
 
 
 
 
                Dim nb_champions As Integer = 350
 
 
                Me.Sort()
 
                best = Me(0).taille
 
                If Not _old_best.Equals(best) Then
                    _old_best = Me(0).taille
                    Console.Write("la meilleur taille à changé (itération n° " & i & ") : " & Me(0).taille)
                    Console.Write(vbCrLf)
                End If
 
                Dim _ex As New List(Of Chemin)
 
                For index As Integer = Me.Count - 1 To nb_champions Step -1
                    'on enleve les moins bons
                    _ex.Add(Me(index))
                    Me.RemoveAt(index)
 
                Next
 
                Me.Finalize()
                Randomize()
                For index As Integer = nb_champions To nb_pop
                    Dim X As Integer = rnd.Next(0, nb_champions - 1)
                    Dim Y As Integer = rnd.Next(0, nb_pop - nb_champions - 1)
                    Dim child As Chemin
                    child = Me(X).mute(_ex(Y))
                    child.calc_taille()
                    Me.Add(child)
                Next
 
 
            Next
            Console.Write("---Fin----")
            Console.Write(vbCrLf)
 
                Return Me(0).taille
 
 
        End Function
 
 
 
 
 
    End Class
 
    Sub Main()
 
 
 
        Dim n As New population(2000)
 
        n.darwin_go(1000)
 
        Console.Read()
 
 
 
    End Sub
 
End Module

un exemple de sortie :

---début----
la meilleur taille à changé (itération n° 1) : 167943,422497821
la meilleur taille à changé (itération n° 3) : 166803,886434155
la meilleur taille à changé (itération n° 4) : 163655,260192314
la meilleur taille à changé (itération n° 6) : 159561,168087194
la meilleur taille à changé (itération n° 9) : 153907,67809602
la meilleur taille à changé (itération n° 18) : 148310,756572416
la meilleur taille à changé (itération n° 24) : 146055,742381058
la meilleur taille à changé (itération n° 25) : 143876,557850289
la meilleur taille à changé (itération n° 28) : 139925,565329304
la meilleur taille à changé (itération n° 31) : 136317,332782553
la meilleur taille à changé (itération n° 43) : 135886,622773987
la meilleur taille à changé (itération n° 49) : 135345,43403493
la meilleur taille à changé (itération n° 56) : 131069,080268595
la meilleur taille à changé (itération n° 71) : 130103,509699679
la meilleur taille à changé (itération n° 74) : 126322,692250598
la meilleur taille à changé (itération n° 92) : 125067,228742221
la meilleur taille à changé (itération n° 94) : 121427,846123126
la meilleur taille à changé (itération n° 116) : 116768,614184877
la meilleur taille à changé (itération n° 133) : 114227,330232911
la meilleur taille à changé (itération n° 161) : 114119,062748768
la meilleur taille à changé (itération n° 163) : 110419,928424106
la meilleur taille à changé (itération n° 167) : 110208,891838907
la meilleur taille à changé (itération n° 169) : 108187,832547989
la meilleur taille à changé (itération n° 197) : 107478,560251179
la meilleur taille à changé (itération n° 200) : 106068,708540253
la meilleur taille à changé (itération n° 210) : 105991,264539493
la meilleur taille à changé (itération n° 220) : 103294,43306071
la meilleur taille à changé (itération n° 273) : 102903,636223672
la meilleur taille à changé (itération n° 277) : 99417,3989349055
la meilleur taille à changé (itération n° 331) : 98923,4168314096
la meilleur taille à changé (itération n° 344) : 98712,6473342078
la meilleur taille à changé (itération n° 349) : 98082,0765195518
la meilleur taille à changé (itération n° 358) : 97924,6473407836
la meilleur taille à changé (itération n° 359) : 94413,1112056818
la meilleur taille à changé (itération n° 394) : 94175,4770003541
la meilleur taille à changé (itération n° 395) : 93751,8626534837
la meilleur taille à changé (itération n° 403) : 93727,1325859686
la meilleur taille à changé (itération n° 406) : 93009,700789242
la meilleur taille à changé (itération n° 437) : 92779,4624017051
---Fin----

**JeitEmgie** · 31/03/2010, 22h11

Envoyé par Bucketpc

Pourriez vous commenter ce que vous avez fait ? pour qu'on puisse commenter aussi

je regarde simplement si la solution bête et méchante donne des résultats acceptables… et à quelle vitesse…

on part de chaque planète en allant toujours à la plus proche non encore visitée… et à la fin on garde le chemin le plus court… (donc on prend le plus court parmi seulement N chemins examinés… ce qui est très peu par rapport au nombre total de solutions possibles…)

ce qui donne pour le jeu de données en exemple, un chemin <10% moins bon que la solution par l'algorithme génétique… mais au moins de 2 ordres de grandeur plus rapide…

**Bucketpc** · 01/04/2010, 00h59

Envoyé par JeitEmgie

je regarde simplement si la solution bête et méchante donne des résultats acceptables… et à quelle vitesse…

on part de chaque planète en allant toujours à la plus proche non encore visitée… et à la fin on garde le chemin le plus court… (donc on prend le plus court parmi seulement N chemins examinés… ce qui est très peu par rapport au nombre total de solutions possibles…)

ce qui donne pour le jeu de données en exemple, un chemin <10% moins bon que la solution par l'algorithme génétique… mais au moins de 2 ordres de grandeur plus rapide…

Code :

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

on part de chaque planète en allant toujours à la plus proche non encore visitée… et à la fin on garde le chemin le plus court

Au fait, le problème d'optimisation ne consiste pas à y aller chaque fois au point le plus proche

. cette solution ne peut jamais être juste ni raisonnable, sauf s'il existe un chemin ayant toutes les plus petites valeurs dans le graphe.

**Sylvain Togni** · 01/04/2010, 11h18

Histoire de faire avancer le défi, je viens de coder un solveur exact qui utilise l'algorithme de Little, un algorithme de type branch & bound.

Sauf erreur de ma part la meilleure solution à une longueur de 89188.6, apparemment comme celle trouvée par pseudocode avec son algorithme génétique (bravo !).

11=> 13 1570.82
13=> 18 4564.94
18=> 15 7481.14
15=> 27 9897.17
27=> 17 13605.3
17=> 26 17209.7
26=> 8 20189.8
8=> 21 22149
21=> 5 27219.5
5=> 7 32166.5
7=> 9 36152.9
9=> 2 38982.5
2=> 3 41470.8
3=> 16 44071.1
16=> 25 48159
25=> 23 50966.9
23=> 22 53780.5
22=> 20 57610.2
20=> 29 59786.8
29=> 10 63085.6
10=> 14 66758.8
14=> 12 68109.9
12=> 28 68821.6
28=> 0 72291.8
0=> 24 76576.1
24=> 19 79611.6
19=> 6 83148.8
6=> 4 83848.1
4=> 1 84867.5
1=> 11 89188.6

L'algorithme prend environ 5 secondes pour trouver la meilleure solution, il a été codé en C++ :

Code C++ :

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
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
#include <iostream>
#include <cmath>
#include <cfloat>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <vector>
#include <set>
 
// Planete
 
struct Planete
{
  std::string nom;
  int x, y, z;
};
 
std::istream& operator>>(std::istream& src, Planete& p)
{
  std::getline(src, p.nom, ':');
  char c;
  return src >> p.x >> c >> p.y >> c >> p.z >> c;
}
 
double distance(Planete const& p1, Planete const& p2)
{
  double dx = p1.x - p2.x;
  double dy = p1.y - p2.y;
  double dz = p1.z - p2.z;
  return std::sqrt(dx*dx + dy*dy + dz*dz);
}
 
// Algorithme de little
 
typedef std::pair<int, int> Edge;
 
class Node
{
public:
  Node(int size)
    : myMatrix(size, std::vector<double>(size, DBL_MAX))
    , myRows(size)
    , myCols(size)
    , myLowerBound(0.0)
  {
    for(int i = 0; i < size; ++i)
      myRows[i] = myCols[i] = i;
  }
 
  bool operator<(Node const& other) const
  {
    return myLowerBound < other.myLowerBound
      || (myLowerBound == other.myLowerBound && myEdges.size() > other.myEdges.size());
  }
 
  int getSize() const {return int(myRows.size());}
  int getEdgeCount() const {return int(myEdges.size());}
  Edge const& getEdge(int i) const {return myEdges[i];}
  double getDistance(int i, int j) const {return myMatrix[i][j];}
  double getLowerBound() const {return myLowerBound;}
 
  void setDistance(int i, int j, double d)
  {
    myMatrix[i][j] = d;
  }
 
  Node& bound()
  {
    // Réduction des lignes
    for(int i = 0; i < int(myRows.size()); i++)
    {
      double min = DBL_MAX;
      for(int j = 0; j < int(myCols.size()); j++)
        min = std::min(min, myMatrix[i][j]);
      for(int j = 0; j < int(myCols.size()); j++)
        myMatrix[i][j] -= min;
      myLowerBound += min;
    }
 
    // Réduction des colonnes
    for(int j = 0; j < int(myCols.size()); j++)
    {
      double min = DBL_MAX;
      for(int i = 0; i < int(myRows.size()); i++)
        min = std::min(min, myMatrix[i][j]);
      for(int i = 0; i < int(myRows.size()); i++)
        myMatrix[i][j] -= min;
      myLowerBound += min;
    }
    return *this;
  }
 
  double choseEdge(int& iMax, int& jMax) const
  {
    // Recherche de l'arc dont la non-inclusion entraine la plus forte penalité
    double penaltyMax = -1.0;
    for(int i = 0; i < int(myRows.size()); i++)
    {
      for(int j = 0; j < int(myCols.size()); j++)
      {
        if (myMatrix[i][j] == 0.0)
        {
          double penalty1 = DBL_MAX;
          for(int k = 0; k < int(myCols.size()); k++)
          {
            if (k != j)
              penalty1 = std::min(penalty1, myMatrix[i][k]);
          }
          double penalty2 = DBL_MAX;
          for(int k = 0; k < int(myRows.size()); k++)
          {
            if (k != i)
              penalty2 = std::min(penalty2, myMatrix[k][j]);
          }
          double penalty = penalty1 + penalty2;
          if (penalty > penaltyMax)
          {
            penaltyMax = penalty;
            iMax = i;
            jMax = j;
          }
        }
      }
    }
    return penaltyMax;
  }
 
  void removeRow(int i)
  {
    myRows.erase(myRows.begin() + i);
    myMatrix.erase(myMatrix.begin() + i);
  }
 
  void removeCol(int j)
  {
    myCols.erase(myCols.begin() + j);
    for(int i = 0; i < int(myRows.size()); ++i)
      myMatrix[i].erase(myMatrix[i].begin() + j);
  }
 
  int findRow(int row) const
  {
    for(int i = 0; i < int(myRows.size()); ++i)
    {
      if (myRows[i] == row)
        return i;
    }
    return -1;
  }
 
  int findCol(int col) const
  {
    for(int j = 0; j < int(myCols.size()); ++j)
    {
      if (myCols[j] == col)
        return j;
    }
    return -1;
  }
 
  void removeCycle(int row, int col)
  {
    // Extrémité de départ
    int start = row;
    for(int i = 0; i < int(myEdges.size()); ++i)
    {
      if (myEdges[i].second == start)
      {
        start = myEdges[i].first;
        i = -1; // restart
      }
    }
 
    // Extrémité de fin
    int end = col;
    for(int i = 0; i < int(myEdges.size()); ++i)
    {
      if (myEdges[i].first == end)
      {
        end = myEdges[i].second;
        i = -1; // restart
      }
    }
 
    // Suprrime la possibilité de sous-cycle
    end = findRow(end);
    start = findCol(start);
    setDistance(end, start, DBL_MAX);
  }
 
  void branch(std::set<Node>& queue)
  {
    int iMax, jMax;
    double penalty = choseEdge(iMax, jMax);
 
    // Non-choix de l'arc (iMax, jMax)
    if (penalty < DBL_MAX)
    {
      Node node(*this);
      node.setDistance(iMax, jMax, DBL_MAX);
      queue.insert(node.bound());
    }
 
    // Choix de l'arc (iMax, jMax)
    int row = myRows[iMax];
    int col = myCols[jMax];
    removeRow(iMax);
    removeCol(jMax);
    int i = findRow(col);
    int j = findCol(row);
    if (i >= 0 && j >= 0)
      setDistance(i, j, DBL_MAX);
    if (getSize() > 1)
      removeCycle(row, col);
    myEdges.push_back(Edge(row, col));
    queue.insert(bound());
  }
 
  void makePath()
  {
    // Ferme le chemin
    myEdges.push_back(Edge(myRows[0], myCols[0]));
 
    // Réordonne les arcs
    for(int i = 0; i < int(myEdges.size()); ++i)
    {
      for(int j = i; j < int(myEdges.size()); ++j)
      {
        if (myEdges[j].first == myEdges[i].second)
        {
          std::swap(myEdges[j], myEdges[i + 1]);
          break;
        }
      }
    }
  }
 
private:
  std::vector<std::vector<double> >
                        myMatrix;
  std::vector<int>      myRows;
  std::vector<int>      myCols;
  std::vector<Edge>     myEdges;
  double                myLowerBound;
};
 
int main()
{
  // Coordonnées des planètes
  std::istringstream data(
    "P-1:914,9904,1583;"
    "P-2:2371,7086,9327;"
    "P-3:6266,5886,6028;"
    "P-4:4451,7026,7292;"
    "P-5:1573,6693,8829;"
    "P-6:8875,18,5462;"
    "P-7:1582,6028,8613;"
    "P-8:9426,2272,9831;"
    "P-9:6310,2007,903;"
    "P-10:6896,5130,8681;"
    "P-11:4086,6387,991;"
    "P-12:2897,2825,9816;"
    "P-13:851,5771,2018;"
    "P-14:3020,1260,9760;"
    "P-15:570,5348,766;"
    "P-16:3168,1099,5495;"
    "P-17:4893,9563,7652;"
    "P-18:7634,4480,3935;"
    "P-19:5114,1487,7632;"
    "P-20:1752,6060,5080;"
    "P-21:8425,9370,757;"
    "P-22:7346,365,640;"
    "P-23:6302,8676,3868;"
    "P-24:9013,8025,4246;"
    "P-25:3444,8561,4769;"
    "P-26:8853,8857,6923;"
    "P-27:9065,3143,909;"
    "P-28:5407,2004,5566;"
    "P-29:1030,6451,1908;"
    "P-30:7055,7782,1339;");
 
  // Lecture des planetes
  std::vector<Planete> planetes(
    (std::istream_iterator<Planete>(data)),
    std::istream_iterator<Planete>());
  std::cout << planetes.size() << " planètes lues\n";
 
  // Calcul des distances inter-planètes
  Node node(int(planetes.size()));
  for(int i = 0; i < int(planetes.size()); ++i)
  {
    for(int j = 0; j < int(planetes.size()); ++j)
    {
      if (i != j)
        node.setDistance(i, j, distance(planetes[i], planetes[j]));
    }
  }
 
  // Recherche du plus court chemin par l'algorithm de Little
  std::set<Node> queue;
  queue.insert(Node(node).bound());
  while(!queue.empty())
  {
    Node best(*queue.begin());
    queue.erase(queue.begin());
    if (best.getSize() == 1)
    {
      best.makePath();
      std::cout << "Meilleur chemin : " << best.getLowerBound() << '\n';
      double d = 0;
      for(int i = 0; i < best.getEdgeCount(); ++i)
      {
        d += node.getDistance(best.getEdge(i).first, best.getEdge(i).second);
        std::cout << best.getEdge(i).first << "=>\t" << best.getEdge(i).second << '\t' << d << '\n';
      }
      break;
    }
    best.branch(queue);
  }
}

**JeitEmgie** · 01/04/2010, 16h12

Envoyé par Bucketpc

Code :

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

on part de chaque planète en allant toujours à la plus proche non encore visitée… et à la fin on garde le chemin le plus court

Au fait, le problème d'optimisation ne consiste pas à y aller chaque fois au point le plus proche

. cette solution ne peut jamais être juste ni raisonnable, sauf s'il existe un chemin ayant toutes les plus petites valeurs dans le graphe.

… certes… je n'ai jamais eu de doute là-dessus…

je voulais juste voir ce que çà donne… en terme de rapidité et de "qualité"… par rapport aux solutions optimales…