Artigo Sobre IA

PROGRAMAÇÃO GENÉTICA

Douglas Santana

[e-mail]

Rafael Graziosi

[e-mail]

Rafael Teixeira

[e-mail]

Tayna Oliveira

[e-mail]

1. Resumo

Este artigo introduz os conceitos básicos da Programação Genética e o uso de Algoritmos Genéticos de forma explicativa, abordando a evolução e fazendo uma rápida revisão sobre a estrutura e os conceitos necessários para desenvolver uma aplicação neste conceito, utilizando cases de tecnologia da informação, para concluir e discutir o impacto da PG na área da computação.

2. Abstract

This article introduces the basics concepts of Genetic Programming and the use of Genetic Algorithms in a explanatory way, addressing the evolution and doing a quick review on the structure and the concepts needed to develop an application in this concept, using cases of information technology, to complete and discuss the impact of PG in computing.

Keywords: genetic programming, genetic algorithms, LISP

 

3. Introdução

Um dos grandes desafios da Inteligência Artificial em si, é fazer com que os computadores consigam resolver problemas, sem que sejam formalmente programados para isto. A programação genética (ou PG) surgiu como uma tentativa para resolver este problema. Ela faz parte de uma área denominada Computação Evolutiva, que tem como base de inspiração a Teoria da Evolução de Charles Darwin.

A PG é uma generalização dos algoritmos genéticos (ou AG) que são, por sua vez, uma forma de otimização global baseados nos mecanismos de seleção natural de busca paralela e estruturada, de forma aleatória direcionada, que reforça a busca de pontos de “maior aptidão” em indivíduos que possuam um genótipo formado por cromossomos.

No ambiente da PG os indivíduos que serão evoluídos são os programas de computador, representados por estruturas de árvores sintáticas (uma estrutura de dados em árvore, que representa a estrutura sintática de uma cadeia de acordo com alguma gramática formal). Essas árvores possuem funções e terminais, que determinam suas características e definem seu comportamento no ambiente, onde cada função é um ramo da árvore e cada terminal é uma folha.

As funções podem ser, por exemplo, operações lógicas ou matemáticas, ou funções que provocam iteração. Já os terminais podem ser as variáveis, constantes ou funções que não recebem argumentos, como apresentado nas figuras 3.1 e 3.2 abaixo:

FIGURA 3.1 – Exemplo de um indivíduo em PG

FIGURA 3.2 – Exemplo de árvore sintática

A população é formada por um conjunto de árvores, cada um representando um programa (indivíduo). O cruzamento na PG não é aleatório, pois precisa preservar a sintaxe da árvore.

Solucionar um problema em PG requer um amplo conhecimento sobre o ele e muitas vezes abordagens não convencionais. Algumas das atividades geram problemas matemáticos de grande complexidade e apresentam espaço de busca de soluções praticamente infinita.

Algumas linguagens de programação foram criadas para propor soluções a estes problemas, tais quais podemos citar o LISP, PROLOG, JAGA e muitas outras que usam por base árvores sintáticas.

A seguir abordaremos um case utilizando a PG com a linguagem LISP em semáforos de rodovias de grande tráfego, onde há a possibilidade de uma melhoria e avanço no transito.

4. Materiais e Métodos

É importante entender que na programação genética não existe uma codificação prévia do problema, e sua solução é obtida pela execução do programa que representa o indivíduo.

Para iniciar um sistema baseado em PG é necessário estabelecer os seguintes pontos:

• Determinar o conjunto de terminais e de funções primitivas;

• Definir a função de fitness²;

• Estabelecer parâmetros de controle de execução;

• Definir critérios de parada.

O algoritmo utilizado efetua basicamente os seguintes passos abaixo, que também pode ser visualizado na figura 4.1 logo a seguir:

1. Criar aleatoriamente uma população inicial (de funções e terminais) formada pelos programas (árvores) de computador;

2. Avalia cada árvore (executar o programa) considerando a função de fitness;

3. Verifica se vai existir mutação sobre a população. Se sim, aplicar o operador de mutação sobre uma árvore escolhida de forma aleatória;

4. Seleciona as árvores para a reprodução, baseando-se nos valores retornados pela função de fitness;

5. Efetua o cruzamento sobre árvores escolhidas para reprodução;

6. Gera uma nova população contendo as árvores criadas na fase de cruzamento e de onde foram eliminadas as árvores com menor valor de fitness;

7. Volta ao passo 2 até que sejam atingidos os objetivos mínimos, ou seja ultrapassado o número máximo de gerações genéticas permitidas.

FIGURA 4.1 – Fluxograma das etapas da PG

Para implementação do algoritmo de PG, o seu espaço de busca deverá ser amplo para que facilite a solução do problema e as funções e terminais utilizados deverão ser especificados para o problema.

Função de Fitness

A função de fitness é a fonte que representa o que se deseja modelar, ela deverá medir a adaptação do indivíduo no ambiente, relacionar o indivíduo com os demais gerados e distinguir uma solução completa de outra menos completa. Calcula-se o