Morre Dennis Ritchie, criador da linguagem C e do sistema Unix

Dennis Ritchie, pioneiro em programação de computadores, morreu aos 70 anos de idade nos EUA, de acordo com a Alcatel-Lucent's Bell Labs, companhia que empregava o programador desde 1960. A empresa não revelou a causa do óbito ou quando exatamente Ritchie morreu.

Ritchie criou, nos anos 70, a popular linguagem de programação C, comumente usada para desenvolvimento de sites até hoje.

Ele também ajudou na construção do software operacional Unix. O programa e seus desdobramentos, incluindo o Linux, são amplamente utilizados em vários dispositivos, incluindo servidores, caixas de banco e celulares.

	Divulgação - 27.abr.99
	Dennis Ritchie (centro) e Ken Thompson, da Bell Labs, recebem condecoração do então presidente Bill Clinton

De acordo com biografia de Ritchie no site da Bell Labs, ele nasceu em 9 de setembro de 1941, em Bronxville, Nova York, e estudou física e matemática na Universidade Harvard.

Jeong Kim, presidente da Bell Labs, escreveu em um post no blog da companhia nesta quinta-feira (13) que Ritchie era "verdadeiramente uma inspiração para todos nós, não apenas para suas muitas realizações, mas por quem ele era como um amigo, como um inventor, e como um homem humilde e agradável".

http://www1.folha.uol.com.br/tec/990281-morre-dennis-ritchie-criador

J.C.H Barcellos

Resumo

Os Algoritmos Genéticos representam, atualmente,  uma poderosa ferramenta para busca de soluções de problemas com alto nível de complexidade.

Este artigo  aborda os Meta Algoritmos Genéticos, que é uma classe de Algoritmos Genéticos, e compara-os com os Algoritmos Genéticos tradicionais. Para a realização deste estudo, foi desenvolvido um programa de computador que permite, de forma automática, a realização de testes de desempenho de várias modalidades de Algoritmos Genéticos, bem como a análise dos dados por eles gerados.

Os resultados obtidos mostraram que os Meta Algoritmos Genéticos são mais estáveis, com relação ao seus parâmetros de controle,   do que os Algoritmos Genéticos tradicionais.

1  Introdução

Algoritmos Evolucionários (AE) é a denominação de uma área da Inteligência Artificial (IA) que busca, através de processos baseados na evolução orgânica, a solução de problemas de otimização.

Os Algoritmos Genéticos ( AG )  juntamente com Estratégias Evolutivas (EE) e Programação Evolucionária ( PE ) pertencem a esta classe de algoritmos.

Estes algoritmos podem ser vistos como uma representação matemática - algorítmica das teorias de Darwin e da genética, chamada de  a nova sintaxe da teoria da evolução, cujos principais postulados podem ser resumidos :

·        A evolução é um processo que opera sobre os cromossomos do organismo e não sobre o organismo que os carrega. Desta maneira, o que ocorrer com o organismo, durante sua vida, não irá se refletir sobre seus cromossomos. Entretanto, o inverso não é verdadeiro: os cromossomos do organismo são o projeto e terão reflexo direto sobre todas as características desse organismo (o indivíduo é a decodificação de seus cromossomos).

·        A seleção natural é o elo entre os cromossomos e o desempenho que suas estruturas decodificam (o próprio organismo). O processo de seleção natural faz com que, aqueles cromossomos, que decodificaram organismos mais bem adaptados ao seu meio ambiente, sobrevivam e reproduzam mais do que aqueles que decodificam organismos menos adaptados.

·        O processo de reprodução é o ponto através do qual a evolução se caracteriza. Mutações podem causar diferenças entre os cromossomos dos pais e o de seus filhos. Além disso, processos de recombinação (“crossover”) podem fazer com que os cromossomos dos filhos sejam bastante diferentes dos de seus pais, uma vez que eles combinam materiais cromossômicos de dois genitores.

