Aula 2: Técnicas de Otimização em SBSE

# Representação direta (real-valued encoding)
chromosome = [max_connections, thread_pool_size, cache_size_mb, timeout_ms]
# Exemplo: [200, 50, 512, 5000]

# Representação binária (para espaços discretos pequenos)
# max_connections (50-500) precisa de 9 bits: 2^9 = 512 > 450
binary_chromosome = "001100100" + "0110010" + "1000000000" + "0001001110101000"

def evaluate_web_server_config(chromosome):
    max_conn, threads, cache, timeout = chromosome
    
    # Simular throughput (requests/second)
    throughput = min(max_conn * 0.8, threads * 15) * (1 + cache/2048)
    
    # Simular latência média (ms)
    latency = 10 + (max_conn / threads) * 2 + (5000 - timeout) / 1000
    
    # Penalizar configurações inválidas
    if threads > max_conn * 0.3:  # Muitos threads para poucas conexões
        throughput *= 0.7
    
    # Função objetivo composta (maximizar throughput, minimizar latência)
    fitness = throughput / (latency / 100)  # Normalização
    
    return fitness

def crossover_web_config(parent1, parent2):
    """Crossover uniforme com constraints de domínio"""
    child = []
    for i in range(len(parent1)):
        if random.random() < 0.5:
            child.append(parent1[i])
        else:
            child.append(parent2[i])
    
    # Aplicar constraints
    child[1] = min(child[1], child[0] // 3)  # threads <= connections/3
    
    return child

def mutate_web_config(chromosome, mutation_rate=0.1):
    """Mutação gaussiana com bounds"""
    ranges = [(50, 500), (10, 100), (64, 1024), (1000, 30000)]
    
    for i in range(len(chromosome)):
        if random.random() < mutation_rate:
            # Mutação gaussiana com 10% do range
            std_dev = (ranges[i][1] - ranges[i][0]) * 0.1
            chromosome[i] += random.gauss(0, std_dev)
            
            # Aplicar bounds
            chromosome[i] = max(ranges[i][0], 
                              min(ranges[i][1], int(chromosome[i])))
    
    return chromosome

# Pseudocódigo de comparação
algorithms = {
    'hill_climbing': HillClimbing(neighbor_func=mutate_web_config),
    'simulated_annealing': SimulatedAnnealing(temp_schedule='exponential'),
    'genetic_algorithm': GeneticAlgorithm(pop_size=50, crossover_rate=0.8),
    'particle_swarm': ParticleSwarm(n_particles=30, inertia=0.7)
}

results = {}
for name, algo in algorithms.items():
    best_solution, fitness_history = algo.optimize(
        fitness_func=evaluate_web_server_config,
        max_evaluations=2000
    )
    results[name] = {
        'best_fitness': best_solution.fitness,
        'convergence_speed': generations_to_95_percent(fitness_history),
        'final_config': best_solution.genes
    }

# Representação matricial para decomposição de serviços
class MicroserviceArchitecture:
    def __init__(self, n_classes, max_services):
        # Matrix onde element[i][j] = 1 se classe i está no serviço j
        self.assignment_matrix = np.zeros((n_classes, max_services))
        
    def to_chromosome(self):
        """Converte para cromossomo linear"""
        # Cada gene representa o serviço da classe i
        return [np.argmax(row) for row in self.assignment_matrix]
    
    def from_chromosome(self, chromosome):
        """Reconstrói matriz a partir do cromossomo"""
        self.assignment_matrix.fill(0)
        for class_idx, service_idx in enumerate(chromosome):
            self.assignment_matrix[class_idx][service_idx] = 1
            
    def calculate_cohesion(self):
        """Métrica de coesão intra-serviço"""
        cohesion_sum = 0
        for service_idx in range(self.max_services):
            classes_in_service = np.where(self.assignment_matrix[:, service_idx])[0]
            if len(classes_in_service) > 1:
                # Calcular coesão baseada em dependências
                internal_deps = count_internal_dependencies(classes_in_service)
                possible_deps = len(classes_in_service) * (len(classes_in_service) - 1)
                cohesion_sum += internal_deps / possible_deps if possible_deps > 0 else 0
        return cohesion_sum

# Representação de tamanho variável para sequência de refatorações
class RefactoringSequence:
    def __init__(self):
        self.operations = []  # Lista de (tipo_refactoring, target_class, params)
    
    def crossover_variable_length(self, other):
        """Crossover que preserva dependências entre refatorações"""
        # Identificar subsequências válidas
        valid_subseqs_self = self.find_independent_subsequences()
        valid_subseqs_other = other.find_independent_subsequences()
        
        # Combinar subsequências respeitando precedência
        child = RefactoringSequence()
        child.operations = self.merge_preserving_dependencies(
            random.choice(valid_subseqs_self),
            random.choice(valid_subseqs_other)
        )
        return child
    
    def mutate_structure(self):
        """Mutação que pode adicionar, remover ou modificar operações"""
        mutation_type = random.choice(['add', 'remove', 'modify'])
        
        if mutation_type == 'add' and len(self.operations) < MAX_SEQUENCE_LENGTH:
            insertion_point = random.randint(0, len(self.operations))
            new_operation = self.generate_compatible_operation(insertion_point)
            self.operations.insert(insertion_point, new_operation)
            
        elif mutation_type == 'remove' and len(self.operations) > 1:
            removal_point = random.randint(0, len(self.operations) - 1)
            removed = self.operations.pop(removal_point)
            # Verificar e reparar dependências quebradas
            self.repair_broken_dependencies(removed)

class SoftwareQualityFitness:
    def __init__(self, weights=None):
        self.weights = weights or {
            'maintainability': 0.3,
            'performance': 0.3,
            'security': 0.2,
            'testability': 0.2
        }
    
    def evaluate(self, software_design):
        objectives = {
            'maintainability': self.calculate_maintainability(software_design),
            'performance': self.estimate_performance(software_design),
            'security': self.assess_security_risks(software_design), 
            'testability': self.measure_testability(software_design)
        }
        
        # Abordagem 1: Weighted Sum (Single-objective)
        weighted_fitness = sum(
            self.weights[obj] * value 
            for obj, value in objectives.items()
        )
        
        # Abordagem 2: Pareto Ranking (Multi-objective)
        pareto_rank = self.calculate_pareto_rank(objectives)
        
        # Abordagem 3: Constraint-based (penalty)
        penalty = 0
        if objectives['security'] < MINIMUM_SECURITY_THRESHOLD:
            penalty += 1000 * (MINIMUM_SECURITY_THRESHOLD - objectives['security'])
            
        return {
            'weighted': weighted_fitness - penalty,
            'pareto_rank': pareto_rank,
            'objectives': objectives,
            'penalty': penalty
        }

class AdaptiveFitnessFunction:
    def __init__(self):
        self.evaluation_history = []
        self.diversity_pressure = 0.1
        self.difficulty_adjustment = 1.0
        
    def evaluate_with_context(self, solution, generation, population):
        # Fitness base
        base_fitness = self.base_evaluation(solution)
        
        # Pressure por diversidade (penalizar soluções muito similares)
        diversity_bonus = self.calculate_diversity_bonus(solution, population)
        
        # Adaptive difficulty (aumentar standards ao longo do tempo)
        adjusted_fitness = base_fitness * self.difficulty_adjustment
        
        # Novelty search component (recompensar soluções diferentes)
        novelty_score = self.calculate_novelty(solution, self.evaluation_history)
        
        final_fitness = (
            adjusted_fitness + 
            self.diversity_pressure * diversity_bonus +
            0.1 * novelty_score
        )
        
        # Update history e adaptive parameters
        self.evaluation_history.append(solution)
        if generation % 10 == 0:
            self.update_difficulty_adjustment(population)
            
        return final_fitness
    
    def update_difficulty_adjustment(self, population):
        """Aumenta difficulty se população está convergindo muito rápido"""
        avg_fitness = np.mean([ind.fitness for ind in population])
        fitness_std = np.std([ind.fitness for ind in population])
        
        if fitness_std < 0.05 * avg_fitness:  # Baixa diversidade
            self.difficulty_adjustment *= 1.1
        elif fitness_std > 0.2 * avg_fitness:  # Alta diversidade
            self.difficulty_adjustment *= 0.95

class MemeticAlgorithm:
    def __init__(self, ga_params, local_search_params):
        self.genetic_algorithm = GeneticAlgorithm(**ga_params)
        self.local_search = LocalSearch(**local_search_params)
        self.local_search_frequency = 0.2  # 20% dos indivíduos
        
    def evolve_generation(self, population):
        # Fase 1: Evolução genética padrão
        new_population = self.genetic_algorithm.evolve_generation(population)
        
        # Fase 2: Busca local em indivíduos selecionados
        for individual in new_population:
            if random.random() < self.local_search_frequency:
                improved = self.local_search.improve(individual)
                if improved.fitness > individual.fitness:
                    individual = improved
                    
        return new_population

class IslandGeneticAlgorithm:
    def __init__(self, n_islands, migration_rate=0.05):
        self.islands = [GeneticAlgorithm() for _ in range(n_islands)]
        self.migration_rate = migration_rate
        self.migration_topology = 'ring'  # ring, star, fully_connected
        
    def run_evolution(self, generations):
        for generation in range(generations):
            # Evolve each island independently
            for island in self.islands:
                island.evolve_generation()
                
            # Migration every 10 generations
            if generation % 10 == 0:
                self.perform_migration()
                
    def perform_migration(self):
        """Exchange best individuals between islands"""
        if self.migration_topology == 'ring':
            for i in range(len(self.islands)):
                next_island = (i + 1) % len(self.islands)
                migrants = self.islands[i].select_migrants(
                    int(len(self.islands[i].population) * self.migration_rate)
                )
                self.islands[next_island].accept_migrants(migrants)

def analyze_algorithm_performance(fitness_history):
    """Analisa características de convergência do algoritmo"""
    
    # 1. Convergence Speed
    target_fitness = max(fitness_history) * 0.95
    convergence_generation = next(
        (i for i, f in enumerate(fitness_history) if f >= target_fitness),
        len(fitness_history)
    )
    
    # 2. Diversity Loss Rate  
    diversity_over_time = [
        calculate_population_diversity(generation) 
        for generation in fitness_history
    ]
    diversity_slope = np.polyfit(range(len(diversity_over_time)), diversity_over_time, 1)[0]
    
    # 3. Exploration vs Exploitation Balance
    improvement_frequency = [
        1 if fitness_history[i] > fitness_history[i-1] else 0
        for i in range(1, len(fitness_history))
    ]
    exploration_ratio = np.mean(improvement_frequency)
    
    # 4. Premature Convergence Detection
    plateau_threshold = 50  # gerações sem melhoria significativa
    current_plateau = 0
    max_plateau = 0
    
    for i in range(1, len(fitness_history)):
        if abs(fitness_history[i] - fitness_history[i-1]) < 0.001:
            current_plateau += 1
            max_plateau = max(max_plateau, current_plateau)
        else:
            current_plateau = 0
    
    return {
        'convergence_speed': convergence_generation / len(fitness_history),
        'diversity_retention': abs(diversity_slope),
        'exploration_ratio': exploration_ratio,
        'max_plateau_length': max_plateau,
        'premature_convergence': max_plateau > plateau_threshold
    }