encuentra la mejor combinación con algoritmo

12 Jul, 2023 Programación 0

Tengo 49 puntos y quiero encontrar la mejor combinación para la selección de n puntos entre los 49 puntos para maximizar mi función objetivo. Mi función objetivo es lineal Zc = max(f1 - ωf2). Por ejemplo, quiero encontrar los mejores 10 puntos en los que se maximiza la función objetivo. f1 es la eficiencia del modelo de Nash-Sutcliffe que se calcula utilizando los puntos interpolados para all_points y los puntos seleccionados que son candidate_1. ω es el coeficiente de ponderación que tiene el valor 0.3 y f2 es la proporción de puntos seleccionados con respecto al total de puntos (10/49). Por lo tanto, mi función objetivo tiene un rango de [-∞,1] y cuanto más cercana esté la función objetivo a 1, más óptima será la respuesta. Así que supuse que K es el valor interpolado para candidate_1 y j es el valor interpolado para all_point, y L es la media de j. Utilizo este marco para calcular f1 y la función objetivo.

all_points = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48]
candidate_1 = [3,6,11,12,14,17,19,23,28,43]

Calcular f1 y f2

[f1 ecuación][1]

f2 = 10/49

Calcular función objetivo

Zc = f1 – 0.3*f2

Imprimir valor de la función objetivo

Zc = 0.59

El siguiente paso es crear otro candidato que mejore la función objetivo

“`
Así que, como puedes ver, para candidate_1 mi función objetivo es 0.59. Como sabes, hay muchas opciones para elegir 10 de los 49 puntos. Debo crear otro candidato y seguir haciéndolo hasta que la función objetivo alcance su valor máximo y no cambie mucho después de eso. Necesito una estructura de código para crear candidatos inteligentes que mejoren mi función objetivo.

davy.ai

July 12, 2023 at 12:10 am

Encontrar la Mejor Combinación de Puntos para Maximizar la Función Objetivo

Para encontrar la mejor combinación de 10 puntos que maximice la función objetivo, podemos utilizar una combinación de la función de combinaciones de Python y el algoritmo de Búsqueda Tabú. Aquí tienes una guía paso a paso:

Importa las librerías necesarias y define las variables dadas.

import itertools
from random import randint

all_points = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48]
n = 10
ω = 0.3

Escribe una función para calcular el valor f1 para un conjunto dado de puntos.

def calcular_f1(candidato):
    # Calcula el valor K para el candidato
    K = sum(candidato) / len(candidato)

    # Calcula los valores interpolados para todos los puntos
    valores_j = []
    for punto in all_points:
        valor = (K - punto) / (candidato[-1] - candidato[0])
        valores_j.append(valor)

    # Calcula f1 utilizando la ecuación de eficiencia del modelo de Nash-Sutcliffe
    L = sum(valores_j) / len(valores_j)
    suma_numerador = sum([(valores_j[i] - L)**2 for i in range(len(valores_j))])
    suma_denominador = sum([(valores_j[i] - K)**2 for i in range(len(valores_j))])
    f1 = 1 - (suma_numerador / suma_denominador)

    return f1

Escribe una función para calcular la función objetivo Zc para un conjunto dado de puntos.

def calcular_Zc(candidato):
    f1 = calcular_f1(candidato)
    f2 = n/len(all_points)
    Zc = f1 - (ω * f2)
    return Zc

Utiliza la función de combinaciones para generar todas las posibles combinaciones de 10 puntos a partir de la lista all_points.

combinaciones = list(itertools.combinations(all_points, n))

Define una función para seleccionar aleatoriamente un conjunto candidato de la lista de combinaciones y aplicar el algoritmo de Búsqueda Tabú para encontrar un nuevo conjunto candidato que mejore la función objetivo.

def mejorar_candidato(candidato_actual, lista_tabu):
    # Define las variables para el algoritmo de Búsqueda Tabú
    max_iteraciones = 100
    tamaño_tabu_maximo = 10
    iteracion_actual = 0
    tamaño_tabu = 0

    # Define los valores iniciales
    Zc_actual = calcular_Zc(candidato_actual)
    mejor_candidato = candidato_actual
    mejor_Zc = Zc_actual

    # Inicia el algoritmo de Búsqueda Tabú
    while iteracion_actual < max_iteraciones:
        # Genera nuevos candidatos intercambiando elementos en el candidato actual
        nuevos_candidatos = []
        for i in range(n):
            for j in range(i+1, n):
                nuevo_candidato = list(candidato_actual)
                nuevo_candidato[i], nuevo_candidato[j] = nuevo_candidato[j], nuevo_candidato[i]
                if nuevo_candidato not in lista_tabu:
                    nuevos_candidatos.append(nuevo_candidato)

        # Evalúa los nuevos candidatos y elige el mejor
        mejor_nuevo_candidato = None
        mejor_nuevo_Zc = float('-inf')
        for candidato in nuevos_candidatos:
            Zc = calcular_Zc(candidato)
            if Zc > mejor_nuevo_Zc:
                mejor_nuevo_candidato = candidato
                mejor_nuevo_Zc = Zc

        # Actualiza el candidato actual y el mejor candidato si es necesario
        candidato_actual = mejor_nuevo_candidato
        Zc_actual = mejor_nuevo_Zc
        if Zc_actual > mejor_Zc:
            mejor_candidato = candidato_actual
            mejor_Zc = Zc_actual

        # Actualiza la lista Tabú
        lista_tabu.append(mejor_nuevo_candidato)
        tamaño_tabu += 1
        if tamaño_tabu > tamaño_tabu_maximo:
            lista_tabu.pop(0)
            tamaño_tabu -= 1

        # Actualiza el contador de iteraciones
        iteracion_actual += 1

    return mejor_candidato

Escribe un bucle para seleccionar aleatoriamente un conjunto de inicio y utilizar repetidamente la función mejorar_candidato para encontrar un nuevo conjunto candidato que maximice la función objetivo.

# Define los valores iniciales
candidato_actual = list(all_points[:n])
Zc_actual = calcular_Zc(candidato_actual)
mejor_candidato = candidato_actual
mejor_Zc = Zc_actual
lista_tabu = [candidato_actual]

# Inicia el bucle para encontrar el mejor conjunto candidato
max_iteraciones = 1000
iteracion_actual = 0
while iteracion_actual < max_iteraciones:
    print(f"Iteración {iteracion_actual+1}: {mejor_candidato}  Zc = {mejor_Zc}")
    nuevo_candidato = mejorar_candidato(candidato_actual, lista_tabu)
    nuevo_Zc = calcular_Zc(nuevo_candidato)
    if nuevo_Zc > mejor_Zc:
        mejor_candidato = nuevo_candidato
        mejor_Zc = nuevo_Zc
    candidato_actual = list(all_points[:n])
    Zc_actual = calcular_Zc(candidato_actual)
    lista_tabu = [candidato_actual]
    iteracion_actual += 1

Después de ejecutar el bucle, la variable mejor_candidato contendrá el conjunto de 10 puntos que maximiza la función objetivo.

es.davy.ai

¿Tienes una pregunta?