ALGORITMOS GENÉTICOS - Departamento de Engenharia ...paf/proj/Set2000/AlgoritmosGeneticos.pdf · Introdução 2 Estrutura do relatório O presente relatório encontra-se dividido

INSTITUTO SUPERIOR DE ENGENHARIA DO PORTO

Depar tamento de Informática

ALGORITMOS GENÉTICOS

ESCALONAMENTO AUTOMÁTICO DE REUNIÕES ESCOLARES

Trabalho curricular realizado no âmbito da disciplina de

PROJECTO

5º ano da Licenciatura em Engenharia Informática - Computadores e Sistemas

1999/2000

Eliseu Edgar da Silva Rodrigues

Agradecimentos

Aos meus orientadores, Doutor Carlos Ramos e Eng. Paulo Ferreira.

Ao Dr. Francisco Queirós, pelo apoio prestado.

Aos meus Pais e à Cristina

Índice

1 - Introdução ...............................................................................................................1

2 - Algoritmos genéticos...............................................................................................3

2 - 1 Inicialização ......................................................................................................9

2 - 2 Avaliação ..........................................................................................................9

2 - 3 Selecção ..........................................................................................................10

2 - 4 Reprodução .....................................................................................................13

2 - 4 - 1 Operador de recombinação......................................................................13

2 - 4 - 2 Operador de mutação...............................................................................16

2 - 5 Finalização ......................................................................................................16

3 - Escalonamento automático de reuniões escolares...................................................18

3 - 1 Descrição do Problema....................................................................................18

3 - 2 Modelo de representação .................................................................................19

3 - 3 Definição de parâmetros e penalizações...........................................................20

3 - 4 Execução do algoritmo genético ......................................................................22

3 - 4 - 1 Inicialização............................................................................................22

3 - 4 - 2 Avaliação................................................................................................22

3 - 4 - 3 Selecção.................................................................................................. 26

3 - 4 - 4 Reprodução.............................................................................................27

3 - 4 - 5 Finalização..............................................................................................29

3 - 5 Resultados.......................................................................................................29

3 - 6 Visualização de resultados...............................................................................32

3 - 6 - 1 Evolução das populações.........................................................................33

3 - 6 - 2 - Soluções................................................................................................33

4 - Conclusão..............................................................................................................36

Bibliografia.................................................................................................................38

Anexo 1 - Fundamentos teóricos e matemáticos..........................................................39

Anexo 2 - Glossário de termos técnicos ......................................................................51

Anexo 3 - Listagem do algoritmo genético.................................................................. 53

Introdução

1

1 - Introdu ção

O mundo à nossa volta é formado por uma enorme diversidade de formas de vida,

milhões e milhões de espécies, cada uma exibindo características particulares de

existência.

Todas estas espécies, plantas e animais têm vindo a evoluir constantemente ao longo de

milhões de anos, adaptando-se a permanentes alterações ambientais, de modo a

poderem sobreviver.

Os elementos mais fracos - menos adaptados - têm tendência a morrer, enquanto que os

mais fortes - mais adaptados - têm tendência a sobreviver e procriar, garantindo a

sobrevivência da espécie. A vida é ditada pelas leis da selecção natural

Os algoritmos genéticos, idealizados por John Holland nos anos sessenta com base nas

teorias de Darwin acerca da origem e evolução das espécies, são algoritmos de pesquisa

baseados em mecanismos de selecção natural que exploram a ideia de que os elementos

mais adaptados de um determinado conjunto têm maior probabili dade de sobrevivência

do que os menos adaptados.

Utili zando uma estrutura denominada população, formada por um conjunto de

indivíduos que representam eventuais soluções para um determinado problema em

estudo, os algoritmos genéticos vão gerando iterativamente novas populações a partir

dos indivíduos mais adaptados da população anterior, de modo a obterem uma nova

população cujos indivíduos representem, conceptualmente, um conjunto de soluções

mais apropriadas à resolução do respectivo problema. Por vezes, tendo por objectivo

evitar a estagnação da população e, de certo modo, manter a sua diversidade, os

algoritmos genéticos efectuam a introdução de novos valores na população, o que lhes

permite garantir que a procura de soluções é realizada em todo os pontos do espaço de

pesquisa do problema.

Atendendo às características dos algoritmos genéticos, pode-se considerar que

constituem uma estratégia de pesquisa apropriada para conjuntos de soluções muito

vastos e complexos.

Introdução

2

Estrutura do relatório

O presente relatório encontra-se dividido em quatro capítulos.

O primeiro capítulo faz uma breve introdução aos algoritmos genéticos e às suas

origens.

No capítulo seguinte é feita uma abordagem profunda aos principais conceitos

associados aos algoritmos genéticos, analisando-se os diversos mecanismos por eles

utili zados.

O terceiro capítulo expõe um caso prático de aplicação dos algoritmos genéticos - o

escalonamento automático de reuniões escolares - apresentando no final os resultados

obtidos através do uso de uma aplicação especificamente desenvolvida para o problema,

assim como um estudo comparativo entre vários conjuntos de parâmetros.

Por fim, no último capítulo, é feita uma conclusão muito resumida onde se relembram

os principais temas abordados.

Com o objectivo de explicar os fundamentos teóricos e matemáticos que suportam os

algoritmos genéticos, foi efectuado um breve estudo que, por não se enquadrar

directamente com o caso prático que originou o presente trabalho, se encontra em

anexo.

Algoritmos Genéticos

3

2 - Algoritmos genéticos

Os algoritmos genéticos evidenciam-se no campo dos métodos de pesquisa e

optimização através da assimilação do paradigma Darwiniano da evolução das espécies,

estando a sua terminologia associada a conceitos essenciais da genética.

O conceito de população Mendeliana como conjunto de indivíduos da mesma espécie é

alargado a espécies artificiais cujos indivíduos são, normalmente, representados por

sequências de números - genótipo - que constituem o seu património genético,

determinando as suas características - fenótipo.

Os problemas de optimização estão normalmente associados à satisfação de restrições

que definem um universo intrínseco de soluções. Os algoritmos genéticos são

responsáveis por determinar a solução óptima para o problema, ou, dependendo das

limitações impostas e do tempo disponível para execução do algoritmo, uma solução

aceitável. Os elementos da população - designados por indivíduos ou cromossomas -

correspondem a eventuais soluções, ligando o espaço real das soluções associadas ao

problema que se pretende optimizar a um espaço fictício de pesquisa. Os algoritmos

genéticos actuam sobre o espaço fictício, interpretando os resultados no espaço real

através de uma função de correspondência.

À semelhança do que acontece na evolução natural, os cromossomas, através dos genes,

constituem a base material da hereditariedade. Os genes são elementos que

representando determinados valores - normalmente numéricos - em sequência formam

os cromossomas.

Nos algoritmos genéticos a reprodução dos cromossomas é efectuada em função de uma

selecção artificial, considerando-se mais adaptados os indivíduos que melhor satisfaçam

as restrições impostas pelo problema.

A avaliação do nível de adaptação dos indivíduos às restrições impostas é efectuada

através de uma função, denominada função de avaliação, que associa a cada indivíduo

da população um determinado valor numérico representativo da sua adaptação à

resolução do problema. Após a avaliação da adaptação dos indivíduos da população é

realizada, de forma proporcional a essa adaptação, a selecção de pares de cromossomas

para reprodução.


4

A reprodução cromossomática consiste na troca de partes complementares de

cromossomas. Cada par de cromossomas ascendentes gera um novo par de

cromossomas descendentes, formado por sequências numéricas resultantes da

contribuição mútua e complementar dos seus ascendentes. Com o objectivo de

assegurar a existência de diversidade na população, existe um mecanismo de mutação,

através do qual o locus1 de determinados genes pode ser ocupado por um novo gene -

alelo - proveniente do património genético do problema.

A reprodução dos indivíduos de uma população promove o aparecimento de novos

indivíduos - descendentes - que constituem uma nova população assinalando o termo de

um ciclo do algoritmo genético.

O ciclo de um algoritmo genético pode ser genericamente descrito do seguinte modo:

• Geração aleatória de n cromossomas que formam a população inicial - Inicialização;

• Avaliação individual dos cromossomas;

• Selecção de n/2 pares de cromossomas;

• Reprodução - recombinação e mutação - dos pares de cromossomas seleccionados;

• Finalização.

Ao longo das próximas secções serão analisados, com base no caso concreto do

escalonamento automático de reuniões escolares, os aspectos essenciais da estrutura de

um algoritmo genético e as suas operações básicas: a inicialização, a avaliação, a

selecção, a reprodução e a finalização.

Descrição do problema

Admita-se, como exemplo, uma situação em que existem disponíveis dois dias para

efectuar a marcação de reuniões escolares de oito turmas. Em cada dia é possível

realizar no máximo quatro sessões de reunião, duas de manhã e duas de tarde, podendo-

se verificar a ocorrência de reuniões em simultâneo desde que não envolvam turmas

com docentes comuns.

1 posição ocupada pelo gene relativamente ao cromossoma.


5

O corpo docente das oito turmas é seguidamente apresentado na tabela 1.

Turma Professor

P1 (Director de Turma)

P2

P3 T1

P4


P6

P7 T2

P8

P1


P7 T3

P8


P4

P5 T4

P6

Turma Professor

P1

P2

P5

T5


P3


P7

T6

P8

P1

P4

P5

T7


P2

P3

P6 T8


Tabela 1 - Corpo docente

O escalonamento das reuniões escolares é condicionado pela satisfação de algumas

normas e restrições, umas de ordem física - impossibili dade por parte dos professores de

assistir a várias reuniões em simultâneo - e outras de ordem pedagógica - os professores

que exercem cargos de direcção de turma não devem ser solicitados para sessões a

realizar imediatamente após o término de reuniões relativas a turmas em que exerçam

esse cargo.

Na elaboração do calendário de reuniões devem ainda, sempre que possível, ser

efectuados esforços no sentido de minimizar o número total de sessões a realizar e o

número total de deslocações dos docentes.

Seguidamente são enumeradas as restrições propostas para a resolução do problema em

análise.


6

R1. Os professores não podem assistir a várias reuniões em simultâneo;

R2. Os professores não devem assistir a sessões imediatamente após o término de

reuniões relativas a turmas em que exerçam o cargo de director de turma;

R3. O número total de sessões de reunião não deve ser superior ao número máximo de

turmas por professor;

R4. O número total de deslocações de cada professor não deve ser superior ao valor da

divisão do número de turmas a seu cargo pelo número máximo disponível de

sessões de reunião por dia, arredondado por excesso.

Modelo de representação

A escolha do modelo de representação de um determinado problema assume elevada

importância na sua resolução, devendo ser efectuada - uma vez que estreita

inevitavelmente o modo de pesquisa e representação das soluções - em função do

método que se pretende utili zar e das suas especificações concretas.

No caso particular dos algoritmos genéticos, atendendo a que operam sobre sequências

de valores codificados, é determinante que os problemas sejam bem representados pois

das suas representações dependem a pesquisa e a qualidade das soluções.

O modelo de representação dos algoritmos genéticos consiste na codificação de

soluções em sequências de valores que posteriormente serão interpretados por uma

função de avaliação. Os valores utili zados na codificação das soluções são

normalmente, sem perda de consistência dos fundamentos teóricos dos algoritmos

genéticos, de um dos seguintes tipos: binário - são usados os números 0 e 1; natural -

são usados números naturais; real - são usados números reais.

A escolha do modelo de representação deve ser realizada tendo em consideração o

princípio dos blocos construtores significativos2 e o princípio dos alfabetos mínimos3.

2 "Principle of meaningful building blocks" - segundo este princípio, a codificação deve ser escolhida de

modo a que os esquemas de pequena ordem - com poucas posições fixas - sejam relevantes para o

problema em análise. [Goldberg, 89]. 3 "Principle of minimal alphabets" - segundo este princípio deve ser escolhido o alfabeto de menor

cardinalidade que permita assegurar uma expressão natural do problema. [Goldberg, 89].


7

Seguidamente, é apresentado um possível modelo de representação para o problema em

