[Garcia-10] Introduccion a la Resolucion de Problemas con AG

Vista previa del material en texto

INTRODUCCIÓN A LA RESOLUCIÓN DE PROBLEMAS CON 
ALGORITMOS GENÉTICOS 
G U IL LER MO G A R CÍA 
P R OFE SOR D E IN VE S TIG A CI ÓN D E OP ER A C IO NE S 
Título abreviado: Introducción a los Algoritmos Genéticos 
Autor: Guillermo García, Prof. de Investigación de Operaciones I y II. Universidad Católica Andrés 
Bello. Caracas, Venezuela Tel: (+58) 4166366479 Email: guillermo@ggarciao.com 
Última revisión: 28 de Marzo de 2010 
PALABRAS CLAVES 
• Problema, Problemas de Decisión, Problemas de Búsqueda, Problemas de Optimización, 
Problemas de Conteo, Problema Multiobjetivo, Frente Pareto, Técnicas Computacionales 
Determinísticas, Búsqueda Exhaustiva, Búsqueda Ternaria, Simplex, Ramificación y 
acotamiento, Técnicas Computacionales Heurísticas, Búsqueda Tabú, Simulated Annealing, 
Complejidad Computacional, Complejidad P, Complejidad NP, NP – Completo, Algoritmo 
Genéticos, Individuos, Población, Cromosoma binario, Función Objetivo, Asignación de 
Fitness, Operadores Genéticos, Operador de Selección, Selección con Ruleta, Selección con 
Torneo, Operador de Elección, Elección Aleatoria, Elección Basada en el Individuo, Operador 
de Cruce, Cruce de un Punto, Cruce de dos Puntos, Cruce Cortar y Empalmar, Operador de 
Mutación, Algoritmos Genéticos Multiobjetivo, Asignación de Fitness en Algoritmos 
Genéticos Multiobjetivos 
PROPÓSITO DEL DOCUMENTO 
El presente trabajo tiene como objetivo principal crear una base de conocimiento sólida sobre la 
utilización de los algoritmos genéticos en la resolución de problemas modelados matemáticamente. 
Pasando desde la definición formal de problemas hasta la implementación de algoritmos genéticos, 
este trabajo define, explica y contextualiza muchos de los conceptos que toda persona debe manejar 
al momento de solucionar modelos matemáticos: tipos de problemas, problemas multiobjetivos, la 
complejidad computacional de dichos problemas y técnicas computacionales que los resuelven. 
 
García 2010
 
INTRODUCCIÓN: DESDE 
El ser humano está constantemente planteándose nuevas metas u objet
estacionarios, imaginándose que todo es mejorable. Lo que separa a un ser de su objetivo, es lo que 
usualmente se denomina como problema
una acción. Esta acción es lo que s
Fig. 1 Problema: cruzar un abismo. Solución: un puente
Cuando el problema puede ser planteado de forma matemática, a través de la formulación o 
modelado, la búsqueda de la solución
técnicas buscan dentro de todas las posibles 
encontrada como resultado. Esta búsqueda puede ser realizada de forma:
• Determinística: 
Formalmente, una técnica 
arroja el mismo resultado R.
solución óptima e inmejorable, ya que garantizan de una forma u otra que todas las 
soluciones factibles fueron consideradas.
• Heurística: 
Una técnica es considerada heurística cuando 
ser distinto para la misma entrada E. La solución encontrada por este tipo de técnicas
considerada buena, pero jamás se puede decir que es óptima, ya qu
parte de las soluciones factibles, usando un criterio considerado correcto, más no perfecto, 
para descartar soluciones no óptimas.
 
 
2010 Introducción a los Algoritmos Genéticos 
2 
INTRODUCCIÓN: DESDE EL PROBLEMA HASTA LA SOLUCIÓN
El ser humano está constantemente planteándose nuevas metas u objetivos, evitando los estados 
estacionarios, imaginándose que todo es mejorable. Lo que separa a un ser de su objetivo, es lo que 
problema: un estado o situación que debe ser cambiada a través de 
una acción. Esta acción es lo que se denomina usualmente como solución. 
Problema: cruzar un abismo. Solución: un puente 
 
puede ser planteado de forma matemática, a través de la formulación o 
solución puede realizarse a través de técnicas computacionales
técnicas buscan dentro de todas las posibles soluciones del problema, seleccionando la mejor 
encontrada como resultado. Esta búsqueda puede ser realizada de forma: 
Formalmente, una técnica es determinística cuando para una misma entrada E siempre 
arroja el mismo resultado R. Adicionalmente, este tipo de técnicas dan como resultado la 
solución óptima e inmejorable, ya que garantizan de una forma u otra que todas las 
soluciones factibles fueron consideradas. 
Una técnica es considerada heurística cuando cada vez que se aplica, el resultado R puede 
ser distinto para la misma entrada E. La solución encontrada por este tipo de técnicas
considerada buena, pero jamás se puede decir que es óptima, ya que solo considera una 
parte de las soluciones factibles, usando un criterio considerado correcto, más no perfecto, 
para descartar soluciones no óptimas. 
SOLUCIÓN 
ivos, evitando los estados 
estacionarios, imaginándose que todo es mejorable. Lo que separa a un ser de su objetivo, es lo que 
: un estado o situación que debe ser cambiada a través de 
 
puede ser planteado de forma matemática, a través de la formulación o 
cas computacionales. Estas 
, seleccionando la mejor 
cuando para una misma entrada E siempre 
Adicionalmente, este tipo de técnicas dan como resultado la 
solución óptima e inmejorable, ya que garantizan de una forma u otra que todas las 
cada vez que se aplica, el resultado R puede 
ser distinto para la misma entrada E. La solución encontrada por este tipo de técnicas es 
e solo considera una 
parte de las soluciones factibles, usando un criterio considerado correcto, más no perfecto, 
García 2010 Introducción a los Algoritmos Genéticos 
3 
 
 
 
 
 
 
 
 
 
 
Fig. 2 Técnica Determinística vs. Técnica Heurística 
El uso de técnicas determinísticas correctamente diseñadas garantiza la obtención, si existe, de la 
solución óptima e inmejorable, por lo cual su uso es siempre deseado, pero no siempre factible. 
Todo depende de la complejidad computacional del problema a resolver. 
La complejidad computacional es una cualidad de un problema, que se refiere a la cantidad de 
recursos computacionales que consumiría su resolución, independientemente de la técnica 
utilizada. Si la clase de complejidad computacional de un problema es “demasiado elevada”, las 
técnicas determinística no pueden ser aplicadas porque evaluar todas las soluciones factibles es 
imposible en tiempos humanamente decentes. Es aquí cuando las técnicas heurísticas tienen 
validez, ya que dan una solución considerada buena en un tiempo humanamente aceptable. 
Las clases de complejidad computacional se definen tomando en cuenta tres factores: 
• El Tipo de Problema: la forma del problema a ser resuelto. Ej: Problema de decisión, de 
búsqueda, de optimización, etc. 
• El Modelo de Cómputo: el tipo de computador que resolverá el problema. Ej: Máquina de 
Turing Determinística, Máquina de Turing No Determinística, etc. 
• Los recursos necesarios: se refieren al tiempo o espacio a ser consumidos. Ej: Tiempo 
Polinomial, Espacio Logarítmico, etc. 
Usando estos factores, se han definido clases de complejidad computacional para clasificar 
problemas: como P que contiene todos los problemas de decisión que pueden ser resueltos en 
tiempos polinomiales en una máquina de Turing determinística; o NP que contiene todos los 
problemas de decisión que pueden ser resueltos en tiempos polinomiales en una máquina de Turing 
no determinística. 
Solución 
Buena 
Técnica 
Heurística 
Técnica 
determinística 
Solución 
Óptima 
García 2010 Introducción a los Algoritmos Genéticos 
4 
 
 
 
 
 
 
Fig. 3 Relación entre los conjuntos P, NP y NP-Completo 
Conocer la clase de complejidad computacional de un problema permite determinar que técnica 
computacional utilizar para resolverlo. En algunos casos, el problema no podrá ser resuelto de 
forma determinística (por ejemplo, los problemas NP-completos) y por eso se abordan con 
aproximaciones o técnicas heurísticas. 
Dentro de las técnicas heurísticas más utilizadas para resolver problemas se encuentran los 
algoritmos genéticos. Esta técnica, inspirada en el proceso evolutivo de los seres vivos, comienza 
con un conjunto aleatoriode soluciones factibles al problema e iterativamente las va mejorando 
usando mecanismos evolutivos: 
• Selección: Las soluciones más “fuertes” tendrán la capacidad de cruzarse 
• Elección: Las soluciones capaces de cruzarse forman “parejas”. 
• Cruce: Las soluciones “padres” generan soluciones “hijas” que suelen ser más “fuertes” 
• Mutación: Las soluciones “hijas” tienen características que no proviene de sus “padres” 
 
 
 
 
 
 
 
 
Fig. 4 El valor binario de los caracteres ASCII suele ser una buena representación 
cromosómica de los caracteres alfanuméricos 
P NP-Completo 
NP 
S 
0 
1 
0 
1 
0 
0 
1 
1 
Solución 
Real 
Representación 
binaria 
Z 
0
1
0
1
1
0
1
0 
Solución 
Real 
Representación 
binaria 
García 2010 Introducción a los Algoritmos Genéticos 
5 
 
