FACULDADES INTEGRADAS DE ITARARÉ -FAFIT

FACULDADES INTEGRADAS DE ITARARE´ - FAFIT

VINICIUS M FERAZ

´ IA: ORGANIZANDO QUADROS DE HORARIOS ESCOLARES

˜ DE CURSO TRABALHO DE CONCLUSAO

ITARARE´ 2016

VINICIUS M FERAZ

´ IA: ORGANIZANDO QUADROS DE HORARIOS ESCOLARES

Trabalho de conclus˜ao de curso apresentado a Faculdades Integradas de Itarar´e - FAFIT para a obtenc¸a˜ o do t´ıtulo de Bacharelado em Sistemas de Informac¸a˜ o. Orientador:

´ ITARARE 2016

Prof. Me. Jos´e Ricardo Hoffmann

Dedico este trabalho a Deus pelo tempo, paciˆencia e dedicac¸a˜ o que me garantiu para conclus˜ao do mesmo.

AGRADECIMENTOS

Gostaria de agradecer primeiramente aos meus pais pelas condic¸o˜ es que me garantiram para a realizac¸a˜ o deste trabalho. Em segundo lugar meus mestres e professores que me permitiram adquirir o conhecimento necess´ario para elaborac¸a˜ o deste trabalho.

Tamb´em

gostaria de agradecer aos meus colegas por me suportarem e por me ajudarem ao longo destes 4 anos.

They shall not hurt nor destroy in all my holy mountain: for the earth shall be full of the knowledge of the LORD, as the waters cover the sea. Isaiah 11:9 – King James Bible

RESUMO

´ FERRAZ, Vinicius. IA: ORGANIZANDO QUADROS DE HORARIOS ESCOLARES. 49 f. Trabalho de conclus˜ao de curso – , Faculdades Integradas de Itarar´e - FAFIT. Itarar´e, 2016. O presente trabalho e´ estudo e implementac¸a˜ o de Inteligˆencia Artifical. Inicialmente ser˜ao apresentadas algumas definic¸o˜ es sobre Inteligˆencia Artificial e Algoritmo Gen´etico. Em seguida, ser´a discutido o problema e suas partes visando a melhor forma de encaixa-lo ao algoritmo para que o software consiga chegar com facilidade e rapidez ao objetivo que e´ o melhor quadro de hor´ario com todas as restric¸o˜ es satifeitas. Ent˜ao ser˜ao feitos v´arios testes para avaliar as poss´ıveis configurac¸o˜ es do AG com o problema proposto visando identificar a melhor configurac¸a˜ o. Por fim, ser˜ao apresentados gr´aficos comentados que provam que para este problema os m´etodos de cruzamento simples s˜ao bem mais eficientes que os permutativos. Palavras-chave: Automatizac¸a˜ o.

Inteligˆencia Artificial.

Algor´ıtmo Gen´etico.

Quadros de Hor´arios.

ABSTRACT

FERRAZ, Vinicius. TITLE IN ENGLISH. 49 f. Trabalho de conclus˜ao de curso – , Faculdades Integradas de Itarar´e - FAFIT. Itarar´e, 2016. The present work is study and implementation of Artificial Intelligence. Initially will be shown some definitions of Artificial Intelligence and Genetic Algorithm. So, will be discussed the problem and its parts aiming the best way to join it together with the algorithm for the software to achieve the best answer faster and easier. Then some tests are going to evaluate the possible configurations of the Genetic Algorithm with the proposed problem aiming the best configurations. At the end, comented graphics will be shown proving that for this problem the simple crossover methods are much more efficient than the permutatives ones. Keywords: Artificial Intelligence. Genetic Algorithm. Schedules. Automation.

LISTA DE FIGURAS

FIGURA 1 FIGURA 2 FIGURA 3 FIGURA 4 FIGURA 5 FIGURA 6 FIGURA 7 FIGURA 8 FIGURA 9 FIGURA 10 FIGURA 11 FIGURA 12 FIGURA 13 FIGURA 14 FIGURA 15 FIGURA 16 FIGURA 17 FIGURA 18 FIGURA 19 FIGURA 20 FIGURA 21 FIGURA 22 FIGURA 23 FIGURA 24

– – – – – – – – – – – – – – – – – – – – – – – –

Ciclo de Vida AG. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cruzamento de 1 ponto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cruzamento de 2 pontos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cruzamento Order 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cruzamento PMX. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Prot´otipo Gene. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Prot´otipo Cromossomo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Diagrama de Classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 1 - 1P Steady State. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 1 - 1P Generational. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 1 - 2P Steady State. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 1 - 2P Generational. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 1 - O1C Steady State. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 1 - O1C Generational. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 1 - PMX Steady State. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 1 - PMX Generational. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 2 - 1P Steady State. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 2 - 1P Generational. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 2 - 2P Steady State. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 2 - 2P Generational. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 2 - O1C Steady State. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 2 - O1C Generational. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 2 - PMX Steady State. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cen´ario 2 - PMX Generational. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18 21 22 22 23 29 30 31 35 36 36 37 38 38 39 39 40 41 41 42 42 43 43 44

LISTA DE TABELAS

TABELA 1 TABELA 2 TABELA 3 TABELA 4 TABELA 5 TABELA 6

– – – – – –

Exemplo de soluc¸a˜ o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exemplo de Tabela de Regras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Resultados de Tempo Cen´ario 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Resultados de Tempo Cen´ario 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Resultados de fitness Cen´ario 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Resultados de fitness Cen´ario 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17 20 44 45 45 45

LISTA DE SIGLAS

IA

Inteligˆencia Artifical

AG

Algor´ıtmo Gen´etico

O1C

Order 1 Crossover

PMX

Permutation Crossover

1P

Cruzamento de 1 Ponto

2P

Cruzamento de 2 Pontos

´ LISTA DE SIMBOLOS

n

En´esimo Termo, ou ultimo poss´ıvel

´ SUMARIO

˜ 1 INTRODUC ¸ AO .............................................................. 1.1 OBJETIVO GERAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 OBJETIVOS ESPEC´IFICOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 JUSTIFICATIVA DO TRABALHO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 ESTRUTURA DO TRABALHO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˆ 2 INTELIGENCIA ARTIFICIAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 2.1 O QUE E IA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 2.2 HISTORIA E RUMO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 2.3 O QUE E´ ALGORITMO GENETICO .......................................... ˜ 2.4 IMPLEMENTAC¸AO DE AG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 In´ıcio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 Populac¸a˜ o In´ıcial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.3 Selec¸a˜ o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.4 Cruzamento e Mutac¸a˜ o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.5 Substituic¸a˜ o, Nova Populac¸a˜ o e Loop Condicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 JAVA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 O QUE E´ JAVA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 FERRAMENTAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 JAVA E AG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 METODOLOGIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 DESENVOLVIMENTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 PROJETO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˜ 5.2 CLASSES E CONFIGURAC¸OES DE USO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˜ 5.3 SELEC¸AO NATURAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Controle do Ciclo de Vida do AG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.2 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ ˜ 6 RESULTADOS(ANALISE E DISCUSSAO) ................................... ´ 6.1 CENARIO 1 ................................................................. 6.1.1 1P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.2 2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.3 O1C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.4 PMX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 6.2 CENARIO 2 ................................................................. 6.2.1 1P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2 2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.3 O1C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.4 PMX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˜ 6.3 CONSIDERAC¸OES FINAIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˜ 7 CONCLUSAO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ˆ REFERENCIAS .................................................................

13 13 14 14 14 15 15 16 16 17 18 19 20 21 24 26 26 26 27 28 29 29 30 31 32 32 34 34 35 36 37 38 40 40 40 42 43 44 47 49

13

1

˜ INTRODUC ¸ AO

A IA e´ um assunto de certa relevˆancia dentro da programac¸a˜ o, pois um sistema que registra e manipula diversas informac¸o˜ es, mas n˜ao organiza tais informac¸o˜ es de forma estrat´egica com a finalidade de serem analisadas, dificilmente ter´a capacidade de identificar situac¸o˜ es comuns ou incomuns e poder´a deixar as decis˜oes a serem tomadas pelo usu´ario sem fundamentos, por fim se tornar´a apenas um sistema que registra informac¸o˜ es. Neste trabalho o tema de IA ser´a abordado como ferramenta para solucionar o problema que e´ organizar quadros de hor´arios de uma escola. Para solucionar este problema ser´a utilizada uma implementac¸a˜ o do Algoritmo Gen´etico, neste algoritmo a soluc¸a˜ o do problema e´ vista como um cromossomo, que neste caso ser´a o conjunto de quadros de hor´arios que juntos s˜ao cada quadro de horario de cada s´erie/turma da instituic¸a˜ o educacional de teste. Dentro deste problema existem diversas dificuldades tais como: grande quantidade de salas/turmas, grande quantidade de disciplinas a serem ministradas, grande quantidade de professores com hor´arios indispon´ıveis, quantidade de professores escassos para determinadas disciplinas, quantidade de aulas por dia para diferentes escolas, aulas que devem ficar seguidas e o esforc¸o exaustivo para organizar o quadro deixando cada professor ministrando as disciplinas corretas dentro de hor´arios dispon´ıveis para todas as s´eries/turmas da escola. Apesar do Algoritmo Gen´etico n˜ao poder solucionar a escassez de professores de algumas disciplinas, ele poder´a propor uma soluc¸a˜ o para o problema dos quadros de hor´arios e a contratac¸a˜ o de mais professores em escassez, caso n˜ao haja outra soluc¸a˜ o viavel atrav´es da troca de hor´arios. 1.1

