
MÉTODOS METAHEURÍSTICOS APLICADOS A UM MODELO DE

PLANEJAMENTO DE CULTURAS

Ćıntia Pimentel de Oliveira

Dissertação apresentada à Universidade

Estadual Paulista “Júlio de Mesquita Filho”

para obtenção do t́ıtulo de Mestre em

Biometria.

BOTUCATU

São Paulo - Brasil

Março - 2013


MÉTODOS METAHEURÍSTICOS APLICADOS A UM MODELO DE

PLANEJAMENTO DE CULTURAS

Ćıntia Pimentel de Oliveira

Orientadora: Profa. Dra. Helenice de Oliveira Florentino Silva

Dissertação apresentada à Universidade

Estadual Paulista “Júlio de Mesquita Filho”

para obtenção do t́ıtulo de Mestre em

Biometria.

BOTUCATU

São Paulo - Brasil

Março - 2013


Agradecimentos

Não há palavras para descrever o sentimento de gratidão pelo apren-

dizado e experiências que a universidade tem me proporcionado nos últimos anos.

Descobri que os desafios vêm e vão, e diante deles sempre temos algo

melhor para buscar e dar de nós mesmos. Enfrentá-los só se torna uma tarefa posśıvel

com fé em Deus e ajuda de cada pessoa que passa por nossas vidas, contribuindo de

alguma forma para que vençamos mais uma etapa.

Agradeço aos meus pais, João e Inês, por serem meus melhores amigos,

e pelo apoio e amor incondicional dado em todos os momentos da minha vida.

Aos amigos da pós-graduação, pessoas inesquećıveis com quem dividi

grande parte do tempo, conhecimento, alegrias e angústias. De modo especial,

agradeço aos amigos Ronaldo, Thiago, Farid, Ĺıvia e Bettina. A vocês desejo muito

sucesso.

A minha querida orientadora, Profª. Helenice, pela paciência, simpa-

tia, competência, incentivos, conselhos e amizade, caracteŕısticas estas indispensáveis

para a realização de uma boa orientação e de um trabalho com satisfação.

A todos os professores que ensinaram, aconselharam e compartilharam

suas experiências, em especial, o Prof. Carlos Roberto Padovani, que, para mim, é

mais que um professor, é um amigo, um exemplo, um educador.

Ao Programa de Pós-Graduação em Biometria do Instituto de

Biociência de Botucatu (IBB) por possibilitar o desenvolvimento deste trabalho.

À Coordenação de Aperfeiçoamento de Pessoal de Nı́vel Superior

(CAPES) pelo apoio financeiro concedido.


Sumário

Página

LISTA DE FIGURAS vi

LISTA DE TABELAS ix

RESUMO xi

SUMMARY xiii

1 INTRODUÇÃO 1

2 REVISÃO DE LITERATURA 3

2.1 Modelagem Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Otimização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2.2.1 Formulação geral de um problema de Otimização . . . . . . . . . . . . 7

2.2.2 Otimização global e local . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.3 Otimização Combinatória . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.3 Exato versus Heuŕıstico . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 Estratégias Heuŕısticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.4.1 Metaheuŕısticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.5 Algoritmo Genético (AG) . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5.1 Representação de um cromossomo . . . . . . . . . . . . . . . . . . . . 18

2.5.2 População . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.5.3 Aptidão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.5.4 Penalização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24


iv

2.5.5 Elitismo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.5.6 Seleção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.5.6.1 Proporcional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.5.6.2 Torneio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.5.6.3 Classificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

2.5.6.4 Truncada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.5.7 Operadores Genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.5.7.1 Crossover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.5.7.2 Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

2.5.7.3 Epidemia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.5.8 Parâmetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.5.9 Critério de parada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.6 Simulated Annealing (SA) . . . . . . . . . . . . . . . . . . . . . . . . . . 42

2.7 Algoritmos Hı́bridos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3 MATERIAL E MÉTODOS 48

3.1 Modelagem Matemática do Problema Biológico . . . . . . . . . . . . . . 48

3.2 Heuŕıstica Construtiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.3 Penalização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.4 Algoritmo Genético . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.5 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.6 Hı́brido AG+SA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.7 Instâncias simuladas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.8 Algoritmos testados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

4 RESULTADOS E DISCUSSÕES 66

5 CONCLUSÕES 81

REFERÊNCIAS BIBLIOGRÁFICAS 83


v

APÊNDICE 87


Lista de Figuras

Página

1 Espaço de busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Fluxograma do processo de busca do AG em uma abordagem geral . . . 18

3 Itens que compõem o problema do agricultor . . . . . . . . . . . . . . . . 19

4 Cromossomo com representação binária . . . . . . . . . . . . . . . . . . . 20

5 Cromossomo com representação inteira . . . . . . . . . . . . . . . . . . . 20

6 População inicial gerada aleatoriamente para o problema do agricultor . 21

7 Representação esquemática da população inicial e população intermediária 22

8 Fluxograma do Algoritmo Genético com elitismo . . . . . . . . . . . . . 26

9 Roleta com aptidão normalizada para a população inicial gerada no pro-

blema do agricultor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

10 Ponteiros constrúıdos pelo método de Amostragem Estocástica Uniforme

para o problema do agricultor . . . . . . . . . . . . . . . . . . . . . . . . 31

11 Posições de corte posśıveis no cromossomo com representação inteira . . 36

12 Troca de genes entre cromossomos pais realizados a partir do ponto de

corte selecionado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

13 Troca de genes entre cromossomos pais realizados com crossover 2-pontos 37

14 Troca de genes entre cromossomos pais realizados com crossover uniforme 38

15 Mutação aleatória em cromossomo com representação binária . . . . . . 40

16 Probabilidade de aceitação de movimentos que não são de melhora pelo

algoritmo SA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

17 Pseudocódigo do algoritmo Simulated Annealing . . . . . . . . . . . . . . 46


vii

18 Área hipotética dividida em lotes para planejamento de plantio . . . . . 50

19 Representação em grafo da região ilustrada na Figura (18) . . . . . . . . 50

20 Matriz de relacionamento de vizinhança entre lotes . . . . . . . . . . . . 52

21 Matriz de probabilidade de proliferação de praga entre culturas . . . . . 52

22 Comportamento da função de penalização exponencial com k = 100. . . . 56

23 Exemplo de matriz solução para o problema abordado . . . . . . . . . . 57

24 Comportamento da função loǵıstica de probabilidade de mutação . . . . 58

25 Posśıvel vizinho da solução corrente S apresentada na Figura (23) . . . . 59

26 Geometria e dimensão das áreas consideradas nas simulações . . . . . . . 61

27 Boxplot com resultados de homogeneidade e desempenho dos algoritmos

testados na instância A para valores da função objetivo . . . . . . . . . . 72

28 Boxplot com resultados de homogeneidade e desempenho dos algoritmos

testados na instância A para o tempo computacional . . . . . . . . . . . 73

29 Boxplot com resultados de homogeneidade e desempenho dos algoritmos

testados na instância B para valores da função objetivo . . . . . . . . . . 74

30 Boxplot com resultados de homogeneidade e desempenho dos algoritmos

testados na instância B para o tempo computacional . . . . . . . . . . . 75

31 Melhor configuração de plantio apresentada pelo algoritmo AG Torneio A 76

32 Melhor configuração de plantio apresentada pelo algoritmo AG Roleta A 76

33 Melhor configuração de plantio apresentada pelo algoritmo SA 10−4 A . . 77

34 Melhor configuração de plantio apresentada pelo algoritmo

AG+SA Torneio A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

35 Melhor configuração de plantio apresentada pelo algoritmo

AG+SA Roleta A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

36 Melhor configuração de plantio apresentada pelo algoritmo AG Torneio B 77

37 Melhor configuração de plantio apresentada pelo algoritmo AG Roleta B 78

38 Melhor configuração de plantio apresentada pelo algoritmo SA 10−4 B . 78

39 Melhor configuração de plantio apresentada pelo algoritmo SA 10−6 B . 78


viii

40 Melhor configuração de plantio apresentada pelo algoritmo

AG+SA Roleta B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

41 Curva de melhora realizada pelo SA iniciado com a melhor solução fact́ıvel

do AG com seleção por Torneio Binário para a instância A . . . . . . . . 79

42 Curva de melhora realizada pelo SA iniciado com a melhor solução fact́ıvel

do AG com seleção por Roleta Viciada para a instância A . . . . . . . . 80

43 Curva de melhora realizada pelo SA iniciado com a melhor solução fact́ıvel

do AG com seleção por Roleta Viciada para a instância B . . . . . . . . 80


Lista de Tabelas

Página

1 Aptidão das soluções geradas para o problema do agricultor . . . . . . . 23

2 Valores de aptidão normalizada e acumulada para os indiv́ıduos gerados

no problema do agricultor . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3 Vocabulários utilizados no processo de recozimento f́ısico e simulado . . . 43

4 Parâmetros utilizados no Simulated Annealing . . . . . . . . . . . . . . . 60

5 Áreas dos lotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

6 Valor da função objetivo e tempo computacional (em segundos) médios

para os algoritmos testados na instância A . . . . . . . . . . . . . . . . . 66

7 Valor da função objetivo e tempo computacional (em segundos) médios

para os algoritmos testados na instância B . . . . . . . . . . . . . . . . . 67

8 Número de soluções fact́ıveis encontradas pelos algoritmos testados na

instância B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

9 Homogeneidade e desempenho dos algoritmos obtidos para a instância A

com relação ao valor da função objetivo . . . . . . . . . . . . . . . . . . 69

10 Homogeneidade e desempenho dos algoritmos obtidos para a instância B

com relação ao valor da função objetivo . . . . . . . . . . . . . . . . . . 69

11 Homogeneidade e desempenho dos algoritmos obtidos para a instância A

com relação ao tempo computacional . . . . . . . . . . . . . . . . . . . . 71

12 Homogeneidade e desempenho dos algoritmos obtidos para a instância B

com relação ao tempo computacional . . . . . . . . . . . . . . . . . . . . 71

13 Informações sobre culturas: nome, famı́lia, época de plantio e duração do

ciclo de vida, adaptado de Santos (2009) . . . . . . . . . . . . . . . . . . 88


x

14 Produtividade mensal porm2 das culturas, adaptado de Aliano Filho (2012) 89

15 Demanda e peŕıodos de demanda das culturas, adaptado de Aliano Filho

(2012) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90


MÉTODOS METAHEURÍSTICOS APLICADOS A UM MODELO DE

PLANEJAMENTO DE CULTURAS

Autora: CÍNTIA PIMENTEL DE OLIVEIRA

Orientadora: Profa. Dra. HELENICE DE OLIVEIRA FLORENTINO SILVA

RESUMO

No contexto atual de sustentabilidade, formas alternativas à utilização

de produtos que podem levar o planeta a uma crise ambiental estão sendo fortemente

estudadas. Na agricultura, uma preocupação brasileira é com a redução do consumo

de agrotóxicos, já que o páıs é um dos maiores consumidores mundiais do produto.

Neste sentido, o planejamento das atividades agŕıcolas é uma ação

preventiva que pode colaborar com a redução da proliferação de pragas entre as

culturas plantadas em lotes e, consequentemente, a redução no consumo de produtos

qúımicos. Ele visa determinar a melhor forma de ocupação de áreas de plantio de

modo que a disposição das culturas e/ou variedades em talhões favoreça o controle

eficiente de pragas.

Neste trabalho é proposto um modelo de otimização 0-1 para minimizar

a probabilidade de proliferação de pragas entre as culturas plantadas, respeitando


xii

restrições de demanda, ocupação de lotes, peŕıodo de cultivo das culturas e tempo

de planejamento. Nesta modelagem, considera-se uma área de plantio genérica, com

lotes irregulares e culturas já plantadas em fazendas vizinhas.

Para resolução do modelo foram utilizadas as estratégias Meta-

heuŕısticas Algoritmo Genético (AG), Simulated Annealing (SA) e a abordagem

