Nuevas Heurısticas Inspiradas En La Naturaleza Para Optimizacion Numerica

Cap´tulo 8 ı

Nuevas Heur´sticas Inspiradas en la Naturaleza ı para Optimizaci´ n Num´ rica o e
E. Mezura-Montes, O. Cetina-Dom´nguez y B. Hern´ ndez-Oca˜ a ı a n

Resumen En este cap´tulo se presenta una introducci´ n a las heur´sticas inspiradas ı o ı en fen´ menos de forrajeo. Se presenta un panorama general de este tipo de proo puestas para resolver problemas de optimizaci´ n yposteriormente se introducen o sus elementos principales. Despu´ s de ello, dos algoritmos bio-inspirados son dee tallados: La Colonia Artificial de Abejas (ABC) y la versi´ n mejorada de la Optio mizaci´ n Mediante el Forrajeo de Bacterias (MBFOA). Se explica la forma en que o ambos algoritmos representan las soluciones de un problema, la manera de escoger las mejores soluciones para guiar a las dem´ s enel proceso de b´ squeda, los opea u radores que permiten generar nuevas soluciones a partir de las ya existentes y los mecanismos de eliminaci´ n para mantener aquellas soluciones m´ s competitivas. El o a uso de ejemplos num´ ricos sencillos apoyan el entendimiento de ambos algoritmos e que, en esencia, son muy simples de implementar y usar.

8.1. Introducci´ n o
Dentro del quehacer humano seencuentra la resoluci´ n de problem´ ticas como a plejas. Entre ellas, se encuentran los problemas de optimizaci´ n, que consisten en o buscar, en un conjunto de soluciones posibles para el problema en cuesti´ n, aquella o

E. Mezura-Montes, O. Cetina-Dom´nguez ı Laboratorio Nacional de Inform´ tica Avanzada (LANIA A.C.) a R´ bsamen 80, Centro, Xalapa, Veracruz, 91000 MEXICO e e-mail:emezura@lania.mx, omarcetina@hotmail.com B. Hern´ ndez-Oca˜ a a n Universidad Ju´ rez Aut´ noma de Tabasco a o Divisi´ n Acad´ mica de Inform´ tica y Sistemas o e a Km. 1 Carr. Cunduac´ n-Jalpa de M´ ndez a e e-mail: betania h o@hotmail.com

255

256

E. Mezura-Montes et al.

que satisfaga de mejor manera una serie de condiciones planteadas. Los problemas de optimizaci´ n pueden clasificarse en dostipos: o 1. Problemas de optimizaci´ n num´ rica: Se busca un conjunto de valores para o e las variables del problema de manera que al sustituirse en la funci´ n objetivo o se maximice o minimice el valor de esta funci´ n. Un ejemplo de este problema o ´ puede ser el dise˜ o de una pieza mec´ nica donde se buscan valores optimos de n a sus dimensiones para minimizar su costo de fabricaci´ n. o 2.Problemas de optimizaci´ n combinatoria: Se busca encontrar el ordenamiento o de un conjunto de elementos de manera que se maximice o minimice el valor de la funci´ n objetivo. Un ejemplo de este tipo de problemas es el del agente o viajero, que debe recorrer un conjunto de ciudades, pasando por ellas s´ lo una o vez, de manera que regrese a su punto de salida y se minimice el costo del viaje. ´Aqu´ se desea encontrar el orden optimo de recorrido de las ciudades. ı Este cap´tulo se centra en el primer tipo de problemas, conocido como el proı blema general de programaci´ n no lineal, que se define, sin p´ rdida de generalidad, o e como: Encontrar x que minimiza f (x) (8.1) sujeta a: gi (x) ≤ 0, i = 1, . . . , m h j (x) = 0, j = 1, . . . , p
n

(8.2) (8.3) ]T

donde x ∈ I es un vectorde n variables de decisi´ n x = [x1 , x2 , . . . , xn y cada R o xi , i = 1, ..., n est´ acotado por l´mites inferiores y superiores Li ≤ xi ≤ Ui , los a ı cuales definen el espacio de b´ squeda S , F es el conjunto de todas las soluciones u que satisfacen las restricciones del problema y se le llama zona factible, siendo claro que F ∈ S , m es el n´ mero de restricciones de desigualdad y p es el n´mero de u u restricciones de igualdad. Las restricciones y la funci´ n objetivo pueden ser lineales o y no lineales. En este problema se pretende encontrar una soluci´ n que minimice una cierta o medida de calidad, conocida como funci´ n objetivo (8.1) que adem´ s debe satiso a facer un conjunto de restricciones asociadas al problema (8.2)-(8.3). Detallando el ejemplo propuesto anteriormente...