OBJETIVO GERAL Agilizar o processo de elaborac¸a˜ o dos quadros de hor´arios de uma instituic¸a˜ o de ensino

por meio do software desenvolvido que usa inteligˆencia artificial para tal finalidade.

14

1.2

OBJETIVOS ESPEC´IFICOS • Atrav´es da Inteligˆencia Artificial, usar t´ecnicas de Algoritmo Gen´eticos para construir um software que organize um conjunto de quadros de hor´arios. • Analisar e implantar m´etodos de Algortimos Gen´eticos que favorec¸am soluc¸o˜ es otimizadas. • Estudar e analisar como combinar o problema dos quadros de hor´arios com os m´etodos dos Algor´ıtmos Gen´eticos. • Analisar e implantar um m´etodo para gerac¸a˜ o aleat´oria de quadros de hor´arios. • Analisar e implantar o melhor m´etodo de organizac¸a˜ o, reorganizac¸a˜ o e recombinac¸a˜ o dos quadros de hor´arios.

1.3

JUSTIFICATIVA DO TRABALHO A dificuldade do trabalho de se montar quadros de hor´arios manualmente cresce

exponencialmente de acordo com o n´umero das vari´aveis envolvidas: quantidade s´eries, quantidade turmas, quantidade professores, quantidade disciplinas e quantidade hor´arios. Diantes destas dificuldades ter uma opc¸a˜ o de software para esta tarefa pode ser uma soluc¸a˜ o melhor do que as dispon´ıveis no mercado. 1.4

ESTRUTURA DO TRABALHO Este trabalho est´a organizado da seguinte forma.

O cap´ıtulo 2 faz uma breve

introduc¸a˜ o a Inteligˆencia Artificial e explica sobre o Algor´ıtmo Gen´etico. O cap´ıtulo 3 faz uma breve introduc¸a˜ o a linguagem de programac¸a˜ o Java. O cap´ıtulo 4 fala sobre a metodologia deste experimento. O cap´ıtulo 5 fala como foi feita a programac¸a˜ o na implementac¸a˜ o do Algor´ıtmo Gen´etico para elaborac¸a˜ o do software. O cap´ıtulo 6 fala dos resultados obtidos nos experimentos com o software desenvolvido. O cap´ıtulo 7 traz a conclus˜ao dos resultados obtidos.

15

2

ˆ INTELIGENCIA ARTIFICIAL

Neste cap´ıtulo ser´a discutido o que e´ inteligˆencia artificial, um pouco da hist´oria e rumo. Tamb´em ser´a visto um algoritmo particularmente interessante que e´ o Algoritmo Gen´etico, deste algoritmo ser˜ao discutidos seus m´etodos e t´ecnicas de Implementac¸a˜ o: Fitness, m´etodos de selec¸a˜ o, m´etodos de substituic¸a˜ o e Operadores de Crossover. 2.1

O QUE E´ IA E´ uma ac¸a˜ o para fazer computadores pensarem, computadores programados para

simularem o pensamento humano para a automatizac¸a˜ o de tarefas intelectuais exercidas por humanos. Estas tarefas geralmente s˜ao tomadas de decis˜oes, resoluc¸o˜ es de problemas reais, escolhas que o computador faz tentando simular comportamentos humanos para que as escolhas parec¸am ter sido feitas por humanos, dentro deste contexto a IA est´a presente no software que ao receber o prontu´ario de um paciente, consegue determinar o diagn´otstico e receitar o rem´edio ideal, tamb´em esta presente no software que analisa o estado atual de uma empresa atrav´es dos hist´oricos de contas e faz o planejamento anual contabilizando investimentos e receitas. (HAUGELAND, 1989). E´ o estudo das faculdades mentais atrav´es do uso de modelos computacionais onde softwares simulam o processo de aprendizagem humano de tal forma que todo o funcionamento do cerebro possa ser simulado atrav´es de algor´ıtmos. Para alcanc¸ar este objetivo e´ necess´ario que o cerebro virtual simule o controle de o´ rg˜aos (olhos, brac¸os, pernas, pele, etc) como humanos. Este e´ o estudo das computac¸o˜ es que tornam poss´ıvel fazer com que m´aquinas possam perceber a realidade e o contexto no qual elas se encontram, raciocinem para que tomem decis˜oes baseadas nas situac¸o˜ es que se encontram e nas funcionalidades e fac¸am ac¸o˜ es de acordo com as decis˜oes computadas. (CHARNIAK; MCDERMOTT, 1985) (WINSTON, 1992) E´ a arte de criar m´aquinas que executem tarefas humanas que requerem inteligˆencia, estas m´aquinas s˜ao providas de softwares que simulam a inteligˆencia humana para que elas

16

possam captar fatos da realidade, tais como onde a m´aquina se encontra, em que situac¸a˜ o ela se encontra, se ela possu´ı materia-prima para exercer sua atividade, em geral, todo o contexto em que ela se situa para que possa funcionar da maneira esperada pelo engenheiro. Neste contexto, a inteligˆencia artificil esta no software do robo que monta um veiculo, no software do robo que pinta um veiculo e no software do robo que consegue seguir um trajeto, identificar um alvo e executar uma ac¸a˜ o para alcanc¸ar um objetivo. (KURZWEIL, 1990) 2.2

´ HISTORIA E RUMO Em 1943 Warren McCulloch e Walter Pitts realizaram um trabalho que foi reconhecido

