UNIVERSIDADE DO RIO GRANDE DO NORTEFEDERAL

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE

CENTRO DE TECNOLOGIA

PROGRAMA DE PÓS-GRADUAÇÃO EM ENGENHARIA ELÉTRICA

ANÁLISE DE CONVERGÊNCIA DEALGORITMOS GENÉTICOS: UMA

ABORDAGEM POR MEIO DE CADEIA DEMARKOV

Luiz Amorim Carlos

Orientador: Prof. Dr. Aldayr Dantas de Araújo

Co-orientador: Prof. Dr. Daniel Aloise

Tese de Doutorado apresentada ao Pro-grama de Pós-Graduação em EngenhariaElétrica da UFRN (área de concentração:Engenharia de Computação) como parte dosrequisitos para obtenção do título de Doutorem Ciências.

Natal, RN, 05 de novembro de 2013

Divisão de Serviços Técnicos

Catalogação da publicação na fonte. UFRN / Biblioteca Central Zila Mamede

Pereira, Fulano dos Anzóis.Sobre a Preparação de Propostas de Tema, Dissertações e Teses no Programa

de Pós-Graduação em Engenharia Elétrica da UFRN / Fulano dos Anzóis Pereira- Natal, RN, 2006

23 p.

Orientador: Sicrano Matosinho de MeloCo-orientador: Beltrano Catandura do Amaral

Tese (doutorado) - Universidade Federal do Rio Grande do Norte. Centro deTecnologia. Programa de Pós-Graduação em Engenharia Elétrica.

1. Redação técnica - Tese. 2. LATEX- Tese. I. Melo, Sicrano Matosinho de. II.Amaral, Beltrano Catandura do. III. Título.

RN/UF/BCZM CDU 004.932(043.2)

Apresentação da Tese de Doutorado noPrograma de Pós-Graduação em Engenharia

Elétrica da UFRN

Luiz Amorim Carlos

Tese de Doutorado aprovada em 05 de novembro de 2013 pela banca examinadora com-posta pelos seguintes membros:

Prof. Dr. Aldayr Dantas de Araújo (orientador) . . . . . . . . . . . . . . . . . DEE/UFRN

Prof. Dr. Daniel Aloise (co-orientador) . . . . . . . . . . . . . . . . . . . . . . . . DCA/UFRN

Prof. Dr. Adrião Duarte Dória Neto . . . . . . . . . . . . . . . . . . . . . . . . . . . DCA/UFRN

Prof. Dr. Dario José Aloise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . DI/UERN

Prof. Dr. Luiz Satoru Ochi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IC/UFF

A minha esposa Aleca e minhasfilhas Talita e Natalia pelo

instimável apoio, constantes ereconfortantes incentivos, fontes

renovadoras de minhas forças.

Agradecimentos

Ao meu orientador e amigo Professor Aldayr Dantas Araújo pela forma dedicada ao meoferecer seu apoio e incentivos, determinantes para a concretização deste trabalho.

Ao co-orientador Professor Daniel Aloise pela forma segura e decidida ao assumir estatarefa de forma tão extemporânea.

Ao Professor André Gustavo, do Depto. de matemática, pelos recorrentes convites àretomada de trabalhos que havíamos feito e que serviram de base para este.

À Coordenação do programa de Pós-Graduação em Engenharia Elétrica e aos serviços desecretaria pelo apoio.

A UFRN que me acolheu em seus quadros de professor e que tanto tem contribuido paraminha formação.

Aos demais colegas e amigos que sempre me depositaram confiança.

Ao Professor Samaherni, do Depto. de Engenharia Elétrica, pela ajuda ao resolver difi-culdades de edição.

À minha família que me deu forças nos frequentes incentivos durante esta jornada.

Resumo

Neste trabalho, a cadeia de Markov será a ferramenta usada tanto na modelagemquanto na análise de convergência do algoritmo genético, tanto na sua versão padrãoquanto nas demais. A escolha deste algoritmo deve-se ao fato do mesmo ter se tornado,nos últimos trinta anos, uma das ferramentas mais usada para achar uma solução do pro-blema de otimização. Esta escolha deve-se à sua comprovada eficácia na busca de umasolução de boa qualidade para o problema, considerando que o conhecimento de uma so-lução de boa qualidade torna-se aceitável tendo em vista que pode não existir um outroalgorimo capaz de obter a solução ótima, para muitos desses problemas. Entretanto essealgoritmo pode ser definido, levando em conta que o mesmo é dependente não apenasda forma como o problema é representado mas também como são definidos alguns dosoperadores, deste sua versão padrão, quando os parâmetros são mantidos fixos, até suasversões com parâmetros variáveis. Por isso, para se alcançar um bom desempenho como aludido algoritmo é necessário que o mesmo tenha um adequado critério na escolha deseus parâmetros, principalmente a taxa de mutação e taxa de cruzamento ou, até mesmo,o tamanho da populaçao. É importante lembrar que aquelas implementações em que parâ-metros são mantidos fixos durante toda a execução, a modelagem do algoritmo por cadeiade Markov resulta numa cadeia homogênea e quando permite a variação de parâmetros aolongo da execução, a cadeia de Markov que o modela passa a ser do tipo não-homogênea.Portanto, na tentativa de melhorar o desempenho do algoritmo, alguns trabalhos têm pro-curado realizar o ajuste dos parâmetros através de estratégias que captem característicasintrínsecas ao problema. Essas características são extraidas do estado presente de execu-ção, com o fim de identificar e preservar algum padrão relacionado a uma solução de boaqualidade e, ao mesmo tempo, descartando aquele padrão de baixa qualidade. As estra-tégias de extração das características tanto podem usar técnicas precisas quanto técnicasnebulosas, sendo neste último caso feita através de um controlador nebuloso. Com o fimde avaliar o desempenho de um algoritmo não-homogêneo, apresenta-se testes onde secompara o algoritmo genético padrão com o algoritmo genético nebuloso, sendo a taxade mutação ajustada por um controlador nebuloso. Para isso, escolhe-se problemas deotimização cujo número de soluções varia exponencialmente com o número de variáveis.

Palavras-chave: Otimização, Cadeia de Markov, Algoritmo Genético.

Abstract

In this work, the Markov chain will be the tool used both in modeling and in the con-vergence analysis of the genetic algorithm. The choice of this algorithm is due to the factthat it has become , over the past thirty years, most of the tools used to find a solution ofthe optimization problem. This choice is due to its effectiveness in finding a good qua-lity solution to the problem, considering that the knowledge of a good quality solutionbecomes acceptable given that there may not be another algorimo able to get the solutiongreat for many of these problems. However, this algorithm can be set, taking into accountthat it is not only dependent on how the problem is represented as but also some of theoperators are defined, the standard version of this, when the parameters are kept fixed, totheir versions parameterized variables. Therefore to achieve good performance with theaforementioned algorithm is necessary that it has an adequate criterion in the choice ofits parameters, especially the rate of mutation and crossover rate or even the size of thepopulation. It is important to remember that those implementations in which parametersare kept fixed throughout the execution, the modeling algorithm by Markov chain resultsin a homogeneous chain and when it allows the variation of parameters during the exe-cution, the Markov chain that models becomes be non - homogeneous. Therefore, in anattempt to improve the algorithm performance, few studies have tried to make the settingof the parameters through strategies that capture the intrinsic characteristics of the pro-blem. These characteristics are extracted from the present state of execution, in order toidentify and preserve a pattern related to a solution of good quality and at the same timethat standard discarding of low quality. Strategies for feature extraction can either useprecise techniques as fuzzy techniques, in the latter case being made through a fuzzy con-troller. A Markov chain is used for modeling and convergence analysis of the algorithm,both in its standard version as for the other. In order to evaluate the performance of a non-homogeneous algorithm presents test which compares the standard genetic algorithm withthe genetic algorithm fuzzy, and the rate of change adjusted by a fuzzy controller. To doso, pick up optimization problems whose number of solutions varies exponentially withthe number of variables.

Keywords: Markov chain, genetic algorithm, fuzzy logic.

Sumário

Sumário i

Lista de Figuras iii

Lista de Tabelas v

1 Introdução 11.1 O algoritmo em análise, suas habilidades e limitações . . . . . . . . . . . 11.2 A ferramenta de modificação do AGP . . . . . . . . . . . . . . . . . . . 21.3 A ferramenta de análise e os requisitos exigidos . . . . . . . . . . . . . . 21.4 Organização do texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

Lista de Símbolos e Abreviaturas 1

2 A otimização: uma visão cronológica 52.1 A otimização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 O crescimento com a onda do computador . . . . . . . . . . . . . . . . . 52.3 Os problemas e suas características . . . . . . . . . . . . . . . . . . . . . 62.4 Classificação pela dificuldade de resolução . . . . . . . . . . . . . . . . . 6

2.4.1 A classe P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.4.2 A classe NP e a inclusão P ⊆ NP . . . . . . . . . . . . . . . . . 72.4.3 A classe NP-Completo . . . . . . . . . . . . . . . . . . . . . . . 7

2.5 Fase determinística versus fase probabilística . . . . . . . . . . . . . . . 82.5.1 A fase determinística . . . . . . . . . . . . . . . . . . . . . . . . 82.5.2 A fase das methaeurísticas . . . . . . . . . . . . . . . . . . . . . 11

3 Ferramentas de contrução e análise 133.1 A lógica nebulosa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2 O conjunto nebuloso e suas funções de pertinência . . . . . . . . . . . . 133.3 Operações com conjuntos nebulosos . . . . . . . . . . . . . . . . . . . . 143.4 A inferência nebulosa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.5 Concepção de um controlador nebuloso . . . . . . . . . . . . . . . . . . 18

3.5.1 O módulo da fuzificação . . . . . . . . . . . . . . . . . . . . . . 183.5.2 O módulo de inferência . . . . . . . . . . . . . . . . . . . . . . . 183.5.3 O módulo de ’defuzificação’ . . . . . . . . . . . . . . . . . . . . 19

3.6 Cadeia de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

i

3.6.1 Definições e propriedades . . . . . . . . . . . . . . . . . . . . . 193.6.2 Ergodicidade da cadeia homogênea . . . . . . . . . . . . . . . . 213.6.3 Ergodicidade da cadeia não-homogênea . . . . . . . . . . . . . . 21

4 A modelagem e análise de convergência 234.1 Os modelados AGH e AGNH . . . . . . . . . . . . . . . . . . . . . . . 234.2 O problema e o formato . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.3 A modelagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.4 Análise de convergência . . . . . . . . . . . . . . . . . . . . . . . . . . 28

4.4.1 Quando a cadeia é do tipo AGH . . . . . . . . . . . . . . . . . . 284.4.2 Quando a cadeia é do tipo AGNH . . . . . . . . . . . . . . . . . 29

4.5 A abordagem e os resultados . . . . . . . . . . . . . . . . . . . . . . . . 31

5 Um estudo de caso: AGH versus AGNHn 335.1 O AGNHn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335.2 O Controlador nebuloso usado no AGNH . . . . . . . . . . . . . . . . . 33

5.2.1 O módulo de ’fuzificação’, para o AGNHn . . . . . . . . . . . . 345.2.2 O módulo de inferência, para o AGNHn . . . . . . . . . . . . . . 385.2.3 O módulo de ’defuzificação’, para o AGNHn . . . . . . . . . . . 38

5.3 Os problemas testes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.3.1 Os resultados obtidos e sugestões para novos testes . . . . . . . . 39

Referências bibliográficas 42

Lista de Figuras

3.1 Pertinência do antecedente . . . . . . . . . . . . . . . . . . . . . . . . . 173.2 Pertinência do consequente . . . . . . . . . . . . . . . . . . . . . . . . . 17

5.1 AGNH + CONTROLADOR NEBULOSO = AGNHn . . . . . . . . . . . 345.2 Pertinência de ng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355.3 Pertinência de dp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.4 Pertinência da taxa de mutação . . . . . . . . . . . . . . . . . . . . . . . 375.5 função 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.6 função 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.7 função 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.8 função 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.9 função 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.10 função 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

iii

Lista de Tabelas

v

Capítulo 1

Introdução

Neste capítulo apresenta-se o algoritmo em estudo destacando-se suas qualidades, li-mitações, ferramentas de melhoria e de análise de eficácia. Todas as ferramentas referidasterão seus detalhes apresentados em seção própria, conforme o caso exija.

1.1 O algoritmo em análise, suas habilidades e limitações

