Métodos Heurísticos

Los problemas de optimización se dividen de manera natural en dos categorías: problemas de

optimización con variables continuas y problemas de optimización con variables discretas. A estos
últimos se les llama problemas de optimización combinatoria. En problemas de tipo continuo, se
busca la solución sobre un conjunto de números reales con ciertas propiedades de continuidad y
generalmente de convexidad; en los problemas de optimización combinatoria, se busca la solución
sobre un conjunto finito o infinito numerable de objetos para los que se pueda definir una función
que evalúe la “calidad” de cada objeto. Estas dos clases de problemas tienen diferentes retos y los
métodos para resolverlos son distintos.

Uno de los problemas computacionales a resolver en optimización combinatoria es la explosión

combinatoria. La explosión combinatoria se encuentra en situaciones donde las elecciones están
compuestas secuencialmente, es decir, dado un conjunto de elementos se pueden obtener diferentes
arreglos ordenados de éstos, permitiendo una vasta cantidad de posibilidades. Situaciones de este
tipo ocurren en problemas de inversión financiera, manejo de inventarios, diseño de circuitos
integrados, manejo de recursos hidráulicos, mantenimiento de sistemas, etc.

Una característica recurrente en los problemas de optimización combinatoria es el hecho que son
muy “fáciles de entender y enunciar, pero generalmente son “difíciles” de resolver en tiempo
razonable. Podría pensarse que la solución de un problema de optimización combinatoria se
restringe únicamente a buscar de manera exhaustiva el valor máximo o mínimo en un conjunto
finito de posibilidades y que, usando una computadora veloz, el problema carecería de interés
matemático, sin pensar por un momento, en el tamaño de este conjunto. En la mayoría de los casos,
este conjunto de posibilidades crece de manera alarmante conforme crece el tamaño de la instancia
del problema. Es frecuente que los problemas de este tipo tengan n! (n factorial) o más soluciones
factibles (donde n es el tamaño de la instancia). Ahora, si una computadora pudiera ser programada
para examinar soluciones a razón de un billón de soluciones por segundo, la computadora
terminaría su tarea, para n = 23 en alrededor de 820 años, para n =24 en alrededor de 19,674 años
y así sucesivamente. Por lo que no tiene sentido resolver de esa forma un problema si al interesado
no le alcanza la vida para ver la respuesta.

Bajo las consideraciones anteriores, el interés de la optimización combinatoria pasa a ser el de

desarrollar algoritmos para los cuales el número de etapas computacionales elementales sea
aceptablemente pequeño. Equivalentemente, que encuentren la solución en un tiempo razonable o
como suele decirse (en términos formales) en “tiempo polinomial”; esto es, los pasos
computacionales elementales es una función polinomial del número de datos.

Durante muchos años se han hecho esfuerzos para resolver problemas de optimización
combinatoria, hay problemas para los que existen algoritmos rápidos y eficientes; por ejemplo, el
problema de programación lineal, flujo en redes, acoplamiento, etc. Sin embargo, existen muchos
problemas de optimización combinatoria para los que no se conocen algoritmos eficientes que los
resuelvan cuando el tamaño del problema es mediano o de gran escala; por ejemplo, el problema
del agente viajero, el problema de asignación cuadrático, el problema de particionamiento, etc.
Estos últimos problemas tienen más de 60 años de ser atacados, en la mayoría de los casos, por
algoritmos desarrollados especialmente para el problema específico y usando una diversidad de
técnicas tales como planos de corte, ramificación y acotamiento, enumeración implícita,
programación dinámica, relajación lagrangeana, entre otras, así como combinaciones de las
técnicas antes mencionadas. Desafortunadamente, no se ha podido dar soluciones eficientes.
También existe la necesidad de producir métodos de aplicabilidad general y flexible para
problemas de optimización combinatoria que obtengan soluciones en un tiempo razonable.

En el estudio de la existencia de algoritmos que permitan encontrar la solución buscada en un

tiempo polinomial y la construcción de ellos, cuando es posible, es muy importante el
conocimiento de las propiedades y estructura matemática del problema. En particular, la teoría de
gráficas permite, en muchos casos, el estudio de esta estructura y al aprovechar sus propiedades es
posible construir los algoritmos buscados, pero para otros problemas, no siempre resulta fácil
aprovechar la estructura. Hay problemas lineales, como los de flujo en redes y acoplamiento, que
pueden resolverse de manera muy eficiente; sin embargo, estos problemas están aparentemente
muy relacionados con otros problemas que se consideran “intratables”. Como ejemplo, los
problemas de trayectoria más corta en una gráfica y de acoplamiento, en donde se conocen
algoritmos O(n2) que los resuelven; en contraste con el problema del agente viajero, el cual
resuelve la trayectoria más corta para visitar el conjunto de todos los vértices de una red
exactamente una vez, que como es bien conocido, es un problema en la denominada clase NP-
Dura cuyos problemas son ampliamente considerados irresolubles por algoritmos polinomiales.
Este fino límite entre problemas “fáciles” y “difíciles” es un fenómeno recurrente en los problemas
de optimización combinatoria.

Para los problemas de optimización en la clase NP-Dura, a la fecha, no se conocen algoritmos que
los resuelvan en tiempo polinomial. Es por esto que, en las últimas décadas, se han desarrollado
algoritmos de tipo heurístico o estocástico para resolver instancias grandes de problemas que
pertenecen a esta clase. Estos algoritmos, no necesariamente encuentran la mejor solución al
problema, pero en general se pueden obtener “buenas soluciones” cuando se aplican, aquí se
entiende “buena solución” en términos de cercanía al valor óptimo. La ventaja principal de este
tipo de algoritmos es que son rápidos y corren en un tiempo polinomial.

Conceptos y Definiciones Preliminares

Podemos diferenciar básicamente dos tipos de optimización: la optimización discreta y la
optimización continua. La optimización discreta se tiene cuando el dominio S de la función
objetivo es un conjunto discreto, en cambio, se habla de optimización continua cuando el dominio
S de la función objetivo es un conjunto continuo.

La búsqueda local constituye una clase interesante de los algoritmos estocásticos y está basada en
el mejoramiento paso a paso de la función de costo al explorar las vecindades de soluciones
cercanas. El uso del algoritmo de búsqueda local presupone la definición de una solución, una
función de costo y una estructura de vecindades. A continuación, se dan algunas definiciones y
ejemplos de las mismas.
El Problema de Optimización

Definición 1.
A la función 𝑓: 𝑆 → 𝑅 donde 𝑆 ⊆ 𝑅𝑛 la denominaremos función costo/beneficio o función objetivo
y al conjunto S lo llamaremos conjunto factible o conjunto de soluciones posibles.

El problema general de optimización consiste en:

Optimizar (minimizar o maximizar) una función objetivo, y en el caso de minimización, por

