<jupyter_start><jupyter_text>El problema binario 3-SAT utilizando un Algoritmo Genético<jupyter_code>import pandas as pd 
import numpy as np
import math
import matplotlib.pylab as plt
#### Cargando la instancia

X = pd.read_csv("uf20-017.cnf", sep=' ', header = 0)
numVariables = int(X.columns[2])
numClausulas = int(X.columns[3])
X.drop(X.columns[3], axis = 'columns', inplace = True)
X.columns = range(X.shape[1])
print(X)
print(numVariables)
print(numClausulas)<jupyter_output>0   1   2
0    5  -6   2
1  -14   4 -15
2    4  -2  16
3    9  -2   4
4   16  -8   6
..  ..  ..  ..
86 -19   7 -13
87   1   3  15
88  20  10  -9
89  11 -12   1
90 -13  -7  10

[91 rows x 3 columns]
20
91<jupyter_text>Funciones fitness Función de fitness 1: Evaluar expresión booleana dada por X<jupyter_code>def fitness1(individuo, X, numVariables, numClausulas):
    
    expression = True
    
    for i in range(numClausulas): 
        # Operar las 3 variables de la clausula i con el or
        aux = False
        
        x1 = X[0][i]
        x2 = X[1][i]
        x3 = X[2][i]
        
        if x1 < 0:
            aux = aux or (not individuo[-x1-1])
        else:
            aux = aux or individuo[x1-1]
            
        if x2 < 0:
            aux = aux or (not individuo[-x2-1])
        else:
            aux = aux or individuo[x2-1]
            
        if x3 < 0:
            aux = aux or (not individuo[-x3-1])
        else:
            aux = aux or individuo[x3-1]
            
        expression = expression and aux
            
    return int(expression)<jupyter_output><empty_output><jupyter_text>Función de fitness 2: Contar el número de "Trues" en en las cláusulas<jupyter_code>def fitness2(individuo, X, numVariables, numClausulas):
    
    count = 0
    
    for i in range(numClausulas): 
        # Operar las 3 variables de la clausula i con el or
        aux = False
        
        x1 = X[0][i]
        x2 = X[1][i]
        x3 = X[2][i]
        
        if x1 < 0:
            aux = aux or (not individuo[-x1-1])
        else:
            aux = aux or individuo[x1-1]
            
        if x2 < 0:
            aux = aux or (not individuo[-x2-1])
        else:
            aux = aux or individuo[x2-1]
            
        if x3 < 0:
            aux = aux or (not individuo[-x3-1])
        else:
            aux = aux or individuo[x3-1]
            
        count += aux
            
    return count<jupyter_output><empty_output><jupyter_text>Operador de selecciónTorneo binario<jupyter_code>def selectionOperator(X, numVariables, numClausulas, P, N, fitness, mu): 
    # 2*mu es el numero de torneos binarios, por lo que habra mu ganadores
    # regresa los indices de los individuos en P seleccionados
    
    randomIndex = np.random.choice(N, 2*mu, replace=True)
    winners = []
        
    k=0
    while 2*k+1 < 2*mu:
        i1 = randomIndex[2*k]
        i2 = randomIndex[2*k+1]

        i1_fitness = fitness(P[i1], X, numVariables, numClausulas)
        i2_fitness = fitness(P[i2], X, numVariables, numClausulas)

        if i1_fitness > i2_fitness:
            winners.append(i1)
        else:
            winners.append(i2)
        k += 1
            
    return winners<jupyter_output><empty_output><jupyter_text>Operador de cruzaCruza en dos puntos<jupyter_code>def crossoverOperator(S, numVars, mu):
    # S es la poblacion seleccionada de P a traves del operador de seleccion
    # mu es el numero de padres a cruzar, el tamaño de S
    # La cruza se hace en S mismo para optimizar
    
    randomIndex = np.random.choice(mu, mu, replace=False)
    
    i=0
    while 2*i+1<mu :
        i1 = randomIndex[2*i]
        i2 = randomIndex[2*i+1]
        
        # 2 puntos de crossover
        crossPoints = np.random.choice(range(1,numVars-1), 2, replace=False)
        crossPoints.sort()
        
        # Cruza de S[i1] con S[i2]
        offspring1 = S[i1]
        offspring2 = S[i2]
            
        for k in range(numVars):
            if k>=crossPoints[0] and k<=crossPoints[1]: # intercambio de bits de los individuos entre los puntos de cruza
                aux = offspring1[k]
                offspring1[k] = offspring2[k]
                offspring2[k] = aux
        
        i += 1<jupyter_output><empty_output><jupyter_text>Operador de mutaciónMutación uniforme<jupyter_code>def uniformMutationOperator(C, numVars, p):
    # C es el conjunto de individuos obtenidos al aplicar el operador de cruza
    # p es la probabilidad de mutacion
    # La mutacion dentro de C para optimizar
    
    for i in range(len(C)):
        for j in range(numVars):
            if np.random.uniform() <= p:
                C[i][j] = not C[i][j]<jupyter_output><empty_output><jupyter_text>Operador de reemplazoElitismo del 10%<jupyter_code>def reemplazoElitismo(X, numVars, numClausulas, P, C_mut, percent, fitness):
    
    fit = []
    
    for i in range(len(P)):
        pair = (fitness(P[i], X, numVars, numClausulas), i)
        fit.append(pair)
    
    fit.sort(reverse=True)
    print(fit)
    elite = fit[:int(len(P)*percent)]
    print('Fitness del mejor de P: ' + str(elite[0][0]))
    R = []
    
    for i in range(len(elite)):
        R.append(P[elite[i][1]][:])
    for i in range(len(C_mut)):
        R.append(C_mut[i][:])
    
    return R<jupyter_output><empty_output><jupyter_text>Algoritmo genéticoTiene como argumentos a un dataframe con la información de la instancia del problema en formado cnf, el número de variables booleanas (numVariables), el número de cláusulas (numClausulas), y la función fitness.<jupyter_code>def solveSAT(X, numVariables, numClausulas, fitness, N=100, elite_percent=0.1, maxIter=100):
    
    mu = int((1-elite_percent)*N) # complemento del porcentaje de la elite
    prob_mutation = 1.0/numVariables
    
    # Poblacion inicial de tamaño N con distribucion uniforme
    P = []
    for i in range(N):
        P.append(list(np.random.choice([True, False], numVariables, replace=True)))
    
    best_fitness = []
        
    for t in range(maxIter):
        # Evaluacion de P
        fit = []
    
        for i in range(N):
            pair = (fitness(P[i], X, numVariables, numClausulas), i)
            fit.append(pair)

        fit.sort(reverse=True)
        elite = fit[:int(len(P)*elite_percent)]
        print('Generacion: ' + str(t) + ' - Mejor fitness de P: ' + str(elite[0][0]) + " - Indice " + str(elite[0][1]))
        
        best_fitness.append(elite[0][0])
        
        # Seleccion por torneo binario
        winners = selectionOperator(X, numVariables, numClausulas, P, N, fitness, mu)

        P2 = []
        for i in range(len(winners)):
            P2.append(P[winners[i]][:])

        # Cruza
        crossoverOperator(P2, numVariables, mu)

        # Mutation
        uniformMutationOperator(P2, numVariables, prob_mutation)

        # Reemplazo 
        for i in range(len(elite)):
            P2.append(P[elite[i][1]][:])
            
        P = P2
        
    # Obtener el maximo fitness de la generacion maxIter
        
    maxFit = 0
    maxIndex = 0

    for i in range(N):
        aux = fitness(P[i],  X, numVariables, numClausulas)
        if aux > maxFit:
            maxFit = aux
            maxIndex = i
    best_fitness.append(maxFit)
    
    print('Generacion: ' + str(maxIter) + ' - Mejor fitness de P: ' + str(maxFit) + " - Indice " + str(maxIndex))
        
    return P[maxIndex], best_fitness<jupyter_output><empty_output><jupyter_text>Aplicación del algoritmo genético a la instancia del problema 3-SAT<jupyter_code>maxIter = 100
sol1, best_fitness1 = solveSAT(X, numVariables, numClausulas, fitness1, maxIter = maxIter)
sol1
fitness1(sol1, X, numVariables, numClausulas)
plt.plot(range(maxIter+1), best_fitness1)
plt.show()
sol2, best_fitness2 = solveSAT(X, numVariables, numClausulas, fitness2)
sol2
fitness2(sol2, X, numVariables, numClausulas)
plt.plot(range(maxIter+1), best_fitness2)
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10769037446594622, 'fraction_numerical': 0.028901734104046242, 'mean_word_length': 2.2685831622176593, 'pattern_counts': {'":': 0, '<': 46, '<?xml version=': 0, '>': 39, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '424548', 'license': 'MIT', 'n_tokens_mistral': 2901, 'n_tokens_neox': 2824, 'n_words': 730, 'path': 'GeneticAlgorithm/3-SAT_AlgoritmoGenetico.ipynb', 'repo_name': 'miguelruor/IA_code', 'size': '7958'}