Cada solución es codificada en una cadena de números y/o caracteres llamada cromosoma. Este 
cromosoma es portado por un individuo de la población y a través de las generaciones y gracias a los 
operadores evolutivos, la información codificada se mezcla con otra para generar una o varias 
nuevas soluciones. 
Aunque empíricamente los algoritmos genéticos han demostrado su eficiencia, al no poder 
conseguir la solución óptima al problema, es importante saber estudiar su comportamiento. Esto se 
logra mediante un análisis estadístico de la población, generación a generación, a través de la 
aplicación de técnicas estadísticas como: 
• Análisis exploratorio: Necesario para determinar cuáles medidas de tendencia central y 
dispersión usar para el estudio descriptivo. 
• Estudio descriptivo: Análisis e interpretación de las medias de tendencia central y 
dispersión determinadas en el análisis exploratorio. 
Este estudio permite verificar si la ejecución del algoritmo genético tiene el comportamiento 
deseado, y de ser así, la solución obtenida podrá ser considerada, con confianza, como una buena 
solución, aunque no se pueda saber si es óptima o no. 
Ciertos cambios han de ser realizados cuando se busca resolver problemas multiobjetivo. Este tipo 
de problema, subconjunto de los problemas de optimización, buscan optimizar más de un objetivo al 
mismo tiempo. Los objetivos suelen ser competitivos, lo que se traduce en la existencia de una 
relación inversa entre ellos (cuando un objetivo mejora, los otros empeoran) y no hay una forma 
analítica de relacionarlos. Esto hace que la solución a este tipo de problema sea un conjunto de 
soluciones, calificadas como óptimas Pareto. 
 
 
 
 
 
Fig. 5 Shaffer F2 es un ejemplo clásico de optimización multiobjetivo 
 
g(x) = x2 h(x) = (x-2)2 
García 2010 Introducción a los Algoritmos Genéticos 
6 
 
UN VISTAZO PRÁCTICO A LA DEFINICIÓN DE PROBLEMAS 
El día a día de los seres humanos consiste en cambiar el estado actual en que se encuentran, 
buscando mejorarlo. Independientemente de lo que cada ser defina como “mejor”, todos se 
encuentran frente a lo mismo: cambiar el estado actual requiere resolver ciertos planteamientos y 
se sabe que si no se responden correctamente, no se llegará al estado deseado sino a otro, en 
muchos casos impredecible. Estos planteamientos con múltiples respuestas, llamadas soluciones, es 
lo que se define como problema. 
Existen varios tipos de soluciones: 
• Solución No Factible: es una respuesta imposible o inválida. Son todas aquellas soluciones 
que se deben descartar al momento de la resolución del problema. 
• Solución Factible: es una respuesta alcanzable o válida. Resolver un problema consiste en 
determinar cuál de ellas es la Solución Óptima. 
• Solución Óptima1: Solución Factible inmejorable. Es la solución que resuelve el problema de 
la mejor manera posible. Pueden existir más de una, pero todas producen el mismo 
beneficio (soluciones óptimas alternativas). 
 
 
Fig. 6. Espacio de Solución para el problema de optimizar f(x) = 1/x 
 
1 Aunque no todos los problemas son de optimización, suele usarse el término solución óptima para referirse 
a la respuesta correcta a cualquier problema 
Región Factible 
Región Factible 
Región No 
Factible 
Y 
X 
García 2010 Introducción a los Algoritmos Genéticos 
7 
 
Para la interpretación y análisis de problemas, las soluciones se suelen graficar en un espacio de 
soluciones, en el cual se pueden observar la región factible y región no factible de del problema2. Para 
ciertos tipos de problemas, como los problemas de optimización, este recurso visual permite hacer 
un análisis menos abstracto del problema, ayudando a la definición de la estrategia a seguir para 
resolverlo. Para otros tipos, como los problemas de búsqueda, el espacio de soluciones simplemente 
representa el formato de la respuesta. 
Ejemplo: Si se quiere saber qué valor de x genera el mayor valor de y (maximizar) para y = 1/x, el 
espacio de solución está formado por todos los valores posibles de x. En la Fig. 6 se puede observar 
que se tienen dos regiones factibles, x menor que cero (x < 0) y x mayor que cero (x > 0). Como la 
función no está definida para x = 0, este valor conforma la región no factible del problema. 
TIPOS DE PROBLEMAS 
Un detalle importante a tomar en cuenta al momento de plantear problemas es saber determinar la 
naturaleza del mismo. 
Ejemplo: El problema de determinar los divisores de un número entero X, tiene como respuesta una 
lista de números enteros que dividen a X sin residuo. En cambio, el problema de saber si un número 
X es primo, tiene como respuesta un valor booleano: SI o NO. Aquí se nota una clara diferencia en el 
espacio de solución, lo que se traduce en la necesidad de definir una estrategia distinta para 
solucionarlo. 
 A B 
Problema 
Conocer los divisores de un número 
entero X 
Conocer si un número X es primo 
Espacio de 
Solución 
Listas de números enteros SI o NO 
Técnica de 
resolución 
Dividir X entre todos los números 
menores que Piso(X/2). Si la división da 
cero, se agrega el divisor a una lista L 
Obtener los divisores de X en una lista L. Si 
tiene solo dos elementos (uno y X) el 
número es primo. 
Tabla 1. Comparación de dos problemas de naturaleza distinta 
 
2 El espacio de solución se puede graficar si y solo si las soluciones se pueden ordenar y tienen menos de 4 
dimensiones. 
García 2010 Introducción a los Algoritmos Genéticos 
8 
 
Se puede observar en la Tabla 1 que los problemas se diferencian en el espacio de solución y, por 
consiguiente, en la técnica de resolución. Aunque la solución de B se puede obtener a partir de la 
solución de A, se debe hacer un cálculo o procedimiento adicional, lo que ya hace las técnicas de 
resolución distintas. 
Las ciencias de la computación clasifican a los problemas computables3 según su naturaleza en los 
siguientes grupos: 
PROBLEMAS DE DECISIÓN 
Los problemas que se pueden plantear en un sistema formal4 cuya respuestas posibles son 
exclusivamente SI o NO son considerados Problemas de Decisión. Básicamente son problemas que 
buscan determinar la validez de una sentencia. Fíjese que una de las características fundamentales 
que definen a este tipo de problemas es que su espacio de solución es binario: SI o NO, VERDARERO 
o FALSO, UNO o CERO. Esto influye a la técnica de resolución a aplicar, ya que usualmente se asume 
que la sentencia es verdadera hasta que se demuestre lo contrario, o viceversa. 
Cuando a un problema de decisión se le puede diseñar un procedimiento de decisión5 que le dé 
respuesta, se dice que el problema es decidible. En caso contrario, si no se puede conseguir un 
algoritmo para buscarle respuesta, se dice que el problema es indecidible6 y esto solo se determina a 
través de demostraciones matemáticas. Es importante tener claro esto, ya que de estar trabajando 
en un problema sobre el cual es muy difícil diseñar un algoritmo, posiblemente haya que recurrir a 
demostracionesmatemáticas para determinar que es indecidible, es decir, que no tiene solución. 
Ejemplo: 
Problema de la partición. Dado un conjunto de números, determinar si se puede dividir este 
conjunto en dos particiones buscando que la suma de los elementos de las particiones sumen lo 
mismo. 
 
3 Los problemas computables son todos aquellos problemas que se pueden resolver mediante un algoritmo. 
4 Un sistema formal (Lógica) está formado por en un lenguaje formal y un conjunto de reglas de inferencia que 
juntos permiten derivar o concluir una expresión a partir de otras expresiones. Ejemplo: (3+1 = 4). Nótese 
que podemos derivar 4 a partir de 1 y 3, gracias al lenguaje de las matemáticas (números y operadores) y las 
reglas de inferencias que la rigen (la suma). 
5 Un procedimiento de decisión es técnica de resolución algorítmica (algoritmo) que resuelve un problema de 
decisión 
6 Problema de la Parada, de Alan Turing y el Problema de la Correspondencia de Emil Post son dos problemas 
indecidibles muy referenciados. 
García 2010 Introducción a los Algoritmos Genéticos 
9 
 
Este problema busca determinar si existe una forma de separar un multi-conjunto7 de números 
enteros en dos particiones, con la condición especial que la suma de los números de las particiones 
arrojen el mismo resultado. 
������� 	� 
��
������� ��	�� 
��1,1,2,2,��3,4,5� � �2,2, �5� � � �1,1,3,4�� 
	��	� 
 � 2 2 5! � �1 1 3 4! � 9 
��1,2,3,5,5,��7� � �1,2, �3,7� � � �3,5,5�� 
	��	� 
 � 1 2 3 7! � �3 5 5! � 13 
Nótese que la respuesta a este problema es binaria: SI o NO hay particiones posibles. Este espacio 
de solución afecta el diseño de la técnica de resolución, en la cual se asumirá que no hay particiones 
hasta que se demuestre lo contrario, o viceversa. 
PROBLEMAS DE BÚSQUEDA 
Cuando el problema planteado consiste en buscar en un conjunto de entrada aquellos elementos 
que cumplan con una determinada condición (o condiciones) se está frente a un Problema de 
Búsqueda. El espacio de solución de este tipo de problemas son tuplas8 de elementos, pudiendo ser 
estos números o cadenas de caracteres (pertenecientes a un lenguaje). Para este caso, el espacio de 
solución no ayuda a la definición una técnica de resolución, ya que aquí el foco está en estudiar la 
entrada y no la salida. 
Hay dos formas comunes, más no únicas, de los problemas de búsqueda: 
• Búsqueda directa: Los que requieren conseguir los elementos del conjunto de entrada que 
cumplan con las condiciones dadas. Este tipo de problema tienen un conjunto finito de 
elementos de entrada, y la salida o respuesta es un subconjunto de elementos de dicha 
entrada. 
 
7 Un multi-conjunto es un conjunto que puede contener elementos repetidos. 
8 Las tuplas son una secuencia ordenada de objetos. Ejemplos: una lista o vector, una fila de una tabla, etc. 
García 2010 Introducción a los Algoritmos Genéticos 
10 
 
