voltarExemplos
1-
Seja uma população constituída pelos seguintes indivíduos:P1 = X1X2X3X4X5X6X7,
P2 = Y1Y2Y3Y4Y5Y6Y7,
P3 = Z1Z2Z3Z4Z5Z6Z7, e
P4 = U1U2U3U4U5U6U7
onde cada componente Xi, Yi, Zi, Ui pode ter os valores A, B, C ou D que denotam a característica de cada indivíduo.
Seleção: S(Pi) = Qi , onde Qi é uma nota arbitrária atribuída a Pi
P1 = AABBCBA
P2 = AAAAAAA
S(P1) = 5
S(P2) = 1
Mutação:
M(Pi) = Pi'P1 = AABBCBA
P1' = M(P1) = AA
CBCBCP2 = AAAAAAA
P2' = M(P2) = AA
CCCCA
Crossover:
C(Pi, Pm) = Pi', Pm'P3 = CDCDCDC
P4 = ABABABA
C(P3, P4) = P3', P4' =
ABADCDC, CDCBABA
Para este exemplo, partiremos de uma função que desejamos otimizar, geraremos um a população de possíveis soluções que deverá evoluir e adaptar-se, maximizando o valor da função.
Partiremos de uma função simples como:
f(x)=2x, uma reta que passa pela origen de coordenadas.Como primeiro passo, teremos que determinar nossa população evolutiva, e codificar a solução do problema.
Cada indivíduo será representado por uma cadeia de bits, e como seus valores decimais devem variar entre 0 e 15, cada indivíduo deverá possuir 4 bits.
Neste momento vamos determinar uma série de parâmetros que regem a marcha da busca do valor ótimo.
Vamos enumerar os passos a seguir:
Geração de uma população inicial, normalmente de modm aleatório;
Evolução dos indivíduos para determinar a idoneidade de cada um;
Determinação do número de cópias que possuirá cada indivíduo;
Seleção das partes dos cromossomos, determinação do lugar onde se vai produzir o intercâmbio de material genético;
A população resultante passará a ser a população inicial da geração seguinte, continuando o ciclo;
Utilizaremos agora, um exemplo numérico:
Primeiro Passo
O primeiro passo é gerar uma população inicial de tipo aleatório na qual vamos codificar os indivíduos. A codificação será simplesmente binária.
Por exemplo pode haver gerado os seguintes quatro indivíduos:
1 0 0 0
1 0 0 1
1 1 1 0
0 1 0 0
A seguir decodificaremos nossos indivíduos para obter o valor decimal correspondente:
8
9
14
4
Segundo Passo
Evoluiremos cada um dos indivíduos para conhecer sua idoneidade, sua adaptação ao meio artificial:
idoneidade = 2 x 8 = 16
idoneidade = 2 x 9 = 18
idoneidade = 2 x 14 = 28
idoneidade = 2 x 4 = 8
Pode-se perceber que há um indivíduo que se destaca dos demais (indivíduo 3), sendo que o indivíduo quatro se mostra pouco apto;
Agora chega o momento de se determinar com qual intensidade se vão mostrar estes indivíduos na seguinte geração. Como já dissemos, a técnica se baseia em dar-lhe maior probabilidade de sobrevivência (indivíduo 3).
2- Aplicação do Algoritmo Proposto por Holland
O enfoque deste trabalho é o problema de programação de operações em um ambiente flow shop permutacional. Em um ambiente flow shop, cada tarefa, dentre um conjunto de n tarefas, deve ser processada na mesma seqüência, em cada máquina dentre um conjunto de m máquinas.
Um caso particular de flow shop é o chamado flow shop permutacional, onde a seqüência de execução das n tarefas em cada máquina é a mesma para todas as máquinas.
Podemos observar então, que o problema consiste em encontrar uma seqüência viável dentre as (n!) existentes, considerando um certo critério(função-objetivo) para a escolha. O objetivo quase sempre é minimizar o intervalo de tempo entre o início de execução da primeira tarefa na primeira máquina e o término de execução da última tarefa na última máquina, chamado de duração total da programação (MAKESPAN).
Devido a sua natureza combinatorial, o problema flow shop permutacional é de difícil resolução ótima para casos de médio e grande porte, sendo classificado como 'NP-HARD'. Portanto a pesquisa, para a sua solução, se concentra em métodos heurísticos, que não podem garantir a qualidade da solução, sendo aceitáveis se a resposta for satisfatória em relação ao esforço computacional e à distância da solução ótima.
Algoritmos Genéticos Propostos
O algoritmo genético é um algoritmo genérico, que tenta imitar a natureza no que tange à sobrevivência do mais adaptado. Foi apresentado pela primeira vez por John Holland da Universidade de Michigan em 1975 e tem sido adaptado para a resolução de diversos problemas de otimização e aplicações de controle.
Para se obter a máxima eficiência/eficácia do algoritmo genético é necessário codificar adequadamente os elementos envolvidos no problema. No caso de programação de operações em máquinas em um ambiente flow shop podemos codificar da seguinte maneira:
a) As seqüências viáveis das tarefas são as filas(cromossomos);
b) Cada tarefa faz o papel do gene;
c) A posição que cada tarefa ocupa na seqüência é chamada de locus;
d) A função-objetivo que tem a função de determinar qual seqüência sobreviverá será o makespan.
De um modo geral podemos esquematizar um algoritmo genético como segue:
Início
Inicializar uma população G(0) com N soluções viáveis
i = 0.
Repertir
Selecionar os pais de G(0) observando o valor da função-objetivo (Reprodução).
Aplicar o operador de cruzamento nos pais (Crossover).
Aplicar o operador mutação e obter a geração G(i + 1) (Mutação).
i = i + 1
Até uma condição de parada
Fim.
Operador Reprodução
A população inicial G(0) será criada através da geração de duas soluções iniciais viáveis. Com o intuito de estudar a influência destas soluções iniciais na solução final, elas serão geradas em um primeiro caso aleatoriamente e depois em um segundo caso através de dois algoritmos encontrados na literatura, NEH(Nawaz,Enscore Jr. and Ham,1983) e FShopH (Moccellin,1993). Em cada um destes casos cada solução inicial formará uma subpopulação através do 'rotacionamento' das tarefas no sentido horário. Tomaremos para o cruzamento o melhor de cada subpopulação, ou seja, com os menores makespan. O procedimento descrito acima denominamos de operador reprodução.
Operador Cruzamento
Após escolhidos os dois indivíduos, aplicaremos o que chamamos de operador cruzamento, que não é nada mais que uma permuta entre os materiais genéticos das duas seqüências. Os operadores de cruzamento usados foram:
a) PMX (Goldberg,1989);
b) MPX (Gorges, 1989);
c) OX (Goldberg, 1989);
d) EOX (Shang and Li, 1991);
e) UM CORTE (Goldberg, 1989);
f) CX (Goldberg,1989);
g) LOX (Falkenauer and Bouffouix, 1991).
Para mais detalhes sobre esses operadores ver MOTA e MOCCELLIN (1995).
Operador mutação
Com o objetivo de aumentar a variabilidade das espécies, nós aplicaremos o operador mutação com uma freqüência de 100% . Esse operador tem a finalidade de resgatar algum material genético (seqüência) importante perdido em outras gerações. Ele apenas trocará de posição duas tarefas escolhidas aleatoriamente.
Na maioria dos textos consultados o número de gerações é de 100. Não havendo qualquer impossibilidade teórica ou prática para o aumento deste parâmetro, nós o elevamos para 120 gerações, sendo desprezível o aumento do tempo de C.P.U. na resolução dos problemas.
O tamanho da população, encontrado na literatura, foi igual ao número de tarefas de cada problema resolvido, adotando então esse procedimento para cada subpopulação.
Experimentação Computacional
Na experimentação computacional resolvemos 420 problemas, subdivididos em três grupos. O primeiro grupo de problemas, considerados de pequeno porte, totalizou 60, divididos em 6 classes de acordo com o número de tarefas 'n' e o número de máquinas 'm', para n = 10 tarefas e m = 4, 7, 10, 15, 20 ou 25 máquinas.
O segundo grupo, de problemas considerados de médio porte, foi constituído de 12 classes de problemas com n = 30 ou 50 e m = 4, 7, 10, 15, 20 ou 25, compondo 120 problemas ao todo.
O terceiro e último grupo, para problemas considerados de grande porte, temos 24 classes, sendo n = 70, 90, 100 ou 110 e m = 4, 7, 10, 15, 20 ou 25.
Os problemas em questão foram gerados aleatoriamente, sendo os tempos de processamento das tarefas números inteiros uniformemente distribuídos no intervalo [0,100].
Para comparar os diversos operadores de cruzamento usaremos a Porcentagem de Sucesso (número de vezes que o algoritmo obteve o menor makespan, isoladamente ou não) que o operador conseguiu em cada grupo de problemas.