ejemplo, utilizamos la notación:
min 𝑓(𝑥)
𝑥∈𝑆

Optimización Continua

Para el caso de minimización en optimización continua, el problema es encontrar 𝑥𝑜𝑝𝑡 ∈ 𝑆 que

satisfaga:
𝑓(𝑥𝑜𝑝𝑡 ) ≤ 𝑓 (𝑥 ) para toda 𝑥 ∈ 𝑆,

en el caso de maximización, la 𝑥𝑜𝑝𝑡 ∈ 𝑆 que satisfaga:

𝑓(𝑥𝑜𝑝𝑡 ) ≥ 𝑓 (𝑥 ) para toda 𝑥 ∈ 𝑆,

A la solución 𝑥𝑜𝑝𝑡 se le llama una solución globalmente óptima y

𝑓𝑜𝑝𝑡 = 𝑓(𝑥𝑜𝑝𝑡 ) denota el costo óptimo, mientras que 𝑆𝑜𝑝𝑡 denota el conjunto de soluciones
óptimas.

Ejemplo: Función de Shubert

La función de Shubert está definida por:

f(x) = cos(2x+1)+2cos(3x+2)+3cos(4x+3)+4cos(5x+4)+5cos(6x+5)

donde -10 ≤ x ≤ 10

Se muestra la función en la Figura 1 donde se aprecian tres mínimos y tres máximos globales en
el intervalo.

Definición 2.
Dado un problema de optimización continua definimos una vecindad para 𝑥 ∈ 𝑆 con radio 𝑟 ∈ 𝑅+
como:
𝐵𝑟 (𝑥) = {𝑦 ∈ 𝑆 | ‖𝑥 − 𝑦‖ < 𝑟}

donde ‖∙‖ es alguna norma definida en S

 Figura 1. Función de Shubert.

Definición 3.
Sea un problema de optimización continua y 𝑆𝑥̅ una vecindad de 𝑥̅ , entonces 𝑥̅ se llama una
solución óptima local o simplemente un óptimo local con respecto a 𝑆𝑥̅ si 𝑥̅ es mejor que o igual
a, todas sus soluciones vecinas con respecto a la función costo. Específicamente, en el caso de
minimización, 𝑥̅ se llama solución mínima local} o simplemente un mínimo local sí

𝑓 (𝑥̅ ) ≤ 𝑓(𝑦), para toda 𝑦 ∈ 𝑆𝑥̅

y en el caso de maximización, 𝑥̅ se llama una solución máxima local o simplemente un máximo

local sí

𝑓 (𝑥̅ ) ≥ 𝑓(𝑦), para toda 𝑦 ∈ 𝑆𝑥̅

Optimización Combinatoria
Definición 4.
Una instancia de un problema de optimización combinatoria puede formalizarse como una pareja
(𝑆, 𝑓), donde S denota el conjunto finito de todas las soluciones posibles y f es una función real, la
función de costo o función objetivo, mapeo definido por

𝑓: 𝑆 → 𝑅
Para el caso de minimización, el problema es encontrar 𝑖𝑜𝑝𝑡 ∈ 𝑆 que satisfaga:
 𝑓(𝑖𝑜𝑝𝑡 ) ≤ 𝑓 (𝑖 ), para toda 𝑖 ∈ 𝑆

en el caso de maximización, la 𝑖𝑜𝑝𝑡 ∈ 𝑆 que satisfaga

𝑓(𝑖𝑜𝑝𝑡 ) ≥ 𝑓 (𝑖 ), para toda 𝑖 ∈ 𝑆

A la solución 𝑖𝑜𝑝𝑡 se le llama una solución globalmente óptima y 𝑓𝑜𝑝𝑡 = 𝑓(𝑖𝑜𝑝𝑡 ) denota el costo
óptimo, mientras que 𝑆𝑜𝑝𝑡 denota el conjunto de soluciones óptimas. Un problema de optimización
combinatoria es un conjunto I de instancias.

Ejemplo: El Problema del Agente Viajero. Considere n ciudades y una matriz dpq de orden 𝑛 ×
𝑛, cuyos elementos denotan la distancia entre cada par (p, q) de ciudades. Se define un recorrido
como una trayectoria cerrada que visita cada ciudad exactamente una vez. El problema es encontrar
el recorrido con longitud mínima.

En este problema, una solución está dada por una permutación cíclica 𝜋 = (𝜋(1), 𝜋(2), … , 𝜋(𝑛)),
permutación cíclica donde 𝜋(𝑘 ) denota la ciudad a visitar después de la ciudad k, con 𝜋 𝑙 (𝑘) ≠
𝑘, 𝑙 = 1,2, … 𝑛 − 1, 𝜋 𝑛 (𝑘) = 𝑘, para toda k. Aquí 𝜋 𝑙 (𝑘) se entiende por la aplicación de l veces
la permutación 𝜋. Cada solución corresponde a un recorrido. El espacio de soluciones espacio de
soluciones está dado por:

𝑆 = todas las permutaciones 𝜋 cíclicas de las 𝑛 ciudades

y la función de costo se define por:

𝑛

𝑓 (𝜋) = ∑ 𝑑𝑖,𝜋(𝑖)
𝑖=1

es decir, 𝑓 (𝜋) da la longitud del recorrido correspondiente a 𝜋. Además, se tiene que la

cardinalidad de S es |𝑆| = (𝑛 − 1)! .

En la Definición 4 se ha distinguido entre un problema y una instancia del problema. De manera

informal, una instancia está dada por los “datos de entrada” y la información suficiente para
obtener una solución mientras que un problema es una colección de instancias del mismo tipo.

En general, un algoritmo exacto es un procedimiento paso a paso que resuelve un problema. Se

dice que un algoritmo resuelve un problema, si puede aplicarse a cualquier instancia y siempre
garantiza una solución. Para este caso un algoritmo exacto es aquel que al aplicarse a una instancia
(𝑆, 𝑓) obtiene 𝑖𝑜𝑝𝑡 ∈ 𝑆𝑖𝑜𝑡 .

Definición 5.
Sea (𝑆, 𝑓) una instancia de un problema de optimización combinatoria. Entonces una estructura
de vecindades es un mapeo:
 𝑁: 𝑆 → 2𝑆

que define para cada solución 𝑖 ∈ 𝑆 un conjunto 𝑆𝑖 ⊂ 𝑆 de soluciones que son “cercanas” a i en
algún sentido. El conjunto 𝑆𝑖 se llama vecindad de la solución i y cada 𝑗 ∈ 𝑆𝑖 se llama un vecino
de i. Además se supone que 𝑗 ∈ 𝑆𝑖 ⟺ 𝑖 ∈ 𝑆𝑗 .

