Contribution à l'optimisation complexe par des techniques de swarm intelligence

2.3.4 Etude expérimentale

Afin d'améliorer les performances de DPSO, une procédure de recherche locale déterministe est appliquée à chaque itération. L'idée de base est de ramener chaque solution à son minimum local utilisant une heuristique d'optimisation locale déterministe [Li, 1995]. Cette heuristique consiste en le choix, pour chaque cellule violant les contraintes électromagnétiques, d'un canal qui valide les différentes contraintes. Les nouvelles solutions constituent les particules de la génération courante.

Le Tableau (2.1) présente les différentes caractéristiques des problèmes étudiés. Ces caractéristiques incluent le vecteur de demande en canaux (D), la matrice de contraintes électromagnétiques (C), le nombre de cellules et le nombre de fréquences disponibles. Le vecteur de demande spécifie le nombre de canaux requis par chaque cellule. Le nombre total de demande (Dtot) représente la somme des éléments de D. Ces différents vecteurs caractéristiques sont illustrés par la figure (2.12).

TAB. 2.1 - Caractéristiques des problèmes étudiés

Probleme #	No. de cellules	No. de canaux valables	Matrice de Compatibilités (C)	Vecteur de demande (D)
1	4	11	C1	D1
2	25	73		D2
3	21	381	C3	D3
4	21	533	C4	D3
5	21	533	C5	D3
6	21	221	C3	D4
7	21	309	C4	D4
8	21	309	C5	D4

FIG. 2.12 - Vecteurs caractéristiques des problèmes étudiés

Les résultats de simulation obtenus pour quelques instances des problèmes spécifiés ci-dessus sont présentés. Il faut noter que les paramètres de l'algorithme sont donnés par la taille de population et le nombre maximum de générations.

Problème #1

Ce problème est relativement simple à résoudre, l'algorithme DPSO est appliqué à une population de 10 individus évoluant durant 10 générations. Le tableau (2.2) présente les différentes affectations de fréquences associées à chaque cellule. Les solutions obtenues montrent que les contraintes de compatibilités électromagnétiques sont toutes validées. Il faut noter que plusieurs solutions ont été obtenues pour ce problème, ces solutions diffèrent uniquement par l'affectation de fréquences des trois premières cellules. En effet, l'affectation de fréquences pour la quatrième cellule illustrée par le tableau (2.2) représente la solution unique qui ne viole pas les interférences de type co-cellule.

TAB. 2.2 Fréquences affectées aux différentes cellules du problème #1

Cel.#	Canaux affectés
1	3
2	7
3	2
4	10	5	0

Problème #2

Le tableau (2.3) représente la solution associée au problème #2. Ce problème est caractérisé par 25 cellules dont le nombre total de demande en fréquences est de 167, alors que le nombre de fréquences disponibles est 73. Pour ce problème, 10 individus qui évoluent durant 10 générations sont utilisés pour l'exécution de l'algorithme DPSO.

TAB. 2.3 - Canaux alloués aux différentes cellules du problème #2

Cel.#	Canaux affectés
1	53	44	57	0	2	4	6	8	10	12
2	3	5	7	9	11	13	15	17	20	22	24
3	14	19	23	28	30	21	32	26	34
4	0	2	4	6	9
5	1	27	29	33	35	41	43	38	46
6	0	2	4	6
7	27	29	31	33	35
8	36	38	41	1	46	52	54
9	3	5	11	7
10	42	40	55	63	67	48	50	69
11	8	12	22	17	51	59	49	62
12	18	49	51	64	68	58	62	45	70
13	56	44	53	61	16	65	44	44	71	57
14	52	36	39	54	47	60	66
15	14	21	23	18	25	28	31
16	0	2	4	6	9	11
17	3	1	5	7
18	10	13	15	19	26
19	20	29	34	32	37
20	3	7	24	33	35	38	40
21	6	13	4	16	19	9
22	0	2	10	26
23	1	11	18	14	21
24	13	19	15	23	25	27	29
25	16	24	28	30	32

Problème #3

Ce problème est plus compliqué que les autres instances en termes du nombre total de demande en fréquences (= 481 canaux requis). En plus, les contraintes cocellule, données par les éléments diagonaux de la matrice, sont peu élevées (=5). Le nombre d'individus utilisé dans ce cas est fixé à 40 et le nombre maximum de générations égal à 30. Le tableau (2.4) présente les canaux affectés à chacune des 21

cellules. Les fréquences allouées à chaque cellule valident toutes les contraintes de compatibilités électromagnétiques.

