8. Comparaisons des algorithmes

Sun Woong Kim, Steven G. Heeringa et Peter W. Solenberger

Précédent | Suivant

En utilisant les quatre problèmes de sélection contrôlée mentionnés à la section 2, nous présentons certains résultats produits par les deux méthodes en utilisant $d_2^{*}$  et $d_{\infty }^{*}$  dans le nouvel algorithme, et en comparant les solutions données par ces méthodes aux solutions générées sous les algorithmes décrits antérieurement par Jessen (1970), Jessen (1978), Causey et coll. (1985), Huang et Lin (1998) et Winkler (2001). Les solutions produites par les deux méthodes en utilisant $d_2^{*}$  et $d_{\infty }^{*}$  ont été obtenues avec le SOCSLP, avec la version 9.2 de SAS/OR (2008). Les solutions de l’algorithme de Sitter et Skinner (1994) en utilisant la programmation linéaire ont également été obtenues en utilisant PROC LP de la version 9.2 de SAS/OR (2008). Les solutions pour les autres méthodes sont les résultats qui ont été publiés dans les articles originaux.

Les réponses à deux questions nous aident à comparer les algorithmes : 1) les solutions issues des nouvelles méthodes diffèrent-elles de celles fournies par les algorithmes antérieurs décrits à la section 5? 2) les solutions issues des nouvelles méthodes donnent-elles pour les tableaux optimaux des probabilités de sélection plus élevées que celles générées en utilisant les méthodes antérieures?

Avant de comparer les algorithmes, nous devons examiner les résultats du tableau 8.1 obtenus au moyen des deux méthodes. Dans le tableau, la méthode utilisant $d_2^{*}$  et celle utilisant $d_{\infty }^{*}$  sont désignées par $N_2$  et $N_{\infty }$ , respectivement. Étant donné que, quand ils sont calculés avec $d_2^{*}$  ( $d_{\infty }^{*}$  ), les tableaux ayant la même valeur de distance se trouvent dans le même groupe, il existera des groupes différents pour tous les tableaux possibles (voir la remarque 6.2). Soit $G$  le nombre de groupes différents. En outre, soit $FO$  la valeur réelle de la fonction objectif (6.5) ou (6.6) et $t$ , le nombre réel de $T$ , le nombre de transitions, présenté à la section 6.3. Ces valeurs sont toutes obtenues au moyen du SOCSLP, et $t$  en particulier indique le nombre d’itérations aux phases 1 et 2 de PROC LP dans le logiciel.

Tableau 8.1
Résultats obtenus avec les nouvelles méthodes
Sommaire du tableau
Le tableau montre les résultats de Résultats obtenus avec les nouvelles méthodes Problème 2.1, Problème 2.2, Problème 2.3 et Problème 2.4, calculées selon $N_2$ et $N_{\infty }$ unités de mesure (figurant comme en-tête de colonne).

	Problème 2.1		Problème 2.2		Problème 2.3		Problème 2.4
	$N_2$	$N_{\infty }$	$N_2$	$N_{\infty }$	$N_2$	$N_{\infty }$	$N_2$	$N_{\infty }$
$G$	4	3	9	2	6	2	157	14
$FO$	1,336	0,620	1,689	0,640	1,582	0,720	1,661	0,701
$t$	2	2	8	6	18	15	43	41

Comme le montre le tableau, la plupart des valeurs de $G$  sont beaucoup plus petites que celles de $L$ , le nombre total de tableaux possibles donné dans le tableau 6.1, sauf dans le cas de la grande valeur de « 157 » pour le problème 2.4, qui découle simplement du fait que les valeurs de $a_{ij}$  sont données à trois décimales près. Lorsqu’on utilise $d_2^{*}$ , les valeurs de $FO$  varient entre 1 et 2, tandis qu’elles sont toujours inférieures à 1 lorsqu’on utilise $d_{\infty }^{*}$ . La plupart des valeurs de $t$  n’atteignent pas l’IC à 95 % de $T$  indiqué au bas du tableau 6.1. Donc, les demandes de ressources informatiques réelles sont inférieures à celles prévues par la théorie.