Em 1975, nos Estados Unidos, com o seu livro Adaptation in Natural and Artificial Systems, John Holland publicou o primeiro trabalho sobre AG. Este livro foi uma compilação de idéias e trabalhos que ele já vinha desenvolvendo há alguns anos. Uma outra escola de pesquisadores desenvolveu, na Alemanha, uma versão diferente, chamada de Estratégias Evolutivas. Elas foram introduzidas inicialmente por Rechemberg ^{[ 2 ]}, nos anos 60 e, mais tarde, desenvolvidas por Schwefel ^{[ 2 ]}.

A partir da publicação do trabalho de Holland, a área de AG tem evoluído constantemente e, atualmente, usam-se algoritmos genéticos na solução de uma diversidade enorme de problemas de engenharia.

Para se entender os Algoritmos Genéticos devem ser definidas algumas nomenclaturas e conceitos provenientes da genética.

2  Conceitos Básicos de Genética

O genótipo é o projeto de um organismo, o conjunto de instruções recebidas dos pais. O fenótipo é a manifestação, numa série de etapas do desenvolvimento, da interação dessas instruções com fatores físicos e químicos - o ambiente em sentido amplo- que permite a realização do projeto do organismo.

Devem-se ressaltar dois dos mais importantes princípios da hereditariedade: o de que o fluxo de informação do genótipo para o fenótipo é unidirecional, e o de que as unidades hereditárias transmissíveis mantêm sua identidade, de geração em geração.

2.1  Cromossomos e Genes

Todos os seres vivos conhecidos são formados a partir de um conjunto de instruções que estão contidas no núcleo de todas as suas células. As estruturas que armazenam estas informações, de como será o indivíduo, recebem o nome de cromossomos. A quantidade, o tamanho e o formato destes cromossomos mudam de espécie para espécie, podendo variar de um único e simples anel circular até uma grande quantidade de bastões. No caso humano, por exemplo, existem 23 pares, ou seja, 46 cromossomos com forma de bastão, que dão aos seres humanos todas as características físicas  (e, até mesmo, algumas psicológicas). A este conjunto de cromossomos dá-se o nome de genoma^[3].

O cromossomo pode ser dividido, para efeito de estudos, em segmentos longitudinais chamados genes. Genes funcionam como unidade genética; para efeitos práticos, são considerados como a unidade básica do cromossomo e juntos, carregam  todas as características que o organismo pode ter.

2.2  Nomenclaturas

Os cromossomos, em geral, ficam agrupados em pares. São denominados cromossomos homólogos os membros de cada par que compartilham os mesmos tipos de genes.

Define-se como locus ou loco o lugar ocupado por um gene dentro de um cromossomo. O mesmo loco pode estar ocupado, em diferentes cromossomos homólogos, por formas gênicas diferentes.

São chamados de alelos a essas variantes de um mesmo gene. Todos estão, naturalmente,  relacionados à mesma função geral, mas podem atuar diversamente. Assim , por exemplo, no caso humano, num determinado locus do cromossomo X existe um alelo que condiciona visão normal das cores e, no mesmo locus do cromossomo homólogo, poderá haver um alelo que impossibilite o seu portador de distinguir o vermelho do verde.

2.2  Reprodução

A reprodução dos seres vivos pode ser dividida em dois tipos: reprodução assexuada e reprodução sexuada. No primeiro caso, os organismos produzem clones, cópias idênticas de si próprios, ocorrendo, em geral, em organismos de baixa complexidade estrutural. Neste caso, estes organismos praticamente não apresentam variações, o que só ocorrerá quando houver mutações .

A reprodução sexuada, entretanto, é o modo usual de organismos mais complexos gerarem novos organismos. Neste caso, dois organismos, através da união de seus gametas, formam um novo organismo. Como cada gameta é haplóide, (carrega apenas metade do número de cromossomos de uma célula normal), a união de dois gametas irá gerar uma célula especial chamada ovo, diplóide, (com o número normal de cromossomos), metade dos quais provenientes do pai e a outra metade da mãe.

A formação do organismo completo poderá ter características fenotípicas distintas das do pai e das da mãe, por dois motivos: primeiro, por apresentar um genótipo distinto do de seus pais (o organismo terá metade dos genes de cada genitor) uma distinção fenotípica também ocorrerá. Segundo, por eventos que podem ocorrer durante a meiose, como se apresenta a seguir.

2.3  Recombinação cromossômica (“crossover”)

