Redes Neurais Artificiais e Algoritmos Genéticos

Sobre 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. Cada processador está ciente apenas dos sinais que manda para e recebe de outros processadores periodicamente.

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

Conjunto de neurônios artificiais
Um padrão de conexão entre os neurônios (Arquitetura ou estrutura da rede)
Método que determina o valor dos pesos (Algoritmo de treinamento ou aprendizagem)

OBS: Uma ilustração de um neurônio ou de uma estrutura de rede (com camadas) poderia ajudar na explicação.

c) Considere a seguinte afirmação: Quanto mais neurônios na camada de saída, melhor a qualidade do resultado de uma RNA. A afirmação é verdadeira ou falsa? Justifique.

A afirmação é falsa. A quantidade de neurônios na saída está relacionada diretamente ao problema. Por exemplo, em um sistema de reconhecimento de padrões (classificação), o número de neurônios na saída será igual ao número de classes que se deseja classificar.

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. Com base no problema, responda:

Imagem

a) Proponha uma maneira de codificar os cromossomos.

Cada gene em um indivíduo seria uma cidade (Permutação de cidades).
Ex: 1 2 3 4 5

b) Defina uma função de aptidão para avaliar a qualidade dos cromossomos.

A função de aptidão poderia ser a soma das distâncias envolvendo as cidades do indivíduo.

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

Indivíduo 01: 1 2 3 4 5 - Fitness: 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.

Cruzamento no terceiro gene
Indivíduo 01: 1 2 3 4 5 1 2 3 4 2
Indivíduo 02: 1 3 5 4 2 1 3 5 4 5
Neste caso, os indivíduos gerados não atendem a restrição do problema (não repetir cidades no trajeto). Para o PCV, diversas formas de codificação e seus respectivos operadores de cruzamento foram desenvolvidos, dentre os principais operadores estão PMX (Partially Matched Crossover), OX (Order Crossover), CX (Cicle Crossover) e HX (Heuristic Crossover). Considere então como fruto de um cruzamento os seguintes novos indivíduos:
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.

Indivíduo 01: 1 5 3 4 2 Mutação: 2 5 3 4 1
Indivíduo 02: 1 3 2 4 5 Mutação: 1 4 2 3 5

f) Aplique a função de aptidão nos descendentes gerados verificando se a solução encontrada é melhor ou não.

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

Sobre Colônia de Formigas (CF)

a) Defina o que é CF.

Algoritmo baseado no comportamento real dos formigueiros. Ao caminhar, as formigas depositam feromônio ao longo do trajeto. Com o passar do tempo, trajetos de menor distância terão maior concentração de feromônio, o que vai favorecer na sua escolha por outras formigas.

b) Quais os elementos fundamentais da CF? Ilustre e exemplifique.

- Regra de transição probabilística
- Regra para atualização de feromônio
- Número máximo de iterações e número de formigas. Além desses, a taxa feromônio inicial, os pesos para concentração de feromônio (ƒ¿) e qualidade da função (ƒÀ) e a taxa de evaporação também são importantes. OBS: Cabe aqui explicar um pouco o que as regras fazem e como é o funcionamento do algoritmo básico.

Sobre Lógica Fuzzy

a) O valor-verdade da negação de uma proposição em lógica fuzzy é 1 menos o valor-verdade da proposição. Quais são os valores-verdade das proposições "Fred não é feliz" e "John não é feliz"?

pf = 0,8: "Fred é feliz"; pj = 0,4: "John é feliz". Ɛpf = 1 ? pf = 1 ? 0,8 = 0,2: "Fred não é feliz"; Ɛpj = 1 ? pj = 1 ? 0,4 = 0,6: "John não é feliz";

b) O valor-verdade da disjunção (operador or/ou) de duas proposições em lógica fuzzy é o máximo dos valores-verdade de duas proposições. Quais são os valores-verdade das proposições "Fred é feliz ou John é feliz" e "Fred não é feliz ou John não é feliz"?

Sejam p e q variáveis da Lógica Fuzzy. A disjunção p q = max(p ; q). (a) "Fred é feliz ou John é feliz". pf pj = max(Ɛ Ɛ 0,8; 0,4) = 0,8. (b) "Fred não é feliz ou John não é feliz" Ɛpf Ɛpj = max(0,2; 0,6) = 0,6. Utilize os seguintes valores-verdade: pf = 0,8: "Fred é feliz"; pj = 0,4: "John é feliz".