Problème de voyageur de commerce bi-objectif et Algorithme de colonies

Exemple de graphe à 4 sommets

PROBLEME DE VOYAGEUR DE COMMERCE BI-OBJECTIF – CHAPITRE III :
II. INTRODUCTION :
III. REPRESENTATION DU PVC BI-OBJECTIF :
III.1 OBJECTIF :
IV. COMPLEXITE
V. ALGORITHME GENETIQUE :
V. ALGORITHME DE COLONIES DE FOURMIS :
VI. CONCLUSION

Introduction :

Le problème du voyageur de commerce, étudié depuis le 19em siècle, est l’un des plus connus dans le domaine de la recherche opérationnelle. Jouez à trouver le meilleur parcours possible… et découvrez différentes méthodes informatiques proposées pour résoudre ce problème.
C’est déjà sous forme de jeu que William Rowan Hamilton a posé pour la première fois ce problème, dès 1859. Sous sa forme la plus classique, son énoncé est le suivant : « Un voyageur de commerce doit visiter une et une seule fois un nombre fini de villes et revenir à son point d’origine. Trouvez l’ordre de visite des villes qui minimise la distance totale parcourue par le voyageur ». Ce problème d’optimisation combinatoire appartient à la classe des problèmes NP-Complets.
Les domaines d’application sont nombreux : problèmes de logistique, de transport aussi bien de marchandises que de personnes, et plus largement toutes sortes de problèmes d’ordonnancement. Certains problèmes rencontrés dans l’industrie se modélisent sous la forme d’un problème de voyageur de commerce, comme l’optimisation de trajectoires de machines outils : comment percer plusieurs points sur une carte électronique le plus vite possible ?

II.

Continuer la lecture

Optimisation multiobjectif et problèmes d’optimisation mono-objectifs

espace décisionnel et espace objectif d’un problème d’optimisation Multiobjectif

OPTIMISATION MULTIOBJECTIF – CHAPITRE II :
I. INTRODUCTION :
II. DEFINITIONS D’UN PROBLEME :
II.1. TYPES DES PROBLEMES :
II.1.1. UN PROBLEME DE DECISION:
II.1.2. UN PROBLEME POLYNOMIAL REDUCTIBLE
II.1.3. UN PROBLEME DE LA CLASSE P:
II.1.4. UN PROBLEME DE LA CLASSE NP:
II.1.5. UN PROBLEME DE LA CLASSE NP-HARD:
II.1.6. UN PROBLEME DE LA CLASSE NP-COMPLET:
III. LES PROBLEMES D’OPTIMISATION MONO-OBJECTIFS :
III.1. CONTRAINTES
IV. PROBLEME D’OPTIMISATION MULTIOBJECTIF :
IV.1. DEFINITION :
IV.2. CLASSIFICATION DES PROBLEMES D’OPTIMISATION MULTIOBJECTIF :
IV.2.1. CLASSIFICATION « POINT DE VUE DECIDEUR » :
IV.2.2. CLASSIFICATION « POINT DE VUE CONCEPTEUR » :
V. APPROCHES DE RESOLUTION MULTIOBJECTIF :
V.1. NOTION DE DOMINANCE
V.2. APPROCHE PARETO :
V.2.1. DEFINITION 1
V.2.2. DEFINITION2
V.2.3. OPTIMALITE DE PARETO
VI. CONCLUSION

I. Introduction :

L’optimisation multiobjectif est un axe de recherche très important à cause de la nature multiobjectif de la plupart des problèmes réels. Les premiers travaux menés sur les problèmes multiobjectifs furent réalisés au 19éme siècle sur des études en économie par Edgeworth et généralisés par Pareto.
L’optimisation multiobjectif est un domaine fondamental de l’aide a la décision multicritère, auquel de nombreux milieux scientifiques et industriels se doivent faire face, la résolution d’un problème d’optimisation multiobjectif

Continuer la lecture

Le problème de voyageurs de commerce Bi-Objectifs