h́ıbrida Algoritmo Genético com Simulated Annealing (AG+SA) para obtenção de

boas estimativas para o planejamento otimizado das atividades agŕıcolas.

Aplicações práticas a duas instâncias distintas foram realizadas e as

melhores soluções fact́ıveis encontradas pelos algoritmos são apresentadas, bem como

comparação e discussão dos resultados e desempenho computacional dos métodos.

Os resultados computacionais indicam que os algoritmos meta-

heuŕısticos propostos encontraram soluções fact́ıveis de boa qualidade em um tempo

computacional reduzido, e em especial, as estratégias h́ıbridas demonstraram ser

excelentes ferramentas para aux́ılio no planejamento de plantio.


METAHEURISTIC METHODS APPLIED TO A PLANNING

CULTURES MODEL

Author: CÍNTIA PIMENTEL DE OLIVEIRA

Adviser: Profa. Dra. HELENICE DE OLIVEIRA FLORENTINO SILVA

SUMMARY

In the sustainability context we are living nowadays, alternative forms

to the utilization of products that can lead the Earth to an environmental crisis have

been strongly studied. In agriculture, the Brazilian concern is about the reduction

of pesticide consumption, once the country is one of the world’s major consumers of

it.

In this sense, the planning of the agricultural activity is a preventive

action that can contribute to reduce the proliferation of pests among crops planted in

lots and, consequently, decrease the excessive consumption of such chemicals. This

approach aims to determine the best way to use the planting areas arranging the

crops and/or varieties in support to an efficient pests control.

The research’s objective is to propose an optimization model 0-1 in

order to minimize the likelihood of pests proliferation among planted crops, consid-

ering constraints demand, lots occupation, crops growing period and planning time.


xiv

In this model, it is considered a generic planting area with irregular lots and already

planted crops in neighboring farms.

In the model’s solutions, Genetic Algorithm and Simulated Annealing

Metaheuristics strategies were used, as well as a Genetic Algorithm jointly with

Simulated Annealing hybrid approach in order to obtain good estimates for the

optimized planning of agricultural activities.

A practical application for the two instances was performed and the

best feasible solutions found by the algorithms are presented as well as a comparison

and discussion of the results and performance of computational methods.

The computational results indicate that the metaheuristic algorithms

found feasible solutions with good quality in a reduced computational time, and in

particular, the proposed hybrid strategies have proven to be excellent tools to help

planning the planting.


1 INTRODUÇÃO

Com terras férteis, extensas e clima proṕıcio para a agricultura, o

Brasil é um dos principais produtores e fornecedores mundiais de alimentos. Grande

produção agŕıcola em atividade torna o páıs o cenário favorável ao surgimento das

pragas. Pragas são organismos que causam danos econômicos ao agricultor, e o meio

mais utilizado pelo homem em seu combate são os agrotóxicos (Martins Jr., 2002).

Os agrotóxicos tornaram-se uma preocupação brasileira devido ao seu

uso indiscriminado em lavouras. Em 2010 foram consumidos no Brasil cerca de 790

mil toneladas de agrotóxicos, conforme pesquisa publicada no boletim Em Questão

(edição 1460, de 31 de janeiro de 2012) da Secretaria de Comunicação da Presidência

da República, o que coloca o páıs entre os maiores consumidores de agrotóxicos do

mundo.

O controle de pragas com agrotóxicos tem se tornado cada vez mais ine-

ficiente devido à resistência que as pragas adquirem com o tempo, exigindo dosagens

cada vez mais elevadas e aplicações mais frequentes, onerando o custo de produção,

aumentando os riscos de contaminação do meio ambiente e prejudicando a saúde

humana e animal (Martins Jr., 2002).

Atualmente, a principal alternativa à utilização de agrotóxicos é o con-

trole biológico, que tem se mostrado eficiente no combate as pragas das principais

culturas produzidas no Brasil. Estudos realizados por Parra et al. (2002) e Venzon

et al. (2008) utilizando controle biológico demonstram casos de sucesso e o potencial

de redução na intensidade de infestação em culturas como citrus, cana-de açúcar,

milho, sorgo, tomate, entre outros. Contudo, tanto o controle biológico quanto o

qúımico, em geral, são ações não preventivas de combate às pragas, ou seja, são


2

utilizados quando existem focos de pragas ou estas já estão instaladas na lavoura.

Neste cenário, técnicas preventivas e alternativas sustentáveis de com-

bate às pragas têm sido desenvolvidas, e dentre elas destaca-se o planejamento das

atividades de plantio em sistemas agŕıcolas. A ação de planejar visa fornecer ao

agricultor, diante de certas limitações de recursos, a melhor forma de ocupação de

suas terras com as culturas, com objetivos espećıficos, como por exemplo, aumentar

o lucro ou diminuir os custos.

Assim, neste trabalho é proposto um modelo matemático para auxiliar

o planejamento de culturas em sistemas agŕıcolas, cujo objetivo é investigar, através

de estratégias metaheuŕısticas de otimização, a melhor forma de ocupação de uma

área dispońıvel para plantio, subdividida em lotes, de modo que a disposição dessas

culturas e/ou variedades em talhões favoreça o controle eficiente de pragas.

Aplicações práticas foram realizadas e as melhores soluções fact́ıveis

encontradas pelos algoritmos estudados são apresentadas, bem como a comparação

e discussão dos resultados e desempenho computacional dos métodos.

A ação de planejar as atividades agŕıcolas pode contribuir para a mini-

mização da proliferação de pragas entre as culturas e apresenta ganhos sociais,

econômicos e ambientais, tais como, atender a demanda social de produtos livres

de agrotóxicos, reduzir gastos do agricultor com produtos de combate às pragas,

reduzir os riscos de contaminação ambiental com produtos qúımicos, entre outros.


2 REVISÃO DE LITERATURA

2.1 Modelagem Matemática

Nos últimos anos o Brasil tem ocupado posição de destaque no cenário

mundial de produção e exportação de alimentos, e para atender tamanha demanda,

grandes investimentos econômicos, tecnológicos e loǵısticos têm sido realizados.

Com este avanço, os problemas nas agroindústrias se tornaram bastante complexos,

fazendo com que os gestores lancem mão de todas as ferramentas posśıveis de apoio,

como exemplo, as computacionais e matemáticas. Assim, destacam-se as importantes

contribuições da modelagem matemática para as pesquisas nesta área.

Por sua caracteŕıstica interdisciplinar, a modelagem matemática tem

contribúıdo de forma significativa para a expansão das atividades agŕıcolas no páıs e

para a redução dos problemas econômicos e ambientais decorrentes deste crescimento.

Para Biembengut & Hein (2000), a modelagem matemática constitui

um ramo próprio da Matemática que tenta traduzir situações reais para uma lin-

guagem matemática, para que por meio dela se possa melhor compreender, prever e

simular ou, ainda, mudar determinadas vias de acontecimentos, com estratégias de

ação, nas mais variadas áreas do conhecimento.

Bassanezi (2002) define modelagem matemática como a arte de trans-

formar problemas da realidade em problemas matemáticos e resolvê-los interpretando

suas soluções na linguagem do mundo real.

Numa perspectiva agŕıcola, a modelagem matemática visa transformar

um problema econômico ou biológico real em objeto de estudo, possibilitando a

previsão do comportamento do sistema de produção e a compreensão da relação e


4

influência entre os seus diversos componentes.

Contudo, trabalhar com modelagem matemática não é uma tarefa sim-

ples. Em geral, é preciso sair de uma área dominada para uma área em que os outros

dominam e, para isso, é necessário bases e fundamentos.

Construir um modelo matemático, segundo Biembengut & Hein

(2000), significa determinar um conjunto de śımbolos e relações matemáticas que

traduz, de alguma forma, o fenômeno em questão ou problema de situação real.

Contudo, é importante ressaltar que a realidade é tão complexa que modelos mais

rebuscados e que incorporam grande parte das variáveis reais podem se tornar dif́ıceis

de resolver, enquanto um modelo muito simples pode não representar bem o pro-

blema real.

Portanto, o que se observa na maioria das vezes, é a proposta de um

modelo simples que permite explorar bons aspectos do fenômeno observado e a partir

dáı, incoporar mais variáveis e equações, a fim de aprimorar o modelo.

Existem vários trabalhos na literatura que foram desenvolvidos uti-

lizando modelagem matemática com foco em planejamento de produção, em especial

em produção agŕıcola. Em geral, estes trabalhos buscam otimizar áreas de produção,

aproveitamento de matérias-primas, reduzir custos, aumentar lucro, reduzir produção

de reśıduos, entre outros.

Kantorovich (1960) foi pioneiro em propor modelos matemáticos para

melhorias na organização e planejamento de produção. Em seu trabalho, o autor

propõe modelos para determinar desde a distribuição ideal de terras cultiváveis,

do trabalho de máquinas e mecanismos, até modelos para redução da produção de

reśıduos obtidos em cortes de matérias-primas pela indústria.

Desde então, o interesse por pesquisas de melhorias na área agŕıcola

tem crescido, e modelos matemáticos têm sido utilizados para determinar, segundo

Bernardon & Calgaro (2007), a alocação ótima de culturas em área de plantio, pro-

dutividade de culturas e de riscos de produção em sistemas de cultivo, crescimento de

colheitas individuais ou a gerência de sistema de cultivos, a melhoria dos genótipos


5

e dos cultivares, o manejo da água de irrigação e a avaliação de risco da colheita e a

segurança do alimento.

Com o objetivo de planejar o plantio de culturas em sistemas agŕıcolas,

destacam-se trabalhos recentes com elaboração de modelos para a programação de

rotação de culturas.

Fey et al. (2000) utilizaram um modelo de programação linear com

restrições de terra, rotação de culturas, financeiras e de maquinaria, para planejar

o plantio de culturas em uma propriedade agŕıcola real, visando aumentar a sua

lucratividade.

Santos et al. (2007) propuseram um modelo de programação linear

para a programação de rotação de culturas em uma área de plantio, cujo objetivo

era maximizar a ocupação das áreas de plantio sujeito a restrições de vizinhança,

sucessão para culturas de mesma famı́lia botânica, adubação verde e pousio.

Santos (2009) e Aliano Filho (2012) propuseram um modelo de pro-

gramação linear para maximizar o lucro da rotação de culturas, sendo o último com

acréscimo de restrições de demanda, e utilizaram estratégias metaheuŕısticas para

resolução dos modelos. Também Gomes & Arenales (2010) extenderam as ideias de

Santos (2009) para problemas com restrições de áreas mı́nimas para lotes e redução

do número total de lotes usados.

Como visto, existe um amplo uso de modelos matemáticos na repre-

sentação, análise e obtenção de estimativas de parâmetros para problemas reais na

agricultura. O crescimento do número de pesquisas nesta área é consequência da

importância que a agricultura tem representado para a economia brasileira, especial-

mente no que tange à redução de problemas ambientais.

Nas seções seguintes serão abordadas as técnicas necessárias para a

re-solução do modelo objeto deste trabalho.


6

2.2 Otimização

A palavra “ótimo” vem do Latim optimus e significa “o melhor”.

Otimizar refere-se, portanto, à tentativa de trazer o que estamos lidando em direção

ao seu estado final, isto é, para o seu melhor (Andréasson et al., 2005).

Segundo Beightler, Phillips e Wilde, citado por Goldberg (1989), a

teoria da otimização estuda como descrever e alcançar o que é melhor, uma vez

que se sabe como medir e modificar o que é bom ou ruim. Ela abrange o estudo

quantitativo do ótimo e métodos para encontrá-lo.

A Otimização é, portanto, uma área de conhecimento dentro da

Matemática que fornece as ferramentas apropriadas para que melhorias desejadas

em um determinado processo sejam alcançadas. E ainda, as técnicas de otimização

visam, segundo Brandão & Saramago (2011), determinar a melhor solução para um

problema sem ter que testar todas as possibilidades envolvidas.

