Por uma Filosofia para Algoritimos Evolucionários Autor: Pedro Luis Kantek Garcia Navarro Resumo Os algoritmos evolucionários são um "guarda chuva" no qual se abrigam diversas tendências de pesquisa em universidades e centros de pesquisa no mundo. Conhecidos também pelo seu "filho" mais ilustre (os algoritmos genéticos), despertam interesse e curiosidade. Descendentes diretos da comunidade de inteligência artificial (IA), eles acrescentam um novo paradigma: a simulação da evolução natural com o ambiente, promovendo os mais aptos e gerando descendências sempre melhores em fazer alguma coisa. Como trazer essa idéia a programas de computador capazes de, em última análise, conseguirem machine learning é relato fascinante. Mas, à parte da questão técnica (é viável ?, é possível ?, como fazê-lo ?) talvez deva-se também pensar um pouco além, e refletir sobre o que esta técnica pode representar mais tarde. Este é o objetivo do presente texto. Após apresentar o mínimo indispensável de conceitos técnicos, ele justifica a importância da reflexão e procura fazê-la com as limitações existentes, que de resto são adrede reconhecidas. "A história da evolução nos diz que a vida supera todas as barreiras. A vida se espalha. Ocupa novos territórios. De modo doloroso, por vezes perigoso. Mas a vida dá um jeito. Eu não queria bancar o filósofo, mas é isso aí". Dr. Ian Malcolm, o caricato matemático de Jurassic Park, livro de ficção de Michael Crichton. Antes de tudo... Comece-se delimitando o foco de estudo, pois que a palavra "filosofia" tende a englobar muita coisa, o pensar sobre tudo, do início ao fim das coisas. Do dicionário Aurélio, tira-se que a filosofia "é o estudo que intenta ampliar o conhecimento da realidade, buscando apreendê-la". Quando qualificada, ainda segundo o dicionarista, tal filosofia busca "reunir determinados conhecimentos de um campo (no presente caso, dos algoritmos evolucionários) em um número reduzido de princípios que lhe servem de fundamento e lhe restringem o alcance". Portanto, o que se quer é algo sobre a base desse ramo do conhecimento e os princípios que o sustentam. Empreitada ambiciosa, por certo. Não se a subestima, com certeza. Registre-se uma dificuldade adicional, que é a formação, tanto escolar quanto profissional do autor. Ela foi apenas em informática, o que parafraseando um pensador da área "é pouco, muito pouco" para sequer arranhar os problemas que estão à frente. Mas, que fazer ? É tentador deixar que as coisas se resolvam de per si, mais adiante. Mas, a informática sempre se ressentiu de mais gente que a pensasse não como megabytes e novos releases de programas, sempre devorados de maneira insaciável, mas como algo que está a mudar a face deste nosso (único) mundo. Talvez uma saída seja apoiar-se sobre os ombros dos que já meditaram sobre problemas semelhantes e deram suas idéias ao papel. Pensando, matutando, digerindo o que se vive, olhando, lendo, ouvindo e sentindo o que nos rodeia e buscando tirar daí o substrato dos algoritmos evolucionários. Esse é o objetivo deste trabalho. Ao final, o leitor poderá dizer se se teve algum sucesso. Porque Filosofia dos Algoritmos Evolucionários Fazem bem as universidades americanas ao atribuírem o grau de PhD aos indivíduos que atingem o ápice da carreira universitária. O significado completo da sigla, phylosofia e doctor traduz o que se espera de uma pessoa que dedicou longos anos, possivelmente os mais produtivos de sua vida intelectual, ao estudo. Que, além do domínio de técnicas avançadas, de aplicações impressionantes, ou de saberes especializados, seja o PhD também um pensador de sua ciência. Não nas finalidades e aplicações práticas, mas também (e quiçá principalmente) nas causas primeiras. No substrato no qual se apoia todo o edifício conceitual estudado e conhecido, e sobretudo nas implicações e conseqüências que tal saber traz ao homem no mais íntimo do seu ser. Na informática a demanda por pensar o antes, é ainda mais forte e presente, no mínimo por duas razões: a primeira diz que a informática é nova. Tem quando muito 50 anos, tempo que se parece extenso para uma vida humana, é um pequeno átimo nessa longa aventura desde que das árvores descemos e passamos a andar sobre duas pernas. A natureza econômica e a busca por eficiência, bem-estar material, eficácia, produtividade que, inegavelmente, tem levado a informática a imiscuír-se em tudo e em todos, faz com que nesta área, o mundo tenha pressa. Usa-se aqui o que os economistas chamam de princípio do porco: "se algo é bom, mais é melhor". Mas a segunda razão talvez seja mais forte. Nas palavras de Weizenbaum2, talvez um dos pioneiros nessa área "de certo modo, os computadores são máquinas universais e que num certo sentido podem fazer tudo" (Weizenbaum, 1992). Felizes as ciências que podem se apoiar na sabedoria dos antigos que nos antecederam séculos e que já se preocupavam em ter uma visão crítica das coisas. Aí está Hipócrates, que no seu juramento do médico sugere questões e questionamentos inteiramente aplicáveis aos dias de hoje. Também o direito romano traz ao advogado algo a pensar. E, não se argumente que o mundo era diferente, pois ele podia sê-lo, mas o gênero humano era rigorosamente o mesmo. Pois a tese aqui, é que faltam à informática mais pessoas que a vejam não com os olhos embevecidos pelas conquistas tecnológicas, mas sim com olhos e cérebro críticos e isentos. Essa falta não sugere que tais pensadores não tenham existido. Cientistas (Von Neumann, Turing, Penrose e o já citado Weizenbaum, só para ficar com alguns) escreveram sobre isso. Eles existem, mas são poucos. E mais, parecem chegar sempre tarde, pois quando alcançam um patamar qualquer dos tecnicistas, estes já há muito o deixaram. A moderna ciência tem sido acusada, e justamente, de ser neutra, nem moral, nem imoral mas amoral, com toda a carga perigosa que esta palavra possa ter. Veja-se a ciência nuclear, que tanto responde por holocaustos como o de Hiroshima quanto pela geração de mais da metade da energia elétrica da França. A engenharia genética, a psicanálise, a química industrial, e a lista pode ser infindável, são provas prementes dessa afirmação. Pois bem, o ponto é: conquistas da computer science têm habilitado seus detentores a possuir uma ferramenta em mãos da qual se pode dizer tudo: poderosa, revolucionária, alargadora das diferenças entre ricos e pobres, menos uma coisa: que ela seja irrelevante. Possivelmente, a área da computação que mais tenha dado origem a tais reflexões, por razões óbvias, seja a inteligência artificial. Desde o já célebre seminário do Dortmound College em 1956 até hoje, a possibilidade de criar máquinas "inteligentes", que façam sombra ao homem, tem ressuscitado o mito do Frankstein, a criatura que se volta contra o criador. Um ramo da IA, conhecido como IA forte, pretende mais, a saber que o homem nada mais é do que um processador de dados, e que entendidos seu hardware e seu software, tal homem em nada diferirá de um computador. Este escrito navegará em áreas próximas, pois por baixo da IA nasce um ramo que, embora guarde semelhanças com aquela, trata de questões um pouco diferentes. Refere-se aos algoritmos evolucionários (AE) e no que ela pode nos trazer nos próximos lustros. Claro está, que ao se pensar o futuro de algo tão novo, corre-se um risco. O de que expectativas e desejos perfeitamente justificados a seu tempo, acabem não dando em nada. Novamente, a história pode dar exemplos abundantes. Para não ir muito longe, pense-se no comunismo e em toda a sua carga de promessas que sensibilizou e mobilizou, às vezes até às vias de fato, parte da humanidade neste século, e que, embora tenha modificado sensivelmente o capitalismo (e talvez este seja um dos seus grandes méritos) acabou melancolicamente com jovens alegremente embriagados, em festa, demolindo o muro de Berlim e guardando seus pedaços como souvenirs. Pois, voltando aos AE, precisamos antes de seguir nessa discussão, obter e precisar alguns conceitos operacionais. Poucos e simples, como convém a alguém que tem a pretensão de ver a floresta e não apenas algumas árvores em pequenos detalhes. Os AE nasceram com os biólogos. Sendo o computador, como já se viu, um simulador universal, nada mais justo que biólogos tentassem aprender algo sobre sua ciência usando esta máquina do "faz de conta". Seria uma simples aplicação, se não levasse a insights em outro grupo de cientistas: os da computação. Um dos primeiros é John Holland, que em 1975 escreve o livro seminal da computação genética Adaptation in Natural and Artificial Systems. A tese central do trabalho de Holland era (e é) de que os mecanismos de evolução natural, magnificamente explicitados por Charles Darwin pudessem servir de modelo para resolver problemas artificiais complexos. Neste último adjetivo, reside o grande charme dos AE. Certamente irrelevante para problemas triviais, eles tendem a ganhar robustez em situações onde outros mecanismos de solução ou são impraticáveis (pela ordem de magnitude do esforço computacional necessário) ou, o que é pior: inexistentes. Goldberg, já afirma "the central theme of research on genetic algorithms has been robustness, the balance between efficiency and efficacy necessary for survival in many different environments" (Goldberg, 1989). Subjacente a esta idéia, há que se fazer uma constatação: a de que a complexidade é, daqui para a frente, companheira inseparável de grande parte dos empreendimentos humanos, do presente e do futuro3. Como diz Roger Lewin "há um consenso geral, embora vago, de que a complexidade tem aumentado no decorrer da história evolutiva" (Lewin, 1993). Embora Lewin fale da evolução biológica, crê-se ser perfeitamente aceitável trazer, mutatis mutandis, este conceito para a sociedade humana. Vem em ajuda uma nova analogia. O autor já citado sugere como medida objetiva da complexidade (ainda biológica, não faz mal) a contagem do número de diferentes tipos de células em um organismo. Troque-se célula por posto de trabalho e organismo por empresa e temos uma medida razoável de como as obras humanas têm se tornado complexas. Apenas para encerrar esta visão introdutória termina-se citando Soucek, que diz que o futuro da computação está no entorno dos seguintes eventos: (Soucek, 1992).
Claro está que, mesmo que apenas uma parcela de tais previsões de fato se confirme, os modelos tradicionais de computação serão incapazes de coexistir com tais tecnologias e forçosamente terão que dar lugar a novos paradigmas no uso do computador. Algoritmos Evolucionários Os algoritmos evolucionários são um campo multidisciplinar que abrange diversos ramos, alguns antigos, outros de mais recente constituição, mas todos baseados numa simulação dos processos de evolução natural aplicada à solução de problemas computacionalmente difíceis. O primeiro, até cronologicamente, é o dos algoritmos genéticos (AG) que originalmente nasceram com objetivo de possibilitar experiências de machine learning, e posteriormente foram aproveitados para melhorar processos de otimização. Baseiam-se em três idéias: a codificação de parâmetros que gerem uma dada solução a um problema na forma de strings de tamanho fixo (que aqui se chamam cromossomos); a criação de uma função cuja finalidade é atribuir uma nota (conhecida como aptidão) a uma determinada solução e que faz o papel do ambiente na evolução natural clássica; e a utilização de operadores, copiados da natureza, que permitem simular a passagem de gerações pelo ambiente. Os principais operadores são: a seleção (simula o cruzamento de seres); a mutação; e a troca de material genético, aqui chamado crossover. Um segundo ramo é o da programação evolucionária (PE). Similar aos AG, porém com algumas diferenças: ao invés de emular operadores genéticos, a PE põe ênfase na herança de comportamento entre "pais" e "filhos". Usado originalmente para predizer o comportamento de um autômato finito, algo, portanto, também próximo a machine learning. Outro ramo é o chamado estratégia evolucionária (ES), similar a PE, mas nascido de maneira independente na Alemanha, por volta de 1963. Os sistemas classificadores (SCF), constituem-se na aplicação dos algoritmos genéticos à aprendizagem de máquina. No começo os AG e os SCF eram uma coisa só. Separaram-se depois, quando os AG vocacionaram-se à otimização. Os AG formam apenas uma parte, na verdade a terça parte dos sistemas classificadores. A programação genética (PG) é uma generalização dos AG, na qual os cromossomos deixam de ser strings de tamanho fixo e passam a ser programas que quando executados tornam-se os candidatos à solução. Representam-se agora como árvores. Os programas da população são compostos de elementos de dois conjuntos: o de funções e o de símbolos terminais. Na PG o crossover é obtido substituíndo-se subárvores entre os indivíduos. Usualmente não há mutação. Mais Conceitos Ver-se-ão a seguir, alguns conceitos básicos a todos os campos acima, embora com nítida orientação para os algoritmos genéticos. Tal escolha se justifica por serem eles os iniciadores de todo o ramo de estudo. Dado um problema complexo que se quer resolver, tudo se inicia pela escolha de um método de codificação, que permita representar uma solução qualquer por meio de um string de bits, no caso mais simples, ou de um alfabeto mais poderoso, no caso de problemas específicos. Note-se que o uso de bits dá à técnica uma generalidade e uma correção matemática, que de outra forma ela não teria. É o caso do teorema dos esquemas (Goldberg 1989, págs 30 e seguintes) que oferece prova formal do crescimento da aptidão média das soluções com o passar das gerações. Isto posto, uma população de indivíduos, possivelmente randômica, é criada. Segue-se a elaboração de uma função de avaliação. Ela pode ser uma função matematicamente definida, um programa de computador, ou até a intervenção de um ser humano4. Tal função cria uma solução a partir dos parâmetros codificados no cromossomo de cada um dos indivíduos da população original e atribui-lhe uma nota, que a literatura registra como fitness (aptidão). Com isso, têm-se indivíduos mais bem dotados e também indivíduos de baixa aptidão. Agora, pares de indivíduos são escolhidos aleatoriamente, usando mecanismos que privilegiem os mais bem dotados para gerarem descendência. O mecanismo usual atende pelo nome de "roda da roleta". Ele pode ser visto como uma roleta de cassino, no qual a abertura angular de cada indivíduo é proporcional à sua aptidão. Joga-se a bolinha (gera-se um pseudo-aleatório) e voilà, um pai foi selecionado. Existindo dois pais, eles trocam partes de seus cromossomos, também de modo aleatório, o que já se viu, recebe o nome de crossover e tem-se dois filhos que, embora diferentes de seus pais, inegavelmente trazem uma bagagem hereditária. Encerra o ciclo, a aplicação de mudanças aleatórias, em um ou mais genes (um cromossomo se compõe de genes) e com baixa probabilidade de ocorrer, tal como na natureza. Esta é a chamada mutação. A idéia é que o crossover, atuando primeiro, funcione como uma pesquisa ampla em todo o espaço de soluções, enquanto a mutação, preocupa-se em ajustes finos sobre os pontos máximos encontrados. No momento da função de avaliação atribuir suas notas, o uso de alguns conceitos operacionais, claramente melhora o processo. Dois deles são: o janelamento, que faz com que indivíduos com baixa aptidão continuem sendo selecionados, e a normalização linear, que evita o fenômeno conhecido como "super indivíduo" e que quando ocorre costuma monopolizar todos os cruzamentos, gerando o que se convencionou chamar de "convergência precoce". A justificativa para que indivíduos de baixa aptidão, devam ser usados como fonte de material genético, está no seu potencial de exploração de pontos inexplorados do espaço amostral. Problemas Um problema sério que se enfrenta é que nem sempre tais algoritmos convergem para um ótimo global. Trata-se de fenômeno conhecido como deception. A decepção ocorre quando há epístase nos cromossomos. Define-se epístase, como a iteração entre genes. Como diz Beasley "a gene is said to be epistatic when its presence supresses the effect of a gene at another position within the chromossome" (Beasley, 1993). Este fato ocorre em problemas com múltiplas variáveis interdependentes. Claramente algoritmos genéticos funcionam muito bem quando há baixa epístase. Se a epístase surgir como um problema da codificação usada para representar os cromossomos, a solução já está à vista: trata-se de propor um novo, e possivelmente mais criativo (ainda que mais complexo) processo de codificação. Quando a epístase for intrínseca ao problema em estudo, a literatura recomenda (por exemplo, em Davies 1991), a adaptação dos AG em novos algoritmos, a que o autor chamou de híbridos, no sentido de que são uma mescla entre algoritmos convencionais (claramente orientados ao problema que se quer resolver) com os algoritmos genéticos. Neste caso, em geral, também é necessário recriar os operadores genéticos de maneira a adaptá-los ao novo domínio do problema. O que se perde em generalidade, facilidade de uso e segurança pode ser ganho em eficácia. Outro problema, este inerente ao tema, é que por serem técnica estocástica por excelência, não possibilitam uma solução única, acabada e definitiva. É mister trabalhar com conjuntos de soluções e resultados aproximados, obtidos com base em tratamento estatístico das diversas execuções. É conseqüência desta característica que tais algoritmos sempre são enormes devoradores de recursos de hardware5. Mais ainda, pode ser que uma solução maravilhosa que tenha sido encontrada uma vez, nunca mais venha a se reproduzir, o que força, de novo, a levantar a magnitude da quantidade de execuções da solução do problema. Finalmente, talvez o maior problema enfrentado seja o pouco tempo decorrido desde que tais técnicas cairam no domínio público. Ainda não houve tempo para que a comunidade mundial de informática use, critique, sugira e finalmente aprove esta abordagem para a solução de problemas complexos. Só o tempo há de confirmar este approach como válido e útil, ou como mais uma promessa não cumprida. E a filosofia ? Esta parte do texto vai ser conduzida na forma de perguntas, que, como seres humanos, temos o direito de fazer seguidas das respostas que trazem a possível e modesta contribuição ao assunto. Vamos a elas:
Conclusão É tentador prever um futuro brilhante para os algoritmos evolucionários. Se tomado como indicador o interesse da comunidade acadêmica por eles, tal futuro poderia parecer garantido. Entretanto, a lista de problemas e dificuldades a superar parece igualmente grande. Sua principal contribuição, até agora, sem dúvida é a inauguração de novo paradigma na construção de sistemas de informação. Isso significa, no mínimo, novas linhas de pesquisa, novas abordagens para problemas antigos e também, o que é importante, para novos problemas. Eles já provaram que são importantes demais para serem desprezados como irrelevantes ou como mero modismo. Caberá às novas gerações de pesquisadores, quiçá libertos das convenções e do determinismo que sempre vigiu na ciência da computação, escrever as novas e talvez brilhantes páginas dessa iteração entre computadores e evolução natural. Bibliografia BEASLEY, D., D. BULL, R. MARTIN. (1993). An overview of genetics algorithms: part 1 - fundamentals. Inter University Committee on Computing. ftp://alife.santafe.edu/pub/USER-AREA/EC/GA/papers/over93.ps.gz. University Computing, 1993, 15(2) 58-69. BEASLEY, D., D. BULL, R. MARTIN. (1993). An overview of genetics algorithms: part 2 - reseach topics. Inter University Committee on Computing. ftp://alife.santafe.edu/pub/USER-AREA/EC/GA/papers/over93-2.ps.gz. University Computing, 1993, 15(4) 170-181. BITTENCOURT, G. (1994). Roger C. Schrank: "Where's the AI?" - Análise Crítica. LCMI-CPGEE, Universidade Federal de Santa Catarina. Florianópolis. DAVIES, L. (1991). Handbook of Genetic Algorithms. Van Nostrand Reinhold. New York. FORREST, S. editor. (1993). Proceedings of the fifth international conference on GENETIC ALGORITHMS. Universidade de Illinois. Estados Unidos da América. GOLDBERG, D. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing Company Inc. Massachussets. HIETKOETTER, J. (1995). ENCORE - The evolutionary computation repository network. Eunet Deutschland Gmbh. ftp: //ftp. Germany. EU.net/pub/research/softcomp/EC (192.76.144.75) HOLLAND, J. (1992). Genetic Algorithms. Scientific American, July, 1992. Scientific American Inc. New York. HOLLAND, J. (1992). Adaptation in Natural and Artificial Systems. MIT Press, Massachussets. LEWIN, R. (1993). Complexidade: a vida no limite do caos. Editora Rocco Ltda. Tradução do original americano Complexity: life at the edge of chaos. Rio de Janeiro. MICHIE, D., JONHSTON, R. (1985). O computador criativo, Editorial Presença, Lisboa. PENROSE, R. (1989). The Emperor's new mind- concerning computers, minds and laws of physics. Oxford University Press. RIOLO, R. (1992). The survival of the fittest bits. Scientific American, Secção "the amateur scientist". July 1992. Scientific American Inc. New York. SHORROCK S. (1980). A origem da diversidade: as bases genéticas da evolução. Tradução do original The genesis of diversity. T. A. Queiroz, editor, editora Universidade de São Paulo. São Paulo. SOUCEK, B. (1992). Dynamic, Genetic and Chaotic Programming. The sixth generation. The Wiley & Sons, Inc. New York. WEIZENBAUN, J. (1992). O Poder do computador e a razão humana. Editorial Presença. Lisboa.
|
