#-------------------------------------------------------------------- # Fichero: maxifeli.txt # Objetivo: Explicar el sistema MaxiFeli # Fecha: J.19.12.2019 # Autor: Pedro Reina # Licencia: Dominio público # https://creativecommons.org/publicdomain/zero/1.0/deed.es #-------------------------------------------------------------------- Este sistema resuelve el problema de colocar por parejas un grupo de personas de modo que se maximice el total de preferencias para sentarse que hayan expresado anteriormente esas personas. El sistema llama "felicidad" a la suma de preferencias obtenida. Las personas pueden expresar sus preferencias mediante una página web y el administrador del sistema ejecuta una serie de programas para realizar los emparejamientos. #------------------- # Requisitos #------------------- La programación está escrita en Python 2.7 y PHP-CLI La programación web está escrita en PHP 5 y PHP-CLI La base de datos está en formato SQLite 3 El manejo de bases de datos SQLite en Python usa Another Python SQLite Wrapper La generación de PDF desde Python usa ReportLab #------------------- # Utilización #------------------- Primer paso: creación de la base de datos Se ejecuta el programa 1-crea.sh y se genera maxifeli.db a partir del archivo maxifeli.sql. Aviso: se borra el archivo maxifeli.db anterior. Segundo paso: creación del archivo de usuarios y contraseñas Se crea un archivo de texto con codificación UTF-8 que contenga un nombre en cada línea; se muestra como ejemplo el archivo ejemplo-nombres.txt. Al archivo se le pone como nombre maxifeli-nombres.txt. (También se puede crear un enlace simbólico a ese nombre). Se ejecuta el archivo 2-genera-nuc.py y se genera el archivo maxifeli-nuc.csv que incluye los nombres, la propuesta de usuario y las contraseñas. Hay que comprobar (a mano) que no hay nombres de usuario repetidos y hacer las modificaciones necesarias. El archivo maxifeli-nuc.csv se puede usar como base para realizar una combinación de correspondencia usando algún procesador de textos. Se ofrece como ejemplo el archivo maxifeli-patron.odt Tercer paso: inserción en la base de datos de los usuarios Se ejecuta el archivo 3-inserta-nuc.py y se añaden a maxifeli.db los datos del archivo maxifeli-nuc.csv. Cuarto paso (solo para pruebas): generación aleatoria de preferencias Para poder probar si el sistema funciona correctamente antes de repartir las credenciales y poner en marcha el servidor web, se puede ejecutar el programa 4-inventa-preferencias.py que modifica el archivo maxifeli.db incluyendo algunas preferencias generadas aleatoriamente. Cuarto paso (real): cumplimentación vía web de las preferencias de los usuarios Se suben a un servidor web los archivos del directorio 4-web junto con el archivo maxifeli.db. El programa servidor web debe tener permisos de escritura sobre el archivo maxifeli.db. El archivo punto.htaccess se puede usar si el servidor web es Apache para evitar que cualquiera pueda descargar el archivo maxifeli.db. Hay que renombrarlo a .htaccess si se usa la configuración habitual de Apache. Se reparten a los usuarios sus credenciales y se les da un tiempo para que entren en la página web y anoten sus preferencias. Si algún usuario no recuerda su contraseña, se puede usar en el servidor web el programa cambiaCodigo.php para restaurarla. Quinto paso (opcional): impresión de las preferencias Se recupera el archivo maxifeli.db del servidor web y se ejecuta el archivo 5-imprime-preferencias.py. Se obtiene el archivo preferencias.pdf con un volcado de las preferencias de los usuarios. En este directorio se ve un ejemplo. Sexto paso: generación de los emparejamientos Se recupera el archivo maxifeli.db del servidor web (si no se ha hacho en el quinto paso) y se ejecuta el archivo 6-empareja.py y se obtienen los archivos parejas.pdf y parejas.txt con los datos de la mejor solución encontrada. En este directorio se ve un ejemplo de ejecución (el archivo ejemplo.png) y del resultado obtenido. #------------------- # Agradecimientos #------------------- Los iconos usados en el programa web son del proyecto Oxygen https://github.com/pasnox/oxygen-icons-png El tipo de letra usado para los textos de la página web es Encode Sans de Impallari Type, con licencia SIL Open Font. http://www.fontsquirrel.com/fonts/encode-sans El tipo de letra usado para los títulos de la página web es Bree Serif Regular, de typetogether, con licencia SIL Open Font. http://www.fontsquirrel.com/fonts/bree-serif El tipo de letra usado para los botones de la página web es Nunito Bold, de Vernon Adams, con licencia SIL Open Font. http://www.fontsquirrel.com/fonts/nunito El método para generar en PHP 5 el hash de la contraseña de los usuarios es de Anthony Ferrara con licencia MIT. #------------------- # Comentarios #------------------- Llevaba tiempo con ganas de intentar resolver este problema. Mi idea inicial era que sería necesario utilizar alguna técnica de inteligencia artificial porque el método de fuerza bruta se enfrentaría a la dificultad del crecimiento exponencial del espacio de posibilidades. En noviembre de 2019 pensé otra vez en la posibilidad de programar un método para resolver el problema con la intención de utilizarlo realmente para emparejar a mis alumnos de un grupo en el centro de enseñanza en el que trabajaba. Ese mes estaba leyendo un libro de Daniel Dennett en el que aparecía a menudo la idea de competencia sin comprensión, que se aplica a la evolución animal, a la percepción humana y muchas más situaciones y me apareció clara la idea de que un algoritmo genético sería un buen método de resolución (sin comprensión). Mi grupo de alumnos de referencia se componía de 28 personas. El espacio de posibles soluciones de emparejamiento tiene 27·25·23·19·17·15·13·11·9·7·5·3 = 2,13·10^14 elementos (213 billones) y calculé que si un algoritmo de fuerza bruta pudiera valorar un millón de elementos cada segundo, tendría que estar trabajando más de seis años para encontrar la mejor opción. El algoritmo genético resuelve el problema en cuestión de segundos (pocos). Existe un algoritmo muy obvio para intentar encontrar una solución, que consiste en ir quedándose cada vez con la pareja que dé mayor felicidad. Este método siempre da peores soluciones que el algoritmo genético. Por último, trabajé en la posibilidad de adaptar el método húngaro de asignación de personas a tareas para resolver este problema. Aunque en un caso de prueba vi que sería posible la adaptación, deseché la posibilidad de programarlo porque llegué a la misma solución que con el algoritmo genético, que ya tenía programado. #------------------- # El algoritmo genético #------------------- Partimos de una población de n elementos, que suponemos que es par. Cada elemento es una persona humana. Cada elemento ha expresado con un número entero no negativo su preferencia por sentarse con cada uno de los demás elementos. Este número se denomina felicidad. Para el número de linajes establecido: Para el número de supervivientes establecido: Llamamos individuo a una posible colocación por parejas de los n elementos. Creamos cada individuo de la generación inicial eligiendo una permutación de los n elementos tomada al azar. Consideramos que el emparejamiento se ha producido entre el elemento 1 y el 2, el 3 con el 4, y así sucesivamente. Para el número de generaciones establecido: Para cada superviviente: Generamos aleatoriamente el número de hijos establecido. Cada hijo se genera intercambiando al azar dos elementos del padre. No existen las madres, la reprodución no es sexual, no hay intercambio de información entre individuos. Calculamos la felicidad de cada individuo sumando las felicidades de todos sus elementos. Ordenamos los individuos de mayor a menor felicidad. Nos quedamos con los individuos que tengan más felicidad. Solo sobrevive el número de supervivientes establecido. Guardamos el individuo con mayor felicidad de todo el linaje. Ordenamos los mejores individuos de cada linaje de mayor a menor felicidad. Nos quedamos como resultado final con el individuo de mayor felicidad de todos los linajes.