Problemas de otimização podem ser encontrados nas mais diversas

áreas das ciências exatas, biológicas e tecnológicas, e sua utilização está fundamen-

tada na capacidade de auxiliar a tomada de decisões de forma eficiente.

Inicia-se o processo de modelagem identificando as variáveis do pro-

blema. Isso significa reconhecer no problema quais são as principais variáveis en-

volvidas no processo a ser otimizado, chamadas de variáveis de decisão. Em seguida,

define-se o objetivo do problema, que pode ser de minimização ou maximização de

uma função das variáveis de decisão, chamado de função objetivo. As variáveis de

decisão muitas vezes devem obedecer à condições limitantes inerentes ao problema,

que são chamadas de restrições. As equações que descrevem as restrições podem ser

de igualdade ou desigualdade. A solução a ser encontrada pertence a um conjunto

viável, denominado espaço fact́ıvel. A Figura (1) apresenta a idéia de espaço de

busca por soluções fact́ıveis.

O procedimento descrito acima, de identificação do objetivo, variáveis

e restrições de um dado problema é chamado de modelagem (Wright & Nocedal,

1999).


7

Figura 1 - Espaço de busca

2.2.1 Formulação geral de um problema de Otimização

Em geral, um problema de otimização é escrito como:

Minimizar f(x)

Sujeito a: hi(x) = 0, i ∈ I

gj(x) ≤ 0, j ∈ J

x ∈ D.

Nesta formulação, x é um vetor n-dimensional das variáveis xi, x =

(x1, x2, . . . , xn), e f(x), hi(x) e gj(x) são funções reais das variáveis xi. I e J

representam os conjuntos de ı́ndices das restrições de igualdade e desigualdade,

I = 1, 2, . . . ,m e J = 1, 2, . . . , n. O conjunto D é um subconjunto do espaço n-

dimensional, D ⊂ Rn. A função f é a função objetivo do problema, definida em

f : Rn � R e as equações de igualdade hi = 0 e desigualdade gj ≤ 0 são as suas

restrições, em que hi : R
n � R e gj : R

n � R (Luenberger & Ye, 2008).

A função objetivo e as funções de restrições podem ser lineares ou não

lineares em relação às variáveis de decisão. Esta caracteŕıstica classifica o problema

como sendo pertencente à Programação Linear ou Programação Não-Linear.

De acordo com Bregalda et al. (1988), em matemática, problemas de

Programação Linear são problemas de otimização nos quais a função objetivo e as


8

restrições são todas lineares. Em contrapartida, um modelo de otimização constitui

um problema de Programação Não-Linear se exibir qualquer tipo de não-linearidade,

seja na função objetivo ou em qualquer de suas restrições (Goldbarg & Luna, 2005).

Além disso, algumas caracteŕısticas importantes a serem observadas

no problema a ser otimizado são: o tipo das variáveis de decisão, que podem ser

discretas ou cont́ınuas, e se possui ou não restrições, denominado problema restrito

ou irrestrito.

Determinados problemas de otimização só tem sentido quando as res-

postas obtidas através das variáveis de decisão forem expressas por números inteiros,

xi ∈ Z, em que Z é o conjunto dos números inteiros, ou por números binários,

xi ∈ {0, 1}. Nestes casos, denominamos problemas de otimização discreta.

Por exemplo, se o objetivo é determinar o número de funcionários para

realizar determinadas tarefas, como nos clássicos problemas de designação, utilizam-

se variáveis inteiras. Ou ainda, se o objetivo é decidir se coloca ou não um de-

terminado item na mochila, como nos clássicos problemas da mochila, é satisfatório

utilizar variáveis binárias para expressar as respostas sim ou não, verdadeiro ou falso.

Caso contrário, quando as variáveis de decisão puderem assumir quais-

quer valores reais, xi ∈ R, denomina-se problemas de otimização cont́ınua. Nestes

problemas, em geral, deseja-se determinar as melhores medidas, os melhores tempos,

dentre outras variáveis de natureza cont́ınua.

Os problemas de otimização irrestritos são aqueles em que os conjun-

tos de restrições I e D são vazios, ou seja, I = D = Ø. Porém, a maioria dos

problemas encontrados na natureza não variam livremente, ou seja, possuem alguma

restrição com relação a quantidades dispońıveis, tempo, capacidade, entre outros.

Isso caracteriza os problema de otimização restritos, em que I ̸= Ø e/ou D ̸= Ø.

Após a formulação de um modelo representativo para o problema real

e determinadas as suas principais caracteŕısticas, é possivel aplicar as técnicas de

otimização baseadas em algoritmos para determinar a melhor solução posśıvel para

o problema, chamada de solução ótima. Contudo, não existe um algoritmo universal


9

para a resolução dos modelos, mas um conjunto de métodos, entre os quais alguns

são mais apropriados para determinadas aplicações (Wright & Nocedal, 1999), e a

escolha da técnica de otimização irá depender, sobretudo, da qualidade e precisão da

solução que se deseja determinar.

2.2.2 Otimização global e local

Um ponto x é dito solução ótima global da função f se x ∈ D(f) e

f(x) ≥ f(y) para todos os valores de y no domı́nio de f . Assim, a solução ótima

global é o ponto cuja função objetivo atinge o menor ou maior valor entre todos os

pontos da região fact́ıvel, dependendo do objetivo de minimização ou maximização,

respectivamente.

Um ponto x é dito solução ótima local da função f se x ∈ D(f) e

f(x) ≤ f(y) para todos os valores de y no domı́nio de f . Assim, a solução ótima

local é o ponto cuja função objetivo é menor ou maior que todos os pontos vizi-

nhos da região fact́ıvel, dependendo do objetivo de minimização ou maximização,

respectivamente.

Em muitos problemas reais a solução ótima global é desejada, mas,

por serem estes problemas complexos, envolverem grande número de variáveis e

instâncias de grande porte, tal solução é dif́ıcil de ser encontrada. Estes problemas

são conhecidos como problemas combinatoriais, e suas principais idéias são expostas

na seção a seguir.

2.2.3 Otimização Combinatória

Existe uma classe de problemas especialmente interessantes dentro da

Otimização que são chamados de Otimização Combinatória. A principal caracte-

ŕıstica destes problemas está relacionada ao espaço finito e discreto de busca de

soluções, o que dificulta o tratamento até a otimalidade devido ao esforço computa-

cional exigido em espaços suficientemente grandes.

Em muitos casos, a solução ótima destes problemas ainda está limitada


10

somente a pequenas instâncias, e não há metodologia comprovadamente eficaz para

resolvê-los até a solução ótima global. Por isso, o grande desafio da Otimização Com-

binatória é produzir, em tempo computacional competitivo, soluções tão próximas

quanto posśıveis da solução ótima.

Muitos problemas reais se caracterizam por serem altamente combi-

natórios, e são neles que se concentram grande parte das pesquisas de avaliação de

desempenho de algoritmos sobre instâncias de grande porte.

O termo instância refere-se a uma especificação de valores dados aos

valores de entrada num determinado momento, satisfazendo às condições ou res-

trições próprias do problema (Goldbarg & Luna, 2005). O tamanho de uma instância

está relacionado, portanto, a quantidade de variáveis de entrada do programa, inde-

pendentemente dos valores associados aos parâmetros que o alimentarão.

Para Hochbaum (1996), quando a solução ideal se torna inatinǵıvel,

então vale a pena sacrificar a otimalidade e se contentar com uma solução fact́ıvel, que

pode ser calculada de forma eficiente. Dáı surge à necessidade de desenvolvimento

de métodos para tratar problemas de natureza combinatorial a partir da exploração

mais ampla do espaço de busca, procurando soluções, quando não ótimas, ao menos

de boa qualidade, medida por alguma função pré-definida.

Santos (2009) classifica o problema de planejamento agŕıcola, objeto de

interesse neste trabalho, como um problema de otimização combinatória complexo,

pois envolve, em geral, um grande número de culturas com limitações espećıficas

quanto à época de plantio e com peŕıodos de cultivo e produtividade muito variáveis.

Tal problema pode ser resolvido em pequenas instâncias com métodos exatos, mas

para um número maior de instâncias, o recurso é fazer uso de métodos heuŕısticos.

Na seção a seguir serão discutidas as vantagens e desvantagens de tais técnicas.

2.3 Exato versus Heuŕıstico

Existem duas abordagens para resolver problemas de otimização: os

métodos Exatos e os métodos Heuŕısticos.


11

Os métodos exatos são, em geral, baseados em gradientes e pos-

suem condições de otimalidade que garantem a solução ótima. Já os métodos

heuŕısticos são métodos aproximativos, que não garantem a convergência, mas pro-

porcionam boas soluções em tempo computacional razoável, quando comparados com

os métodos exatos.

Tradicionalmente, os métodos exatos se caracterizam pela rigidez de

seus modelos matemáticos representados através de seus Teoremas, dificultando a

representação de situações reais cada vez mais complexas e dinâmicas (Ochi, 1998).

Nestes casos, o modelo é conhecido e sua solução depende do conhecimento das

derivadas da função objetivo. Por isso, os melhores resultados destes métodos são

para funções cont́ınuas, convexas e semi-modais (Brandão & Saramago, 2011).

Muitas vezes, no mundo real, os problemas são complexos, não-lineares,

de dif́ıcil representação e descritos por funções nem sempre diferenciáveis, neces-

sitando de métodos numéricos para a sua solução (Ochi, 1998). Dáı surgiu a neces-

sidade de desenvolver técnicas capazes de proporcionar soluções ótimas ou próximas

da ótima, mesmo que a qualidade não seja comprovadamente ótima.

Estes métodos se tornaram conhecidos como heuŕısticas, e trouxeram

flexibilidade ao algoritmo de busca ao associar técnicas de otimização com ferramen-

tas da Inteligência Artificial.

Por isso, a escolha do método depende das caracteŕısticas do proble-

ma a ser otimizado, principalmente do comportamento da função que o representa

(Goldbarg & Luna, 2005).

Os métodos exatos têm como vantagem a garantia da solução ótima,

baixo número de avaliações da função objetivo, e em geral, convergência em tempo

aceitável, dependendo do problema espećıfico. Por outro lado, têm como desvan-

tagem a modelagem mais complexa, alto custo computacional em problemas de

grande instância, não são muito eficientes em tratar problemas em que o espaço de

busca é grande e discreto e, muitos algoritmos dependem da existência de derivadas.

Também destacam-se as vantagens e desvantagens dos métodos


12

heuŕısticos. São vantagens a fácil implementação, flexibilidade do algoritmo com

boa solução para a maioria dos problemas, baixo custo computacional, capacidade

de encontrar ótimos globais de funções de alta complexidade e, não exigência do

cálculo de derivadas. Por outro lado, são desvantagens destes métodos a não garan-

tia da otimalidade da solução obtida, um algoritmo eficiente para um problema pode

não ser eficiente para outro e, exigência de um elevado número de avaliações da

função objetivo.

O cerne da dificuldade da abordagem exata está relacionada aos pro-

blemas de otimização combinatória, que representam grande parte dos problemas

reais. A partir deste cenário e do avanço dos recursos computacionais, as heuŕısticas

se tornaram uma ferramenta eficiente (rápida) para a solução de problemas de na-

tureza combinatorial, e para comparação de solução com os métodos clássicos de

otimização. A seguir, serão conceituados os elementos das técnicas heuŕısticas.

2.4 Estratégias Heuŕısticas

Etimologicamente, a palavra “heuŕıstica” vem da palavra grega

Heuriskein, que significa “descobrir”, “encontrar”. Seu desenvolvimento se deu a

partir de problemas de otimização espećıficos, em que as heuŕısticas eram desenha-

das com o propósito de cada problema, e não eram, via de regra, pasśıveis de serem

utilizadas em outros problemas. Sua principal limitação está relacionada a dificul-

dade de escapar de ótimos locais, por serem algoritmos de busca intensiva.