problème du sac à dos Knapsackproblem

La résolution du problème de voyageurs de commerce Bi-Objectifs
République Algérienne Démocratique et Populaire
Ministere de l’Enseignement Supérieur et de la Recherche Scientifique

Département de Mathématique et d’Informatique

Soutenance
Présenté pour l’obtention du diplôme de MASTER Option Réseaux et Multimédia

La Résolution du Problème de Voyageurs de Commerce Bi-Objectifs
par La Métaheuristique d’Optimisation par Colonie de Fourmis Artificielles

Par
KOUCHI Mohamed & Mili Kamel

Promotion
2012 – 2013

Introduction générale

Les problèmes d’optimisation occupent actuellement une place importante dans la communauté scientifique, on peut voir de façon intuitive, un problème d’optimisation comme un problème de recherche qui consiste à explorer un espace contenant l’ensemble de toutes les solutions potentielles réalisables, dans le but de trouver la solution optimale, sinon la plus proche possible de l’optimum, permettant de minimiser ou maximiser une fonction dite objectif.
Il existe deux grandes

Continuer la lecture

La sécurisation du réseau SIGTRAN de la Sonatel

La sécurisation du réseau SIGTRAN de la Sonatel

IV.3 Méthodes de sécurisation du réseau SIGTRAN

Les réseaux IP prennent de plus en plus d’importance dans les réseaux des télécommunications, de l’accès jusqu’au transport.

** Comment sécuriser le réseau SS7 standard

La sécurité dans les réseaux téléphoniques est principalement basée sur la fermeture totale d’un réseau.

Deux principaux protocoles sont utilisés :

  • Les protocoles d’accès RNIS (et les autres)
  • Les protocoles de la pile SS7 du cœur réseau

Comme les réseaux de signalisations de base (SS7) sont souvent éloignés physiquement et/ou inaccessibles à l’utilisateur, il est supposé qu’ils sont protégés contre les utilisateurs malveillants.

Les équipements télécoms sont souvent sous clés. Entre une frontière du réseau et le réseau SS7, le filtrage de paquets est parfois utilisé. Les utilisateurs finaux ne sont pas directement connectés à des réseaux SS7.

Les protocoles d’accès sont utilisés pour l’utilisateur final de signalisation.

Les protocoles de signalisations de l’utilisateur final sont traduits en protocoles SS7 de base des commutateurs téléphoniques gérés par des opérateurs de réseau.

Les autorités de la réglementation exigent souvent les commutateurs SS7 avec des connexions à différents commutateurs SS7 d’être conforme au niveau national et/ou aux spécifications de test international.

Il n’y a pas des méthodes normalisées d’utilisation des technologies de cryptage pour assurer la confidentialité ou l’utilisation de technologies

Continuer la lecture

L’amélioration du réseau de signalisation de la Sonatel

Proposition sur les résultats d’analyses et audits obtenus pour l’amélioration du réseau de signalisation de la Sonatel – Chapitre IV :

IV.1 Analyse des résultats
Dans le cadre de l’amélioration du réseau de signalisation de la Sonatel, des analyses de tous les résultats émanent des études et audits au niveau des plateformes STP et aux liens des signalisations ont été effectué. L’objectif de cette analyse c’est de pouvoir identifier certains disfonctionnements s’ils existent dans le réseau et d’apporter quelles que proposions afin d’améliorer la performance du réseau. En examinant d’une manière détaillée les résultats des études faites dans les différentes entités du réseau de signalisation, les disfonctionnement décelés dans l’intervalle d’observation n’ont pas été très critiques. Mais lors d’une vérification dans l’ensemble des autres fichiers contenant les KPI observés dans les périodes et jours qui n’ont pas été inclus dans notre cadre d’étude, certains défauts ont été détecté dans le réseau.
Puisqu’il sera très difficile d’introduire dans ce document l’étude et analyse faites pour tous les fichiers des indicateurs hebdomadaire ou journalier, nous avons conservé dans ce document que les études d’une journée. Dans les paragraphes qui suivent des décisions ou propositions seront prises suite aux résultats donnés pendent les analyses du système globale (SYSTOT) et ses composant (COMP)
IV.1.1 Décision sur les résultats du SYSTOT(STP)
La