historicamente como o primeiro trabalho de IA. Baseados no conhecimento da fisiologia b´asica e da func¸a˜ o dos neurˆonios no cerebro, uma an´alise formal da l´ogica proposicional criada por Russel e Whitehead e a teoria da computac¸a˜ o de Turing. Esses dois pesquisadores propuseram um modelo de neurˆonios artificiais no qual cada neurˆonio se caracteriza por estar “ligado” ou “desligado”, com a troca para “ligado” ocorrendo em resposta a` estimulac¸a˜ o por um n´umero suficiente de neurˆonios vizinhos. A IA abrange uma vasta variedade de subcampos desde a´ reas de uso geral, como aprendizado e percepc¸a˜ o at´e tarefas espec´ıficas como jogos, onde o advers´ario e´ um computador que consegue analisar situac¸o˜ es passadas aprendendo e desenvolvendo estrat´egias melhores para tentar vencer o jogador. (RUSSEL; NORVIG, 2004) Em resumo, a IA e´ um caminho enorme para ser explorado e com v´arias ramificac¸o˜ es e divis˜oes, pois, para cada atividade humana e´ poss´ıvel criar um algoritmo que preveja padr˜oes e/ou auxilie na gest˜ao de informac¸o˜ es ou na execuc¸a˜ o de atividades. 2.3

´ O QUE E´ ALGORITMO GENETICO Dentro da IA existe um algoritmo espec´ıfico que ser´a implementado neste trabalho

e se chama Algoritmo Gen´etico. Este algoritmo e´ uma abstrac¸a˜ o da teoria evolucionista de Darwin que foi desenvolvida em A Origem das Esp´ecies e que diz que durante a reproduc¸a˜ o dos seres vivos pode ocorrer mutac¸o˜ es que podem ser preservadas nas gerac¸o˜ es sucessivas. Numa reproduc¸a˜ o sexuada e´ necess´ario um organismo macho e outro femea, que s˜ao chamados de estados pais, eles geram um novo indiv´ıduo que resulta numa mistura gen´etica dos estados pais com a poss´ıvel mutac¸a˜ o. (RUSSEL; NORVIG, 2004) (DARWIN, 1859) De um ponto de vista mais t´ecnico e´ uma variante de busca em feixe estoc´astica,

17

onde s˜ao geradas soluc¸o˜ es aleat´orias e a partir destas soluc¸o˜ es s˜ao geradas recombinac¸o˜ es, recombinac¸o˜ es das recombinac¸o˜ es e assim sucessivamente at´e ser achada uma soluc¸a˜ o v´alida. A analogia em relac¸a˜ o a selec¸a˜ o natural ocorre no momento em que as soluc¸o˜ es ruins v˜ao sendo descartadas e as soluc¸o˜ es boas v˜ao sendo preservadas, igual ocorre na natureza selvagem onde apenas o ser mais apto sobrevive. A recombinac¸a˜ o simboliza reproduc¸a˜ o sexuada. Estes algoritmos codificam uma soluc¸a˜ o em potencial para um problema espec´ıfico em uma simples estrutura de dados, parecida com um cromossomo, ent˜ao a matriz de soluc¸o˜ es vai recombinando os cromossomos na tentativa de evolui-los. (WHITLEY, 1994) (RUSSEL; NORVIG, 2004) Em resumo, o algoritmo gen´etico e´ definido assim por ter a habilidade de gerar novas soluc¸o˜ es, a partir da populac¸a˜ o inicial (conjunto de poss´ıveis soluc¸o˜ es aleat´orias), atrav´es de cruzamentos e mutac¸o˜ es. Contudo, n˜ao basta apenas gerar novas soluc¸o˜ es se n˜ao for poss´ıvel avalia-las, afinal uma nova soluc¸a˜ o pode ser melhor ou pior, por´em o foco deve ser sempre uma soluc¸a˜ o que resolva melhor o problema em quest˜ao, assim o algoritmo gen´etico vai avaliando e filtrando a nova populac¸a˜ o que vai sendo gerada at´e chegar na melhor soluc¸a˜ o poss´ıvel. 2.4

˜ DE AG IMPLEMENTAC¸AO Durante o processo de implementac¸a˜ o do algoritmo gen´etico o primeiro passo e´

projetar a soluc¸a˜ o do problema a ser resolvido como um cromossomo. O cromossomo e´ composto de v´arios genes que s˜ao representac¸o˜ es das vari´aveis envolvidas na soluc¸a˜ o do problema, ele deve ser codificado numa String simples para simplificar o tratamento e melhorar o desempenho do algoritmo. (WHITLEY, 1994) Na tabela 1 e´ poss´ıvel observar uma poss´ıvel soluc¸a˜ o para o problema de uma escola com 1 s´erie para ter o hor´ario montado. Tabela 1: Exemplo de soluc¸a˜ o

S´erie 1 SEG Mat - Dan Mat - Dan Geo - Eli Geo - Eli

TER QUA QUI SEX Port - Ma Ed.F - Net Port - Z´e Bio - Lu Port - Ma Ing - Ma Port - Z´e Bio - Lu Hist - F´a Quim - Ca Mat - Dan F´ıs - Tom Hist - F´a Quim - Ca Mat - Dan F´ıs - Tom Fonte: Autoria pr´opria.

Esta soluc¸a˜ o deve ser montada numa String e pode ficar assim: s1(SEG(mat-dan;mat-dan;geo-eli;geo-eli);TER(port-ma;port-ma;hist-fa;hist-

18

fa);QUA(ed.f-net;ing-ma;quim-ca;quim-ca); QUI(port-ze;port-ze;mat-dan;mat-dan); SEX(biolu;bio-lu;fis-tom;fis-tom)) A estrutura seria isso: uma matriz de 3 dimens˜oes onde a primeira dimens˜ao e´ de s´eries, a segunda de dias, a terceira de aulas com as informac¸o˜ es da disciplina e professor. Esta matriz resulta numa matriz multidimensional de disciplina e professor. A partir do momento que o cromossomo est´a projetado e´ importante conhecer o ciclo de vida do Algoritmo Gen´etico. O AG tem basicamente 7 passos.

INÍCIO POPULAÇÃO INÍCIAL

SELEÇÃO CROSSOVER & MUTAÇÃO NOVA POPULAÇÃO

LOOP CONDICIONAL

FIM Figura 1: Ciclo de Vida AG. Fonte: Adaptado de (LARGET, 2012)

2.4.1

IN´ICIO No inicio e´ importante levar em considerac¸a˜ o algumas vari´aveis que podem ser usadas

no controle do algoritmo: • Gerac¸a˜ o: Valor limitador de execuc¸a˜ o do algortimo, este valor define quantas gerac¸o˜ es ser˜ao criadas ap´os a populac¸a˜ o inicial.

19

• Populac¸a˜ o: Vetor que geralmente e´ limitado para uma poss´ıvel populac¸a˜ o m´axima que impede o algoritmo de criar cromossomos al´em deste valor. • Populac¸a˜ o Intermedi´aria: Populac¸a˜ o dos cromossomos selecionados para reproduc¸a˜ o e gerac¸a˜ o da nova populac¸a˜ o. Os cromossomos selecionados podem ser repetidos de acordo com o m´etodo de selec¸a˜ o. • Porcentagem de Mutac¸a˜ o: Esta porcentagem define a probabilidade de um cromossomo ser alvo de uma mutac¸a˜ o gen´etica, durante a concepc¸a˜ o ap´os o crossover, e ter o valor de um determinado gene alterado aleat´oriamente. • Pontos de Corte: S˜ao pontos pr´e-definidos no cromossomo onde ocorrer˜ao as divis˜oes dos cromossomos para a reconstruc¸a˜ o dos novos cromossomos mesclando partes dos cromossomos pais. Em um crossover simples e´ definido apenas um ponto de corte, por´em pode haver mais pontos como ser´a visto adiante. (LARGET, 2012) 2.4.2

˜ IN´ICIAL POPULAC¸AO Durante esta etapa o algor´ıtmo normalmente gera uma populac¸a˜ o inicial aleat´oria, o

tamanho desta populac¸a˜ o e´ definido pelo tamanho do vetor populac¸a˜ o. Uma populac¸a˜ o inicial grande pode trazer resultados melhores mais rapido por´em retardar´a o processo do ciclo de vida. (LARGET, 2012) Em seguida ser´a avaliado e atribu´ıdo um valor a` cada cromossomo da populac¸a˜ o, este valor e´ calculado a partir da sua composic¸a˜ o gen´etica, ou seja, cada cromossomo ter´a todos os seus genes avaliados por uma func¸a˜ o conhecida como func¸a˜ o objetivo que definir´a o qu˜ao boa e´ determinada composic¸a˜ o de genes usando de regras, este valor e´ chamado avaliac¸a˜ o ou fitness, este c´alculo tamb´em e´ feito para os novos cromossomos gerados na nova populac¸a˜ o. (LARGET, 2012) Os termos fitness e avaliac¸a˜ o podem ser vistos e usados como sinˆonimos, por´em e´ bom fi fazer distinc¸a˜ o entre eles. No AG canˆonico, fitness e´ definido por f (x) = onde fi e´ a avaliac¸a˜ o f relacionada a string i e f e´ a m´edia da avaliac¸a˜ o de todas as strings na populac¸a˜ o, primeiro os cromossomos s˜ao avaliados, e somente ap´os toda a populac¸a˜ o ser avaliada e´ que ser´a calculado o fitness, deste modo, o fitness cresce na medida que a populac¸a˜ o se desenvolve, o que pode retardar o processo evolutivo, por´em garantindo uma populac¸a˜ o com fitness mais equilibrado gerando melhores chances de reproduc¸a˜ o. (WHITLEY, 1994) Para estimar o fitness e´ proposto o uso de regras e para tal a criac¸a˜ o de uma tabela que

20

deve conter dois tipos de regras, para cada regra violada uma subtrac¸a˜ o do fitness e para cada regra satisfeita uma adic¸a˜ o ao fitness: (LARGET, 2012) 1. Soft: Uma regra que pode ser quebrada sem comprometer a soluc¸a˜ o, a custo de uma pequena subtrac¸a˜ o do fitness, e que ao ser obedecida soma-se uma pequena quantidade de fitness. 2. Hard: Uma regra que ao ser quebrada compromete toda a soluc¸a˜ o zerando o fitness. O fitness deve variar entre 0 e 1, sendo 0 uma soluc¸a˜ o inaceit´avel, que quebrou pelo menos uma regra hard, at´e 1, uma soluc¸a˜ o que talvez o software n˜ao chegue, a soluc¸a˜ o perfeita. (LARGET, 2012) Tabela 2: Exemplo de Tabela de Regras

Tipo Gene Soft xxx Hard xxx Soft yyy Hard yyy Soft zzz Hard zzz

Regra >= 1000 >2000 2000

Satifeita +0,1 0 +0,1 0 +0,1 0

Insatisfeita -0,1 +0,1 -0,1 +0,1 -0,1 +0,1

Fonte: Autoria pr´opria.

2.4.3

˜ SELEC¸AO Nesta etapa todo cromossomo da populac¸a˜ o estar´a com o seu fitness calculado

permitindo com grande facilidade identificar os melhores cromossomos para o cruzamento. (HOFFMANN, 2013) Para selecionar cromossomos existem v´arios m´etodos, entre eles: • Roleta: Neste m´etodo a populac¸a˜ o e´ vista como um gr´afico pizza onde a porc¸a˜ o preenchida por cada cromossomo corresponde ao valor do seu fitness, ou seja, quanto maior o fitness maior a porc¸a˜ o do pedac¸o e maiores s˜ao as chances do cromossomo ser selecionado, a selec¸a˜ o da populac¸a˜ o intermedi´aria ocorre de forma estoc´astica girando um valor ao redor da pizza como naquele jogo de roleta de cassinos. (WHITLEY, 1994) • Resto de Amostra Estoc´astica: Este e´ o m´etodo que mais se aproximar´a do valor do fitness esperado. Ele utiliza do fitness calculado com base na avaliac¸a˜ o do cromossomo

21

fi e ter´a valor pr´oximo a 1. Este valor f representa em porcentagem a chance do cromossomo entrar na populac¸a˜ o intermedi´aria, e da populac¸a˜ o, ou seja o fitness usa da formula

ou seja, 0,8 representa 80% de chance e 1,2 representa 120% que e´ uma c´opia mais 20% de chance para uma segunda c´opia.(WHITLEY, 1994) • Amostra Estoc´astica Universal: Este m´etodo e´ parecido com a roleta, por´em seleciona toda a populac¸a˜ o intermedi´aria de uma s´o vez. (WHITLEY, 1994) • Torneio estoc´astico: Neste m´etodo primeiro e´ configurado o numero n de participantes do torneio. De acordo com o n´umero de paticipantes, s˜ao selecionados n cromossomos para o torneio que selecionar´a o cromossomo com o maior fitness. E´ criado um torneio para selecionar cada um dos pais. (HOFFMANN, 2013) 2.4.4

˜ CRUZAMENTO E MUTAC¸AO O cruzamento e´ o m´etodo respons´avel por retirar uma parte da informac¸a˜ o gen´etica do