TAB. 2.4 - Canaux alloués aux différentes cellules du problème #3

Cel.#	Canaux affectés
1	127	1	6	11	16	21	26	31
2	187	2	7	12	17	22	27	37	42	47	52	57	62	67
	72	77	82	87	92	97	102	107	112	117
3	122	3	8	13	18	23	28	33
4	61	1	6	11	16	21	26	31
5	40	0	5	10	15	20	25	30
6	79	0	5	10	15	20	25	30	35	40	45	50	55	60
	65
7	122	3	8	13	18	23	28	33	38	43	48	53	58	63
	68	73	78	83
8	284	4	9	14	19	41	46	51	56	61	66	71	76	81
	86	91	96	101	106	111	116	121	126	131	136	141	146	151
	156	161	166	171	176	181	186	191	196	201	206	211	216	221
	226	231	236	241	246	251	256	261	266	271
9	0	5	10	15	20	25	30	35	40	45	50	55	60	65
	70	75	80	85	90	95	100	105	110	115	120	125	130	135
	140	145	150	155	160	165	170	175	180	185	190	195	200	205
	210	215	220	225	230	235	240	245	250	255	260	265	270	275
	280	285	290	295	300	305	310	315	320	325	330	335	340	345
	350	355	360	365	370	375	380
10	36	43	48	53	58	63	68	73	78	83	88	93	98	103
	108	113	118	123	128	133	138	143	148	153	158	163	168	173
11	67	2	7	12	17	22	27	32	37	42	47	52	57
12	79	3	8	13	18	23	28	33	38	44	49	54	59	64
	69
13	156	1	6	11	16	21	26	31	36	41	46	51	56	61
	66	71	76	81	86	91	96	101	106	111	116	121	126	131
	136	141	146
14	32	2	7	12	17	22	27	37	52	57	62	67	72	77
	82
15	88	207	212	217	222	227	232	237	242	247	252	257	262	267
	272	93	98	103	108	113	118	123	128	133	138	143	148	153
	158	163	168	173	178	183	188	193
16	301	306	24	29	34	39	44	49	54	59	64	69	74	79
	84	89	94	99	104	109	114	119	124	129	134	139	144	149
	154	159	164	169	174	179	184	189	194	199	204	209	214	219
	224	229	234	239	244	249	254	259	264	269	274	311	279	286
	291
17	192	127	132	137	142	147	152	157	162	167	172	177	182	197
	202	208	213	218	223	228	233	238	243	248	253	258	263	268
18	66	4	9	14	19	41	46	51
19	87	1	6	11	16	21	26	31	36	42
20	47	2	7	12	17	22	27	32	37	52	57	62	67
21	56	3	8	13	18	23	28	33

On peut constater que la 9^ème cellule (tableau 2.4), caractérisée par le plus grand nombre de demande en fréquences (=77), exploite l'ensemble du spectre disponible sans violer les contraintes de compatibilités. En effet, la complexité de ce problème réside dans le fait que pour la neuvième cellule, il existe une solution unique qui évite toute violation de contraintes de type co-cellule, alors que le reste des contraintes doivent être validées par les autres cellules.

Problème #6

Pour ce problème, Le nombre de cellules est 21, le spectre disponible est [0...220], le nombre total de demande en canaux est 470. L'algorithme DPSO est appliqué à une population de 60 individus évoluant durant 30 générations. La solution finale obtenue à la convergence de DPSO est présentée dans le tableau (2.5).

TAB. 2.5 - Canaux alloués aux différentes cellules du problème #6

Cel.#	Canaux affectés
1	20	53	0	5	10
2	23	49	1	6	13
3	63	68	2	8	14
4	36	41	3	9	48	16	21	26
5	73	51	58	66	1	6	11	18	23	28	33	38
6	135	120	1	6	125	12	17	22	27	32	37	42	47	52
	57	62	67	72	77	82	87	92	97	102	107
7	96	63	2	7	14	19	24	29	34	39	44	50	55	68
	73	78	83	88	101	108	117	122	127	132	137	142	147	152
	157	162
8	136	76	3	9	16	21	26	31	36	41	46	51	56	61
	66	71	81	86	91	141	146	103	111	116	121
9	190	185	4	11	25	30	35	40	45	70	75	80	85	90
	95	100	105	110	115	120	125	130	135	140	145	150	155	160
	165	170