• Búsqueda combinatoria: Los que requieren combinar los elementos de la entrada para 
conseguir la combinación de ellos que cumpla con las condiciones dadas. Aquí la salida no 
es una lista de elementos del conjunto de entrada, sino una lista de combinaciones de ellos. 
Entender estas formas es muy importante porque esto afectará considerablemente el diseño de las 
técnicas de resolución a aplicar. En el caso de problemas de búsqueda directa, usualmente la 
técnica esta en hacer un único recorrido ordenado por la entrada, mientras la búsqueda 
combinatoria recorre la entrada varias veces, armando combinaciones que cumplan con las 
condiciones. 
Ejemplo: 
Factorización prima. Dado un número compuesto9 N, encontrar sus factores primos. 
Un número entero, si no es primo, puede ser expresado como un producto de números menores 
que él. En matemática, a esto se le llama Factorización. La Factorización Prima es un caso particular 
de factorización, donde se exige que los números menores, llamados factores, sean primos. 
������� 	� $��
���� 
����� 
 105 � 3 & 5 & 7 
207 � 3 & 3 & 23 
349 � 349 ��� �����! 
Es importante entender que la entrada de este problema de búsqueda directa no es el número a 
descomponer, sino todos los posibles divisores de este. Por ejemplo, si se quiere descomponer el 
número 105, el conjunto de entrada al problema es el rango de números enteros [1, 105]10. Dentro 
de este conjunto hay que buscar los elementos (números) que cumplan con la condición (ser un 
divisor de 105 y ser un número primo). 
PROBLEMAS DE CONTEO 
Cuando se necesita saber la cantidad de elementos que cumplen con determinada condición, se está 
frente a un Problema de Conteo. Usualmente se define de la siguiente manera: dado el conjunto de 
 
9 Número que es el resultado del producto de otros números, llamados factores. 
10 Este rango es el más obvio, pero se puede reducir de varias maneras. Por ejemplo, [1, 52], ya que si 
multiplicamos 53 (vecino de la cota superior) por cualquier número entero mayor que 1 da más de 105. 
García 2010 Introducción a los Algoritmos Genéticos 
11 
 
entrada E, determinar el tamaño de S, donde S es un subconjunto de E formado por los elementos 
que cumplen con la condición dada11. Esta es la forma de los problemas de conteo más estudiada 
por las ciencias de la computación porque son las que requieren un cómputo particular para su 
resolución. 
En este tipo de problemas, el espacio de solución siempre es un número entero mayor o igual que 
cero, es decir [0,∞). Pero aquí el espacio de solución ayuda poco a la creación de la técnica de 
resolución, ya que la tarea importante es manipular la entrada para contar eficientemente los 
elementos. 
Ejemplo: 
Grafos Hamiltonianos. Contar la cantidad de ciclos hamiltonianos existentes en un grafo. 
 
Fig. 7. Un ciclo hamiltoniano en un dodecaedro 
Un Ciclo Hamiltoniano es un camino en el grafo que visita todos los nodos una sola vez, empezando 
y terminando en el mismo nodo. Para dar respuesta a este problema se debe diseñar un algoritmo 
que vaya visitando todos los nodos del grafo, sin repeticiones, comenzando y terminando en el 
mismo nodo y cada vez que consiga un ciclo que cumpla con las condiciones dadas, se aumenta un 
contador, que comienza en cero porque se asume que no hay ciclos al comienzo. Nótese que el 
contador siempre será un número entero mayor o igual a cero, igual que el espacio de solución de 
todos los problemas de conteo. 
 
11 Hay problemas de conteo que no tienen esta forma, como por ejemplo los problemas que se resuelven con 
Teoría Combinatoria. 
García 2010 Introducción a los Algoritmos Genéticos 
12 
 
PROBLEMAS DE OPTIMIZACIÓN 
Cuando se debe maximizar o minimizar el resultado arrojado por una función o procedimiento, se 
dice que es un problema de optimización. Su forma usual es una función, llamada función objetivo, 
que a partir de un grupo de parámetros de entrada, arroja una única salida. El objetivo es encontrar 
los valores de los parámetros de entrada que arrojen la mejor salida (máximo o mínimo). 
El espacio de solución de este tipo de problemas está conformado por tuplas de tamaño igual al 
número de parámetros que recibe la función objetivo, donde cada posición de la tupla representa un 
parámetro. Este tipo de espacio de solución es el más sencillo de manipular porque las tuplas 
funcionan como un punto en un sistema de coordenadas12. Esto es importante tenerlo claro, ya que 
la respuesta a este tipo de problemas son los valores de los parámetros de entrada (una tupla), no la 
salida que ellos producen. La salida de la función es un resultado secundario, que es consecuencia 
de haber conseguido la tupla que optimiza al problema. 
 
 
 
 
 
 
Fig. 8. Espacio de Solución de un problema de optimizaciónde dos parámetros 
 
Como la resolución de este tipo de problemas consiste en conseguir un máximo o mínimo, el espacio 
de solución debe estar bien limitado en la dirección de la optimización, aunque su contenido sea 
infinito. Si esto no es así, siempre se podrá conseguir una tupla A que genere una mejor salida que la 
tupla B, lo que hace que la búsqueda de la mejor tupla sea imposible o, en el mejor de los casos, 
obvia. Las fronteras del espacio de solución se llaman restricciones, las cuales simplemente indican 
que valores de los parámetros de entrada son considerados válidos. 
 
12 En la mayoría de los casos el dominio de los parámetros es R lo que hace al espacio de solución continuo. 
Esto permite usar el Sistema de Coordenada Cartesiano para graficar dicho espacio. 
Parámetro A 
Espacio de 
Solución 
Parámetro B 
Salida de la 
Función a 
optimizar 
García 2010 Introducción a los Algoritmos Genéticos 
13 
 