En el problema del agente viajero una estructura de vecindades 𝑁𝑘 , llamada k-cambios, define
para cada solución i una vecindad 𝑆𝑖 que consiste del conjunto de soluciones que pueden obtenerse
a partir de la solución i cambiando k aristas del recorrido correspondiente a la solución i y
remplazándolos por otras k aristas de tal manera que nuevamente se obtenga un recorrido.

Si k = 2, entonces 𝑁2 es la estructura de vecindades de 2-cambios. El 2-cambios 𝑁2 (𝑝, 𝑞) puede

verse como invertir el orden en el que las ciudades p y q se visitan en el recorrido. Si el mecanismo
2-cambios 𝑁2 (𝑝, 𝑞) cambia una solución i en una solución j, entonces las permutaciones cíclicas
𝜋𝑖 y 𝜋𝑗 están relacionadas de la siguiente manera. Sea k denote el entero tal que 𝜋𝑖𝑘 (𝑝) = 𝑞, 1 <
𝑘 < 𝑛, entonces se tiene:

𝜋𝑗 (𝑝) = 𝜋𝑖−1 (𝑞 ) = 𝜋𝑖𝑘−1 (𝑝),

𝜋𝑗 (𝜋𝑖 (𝑝)) = 𝑞 = 𝜋𝑖𝑘 (𝑝),

𝜋𝑗 (𝜋𝑖𝑟 (𝑝)) = 𝜋𝑖𝑟−1 (𝑝), 𝑟 = 2, … , 𝑘 − 1,

𝜋𝑗 (𝑠) = 𝜋𝑖 (𝑠), en otro caso.

así,
𝑆𝑖 = {𝑗 ∈ 𝑆| 𝜋𝑗 se obtiene de 𝜋𝑖 por 2-cambios}
y
|𝑆𝑖 | = (𝑛 − 1)(𝑛 − 2) para toda 𝑖.

Además, cada solución j puede obtenerse a partir de cualquier solución i por n-2, 2-cambios, es
decir, para toda 𝑖, 𝑗 ∈ 𝑆 existe una sucesión 𝑙0 , 𝑙1 , … , 𝑙𝑛−2 ∈ 𝑆 tal que:

𝜋𝑖 = 𝜋𝑙0 y 𝜋𝑙𝑛−2 = 𝜋𝑗

y 𝜋𝑙𝑘+1 se obtiene desde 𝜋𝑙𝑘 , 𝑘 = 0, … , 𝑛 − 3 por un 𝑁2 (𝑝, 𝑞) cambios, donde