Também conhecida como permutação ou simplesmente recombinação, é o fenômeno que ocorre durante a meiose, onde os cromossomos homólogos se pareiam antes de se segregarem para gametas diferentes. O que ocorre, basicamente, é que uma parte de um cromossomo pode ser trocada com a outra parte do cromossomo homólogo, fazendo com que alelos, que antes estavam no mesmo cromossomo, passem a ficar em cromossomos separados.

2.4 Mutação

A hereditariedade é uma força conservadora que confere estabilidade a sistemas biológicos. Contudo, nenhum mecanismo composto de moléculas e sujeito ao impacto do mundo físico pode ser perfeito. Erros na cópia produzem seqüências alteradas de DNA - MUTAÇÕES - que são perpetuadas. Mutação é um termo vago, e é freqüentemente definido como uma mudança na seqüência de pares de base de um gene, mas às vezes o termo é usado de maneira mais ampla de modo a incluir mudanças no número e estrutura dos cromossomos.

3  O algoritmo

O algoritmo, proposto por Holland, é conhecido na literatura como Simple Genetic Algorithm ou  Standard Genetic Algorithm ou simplesmente pela sigla SGA. Pode-se descrever o algoritmo, sucintamente, em seis passos ^{[ 1 ]} :

(1) Inicie uma população, de tamanho N, com cromossomos gerados aleatoriamente;

(2)  Aplique a função de adequação em cada cromossomo desta população;

(3)  Crie novos cromossomos através de cruzamentos de cromossomos selecionados desta população. Aplique recombinação e mutação nestes cromossomos;

(4)  Elimine membros da antiga população, de modo a ter espaço para inserir estes novos cromossomos, mantendo a população com o mesmo número N de cromossomos;

(5)  Aplique a função de adequação nestes cromossomos e insira-os na população;

(6)  Se a solução ideal for encontrada ou, se o tempo (ou número de gerações) se esgotou, retorne o cromossomo com a melhor adequação. Caso contrário, volte ao passo (3).

Se tudo ocorrer bem, esta simulação do processo evolutivo irá produzir, à medida que as gerações forem se sucedendo, cromossomos cada vez mais bem adaptados, isto é,  com melhor valor da função de adequação, de maneira que, no final, obtém-se uma solução (cromossomo) com alto grau de adequação ao problema proposto.

No passo (3 ) do algoritmo existem dois operadores um de mutação e outro de recombinação que, para operarem precisam que um evento de probabilidade pm e pc , respectivamente, ocorram.

Estas probabilidades são escolhidas a priori, isto é, antes da execucao do programa. O próximo item abordará este tema.

3.1  A Escolha dos Parâmetros

Um dos problemas que deve ser enfrentado, para quem pretende usar um AG, reside na escolha dos seus parâmetros. Todos os AG usam, pelo menos, três  parâmetros numéricos: Probabilidade de Recombinação (pc),  Probabilidade de Mutação (pm) e Tamanho da População (pop).

Pode-se verificar ( figura 3.1 ) uma grande variação no desempenho, em função dos parâmetros, notadamente na probabilidade de mutação.

Número médio de gerações para se achar a raiz de função em função do grau de dificuldade

F1 = X3-pi                                      pop=30

F2 = X*sin(20*X)+1                  pc=0,75

Tamanho do Cromossomo = Grau de dificuldade;

9, 12, 15 e 19 cromossomos à1,2,3,4 casas decimais, respectivamente ;

Nº médio de gerações: obtido com a média de 200 experimentos (100 para cada função).

Figura 3.1 - Desempenho & Taxa de Mutação p/ SGA – [F1 & F2 ]

Para contornar este fato uma nova modalidade de AG foi desenvolvida: o chamado Meta Algoritmo Genético.

4  Meta Algoritmos Genéticos

Um dos primeiros (se não o primeiro) que sugeriu usar um AG (chamado de Meta-AG) para controlar outro AG foi Weinberg (1970)^{[ 4 ]}.

Embora Weinberg tivesse detalhado o esquema de como um AG poderia controlar os parâmetros de outro AG, ele não chegou a implementar, num programa, sua idéia (posteriormente Grefensttete em 1986 ^{[ 5 ]} implementou-a).