análise - o escalonamento automático de reuniões escolares.

O conjunto H4, constituído pelos valores {1, 2, 3, 4, 5, 6, 7, 8}, representa os oito

períodos de tempo disponíveis para marcação de reuniões, correspondendo o valor 1 ao

primeiro período do turno da manhã do primeiro dia, o valor 2 ao segundo período do

turno da manhã do primeiro dia e, análoga e sucessivamente, o valor 8 ao último

período do turno da tarde do segundo dia, como se demonstra na tabela 2.

1º Dia 2º Dia

1º Tempo 1 5 Turno da Manhã

2º Tempo 2 6

1º Tempo 3 7 Turno da Tarde

2º Tempo 4 8

Tabela 2 - Períodos de tempo disponíveis para marcação de reuniões

O calendário de reuniões é representado por sequências numéricas de oito valores,

eventualmente repetidos, contidos no conjunto H. O primeiro valor identifica o período

de tempo em que se realizará a reunião referente à turma 1, o segundo valor identifica o

período de tempo em que se realizará a reunião referente à turma 2 e, sucessivamente, o

último valor da sequência identifica o período de tempo em que se realizará a reunião

referente à turma 8, representando cada sequência numérica uma eventual solução para

o problema.

Analisando, por exemplo, uma sequência constituída pelos valores 6 3 2 7 1 1 8 7,

verifica-se que a reunião referente à turma 1 se realizará no sexto período de tempo, a

reunião referente à turma 2 se realizará no terceiro período de tempo e, por analogia, a

reunião referente à turma 8 se realizará no sétimo período de tempo.

4 David E. Goldberg utili za na sua notação a letra H como abreviatura da palavra hiperplano.


8

1º Dia 2º Dia

T5 1º Tempo

T6

Turno da Manhã

2º Tempo T3 T1

T4 1º Tempo T2

T8 Turno da Tarde

2º Tempo T7

Tabela 3 - Calendár io de reuniões resultante da sequência numérica 6 3 2 7 1 1 8 7

Observando a tabela 3 é possível identificar a ocorrência de reuniões simultâneas no

primeiro período de tempo do turno da manhã do primeiro dia e no primeiro período de

tempo do turno da tarde do segundo dia, verificando-se no segundo caso a não

satisfação de uma restrição de ordem física, dado que as turmas 4 e 8 cujas reuniões se

realizam simultaneamente têm os docentes 3 e 6 em comum.

Apesar do problema em análise ser bastante simples, na medida em que é constituído

por um pequeno subconjunto de turmas e professores, o seu espaço de pesquisa é

composto por 16.777.216 pontos distintos5, o que torna impraticável a exploração

sistemática e extensiva de todas as soluções.

Operações básicas

O mecanismo dos algoritmos genéticos é formado pelas seguintes operações básicas:

• Inicialização;

• Avaliação;

• Selecção;

• Reprodução;

• Finalização.

5 Atendendo a que existem oito turmas e que as respectivas reuniões podem ocorrer num de oito períodos

de tempo, a dimensão do espaço de pesquisa é determinada através da expressão 8×8×8×8×8×8×8×8 = 88.


9

2 - 1 Inicialização

O processo de inicialização dos algoritmos genéticos consiste na geração aleatória de n

sequências numéricas - cromossomas - formadas por oito elementos6 - genes -

representativos de valores contidos no alfabeto7 do problema, eventualmente repetidos.

Cada sequência numérica representa um calendário de reuniões - fenótipo - codificado

segundo o modelo de representação - genótipo -, constituindo o conjunto de todas as

sequências geradas - indivíduos - a população inicial.

O número de indivíduos das populações iniciais - n - é determinante na resolução dos

problemas, exercendo influência directa sobre a eficácia dos algoritmos. Populações

constituídas por um número demasiado pequeno de indivíduos convergem rápida e

prematuramente para estados em que todos os cromossomas são semelhantes,

implicando que os espaços de pesquisa das soluções não sejam devidamente explorados.

Populações com um número elevado de indivíduos incrementam exponencialmente o

tempo de execução do algoritmo genético, sem que se verifiquem ganhos significativos

no processo de convergência.

O número de indivíduos de uma população pode ser idealizado, segundo formulações

teóricas, através de cálculos baseados na dimensão do espaço de pesquisa de soluções,

na variância do processo de selecção e em conhecimentos relativos à evolução das

soluções.

2 - 2 Avaliação

O processo de avaliação tem por objectivo, como o próprio nome indica, determinar o

valor de adaptação das soluções geradas.

Através de uma função de avaliação, especificamente desenvolvida para cada problema

de optimização, é efectuada a avaliação de todos os indivíduos da população, no

sentido de aferir as suas adaptações.

6 Um elemento por cada turma. 7 Conjunto de valores - alelos - que cada gene pode assumir. No caso em análise, o alfabeto é formado

pelo conjunto de valores { 1 2 3 4 5 6 7 8} .


10

A função de avaliação, também designada por função objectiva, pode ser de natureza

matemática - o seu valor é calculado através de expressões matemáticas - ou de natureza

empírica - o seu valor é calculado através de penalizações resultantes da não satisfação

de restrições. No caso em análise - o escalonamento automático de reuniões escolares -

a função de avaliação f(c), seguidamente apresentada, é de natureza empírica.

44332211

1)(

RPRPRPRPcf

×+×+×+×=

Os valores P1, P2, P3 e P4 correspondem, respectivamente, aos valores das

penalizações atribuídas ao cromossoma c por cada infracção - não satisfação - das

restrições R1, R2, R3 e R4, anteriormente enumeradas.

2 - 3 Selecção

Após a avaliação, cada indivíduo da população tem associado um valor numérico que

traduz o seu nível de adaptação às restrições do problema.

A fase de selecção, revestida de elevada importância no contexto dos algoritmos

genéticos, consiste na escolha de n indivíduos, eventualmente repetidos, para posterior

reprodução.

A escolha dos indivíduos mais adaptados da população através de um operador de

selecção determinístico aparenta garantir o nível ideal de pressão selectiva, contudo,

uma escolha demasiado elitista reduz a diversidade da população impossibili tando que

todo o espaço de pesquisa de soluções seja devidamente explorado. É importante

permitir que indivíduos pouco adaptados tenham probabili dade, embora reduzida, de ser

seleccionados.

Ao longo dos últimos anos foram propostos e estudados diversos operadores de

selecção, entre os quais assumem especial relevo os operadores de selecção

proporcional e os operadores de selecção por ordem de classificação.

Os operadores de selecção proporcional atribuem as probabili dades de selecção em

função da relação existente entre o nível individual de adaptação dos indivíduos e o

nível global de adaptação da população. Os operadores de selecção por ordem de


11

classificação atribuem as probabili dades de selecção em função de uma tabela

classificativa.

Um dos métodos de selecção proporcional mais comuns é o método da roleta8, segundo

o qual a cada indivíduo i da população é atribuída uma probabili dade de selecção Ps(i),

calculada através do quociente entre a sua adaptação e o somatório das adaptações de

todos os indivíduos da população.

( ) ( )( )∑

=

=n

j

s

jf

ifiP

1

para i = 1,...,n

8 Método de selecção "Roulette Wheel Parent Selection". [Holland, 75].

I f(i) Ps(i)

1 1/2.5 0.4

2 1/4 0.25

3 1/4 0.25

4 1/10 0.1

25%

10%

40%

25%

Figura 1 - Selecção proporcional (probabili dades de selecção segundo o método da roleta)

Segundo este método a selecção de indivíduos é realizada através da simulação de n

rotações de uma roleta cujas divisões representam os n indivíduos da população. Após o

término de cada rotação, o indivíduo correspondente à divisão indicada pelo ponteiro é

seleccionado.


12

Além do método da roleta foram ainda estudados outros operadores de selecção

proporcional tais como, por exemplo, o método de selecção universal estocástica9 -

semelhante ao método da roleta mas com a particularidade de que a roleta tem n

ponteiros uniformemente espaçados bastando simular uma rotação para seleccionar os n

indivíduos - e o método de selecção remanescente estocástica10 - calculado o valor da

probabili dade de selecção de um indivíduo i, a parte inteira de Ps(i) representa o número

mínimo de vezes que o indivíduo i será garantidamente seleccionado. A parte

fraccionária de Ps(i) representa a probabili dade que o indivíduo i tem de ser novamente

seleccionado para o preenchimento das posições restantes.

A evolução das populações ao longo das gerações tende a normalizar os valores de

adaptação dos indivíduos o que se traduz num decréscimo da pressão de selecção.

Fundamentados no facto de que a eficácia dos operadores de selecção proporcional

depende da existência de diferenças substanciais entre os valores de adaptação dos

indivíduos mais adaptados e os valores de adaptação dos indivíduos menos adaptados,

surgiram os operadores de selecção por ordem de classificação, cujas pressões de

selecção são independentes dos valores de adaptação dos indivíduos, não se

verificando, portanto, a ocorrência de decréscimos.

O método de selecção por torneio11 - um dos métodos de selecção por ordem de

classificação - consiste na organização de n torneios entre dois ou mais indivíduos da

população escolhidos aleatoriamente. O indivíduo seleccionado é o que estiver em

posição de superioridade no confronto directo entre os valores de adaptação.

A selecção de indivíduos pode também ser realizada através de métodos mistos

resultantes da combinação de operadores de selecção proporcionais e de operadores de

selecção por ordem de classificação. Um exemplo desses métodos de selecção é a

selecção com normalização linear, em que os indivíduos da população são ordenados

por ordem decrescente de adaptação e lhes é atribuída - segundo uma função linear -

uma probabili dade de selecção em conformidade com a posição ocupada.

9 Método de selecção "Stochastic Universal Selection" 10 Método de selecção "Stochastic Remainder Selection" 11 Método de selecção "Tournament Selection"


13

i f(i) Classificação(i) Ps(i)

1 1/2.5 1 0.45

2 1/4 2 0.22

3 1/4 2 0.22

4 1/10 4 0.11

22%

11%

45%

22%

Figura 2 - Selecção com normalização linear

Os operadores de selecção podem ser complementados através do uso de mecanismos

de elitismo - técnicas através das quais um determinado subconjunto composto pelos

melhores indivíduos da população actual é automaticamente seleccionado e inserido na

nova população.

Os mecanismos de elitismo permitem aumentar significativamente o desempenho dos

algoritmos genéticos, garantindo que as melhores soluções da geração actual não se

perdem nem são destruídas durante a fase de reprodução.

2 - 4 Reprodu ção

Na fase de reprodução os n indivíduos seleccionados - progenitores - são emparelhados

dois a dois, de modo a que cada par gere dois novos indivíduos - descendentes.

O processo de reprodução é composto por dois operadores distintos - o operador de

recombinação e o operador de mutação - limitados por probabili dades de ocorrência.

2 - 4 - 1 Operador de recombinação

Os operadores de recombinação admitem várias modalidades tais como o cruzamento

num ponto12, o cruzamento em dois pontos13 e o cruzamento uniforme,14 cada uma delas

com características muito particulares.

12 "Single-point crossover". [Holland, 75]. 13 "Two-point crossover". [Davis, 91].


14

A escolha do operador de recombinação deve ser efectuada tendo em consideração o

tipo de problema que se pretende resolver, pois a evolução do processo de convergência

depende do operador de recombinação utili zado.

a) Cruzamento num ponto

O operador de cruzamento num ponto selecciona aleatoriamente um ponto de corte na

estrutura dos cromossomas progenitores.

Os cromossomas descendentes são constituídos pelos genes resultantes da justaposição

das sequências complementares dos seus progenitores, definidas pelo ponto de

cruzamento.

Cromossomas progenitores Cromossomas descendentes

6 3 2 �

7 1 1 8 7 6 3 2 5 1 6 3 8

4 2 1 �

5 1 6 3 8 4 2 1 7 1 1 8 7

↑

Ponto de corte

Figura 3 - Cruzamento num ponto

A figura 3 ilustra um exemplo do processo de cruzamento num ponto. O ponto

seleccionado para corte foi o ponto três15.