Para Melián et al. (2003), heuŕıstica é o termo apropriado para os pro-

cedimentos que, empregando conhecimento acerca de um problema e das técnicas

aplicáveis, tentam encontrar soluções (ou aproximar-se delas) usando uma quanti-

dade de recursos (geralmente tempo) razoável.

Goldbarg & Luna (2005) definem uma heuŕıstica como uma técnica que

busca alcançar uma boa solução utilizando um esforço computacional considerado

razoável, sendo capaz de garantir a viabilidade da solução encontrada ou, ainda, em

alguns casos, a otimalidade, especialmente nas ocasiões em que essa busca partir de


13

uma solução viável próxima ao ótimo.

Os métodos heuŕısticos podem ser classificados em:

� heuŕısticas de construção: as soluções são constrúıdas elemento a elemento,

seguindo algum critério heuŕıstico de otimização, até que se tenha uma solução

viável. Ex: o método guloso;

� heuŕısticas de busca em vizinhança: a partir de uma solução inicial viável,

realizam-se operações de troca na vizinhança da solução corrente, a fim de

melhorar esta solução até que não seja mais posśıvel a melhoria ou algum

outro critério de parada seja satisfeito. Ex: busca local;

� metaheuŕısticas: são heuŕısticas genéricas mais sofisticadas, em que uma

heuŕıstica mais simples é gerenciada por um procedimento que visa explorar

inteligentemente a instância do problema e o seu espaço de soluções;

� heuŕısticas h́ıbridas: é a combinação de duas ou mais heuŕısticas, visando

melhorias na performance do algoritmo.

Dentre as heuŕısticas, as metaheuŕısticas são estratégias mais genéricas

que, controladas por critérios probabiĺısticos, possibilitam escapar de ótimos locais

e, portanto, explorar regiões mais promissoras.

2.4.1 Metaheuŕısticas

O termo “metaheuŕıstica” se obtém de antepor a palavra heuŕıstica

ao prefixo meta, que significa “mais além” ou “a um ńıvel mais elevado” (Melián

et al., 2003). Elas surgiram como forma de superar as heuŕısticas convencionais,

pois possuem estratégias para tentar escapar das armadilhas dos ótimos locais e a

facilidade para se aplicar a um extenso conjunto de problemas.

Para Melián et al. (2003), as metaheuŕısticas podem ser concebidas

como estratégias inteligentes para a concepção de procedimentos heuŕısticos mais

generalistas e com alto desempenho.


14

Glover & Kochenberger (2003) definem as metaheuŕısticas como

métodos de solução que orquestram uma interação entre os processos de melho-

ria e estratégias locais de ńıvel superior para criar um processo capaz de escapar de

ótimos locais e realizar uma pesquisa robusta de um espaço de solução.

A estratégia inteligente a qual as metaheuŕısticas são pautadas consiste

basicamente em melhorar a solução ao longo do desenvolvimento do algoritmo por

meio de ações de intensificação e diversificação.

Na intensificação, ao encontrar uma boa solução para o problema,

realiza-se uma busca próxima à sua região, introduzindo pequenas mudanças, a fim

de se obter alguma melhora. E, para não permitir convergência para ótimos locais,

utiliza-se a estratégia de diversificação para encontrar outras regiões do espaço de

busca que ainda não tenham sido exploradas, e que podem conter melhores soluções.

Outra caracteŕıstica importante a ser observada nas diferentes meta-

heuŕısticas é com relação ao número de soluções com que trabalham, que pode ser

única ou uma população. As estratégias de solução única partem de uma solução

inicial e descrevem movimentos no espaço de busca que consistem em sair da solução

corrente para uma melhor solução ou região mais promissora. Já as estratégias

baseadas em população partem de um conjunto de soluções iniciais e, por meio de

procedimentos de busca definidos, descrevem a evolução da população no espaço de

busca, com o objetivo de combiná-las e produzir melhores soluções.

A seguir destacam-se as principais metaheuŕısticas com relação ao

número de soluções com que trabalham:

� Solução única: Simulated Annealing, Busca Tabu, GRASP, VNS, entre ou-

tros.

� População: Algoritmos Genéticos, Scartter Search, Colônia de Formigas, en-

tre outros.

Em geral, as metaheuŕısticas apresentam as seguintes vantagens

(Melián et al., 2003):


15

� Simplicidade: são baseadas em um prinćıpio simples e claro;

� Adaptabilidade: são aplicáveis a qualquer tipo de problema, através de pe-

quenas adaptações;

� Robustez: apresenta bons resultados a uma grande variedade de problemas.

A reunião de atributos aqui destacados, que compõem as meta-

heuŕısticas, caracterizam-na como um bom método de busca por soluções em proble-

mas de otimização combinatória e, por isso, o número de pesquisas utilizando estas

estratégias tem crescido e se sofisticado cada vez mais, aplicando-se a espaços de

busca de soluções cada vez mais complexos.

As seções que seguem descrevem os Algoritmos Genéticos e Simulated

Annealing, estratégias que serão utilizadas neste trabalho.

2.5 Algoritmo Genético (AG)

A perspectiva evolutiva registrada por Darwin em 1859 em sua obra

A Origem das Espécies (Darwin, 1859) revolucionou a ciência com idéias inovadoras

sobre evolução e seleção natural. Gould (1977) resume a teoria darwiniana em 3

componentes, sendo estes dois fatos inegáveis e uma conclusão inevitável:

1. Produção excessiva de descendentes: Os organismos produzem mais des-

cendentes do que podem sobreviver.

2. Hereditariedade: organismos variam, e estas variações são herdadas, pelo

menos em parte, por sua descendência.

3. Seleção Natural: Em média, indiv́ıduos mais adaptados são favorecidos pelo

ambiente e tendem a reproduzir mais.

A condição (1) gera competição por recursos entre organismos para a

sua sobrevivência e reprodução, e está condicionada a capacidade suporte do ambi-

ente. A condição (2) está relacionada a observação de Darwin de que os organismos


16

variam dentro das populações e que os filhos tendem a parecer-se com os seus pais.

Estas condições levam a conclusão (3), que os organismos com caracteŕısticas mais

vantajosas que os seus competidores têm mais chances de reprodução e geram maior

número de descendentes, enquanto que caracteŕısticas que não conferem nenhuma

vantagem não são passadas para a geração seguinte.

Para Futuyma (2002), a evolução biológica consiste na mudança das

caracteŕısticas hereditárias de grupos de organismos, denominados populações e

espécies, ao longo das gerações. Numa perspectiva de longo prazo, a Evolução é

a descendência, com modificações, de diferentes linhagens a partir de ancestrais co-

muns.

Desde então, diversas áreas do conhecimento têm sofrido fortes in-

fluências advindas dos pensamentos Darwinianos, em especial a Matemática e a

Computação, que vem registrando numerosos estudos na área de Computação Evo-

lutiva e Inteligência Artificial.

De acordo com Brandão & Saramago (2011), estudos utilizando es-

tratégias evolutivas em computação iniciaram-se em 1964, com os pesquisadores

alemães Ingo Rechenberg e Hans-Paul Schwefel, mas foi em 1975 que as principais

idéias de computação evolutiva foram solidificadas pelo cientista americano John

Henry Holland, em seu livro Adaptation in Natural and Artificial Systems (Holland,

1975), com a criação dos Algoritmos Genéticos como estratégia para a solução de

problemas numéricos.

De acordo com Mitchell (1992) e Goldberg (1989), o objetivo original

de Holland não era projetar algoritmos para resolver problemas espećıficos, mas sim

estudar formalmente o fenômeno da adaptação como ocorre na natureza e desenvolver

formas em que os mecanismos de adaptação natural pudessem ser importados para

os sistemas de computador.

Foi em 1989 que o cientista americano David E. Goldberg descreveu

o Algoritmo Genético como um procedimento de busca baseado nos mecanismos de

seleção natural e genética (Goldberg, 1989).


17

Desde a sua criação e formalização, os Algoritmos Genéticos têm sido

muito utilizados para uma grande variedade de problemas de busca e otimização,

por serem algoritmos computacionalmente simples, porém poderosos na sua busca

por melhoras (Goldberg, 1989).

O Algoritmo Genético (AG) é, portanto, um procedimento de busca

que utiliza escolhas aleatórias como ferramenta para guiar a busca altamente explo-

ratória por meio da codificação de um espaço de parâmetros em direção a regiões do

espaço de busca com provável melhora (Goldberg, 1989).

O AG baseia-se na representação de um problema por meio de um

conjunto de indiv́ıduos que são soluções potenciais para o problema em questão,

chamada de população. Cada indiv́ıduo da população é denominado cromossomo e

possui uma aptidão, que é a sua capacidade de sobreviver e reproduzir no ambiente.

Em sua abordagem mais geral, inicia-se o algoritmo construindo uma

população inicial, que pode ser gerada de forma aleatória ou por uma heuŕıstica

construtiva. Em seguida, todos os indiv́ıduos da população têm o seu desempenho

avaliado por uma função de avaliação. Esta população passará então por processos

consecutivos de reprodução, por meio de operações de seleção, crossover e mutação.

Cada ciclo de reprodução determina uma nova população de indiv́ıduos, chamada de

geração, e o processo continua até que um critério de parada seja satisfeito.

O processo ilustrado na Figura (2) busca uma melhor solução para um

determinado problema por meio da evolução das populações. Após um certo número

de gerações, espera-se convergir para uma geração de elite, que corresponde a uma

solução ótima ou quase ótima para o problema.

Goldbarg & Luna (2005) resumem os procedimentos básicos de um AG

em:

1. Representação das soluções na estrutura de cromossomos;

2. Construção de uma população inicial de cromossomos;

3. Definição de uma função de avaliação dos cromossomos segundo suas aptidões;


18

Figura 2 - Fluxograma do processo de busca do AG em uma abordagem geral

4. Definição dos operadores genéticos que vão permitir a produção de novos in-

div́ıduos;

5. Definição dos parâmetros do AG, tais como critério de parada, tamanho da

população, entre outros.

2.5.1 Representação de um cromossomo

Para trabalhar com o Algoritmo Genético é preciso primeiramente co-

dificar as informações do problema em uma estrutura denominada cromossomo, de

modo que o método consiga trabalhar com os dados que lhes são fornecidos (Brandão

& Saramago, 2011). Esta codificação é, na verdade, a representação de uma solução.

Para Koza (1992), a representação é um passo fundamental no trabalho

com o AG, pois ele manipula diretamente a representação codificada do problema,

e o esquema de representação pode limitar severamente a janela pela qual o sistema


19

observa o mundo.

Na literatura, a codificação das variáveis para o AG é usualmente feita

por meio de uma representação binária (zero-um) em que cada valor associado repre-

senta a presença (valor 1) ou ausência (valor 0) de certa caracteŕıstica no indiv́ıduo.

Embora esta representação tenha se mostrado eficiente para vários

problemas, observou-se, à medida que foram crescendo as aplicações dos AGs em

problemas com um elevado número de restrições, que esta representação pode não

ser a mais adequada, surgindo dáı alternativas como a representação por números

reais ou inteiros, em que um cromossomo é descrito por um vetor de números reais

ou inteiros, dependendo do problema (Koza, 1992).

A t́ıtulo de ilustração, vamos considerar um exemplo simples:

Problema do Agricultor: Suponha que um agricultor dispõe de

cinco tipos de plantas e apenas três canteiros dispońıveis para plantio. Deseja-se

saber qual a melhor combinação de plantas nos canteiros, a fim de minimizar os

custos do agricultor com o plantio.

Figura 3 - Itens que compõem o problema do agricultor

Um cromossomo com representação binária para o problema do agricul-

tor pode ser definido como mostra a Figura (4).

Na Figura (4), a combinação de 15 bits representa um cromossomo para

o problema do agricultor, ou seja, uma posśıvel solução. Cada gene Xi, i = 1, 2, 3,

representa um canteiro e cada alelo de Xi representa uma planta. Desta forma, o