Les solutions produites par différents algorithmes pour les trois premiers problèmes sont présentées par ordre dans les tableaux 8.2 à 8.4. Les résultats pour le problème 2.4 sont décrits simplement ci-dessous. (Le tableau des solutions de ce problème peut être obtenu sur demande.) Dans le tableau 8.2, la méthode de Sitter et Skinner (1994), et les méthodes 2 et 3 de Jessen (1970) sont désignées par $SS$ , $J2$  et $J3$ , respectivement. Les solutions pour $J2$  et $J3$  dans le tableau sont tirées de Jessen (1970, p. 782). Le tableau montre que toutes les méthodes, sauf la méthode 3 de Jessen (1970) donnent la même solution pour le tableau de dimensions $3\text{ x }3$  du problème 2.1. Dans les solutions communes, la probabilité de sélection des tableaux optimaux, désignée par ${\displaystyle {\sum }_{B_k\in {\mathfrak{B}}_{\infty }}p\left(B_k\right)},$ est de 0,5.

Tableau 8.2
Comparaison des solutions du problème 2.1
Sommaire du tableau
Le tableau montre les résultats de Comparaison des solutions du problème 2.1. Les données sont présentées selon $B_k$ (titres de rangée) et $p\left(B_k\right)$ (figurant comme en-tête de colonne).

$B_k$	$p\left(B_k\right)$
	$N_2$	$N_{\infty }$	$SS$	$J2$	$J3$
$$\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}$$	0,2	0,2	0,2	0,2	0,1
$$\begin{array}{ccc}1& 0& 1\\ 1& 1& 0\\ 0& 1& 1\end{array}$$ Note *	0,5	0,5	0,5	0,5	0,4
$$\begin{array}{ccc}1& 1& 0\\ 0& 1& 1\\ 1& 0& 1\end{array}$$	0,3	0,3	0,3	0,3	0,2
$$\begin{array}{ccc}0& 1& 1\\ 1& 1& 0\\ 1& 0& 1\end{array}$$					0,1
$$\begin{array}{ccc}1& 0& 1\\ 0& 1& 1\\ 1& 1& 0\end{array}$$					0,1
$$\begin{array}{ccc}1& 1& 0\\ 1& 0& 1\\ 0& 1& 1\end{array}$$					0,1
Total	1,0	1,0	1,0	1,0	1,0
Total Note †	0,5	0,5	0,5	0,5	0,4
Tableau optimal Retour à la référence de note *   La somme des probabilités de sélection pour les tableaux optimaux. Retour à la référence de note †

Dans le tableau 8.3, la méthode de Jessen (1978) est désignée par $JS$ . La solution pour $JS$  présentée dans le tableau est tirée de Jessen (1978, p. 375-376). Comme le montre le tableau, les nouvelles méthodes en utilisant $d_2^{*}$  et $d_{\infty }^{*}$  donnent la même solution pour le tableau de dimensions $4\times 4$  du problème 2.2; cependant, la moitié seulement des tableaux figurant dans ces solutions concorde avec les tableaux figurant dans les solutions produites par les méthodes de Sitter et Skinner (1994) et Jessen (1978). En outre, les méthodes de Sitter et Skinner et de Jessen donnent une probabilité plus faible, égale à 0,6, aux tableaux optimaux, tandis que les nouvelles méthodes attribuent une probabilité plus élevée, égale à 0,8, aux tableaux.

Tableau 8.3
Comparaison des solutions du problème 2.2
Sommaire du tableau
Le tableau montre les résultats de Comparaison des solutions du problème 2.2. Les données sont présentées selon $B_k$ (titres de rangée) et $p\left(B_k\right)$ (figurant comme en-tête de colonne).

$B_k$	$p\left(B_k\right)$
	$N_2$	$N_{\infty }$	$SS$	$JS$