Continuer la lecture

L’occupation des canaux sémaphore et le taux d’occupation du COMP

Charge des liens HSL en transmission et en émission

III.3 Les recommandations
L’Assemblée mondiale de normalisation des télécommunications (AMNT), qui se réunit tous les quatre ans, détermine les thèmes d’étude à traiter par les Commissions d’études de l’UIT-T, lesquelles élaborent en retour des Recommandations sur ces thèmes. Le respect de certaines recommandations se fait à titre volontaire. Cependant, il se peut que parmi ces recommandations il y ait certaines dispositions obligatoires. Dans certaine circonstance les opérateurs de télécommunications s’obligent à respecter des recommandations pour maintenir de la qualité de service du réseau. Nous allons présenter dans les paragraphes qui suivent certaines recommandations qui nous servirons comme référence pour calculer la performance du réseau de signalisation de la Sonatel.

III.3.1 Occupation des canaux sémaphore

Le système de signalisation par canal sémaphore est défini par la recommandation IUT Q.700. Un canal sémaphore peut donc avoir à traiter en situation anormale (jours spécial) plus de trafic qu’en situation normale. Pour cette raison, un canal sémaphore ne peut pas utiliser en situation normale plus de 40% de son débit nominal. Lorsqu’un canal tombe, son trafic est alors renvoyé vers un autre canal qui sera utilisé à 80% au maximum de son débit minimal. Les 20% qui restent sont utilisé afin de transporter des messages de gestion. Dans le cas des liens LSL, le débit du canal sémaphore est de 64kbps. Un message ISUP ayant une taille moyenne de 40 octets, le canal sémaphore utilisé en

Continuer la lecture

Trafic engineering du réseau de signalisation de la Sonatel

illustration du traitement des messages du STP

Analyse de la performance du réseau de signalisation de la Sonatel – Chapitre III:

III.2 Trafic engineering du réseau de signalisation

Les indicateurs numériques obtenus après la récupération des rapports de mesures dans le serveur FTP, seront étudiés et analysés à fin de pouvoir tirer des résultats. L’objectif de cette étude est de pouvoir déterminer la performance du réseau de signalisation. Comme nous avons déjà décrit précédemment les paramètres nécessaires aux études et analyses engineering, il est indispensable de classifier ces paramètres pour faciliter les étapes des études. Au cours de notre étude et analyse nous allons classifier ces indicateurs en deux catégories :
** Catégorie du niveau supérieur
** Catégorie du niveau inférieur
Nous appelons catégorie du niveau supérieur tous les indicateurs qui associent des messages de couches supérieurs (couche application). Tandis que la catégorie du niveau inférieur concerne les indicateurs associant des messages de la couche basse du model de référence OSI. Notons que ces deux catégories entrent dans le cadre d’étude des indicateurs clé de la performance du réseau SS7 et SIGTRAN.

III.2.1 Analyse des données numériques des indicateurs du système STP(SYSTOT)

Sachant que l’heure chargée du réseau de signalisation est préalablement définie, il nous reste à récupérer les indicateurs générés dans cet intervalle d’heure chargé. Les données de ses indicateurs sont l’ensemble des messages traités

Continuer la lecture

Les mesures (key Performance Indicator) de la plateforme STP

Analyse de la performance du réseau de signalisation de la Sonatel – Chapitre III:

III.1 Présentation des mesures (key Performance Indicator) de la plateforme STP