primeiro alelo de X1 pode assumir o valor 1 ou 0, que representará se a planta 1


20

Figura 4 - Cromossomo com representação binária

será cultivada ou não naquele canteiro, respectivamente. Por isso, a posição do alelo

dentro do gene é fundamental para a interpretação da solução.

Observe ainda que, para a solução ser fact́ıvel, cada geneXi deve conter

em sua configuração apenas um bit de valor 1, pois ele associa ao canteiro uma única

planta a ser cultivada. Do contrário, implicaria que mais de uma planta pode ser

plantada em um determinado canteiro, o que não é permitido no problema. Portanto,

na configuração ilustrada na Figura (4), o agricultor deverá plantar nos canteiros 1,

2, e 3 as plantas 2, 5 e 3, respectivamente.

A Figura (5) utiliza a representação com números inteiros sugerida em

Koza (1992) para a mesma configuração do problema do agricultor.

Figura 5 - Cromossomo com representação inteira

Nota-se que representação inteira para o problema do agricultor torna-

se mais simplificada do que a binária, pois não necessita da posição do alelo indicando

a planta que deve ser cultivada, e cada gene Xi é composto por apenas um valor,

que especifica a cultura que deve ser plantada naquele canteiro.

Michalewicz (1994) defende o uso de estruturas adequadas de dados

(possivelmente complexos) para a representação do cromossomo, e que este não pre-


21

cisa necessariamente ser representado por uma cadeia binária. Desta forma, a repre-

sentação deve ser aquela que melhor represente o problema em questão e deve estar

corretamente associada a soluções válidas do problema analisado.

2.5.2 População

Com a representação de um indiv́ıduo definida, o primeiro passo para

inicialização do AG é criar uma população inicial. É um processo, na maioria das

vezes simples, que implica em criar Q indiv́ıduos que irão compor a primeira geração

(g = 1) do AG. Após a criação da população inicial, a população estará em cons-

tante fluxo nas próximas gerações devido a reprodução e morte dos indiv́ıduos que

a compõem.

Comumente, a população inicial é gerada de forma aleatória, ou seja,

cada alelo pode conter um dos posśıveis valores do conjunto adotado (binário, inteiro,

real, ...), com probabilidade uniforme. Para o problema do agricultor, gerou-se uma

população inicial com Q indiv́ıduos na estrutura de cromossomos com representação

inteira em que cada indiv́ıduo é expresso por um cromossomo de 3 genes, e cada gene

contém um número inteiro escolhido aleatoriamente entre 1 e 5, que é a identificação

das plantas dispońıveis. Suponha Q = 5, obteve-se aleatoriamente para o problema

do agricultor os cromossomos apresentados na Figura (6).

Figura 6 - População inicial gerada aleatoriamente para o problema do agricultor

Estudos utilizando técnicas heuŕısticas para construção da população

inicial têm constatado que a inicialização não aleatória desta população pode acelerar


22

a convergência do AG (Moujahid et al., 2007). Assim, para problemas em que a

geração de uma população inicial não é tão imediata e o espaço de soluções fact́ıveis

é muito restrito, utilizam-se heuŕısticas simples e rápidas para esta tarefa.

Além da população inicial, o Algoritmo Genético trabalha com um

população intermediária (mating pool), que é obtida a partir da população inicial e

por meio da operação de seleção.

O número de indiv́ıduos Y na população intermediária é determinado

pela taxa de seleção ps definida pelo programador, de modo que 1 ≤ Y ≤ Q, em que

Q é o número de indiv́ıduos na população inicial. Os Y indiv́ıduos são escolhidos

utilizando-se algum método de seleção e participarão do processo de reprodução da

população.

A ideia da população intermediária é permitir que uma parte dos in-

div́ıduos da geração atual, aqueles que não foram selecionados para a reprodução,

sejam mantidos na próxima geração, preservando assim caracteŕısticas da população

atual na nova população após o processo de reprodução.

Figura 7 - Representação esquemática da população inicial e população intermediária

Observe que quando Y = 1 ocorre reprodução assexuada, ou seja, há

apenas um indiv́ıduo na população intermediária para fazer cruzamentos. Neste caso,

não haverá variação genética. Para Y = Q tem-se que a população intermediária

é a própria população inicial. Neste caso, não há garantias de manter indiv́ıduos

da geração atual na próxima geração, pois todos os indiv́ıduos estão suscept́ıveis a

participar do cruzamento e serem substitúıdos por indiv́ıduos mais aptos.


23

2.5.3 Aptidão

Aptidão é a essência da seleção natural de Darwin e igualmente dos

Algoritmos Genéticos. Na natureza, a aptidão de um indiv́ıduo é a sua probabilidade

de sobreviver até a idade de reprodução, e reproduzir-se. Esta medida pode ser obtida

considerando-se, por exemplo, o número de filhos.

No mundo artificial dos algoritmos matemáticos, em geral, mede-se

a aptidão dos indiv́ıduos utilizando alguma função representativa do problema e,

em seguida, utiliza-se essa medida para controlar a aplicação das operações que

modificam as estruturas da população artificial (Koza, 1992). A forma mais comum

de medir esta aptidão nos AGs é construindo uma função de avaliação que atribui

um valor de aptidão a cada indiv́ıduo da população. Essa função deve ser definida

para cada problema de maneira espećıfica e será denotada por eval(Si). Assim, dado

um cromossomo Si, a função de avaliação eval(Si) lhe designa um número real que

supostamente reflete o grau de adaptação desse indiv́ıduo ao problema (Moujahid

et al., 2007).

Para o problema do agricultor, a aptidão de um dado cromossomo

poderá ser, por exemplo, o custo total do cultivo de determinadas plantas nos can-

teiros. Conhecido os custos de cultivar cada planta em cada canteiro, é posśıvel

obter valores para a função de avaliação. A Tabela (1) mostra, dentre as soluções

correntes, que S1 é a solução viável para o problema, pois apresenta menor custo.

Tabela 1: Aptidão das soluções geradas para o problema do agricultor

Cromossomo Solução Aptidão

S1 3− 5− 1 3

S2 5− 2− 4 16

S3 2− 1− 2 6

S4 5− 3− 4 13

S5 4− 4− 5 10

A aptidão de um indiv́ıduo está fortemente relacionada com a sua in-


24

fluência sobre o desenvolvimento da população. Quando muitos descendentes de um

único indiv́ıduo sobrevivem e reproduzem-se, então muitos membros da população

resultante, a chamada “próxima geração”, levarão alelos deste indiv́ıduo (Holland,

1975).

2.5.4 Penalização

Observou-se na Seção 2.5.3 que uma boa função de avaliação é aquela

que reflete uma aptidão real para cada indiv́ıduo. Contudo, em muitos problemas

de otimização combinatória, boa parte das soluções representadas na população do

AG são não fact́ıveis, ou seja, não satisfazem todas as restrições do problema. Estas

soluções podem muitas vezes apresentar melhores valores de avaliação do que soluções

fact́ıveis, e dáı surge a necessidade de penalizá-las, de modo que o algoritmo não

convirja para uma solução que não satisfaça as exigências do problema.

Nestes casos, os indiv́ıduos estão sujeitos a um conjunto de restrições,

tornando necessária a utilização de estratégias para melhorar o desempenho do Al-

goritmo Genético, e dentre elas destacam-se a absolutista e a penalização.

Na abordagem absolutista os indiv́ıduos que não satisfazem as res-

trições não são considerados soluções para o problema, mas seguem fazendo cruza-

mentos e mutações para a obtenção de indiv́ıduos fact́ıveis. Na abordagem de penal-

ização, atribui-se um valor de penalização para cada indiv́ıduo que infringe restrições.

A idéia geral da penalização é diminuir a aptidão do indiv́ıduo (ou aumentar, de-

pendendo do objetivo do problema) em um valor que diz respeito às restrições que

o indiv́ıduo viola.

Desta forma, a função objetivo de um problema com penalização pode

ser escrita como segue:

f(Si) =

 eval(Si), se Si é fact́ıvel

eval(Si)± penalidade(Si), caso contrário
,


25

em que Si é o indiv́ıduo, i = 1, ..., Q, eval é a função de avaliação e penalidade é

a função de penalização, que vale zero se nenhuma violação ocorre, e é um valor

positivo, caso contrário.

Linden (2008) destaca três formas de penalização: estática, dinâmica e

adaptativa. A penalização estática é definida a priori e não se altera com a execução

do algoritmo. Na penalização dinâmica, define-se uma função para a evolução da

punição com o tempo, aumentado-a com o decorrer do algoritmo. Já a adaptativa,

ao invés de usar uma função para a penalização, utiliza a avaliação da população

corrente como um feedback para guiar a modificação da penalização.

A estratégia de penalização, de modo geral, deve garantir que o pior

indiv́ıduo que respeita as restrições tenha avaliação superior àquela do melhor in-

div́ıduo não fact́ıvel. Espera-se que, com a penalização das soluções não fact́ıveis, o

algoritmo se aproxime cada vez mais da região viável do problema restrito, haja visto

que as soluções fora do espaço viável apresentarão valores de aptidão muito ruins para

a otimização do problema e serão facilmente desconsideradas pelo algoritmo.

2.5.5 Elitismo

O elitismo é um operador que força o Algoritmo Genético a preser-

var um número fixo de melhores indiv́ıduos fact́ıveis na população em cada geração.

A ideia é que os melhores indiv́ıduos da população não sejam perdidos durante o

processo de reprodução, e que a diversificação gerada pelo algoritmo aproveite in-

formações destas soluções.

Um Algoritmo Genético com Elitismo copia os melhores indiv́ıduos da

popu-lação em toda geração, assegurando que durante a reprodução estes indiv́ıduos

não sejam perdidos, e ao final do processo, os devolvem à população. A Figura (8)

mostra o funcionamento do AG com Elitismo.

Na literatura, o elitismo tem mostrado melhoras significantes no de-

sempenho do AG (Mitchell, 1992). Contudo, há cŕıticas em sua utilização por causar

decrescimento na diversidade da população por meio do aumento da pressão seletiva


26

Figura 8 - Fluxograma do Algoritmo Genético com elitismo

(Ishibuchi et al., 2007).

2.5.6 Seleção

Antes de operar geneticamente para obter a reprodução da população,

deve-se selecionar os indiv́ıduos que participarão deste processo, e isto é feito por meio

do operador de seleção. Seleção é, portanto, um método que copia cromossomos da

população corrente para a população intermediária, a fim de se reproduzirem. Em

geral, a seleção privilegia os indiv́ıduos mais aptos, ou seja, quanto maior for a aptidão

do indiv́ıdio, maior a sua chance de ser selecionado para a população intermediária.

Na literatura existem 4 principais formas de seleção: Proporcional,


27

Torneio, Classificação e Truncada. A escolha do método pode influenciar direta-

mente o desempenho do algoritmo, pois produzem mudanças no comportamento

das soluções, induzindo uma pressão de seleção diferente na população (De Jong &

Sarma, 1995).

Dentre os métodos citados, a Seleção Proporcional (Fitness-

Proporcional Selection) foi pioneira e é a que dá maior chance de indiv́ıduos mais

aptos serem selecionados. Contudo, em casos de existência de super-indiv́ıduos na

população (indiv́ıduos com aptidão muito superior a dos demais), pode-se obter con-

vergência prematura para um ótimo local, já que a reprodução descomedida deste

indiv́ıduo ao longo das gerações pode acabar com a diversidade da população.

Pensando nisto, métodos de seleção que diminuam a dominância do

super-indiv́ıduo e solucionem o problema da convergência prematura foram propos-

tos. Estes métodos visam diminuir a pressão seletiva na população, dando mais

chances para indiv́ıduos menos aptos serem selecionados para a reprodução. Por um

lado, nestes métodos, se ganha com diversidade da população, mas por outro lado,

faz com que o algoritmo chegue mais lentamente à solução desejada.

