Un algoritmo de aprendizaje profundo para el problema Max-Cut basado en la estructura de red de punteros con estrategias de aprendizaje supervisado y de refuerzo
Autores: Gu, Shenshen; Yang, Yue
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Un algoritmo de aprendizaje profundo para el problema Max-Cut basado en la estructura de red de punteros con estrategias de aprendizaje supervisado y de refuerzo
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
El problema de corte máximo
Problema de optimización combinatoria
Algoritmos heurísticos
Red de punteros
Estrategias de aprendizaje profundo
Situaciones a gran escala
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 35
Citaciones: Sin citaciones
El problema de Max-cut es un problema de optimización combinatoria bien conocido, que tiene muchas aplicaciones del mundo real. Sin embargo, se ha demostrado que el problema es no determinista polinomial-duro (NP-duro), lo que significa que los algoritmos de solución exacta no son adecuados para situaciones a gran escala, ya que lleva demasiado tiempo obtener una solución. Por lo tanto, diseñar algoritmos heurísticos es una dirección prometedora pero desafiante para resolver eficazmente problemas de Max-cut a gran escala. Por esta razón, proponemos un método único que combina una red de punteros y dos estrategias de aprendizaje profundo (aprendizaje supervisado y aprendizaje por refuerzo) en este documento, con el fin de abordar este desafío. Una red de punteros es una red neuronal profunda secuencia a secuencia, que puede extraer características de datos de una manera puramente basada en datos para descubrir las leyes ocultas detrás de los datos. Combinando las características del problema de Max-cut, diseñamos los mecanismos de entrada y salida del modelo de red de punteros, y utilizamos el aprendizaje supervisado y el aprendizaje por refuerzo para entrenar el modelo y evaluar el rendimiento del modelo. A través de experimentos, ilustramos que nuestro modelo puede aplicarse bien para resolver problemas de Max-cut a gran escala. Nuestros resultados experimentales también revelaron que el nuevo método fomentará aún más una exploración más amplia de la red neuronal profunda para problemas de optimización combinatoria a gran escala.
Descripción
El problema de Max-cut es un problema de optimización combinatoria bien conocido, que tiene muchas aplicaciones del mundo real. Sin embargo, se ha demostrado que el problema es no determinista polinomial-duro (NP-duro), lo que significa que los algoritmos de solución exacta no son adecuados para situaciones a gran escala, ya que lleva demasiado tiempo obtener una solución. Por lo tanto, diseñar algoritmos heurísticos es una dirección prometedora pero desafiante para resolver eficazmente problemas de Max-cut a gran escala. Por esta razón, proponemos un método único que combina una red de punteros y dos estrategias de aprendizaje profundo (aprendizaje supervisado y aprendizaje por refuerzo) en este documento, con el fin de abordar este desafío. Una red de punteros es una red neuronal profunda secuencia a secuencia, que puede extraer características de datos de una manera puramente basada en datos para descubrir las leyes ocultas detrás de los datos. Combinando las características del problema de Max-cut, diseñamos los mecanismos de entrada y salida del modelo de red de punteros, y utilizamos el aprendizaje supervisado y el aprendizaje por refuerzo para entrenar el modelo y evaluar el rendimiento del modelo. A través de experimentos, ilustramos que nuestro modelo puede aplicarse bien para resolver problemas de Max-cut a gran escala. Nuestros resultados experimentales también revelaron que el nuevo método fomentará aún más una exploración más amplia de la red neuronal profunda para problemas de optimización combinatoria a gran escala.