Este trabalho destina-se à análise do algoritmo genético, AGP, descrito em [Holland1975], e o faz pelas razões, a seguir destacadas, que têm levado o mesmo a ser um dosmais usados algoritmos, com o fim a que ele se destina, dos últimos 20 anos.

A primeira habilidade destacável do algoritmo é a capacidade que o mesmo tem de-monstrado em obter uma solução de boa qualidade para o problema a que ele se destina,o problema de otimização. Ressalte-se que, para esse tipo de problema, a satisfação poruma solução de boa qualidade, em lugar da solução ótima, deve-se à limitação teórica,muitas vezes imposta pelo problema, limitação essa que será abordada posteriormente emseção própria.

A segunda habilidade é a abrangência do campo de aplicação do algoritmo, decorrentedo seu caráter adaptativo ao permitir seu uso em formas diferentes de representação doproblema. Este caráter está associado aos conceitos de genótipo e fenótipo que o mesmofaz uso, possibilitando, com isso, sua aplicação em problemas dos mais variados matizes.

A terceira habilidade vem do fato do algoritmo genético padrão, tal como descritoem [Michalewicz 1992], aqui denominado por AGP, permitir múltiplas possibilidades deconfiguração para os seus operadores de seleção, de cruzamento e de mutação. Nestecaso, o caráter adaptativo é reafirmado, permitindo, com isso, a busca por uma melhorconfiguração a tornar o algoritmo mais eficaz. Contudo esta habilidade traz enormesdificuldades para a busca desses valores dos parâmetros que confirmem o equilíbrio a setraduzir em um bom desempenho, sem contar, é claro, com a garantia de solução ótima,limitação de caráter teórico, associada à eficiência temporal.

Por isso, considera-se que o tema não é apenas estimulante mas também aberto apossibilidades de melhoria.

2 CAPÍTULO 1. INTRODUÇÃO

1.2 A ferramenta de modificação do AGPComo já foi dito, o algoritmo genético pede adequadas regas na escolha de seus parâ-

metros e estas regras tanto podem produzir, ao longo da evolução, parâmetros constantescom podem produzir parâmetros variáveis. No caso de parâmetros fixos o que se tem feitoé usado indicações da literatura, como em [Michalewicz 1992, Goldberg 1989]. Para ocaso de parâmetros variáveis, quando exige a definição do valor a ser usado em cada itera-ção do algoritmo, algumas estatégias têm sido usadas, podendo estas serem classificadaspor estratégias precisas, como em [Campos, Pereira, Carlos e de Assis 2012], ou estra-tégias nebulosas, como em [Cavalheiro 2003, Burdelis 2009]. A estratégia nebulosa éconstruída com elementos da lógica nebulosa, definida em [Zadeh 1965].

A lógica nebulosa, cujos detalhes serão apresentados em seção própria, é fundamen-tada em argumentos imprecisos, possibilitando a emulação de um operdor, através de umconjunto de regras que representam a experiência do operador, na operação do instru-mento a ser operado. Esse conjunto de regras quando usado juntamente com uma regrade inferência constituem o núcleo do que se chama controlador nebuloso e é com esseinstrumento, descrito em seção própria, que se busca a melhoria do algoritmo do AGP,resultando no AGNHn.

É com o uso dessa estratégia, na definição do parâmetro de mutação, que o algoritmogenético padrão, AGP, é modificado dando lugar ao algoritmo genético nebuloso - AG-NHn. Acredita-se que esta escolha, por impor um caráter endógeno, evita que fatoresexternos possam reduzir o desempenho do algorimo, possibilitando um bom equilíbrioentre diversificação e intensificação, instrumentos basilares para um bom desempenho doalgoritmo.

1.3 A ferramenta de análise e os requisitos exigidosComo o algoritmo a ser modificado é o AGP e em virtude de sua modelagem ser feita,

em seção própria, por cadeia de Markov homogênea, o mesmo pode ser também denomi-nado por algoritmo genético homogêneo - AGH. Em virtude da modificação pretendida,seja pelo uso da ferramenta descrita em 1.2 ou qualquer outra, permitindo a variação dataxa de mutação, resultar em um algoritmo cuja cadeia de Markov que o modela é dotipo não-homogênea, sua denominação passa a ser algoritmo genético não-homogêneo -AGNH.

A cadeia de Markov, cujos detalhes técnicos serão apresentados em seção própria,será o instrumento de análise de convergência dos algortimos. A escolha desta ferramentase dá não apenas por ser ela adequada à análise de processos estocásticos que levam essenome mas também em vista de sua abrangência, já que a mesma pode ser usada, para o fimdeclardo, tanto no algoritmo AGH, com seus parâmetros fixos, como em [Rudolph 1994]e em [Neto 2010], quanto no AGNH, com seus parâmetros variáveis, como em [Campos,Pereira, Carlos e de Assis 2012, Campos, Pereira e Rojas Cruz 2012].

Sendo a cadeia modeladora, do AGNH, do tipo não-homogênea, os requisitos de con-vergência para a mesma vão além dos exigidos para o caso da cadeia do tipo homogênea,o caso do AGH.

1.4. ORGANIZAÇÃO DO TEXTO 3

Essas condições precisam ser garantidas afim de garantir a convergência dos algorit-mos, em especial para o caso não-homogêneo do tipo nebuloso, AGNHn, por ser este oobjetivo da tese.

1.4 Organização do textoNo capítulo 2 procura-se contextualizar o tema dando elementos para a classificação

de problemas e de algoritmos, com o fim de mostrar a importância e a necessidade dacontribuição oferecida. No capítulo 3 apresenta-se as ferramentas usadas, tanto na cons-trução da proposta quanto na análise. No capítulo 4 apresenta-se os algoritmos, padrão -AGP/AGH e o nebuloso - AGNHn e suas respectivas modelagens e, em seguida, faz-se asanálises de convergências dos algoritmos. Por fim, no capítulo 5, apresenta-se um estudode caso para comparar os desempenhos, AGH × AGNHn, dos algoritmos analisados.

4 CAPÍTULO 1. INTRODUÇÃO

Capítulo 2

A otimização: uma visão cronológica

Neste capítulo pretende-se dar uma ambicosa contribuição ao oferecer uma visão geralda otimização, desde os primórdios até o seu estado atual, apresentando cronologicamenteo seu desenvolvimento através de seus expressivos resultados.

2.1 A otimizaçãoA otimização é uma área da metemática aplicada que cuida tanto da modelagem de

problemas quanto da geração de algoritmos. Esses problemas constituem o desejo deotimização de sistemas para os quais se buscam modelos enquanto os algoritmos são osinstrumentos com os quais se pretende dar respostas a esses modelos, buscando em cadauniverso uma solução ótima para o mesmo. A otimalidade é obtida por algum critériochamado objetivo, definido e dependente das variáveis do modelo, que assumem valoresno universo do mesmo.

2.2 O crescimento com a onda do computadorA despeito de já existir o conhecimento de técnicas, desde o século 18, capazes de

oferecer algoritmos que levem à solução do problema, estes algoritmos consideram ape-nas características associadas à existência e unicidade de solução sem levar em conta adificuldade de resolução do problema associada à cardinalidade do conjunto de soluçõespossíveis que, a depender desta, pode levar a não aceitação do algoritmo, em vista dotempo que o mesmo gasta para oferecer a solução ótima. Ao tempo, sem o computa-dor, só era possível realizá-las à mão e, em consequência, para problemas com um baixograu de dificuldade. Mas esses casos nunca despertaram interesse pois os problemas reaistêm, quase sempre, um grande número de soluções possíveis a ponto de, em muitos ca-sos, exponencial, demandar cálculos que só se tornaram realizáveis com o surgimento docomputador. Por isso, o crescimento da otimização se deu casado com o surgimento docomputador, e o aumento da capacidade de cálculo do computador fez reduzir em muitoas limitações no desenvolvimento de novos algoritmos, apesar de persistirem outras difi-culdades inerentes ao problema e invariantes com esse movimento, como nos chamadosproblemas não-polionomiais.

6 CAPÍTULO 2. A OTIMIZAÇÃO: UMA VISÃO CRONOLÓGICA

2.3 Os problemas e suas característicasEsses problemas têm origem nas mais variadas áreas do conhecimento humano, como

em tarefas de engenharia elétrica, de engenharia de produção, de computação, etc., comorelatam [Rockafellar 1972, Salkin 1975, Gill et al. 1981, Chvátal 1983, Nemhauser eWolsey 1988] e têm diferentes características, em vista da presença ou não das mais va-riadas características das funções envolvidas no modelo, tais como linearidade, convexi-dade, diferenciabilidade e também em relação ao domínio do modelo, podendo este serirrestrito ou restrito e ainda contínuo ou discreto. Cada uma dessas características em-prestam o nome aos problemas entretanto a classificação, de acordo com a dificuldade deresolução, é como segue.

2.4 Classificação pela dificuldade de resoluçãoNesta seção apresenta-se uma pequena amostra à classificação dos problemas de oti-

mização, pela dificuldade na sua resolução e, com isso, identifica-se classes que dão o realsentido da busca por um algoritmo pseudo eficiente, o que inevitavelmente tem levado aouso das mathaeurísticas, dentre estas o algoritmo genético.

O problema, a instância e seu tamanho

A modelagem matemática oferece o modelo ou, como se costuma chamá-lo, o pro-blema de otimização. Esse modelo ou problema, Γ, é caracterizado por uma estrutura dedados, um conjunto de regras, que estabelecem como esses dados se relacionam e comodevem ser processados em busca da solução através de um critério ou objetivo que definea qualidade da solução encontrada. Cada atribuição à estrutura de Π, por um particularconjunto de dados, é chamada de instância, Γ, do problema Γ, ou, por facilidade, pode-seusar a representação γ ∈ Γ. Portanto cada problema de otimização, Γ, tem a si associa-das suas infinitas instâncias, γ′s, e cada uma dessas com tamanho de representação finito.Quando admitida a representação binária o tamanho da instância será o inteiro da formaκ(n) = ∑

ni=0 δi2i, sendo δi = 0 ou 1, para algum n.

O critério de classificação

Para este fim, alguns critérios têm sido usados e dentre esses tem se destacado o crité-rio do pior caso, a despeito do critério do caso médio, por este oferecer, em alguns casos,dificuldade na sua caracterização. O critério do pior caso, como o próprio nome declara,usa a estratégia de definir a dificuldade de resolução de Γ pela dificuldade de resoluçãoda instância, γ ∈ Γ, mais desfavorável possível. Em vista disso, considere as definiçõesseguintes.

Algoritmo polinomial

Considere o polinômio de grau m, pm(x) = ∑mi=0 δixi, sendo δi = 0 ou 1, e seja o

inteiro, κ(m) = pm(2), descrito antes como tamanho da instância.

2.4. CLASSIFICAÇÃO PELA DIFICULDADE DE RESOLUÇÃO 7

Um algoritmo A destinado a resolver um problema Γ é dito ter ordem polinomial, ousimplesmente se diz A que A é O(κ(m)n), quando A resolve qualquer instância γ ∈ Γ detamanho κ(m) no tempo pn(κ(m)), quando é satisfeita a condição κ(m) ≤ αpn(κ(m)),para todo n ≥ m, algum α > 0 e todo γ ∈ Γ. Neste caso a função κ(m)n é chamada decomplexidade do algoritmo A e dita polinomial e, em consequência, o problema, Γ, étambém assim chamado.

2.4.1 A classe P

Esta classe é constituída dos problemas Γ para os quais se conhece um algoritmo poli-nomial que resolve qualquer instância γ∈ Γ. Dentre muitos estão os problemas: resoluçãode sistema linear, o problema da árvore gerdora mínima, o problema de programação li-near, etc.

Com a constatação da existência de problemas não pertencentes à classe P, ainda quepossam vir a pertencerem, se faz necessário a definição uma classe mais abrangente quea classe P, como a classe NP a seguir definida.

O problema de decisão

Para se chegar à definição de NP define-se inicialmente o problema de decisão, comosendo aquele cuja solução é apenas o SIM ou o NÃO. Portanto a cada problema Γ define-se um problema de decisão associado a Γ como sendo o problema dado pela inclusãoγ ∈ Γ. Observe, que em vista da infinidade de problemas de decisão, γ ∈ Γ, a resposta,em tempo polinomial, a esse problema seria dada com um hipotético conjunto de infinifascópias de um algoritmo polinomial, rodando em paralelo. Este procedimento é o quepassou a ser chamado algoritmo não-determinístico polinomial. Maiores detalhes sobre otema podem ser encontrados em [Garey e Johnson 1979, Papadimitriou 1982, Nemhausere Wolsey 1988, Ribeiro 1998]. Em vista disso, a definição seguinte.