O esquema de um Meta-AG pode ser entendido mais facilmente tendo por base a figura 4.1:

Figura 4.1 - Esquema do Meta-AG

Aqui pode-se ver, esquematicamente,  três procedimentos enviando  e recebendo mensagens:

O primeiro, etiquetado como Meta-AG,  envia mensagens (as probabilidades de recombinação e de mutação) para o AG (tradicional) e recebe deste o valor médio de adequação de sua população (média aritmética da adaptabilidade dos indivíduos). Com base neste valor, o cômputo do valor de adequação do meta-cromossomo poderá ser calculado.

O segundo procedimento, etiquetado como AG, é um Algoritmo Genético  tradicional (AG-trad) que  usa os parâmetros (valores  de pc e pm) provenientes do Meta-AG para seu processamento interno.

De outro lado, como parte de seu processamento natural,  este AG-trad envia indivíduos de sua população (cromossomos) para o terceiro procedimento, aqui destacado, que é a Função de Adequação (que em última instância é o problema que o usuário quer resolver). Este procedimento devolve, por sua vez,  um valor real: o grau de adequabilidade deste cromossomo ao problema.

Deve-se ressaltar que o Meta-AG, em si, é um AG e, portanto,  também deverá ser parametrizado por, ao menos,  uma tripla (pc, pm, pop).

Aqui existe uma aparente contradição: usa-se um AG (Meta) para se evitar a escolha, sujeita a erros,  dos parâmetros (pc e pm) para um outro AG (AG-trad) e, contudo, este mesmo Meta-AG necessita destes mesmos parâmetros para poder operar !

Isso de fato ocorre mas, os parâmetros  (pc, pm) que são escolhidos para o Meta-AG, como será visto, não exercem uma influência direta no AG, protegendo-o, de certa forma, de erros (ou azar) na escolha dos mesmos. Além disso, espera-se que o AG-trad receba parâmetros adaptativos: os parâmetros devem mudar, com o decorrer do processamento, adaptando-se, de modo a elevar (maximizar) o valor médio de adequação dos cromossomos de sua população. 

4.1  O funcionamento do Meta-AG

O Meta-AG, sendo ele próprio um SGA, inicia sua meta-população  (em torno de 10 meta-cromossomos ) com valores aleatórios para pc  e pm. Após montada esta população inicial, tais restrições deixam de vigorar e, pc e pm podem assumir quaisquer valores entre 0 e 1. O SGA, que está acoplado ao Meta-AG, também é inicializado normalmente e sua população  avaliada.

Após esta fase de inicialização, o Meta-AG salva o valor médio da população do SGA e, em seguida, envia um par (pc,pm) , contido em seu meta-cromossomo para o SGA. Este, por sua vez, usa estas probabilidades em seu processamento por uma ou duas  gerações, fim das quais, sua população é novamente avaliada e este valor é retornado ao Meta-AG.

O Meta-AG, com base nos valores iniciais e finais da média da população do SGA, calcula a avaliação para o seu meta-cromossomo.

É importante ressaltar que a população do SGA (que trata do problema do usuário via função de adequação) está em evolução constante. Assim, cada meta-cromossomo usa a população que foi trabalhada e deixada pelo meta-cromossomo anterior. Isto significa que a população não é reinicializada para que cada meta-cromossomo seja testado, diminuindo consideravelmente este possível  “over-head”.

A figura 4.2 mostra o desempenho do Meta-AG em função da probabilidade de mutação com os mesmos parâmetros da figura 3.1

Número médio de gerações para se achar a raiz de função em função do grau de dificuldade

Figura 4.2 - Variação de desempenho com a Taxa de Mutação Meta-AG [F1&F2]

 Tabela 4.1 – Variação da desempenho com a taxa de mutação [F1&F2]

A coluna Max informa a quantidade média máxima de gerações necessárias para resolver o problema.

A coluna Min  informa a quantidade média mínima de gerações necessárias  para resolver o problema.

A coluna  D% informa a variação percentual (100* (Max-Min)/Min) .

Observando a tabela 4.1, verifica-se que o Meta-AG apresenta uma variação de desempenho com a taxa de mutação bem menor que o SGA.

