Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 44
Algoritmos Genéticos
Aula 4
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 45
Analogia entre a evolução natural e os algoritmos genéticos
Analogia com a Natureza
Evolução Natural ⇔ Algoritmos Genéticos
Indivíduo — Solução
Genótipo (cromossomas) — Representação da Solução
Reprodução Sexual — Operador de Recombinação (p.ex. cruzamento)
Mutação — Operador Mutação
População — Conjunto de Soluções
Gerações — Ciclos
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 46
Esqueleto típico de um algoritmo genético
Gerar P0
t ← 0Avalia Pt
enquanto ¬ Condição de final Pt fazP’t ← Selecciona Pt
P’’t ← Aplica operadores de recombinação P’tP’’’t ← Aplica operadores de mutação P’’tAvalia P’’’tPt+1 ← Selecciona Sobreviventes de Pt e de P’’’tt ← t + 1
Fimretorna Melhor Solução Global
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 47
Operações de Recombinação
ABCDEFGHIJ abcdefghij
ABCDEFghij abcdefGHIJ
Progenitores
Descendentes
Ponto de Corte Ponto de Corte
ABCDEFGHIJ abcdefghij
ABCDefgHIJ abcdEFGhij
Progenitores
Descendentes
Pontos de Corte Pontos de CorteDois Exemplos do operador de recombinação
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 48
Operador de Mutação
Exemplo de Mutação
0011010011
0011000011
Cromossoma
Cromossomaapós a mutação
Ponto deMutação
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 49
Problema Exemplo
Considere o problema de sequenciamento de 5 tarefas numa única máquina.
Para cada tarefa j (j=1, …, 5), seja pj o tempo de processamento, dj a data de entrega e wj a penalização no caso da tarefa j se atrasar.
O objectivo é minimizar a soma pesada dos atrasos ΣwjTj.
Os tempos de processamento são respectivamente p1=2, p2=4, p3=1, p4=3 e p5=3, e as datas de entrega d1=5, d2=7, d3=11, d4=9 e d5=8.
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 50
Problema Exemplo (cont)
Para visualizar uma sequência é muitas vezes utilizado um diagrama de Gantt, onde as linhas estão associadas às tarefas e as colunas aos períodos de tempo. Para a sequência de tarefas [3,1,2,5,4] obtém-se o calendário representado a seguir.
1 2 3 4 5 6 7 8 9 10 11 12 13 1 2
tarefas 3 4 5 tempo
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 51
Problema Exemplo (cont)RecombinaçãoSupondo o seguinte par de indivíduos, são seleccionados 2 pontos de cruzamento (4º e 7º). Os genes situados entre os dois pontos de cruzamento, inclusive, são copiados para os seus descendentes, sendo as restantes posições preenchidas por um caracter H.
A=123456789 A’=HHH4567HHB=452187693 B’=HHH1876HH
De seguida, e começando no segundo ponto de cruzamento do pai B define-se uma nova ordem para os genes:[9 3 4 5 2 1 8 7 6].Depois de remover os genes 4, 5, 6 e 7 já definidos no filho A’, ficamos com os genes [9 3 2 1 8]. As posições em A’ com H serão preenchidas pela sequência anterior começando pelo segundo ponto de cruzamento. Assim sendo:
A’=218456793
Da mesma forma para gerar o segundo descendente B’, define-se uma nova sequência a partir de A: [8 9 1 2 3 4 5 6 7]. Eliminando os genes já definidos em B’, obtém-se a sequência: [9 2 3 4 5]. A seguir substitui-se nas lacunas (H) de B’ a sequência obtida, começando no 2º ponto de cruzamento obtendo-se o descendente B’.
B’=345187692
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 52
Problema Exemplo (cont)
% tarefa(Id,TempoProcessamento,DataEntrega,Penalizacao).tarefa(t1,2,5,1).tarefa(t2,4,7,6).tarefa(t3,1,11,2).tarefa(t4,3,9,3).tarefa(t5,3,8,2).
% parameterizaçãogeracoes(3).populacao(4).prob_cruzamento(1.0).prob_mutacao(0.1).
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 53
Problema Exemplo (cont)
/** Algoritmo genetico **/
gera:-numero_tarefas(N),assert(tarefas(N)),gera_populacao(Pop),avalia_populacao(Pop,PopAv),ordena_populacao(PopAv,PopOrd),geracoes(NG),gera_geracao(NG,PopOrd).
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 54
Problema Exemplo (cont)
gera_populacao(Pop):- populacao(TamPop), tarefas(NumT),findall(Tarefa,tarefa(Tarefa,_,_,_),ListaTarefas),gera_populacao(TamPop,ListaTarefas,NumT,Pop).
gera_populacao(0,_,_,[]):-!.gera_populacao(TamPop,ListaTarefas,NumT,[Ind|Resto]):-
TamPop1 is TamPop-1,gera_populacao(TamPop1,ListaTarefas,NumT,Resto),gera_individuo(ListaTarefas,NumT,Ind), not member(Ind,Resto).
gera_individuo([G],1,[G]):-!.gera_individuo(ListaTarefas,NumT,[G|Resto]):-
random(N,NumT), retira(N,ListaTarefas,G,NovaLista),NumT1 is NumT-1, gera_individuo(NovaLista,NumT1,Resto).
retira(1,[G|Resto],G,Resto).retira(N,[G1|Resto],G,[G1|Resto1]):-
N1 is N-1, retira(N1,Resto,G,Resto1).
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 55
Problema Exemplo (cont)/** Avaliacao da populacao **/avalia_populacao([],[]).avalia_populacao([Ind|Resto],[Ind*V|Resto1]):-
avalia(Ind,V),avalia_populacao(Resto,Resto1).
/** Avaliacao dos individuos **/avalia(Seq,V):- avalia(Seq,0,V).
avalia([],_,0).avalia([T|Resto],Inst,V):-
tarefa(T,Dur,Prazo,Pen),InstFim is Inst+Dur,avalia(Resto,InstFim,VResto),(
(InstFim =< Prazo,!, VT is 0);
(VT is (InstFim-Prazo)*Pen)),V is VT+VResto.
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 56
Problema Exemplo (cont)
ordena_populacao(PopAv,PopAvOrd):-bsort(PopAv,PopAvOrd).
/* Ordenacao (bubble sort) */bsort([X],[X]):-!.bsort([X|Xs],Ys):-bsort(Xs,Zs),btroca([X|Zs],Ys).
btroca([X],[X]):-!.btroca([X*VX,Y*VY|L1],[Y*VY|L2]):-VX>VY,!,btroca([X*VX|L1],L2).
btroca([X|L1],[X|L2]):-btroca(L1,L2).
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 57
Problema Exemplo (cont)
gera_geracao(0,Pop):-!, write('Geração '), write(0), write(':'), nl, write(Pop), nl.
gera_geracao(G,Pop):-write('Geração '), write(G), write(':'), nl, write(Pop), nl,cruzamento(Pop,NPop1),mutacao(NPop1,NPop),avalia_populacao(NPop,NPopAv),ordena_populacao(NPopAv,NPopOrd),G1 is G-1,gera_geracao(G1,NPopOrd).
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 58
Problema Exemplo (cont)/** Operador de crossover **/cruzamento([],[]).cruzamento([Ind*_],[Ind]).cruzamento([Ind1*_,Ind2*_|Resto],[NInd1,NInd2|Resto1]):-
gerar_pontos_cruzamento(P1,P2),prob_cruzamento(Pcruz), Pc is rand(1),((Pc =< Pcruz,!,cruzar(Ind1,Ind2,P1,P2,NInd1),
cruzar(Ind2,Ind1,P1,P2,NInd2));(NInd1=Ind1,NInd2=Ind2)),cruzamento(Resto,Resto1).
cruzar(Ind1,Ind2,P1,P2,NInd1):-sublista(Ind1,P1,P2,Sub1),tarefas(NumT),R is NumT-P2,rotate_right(Ind2,R,Ind21),elimina(Ind21,Sub1,Sub2),insere(Sub2,Sub1,P2,NInd1). /*insere Sub2 em Sub1 a partir de P2 obtendo NInd1*/
Apontamentos Teórico-Práticos de Algoritmia Avançada LEI/ISEP – Métodos de Pesquisa – Carlos Ramos 59
Problema Exemplo (cont)/** operador de mutacao **/mutacao([],[]).mutacao([Ind|Resto],[NInd|Resto1]):-
prob_mutacao(Pmut), Pm is rand(1),((Pm < Pmut,!,mutacao1(Ind,NInd));NInd=Ind),mutacao(Resto,Resto1).
mutacao1(Ind,NInd):-gerar_pontos_cruzamento(P1,P2), /* Selecciona 2 genes para serem trocados */obtem(Ind,P1,G1), obtem(Ind,P2,G2),mutacao2(Ind,G1,G2,NInd).
mutacao2([G1|Resto],G1,G2,[G2|Resto1]):-!, mutacao2(Resto,G1,G2,Resto1).
mutacao2([G2|Resto],G1,G2,[G1|Resto]).mutacao2([G|Resto],G1,G2,[G|Resto1]):-
mutacao2(Resto,G1,G2,Resto1).
obtem([G|_],1,G):-!.obtem([_|Resto],P,G):- P1 is P-1, obtem(Resto,P1,G).