Estás leyendo la publicación: ¿Cómo los algoritmos evolutivos pueden optimizar la clasificación?
Una colección desordenada de elementos se ordena colocándolos en un orden monótonamente ascendente (o decreciente). La eficiencia de clasificar grandes conjuntos de datos, tanto en términos de tiempo como de memoria utilizada, exige avances en los algoritmos de clasificación y sus implementaciones en la informática moderna. Los modelos de aprendizaje automático podrían usarse para mejorar estos algoritmos de clasificación. Al analizar datos experimentales, el aprendizaje automático permite la creación de algoritmos adaptables. Para elegir un algoritmo dependiendo de las propiedades del conjunto de datos, este artículo revisa los algoritmos evolutivos. Los siguientes son los temas a tratar.
Tabla de contenido
- Clasificación en aprendizaje automático
- Algoritmos genéticos utilizados para optimizar la clasificación
- Ventajas de utilizar el algoritmo genético
Desde los albores de las computadoras, la clasificación ha llamado mucho la atención como una actividad fundamental de datos. Entendamos los algoritmos de clasificación.
Clasificación en aprendizaje automático
Una operación de clasificación implica colocar datos en un orden específico. El algoritmo de clasificación define la técnica para organizar los datos en un orden determinado. La búsqueda de datos puede ser muy eficiente cuando los datos se mantienen ordenados, razón por la cual la clasificación es importante. La representación de datos en formas más comprensibles es otro uso para la clasificación.
Los algoritmos para clasificar datos pueden necesitar un poco más de espacio para la comparación y el almacenamiento a corto plazo de algunos componentes de datos. Se afirma que estos algoritmos ordenan en el lugar, por ejemplo, dentro de la propia matriz, y no ocupan más espacio. Se conoce como clasificación en el lugar. Una ilustración de la clasificación en el lugar es la clasificación de burbuja. Pero para algunos algoritmos de clasificación, la cantidad de espacio utilizado por el programa es mayor o igual que la cantidad de elementos que se clasificarán. La clasificación no in situ se define como la clasificación con una necesidad de espacio igual o mayor. Una ilustración de la ordenación no en el lugar es la ordenación por combinación.
Según los efectos después de clasificar los datos, estos algoritmos de clasificación se clasifican como estables y no estables. Por ejemplo, cuando deseamos mantener la secuencia de elementos en una tupla, la estabilidad del algoritmo importa.
Si un algoritmo de clasificación utiliza elementos que se han “ordenado” previamente en la lista que debe clasificarse, se dice que es adaptativo. En otras palabras, durante la clasificación, los algoritmos adaptativos intentarán evitar la reordenación de elementos si la lista de origen ya tiene una parte ordenada. Se dice que un algoritmo que ignora los elementos que se han ordenado previamente no es adaptativo. Para asegurarse de que los elementos estén ordenados correctamente, intentan colocar cada elemento en un nuevo orden.
¿Por qué es necesaria la optimización?
Aunque la tecnología de compilación ha automatizado en gran medida la optimización de programas, aún se requiere mucha participación humana para producir código de alta calidad. Hay dos justificaciones para esta afirmación:
- Las implementaciones inconsistentes de los compiladores.
- Los compiladores tradicionales no contienen información semántica, lo que limita su capacidad para cambiar los datos.
¿Está buscando un repositorio completo de bibliotecas de Python utilizadas en ciencia de datos, echa un vistazo aquí.
Algoritmos genéticos utilizados para optimizar la clasificación
El algoritmo óptimo solo se puede encontrar mediante la búsqueda porque no existen modelos analíticos del rendimiento de los algoritmos de clasificación en términos de los parámetros arquitectónicos de la máquina. Además, investigaciones anteriores sobre la complejidad de la clasificación se basaron en la suposición incorrecta de que acceder a cada pieza lleva la misma cantidad de tiempo con la tecnología moderna.
En un algoritmo genético, los valores de los parámetros de las primitivas de clasificación y selección, así como su composición, determinan el espacio de búsqueda. El objetivo de la búsqueda es encontrar la clasificación jerárquica que mejor se adapte a las características arquitectónicas de la máquina y las características del conjunto de entrada.
Una analogía entre la estructura genética y el comportamiento de los cromosomas en la población sirve como base para los algoritmos genéticos. La base de los GA basados en esta comparación es la siguiente.
- Los miembros de la población compiten por los recursos y se aparean.
- Los individuos sucesivos (más aptos) se aparean para tener más hijos que otros individuos.
- Los padres ocasionalmente tienen hijos que son mejores que cualquiera de los padres; esto se debe a que los genes de los padres “más aptos” se propagan a lo largo de la generación.
- Como resultado, cada próxima generación se vuelve más amigable con el medio ambiente.
Las primitivas de clasificación y selección se emplean como nodos basados en árboles en el esquema. Para crear nuevos niños y alterar la población, se utilizan operadores genéticos. Las dos operaciones que emplean la mayoría de los algoritmos genéticos son el cruce y la mutación.
Transversal
Los subárboles de varios árboles se intercambian durante el cruce. El objetivo de Crossover es producir nuevos descendientes que se desempeñen mejor que sus padres. Cuando los nuevos hijos heredan los mejores subárboles de los padres, es probable que esto ocurra. En la mayoría de los casos, se emplea un punto de cruce único, y el punto de cruce se elige al azar.
Mutación
Este operador realiza ajustes en un solo árbol. Da la varianza de la población. La población no puede seguir siendo la misma después de una generación dada debido a la mutación. Esta estrategia permite que la búsqueda escape parcialmente a los óptimos locales. En un esfuerzo por identificar mejores valores, la mutación modifica los valores de los parámetros. Las siguientes modificaciones son posibles con el operador de mutación:
- Cambie los valores de los parámetros al azar al ordenar y elegir nodos básicos.
- Cambia dos subárboles.
- Incluyendo un nuevo subárbol.
- Saca un subárbol. Con esta técnica, se pueden eliminar los subárboles innecesarios.
Función de acondicionamiento físico
La probabilidad de que un individuo se reproduzca está determinada por la función de aptitud. La probabilidad de que un organismo se reproduzca y evolucione aumenta con la aptitud. La función de fitness será el rendimiento. Pero al diseñar la función de aptitud, se han tenido en cuenta los siguientes dos factores:
- El objetivo es un algoritmo de clasificación que funcione bien con todas las entradas potenciales. Por lo tanto, la condición física básica de un árbol es su desempeño promedio. Se establece una penalización en los árboles con rendimiento variable al aumentar la aptitud base en un número que se basa en la desviación estándar de su rendimiento mientras se clasifican las entradas de prueba; sin embargo, el algoritmo de clasificación tiene que funcionar bien de manera consistente en todas las entradas también es un objetivo.
- La varianza de la aptitud de la población es significativa en las generaciones iniciales. En otras palabras, algunos árboles de clasificación funcionan mucho mejor que otros. Dado que estos pocos árboles tendrían una probabilidad considerablemente mayor de reproducirse, la mayoría de los niños serían sus descendientes si nuestra función de aptitud fuera directamente proporcional al rendimiento del árbol. Estos descendientes eventualmente constituirían la mayoría de la población. De esto podría surgir una convergencia prematura, lo que restringiría que el algoritmo investigue partes del espacio de búsqueda fuera de la vecindad de los árboles más adecuados. Para resolver este problema, nuestra función de aptitud aprovecha el orden de desempeño o el rango de los árboles de clasificación de la población. La diferencia absoluta de rendimiento entre árboles se ignora cuando se aplica la clasificación de rendimiento, por lo tanto, los árboles con menor rendimiento tienen una mayor probabilidad de reproducirse que los árboles con mayor rendimiento. Esto elimina el problema de la convergencia temprana y la convergencia a un óptimo local.
Ventajas y desventajas de usar algoritmos genéticos
Hay algunos beneficios de usar algoritmos genéticos sobre otros métodos de optimización.
- Los algoritmos de clasificación se pueden expresar como un árbol usando primitivas, donde cada primitiva representa un nodo. Como resultado, los algoritmos genéticos pueden utilizarse simplemente para explorar el universo de árboles potenciales para obtener la mejor estructura de árbol y valores de parámetros asociados con cada nodo.
- Los algoritmos genéticos mantienen los mejores subárboles y aumentan sus posibilidades de reproducción. Debido a que un subárbol también es un algoritmo de clasificación, los algoritmos de clasificación pueden hacer uso de esto.
Un algoritmo genético es una herramienta prometedora para resolver problemas, pero tiene algunas fallas que pueden conducir a la ineficiencia.
- Es difícil ajustar la configuración. Requiere la determinación de numerosos parámetros, como el tamaño de la población, la tasa de mutación y la duración máxima de la ejecución, así como la creación de algoritmos para la selección, la recombinación y la mutación. Encontrar alternativas viables para estos es una tarea difícil con poco o ningún respaldo teórico.
- No hay garantía de que se produzca la convergencia. No hay garantía de que el algoritmo encuentre un óptimo global. Es posible que quede atrapado en uno de los óptimos locales.
Conclusión
Elegir un algoritmo de evolución adecuado es una decisión crítica. El algoritmo de evolución decide cuántos niños se producirán, cuántos miembros de la generación actual serán reemplazados, etc. Con este artículo, hemos entendido el requisito de optimización en la clasificación y el uso de GA para optimizar los algoritmos de clasificación.