Por exemplo: a primeira linha informa que para cromossomos com 12 bits de comprimento (precisão de 2 casas decimais), o SGA levou em média, no pior caso, 22 gerações para achar a raiz  e, no melhor caso,  8 gerações, o que  representa uma variação de 175%.

Já o Meta-Ag  gastou em média 9 gerações no pior caso e 8 gerações  no melhor caso, com uma variação de 13%, mostrando-se, neste caso, mais estável que o SGA. A mesma conclusão é válida para as outras linhas da tabela.

5 Conclusões

Após o SGA ser submetido a testes de sensibilidade de parâmetros, foi constatado que o algoritmo, na sua versão mais simples, apresenta um desempenho fortemente dependente da probabilidade de mutação, como pôde ser constatado nos resultados apresentado na figura 3.1.

A literatura também não mostra solução para o problema da escolha dos parâmetros, pois os valores sugeridos estão dentro de uma faixa muito larga. Foram realizados testes com os valores sugeridos na literatura e, mesmo assim, constatou-se uma significativa variação no desempenho do SGA.

Uma solução encontrada na literatura é o uso dos chamados Meta-Algoritmos Genéticos (Meta-AG) que são AG projetados para  controlar os parâmetros de outro AG.

Embora o Meta-Algoritmo dependa também de parâmetros iniciais, verificou-se que o seu comportamento, como um todo, não fica tão sensível a eles, permanecendo muito mais estáveis que o SGA (Tabela 4.1).

Portanto, pode-se afirmar que os Meta-Ags são  mais estáveis em seu tempo de resposta, seu desempenho não é tão dependente dos parâmetros de probabilidades iniciais  (pc e pm) e possuem um vasto campo de estudos pois existem mais possibilidades  de melhoramentos que o algoritmo genético padrão.

Referências Bibliográficas

[1] DAVIS, L. Handbook of Genetic Algorithms. New York: Van Nostrand Reinhold, 1991.

[2] SOUCEK, B. Dynamic Genetic and Chaotic Programming, the sixth generation. New York-Toronto-Singapure-Brisbane: John Wiley &Sons Inc., 1992.

 [3] FREIRE-MAIA, N. Genética de Populações humanas. São Paulo: HUCITEC, Ed. da Universidade de São Paulo, 1974.

[4 ] GOLDBERG, David E. Genetic algorithms in search, optimization, and machine learning. Addison Wesley Longman, Inc,  1989.

 [5] GREFENSTETTE, J.J. Optimization of Control Parameters for Genetic Algorithms, IEEE Trans. Systems, Man, and Cybernetics, Vol. SMC-16, No.1 pp122-128 (1986).

Um novo método de busca unidimensional por eliminação.

J. C. H. Barcellos[1]; F. A. M. Cipparrone[2]; E. Ranzini[3]

Sumário: O algoritmo  proposto neste artigo pertence à categoria dos métodos de busca unidimensional por eliminação,  podendo ser usado, portanto, na otimização de funções descontínuas.

Este novo método é baseado na busca por dicotomia, tendo porém um caráter probabilístico,  mostrando-se, em muitos casos, superior ao algorítmo de Fibonacci (considerado o mais eficiente método de eliminação até o momento), com a vantagem de ser muito mais simples.

Introdução

Os métodos de busca unidimensional são utilizados  em muitos algoritmos de otimização multivariável, onde são executadas sucessivas buscas unidimensionais em direções escolhidas  .

São portanto básicos, e de sua escolha dependerá a eficiência do processo de busca como um todo.

Partindo-se de um intervalo de incerteza inicial , ou seja, o intervalo onde se deseja localizar o extremo da função, este é reduzido progressivamente até delimitarmos o extremo dentro da precisão desejada.

Da categoria de métodos de busca unidimensional por eliminação, ou seja, algoritmos que vão descartando progressivamente intervalos onde o extremo não está localizado, os algoritmos mais utilizados são: [1,2]

·      Dicotomia

·      Interval Halving

·      Golden Section

·      Fibonacci