cromossomo pai e outra parta da m˜ae e criar um novo cromossomo cruzando estas informac¸o˜ es. Os m´etodos de cruzamento podem ser divididos em 2 categorias: • Simples: Que cruzam as informac¸o˜ es indiscriminadamente. • Permutativos: Que tentam manter as regras que existem entre os genes. Existem diversos m´etodos de cruzamento que criam 1 ou mais novos cromossomos de uma vez, entre os m´etodos veremos: 1 Ponto: E´ gerado aleatoriamente 1 ponto de corte e feita uma recombinac¸a˜ o pegando a 1a parte do pai e a 2a parte da m˜ae.

Figura 2: Cruzamento de 1 ponto. Fonte: Autoria Pr´opria

22

2 Pontos: S˜ao gerados aleatoriamente 2 pontos de cortes para os dois cromossomos e feito recombinac¸o˜ es a partir dos cortes, do pai e´ herdado a 1a e a 3a parte e da m˜ae a parte do meio.

Figura 3: Cruzamento de 2 pontos. Fonte: Autoria Pr´opria

Order 1 Crossover: Este e´ um m´etodo de permutac¸a˜ o. Basicamente, uma parte de alelos consecutivos s˜ao herdados do pai, o restante dos valores s˜ao colocados como aparecem na m˜ae. Genes com valores repetidos podem ser evitados, assim n˜ao ocorre o risco do filho nascer com genes comprometidos que quebram alguma regra. (STARKWEATHER et al., 2011)

x

8473625190

0123456789

36251

0123456789 0473625189

Figura 4: Cruzamento Order 1. Fonte: Autoria Pr´opria

Explicando a figura 4: 1. Foi selecionada a parte x do pai, genes no retˆangulo: 3,6,2,5,1. 2. E´ iniciada uma busca e marcac¸a˜ o dos genes presentes na parte x na m˜ae. 3. Os genes da parte x do pai s˜ao herdados diretamente pelo filho.

23

4. Em seguida o O1C comec¸a a copiar sequencialmente os genes sublinhados da m˜ae a partir da posic¸a˜ o final da parte x, seguindo esta l´ogica copiou os genes 8,9,0, 4 e 7. PMX Crossover: Este operador funciona parecido com o Order 1, e´ uma permutac¸a˜ o que ignora genes repetidos, por´em disp˜oe de um m´etodo diferente para evitar genes repetidos que j´a foram acomodados no corte inicial que veio do pai. (STARKWEATHER et al., 2011).

8473625190

0123456789

36251

Acomodando gene 4

Acomodando gene 7

8473625190

8473625190

0123456789

0123456789

436251

7436251

Acomodando os demais 0123456789 0743625189

Figura 5: Cruzamento PMX. Fonte: Autoria Pr´opria

Explicando a figura 5: 1. E´ recortado a parte x do pai que e´ herdado diretamente pelo filho . 2. Dentro da a´ rea de corte correspondente da m˜ae, o algor´ıtmo procura por genes que ainda n˜ao foram herdados e devido a isso marca o 4 e o 7 e inicia um processo para que estes genes sejam acomodados no filho. 3. O processo para localizar o espac¸o e´ assim: a) Ao identificar que o gene n que est´a de fora, o algor´ıtmo verifica o valor que o gene n ocupa no pai. b) Localiza o mesmo valor na m˜ae.

24

c) Se o ´ındice do valor na m˜ae estiver dentro da area de corte, ent˜ao voltar ao passo a) usando o valor. d) Se a posic¸a˜ o n˜ao estiver na a´ rea de corte, ent˜ao inserir o gene n nesta posic¸a˜ o do filho. 4. Copiar os demais valores da m˜ae para o filho. E´ tendˆencia natural durante as iterac¸o˜ es do ciclo de vida do algor´ıtmo, que a populac¸a˜ o se torne cada vez mais homogˆenea, por´em o ideal e´ manter uma pequena frac¸a˜ o da populac¸a˜ o com genes diferenciados. Para criar genes diferenciados e´ necess´ario usar de func¸o˜ es de mutac¸o˜ es que durante o cruzamento, se a porcentagem de mutac¸a˜ o for alcanc¸ada, o novo cromossomo sofrer´a uma mutac¸a˜ o onde os genes indicados aleat´oriamente ter˜ao seu valores alterados conforme definido pela func¸a˜ o. A mutac¸a˜ o pode ocorrer de v´arias formas, entre elas: Invers˜ao de genes, deslizamento de genes e alterac¸a˜ o aleat´oria do valor de genes. (HOFFMANN, 2013) 2.4.5

˜ NOVA POPULAC¸AO ˜ E LOOP CONDICIONAL SUBSTITUIC¸AO, Ap´os a finalizac¸a˜ o do processo de cruzamento e´ o momento da substituic¸a˜ o da

populac¸a˜ o, momento em que o algor´ıtmo decide quais dos cromossomos gerados anteriormente e dos novos ser˜ao levados para a nova populac¸a˜ o. (HOFFMANN, 2013) Existem 2 t´ecnicas distintas de substituic¸a˜ o que s˜ao: • Steady State: Nesta t´ecnica o n´umero de filhos que s˜ao passados a nova populac¸a˜ o e´ limitado. Para que sejam inclu´ıdos filhos, o algor´ıtmo deve selecionar pais para serem descartados com a finalidade de liberar vagas. Esta t´ecnica tenta reproduzir o modo que ocorre nas gerac¸o˜ es de algumas esp´ecies de animais que mesmo um avˆo ainda pode ter bons filhos e concorrer com os netos e seus filhos. (HOFFMANN, 2013)(BEASLEY et al., 1993) • Generational: Nesta t´ecnica toda a gerac¸a˜ o predecessora e´ descartada sendo substitu´ıda pela gerac¸a˜ o sucessora. Assim como ocorre em algumas esp´ecies de insetos que morrem ao procriar. (HOFFMANN, 2013) Para apoio da t´ecnica de selec¸a˜ o utilizada existe outro m´etodo que pode ser usado em conjunto chamado Elitismo. O Elitismo far´a com que certos indiv´ıduos da populac¸a˜ o sejam eleitos para a nova populac¸a˜ o independente das condic¸o˜ es da execuc¸a˜ o. (HOFFMANN, 2013)

25

Ap´os a finalizac¸a˜ o do processo de cruzamento e selec¸a˜ o a nova populac¸a˜ o estar´a pronta para ser avaliada, ter seu fitness calculado e iterar pelo ciclo de vida do algor´ıtmo at´e o fim que ocorre no loop condicional quando o limite de gerac¸a˜ o e´ alcanc¸ado. (HOFFMANN, 2013)

26

3

JAVA

3.1

O QUE E´ JAVA Java e´ uma linguagem de programac¸a˜ o utilizada para criac¸a˜ o de softwares port´aveis

entre sistemas operacionas, grac¸as a JRE qualquer aplicativo desenvolvido em Java pode rodar tranquilamente em sistemas Unix, Windows, Mac, entre outros. Java opera com objetos, um obejto e´ uma composic¸a˜ o de vari´aveis que podem ser manipuladas ao ser chamado algum de seus m´etodos. Um m´etodo e´ uma sequˆencia de instruc¸o˜ es que podem acessar e alterar as informac¸o˜ es internas do objeto. Quando um m´etodo e´ chamado, n˜ao se sabe exatamente todo o procedimento ocorrido internamente, por´em o resultado deve ser claro o suficiente para que o m´etodo seja utiliz´avel e e´ isto que importa. (HORSTMANN; CORNELL, 1993) Java e´ uma linguagem orientada a objetos e isso torna Java uma linguagem muito produtiva e reutiliz´avel, por exemplo se e´ criado um objeto base com atributos e m´etodos gen´ericos, e´ poss´ıvel criar um objeto mais complexo e espec´ıfico que herde todos os atributos e m´etodos, e caso algum m´etodo precise ser alterado e´ poss´ıvel fazer uma revis˜ao deste m´etodo na especializac¸a˜ o do objeto usando o comando @Override1 . (HORSTMANN; CORNELL, 1993) Java possu´ı uma enorme variedade de bibliotecas que auxiliam na produc¸a˜ o de softwares, s˜ao bibliotecas para gr´aficos, interfaces, design, criptografia, redes, som, armazenamento em banco de dados e muitos outros prop´ositos. (HORSTMANN; CORNELL, 1993) 3.2

FERRAMENTAS Para o desenvolvimento em java e´ primordialmente necess´ario um editor de c´odigo

fonte, para este caso existem diversas ferramentas que podem ser usadas desde ferramentas de edic¸a˜ o de texto simples, estas consomem pouqu´ıssima mem´oria, por´em n˜ao contribuem 1 Comando/Palavra

reservada que deve ser escrito antes da declarac¸a˜ o do m´etodo a ser revisado. Pode ser interpretado como revisar.

27

para a efic´acia da tarefa de programar, pois uma verdadeira ferramenta de edic¸a˜ o de c´odigo faz necess´ario uma composic¸a˜ o de ferramentas, tais como: func¸a˜ o de autocompletar c´odigos, localizac¸a˜ o e substituic¸a˜ o de palavras, navegador de arquivos do projeto, verificador ortogr´afico, debug, compilac¸a˜ o do c´odigo fonte, macros auxiliares, etc. Todas essas ferramentas juntas formam o que e´ chamado de IDE, Integrated Development Enviroment (Ambiente de Desenvolvimento Integrado). A IDE que ser´a usada para a codificac¸a˜ o do projeto e´ o Netbeans. 3.3