$$\begin{array}{cccc}0& 0& 1& 1\\ 0& 1& 0& 1\\ 1& 1& 0& 0\\ 1& 0& 1& 0\end{array}$$	0,2	0,2
$$\begin{array}{cccc}0& 0& 1& 1\\ 1& 1& 0& 0\\ 0& 0& 1& 1\\ 1& 1& 0& 0\end{array}$$ Note *	0,2	0,2	0,4	0,2
$$\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 0& 1& 1\\ 1& 1& 0& 0\end{array}$$ Note *	0,2	0,2
$$\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 1\end{array}$$ Note *	0,4	0,4	0,2	0,4
$$\begin{array}{cccc}0& 1& 1& 0\\ 0& 0& 1& 1\\ 1& 1& 0& 0\\ 1& 0& 0& 1\end{array}$$			0,2
$$\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 0& 1\\ 1& 0& 0& 1\\ 0& 1& 1& 0\end{array}$$			0,2
$$\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 1\\ 1& 0& 1& 0\end{array}$$				0,2
$$\begin{array}{cccc}0& 0& 1& 1\\ 0& 1& 0& 1\\ 1& 0& 1& 0\\ 1& 1& 0& 0\end{array}$$				0,2
Total	1,0	1,0	1,0	1,0
Total Note †	0,8	0,8	0,6	0,6
Tableau optimal Retour à la référence de note *   La somme des probabilités de sélection pour les tableaux optimaux. Retour à la référence de note †

Le problème 2.3, avec 141 tableaux possibles, est considérablement plus grand que les deux problèmes susmentionnés. Les solutions de ce problème sous les cinq méthodes sont comparées au tableau 8.4. Dans le tableau, les méthodes de Causey et coll. (1985) et de Huang et Lin (1998) sont désignées par $CA$  et $HU$ , respectivement. Les solutions pour $CA$  et $HU$  dans le tableau sont tirées de Causey et coll. (1985, p. 906) et de Huang et Lin (1998, figure 3), respectivement.

Tableau 8.4
Comparaison des solutions du problème 2.3
Sommaire du tableau
Le tableau montre les résultats de Comparaison des solutions du problème 2.3. Les données sont présentées selon $B_k$ (titres de rangée) et $p\left(B_k\right)$ (figurant comme en-tête de colonne).

$B_k$	$p\left(B_k\right)$
	$N_2$	$N_{\infty }$	$SS$	$CA$	$HU$
$$\begin{array}{ccc}0& 2& 0\\ 1& 0& 1\\ 0& 0& 0\\ 2& 0& 0\\ 1& 1& 0\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$	0,2	0,2	0,2
$$\begin{array}{ccc}0& 2& 0\\ 1& 0& 1\\ 1& 0& 0\\ 1& 0& 1\\ 1& 0& 1\\ 0& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}$$	0,1	0,2	0,03
$$\begin{array}{ccc}0& 2& 0\\ 1& 0& 1\\ 1& 0& 0\\ 1& 1& 0\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$	0,1
$$\begin{array}{ccc}0& 2& 0\\ 2& 0& 1\\ 0& 0& 0\\ 1& 0& 0\\ 1& 0& 1\\ 0& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}$$	0,1
$$\begin{array}{ccc}0& 2& 0\\ 2& 0& 1\\ 0& 0& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 0\\ 0& 0& 1\end{array}$$	0,1
$$\begin{array}{ccc}1& 2& 0\\ 1& 0& 1\\ 0& 0& 0\\ 1& 0& 0\\ 1& 1& 0\\ 0& 0& 1\\ 0& 0& 1\\ 0& 0& 0\end{array}$$ Note *	0,1		0,08
$$\begin{array}{ccc}1& 2& 0\\ 1& 0& 1\\ 0& 0& 0\\ 1& 1& 0\\ 1& 1& 0\\ 0& 0& 1\\ 0& 0& 0\\ 0& 0& 0\end{array}$$ Note *	0,3	0,4	0,2	0,4	0,4
$$\begin{array}{ccc}0& 2& 0\\ 2& 0& 1\\ 0& 0& 0\\ 1& 0& 0\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 1\end{array}$$		0,2
$$\begin{array}{ccc}0& 2& 0\\ 1& 0& 1\\ 1& 0& 0\\ 1& 0& 0\\ 1& 0& 0\\ 0& 1& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}$$			0,11
$$\begin{array}{ccc}0& 2& 0\\ 1& 0& 1\\ 1& 0& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$			0,03
$$\begin{array}{ccc}0& 2& 0\\ 1& 0& 1\\ 1& 0& 0\\ 1& 0& 1\\ 1& 1& 0\\ 0& 0& 0\\ 0& 0& 0\\ 0& 0& 1\end{array}$$			0,03
$$\begin{array}{ccc}0& 2& 0\\ 2& 0& 1\\ 0& 0& 0\\ 1& 1& 0\\ 1& 0& 1\\ 0& 0& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$			0,09
$$\begin{array}{ccc}0& 2& 0\\ 2& 0& 1\\ 0& 0& 0\\ 1& 1& 0\\ 1& 0& 1\\ 0& 0& 1\\ 0& 0& 0\\ 0& 0& 0\end{array}$$			0,08
$$\begin{array}{ccc}0& 2& 0\\ 2& 0& 1\\ 0& 0& 0\\ 1& 1& 0\\ 1& 1& 0\\ 0& 0& 1\\ 0& 0& 0\\ 0& 0& 0\end{array}$$			0,03
$$\begin{array}{ccc}1& 2& 0\\ 1& 0& 1\\ 0& 0& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}$$			0,06
$$\begin{array}{ccc}1& 2& 0\\ 1& 0& 1\\ 0& 0& 0\\ 1& 0& 1\\ 1& 1& 0\\ 0& 1& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}$$			0,06
$$\begin{array}{ccc}0& 2& 0\\ 1& 0& 1\\ 0& 0& 0\\ 2& 0& 0\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 1\end{array}$$				0,2
$$\begin{array}{ccc}0& 2& 0\\ 1& 0& 1\\ 1& 0& 0\\ 1& 0& 0\\ 1& 0& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$				0,2	0,2
$$\begin{array}{ccc}0& 2& 0\\ 2& 0& 1\\ 0& 0& 0\\ 1& 0& 1\\ 1& 1& 0\\ 0& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}$$				0,2
$$\begin{array}{ccc}0& 2& 0\\ 1& 0& 1\\ 0& 0& 0\\ 2& 0& 0\\ 1& 1& 0\\ 0& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}$$					0,2
$$\begin{array}{ccc}0& 2& 0\\ 2& 0& 1\\ 0& 0& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$					0,2
Total	1,0	1,0	1,0	1,0	1,0
Total Note †	0,4	0,4	0,28	0,4	0,4
Tableau optimal Retour à la référence de note *   La somme des probabilités de sélection pour les tableaux optimaux. Retour à la référence de note †