Les mesures obtenus pendant une observation planifié ou à la demande, sont des données importantes qui constituent des indicateurs que l’administrateur du système s’appuie pour déterminer la performance de son système. Ces indicateurs jouent un rôle primordial, car ce sont des paramètres clés qu’un administrateur ou gestionnaire du trafic téléphonique utilise pour prévenir à une éventuelle extension du système ou dimensionner les composants du réseau. La plateforme STP (EAGLE 5 ISS) de la Sonatel que nous étudions dispose douze type de mesures regroupées en cinq catégories. Nous allons présenter ces douze types de mesures avec ses catégories, mais notre étude se basera sur un nombre restreint de ces mesures.
Voici les cinq catégories et les différents types des mesures de ces catégories :

1. Rapports Engineering du traffic

– Le système intégral du STP, nommé en langage technique (SYSTOT)
– les mesures de se composant (COMP)
– Gestion du réseau (NM)

2. Dépistage d’Erreur/ Rapports de Diagnostic des pannes

– Disponibilité quotidienne (AVLD)
– Disponibilité journalière en heure (AVLDTH)
– Disponibilité (AVL)

3. Rapports journalier sur les maintenances

– Mesures quotidiennes pour les maintenances (MTCD)
– Mesures quotidiennes pour les maintenances en

Continuer la lecture

Vue d’ensemble des équipements de signalisation utilisé par la Sonatel

réseau de la transmission de signalisation

II.3.4 Vue d’ensemble des équipements de signalisation utilisé par la Sonatel (EAGLE STP)

Eagle STP qui est l’équipement intelligent du réseau de la signalisation, est composé de deux (2) types de baies que sont :
– La baie de contrôle (CF, Control Frame) qui est la première et principale baie de la PTS. Elle est identifiée par un numéro de série qui lui est propre et unique. Elle comprend trois (3) étagères dont une de Contrôle (Control Shelf), qui comprend tous les composants du sous-système administration et maintenance du PTS et deux autres pour les extensions (Extension Shelf) séparés entre eux par un système de ventilation électrique.
– La baie d’extension (EF, Extension Frame), étant constituée de trois (3) alvéoles (shelves) séparés par un système d’aération électrique, cette baie est utilisée pour augmenter la capacité des liens de signalisation en ajoutant des cartes.
baie de l’EAGLE STP
Figure 15 : baie de l’EAGLE STP
Les baies sont alimentées en énergie par le « FAP » (Fuse and Panel Alarm) qui est aussi le gestionnaire des alarmes. Les alvéoles de chacune de baie comportent dix-huit (18) cartes identifiées par un numéro spécifique.
La nomenclature utilisée pour localiser une carte dans une alvéole se fait comme suit :
* CF00 pour la baie principale
* EF00 à EF16 pour les baies d’extension
* 1XYZ pour les cartes avec : X étant la position de la baie dans le système (1=CF00, 2=CF01, 3=CF03)
Y étant la position e

Continuer la lecture

Architecture détaillé du cœur réseau mobile de la Sonatel

Architecture SS7 de l’interconnexion

II.3 Etude du réseau de signalisation de la Sonatel et Présentation des composants du cœur réseau

Pour assurer une couverture du réseau mobile dans tous le territoire Sénégalais la Sonatel dispose actuellement de :
– Cinq MSCs NGN de type Huwaeï,
– Deux NgHLRs Alcatel,
– Deux STPs de type TEKELEC.
Du côté plateforme de service il déploie :
– Deux SMSC,
– Deux VMS,
– Deux CRBT,
– Un USSD,
– Deux SGSN et deux GGSN pour le domaine packet
– Deux IN.
Ces équipements représente en général le cœur du réseau mobile de la Sonatel.
Au niveau Radio la Sonatel dispose :
– Une centaine de BSC (Base Station Controller)
– Des centaines BTS,
– Quatre RNC (Radio Network controller) et
– Une trentaine de node B
Le réseau de signalisation de la Sonatel est composé de deux STP nommé EAGLE STP ou EAGLE 5 ISS fabriqués par TEKELEC portant actuellement la release R38.0. En raison de sécurité les deux STP ne sont pas installés dans la même localité. L’un se trouve dans le site de Technopole et l’autre EAGLE STP est implanté dans le site de Dakar RP. C’est à partir de ce réseau de signalisation que les équipements du cœur réseau mobile sont interconnectés pour assurer le dialogue interne et externe du réseau. Nous allons voir en détail les équipements qui sont interconnectés avec les plateformes STP dans le prochain paragraphe.

