Har landeigenskapar betyding for folks haldningar?

Como forma de acelerar a convergˆencia do m´etodo, foi utilizado um algoritmo aleat´orio de busca local que avalia a qualidade de algumas solu¸c˜oes pertencentes `a vizi-

nhan¸ca da solu¸c˜ao analisada.

A partir de uma solu¸c˜ao s0 encontrada no espa¸co de busca irrestrito, pode-se

encontrar uma solu¸c˜ao de melhor qualidade, realizando uma busca local em sua vizinhan¸ca [31] [37], tendo como parˆametro de avalia¸c˜ao do fitness o crit´erio de otimiza¸c˜ao geral. Como o gen´otipo dos indiv´ıduos ´e composto por vari´aveis bin´arias, pode-se definir uma vizinhan¸ca de s0 como sendo

N (s0) = {si; H(s0, s1) = 1},

onde H(s0, s1) ´e a distˆancia hamming entre s0 e s1, ou seja, os gen´otipos de s0 e

s1 diferem por apenas um d´ıgito [15].

Assim, o algoritmo utilizado para a busca local foi o seguinte:

1. Tome uma solu¸c˜ao inicial s0;

2. Tome um subconjunto N′_(s

0) ⊂ N(s0);

3. Repita at´e que f (s0) ≥ f(si), ∀si ∈ N′(s0):

Fa¸ca s0 = si ∈ N′(s0), ondef (si) ≥ f(sk), ∀sk ∈ N′(s0)

Apenas alguns elementos de N (s0) podem ser analisados, pois o tamanho de

N (s0) tem crescimento superior ao polinomial conforme aumenta o n´umero de produtos

Cap´ıtulo 4

TESTES E RESULTADOS

A metodologia proposta no cap´ıtulo terceiro foi validada pela elabora¸c˜ao de testes com problemas de seq¨uenciamento Job Shop est´aticos, pr´eviamente particionados pela Tecnologia de Grupos. A metodologia foi aplicada atrav´es da sua implementa¸c˜ao em um programa computacional, possibilitando a realiza¸c˜ao de um n´umero de testes capaz de fornecer informa¸c˜oes suficientes para as conclus˜oes deste cap´ıtulo.

4.1

PROGRAMA COMPUTACIONAL

O programa computacional criado para resolver os problemas testados foi imple- mentado na linguagem C++, sendo subdividido nos seguintes m´odulos, representados na figura 4.1:

• M´odulo Inicial

Efetua a leitura do problema Job Shop particionado, identificando os subproblemas e o acoplamento entre as c´elulas de m´aquinas.

Método do Subgradiente Módulo Inicial Problema Primal Método de Resolução Algoritmo Genético Operador de Crossover Operador de Mutação Operador de Seleção Busca Local Cálculo do Fitness do Subproblema Cálculo do Fitness do Problema Geração de Números Aleatórios Subrotina Geral Método do Subgradiente Módulo Inicial Problema Primal Método de Resolução Algoritmo Genético Operador de Crossover Operador de Mutação Operador de Seleção Busca Local Cálculo do Fitness do Subproblema Cálculo do Fitness do Problema Geração de Números Aleatórios Subrotina Geral Método do Subgradiente Módulo Inicial Problema Primal Método de Resolução Algoritmo Genético Operador de Crossover Operador de Mutação Operador de Seleção Busca Local Cálculo do Fitness do Subproblema Cálculo do Fitness do Problema Geração de Números Aleatórios Subrotina Geral

Figura 4.1: Programa Computacional.

• M´etodo de Resolu¸c˜ao

Realiza a coordena¸c˜ao entre as itera¸c˜oes, fazendo a passagem dos parˆametros entre os m´odulos do M´etodo do Subgradientee do Problema Primal, verificando se o crit´erio de parada j´a foi satisfeito.

• M´etodo do Subgradiente

Calcula as novas vari´aveis duais atrav´es do M´etodo do Subgradiente (se¸c˜ao 3.2.1), tendo por base o resultado primal atual.

• Problema Primal

Controla a resolu¸c˜ao dos subproblemas pelo Algoritmo Gen´etico, para os quais passam as respectivas vari´aveis duais, fazendo o acoplamento das suas solu¸c˜oes.

Programa Computacional 66

• Algoritmo Gen´etico

Gera uma popula¸c˜ao inicial aleat´oria de 99 solu¸c˜oes para o subproblema, a cuja popula¸c˜ao ´e adicionada a melhor solu¸c˜ao da itera¸c˜ao anterior. A evolu¸c˜ao desta popula¸c˜ao de solu¸c˜oes ´e organizada at´e a sua convergˆencia para solu¸c˜ao do subpro- blema, atrav´es da aplica¸c˜ao dos Operadores Gen´eticos, em um m´aximo de 500 gera¸c˜oes.

Uma estrat´egia salvacionista ´e utilizada com a perpetua¸c˜ao do melhor indiv´ıduo de uma gera¸c˜ao para a pr´oxima gera¸c˜ao e do melhor indiv´ıduo de uma itera¸c˜ao para a pr´oxima itera¸c˜ao.

• Operador Gen´etico de Sele¸c˜ao

Realiza a escolha das solu¸c˜oes que sofrer˜ao a a¸c˜ao dos Operadores Gen´eticos de Crossover e de Muta¸c˜ao atrav´es do m´etodo Roulette Wheel (se¸c˜ao 2.3).

• Operador Gen´etico de Crossover

Aplica o Operador Gen´etico de Crossover Uniforme (se¸c˜ao 2.3) em pares de solu¸c˜oes, gerando duas novas solu¸c˜oes pertencentes `a pr´oxima gera¸c˜ao.