b) Cruzamento em dois pontos

O operador de cruzamento em dois pontos selecciona aleatoriamente dois pontos de

corte na estrutura dos cromossomas progenitores.

A constituição de cada um dos cromossomas descendentes é idêntica à constituição de

um dos progenitores, à excepção da sequência de genes contida entre os pontos de

cruzamento, que é idêntica à do outro progenitor.

14 "Uniform Crossover". [Syswerda, 89].


15


6 3 � 2 7 1 1 � 8 7 6 3 1 5 1 6 8 7

4 2 � 1 5 1 6 � 3 8 4 2 2 7 1 1 3 8

↑ ↑

Pontos de corte

Figura 4 - Cruzamento em dois pontos

A figura 4 ilustra um exemplo do processo de cruzamento em dois pontos. Os pontos

seleccionados para corte foram os pontos dois e seis.

c) Cruzamento uniforme

O operador de cruzamento uniforme selecciona aleatoriamente um determinado número

de genes - e respectivos locus - na estrutura dos cromossomas progenitores.

Os genes cujos locus forem seleccionados são cruzados. Os restantes mantêm-se

inalterados.

O exemplo da figura 5 permite visualizar um cruzamento uniforme. Os locus

seleccionados para cruzamento foram os locus dois, quatro, seis e sete.


6 3 2 7 1 1 8 7 6 2 2 5 1 6 3 7

4 2 1 5 1 6 3 8 4 3 1 7 1 1 8 8

↑ ↑ ↑ ↑

Locus seleccionados

Figura 5 - Cruzamento uniforme

15 O ponto de corte pode pode-se situar entre 1 e l -1, correspondendo l ao número de genes dos

cromossomas, ou seja, ao seu comprimento (length).


16

2 - 4 - 2 Operador de mutação

Após o cruzamento, cada descendente gerado pelo processo de cruzamento possui uma

estrutura ordenada de genes da mesma espécie da dos seus ascendentes.

A mutação, processada ao nível dos genes com probabili dade de ocorrência

normalmente baixa16, consiste na substituição de determinados genes dos cromossomas

por outros genes - alelos - existentes no património genético da população.

Admitamos que o gene representado pelo valor sete no quarto locus do segundo

descendente da figura 5 foi seleccionado para mutação, e que o valor dois - escolhido

aleatoriamente a partir do conjunto H = {1, 2, 3, 4, 5, 6, 7, 8} - o irá substituir.

A constituição do segundo cromossoma será então a seguinte:

Cromossoma (antes da mutação) Cromossoma (após a mutação)

4 3 1 7 1 1 8 8 4 3 1 2 1 1 3 8

↑

Locus seleccionado

Figura 6 - Mutação

2 - 5 Finalização

Após as operações de inicialização, avaliação, selecção e reprodução, é atingida a

última operação do ciclo básico de um algoritmo genético - a finalização.

Os critérios de finalização - estabelecidos em função dos objectivos do problema a

optimizar - determinam se o algoritmo deve continuar o seu processamento, executando

mais uma iteração, ou deve ser terminado.

O término do algoritmo pode dever-se a um dos seguintes factores: foi atingida uma

solução que satisfaz todas as restrições impostas pelo problema; foi atingido o limite

máximo de iterações estabelecido para o algoritmo genético. Neste caso, uma vez que

16 Probabili dades de mutação elevadas transformariam o algoritmo genético num método de busca

aleatório.


17

não foi atingida nenhuma solução óptima, é eleita a solução cuja adaptação às restrições

impostas pelo problema se mostrou mais aceitável.

Figura 7 - Ciclo básico de um algor itmo genético

Selecção

Reprodução

Iniciali zação

Avaliação

Fim

Finalização ?

Sim

Não

Escalonamento automático de reuniões escolares

18

3 - Escalonamento automático de reuniões esc olares

Todos os anos é perdido um elevado número de horas na elaboração de calendários de

reuniões intercalares, uma tarefa de enorme complexidade que por vezes leva à

especialização de pessoas nessa área.

No decurso do presente capitulo será apresentado um estudo teórico-prático realizado

no âmbito do escalonamento automático de reuniões escolares através de algoritmos

genéticos.

3 - 1 Descrição do Prob lema

O problema da calendarização de reuniões escolares é caracterizado pela adjudicação de

períodos de tempo às turmas da escola, um a cada turma, de modo a que se realizem as

respectivas reuniões.

A adjudicação dos períodos de tempo é condicionada pela satisfação de algumas normas

e restrições de ordem física e pedagógica, enumeradas na tabela 4.

Restrição Descrição

R1 Os professores não podem assistir a várias reuniões em simultâneo.

R 2 Os professores não devem assistir a reuniões imediatamente após o término

de reuniões relativas a turmas em que exerçam o cargo de director de turma.

R 3 O número total de sessões de reunião não deve ser superior ao número

máximo de turmas por professor.

R 4

O número total de deslocações de cada professor não deve ser superior ao

valor da divisão do número de turmas a seu cargo pelo número máximo

disponível de sessões de reunião por dia, arredondado por excesso.

Tabela 4 - Restr ições propostas para o escalonamento automático de reuniões escolares

A primeira restrição justifica-se pelo facto de que é fisicamente impossível a presença

de um docente em várias reuniões em simultâneo; a segunda, de ordem pedagógica,


19

fundamenta-se no facto de que após o término de uma reunião o docente que exerce o

cargo de director de turma deve ter disponibili dade de tempo para tomar eventuais

notas; as terceira e quarta restrições são importantes na medida em que permitem

minimizar o número de sessões de reunião necessárias e o número de deslocações17 dos

professores à escola.

A não satisfação das restrições enumeradas pode tornar o calendário de reuniões pouco

viável ou mesmo impossível, caso se verifiquem violações da primeira restrição.

3 - 2 Modelo de representação

O modelo de representação é codificado por sequências de números naturais

representativos dos períodos de tempo disponíveis para realização de reuniões.

Assumindo a existência de cinco dias disponíveis para realização de reuniões e que em

cada dia podem ser efectuadas quatro sessões de reunião, duas de manhã e duas de

tarde, é proposto o seguinte alfabeto

H = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}

cujo significado se pode observar na tabela 5.

1º Dia 2º Dia 3º Dia 4º Dia 5º Dia

1º Tempo 1 5 9 13 17

Man

hã

2º Tempo 2 6 10 14 18

1º Tempo 3 7 11 15 19

Tar

de

4º Tempo 4 8 12 16 20

Tabela 5 - Períodos de tempo representados pelo alfabeto proposto

17 Esta medida assume elevada importância se for tido em conta que as reuniões intercalares geralmente


20

Com base no alfabeto proposto é possível gerar a população inicial, sendo os seus

cromossomas constituídos por um número t de genes equivalente ao total de turmas

existentes na escola. O locus de cada gene representa uma turma.

O modelo matricial proposto para a representação da população do problema é

apresentado na tabela 6.

t genes

G1 G2 ... Gt-1 Gt

C1

C2

...

Cn-1

n cr

omos

som

as

Cn

Tabela 6 - Modelo matr icial proposto para representação da população

As linha da matriz são formadas por sequências numéricas codificadas - genótipo -

cujos valores representam possíveis soluções - fenótipo; as colunas representam as datas

de realização das reuniões - períodos de tempo seleccionados a partir do conjunto H.

3 - 3 Definição de parâmetros e penalizações

A execução do algoritmo genético pressupõe a definição de uma série de parâmetros e

penalizações.

Observe-se, com recurso à figura 8, proveniente da aplicação especificamente

desenvolvida para o problema do escalonamento automático de reuniões no âmbito do

presente projecto, alguns parâmetros que é necessário definir.

decorrem durante os períodos de férias.


21

Figura 8 - Parametr ização do algor itmo genético

Como se pode observar, é possível parametrizar os vários mecanismos anteriormente

estudados: operadores de selecção e recombinação, probabili dades de recombinação,

mutação e inversão, número de gerações e tamanho da população. As diferentes

combinações de parâmetros, como se verá mais à frente, conduzem a diferentes

resultados.

Após a definição dos parâmetros, é necessário atribuir valores às penalizações

resultantes de infracções às restrições do problema.

A figura 9 ilustra um possível conjunto de valores de penalização. O elevado valor da

penalização da restrição R1 deve-se ao facto de que a sua não satisfação implica que o

calendário associado seja impossível. As restantes restrições, apesar de não serem de

carácter exclusivo, devem reflectir a gravidade que lhes está associada, facto pelo qual

os valores apresentados obtidos experimentalmente, parecem ser os mais adequados.

Figura 9 - Penalizações das restr ições do problema


22

3 - 4 Execução do algoritmo genético

3 - 4 - 1 Inicialização

A inicialização consiste na geração de quatro18 cromossomas constituídos por cinquenta

e quatro19 genes, um por cada turma, cujos valores são aleatoriamente seleccionados a

partir do alfabeto anteriormente definido.

3 - 4 - 2 Avaliação

A avaliação dos cromossomas é efectuada através do cálculo da penalização total

resultante das infracções às quatro restrições estabelecidas.

Descodificação dos cromossomas

Considere-se o cromossoma representado pela sequência: 6 3 4 1 2 1 9 8 (...) 19 13.

G1 G2 G3 G4 G5 G6 G7 G8 (...) G53 G54

6 3 4 1 2 1 9 8 (...) 19 13


1º Tempo 1

Turma 4

Turma 6

5

9

Turma 7

13

Turma 54

17

Man

hã

2º Tempo 2

Turma 5

6

Turma 1

10 14 18

1º Tempo 3

Turma 2

7 11 15 19

Turma 53

Tar

de

4º Tempo 4

Turma 3

8

Turma 8

12 16 20

Figura 10 - Descodificação dos cromossomas

18 Valor definido para o parâmetro "Tamanho da População". 19 O número total de turmas cujas reuniões se pretende escalonar.


23

Através da figura 10 é possível observar que a descodificação dos cromossomas é

efectuada adjudicando à turma 1 o período de tempo 6, à turma 2 o período de tempo 3

e assim sucessivamente até que à turma 54 seja adjudicado o período de tempo 13. O

período de tempo a que a reunião de uma turma t é adjudicada é identificado pelo valor

do gene cujo locus é t.

Cálculo do número de infracções à restr ição R1

Após a descodificação das soluções é obtida uma lista com todas as reuniões

adjudicadas a cada período de tempo. Analisando o corpo docente das turmas agendadas

para cada sessão é possível verificar a existência de reuniões que envolvam em

simultâneo os mesmos professores.

Na figura 10, por exemplo, para determinar se existem professores comuns às turmas

cujas reuniões se realizam no primeiro período de tempo basta comparar os corpos

docentes das turmas 4 e 6. Se se verificar a existência de docentes comuns às duas

turmas, o número de infracções é incrementado de acordo com o número de professores

em conflito.

Com o objectivo de flexibili zar o problema do escalonamento automático de reuniões e

atendendo ao facto de que alguns professores, por exemplo os professores de educação

moral e religião católica, são docentes de um elevado número de turmas, foi

desenvolvido um mecanismo que permite despenalizar a convocação - e respectiva

ausência - de professores para reuniões simultâneas. Nesta situação as infracções à

primeira restrição são ignoradas.

A figura 11 ilustra o formulário que permite despenalizar a ausência de professores em

reuniões simultâneas. O professor 53, visualizado na figura, é docente da disciplina de

educação moral e religião católica em trinta e duas turmas de uma escola secundária

Portuguesa.


24

Figura 11 - Despenalização da ausência de professores em reuniões simultâneas


As infracções à restrição R2 resultam da existência de reuniões que envolvam directores

de turma cuja reunião referente à turma em que exercem esse cargo tenha decorrido no

período de tempo imediatamente anterior20.

O valor do número de infracções é calculado através da contagem do número de

reuniões agendadas para o período p+1 que envolvam directores de turmas cujas

reuniões tenham decorrido no período p.

Retomando a figura 10, para determinar se a restrição R2 é violada no segundo período,

basta verificar se os directores das turmas 4 e 6 são docentes da turma 5. Em caso