Dentre estes, o mais eficiente (e também o mais complexo) é sem dúvida o de Fibonacci, que utiliza a famosa sequência de Fibonacci na escolha das amostras da função a ser extremizada.

Em todos os métodos de eliminação é feita a suposição de unimodalidade (um único vale no intervalo em caso de minimização e um único pico em caso de maximização) da função no intervalo considerado, no que tange ao descarte dos intervalos. Se, por acaso, a função não for unimodal, o algoritmo converge para um extremo local. Como, nos métodos multivariáveis, são executadas buscas unidimensionais em diferentes direções, tal fato não tem normalmente maiores consequências.

Embora os métodos de eliminação pudessem, a princípio, ser considerados menos eficientes que os chamados métodos de interpolação (“curve fitting”), são mais robustos que os últimos, posto que quando o polinômio interpolador não representa adequadamente a variação da função, os métodos de interpolação podem apresentar convergência muito lenta, podem divergir ou mesmo prever o mínimo da função fora do intervalo inicial de incerteza.

Além disto, os métodos de eliminação não necessitam da derivada da função e são aplicáveis a funções descontínuas, ao contrário de muitos métodos de interpolação. [1]

Descrição do Método ( BCR )

Na elaboração do BCR, observamos que no método da dicotomia, algumas informações (amostras da função) eram prematuramente descartadas. Estas poderiam ser usadas de uma forma mais eficaz para a avaliação do novo intervalo.

Na busca por dicotomia [1], são realizadas amostragens da função em dois pontos tão próximos quanto possível do centro do intervalo de incerteza. A idéia é eliminar a cada passo praticamente metade do intervalo de incerteza, baseado nos valores relativos da função objetivo nos pontos amostrados e em sua unimodalidade.

Denotemos o intervalo inicial [X₀, X₃] e seu comprimento  por L₀ e seja a posição das duas amostras dadas por: X₁ =      e    X₂ =

onde é o número positivo muito pequeno escolhido., considerando a precisão da máquina, de modo que as duas amostragens dêem resultados diferentes.

Então, o novo intervalo de incerteza será [X₀, X₂ ] se f(X₁) <= f(X₂) , ou [X₁, X₃ ] caso contrario. Em ambos os casos o novo intervalo terá o  comprimento . O próximo par de amostras é tomado no centro do novo intervalo de incerteza, e assim sucessivamente. Conforme a figura :

O BCR executa o procedimento da dicotomia com as seguintes modificações:

·      No início são avaliados os extremos (X₀ e X₃) do intervalo[4].

·      Ao invés de sempre avaliar 2 pontos centrais do intervalo, avaliamos a princípio apenas um ponto central (X₁). Se f(X₀)<f(X₁)<f(X₃), o novo intervalo, considerando a unimodalidade, será [X₀, X₁]. Na situação simétrica f(X₃)<f(X₁)<f(X₀), o novo intervalo será [X₁, X₃] (conforme figura ). Caso contrário é feita a dicotomia convencional, escolhendo-se o ponto X₂=X₁+ como o segundo ponto central  próximo a X₁.

Uma vantagem adicional em relação ao Fibonacci é que este necessita que estabeleçamos a priori o número total de iterações a ser realizado, ao contrário do BCR e dos demais.

Análise de Eficiência

No melhor caso (uma função monotônica no intervalo), o algoritmo usará sempre apenas uma avaliação central da função,( além das duas iniciais), de modo que metade do intervalo é descartada a cada avaliação da função. Neste caso, o BCR é muito superior a todos os outros.

No pior caso, que corresponderia, por exemplo, a derivadas muito altas, perto de um dos extremos, com a função também possuindo um valor alto, ele se  torna idêntico ao algoritmo da dicotomia, pelo menos inicialmente. Neste caso, as duas primeiras avaliações seriam desperdiçadas em relação ao método da dicotomia.

No entanto, para funções não tão anômalas, o método se mostrou bastante eficiente, superando em muitos casos o método de Fibonacci, conforme demonstram os exemplos fornecidos na seção de resultados.

A tabela I a seguir ilustra a relação entre número de chamadas da função e tamanho do intervalo final em relação ao inicial. (OBS: d = 10^-10)  [1].

Tabela I - Tamanho do intervalo final X Número de iterações

