hgghgh

Por ejemplo, el procedimiento de búsqueda de gradiente descrito en la sección 12.5 es un procedimiento
de mejora local. Si éste comienza, por ejemplo, con x 5 0 como la solución de prueba
inicial en la fi gura 13.1, ascendería por la pendiente al probar en forma exitosa valores más grandes
de x hasta que, en esencia, llegara a la cumbre de la montaña en x 5 5, punto en el que se detendría.
Enla fi gura 13.2 se muestra una secuencia típica de valores de f (x) que se obtendría mediante este
procedimiento de mejora local cuando se inicia desde la parte baja de la gráfi ca.
Como el ejemplo de programación no lineal que se muestra en la fi gura 13.1 involucra sólo
una variable, el método de bisección que se describió en la sección 12.4 también se podría aplicar
a este problemaparticular. Éste es otro ejemplo de un procedimiento de mejora local, puesto que
cada iteración comienza en la solución de prueba actual a buscar una mejor solución en su vecindad
(que se defi ne por las cotas inferior y superior actuales sobre el valor de la variable). Por ejemplo,
si la búsqueda comenzara con una cota inferior de x 5 0 y una cota superior de x 5 6 en la fi gura
13.1, la secuenciade soluciones de prueba que se obtendría por el método de bisección sería x 5 3,
x 5 4.5, x 5 5.25, x 5 4.875, hasta convergir a x 5 5. Los valores correspondientes de la función
objetivo de estas cuatro soluciones de prueba son 2.975 millones, 3.286 millones, 3.300 millones
y 3.302 millones, respectivamente. Por consiguiente, la segunda iteración proporciona una mejora
más o menos grande sobrela primera (311 000), la tercera iteración da una mejora mucho más pequeña
(14 000), mientras que la cuarta sólo ofrece una mejora marginal (2 000). Como se muestra
en la fi gura 13.2, este patrón es bastante típico de los procedimientos de mejora local (aunque con
alguna variación en la tasa de convergencia al máximo local).
Igual que en el procedimiento de búsqueda de gradiente, estabúsqueda con el método de
bisección se quedaría atrapada en el óptimo local de x 5 5, por lo que nunca encontraría el óptimo
global en x 5 20. Como otros procedimientos de mejora local, tanto el de búsqueda de gradiente
como el método de bisección fueron diseñados sólo para obtener una mejoría sobre la solución de
prueba actual dentro de su vecindad local. Una vez que éstos ascienden hasta el pico dela montaña,
se deben detener porque ya no pueden ascender más dentro de la vecindad local de la solución
de prueba en la cumbre. Este inconveniente ilustra la desventaja de cualquier procedimiento de
mejora local.
Desventaja de un procedimiento de mejora local: Cuando se aplica un procedimiento
de mejora local bien diseñado a un problema de optimización con múltiples óptimos
locales, elprocedimiento convergirá hacia un óptimo local y se detendrá. El óptimo local
que encuentre dependerá del punto en el que el procedimiento inicia su búsqueda. Por
lo tanto, el procedimiento encontrará el óptimo global sólo si inicia la búsqueda en la
vecindad de dicho óptimo global.
Para tratar de evitar esta desventaja se puede reiniciar el procedimiento de mejora local cierto
número de veces apartir de soluciones de prueba aleatorias. Con frecuencia, cuando se reinicia
desde una parte nueva de la región factible se llega a un nuevo óptimo local. Si se repite esta rutina
cierta cantidad de veces se incrementa la posibilidad de que el mejor óptimo local que se obtuvo
en realidad sea el óptimo global. Este enfoque funciona bien con problemas pequeños, como el
FIGURA 13.2
Secuenciatípica de valores
de la función objetivo de
las soluciones obtenidas
por un procedimiento de
mejora local, cuando éste
converge hacia un óptimo
local durante su aplicación
a un problema de maximización.
f(x)
1 2 3 4 Iteración
Una mejora
grande
Una mejora
más pequeña
Una mejora
muy pequeña
13.1 NATURALEZA DE LA METAHEURÍSTICA 565
566 CAPÍTULO 13 METAHEURÍSTICA
problema de...