JAVA E AG Java possu´ı algumas biblioteca para o desenvolvimento de algoritmos gen´eticos,

entre elas: JGAP, JAGA, Jenes. Por´em para este trabalho ser´a desenvolvido o algor´ıtmo personalizado focado na melhora da performance.

28

4

METODOLOGIA

O experimento representa o melhor exemplo de pesquisa cient´ıfica e e´ composto de 3 etapas: (GIL, 2002) 1. Apontar um objeto de estudo. 2. Identificar e selecionar as vari´aveis capazes de alterar o objeto de estudo. 3. Identificar as formas de controle e de influˆencia de cada vari´avel sobre o objeto de estudo. O objeto de estudo deste experimento e´ aplicar a otimizac¸a˜ o utilizando de Algor´ıtmos Gen´eticos para resolver o problema de criac¸a˜ o e organizac¸a˜ o de hor´arios envolvendo os relacionamentos entre S´erie/Turma, Disciplina e Professor. As t´ecnicas de reproduc¸a˜ o (Crossover, Mutac¸a˜ o), m´etodos de selec¸a˜ o (Roleta e Torneio) e m´etodos de substituic¸a˜ o (Generational e Steady State) s˜ao as vari´aveis e sub experimentos que fazem parte do Algor´ıtmo Gen´etico no momento da adaptac¸a˜ o do problema. Para identificar as formas de controle e influˆencias das vari´aveis ser˜ao criados 2 cen´arios que seguir˜ao um padr˜ao e servir˜ao para medir o desempenho e performance do Algor´ıtmo Gen´etico para o problema proposto: • Cen´ario pequeno com poucas salas e turmas, f´acil de ser solucionado. • Cen´ario grande com uma quantidade significativa de turmas e disciplinas, exigir´a um esforc¸o consider´avel para ser solucionado. Para a avaliac¸a˜ o de desempenho ser˜ao gerados resultados num´ericos, mas ser˜ao representados por gr´aficos que demonstrar˜ao a evoluc¸a˜ o e desempenho do algor´ıtmo.

29

5

DESENVOLVIMENTO

Neste cap´ıtulo ser´a comentado como foi elaborado o software em quest˜ao. 5.1

PROJETO Para a soluc¸a˜ o do problema de organizar um quadro de hor´arios foi escolhido o uso

do algoritmo gen´etico para encontrar a melhor soluc¸a˜ o poss´ıvel, para tal finalidade foi criado um prot´otipo da soluc¸a˜ o que ser´a usado pelo AG para criar soluc¸o˜ es aleat´orias e criar novas soluc¸o˜ es a partir das soluc¸o˜ es criadas. Todas as soluc¸o˜ es ser˜ao avaliadas e o AG continuar´a a busca at´e encontrar uma soluc¸a˜ o o´ tima. O prot´otipo da soluc¸a˜ o ser´a referenciado como cromossomo que e´ composto por genes, a estrutura b´asica do gene foi projetada no software para conter apenas as informac¸o˜ es da disciplina e do professor. Disciplina

Professor

Figura 6: Prot´otipo Gene. Fonte: Autoria Pr´opria

Pensando na ligac¸a˜ o direta que h´a entre disciplina e professor, o gene foi projetado para conter apenas essas duas informac¸o˜ es que s˜ao dependentes, a disciplina deve ser obrigatoriamente ministrada por um professor capacitado nela. Tendo em mente que os dias, aulas e s´eries s˜ao dados constantes e invari´aveis, ent˜ao ser˜ao declarados como vetores, percorridos e preenchidos de forma sequencial. O cromossomo ser´a uma matriz tridimensional composta de N genes.

N = dias ∗ aulas ∗ turmas

(1)

Explicando a equac¸a˜ o 1, dias s˜ao os dias de aulas (padr˜ao = 5, segunda a sexta), aulas

30

e´ a quantidade de aulas por dia (padr˜ao = 4), s´eries e´ o total de s´eries cadastradas.

Série 1 Série 2 Dia 1

Dia 1

Dia 2

Dia n

Série n

Disciplina Professor

Dia 1

Dia 2

Dia 2

Dia n

Aula 1 Aula 2 Aula 3 Aula 4 Aula 5 Aula n

Dia n

Figura 7: Prot´otipo Cromossomo. Fonte: Autoria Pr´opria

5.2

˜ CLASSES E CONFIGURAC¸OES DE USO Neste momento foi comprovada a necessidade de criar interface, controladores e

classes para fazer a pr´e-configurac¸a˜ o das informac¸o˜ es, tais como: Cadastro de Disciplinas: Uma lista contendo todas as disciplinas que ser˜ao ensinadas. Cadastro de Professores: Uma lista dos professores, que contenha a lista de disciplinas ministradas por ele e uma tabela de disponibilidade onde para cada aula do dia possa ser definido se o professor pode ou n˜ao pegar aula. Cadastro de S´eries: Uma lista das s´eries cadastradas, neste cadastro tamb´em deve conter a grade curricular, lista de disciplinas ensinadas para a s´erie. Escola: Entidade respons´avel por gerenciar os cadastros.

Conter´a a lista de

Disciplinas, lista de S´eries e lista de Professores, al´em de outros m´etodos que ser˜ao usados para gest˜ao. Cromossomo: Classe que far´a uso da classe escola para definir o modelo do cromossomo e conter´a m´etodos de crossover, c´alculo de fitness, entre outros m´etodos comuns ao AG. Gene: Cada gene corresponde a uma determinada aula que e´ composta por uma disciplina e um professor.

31

Figura 8: Diagrama de Classes. Fonte: Autoria Pr´opria

5.3

˜ NATURAL SELEC¸AO Com o b´asico definido, ser´a preciso aprofundar no algor´ıtmo gen´etico e implementar

os m´etodos de selec¸a˜ o, os m´etodos de cruzamento, os m´etodos de substituic¸a˜ o e os m´etodos de mutac¸a˜ o.

32

Como s˜ao v´arias opc¸o˜ es de cada etapa, a classe Selec¸a˜ o Natural possu´ı todos os m´etodos implantados. Esta e´ a classe principal do projeto que faz todo o gerenciamento do AG e suas configurac¸o˜ es e criac¸a˜ o dos relat´orios de desempenho. 5.3.1

CONTROLE DO CICLO DE VIDA DO AG Aqui ser´a comentado a implementac¸a˜ o de alguns m´etodos que necessitam de

implementac¸o˜ es espec´ıficas e controlam o ciclo de vida do AG: • evolucao: E´ respons´avel por cuidar do ciclo de vida do AG, neste m´etodo ser´a iterado de 0 at´e o valor da vari´avel POPULACAO o m´etodo geraFilhos. Ao final registra o tempo de durac¸a˜ o do ciclo de vida do AG e exibe a melhor soluc¸a˜ o encontrada. • geraFilhos: M´etodo que executa os seguintes procedimentos: 1. Seleciona os pais, de acordo com o m´etodo de selec¸a˜ o escolhido pela vari´avel METODO SELECAO. 2. Cruza os pais, de acordo com o m´etodo de crossover definido pela vari´avel METODO CRUZAMENTO. A mutac¸a˜ o ocorre no construtor do Chromossomo e foi programada da seguinte forma, ao localizar uma aula, com professor com hor´ario indispon´ıvel ou com outra aula no mesmo hor´ario, ter´a um novo professor, que ensine a disciplina da aula, escolhido de forma aleat´oria. 3. Faz a substituic¸a˜ o da populac¸a˜ o de acordo com o m´etodo de substituic¸a˜ o selecionado pela vari´avel METODO SUBSTITUICAO. 4. Aplica o Elistimo se a opc¸a˜ o ELITISMO for verdadeira e o valor da vari´avel ELITISMO TAMANHO for maior que 0. 5. Cria o output para a elaborac¸a˜ o do gr´afico de desempenho do algor´ıtmo. 5.3.2

CROSSOVER Como h´a diferenc¸a nos m´etodos de cruzamento, foi usado 2 m´etodos simples e 2

permutativos, o cruzamento ocorre de forma diferente dependendo do m´etodo. Cruzamento Simples: Para os m´etodos de 1 ponto e 2 pontos foi definido que o corte ocorre na matriz de s´eries, ou seja, se um cromossomo possu´ı 7 s´eries cadastradas, ent˜ao uma

33

poss´ıvel reproduc¸a˜ o pegar´a as 3 primeiras s´eries do pai e as demais da m˜ae, isso sem alterar nenhum quadro de hor´ario destas s´eries. Cruzamento Permutativo: Para os m´etodos O1C e PMX foi definido que cortes ocorrem 1 vez por s´erie cadastrada, ou seja, um cromossomo que possu´ı 7 s´eries cadastradas ter´a 7 cortes alterando todos os quadros de hor´arios da seguinte forma: herdar´a uma parte das aulas diretamente do pai e herdar´a outra parte da m˜ae, por´em os genes tomar˜ao cuidado para respeitarem a grade curricular da s´erie, ou seja, caso a nova soluc¸a˜ o herde 2 aulas de inglˆes do pai, a grade curricular possua apenas 2 aulas de inglˆes, a nova soluc¸a˜ o esteja prestes a herdar mais uma aula de inglˆes da m˜ae, ent˜ao o algor´ıtmo evitar´a esta aula de inglˆes e procurar´a completar corretamente a grade curricular.