𝑝 = 𝜋𝑗𝑘 (1) y 𝑞 = 𝜋𝑙𝑘 ( 𝜋𝑗𝑘+1 (1)

Definición 6.
Sea (𝑆, 𝑓) una instancia de un problema de optimización combinatoria, N una estructura de
vecindades. Entonces un mecanismo de generación es un medio para seleccionar una solución j de
la vecindad 𝑆𝑖 de la solución i.

Dada una instancia de un problema de optimización combinatoria y una estructura de vecindades,

el algoritmo de búsqueda local es un algoritmo que itera sobre un número de soluciones. Comienza
con una solución inicial, que a menudo se genera aleatoriamente, después se aplica un mecanismo
de generación que continuamente trata de encontrar una mejor solución en la vecindad de la
solución actual, esto es, una solución con menor costo. Si se encuentra una solución con estas
características, la solución actual se reemplaza por esta solución. De otra manera, el algoritmo
continúa con la solución actual. El algoritmo termina cuando el mecanismo de generación no puede
encontrar una mejor solución a partir de la solución actual. El algoritmo de búsqueda local en
pseudo-código se muestra en la Figura 2.

Figura 2. Algoritmo de Búsqueda Local en pseudo-código.

Un concepto importante en el análisis de algoritmos de búsqueda local es el de optimalidad local.

Definición 7.
Sea (𝑆, 𝑓) una instancia de un problema de optimización combinatoria y N una estructura de
vecindades, entonces 𝑖̅ se llama una solución óptima local o simplemente un óptimo local con
respecto a N si 𝑖̅ es mejor que o igual a, todas sus soluciones vecinas con respecto al costo.
Específicamente, en el caso de minimización, 𝑖̅ se llama solución mínima local o simplemente un
mínimo local sí

𝑓 (𝑖̅) ≤ 𝑓(𝑗), para toda 𝑗 ∈ 𝑆𝑖̅

y en el caso de maximización, 𝑖̅ se llama una solución máxima local o simplemente un máximo

local sí

𝑓 (𝑖̅) ≥ 𝑓(𝑗), para toda 𝑗 ∈ 𝑆𝑖̅

Definición 8.
Sea (𝑆, 𝑓) una instancia de un problema de optimización combinatoria y sea N una estructura de
vecindades. Entonces N se llama exacta si para cada 𝑖̅ ∈ 𝑆 que es localmente óptimo con respecto
a N, 𝑖̅ también es globalmente óptimo.

De aquí se observa que, los algoritmos de búsqueda local terminan con un óptimo local a menos
que la estructura de vecindades sea exacta. Generalmente es difícil definir estructuras de
vecindades exactas, ya que la definición de una estructura de vecindades exacta frecuentemente
involucra hacer una búsqueda exhaustiva en todo el conjunto S.

La calidad del óptimo local obtenido por el algoritmo de búsqueda local, depende fuertemente de
la solución inicial y para muchos problemas de optimización combinatoria no se tiene una solución
inicial apropiada a la mano. Además la complejidad del problema, en el peor de los casos, no se
conoce para muchos problemas.

Entre las ventajas de usar el algoritmo de búsqueda local es que se puede aplicar de manera general
a diferentes problemas específicos de optimización combinatoria, sin alterar su estructura, ya que
únicamente se requiere de especificar la función de costo y la estructura de vecindades.

Algunas formas de relajar las desventajas del algoritmo de búsqueda local son las siguientes:

 Ejecutar el algoritmo de búsqueda local para un número grande de diferentes soluciones

iniciales. Es claro que de manera asintótica (garantizando que todas las soluciones han sido
usadas como inicial) el algoritmo encontrará el óptimo global con probabilidad uno.
 Introducir estructuras de vecindades complejas, de tal forma que se explore una parte
grande del conjunto de soluciones. A menudo encontrar una estructura de este tipo requiere
de un conocimiento experto del problema de optimización combinatoria tratado.
 Aceptar con ciertos límites las transiciones correspondientes a un incremento del valor de
la función de costo; note que en el algoritmo de búsqueda local solamente se aceptan
transiciones que correspondan a soluciones que decrementen el costo.

Heurísticas y Metaheurísticas
La palabra heurística proviene del griego heuriskein, al igual que la palabra eureka y quiere decir
encontrar.
La popularización del concepto se debe al matemático George Pólya, con su libro Cómo resolverlo
(How to solve it). El libro contiene recetas heurísticas que trataba de enseñar a sus alumnos.

En Ciencias de la Computación e Inteligencia Artificial, el término “heurístico se aplica

usualmente a métodos de búsqueda inteligente. En este sentido “búsqueda heurística” usa toda la
información disponible para dirigirse a una solución a través de trayectoria prometedoras. Aquí el
objetivo es hacer posible que el proceso de búsqueda evite examinar malas soluciones basándose
en la información contenida en los datos previamente reunidos.
En investigación de Operaciones el término heurístico se aplica a menudo a métodos (que pueden
o no involucrar búsquedas) que están basados en argumentos intuitivos o plausibles que conducen
a soluciones razonables pero que no garantizan el óptimo. Son métodos para el problema bajo
estudio, basados en reglas de sentido común, o adaptaciones de métodos exactos para modelos
simples. Son métodos usados para encontrar soluciones razonables a problemas que son difíciles
de resolver exactamente.

En optimización, en particular, un método heurístico se refiere a un método rápido y práctico

basado en estrategias que son sencillas para dirigir a una solución que es aproximadamente óptima
(pero no lo garantiza) o casi óptima. Así, un método heurístico puede encontrar una solución
óptima pero no hay ninguna seguridad de que la encuentre. Aunque un buen método heurístico, en
principio, determina la mejor solución disponible dentro del tiempo permitido. Muchos métodos
heurísticos involucran algún tipo de búsqueda para vislumbrar una buena solución aproximada.

Los métodos heurísticos son tan antiguos como la toma de decisiones. Hasta antes de la aparición
de las computadoras se utilizaban métodos heurísticos poco elegantes pero efectivos, para obtener
soluciones de problemas grandes de decisión
En las décadas de los 60's y 70's se desarrollaron algoritmos exactos basados en construcciones
matemáticas sofisticadas para ciertos tipos de problemas de optimización tales como programas
lineales, programación cuadrática convexa y problemas de programación no lineal convexa.

Las característica especial que distingue a estos problemas es que las condiciones de optimalidad
proveen caracterizaciones eficientes para las soluciones óptimas sean conocidas. Los algoritmos
exactos para estos problemas están basados en estas condiciones de optimalidad. Por estas
condiciones especiales se considera que son problemas agradables (o fáciles) entre los modelos
de optimización.

En los 80's y actualmente, se implementan paquetes de software para estos algoritmos sofisticados,
y sistemas de computación que pueden ejecutarse para amplia variedad. De modo que hoy en día
no hay razón para usar métodos heurísticos para resolver instancias de estos problemas, ya que
pueden resolverse de manera muy eficiente por estos algoritmos exactos.
Desafortunadamente las investigaciones no han dado algoritmos eficientes para obtener soluciones
exactas para problemas de optimización combinatoria que no están en esta clase agradable.

Los métodos de ramificación y acotamiento, enumeración parcial y planos de corte, pueden

resolver instancias de tamaño moderado, pero en general el tiempo requerido para estas soluciones
crece exponencialmente con el tamaño de la instancia.
Las aplicaciones de Optimización Combinatoria en el mundo real conducen a modelos de gran
escala, tales como: en la industria automotriz, diseño óptimo de muchos artículos manufacturados,
en el diseño de sistemas de telecomunicaciones y en muchas otras áreas, conducen a modelos de
optimización de gran escala.

Las investigaciones que se han llevado en complejidad computacional de algoritmos y la teoría de

la NP-completez, muestran que muchos problemas de optimización combinatoria quizá sean
problemas intratables. La alternativa para resolver este tipo de problemas es usar buenos métodos
heurísticos para encontrar buenas soluciones aproximadas. La experiencia indica que hay muchos
métodos heurísticos que son simples de implementar.

Por todas estas razones, los métodos heurísticos son métodos que deben ser seleccionados para
resolver problemas de optimización combinatoria de gran escala.

Métodos Glotones
Los métodos heurísticos en general se aplican a problemas específicos, pero tienen varios
principios ampliamente aplicables para el diseño. Uno muy popular es el principio de la
glotonería (en inglés greedy) que guía a los métodos glotones. Cada paso sucesivo en estos
métodos se toma de tal manera que minimiza el costo inmediato (o maximiza la ganancia
inmediata).

Las tres características principales de los métodos glotones son los siguientes.
• Característica incremental. Se representa al problema de tal manera que una solución
puede ser vista o como un subconjunto de un conjunto de elementos o como una sucesión
de un conjunto de elementos en algún orden.

• Característica no marcha para atrás. Una vez que un elemento se selecciona para la
inclusión en el conjunto solución (o el elemento se incluye en la sucesión en la posición
actual) nunca se regresa o se reemplaza por algún otro elemento (o su posición en la
sucesión nunca se altera). Esto es, en un algoritmo glotón, las decisiones que se hacen en
alguna etapa, nunca se revisan posteriormente.

• Característica de selección glotona. Cada elemento adicional que se selecciona para la

inclusión en el conjunto solución, o selección para ocupar la siguiente posición en la
sucesión, es la mejor entre todas aquellas que están disponibles para ser seleccionadas en
este paso por algún criterio, en el sentido que contribuya en este paso a la mínima cantidad
para el costo total, o la máxima cantidad para la ganancia total, cuando es visto a través de
este criterio.

Pueden usarse criterios diferentes para caracterizar el mejor cuando se hace la selección,
dependiendo de la naturaleza del problema a resolver. El éxito del método depende de manera
crítica de cómo se escoja este criterio.
Por lo tanto un algoritmo glotón construye la solución por pasos y en cada paso selecciona un
elemento para incluirlo en la solución que sea el mejor entre todos aquellos que sean elegibles para
incluirse.
La selección en cada etapa está basada en los valores que se tengan en ese momento. Por lo tanto
los métodos glotones se conocen como métodos miopes.

Búsqueda Local
Otra forma de diseñar métodos heurísticos se basa en comenzar con una solución completa del
problema, y tratar de mejorar por medio de una búsqueda local en una vecindad de la solución. La
solución inicial puede obtenerse de manera aleatoria o ser obtenida por algún método glotón. Cada
paso subsecuente, en este método, toma la solución del paso anterior y trata de mejorarla
intercambiando un número pequeño de elementos en la solución con aquellos que no están en la
solución o por alguna otra técnica de búsqueda local.

El proceso continua hasta que no es posible mejorar la solución, con esta búsqueda local, de tal
manera que se tiene un mínimo local. Estos métodos se conocen como métodos de búsqueda local
o intercambio heurístico o de descenso. Un óptimo local es bueno o mejor que todas las
soluciones en esta vecindad, pero puede que no sea un óptimo global, es decir, puede que no sea
la mejor solución del problema.

Por esta limitación generalmente se aplica el método de búsqueda local muchas veces, con
soluciones iniciales diferentes y al final se selecciona la mejor de entre todos los mínimos locales.
Esto se conoce como el método de búsqueda local iterado.

Limitaciones de los Métodos Heurísticos

• Ningún algoritmo heurístico garantiza convergencia a la solución óptima del problema.
• En general convergen a “buenas soluciones” pero no existe una garantía que la solución
obtenida sea de buena calidad.
• Todos los heurísticos citados en la literatura, están basados en llevar a cabo mejoras
iterativas para obtener una propuesta.

En optimización, el adjetivo heurístico, se suele usar para caracterizar a las técnicas por las cuales
se mejora en promedio la solución de cierto problema. Se utilizan algoritmos heurísticos para
obtener “buenas soluciones” (soluciones subóptimas, o cercanas a la óptima global) de problemas
cuyos algoritmos de solución no son factibles en tiempos polinomiales como, por ejemplo, el
problema del agente viajero.

En computación, es fundamental encontrar algoritmos con buenos tiempos de ejecución y que

proporcionen “buenas soluciones”, una heurística es un algoritmo que trata de satisfacer al menos
uno de estos requerimientos, si no es que ambos. Muchos algoritmos en la inteligencia artificial
son heurísticos por naturaleza o usan reglas heurísticas, como ejemplo están los algoritmos que se
verán en este curso, los cuales utilizan una amplia variedad de reglas heurísticas.

El nombre de metaheurística, combina el prefijo meta del griego (que significa “más allá”, “a un
nivel más alto”) con la palabra heurística, en otras palabras, se puede decir que metaheurística se
refiere a una estrategia de nivel superior que guía a otras heurísticas para buscar soluciones
factibles en dominios donde la tarea es compleja.

En general, las palabras heurística y metaheurística las consideraremos equivalentes cuando se

trate de algoritmos de solución para problemas de optimización combinatoria.

Problemas de Optimización
En este capítulo se proporcionan varios ejemplos de problemas clásicos que se utilizan para probar
la eficiencia, robustez y rapidez computacional de algoritmos. En la primera parte se proporcionan
problemas de optimización combinatoria que en su mayoría son del tipo NP difíciles; en la segunda
parte se presentan problemas de optimización continua, así como algunas gráficas de estos.

Ejemplos de Problemas NP
En esta sección se presentan ejemplos de problemas NP. Algunos de los cuales serán retomados
posteriormente.

Problemas P y NP
Un algoritmo es un procedimiento paso a paso para resolver un problema computacional. Para una
entrada dada, genera la salida correcta después de un número finito de pasos. La complejidad de
tiempo o tiempo de ejecución del algoritmo, expresa el número total de operaciones, como
adiciones o comparaciones, como una función del tamaño de la entrada. Se dice que un algoritmo
es polinomial o un algoritmo es de tiempo polinomial, si su tiempo de ejecución está acotado por
un polinomio con variable en el tamaño de entrada. Se dice que un algoritmo es eficiente si su
tiempo de ejecución es polinomial. Los problemas resolubles en tiempo polinomial forman la clase
P y están considerados como problemas factibles a resolver, por ejemplo, un algoritmo muy
conocido es el de ordenamiento por selección, que ordena una lista de enteros de la siguiente
manera:
 Encontrar el valor mínimo en la lista.
 Intercambiarlo con el primer elemento.
 Repetir los pasos para el resto de la lista.

Para ordenar la lista, (3 1 6 8 2), con el método de selección tenemos los siguientes pasos:

 (3 1 6 8 2),
 (1 3 6 8 2),
 (1 2 6 8 3),
 (1 2 3 8 6),
 (1 2 3 6 8).

Podemos determinar el número de comparaciones requeridos por el algoritmo de la siguiente

forma. Dada una lista con n elementos, para localizar el valor mínimo, tenemos que revisar todos
los n elementos, haciendo (n-1) comparaciones, y después intercambiándolo con la primera
posición. Luego, para encontrar el valor mínimo con el resto de la lista, se revisa los n-1 elementos
restantes, haciendo n-2 comparaciones. De esta forma, hacemos en total (n - 1) + (n - 2) + ∙∙∙ + 2
𝑛(𝑛−1)
+ 1 = 2 comparaciones.

En la Tabla 1 vemos el comportamiento aproximado de varias funciones importantes en el análisis

de algoritmos. La primera columna indica los valores de la entrada, las demás columnas tienen
valores aproximados (en algunos casos) para las funciones que vienen en la primera fila. Las filas
2-6 representan funciones usadas para complejidad polinomial, mientras las últimas dos son de
complejidad exponencial y factorial. Aunque los problemas en P con complejidad 𝑂(𝑛𝑘 ) son
considerados como “factibles” a resolver, esto también depende de la constante, la potencia k y el
tamaño de entrada n involucrados, como el lector puede apreciar de la Tabla

Tabla 1. Valores aproximados de algunas funciones.

Otra clase de problemas, como el agente viajero, son conocidos como problemas NP, donde NP
significa “polinomial no-determinista”. Para estos problemas, no se conocen algoritmos de tiempo
polinomial que los resuelvan, y generalmente se cree que tampoco existen, aunque la pregunta: ¿P
= NP? es decir, si las dos clases de problemas coinciden, es considerada como una de las más
importantes en la ciencias computacionales teóricas.

También hay una subclase importante de problemas NP conocida como NP-Completa, de los
cuales, si se puede demostrar que uno de ellos es resoluble en tiempo polinomial, entonces también
cualquier problema en NP-Completa sería resoluble en tiempo polinomial. Además la clase NP-
Completa tiene interés práctico porque contiene muchos problemas comunes, como el Problema
del Agente Viajero.

Todavía no se pueden resolver los problemas NP-completos con algoritmos eficientes, es decir, de
tiempo polinomial; sin embargo, estos problemas ocurren con frecuencia. ¿Qué podemos hacer?

En parte, depende si se quiere una solución exacta o aproximada al problema. Por ejemplo, si el
tamaño de entrada del problema no es grande, puede ser factible encontrar la solución exacta con
algún método directo. En el caso del Problema del Agente Viajero, la solución más directa es la
de intentar todas las permutaciones de las n ciudades y encontrar la más barata, dando una
complejidad de O(n!). Desafortunadamente, con menos de 100 ciudades vemos, en la Tabla 1 que
rápidamente encontramos problemas, pero puede haber otros enfoques especializados, por ejemplo
con programación dinámica, que reduce la complejidad y permite resolver exactamente para un
número mayor de ciudades; en el problema del agente viajero, se ha ido resolviendo desde 49
ciudades en 1954, al record actual de 85,900 ciudades en 2006, el último tomando 136 años de
tiempo CPU.

Otra posibilidad es utilizar un método heurístico, que no garantiza encontrar la solución exacta,
pero puede encontrar “buenas soluciones” en tiempos razonables. A continuación, se presentan
algunos ejemplos de problemas NP.
Problema de Asignación Cuadrática
Una formulación matemática de esta problemática fue inicialmente planteada por Koopmans y
Beckmann y consiste en minimizar:
𝑛 𝑛

𝑓 (𝜋) = ∑ ∑ 𝑎𝑖𝑘 𝑏𝜋(𝑖)𝜋(𝑘)

𝑖=1 𝑘=1

donde 𝜋 es una permutación del conjunto N ={1,..., n } y 𝑎𝑖𝑘 , 𝑏𝑖𝑘 para i, k = 1,...,n, son números
reales. Equivalentemente, se desea encontrar una permutación 𝜋 del conjunto N que minimice el
valor de 𝑓 (𝜋).

Una forma sencilla de interpretar el problema planteado es suponer que existen n sitios disponibles
y se van a construir n edificios en estos lugares. Sea 𝑎𝑖𝑘 la distancia entre el sitio i y el sitio k y
suponga que las cantidades 𝑏𝑗𝑙 denoten el número de personas por semana que viajarán entre el
edificio j y l. El problema es asignar los sitios de construcción de manera que la distancia recorrida
se minimice. Cada asignación puede describirse matemáticamente como una permutación π del
conjunto N ={1,..., n }, mientras que el producto 𝑎𝑖𝑘 𝑏𝜋(𝑖)𝜋(𝑘) describe la distancia semanal
recorrida por la gente que viaja entre los edificios j = 𝜋(𝑖) y l = 𝜋(𝑘) si la construcción j se realiza
en el sitio i y la construcción l se realiza en el sitio k.

Considere un ejemplo numérico donde se desea localizar cuatro edificios A, B, C y D en cuatro

sitios a, b, c, d. Suponga que las distancias (en metros) entre los cuatro edificios están dadas por
la matriz de distancias (𝑎𝑖𝑘 ):

0 340 320 400

340 0 360 200
𝑎𝑖𝑘 =[ ]
320 360 0 180
400 200 180 0

El edificio A es la biblioteca, el edificio B son aulas y cubículos, el edificio C son oficinas

administrativas y el edificio D son dormitorios. Las “conexiones” entre estos edificios se describen
por medio de la matriz de conexión (𝑏𝑗𝑙 ), donde (𝑏𝑗𝑙 ) es una medida para el número de personas
y la frecuencia con la que viajan del edificio j al edificio l:

0 80 40 30
80 0 30 20
𝑏𝑗𝑙 = [ ]
40 30 0 10
30 20 10 0

Observe que si se construye el edificio A en el sitio a, el edificio B en el sitio b, el edificio C en

el sitio c y el edificio D en el sitio d, entonces se obtendría el siguiente valor de la función objetivo:
 𝑛 𝑛

𝑧 = ∑ ∑ 𝑎𝑖𝑘 𝑏𝑖𝑘 = 137,200

𝑖=1 𝑘=1

que corresponde a la permutación π(i)=i para i=1,2,3,4. Por otro lado, suponga que A se construye
en el sitio d, B en b, C en c y D en a, se tiene la permutación π(1)=4, π(2)=2, π(3)=3, π(4)=1 y el
valor de la función objetivo es ahora.
𝑛 𝑛

𝑧 = ∑ ∑ 𝑎𝑖𝑘 𝑏𝜋(𝑖)𝜋(𝑘) = 112,000

𝑖=1 𝑘=1

Otra interpretación del problema planteado consiste en suponer que n módulos se han colocado en
un tablero y se han conectado por medio de “alambres”. Los módulos deben colocarse de manera
que la longitud total del alambre que los conecta sea mínima.

Denote la distancia entre las posiciones i y k en el tablero por 𝑎𝑖𝑘 . Sea 𝑏𝑗𝑙 el número de conexiones
entre el módulo j y el módulo l. Entonces, una permutación π del conjunto N ={1,..., n } asigna
una posición en el tablero a todo módulo. Si j se sitúa en la posición i y l está situado en la posición
k, el producto 𝑎𝑖𝑘 𝑏𝜋(𝑖)𝜋(𝑘) es la longitud del alambre entre los módulos j=π(i) y l=π(k). Por lo tanto
la longitud total del alambrado es:
𝑛 𝑛

∑ ∑ 𝑎𝑖𝑘 𝑏𝜋(𝑖)𝜋(𝑘)
𝑖=1 𝑘=1

y el problema se reduce a:
𝑛 𝑛

min 𝑧 = ∑ ∑ 𝑎𝑖𝑘 𝑏𝜋(𝑖)𝜋(𝑘)

𝜋
𝑖=1 𝑘=1

El problema anterior, se conoce comúnmente en la literatura como el Problema de Asignación

Cuadrática (por sus siglas en inglés, QAP). Una formulación similar del QAP es aplicable para el
diseño de paneles de control y teclados de máquinas. Existen muchas otras aplicaciones del QAP
por ejemplo:
 Problemas de ubicación de edificios, planeación de hospitales.
 En deportes, se aplica en problemas de calendarización.
 En sistemas de información, un orden óptimo para interrelacionar datos en una cinta
magnética.
 En química, para analizar reacciones químicas para componentes orgánicas.
 En balancear turbinas para autos de carreras.
 En arqueología, modelos para ordenar datos arqueológicos.
Problema de Conjunto Independiente
Considere una gráfica G = (V, E) no dirigida, donde V es el conjunto de vértices y E es el conjunto
de aristas. Un subconjunto I de V se dice que es un conjunto independiente de vértices, también
conocido como conjunto estable, de G si no existen dos vértices en I que sean adyacentes; es decir,
no existen dos vértices que estén ligados por una arista. Para la Figura 3, por ejemplo, los conjuntos
de vértices {1,5,7}, {2,6}, {2,4,6}, son conjuntos independientes.

Un conjunto independiente se llama maximal si no existe otro conjunto que sea independiente en
el que esté contenido propiamente. Esto es, un conjunto independiente I es maximal si para todo
conjunto H tal que 𝐼 ⊂ 𝐻 con 𝐼 ⊂≠ 𝐻, se tiene que H no es independiente. Por ejemplo, para la
Figura 3, los conjuntos {1,5,7}, {2,4,6}, {3,6} y {1,8}, son conjuntos independientes maximales
y los conjuntos {1}, {2,6}, {1,5} no son maximales.

En general, existe más de un conjunto independiente maximal para una gráfica dada. También,
como se vio en los ejemplos anteriores, el número de vértices en los conjuntos independientes
maximales no es necesariamente el mismo.

Figura 3. Gráfica con 8 vértices y 14 aristas.

Si Q es la familia de conjuntos independientes asociados a una gráfica G, entonces el número:

𝛼|𝐺 | = max|𝐼 |
𝐼∈𝑄

se llama el número independiente o de estabilidad de una gráfica G}, y el conjunto I* para el que
se obtiene este número se llama un conjunto independiente máximo. El Problema de Conjunto
Independiente consiste en encontrar dentro de todos los conjuntos independientes I en Q, un
conjunto independiente I* cuya cardinalidad sea máxima; es decir, que tenga el número máximo
de elementos. En la Figura 3, la familia de conjuntos maximales está compuesta por:

{{1,5,7}, {1,6}, {1,8}, {2,4,6}, {2,4,8}, {,5}, {3,6}, {3,8}, {4,5}}

el más grande de estos conjuntos tiene 3 elementos y por lo tanto 𝛼 |𝐺 | = 3. Cualquier conjunto
de la familia maximal con 3 elementos es un conjunto independiente máximo, por lo tanto, los
conjuntos independientes máximos para la gráfica de la Figura 3 son: {1,5,7}, {2,4,6} y {2,4,8}.

Problema de Coloración Mínima.

Considere una gráfica G = (V, E) no dirigida, donde V es el conjunto de vértices y E es el conjunto
de aristas. Se define una coloración de G como una aplicación 𝐶: 𝑉 → {1,2, … , 𝑛}

que identifica a C(i) como el color del vértice i, de forma tal que dos vértices adyacentes no tengan
el mismo color, es decir, {i, j} ∈ E ⇒ C (i) ≠ C (j).

Una coloración de una gráfica G con k colores define una partición del conjunto de vértices en
subconjuntos V1, V2,…, Vk, donde Vj denota los vértices que tienen asignado el color j. Claramente,
cada Vj es un conjunto independiente, al cual se le llama clase de color j o clase cromática j. Se
dice que una k-coloración de G es una coloración que no utiliza más de k colores, y una gráfica es
k-coloreable si admite una k-coloración. Al mínimo valor k tal que G es k-coloreable se le llama
número cromático de la gráfica y se denota por 𝜒(𝐺).

