Algoritmos Genéticos Aplicados ao

Problema da Mochila Multidimensional

Bianca de Almeida Dantas

Marcio Osshiro

Sumário

• Algoritmos Genéticos • Relembrando a Mochila 0-1 • Aplicações de AGs • Mochila Multidimensional • Representação da Mochila • AG aplicado à Mochila Multidimensional • Implementação Sequencial • AGs Paralelos • Implementação Paralela com MPI • Referências

Algoritmos Genéticos

• Algoritmos que buscam soluções para problemas de otimização e de busca com base na genética e na seleção natural da Teoria da Evolução de Darwin.

• Ideia desenvolvida por John Holland no início da década de 1970.

• Os indivíduos mais fortes, ou seja, mais adaptados ao ambiente, tem mais chance de sobreviver e gerar descendentes.

• Quando aplicamos AGs à solução de problemas, representamos as possíveis soluções como indivíduos em uma população.

• Basicamente, existem três tipos de representação dos indivíduos: ▫ Binária: genes são codificados por 0 ou 1. ▫ Gray: permite a criação de adjacências entre

cromossomos binários, na qual um cromossomo se diferencia de seus adjacentes pela modificação de um bit.

▫ Real: os genes são números reais.

• A escolha da representação a ser utilizada influencia no desempenho e depende de análise detalhada.

Figura: Esquema de funcionamento de um Algoritmo Genético

AG – População Inicial

• Uma população composta de n indivíduos (cromossomos) gerada aleatoriamente para iniciar o processo de busca por soluções para o problema em questão.

• Pode-se especificar restrições na geração da população inicial, por exemplo, permitir somente soluções válidas.

• O tamanho da população inicial precisa ser definido.

AG - Avaliação

• A cada geração (representada por uma população), os indivíduos são avaliados de acordo com sua adaptação ao ambiente. Isso é feito através de uma função de avaliação denominada fitness.

• Permite comparar indivíduos para aplicar os mecanismos de seleção para criação das novas gerações.

AG - Seleção • Processo para escolha de quais indivíduos da

população atual serão utilizados para dar origem aos indivíduos da nova geração.

• Em geral, indivíduos com maior fitness tem maior chance de serem selecionados.

• Diferentes métodos: ▫ Roleta: probabilidade de escolha de um indivíduo

proporcional ao fitness. ▫ Torneio: seleção de pequenas subpopulações e

posterior seleção do melhor de cada subgrupo. ▫ Elitismo: os melhores cromossomos são copiados

para a nova população, os demais são gerados por reprodução.

AG - Reprodução

• Realizada através da aplicação de operadores genéticos que determinarão a composição dos novos indivíduos.

• Geralmente são utilizados dois:

▫ Crossover: gera descendentes baseado nos genes de dois pais.

▫ Mutação: permite a diversificação do espaço de soluções, evitando a conversão em torno de poucas soluções boas, que representam um ótimo local.

• Tipos de crossover:

▫ Crossover de um ponto: uma posição P é escolhida aleatoriamente dentro do cromossomo e dois descendentes são gerados: um com os primeiros bits (até P) do primeiro pai e com os últimos do segundo pai, outro com os primeiros bits do segundo pai e os últimos do primeiro pai.

Figura: Exemplo de crossover de um ponto.

▫ Crossover de dois pontos: similar ao crossover de um ponto, mas são escolhidas duas posições ao invés de uma.

▫ Burst crossover: o teste para o crossover é feito para todas as posições, podendo resultar em muitos pontos de crossover, dependendo na probabilidade selecionada.

• Tipos de mutação:

▫ Mutação por indivíduo: cada indivíduo pode sofrer no máximo uma mutação em um gene aleatório.

▫ Mutação por bit: cada gene do cromossomo pode sofrer mutação.

▫ Mutação por troca: os valores de dois genes escolhidos aleatoriamente são trocados.

▫ Mutação invertida: similar à mutação por bit, mas os genes selecionados recebem o oposto do valor que possuíam anteriormente.

• Após as operações de crossover e de mutação, é necessário definir quais serão os indivíduos que devem compor a população da próxima geração.

• Todo esse processo de Avaliação – Seleção – Reprodução é repetido até que se satisfaça alguma condição ou por um número de gerações predefinido.

Aplicações de AGs

• Os problemas de otimização de grande porte tem demandado a busca por soluções eficientes computacionalmente. Os AGs se adaptam a muitos desses problemas.

• Exemplos: roteamento, agendamento, jogos, problema do caixeiro viajante, otimização de consultas.

• Iremos nos concentrar no problema da mochila multidimensional.

Relembrando a Mochila 0-1

• Dados:

▫ uma mochila de compartimento único e com uma capacidade máxima.

▫ conjunto de itens, cada qual com um peso e um valor associados.

• Quais itens podem ser carregados na mochila sem exceder sua capacidade e maximizando o valor a ser carregado?

• Formalmente:

▫ Dados um conjunto N de n objetos com valores

positivos pj, pesos wj e uma mochila de capacidade

inteira e positiva c, determine um vetor (x1, x2, ..., xn

que encontre:

𝑚𝑎𝑥 𝑝𝑗𝑥𝑗

𝑛

𝑗=1

Respeitando as condições 𝑤𝑗𝑥𝑗 ≤ 𝑐𝑛𝑗=1

e 𝑥𝑗 ∈ 0, 1 , 𝑗 = 1,… , 𝑛

Mochila Multidimensional

• Também chamado de mochila compartimentada.

• Bastante semelhante ao problema da mochila 0-1 clássico.

• Leva em consideração que a mochila possui mais de um compartimento (cada um com sua capacidade), o que acrescenta um novo conjunto de restrições.

• Formalmente:

▫ Dados um conjunto de n objetos com valores positivos

pj, pesos wj e uma mochila com m compartimentos de

capacidade inteira e positiva ci, determine um vetor (x1,

x2, ..., xn) que encontre:

𝑧 = 𝑚𝑎𝑥 𝑝𝑗𝑥𝑗

𝑛

𝑗=1

Respeitando as condições 𝑤𝑗𝑥𝑗 ≤ 𝑐𝑖 , 𝑖 = 1,… ,𝑚𝑛𝑗=1

e 𝑥𝑗 ∈ 0, 1 , 𝑗 = 1,… , 𝑛

• Vetor de valores dos itens com n posições;

• Vetor de capacidades dos compartimentos com m posições;

• Matriz m x n que representa o quanto cada item ocupa do compartimento.

• Vetor solução que especifica qual item deve ser levado ou não, composto de 0’s e 1’s.

Representação da Mochila

AG aplicado à Mochila Multidimensional

• Utilizamos a representação binária de cromossomos.

• Uma população inicial é gerada aleatoriamente. Escolhemos que somente existirão indivíduos válidos.

• A função de fitness é o cálculo do valor de z para cada indivíduo.

• Crossover de um ponto. • Mutação invertida. • Tamanho da população e número de gerações

como entrada.

Implementação Sequencial

• Código em C++

AGs Paralelos

• AGs são bem estruturados por natureza e sua paralelização não é difícil.

• Permite divisão de tarefas entre os processadores de sistemas paralelos e distribuídos.

• Diferentes modelos de paralelização:

▫ Global (Mestre-Escravo)

▫ Granularidade Grossa

▫ Granularidade Fina

▫ Híbridos Hierárquicos

Modelo Mestre-Escravo

• Um nó será o “mestre” os demais serão os “escravos”.

• O mestre conterá a população e realizará maior parte das operações do AG.

• O mestre pode atribuir algumas tarefas computacionalmente intensivas para seus discípulos e, então, espera pelas respostas.

Modelo de Granularidade Grossa

• A população é dividida entre os nós de processamento. Cada nó executa o AG em sua subpopulação.

• Para assegurar que boas soluções sejam “espalhadas”, um nó pode ocasionalmente enviar um cromossomo escolhido para os demais.

• O cromossomo recebido pelos demais nós substituirá algum outro cromossomo (em geral, o indivíduo menos adaptado).

Modelo de Granularidade Fina

• Cada nó de processamento possui um único indivíduo.

• Os nós de computação estão, em geral, organizados em uma estrutura espacial que define com quais outros nós a comunicação pode ser feita.

• Para realizar as operação genéticas, um nó deve interagir com seus vizinhos.

• Grande sobrecarga de comunicação.

Modelo Híbrido Hierárquico

• Estruturado em dois níveis.

• Por exemplo: no nível mais alto trabalha com granularidade grossa e no nível mais baixo com granularidade fina.

• Combina os benefícios de seus componentes e tem maior potencial que uma única implementação.

Implementação Paralela com MPI

• Utiliza o modelo de granularidade grossa.

• A operação de migração é realizada em intervalos de X gerações, onde o X é fornecido como entrada do programa.

• No processo de migração implementado, todos os nós escolhem o melhor indivíduo de sua população local e envia para os demais.

• Os nós substituem seus indivíduos menos aptos pelos indivíduos recebidos.

• Código C++ com MPI....

Referências

• Chu, P.C.; Beasley, J.E. A Genetic Algorithm for the Multidimensional Knapsack Problem. Journal of Heuristics. 1998.

• Hoff, A.; Løkketangen, A.; Mittet, I. Genetic Algorithms for 0/1 Multidimensional Knapsack Problems. Proceedings Norsk Informatikk Konferanse. 1996.

• Puchinger, J.; Raidl, G.R.; Pferschy, U. The Core Concept for the Multidimensional Knapsack Problem. Proceedings of the 6th European Conference. 2006.

• Yussof, S.; Razali, R.A. Na Investigation on the Effect of Migration Strategy on Parallel GA-Based Shortest Path Routing Algorithm. Communications and Network. 2012.