afirmativo o número de infracções à segunda restrição é aumentado proporcionalmente

ao número de directores de turma envolvidos.


O número ideal de sessões de reunião pode ser calculado de acordo com o número

máximo de turmas em que cada professor lecciona.

20 Excepto em situações em que a reunião referente à turma em que exercem cargo de direcção ocorra no

último período de tempo do dia.


25

Assumindo que o professor 1 é docente de dez turmas e que o professor 2 é docente de

8 turmas, o número ideal de sessões seria dez, pois qualquer valor superior implicaria

que o professor 1 estivesse inactivo durante pelo menos uma sessão e qualquer valor

inferior implicaria a sua presença simultânea em várias reuniões.

Assim, para calcular quantas infracções foram cometidas relativamente à restrição R3

torna-se necessário determinar o número ideal de sessões de reunião e subtraí-lo ao

valor total de sessões efectivamente marcadas - calculado através da contagem das

sessões com reuniões agendadas.

No exemplo da figura 10 estão calendarizadas nove sessões21.


A última restrição refere-se ao número de deslocações à escola realizadas por cada

docente, sendo a sua penalização calculada em função do número de sessões que é

possível efectuar em cada dia e do número de turmas leccionadas por cada professor.

Considerando novamente os professores 1 e 2, docentes de dez e oito turmas,

respectivamente, observa-se que os seus números ideais de deslocações22 seriam

3410 = e 248 = .

O número de infracções à restrição R4 resulta do somatório das diferenças entre o

número de deslocações efectivas - calculadas com base no número de dias em que os

professores têm pelo menos uma reunião - e o número ideal de deslocações à escola de

cada professor.

Cálculo do valor de adaptação dos cromossomas

Após o cálculo do número de vezes que as restrições R1, R2, R3 e R4 não são

satisfeitas, o cálculo do valor de adaptação dos cromossomas é efectuado através da

seguinte fórmula23

21 Note-se que o exemplo apenas representa a descodificação de um subconjunto do cromossoma formado

por dez genes. 22 O número ideal de deslocações do professor Pi é obtido pela expressão Pi = Ti / S em que Ti

representa o número de turmas do professor i e S representa o número máximo disponível de sessões de

reunião por dia.


26

44332211