Ejemplo: 
Problema de la Mochila. Se tiene un contenedor (mochila) que tiene una capacidad máxima M (en 
peso), y un grupo de elementos, cada uno con peso Pi y valor Vi. El objetivo es conseguir la 
combinación de elementos que entren dentro del contenedor (∑ 
( ) *) que maximice el valor del 
contenido (*�& ∑ �(). Este es un problema de optimización combinatoria. 
 
 
 
 
 
Fig. 9 Problema de la Mochila 
La forma más común de plantear el espacio de solución es con tuplas de tamaño igual a la cantidad 
de elementos del problema. Los valores admisibles en la tupla son solo uno (1) y cero (0), donde 
uno (1) indica que el elemento está dentro del contenedor, mientras que cero (0) indica que esta 
fuera. Para obtener el peso de la mochila para determinada tupla A, se suman todos los pesos de los 
elementos con uno (1) en la tupla, mientras lo que tienen cero (0) no se suman porque están fuera. 
El proceso es equivalente para obtener el valor de la mochila. Definido de esta manera, el problema 
se centra en conseguir la combinación de unos y ceros que respete la restricción de peso del 
contenedor y maximice el valor de su contenido. 
Debido a la restricción de peso del contenedor, la respuesta a este problema no es simplemente 
“meter a todos los elementos dentro de la mochila”, por lo cual hay tuplas que son factibles y otras 
que son no factibles. 
EQUIVALENCIA ENTRE TIPOS DE PROBLEMAS 
Los problemas se clasifican por tipos, pero pequeñas transformaciones a la forma del mismo 
permiten cambiarlo a otro tipo de problema, considerándolo equivalente. Lo importante es que este 
cambio sea tan pequeño en comparación con el resto de la definición que el problema, con o sin el 
cambio, se resuelva prácticamente de la misma forma. 
Peso = 5 
Valor = 3 
Peso = 7 
Valor = 6 
Peso = 3 
Valor = 6 
Peso = 9 
Valor = 5 
Peso = 3 
Valor = 4 
Peso = 4 
Valor = 4 
Peso = 8 
Valor = 14 
MOCHILA 
Capacidad = 10 
 
 
 
Peso = 5 
Valor = 8 
Peso = 3 
Valor = 6 
García 2010 Introducción a los Algoritmos Genéticos 
14 
 
En la Tabla 1 se puede ver un par de problemas equivalentes. El primero, conocer los divisores de 
un número X. Este es un problema de búsqueda, donde la entrada son todos los números enteros 
menores que Piso(X/2) y la salida una lista de números enteros. El segundo problema, es conocer si 
un número X es primo o no. Esto es un problema de decisión sencillo: una sentencia como entrada 
(¿X es primo?) y de respuesta binaria (SI o NO). Pero analizando en detalle los problemas, al 
conseguir los divisores de X podemos saber si es primo o no con una simple operación extra: contar 
los divisores. Nótese que el foco del problema está en conseguir los divisores, porque una vez 
encontrados, contarlos es muy sencillo. Por este análisis, llamado reducción13, podemos decir que el 
problema de decisión “Determinar si X es primo o no” es equivalente al problema de búsqueda 
“Determinar los divisores de X”. 
 
Ejemplo: Problema de la Partición. 
Problema de 
Decisión 
Problema de de 
Búsqueda 
Problema de Conteo Problema de 
Optimización 
Dado un conjunto de 
números, determinar si 
se puede dividir en dos 
particiones haciendo 
que la suma algebraica 
de los elementos de las 
particiones sumen lo 
mismo. 
Dado un conjunto de 
números, determinar 
todas las formas de 
dividir a dicho conjunto 
en dos particiones, 
haciendo que la suma de 
los elementos de las 
particiones sumen lo 
mismo. 
Dado un conjunto de 
números, determinar 
cuántas formas existen 
de dividir a dicho 
conjunto en dos 
particiones, haciendo que 
la suma de los elementos 
de las particiones sumen 
lo mismo. 
Dado un conjunto de 
números, determinar la 
división en dos 
particiones que minimice 
la diferencia en la suma 
de los elementos de las 
particiones. 
Tabla 2. Problema de la Partición planteado de varias formas 
En la Tabla 2 se puede ver como el problema de la partición se puede plantear de diversas formas, 
manteniendo su esencia. Nótese que si resolvemos el problema de búsqueda, podemos responder el 
problema de conteo y el problema de decisión con una simple operación extra. Ahora, en muchos 
casos solo nos importará resolver el problema de decisión, así que al encontrar la primera forma de 
particionar el conjunto detenemos la búsqueda. Aquí se nota que, aunque sean equivalentes, 
resolver el problema de decisión de este planteamiento es más “rápido” que resolver el problema de 
búsqueda, aunque la complejidad es la misma: conseguir la partición. El problema de optimización 
de este planteamiento difiere un poco de los demás, ya que el no busca saber si se puede o no 
particionar el conjunto respetando la restricción, sino que conseguirá las particiones que 
 
13 Formalmente, un problema computable es reducible a otro problema computable cuando se puede usar la 
técnica de resolución de uno en el otro para resolverlo eficientemente. 
García 2010 Introducción a los Algoritmos Genéticos 
15 
 
minimicen la diferencia de sus sumas. Es evidente, que el mejor resultado que puede conseguir la 
técnica de resolución del problema de optimización es unas particiones cuya diferencia sea cero (0), 
lo que es igual a resolver el problema de búsqueda. 
 
Ejemplo: Factorización Prima. 
Problema de 
Decisión 
Problema de de 
Búsqueda 
Problema de Conteo Problema de 
Optimización 
Dado un número N, 
determinar si ese 
número tiene solo dos 
factores primos. 
Dado un número N, 
determinar sus factores 
primos. 
Dado un número N, 
determinar la cantidad 
de factores primos que lo 
componen. 
 
---------------- 
Tabla 3. Problema de la Factorización Prima planteado de varias formas 
En la Tabla 3 se tiene al problema de la factorización prima planteado de diversas formas. Aquí 
nuevamente resolver el problema de búsqueda permite responder el problema de decisión y el 
problema de conteo agregando una sencilla operación. Lo importante a observar en este ejemplo, es 
que no existe un problema de optimización obvio para el problema de la factorización prima14. Esto 
busca ejemplificar que la reducción no siempre puede conseguir equivalencias. 
 
Ejemplo: Problema de la Mochila. 
Problema de 
Decisión 
Problema de de 
Búsqueda 
Problema de Conteo Problema de 
Optimización 
Dado un contenedor de 
capacidad C y 
elementos con peso Pi y 
valor Vi, determinar si 
existe un contenido 
que respete la 
capacidad del 
contenedor ( ∑ +, < C) 
y cuyo valor sea igual a 
R (∑ -, � .). 
Dado un contenedor de 
capacidad C y elementos 
con peso Pi y valor Vi, 
determinar todas las 
formas posibles de crear 
un contenido que respete 
la capacidad del 
contenedor ( ∑ 
� < C) y 
cuyo valor sea igual a R 
(∑ �� � /). 
Dado un contenedor de 
capacidad C y elementos 
con peso Pi y valor Vi, 
determinar cuántas 
formas existen de crear 
un contenido que respete 
la capacidad del 
contenedor ( ∑ 
� < C) y 
cuyovalor sea igual a R 
(∑ �� � /). 
Dado un contenedor de 
capacidad C y elementos 
con peso Pi y valor Vi, 
maximizar el valor del 
contenido del contenedor 
(*�& ∑ ��), respetando 
que la suma de su 
contenido no supere su 
capacidad ( ∑ 
� < C) 
Tabla 4. Problema de la Mochila planteado de varias formas 
 
14 Puede que exista un problema de optimización complejo, que requiera en determinada parte resolver el 
problema de la factorización prima, pero usualmente es un paso a realizar, no el objetivo de la optimización. 
García 2010 Introducción a los Algoritmos Genéticos 
16 
 
El problema de la Mochila puede ser planteado de diversas formas, como se ve en la Tabla 4. 
Normalmente, la forma de problema de optimización es la más usada, pero aquí la reducción nos 
permitió conseguir problemas equivalentes, ya que puede que no se quiera optimizar el valor de la 
mochila, sino conseguir la combinación que nos permita obtener exactamente el valor deseado. 
COMPLEJIDAD COMPUTACIONAL DE LOS PROBLEMAS 
Aunque los estudios enmarcados en la Teoría de la Complejidad Computacional son de corte 
matemático muy abstracto y con fines más demostrativos que prácticos, es importante que las 
personas dedicadas a resolver problemas entiendan los principios que rigen a esta área de 
conocimiento, ya que las intuiciones y demostraciones manejadas en la Teoría de la Complejidad 
afectan considerablemente la forma de resolver problemas en la vida real. 
La Teoría de la Complejidad se dedica a determinar la complejidad intrínseca asociada a las tareas 
computacionales, es decir, a problemas computables. Nótese que el objetivo está asociado al 
problema, no a la técnica de resolución, por lo cual la complejidad computacional es una 
característica del problema, sin importar cómo se solucione15. 
La complejidad computacional de un problema es una característica cualitativa que busca agrupar 
problemas computables por la cantidad de tiempo de procesamiento y espacio de memoria que 
consume su resolución. Pero los problemas computables no pueden tratarse aislándolo del contexto 
como cualquier otro problema matemático, ya que está demostrado que el consumo de recursos en 
la resolución de un problema depende del tamaño de la entrada y el modelo de cómputo. En la 
práctica esto es fácilmente observable en el comportamiento de las computadoras16: 
• Una búsqueda secuencial en un archivo de 2 Megabytes requiere MENOS tiempo de 
procesamiento que la misma búsqueda en un archivo de 2 Gigabytes. 
• Un algoritmo de búsqueda secuencial en un archivo, ejecutada en un computador con un 
solo procesador requiere MÁS tiempo de procesamiento que la misma búsqueda, en el 
mismo archivo, en un computador de dos procesadores (paralelismo). 
 
15 Realmente, la complejidad de un problema se determina basándose en la forma en que se comporta la 
técnica de resolución más eficiente conocida para resolverlo. Así que aunque la complejidad se le atribuya al 
problema, siempre depende de la mejor técnica de resolución conocida. 
16 Estos ejemplos pueden no ser rigurosos ni formales para la Teoría de Complejidad, pero si muestran a 
grandes rasgos el impacto que tiene en el consumo de recursos el tamaño de la entrada y el modelo de 
cómputo. 
García 2010 Introducción a los Algoritmos Genéticos 
17 
 
Para formalizar esta agrupación, se han definido clases de complejidad que definen funciones 
matemáticas de comportamiento del consumo de recursos basado en el tamaño de la entrada. Es 
importante destacar que dicha función está formulada según el modelo de cómputo usado: si 
cambia el modelo de cómputo, la función tendrá una forma diferente. 
Otro aspecto importante en la definición de clases de complejidad es el tipo de problema, pero esto 
requiere poca atención en la práctica ya que empíricamente se piensa que todo problema puede ser 
planteado como un problema de decisión (por reducción). Gracias a esta guía empírica casi siempre 
se utiliza las clases de complejidad definidas para los problemas de decisión al momento de describir 
la complejidad de la mayoría de los problemas computables. 
En resumen, los problemas computables se clasifican por clases de complejidad, las cuales se definen 
analizando tres (3) aspectos del problema: tipo de problema, modelo de cómputo y el 
comportamiento de consumo de recursos (función). 
Sabiendo cómo se crean las clases de complejidad, es importante entender lo difícil que es 
considerar todos los modelos de cómputo existentes, principalmente por su complejidad 
matemática. Es por esta razón que la Teoría de la Complejidad utiliza varias formas de Máquinas de 
Turing para simplificar el análisis, pero sin sacrificar su validez en el mundo real. Este punto está 
tratado en la Tesis de Church-Turing, la cual dice que “un problema computable puede ser resuelto 
en una Máquina de Turing si y solo si puede ser resuelto por cualquier otro modelo de cómputo 
general y razonable”17. Asumiendo esta tesis, al demostrar que un problema se puede solucionar en 
una Máquina de Turing se concluye que también se puede resolver en un computador actual. 
CLASES P, NP Y NP-COMPLETO 
Una buena forma de entender las clases de complejidad es pensar en ellas como conjuntos de 
problemas y por ende, hay que familiarizarse con las intersecciones y los subconjuntos, que 
contienen a los problemas que pertenecen a más de una clase. 
Basados en la regla empírica que intuye que por reducción todo problema puede expresarse como 
un problema de decisión, aquí se mencionará solamente las clases que clasifican a dichos problemas. 
 
17 Es una Tesis y no un Teorema porque es una intuición empírica no demostrada. La forma de “modelo de 
cómputo general y razonable” se dejó abstracto intencionalmente para hacer entrar dentro de ella a todos 
aquellos modelos de cómputo conocidos hasta el momento. 
García 2010 Introducción a los Algoritmos Genéticos 
18 
 
Las dos primeras clases que hay que mencionar relacionada con los problemas de decisión, son las 
clases decidible e indecidible. Estos dos conjuntos disjuntos, separan a los problemas que se pueden 
solucionar (decidibles) de los que no (indecidibles). 
 
 
 
Fig. 10 Clases de problemas de decisión 
Los problemas indecidibles son categóricamente no solucionables por computadora, por lo cual su 
estudio en la Teoría de la Complejidad no va más allá de la determinación de su indecibilidad: Si se 
determina por demostración matemática, que un problema no se puede solucionar por 
computadora, se clasifica como indecidible y no se estudia más18. 
Los problemas decidibles, que son aquellos problemas de decisión a los cuales se les pueden crear al 
menos un algoritmo que los solucione, son el centro de estudio de las ciencias de la computación, 
porque son todos aquellos planteamientos a los que una computadora puede dar respuesta. 
Dentro del conjunto de problemas decidibles, se encuentra un zoológico de clases que agrupan a 
dichos problemas por la forma que consumen espacio de memoria y tiempo de procesamiento, pero 
este último aspecto es el más estudiado en la práctica. 
 La clase P fue una de las primeras en definirse. Incluye a todos los problemas de decisión que puede 
conseguírsele respuesta en tiempo polinomial (���0��!) en una Máquina de Turing 
Determinística19. En otras palabras, se trata de todos aquellos problemas que para una entrada de 
tamaño n, se le consigue respuesta en un tiempo 
 � ���0��!. Por ejemplo: si para un determinado 
problema con una entrada n se puede conseguir una solución en 
 � �1 2 en una Máquina de 
Turing Determinística o equivalente, se puede decir que el problema pertenece a la clase P. 
 
18 Un problema indecidible muy usadocomo ejemplo por los computistas es el Halting Problem, el cual 
consiste en construir un algoritmo que dado otro algoritmo O con su entrada E, pueda determinar si el 
algoritmo 0 terminará de procesar a E en algún momento. Esto es equivalente a crear una aplicación que 
determine que otra aplicación está “guindada”. 
19 Una Máquina de Turing Determinística es aquella que para determinado comando, siempre ejecuta una 
misma y única acción. 
Decidibles Indecidibles 
García 2010 Introducción a los Algoritmos Genéticos 
19 
 
La clase P es una de las más obvias dentro de la Teoría de la Complejidad, porque incluye a muchos 
de los problemas matemáticos básicos que requieren muchas operaciones consecutivas, lo cuales 
fueron los que motivaron la creación del computador. Por ejemplo, está demostrado que 
determinar si un número X es primo o no, es un problema de decisión de clase P. 
Ahora, NP es una clase particular de problemas donde no se habla del tiempo consumido para su 
solución, sino del tiempo consumido para determinar si una solución dada es correcta o no. Un 
problema pertenece a la clase NP si se puede chequear la validez de una solución dada en tiempo 
polinomial en una Máquina de Turing Determinística20. 
Con un pequeño ejercicio mental podemos entender que todo problema en P está también en NP: Si 
podemos conseguir la solución en tiempo polinomial (problema en P), en el peor de los casos 
validar si la solución es la correcta se tardará el mismo tiempo polinomial que conseguirla 
(problema en NP). Nuevamente el problema de determinar si un número es primo es edificante: 
Está demostrado que determinar si un número X es primo o no se resuelve en un tiempo 
polinomial, por ende está en P, ahora chequear la validez de la respuesta “X es primo” es igual a 
volver a determinar si X primo y esto se resuelve en tiempo polinomial, por lo cual el problema 
también está en NP. 
 
 
 
 
Fig. 11 Relación entre las clases P y NP 
Saber que todo problema P está también en NP responde positivamente a la pregunta ¿Todo 
problema que se puede solucionar en tiempo polinomial se puede validar su solución en tiempo 
polinomial?, pero lo que aún no se ha respondido categóricamente es el sentido inverso de esa 
pregunta ¿Todo problema al cual se le puede validar su solución en tiempo polinomial se puede 
 
20 La definición “original” de NP es: Un problema pertenece a NP si se puede obtener una solución en tiempo 
polinomial en una Máquina de Turing No Determinística. El detalle es que está demostrado que ambas 
definiciones son equivalente. 
P 
NP 
García 2010 Introducción a los Algoritmos Genéticos 
20 
 
solucionar en tiempo polinomial?21 De ser positiva la respuesta, eso implicaría que 
 � 2
, pero 
empíricamente se piensa que esto no es verdad, ya que hay muchos problemas a los cuales no se le 
ha podido diseñar una técnica de resolución que los solucione en tiempo polinomial, pero validar si 
la respuesta es correcta se puede hacer en tiempos polinomiales. Este conjunto es 2
 3 
. 
Estos problemas son los más estudiados por las ciencias de la computación, porque son problemas 
decidibles, lo que significa que son solucionables, pero que no se puede conseguir la respuesta 
correcta en tiempos humanamente decentes, lo que es casi igual a no solucionarlos. La esperanza 
está en que aunque no se ha conseguido una forma de solucionarlos en tiempo polinomial, 
matemáticamente no se ha demostrado que no hay forma de conseguirlo. 
Estudiando a fondo el conjunto de problemas pertenecientes a (2
 3 
) se definió un grupo 
particular de problemas llamados NP-Completos, cuya característica adicional es que todo problema 
en NP puede ser reducido a ellos, es decir, que cualquier problema NP se puede reducir a un 
problema NP-Completo. La definición de esta clase es un gran aporte, ya que si se soluciona en 
tiempos decentes un problema en NP-Completo, se estaría solucionando todos los problemas en NP, 
demostrando así que 
 � 2
. Pero la experimentación ha mostrado lo contrario, ya que los 
problemas pertenecientes a la clase NP-Completo son los problemas más difíciles de NP. 
 
 
 
 
Fig. 11 Relación entre las clases P, NP y NP-Completo 
Entendiendo las clases de complejidad y las relaciones entre ellos, solo falta conocer la técnica que 
determina si un problema pertenece o no a determinada clase. Formalmente, esto se logra a través 
de demostraciones matemáticas, basado en teoremas y axiomas, pero en la práctica la clave está en 
la reducción. Toda persona que resuelva problemas debe conocer la mayor cantidad de problemas 
posibles ya clasificados, y tratar de reducir el problema de la vida real a alguno de estos. 
 
21 Esta pregunta se le suele referenciar como P vs NP. Este planteamiento es considerado uno de los grandes 
enigmas matemáticos de la actualidad. 
P NP-Completo 
NP 
García 2010 Introducción a los Algoritmos Genéticos 
21 
 
Una vez clasificado el problema que se está tratando, la persona encargada de resolverlo puede 
aplicar una de las técnicas conocida para solucionarlos, haciendo pequeñas adaptaciones. Rara vez, 
una persona que soluciona problemas se ve forzado a definir una técnica de resolución nueva, esto 
es solo justificable si el problema no pudo ser clasificado por reducción22. 
EJEMPLOS: REDUCCIÓN DE PROBLEMAS REALES 
La realidad está llena de problemas y aquellos que pretendan resolverlos definitivamente deben 
tener la capacidad de abstracción que les permita reducirlos a un modelo matemático bien 
conocido o en estudio. Cualquier otra estrategia para resolver problemas que no contemple el 
modelado matemático y la reducción como parte fundamental del análisis están condenados a dar 
respuestas sesgadas, que solo con suerte resultarán ser las correctas. En Teoría de la Toma de 
Decisiones se clasifican las decisiones por la calidad del análisis previo a la toma de decisión, no al 
resultado: Una decisión es buena cuando se estudió a profundidad y los pasos de dicho estudio son 
reproducibles. Así, en caso de que el resultado sea positivo, siempre se podrá tomar la misma 
decisión cuando las condiciones, establecidas en el estudio, se den. En caso que el resultado sea 
negativo, se sabe que no se puede volver a tomar esa decisión en las condiciones determinadas por 
el estudio, lo que requiere que se profundice el análisis para llegar a la respuesta correcta. 
Una buena estrategia al momento de elaborar el modelo matemático, es compararlo con modelos ya 
existentes, tratando de hacer una reducción del mismo para ver si son equivalentes. De poder 
conseguirse una equivalencia entre el problema real y el problema abstracto ya estudiado, se 
podrán reutilizar las técnicas de resolución conocidas, lo que asegura que el problema se está 
abordando correctamente desde el punto de vista matemático. Si no se consigue una equivalencia, 
situación que es poco probable, valdrá la pena formalizar el problema encontrado tratando de 
clasificarlo y determinándole su complejidad, y así abultar los conocimientos en el área de 
problemas computables. 
Ejemplo: Balanceo de Carga23 ���� Problema de la Partición (clase NP-Completo) 
Para mejorar los tiempos de respuestas de aplicaciones de alta demanda, como muchas de las 
aplicaciones de internet, se suelen dedicar varios centros de cómputo (servidores) para atender a 
 
22 Las personas que se encargan de definir las técnicas de resolución a problemas conocidos y clasificados son 
investigadores cuyo foco de interés es la técnica de resolución en sí, más que el problema mismo. 
23 El Balanceo de Carga es un planteamiento que está en constante estudio por la academia y la industria, por 
lo cual, la estrategia de solución aquí plasmada puede no usarse comúnmente hoy en día.García 2010 Introducción a los Algoritmos Genéticos 
22 
 
las peticiones de los usuarios. Cada una de estas peticiones requiere una capacidad de memoria y 
procesamiento distinta, aunque haciendo un buen estudio estadístico se pueden crear “tipos de 
peticiones” que agrupen a las peticiones que se asemejen en la cantidad de memoria y 
procesamiento que consumen. Una vez creados los tipos de peticiones y cada una de las peticiones 
posibles clasificadas en dichos tipos, se puede crear un Balanceador de Carga, que busque repartir 
las peticiones concurrentes entre N servidores, buscando que cada uno de ellos realice la misma 
cantidad de esfuerzo computacional. 
Supóngase que se tiene tres tipos de peticiones A, B y C y cada una de ellas tiene asociado un 
consumo de memoria y procesamiento, establecido previamente por estudio estadístico. En 
determinado momento t, al Balanceador de Carga le llegan 4 peticiones al mismo tiempo, creando la 
situación de la Tabla 5. Ahora este debe repartir las peticiones entre dos (2) servidores, buscando 
que cada uno de ellos realice el mismo esfuerzo computacional. Es decir, para la situación de la 
Tabla 5 se desearía que cada servidor utilice 21,5 Kb de memoria y 14 mseg de procesador, pero 
las peticiones no se pueden separar, así que el problema aquí es conseguir dos (2) particiones de 
peticiones que minimicen la diferencia entre el esfuerzo computacional que se necesita para 
atenderlas. 
Petición Tipo Memoria Procesamiento 
1 A 8 Kb 5 mseg. 
2 B 15 Kb 3 mseg. 
3 C 5Kb 10 mseg. 
4 B 15 Kb 3 mseg. 
Total 43 Kb 28 mseg. 
Tabla 5. Ejemplo de 4 peticiones concurrentes en determinado momento t. 
Si se obvia la parte la parte técnica de manipulación de peticiones y la distribución de aplicaciones, 
al realizar una reducción del problema de balanceo de carga, se llegará a la forma de optimización 
del problema de la partición, como se ve en la Tabla 2. Poder hacer esta equivalencia nos permite 
atacar el problema del balanceo de carga con las mismas técnicas que resuelven el problema de la 
partición, lo que nos garantiza que la respuesta dada será buena, basada en certezas matemáticas. 
 
 
García 2010 Introducción a los Algoritmos Genéticos 
23 
 
Ejemplo: Ruptura de la encriptación RSA ���� Problema de la Factorización Prima (clase NP) 
El algoritmo RSA es uno de los algoritmos de encriptación de clave asimétrica24 más utilizado de 
hoy día para enviar datos de forma segura y autenticada. El aporte de este algoritmo está en la 
forma en la que genera la clave pública y la clave privada: 
La generación de las claves (pública y privada) se basa en varias operaciones matemáticas no muy 
complejas sobre un par de números, identificados en el algoritmo como p y q. Operando estos dos 
números con varias funciones matemáticas se obtienen todos los números que conforman la clave 
pública y la clave privada. La clave pública está formada por un número n (modulus n) y un 
exponente de cifrado e, mientras que la clave privada está formada por la el mismo número n y 
exponente de descifrado d. 
Es bien sabido, porque es parte del algoritmo RSA, que n es el producto de p y q (� � � 5 6). Si se 
puede obtener p y q a partir de n, que es parte de la clave pública, se puede obtener la clave privada 
(operando a p y q como lo dicta el algoritmo para obtener a d). Si se reduce el problema, obtener p y 
q a partir de n es equivalente a resolver el problema de factorización prima para n. 
Ejemplo: Repartición de paquetes ���� Problema de Grafos Hamiltonianos (clase NP-Completo) 
Las empresas mueven constantemente sus productos desde la fábrica hacia los almacenes, desde 
los almacenes hacia las tiendas, desde las tiendas hacia los hogares de los consumidores. Este 
transporte requiere la coordinación de dos aspectos fundamentales: los productos y el transporte25. 
El estudio del transporte es de suma importancia, ya que se debe diseñar una forma de operar que 
permita a los orígenes despachar a los destinos minimizando el costo de transportar los productos. 
Uno de los elementos más estudiados en la estructura de costo del transporte es la definición de la 
ruta de costo mínimo, ya que recorrer ineficientemente los destinos se traduce en costos que 
pueden evitarse. La ruta óptima debe considerar que el transporte visite todos los destinos 
necesarios, y evidentemente, volver al origen de donde partió26. 
 
24 La encriptación de clave asimétrica es una forma de cifrar y descifrar datos con una clave pública, que todo 
el mundo puede conocer, y una clave privada, que solo el que descifra los datos puede conocer. 
25 También son aspectos importantes la demanda y oferta de los productos, pero usualmente estos aspectos 
son difíciles de controlar y se asumen como condiciones. 
26 Esto no necesariamente es así, ya que dependiendo de la realidad de la empresa, el transporte pudiera 
partir de determinado lugar y pernotar en otro, pero esto es un pequeño detalle que no cambia la complejidad 
del problema 
García 2010
 
Este problema tiene una representación natural en grafos, donde los nodos son el origen y los 
destinos, los lados son los caminos, y los pesos de los la
en el grafo se obvian los destinos que el transporte no tiene que visitar, conseguir la ruta de costo 
mínimo es igual a resolver la forma de optimización del 
determinar el ciclo hamiltoniano de costo mínimo.
Fig. 10 El problema de repartición de paquetes en ciudades de Alemania
Ejemplo: Portafolio de Inversión 
Un portafolio de inversión es una combinación de bonos y acciones 
rendimiento al inversionista. Estadísticamente se ha determinado una relación entre la cantidad de 
dinero invertido en acciones y la cantidad de dinero invertida en bonos, y el riesgo que generará 
dicha combinación27. El riesgo se c
riesgo, aumenta el rendimiento, pero el objetivo de todo inversionista es maximizar el rendimiento, 
minimizando el riesgo. Ahora, estos estudios estadísticos solo hablan de acciones y bonos del
pasado, que seguramente ya no tengan el riesgo y el rendimiento de años o meses anteriores, o 
quizá ya ni existan. Es por eso que este estudio habla de las acciones y bonos como cosas abstractas, 
 
27 Este estudio se le suele asociar con la búsqueda del 
bonos y acciones que generan el mínimo riesgo.
2010 Introducción a los Algoritmos Genéticos 
24 
tiene una representación natural en grafos, donde los nodos son el origen y los 
destinos, los lados son los caminos, y los pesos de los lados el costo asociado a recorrer el camino. Si 
en el grafo se obvian los destinos que el transporte no tiene que visitar, conseguir la ruta de costo 
mínimo es igual a resolver la forma de optimización del problema de los grafos hamiltonianos
ciclo hamiltoniano de costo mínimo. 
 
El problema de repartición de paquetes en ciudades de Alemania
Portafolio de Inversión ���� Problema de la Mochila (clase NP-Completo)
Un portafolio de inversión es una combinación de bonos y acciones que generan determinado 
rendimiento al inversionista. Estadísticamente se ha determinado una relación entre la cantidad de 
dinero invertido en acciones y la cantidad de dinero invertida en bonos, y el riesgo que generará 
. El riesgo se comporta de forma directa al rendimiento, ya que al aumentar el 
riesgo, aumenta el rendimiento, pero el objetivo de todo inversionista es maximizar el rendimiento, 
minimizando el riesgo. Ahora, estos estudios estadísticos solo hablan de acciones y bonos del
pasado, que seguramente ya no tengan el riesgo y el rendimiento de años o meses anteriores, o 
quizá ya ni existan. Es por eso que este estudio habla de las acciones y bonos como cosas abstractas, 
Este estudio se le suele asociar con la búsqueda del Minimum Risk Portafolio, el cuál es una combinación de 
bonos y acciones que generan el mínimo riesgo.tiene una representación natural en grafos, donde los nodos son el origen y los 
dos el costo asociado a recorrer el camino. Si 
en el grafo se obvian los destinos que el transporte no tiene que visitar, conseguir la ruta de costo 
problema de los grafos hamiltonianos: 
El problema de repartición de paquetes en ciudades de Alemania 
Completo) 
que generan determinado 
rendimiento al inversionista. Estadísticamente se ha determinado una relación entre la cantidad de 
dinero invertido en acciones y la cantidad de dinero invertida en bonos, y el riesgo que generará 
omporta de forma directa al rendimiento, ya que al aumentar el 
riesgo, aumenta el rendimiento, pero el objetivo de todo inversionista es maximizar el rendimiento, 
minimizando el riesgo. Ahora, estos estudios estadísticos solo hablan de acciones y bonos del 
pasado, que seguramente ya no tengan el riesgo y el rendimiento de años o meses anteriores, o 
quizá ya ni existan. Es por eso que este estudio habla de las acciones y bonos como cosas abstractas, 
el cuál es una combinación de 
García 2010 Introducción a los Algoritmos Genéticos 
25 
 