2.4.2 A classe NP e a inclusão P ⊆ NP

A classe NP é constituída dos problemas Γ para os quais qualquer problema de decisãoassociado a Γ seja resolvido por um algoritmo não-determinístico polinomial, ou seja,basta que o problema de decisão associado a Γ seja polinomial, para qualquer Γ ∈ NP.Observe que esta exigência não é dirigida a Γ mas ao problema de decisão associado aΓ. Assim definida, fica claro que a relação entre P e NP fica dada por P ⊆ NP. Portantopode-se dizer que NP é constituída dos problemas, Γ, para os quais não se conhece umalgoritmo polinomial que o resolva.

Muitos problemas, como fizeram em [Cobham 1964, Edmonds 1965a, Edmonds 1965b,Edmonds e Johnson 1970, Edmonds e Karp 1972, Edmonds e Johnson 1973], foram intro-duzidos nessa classe, os quais deram motivos para que se chegasse ao resultado seguinte.

8 CAPÍTULO 2. A OTIMIZAÇÃO: UMA VISÃO CRONOLÓGICA

2.4.3 A classe NP-CompletoNo desejo de descrever o universo dos problemas, a partir da intratbilidade dos mes-

mos, torna-se inevitável partir do trabalho de Alan Turing com os seus problemas demais alto grau de intratabilidade denominados de problemas indecidíveis, porque não háqualquer algoritmo que os resolva, como o seu legítmo representante, o chamdo pro-blema da parada. Entretanto ao se restringir ao universo da otimização, tratando-se deproblemas decidíveis, em 1971 Stephen Cook em seu destacado trabalho, [Cook 1971a],definiu a classe NP−Completo e introduziu o seu primeiro representante, o problema dasatisfabilidade-SAT. Esta classe é portanto constituída dos problemas, de NP, que são tãointratáveis quanto o problema SAT. Posteriormente outros problemas foram sendo intro-duzidos, como fez R. M. Karp em [Karp 1972] e outros, fazendo a classe crescer tanto quequalquer tentativa de descrição da mesma seria muito enfadonho. A seguir apresenta-se aárvore de redução, cujos detalhes podem ser encontradas em [Garey e Johnson 1979]

SAT↓

3SAT

3DM - 3-Dimensional Matching VC - Cobertura de vértice↓

Partition HC-Hamiltonian circuit Clique

Todas essas introduções são feitas com a técnica de redução polinomial pela qualum primeiro problema é transformado em um segundo, por meio de uma transformaçãoem tempo polinomial, determinando, com isso, que a intratabilidade do primeiro é dadapela intratabilidade do segundo, ou seja, se um problema da classe NP−Completos forintroduzido na classe P, serão todos os outros.

A despeito da classificação dada acima, uma outra classe que merece destaque, emvista do objetivo deste trabalho, é a que classifica, os problemas e os algoritmos que sedestinam a resolvê-los, levando em conta as características descritas na seção 2.3, comosegue.

2.5 Fase determinística versus fase probabilísticaDentre tantas características que podem ser usadas para classificar os algoritmos de

otimização, duas classes serão aqui escolhidas, a saber, a classe dos algoritmos que têm ocaráter determinístico e a classe dos algoritmos que têm o caráter probabilístico.

2.5.1 A fase determinísticaOs algoritmos desta fase, que vai até o fim dos anos 60 ou início dos anos 70, além

de terem caráter predominantemente determinístico são monotônicos, devido ao fato dapassagem da solução presente para a próxima ser sempre motivada pela melhoria no cri-tério ou função objetivo. Também não se pode deixar de notar a explícita separação entre

2.5. FASE DETERMINÍSTICA VERSUS FASE PROBABILÍSTICA 9

métodos que são dirigidos a problemas irrestritos e métodos que se dirigem a problemascom restrições, podendo ainda, estas restrições, serem de igualdade ou de desiguldades.

As características determinísticas desses algoritmos, sejam para problema irrestritoseja para problema com restrições, devem-se, em parte, ao uso de condições de caracte-rização de ótimos, que o fazem apenas para ótimos locais a não ser em condições espe-ciais como, por exemplo, quando se tem a convexidade ou informação sobre curvatura.Estas condições, há muito, foram estabelecidas pela matemática com hipótese de dife-renciabilidade, tanto para o caso irrestrito com o conceito de ponto crítico, como em[Fletcher 1980], quanto para o caso com restrições de igualdade, com o resultado esta-belecido, para os chamados problemas com vínculos dados em cursos de cálculo, pelascondições dos chamados multiplicadores de Lagrange.

Para o problema com restrições de desiguldade as condições de caracterização fo-ram obtidas, também com a hipótese de diferenciabilidade, nas conhecidas condições deKarush-Kuhn-Tucker, apresentadas em [Kuhn e Tucker 1951], com abordagem tambémem [Avriel 1976, Bazaraa e Shetty 1979, Fletcher 1981]. Estas condições são uma gene-ralização das condições de Lagrange, já referidas e obtidas para restrições de igualdade.Também não se pode deixar de lembrar o uso do conceito de quase -diferenciabilidade,presente nos problemas do tipo max-min, cuja caracterização de ótimo local é dada pelainclusão do subgradiente nulo no conjunto convexo chamado de subdiferencial. Os con-ceitos de subgradiente, obtido pela generalização do conceito de gradiente, e de subdife-rencial podem ser vistos em [Rockafellar 1972].

De início, devido à natureza bivalente do domínio do problema, podendo ser contínuoou discreto, nota-se também, por pesquisadores da área, uma repercussão dessa bivalên-cia a gerarem algoritmos dirigidos tanto a problemas contínuos quanto para problemasdiscretos.

Quando o problema é contínuo

Por oferecerem uma menor dificuldade na sua resolução, os problemas irrestritos e,portanto não lineares, foram os primeiros a terem algoritmos destinados à sua resolução,haja vista o método da máxima descida, ’steepest descent method’, atribuído ao matemá-tico Cauchy, que faz uso do gradiente da função para definir a direção de busca, métodoesse que só se tornou efetivo quando auxiliado por mecanismos de busca linear do tipoencontrado em [Goldstein 1965, Armijo 1966]. Ainda no caso de problema irrestrito seregistra a existência de métodos que não usam a derivada, como em [Nelder e Mead 1965].

Com a introdução de restrições o problema tem o grau de dificuldade aumentado equando trata-se do problema de programação linear o destaque é inevitável devido aométodo simplex, publicado por G. B. Dantzig no início dos anos 50, com detalhes em[Dantzig 1963, Chvátal 1983]. Este método foi durante muito tempo usado e comportava-se, na prática, como um algoritmo polinomial, entretanto devido ao trabalho de [Klee eMinty 1972] onde apresentaram um exemplo, que pode ser visto em [Chvátal 1983], parao qual o método não apresenta comportamento polinomial, chegando a realizar 2n−1 ite-rações. Por isso, o problema de programação linear não podia ser incluído na classe dosproblemas polinomiais. Mas, no final da década de 70, esse foi definitivamente introdu-zido na classe dos problemas polinomiais com um trabalho de grande repercussão, devido

10 CAPÍTULO 2. A OTIMIZAÇÃO: UMA VISÃO CRONOLÓGICA

a [Khachiyan 1979] e, posteriormente, com a versão oferecida por [Karmarkar 1984], ba-seado trabalho de [Dikin 1967], a classe de métodos de pontos interiores, cujos detalhespodem ser vistos em [Gonzaga 1989], tornaram-se bastante promissores e o simplex final-mente passou a ter um concorrente no critério de eficiência. Ainda nos anos 80 esses mé-todos foram estendidos à classe dos problemas convexos, como em [Ye 1987] e [Gonzagae Carlos 1990].

Talvez pelo fato da introdução de restrições representar aumento na dificuldade deresolução do problema, no caso de restrições não -lineares, as primeiras tentativas emresolvê-lo tenha sido no sentido de eliminar o efeito das mesmas, tratando-as de formaimplícita, com técnicas do tipo barreira e do tipo penalidade, cujos detalhes podem servistos em [Gill et al. 1981].

Posteriormente, para o caso de restrições não-lineares, uma outra estratégia bastanteusada foi a estratégia de conjunto ativo, com o fim de definir uma direção de busca. Umavez conhecido o conjunto ativo gera-se, com ele, um subproblema decorrente da reduçãodo problema a algumas de suas variáveis, definidas pelo conjunto ativo, no qual somentealgumas das variávies do problema original são livres. Com isso, define-se a direção debusca pela projeção do gradiente da função objetivo sobre o espaço tangente das restriçoesativas. Essa classe de métodos chamados de métodos do gradiente projetado, apresentadapor [Rosen 1960], certamente teve sua inspiração no algoritmo simplex, já conhecido àépoca. Entretantno esses métodos oferecem uma dificuldade devido ao fato da projeçãodo gradiente, sobre o espaço tangente, mesmo sendo uma direção de busca que garantaa melhoria do critério, pode gerar inviabilidade. Por isso, os métodos do tipo gradienteprojetado, quando usados em retriçoes não-lineares, precisam usar algum critério, cha-mado função mérito, que reflita o grau de curvatura das restrições, a fim de corrigir, tantoquanto possível, a inviabilidade gerada.

Por último, pode-se afirmar que o determinismo por uma solução que garanta umamelhoria no critério, quando comparado com o valor da solução presente, é o traço comumde todos esses métodos e esse mesmo caráter monotônico continua presente nos métodosdirigidos ao problema com quase -diferenciabilidade, onde a direção de busca, neste caso,é um sub -gradiente, pertencente ao sub -diferencial, ver detalhes em [Rockafellar 1972].Esses métodos são os chamados métodos do tipo feixe ’bundle method’, cujos detalhespodem ser vistos nos trabalhos de [Lemarechal 1980].

Quando o problema é discreto

Essa é uma classe de problemas que tem ocupado grande parte da comunidade depesquisadores. Este fato se deu não apenas por estarem, os problemas, presentes em mui-tas áreas da atividade humana e por permitirem assim a molelagem de muitos problemasreais. Dentre esses problemas, alguns representantes que merecem destaque, pelo ele-vado grau de dificuldade na sua resoulção, dado pelo elevado número de soluções viáveis,como é o caso, talvez mais famoso, do problema do caixeiro viajante.

Esses problemas podem ser modelados como um problema de programação inteira,quando suas variáveis assumem apenas valores inteiros, ou podem ser modelados, equi-valentemente, como problemas em que suas variáveis assumem apenas os valores 0 ou 1,por isso, de domínio representado por [0,1]n, para n variáveis. Dado o elevado número de

2.5. FASE DETERMINÍSTICA VERSUS FASE PROBABILÍSTICA 11

soluções possíveis, os algoritmos usam a idéia de descarte de soluções, definido por al-gum critério de descarte de soluções, que não mais mereçam ser cogitadas em vista dessecritério.

Um desses métodos é o método de corte que se destina à resolução do problema li-near inteiro e tem por base a relaxação da condição de inteiro. Tratando-o como se seudomínio fosse contínuo, resultante da envoltória convexa das soluções inteiras, podendoeste ser resolvido pelo simplex, para gerar uma cota, conforme o caso, superior (ou in-ferior) para o problema de minimização (ou maximização) e posteriormente se introduzseguidamente corte, que não descarte a solução ótima mas que descarte soluções não pro-missoras, gerando, com esses cortes, uma sequência de soluções que se espera inteirase tão mais próxima quanto se desejar da solução ótima. Maiores detalhes sobre essesmétodos podem ser vistos em [Salkin 1975].

Um outro, talvez o mais importante método que usa o critério de descarte de solução,por ter em alguns casos um desempenho satisfatório, é o chamado método ’branch andbound’. Estes algoritmos definem um ramo (’branch’) de problemas a ser explorado e fazdescarte desse ramo com base no uso do limitante (’bound’), adequado ao caso limitanteinferior(limitante superior).

2.5.2 A fase das methaeurísticasEsses algoritmos passaram a ser chamados de methaeurísticas por terem um traço