1)(

RPRPRPRPcf

×+×+×+×=

onde P1, P2, P3 e P4 representam, respectivamente, os valores de penalização atribuídos

às infracções das primeira, segunda, terceira e quarta restrições e R1, R2, R3 e R4

representam o número de infracções verificadas relativamente às mesmas.

Assumindo que a descodificação completa do cromossoma da figura 10 revela que as

restrições R1, R2, R3 e R4 foram violadas oito, cinco, duas e vinte vezes,

respectivamente, o valor de adaptação do referido cromossoma seria o seguinte

8540

1

20205008000

1

201210510081000

1)( =

+++=

×+×+×+×=cf

3 - 4 - 3 Selecção

A selecção de cromossomas, no contexto da aplicação desenvolvida, pode ser efectuada

através de um de dois operadores: um operador proporcional - o método de selecção da

roleta - ou um operador misto - o método de selecção com normalização linear - que

combina características de selecção proporcional e de selecção por ordem de

classificação.

Segundo o método de selecção da roleta a probabili dade de selecção dos cromossomas é

proporcional às suas adaptações e calculada através da fórmula

∑=

=n

j

s

jf

cfcP

1

)(

)()(

em que a função f() representa o valor de adaptação e n, neste caso concreto, é quatro;

segundo o método de selecção com normalização linear, a probabili dade de selecção é

determinada através da criação de uma tabela classificativa ordenada por ordem

23 No caso dos valores R1, R2, R3 e R4 serem nulos – solução óptima - o denominador deve assumir o

valor 1 de modo a que, por um lado, não seja executada uma divisão por zero, e por outro, a percentagem

de adaptação assuma o valor 1, ou seja, 100%.


27

decrescente dos valores de adaptação dos cromossomas, e da aplicação de uma função

linear que atribui probabili dades de selecção de acordo com a posição ocupada.

Para assegurar que as melhores soluções de cada geração não são destruídas pelo

processo de reprodução foi implementado um mecanismo de elitismo, através do qual é

possível a selecção automática dos melhores cromossomas da população actual a

respectiva introdução na população da próxima geração.

3 - 4 - 4 Reprodução

Os operadores de reprodução - cruzamento e mutação - ocorrem segundo as

probabili dades definidas na fase de parametrização.

Cruzamento

O operador de cruzamento incide sobre pares de cromossomas seleccionados da

população actual gerando novos cromossomas, possuidores de características genéticas

dos seus ascendentes.

Considerem-se os seguintes cromossomas e respectivos calendários de reunião

G1 G2 G3 G4 G5 G6 G7 G8 (...) G53 G54

Cromossoma 1 (ascendente) 6 3 4 1 2 1 9 8 (...) 19 13

Cromossoma 2 (ascendente) 3 1 9 4 7 13 6 5 (...) 17 10


1º

Tempo

1

T4+T6

5 9

T7

13

T54

17

Man

hã

2º

Tempo

2

T5

6

T1

10 14 18

1º

Tempo

3

T2

7 11 15 19

T53

Tar

de

4º

Tempo

4

T3

8

T8

12 16 20


1º

Tempo

1

T2

5

T8

9

T3

13

T6

17

T53 Man

h

ã

2º

Tempo

2 6

T7

10

T54

14 18

1º

Tempo

3

T1

7

T5

11 15 19

Tar

de

4º

Tempo

4

T4

8

12 16 20

Reuniões do cromossoma ascendente 1

Reuniões do cromossoma ascendente 2

Figura 12 - Cruzamento (cromossomas ascendentes)


28

Aplicando um operador de cruzamento aos cromossomas ascendentes, por exemplo, o

operador de cruzamento num ponto de corte situado no quarto locus, obtêm-se os

seguintes descendentes.

G1 G2 G3 G4 G5 G6 G7 G8 (...) G53 G54

Cromossoma 1 (descendente) 6 3 4 1 7 13 6 5 (...) 17 10

Cromossoma 2 (descendente) 3 1 9 4 2 1 9 8 (...) 19 13


1º

Tempo

1

T4

5

T8

9 13

T6

17

T53

Man

hã

2º

Tempo

2 6

T1+T7

10

T54

14 18

1º

Tempo

3

T2

7

T5

11 15 19

Tar

de

4º

Tempo

4

T3

8 12 16 20


1º

Tempo

1

T2+T6

5 9

T3+T7

13

T54

17

Man

h

ã 2º

Tempo

2

T5

6 10 14 18

1º

Tempo

3

T1

7 11 15 19

T53 Tar

de

4º

Tempo

4

T4

8

T8

12 16 20

Reuniões do cromossoma descendente 1

Reuniões do cromossoma descendente 2

Figura 13 - Cruzamento (cromossomas descendentes)

Mutação

O operador de mutação opera ao nível dos genes, efectuando a troca dos valores de

determinados locus do cromossoma por outros valores - alelos.

Observando a figura 14 é possível verificar a acção do operador de mutação nos terceiro

e sétimo locus do cromossoma.


29

G1 G2 G3 G4 G5 G6 G7 G8 (...) G53 G54

Cromossoma 1 (antes da mutação) 6 3 4 1 7 13 6 5 (...) 17 10

Cromossoma 1 (após a mutação) 6 3 19 1 7 13 12 5 (...) 17 10


1º

Tempo

1

T4

5

T8

9 13

T6

17

T53

Man

hã

2º

Tempo

2 6

T1+T7

10

T54

14 18

1º

Tempo

3

T2

7

T5

11 15 19

Tar

de

4º

Tempo

4

T3

8 12 16 20


1º

Tempo

1

T4

5

T8

9 13

T6

17

T53 Man

h

ã

2º

Tempo

2 6

T1

10

T54

14 18

1º

Tempo

3

T2

7

T5

11 15 19

T3 Tar

de

4º

Tempo

4 8

12

T7

16 20

Reuniões do cromossoma 1antes da mutação

Reuniões do cromossoma 1 após a mutação

Figura 14 - mutação

3 - 4 - 5 Finalização

A finalização do algoritmo verifica-se quando ocorre uma das seguintes condições:

1. O algoritmo gera uma solução em que as restrições R1, R2, R3 e R4 não sofrem

qualquer infracção, o que significa que foi encontrada a solução óptima do

problema;

2. Foi atingido o número máximo de gerações definido como limite de execução do

algoritmo. Neste caso é terminada a execução do algoritmo adoptando-se a solução

encontrada até ao momento que mais se adapte à resolução do problema.

3 - 5 Resultados

O tema que motivou o presente trabalho foi a elaboração de um modelo matemático que

recorrendo aos algoritmos genéticos efectuasse o escalonamento automático de reuniões


30

escolares. Paralelamente ao estudo teórico foi também desenvolvida uma aplicação

prática com o objectivo de simular e testar o modelo elaborado.

Seguidamente são apresentados os valores obtidos pela aplicação através de ciclos de

cinco simulações com várias combinações de parâmetros. As colunas valor 1, valor 2,

valor 3, valor 4 e valor 5 correspondem aos valores das simulações; a coluna valor

médio representa a média aritmética dos cinco valores obtidos para cada combinação de

parâmetros

Os resultados foram obtidos com populações formadas por vinte indivíduos e um limite

de execução do algoritmo de cinquenta gerações.

Selecção Reprodução Resultados

Simulação Operador Eliti smo

Operador

Cruzamento

Probabili dade

Cruzamento

Probabili dade

Mutação

Valor

1

Valor

2

Valor

3

Valor

4

Valor

5

Valor

Médio

1 Proporcional Sim 1 Ponto 90% 1% 14318 15517 10718 7018 16809 12876

2 Proporcional Sim 2 Pontos 90% 1% 15808 14414 15923 15518 15508 15434

3 Proporcional Sim Uniforme 90% 1% 8923 16418 11719 16323 12713 13219

4 Proporcional Não 1 Ponto 90% 1% 26818 30518 18822 24913 26423 25499

5 Proporcional Não 2 Pontos 90% 1% 29703 32608 29922 25223 24226 28336

6 Proporcional Não Uniforme 90% 1% 28423 19613 31118 17013 27823 24798

7 Linear Sim 1 Ponto 90% 1% 9818 5612 6513 8813 10218 8195

8 L inear Sim 2 Pontos 90% 1% 8614 6813 4113 8523 7603 7133

9 L inear Sim Uniforme 90% 1% 10708 4508 6312 8713 5718 7192

10 Linear Não 1 Ponto 90% 1% 8612 7512 6518 9512 10709 8573

11 Linear Não 2 Pontos 90% 1% 6318 11513 4914 6813 11523 8216

12 Linear Não Uniforme 90% 1% 8408 8613 4718 11512 4013 7453







19 Linear Sim 1 Ponto 90% 5% 8718 9918 8818 11113 12812 10276

20 Linear Sim 2 Pontos 90% 5% 10213 11509 8913 11913 6813 9872

21 Linear Sim Uniforme 90% 5% 4613 8518 9323 10513 10023 8598

22 Linear Não 1 Ponto 90% 5% 12428 11818 11314 15013 15218 13158




31







31 L inear Sim 1 Ponto 95% 1% 5513 7619 5618 9114 3613 6295


33 L inear Sim Uniforme 95% 1% 6613 4218 7923 4413 4723 5578

34 Linear Não 1 Ponto 95% 1% 5813 4618 10812 7621 8423 7457









43 L inear Sim 1 Ponto 95% 5% 4718 7618 7718 8518 7418 7198


45 Linear Sim Uniforme 95% 5% 9018 4118 12713 8716 12813 9476

46 Linear Não 1 Ponto 95% 5% 14021 11713 16008 12013 11809 13113



Tabela 7 - Resultados obtidos ao fim de 50 gerações com populações de 20 cromossomas

A tabela 7 ilustra os valores resultantes de todas as combinações quanto ao tipo de

operador de selecção (proporcional ou linear), elitismo (activo ou inactivo), operador de

cruzamento (um ponto, dois pontos ou uniforme), probabili dade de cruzamento (90% ou

95%) e probabili dade de mutação (1% ou 5%).

Observando os valores da tabela anterior, conclui-se que os cinco melhores resultados

médios foram obtidos com os parâmetros das simulações 8, 9, 31, 33 e 43.

Com o objectivo de explorar mais pormenorizadamente os parâmetros que

demonstraram melhores resultados aumentou-se o número de cromossomas para cem e

o número de gerações para duzentos e cinquenta, atingindo-se os seguintes valores:


32

Selecção Reprodução

Simulação Operador Eliti smo

Operador

Cruzamento

Probabili dade

Cruzamento

Probabili dade

Mutação

Resultado Final

8 Linear Sim 2 Pontos 90% 1% 102

9 Linear Sim Uniforme 90% 1% 99

31 L inear Sim 1 Ponto 95% 1% 95

33 Linear Sim Uniforme 95% 1% 108

43 Linear Sim 1 Ponto 95% 5% 112

Tabela 8 - Resultados obtidos ao fim de 250 gerações com populações de 100 cromossomas

Da análise da tabela 8 conclui-se que os parâmetros que melhor se ajustam ao modelo

proposto para a resolução do problema do escalonamento automático de reuniões são os

da simulação 31: selecção com normalização linear, elitismo, cruzamento num ponto,

probabili dade de cruzamento de 95% e probabili dade de mutação de 1%. Através destes

parâmetros foi possível atingir, ao fim de seiscentas e quatro gerações de uma

população formada por quinhentos cromossomas, uma solução com penalização total de

89 valores, referente às seguintes infracções.

Restrição Nº. Infracções Penalização definida Penalização Total

R1 0 1000 0

R2 0 100 0

R3 3 10 30

R4 59 1 59

Tabela 9 - Penalizações da melhor solução atingida

3 - 6 Visualização de resultados

Os resultados obtidos podem ser visualizados sob dois pontos de vista: um relacionado

com a evolução das populações ao longo do processamento do algoritmo genético e

outro relacionado com as soluções propriamente ditas.


33

3 - 6 - 1 Evolução das populações

A evolução dos algoritmos genéticos é caracterizada por uma forte convergência ao

longo das gerações.

Analisando o gráfico da figura 15, representativo das melhores penalizações - curva

inferior - e das penalizações médias das populações - curva superior - verifica-se que os

valores inicialmente elevados de penalização das populações decrescem ao longo das

gerações, justificados pela teoria da selecção natural, segundo a qual os indivíduos mais

adaptados sobrevivem em detrimento dos menos adaptados. Ao fim de algumas

gerações, dado que todos os indivíduos da população se tornam semelhantes o processo

de convergência estabili za, ficando a convergência do algoritmo genético dependente da

introdução de novos valores no património genético, por exemplo, através do operador

de mutação.

Figura 15 - gráfico representativo da evolução das populações ao longo das gerações

3 - 6 - 2 - Soluções

As soluções geradas ao longo do processamento do algoritmo genético podem ser

graficamente visualizadas em função das datas de ocorrência das reuniões e em função

dos professores.


34

A visualização de soluções em função das datas de ocorrência permite ter uma noção

das turmas e dos professores envolvidos em cada sessão.

Figura 16 - visualização de soluções em função da data

A visualização de soluções em função dos professores permite tomar conhecimento das

sessões para as quais os professores estão convocados.

Figura 17 - visualização de soluções em função do professor

Através de qualquer um dos modos de visualização é possível avaliar o valor da

penalização média da população e do melhor cromossoma. Relativamente ao melhor


35

cromossoma de cada população, é ainda possível verificar quais as restrições infringidas

e as respectivas penalizações.

Conclusão

36

4 - Conclusão

O tema que motivou o presente trabalho foi o estudo dos algoritmos genéticos e a

aplicação das suas potencialidades a um caso real concreto que, devido à sua

complexidade, todos os anos consome centenas de horas às administrações escolares em

todo o país - a calendarização de reuniões intercalares.

O estudo começou pela análise dos principais processos responsáveis pelo

funcionamento interno dos algoritmos genéticos: a inicialização; a avaliação; a selecção;

a reprodução e a finalização, tendo sido visto que:

• O processo de inicialização consiste na geração da população inicial do algoritmo;

• O processo de avaliação é responsável pela aferição dos níveis de adaptação dos

indivíduos à resolução do problema, segundo critérios específicos do problema,

geralmente expressos em termos de restrições;

• O processo de selecção escolhe para reprodução os cromossomas melhor

classificados na fase de avaliação;

• O processo de reprodução consiste no cruzamento e mutação dos cromossomas

selecionados, dando origem a novos descendentes, conceptualmente mais adaptados,

que formam a próxima população;

• O processo de finalização determina o término do processamento do algoritmo

genético podendo verificar-se devido a dois factores: foi encontrada uma solução

que satisfaz integralmente as restrições impostas pelo problema; foi atingido o limite

máximo imposto à execução do algoritmo.

Após o estudo relativo aos mecanismos que suportam os algoritmos genéticos, foi

apresentado um modelo proposto para o escalonamento automático de reuniões

escolares e os respectivos resultados.

A qualidade das soluções atingidas pelos algoritmos genéticos, como foi demonstrado,

depende largamente dos parâmetros utili zados, facto que motivou a realização de várias

simulações experimentais de modo a obter um conjunto de parâmetros adequado ao

problema.

Conclusão

37

Ao fim de várias tentativas foi conseguido um conjunto de parâmetros que teoricamente

se adequa à calendarização de reuniões e, através dele, foi atingida uma solução de

qualidade elevada segundo a qual as principais restrições do problema são

completamente satisfeitas e as restantes, embora parcialmente insatisfeitas, não se

revelam comprometedoras.

Como conclusão, de acordo com os resultados obtidos, pensa-se ser viável a aplicação

de algoritmos genéticos a problemas de escalonamento, não só de reuniões escolares,

como também de exames escolares, horários escolares e, eventualmente, problemas

industriais como por exemplo escalonamento de ordens de fabrico e afectação de

recursos.

Bibliografia

38

Bibliografia

Davis, 91 Davis, L.: Handbook of Genetic Algorithms.

Van Nostrand Reinhold, New York, (1991).

Goldberg, 89 Goldberg, D.: Genetic Algorithms in Search, Optimization and Machine Learning.

Addison-Wesley, New York, (1989)

Holland, 75 Holland, J.: Adaptation in Natural and Artificial Systems.

The University of Michigan Press, (1975)

Mahfoud, 95 Mahfoud, S.: Niching Methods for Genetic Algorithms. PhD Thesis.

University of Illi nois at Urbana-Champaign, (1995)

Mitchell , 96 Mitchell , M.: An Introduction to Genetic Algorithms.

Massachusetts Institute of Technology, (1996)

Queirós, 95 Queirós, F.: Construção automática de Horários de Aulas.

Universidade Portucalense, (1995)

Syswerda, 89 Syswerda, G.: Uniform Crossover in Genetic Algorithms.

Proceedings of the Third International Conference on Genetic Algorithms.

San Mateo, Cali fornia, Morgan Kaufmann Publishers, (1989)

Foram ainda consultadas, entre outras, as seguintes páginas da internet:

http://gal4.ge.uiuc.edu/

http://cs.felk.cvut.cz/~xobitko/ga/

Fundamentos teóricos e matemáticos

39

Anexo 1 - Fund amentos teóricos e matemáticos

Os algoritmos genéticos não constituem um instrumento cientifico, mas sim uma teoria

científica, cuja complexidade e universo de aplicação não estão ainda determinados.

A importância dos resultados obtidos indiciam a elevação dos algoritmos genéticos a

campo disciplinar autónomo, contudo, a distância que separa os fundamentos teóricos e

a componente prática - traduzida por uma constante adaptação de novas concepções da

genética à reconstrução dos algoritmos genéticos - sugere um movimento com duas

frentes, uma externa, delimitando um quadro epistémico em discussão com a biologia

evolutiva, outra interna, estabelecendo linhas de tensão entre os fundamentos teóricos e

as aplicações práticas.

Samir W. Mahfoud escreveu24 "In the literature, GAs are currently undergoing a

process of testing and redesign, mostly through ad hoc experimentation. 'New and

improved' GAs are unveiled seemingly every day, with the driving motivation often

being novelty; in many cases, previously introduced GAs are simpler, and have

identical or better performance. At the opposite extreme is research into precise

mathematical modelli ng of GAs. Inevitably, exact models of GAs are more complex and

analytically unwieldy than the GAs themselves. Precise mathematical modelli ng has not

yet resulted in improved designs for GAs.

The middle ground between the two extremes of approaches - ad hoc experimentation

and precise mathematical modelli ng - has, with a few notable exceptions, remained

vacant."

A teoria dos esquemas, proposta por John Holland25 e posteriormente revista por David

E. Goldberg26, fundamenta e serve de suporte teórico aos algoritmos genéticos.

24 [Mahfoud, 95]. 25 [Holland, 75]. 26 [Goldberg, 89].


40

Teoria dos esquemas

Apesar dos algoritmos genéticos serem reconhecidamente acessíveis a nível de

descrição e programação existem muitas questões em aberto relativas ao seu modo de

funcionamento e ao tipo de problemas a que melhor se adaptam.

A teoria formulada por John Holland em 1975 relativamente ao modo de funcionamento

dos algoritmos genéticos assumia que, de modo geral, os algoritmos genéticos

funcionavam através da pesquisa e recombinação de blocos construtores -

subsequências formadas por elementos com elevado nível de adaptação.

A noção de esquema27 foi introduzida no sentido de formalizar a noção informal de

bloco construtor. Assumindo, sem perda de generalidade, cromossomas representados

por elementos contidos no alfabeto binário - zeros e uns -, um esquema é uma sequência

de valores representada por um conjunto de zeros, uns e asteriscos, sendo o asterisco um

metasímbolo que pode assumir o valor zero ou um.

O esquema da figura 18, constituído pela sequência 1 0 1 * 0 * 0 1 representa quatro

cromossomas distintos:

1 0 1 * 0 * 0 1

1 0 1 0 0 0 0 1

1 0 1 0 0 1 0 1

1 0 1 1 0 0 0 1

1 0 1 1 0 1 0 1

Figura 18 - Cromossomas representados pelo esquema 1 0 1 * 0 * 0 1

Analogamente ao número de cromossomas que um esquema pode representar, interessa

calcular o número de esquemas distintos que podem ser representados por um

determinado cromossoma. Assumindo que os cromossomas são compostos por oito

genes - à semelhança dos cromossomas da figura 18 -, cada cromossoma c pode

representar um conjunto de duzentos e cinquenta e seis28 esquemas.

27 "Schema" ou "Schemata" 28 Dado que o alfabeto é binário - H = { 0, 1} - e os cromossomas são formados por oito genes - l = 8 -,

cada cromossoma pode representar 28 esquemas.


41

Os algoritmos genéticos processam explicitamente n cromossomas de comprimento l e

implicitamente um número de esquemas compreendido entre 2l e n × 2l - o facto de não

serem implicitamente processados exactamente n × 2l cromossomas, deve-se à

existência de esquemas comuns a vários cromossomas.

O seguinte problema de optimização, cujo objectivo é maximizar a função f(x) = x2 para

valores de x compreendidos entre zero e quinze, permite analisar os mecanismos que

servem de orientação aos algoritmos genéticos na pesquisa das soluções.

A tabela 10 indica os parâmetros utili zados.

Modelo de representação: Codificação binária

Inicialização:

(população inicial gerada aleatoriamente)

c1 1 1 1 0

c2 1 1 0 0

c3 0 0 1 1

Avaliação: f(c) = c2

Selecção: Selecção directamente proporcional

Reprodução: Cruzamento num ponto e mutação

Tabela 10 - Parâmetros utili zados na maximização da função f(x) = x2

O cálculo do nível de adaptação dos cromossomas c1, c2 e c3 através da função de

avaliação revela os valores29 196, 144 e 3 obtendo-se, portanto, probabili dades de

selecção30 na ordem dos 57.1%, 42.0% e 0.9%, respectivamente.

Neste caso, o algoritmo genético processa explicitamente três cromossomas e

implicitamente trinta e oito esquemas - valor compreendido entre 24 e 3 × 24 -, dos quais

um é representado pelos três cromossomas, oito são representados por conjuntos de dois

cromossomas e vinte e sete são representado por um único cromossoma.

A tabela 11 e a figura 19 ilustram a representação e a intersecção dos esquemas

relativos aos três cromossomas.

29 Os valores apresentados foram calculados com base no fenótipo dos cromossomas - valores 1110, 1100

e 0011 convertidos do sistema de representação binário para o sistema de representação decimal. 30 Utili zando o método de selecção "Roulette Wheel Parent Selection".


42

Esquema Cromossoma

1 1 1 0

Cromossoma

1 1 0 0

Cromossoma

0 0 1 1 1 * * * * * * * * * * * * 2 * * * 0 * * * 0 3 * * 1 * * * 1 * 4 * * 1 0 5 * 1 * * * 1 * * 6 * 1 * 0 * 1 * 0 7 * 1 1 * 8 * 1 1 0 9 1 * * * 1 * * * 10 1 * * 0 1 * * 0 11 1 * 1 * 12 1 * 1 0 13 1 1 * * 1 1 * * 14 1 1 * 0 1 1 * 0 15 1 1 1 * 16 1 1 1 0 17 * * 0 * 18 * * 0 0 19 * 1 0 * 20 * 1 0 0 21 1 * 0 * 22 1 * 0 0 23 1 1 0 * 24 1 1 0 0 25 * * * 1 26 * * 1 1 27 * 0 * * 28 * 0 * 1 29 * 0 1 * 30 * 0 1 1 31 0 * * * 32 0 * * 1 33 0 * 1 * 34 0 * 1 1 35 0 0 * * 36 0 0 * 1 37 0 0 1 * 38 0 0 1 1

Tabela 11 - Representação dos esquemas relativos aos cromossomas 1 1 1 0, 1 1 0 0 e 0 0 1 1


43

Cromossoma 1 1 0 0

Cromossoma 1 1 1 0 17 18

4 7 8 2 5 6 19 20

11 12 15 9 10 13 21 22

16 14 23 24

1

3

25 26 27 28

29 30 31 32 33

34 35 36 37 38

Cromossoma 0 0 1 1

Figura 19 - Intersecção dos esquemas relativos aos cromossomas 1 1 1 0, 1 1 0 0 e 0 0 1 1

Efeito da selecção nos esquemas

Quais serão as expectativas de um determinado esquema estar representado na próxima

geração? Serão as alterações provocadas pelos operadores genéticos aleatórias, ou

obedecem a alguma lei?

David E. Goldberg, com o objectivo de esclarecer o efeito da selecção nos esquemas,

definiu o seguinte plano: cálculo do valor de adaptação dos esquemas através da média

aritmética da adaptação dos cromossomas que os representam; cálculo do valor de

adaptação média da população através da média aritmética da adaptação dos seus

indivíduos; cálculo do número de vezes que o esquema é esperado na próxima geração;

confronto, para cada esquema, do seu valor de adaptação com a adaptação média da

população, o número de vezes que o esquema está representado na geração actual e

número de vezes que se espera que venha a ser representado na próxima geração.

A tabela 12 esboça os resultados obtidos relativamente ao problema de maximização da

função f(x) = x2. O valor da adaptação média da população é 114.


44

Esquema Adaptação Representações actuais Representações esperadas

1 114 3 3 2 170 2 2.98 3 100 2 1.75 4 196 1 1.72 5 170 2 2.98 6 170 2 2.98 7 196 1 1.72 8 196 1 1.72 9 170 2 2.98 10 170 2 2.98 11 196 1 1.72 12 196 1 1.72 13 170 2 2.98 14 170 2 2.98 15 196 1 1.72 16 196 1 1.72 17 144 1 1.26 18 144 1 1.26 19 144 1 1.26 20 144 1 1.26 21 144 1 1.26 22 144 1 1.26 23 144 1 1.26 24 144 1 1.26 25 144 1 0.03 26 144 1 0.03 27 144 1 0.03 28 3 1 0.03 29 3 1 0.03 30 3 1 0.03 31 3 1 0.03 32 3 1 0.03 33 3 1 0.03 34 3 1 0.03 35 3 1 0.03 36 3 1 0.03 37 3 1 0.03 38 3 1 0.03

Tabela 12 - Efeito da selecção nos esquemas


45

Os valores da tabela 12 sugerem que a relação entre a adaptação dos esquemas e a

adaptação m da população determina o número de exemplares de cada esquema

esperado na próxima geração.

Foi formalmente demonstrado por David E. Goldberg, que a quantidade de exemplares

processados de um determinado esquema aumenta, ou diminui, relativamente à geração

anterior, em função da fórmula

f

HftHmtHm

)(),()1,( ×=+

em que m(H,t+1) e m(H,t) representam, respectivamente, o número de esquemas H

representados na geração t+1 e na geração t, f(H) representa a adaptação do esquema H,

e f representa a adaptação média da população.

Efeito do cruzamento nos esquemas

Os esquemas possuem duas propriedades que permitem diferenciá-los: a ordem do

esquema e o comprimento definidor do esquema.

A ordem do esquema - representada por o(H) - corresponde ao número de símbolos "0"

e "1" contidos no esquema, o comprimento definidor - representado por δ(H) -

corresponde à distância entre os símbolos "0" e "1" que ocupam as posições mais

próximas das extremidades do esquema31. Relativamente ao esquema número vinte e

um da tabela 11, por exemplo, os valores da ordem e do comprimento definidor são,

respectivamente, O(1 * 0 *) = 2 e δ(1 * 0 *) = 3 -1 = 2.

A fórmula anterior não considera a possibili dade de destruição dos esquemas por acção

do operador de cruzamento. Retomando os cromossomas da tabela 11, constituídos

pelas sequências 1 1 1 0 e 0 0 1 1, suponha-se que são seleccionados para cruzamento -

cruzamento num ponto - e que o ponto de corte, aleatoriamente escolhido, é o ponto um.

Os cromossomas resultantes, constituídos pelas sequências 1 0 1 1 e 0 1 1 0, permitem

observar a permanência do esquema quatro - * * 1 0 - na nova geração e a destruição e

31 O comprimento definidor de um esquema constituído por um único símbolo é zero. [Goldberg, 89].


46

consequente exclusão do esquema dez - 1 * * 0, apesar da melhor adaptação do

esquema dez relativamente ao esquema quatro.

O factor responsável pela destruição do esquema dez é o seu elevado comprimento

definidor. Atendendo ao comprimento definidor do esquema dez, cujo valor é três,

verifica-se que apenas uma recombinação extremamente favorável permitiria a sua não

destruição, ao contrário do esquema quatro, que devido ao seu reduzido comprimento

definidor - um - apenas poderá ser destruído, eventualmente, por um corte na posição

três.

A probabili dade Psc de um esquema H constituído por l elementos sobreviver a um

cruzamento cuja probabili dade de ocorrência é Pc é obtida através da seguinte

desigualdade

1

)(1

−×−≥

l

HPP csc

δ

Efeito da mutação nos esquemas

A mutação encerra a análise dos efeitos dos operadores genéticos relativamente à

proliferação dos esquemas.

Considerando que o operador de mutação consiste na troca do valor de um gene de "0"

para "1" ou de "1" para "0" e que ocorre com probabili dade Pm, observa-se que um

esquema H é conservado se os símbolos "0" e "1" não forem alterados no cromossoma

que o representa.

A probabili dade Psm de um esquema H sobreviver ao operador de mutação é

representada pela seguinte fórmula32

)()1( HOmsm PP −=

32 A probabili dade de destruição de um esquema através do operador de mutação aumenta de acordo com

o valor da sua ordem O(H).


47

Atendendo ao facto de que o operador de mutação ocorre, tradicionalmente, segundo

probabili dades reduzidas33, a fórmula anterior pode ser representada do seguinte modo

msm PHOP ×−= )(1

Teorema fundamental dos algoritmos genéticos

Ao longo dos últimos parágrafos foram enunciados os efeitos dos operadores genéticos

relativamente ao número esperado de representações dos esquemas na geração seguinte,

constatando-se que a proliferação dos esquemas se verifica mediante a satisfação de três

condições fundamentais: a adaptação dos esquemas deve ser superior à adaptação média

da população; os esquemas devem possuir um comprimento definidor curto; a ordem

dos esquemas deve ser reduzida.

O teorema fundamental dos algoritmos genéticos, também conhecido por teorema dos

esquemas, permite quantificar e relacionar as três condições de proliferação dos

esquemas

×−

−×−××≥+ mc PHO

l

HP

f

HftHmtHm )(

1

)(1

)(),()1,(

δ

Considerando que a diferença entre a adaptação de um esquema H e a adaptação média

da população é constante ao longo das gerações, ou seja, f(H) - f = c, o teorema

anterior admite o seguinte corolário

( )

×−

−×−×+×≥+ mc

iPHO

l

HPctHmitHm )(

1

)(11),(),(

δ

33 O uso excessivo do operador de mutação é ineficaz, podendo, em casos extremos, degenerar os

algoritmos genéticos em métodos de pesquisa aleatória. Alguns autores ignoram o operador de mutação

afirmando, inclusive, que "a mutação é secundária na natureza e nos algoritmos genéticos".


48

Observando o corolário anterior conclui-se que, descontando os efeitos dos operadores

de cruzamento e mutação, o número esperado de representações dos esquemas segue

uma progressão geométrica de razão 1+c, ou seja, os esquemas com adaptação acima da

média crescem exponencialmente e os esquemas com adaptação abaixo da média

decrescem exponencialmente.

Os esquemas com adaptação acima da média, comprimento definidor curto e ordem

reduzida denominam-se esquemas úteis, ou blocos construtores34. Do ponto de vista

prático dos algoritmos genéticos o número de esquemas processados em cada geração

não é muito relevante. O que interessa determinar é o número de blocos construtores

processados.

Segundo John Holland, o número de esquemas úteis processados numa população

formada por n indivíduos é n3. A propriedade anterior - paralelismo implícito - levou à

formulação de uma conjectura crucial denominada hipótese dos blocos construtores:

"Os blocos construtores implicitamente processados por uma população de n

cromossomas combinam-se formando melhores cromossomas".

Linhas de tensão

Uma das principais diferenças entre o processo de evolução natural e o processo de

evolução simulado pelos algoritmos genéticos consiste na incapacidade, por parte dos

algoritmos genéticos, de manter uma população variada. Ao fim de algumas gerações os

indivíduos contidos numa população artificial praticamente não apresentam diferenças

entre si, dizendo-se, em linguagem formal, que a população convergiu.

O sentido de convergência está estritamente ligado ao sentido de perda de diversidade

da população. Uma população pode convergir sem perder diversidade - situação

verificada em problemas multimodais, em que o algoritmo converge para várias

soluções -, no entanto, o contrário não é válido, ou seja, uma população que perca

diversidade converge obrigatoriamente. A existência de diversidade numa população

revela-se de elevada importância.

Atendendo à necessidade de garantir um processo de convergência eficaz, David E.

Goldberg enumerou um conjunto de linhas fundamentais de tensão, segundo as quais os

algoritmos genéticos devem:

34 "Buiding blocks"


49

1. assegurar a existência de blocos construtores suficientes na população;

2. assegurar a sobrevivência dos blocos construtores;

3. assegurar recombinações favoráveis dos blocos construtores.

A figura 20 relaciona as linhas fundamentais de tensão com o modelo dos algoritmos

genéticos.

Figura 20 - L inhas fundamentais de tensão dos algor itmos genéticos

A dimensão do espaço de pesquisa de soluções regula o número mínimo de blocos

construtores necessários à convergência do algoritmo para a solução óptima.

A tensão da primeira linha é determinada pela complexidade do problema verificando-

se a dois níveis: ao nível da inicialização e ao nível da mutação. Ao nível da

inicialização deve-se assegurar que a população inicial é constituída por um número

suficiente de indivíduos; ao nível da mutação deve-se assegurar a introdução de novos

valores no património genético da população, proporcionando potenciais ganhos a nível

dos blocos construtores.

A segunda linha de tensão cujos principais intervenientes são os operadores de selecção

e reprodução deve assegurar a sobrevivência dos blocos construtores, facto de que

depende a convergência útil dos algoritmos genéticos.

Inicialização

Avaliação

Selecção

Cruzamento

Mutação

Linha

1

Linha

2

Linha

3 R

epro

duçã

o Finalização


50

Atendendo ao facto de que a sobrevivência dos blocos construtores não garante por si só

a convergência dos algoritmos genéticos para a solução óptima, a terceira linha de

tensão tem por objectivo assegurar um processo de recombinação correcto que permita

aos cromossomas descendentes representarem mais blocos construtores do que os seus

ascendentes.

Glossário de termos técnicos

51

Anexo 2 - Glossário de termos técnicos

Alelo Valor que um gene posicionado num determinado locus do

cromossoma pode assumir.

Bloco construtor Esquema de ordem reduzida, comprimento definidor curto e

adaptação acima da média.

Compr imento definidor Distância compreendida entre os símbolos que ocupam as

posições mais extremas de um esquema.

Cruzamento Processo segundo o qual é efectuada a troca de material

genético entre cromossomas.

Cruzamento em dois pontos Operador de cruzamento que utili za dois pontos de corte no

cromossoma.

Cruzamento num ponto Operador de cruzamento que utili za um ponto de corte no

cromossoma.

Cruzamento uniforme Operador de cruzamento que efectua troca de genes entre dois

cromossomas segundo uma probabili dade de ocorrência,

geralmente na ordem dos 50%.

Eli tismo Mecanismo que assegura a permanência das melhores soluções

das populações ao longo das gerações.

Esquema Sequência de valores normalmente representada por zeros, uns e

asteriscos em que os asteriscos podem assumir o valor zero ou

um.

Fenótipo Características exibidas por um cromossoma após a sua

descodificação.

Genótipo Conjunto de valores constituintes dos cromossomas.

Indivíduo Elemento da população. No contexto dos algoritmos genéticos

os indivíduos correspondem aos cromossomas.

Locus Posição particular de um cromossoma.

Mutação Processo de substituição do valor de um determinado gene por

um valor alternativo existente no património genético.

Ordem Número de símbolos definidos num esquema.

Paraleli smo implícito Propriedade dos algoritmos genéticos segundo a qual o número

de esquemas úteis processados numa população composta por n

indivíduos é n3.

População Conjunto de indivíduos. No contexto dos algoritmos genéticos

representa o conjunto dos cromossomas.

Probabili dade de cruzamento Probabili dade segundo a qual ocorre o operador de cruzamento.

Probabili dade de mutação Probabili dade segundo a qual ocorre o operador de mutação.

Recombinação (ver cruzamento).

Glossário de termos técnicos

52

Selecção Processo modelado segundo a teoria da selecção natural

utili zado para direccionar os algoritmos genéticos para melhores

zonas do espaço de pesquisa de soluções. Aos indivíduos mais

adaptados de cada população é atribuída maior probabili dade de

reprodução e sobrevivência.

Selecção por ordem de classificação Mecanismo de selecção utili zado nos algoritmos genéticos,

segundo o qual as probabili dades de selecção são atribuídas em

função das posições ocupadas pelos cromossomas numa tabela

classificativa.

Selecção proporcional Mecanismo básico de selecção utili zado nos algoritmos

genéticos, segundo o qual as probabili dades de selecção são

atribuídas proporcionalmente às adaptações dos indivíduos.

Listagem do algoritmo genético

53

Anexo 3 - Listagem do algoritmo genético

A listagem que se segue corresponde a uma classe implementada em Visual Basic 6.0,

utili zada na aplicação para suporte dos algoritmos genéticos.

Option Explicit

Option Base 1 Public Enum OperadorRecombinacao gaCrossoverUmPonto = 1 gaCrossoverDoisPontos = 2 gaCrossoverUniforme = 3 End Enum Public Enum ModoSeleccao

gaSelec caoProporcional = 1 gaSeleccaoLinear = 2 End Enum 'Probabilidade de Recombinação Private mProbabilidadeRecombinacao As Byte 'Probabilidade de Mutação Private mProbabilidadeMutacao As Byte 'Probabilidade de Inversão Private mProbabilidadeInversao As Byte 'Elismo ? (True/False) Private mElitismo As Boolean 'Nº de Cromossomas Private mNumeroCromossomas As Long 'Nº de Genes Private mNumeroGenes As Long 'Número Total de Gerações Private mNumeroGeracoes As Long 'Número da Geração Actual Private mGeracao As Long 'Indice da Melhor Geração Private mIndiceMelhorG eracao As Long 'Vector com os Valores do Alfabeto Private mAlfabeto() As Long 'Nº de Elementos que contidos no Alfabeto Private mNumeroElementosAlfabeto As Long 'Matriz com a População Actual Private mPopulacao() As Long 'Matriz com a População Temporaria da Próxima Geração Private mPopulacaoTemporariaProximaGeracao() As Long 'Matriz com a População da Próxima Geração Private mPopulacaoProximaGeracao() As Long 'Vector com as Penalizações dos Cromossomas da População Actual Private mPenalizacaoCromossoma() As Long 'Indice do Melhor Cromossoma da População Actual Private mIndiceMelhorCromossoma As Long 'Matriz com os Melhores Cromossomas das Gerações Anteriores Private mMelhorCromossomaGeracao() As Long 'Vector com as Penalizações dos Melhores Cromossomas das Gerações Anteriores Private mPenalizacaoMelhorCromossomaGeracao() As Long ' Vector com as Penalizações Médias das Gerações Anteriores Private mPenalizacaoMediaGeracao() As Long 'Operador de Recombinação Private mOperadorRecombinacao As OperadorRecombinacao 'Modo de Selecção Private mModoSelecca o As ModoSeleccao 'Indica paragem no Processamento Private mParar As Boolean Public Event AvaliarCromossoma(NumeroCromossoma As Long, Cromossoma As Variant, PenalizacaoCromossoma

As Long) Public Event ProcessarGeracao(Geracao As Long) Public Event AposProcessarGeracao() Public Event FimProcessamento(Penalizacao As Long) Public Property Let ProbabilidadeRecombinacao(Valor As Byte) mProbabilidadeRecombinacao = Valor End Property Public Pro perty Get ProbabilidadeRecombinacao() As Byte ProbabilidadeRecombinacao = mProbabilidadeRecombinacao End Property


54

Public Property Let ProbabilidadeMutacao(Valor As Byte) mProbabilidadeMutacao = Valor End Property Public Property Get Probabilidad eMutacao() As Byte ProbabilidadeMutacao = mProbabilidadeMutacao End Property Public Property Let ProbabilidadeInversao(Valor As Byte) mProbabilidadeInversao = Valor End Property Public Property Get ProbabilidadeInversao() As Byte Probabilidade Inversao = mProbabilidadeInversao End Property Public Property Let Elitismo(Valor As Boolean) mElitismo = Valor End Property Public Property Get Elitismo() As Boolean Elitismo = mElitismo End Property Public Property Get NumeroCromossomas() As Long NumeroCromossomas = mNumeroCromossomas End Property Public Property Get NumeroGenes() As Long NumeroGenes = mNumeroGenes End Property Public Property Get NumeroGeracoes() As Long NumeroGeracoes = mNumeroGeracoes End Property Public Proper ty Get Geracao() As Long Geracao = mGeracao End Property Public Property Get IndiceMelhorGeracao() As Long IndiceMelhorGeracao = mIndiceMelhorGeracao End Property Public Property Get Alfabeto() As Variant Dim A() As Long Dim E As Lo ng ReDim A(1 To mNumeroElementosAlfabeto) For E = 1 To mNumeroElementosAlfabeto A(E) = mAlfabeto(E) Next Alfabeto = A End Property Public Property Get NumeroElementosAlfabeto() As Long NumeroElementosAlfabeto = mNumeroElementosAl fabeto End Property Public Property Get Populacao() As Variant Populacao = mPopulacao End Property Public Property Get ElementoPopulacao(IndiceCromossoma As Long, IndiceGene As Long) As Long ElementoPopulacao = mPopulacao(IndiceCromossoma, IndiceGe ne) End Property Public Property Get Cromossoma(IndiceCromossoma As Long) As Variant Dim C() As Long Dim G As Long ReDim C(1 To mNumeroGenes) For G = 1 To mNumeroGenes C(G) = mPopulacao(IndiceCro mossoma, G) Next Cromossoma = C End Property Public Property Get PenalizacaoCromossoma(IndiceCromossoma As Long) As Long PenalizacaoCromossoma = mPenalizacaoCromossoma(IndiceCromossoma) End Property Public Property Get IndiceMelhorCromossoma() A s Long IndiceMelhorCromossoma = mIndiceMelhorCromossoma End Property


55

Public Property Get MelhorCromossomaGeracao(IndiceGeracao As Long) As Variant Dim C() As Long Dim G As Long ReDim C(1 To mNumeroGe nes) For G = 1 To mNumeroGenes C(G) = mMelhorCromossomaGeracao(IndiceGeracao, G) Next MelhorCromossomaGeracao = C End Property Public Property Get PenalizacaoMelhorCromossomaGeracao(IndiceGeracao As Long) As Long PenalizacaoMelhorCromos somaGeracao = mPenalizacaoMelhorCromossomaGeracao(IndiceGeracao) End Property Public Property Get PenalizacaoMediaGeracao(IndiceGeracao As Long) As Long PenalizacaoMediaGeracao = mPenalizacaoMediaGeracao(IndiceGeracao) End Property Public Property Let OperadorRecombinacao(Valor As OperadorRecombinacao) mOperadorRecombinacao = Valor End Property Public Property Get OperadorRecombinacao() As OperadorRecombinacao OperadorRecombinacao = mOperadorRecombinacao End Property Public Property Let M odoSeleccao(Valor As ModoSeleccao) mModoSeleccao = Valor End Property Public Property Get ModoSeleccao() As ModoSeleccao ModoSeleccao = mModoSeleccao End Property Private Sub GerarPopulacaoInicial() Dim C As Long Dim G As Long Dim E As Long For C = 1 To mNumeroCromossomas + IIf(mElitismo = True, 1, 0) For G = 1 To mNumeroGenes Randomize E = Int(mNumeroElementosAlfabeto * Rnd + 1) mPopulacao(C, G) = mAlfabeto(E) Next Next End Sub Private Sub AvaliarPopulacao() Dim C As Long Dim G As Long Dim Penalizacao As Long Dim PenalizacaoTotalGeracao As Long PenalizacaoTotalGeracao = 0 mIndiceMelhorC romossoma = 1 For C = 1 To mNumeroCromossomas + IIf(mElitismo = True, 1, 0) Penalizacao = 0 RaiseEvent AvaliarCromossoma(C, Cromossoma(C), Penalizacao) mPenalizacaoCromossoma(C) = Penalizacao If Penalizacao < mPenalizacaoCromosso ma(mIndiceMelhorCromossoma) Then mIndiceMelhorCromossoma = C End If PenalizacaoTotalGeracao = PenalizacaoTotalGeracao + Penalizacao Next mPenalizacaoMelhorCromossomaGeracao(mGeracao) = mPenalizacaoCromossoma(mIndiceMelhorCromosso ma) mPenalizacaoMediaGeracao(mGeracao) = PenalizacaoTotalGeracao / mNumeroCromossomas + IIf(mElitismo

= True, 1, 0) For G = 1 To mNumeroGenes mMelhorCromossomaGeracao(mGeracao, G) = mPopulacao(mIndiceMelhorCromossoma, G) Next If mPenaliza caoCromossoma(mIndiceMelhorCromossoma) <

mPenalizacaoMelhorCromossomaGeracao(mIndiceMelhorGeracao) Then mIndiceMelhorGeracao = mGeracao End If End Sub Private Sub OrdenarClassificacaoCromossoma(ClassificacaoCromossoma() As Long, Chave As Long) Dim C As Long Dim C1 As Long Dim C2 As Long Dim V As Long Dim Valor As Long For C1 = 1 To mNumeroCromossomas + IIf(mElitismo = True, 1, 0) - 1


56

C = C1 For C2 = C1 + 1 To mNumeroCromossoma s + IIf(mElitismo = True, 1, 0) If ClassificacaoCromossoma(C2, Chave) < ClassificacaoCromossoma(C, Chave) Then C = C2 End If Next If C <> C1 Then For V = 1 To 3 Valor = ClassificacaoCromossoma( C1, V) ClassificacaoCromossoma(C1, V) = ClassificacaoCromossoma(C, V) ClassificacaoCromossoma(C, V) = Valor Next End If Next End Sub Private Sub SeleccionarPopulacaoProximaGeracao() Const LIMITE_INFERIOR As Long = 1 Const LIMITE_SUPERIOR As Long = 2 Const INDICE As Long = 1 Const Penalizacao As Long = 2 Const CLASSIFICACAO As Long = 3 Dim C As Long Dim G As Long Dim SomatorioInversaPenalizacoes As Double Dim ClassificacaoC romossoma() As Long Dim ValorRoleta() As Double Dim ValorSeleccionado As Double Dim Ponteiro As Long SomatorioInversaPe nalizacoes = 0 ReDim ValorRoleta(1 To mNumeroCromossomas + IIf(mElitismo = True, 1, 0), 1 To 2) ValorRoleta(1, LIMITE_INFERIOR) = 0 ValorRoleta(mNumeroCromossomas + IIf(mElitismo = True, 1, 0), LIMITE_SUPERIOR) = 1 Select Case mModoSeleccao Case gaSeleccaoProporcional For C = 1 To mNumeroCromossomas + IIf(mElitismo = True, 1, 0) SomatorioInversaPenalizacoes = SomatorioInversaPenalizacoes + 1 / mPenalizacaoCromossoma(C) Next For C = 1 To mNumeroCromossomas + IIf(mEli tismo = True, 1, 0) - 1 ValorRoleta(C, LIMITE_SUPERIOR) = ValorRoleta(C, LIMITE_INFERIOR) + ((1 /

mPenalizacaoCromossoma(C)) / SomatorioInversaPenalizacoes) ValorRoleta(C + 1, LIMITE_INFERIOR) = ValorRoleta(C, LIMITE_SUPERIOR) Next Case gaSeleccaoLinear ReDim ClassificacaoCromossoma(1 To mNumeroCromossomas + IIf(mElitismo = True, 1, 0), 1 To 3) For C = 1 To mNumeroCromossomas + IIf(mElitismo = True, 1, 0) ClassificacaoCromossoma(C, INDICE) = C Classif icacaoCromossoma(C, Penalizacao) = mPenalizacaoCromossoma(C) Next Call OrdenarClassificacaoCromossoma(ClassificacaoCromossoma, Penalizacao) ClassificacaoCromossoma(1, CLASSIFICACAO) = 1 For C = 2 To mNumeroCromossomas + IIf(mElitism o = True, 1, 0) If ClassificacaoCromossoma(C, Penalizacao) = ClassificacaoCromossoma(C - 1, Penalizacao)

Then ClassificacaoCromossoma(C, CLASSIFICACAO) = ClassificacaoCromossoma(C - 1, CLASSIFICACAO) Else Classific acaoCromossoma(C, CLASSIFICACAO) = C End If Next Call OrdenarClassificacaoCromossoma(ClassificacaoCromossoma, INDICE) For C = 1 To mNumeroCromossomas + IIf(mElitismo = True, 1, 0) SomatorioInversaPenalizacoes = Somatorio InversaPenalizacoes + 1 / ClassificacaoCromossoma(C,

CLASSIFICACAO) Next For C = 1 To mNumeroCromossomas + IIf(mElitismo = True, 1, 0) - 1 ValorRoleta(C, LIMITE_SUPERIOR) = ValorRoleta(C, LIMITE_INFERIOR) + ((1 /

ClassificacaoCromossom a(C, CLASSIFICACAO)) / SomatorioInversaPenalizacoes) ValorRoleta(C + 1, LIMITE_INFERIOR) = ValorRoleta(C, LIMITE_SUPERIOR) Next End Select For C = 1 To mNumeroCromossomas Randomize ValorSeleccionado = Rnd Ponteiro = 1 While ValorSeleccionado >= ValorRoleta(Ponteiro, LIMITE_SUPERIOR) Ponteiro = Ponteiro + 1 Wend For G = 1 To mNumeroGenes mPopulacaoTemporariaProximaGeracao(C, G) = mPopulacao(Ponteiro, G) Next Next End Sub Pri vate Sub EmparelharPopulacaoProximaGeracao() Dim C As Long Dim G As Long


57

Dim D As Collection Dim I As Long Dim S As Long Set D = New Collection For C = 1 To mNumeroCromossomas D.Add C , "C" & C Next For C = 1 To mNumeroCromossomas Randomize I = Int(D.Count * Rnd + 1) S = D(I) For G = 1 To mNumeroGenes mPopulacaoProximaGeracao(C, G) = mPopulacaoTemporariaProximaGeracao(S, G) Next D.Remove (I) Next Set D = Nothing End Sub Private Sub RecombinarPopulacaoProximaGeracao() Dim C As Long Dim G As Long Dim P As Long Dim P1 As Long Dim P2 As Long Dim Gene As Long Select Case mOperadorRecombinacao Case gaCrossoverUmPonto For C = 1 To mNumeroCromossomas Step 2 Randomize If Rnd < mProbabilidadeRecombinacao / 100 Then Randomize P = Int((mNumeroGenes - 1) * Rnd + 1) For G = 1 To P Gene = mPopulacaoProximaGeracao(C, G) mPopulacaoProximaGeracao(C, G) = mPopulacaoProximaGeracao(C + 1, G) mPopulacaoProximaGeracao(C + 1, G) = Gene Next End If Next Case gaCrossoverDoisPontos For C = 1 To mNumeroCromossomas Step 2 Randomize If Rnd < mProbabilidadeRecombinacao / 100 Then Do Randomize P1 = Int((mNumeroGenes) * Rnd + 1) Randomize P2 = Int( (mNumeroGenes) * Rnd + 1) If P2 < P1 Then P = P1 P1 = P2 P2 = P End If Loop Until P1 <> P2 And P1 > 1 And P2 < mNumeroGenes For G = P1 To P2 Gene = mPopulacaoProximaGeracao(C, G) mPopulacaoProximaGeracao(C, G) = mPopulacaoProximaGeracao(C + 1, G) mPopulacaoProximaGeracao(C + 1, G) = Gene Next End If Next Case gaCrossoverUniform e For C = 1 To mNumeroCromossomas Step 2 Randomize If Rnd < mProbabilidadeRecombinacao / 100 Then Randomize For G = 1 To Int((mNumeroGenes) * Rnd + 1) Randomize P = Int((mNumeroGene s) * Rnd + 1) Gene = mPopulacaoProximaGeracao(C, P) mPopulacaoProximaGeracao(C, P) = mPopulacaoProximaGeracao(C + 1, P) mPopulacaoProximaGeracao(C + 1, P) = Gene Next End If Next End Select End Sub Private Sub MutarPopulacaoProximaGeracao() Dim C As Long Dim G As Long Dim E As Long For C = 1 To mNumeroCromossomas


58

For G = 1 To mNumeroGenes Randomize If Rnd < mProbabilidadeMutacao / 100 Then Randomize E = Int(mNumeroElementosAlfabeto * Rnd + 1) mPopulacaoProximaGeracao(C, G) = mAlfabeto(E) End If Next Next End Sub Private Sub InverterPopulacaoProximaGeracao() Dim C As Long Dim G As Long Dim Cromossoma() As Long ReDim Cromossoma(1 To mNumeroGenes) For C = 1 To mNumeroCromossomas Randomize If Rnd < mProbabilidadeInversao / 100 Then For G = 1 To mNumeroGenes Cromossoma(mNumeroGenes - G + 1) = mPopulacaoProximaGeracao(C, G) Next For G = 1 To mNumeroGenes mPopulacaoProximaGeracao(C, G) = Cromossoma(G) Next End If Next End Sub Private Sub ComutarPopulacao() Dim C As Long Dim G As Long If mElitismo = True Then If mIndiceMelhorCromossoma <> mNumeroCromossomas + 1 Then For G = 1 To mNumeroGenes mPopulacao(mNumeroCromossomas + 1, G) = mPopulacao(mIndiceMelhorCromossoma, G) Next End If End If For C = 1 To mNumeroCromossomas For G = 1 To mNumeroGenes mPopulacao(C, G) = mPopulacaoProximaGeracao(C, G) Next Next End Sub Public Sub Iniciar(Alfabeto As Variant, Cromossomas As Long, Gene s As Long, Geracoes As Long) mAlfabeto = Alfabeto mNumeroElementosAlfabeto = UBound(mAlfabeto) If mNumeroElementosAlfabeto = 0 Then MsgBox "Alfabeto Inválido.", vbInformation Exit Sub End If mNumeroCromossomas = Cromossoma s If mNumeroCromossomas < 2 Or mNumeroCromossomas Mod 2 <> 0 Then MsgBox "Número de Cromossomas Inválido.", vbInformation Exit Sub End If mNumeroGenes = Genes If mNumeroGenes = 0 Then MsgBox "Número de Genes Inválido.", vbInfo rmation Exit Sub End If mNumeroGeracoes = Geracoes If mNumeroGeracoes = 0 Then MsgBox "Número de Gerações Inválido.", vbInformation Exit Sub End If ReDim mPopulacao(1 To mNumeroCromossomas + IIf(mElitismo = True, 1, 0), 1 To mNumeroGenes) ReDim mPopulacaoTemporariaProximaGeracao(1 To mNumeroCromossomas, 1 To mNumeroGenes) ReDim mPopulacaoProximaGeracao(1 To mNumeroCromossomas, 1 To mNumeroGenes) ReDim mPenalizacaoCromossoma(1 To mNumeroCromossomas + IIf(mElitism o = True, 1, 0)) ReDim mMelhorCromossomaGeracao(1 To mNumeroGeracoes, 1 To mNumeroGenes) ReDim mPenalizacaoMelhorCromossomaGeracao(1 To mNumeroGeracoes) ReDim mPenalizacaoMediaGeracao(1 To mNumeroGeracoes) mGeracao = 1 mIndiceMelhorGeracao = 1 mParar = False Call GerarPopulacaoInicial Call Processar End Sub


59

Public Sub Parar() mParar = True End Sub Public Sub Continuar() mParar = False Call Processar End Sub Public Sub Processar() Do While mGeracao < mNumeroGeracoes RaiseEvent ProcessarGeracao(mGeracao) Call AvaliarPopulacao RaiseEvent AposProcessarGeracao DoEvents If mPenalizacaoMelhorCromossomaGeracao(mGeracao) > 0 And mParar = False Then mGeracao = mGeracao + 1 Call Sel eccionarPopulacaoProximaGeracao Call EmparelharPopulacaoProximaGeracao Call RecombinarPopulacaoProximaGeracao Call MutarPopulacaoProximaGeracao Call InverterPopulacaoProximaGeracao Call ComutarPopulacao El se Exit Do End If Loop If mParar = False Then If mGeracao = mNumeroGeracoes Then RaiseEvent ProcessarGeracao(mGeracao) Call AvaliarPopulacao RaiseEvent AposProcessarGeracao DoEvents End I f RaiseEvent FimProcessamento(mPenalizacaoMelhorCromossomaGeracao(mIndiceMelhorGeracao)) End If End Sub

Documents

ALGORITMOS GENÉTICOS - Departamento de Engenharia ...paf/proj/Set2000/AlgoritmosGeneticos.pdf · Introdução 2 Estrutura do relatório O presente relatório encontra-se dividido