---
title: "TP Statistique"
author: "Titi & Kiki"
date: "06 avril 2021"
output: pdf_document
---
```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)
## il est possible qu'avant d'installer le package TSPpackage vous deviez installer ou ré-installer Rcpp
#install.packages('Rcpp')
# install.packages('./TSPpackage_1.0.tar.gz',repos=NULL,type='bin') ## pour linux
#install.packages('./TSPpackage_1.0.zip',repos=NULL,type='bin') ## pour windows
## je ne peux pas fournir de package pour mac...
## Appels aux packages, après les avoir installés !
library(sp)
library(maps)
library(microbenchmark)
library(TSP)
library(TSPpackage)
library(Rcpp)
library(MASS)
library(multcomp)
library(purrr)
set.seed(69963)
```
Voici le plan de ce qui sera fait dans le TP.
# Test Package
```{r, echo=TRUE}
#test package irene
villes <- read.csv('./DonneesGPSvilles.csv',header=TRUE,dec='.',sep=';',quote="\"")
coord <- cbind(villes$longitude,villes$latitude)
dist <- distanceGPS(coord)
voisins <- TSPnearest(dist)
print(voisins)
```
# 0. Visualisation de chemins
Lecture du fichier des villes :
```{r, echo=TRUE}
villes <- read.csv('DonneesGPSvilles.csv',header=TRUE,dec='.',sep=';',quote="\"")
str(villes)
```
Représentation des chemins par plus proches voisins et du chemin optimal :
```{r, echo=TRUE}
coord <- cbind(villes$longitude,villes$latitude)
dist <- distanceGPS(coord)
voisins <- TSPnearest(dist)
pathOpt <- c(1,8,9,4,21,13,7,10,3,17,16,20,6,19,15,18,11,5,22,14,12,2)
par(mfrow=c(1,2),mar=c(1,1,2,1))
plotTrace(coord[voisins$chemin,], title='Plus proches voisins')
plotTrace(coord[pathOpt,], title='Chemin optimal')
```
Les longueurs des trajets (à vol d'oiseau) valent respectivement, pour la méthode des plus proches voisins :
```{r, echo=FALSE}
voisins$longueur
```
et pour la méthode optimale :
```{r, echo=FALSE}
calculeLongueur(dist,pathOpt)
```
Ceci illustre bien l'intérêt d'un algorithme de voyageur de commerce. Nous allons dans la suite étudier les performances de cet algorithme.
# 1. Comparaison d'algorithmes
Nombre de sommets fixes et graphes "identiques".
```{r, echo=TRUE}
n <- 10
sommets <- data.frame(x = runif(n), y = runif(n))
couts <- distance(sommets)
```
## 1.1. Longueur des chemins
Comparaison des longueurs de différentes méthodes :
* boxplots
* test entre 'nearest' et 'branch'
* tests 2 à 2
```{r, echo=TRUE}
n <- 10
vectNear = rep(0,50)
vectBranch = rep(0,50)
vectRep = rep(0,50)
vectInsert = rep(0,50)
vectTwo = rep(0,50)
#boucle permettant de recupérer la longueur des chemins pour les 5 méthodes (50 itérations)
for(i in 1:50){
sommets <- data.frame(x = runif(n), y = runif(n))
couts <- distance(sommets)
vectNear[i] = TSPsolve(couts, "nearest")
vectBranch[i] = TSPsolve(couts, "branch")
vectRep[i] = TSPsolve(couts, "repetitive_nn")
vectInsert[i] = TSPsolve(couts, "nearest_insertion")
vectTwo[i] = TSPsolve(couts, "two_opt")
}
```
```{r, echo =FALSE}
boxplot(vectNear,vectBranch,vectRep,vectInsert,vectTwo, names = c("nearest", "branch", "rep", "NI", "2opt"))
```
```{r mean, echo = FALSE}
#moyenne méthode nearest
mean(vectNear)
#moyenne méthode branch
mean(vectBranch)
```
Test de comparaisons d'échantillons appariés : --> Variable d'intérêt = longueur pour 2 algo différents
```{r}
t.test(vectNear, vectBranch, paired=TRUE, alternative = "greater");
```
Seconde possiblitée
```{r}
t.test(vectNear-vectBranch, mu=0, alternative = "greater");
```
==> P valeur << 0.05 ==> Rejet de (H0)
```{r}
results = c(vectNear, vectBranch, vectRep, vectInsert, vectTwo)
methods = c(rep("nearest",50),rep("branch",50),rep("repetitive_nn",50),rep("nearest_insertion",50),rep("two_opt",50))
pairwise.t.test(results,methods,adjust.method="bonferroni", paired=TRUE)
```
P Valeur proche de 1 ==> Aucun différence, P Valeur proche de 0 ==> Différence significative
## 1.2. Temps de calcul
Comparaison des temps à l'aide du package microbenchmark.
```{r}
n=10 #on a des graphes avec 10 sommets
microbenchmark( TSPsolve(cout, "nearest"),
TSPsolve(cout, "branch"),
TSPsolve(cout, "repetitive_nn"),
TSPsolve(cout, "nearest_insertion"),
TSPsolve(cout, "two_opt"),
times=50, setup={cout = distance(data.frame(x = runif(n), y = runif(n)))})
```
# 2. Etude e la complexité de l'algorithme Branch and Bound
## 2.1. Comportement par rapport au nombre de sommets : premier modèle
Récupération du temps sur 10 graphes pour différentes valeurs de $n$.
Ajustement du modèle linéaire de $\log(temps)^2$ en fonction de $n$.
Analyse de la validité du modèle :
* pertinence des coefficients et du modèle,
* étude des hypothèses sur les résidus.
```{r eval=FALSE}
sommets <- data.frame(x = runif(n), y = runif(n))
couts <- distance(sommets)
```
```{r}
seqn <- seq(4,20,1)
temps = c()
for(i in 1:17){
temps = rbind(temps, microbenchmark(TSPsolve(couts, method = "branch"),times = 50,setup = { n <- seqn[i]
couts <- distance(cbind(x = runif(n), y = runif(n)))})$time)
}
```
```{r}
par(mfrow=c(1,2))# 2 graphiques sur 1 ligne
matplot(seqn, temps, xlab="n", ylab="temps")
matplot(log(seqn), log(temps), xlab="log(n)", ylab=expression(log(temps)))
```
```{r}
vect_temps <- log(as.vector(temps))
vect_dim <- rep(log(seqn),times=50)
temps.lm <- lm(vect_temps~vect_dim)
summary(temps.lm)
```
```{r}
par(mfrow=c(2,2))
plot(temps.lm)
```
```{r}
shapiro.test(residuals(temps.lm))
```
## 2.2. Comportement par rapport au nombre de sommets : étude du comportement moyen
Récupération du temps moyen.
Ajustement du modèle linéaire de $\log(temps.moy)^2$ en fonction de $n$.
Analyse de la validité du modèle :
* pertinence des coefficients et du modèle,
* étude des hypothèses sur les résidus.
```{r}
temps.moy <- rowMeans(temps)
```
```{r}
par(mfrow=c(1,2))
matplot(seqn, temps.moy, xlab='n', ylab='temps moyen')
matplot(seqn, log(temps.moy)^4, xlab='n', ylab=expression(log(temps_moyen)^4))
```
```{r}
vect_temps.moy <- log(as.vector(temps.moy))^4
temps.moy.lm <- lm(vect_temps.moy ~ seqn)
summary(temps.moy.lm)
```
```{r}
par(mfrow=c(2,2))
plot(temps.lm)
```
```{r}
shapiro.test(residuals(temps.lm))
```
## 2.3. Comportement par rapport à la structure du graphe
Lecture du fichier 'DonneesTSP.csv'.
Ajustement du modèle linéaire de $\log(temps.moy)^2$ en fonction de toutes les variables présentes. Modèle sans constante.
Mise en \oe uvre d'une sélection de variables pour ne garder que les variables pertinentes.
Analyse de la validité du modèle :
* pertinence des coefficients et du modèle,
* étude des hypothèses sur les résidus.
```{r}
data.graph <- read.csv('DonneesTSP.csv', header=TRUE, dec=".", sep=",", quote="\"")
```
```{r}
data.graph$dim <- log(data.graph$dim)
data.graph.lm <- lm(log(data.graph$tps)~.,data = data.graph)
```
```{r}
step(data.graph.lm)
```
```{r}
data.graph$mean.dist <- NULL
data.graph.lm<-lm(log(data.graph$tps)~.,data = data.graph)
summary(data.graph.lm)
```
```{r}
par(mfrow=c(2,2))# 4 graphiques, sur 2 lignes et 2 colonnes
plot(data.graph.lm)
```
```{r}
shapiro.test(residuals(data.graph.lm))
```
Sign in with Wallet
Connect another wallet