Artigo: Berth allocation planning in the public berth system by
genetic algorithms
Akio Imai, Etsuko Nishimura, Stratos Papadimitriou, 2.001
Heurística usando Algoritmo Genético
Esboço do procedimento de solução
•Para resolver o DBAP o problema foi dividido em N sub-problemas (SUBs)
de alocação de berços como um fator temporário, conforme a figura abaixo;
Subproblema 1
CHEGADA
Navio1 Navio2 Navio3
Subproblema 2
Navio4
Navio5 Navio6 Navio7 Navio8
Tempo
ABERÇAMENTO
Berço1
Berço2
Berço3
Navio2
Navio1
Navio6
Navio3
Navio7
Navio4
Navio5
Navio8
•Quando todos berços se tornam disponíveis, o 1º SUB é resolvido pelo
Algoritmo Genético. Herdando a solução do 1º SUB (isto é, o momento quando
cada berço se torna disponível para o próximo SUB), o próximo SUB é
resolvido;
•O processo é repetido até que o último SUB seja resolvido, sempre herdando
a solução de um SUB para outro.
Subproblema 1
CHEGADA
Navio1 Navio2 Navio3
Subproblema 2
Navio4
Navio5 Navio6 Navio7 Navio8
Tempo
ABERÇAMENTO
Berço1
Berço2
Berço3
Navio2
Navio1
Navio6
Navio3
Navio7
Navio4
Navio5
Navio8
•A solução final pode ser afetada pelas soluções intermediárias. Isto não
significa que a herança da melhor solução intermediária garante a melhor
solução para o problema inteiro. Em outras palavras, a segunda e terceira
melhores soluções intermediárias podem resultar na melhor solução para o
problema inteiro.
•Nos experimentos dos autores as melhores soluções intermediárias são
herdadas de uma série de SUB´s.
Subproblema 1
CHEGADA
Navio1 Navio2 Navio3
Subproblema 2
Navio4
Navio5 Navio6 Navio7 Navio8
Tempo
ABERÇAMENTO
Berço1
Berço2
Berço3
Navio2
Navio1
Navio6
Navio3
Navio7
Navio4
Navio5
Navio8
Heurística usando Algoritmo Genético
Gerar indivíduos iniciais
se navios estão satisfeitos
com a profundidade da água
nos berços atribuídos
SIM
NÃO
Calcular o valor da
função objetivo
Transformar isto no valor
do fitness
SIM
Faça o fitness do
indivíduo
insatisfeito ser
zero
se a geração corrente for a
primeira
NÃO
se existir genótipos
iguais uns aos outros
NÃO
Faça os indivíduos que
possuem melhor fitness
serem novos pais
SIM
FIM
se a geração
corrente for a última
SIM
Faça o fitness de
um indivíduo ser
zero
NÃO
Operações
genéticas
Gerar novos
filhos
Ajustar
uma
nova geração
Representação
•Na aplicação desenvolvida pelos autores foi escolhido trabalhar com
programação das ordens ao invés da programação de berços;
•Ao invés de usar a representação binária, os cromossomos são
representados como ‘ strings’ de caracteres.
GENE: NAVIO # 1~9, 0(ZERO)
CÉLULA # 1 2 3 4 5 6 7 8 9 10
CROMOSSOMO 2 8 5 9 0 4 7 3 1 6
BERÇO #
1 1 1 1
2 2 2 2 2
ORDEM DE SERVIÇO
1 2 3 4
1 2 3 4 5
SEPARADOR
Cromossomo R1
O comprimento é dado
pelo nº de navios + o nº
de berços -1;
GENE: NAVIO # 1~9, 0(ZERO)
CÉLULA # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
CROMOSSOMO 0 0 0 2 8 0 5 0 9 4
7
0
3
1
0
6
0
0
BERÇO #
2
2
2
2
2
2
2
2
3
4
ORDEM DE SERVIÇO
1 1 1 1 1 1 1 1 1 2
1 2
3
4 1 2
5
SEPARADOR
Cromossomo R2
Cada parte possui um ‘string’ de comprimento fixo, o qual representa o nº
total de navios a serem programados
Atenção à profundidade da água do berço
•Em um cromossomo, nem todos os navios podem ser sempre atendidos
nos berços aos quais foram atribuídos, devido às condições físicas tal
como a profundidade da água;
•Se os navios não atenderem à restrição que garante que a profundidade da
água do berço seja superior à do navio, então o valor do fitness do
cromossomo correspondente é ajustado para zero e a próxima geração não
herda este cromossomo.
Atendendo múltiplos navios em um berço ao mesmo tempo
•A representação do cromossomo da solução define o conjunto de
atribuições de navios a berços, dando aos navios as posições e seqüência
de atendimento para cada berço;
•Para minimizar a FO um navio estando no porto deveria ser atracado no
berço atribuído para iniciar seu serviço assim que possível baseado na
posição resultante da seqüência de atendimento;
•Este princípio é válido quando o berço atribuído já está atendendo outros
navios se o comprimento total dos navios não exceder o comprimento do
berço;
•O procedimento examina os navios por ordem de atendimento no berço;
•Seleciona-se um navio e analisa a factibilidade do comprimento do berço
com os navios em atendimento e o navio a ser atendido;
•Se o momento atual for após a chegada do navio, ele é atendido no
momento atual; em caso contrário, ele é atendido assim que chegar.
Operadores do Algoritmo Genético
•O mecanismo fundamental do GA consiste de 3 principais operações:
•Reprodução: processo em que alguns cromossomos individuais são
copiados de acordo com os valores da sua função de fitness, ou seja,
aqueles que possuírem maiores valores de fitness podem ter maiores cópias
na próxima geração;
•Crossover: cruzamento entre pais, introduzindo novos filhos. O operador
empregado nesta aplicação é o 2-point crossover. O crossover pode gerar
filhos infactíveis, não atendendo à restrição, por exemplo, de que um navio
seja atendido somente uma única vez, mas para isso uma operação é
seguida;
•Mutação: introduz mudanças aleatórias nos cromossomos pela alteração
do valor de um gene com uma dada probabilidade chamada taxa de
mutação.
Exemplo de Crossover:
PAIS
Cromossomo A 2 8 5 9 0 4 7 3 1 6
Cromossomo B 6 3 1 2 5 7 0 8 9 4
FILHOS
Cromossomo C’ 2 8 1 2 5 7 7 3 1 6
PROVISÓRIOS
Cromossomo D’ 6 3 5 9 0 4 0 8 9 4
FILHOS
Cromossomo C
DEFINITIVOS
Cromossomo D 6 3 5 9 0 4 0 8 9 4
2 8 1 2 5 7 7 3 1 6
Experimentos Computacionais
•Os autores do artigo compararam os resultados obtidos com o GA e a
Relaxação Lagrangeana (desenvolvida em outro trabalho), e para isso
inicialmente desconsideraram a simultaneidade de navios em um mesmo
berço;
•Ambos os problemas foram resolvidos para 5, 7 e 10 berço cada um
contendo 25 e 50 navios, permitindo 6 problemas protótipo;
•Tanto para os problemas com 25 navios, quanto os de 50 navios obtiveram
uma solução factível melhor no LR do que no GA embora as diferenças não
sejam significantes;
•Entre os 2 esquemas de cromossomos não houve diferença significativa,
exceto no problema 5 berços, 50 navios, onde R2 se comportou melhor
que o R1;
Comparando GA com Relaxação Lagrangeana
•O valor percentual representa o ‘gap’ entre o respectivo valor encontrado e o
limite inferior. Para os problemas de 25 navios eles são próximos a 10% e para
os problemas de 50 navios eles são mais que 15%.
Total do tempo de
serviço (horas)
2000
15% 16% 24%
LR
1500
18% 18% 16%
Limite inferior
23% 26% 24%
R1
R2
1000
8% 11% 11%
500
12% 14% 14%
11% 11% 11%
0
5 x 25
7 x 25 10 x 25 5 x 50
7 x 50
Berços x Navios
10 x 50
Soluções do GA com serviço simultâneo (SS)
•Os mesmo 6 problemas protótipo foram repetidos porém com serviço
simultâneo;
•Foi analisada a velocidade de convergência do algoritmo comparando os
problemas com e sem o SS;
•Obviamente, os valores dos problemas com SS são menores que os sem SS;
•Para todos os problemas não houve melhoria observada após as 200
gerações (sendo que foi dado o limite de 2000 gerações);
•Próximo do limite de gerações o R2 superou o R1, ou não houve diferença
entre eles;
•Para os problemas 5 berços, 25 navios, sem SS, e os problemas 50 navios
com SS, o R1 superou o R2 nas primeiras 400 gerações e após inverteu-se o
desempenho e, aí, dessa observação, pode-se dizer que o R1 possui
velocidade de convergência mais rápido que o R2;
•Foi analisado também a relação entre o comprimento da ‘string’ e o tempo
do CPU para os problemas com SS;
Comprimento da String e tempo do CPU(2000 gerações)
Berços x Navios
Comprimento da string
Tempo do CPU (min)
R1
R2
R1
R2
5 x 25
29
125
4,7
8,9
7x 25
31
175
6,6
13,5
10 x 25
34
250
9,5
22,1
5 x 50
54
250
15,4
29,2
7 x 50
56
350
20,8
45,5
10 x 50
59
500
28,5
76,5
•A diferença do tempo de CPU entre R1 e R2 é exatamente proporcional ao
comprimento da string;
•Foi concluído que a diferença na qualidade da solução entre os 2
cromossomos não é significante enquanto o tempo de computação é o dobro
de R1.
Aplicação prática
•O algoritmo foi implementado no porto de KOBE
fevereiro de 1996;
durante o mês de
•O problema inteiro foi dividido em SUB´s, cada qual com o planejamento
de 1 dia (resultando em 29 SUB´s), 3 dias (10 SUB´s) ou 6 dias (5 SUB´s);
•Foram criados problemas com berços disponíveis variando de 3 a 7;
•Para problemas com mais de 4 berços não houve diferença significativa
entre R1 e R2;
•O R2 superou R1 no problema de 10 SUB´s com 4 berços e no problema 5
SUB´s com 3 e 4 berços;
•O tempo gasto com o serviço da época, gastava aproximadamente 3000
horas com 7 berços disponíveis em KOBE, e, com esta implementação do
GA o mesmo serviço pôde ser feito com 5 berços, reduzindo-se 2 deles.