Linden (2008) destaca alguns pontos em que o método de seleção uti-

lizado pode influenciar no desempenho do algoritmo:

1. Pode-se acelerar ou retardar a ocorrência da convergência genética;

2. Fica mais ou menos agressivo no aproveitamento das melhores soluções;

3. Ao utilizar apenas indiv́ıduos com excelentes avaliações pode-se estar jogando

fora bons esquemas presentes nos indiv́ıduos com avaliações ruins;

4. Ao permitir muito que indiv́ıduos com avaliações ruins participem do processo

reprodutivo, os esquemas que os tornam ruins não desaparecerão da população.


28

2.5.6.1 Proporcional

A implementação da Seleção Proporcional é usualmente feita utilizando

um dos métodos: Roleta Viciada ou Amostragem Estocástica Uniforme.

A Roleta Viciada (Roulette Wheel) é a mais popular forma de imple-

mentação da Seleção Proporcional à aptidão do indiv́ıduo. Neste método, a chance de

um indiv́ıduo ser selecionado está proporcionalmente ligada à sua aptidão, e em geral,

os indiv́ıduos são selecionados aleatoriamente, dando maior chance de reprodução

àqueles mais aptos. Koza (1992) descreve o procedimento usual da Roleta Viciada

como segue.

Se f(Si) é a aptidão do indiv́ıduo Si da geração corrente, então, neste

método de seleção, a chance do indiv́ıduo Si ser copiado para a população inter-

mediária é dada pela Equação (1).

pi =
f(Si)

Q∑
j=1

f(Sj)

, i = 1, . . . , Q. (1)

Tipicamente, pi é a aptidão normalizada do indiv́ıduo Si. Define-se

uma função qi que acumula o valor das aptidões de todos os indiv́ıduos da geração

corrente, dada pela Equação (2).

qi =

Q∑
j=1

pj, i = 1, . . . , Q, (2)

em que Q é o número de indiv́ıduos da população e 0 ≤ qi ≤ 1, com i = 1, . . . , Q.

A seleção de um indiv́ıduo por Roleta Viciada consiste em gerar um

número aleatório r uniformemente distribuido no intervalo [0, 1] e compará-lo com

a função qi. Quando pi−1 ≤ r ≤ pi, indica que o indiv́ıduo Si foi selecionado.

Repete-se o processo por Y vezes, o número de indiv́ıduos da população intermediária

determinada pela taxa ps.


29

Para a população inicial criada no exemplo do agricultor, dispońıvel

na Tabela (1), suponha que deseja-se determinar uma população intermediária de

Y = 3 indiv́ıduos utilizando o método da Roleta Viciada, como mostra a Tabela (2).

Tabela 2: Valores de aptidão normalizada e acumulada para os indiv́ıduos gerados

no problema do agricultor

Indiv́ıduo pi qi

S1 0, 0625 0, 0625

S2 0, 3333 0, 3958

S3 0, 1250 0, 5208

S4 0, 2708 0, 7917

S5 0, 2083 1

A partir das informações da Tabela (2), pode-se construir a Roleta

Viciada com aptidão normalizada, como mostra a Figura (9), e prosseguir com o

método, descrito a seguir.

Figura 9 - Roleta com aptidão normalizada para a população inicial gerada no pro-

blema do agricultor

Sorteia-se um valor para r pertencente ao intervalo [0, 1], e verifica-

se, por meio da função acumulada, qual indiv́ıduo foi selecionado pelo método para

compor a população intermediária. Por exemplo, se 0 ≤ r ≤ 0, 0625, o indiv́ıduo S1

será selecionado, ou se 0, 0625 < r ≤ 0, 3958, o indiv́ıduo S2 será selecionado, e assim

por diante. O indiv́ıduo selecionado é então retirado da Roleta Viciada e uma nova


30

roleta é constrúıda com os indiv́ıduos restantes. Este processo é repetido Y vezes,

que no exemplo ilustrado equivale a três vezes.

O método da Roleta Viciada tem sido muito utilizado na literatura,

porém, como destacado, pode apresentar problemas de rápida convergência devido a

existência de super-indiv́ıduos na população, que muitas vezes representa um ótimo

local, e não global, como é de interesse.

Outro método de seleção que utiliza a idéia de seleção Proporcional

à aptidão é a Amostragem Estocástica Uniforme (Stochastic Universal Sampling).

Neste método, todos os indiv́ıduos são mapeados para segmentos cont́ıguos de uma

linha, sendo que o tamanho de cada segmento é proporcional ao valor da aptidão do

indiv́ıduo (Linden, 2008).

O primeiro passo é fazer uma normalização dos tamanhos dos segmen-

tos, como no método da Roleta Viciada, expressa na Equação (1). Em seguida, para

selecionar os Y indiv́ıduos que irão compor a população intermediária, sorteia-se um

número r pertencente ao intervalo [0, 1
Y
] e constrói-se Y ponteiros, como mostra a

Equação (3).

r, r +
1

Y
, r +

2

Y
, . . . , r +

Y − 1

Y
(3)

Estes ponteiros apontam os segmentos de reta normalizados seleciona-

dos pelo método e indicam que os indiv́ıduos “donos” destes segmentos serão os

escolhidos para a população intermediária.

Suponha que deseja-se selecionar Y = 3 indiv́ıduos para compor a

população intermediária no problema do agricultor, e que sorteou-se aleatoriamente r

igual a 0, 2, sabendo que r ∈ [0, 1
3
]. Então, os indiv́ıduos selecionados pelos ponteiros

é mostrado na Figura (10).

Observe na Figura (10) que os ponteiros constrúıdos pelo método in-

dicam que S2, S4 e S5 foram os indiv́ıduos selecionados.

Linden (2008) destaca ainda que, assim como no método da Roleta

Viciada, a Amostragem Estocástica Uniforme ainda não resolve o problema da con-


31

Figura 10 - Ponteiros constrúıdos pelo método de Amostragem Estocástica Uniforme

para o problema do agricultor

vergência para super-indiv́ıduos.

2.5.6.2 Torneio

Torneio (tournament selection) é um método de seleção em que k in-

div́ıduos são escolhidos aleatoriamente da população e apenas um será selecionado

para a população intermediária, aquele mais apto entre os k.

Desta forma, um número aleatório r é escolhido uniformemente no

intervalo [0, 1]. Se r < b (em que b é um parâmetro, por exemplo, 0, 9), o indiv́ıduo

mais apto entre os k será selecionado para ser um dos pais, caso contrário, o menos

apto será selecionado. Os k indiv́ıduos são então devolvidos na população original e

podem ser selecionados novamente (Mitchell, 1992).

A forma mais usual de implementação da seleção por torneio é o

chamado torneio binário, em que dois indiv́ıduos concorrem na seleção. Neste caso,

k = 2 e não é utilizado o parâmetro b para testar o vencedor do torneio, e isso implica

em colocar os indiv́ıduos em competição direta e o mais apto vence sempre.

A implementação da seleção por torneio binário é simples e é descrita

a seguir:

1. Seleciona-se 2 indiv́ıduos da população aleatoriamente para participar do

torneio;


32

2. Os 2 indiv́ıduos são colocados em competição direta pelo direito de ser pai,

usando como arma a sua aptidão;

3. O indiv́ıduo mais apto entre os 2 é copiado para a população intermediária,

ficando dispońıvel para a reprodução.

Observe que o torneio de tamanho k implica em quantos competidores

serão selecionados aleatoriamente dentro da população para participar do torneio e é

definido pelo programador. Assim, k deve ser no mı́nimo igual a 2 para poder haver

competição entre indiv́ıduos e no máximo igual ao tamanho da população Q, sendo

que, neste segundo caso, o vencedor será sempre o mesmo, o indiv́ıduo mais apto.

Vale ainda notar que, quando o parâmetro b não é utilizado, o pior

indiv́ıduo nunca participará da reprodução, pois ele nunca será vencedor de um

torneio, exceto em raros casos de concorrer ele com ele mesmo.

2.5.6.3 Classificação

A implementação da Seleção por Classificação, assim como a Seleção

Proporcional, é feita utilizando um dos métodos: Linear ou Exponencial.

No método de seleção por Classificação (rank selection) os indiv́ıduos

da população não serão selecionados de acordo com sua aptidão absoluta, como na

seleção Proporcional, e sim classificados de acordo com sua aptidão (Mitchell, 1992).

A partir de sua classificação, terão os seus valores de desempenho recalculado por

meio de uma transformação, que pode ser linear ou exponencial.

Este método foi proposto por Baker em 1985, como forma de superar

a convergência prematura observada nos métodos de Seleção Proporcional (Mitchell,

1992), e é descrito como segue.

Primeiramente, ordena-se todos os indiv́ıduos da população de acordo

com a sua aptidão, estabelecendo assim uma classificação dos indiv́ıduos em ordem

crescente (o pior terá classificação igual a 1, o segundo pior 2, até o último que terá

a melhor classificação igual a Q, que é número de indiv́ıduos na população). Em


33

seguida, atribui-se a cada indiv́ıduo um valor de adequação determinado por sua

posição na classificação, que pode ser obtida pela Equação (4).

E(i, t) = Min+ (Max−Min)
(rank(i, t)− 1)

Q− 1
, (4)

em que,

� E(i, t) é o valor de adequação que deseja-se calcular para o indiv́ıduo i da

geração t;

� Min é o valor da avaliação que será atribúıdo ao indiv́ıduo pior classificado;

� Max é o valor da avaliação que será atribúıdo ao indiv́ıduo melhor classificado;

� Q é o número de indiv́ıduos na população;

� rank(i, t) é a classificação atribúıda ao indiv́ıduo i na geração t.

Esta forma de classificação é chamada de classificação linear. Com

o valor E de adequação de cada indiv́ıduo estabelecido pela Equação (4), pode-se

utilizar um dos métodos descritos anteriormente (Roleta Viciada ou Amostragem

Estocástica Uniforme) para determinação da população intermediária.

Linden (2008) propõe ainda uma maneira de manter a pressão seletiva

em um ńıvel mais alto, utilizando uma função de classificação exponencial, denomi-

nada classificação exponencial.

E(i) =
1− e−i

c
, (5)

em que i é a posição do indiv́ıduo (do pior para o melhor) e c é uma constante.

O uso da função exponencial aumenta a diferença entre a avaliação

do melhor indiv́ıduo e a do pior, aumentando a pressão seletiva e, por conseguinte,

diminuindo a diversidade da população. Assim, o problema do super-indiv́ıduo fica

imediatamente resolvido e não se tem tanta homogeneidade nas avaliações quanto

no caso de uso de uma função linear (Linden, 2008).


34

Koza (1992) observa as vantagens e desvantagens do método de

seleção por classificação:

Seleção por classificação reduz potencialmente os efeitos dominantes

dos super-indiv́ıduos na população por distribuir melhor a chance de

sorteio entre os indiv́ıduos, limitando assim a pressão de seleção. Ao

mesmo tempo, este método de seleção exagera na aproximação dos

valores de adequação entre ind́ıv́ıduos e super-indiv́ıduos, de modo que

os melhores cromossomos não se distinguem muito dos demais.

2.5.6.4 Truncada

No método de Seleção Truncada (truncation selection) apenas os x me-

lhores indiv́ıduos da população serão escolhidos para a reprodução. O parâmetro x

pertence ao intervalo [1, Q], em que Q é o número de indiv́ıduos da população. Para

x = 1, a reprodução torna-se monótona, ou seja, apenas um indiv́ıduo participará

da reprodução, e isso implica que todos os filhos serão iguais ao pai. Para x = Q, a

versão truncada passa a se comportar como a não truncada, e todos os indiv́ıduos

da população estão dispońıveis para a reprodução. Neste último caso, a população

intermediária é a própria população.

Para a implementação do método, os indiv́ıduos são ordenados de

forma decrescente (de Q a 1) de acordo com sua avaliação, e somente aqueles cujas

posições estiverem entre 1 e a posição de corte x poderão participar da seleção. Fica