que el inversionista debe transformar en realidad, seleccionando del mercado las acciones y bonos 
disponibles en la actualidad. Esta decisión, no es sencilla y suele ser imprudente tomarla sin tratar, 
por lo menos, de conseguir un modelo matemático, que si bien no considere todas las variables, que 
por lo menos tome en cuenta las que son importantes para el inversionista. 
 
 
 
 
 
Fig.11 Portafolio de Inversión que busca maximizar el rendimiento 
El modelo matemático que más se asemeja a este problema es la forma de optimización del 
problema de la mochila, donde el contenedor es el portafolio, la capacidad del contenedor es la 
cantidad de dinero que posee el inversionista, los elementos son las acciones y bonos. El peso de 
cada elemento es su costo de adquisición mientras que su valor es el rendimiento que promete28. El 
objetivo: maximizar el rendimiento del portafolio, respetando la cantidad de dinero disponible. 
TÉCNICAS DETERMINÍSTICAS PARA RESOLUCIÓN DE PROBLEMAS 
DE OPTIMIZACIÓN 
Una técnica computacional se considera determinística cuando para una entrada E retorna siempre 
la misma salida S, sin importar otras variables del entorno, como el tiempo. En pocas palabras son 
técnicas consistentes y sin contradicciones, ya que siempre arrojan la misma salida para cada 
entrada29. 
Teniendo claro que un problema se considera resuelto cuando se consigue su solución óptima, 
podemos decir que una técnica determinística de resolución de problemas es una técnica 
 