34

6

´ ˜ RESULTADOS(ANALISE E DISCUSSAO)

Neste cap´ıtulo ser˜ao apresentados os resultados obtidos atrav´es das simulac¸o˜ es feitas no programa com base na evoluc¸a˜ o do fitness para cada operador de cruzamento. Para os testes foram planejados dois cen´arios um pequeno e outro grande. Para os dois cen´arios foi definida uma grade fixa de disciplinas definida como: 4x Portuguˆes, 4x Matem´atica, 2x Hist´oria, 2x Geografia, 2 Biologia, 2x Qu´ımica, 2x F´ısica, 1x Educac¸a˜ o F´ısica, 1x Inglˆes. Para os dois cen´arios tamb´em ser˜ao realizados v´arios testes para encontrar a melhor combinac¸a˜ o de m´etodo de selec¸a˜ o, m´etodo de cruzamento e m´etodo de substituic¸a˜ o. Para todos os testes foram definidas algumas configurac¸o˜ es, por exemplo: • Todos os testes ter˜ao mutac¸a˜ o de 20%. • Elistimo s´o ser´a usado com o m´etodo de selec¸a˜ o Generational configurado com tamanho para apenas uma soluc¸a˜ o. • Para o m´etodo de selec¸a˜ o Steady State, o numero de eliminados ser´a de 1/3 da populac¸a˜ o. • O tamanho do torneio estoc´astico ser´a 2. • Para os dois cen´arios ser˜ao executados v´arios testes para avaliar os m´etodos de selec¸a˜ o e substituic¸a˜ o. 6.1

´ CENARIO 1 Este, que foi definido como o mais simples de ser solucionado, possuir´a 5 s´eries

e professores em abundˆancia para que seja poss´ıvel chegar numa soluc¸a˜ o rapidamente. Professores: 4x Portuguˆes, 4x Matem´atica, 2x Geografia e Hist´oria, 2x Qu´ımica e Biologia, 1x F´ısica, 1x Educac¸a˜ o F´ısica e 1x Inglˆes. Para os testes a seguir foi usada uma populac¸a˜ o de 300 cromossomos por 20 gerac¸o˜ es.

35

6.1.1

1P O primeiro teste consiste na seguinte configurac¸a˜ o: M´etodo de substituic¸a˜ o Steady

State e m´etodos de selec¸a˜ o roleta e torneio, figura 9. O algor´ıtmo consegue criar uma soluc¸a˜ o perfeita rapidamente e evolu´ı toda a populac¸a˜ o em at´e 20 gerac¸o˜ es. Como pode ser observado na figura 9, o m´etodo de selec¸a˜ o Steady State, por s´o trocar os piores 1/3 da populac¸a˜ o sobrevivente por 1/3 da dos filhos gerados, as vezes gera soluc¸o˜ es piores no 1/3 que entra do que no 1/3 que sa´ı, isso pode ser bem observado na figura 9 com m´etodo de selec¸a˜ o roleta, que n˜ao conseguiu que a pior soluc¸a˜ o chegasse a perfeic¸a˜ o. Roleta - Duração 454ms 1000 995 990 985 980 975 970 0 2 4 Torneio Estocástico - Duração 466ms 1000 995 990 985 980 975 970 965 0 2 4

Max. Med. Min.

6

8

10

12

14

16

18

20

Max. Med. Min.

6

8

10 Geração

12

14

16

18

Figura 9: Cen´ario 1 - 1P Steady State. Fonte: Autoria Pr´opria

E´ poss´ıvel observar pela figura 9 que a roleta parece demorar um pouco mais que o torneio para deixar a populac¸a˜ o homogˆenea. Na figura 10 e´ poss´ıvel observar a principal caracter´ıstica da Generational, que e´ trocar toda a populac¸a˜ o pelos filhos de uma vez, as linhas med. e min. mostram quedas que ocorrem devido a indiv´ıduos de baixo fitness que entraram na populac¸a˜ o, isso s´o n˜ao ocorre na max. porque para a execuc¸a˜ o do Generational foi ativado o Elistismo que segura o cromossomo do topo na populac¸a˜ o. Se compararmos a figura 9 com a figura 10 podemos observar que apesar dos 4 testes terem chego extremamente r´apidos em uma soluc¸a˜ o perfeita, em m´edia 485 milisegundos, caso n˜ao tivessem chego, o m´etodo de substituic¸a˜ o Generational teria chances muito maiores de evoluir a populac¸a˜ o do que pelo Steady State que praticamente deixou a populac¸a˜ o homogˆenea. Tamb´em e´ possivel observar que a selec¸a˜ o Generational parece consumir um pouco mais de tempo e processamento, tempo m´edio dos testes Generational = 511 milisegundos, tempo

20

36 Roleta - Duração 510ms 1000 995 990 985 980 975 970 965 960 955 950 0 2 4 Torneio Estocástico - Duração 512ms 1000 995 990 985 980 975 970 965 960 955 0 2 4

Max. Med. Min.

6

8

10

12

14

16

18

20

Max. Med. Min.

6

8

10

12

14

16

18

20

Geração

Figura 10: Cen´ario 1 - 1P Generational. Fonte: Autoria Pr´opria

m´edio dos testes Steady State = 460 milisegundos. O tempo m´edio dos testes com o m´etodo de cruzamento 1P foi 485,5 milisegundos. 6.1.2

2P

Roleta - Duração 539ms 1000 995 990 985 980 975 970 0 2

Max. Med. Min.

4

Torneio Estocástico - Duração 416ms 1000 995 990 985 980 975 970 965 0 2 4

6

8

10

12

14

16

18

20

Max. Med. Min.

6

8

10

12

14

16

18

Geração

Figura 11: Cen´ario 1 - 2P Steady State. Fonte: Autoria Pr´opria

Diferente dos testes da figura 9, que demoraram um pouco mais para chegar numa populac¸a˜ o homogˆenea, os testes da figura 11 foram mais r´apidos e os ´ındices min, med e max convergiram rapidamente, o que demonstra que o m´etodo 2P tem uma tendˆencia maior para evoluir mais r´apido a populac¸a˜ o do que o m´etodo 1P. O 2P em conjunto com o m´etodo de substituic¸a˜ o Generational apresentou resultados

20

37 Roleta - Duração 515ms 1000 995 990 985 980 975 970 965 960 955 0 2 4 Torneio Estocástico - Duração 438ms 1000 995 990 985 980 975 970 965 960 0 2 4

Max. Med. Min.

6

8

10

12

14

16

18 Max. Med. Min.

6

8

10 G

12

14

16

18

ã

Figura 12: Cen´ario 1 - 2P Generational. Fonte: Autoria Pr´opria

inesperados ao apresentar uma linha de min. sem quedas, aparentemente um comportamento at´ıpico. Ao compararmos as figuras 11 e 12 pode-se notar um padr˜ao bem claro na curva de evoluc¸a˜ o que s´o n˜ao foi obedecido na figura 12 pelo m´etodo roleta. O tempo m´edio dos testes com 2P com os m´etodos de selec¸a˜ o roleta e torneio foram respectivamente 527 e 427 milisegundos. O tempo m´edio dos testes com o m´etodo de cruzamento 2P foi 477 milisegundos. 6.1.3

20

O1C Nos gr´aficos a seguir e´ poss´ıvel verificar uma grande diferenc¸a em relac¸a˜ o aos gr´aficos

anteriores, as curvas de med. e min. seguem visivelmente o padr˜ao das curvas dos gr´aficos anteriores com m´etodo de substituic¸a˜ o Generational, isso ocorre porque o O1C e´ um m´etodo permutativo e o corte e´ feito em cada quadro de hor´ario, por isso, quando ele est´a alocando os genes que ser˜ao herdados da m˜ae, estes genes s˜ao alocados para evitar a quebra das regras da grade curricular resultando numa soluc¸a˜ o totalmente diferente das soluc¸o˜ es pais. Na figura 13 pode-se observar que o med. e o min. ficam praticamente constantes, isto pode significar maiores chances do algor´ıtmo conseguir uma soluc¸a˜ o melhor nas gerac¸o˜ es vindouras, por´em, fica claro uma deficiˆencia de evoluir a populac¸a˜ o a curto prazo. Em conjunto com o m´etodo de substituic¸a˜ o Generational foi apresentado os piores resultados at´e o momento, como pode ser observado na figura 14, onde o algor´ıtmo teve bastante dificuldade de evoluir a populac¸a˜ o, como se praticamente a populac¸a˜ o ficasse parada no tempo.

20

38 Roleta - Duração 705ms 1000 995 990 985 980 975 970 965 0 2 4 Torneio Estocástico - Duração 605ms 1000 995 990 985 980 975 970 0 2 4

Max. Med. Min.

6

8

10

12

14

16

18

20

Max. Med. Min.

6

8

10 Geração

12

14

16

18

20

Figura 13: Cen´ario 1 - O1C Steady State. Fonte: Autoria Pr´opria

Pode-se observar com o m´etodo de selec¸a˜ o torneio a primeira vez, at´e o momento, na qual o algor´ıtmo n˜ao conseguiu solucionar o problema no intervalo proposto. Roleta - Duração 756ms 1000 995 990 985 980 975 970 965 960 955 950 0 2

Max. Med. Min.

4

6

Torneio Estocástico - Duração 728ms 1000 995 990 985 980 975 970 965 960 955 0 2 4

8

10

12

14