claro então que este método de seleção favorece a reprodução dos indiv́ıduos mais

aptos, causando maior pressão seletiva do que todos os outros métodos.

Linden (2008) explica que “a seleção truncada permite que o AG se

concentre somente nas melhores soluções da população, permitindo que se chegue a

uma boa solução de forma mais rápida”. Contudo, por causar maior perda da diver-

sidade, faz com que o AG apresente o pior desempenho e sugere que seja utilizada

em uma estratégia h́ıbrida, no começo da evolução do AG, quando a variedade de

indiv́ıduos ainda é grande.


35

2.5.7 Operadores Genéticos

Os operadores genéticos representam o núcleo de um AG. O objetivo

básico de um operador genético é produzir cromossomos que possuam propriedades

genéticas superiores às encontradas nos cromossomos anteriores (Ochi, 1998).

No Algoritmo Genético, os operadores genéticos convencionais são a

mutação e o crossover. Contudo, existem outras formas não convencionais de obter

variação genética, tais como: inversão, migração e epidemia. Enquanto os operadores

genéticos convencionais são utilizados em todas as gerações do AG, os operadores não

convencionais podem ser acionados ocasionalmente, como artif́ıcio para melhorar a

diversidade genética da população em uma geração espećıfica ou por um determinado

número de gerações.

Em geral, quando os indiv́ıduos de uma população passam a ter cro-

mossomos muito semelhantes, e isso pode ser medido comparando-se as suas ap-

tidões, possivelmente o algoritmo estará convergindo para um ótimo local, e então a

utilização de operadores não convencionais pode ser interessante.

2.5.7.1 Crossover

O operador genético crossover (ou cruzamento) é a fonte de quase

toda a variação genética do AG. Ele permite que novos indiv́ıduos sejam criados e,

portanto, que novos pontos no espaço de busca sejam testados (Koza, 1992).

O crossover inicia-se escolhendo aleatoriamente dois pais da população

intermediária. Em seguida, escolhe-se também aleatoriamente uma posição de corte k

nos cromossomos pais e troca-se as subsequências antes e depois deste local, criando-

se dois filhos. Esta posição de corte k determina a partir de qual locus gênico1

o crossover será efetuado. No exemplo do agricultor com representação inteira,

suponha alguns pais selecionados para o cruzamento, como mostra a Figura (11).

Observe na Figura (11) que existem (lg−1) posições de corte posśıveis

1Lócus gênico representa o local ocupado pelo gene no cromossomo.


36

Figura 11 - Posições de corte posśıveis no cromossomo com representação inteira

para se fazer o cruzamento entre os pais selecionados, em que lg é o número de lócus

gênico que compõem o cromossomo. Se o ponto de corte selecionado for o ponto 1,

o cruzamento produzirá os filhos mostrados na Figura (12).

Figura 12 - Troca de genes entre cromossomos pais realizados a partir do ponto de

corte selecionado

A operação de cruzamento produzirá, portanto, dois filhos. Estes fi-

lhos, em geral, são diferentes de seus pais e diferentes entre śı. Contudo, cada filho

contém algum material genético herdado de seus genitores.

A quantidade de cromossomos a serem submetidos ao processo de

cruzamento é definida pela taxa de crossover pc, especificada pelo usuário e será

discutido na Seção 2.5.8.

Podemos explorar algumas variações do operador crossover, tais como:

� Monogamia ou Poligamia;

� Sexuado ou Assexuado;


37

� Um-ponto, n-pontos e uniforme.

Quando estabelecemos apenas uma posição de corte nos cromossomos

pais, tem-se a estratégia denominada crossover 1-ponto (single-point crossover).

Pode-se também escolher mais de uma posição de corte, e neste caso, tem-se a

estratégia denominada crossover n-pontos (multi-point crossover). No crossover n-

pontos são escolhidas n posições de corte aleatoriamente (1 < n < gl, em que gl é o

número de lócus nos genes), e em seguida realizam-se trocas alternadas de sequências

de genes determinadas pelas posições de cortes. A Figura (13) ilustra um crossover

2-pontos.

Figura 13 - Troca de genes entre cromossomos pais realizados com crossover 2-pontos

Outra possibilidade é, ao invés de trocar segmentos determinados pelas

posições de cortes, criar uma máscara de crossover, operação chamada de crossover

uniforme. Desta forma, para cada gene a ser preenchido nos cromossomos filhos, o

operador de cruzamento uniforme sorteia de qual dos pais este deve ser copiado. A

máscara de cruzamento é uma sequência binária de tamanho G, em que cada valor

associado representa a troca de genes (valor 1) ou não (valor 0). A Figura (14) ilustra

um exemplo de crossover uniforme.

Na monogamia, dois pais são escolhidos da população intermediária


38

Figura 14 - Troca de genes entre cromossomos pais realizados com crossover uni-

forme

para a reprodução apenas uma vez. Isso significa que, após o cruzamento, são retira-

dos da população intermediária e não podem ser sorteados novamente. Nesta forma

de reprodução, a população intermediária deve conter obrigatoriamente um número

par de indiv́ıduos e no mı́nimo 2× pc ×Q indiv́ıduos (em que pc ×Q é o número de

cruzamentos a serem realizados).

No caso da poligamia, o número de indiv́ıduos na população inter-

mediária é independente de ser par e da taxa de cruzamento pc. A cada cruzamento

entre dois indiv́ıduos, eles retornam à população intermediária, podendo ser sele-

cionados novamente para cruzar com outros cromossomos.

O crossover sexuado é aquele que força o algoritmo a escolher 2 pais

distintos para a reprodução. Do contrário, quando permitimos o cruzamento uti-

lizando o mesmo pai, estamos permitindo o crossover assexuado, e que produzirá 2

filhos idênticos ao pai. Esta segunda forma de crossover não tráz variação genética

para a nova população, apenas conduz o algoritmo genético a agir de forma diferente

da primeira. Isto pode ser definido na implementação do algoritmo.

Assim, estas caracteŕısticas podem ser combinadas na implementação

do algoritmo, como por exemplo: Crossover 1-ponto e com Poligamia, ou Crossover


39

3-pontos e com Monogamia.

2.5.7.2 Mutação

Como visto, o operador crossover causa variação nos indiv́ıduos da

população fazendo recombinação dos genes dos cromossomos pais. Contudo, se não

houver diversificação de cromossomos além daqueles já criados e testados, o algoritmo

genético pode convergir para um ótimo local e dali não conseguir escapar. Por isso, o

operador de mutação é fundamental para um AG. É ele que garante a continuidade

da existência de diversidade genética na população, enquanto o operador de crossover

contribui fortemente para a igualdade entre os indiv́ıduos (Linden, 2008).

O operador de mutação força o algoritmo a explorar outras áreas da

região de busca por introduzir mudanças aleatórias, ou mutações, nos cromossomos

(Brandão & Saramago, 2011).

De modo geral, a mutação altera um ou mais genes de um cromossomo

de acordo com uma função de probabilidade, e a frequência de aplicação da operação

de mutação é controlada por um parâmetro chamado probabilidade de mutação, de-

notado por pm (Koza, 1992).

Para todo indiv́ıduo da população intermediária, sorteia-se aleatoria-

mente um valor r uniformemente distribúıdo no intervalo [0, 1] e verifica-se se este

sofrerá mutação comparando r com pm. Para os indiv́ıduos que sofrerão mutação

(quando r < pm), escolhe-se aleatoriamente um lócus do cromossomo (dentre os L

existentes) como posição de mutação. O alelo contido neste lócus será modificado.

Se a representação é binária, o alelo é apenas complementado (Koza, 1992).

Em casos em que a representação do cromossomo é inteira, deve-se

escolher aleatoriamente um novo alelo, diferente daquele existente, para ocupar o

lócus selecionado.

Na Figura (15), selecionou-se aleatoriamente o lócus 2 para a mutação.

Como a representação utilizada é binária, inverte-se o bit 0 para 1, originando um


40

Figura 15 - Mutação aleatória em cromossomo com representação binária

novo indiv́ıduo.

Diferentemente do crossover, a mutação é uma operação assexuada e

que opera em apenas um indiv́ıduo. Além disso, o operador mutação pode agir sobre

uma solução fact́ıvel e torná-la não fact́ıvel, ou vice e versa, por isso, é utilizado com

muita moderação nos AGs.

2.5.7.3 Epidemia

Epidemia, também chamada de Eliminação, é uma operação que im-

plica em, numa determinada geração, eliminar uma porcentagem X de indiv́ıduos

menos aptos da população e gerar novos indiv́ıduos para ocupar seus lugares na

população.

A gravidade da epidemia é quem determina a porcentagem X de in-

div́ıduos que serão eliminados, podendo chegar até a 100%, e neste caso, toda a

população atual será eliminada e substitúıda por uma nova.

Observe que a epidemia, em geral, só terá efeito se utilizada junto

com o Elitismo, em especial quando X = 100%, pois acionar uma epidemia desta

magnitude na g-ésima geração implica em dar ińıcio a um novo AG de apenas (G−g)

gerações (em que G é o número total de gerações e 1 ≤ g ≤ G).

2.5.8 Parâmetros

Outra decisão importante a ser feita na implementação de um AG é

com relação a definição dos valores para os principais parâmetros. São eles: tamanho


41

da população Q, taxa de seleção ps, taxa de crossover pc, probabilidade de mutação

pm e número de gerações G.

O tamanho da população Q determina o número de pontos no espaço

de busca que será explorado por geração no AG. Pode ser um número fixo ou variável,

controlado por alguma função. Reduzir o tamanho da população pode a ocasionar

convergência para um ótimo local ou a convergência mais lenta para um ótimo global.

Por outro lado, maior população implica em maior custo computacional. Estas ideias

também se extendem ao parâmetro G, que determina o número de gerações do AG.

A taxa de crossover pc é um parâmetro definido pelo usuário que deter-

mina, para todas as gerações, o número de cruzamentos entre indiv́ıduos que serão

realizados.Pode ser um valor fixo ou variável, ao longo das gerações, determinado

por um função. Por exemplo, se a taxa de crossover é definida em 60% sobre uma

população de 100 indiv́ıduos, então, a cada geração, ocorrerá 60 cruzamentos. A

taxa de crossover não pode ser muito baixa, pois como visto, é a grande responsável

pela diversificação dos indiv́ıduos na população.

A taxa de mutação pm está associada a chance de um indiv́ıduo sofrer

alteração das suas informações genéticas. Pode ser um valor fixo ou variável, deter-

minado por uma função. Se a taxa pm for baixa demais (próxima de 0), a mutação

agirá de forma extremamente parcimoniosa e a população terá pouca diversificação

nos indiv́ıduos ao longo das gerações (Linden, 2008). Contudo, se a taxa de mutação

for muito alta (próxima de 1), então o AG passará a ter um comportamento parecido

com um algoritmo aleatório e perderá suas caracteŕısticas interessantes.

De modo geral, os parâmetros pc e pm são responsáveis por controlar

a frequência de reprodução na população, e a determinação de seus valores pode

interferir na qualidade da solução obtida pelo algoritmo.

Há uma grande discussão na definição destes parâmetros na literatura.

Mitchell (1992) faz um levantamento dos parâmetros testados por diversos autores

da área e dentre eles, destacam-se experimentos de De Jong, que indicaram como

melhores valores: tamanho da população entre 50−100 indiv́ıduos; crossover 1-ponto


42

a uma taxa de 60%; e probabilidade de mutação de 1%.

Estas configurações tornaram-se amplamente utilizadas nos AGs pela

comunidade. Contudo, estes valores não são comprovadamente os mais eficientes, e

sugere-se ainda mais pesquisas para determinar valores nos quais o algoritmo trabalha

melhor para problemas espećıficos, visto que o controle sobre os parâmetros é de

fundamental importância para uma convergência rápida e global.

2.5.9 Critério de parada

No Algoritmo Genético o processo de reprodução acontece em cada