En una gráfica G, el Problema de Coloración Mínima busca una coloración de G que no utilice
más de 𝜒(𝐺) colores.

Por ejemplo la Figura 3 es k-coloreable para k = 3,4,5,… si seleccionamos k = 3 se puede colorear

los vértices 1, 5 y 7 con el color 1, los vértices 2, 4 y 6 con el color 2 y los vértices 3 y 8 con el
color 3. Es decir, V1 = {1, 5, 7}, V2 = {2, 4, 6} y V3 = {3, 8}. También se puede observar que 𝜒(𝐺)
= 3, ya que para colorear, por ejemplo, los vértices 1, 2 y 3 se requieren colores distintos.

Problema de Empaquetamiento
El Problema de Empaquetamiento (Bin Packing Problem) consiste en acomodar el mayor número
de objetos (cada uno con determinado peso o valor) en el menor número de contenedores (cajas,
huecos, camiones, etc.). En el problema de empaquetamiento se tienen n objetos a1, a2,…, an, los
cuales tienen un peso w(ai) ∈ (0,1] que serán empaquetados en un número mínimo de contenedores
B1, B2,…, Bm tal que

∑ 𝑤(𝑎𝑖 ) ≤ 1, 1 ≤ 𝑗 ≤ 𝑚
𝑎𝑖 ∈𝐵𝑗
 Por ejemplo, si se tienen 5 objetos a1, a2, a3, a4, a5 con pesos w(a1)=0.8, w(a2)=0.6, w(a3)=0.5,