comum pois, diferentes dos determinísticos, perdem o caráter monotônico, quando a evo-lução já não é mais motivada pela melhoria no valor do critério mas evoluem com baseem alguma medida de probabilidade de sucesso. O primeiro algoritmo de otimização ausar essa estratégia foi o ’simulated annealing’, devido a [Kirkparick et al. 1983]. De-pois deste, agora não mais gerando apenas uma sequência de pontos e sim uma sequênciade amostras de pontos, os quais evoluem a partir de uma amostra de elementos viáveis,identificano nela, por meio de algum critério escolhido, elementos que tenham chancede serem bons ótimos locais mas também introduzindo na mesma novos pontos paraque tenha essa chance aumentada. Dentre esses, o método de busca tabu, devido a[Glover 1986, Hansen 1986], cujos detalhes podem ser vistos em [Glover e Laguna 1993],algoritmo genético devido a [Holland 1975], GRASP devido a [Ribeiro 1998], o coloniade formiga de [Dorigo et al. 1996], dentre outros.

Esta estratégia, a despeito de permitir que se possa ir para uma solução de valor desfa-vorável, tem a finalidade de fugir de ótimos locais permitindo que se visite outras regiõespromissoras. Com isto, constata-se que os algoritmos perdem o ímpeto por uma solu-ção local, para evitar que venham a ficar presos em ótimos locais de baixa qualidade e,ao mesmo tempo, sem esquecer que todo ótimo global é também local, a busca por esteprecisa ser enfrentada. Por isso, o controle entre a necessidade pela busca de um ótimolocal e a intensidade com que se realiza essa busca é o que se chama, respectivamente, deintensificaçao e diversificação. Portanto, um bom algoritmo é aquele que encontra umasolução tão boa quanto possível, exigindo com isso um bom equilíbrio entre diversificaçãoe intensificação.

5

12 CAPÍTULO 2. A OTIMIZAÇÃO: UMA VISÃO CRONOLÓGICA

Capítulo 3

Ferramentas de contrução e análise

Neste capítulo apresenta-se os elementos da lógica nebuloso e do controlador ne-buloso para com este definir o algoritmo genético nebuloso, resultante da junção doAGP/AGH, tal como descrito da seção 4.1, com o controlador nebuloso. Por fim apresenta-se a cadeia de Markov que será o instrumento de análise do algoritmo proposto.

3.1 A lógica nebulosaA lógica nebulosa, introduzida por Zadeh, em [Zadeh 1965], está para a teoria de

conjunto nebuloso da mesma forma que a lógica clássica está para a teoria clássica deconjuntos. Na teoria clássica, um conjunto X é uma coleção de elementos x de um dadouniverso U , onde se define a proposição clássica, x ∈ X , para a qual o valor lógico é SIMou NÃO aos quais se associa, respectivamente, aos valores 1 ou 0, também chamadosde grau de pertinência do elemento x ao conjunto X . Portanto a exentão sugerida porZadeh permite que o grau de pertinência, agora diferente de 0 e 1, assuma valores nointervalo [0,1] e, em consequência, permite-se que se defina para x , agora nebuloso, aproposição nebulosa x ∈ X , cuja avaliação agora é multi-valorada ou imprecisa. Paramelhor esclarecer sobre a necessidade de tal extensão, sabe-se que a lógica clássica gerasituações indesejáveis quando, por exemplo, se padroniza que uma pessoa é consideradabaixa quando sua altura vai até 1.50m e, portanto, quem tem altura 1.51m, nesse padrão,já é considerado alto, mesmo julgamento dado a quem tem altura 1.70. A lógica nebulosatrata esse tipo de inadequação, respeitando a ordem natural de altura, através de grauvalorado de pertinência, permitindo que a pessoa que tenha a altura 1.51 seja tambémconsiderada baixa mesmo que tenha grau de pertinência menor do que a que tem altura1.50, mas também permite que essa mesma pessoa, de altura 1.51, possa também serconsiderada alta, com grau de pertinência mais alto do que aquela pessoa que tem altura1.50.

3.2 O conjunto nebuloso e suas funções de pertinênciaOs resultados pretendidos na seção 3.1 serão alcançados com a caracterização dos

conjuntos nebulosos Ui ⊆U , sendo ∪Ui = U e ∩Ui 6= /0, através das respectivas funções

14 CAPÍTULO 3. FERRAMENTAS DE CONTRUÇÃO E ANÁLISE

de pertinência µi : U → [0,1] definida pela função

µi(x) =

µ j(x) quando µ j(x) ∈ (0,1]0 caso contrário

sendo Ui também chamado de conjunto de valor linguístico i, e as funções µ j : Ui→ [0,1],ambos definidos convenientemente, tanto na sua forma quanto na quantidade. Observeque a lógica clássica torna-se um caso particular da nebulosa quando nesta existe apenasum valor linguístico, ou seja, ∪Ui =U , e µi : Ui→0,1.

3.3 Operações com conjuntos nebulososNesta seção apresenta-se as principais operações entre conjuntos nebulosos. Estas

operações, a exemplo do que se faz na lógica clássica com a função característica, sãofeitas através de suas funções de pertinência. Portanto, nas definições seguintes considera-se que os conjuntos A e B serão caracterizados pelas respectivas funções de pertinência µAe µB. Sendo assim, seguem as definições dos operadores básicos de conjuntos e algumasde suas propriedades, cujos detalhes podem ser encontrados em [Zadeh 1965], onde foramlançadas.

A igualdade - A = B

Ocorre a igualdade entre os conjuntos A e B quando as funções de pertinência têm omesmo domínio e µA = µB, em todo o domínio.

A inclusão - A⊂ (⊆)B

A inclusão, A⊂ (⊆)B, se dá quando as funções de pertinência satifazem a µA < (≤)µB.Neste caso o domínio de µA está contido, podendo ser o próprio ou não, no domínio deµB.

União de conjunto - ∪

Define-se A∪B pela função de pertinência

µA∪B = maxµA,µB

sendo esta operação associativa, A∪ (B∪C) = (A∪B)∪C.

Interseção de conjuntos - ∩

Define-se A∩B pela função de pertinência

µA∩B = minµA,µB

que também é associativa, A∩ (B∩C) = (A∩B)∩C.

3.3. OPERAÇÕES COM CONJUNTOS NEBULOSOS 15

Com os operadores acima também vale a distributividade,

A∩ (B∪C) = (A∩B)∪ (A∩C)

A∪ (B∩C) = (A∪B)∩ (A∪C)

O complementar de A - Ac

Define-se Ac pela função de pertinência

µAc = 1−µA

Agora, com os operadores definidos acima, pode-se verificar a satisfação das leis deDe Morgan,

(A∪B)c = Ac∩Bc

(A∩B)c = Ac∪Bc

Diferença simétrica A−B

Este conjunto é caracterizado pela pertinência µ(A−B) = |µA−µB|

Generalizando os operadores

Em vista da operação (∩), realizada pelo operador descrito acima, poder também serrealizada pelos operadores:

1. Produto - µA∩B = µA ·µB;2. Por Lukasiewicz - µA∩B = max0,µA +µB−1

dentre outros.Com o operador, Tn, chamado t-norma,

Tn : µA(U)×µB(U)→ [0,1]

por Tn(µA,µB) = µA∩B, satisfazendo às seguintes condições:

1. Comutativa: Tn(a,b) = Tn(b,a)2. Associativa: Tn(a,Tn(b,c)) = Tn(Tn(a,b),c)3. Elemento neutro: Tn(1,a) = Tn(a,1) = a4. Monotonicidade: Tn(a,b)≤ Tn(c,d) quando a≤ c e b≤ d

faz cada um dos outros um caso particular deste.De forma similar, quando for o caso da operação (∪), como a mesma também pode

ser realizada pelos operadores:

1. Por soma-produto - µA∪B = µA +µB−µA ·µB2. Por dual de Lukasiewicz - µA∪B = min1,µA +µB

16 CAPÍTULO 3. FERRAMENTAS DE CONTRUÇÃO E ANÁLISE

dentre outros.Com o operador, Tc, chamado t-conorma,

Tc : µA(U)×µB(U)→ [0,1]

por Tc(µA,µB) = µA∪B, que satisfazendo às seguintes condições:

1. Comutativa: Tc(a,b) = Tc(b,a)2. Associativa: Tc(a,Tc(b,c)) = Tc(Tc(a,b),c)3. Elemento neutro: Tc(0,a) = Tc(a,0) = a4. Monotonicidade: Tc(a,b)≤ Tc(c,d) quando a≤ c e b≤ d

faz cada um dos outros um caso particular deste.

3.4 A inferência nebulosaA inferência nebulosa usa uma regra de inferência e uma base de regras, também

chamda de matriz de regras. A regra de inferência nebulosa tem em seu antecedente umconjunto de regras da sua base. Estas regras são definidas pela sensibilização das mesmasa partir de algum valor preciso, as quais passam a ser chamadas de regras disparadas ecom as quais se infere o resultado. Sua realização depende da realização do operador deimplficação e do operador relação, descritos a seguir.

Na lógica clássica, para as proposições p e q, uma regra de inferência bastante usadaé a chamada regra modus ponens, definida por

[p∧ (p→ q)]→ q

onde (∧) é o operador conjunção e (→) é o operador condicional. Para a lógica nebulosa,define-se, a partir desta, a regra modus ponens generalizada, dada por

[p′∧ (p→ q)]→ q′

onde p, p′, q e q′ são proposições nebulosas.Nesta regra generalizada a proposição p→ q é uma regrada matriz de regras enquanto

que as proposições p′ e q′ serão construídas a seguir, a fim de garantir o valor verdadeiroda regra de inferência.

Para realizar a regra de inferência faz-se necessário definir o operador implicação e ooperador relação. Para a definição do operador implicação, considere a sentença r→ s epara esta sua realização, para uma entrada 1.5, como sugeriu [Mandani e Assilan 1999],fica explicitada nos gráficos seguintes:

Gráfico do antecedente versus gráfico do consequente

O gráfico do antecedente é obtido com a pertinência de r e a entrada precisa 1.5

3.4. A INFERÊNCIA NEBULOSA 17

Figura 3.1: Pertinência do antecedente

e

0

0.5

1

0 1.5 3domínio de r

B(x)C(x)

Figura 3.2: Pertinência do consequente

0

0.5

1

0 1.5 3domínio de s

B(x)C(x)

Portanto, sendo verdadeiro o antecedente r será também verdadeiro o consequentepois o corte apenas reduz a pertinência deste, não havendo alteração no seu domínio.

Quanto ao operador relação, aqui representada por ∗, o mesmo é definido para funçõesde pertinências com domínios diferentes, a fim de torná-los iguais. Para tal, considere asproposições p1(x) e p2(y) definidas nos universos X e Y e, por facilidade de descrição,admita que p≡ p1(x)∧ p2(y). Sendo assim, a partir das funções de pertinência de p1(x)e p2(y) define-se as respectivas funções de pertinência de p1(x,y) e p2(x,y), resultantesdas respectivas extensões das mesmas e com estas, agora definidas no mesmo universo

18 CAPÍTULO 3. FERRAMENTAS DE CONTRUÇÃO E ANÁLISE

X×Y , define-se a função

p∗(x,y) = p1 ∗ p2 = ∗p1(x,y), p2(x,y)

, como sugerido em [Mandani e Assilan 1999, Takagi e Sugeno 1985], podendo ∗ ser de-finida pelo min, pelo produto p1(x,y)p2(x,y) dentre outras. Agora, define-se a associaçãop′ ≡ p1 ∗ p2 para se chegar ao antecedente da regra, [p′∧ (p→ q)].

3.5 Concepção de um controlador nebulosoUm controlador nebuloso é constituído de três módulos, o da ’fuzificação’, o da in-

ferência e o da ’defuzificação’. O primeiro módulo é responsável pela transformação dainformação precisa em informação nebulosa enquanto que o módulo da inferência é res-ponsável pela geração de novas informações nebulosas obtidas a partir das informaçõesnebulosas do primeiro módulo e, por último, o terceiro módulo transforma as informaçõesnebulosas do segundo módulo em informações precisas, do universo no qual teve inicio oprocesso.

3.5.1 O módulo da fuzificação

Para definir o primeiro módulo identificam-se no problema, para o qual o controladoré dirigido, os domínios X ′s e as variáveis xi, que se tornarão nebulosas pela escolha dapartição nebulosa de cada domínio X . Com essa escolhas definem-se entre estas variá-veis quais serão de entrada, xentrada e quais serão de saídas, xsaída, sendo estas últimasdependentes das primeiras e seus valores precisos é que serão usados no ajuste do quese pretende controlar. Para isso, associa-se a cada variável a sua correspondente variávellinguística, de mesmo nome e assumindo valores liguísticos, tais como, baixa -B, mé-dia -M e alta -A, valores estes escolhidos com a conveniente partição nebulosa. Em cadauniverso linguístico associado a X definem-se as funções de pertinências µ j, sendo j umvalor linguístico, por