• Operador Gen´etico de Muta¸c˜ao

Aplica o Operador Gen´etico de Muta¸c˜ao (se¸c˜ao 2.3), a uma taxa de probabilidade de 2%, sobre a popula¸c˜ao de solu¸c˜oes.

• Busca Local

Faz uma Busca Local em um subconjunto da vizinhan¸ca com distˆancia Hamming igual a um (H(s0, si) = 1) da solu¸c˜ao analisada (se¸c˜ao 3.3).

Calcula o fitness de uma solu¸c˜ao para um subproblema, n˜ao considerando as res- tri¸c˜oes de acoplamento perdidas no processo de decomposi¸c˜ao, conforme a fun¸c˜ao 3.10 apresentada na se¸c˜ao 3.2.1.

• C´alculo do Fitness do Problema

Calcula o fitness de uma solu¸c˜ao para o problema Job Shop, composta pela uni˜ao das solu¸c˜oes dos subproblemas, considerando as restri¸c˜oes de acoplamento perdidas no processo de decomposi¸c˜ao, conforme a fun¸c˜ao 3.7 apresentada na se¸c˜ao 3.2.1.

• Gera¸c˜ao de N´umeros Pseudo-Aleat´orios

Sendo a heur´ıstica dos Algoritmos Gen´eticos composta por elementos aleat´orios, como a escolha de quais solu¸c˜oes sofrer˜ao a a¸c˜ao dos operadores gen´eticos ou quais os genes dos cromossomos pais ser˜ao copiados para os cromossomos filhos (se¸c˜ao 2.3), foi necess´aria a cria¸c˜ao deste m´odulo que possibilita a gera¸c˜ao de uma mesma seq¨uˆencia de n´umeros pseudo-aleat´orios a partir de um mesmo n´umero semente. A t´ecnica utilizada para a gera¸c˜ao destes n´umeros pseudo-aleat´orios foi o Gerador Tausworthe [19], por ser computacionalmente mais simples de ser implementada.

Para a execu¸c˜ao do programa criado, foi utilizado um computador com proces- sador Intel Celeron 800 MHz, e 64MB de mem´oria.