28 Es importante destacar que el rendimiento de los bonos es garantizado, mientras el rendimiento de las 
acciones es estimado a partir de proyecciones, pero para el estudio se suelen considerar igual o se puede 
multiplicar el rendimiento de la acción por algún factor asociado a la confianza en la proyección. 
29 Las funciones matemáticas son consideras determinísticas ya que siempre arroja el mismo resultado para 
cada valor posible de x. Por ejemplo: 7�&! � &1 para & � 2 8 7�&! � 4 
Costo = 5 
Rend. = 3 
Costo = 7 
Rend. = 6 
Costo = 3 
Rend. = 6 
Costo = 9 
Rend. = 5 
Costo = 3 
Rend. = 4 
Costo = 4 
Rend. = 4 
Costo = 8 MM 
Rendimiento = 14 M 
Portafolio 
Capacidad = 10 MM 
 
 
 
Costo = 5 
Rend. = 8 
Costo = 3 
Rend. = 6 
García 2010 Introducción a los Algoritmos Genéticos 
26 
 
computacional que consigue siempre la solución óptima SO para la entrada E, sin importar cuando 
ni como se ejecute la técnica. Este es el comportamiento deseado de toda técnica resolución de 
problemas, el detalle es que no siempre esta solución se consigue en tiempos humanamente 
aceptables; en pocas palabras, las técnicas determinísticas solo resuelven los problemas en P30. 
Es importante destacar, que hay técnicas determinísticas “genéricas”, que pueden ser aplicadas a 
problemas de diferente tipo y forma haciéndole pequeñas adecuaciones31, así como existen técnicas 
determinísticas “específicas” que solo resuelven a determinado problema. Aquí solo trataremos 
algunas técnicas determinísticas “genéricas” para la resolución de problemas de optimización, ya 
que una buena parte de los problemas de la vida real se plantean de esta forma. 
BÚSQUEDA EXHAUSTIVA 
Esta técnica es también llamada búsqueda por fuerza bruta por ser la solución más sencilla pero la 
menos “inteligente”. Esta técnica consiste en comparar cada solución factible SF con todas las otras 
soluciones factibles, si no existe una solución factible mejor, se puede decir que la solución factible SF 
es la solución óptima SO. Como esta técnica recorre todo el espacio de solución varias veces, dicho 
espacio no requiere estar ordenado de una manera especial. 
Solucion solucionOptima = null, solucionFactible = null; 
boolean esOptima; 
for(int i = 0; i < espacioDeSolucion.length; i++){ 
 solucionOptima = espacioDeSolucion[i]; 
 esOptima = true; 
 for(int j = 0; j < espacioDeSolucion.length; j++){ 
 solucionFactible = espacioDeSolucion[j]; 
 if(solucionFactible.esMejorQue(solucionOptima)){ 
 esOptima = false; 
 break; 
 } 
 } 
 if(esOptima){ 
 break; 
 } 
} 
return solucionOptima; 
Fig. 12 Pseudo-código de una búsqueda exhaustiva para problemas de optimización con espacio de 
solución no ordenados. 
 
 
30 Muchas de estas técnicas se puede aplicar a problemas NP, pero los tiempos de respuestas no son 
aceptables, hablándose usualmente de siglos o milenios del calendario gregoriano (el usado por el mundo 
occidental) para entradas grandes. 
31 A este tipo de técnicas también se le llaman meta-determinísticas. 
García 2010 Introducción a los Algoritmos Genéticos 
27 
 
