Algoritmo de busca

Olá, Taís. Tudo bem?

Construir um algoritmo genético em C envolve alguns conceitos fundamentais de evolução, como seleção, cruzamento e mutação. Vou te dar algumas dicas para começar:

1. Estrutura do Algoritmo Genético:

   • População: A primeira coisa é criar uma população inicial com possíveis soluções.
   • Função de avaliação: Você precisa de uma função que avalie o "fitness" (aptidão) de cada solução.
   • Seleção: As melhores soluções são selecionadas para formar uma nova geração.
   • Cruzamento (Crossover): Algumas soluções são combinadas para gerar novas soluções.
   • Mutação: Algumas soluções podem ser modificadas aleatoriamente para adicionar diversidade.

2. Exemplo de Estrutura Básica em C:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define POPULACAO 10 // Tamanho da população
#define GENOMA 5 // Tamanho de cada solução (genoma)

// Função para avaliar o fitness de uma solução
int fitness(int genoma[]) {
    int soma = 0;
    for (int i = 0; i < GENOMA; i++) {
        soma += genoma[i];
    }
    return soma;
}

// Função para gerar um número aleatório entre 0 e 1
int rand_bin() {
    return rand() % 2;
}

// Função para criar a população inicial
void criar_populacao(int populacao[POPULACAO][GENOMA]) {
    for (int i = 0; i < POPULACAO; i++) {
        for (int j = 0; j < GENOMA; j++) {
            populacao[i][j] = rand_bin();
        }
    }
}

// Função principal
int main() {
    srand(time(NULL)); // Inicializa o gerador de números aleatórios

    int populacao[POPULACAO][GENOMA];
    criar_populacao(populacao);

    // Avalia a aptidão de cada indivíduo
    for (int i = 0; i < POPULACAO; i++) {
        printf("Individuo %d: ", i);
        for (int j = 0; j < GENOMA; j++) {
            printf("%d ", populacao[i][j]);
        }
        printf(" Fitness: %d\n", fitness(populacao[i]));
    }

    return 0;
}

1. Explicação do Código:

   • População: A população é representada por uma matriz populacao[POPULACAO][GENOMA], onde cada linha é um genoma de uma solução possível.
   • Fitness: A função fitness soma os valores dos genes do genoma (quanto mais próximo de 1, melhor a solução).
   • Geração aleatória: Cada indivíduo na população é gerado aleatoriamente com 0s e 1s através da função rand_bin().
   • Avaliação: O código imprime o genoma de cada indivíduo da população e sua aptidão (fitness).

2. Próximos Passos:

   • Seleção: Selecionar os melhores indivíduos com base na aptidão.
   • Cruzamento: Combinar dois genomas para formar um novo.
   • Mutação: Alterar aleatoriamente um gene de um indivíduo para introduzir diversidade.

Espero ter ajudado. Conte com o apoio do Fórum. Fico à disposição.

Abraços e bons estudos!

Tudo bem Renan. Obrigada pelo retorno. Como seria em Python? Teria alguma implementação especifica para otimizar jogos? Nesse caso o jogo é o Pac-Man.

Olá, Taís.

Sobre sua última dúvida, vou mostrar como implementar um algoritmo genético em Python que pode ser ajustado para otimizar estratégias de jogos como o Pac-Man.A ideia básica é usar o algoritmo genético para ensinar o personagem a escolher o melhor caminho para maximizar pontos ou evitar inimigos.

Veja este exemplo inicial:

import random

# Configurações do algoritmo
POPULATION_SIZE = 20
GENOME_LENGTH = 10  # Número de passos ou decisões
GENERATIONS = 50
MUTATION_RATE = 0.1

# Função de avaliação (fitness): avalia pontuação para um genoma
def evaluate(genome):
    # Aqui você adapta o cálculo ao Pac-Man, considerando coleta de pontos e desvio de inimigos
    score = 0
    for step in genome:
        if step == 1:  # Exemplo: passo para frente coleta pontos
            score += 10
        elif step == 0:  # Exemplo: passo inválido (bateu na parede)
            score -= 5
    return score

# Função para criar a população inicial
def generate_population():
    return [[random.randint(0, 1) for _ in range(GENOME_LENGTH)] for _ in range(POPULATION_SIZE)]

# Seleção: Escolhe os melhores indivíduos com base na aptidão
def select(population, fitness):
    sorted_population = sorted(zip(population, fitness), key=lambda x: x[1], reverse=True)
    return [ind for ind, _ in sorted_population[:POPULATION_SIZE // 2]]

# Cruzamento (crossover): Combina dois genomas para criar descendentes
def crossover(parent1, parent2):
    point = random.randint(1, GENOME_LENGTH - 1)
    return parent1[:point] + parent2[point:]

# Mutação: Altera aleatoriamente genes para diversidade
def mutate(genome):
    for i in range(len(genome)):
        if random.random() < MUTATION_RATE:
            genome[i] = 1 - genome[i]
    return genome

# Algoritmo Genético
def genetic_algorithm():
    population = generate_population()
    for generation in range(GENERATIONS):
        # Avalia a população
        fitness = [evaluate(genome) for genome in population]
        
        # Seleciona os melhores indivíduos
        selected = select(population, fitness)
        
        # Gera nova população com cruzamentos e mutações
        new_population = []
        while len(new_population) < POPULATION_SIZE:
            parent1, parent2 = random.sample(selected, 2)
            offspring = crossover(parent1, parent2)
            new_population.append(mutate(offspring))
        population = new_population

        # Melhor indivíduo da geração atual
        best_genome = population[fitness.index(max(fitness))]
        print(f"Geração {generation + 1}: Melhor fitness = {max(fitness)}, Genoma = {best_genome}")

    return best_genome

# Executa o algoritmo genético
best_solution = genetic_algorithm()
print("Melhor solução encontrada:", best_solution)

Como aplicar ao Pac-Man:

1. Customizar a avaliação (fitness): Inclua regras para:
   • Penalizar colisões com fantasmas.
   • Recompensar comer pílulas e frutas.
   • Pontuar a distância percorrida em relação ao objetivo.
2. Genoma: Em vez de 0s e 1s, use ações como esquerda, direita, cima e baixo (por exemplo, números 0-3).
3. Ambiente do jogo: Integre essa lógica a um simulador do Pac-Man (como o Pygame) para avaliar o genoma diretamente no mapa.

Fico à disposição. Abraços e bons estudos!

Bom dia Renan,

Desculpa a demora para responder. Obrigada pela ajuda. Foi útil sim. No momento estou desenvolvendo um banco de dados para otimizar a gestão de leitos de internação hospitalar. Desejo saber:

1. Quais informações deve conter o documento MAD - Metodologia de Administração de Dados?
2. O que seria o tuning no Banco de dados?
3. Pelo sqlLite é possível também trabalhar com views, procedure, índices, backup?
4. Qual o melhor caminho para gerar dados fictícios de cadastro de pessoas como nomes, telefones, endereços e e-mails, usando o GPT? Quero gerar umas 850.(para clientes, enfermeiros, médicos, funcionários...)

Na parte de testes, qual curso abrange os testes baseado na especificação ( partição por equivalência, partição por categoria...) e testes estruturais ( critérios de cobertura de linha, cobertura de condição, cobertura de ramificação, cobertura de caminhos) usando o Junit?

Oi Taís,

Sugiro marcar a resposta do Renan como solucionado ☑️ e abrir um novo tópico no Forum 😎

Bons Estudos! 🤓

Ok. Obrigada.