w(a4)=0.2, w(a5)=0.3. Para este ejemplo, el mínimo número de contenedores que se requieren es 3
y una posible solución es: B1 = {a1}, B2 = {a2 , a5}, B3 = {a3, a4}.

Problema de Cubrimiento de Vértices

Dada una gráfica no dirigida G = (V, E}), donde V es el conjunto de vértices y E es el conjunto de
aristas, un cubrimiento por vértices es un conjunto C de vértices tal que cada arista de G tiene al
menos uno de sus vértices adyacentes en C. El Problema de Cubrimiento de Vértices (The Vertex
Cover Problem) consiste en encontrar un cubrimiento por vértices más pequeño.

Por ejemplo, para la Figura 3, un cubrimiento por vértices está dado por los conjuntos: C1 = {1, 2,
3, 6, 7, 8}, C2 = {1, 3, 5, 6, 7}, C3 = {2, 3, 4, 6, 8}, C4 = {1, 2, 3, 4, 5, 6, 7, 8}. Los conjuntos C2
y C3 son dos posibles soluciones al problema. No existe ningún cubrimiento que tenga 4 o menos
elementos.

Problema de Clan Máximo.

Considere una gráfica G = (V, E) no dirigida, donde V es el conjunto de vértices y E es el conjunto
de aristas. Un subconjunto 𝑆 ⊂ 𝑉 se dice que es un clan si para cada par de vértices v1 , v2 en S
con v1 ≠ v2 existe la arista (v1 , v2) en E. El Problema de Clan Máximo} (Maximum Clique) consiste
en encontrar un subconjunto S de vértices tal que para cada par de vértices en S existe una arista
en G y tal que |𝑆| sea máximo.

En la Figura 3, los conjuntos S1 = {1, 2, 3}, S2 = { 5, 6, 8} y S3 = {6, 8} son clanes de tamaño 3, 3

y 2 respectivamente. Los conjuntos S1 y S2 son dos posibles soluciones al problema. No existe
ningún clan de cardinalidad mayor.

Problema de Corte Máximo.

Considere una gráfica G = (V, E) no dirigida, donde V es el conjunto de vértices y E es el conjunto
de aristas. El Problema de Corte Máximo (Maximum Cut) se refiere a encontrar un subconjunto
𝐶 ⊂ 𝑉 que maximiza el número de aristas que tienen un vértice en C y el otro fuera de C.

En la Figura 3, el conjunto C1 = {3,5,6,8} hace que el conjunto de aristas A1 = {(1,3), (2,5), (2,3),
(3,4), (3,7), (6,7), (7,8)}. Tengan un vértice en C1 y el otro fuera de C1.

Problema de Satisfacibilidad
Una variable booleana x es una variable que toma solamente valores de cierto o falso. Las variables
booleanas pueden combinarse usando los conectores lógicos “o” (denotado aquí por +), “y”
(denotado como multiplicación), y “no” (denotado por ⌐) para formar una expresión booleana, se
hace lo mismo que con variables reales, se combinan con operaciones algebraicas. Por ejemplo,

¬𝑥3 ∙ (𝑥1 + ¬𝑥2 + 𝑥3 )

es una fórmula booleana. Dados los valores de cierto o falso para cada variable, se puede evaluar
la fórmula booleana, justo como una expresión algebraica. Por ejemplo, para la fórmula booleana
anterior tomando x1 = cierto, x2 = cierto, y x3 = falso, la expresión da el valor cierto.

La fórmula anterior puede hacerse cierta para algunas asignaciones. Tal fórmula booleana se dice
que es satisfacible. No todas las fórmulas son satisfacibles; hay algunas que no se pueden hacer
ciertas para ninguna asignación, esencialmente porque tienen alguna “contradicción”. Por ejemplo,
considere