Si se observa la Fig. 12 se puede notar claramente cómo funciona esta técnica: Se toma una solución 
y se asume como óptima luego se compara con TODAS las soluciones factibles del espacio de 
solución. Si alguna la vence, la marcamos como no óptima y pasamos a la próxima, si nadie la venció 
ya se consiguió la solución óptima y el algoritmo se detiene. 
Como muchas otras, esta técnica presenta dos escenarios: 
• El mejor escenario es cuando la primera solución considera óptima es la óptima, ya que se 
recorre el espacio de solución una sola vez, lo que implica n iteraciones (siendo n el tamaño 
del espacio de solución). 
• El peor escenario es cuando la última solución considerada óptima es la óptima, ya que se 
recorre el espacio de solución n veces, lo que implica n2 iteraciones. 
BÚSQUEDA TERNARIA 
Si el espacio de solución tiene un orden natural estrictamente ascendente y luego estrictamente 
descendente (o viceversa), se puede aplicar un principio de “divide y vencerás” para obtener la 
solución óptima. La búsqueda ternaria divide el espacio de solución en tres áreas A, B y C de igual 
tamaño. La idea es ir demostrando que la solución óptima no está en las áreas A ó C, y por ende esta 
en las dos restantes. Luego, se divide las áreas restantes en otras tres áreas y se repite el proceso, 
recursivamente, hasta que se consigue un área no divisible en tres, lo que es igual a decir que 
quedan solo dos soluciones factibles, que definitivamente una de ella es la solución óptima32. 
 
 
 
 
 
 
Fig. 13 Dos iteraciones de búsqueda ternaria en gráficas 
 
32 Es importante destacar que esta técnica puede tener un sinfín de variantes para adecuarlas al problema y 
su espacio de solución. La forma aquí descrita es una forma muy genérica. 
A 
Crece 
B C 
Crece 
Decrece 
Descartada A Estudiar 
A 
Crece 
B C 
Decrece 
Descartada A Estudiar 
Decrece 
García 2010 Introducción a los Algoritmos Genéticos 
28 
 
Esta técnica compara los puntos extremosde las áreas A, B y C determinando si la función crece o 
decrece en dicha área. Por ejemplo, en la primera gráfica de la Fig. 13 podemos observar que el 
área A y B crecen mientras el área C decrece. 
Una vez determinado el comportamiento de cada área, se puede notar que el punto máximo de la 
función estará entre un área que crece y una que decrece (o viceversa), porque entre ellas está el 
“punto de inflexión” de la función, es decir, la solución óptima. Volviendo a la Fig. 13 se puede 
observar que el punto más alto de la curva está siempre entre las dos áreas que cambian de 
comportamiento: en la primera gráfica podemos observar que el algoritmo decidió seguir 
estudiando las áreas B y C, donde este último contiene a la solución óptima. 
SIMPLEX 
Las técnicas basadas en búsquedas solo trabajan correctamente con espacios de solución ordenados 
y discretos donde la cantidad de soluciones factibles es finita. Pero existen muchos problemas cuyo 
espacio de solución es ordenado pero continuo y por ende entre dos soluciones factibles A y B 
cualesquiera, existen infinitas soluciones factibles. 
Cuando el modelo matemático de un problema de optimización, incluyendo las restricciones, está 
formado exclusivamente por ecuaciones y/o inecuaciones lineales y su espacio de solución es 
continuo y ordenado se pueden aplicar técnicas de resolución de problemas de programación 
lineal33, como el algoritmo SIMPLEX. 
 
 
 
 
 
Fig. 14. Problema de programación lineal planteado de forma gráfica 
 
33 Es importante saber que está demostrado que cualquier problema de programación lineal pertenece a la 
clase de complejidad P. 
Región 
Factible 
Restricción 
A 
Restricción 
B 
Restricción 
C 
García 2010 Introducción a los Algoritmos Genéticos 
29 
 
Esta técnica se basa en la premisa comprobada de que la solución óptima de los problemas de 
optimización está en las fronteras (restricciones) del espacio de solución, nunca en su interior. Esto 
reduce enormemente el espacio de solución, pero aún existen infinitos puntos en las fronteras 
(recuerde que el espacio es continuo). Pero además se sabe que la solución óptima está en las 
intersecciones de las restricciones (recuerde que son líneas rectas), por lo cual ya tenemos un grupo 
finitos de puntos en los cuales buscar. En la Fig. 14 se pueden ver las restricciones en verde, y las 
intersecciones, que son los puntos considerados por SIMPLEX, están marcadas con un círculo azul. 
Ciertamente, se puede aplicar una búsqueda exhaustiva en el conjunto finito de intersecciones de 
las restricciones, pero igualmente conseguir estos puntos requiere un esfuerzo computacional muy 
alto. SIMPLEX es un algoritmo muy eficiente porque es capaz de buscar ordenadamente sobre los 
puntos de las intersecciones sin saber cuáles son antes de comenzar, es decir, va calculando las 
intersecciones a medida que las necesita, lo que ahorra muchísimo esfuerzo computacional. 
RAMIFICACIÓN Y ACOTAMIENTO 
Muchos problemas de programación lineal no pueden dar respuesta con valores con decimales, 
porque no tendría sentido en la vida real. Esto hace que el espacio de solución vuelva a ser finito, 
pero agrega una dificultad: la solución óptima ya no está sobre las restricciones, sino sobre un punto 
“cerca” de ellas34. En la Fig. 15 se puede observar que la región factible no es un espacio continuo, 
sino un grupo de puntos. Es importante resaltar que las soluciones factibles no están sobre las 
intersecciones de las restricciones, y por ende SIMPLEX es incapaz de darle respuesta. 
 
 
 
 
 
 
Fig. 15 Problema de programación entera planteado de forma gráfica 
 
34 Un problema de programación entera o binaria, que no es más que un problema de programación lineal con 
restricciones especiales, pertenece a la clase NP-Completo 
Restricción 
A 
Restricción 
B 
Restricción 
C 
García 2010 Introducción a los Algoritmos Genéticos 
30 
 
 Una forma de solucionar este tipo de problemas es usando la técnica de Ramificación y 
Acotamiento, que consiste en ir agregando cotas (restricciones) al problema para que los puntos del 
espacio de solución formados por números enteros estén sobre las restricciones, y por ende se puede 
aplicar SIMPLEX. Al momento de agregar una cota, se deben considerar dos escenarios: que la cota 
sea del tipo “mayor o igual que” o del tipo “menor o igual que”, generándose así dos ramas. Esta 
agregación de cotas y resolución con SIMPLEX se va realizando recursivamente sobre cada una de 
las ramas hasta obtener la rama que contenga a la solución óptima. 
TÉCNICAS META-HEURÍSTICAS PARA RESOLUCIÓN DE PROBLEMAS 
DE OPTIMIZACIÓN 
Un problema se considera solucionado cuando se consigue la solución óptima, no una solución 
factible buena o mejor que otras en comparación. Es por esta razón que siempre se trata de resolver 
problemas usando técnicas determinísticas, ya que garantizan la obtención de la solución óptima. 
Pero si la técnica determinística promete la obtención de dicha solución utilizando una cantidad de 
tiempo y espacio increíblemente altos, se debe considerar que la técnica no puede aplicarse a ese 
problema. 
Retomando los conceptos de complejidad computacional, se dice que un problema está en la clase P 
si existe al menos una forma de solucionarlo en tiempos polinomiales en una Máquina de Turing sin 
importar el tamaño de la entrada, es decir, que exista al menos una técnica determinística que los 
solucione en tiempos decentes para cualquier entrada. Por ende, si un problema es NP-Completo, es 
porque ninguna de las técnicas determinísticas conocidas lo puede resolver en tiempos decentes si 
la entrada es relativamente grande35. Por esta razón, es que hoy en día se considera “aceptable” 
darle respuestas a los problemas NP-Completos con soluciones factibles buenas o mejores que otras 
por comparación, a través de técnicas heurísticas. 
Una técnica es considerada heurística cuando su diseño está basado en experiencias, intuiciones 
y/o inspiraciones que se aplican para conseguir una solución factible buena, la cual se asume que 
está muy cercana a la solución óptima, ya que estas técnicas carecen de un mecanismo que 
 