II.3.1 Architecture détaillé du cœur réseau mobile

Sur cette architecture nous

Continuer la lecture

Les couches SIGTRAN – les messages de la signalisation SS7 sur IP

composant de SIGTRAN

II.2 Convergence du réseau de signalisation SS7 vers la signalisation sur IP (SIGTRAN)

SIGTRAN est un groupe de Travail de l’IETF ayant comme objectif de définir une architecture pour le transport des données de signalisation temps réel à travers les réseaux IP. SIGTRAN est l’acronyme de SIGnaling TRANsport. C’est une partie des réseaux de la nouvelle génération basée sur le protocole IP. SIGTRAN a été conçu pour l’acheminement de trafic de signalisation tel que SS7, RNIS, et tous les réseaux NGNs utilisant les avantages du SS7, à travers les réseaux IP. La signalisation SS7 sur IP qu’on va l’appeler souvent SIGTRAN définit un protocole de transport fiable appelé SCTP (Stream Control Transmission Protocol) et une couche d’adaptation des usagers (User Adaptation; UA) permettant de transporter des protocoles de signalisation téléphonique sur IP (Figure 10). La pile de protocole SIGTRAN est définie dans la référence RFC 2719. SCTP est un protocole “TCP de la nouvelle génération” permettant de remédier aux problèmes liés à l’utilisation du protocole TCP puisque ce dernier est un protocole orienté octets et n’est pas capable de fournir la vitesse et la fiabilité requises par la signalisation. En effet, SCTP est un protocole orienté message permettant de définir des trames de données structurées alors que TCP n’impose aucune structure des octets transmises.
Le nom Stream Control Transmission Protocol découle de la fonction multi-streaming fournie par SCTP. Un stream (flot) est un canal

Continuer la lecture

Architecture du protocole de signalisation sémaphore N°7

La Pile de protocoles SS7 et Le modèle de référence OSI

Architecture du protocole de signalisation sémaphore N°7 et modèle OSI

II.1.3 Architecture du protocole de signalisation sémaphore N°7 et le modèle OSI

Le réseau sémaphore étant un réseau à commutation par paquets, il est naturel de reprendre une architecture en couches.

Les concepteurs de cette architecture ont pris référence sur l’architecture du modèle OSI (Open System interconnection).

La figure suivante illustre une comparaison entre les deux architectures.

La Pile de protocoles SS7 et Le modèle de référence OSI

Figure 8 : La Pile de protocoles SS7 et Le modèle de référence OSI

Les fonctions matérielles et logicielles du protocole SS7 sont divisées en quatre niveau, le terme niveau est utilisé pour faire une différence avec le concept des couches du modèle OSI.

La figure 8 nous indique la différence qui existe entre les deux concepts.

Le sous-système transport de messages (en anglais: Message Transfer Part ) est défini dans les recommandations Q.701, Q.702, Q.703, Q.704, Q.706 et Q.707. Il transporte les messages entre les différentes interfaces utilisateurs.

Le niveau 1 ou MTP 1 (Message Transfer Part level 1), est équivalent à la couche physique du modèle OSI.

MTP 1 définit les caractéristiques physiques, électriques, et fonctionnelles du lien de signalisation numérique. Plusieurs supports

Continuer la lecture

Les différents modes de la signalisation sémaphore SS7

Mode quasi-associé

II.1.2 Les différents modes de la signalisation sémaphore (SS7)

C’est à partir de la signalisation hors bande ou out of band également appelé Common Channal Signaling (CCS), qu’on a déterminé les différents modes de signalisation.

II.1.2.1 Signalisation en mode Associé