10	197	202	207	7	12	17	22	27	32	37	42	47	52	57
	62	67	72	77	82	87	92	97	102	107	112	117	122	127
	132	137	142	147	152	157	162	167	172	177	182	187
11	13	19	24	29	219	44	49	54	59	64	69	74	79	84
	89	94	99	104	109	114	119	124	129	134	139	144	149	154
	159	164	169	174	179	184	189	194	199	204	209	214
12	0	5	10	15	20	25	30	35	40	45	50	55	60	65
	70	75	80	85	90	95	100	105	110	115	120	125	130	135
	140	145	150	155	160	165	170	175	180	185	190	195	200	205
	210	215	220
13	98	103	0	5	10	15	20	25	30	35	40	45	51	56
	61	66	71	76	81	86
14	174	179	4	11	18	23	49	54	59	64	69	74	79	84
	89	94	99	104	109	114	119	124	129	134	139	144	149	154
	159	164
15	188	106	8	58	65	193	198	203	208	213	218	112	118	123
	128	133	138	143	148	153	158	163	168	173	178
16	151	60	131	28	33	38	43	48	156	161	166	171	180	189
	194
17	93	98	0	5	10	15	20	50	55	175	181	186	191	196
	201
18	61	76	81	34	39	86	46	188	53	193	198	71	203	208
	91	213	218	103	111	116	121	126	136	141	146	153	158	163
	168	173
19	97	102	1	6	12	17	22	27	32	37	42	47	52	57
	62	67	72	77	82	87
20	119	109	2	13	18	23	29	44	49	54	59	64	69	74
	79	84	89	94	99	104
21	143	96	3	8	14	21	26	31	36	41	51	56	63	68
	73	78	83	88	101	106	113	118	123	128	133

Problème #8

Pour ce système cellulaire de 21 cellules, le spectre disponible est [0...308], le nombre total de demande en canaux est 470. Le nombre des contraintes co-cellule est égal à 7. Le tableau (2.6) présente la solution obtenue utilisant une population de 60 individus qui évolue durant 30 générations.

TAB. 2.6 - Canaux alloués aux différentes cellules du problème #8

Cel.#	Canaux affectés
1	47	5	12	19	26
2	0	7	14	23	30
3	69	76	41	48	55
4	22	29	89	96	103	117	1	8
5	173	180	187	31	110	17	3	10	24	61	68	75
6	200	156	193	165	172	182	0	8	15	22	29	36	43	50
	57	64	71	78	85	92	99	106	117	124	131
7	138	145	152	159	238	250	2	10	17	24	31	38	45	52
	59	66	73	80	87	94	101	108	115	180	187	195	202	209
	216	223
8	28	229	21	56	35	42	49	63	70	77	84	91	98	111
	118	128	161	168	175	236	286	243	252	259	266
9	172	179	186	263	270	256	249	4	11	18	25	32	39	46
	53	60	67	74	81	88	95	102	109	116	123	130	137	144
	151	158
10	36	288	6	13	295	302	43	50	57	64	71	78	85	92
	99	113	120	127	134	141	148	155	162	169	176	183	190	197
	204	211	267	274	281
11	269	276	283	290	19	297	304	26	38	45	52	59	66	73
	80	87	94	101	108	115	122	129	136	143	150	157	164	171
	178	185	241	248	255
12	0	7	14	21	28	35	42	49	56	63	70	77	84	91
	98	105	112	119	126	133	140	147	154	161	168	175	182	189
	196	203	259	266	273	280	287	294	301	308
13	121	128	135	142	149	102	3	11	18	25	32	39	46	53
	60	67	74	81	88	95
14	225	190	197	204	211	218	6	13	20	27	34	41	48	55
	62	69	76	83	90	97	104	112	119	126	133	140	147	154
	162	169
15	248	122	136	143	150	157	164	171	178	185	192	199	206	213
	220	227	234	241	255	262	269	276	283	290	297
16	273	245	125	132	139	181	1	8	15	189	196	203	210	217
	224
17	174	277	284	291	193	200	20	27	62	207	214	221	105	228
	235
18	293	286	188	131	138	124	195	2	9	16	23	202	33	40
	47	54	209	216	223	230	237	244	251	258	265	272	279	145
	152	159
19	113	120	127	134	141	148	5	12	19	26	33	40	47	54
	61	71	78	85	92	99
20	108	115	129	160	146	153	3	10	17	24	31	38	45	52
	59	66	73	80	87	94
21	163	170	177	184	191	198	0	7	14	29	42	49	56	68
	75	82	89	96	103	110	117	126	133	140	149