µ j : X → [0,1]

que associa cada valor preciso de x ∈ X ao valor µ j(x), chamado de grau de pertinênciade x ao valor linguístico j, o que completa o módulo de ’fuzificação’.

3.5.2 O módulo de inferência

O principal módulo do controlador é o módulo de inferência que faz uso da operaçãode inferência, descrita na seção 3.4, a qual retira da sua matriz de regras cada uma dasregras disparadas, pelos valores linguísticos de entrada, e dela infere os valores linguís-ticos de saída. Cada regra disparada é representada pela proposição p→ q da regra deinferência. É claro que quando a proposição p→ q é falsa o valor inferido é verdadeiro,pois p→ q representa a experiência de alguém, o operdor, que tenha bastante conheci-mento do processo para o qual se destina o controlador, já que este pretende substituir ao

3.6. CADEIA DE MARKOV 19

operador. Entretanto não se pode excluir a possibiliidade do operador tomar uma decisãoerrada.

3.5.3 O módulo de ’defuzificação’Este módulo é responsável pela geração da informação precisa, extraída da informação

nebulosa gerada no módulo de inferência, como resposta para que se realize o processopor completo.

3.6 Cadeia de MarkovNesta seção procede-se a definição de cadeia de Markov e apresenta-se as proprieda-

des que merecem ser destacadas a fim de facilitar a compreensão da ferramenta usada naanálise de convergência do algoritmo em estudo.

A cadeia de Markov foi escolhida como ferramenta em virtude de sua abrangênciatanto na modelagem como instrumento de análise, para os casos abordados.

3.6.1 Definições e propriedadesUm processo estocástico discreto Xt, t = 1,2, · · · , com espaço de estados Ω, é cha-

mado de cadeia de Markov quando, para todo t e i1, · · · , it ∈Ω, satifaz à seguinte condição

P[Xt = it |Xt−1 = it−1,Xt−2 = it−2, · · · ,X1 = i1] = P[Xt = it |Xt−1 = it−1]

Sendo assim, define-se a chamada matriz de transição, P(t), ou matriz de um passo, deelementos

p(t)i j = P[Xt = it |Xt−1 = it−1], i, j ∈Ω

como sendo a matriz cujos elementos são as probabilidades de transições do estado i parao estado j, no instante t, quando a mesma satisfaz às seguintes condições

p(t)i j ≥ 0 para todo i, j ∈Ω e ∑j∈Ω

p(t)i j = 1 para todo t

Cadeia homogênea versus não-homogênea

Uma cadeia é dita homogênea quando sua transição não depende de t, sendo repre-sentada por P. Quando a cadeia tiver transição dependente de t será a mesma dita não-homogênea, sendo representada por P(t).

Para uma distribuição de probabilidade π0, sobre o conjunto de estados Ω, a ca-deia P(t)∞

t=1 fica completamente conhecida pela sequência π(t)∞t=1, de componentes

π(t)j , j ∈Ω, dada por

π(t) = π

0Pt quando a cadeia é homogênea

20 CAPÍTULO 3. FERRAMENTAS DE CONTRUÇÃO E ANÁLISE

pois sendo homogênea, P(t) = P, e a matriz de transição de t passos é dada pelo produtoPt . Quando a cadeia é não-homogênea a mesma fica conhecida, pela equação

π(t) = π

0P(1) ·P(2) · . . . ·P(t)

ou ainda porπ(m,t) = π

0P(m+1) ·P(m+2) · . . . ·P(t)

Sendo markoviana, a cadeia, as equações apresentadas possibilitam a descrição adi-antada da evolução da cadeia também chamada de cauda da cadeia, sendo esta de grandeutilidade na sua análise. Além disso, sendo a cadeia não-homogênea a equação possibilitao questionamento da dependência da convergência cadeia à distribuição inicial, ou seja,quando se deseja saber se há convergência ou não de (πm,t)∞

t=1, podendo ainda ser inde-pendente ou não de π0. Quando independente o comportamento é chamado de perda dememória.

Quando não houver convergência mas há perda de memória se diz que a cadeia éfracamente ergódica e quando houver convergência com perda de memória se diz que acadeia é fortemente ergódica.

Estados intercomunicantes e subcadeiaUm par de estados i, j é dito intercomunicantes quando existem instantes m e n tais

que p(m)i j > 0 e p(n)ji > 0.

Uma subcadeia de uma cadeia Xt, t = 1,2, · · · , com espaço de estados Ω= 1,2, · · ·,é qualquer cadeia resultante da restrição de Xt ∈Ω

′, onde Ω

′ ⊂Ω é o espaço de estadoda subcadeia. Sendo assim, Ω

′é chamado de conjunto fechado, no sentido da não inter-

comunicação de seus estados com qualquer outro estado de Ω−Ω′. Observe que Ω

′pode

ter apenas um elemento e, neste caso, o seu estado é chamado de estado absorvente dacadeia.

Irredutibilidade da cadeiaUma cadeia é dita irredutível quando todos os seus estados são intercomunicantes.

O período de uma cadeiaO período de um estado j é o inteiro, ρ, maior divisor comum do conjunto t|p(t)j j > 0,

ou seja, ρ = MDCt|p(t)j j > 0. Quando ρ = 1 diz-se que o estado é aperiódico.Sendo a cadeia irredutível, pelo corolário II.2.1 de [Isaacson e Madsen 1976], quando

afirma todos os seus estados têm o mesmo período.

Todos os estados de um subconjunto irredutível são do mesmo tipo

garante que todos os seus estados têm o mesmo período.Uma cadeia é dita aperiódica quando é irredutível e todos os seus estados são aperió-

dicos ou quando redutível e os períodos de suas subcadeias não são múltiplos.

A primeira visita a um estado

3.6. CADEIA DE MARKOV 21

Seja, f ti j, a probabilidade da primeira visita ao estado j ocorrer no instante t, dado que

Xk = i, ou seja

f ti j = P[Xt+k = j,Xt+k−1 6= j, · · · ,Xk+1 6= j,Xk = i]

e toma-se, f 0i j = f 0

ii = 0.

Estado persistente versus estado transienteUm estado j é dito persistente quando ∑

∞t=1 f t

j j = 1 e transiente quando ∑∞t=1 f t

j j < 1.

Persistência positiva e nulaSendo ∑

∞t=1 f t

j j = 1 e o valor esperado ∑∞t=1 t f t

j j <∞ diz-se que o estado j é persistentepositivo e quando ∑

∞t=1 t f t

j j = ∞ diz-se que o estado j é persistente nulo.

3.6.2 Ergodicidade da cadeia homogênea

Esta característica da cadeia é identificada com a análise da mesma em tempos longosou t grande, o suficiente para que se possa ter alguma previsibilidade sobre o comporta-mento futuro da mesma.

Quando, para todo i, são satisfeitas as condições

limn→∞

pni j = π j > 0 (3.1)

∑j

π j = 1 (3.2)

diz-se que a cadeia é ergódica

3.6.3 Ergodicidade da cadeia não-homogênea

Para este caso a ergodicidade é definida a partir do coeficiente de ergodicidade oucoeficiente de Dobrushin, o qual dá uma medida de distância entre as linhas da matriz detransição, definido a seguir

O coeficiente de ergodicidadeSendo a matriz de transição da cadeia, com espaço de estado Ω finito, dada por Pn

define-se o coeficiente de ergodicidada de Dobrushin

α(Pn) = maxi, j∈Ω

∑l∈Ω

|pnil− pn

jl|+

onde |pnil− pn

jl|+ = max0, pn

il− pnjl e com este define-se

δ(Pn) = 1−α(Pn)

e, em decorrência de 0≤ α(Pn)≤ 1, conclui-se que 0≤ δ(Pn)≤ 1.

22 CAPÍTULO 3. FERRAMENTAS DE CONTRUÇÃO E ANÁLISE

Uma outra medida de grande importância, tomada sobre a matriz de transição, é aseguinte A norma

Defina a norma, representada por ‖ · ‖, por

‖z‖= ∑i∈Ω

|zi|, e ‖Pn‖= maxi∈Ω

∑j∈Ω

|pni j|

e com esta norma as definições seguintes

Ergodicidade fracaDiz-se que uma cadeia é fracamente ergódica quando

limsupk→∞, y0,z0

‖ym,k− zm,k‖= 0, para todo m

sendoz(m,k) = z0Pm+1Pm+2 · · ·Pk para uma distribuição inicial z0

Ergodicidade forteDiz-se que uma cadeia é fortemente ergódica quando existe um vetor z ≥ 0, ‖z‖ = 1

tal quelimsupk→∞, y0

‖ym,k− z‖= 0, para todo m

Capítulo 4

A modelagem e análise de convergência

Neste capítulo pretende-se obter a modelagem dos algoritmos. Para isso apresenta-seos algoritmos AGH e AGNH a serem modelados, para o problema no formata escolhido.Por último chega-se às condições que garantem a convergência, tanto para o AGH quantopara o AGNH.

4.1 Os modelados AGH e AGNHNesta seção apresenta-se os algoritmos AGP/AGH e AGNH a serem modelados, com

o fim de permitirem as análises desejadas.O algoritmo AGP/AGH, tal como descrito em [Goldberg 1989],[Holland 1975] e

[Michalewicz 1992], parte de uma amostra de soluções viáveis Pop(0), de tamanho tp,chamada de população, e evolui, no tempo t, realizando as operações de seleção, de cru-zamento e de mutação, respectivamente, representadas por S, C e M, sobre a populaçãoPopt , gerando, com isso, a sequência Pop(t)∞

t=1Todos esses operadores são usados na busca do equilíbrio entre diversificação, a ca-

pacidade da população de se manter diversa a fim de evitar que o algoritmo fique preso aum ótimo local de baixa qualidade, e intensificação, a capacidade que o algoritmo tem deencontrar a melhor solução possível.

A dinâmica do algoritmo garante que a população resultante da aplicação destes ope-radores só dependa da população sobre a qual eles operam e não de toda história doprocesso e, em consequência, garante que o algoritmo genético possa ser modelado poruma cadeia de Markov.

Em vista da multiplicidade de definição do algoritmo, referida na seção 1.1, a buscapor um algoritmo com um bom desempenho, alternativo à versão padrão, AGP/AGH,quando se mantém os parâmetros fixos, tornou-se efetiva. Muitos trabalhos, nesse sen-tido, são encontrados na litertura e todos esses visam encontrar parâmetros que melhoremo desempenho do algoritmo. Nessas tentativas, alguns têm buscado respostas fazendoalterações na estrutura do algoritmo padrão, como em [Cerf 1996], quando faz o ajustetendo como referência o tamanho da população ou como em [Greenwell et al. 1995] quebusca a resposta na análise do operador mutação a fim de descobrir regiões nas quais háuma maior probabilidade do algoritmo encontrar o ótimo. Além destas tantas outras tenta-tivas têm sido feitas, como apontam os trabalhose de [Eiben e M. 1991, Nix e Vose 1992].

24 CAPÍTULO 4. A MODELAGEM E ANÁLISE DE CONVERGÊNCIA

Quando a análise é feita a partir da modelagem do algoritmo por cadeia de Markovdeve ser levado em conta que a cadeia que modela o algoritmo pode ser homogênea, comoem [Rudolph 1994], mas também pode ser não-homogênea. Mas a não-homogeneidade,quando decorrente da mudança nas taxas de mutação e de cuzamento, pode ainda advir detécnicas precisas, como em [Campos, Pereira, Carlos e de Assis 2012, Campos, Pereirae Rojas Cruz 2012], mas também pode ser decorrente de técnicas imprecisas ou técnicasque fazem uso da lógica difusa, como em [lee 1972, Cavalheiro 2003, Burdelis 2009]. Ouso dessas técnicas, sejam precisas ou imprecisas, dão origem ao que aqui é chamado deAGNH mas, com o fim de destacar, tendo em vista o estudo de caso aqui apresentado,quando se tratar de técnica nebulosa o algoritmo será referido por AGNHn.

