T IME ‐ DEPENDENCY FOR THE EFFECT OF  S100A4  ON CELL PROLIFERATION

Algoritmos Genéticos (AG) são modelos computacionais/matemáticos utilizados em problemas de otimização, busca combinatória, classificação de padrões e em outros que necessitem de busca em um espaço de soluções [Lecheda 2004]. Inspirado na maneira como a teoria da evolução das espécies de Darwin foi construída e nas leis de Gregor Mendel, Jonh Holland [Holland 1975] em meados dos anos 70 desenvolveu juntamente com sua equipe de pesquisa um modelo computacional capaz de reproduzir o comporta- mento evolutivo das espécies em estruturas de dados e modelos matemáticos. Ele dividiu esse modelo nas seguintes etapas: inicialização, avaliação, seleção, cruzamento, mutação, atualização e finalização.

Um AG trabalha basicamente criando uma população de possíveis respostas para o problema e submete essas ao processo de evolução. Durante esse processo, os indivíduos (possíveis soluções) presentes em uma população combinam-se gerando novos indivíduos. Entre esses, são selecionados os que forem considerados mais aptos para resolver o pro- blema. Sendo assim, os demais indivíduos são descartados. Esses melhores indivíduos são novamente submetidos ao processo de evolução até que uma solução seja encontrada ou alguma condição de parada seja invocada.

Durante as últimas décadas, diversas áreas adotaram os algoritmos genéticos como método para resolver os problemas de otimização. Entre essas podemos citar: Simulação de modelos biológicos, codificação de DNA, indução e otimização de bases de regras e até composição musical. Para cada uma dessas áreas o algoritmo sofre algumas alterações para adaptar-se ao problema em questão. A Figura 2.1 mostra a estrutura básica de funcionamento de um AG.

Em seu funcionamento os algoritmos genéticos iniciam suas operações e geram a popu- lação de indíviduos que são possíveis soluções. A geração desses normalmente é feita por um mecanismo aleatório que visa gerar indíduos com maior biodiversidade1 _{[Michael Bow-}

man e Labiche 2010]. Os indivíduos gerados são submetidos a um processo de avaliação, onde recebem uma nota ou um índice que indica o quão aptos eles são para combinarem-se a outras soluções formando novos indivíduos. A função de avaliação deve ser construída de acordo com o problema que está sendo tratado, fornecendo uma nota adequada a cada um dos indivíduos. Após gerar a população inicial e avaliar seus indivíduos o algoritmo termina sua primeira etapa. Na próxima etapa, funções como crossover e mutação são executadas. O Algoritmo1 descreve uma representação das funções em um pseudocódigo

1

Biodiversidade se refere ao termo utilizado em computação bio-inspirada, onde o significado está ligado a geração de dados de entrada distintos que serão usados em um algoritmo.

Figura 2.1: Estrutura de funcionamento de um algoritmo genético.

de um AG. Nele a variável t representa o tempo atual do algoritmo, P é a população que será gerada e d é um valor adotado como critério de parada.

Algoritmo 1 Algoritmo Genetico:

1: d ← Valor como critério de parada 2: IniciaP opulacao(P, t) 3: Avaliacao(P, t) 4: while t < d do 5: t ← t + 1 6: SelecionaReprodutores(P, t) 7: CruzaSelecionados(P, t) 8: M utaResultantes(P, t) 9: AvaliaResultantes(P, t) 10: AtualizaP opulacao(P, t) 11: end while

Após a primeira etapa mencionada anteriormente, o algoritmo entra no seu loop de controle (linha 4, Algoritmo1) onde pode ser definido um ou mais críterios de parada. No Algoritmo1 é definido apenas um tempo limite para interrupção do processo de busca do AG. A função SelecionaReprodutores(P, t) (linha 6) é responsável por selecionar os indi- víduos que melhor foram avaliados pela função Avaliacao(P, t) (linha 2). Esse processo

pode ser feito de diversas maneiras, utilizando rankings que classificam em posições os indivíduos, por giro de roleta que aleatoriamente determina uma posição e todos aque- les que estiverem a frente dessa posição são escolhidos e os demais são descartados, ou até mesmo por torneios, onde os indivíduos são divididos em grupos e cooperam para aumentar o valor de avaliação do grupo. O objetivo é selecionar aqueles que podem me- lhor disseminar suas características durante a reprodução gerando melhores indivíduos, ou seja, mais próximos da solução do problema.

A função CruzaSelecionados(P, t) (linha 7) realiza o processo chamado de crossover que gera novas soluções (indivíduos) para o problema. Inicialmente, a função faz o parea- mento para determinar quais pares de indivíduos serão combinados para reproduzirem. Esse processo também possui diversas maneiras de ser feito. Entre essas, é posssível combinar um indivíduo com alto índice de avaliação com um outro de baixa avaliação, combinar indivíduos com características semelhantes e até mesmo um indivíduo com ele mesmo. Após a etapa de pareamento é feito o cruzamento utilizando os operadores2

res- ponsáveis por isso. Esses operadores alteram a representação de cada par de indivíduos combinando suas representações de acordo com alguma modelagem. A representação de um indivíduo é geralmente feita por um vetor binário, onde esse possui o comprimento e os dados que mapeiam uma possível solução para o problema, sendo assim um indivíduo do algoritmo. Existem diversos operadores considerados tradicionais em um AG, contudo podem ser criados novos operadores, se necessário.

A mutação definida pelo método MutaResultantes(P, t) (linha 8) opera sobre os indi- víduos restantes do cruzamento com uma probabilidade de efetuar alguma mudança sobre eles. A ideia dessa função é representar as diversidades geradas pela mutação na natureza, assim é feita mais uma combinação entre as soluções nessa etapa. Os dois métodos fi- nais do algoritmo AvaliaResultantes(P, t) (linha 9) e AtualizaP opulacao(P, t) (linha 10) avaliam os novos indivíduos gerados e os inserem na população original P . Com isso, é feito o teste se o algoritmo deve parar ou não, caso continue, o processo de operações se repete e novos indivíduos são gerados.

Algumas das principais características dos algoritmos géneticos são:

• Busca codificada: Um AG não trabalha sobre o domínio do problema e sim sobre uma representação de suas soluções, isso pode ser útil quando é necessário utilizar a técnica em diferentes problemas.

• Busca através de hiperplanos: Através dos operadores de cruzamento é possível guiar a busca de forma que sejam evitados máximos e mínimos locais de um problema [Michael Bowman e Labiche 2010].

2

Operador em um algoritmo de busca, é responsável por efetuar uma operação ou mudança sobre uma determinada possível solução da busca com o objetivo de modificar essa ou gerar uma nova possível solução

• Paralelismo na implementação: Considerando que cada indivíduo do algoritmo pode ser modelado como um objeto único ou um conjunto de invíduos como uma instância, é possível simplificar e acelerar o processo de construir várias soluções utilizando de paralelismo na execução deste processo.

Dessa maneira, os algoritmos genéticos são uma das princípais técnicas de busca local, tendo sua aplicação estendida a várias áreas e problemas.