16

18

Max. Med. Min.

6

8

10

12

14

16

18

Geração

Figura 14: Cen´ario 1 - O1C Generational. Fonte: Autoria Pr´opria

O tempo m´edio com os m´etodos de selec¸a˜ o roleta e torneio foram respectivamente 730,5 e 666,5 milisegundos. O tempo m´edio dos testes com o m´etodo de cruzamento O1C foi 698,5 milisegundos. 6.1.4

20

PMX Este m´etodo por tamb´em ser permutativo trouxe resultados bastante parecidos com o

O1C. Por´em possu´ı uma leve diferenc¸a em relac¸a˜ o ao O1C, depois que o pai doa uma parte

20

39

do cromossomo, os cromossomos da m˜ae s˜ao acomodados da seguinte forma, o algor´ıtmo identifica uma aula que n˜ao foi herdada no corte do pai, mas que esteja presente na parte correspondente da m˜ae, ent˜ao esta aula da m˜ae ser´a acomodada no filho, por´em para achar o lugar ideal o algor´ıtmo tenta localizar um espac¸o de uma aula da m˜ae que tenha sido herdada pela area do corte do pai, ao encontrar essa aula que j´a foi herdada do pai, o algor´ıtmo troca a aula herdada do pai pela aula que ainda n˜ao foi herdada da m˜ae. Roleta 1000 995 990 985 980 975 970 965 0 2 Torneio Estocástico 1000 995 990 985 980 975 970 0 2

Max. Med. Min.

4

6

8

10

12

14

16

18

20

Max. Med. Min.

4

6

8

10

12

14

16

18

20

Geração

Figura 15: Cen´ario 1 - PMX Steady State. Fonte: Autoria Pr´opria

Roleta 1000 995 990 985 980 975 970 965 960 955 950 0

Max. Med. Min.

2

Torneio Estocástico 1000 995 990 985 980 975 970 965 960 955 950 0 2

4

6

8

10

12

14

16

18

Max. Med. Min.

4

6

8

10 Geração

12

14

16

18

Figura 16: Cen´ario 1 - PMX Generational. Fonte: Autoria Pr´opria

O tempo m´edio com os m´etodos de selec¸a˜ o roleta e torneio foram respectivamente 918,5 e 820 milisegundos. O tempo m´edio dos testes com o m´etodo de cruzamento PMX foi 869,25 milisegundos.

20

20

40

6.2

´ CENARIO 2 Este e´ um cen´ario um pouco mais dificil de ser solucionado, possu´ı 10 s´eries e

bastante professores para que seja poss´ıvel chegar numa soluc¸a˜ o com um esforc¸o consider´avel. Professores: 6x Portuguˆes, 6x Matem´atica, 4x Geografia e Hist´oria, 4x Qu´ımica e Biologia, 1x F´ısica, 1x Educac¸a˜ o F´ısica e 1x Inglˆes. Para os testes a seguir foi usada uma populac¸a˜ o de 600 cromossomos por 50 gerac¸o˜ es. 6.2.1

1P Por ser um cen´ario com bem mais informac¸o˜ es e possibilidades que o anterior, o

esforc¸o fica visivel nos gr´aficos. Roleta - Duração 3895ms 1000 990 980 970 960 950 940 930 920 910 0 5 10 Torneio Estocástic - Duração 3375ms 1000 990 980 970 960 950 940 930 920 910 0 5 10

Max. Med. Min.

15

20

25

30

35

40

45

Max. Med. Min.

15

20

25

30

35

40

45

Geração

Figura 17: Cen´ario 2 - 1P Steady State. Fonte: Autoria Pr´opria

E´ poss´ıvel observar pela figura 17 que a roleta parece demorar um pouco mais que o torneio para deixar a populac¸a˜ o homogˆenea. O tempo m´edio com os m´etodos de selec¸a˜ o roleta e torneio foram respectivamente 4118,5 e 3557 milisegundos. O tempo m´edio destes testes com o m´etodo de cruzamento 1P foi 3837,75 milisegundos 6.2.2

50

2P Apesar da maior quantidade de informac¸a˜ o, ainda assim o software tem iniciado a

populac¸a˜ o com cromossomos com o fitness bem alto, por´em fica claro que e´ necess´ario um

50

41 Roleta - Duração 4342ms 990 980 970 960 950 940 930 920 910 900 890 0 5 10 Torneio Estocástico - Duração 3739ms 1000 990 980 970 960 950 940 930 920 910 900 0 5 10

Max. Med. Min.

15

20

25

30

35

40

45

50

Max. Med. Min.

15

20

25 Geração

30

35

40

45

50

Figura 18: Cen´ario 2 - 1P Generational. Fonte: Autoria Pr´opria Roleta - Duração 3880ms 1000 990 980 970 960 950 940 930 920 910 0 5 10 Torneio Estocástico - Duração 3357ms 1000 990 980 970 960 950 940 930 920 910 0 5 10

Max. Med. Min.

15

20

25

30

35

40

45

Max. Med. Min.

15

20

25 Geração

30

35

40

45

Figura 19: Cen´ario 2 - 2P Steady State. Fonte: Autoria Pr´opria

esforc¸o bem maior para encontrar um cromossomo com um fitness que seja um pouco mais alto que o melhor da populac¸a˜ o. Novamente e´ poss´ıvel observar pela figura 19 a roleta demorando um pouco mais que o torneio para deixar a populac¸a˜ o homogˆenea. O tempo m´edio com os m´etodos de selec¸a˜ o roleta e torneio foram respectivamente 3732 e 3343 milisegundos. O tempo m´edio destes testes com o m´etodo de cruzamento 2P foi 3537,5 milisegundos Os m´etodos de cruzamento simples mostram um bom desempenho no ciclo de vida do algor´ıtmo.

50

50

42 Roleta - Duração 3584ms 1000 980 960 940 920 900 880 0 5 10 Torneio Estocástico - Duração 3329ms 1000 990 980 970 960 950 940 930 920 910 900 0 5 10

Max. Med. Min.

15

20

25

30

35

40

45

50

Max. Med. Min.

15

20

25 Geração

30

35

40

45

50

Figura 20: Cen´ario 2 -2P Generational. Fonte: Autoria Pr´opria

Dos 8 testes com m´etodos de cruzamento simples apenas 1 n˜ao conseguiu chegar numa soluc¸a˜ o perfeita. 6.2.3

O1C A seguir os testes finais com m´etodos de cruzamento permutativos.

Roleta - Duração 4715ms 990 980 970 960 950 940 930 920 910 0 5 10 Torneio Estocástico - Duração 4631ms 990 980 970 960 950 940 930 920 910 0 5 10

Max. Med. Min.

15

20

25

30

35

40

45

Max. Med. Min.

15

20

25

30

35

40

45

Geração

Figura 21: Cen´ario 2 - O1c Steady State. Fonte: Autoria Pr´opria

