APRESENTACAO A Parallel Genetic Algorithm for Shortest Path Routing Problem

PCO102 – Inteligência Artificial

A Parallel Genetic Algorithm for
Shortest Path Routing Problem
Salman Yussof, Rina Azlin Razali e Ong Hang See
Department of System and Networking

2009 International Conference on Future Computer and
Communication

PCO102 – Inteligência Artificial

Motivação

Algoritmos tradicionais de roteamento de caminho mais curtos
Soluções com AG são escaláveis e estáveis, mas não rápidas o suficiente Métodos alternativos continuam a ser pesquisados PCO102 – Inteligência Artificial

Proposta

Desenvolver um algoritmo genético paralelo para resolver o problema de roteamento de menor caminho que tivesse um tempo de processamento aceitável.

Algoritmo genético paralelo (PGA)

PCO102 – Inteligência Artificial

Parallel Genetic Algorithm

Implementação: Coarse-Grained
Migração

Nós de processamento Envio do melhor resultado
Nó coletor

PGA Proposto

PCO102 – Inteligência Artificial

Nós de processamento

Inicializar sub-pop. p
Nó origem A

B p Cromossomo 1: [ A B E ]

C

Cromossomo 2: [ A C E ]

p

D

E Nó destino

PGA Proposto

PCO102 – Inteligência Artificial

Nós de processamento

Inicializar sub-pop. Avaliar

fitness

Valor da avaliação

1 fi  ci Custo total do caminho

PGA Proposto

PCO102 – Inteligência Artificial

Nós de processamento

Inicializar sub-pop. Avaliar

fitness

Criar piscina PGA Proposto

PCO102 – Inteligência Artificial

Nós de processamento

Inicializar sub-pop. Avaliar

fitness

Criar piscina Cromossomo pai 1: [A B C G H I X Y Z]
Cromossomo pai 2: [A K L M I T U Z]

Cruzar até n filhos Cromossomo filho 1: [A B C G H I T U Z]
Cromossomo filho 2: [A K L M I X Y Z]

PGA Proposto

PCO102 – Inteligência Artificial

Nós de processamento

Inicializar sub-pop. Avaliar

fitness

Criar piscina Cromossomo original:
[A C E F G H I Y Z]

Cruzar até n
filhos