Nous notons que toutes ces méthodes fournissent des solutions différentes et qu’il y a chevauchement d’environ la moitié des tableaux entre les nouvelles méthodes et la méthode de Sitter et Skinner (1994). En outre, les solutions produites par les méthodes de Causey et coll. (1985) et de Huang et Lin (1998) sont assez différentes de la solution de la méthode utilisant $d_{\infty }^{*}$ . La méthode utilisant $d_2^{*}$  et la méthode de Sitter et Skinner répartissent les probabilités de sélection entre deux tableaux optimaux, tandis que les trois autres méthodes n’attribuent la probabilité qu’à un seul tableau optimal. La méthode de Sitter et Skinner semble être moins efficace pour sélectionner des tableaux optimaux, puisqu’elle donne la probabilité de 0,28 à ces derniers, tandis que les autres méthodes donnent une probabilité plus élevée, soit 0,4.

Les solutions du problème 2.4, qui est le plus grand des problèmes donnés, sont comparées sous quatre méthodes ( $N_2$ , $N_{\infty }$ , $SS$  et la méthode de Winkler, 2001). Deux tableaux seulement, y compris un tableau optimal, sont les mêmes dans les solutions, et les deux nouvelles méthodes donnent les mêmes probabilités (0,127 et 0,483) à ces deux tableaux. Même si l’on compare la méthode utilisant $d_{\infty }^{*}$  aux méthodes de Sitter et Skinner (1994) et de Winkler (2001), les solutions de ces auteurs sont très différentes. En outre, les nouvelles méthodes donnent la même probabilité de sélection de 0,483 au tableau optimal, tandis que les méthodes antérieures donnent les probabilités plus faibles de 0,385 et 0,104, respectivement.

En résumé, il semble que les nouvelles méthodes réussissent à atteindre les spécifications S1 et S2 des solutions optimales. Notons que les nouvelles méthodes produisent systématiquement des probabilités de sélection plus élevées pour les tableaux optimaux et que les totaux de ces probabilités sont toujours les mêmes. Les solutions issues des nouvelles méthodes sont très différentes de celles obtenues en utilisant les méthodes antérieures lorsque les problèmes de sélection contrôlée ne sont pas petits. Cela implique que les solutions découlant des méthodes antérieures sont peut-être loin d’être optimales sous les critères S1 et S2 (E1 et E2).

Précédent | Suivant