Ce mode est le plus simple à implémenter, le canal sémaphore est parallèle aux circuits de paroles pour lequel permet l’échange des informations de la signalisation (voir figure 5). Ce mode n’est pas idéal car il requiert un canal sémaphore entre un point de signalisation donné (SP, signaling point) et tous les autres SP.
Les messages de signalisations suivent alors la même route que la voix mais sur des supports différents.
mode associé
Figure 5 : mode associé

II.1.2.2 Signalisation en mode quasi-associé

La signalisation en mode quasi-associé est semblable au mode non associé que nous allons voir dans le prochain paragraphe, mais avec un petit nombre de STP (Signaling Transfert Point) est traversé pour atteindre la destination finale (au minimum deux). C’est le mode le plus utilisé afin de minimiser le temps nécessaire pour acheminer les messages. La figure 6 montre que les messages de la signalisation associés à l’établissement des circuits de parole entre les commutateurs A et B suivent le chemin A-C-B. Le STP ne fait que relaie les messages émis par le PS du central A au PS du

Continuer la lecture

Architecture et type de point de signalisation SS7

Points et liens de Signalisation SS7, cas du GSM

Rôle principal de la signalisation dans un réseau téléphonique – Chapitre II:

II.1 Principe de base de la signalisation

La signalisation au sein d’un réseau de télécommunication fait référence à l’ensemble des échanges d’informations entre les équipements du réseau, nécessaires pour fournir et maintenir le service. Les informations de la signalisation sont acheminées sous forme de messages caractérisés par des paquets de donnés à débit élevé. Nous devons noter que la signalisation peut être transmise de deux manières :
** Signalisation en bande de base
** Signalisation hors – bande
La signalisation en bande de base est la méthode qui a été utilisée par le réseau téléphonique traditionnel. Les signaux permettant d’établir un appel entre deux commutateurs s’effectuaient toujours dans le même canal que le transport de la voix. La signalisation prenait la forme d’une série d’impulsions multifréquences (MF), un peu comme la tonalité de composition du numéro entre les commutateurs.
Dans le cas de la signalisation hors-bande la conversation et la signalisation ne prennent pas le même canal. Ce type de signalisation nécessite l’établissement d’un canal numérique pour l’échange des informations de signalisation appelé lien de signalisation ou canal sémaphore. Les canaux sémaphores de signalisation véhiculent les informations avec des débits de 56kps aux Etats Unis ou 64 kilobits par second (kb/s) pour les autres pays.
La signalisation hors-bande a

Continuer la lecture

L’organigramme de l’entreprise Sonatel  et le service d’accueil

Organigramme de la Direction des Opération Sonatel

I.4 Organigramme de l’entreprise

La direction de la Sonatel est composée d’une direction générale, d’une direction générale adjointe, des directeurs des filiales (Orange Mali, Orange Guinée, Orange Bissau) et de 15 directions opérationnelles composées chacune de plusieurs départements, services et centres techniques.

I.4.1 Présentation du Direction des Opérations (DO)

Parmi les directions que nous venons de citer précédemment, nous allons essayer de présenter brièvement la Direction des Opérations Réseaux et Systèmes d’Information (DO). Cette direction est composée de deux pôles :
Le pôle d’intervention DINT et le pôle d’exploitation des réseaux (DEX) dont c’est ici que notre stage a été déroulé particulièrement au service SECR (Supervision Energie et Cœur de Réseau).

I.4.2 Le pôle d’exploitation des réseaux DEX

Le pôle d’exploitation des réseaux est chargé d’accomplir les tâches suivantes :
– Assurer l’exploitation et la supervision.
– Garantir la qualité de service de bout en bout des réseaux d’accès en conformité avec les exigences des clients.
– Piloter l’intégration opérationnelle d’exploitation et de supervision du réseau.
– Assurer le déploiement, l’administration et le suivi de la maintenance des serveurs, des systèmes, des bases de données et des réseaux informatiques.
– Concevoir et mettre en œuvre les dossiers, procédures et modes opératoires d’exploitation des applications.

Continuer la lecture