Como pode ser observado, tanto na figura 21 quanto na figura 22 mostram, este m´etodo O1C age assim, quanto maior a dificuldade do teste pior e´ o resultado. Isso e´ conta da reorganizac¸a˜ o que o O1C tem feito na nova populac¸a˜ o, este tipo de ac¸a˜ o acaba praticamente gerando uma nova soluc¸a˜ o alet´oria com pouqu´ıssima informac¸a˜ o semelhante a` informac¸a˜ o dos pais.

50

50

43 Roleta - Duração 4539ms 980 970 960 950 940 930 920 910 900 890 0 5 10 Torneio Estocástico - Duração 4958ms 990 980 970 960 950 940 930 920 910 900 890 0 5 10

Max. Med. Min.

15

20

25

30

35

40

45

50

Max. Med. Min.

15

20

25 Geração

30

35

40

45

50

Figura 22: Cen´ario 2 - O1C Generational. Fonte: Autoria Pr´opria

O tempo m´edio com os m´etodos de selec¸a˜ o roleta e torneio foram respectivamente 4627 e 4794,5 milisegundos. O tempo m´edio destes testes com o m´etodo de cruzamento O1C foi 4710,75 milisegundos. Se o resultado obtido somado com o tempo de obtenc¸a˜ o e´ comparado com os outros m´etodos fica visivel a incompatibilidade deste m´etodo com o problema. 6.2.4

PMX

Roleta - Duração 5378ms 990 980 970 960 950 940 930 920 910 0 5 10 Torneio Estocástico - Duração 5069ms 990 980 970 960 950 940 930 920 910 0 5 10

Max. Med. Min.

15

20

25

30

35

40

45

50

Max. Med. Min.

15

20

25

30

35

40

45

Geração

Figura 23: Cen´ario 2 - PMX Steady State. Fonte: Autoria Pr´opria

Apesar do PMX tamb´em ser permutativo, porem um pouco diferente do O1C que praticamente embaralha toda a soluc¸a˜ o, o PMX apenas troca os genes herdados do pai pelos da m˜ae assim tamb´em mantendo a regra da grade curricular, contudo esta vis´ıvel que ainda assim

50

44 Roleta - Duração 5843ms 990 980 970 960 950 940 930 920 910 900 890 0 5 10 Torneio Estocástico - Duração 5623ms 990 980 970 960 950 940 930 920 910 900 890 0 5 10

Max. Med. Min.

15

20

25

30

35

40

45

Max. Med. Min.

15

20

25 Geração

30

35

40

45

Figura 24: Cen´ario 2 - PMX Generational. Fonte: Autoria Pr´opria

n˜ao faz do PMX um m´etodo compat´ıvel com o problema, pois os resultados obtidos foram muito parecidos com os do O1C. O tempo m´edio com os m´etodos de selec¸a˜ o roleta e torneio foram respectivamente 5610,5 e 5346 milisegundos. O tempo m´edio destes testes com o m´etodo de cruzamento PMX foi 5478,25 milisegundos 6.3

50

˜ CONSIDERAC¸OES FINAIS A seguir quadros mostrando os resultados em relac¸a˜ o ao tempo de execuc¸a˜ o do

cen´arios e seus testes: Tabela 3: Resultados de Tempo em milisegundos Cen´ario 1

M´etodos Selec¸a˜ o e Substituic¸a˜ o Roleta e Steady State Torneio e Steady State Roleta e Generational Torneio e Generational Total M´edia

1P 2P 454 539 466 416 510 515 512 438 1942 1908 485,5 477

O1C 705 605 756 728 2794 698,5

PMX 888 807 949 833 3477 869,25

Fonte: Autoria pr´opria.

Com a tabela 3 mostrando o tempo de execuc¸a˜ o de cada teste fica claro que os m´etodos de cruzamento simples s˜ao bem mais a´ geis que os m´etodos de cruzamento permutativos. Novamente fica comprovado pela tabela 4 a agilidade dos m´etodos de cruzamento simples, enquanto os m´etodos permutativos demonstram que quanto maior o problema maior

50

45

Tabela 4: Resultados de Tempo em milisegundos Cen´ario 2

M´etodos Selec¸a˜ o e Substituic¸a˜ o Roleta e Steady State Torneio e Steady State Roleta e Generational Torneio e Generational Total M´edia

1P 3895 3375 4342 3739 15351 3837,75

2P 3880 3357 3584 3329 14150 3537,5

O1C 4715 4631 4539 4958 18843 4710,75

PMX 5378 5069 5843 5623 21913 5478,25

Fonte: Autoria pr´opria.

ser´a o tempo de processamento que o tempo dos m´etodos simples. Nas tabelas 5 e 6 e´ apresentada a gerac¸a˜ o que o algor´ıtmo encontrou a primeira soluc¸a˜ o perfeita para cada teste. Nos testes onde n˜ao foi poss´ıvel chegar na soluc¸a˜ o perfeita foi atribu´ıdo o valor m´aximo da gerac¸a˜ o para que hajam valores. Tabela 5: Resultados de fitness Cen´ario 1

M´etodos Selec¸a˜ o e Substituic¸a˜ o Roleta e Steady State Torneio e Steady State Roleta e Generational Torneio e Generational Total M´edia

1P 3 2 1 4 10 2,5

2P O1C 2 7 2 4 2 1 1 20* 7 32 1,75 8

PMX 5 1 16 0 22 5,5

Fonte: Autoria pr´opria.

Tabela 6: Resultados de fitness Cen´ario 2

M´etodos Selec¸a˜ o e Substituic¸a˜ o Roleta e Steady State Torneio e Steady State Roleta e Generational Torneio e Generational Total M´edia

1P 39 13 8 50* 110 27,5

2P O1C 7 50* 8 50* 15 36 11 50* 41 186 10,25 46,5

PMX 50* 50* 50* 50* 200 50

Fonte: Autoria pr´opria.

Como pode ser observado pelas tabelas 5 e 6 os m´etodos de cruzamento simples s˜ao bem mais adequados ao problema proposto, pois conseguiram dentro dos limites estabelecidos em ambos cen´arios evoluir a populac¸a˜ o, em quase todos os testes, a` perfeic¸a˜ o, somente em um dos testes e que provavelmente foi ao acaso, n˜ao foi poss´ıvel chegar na soluc¸a˜ o perfeita. Por outro lado os m´etodos de cruzamentos permutativos demonstraram consumir processamento

46

sem retorno, ou seja, s˜ao m´etodos que demoraram mais para tentar evoluir a populac¸a˜ o sem sucesso, pois a populac¸a˜ o ficou praticamente estagnada e sem evoluc¸a˜ o em certos momentos como pode ser observado nos gr´aficos destes m´etodos.

47

7

˜ CONCLUSAO

Este trabalho apresentou uma implementac¸a˜ o do algor´ıtmo gen´etico para a soluc¸a˜ o do problema de criac¸a˜ o dos quadros de hor´arios de uma escola. Com a implementac¸a˜ o do algor´ıtmo gen´etico apareceram v´arias opc¸o˜ es de configurac¸o˜ es, tais como: m´etodos de selec¸a˜ o, m´etodos de cruzamento, m´etodos de substituic¸a˜ o, porcentagem de mutac¸a˜ o, elitismo, quantidade do elitismo, entre outras. Com os m´etodos de cruzamento simples, 1P e 2P, o algor´ıtmo desenvolvido conseguiu solucionar facilmente os cen´arios propostos, por´em isso n˜ao aconteceu somente grac¸as aos m´etodos de cruzamento, as outras configurac¸o˜ es foram importantes para que o algor´ıtmo conseguisse evoluir a populac¸a˜ o a` perfeic¸a˜ o. Entre os m´etodos de selec¸a˜ o n˜ao ficou claro, e talvez n˜ao seja poss´ıvel eleger o melhor, pois os dois agem de modo semelhante selecionando individuos de modo aleat´orio, a sutil diferenc¸a e´ que a roleta assim como o torneio tenta prevalecer os melhores indiv´ıduos, por´em ainda d´a chance ao pior da populac¸a˜ o, por outro lado o torneio nunca selecionar´a o pior da populac¸a˜ o e quanto maior o torneio, menor ser´a as chances dos piores indiv´ıduos da populac¸a˜ o serem selecionados. Entre os m´etodos de substituic¸a˜ o tamb´em n˜ao e´ poss´ıvel eleger o melhor, pois os dois agem de forma parecida, apesar de serem abordagens opostas. Enquanto o m´etodo Steady State configura a parcela da populac¸a˜ o que sa´ı (neste trabalho foi definido 1/3 da populac¸a˜ o), o m´etodo Generational configura a parcela da populac¸a˜ o que permanece com o elistimo, se n˜ao houver elitismo, ent˜ao toda a populac¸a˜ o seria descartada dificultando demais o processo evolutivo. De qualquer forma, foi observado que uma parcela muito pequena, assim como configurada no elitismo de apenas um cromossomo avanc¸ar para a pr´oxima populac¸a˜ o, tem uma tendˆencia a retardar a evoluc¸a˜ o, por´em o mesmo ocorre se o elitismo for alto demais. Independente do m´etodo de substituic¸a˜ o, para este problema, o ideal e´ trocar em torno da metade a 1/5 da populac¸a˜ o pelos melhores da nova populac¸a˜ o. A mutac¸a˜ o foi um processo muito importante para a evoluc¸a˜ o da populac¸a˜ o, apesar

48

de ter sido configurado para ocorrer em apenas 20% dos cromossomos da nova populac¸a˜ o, numa populac¸a˜ o de 500 isso j´a significa 100 cromossomos mutantes. O foco da mutac¸a˜ o e´ tentar corrigir problemas de forma aleat´oria, ou seja, quando um cromossomo apresentava aulas com professores duplicados, a mutac¸a˜ o identificava essas aulas e trocava elas aleat´oriamente de posic¸a˜ o na tentativa de eliminar a duplicac¸a˜ o de professor. Uma taxa de mutac¸a˜ o alta demais tende a retardar o processo evolutivo, assim como uma taxa baixa demais, pois com a taxa alta demais ocorrem mutac¸o˜ es a todo momento que acabam duplicando, na mesma proporc¸a˜ o que dividindo, as aulas com professores duplicados.

49

ˆ REFERENCIAS

BEASLEY, D.; BULL, D. R.; MARTIN, R. R. An orverview of genetic algorithms: Part 1, fundamentals. Inter-University Committee on Computing: University Computing, 1993. CHARNIAK, E.; MCDERMOTT, D. Introduction to Artificial Intelligence. Boston, MA: Addison-Wesley Longman Publishing Co., Inc., 1985. DARWIN, C. A Origem das Esp´ecies. Inglaterra: Martin Claret, 1859. GIL, A. C. Como elaborar Projetos de Pesquisa. S˜ao Paulo: Atlas, 2002. HAUGELAND, J. Artificial Intelligence - The Very Idea. London, England: A Bradford Book, 1989. HOFFMANN, J. R. GENIUS – Um escalonamento baseado em algoritmos gen´eticos para comutadores de alto desempenho. Curitiba: Biblioteca Central da UTFPR, 2013. HORSTMANN, C. S.; CORNELL, G. Core java, Volume I - Fundamentals. Inter-University Committee on Computing: Prentice Hall, 1993. KURZWEIL, R. The Age of Intelligent Machines. USA: MIT Press, 1990. LARGET, H. Genetic Algorithms used in Timetable Management. Conventry University: Conventry University, 2012. RUSSEL, S. J.; NORVIG, P. Artificial Intelligence: A modern approach. Edinburgh Gate: Pearson, 2004. STARKWEATHER, T. et al. A Comparison of Genetic Sequencing Operators. Fot Collins: Colorado State University, 2011. WHITLEY, D. A Genetic Algorithm Tutorial. Fort Collins: Colorado State University, 1994. WINSTON, P. H. Artificial Intelligence. Massachusetts Institute of technology: Pearson, 1992.