35 En la práctica se pueden aplicar técnicas determinísticas a problemas NP-Completos y conseguir la solución 
óptima, pero obviamente la entrada tiene que ser muy pequeña. A medida que la entrada aumenta en tamaño, 
el tiempo requerido para la resolución también aumenta pero no proporcionalmente. 
García 2010 Introducción a los Algoritmos Genéticos 
31 
 
garantice que todas las soluciones fueron consideradas36. Por esta razón, nunca se puede saber si la 
solución factible encontrada por una técnica heurística es o no es la solución óptima. 
Otra característica usual de las técnicas heurísticas es que la solución factible que dan como 
respuesta puede cambiar dependiendo de cuando se ejecute. En otras palabras, ejecutar dos veces 
una técnica heurística para un problema con la misma entrada puede generar dos soluciones 
factibles distintas, el detalle es que estas soluciones deben generar un beneficio igual o parecido. 
Aquellas técnicas heurísticas “genéricas” que pueden aplicarse a varios problemas, e incluso, 
ignoran la forma del mismo, se le llaman técnicas meta-heurísticas. Estas suelen ser las más 
utilizadas en la resolución de problemas NP-Completos por su versatilidad y su comprobada 
efectividad. 
BÚSQUEDA TABÚ 
La búsqueda tabú es una técnica de búsqueda local, es decir, que no busca en todo el espacio de 
solución sino que empiezan con una determinada solución factible del espacio y se limita a buscar en 
sus “alrededores”. Nótese que lo importante aquí está en determinar la solución factible inicial y 
definir los “alrededores” donde se buscará:dos de los criterios más sencillos de usar son empezar 
en una solución factible seleccionada de forma aleatoria y definir los “alrededores” a través de la 
distancia cartesiana entre las soluciones factibles. Una vez parada en una solución factible, llamada 
solución actual, las técnicas de búsqueda local seleccionan la mejor solución en sus “alrededores”. 
Esto lo hacen iterativamente hasta que se cumpla una condición de parada, usualmente un número 
de iteraciones definido al comienzo o si no consiguen una solución factible mejor que la solución 
actual en los “alrededores”. 
 
 
 
 
Fig. 16 Una representación de la Búsqueda Tabú 
 
36 Las técnicas que cuentan con este tipo de mecanismos son las determinísticas 
Iteración 
Uno 
Iteración 
Dos 
Iteración 
Tres 
Iteración 
Cuatro 
Solución 
Actual 
Solución 
Actual 
Solución 
Actual 
Solución 
Actual 
García 2010 Introducción a los Algoritmos Genéticos 
32 
 
La búsqueda tabú es una implementación especial de una búsqueda local por poseer una lista tabú, 
que contiene a todas las soluciones que el algoritmo debe ignorar de los “alrededores”. La lista tabú 
puede contener soluciones indeseables por alguna restricción y/o soluciones ya consideradas. En la 
Fig. 16 se puede notar que las soluciones factibles de los “alrededores” de la solución actual tienen 
un color diferente para cada iteración, lo que representa las soluciones a estudiar en dicha 
iteración. Nótese que por ejemplo en la iteración tres no se consideran las soluciones de la iteración 
dos aunque estén muy cercanas a la solución actual, ya que están contenidas en la lista tabú porque 
ya fueron consideradas. 
SIMULATED ANNEALING 
Esta técnica meta-heurística es una implementación especial de una búsqueda local, es decir, que su 
funcionamiento principal se basa en la búsqueda de una mejor solución que la actual en los 
“alrededores” hasta que se cumpla una condición de parada definida. 
Simulated Annealing define su funcionamiento inspirándose en el proceso de Recocido de Acero, 
técnica empleada para disminuir los defectos en el material que consiste en calentar el acero para 
luego enfriarlo controladamente. El calor hace que los átomos salgan de su posición inicial, 
cambiando a posiciones de mayor energía. Cuando la temperatura del material es alta los átomos se 
mueven prácticamente de forma aleatoria pero mientras baja la temperatura del material de forma 
controlada el movimiento de los átomos se hace más selectivo, ya que el material presenta mayores 
diferenciales de energía y un determinado átomo puede no conseguir cerca de él una mejor 
posición en comparación con su posición actual. 
En la Fig. 17 se puede observar una implementación de una búsqueda local inspirada en el proceso 
de Recocido del Acero. Lo primero que se define es la temperatura actual que suele ser un valor 
muy alto, y una temperatura mínima a la que se llegará cuando poco a poco se disminuya la 
temperatura (como en el Recocido). Estas dos temperaturas forman parte de la condición de parada 
de esta técnica, ya que cuando la temperatura actual sea menor o igual que la temperatura mínima, 
el algoritmo se detiene37. Luego, se selecciona la solución factible donde se comenzará la búsqueda. 
La forma más sencilla de hacerlo es seleccionando una solución al azar. Una vez establecidas las 
temperaturas y seleccionada la solución factible inicial comienzan las iteraciones. 
 
37 Otras condiciones de parada adicionales se pueden agregar al algoritmo para mejorar su funcionamiento, 
como por ejemplo número máximo número de iteraciones. 
García 2010 Introducción a los Algoritmos Genéticos 
33 
 
int temperaturaActual = 999999999; 
int temperaturaMinima = 9999; 
 
Solucion solucionActual = espacioDeSolucion.seleccionarSolucionInicial(); 
Solucion solucionProxima = null; 
boolean bajarTemperatura; 
 
while(temperaturaActual > temperaturaMinima){ 
 bajarTemperatura = false; 
 while(!bajarTemperatura){ 
 solucionProxima = 
 espacioDeSolucion.seleccionarSolucionCercaDe(solucionActual); 
 double deltaDeEnergia = solucionProxima.costo() – solucionActual.costo(); 
 if(deltaDeEnergia < 0){ 
 solucionActual = solucionProxima; 
 bajarTemperatura = true; 
 } else { 
 double probabilidad = 
 DistribucionBoltzmann.calcular(deltaDeEnergia,temperaturaActual); 
 double aleatorio = Math.random(); 
 
 if(aleatorio > probabilidad){ 
 solucionActual = solucionProxima; 
 bajarTemperatura = true; 
 } 
 } 
 } 
 ControladorDeTemperatura.bajar(temperaturaActual); 
} 
return solucionActual; 
Fig. 17 Pseudo-código de Simulated Annealing para un problema de minimización. 
Para cada iteración, se selecciona una solución de los “alrededores” de la solución actual, la cual se 
analizará para ver si es aceptable o no como próxima solución a considerar. Si la nueva solución 
mejora a la actual, ya se acepta como solución actual y se pasa a la próxima iteración, sino se 
aceptará la nueva solución basándose en una probabilidad, usando una distribución de Boltzmann38 
(�9�
∆;<;=>?@
A;BC;=@AD=@!) que depende de la desmejora que genera la nueva solución (delta) y la temperatura 
actual.39 Luego de este análisis, se disminuye la temperatura actual antes de seleccionar la próxima 
solución a estudiar. Una de las estrategias más sencillas para disminuir la temperatura es restarle 
una constante (disminución lineal). 
 
 
38 La distribución probabilística de Boltzmann describe los estados de un sistema desde la perspectiva de la 
energía. 
39 Nótese que si la solución no es seleccionada ni por su delta ni por la distribución probabilística, se 
selecciona una nueva solución a considerar pero sin disminuir la temperatura actual. 
García 2010 Introducción a los Algoritmos Genéticos 
34 
 
ALGORITMOS GENÉTICOS – TÉCNICA META-HEURÍSTICA 
BIOINSPIRADA 
Las técnicas meta-heurísticas basan su funcionamiento en intuiciones educadas, experiencias 
repetidas o inspiraciones en otros elementos porque suelen ser guías confiables en la resolución de 
problemas por demostración experimental. Por ejemplo, la evolución de los seres vivos es, sin duda 
alguna, un mecanismo de resolución de problemas de optimización muy efectivo: Para las especies, 
sobrevivir es el problema a resolver y las soluciones son aquellos individuos de la especie que lo 
logren. La vida ha demostrado a través del tiempo que las especies siempre consiguen un grupo de 
individuos que evitan la extinción, por lo cual este proceso evolutivo es una guía empírica excelente 
para solucionar problemas. 
Las especies logran sobrevivir gracias a los mecanismos evolutivos que hacen que los individuos de 
próximas generaciones se adapten cada vez más a las condiciones del medio ambiente. Estos 
mecanismos tienen principios sencillos, aunque en la vida real ocurren de forma increíblemente 
compleja. 
Uno de los mecanismos más conocidos es la selección natural, aporte de Charles Darwin, el cual 
establece que los individuos más aptos de la especie son los que sobreviven y por esto, a medida 
que pase el tiempo los individuos menos aptos perecen. La interpretación de esto es muy sencilla: 
los individuos que no solucionan el problema de sobrevivir correctamente desaparecen, mientras 
aquellos que tienen una solución aceptable perduran. En la naturaleza, la definición de aptitud de 
un individuo para sobrevivir es increíblemente compleja, pero de una u otra forma existe. Por 
ejemplo, para las gacelas en África, la velocidad y perspicacia en la huida es vital para sobrevivir a 
los ataques de depredadores, por lo