(𝑥1 + 𝑥2 + 𝑥3 ) ∙ (𝑥1 + ¬𝑥2 ) ∙ (𝑥2 + ¬𝑥3 ) ∙ (¬𝑥1 + 𝑥3 ) ∙ (¬𝑥1 + ¬𝑥2 + ¬𝑥3 )

Para que la fórmula anterior sea cierta, todas las subfórmulas dentro de paréntesis (llamadas
cláusulas) que contienen literales (esto es, variables o negaciones) deben ser ciertas. La primera
cláusula dice que al menos una de las variables debe ser cierta. Las siguientes tres cláusulas forzan
a todas las variables a tener el mismo valor y como al menos una debe ser cierta (de la primera
cláusula), entonces todas deben ser ciertas. A pesar de esto, la última cláusula requiere que no
todas sean ciertas, y así la fórmula contiene una contradicción, por lo tanto es no satisfacible. El
problema de satisfacibilidad se puede enunciar como:

Dadas m cláusulas C1,..., Cm que contienen las variables x1,..., xn, ¿Es la fórmula 𝐶1 ∙ 𝐶2 ⋯ 𝐶𝑚
satisfacible?

Problema de la Mochila
Dado un conjunto U = { a1, a2,…, an}, de n elementos con pesos pi, i=1,2,…, n y un parámetro B
> 0. El objetivo es encontrar un subconjunto U' ⊂ U tal que

∑ 𝑝𝑗 ≤ 𝐵
𝑗∈𝑈 ′

sea máxima. A este problema se le llama el Problema de la Mochila (Knapsack Problem).

Cuadrados Mágicos.
Dada una matriz de 4x4 como:
 16 3 2 13
5 10 11 8
[ ]
9 6 7 12
4 15 14 1

Esta matriz no es un arreglo al azar. Todos los enteros del 1 al 16 se usan, la suma de cada renglón,
columna y las dos diagonales son iguales a 34. Este tipo de matrices se conocen como cuadrados
mágicos. Hay cuadrados mágicos de cualquier tamaño, excepto de 2x2. Claramente la suma común
de los renglones columnas y diagonales está en función de n. Para n = 3, la suma es 15.

Para valores de n = 3, 4 y 5 aquí hay unos cuadrados mágicos:

17 24 1 8 15
16 3 2 13
8 1 6 23 5 7 14 16
5 10 11 8
[3 5 7] [ ] 4 6 13 20 22
9 6 7 12
4 9 2 10 12 19 21 3
4 15 14 1 [11 18 25 2 9]

Así, el problema de Cuadrados Mágicos (Magic Squares) es a partir de un valor entero n > 2 se
debe construir una matriz cuadrada de n x n con entradas del 1 al n x n tal que la suma de cada
renglón, columna y las dos diagonales son iguales a una constante que depende del valor n.

El Problema del Sudoku

El Sudoku es un pasatiempo muy popular a nivel mundial. El nombre, Sudoku, viene de japones
donde “Su” significa número y “Doku” significa individualmente.

En el caso general, el objetivo del Sudoku es llenar una cuadrícula de n2 x n2 celdas, dividida en
n2 subcuadrículas de n x n en donde se deben colocar los enteros del 1 a n2 de acuerdo a los
siguientes tres reglas:

1. Las celdas de cada uno de los renglones deben contener los enteros de 1 a n2 exactamente
una vez.
2. Las celdas de cada una de las columnas deben contener los enteros de 1 a n2 exactamente
una vez.
3. Cada una de las subcuadrículas deben contener los enteros de 1 a n2 exactamente una vez.

Al entero n se le denomina el orden del Sudoku.

En la Figura 4 se da un ejemplo de un Sudoku de orden 3, donde se puede observar que existen

algunas celdas prellenadas con los enteros del 1 al 32 y el jugador debe completar la cuadrícula
siguiendo las tres reglas descritas anteriormente. En la Figura 5 se presenta una solución válida de
la Figura 4.
En 2002, Yato mostró que el Sudoku es un problema NP-Completo. La prueba usa una reducción
simple para el problema de cuadrados latinos, el cual ha sido probado que es NP-Completo.

Figura 4. Sudoku.

Figura 5. Solución válida al Sudoku de la Figura 4

Problemas Continuos
Para la comparación de diferentes algoritmos diseñados para resolver problemas de optimización
continua, a lo largo de los años se ha propuesto una colección de funciones de prueba. Las
funciones están escogidas para reflejar diferentes facetas que podrían resultar difíciles para un
algoritmo. Estas propiedades de una función son: unimodalidad, multimodalidad,
dimensionalidad, continuidad, diferenciabilidad, convexidad, el número de óptimos locales y su
distribución, el número de óptimos globales y su distribución.

A continuación, definimos algunas de las funciones que se han utilizadas (Molga, Michalewicz),
formulando todos los problemas para minimización.

La función de Ackley
La función de Ackley es una función multimodal. Está definida por:

𝑥𝑖2
−0.2√∑𝑁
𝑖=1 𝑁 𝑁
(𝑓(𝑥1 , 𝑥2 , . . . , 𝑥𝑛 ) = −20 𝑒 − 𝑒 (∑𝑖=1 cos 2𝜋𝑥𝑖 )/𝑁 + 20 + 𝑒1

-32.768 ≤ xi ≤ 32.768, i = 1, 2, …, N.

Tiene un mínimo global de 𝑓 (𝑥1 , … , 𝑥𝑁 ) = 0 en xi =0, i=1,2,…, N.

Figura 6. La función de Ackley en dos dimensiones.

La función RCOS de Branin
La función rcos de Branin tiene un mínimo global en tres diferentes puntos. Está definida por:

𝑓 (𝑥, 𝑦) = 𝑎(𝑦 − 𝑏𝑥 2 + 𝑐𝑥 − 𝑑)2 + 𝑒(1 − 𝑓) cos 𝑥 + 𝑒,

-5 ≤ x ≤10, 0 ≤ y ≤ 15

donde usualmente se toma:

a = 1, b = 5.1/(4π2), c = 5/π, d = 6, e = 10, f = 1/(8/π).

Tiene el mínimo global de f(x,y) = 0.397887 en los puntos:

x = -π, y = 12.275,
en x = π, y = 2.275,
y en x = 9.42478, y = 2.475.

Figura 7. La función rcos de Branin.

La función de Easom
La función de Easom es una función unimodal, donde el mínimo global se encuentra en una área
pequeña comparado con el resto del dominio.

2 − (𝑦−𝜋)2
𝑓 (𝑥, 𝑦) = −cos(𝑥 )cos(𝑦)exp−(𝑥−𝜋)
-100 ≤ x,y ≤ 100.

Tiene un mínimo global de f(x,y) = -1 en x = y = π

Figura 8. La función Easom.