Por razões associadas à escolha da ferramenta de modelagem, esclarecidas ao tempoda definição da cadeia de Markov, somente o operador seleção não pode vir a dependerdo instante t, sendo o parâmetro tp mantido fixo. Mas isto, a nosso ver, não deve trazernenhum prejuízo ao desempenho do algoritmo pois a despeito de tp não apenas refletir nacardinalidade da população mas também na sua diversidade, esta última pode ser melhore adequadamente controlada pela mutação.

Algoritmo AGHUma população inicial P, de cardinalidade tp, é gerada e escolhe-se txc, txm e pq, sendoos mesmos mantidos fixosRepita

Chame Seleção(P) retornando PSChame Cruzamento(PS) retornando PSCChame Mutação(PSC) retornando PSCMP←− PSCM

Até que algum critério de parada seja satisfeito.

enquanto que uma versão não-padrão para o AG, com tp fixo, e os demais parâmetrosvariando com t, txc(t), txm(t) e pq(t), fica definida como segue

Algoritmo AGNHUma população inicial P, de cardinalidade tp, é gerada e define-se os valores iniciais paratxc, txm e pqRepita

Chame Seleção (P) retornando PSChame Cruzamento (PS), com txc e pq, retornando PSCChame Mutação (PSC), com txm, retornando PSCMP←− PSCMChame a regra de geração de pqChame a regra de ajuste para txcChame a regra de ajuste para txm

Até que algum critério de parada seja satisfeito.

4.1. OS MODELADOS AGH E AGNH 25

Seus operadores

A seguir a descrição de cada um dos operadores usados no algoritmo AGH

O operador seleção

O operador seleção opera sobre uma população de pontos

[X t1,X t2 , · · · ,X ttp ], X ti ∈ G

e, tendo em vista que se busca o ponto ótimo, o faz com o uso de alguma medida deadequabilidade do ponto X ti , dada por p(X ti), que leve em conta o critério de otimalidade.Uma adequabilidade bastante usada é definida por

p(X ti) =f (X ti)

∑tpj=1 f (X t j)

, i = 1, · · · , tp

Tendo definidas as adequabilidades, p(X ti), um mecanismo de seleção, com reposição,é realizado com base numa roleta com setores de tamanhos p(X ti), que deve ser rodada tpvezes, selecionando em cada rodada um elemento para a nova população.

Tendo em vista que a escolha da adequabilidade pode levar a um super representantena população e, por isso, levar o algoritmo a uma indesejável convergência prematura, fatoque passou a ser chamada de pressão seletiva. Entretanto, quando isso ocorrer, para tiraressa pseudo superioridade, tanto a técnica de escalamento da função objetivo, indicadaem [Goldberg 1989], quanto outras técnicas, indicadas em [Michalewicz 1992], podemser usadas com o fim de controlar essa pressão.

O operador cruzamento

A definição deste operador pede não somente a definição de txc, taxa de cruzamento,taxa essa dependente ou não de t, a determinar a quantidade de elementos que cruzarão,mas também dependente da escolha desses elementos na população, a definir quais ele-mentos cruzarão, e, por último, depende do ponto de quebra, pq, se for apenas um. Tendosido escolhido o par X i, X j e o ponto de quebra, indicado por |, podendo este ser escolhidoaleatoriamente, o cruzamento é feito em txc pares escolhidos na população, com a trocados pontos

X i = (x1i, · · · ,xki, |x(k+1)i, · · · ,xni) e X j = (x1 j , · · · ,xk j , |x(k+1) j , · · · ,xn j)

pelos pontos seguintes

X i′= (x1i, · · · ,xki,x(k+1) j , · · · ,xn j) e X j

′= (x1 j , · · ·xk j ,x(k+1)i, · · · ,xni)

Para não gerar indesejáveis tendências a escolha dos pares pode ser feita considerandoque os pontos da população são uniformemente distribuídos ou não, se assim desejar,como em [Goldberg 1989, Michalewicz 1992].

26 CAPÍTULO 4. A MODELAGEM E ANÁLISE DE CONVERGÊNCIA

O operador mutação

Este operador, cuja descrição pode ser vista em detalhes em [Michalewicz 1992], é oprincipal responsável pela diversidade da população e a taxa de mutação, txm, a determi-nação da quantidade de soluções sujeitas à mutação, pode depender ou não de t. Como nocaso do cruzamento, este operador também depende da forma de representação da soluçãoe quando esta representação é binária costuma-se fazê-la pela troca do bit escolhido.

4.2 O problema e o formato

Com o objetivo de definir a modelagem para os algoritmos acima, da forma maisabrangente possível, decide-se usar o problema de otimização no seguinte formato, tendoem vista que este modelo representa uma expressiva classe de problemas de otimiza-ção, cuja dificuldade de resolução está associada à cardinalidade do conjunto de soluçõesviáveis que cresce exponencialmente, como é o caso apresentado a seguir, onde esse cres-cimento se dá tanto com o crescimento de n quanto com crescimento de k, sem contarcom o valor de tp que é relativamente pequeno. Por isso, o problema é dado no seguinteformato

max f (X l) : X l ∈ G (4.1)

Admite-se que f é uma função positiva e limitada superiormente, sobre G, dado peloproduto cartesiano, G = X1×X2×·· ·×Xn, obtidos da discretização dos contínuos, c(Xi),domínios das variáveis xi, para i = 1, · · · ,n, com k escolhido a fim de garantir a precisãodesejada.

Como o algoritmo depende da forma de representação do conjunto viável, a despeitoda representação binária ter sido usada com maior frequência, talvez por facilidades nadefinição dos operadores, aqui decide-se pela representação em ponto-flutuante, já queesta não traz nenhum prejuízo para os fins desejados e possibilita uma abordagem maisgenérica. Sendo assim,

Xi = xi j ∈ Xi i = 1, · · · ,n

e o conjunto G, de cardinalidade 2nk, é constituídos dos pontos

X l = (x1l , · · · ,xnl), xil ∈ Xi, l = 1, · · · ,2nk

4.3 A modelagem

Para se chegar à modelagem desejada observa-se inicialmente que os operadores S, Ce M do AGH podem ser modeladas, cada um deles, por uma cadeia de Markov, pois ficambem definidos apenas com o conhecimento das populações sobre as quais eles operam. Oconjunto de estados da cadeia é dado por Ω = 1,2, · · · ,2nktp, onde tp é o tamanho daspopulações sobre as quais estes operadores atuam. Portanto a transição da cadeia, quemodela o AGH, se dá pela transição dada pelo produto (SCM)t∞

t=1, sobre o conjunto

4.3. A MODELAGEM 27

de estados Ω = 1,2, · · · ,2nktp. Apenas os detalhes da modelagem de S são oferecidosporque esta é mandatária na análise desejada.

É importante observar que cada uma das matrizes S, C e M pode ainda ser dependentede t ou não. Quando sim, diz-se que a cadeia é homogênea e quando não diz-se que acadeia é não-homogênea. Sendo assim, quando a cadeia for homogênea será dada porP(t) = (SCM)t. Quando não-homogênea, a depender das características desejadas aoalgoritmo a gerarem a não-homogeneidade, como aqui quando admite-se apenas que Ce M dependem de t, para evitar variações na cardinalidade do conjunto de estados Ω,levando as mesmas a Ct e Mt , o que resulta na cadeia

Pt = PSPtSCPt

SCM

para PS = S(Popt), PtSC =Ct(Pt

S) e PtSCM = Mt(Pt

SC), ou PS = S, PtSC =Ct e Pt

SCM = Mt .

A transição S

Para se chegar à transição S a partir da sequência de populações Popt∞t=1 definida

porPopt = [X t1,X t2, · · · ,X ttp ]

, sendo esta obtida de Popt−1 pelo uso de uma roleta. A seguir, considere a sequência devariáveis aleatórias F t∞

t=1, dada pelos arranjos

F t = F t1F t2 · · ·F ttp

onde cada variável aleatória F ti , assume valores em G, com i ∈ Ω e, em consequência, acardinalidade de Ω é |Ω|= 2nktp . Sendo assim, define-se os conjuntos Φ(F t

j ), dado por

Φ(F tj ) = t j1, t j2, · · · , t jtp

e a sequência ℑ(F tj ) dada por

ℑ(F tj ) = [t j1, t j2, · · · , t jtp ]

e com estes a matriz de transição, S = [si j] i, j ∈Ω, dada por

si j = P[F t = F tj |F t−1 = F t−1

i ]

ou ainda

si j =

0 quando Φ(F t−1

i )−Φ(F tj ) 6= /0, para todo j

caso contrário

1 quando |Φ(F t−1

i )|= 1∏k∈ℑ(Ft

j )(1− f k)1−I(k)( f k)I(k) caso contrário

28 CAPÍTULO 4. A MODELAGEM E ANÁLISE DE CONVERGÊNCIA

onde para cada arranjo F tj define-se o arranjo f j = f j1 f j2 · · · f jtp sendo

f ji =f (X ji)

∑tpi=1 f (X ji)

j ∈ ℑ(F tj )]

com /0 representando o conjunto vazio, | ∗ | representando a cardinalidade de ∗ e ∏k∈I f k

representando o produto de todos os f k ∈ ℑ(F t−1j ) para

I(k) =

1 quando k ∈ ℑ(F t−1j )

0 caso contrário

A transição Ct

O cruzamento, cujos detalhes podem ser vistos em [Michalewicz 1992, Goldberg1989], como depende não somente de txc, a definir quantos pares cruzarão, mas tambémda escolha sobre a população, a definir quais pares cruzarão, e, por último, da forma comocruzarão, com a escolha do ponto de quebra, pq, que define o ponto de troca de conteúdosentre os pares, podendo este ser gerado aleatoriamente e distintos, para cada par. Por isso,a transição Ct(Popt , txt

c, pq), sendo cti j, i, j ∈ Ω, será conhecida com a possibilidade da

escolha

I(X i,X j) =

1 quando o par ,X i,X j, i, j ∈Φ(F t

j ) for escolhido para cruzar0 caso contrário

e, também, com a geração aleatória do inteiro 0≤ pq ≤ n, para se proceder o cruzamento,descrito acima. Observe que para se chegar a uma transição homogênea para C, ainda quetxc seja fixo, será necessária a fixação do parâmetro pq.

A transição Mt

A mutação, cujos detalhes podem ser vistos em [Michalewicz 1992, Goldberg 1989],depende não somente de txm, a dizer quantas componente da população serão afetados,mas também da escolha, na população, dessas componentes, a definir quais componentesmutarão. Por isso, sua transição Mt(Popt , txt

m), sendo mti j, i, j ∈Ω, será conhecida com as

escolhas dadas por

Ii j =

1 quando a componente escolhida for i ∈ ℑ(X j), j ∈ ℑ(F t

j )

0 caso contrário

quando se procede a mutação da componente i.

4.4 Análise de convergência

As análises de AGH e AGNH são feitas separadas, entretanto o caso homogêneo podeser alcançado a partir do caso não-homogêneo, como um caso prticular.

4.4. ANÁLISE DE CONVERGÊNCIA 29

4.4.1 Quando a cadeia é do tipo AGH

Sua aperiodicidade e sua irredutibilidadeTendo em vista que a população seguinte, definida pelos operadores, é construída por

critérios aleatórios, não sendo permitido nenhuma regularidade nesta escolha, a conclusãosobre aperiodicidade é imediata. Quanto à irredutibilidade, a mesma é garantida porqueo operador seleção já garante intercomunicação entre qualquer população que tem pelomenos um dos pontos da população presente e, quando não tem, ainda assim, a interco-municação fica garantida pela natureza aleatória dos operdores cruzamento e mutação.

Toda persitência de AGH é positivaSendo a cadeia finita e irredutível, o resultado fica garantido pelo lema III.2.1 de

[Isaacson e Madsen 1976], quando afirma que

Uma cadeia de Markov que é finita e irredutível todos os estados sãopersistentes positivos

Sua ergodicidadeOs resultados acima garantem irredutibilidade, aperiodicidade e persistência positiva,

para a cadeia do AGH, logo, tendo em vista os seguintes resultados, em [Isaacson eMadsen 1976]:Teorem III.2.1, quando afirma que

Seja P = (pi j) a matriz de transição para uma cadeia de Markov que é irredutível,persistente e aperiódica. Então para todo i ∈Ω vale

(a)

limn→∞ pn

i j =1

∑∞k=0 f k

iise ∑

∞k=0 f k

ii < ∞

0 caso contrário

(b)

limn→∞ pn

i j =1

∑∞k=0 f k