Resultados

Para uma razão de redução de 0.5E-9, com partindo-se do intervalo inicial [-1,1], foram simuladas várias funções com vistas a determinar o menor número de avaliações da função que gerasse tal redução. Os resultados estão na tabela II a seguir:

Tabela II - Resultados Práticos

Pseudo - Código

O pseudo-código do BCR é descrito a seguir:

{ São dados:

   a0 e b0 (extremos do intervalo de incerteza inicial)

   reduction_ratio (comprimento do intervalo final / comprimento do intervalo inicial )

   delta (número pequeno para a dicotomia - vide texto)

 }

            a = a0

            b = b0

            ya = f(a)

            yb = f(b)

            M = reduction_ratio*(b0-a0)

            If  M < delta then begin

                        Print(‘Your reduction ratio must be greater than delta/(b0-a0)’)

                        Halt

            end

            Repeat

                        x = (a+b)/2

                        y = f(x)

                        If  (y<ya) and (y<yb)  then begin

                                   {Dichotomy Procedure}

                                   xa = x

                                   y1 = y

                                   xb = x+delta

                                   y2 = f(xb)

                                   If  y1<y2  then begin

                                               b=xb

                                               yb=y2

                                   end

                                   else begin

                                               a = xa

                                               ya = y1

                                   end

                        end

                        else If  y>ya  then begin

                                   b = x

                                   yb = y

                        end

                        else begin

                                   a = x

                                   ya = y

                        end

            Until (b-a) < M

            Print (‘Minimum Point = ‘, (a+b)/2)

 Prova de convergência

    Vamos demonstrar a convergência do método para um ponto de mínimo no intervalo [A,B], usando como hipótese que a função possua um unico vale  no intervalo considerado.

Tratando-se de um método de eliminação, em que o intervalo de pesquisa vai sucessivamente sendo reduzido até a precisão desejada, vamos analisar uma única iteração e mostrar que o novo intervalo, reduzido em relação ao anterior,  conterá o ponto de mínimo .

O método inicia calculando o centro do intervalo  ( C ) e sua ordenada correspondente:

C = ( A+B) / 2  ;

FC = F( C ) ;  

Onde   FA =  F( A )   e   FB = F( B )

Então  teremos as seguintes possibilidades para  FC :

a)    FA <   FC  <  FB

b)    FA   >  FC  >  FB

c)    Outros casos

Caso  a)  FA <   FC  <  FB

Neste caso o novo intervalo de pesquisa, que conterá o ponto de mínimo, sera o intervalo [A,C] .

A prova pode ser feita por absurdo:

  Suponhamos, por absurdo, que o pto de minimo, X, esteja no intervalo [C,B], neste caso teríamos :

         FA < FC   ( Por hipótese )   e

         FX < FC    ( Pois X é pto de mínimo )

Isto implicaria que o intervalo [A, X]  nao seria um vale ( pois FC é maior que ambos os extremos ), e portanto o intervalo [A,B]  tambem não o seria, contrariando a hipótese.

b)    FA   >  FC  >  FB

Este caso é simétrico ao caso a)  e portanto a prova é analoga.

c)    Outros casos

 No último caso, qdo Fc nao esta no caso a) nem no caso b), o método tradicional da  dicotomia é  adotado :

Um pto D = C+d   ( onde d » 0  ) é escolhido , de modo que  teremos :

 Se f(C) £  f( D ) então o novo intervalo sera [A, D]

caso contrario o novo intervalo será [C, B ]. Posto que em uma tripleta de ptos X, Y, Z. onde  f(Y)  é inferior a ambos   f(X) e f(Z) , então tal intervalo sempre encerra um mínimo local.

Bibliografia

[1]  Luenberger , D. G. Linear and Nonlinear Programming.

             Second Edition. Addison-Wesley, 1984.

[2]  Rao, S. S. Engineering Optimization: Theory and Practice.

      Third Edition. Wiley. New York. 1996.

[3]  Minoux, M. Mathematical Programming: Theory and Algorithms.

       Wiley. New York. 1986.

[4]  Acton, F. S.  Numerical Methods That Work.

       Harper and Row. New York. 1970.