geração, de forma iterativa, diversificando os indiv́ıduos da população, até que algum

critério de parada seja satisfeito.

O critério de parada é, em geral, expresso em termos do número de

gerações a serem executadas. Neste caso, determina-se um número fixo G de gerações

para a evolução do algoritmo, cujo tempo computacional seja aceitável. Obtém-se ao

final das gerações a melhor solução posśıvel para o pro-blema no tempo estabelecido.

Em problemas em que uma solução ótima pode ser reconhecida, o algoritmo pode

terminar quando tal indiv́ıduo for encontrado (Koza, 1992).

Pode-se ainda estabelecer um número w de gerações em que não se

observa melhoras significativas na solução ótima encontrada até o momento. Neste

caso, é estabelecida uma precisão p no ińıcio do algoritmo que verificará, ao longo

de w gerações, se as soluções encontradas são melhoradas em ao menos um valor p.

2.6 Simulated Annealing (SA)

O método Simulated Annealing (Recozimento Simulado) tem sua fun-

damentação baseada no processo f́ısico de recozimento, no qual substâncias como

metais são fundidos a altas temperaturas e em seguida resfriados lentamente, até

atingirem o estado de congelamento.

Sob altas temperaturas, o material possui uma configuração de alta

energia, em que suas part́ıculas se arranjam de forma aleatória. Mas, durante o


43

Tabela 3: Vocabulários utilizados no processo de recozimento f́ısico e simulado

F́ısica Otimização

Configuração Solução

Configuração de energia mı́nima Solução ótima

Nı́vel de energia Valor da função objetivo

Temperatura Parâmetro de controle

Congelamento Critério de parada

processo de resfriamento, o material passará por diversas configurações de energia

mais baixa, até atingir uma configuração de energia mı́nima, formando um material

sólido, livre de imperfeições.

Em 1983, Kirkpatrick et al. (1983) propuseram esta idéia como es-

tratégia de otimização, e seu desenvolvimento só foi posśıvel a partir de estudos

realizados por Metropolis et al. (1953), que resultou no mais conhecido método de

Monte Carlo, o algoritmo de Metropolis.

O algoritmo de Metropolis é utilizado para simular a mudança do es-

tado de energia de um sistema quando sujeito ao processo de resfriamento, até con-

vergir ao estado de congelamento. Já o algoritmo Simulated Annealing, ao inserir o

fator temperatura no algoritmo de Metropolis, emprega uma sequência de tempera-

turas decrescentes, imitando o processo de recozimento e gerando soluções para um

problema de otimização.

Para se alcançar o estado de energia mı́nimo desejado, deve-se partir

de uma temperatura inicial suficientemente alta e o processo de resfriamento deve

ser suficientemente lento. Isto possibilita explorar melhor o espaço de soluções, e

consequentemente, encontrar a melhor solução que minimiza o problema em questão.

A analogia entre o processo f́ısico e o problema de otimização podem ser resumidos

na Tabela (3).

Na implementação do SA, os principais parâmetros a serem considera-

dos são: temperatura inicial (Tinicial), temperatura final (Tfinal), número de iterações


44

em cada temperatura (L), e taxa de resfriamento (α).

A partir de uma solução inicial s, constrúıda de forma aleatória ou por

uma heuŕıstica construtiva, o processo de recozimento simulado inicia-se com Tinicial

elevada, e a cada temperatura corrente, geram-se soluções até que o equiĺıbrio a esta

temperatura seja alcançado. Este equiĺıbrio é dado pelo número de iterações L na

temperatura corrente.

A cada iteração do método, um novo estado de energia é gerado a partir

do estado corrente, por uma modificação aleatória neste. Isso significa que, a partir

da solução corrente s, determina-se uma vizinhança V (s), escolhe-se aleatoriamente

uma solução s′ ∈ V (s), e avalia-se a função objetivo neste novo ponto.

A variação de energia no sistema obtida do movimento de s para s′ é

expressa em ∆ e pela Equação (6).

∆ = f(s′)− f(s) ≥ 0 (6)

Assim, se a nova configuração s′ é de energia menor que a configuração

corrente s, ou seja, ∆ < 0, a nova configuração passa a ser a configuração corrente,

ou seja, s � s′. Caso contrário, sorteia-se um número aleatório r ∈ [0, 1] e verifica-se

a probabilidade de aceitar um movimento que não é de melhora, dada pela Equação

(7).

P (aceitação) = e−∆/(kT ), (7)

em que k é a constante de Boltzmann e T é a temperatura corrente.

O comportamento da função de probabilidade apresentada na Equação

(7) pode ser observado na Figura (16). Note que em baixas temperaturas movimentos

que não são de melhora são aceitos com probabilidade baixa, enquanto em altas

temperaturas, a chance de aceitação aumenta, a fim de evitar que o algoritmo convirja

para um ótimo local. Na Figura (16) fixou-se ∆ igual a 1, e temperaturas variando

de 1 a 100, com o objetivo de verificar o comportamento da função de um modo mais

geral.

Após L iterações, a temperatura corrente é então rebaixada a uma taxa


45

Figura 16 - Probabilidade de aceitação de movimentos que não são de melhora pelo

algoritmo SA

α, T = αT e o processo prossegue até o congelamento, ou seja, até atingir a mais

baixa temperatura definida em Tfinal, que deve ser suficientemente próxima de zero

(Tfinal ≈ 0).

A sequência de temperaturas empregadas, determinada pela taxa de

resfriamento α (0 < α < 1), juntamente com o número de iterações L a cada tem-

peratura (L > 0), são parâmetros definidos pelo usuário.

Em geral, como o objetivo é obter um resfriamento suficientemente

lento, adota-se α o mais próximo de 1 posśıvel, por exemplo, α = 0, 95. Isso implica

em aumentar o número de temperaturas testadas pelo método, e consequentemente,

haverá mais iterações. Por isso, o número de iterações L deve ser equilibrada ao

número de iterações definidas por α, a fim de se obter um algoritmo com tempo

computacional de execução aceitável.

Este procedimento é repetido até se atingir o estado de congelamento.

Para melhor compreensão do processo, um pseudocódigo para o algoritmo do Simu-

lated Annealing é apresentado na Figura (17).


46

Figura 17 - Pseudocódigo do algoritmo Simulated Annealing

Como estratégia de otimização, o SA é um método de busca local que

permite movimentos que não são de melhora, de acordo com uma probabilidade de

aceitação, possibilitando assim escapar de mı́nimos locais.

2.7 Algoritmos Hı́bridos

Algoritmos h́ıbridos consistem na utilização conjunta de métodos de

otimização exatos e/ou heuŕısticos, combinando suas vantagens a fim de obter me-

lhores soluções. Estes métodos, em geral, visam reunir boas caracteŕısticas de dois

ou mais métodos em um único algoritmo, com o objetivo de melhorar a convergência

e obter melhores soluções para o problema.

A partir da constatação de que nenhum método de otimização é per-

feito, vários sistemas h́ıbridos têm sido propostos. Goldbarg & Luna (2005) fazem

um levantamento de trabalhos que propõem Algoritmos Genéticos combinados com


47

estratégias exatas ou heuŕısticas para resolução de problemas de otimização. Den-

tre estes métodos, destacam-se a combinação do AG com Simulated Annealing, Hill

Climbing, Colônia de Formigas e Busca Tabu.

Para Davis (1991), o resultado da hibridização costuma ser melhor

que o obtido com qualquer uma das duas técnicas isoladamente. Porém, não existe

regra para a combinação dos métodos, depende da complexidade do problema e das

estratégias de otimização conhecidas pelo programador.

Quando utilizamos o Algoritmo Genético como estratégia de

otimização, Ochi (1998) sugere a combinação com alguma estratégia de busca local

ao redor das soluções de elite, fazendo assim um refinamento a partir das melhores

soluções encontradas. Para Goldberg (1989), um caminho eficiente para melhorar

consideravelmente o desempenho de um AG é fazer este refinamento da solução

através do SA.

A partir desta idéia, utilizou-se a estratégia h́ıbrida AG+SA que con-

siste em pegar a melhor solução gerada pelo Algoritmo Genético ao final das gerações

e utilizá-la como solução inicial do Simulated Annealing, que normalmente utilizaria

uma solução inicial constrúıda aletoriamente.


3 MATERIAL E MÉTODOS

Neste caṕıtulo é proposto o estudo e a formulação de um modelo

matemático para o planejamento de plantio em lotes visando reduzir a proliferação

de pragas entre culturas, bem como a resolução do modelo a partir de estratégias

metaheuŕısticas de otimização. O estudo e a implementação das metaheuŕısticas

Algoritmo Genético (AG), Simulated Annealing (SA) e h́ıbrido AG+SA foram reali-

zados.

Para o desenvolvimento das simulações computacionais foi utilizado

o software Matlab R2010a, versão 7.10.0.499, em microcomputadores com proces-

sador Intel Core i3 e 2 GB de memória RAM, em sistema operacional Windows

7. Neste ambiente foram implementadas as estratégias metaheuŕısticas AG, SA

e h́ıbrido AG+SA, e simuladas para duas instâncias do problema, variando-se os

parâmetros de entrada, a fim de se observar a influência destes no desempenho dos

algoritmos.

3.1 Modelagem Matemática do Problema Biológico

Nesta seção é apresentado ummodelo de Programação Não-Linear para

aux́ılio no planejamento otimizado do plantio e cultivo de culturas em determinados

lotes durante um peŕıodo de tempo, de modo que a disposição dessas culturas e/ou

variedades nos lotes favoreça o controle eficiente de pragas. Isto implica em determi-

nar um modelo matemático para o planejamento de plantio e cultivo que minimize

a probabilidade de proliferação de pragas entre as culturas, levando em consideração

restrições de demanda, peŕıodo de cultivo de culturas, ocupação de lotes e tempo de


49

planejamento.

Para a construção do modelo matemático para o problema apresentado

serão considerados os seguintes parâmetros:

� N : número de culturas dispońıveis para o plantio;

� K: número de lotes dispońıveis para o plantio;

� M : número de lotes/culturas circunvizinhos à fazenda de interesse;

� i e ī: ı́ndices relacionados às culturas, i = 1, ..., (N +M) e ī = 1, ..., (N +M);

� j e j̄: ı́ndices relacionados aos lotes, j = 1, ..., (K +M) e j̄ = 1, ..., (K +M);

� A: duração do planejamento, igual para todos os lotes;

� T : quantidade de subdivisões do peŕıodo A;

� t: ı́ndice relacionado ao peŕıodo do planejamento, t = 1, ..., T .

Seja um planejamento de culturas em um peŕıodo A e uma unidade

temporal que divide A em T subpeŕıodos. Construir um planejamento de culturas

de duração A implica em decidir qual cultura deverá ser plantada em cada lote na

unidade de tempo adotada (dia, semana, mês, bimestre, etc). Considera-se que a

área de plantio está subdividida em K lotes e que possui M fazendas circunvizinhas

com M culturas já plantadas.

Para ilustração do problema proposto, considere um planejamento de

culturas no horizonte de 2 anos (A = 2), dividido em 24 meses (T = 24), em que

os subpeŕıodos considerados no modelo, neste caso, variam em t = 1, ..., 24. Assim,

t = 3 refere-se ao 3º mês do planejamento.

Suponha a região ilustrada na Figura (18) em que deseja-se realizar

o plantio de culturas. Os lotes M1, M2, M3 e M4 representam as fazendas cir-

cunvizinhas à área de interesse de plantio. Já os lotes K1, K2, K3, K4, K5 e

K6, representam as subdivisões em lotes da área dispońıvel para plantio. Podemos

observar as seguintes caracteŕısticas da região:


50

Figura 18 - Área hipotética dividida em lotes para planejamento de plantio

� Área dispońıvel para plantio subdividida em K = 6 lotes (K1, . . . , K6);

� Área circunvizinha à região de interesse com M = 4 fazendas e culturas já

fix