ii∀ j ∈Ω se ∑

∞k=0 f k

ii < ∞

0 caso contrário

Teorem III.2.2 de [Isaacson e Madsen 1976], quando afirma queSeja P = (pi j) a matriz de transição de uma cadeia de Markov irredutível, aperiódica

e persistente positiva. Sendo limn→∞ pni j conhecido e independente de i, defina

π j = limn→∞

pni j

Os π′s satisfazem às seguintes condições

π j > 0, ∑j∈Ω

π j = 1 π j = ∑j∈Ω

πi pi j

Portanto a ergodicidade da cadeia que modela o AGH fica garantida.

30 CAPÍTULO 4. A MODELAGEM E ANÁLISE DE CONVERGÊNCIA

4.4.2 Quando a cadeia é do tipo AGNH

Neste caso a ergodicidade da cadeia é definida através do coeficiente de ergodicidade,tal como definido na seção 3.6.3.

O coeficiente de ergodicidade de SCom o coeficiente de Dobrushin definido na seção 3.6.3, para cada estado F t

j , corres-pondente à coluna j da matriz de transição S, os elementos si j são 0, sempre existente,e/ou 1 e/ou ∏

tpk=1(1− f k)1−I(k)( f k)I(k). Então pode-se afirmar que α(S) = 1 e, em con-

sequência,δ(S) = 0

Sua ergodicidade fraca

Sendo P(t)= SC(t)M(t), como o lema V.2.3, em [Isaacson e Madsen 1976] que afirma

Se P e Q são matrizes estocástica então δ(PQ)≤ δ(P)δ(Q)

chega-se aδ(P(t))≤ δ(S)δ(C(t))δ(M(t))

e tambémδ(Pm,t)≤ δ(Pm+1)δ(Pm+2) . . .δ(Pm+t)≤ δ(S)

já quePm,t = Pm+1Pm+2 . . .Pm+t

e cada Pm+i, i = 1, . . . , t é do tipo SC(t)M(t). Logo conclui-se que limt→∞ Pm,t = 0. Por-tanto, com o teorema V.3.1 seguinte, de [Isaacson e Madsen 1976],

Uma cadeia não-homogênea é fracamente ergódica se e somente se, paratodo m, limt→∞ δ(Pm,t) = 0

chega-se à conclusão de que a cadeia do AGNH é fracamente ergódica.

Sua ergodicidade forte

Sabe-se que a ergodicidade fraca é condição necessária para a ergodicidade forte eque, em virtude do espaço de estados, Ω, ser finito, a cadeia tem pelo menos um autovetorψ com autovalor 1 e ‖ψ‖= 1, para cada transição P(t). Sendo assim, como [Isaacson eMadsen 1976] afirma que

Sendo P(t) a transição de uma cadeia de Markov não-homogênea fra-camente ergódica, com espaço de estado, Ω, finito, existe para cada t umautovetor ψt com autovalor 1 e ‖ψt‖= 1

4.5. A ABORDAGEM E OS RESULTADOS 31

para essa sequencia de autovetores ψt, correspondente à sequencia de transições P(t)∞t=1,

com Ω finito, conclui-se, em vista do teorema V.4.3, de [Isaacson e Madsen 1976], queafirma

Sendo a sequência, ψt, obtida de uma correspondente cadeia fraca-mente ergódica e se esta sequência ψt satisfaz

∞

∑j=1

∥∥ψ j−ψ j+1∥∥< ∞

então a cadeia é fortemente ergódica.

que a cadeia de Markov que modela o AGNH é fortemente ergódica.

4.5 A abordagem e os resultadosEsta abordagem destaca a importância que a matriz S tem na análise de convergência,

levando as outras matrizes C(t) e M(t) a serem secundárias, nesse sentido. A importânciadeste fato está na independência do resultado em relação, por exemplo, aos valores de txmque esta pode assumir ao longo do processo, permitindo que txm→ 0, com o aumento deng, tendência que se pede e pode ser observada na base de regras oferecida na seção 5.2.2.

32 CAPÍTULO 4. A MODELAGEM E ANÁLISE DE CONVERGÊNCIA

Capítulo 5

Um estudo de caso: AGH versusAGNHn

Neste capítulo apresenta-se a descrição do AGNHn, resultante do AGH pelo uso docontrolador nebuloso, que ajustaria os parâmtros associados aos operadores de mutação,txm e de cruzamento, txc.

5.1 O AGNHnEsta versão parte da versão padrão, descrita na seção 4.1, e agrega o controlador ne-

buloso, definido para esse fim na seção 5.2, para ajustar apenas o parâmetro txm.Para a realização de testes comparativos, AGH×AGNHn, escolheu-se problemas que

constam de testes realizados, tanto em [Michalewicz 1992] como em [Gonçalves 1997].

Algoritmo AGNHUma população inicial P, de cardinalidade tp, é gerada e define-se os valores iniciais paratxc, txm e pqRepita

Chame Seleção (P) retornando PSChame Cruzamento (PS), com txc e pq, retornando PSCChame Mutação (PSC), com txm, retornando PSCMP←− PSCMChame a regra de geração de pqChame a regra de ajuste para txcChame a regra de ajuste para txm

Até que algum critério de parada seja satisfeito.

5.2 O Controlador nebuloso usado no AGNHO controlador nebuloso seguinte destina-se a auxiliar o AGNH, com o qual passa a

ser chamado de AGNHn, com o fim de ajustar apenas o parâmetro taxa de mutação, txm.Portanto, sendo apenas uma variável a ser controlada, a txm, será esta a variável de saídado controlador e para esta estabelece-se sua dependência à diversidade da população, dp,

34 CAPÍTULO 5. UM ESTUDO DE CASO: AGH VERSUS AGNHN

e também ao número de gerações, ng, sendo as duas últimas as variáveis de entrada docontrolador.

Figura 5.1: AGNH + CONTROLADOR NEBULOSO = AGNHn

5.2.1 O módulo de ’fuzificação’, para o AGNHn

Aqui escolhe-se como variáveis de entrada a diversidade da população, dp e o númerode gerações, ng e como variável de saída a taxa de mutação, txm. Para cada um dosuniversos dp, ng e txm os valores linguísticos escolhidos foram baixo, B, médio, M ealto, A. É claro que a partição nebulosa de cada universo poderia ser outra, contendo ummaior número de valores lingísticos. Sendo assim, define-se as respectivas funções depertinência, a seguir

Variáveis de entrada

As funções de pertinência da variável número de gerações, ng

µB(ng) =

1 para 0≤ ng < 100−ng−100

100 +1 para 100≤ ng < 2000 para ng ≥ 200

5.2. O CONTROLADOR NEBULOSO USADO NO AGNH 35

µM(ng) =

0 para 0≤ ng < 100ng−100

100 para 100≤ ng < 2001 para 200≤ ng < 500−ng−500

100 +1 para 500≤ ng < 6000 para ng ≥ 600

µA(ng) =

0 para 0≤ ng < 500ng−500

100 para 500≤ ng < 6001 para ng ≥ 600

cujo gráfico é o seguinte

Figura 5.2: Pertinência de ng

0

0.2

0.4

0.6

0.8

1

0 100 200 300 400 500 600 700 800 900 1000número de gerações - ng

B(x)M(x)A(x)

As funções de pertinência da diversidade da população, dp

A a diversidade da população, dp, será a medida do estado da população presente,portanto a média,

f =∑

tpi=1 f (Xi)

tp

será usada com este fim. Para isso, as seguintes funções foram definidas em domínios,com seus respectivos valores linguísticos, a fim de garantir uma medida central para 60%dos casos.

36 CAPÍTULO 5. UM ESTUDO DE CASO: AGH VERSUS AGNHN

µBf (dp) =

1 para 0≤ dp < 0.45 f− dp

0.15 f +4 para 0.45 f ≤ dp < 0.6 f0 para dp ≥ 0.6 f

µMf (dp) =

0 para 0≤ dp < 0.45 fdp

0.15 f −3 para 0.45 f ≤ dp < 0.6 f1 para 0.6 f ≤ dp < 0.75 f− dp

0.15 f +6 para 0.75 f ≤ dp < 0.9 f0 para dp ≥ 0.9 f

µAf (dp) =

0 para 0≤ dp < 0.75 f

dp0.15 f −5 para 0.75 f ≤ dp < 0.9 f1 para dp ≥ 0.9 f

cujo gráfico é o seguinte

Figura 5.3: Pertinência de dp

0

0.2

0.4

0.6

0.8

1

0 0.5 1 1.5 2diversidade da população - dp para média=1

B(x)M(x)A(x)

Variável de saída

As funções de pertinência da taxa de mutação, txm

Observe que estas funções, de domínio [0,1] são parametrizadas por ng e esta parame-trização foi assim obtida para reduzir possíveis trocas de valores linguísticos na respostado controlador, principalmente com o crescimento de ng.

5.2. O CONTROLADOR NEBULOSO USADO NO AGNH 37

µBng(txm) =

1 para 0≤ txm <×10−2(2ng−1)

ng

− ng3×10−2 txm + 2

3(ng +1) para 10−2(2ng−1)ng

≤ txm <2×10−2(ng+1)

ng

0 para 2×10−2(ng+1)ng

≤ txm ≤ 1

µMng(txm) =

0 para 0≤ txm <10−2(2ng−1)

ngngtxm

3×10−2 +1

3(1−2ng)para 10−2(2ng−1)

ng≤ txm <

2×10−2(ng+1)ng

1 para 2×10−2(ng+1)ng

≤ txm <10−2(6ng−1)

ng

− ng3×10−2 txm +2ng +2/3 para 10−2(6ng−1)

ng≤ txm <

2×10−2(3ng+1)ng

0 para 2×10−2(3ng+1)ng

≤ txm ≤ 1

µAng(txm) =

0 para 0≤ txm <

10−2(6ng−1)ng

(ng

3×10−2 )txm−2ng +1/3 para 10−2(6ng−1)ng

≤ txm <2×10−2(3ng+1)

ng

1 para 2×10−2(3ng+1)ng

≤ txm ≤ 1

cujo gráfico, para ng = 1 segue

Figura 5.4: Pertinência da taxa de mutação

0

0.2

0.4

0.6

0.8

1

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1taxa de mutação - txm para ng=1

B(x)M(x)A(x)

38 CAPÍTULO 5. UM ESTUDO DE CASO: AGH VERSUS AGNHN

5.2.2 O módulo de inferência, para o AGNHn

Neste caso, parte-se do seguinte conjunto de regras do tipo p → q a constituirema matriz de regras e representarem as decisões do especialista, tomadas em cada caso.Portanto, frente à proposição p, composta com os valores linguísticos dp e ng, a decisãoa ser tomada será q, representando o valor linguístico inferido para txm, como descritoem 3.4. Estas decisões são definidas levando em conta que sempre que houver umadiminuição prematura de dp a regra deve imprimir um aumento em txm e quando ng foralto txm o valor de txm deve ser mantido ou até reduzido, mas nunca aumentado. A tableaseguinte foi sugerida a fim de contemplar estas condições.

txm ngB M A B∧M M∧ A

B A A M A MM A M B M B

dp A A M B M BB∧M A M M M BM∧ A A M B B B

Em seguida, pela regra de inferência generalizada, dada por

[p′∧ (p→ q)]→ q

′

onde p, p′, q e q

′são proposições nebulosas, chega-se à resposta deste módulo para txm

correspondente ao valor linguístico, novamente inferido pela regra descrita em 3.4. Combase em txm chega-se à pertinência µout , que será considerado no módulo de ’defuzifica-ção’ seguinte.

5.2.3 O módulo de ’defuzificação’, para o AGNHn

Tendo recebido µout do módulo de inferência, toma-se em seu domínio, por algum doscritério descritos em [Takagi e Sugeno 1985, Pedrycz 1989, Mandani e Assilan 1999], umponto para servir como resposta precisa do controlador, passando este ao algoritmo a fimdo mesmo, na geração presente, realizar o operador de mutação. Neste caso, a regra usadafoi a regra do centróide, dada por

∑xiµout(xi)

∑µout(xi).

5.3 Os problemas testesOs problemas usados foram escolhidos por terem graus de dificuldades diferentes e

constam de testes em [Michalewicz 1992] e [Gonçalves 1997], sendo os seguintes:

5.3. OS PROBLEMAS TESTES 39

f1(x1,x2) = 6+ x21−3cos(2πx1)+ x2

2−3cos(2πx2),para [−2,1]2

