Redes Neurais, Algoritmos Genéticos e Lógica Fuzzy

1. Redes Neurais Artificiais (RNA)

a) Defina o que é uma RNA

Redes Neurais Artificiais são dispositivos de computação paralela que consistem de muitos processadores interconectados (neurônios artificiais). Cada processador conhece apenas os sinais que envia e recebe periodicamente de outros processadores. Essas redes são usadas para modelar funções complexas, reconhecimento de padrões, regressão, entre outros problemas de aprendizagem.

b) Quais os elementos fundamentais de uma RNA? Ilustre e exemplifique

Os elementos fundamentais de uma RNA são:

• Conjunto de neurônios artificiais — unidades de processamento que recebem entradas, aplicam uma função de ativação e produzem saídas.
• Padrão de conexão (arquitetura) — define como os neurônios estão organizados em camadas e como se conectam (ex.: redes feedforward, redes recorrentes).
• Método de ajuste de pesos (algoritmo de treinamento) — algoritmo que determina os valores dos pesos sinápticos, por exemplo, retropropagação (backpropagation), gradiente descendente, aprendizagem por reforço.

Observação: Uma ilustração de um neurônio e de uma estrutura em camadas (camada de entrada, camadas ocultas e camada de saída) pode ajudar na explicação.

c) A afirmação sobre o número de neurônios na camada de saída

A afirmação "Quanto mais neurônios na camada de saída, melhor a qualidade do resultado de uma RNA" é falsa. A quantidade de neurônios na saída está diretamente relacionada ao problema. Por exemplo, em um sistema de reconhecimento de padrões (classificação), o número de neurônios na saída deve ser igual ao número de classes a serem discriminadas. Aumentar indevidamente o número de neurônios na saída não melhora a qualidade e pode introduzir redundância ou overfitting.

2. Problema do Trajeto (PCV) e Algoritmo Genético

A Figura 1 apresenta um grafo com a ligação entre 5 cidades e as respectivas distâncias em quilômetros. Tem-se um problema onde é necessário passar por todas as cidades apenas uma vez. O objetivo é encontrar uma rota de menor custo usando um Algoritmo Genético.

Imagem

a) Proponha uma maneira de codificar os cromossomos

Uma codificação comum é representar cada gene como uma cidade, formando uma permutação das cidades. Exemplo de indivíduo: 1 2 3 4 5.

b) Defina uma função de aptidão

A função de aptidão (fitness) pode ser a soma das distâncias ao longo do percurso representado pelo indivíduo. Em algoritmos genéticos para minimização, pode-se usar a inversa da distância total ou simplesmente comparar distâncias totais (menor é melhor).

c) Gere dois cromossomos e avalie a aptidão deles

Exemplos:

• Indivíduo 01: 1 2 3 4 5 — Fitness (soma das distâncias): 2 + 4 + 3 + 3 + 3 = 15
• Indivíduo 02: 1 3 5 4 2 — Fitness: 9 + 7 + 3 + 8 + 2 = 29

d) Realize o cruzamento entre os cromossomos do item c

Um cruzamento simples aplicado no terceiro gene pode produzir, se feito sem respeitar a restrição de permutação, sequências inválidas (com repetições):

• Indivíduo 01 (parental): 1 2 3 4 5 → tentativa de cruzamento: 1 2 3 4 5 1 2 3 4 2
• Indivíduo 02 (parental): 1 3 5 4 2 → tentativa de cruzamento: 1 3 5 4 2 1 3 5 4 5

Nesse caso, os indivíduos gerados não atendem à restrição do problema (não repetir cidades). Para o Problema do Caixeiro Viajante (PCV), foram desenvolvidos operadores de cruzamento que preservam permutações, entre os principais estão: PMX (Partially Matched Crossover), OX (Order Crossover), CX (Cycle Crossover) e HX (Heuristic Crossover).

Considere então como fruto de um cruzamento os seguintes novos indivíduos válidos:

• Indivíduo 01: 1 5 3 4 2
• Indivíduo 02: 1 3 2 4 5

e) Aplique uma mutação em um gene dos cromossomos do item c

Aplicando uma mutação (por exemplo, troca de posições) nos descendentes:

• Indivíduo 01 (antes): 1 5 3 4 2 — Mutação (troca 1 com 2): 2 5 3 4 1
• Indivíduo 02 (antes): 1 3 2 4 5 — Mutação (troca 3 com 4): 1 4 2 3 5

f) Avalie a aptidão dos descendentes gerados

• Indivíduo 01: 2 5 3 4 1 — Fitness: 3 + 7 + 3 + 6 + 2 = 21
• Indivíduo 02: 1 4 2 3 5 — Fitness: 6 + 8 + 4 + 7 + 3 = 28

Comparando com os pais, observa-se que os descendentes não são melhores que o Indivíduo 01 original (15), portanto a solução encontrada neste exemplo não melhorou em relação ao melhor parental (15).

3. Colônia de Formigas (CF)

a) Defina o que é Colônia de Formigas

Colônia de Formigas é um método de otimização inspirado no comportamento real das formigas. Ao caminhar, as formigas depositam feromônio ao longo do trajeto. Com o passar do tempo, trajetos mais curtos tendem a concentrar mais feromônio, favorecendo sua escolha por outras formigas e, assim, emergindo rotas de melhor qualidade.

b) Elementos fundamentais da Colônia de Formigas

Os principais elementos do algoritmo são:

• Regra de transição probabilística — define a probabilidade de uma formiga escolher a próxima aresta com base no feromônio e numa heurística (por exemplo, visibilidade/inversa da distância).
• Regra de atualização de feromônio — feromônio é depositado ao longo das trajetórias pelas formigas; também existe evaporação que evita convergência prematura.
• Parâmetros do algoritmo — número de iterações, número de formigas, taxa de feromônio inicial, coeficientes que ponderam a influência do feromônio (α) e da heurística (β), e taxa de evaporação (ρ).

Observação: Vale explicar como as regras interagem: a regra de transição orienta a construção de soluções pelas formigas; a atualização reforça rotas boas; a evaporação permite explorar novas soluções.

4. Lógica Fuzzy

a) Negação em lógica fuzzy — valores-verdade

Dado que o valor-verdade da negação é 1 menos o valor-verdade da proposição, e considerando:

• pf = 0,8 : "Fred é feliz"
• pj = 0,4 : "John é feliz"

Temos:

• "Fred não é feliz": 1 − pf = 1 − 0,8 = 0,2
• "John não é feliz": 1 − pj = 1 − 0,4 = 0,6

b) Disjunção (ou) em lógica fuzzy — valores-verdade

Na lógica fuzzy, a disjunção (operador ou) é definida como o máximo dos valores-verdade:

p ∨ q = max(p, q)

Aplicando aos valores fornecidos:

• "Fred é feliz ou John é feliz": max(0,8; 0,4) = 0,8
• "Fred não é feliz ou John não é feliz": max(0,2; 0,6) = 0,6

Utilize os valores-verdade:

• pf = 0,8: "Fred é feliz"
• pj = 0,4: "John é feliz"