f2(x1,x2) = 0.5−sin2

√x2

1 + x22−0.5

(10.001x21 + x2

2)2,para [−1280/63,1240/63]2

f3(x1,x2) =1

0.3+ x21 + x2

2,para [−4,1]2

f4(x1,x2) = [1+(x1 + x2 +1)2(19−14x1 +3x22−14x2 +6x1x2 +3x22)]×

×[30+(2x1−3x2)2(18−32x1 +12x2

1 +48x2−36x1x2 +27x22],para [−2,2]2

f5(x1,x2) = (x2−5.14π2 x2

1−5π

x1−6)2 +10(1− 18π

)cos(x1)+10,para [5,10]× [0,15]

f6(x1,x2) = 3(1− x1)2 exp(−x2

2− (x2−1)2)+∣∣∣10(

x1

5− x3

1− x52)exp(x2

1− x22)∣∣∣+

+13

exp(−(x1−1)2− x22),para [−2,4]2

5.3.1 Os resultados obtidos e sugestões para novos testesCada uma das duas versões do algoritmo genético, AGH e AGNHn, foi executada 100

vezes para cada um dos problemas acima e cada execução realiza 1000 iterações. Comose conhece, a priori, o ótimo do problema, a taxa de sucesso do algoritmo é a soma dossucessos nas 100 execuções. O ganho obtido, do AGNHn sobre o AGH, fica evidenciadonos gráficos seguintes, o que mostra ser promissora a modificação aqui sugerida no AGH.

Quanto ao algoritmo, o aumento do número valores lingísticos e a desindexação dafunção de pertinência, do número de gerações, são algumas das alterações que merecemtestes.

Quanto ao problema escolhido para testes, uma escolha que abre outras possibilidadespara testes destacáveis é o problema do caixeiro viajante. Esses testes são recomendadosnão apenas pela importância que o problema do caixeiro viajante tem para a otimizaçãomas também pela possibilidade do referido problema poder ser posto no mesmo formatoda seção 4.2, sendo n o número de cidades.

40 CAPÍTULO 5. UM ESTUDO DE CASO: AGH VERSUS AGNHN

Figura 5.5: função 1 Figura 5.6: função 2

Figura 5.7: função 3 Figura 5.8: função 4

5.3. OS PROBLEMAS TESTES 41

Figura 5.9: função 5 Figura 5.10: função 6

42 CAPÍTULO 5. UM ESTUDO DE CASO: AGH VERSUS AGNHN

Referências Bibliográficas

Armijo, L. (1966), ‘Minimization of functions having lipschitz continuous first partialderivatives.’, Pacific J. Math. (16), 1–3.

Avriel, Mordecai (1976), NONLINEAR PROGRAMMING Analysis and Methods,Prentice-Hall, New Jersey.

Bazaraa, Mokhtar S. e C. M. Shetty (1979), NONLINEAR PROGRAMMING Theory andAlgorithms, John Wiley e Sons, New York.

Burdelis, M. A. P. (2009), Ajuste de taxas de mutação e de cruzamento de algoritmos ge-néticos utilizando-se inferências nebulosas, Dissertação de mestrado, UniversidadePolitécnica de São Paulo, São Paulo, SP.

Campos, V. S. M., A. G. C. Pereira e J. A. Rojas Cruz (2012), ‘Modelling the genetic al-gorithm by a non-homogeneous markov chain: Weak and strong ergodicity’, Theoryof Probability and its Applications 57(1), 185 – 192.

Campos, V. S. M., A. G. C. Pereira, L. A. Carlos e I. A. S. de Assis (2012), ‘Algoritmogenético por cadeia de markov homogêne versus não-homogênea: Um estudo com-parativo’, Revista del Instittuto Chileno de Ivestigacióin Operativa -ICHIO 2(1).

Cavalheiro, Andreia Philipp (2003), Lógica difusa no controle de parâmetros do algoritmogenético para o problema do caixeiro viajante, Dissertação de mestrado, Universi-dade Federal do Rio Grande do Norte, Natal, RN.

Cerf, R. (1996), ‘A new genetic algorithm’, Ann. Appl. Probability 6(3), 778–817.

Chvátal, Vašek (1983), LINEAR PROGRAMMING, W.H. Freeman and Company, NewYork.

Cobham, A. (1964), The intrinsc computacional difficulty of functions, em Y.Bar-Hillel,ed., ‘Proc. 1964 International Congress for Logic Methodology and Philosophy ofScience’, North Holland, Amsterdam, pp. 24–30.

Cook, S. A. (1971a), The complexity of theorem-proving procedures, em ‘Proc. 3rd Ann.ACM Symp. on Theory of Computing’, Association for Computing Machinery, NewYork, pp. 151–158.

Dantzig, G. B. (1963), Linear Programming and Extensions, Princeton University Press,Princeton.

43

44 REFERÊNCIAS BIBLIOGRÁFICAS

Dikin, I. I. (1967), ‘Iteraative solution of problem de linear and quadratic programming’,Soviet Mathematic Doklady (8), 674–675.

Dorigo, M., V. Maniezzo e A. Colorni (1996), ‘The ant system: Optimization by a colonyof coopernating agents’, IEEE Transactions on Systems, Man, and Cybernetics Part26(1), 29–41.

Edmonds, J. (1965a), ‘Paths, trees and flowers’, Canad. J. Math (17), 449–467.

Edmonds, J. (1965b), ‘Minimum partition of a matroid into independent subsets’, J. Res.Nat. Bur. Standards Sect. B(69), 67–72.

Edmonds, J. e E. L. Johnson (1970), Matching: a well-solved class of integer linear pro-gramming, em Gordon e Breach, eds., ‘Combinatorial Structures and their Applica-tions’, New York, pp. 89–92.

Edmonds, J. e E. L. Johnson (1973), ‘Matching, euler tours and chinese postman’, Math.Programming (5), 88–124.

Edmonds, J. e R. M. Karp (1972), ‘Theoretical improvements in algorithmic efficiencyfor network flow problems’, J. Assoc. Comput. Mach. (19), 248–264.

Eiben, A. E., Aarts E. H. L. e Vann Hee K. M. (1991), ‘Global convergence of geneticalgorithms: A markov chain analysis’, Lecture Notes in Computer Science 496, 3–12.

Fletcher, R. (1980), PRATICAL METHODS OF OPTIMIZATION Unconstrained Optimi-zation, John Wiley e Sons, New York.

Fletcher, R. (1981), PRATICAL METHODS OF OPTIMIZATION Constrained Optimiza-tion, John Wiley e Sons, New York.

Garey, Michael R. e David S. Johnson (1979), COMPUTERS AND INTRACTABILITY Aguide to the Theory of NP-Completeness, W. H. Freeman and Company, New York.

Gill, Philip E., Walter Murray e Margaret H. Wright (1981), Pratical Optimization, Aca-demic Press, London.

Glover, F (1986), ‘Future paths for integer programming and links to artificial intelli-gence’, Computers and Ops. Res. (5), 533–549.

Glover, Fred e Manuel Laguna (1993), Modern heuristic techniques for combinatorialproblems, em C. R.Reeves, ed., ‘ADVANCED TOPICS IN COMPUTER SCI-ENCE’, BLACKWELL SCIENTIFIC PUBLICATIONS, New York.

Goldberg, David E. (1989), GENETIC ALGORITHMS in Search, Optimization e MachineLearning, Addison-Wesley Longman, Inc., Berkeley.

Goldstein, A. A. (1965), ‘On steepest descent’, SIAM J. Control (3), 147–151.

REFERÊNCIAS BIBLIOGRÁFICAS 45

Gonçalves, C. R. (1997), Algoritmos de busca aleatória para otimização global: Estraté-gias de busca que preservam a distribuição assintótica, Tese de doutorado, Universi-dade de Brasília, Brasília-DF.

Gonzaga, C. Clovis (1989), Algoritmos de pontos interiores para programação linear, 17colóquio brasileiro de matemática, IMPA, Rio de Janeiro.

Gonzaga, C. Clovis e L. Amorim. Carlos (1990), A primal afine-scaling algorithm forlinearly constrained convex programs, Relatório técnico, COPPE - SISTEMAS, Riode Janeiro.

Greenwell, R. N., Angus J. E. e M. Finck (1995), ‘Optimal mutation probability for ge-netic algorithms’, Mathematicl and Computer Modelling 21(8), 1–11.

Hansen, P (1986), ‘The steepest ascent mildest descent heuristic for combinatorial pro-gramming’, Congress on Numerical Methods in Combinatorial Optimizatio, Capri,Italy (5), 533–549.

Holland, J. H. (1975), ‘Adaptation in natural and artificial systems’, University of Michi-gan Press, Ann Arbor pp. 3–12.

Isaacson, Dean L. e Richard W. Madsen (1976), Markov Chains Theory and Applications,John Wiley e Sons, New York.

Karmarkar, N (1984), ‘A new polynomial time algorithm for linear programming’, Com-binatorica (4), 373–395.

Karp, R. M. (1972), Reductibility among combinatorial problems, em R. E.Miller eJ. W.Thatcher, eds., ‘Complexity of Computer Computations’, New York, pp. 85–103.

Khachiyan, L. G. (1979), ‘A polynomial algorithm for linear programming’, Soviet Math.Doklady (20), 191–194.

Kirkparick, S., Gellat C. D. e Vecchi M. P. (1983), ‘Optimization by simulated annealing’,Science (220), 671–680.

Klee, V. e G. J. Minty (1972), How good is the simplex algorithm?, em O.Shisha, ed.,‘Inequalities-III’, New York, pp. 159–175.

Kuhn, H. W. e A. W. Tucker (1951), Nonlinear peogramming, em J.Neyman, ed., ‘Proce-edings of the Second Berkley Symposium on Mathematical Statistics and Probabi-lity’, Berkley, pp. 481–492.

lee, Michael (1972), Dynamic control, em O.Shisha, ed., ‘Inequalities-III’, New York,pp. 159–175.

Lemarechal, C. (1980), Extensions diverses des methods de gradient et applications, Tesede doutorado, Paris IX.

46 REFERÊNCIAS BIBLIOGRÁFICAS

Mandani, E. H. e S. Assilan (1999), ‘An experiment in linguistic synthesis with a fuzzylogic controller’, International Journal of Human-Computer Studies 51(2), 135–147.

Michalewicz, Z. (1992), Genetic Algorithms + Data + Structures = Evolution Programs,Springer-Verlag, New York.

Nelder, J. A. e R. Mead (1965), ‘A simplex method for function minimization’, ComputerJournal (7), 308–313.

Nemhauser, George L. e Laurence A. Wolsey (1988), Integer and Combinatorial Optimi-zation, John Wiley and Sons, New York.

Neto, J. C. R. (2010), Modelagem dos algoritmos genético simples e simulated annealingpor cadeia de markov, Dissertação de mestrado, Universidade Federal do Rio Grandedo Norte, Natal, RN.

Nix, A. E. e M. D. Vose (1992), ‘Modeling genetic algorithms with markov chains’, Ann.of Mathematics and Artificial Inteligence (5), 79–88.

Papadimitriou, Christos H. (1982), Combinatorial Optimization: Algorithms and Com-plexity, Prentice-Hall Inc., New Jersey.

Pedrycz, W. (1989), Fuzzy Control and Fuzzy Systems, John Wiley, New York.

Ribeiro, Celso C. (1998), Metaheurísticas, Escola brasileira de computação, PUC-RIO,Rio de Janeiro.

Rockafellar, R. T. (1972), CONVEX ANALYSIS, Princeton University Press, Princeton.

Rosen, J. B. (1960), ‘The gradient projection method for nonlinear programming, parte i- linear constraints’, SIAM J. Appl. Math. (8), 181–217.

Rudolph, G. (1994), ‘Convergence analysis of canonical genetic algorithms’, IEEE Tran-sactions on Neural Networks 5(1), 96–101.

Salkin, Harvey M (1975), Integer Programming, Addison-Wesley Publishing Company,Inc., Cleveland, Ohio.

Takagi, T. e M. Sugeno (1985), ‘Fuzzy identification of systems and its applications tomodeling and control’, IEEE Trans. Systems Man Cybernet (15), 116–132.

Ye, Y. (1987), Interior Algorithms for Linear, Quadratic and Linerly Constrained ConvexProgramming, Tese de doutorado, Stanford University, Stanford,Ca.

Zadeh, L. (1965), ‘Fuzzy sets’, Information and Control 8, 338 – 353.