Optimización De Un Mecanismo De Cuatro Barras Usando El

Transcript

“OPTIMIZACIÓN DE UN MECANISMO DE CUATRO BARRAS USANDO EL ALGORITMO DE OPTIMIZACIÓN BASADO EN TORMENTA DE IDEAS “ TESIS Que presenta: Miriam Fernández Jiménez Para obtener el grado de: Maestra en Redes y Sistemas Integrados Director de Tesis: Dr. Efrén Mezura Montes Co-Director de Tesis: Dr. Edgar Alfredo Portilla Flores Xalapa, Veracruz, México Diciembre, 2014 Página 1 Página 2 Dedicatoria A mi hermanito: para que te sirva de motivación y en un tiempo sea yo quien este leyendo tu tesis. Página 3 Agradecimientos A mi madre, por ser un ejemplo de perseverancia y trabajo, eres una excelente amiga y mi guerrera favorita, gracias por tu apoyo y creer siempre en mí. A mi asesor el Dr. Efrén Mezura Montes por brindarme la oportunidad de trabajar con él, por su dirección tan acertada y sobre todo por el tiempo invertido en esta tesis. Al Dr. Edgar Alfredo Portilla Flores por salvarme de las dudas surgidas en el camino, por compartir sus conocimientos y avances en el tema. A la Dra. Cora Beatriz Excelente Toledo por llenarme de ánimo y aportarme una perspectiva adecuada para concluir este trabajo en tiempo y forma, gracias por sus comentarios siempre oportunos. Página 4 ÍNDICE RESUMEN ............................................................................................... 7 Índice de Figuras ................................................................................... 8 Índice de Tablas ..................................................................................... 9 1. Introducción ......................................................................... 10 1.1 Descripción del problema ............................................................. 11 1.2 Hipótesis ......................................................................................... 12 1.3 Objetivo General ............................................................................ 12 1.4 Estructura del documento ............................................................ 13 2. Optimización ........................................................................ 14 2.1 Concepto de Optimización ........................................................ 14 2.3 Técnicas Metaheurísticas .......................................................... 16 2.4 Algoritmos de Optimización y una Clasificación .................... 19 2.4.1 Basados en Inteligencia Colectiva (o de enjambre) ............. 20 2.4.2 Basados en Física y Química ................................................. 21 2.4.3 Otros algoritmos: .................................................................... 21 2.4.4 Algoritmos Evolutivos ............................................................ 22 3. Mecanismos de cuatro Barras ............................................ 24 4. Algoritmo Brain Storm Optimization (BSO) ....................... 30 4.1 Proceso de Lluvia de ideas ....................................................... 30 4.2 Algoritmo Brain Storm Optimization ........................................ 33 4.2.1 Inicialización de la población ................................................. 35 Página 5 4.2.2 Clustering ................................................................................. 35 4.2.3 Alteración de centroides ......................................................... 36 4.2.4 Actualización de Individuos ................................................... 36 5. Metodología y Diseño de Experimentos............................. 40 5.1 Valores Iniciales ......................................................................... 41 5.2 Procedimiento Realizado ........................................................... 42 6. Resultados y Discusión ....................................................... 46 6.1 Resultados .................................................................................. 47 6.2 Discusión..................................................................................... 51 6.3 Comparativa ................................................................................ 53 7. Conclusiones y Trabajo Futuro........................................... 55 Referencias ................................................................................... 56 Página 6 RESUMEN En este trabajo se presenta la optimización de un mecanismo de cuatro barras de tipo Manivela-Biela-Balancín que cuenta con un motor de corriente directa como elemento impulsor del sistema. Para realizar el proceso de optimización se utiliza el algoritmo llamado “Brain Storming Optimization” (BSO), que resuelve problemas de optimización basándose en una técnica grupal del ser humano para resolver problemas llamada lluvia de ideas. Los resultados obtenidos se comparan contra los encontrados por un algoritmo del estado del arte en diseño mecatrónico basado en evolución diferencial. El desempeño del algoritmo BSO muestra ser altamente competitivo con respecto al del algoritmo basado en evolución diferencial, lo que muestra la viabilidad de éste para resolver problemas complejos de diseño en ingeniería. Página 7 ÍNDICE DE FIGURAS Figura 2.1 Diagrama de flujo del comportamiento de un algoritmo evolutivo. .. 23 Figura 3.1 Modelo esquemático de un mecanismo de MBB. ........................... 25 Figura 3.2 Modelo esquemático de un motor de C.D. ...................................... 26 Figura 4.1 Diagrama de flujo del algoritmo BSO. ............................................. 34 Figura 5.1 Datos agrupados alrededor de tres centroides. .............................. 44 Página 8 ÍNDICE DE TABLAS Tabla 4.1 Pasos en el proceso “Brainstorming” ................................................ 31 Tabla 4.2 Reglas de Osborn para la generación de ideas en el proceso Brainstorming .................................................................................................... 32 Tabla 4.3 Pasos del algoritmo BSO. ................................................................. 39 Tabla 5.1 Conjunto de parámetros iniciales para el algoritmo BSO. ................. 41 Tabla 5.2 Ejemplo de una población inicial (conjunto de ideas). ...................... 43 Tabla 6.1 Conjunto de parámetros con los que se obtuvieron mejores resultados. ........................................................................................................ 47 Tabla 6.2 Conjunto de resultados obtenidos en el primer problema de optimización (maximización). Todas las soluciones son factibles. El mejor resultado obtenido se encuentra en color rojo. ................................................. 48 Tabla 6.3 Datos estadísticos obtenidos del conjunto de resultados de la Tabla 6.2 para el primer problema de optimización (maximización). .......................... 49 Tabla 6.4 Conjunto de resultados obtenidos en el segundo problema de optimización (minimización). Todas las soluciones son factibles. El mejor resultado obtenido se encuentra en color rojo. ................................................. 50 Tabla 6.5 Datos estadísticos obtenidos del conjunto de resultados de la Tabla 6.4 para el segundo problema de optimización (minimización). ....................... 51 Tabla 6.6 Valores Obtenidos con Evolución Diferencial para el problema de maximización. ................................................................................................... 53 Tabla 6.7 Valores Obtenidos con BSO para el problema de maximización. .... 54 Tabla 6.8 Valores Obtenidos con Evolución Diferencial para el problema de minimización. .................................................................................................... 54 Tabla 6.9 Valores Obtenidos con BSO para el problema de minimización. ...... 54 Página 9 1. Introducción En la vida cotidiana el ser humano siempre está buscando soluciones más eficaces y rápidas para resolver sus problemas. La idea de hacer más con menos siempre ha despertado un gran interés. Sin embargo, existen problemas de la vida real donde los métodos exactos no son viables, por lo que los métodos aproximados suelen ser una alternativa válida para solucionarlos. La finalidad de este trabajo es aplicar un algoritmo aproximado, basado en una de las formas que los humanos resuelven problemas, en la resolución de un problema mecatrónico de la vida real. En este capítulo se describe el problema, se presenta una hipótesis así como el objetivo a cumplir. Los problemas de optimización son comunes en el quehacer humano. Existen técnicas matemáticas para resolverlos [1]. Sin embargo, existen instancias, particularmente del mundo real, donde dichas técnicas no pueden ser aplicadas, su empleo es complicado, o los resultados obtenidos no son satisfactorios. De ahí que existan técnicas alternativas llamadas heurísticas que, aunque no pueden garantizar encontrar la mejor solución existente, proveen de soluciones altamente competitivas en un tiempo razonable [2]. Entre las opciones más conocidas de este tipo de técnicas se tienen a los algoritmos evolutivos [3] y a la inteligencia colectiva [4]. Los primeros basan su funcionamiento en emular la evolución natural y la supervivencia del más apto para evolucionar soluciones de problemas de optimización y los segundos resuelven la misma tarea pero emulando comportamientos sociales y cooperativos de organismos simples como insectos. Actualmente han surgido nuevas técnicas con inspiraciones diversas. Los seres humanos son los animales más inteligentes del mundo, por lo tanto un algoritmo de optimización basado en el comportamiento del ser humano y en Página 10 su creatividad para resolver problemas debería ser superior a los algoritmos inspirados en el comportamiento colectivo de insectos como hormigas, abejas, etc. [4]. Para este trabajo se ha seleccionado un algoritmo novedoso que se basa en el proceso de lluvia de ideas o brainstorming [5], que es una técnica grupal utilizada para generar ideas nuevas y brindar soluciones a un problema. El algoritmo propuesto de BrainStrorming Optimization (BSO) se probará con el fin de optimizar el diseño de un mecanismo de cuatro barras del tipo ManivelaBiela-Balancín (MBB), el cual tiene acoplado un motor de corriente directa (C.D.) al eje de entrada [6]. 1.1 Descripción del problema El mecanismo de cuatro barras es básico para el diseño de máquinas, por lo que es necesario que se asegure que no falle cuando se encuentre operando. Cada uno de los eslabones que componen al mecanismo de cuatro barras se encuentra unido por articulaciones, las cuales le permiten realizar movimientos dependiendo de su grado de libertad. Cuando se cuenta con un motor de C.D. como elemento impulsor del sistema la velocidad angular de entrada no es constante. El ciclo de trabajo de un mecanismo como éstos, consta de varias posiciones, las cuales son afectadas por diferentes cargas, por lo tanto es necesario implementar un sistema de control que regule la velocidad de entrada al mecanismo con el fin de obtener siempre la salida deseada para la que fue creado ese diseño mecánico. Los detalles técnicos del problema se pueden encontrar en [6]. Para problemas como el que se plantea, la Ingeniería mecatrónica proporciona un enfoque en el que el problema se visualiza como un conjunto de subsistemas interactuando unos con otros para lograr un objetivo, recalcando la Página 11 importancia de que los subsistemas se relacionen para asegurar un mejor desempeño. Sin embargo, existen problemáticas que únicamente pueden resolverse utilizando un algoritmo de tiempo exponencial. Este tipo de problemas está cobrando una mayor notoriedad en la actualidad y se vuelve necesario modelar y resolver tareas como la optimización y el aprendizaje para aplicaciones donde no se puede obtener una solución de manera analítica [7]. Es por ésto que se aplican técnicas metaheurísticas a problemas de optimización [2] y se analizan diferentes opciones para encontrar así, la que proporcione un resultado de mejor calidad. En este trabajo precisamente se pondrá a prueba la eficacia de un algoritmo novedoso basado en el proceso humano de la lluvia o tormenta de ideas, siguiendo la línea de que un algoritmo basado en una técnica humana para resolver problemas proveerá una solución satisfactoria. 1.2 Hipótesis BSO proveerá un mejor desempeño al resolver el problema mecatrónico planteado en el presente trabajo con respecto a un algoritmo evolutivo, evolución diferencial en este caso. 1.3 Objetivo General Implementar el algoritmo de optimización BSO para el diseño óptimo de un mecanismo de cuatro barras. Página 12 1.4 Estructura del documento Capítulo 1. Proyecto. En este capítulo se introduce al lector en lo que será el proyecto general que se atiende en esta tesis, el problema que se ataca y la propuesta de solución que se plantea. Capítulo 2. Optimización. En este apartado se define el concepto de optimización y los elementos que componen un problema de optimización. Capítulo 3. Mecanismos de cuatro Barras. En esta parte del documento se mencionarán los sistemas mecánicos y los mecanismos que los integran, haciendo énfasis en aquellos de cuatro barras y en su proceso de diseño, tema de estudio en esta tesis. Capítulo 4. Algoritmo Brain Storm Optimization. En este capítulo se abordará al algoritmo Brain Storm Optimization, se analizará su funcionamiento y sus operadores, se revisará su pseudo código y finalmente se realizarán las adaptaciones necesarias para resolver el problema planteado. Capítulo 5. Metodología. En este capítulo se explicará el diseño experimental para llegar a los resultados mostrados en el capítulo siguiente. Capítulo 6. Resultados y Discusiones. En este capítulo se mostrarán los resultados a los que se llegaron con la implementación del algoritmo y se realizará un análisis de ellos. Capítulo 7. Conclusiones. En este apartado se presentan las conclusiones de esta tesis y el trabajo futuro. Página 13 2. Optimización Hace tiempo que el hombre busca, mejores maneras de realizar las tareas cotidianas de la vida, que proporcionen el mejor resultado, el que genere mayores ganancias, una mayor producción o aquel que se traduzca en el menor consumo de tiempo, en la menor inversión de dinero o el menor desperdicio de recursos. Procesos de producción y administración, diseños de redes de telecomunicación, problemas de distribución y envíos por mencionar algunos, todos ellos tienen un factor común, el objetivo es maximizar o minimizar un determinado valor, es decir, optimizarlo. Por ello se llaman problemas de optimización. Es importante hablar de la optimización también llamada programación matemática, ya que este trabajo pretende optimizar un diseño mecánico. En este apartado se abordarán los conceptos básicos del tema. 2.1 Concepto de Optimización El proceso de optimización consiste en la búsqueda de la mejor solución para un problema entre un conjunto de alternativas. Para efectos de este trabajo se definirá optimizar como encontrar el valor de las variables que al mismo tiempo que satisfacen las restricciones alcanzan el valor de calidad óptimo conocido como función objetivo. Página 14 Componentes de un problema de optimización:  Función objetivo: Es el propósito de la optimización. Es decir, es la medida cuantitativa que indicará el desempeño o bondad del sistema, es el valor que da la pauta para discriminar si el vector de variables de decisión es el óptimo para maximizar o minimizar un problema. Generalmente se trata de números enteros o reales, matemáticamente se representa de la siguiente manera: f (x)  Variables de decisión: Es el vector de parámetros de entrada que afectan el valor de la función objetivo. xi , i  1,2,..., n El vector  x de n variables se representa de la siguiente manera [8]:  x  x1, x2,, xn  Restricciones: Aportan realismo a la optimización, están definidas por las características y/o requisitos en la vida real de los componentes de un sistema. Se traducen como limitaciones que las variables deben satisfacer, cuando se presentan significa que no cualquier solución es posible o factible. Las restricciones pueden ser expresadas en forma de ecuaciones de igualdad o desigualdad respectivamente [8]: h( x1 ,..., xn )  0 g ( x1 ,..., xn )  0 En un problema de optimización numérica, optimizar equivale a resolver una ecuación de este tipo: max f ( x) x ó min f ( x) x Página 15 2.2 Problemas Tratables e Intratables El esfuerzo necesario para resolver un problema de forma eficiente puede variar enormemente, es por ello que surge la siguiente clasificación de los problemas computacionales:  Tratables: Problemas para los cuales existe un algoritmo de solución que se ejecuta en tiempo polinomial, también conocidos como problemas P (de orden polinomial).  Intratables Problemas para los que no se conoce ningún algoritmo de complejidad polinomial, también llamados problemas NP (de orden no determinístico polinomial). En un problema de optimización, lo deseable es encontrar no solamente una solución, sino la mejor solución, sin embargo existen problemas que únicamente pueden resolverse utilizando un algoritmo de tiempo exponencial o incluso, puede ser que no exista algoritmo alguno, por lo cual, al tener este tipo de información puede optarse por la búsqueda o aplicación de técnicas metaheurísticas existentes, que si bien no garantizan una solución óptima, si pueden proporcionar una buena solución. 2.3 Técnicas Metaheurísticas La palabra heurística se deriva de la palabra griega heuriken que significa “descubrir”. También dio origen a la exclamación eureka, (aquella que hizo famosa Aquímedes) cuyo significado es “lo encontré”. Así definieron Bartholdi y Platzman el concepto de heurística [11]: Página 16 “Una heurística puede verse como un procesador de información que, deliberadamente, pero juiciosamente, ignora cierta información. Ignorando información, una heurística se libra de gran parte del esfuerzo que debió haberse requerido para leer los datos y hacer cálculos con ellos. Por otra parte, la solución producida por tal heurística, es independiente de la información ignorada, y de este modo no se ve afectada por cambios en tal información. Idealmente, se busca ignorar información que resulta muy caro colectar y mantener, esto es, computacionalmente caro de explotar y mantener, y que contribuye en poco a la precisión de la solución.” El propósito de una función heurística es el de guiar el proceso de búsqueda en la dirección más provechosa sugiriendo qué camino tomar cuando hay más de uno disponible. Se podrían comparar con guías de turismo, por un lado pueden sugerir las rutas más interesantes pero por otro lado, podrían omitir lugares de interés para algunas personas. Los métodos heurísticos normalmente están inspirados en la intuición o en la naturaleza y no están diseñados para ningún problema en particular. Una técnica metaheurística es un procedimiento de búsqueda que tampoco garantiza la obtención de la solución óptima y que se basa en la aplicación de algunas reglas sencillas, pero a diferencia de un método heurístico, la búsqueda será orientada con el fin de evitar óptimos locales. Estas técnicas se han vuelto muy recurridas sobretodo en problemas de optimización ya que son simples, efectivas y sobre todo por su mejor desempeño. El funcionamiento de una metaheurística se podría resumir de la siguiente manera: se comienza con un conjunto de soluciones potenciales, aunque no las mejores, a partir de este conjunto se obtiene una o más que satisfacen algún Página 17 criterio y se vuelve a comenzar el proceso hasta llegar a alguna condición de paro previamente definida. Las técnicas metaheurísticas comparten algunas características que se enlistan a continuación [17]:  Son aproximadas, es decir no garantizan encontrar la mejor solución.  Son ciegas, es decir debe indicárseles cuando detenerse, ya que ellas no saben si han logrado una solución óptima.  En ocasiones aceptan soluciones relativamente malas, o al menos no mejores que la anterior, lo que se considera un paso intermedio para llegar a una región de soluciones no explorada. Esta característica se compara con escalar una montaña, donde hay tanto cimas como abismos, las “malas” soluciones serían el equivalente a posicionarse en el fondo de la montaña, pero es solamente desde ese lugar que se puede llegar a una cima más alta incluso de la que se ha descendido.  Son generales, pensadas para implementarse en cualquier problema de optimización, lo único que se requiere es tener una representación adecuada del problema, una función objetivo y un mecanismo para moverse en el espacio de búsqueda.  Bajo ciertas condiciones, asintóticamente convergen con una solución óptima. Estas técnicas permiten resolver problemas complejos de una manera sencilla y obtener soluciones suficientemente buenas en tiempos razonables. Página 18 2.4 Algoritmos de Optimización y una Clasificación Hay problemas de optimización del mundo real que a menudo son problemas NP y por lo tanto se vuelven muy difíciles de resolver. Para este tipo de problemas no se conocen algoritmos eficientes. Como resultado, muchos problemas tienen que ser resueltos por ensayo y error utilizando diversas técnicas de optimización. Cada vez se desarrollan nuevos algoritmos para tratar de hacer frente a estos problemas de optimización difíciles. La naturaleza ha inspirado a muchos investigadores de muchas maneras. Hoy en díamuchos de los nuevos algoritmos son inspirados en la naturaleza o bioinspirados. Entre los algoritmos bio-inspirados, una clase especial de algoritmos se han desarrollado inspirándose en la inteligencia colectiva (o de enjambre). De hecho, los algoritmos basados en la inteligencia de enjambre se encuentran entre los más populares. Entre los ejemplos más conocidos se encuentran la optimización basada en la colonia de hormigas y la optimización de enjambre de partículas. Sin embargo, no todos los algoritmos se basan en los sistemas biológicos. Muchos algoritmos se han desarrollado con base en sistemas físicos y químicos. A continuación se presenta una clasificación de algoritmos basada en la metáfora en la que se inspiran [12]: Página 19 2.4.1 Basados en Inteligencia Colectiva (o de enjambre) La inteligencia colectiva o de enjambre (SI por su equivalente en inglés Swarm Intelligence), se refiere a la conducta cooperativa que surge de la interacción de múltiples agentes; sostiene que la inteligencia se deriva de la interacción de los individuos en un mundo social. Además, este modelo de inteligencia se puede aplicar de manera efectiva a los sistemas de inteligencia artificial [18]. Todos los algoritmos basados en SI usan conjuntos de agentes muy simples, inspirados en el comportamiento colectivo de los insectos sociales, como las hormigas, termitas, abejas y avispas, así como de otros animales sociales como bandadas de pájaros o peces. Mientras que cada ser puede ser considerado como poco inteligente, todo el sistema de múltiples individuos puede mostrar un comportamiento auto-organizado y por lo tanto puede comportarse como una especie precisamente de inteligencia colectiva. Los algoritmos basados en SI se encuentran entre los más populares y ampliamente utilizados. Hay muchas razones de tal popularidad, una de las razones es que los algoritmos basados en SI normalmente comparten información entre múltiples agentes, de modo que se autoorganizan, y aprenden durante cada iteración. Entre los algoritmos más conocidos de esta clasificación se encuentran:  Optimización basada en colonias de hormigas  Colonia artificial de abejas  Optimización basada en enjambre de abejas  Algoritmo de enjambre de partículas Una lista más completa de algoritmo puede ser vista en [12]. Página 20 2.4.2 Basados en Física y Química No todos los algoritmos metaheurísticos son bio-inspirados, debido a que sus fuentes de inspiración a menudo provienen de la física y la química. Para los algoritmos que no son bio-inspirados, la mayoría se han desarrollado mediante la imitación de ciertas leyes físicas y / o químicas, incluyendo las cargas eléctricas, la gravedad, los sistemas fluviales, etc. Entre algunos ejemplos podemos mencionar:  Hoyo negro [19]  Optimización de la fuerza central [20]  Optimización electro-magnética [21]  Búsqueda gravitacional [22] 2.4.3 Otros algoritmos: Cuando los investigadores desarrollan nuevos algoritmos, algunos pueden buscar inspiración fuera de la naturaleza. En consecuencia, algunos algoritmos no son bio-inspirado o basado en la química-física /, a veces es difícil ubicar a algunos algoritmos en las tres categorías, debido a que ellos se han desarrollado mediante el uso de varias características de diferentes fuentes, como social, emocional, etc. Podemos mencionar:  Optimización basada en anarquía de la sociedad [23]  Brain Storming Optimization. [5] Página 21 2.4.4 Algoritmos Evolutivos Los Algoritmos Evolutivos (EAs) se han popularizado como métodos robustos y efectivos para la resolución de problemas de optimización. Un algoritmo evolutivo de basa en una población, cada individuo dentro de esa población representa una solución en potencia al problema. Emulando el proceso de selección natural, el cual asegura la supervivencia del más fuerte o mejor adaptado, un algoritmo evolutivo tiene mecanismos para asegurarse que a través de las generaciones los mejores individuos sean los sobrevivientes. Para determinar si un individuo es mejor que otro, se evalúa cada uno de acuerdo a la función objetivo del problema, dando como resultado un valor llamado “aptitud”, así que el individuo con la mejor aptitud (mayor o menor, según el problema sea de maximización o minimización respectivamente) será el elegido. Estos algoritmos cuentan con operadores de variación como la recombinación y mutación, cuyo objetivo es ir refinando la búsqueda de una solución, de manera que la población se dirige hacia áreas que representen mejor soluciones a un problema. Los algoritmos evolutivos más populares son: la programación evolutiva (Fogel, 1962), los algoritmos genético (Holland, 1975), estrategias evolutivas (Rechenberg, 1973), y la programación genética (Koza, 1992), los cuales han sido inspirados en la evolución biológica. [5] Página 22 A continuación se muestra la Figura 2.1 que incluye el diagrama de flujo del comportamiento general de los algoritmos evolutivos y que de alguna manera engloba el funcionamiento de un algoritmo bio-inspirado. INICIO POBLACIÓN INICIAL EVALUACIÓN DE LA FUNCIÓN OBJETIVO CRITERIOS DE MEJOR INDIVIDUO OPTIMIZACIÓN ALCANZADOS? SOLUCIÓN SELECCIÓN GENERAR NUEVA POBLACIÓN COMBINACIÓN / MUTACIÓN Figura 2.1 Diagrama de flujo del comportamiento de un algoritmo evolutivo. Página 23 3. Mecanismos de cuatro Barras El presente capítulo aborda los puntos más importantes para comprender el problema mecatrónico planteado en el presente trabajo. Contiene su modelo matemático así como sus diagramas correspondientes. Se han tomado los elementos más relevantes a modo de dar un contexto del problema. Para una lectura más a detalle consultar [16] En esta sección se describe brevemente el enfoque dinámico de diseño para un mecanismo de cuatro barras del tipo Manivela-Biela-Balancín (MBB) el cual tiene acoplado un motor de corriente directa (C.D.) al eje de entrada. El mecanismo de cuatro barras, en sus diferentes configuraciones, es uno de los mecanismos más utilizados en la maquinaria industrial. Una de las principales suposiciones en el diseño de dicho mecanismo es la que establece que su velocidad angular de entrada es constante, lo que no siempre se cumple cuando un motor de C.D. es el elemento impulsor del sistema [14]. Lo anterior se puede explicar cuando se estudia el ciclo de trabajo del mecanismo de cuatro barras, en cada ciclo se tienen posiciones en las que la inercia del mecanismo varía tales como: posiciones de volquete, posiciones de máximo y mínimo ángulo de transmisión o posiciones de bloqueo debido a ajustes imprecisos en las articulaciones de los eslabones [15]. En dichas posiciones, la carga “vista” por el motor de impulsión varía y por consecuencia también cambia el par aplicado por el motor al sistema mecánico. Por lo tanto, implementar un sistema de control que regule la velocidad de entrada al sistema mecánico es de gran importancia para el buen funcionamiento del Página 24 mismo, no olvidando que la salida del sistema debe cumplir con los requerimientos para los cuales se diseñó dicho sistema mecánico. A continuación se presentan las funciones objetivo y restricciones del sistema MBB de manera general, sin embargo, se puede consultar a detalle en el reporte [16]. En la Figura 3.1 es presentado el Modelo esquemático de un mecanismo de MBB, donde: Figura 3.1. Modelo esquemático de un mecanismo de MBB. y i son los círculos sombreados que indican la posición de los centros de masa de cada eslabón. mi y Ji representan la masa y el momento de inercia con respecto al centroide del i-ésimo eslabón respectivamente. Li representa la longitud del eslabón. i  es la coordenada para el eslabón en cuestión. kyC Representan a un resorte torsional y a un amortiguador con constantes de rigidez y amortiguamiento respectivamente, y son los Página 25 elementos de carga del mecanismo. Figura 3.2 Modelo esquemático de un motor de C.D. La Figura 3.2 muestra el esquema de un motor de C.D. con caja de engranes en la salida del mismo. Los parámetros descriptivos del sistema eléctrico son: LyR representan la inductancia y la resistencia de armadura respectivamente, i(t) es la corriente de entrada u(t) es el voltaje de entrada. J es el momento de inercia combinado debido al eje de salida y a la caja de engranes de salida, B representa el coeficiente de amortiguación viscosa debido a posibles fricciones de los rodamientos, TL es una carga mecánica constante debida a la fricción en las escobillas, fricción entre engranes o fricción seca en los rodamientos. Tm y Vb Representan al torque magnético y a la fuerza electromotriz del motor, respectivamente. Página 26 Con el propósito de establecer el problema de diseño óptimo como un problema de optimización, sea el vector de variables de diseño: ⃗ Por lo tanto el problema del MBB consiste en optimizar: [ ⃗ ⃗ ] Con 2 funciones objetivos que se optimizan de manera separada ( donde: ) es el desplazamiento del balancín y se requiere un valor lo más grande posible para maximizar la transferencia de energía del motor de entrada hacia el mecanismo de cuatro barras. ⃗ ⃗ Donde: ̇ ⃗ ⃗ ⃗ ⃗ ⃗ ⃗ ⃗ Página 27 Donde y se calculan de acuerdo a la configuración del mecansmo de cuatro barras:    Caso a) Caso b) Caso c) : * ( )+ * ( )+ : ( ) ( ) : * ( )+ * ( )+ Página 28 es la función de mérito para calidad de funcionamiento (Angulo de transmisión) cuyo valor óptimo es lo más cercano a 90° a lo largo de toda la trayectoria. ⃗ ⃗ ( ) ( ) Sujeto a: ̇ ⃗ ⃗ ⃗ ⃗ ⃗ ⃗ ⃗ Dónde: * + * + Página 29 4. Algoritmo Brain Storm Optimization (BSO) Resumen: En los últimos años, se han desarrollado diversos algoritmos basados en poblaciones con el fin de resolver problemas de optimización. En este trabajo, se ha elegido un novedoso algoritmo de optimización basado en la técnica grupal lluvia de ideas. Los resultados experimentales muestran al BSO como un algoritmo muy prometedor [9]. En este capítulo se analizará a detalle tal algoritmo. Cuando un individuo tiene dificultades para resolver un problema, una de tantas posibles opciones para encontrar una solución es recurrir a un grupo de personas (preferentemente con área de conocimiento diferentes) y realizar una tormenta o lluvia de ideas y es altamente probable que gracias a esta técnica, se pueda encontrar una solución al problema planteado. Inspirado en este proceso humano de generar ideas se propone en el año 2011 el algoritmo de optimización Brain Storm Optimization [10]. 4.1 Proceso de Lluvia de ideas El proceso de lluvia de ideas es una técnica creativa ampliamente conocida de la que se ha valido el ser humano para generar ideas de manera interactiva. El “brainstorming”, también llamado lluvia, tormenta o torbellino de ideas fue creado por Alex Osborn en los años 30 y publicado años después. El objetivo principal de esta técnica es generar tantas ideas como sea posible en un determinado tiempo, estas ideas se registran o consideran incluso Página 30 aunque algunas de ellas pudieran parecer poco viables. En la Tabla 4.1 se enlistan los pasos del proceso de lluvia de ideas. Paso 1 Reunir un grupo de personas con áreas de conocimiento lo más variado posible, con el fin de recopilar ideas diversas. Paso 2 Generar el mayor número de ideas posibles respetando las reglas de la Tabla 4.2. Paso 3 Algunas personas, 3 ó 5 por ejemplo actuarán como propietarios del problema, y cada uno elegirá una idea que considera “mejor”. Paso 4 Usar las ideas elegidas en el paso 3 y utilizarlas como punto de partida para generar nuevas ideas, respetando una vez más las reglas de la Tabla 4.2. Paso 5 Una vez más los “propietarios” elegirán las mejores ideas, al igual que en el paso 3. Paso 6 Seleccionar un objeto al azar y utilizar sus funciones y características como pistas, generar más ideas de acuerdo a las reglas de la Tabla 4.2 Paso 7 Una vez más los “propietarios” elegirán las mejores ideas, al igual que en el paso 3. Paso 8 En este punto se habrá obtenido una buena solución considerando o mezclando las ideas surgidas. Tabla 4.1 Pasos en el proceso “Brainstorming” La operación de recoger un objeto en el Paso 6 sirve para la generación de ideas diversas. Puede ayudar al grupo de intercambio de ideas para apartarse de las ideas generadas con anterioridad, por lo tanto, para evitar ser atrapado por las ideas generadas previamente. Como consecuencia, el grupo de Página 31 intercambio de ideas será más abierto de mente y generará más ideas diferentes [10]. Los propietarios de problemas sirven para un propósito diferente. Al elegir varias buenas ideas de las ideas generadas hasta ahora, los propietarios buscan hacer que el grupo de participantes preste más atención a las mejores ideas. Las ideas seleccionadas funcionan como puntos de atracción en el proceso de generación de ideas. Cabe hacer énfasis en dos operaciones muy importantes presentes en el proceso de lluvia de ideas: divergencia y convergencia. “Brainstorming” le da más peso a la cantidad que a la calidad, debido a que se utiliza como un proceso divergente que estimula la creatividad y la innovación, para después transformarse en un proceso convergente en el que las ideas generadas se agrupan, se priorizan y son evaluadas. Para garantizar la espontaneidad, que todas las alternativas posibles fluyan y exista retroalimentación en el grupo, es de vital importancia apegarse a las reglas presentadas en la Tabla 4.2 al momento de generar ideas: Regla 1 Suspender críticas. No hay malas ideas. Regla 2 Toda idea es bienvenida. Regla 3 El desarrollo y combinación de ideas es deseable. Regla 4 La cantidad es fundamental Tabla 4.2 Reglas de Osborn para la generación de ideas en el proceso Brainstorming Página 32 4.2 Algoritmo Brain Storm Optimization Como se mencionó en la Sección 4.1, la técnica de lluvia de ideas plantea que los participantes generen tantas ideas diversas como sea posible, en el algoritmo BSO todas esas ideas generadas conforman a la población y cada idea es una solución potencial al problema. Como en cualquier otro algoritmo basado en población, el algoritmo BSO comienza con la inicialización de la población n, para efectos de simplicidad, el número de la población se mantiene constante en cada iteración. El proceso de iteración comienza después de este punto. Cada idea será evaluada de acuerdo a la función objetivo del problema planteado, para posteriormente ser agrupadas en clusters utilizando el método k-means, las mejores ideas son elegidas como centroides de cada cluster. Después empieza el proceso de reemplazo, primero de un centroide y posteriormente de todas y cada una de las ideas. Esta mecánica - evaluación, agrupamiento y reemplazo – se estará repitiendo hasta alcanzar la condición de paro previamente definida, ya sea un determinado número de iteraciones o de evaluaciones. Finalmente la mejor idea es elegida como la solución obtenida para el problema. [9] El algoritmo BSO se compone de cuatro operadores básicos: inicialización de la población, proceso de clustering, alteración de centroides y actualización de Página 33 individuos. A continuación se describirá cada operador y se presenta en la Figura 4.1 un diagrama de flujo del proceso básico del algoritmo BSO: INICIO Iteración = 1 Inicialización de la población Proceso de Clustering Alteración de centroides Actualización de individuos Iteración = Iteración + 1 Iteración < MAX FIN Figura 4.1 Diagrama de flujo del algoritmo BSO. Página 34 4.2.1 Inicialización de la población A partir de la similaridad de los casos en la mayoría de los algoritmos basados en la inteligencia colectiva, una idea dentro de la población se representa por un vector, el cual es inicializado aleatoriamente con una distribución uniforme dentro del espacio de solución (tomando en cuenta las restricciones) a través de la siguiente fórmula: j j j x j  xmin   ( xmax  xmin ) Dónde: xmaxy xmin son los valores máximos y mínimos de la variable de diseño  x es un valor aleatorio uniformemente distribuido entre 0 y 1 Cada idea entonces es evaluada por la función objetivo, dando como resultado un valor de aptitud, el cual indica la calidad de esta idea para ser considerada como una solución competitiva al problema 4.2.2 Clustering Clustering significa agrupar una serie de datos en conjuntos de objetos similares, ya sea por sus funciones o atributos. Cada grupo llamado cluster consiste en elementos que son similares entre ellos y diferentes a los objetos de otros grupos[13]. Página 35 Formar clusters aporta simplicidad en el modelado de datos y desempeña un papel importante en el descubrimiento de conocimiento y minería de datos, tareas que requieren de una rápida y precisa partición de grandes grupos de datos. El número de clusters elegidos equivale al número de propietarios en el proceso de lluvia de ideas, mientras que determinar el centroide de cada cluster se equipara con la elección de los propietarios de lo que ellos consideren la mejor solución. 4.2.3 Alteración de centroides La alteración de centroides consiste elegir aleatoriamente un cluster, se toma su centroide y se reemplaza por un nuevo individuo generado al azar. Cabe resaltar que esta operación sólo se llevara a cabo cuando se cumpla una regla que se verá más adelante al analizar a detalle todos los pasos del algoritmo BSO. 4.2.4 Actualización de Individuos Este paso irá tomando diversos caminos dependiendo de valores que se van generando aleatoriamente, se establecen al principio del algorimo ciertos parámetros y entonces se van comparando los valores aleatorios con estos parámetros, lo que da resultado diversas combinaciones que pueden originar al nuevo individuo:  Se trabaja con un sólo cluster (su centroide o un individuo al azar del cluster) Página 36  Se trabaja con dos clusters (la combinación de sus centroides o la combinación de dos individuos al azar) Después se agregan valores aleatorios, ruidos Gaussianos para ser exactos, para generar individuos nuevos. La creación de un nuevo individuo se puede representar por: xnew  xselected   * n(, ) Dónde: xnew xselected n(  ,  )  es la idea nueva es la idea seleccionada para generar una nueva es un vector con la función aleatoria Gaussiana con desviación μ y varianza σ es la contribución de cada valor del vector de números aleatorios Gaussianos. Para propósitos del algoritmo  se calcula con la siguiente fórmula:   log sig ((0.5 * max_ iteration  current _ iteration ) / k ) * rand () Dónde: log sig es la función de transferencia del logaritmo sigmoide max_ iteration current _ iteration es el máximo número de iteraciones k es el salto de paso elegido para el algoritmo rand () es un número aleatorio entre 0 y 1. es la iteración actual Página 37 En la Tabla 4.3 se definen todos los pasos a seguir en el algoritmo Brain Storm Optimization donde se ha agregado la tercera columna a la tabla que indica la correspondencia de cada paso con los pasos del proceso de lluvia de ideas mostrado en la Tabla 4.1. Paso 1 Generar aleatoriamente n soluciones potenciales ( ideas) Inicialización Paso 2 Agrupar n ideas en m clusters Equivalen al Agrupamiento Paso 3 Evaluar las n ideas Evaluación Paso 4 Elección de Calificar las ideas y registrar las mejores como centro de cada cluster. Centroides Generar aleatoriamente un valor entre 0 y 1. Paso 5 Alteración de centroide. a) Si el valor es más pequeño que una probabilidad pre determinada p5a : i. Aleatoriamente seleccionar un cluster. ii. Generar una nueva idea al azar que reemplazará al centroide del cluster elegido. propósito de los pasos 3, 5 y 7 que es seleccionar las mejores ideas. Simula al paso 6, se asegura la exploración de áreas nuevas. Para crear nuevos individuos: Paso 6 Alteración de individuos. a) Generar aleatoriamente un valor entre 0 y 1. b) Si el valor es menos que una probabilidad pre determinada p6b i. Aleatoriamente seleccionar un cluster con una probabilidad p6bi. ii. Generar un valor aleatorio entra 0 y 1. iii. Si este valor es menor que una probabilidad predeterminada p6bii: 1. Seleccionar el centroide del cluster y agregarle ruidos gaussianos para generar una nueva idea. iv. De otro modo seleccionar al azar una idea del cluster y agregar ruidos gaussianos para crear una idea nueva. c) En caso contrario seleccionar dos clusters para trabajar. i. Generar un valor aleatorio. ii. Si este valor es menor que una probabilidad pre determinada p6c, se combinarán los centroides de los dos cluster seleccionados y se les agregarán ruidos para generar una nueva idea. Equivale la generación de ideas de los pasos 2, 4 y 6 Página 38 iii. En caso opuesto elegir al azar una idea de cada cluster, se combinarán y posteriormente se les agregarán ruidos gaussianos para crear una nueva idea. d) La idea nueva es evaluada y comparada con la existente, la mejor será guardada y la otra es eliminada. Paso 7 Si se han generado n individuos nuevos, pasar al paso siguiente, de otra manera, regresar a paso 6. Paso 8 Si existe un número de iteraciones máximas y éste ha sido alcanzado, se da por terminado el algoritmo; de otra manera, regresar al paso 2. Tabla 4.3 Pasos del algoritmo BSO. Como se puede apreciar dentro de la Tabla 4.3., en 6.b y 6.c respectivamente, una nueva idea puede ser inspirada en una sola idea existente o en una combinación de dos ideas. Aunque en la vida real una solución podría ser generada a partir de dos o más soluciones propuestas, el algoritmo solo considera la combinación de dos de ellas para mantenerlo simple sin que tenga un impacto en su eficiencia. Al igual que en el proceso de lluvia de ideas, en el algoritmo de optimización BSO se identifican las operaciones de divergencia en la actualización de individuos y convergencia al crear los clusters, que son las dos operaciones básicas implementadas en cada iteración [9]. La probabilidad mencionada en el paso 6.b.i es proporcional al número de individuos en el cluster, es decir entre más individuos se encuentren agrupados en un cluster, éste tendrá más probabilidad de ser seleccionado. Página 39 5. Metodología y Diseño de Experimentos En este capítulo se presenta el procedimiento llevado a cabo para la obtención de los resultados que se muestran en el apartado correspondiente. Se eligió el lenguaje de programación java para implementar el algoritmo BSO y se creó una función correspondiente a cada paso del algoritmo. Retomando el capítulo tres, que describe el funcionamiento de un mecanismo de cuatro barras del tipo MBB, se enfatiza que lo que se pretende optimizar por separado son dos funciones mérito, una de maximización correspondiente a la generación de movimiento: ⃗ ⃗ y una más para la calidad de funcionamiento : ⃗ ⃗ ( ) ( ) Cabe resaltar que ambas funciones se han tratado de manera individual, es decir se ha implementado el algoritmo BSO de manera independiente para cada uno de ellos, dando como resultado dos programas en los que las diferencias observadas consisten en la función empleada para evaluar la aptitud de cada solución y en la manera de elegir la mejor idea al compararla con otra, en un programa se elige la mayor mientras que en el otro la menor. Página 40 5.1 Valores Iniciales Para el propósito de validar la eficacia y utilidad del algoritmo propuesto BSO, en este documento, se ha utilizado un conjunto de parámetros iniciales sugeridos en [10], los cuales se fueron calibrando de manera manual para la obtención del mejor resultado; el único parámetro alterado desde el comienzo es el máximo número de iteraciones, que ha sido reemplazado por el número máximo de evaluaciones, mientras que el primero cuenta el número de generaciones evaluadas, el segundo contabiliza la evaluación de cada solución de manera individual. El conjunto de parámetros iniciales se listan en la Tabla 5.1: n m Evaluación µ Máxima 100 5 0.2 0.8 0.4 0.5 20 50,000 0 1 Tabla 5.1 Conjunto de parámetros iniciales para el algoritmo BSO. Donde n es el tamaño de la población, es decir el número de ideas con las que se trabajará m es el número de clusters en los que se agrupará la población , y , son las probabilidades que se utilizan en los pasos , , y respectivamente del algoritmo BSO es el salto de paso utilizado para modificar cada idea Página 41 Evaluación Máxima es el número máximo de evaluaciones y por lo tanto la condición de paro del algoritmo µyσ son la media y la varianza empleados en la función gaussiana 5.2 Procedimiento Realizado Como se mencionó en el Capítulo 4, el primer paso es la inicialización de la población o conjunto de ideas, el concepto de población se refiere al conjunto de soluciones potenciales y, cada solución a su vez, está conformada por un vector de variables de diseño, retomando una vez más el capítulo tres, el vector de variables de diseño es: ⃗ Por lo tanto cada idea o solución contiene cinco valores, de los cuales cuatro corresponden a las longitudes de los eslabones y el quinto representa el ángulo de transmisión. Los cinco valores, son creados al azar con una distribución uniforme pero respetando las restricciones de diseño del problema MBB, y así a través de las iteraciones del algoritmo, cada idea se irá evaluando, comparando y modificando, prevaleciendo siempre las mejores. En la Tabla 5.2 se muestra una población inicial conformada por 10 ideas a manera de ejemplo: Página 42 Idea 1 Idea 2 Idea 3 Idea 4 Idea 5 Idea 6 Idea 7 Idea 8 Idea 9 Idea 10 L1 L2 L3 L4 ϴ1 0.2794673048 0.2981377429 0.2042088396 0.1042788092 0.4700919755 0.1314028793 0.1930142010 0.0848756843 0.4984497466 0.1059495896 0.0878704052 0.3504121817 0.1426708879 0.0980779500 0.1220947158 0.2797982744 0.1055750120 0.1398641674 0.3036698362 0.0689321719 0.2573591906 0.2984285506 0.4318334500 0.4089662154 0.1460646155 0.4115757266 0.4737310044 0.1513241291 0.3587193824 0.0676471799 0.1232602764 0.4185568358 0.1644453398 0.4980388154 0.4292798053 0.1856829238 0.0857538024 0.4112656620 0.3441162389 0.1701527171 -0.1111583758 -0.6908904402 -0.3567284782 -0.0894746227 -0.7662183467 0.6798111118 -0.1573590726 -0.7384073765 0.3614340874 -0.4170782173 Tabla 5.2 Ejemplo de una población inicial (conjunto de ideas). A continuación se procede a evaluar cada idea para obtener su aptitud y así poder seleccionar las mejores como centroides de cada cluster, se seleccionarán tantos centroides como se haya definido el parámetro m al inicio del algoritmo. Cabe mencionar que el algoritmo BSO fue diseñado para resolver problemas de optimización sin restricciones, y considerando que los dos problemas a resolverse incluyen restricciones, se agregaron los siguientes criterios para comparar ideas (soluciones) [25] :  Entre dos ideas factibles, la que tenga mejor valor en la función de mérito es seleccionada.  Entre una idea factible y otra no factible, se selecciona a la idea factible.  Entre dos ideas no factibles, la que tenga menor suma de violación de restricciones es seleccionada. Página 43 Las funciones mérito se encuentran codificadas en el lenguaje MATLAB, por lo que fueron incluidas en una librería que se agregó al proyecto en Java para poder invocar dichas funciones. Una vez hecho ésto, y con el fin de colocar el resto de las ideas dentro del cluster correspondiente, se calcula la distancia de las ideas a cada uno de los centroides, el cluster más cercano será al que pertenece la idea. A manera de ilustración se muestra la Figura 5.2 que representa un conjunto de datos agrupados en tres clusters de diferentes colores, el punto negro es el centroide cada cluster. Figura 5.1 Datos agrupados alrededor de tres centroides. Ya que se han conformado los clusters, se puede continuar con la alteración de centroides, este paso depende de que se cumpla la condición 5a, por lo tanto habrá iteraciones en las que se lleve a cabo y algunas en las que se omita. Página 44 La alteración de individuos es un paso que siempre se lleva a cabo, siguiendo el flujo del algoritmo BSO en algunas ocasiones se toma una idea y se modifica, también habrá casos donde se combinen dos ideas creando una solución temporal que será modificada. En ambos casos, la nueva idea se compara con la original y se conserva la mejor evaluada. Esto se hace con todas y cada una de las ideas de la población y cada evaluación es contabilizada, ya que este contador es la condición de paro del algoritmo. Después de evaluar cada idea, la población ya no es la misma, así que se vuelve a iniciar el proceso de clustering y todos los pasos subsecuentes hasta llegar al número de evaluaciones máximas, dónde se espera obtener una solución satisfactoria al problema. Página 45 6. Resultados y Discusión En esta sección se muestran los resultados obtenidos por el algoritmo BSO. Se ha realizado un análisis del impacto de la calibración (aumento/disminución) de cada parámetro en los resultados, lo cual ha permitido manipularlos con la intención de elegir un conjunto de parámetros que brinde un mejor desempeño del algoritmo. . El algoritmo se ejecutó treinta veces con cada conjunto de parámetros, se eligió ese número de ejecuciones porque es el usualmente adoptado para comparar algoritmos bio-inspirados. Se analizaron los cambios que provoca el aumento o disminución en cada uno de los parámetros, a modo de calibrar el algoritmo y obtener un mejor resultado. Al final de cada ejecución el algoritmo ofrece una mejor solución encontrada, esta solución fue almacenada y así sucesivamente con cada ejecución, de estas treinta soluciones se identificaba la mejor, la peor y se calcularon algunos valores estadísticos, como son el promedio, la mediana y la varianza, hasta finalmente elegir el conjunto de parámetros con los mejores resultados y cuyo comportamiento además fue bastante robusto, es decir, todas las ejecuciones brindaron un resultado estable. Todas las soluciones obtenidas fueron factibles y la varianza fue menor que con otros conjuntos de parámetros. Página 46 6.1 Resultados Después de haber calibrado manualmente los parámetros, se seleccionaron aquellos que brindaron un mejor resultado, el conjunto de parámetros se muestra a continuación en la Tabla 6.1: Evaluaciones: 50000 K: 30 p5a: 0.65 p6b: 0.75 p6bii: 0.25 p6c: 0.4 ideas: 100 y clusters: 5 Tabla 6.1 Conjunto de parámetros con los que se obtuvieron mejores resultados. Una razón más para elegir estos parámetros es que permitieron que el algoritmo se comportara de manera robusta, es decir, a lo largo de todas las ejecuciones, la varianza entre la función de aptitud en cada ejecución ha sido menor que con otro conjunto de parámetros. Después de resolver el primer problema de optimización con los parámetros de la Tabla 6.1, se obtuvieron las soluciones que se presentan en la Tabla 6.2. Página 47 Corrida 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 p1 0.49996415 0.46347742 0.46091618 0.39700076 0.48397725 0.42844804 0.45978372 0.4749513 0.40958773 0.48678905 0.49167138 0.48173922 0.49670925 0.4700652 0.49496222 0.43190159 0.49999325 0.47859701 0.3516045 0.45066818 0.42283574 0.46331076 0.48935879 0.47221509 0.49543631 0.48349379 0.4984191 0.43316221 0.41131106 0.48607084 p2 0.124819829 0.123933391 0.111196204 0.101327318 0.127270547 0.120086323 0.12749509 0.104158453 0.05661672 0.099204887 0.112430002 0.134685255 0.123901707 0.09073854 0.136188001 0.115353302 0.127871179 0.135691878 0.086338741 0.120635821 0.084524998 0.105918246 0.137378933 0.118868281 0.114179056 0.097632102 0.131594687 0.113190531 0.108663465 0.130699144 p3 0.49996421 0.46347751 0.46091623 0.39700078 0.48397758 0.42844811 0.45978375 0.47495142 0.40958778 0.4867891 0.49167154 0.48173928 0.49670933 0.47006521 0.49496233 0.43190161 0.49999332 0.47859701 0.35160464 0.45066837 0.42283585 0.46331086 0.48935885 0.47221514 0.49543634 0.48349385 0.49841926 0.43316237 0.41131114 0.48607087 p4 0.21953928 0.22550996 0.19287495 0.1800021 0.22947229 0.22517251 0.23728001 0.17503666 0.0874589 0.16352404 0.19133391 0.25209515 0.21790432 0.14776836 0.25215236 0.20975667 0.2273697 0.25661985 0.15080266 0.21964264 0.1386457 0.18034133 0.25789736 0.20983006 0.19481463 0.16052787 0.23777573 0.20341391 0.1964077 0.23858263 teta1 -0.1881153 -0.21167712 -0.17791621 -0.19511195 -0.20543627 -0.23160797 -0.22671115 -0.15329553 -0.08376817 -0.13727202 -0.16412781 -0.23044261 -0.18715736 -0.1259499 -0.22330523 -0.2112216 -0.19578697 -0.23713764 -0.18316836 -0.21208246 -0.1350944 -0.16214145 -0.23236344 -0.19067473 -0.16601054 -0.13688835 -0.20690043 -0.20317157 -0.20712187 -0.21383807 f.obj 1.52053038 1.42191928 1.56356607 1.49070873 1.44764042 1.34159132 1.36106859 1.66789879 1.99910696 1.73634607 1.62529688 1.34621159 1.52073309 1.78128563 1.37470965 1.42378568 1.48793008 1.31979185 1.54188366 1.42023851 1.75446002 1.62347911 1.33860088 1.5095853 1.61670707 1.74564439 1.4415888 1.45705526 1.44063926 1.41307524 Tabla 6.2 Conjunto de resultados obtenidos en el primer problema de optimización (maximización). Todas las soluciones son factibles. El mejor resultado obtenido se encuentra en color rojo. Página 48 Finalmente, en la Tabla 6.3 se muestran las estadísticas obtenidas de los resultados de la Tabla 6.2. Mejor Peor Promedio Mediana Varianza 1.999106961 1.319791852 1.524435952 1.489319404 0.025020211 Tabla 6.3 Datos estadísticos obtenidos del conjunto de resultados de la Tabla 6.2 para el primer problema de optimización (maximización). Para el problema de minimización se utilizaron los mismos parámetros que para el problema de maximización, lo que muestra la baja sensibilidad del algoritmo al resolver diferentes instancias del problema mecatrónico (ver Tabla 6.1). En la Tabla 6.4 se presentan los resultados de las ejecuciones del problema de minimización. Página 49 Corrida p1 p2 p3 p4 teta1 f.obj 1 0.49957044 0.050000087 0.49957045 2 0.49999777 0.050000059 0.49999778 0.24276056 -0.24517297 0.20668106 0.2741357 -0.27853271 0.22228729 3 0.49871239 0.050000063 0.49871246 0.26513622 -0.26947672 0.21723212 4 0.49999999 0.050000035 0.49999999 0.22327689 -0.21566097 5 0.49999985 0.050000003 0.49999995 0.26497184 6 0.49999965 0.050000085 0.49999967 0.24437835 -0.24687766 0.20717707 7 0.49935732 0.050000056 0.49935733 0.23589511 -0.23822604 0.20527493 8 0.49750936 0.050000011 0.49750938 0.26611714 -0.27117296 0.21853002 9 0.49999149 0.050000112 0.49999152 10 0.46014432 0.050000077 0.46014434 0.21385108 -0.22433752 0.22172524 11 0.47732117 0.050000031 0.47732117 0.21750152 -0.22491332 0.21358014 12 0.4999998 0.050000025 0.49999982 0.22280415 -0.21759964 0.20369625 13 0.48069561 0.050000039 0.48069566 0.21992983 -0.22637558 0.21205322 14 0.49999958 0.050000042 0.49999961 0.23942679 -0.24165889 0.20576926 15 0.48472891 0.050000011 0.48472894 0.25973039 -0.27141944 0.22267784 16 0.49999943 0.05000009 0.49999952 0.30777783 -0.31400318 0.24970236 17 0.49983428 0.050000047 0.49983438 0.29196567 -0.29728563 0.23552279 18 0.47058721 0.050000054 0.47058724 0.24472775 -0.26276552 0.22353916 19 0.49999983 0.050000076 0.49999987 0.24469324 -0.24711257 0.20727781 20 0.4999998 0.050000002 0.49999983 0.22307318 -0.21704992 0.20369425 21 0.49999983 0.050000048 0.49999985 22 0.49038675 0.050000012 0.49038676 0.23103015 -0.23470877 0.20859907 23 0.49548322 0.050000097 0.49548323 0.21353513 -0.20664979 0.20629629 24 0.46670755 0.050000039 0.46670759 0.21650421 -0.22681096 0.21854341 25 0.49999987 0.050000009 0.49999989 0.22862951 -0.22733258 0.20392717 26 0.49999981 0.050000075 0.49999985 0.24794331 -0.25032961 0.20839438 27 0.49577534 0.050000022 0.49577536 0.22368821 -0.22387079 0.20547865 28 0.4902182 0.050000041 0.49021821 0.23398427 -0.24062562 0.20923772 29 0.49999893 0.050000011 0.49999895 0.23107544 -0.23247348 0.20418947 30 0.49970063 0.050000031 0.49970064 0.26047509 0.2036936 -0.2686038 0.21637024 0.2945144 -0.29989757 0.23756508 0.2606946 -0.26408643 0.21404775 -0.2640136 0.21410559 Tabla 6.4 Conjunto de resultados obtenidos en el segundo problema de optimización (minimización). Todas las soluciones son factibles. El mejor resultado obtenido se encuentra en color rojo. A continuación se muestran en la Tabla 6.5 las estadísticas derivadas de las ejecuciones de la función de minimización. Página 50 Mejor Peor Promedio Mediana Varianza 0.203693595 0.249702362 0.214228974 0.210645471 0.000122274 Tabla 6.5 Datos estadísticos obtenidos del conjunto de resultados de la Tabla 6.4 para el segundo problema de optimización (minimización). 6.2 Discusión De acuerdo a los experimentos preliminares realizados para obtener valores adecuados para los parámetros del algoritmo BSO, pareciera que el valor inicial k es el que ocasiona un mayor cambio en los resultados. Es importante recordar que k se relaciona con el salto o tamaño de paso y se traduce en la velocidad con que el algoritmo converge, es decir la rapidez con la que todas las ideas (soluciones) comienzan a coincidir. El tamaño de paso es usualmente un parámetro sensible en los algoritmos bioinspirados y parece ser que para BSO también se presenta tal fenómeno. Lo que parece funcionar mejor es promover valores de k que favorezcan tamaños de paso pequeños y acotados por los límites inferiores y superiores de las variables de diseño del problema de optimización. Un aspecto importante a considerar en BSO es el manejo de la diversidad, al igual que el proceso humano de lluvia de ideas recomienda que participen personas con conocimientos diferentes que generen el mayor número de ideas posibles, el algoritmo funcionará mejor cuando las ideas se encuentren dispersas durante la mayor parte del proceso de búsqueda y en cuanto a la Página 51 modificación de ideas, es preferible combinar las de dos clusters diferentes que combinar dos ideas del mismo cluster, ya que éstas tienden a ser parecidas. La probabilidad P5a promueve la diversidad en el algoritmo, pues brinda la posibilidad de generar un nuevo centroide de manera aleatoria y por lo tanto trasladar un cluster de un lugar a otro, explorando así áreas nuevas donde pueda buscarse y en el mejor de los casos encontrarse una solución mejor. Por lo tanto es recomendable que P5a contenga valores relativamente altos, recordando que las probabilidades pueden tomar valores entre 0 y 1, el valor recomendado para P5a es 0.65; un valor más cercano a 1 provocaría el constante movimiento de los clusters pero sin darles el tiempo necesario para realizar una explotación satisfactoria de la región analizada. P6b es el parámetro del que depende si se trabajará con un solo cluster o la unión de ambos, por lo que representa la posibilidad de combinar ideas de diferentes clusters, lo cual pareciera ser deseable. Sin embargo, trabajar con un solo cluster ha brindado mejores resultados en el algoritmo para los problemas de optimización resueltos en este trabajo de tesis. En contraste con P5a, que se encarga de encontrar nuevos zonas sin explorar, P6b permite explotar zonas ya conocidas, incluso combinando información de dos zonas ya exploradas más no necesariamente explotadas. P6bii controla la generación de una nueva idea a partir de un centroide o de una solución aleatoriamente seleccionada de ese cluster. Una vez más, para promover la diversidad es mejor derivar la nueva idea a partir de la escogida de manera aleatoria en el cluster, pero que no sea el centroide, por lo cual se recomienda que esta probabilidad sea baja. El valor seleccionado para el algoritmo es de 0.25. Página 52 Un valor alto del parámetro P6c indica que se generará una idea nueva a partir de la combinación de dos centroides. En el caso contrario (un valor bajo) implica que se usarán dos soluciones escogidas aleatoriamente, una por cada cluster. Lo recomendable en este caso para favorecer diversidad sería que la idea nueva se generara a partir de la combinación de dos ideas escogidas aleatorias, una de cada cluster, por lo que para este parámetro también se recomienda que tenga un valor bajo. Como se ha analizado, los valores de los parámetros se enfocaron en promover la diversidad, es decir la exploración de nuevas zonas para evitar óptimos locales y así omitir alguna buena solución. Esto lleva a pensar que el algoritmo BSO, al menos para el tipo de problemas de optimización aquí resueltos, tiende a converger prematuramente si no se controlan adecuadamente sus parámetros. 6.3 Comparativa Con anterioridad, se ha tratado de resolver el problema mecatrónico objeto de interés en el presente trabajo mediante un algoritmo evolutivo llamado evolución diferencial [16], obteniendo una aptitud de 1.60251619 en el conjunto de datos reportado como el mejor obtenido usando también 50,000 evaluaciones. A continuación en la Tabla 6.7 se presentan los valores sugeridos tanto para las longitudes de los cuatro eslabones (p1 a p4), como para el ángulo p1 p2 p3 p4 p5 (p5). Func_obj 0.49999999984790 0.11671204534865 0.49999999985041 0.20000000004315 -0.16931779839141 1.60251619195312 Tabla 6.6 Valores Obtenidos con Evolución Diferencial para el problema de maximización. Página 53 En cambio BSO ofrece una aptitud de 1.99910696 y sugiere las siguientes longitudes y ángulo (ver Tabla 6.7): p1 p2 p3 p4 p5 Func_obj 0.40958772876021 0.05661671985166 0.40958778149574 0.08745890030250 -0.08376817167463 1.99910696096319 Tabla 6.7 Valores Obtenidos con BSO para el problema de maximización. Retomando el Capítulo 3, la función de maximización representa el desplazamiento del balancín, y precisamente lo ideal es que éste sea lo más grande posible con el fin de maximizar la transferencia de energía de entrada del motor, como se puede apreciar en las Tablas 6.6 y 6.7, BSO aporta un resultado considerablemente mejor que la evolución diferencial. La aptitud obtenida mediante evolución diferencial para la función de minimización del problema mecatrónico es de 0.20369337, y las correspondientes medidas para las longitudes de los eslabones y el ángulo de dicho problema se aprecian en la Tabla 6.8: p1 p2 p3 p4 p5 func_obj 0.50000000000000 0.05000000000000 0.50000000000000 0.22335685188079 -0.21660995419566 0.20369337272871 Tabla 6.8 Valores Obtenidos con Evolución Diferencial para el problema de minimización. Mientras que la aptitud obtenida con BSO es de 0.20369359, en este caso, los dos algoritmos ofrecen una solución muy similar, por lo que en este caso particular no se puede decir que uno se comporte mejor que el otro (ver Tabla 6.9). p1 p2 p3 p4 p5 func_obj 0.49999998507702 0.05000003511475 0.49999998943171 0.22327689282280 -0.21566097005284 0.20369359524221 Tabla 6.9 Valores Obtenidos con BSO para el problema de minimización. Página 54 7. Conclusiones y Trabajo Futuro En este trabajo se implementó el algoritmo BSO para optimizar el diseño de un mecanismo de cuatro barras. El algoritmo se adaptó para poder resolver dos problemas de optimización con restricciones usando tres reglas de factibilidad encontradas en la literatura especializada. Se realizó un análisis empírico para determinar valores adecuados de los parámetros del algoritmo, donde se concluyó que tales valores deben apuntar a mantener diversidad en la mayor parte del proceso de optimización y así evitar caer en óptimos locales. Finalmente, se compararon los resultados obtenidos contra los reportados por otros autores usando el algoritmo de evolución diferencial, considerando un número similar de evaluaciones. De dicha comparación se concluyó que BSO fue capaz de obtener mejores resultados en el problema de maximización de la transferencia de energía del sistema e igualar los resultados en el problema de minimización que tiene que ver con la calidad del funcionamiento del sistema. Es importante remarcar que evolución diferencial es un algoritmo evolutivo altamente competitivo, por lo que es meritorio que un algoritmo relativamente nuevo como BSO provea de resultados iguales, e incluso mejores, con respecto a los obtenidos con dicho algoritmo evolutivo. Finalmente, quedan aspectos que no fueron atendidos y que dejan un espacio abierto para futuros trabajos, tales como la calibración de parámetros con herramientas especializadas como iRace [24], así como aplicar una técnica diferente para formar clusters. Finalmente se pretende utilizar diferentes distribuciones para generar números aleatorios en la conformación de nuevas ideas. Página 55 Referencias [1] A. Ravindran, K.M. Ragsdell, and G.V Reklaitis, Engineering Optimization, Methods and Applications, Wiley, 2006. [2] Z. Michalewicz and D.B. Fogel, How to Solve It: Modern Heuristics, Springer, 2nd Edition, 2004. [3] A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing, Springer, 2003. [4] A.P. Engelbrecht, Fundamentals of Computational Swarm Intelligence, Wiley, 2005. [5] Y. Shi, An Optimization Algorithm Based on Brainstorming Process, International Journal of Swarm Intelligence Research, 2(4):35-62, 2011. [6] C. Morales-Cruz, R.A. Suárez-Santillán, B. Hernández-Ocaña, E. MezuraMontes, E.A. Portilla-Flores, M.G. Villarreal-Cervantes, Optimización del mecanismo de entrada de una Transmisión de Variación Continua comparando Evolución Diferencial y Forrajeo de Bacterias Modificado, en Memorias del 10o Congreso Nacional de Mecatrónica, Puerto Vallarta, México, pp. 61-65, ISBN: 978-607-95347-6-9, Noviembre 2011. [7] E.A. Portilla-Flores, E. Mezura-Montes, J. Álvarez Gallegos, C.A. Coello Coello, C.A. Cruz-Villar and M.G. Villareal-Cervantes, Parametric Reconfiguration Improvement in Non-Iterative Concurrent Mechatronic Design Using an Evolutionary-Based Approach, Engineering Applications of Artificial Intelligence, 24(5):757-771, 2011. [8] Ma. Guadalupe Martínez-Peñaloza, Un estudio empírico de dos algoritmos evolutivos para clustering multi-objetivo , Universidad Veracruzana, Pp 20-21. Página 56 [9] Yuhui Shi, Jingqian Xue, Yali Wu, Multi-Objective Optimization Based on Brain Storm Optimization Algorithm, International Journal of Swarm Intelligence Research, 4(3), 1-21, July-September 2013 [10] Yuhui Shi, Brain Storm Optimization Algorithm, Y. Tan et al. (Eds.): ICSI 2011, Part I, LNCS 6728, pp. 303–309, 2011. [11] Carrillo Higueras, Franz Joaquín, Una heurística robusta para la planificación de la producción: desarrollo y aplicación a un caso real, 2008 [12] Iztok Fister Jr., Xin-She Yang, Iztok Fister, Janez Brest, Duˇsan Fister, A Brief Review of Nature-Inspired Algorithms for Optimization, ELEKTROTEHNIˇSKI VESTNIK 80(3): 1–7, 2013. ENGLISH EDITION [13] Ajith Abraham, Swagatam Das, and Sandip Roy, Swarm Intelligence Algorithms for Data Clustering, Soft Computing for Knowledge Discovery and Data Mining 2008, pp 279-313 [14] Tao J., Sadler J.P., “Constant Speed Control of a Motor Driven Mechanism System”, Mechanism and Machine Theory, Vol. 30, No. 5, pp. 737-748, 1995. [15] J. E. Shigley, J.J. Uicker Jr., Teoría de máquinas y mecanismos, Mc Graw Hill, México, 1994. [16] Portilla Flores Edgar Alfredo, Diseño óptimo de un mecanismo de cuatro barras: un enfoque dinámico, 2013 [17] Habib Youssef, Sadiq M. Sait, HakimAdiche, Evolutionary algorithms, simulated annealing and tabu search: a comparative study, Engineering Applications of Artificial Intelligence 14 (2001) 167–181 [18] Kennedy James , Eberhart Rusell C., Swarm Intelligence, Academic Press, 2001 [19] Abdolreza Hatamlou. Black hole: A new heuristic optimization approach for data clustering. Information Sciences, 2012. Página 57 [20] Richard A Formato. Central force optimization: A new metaheuristic with applications in applied electromagnetics. Progress In Electromagnetics Research, 77:425–491, 2007. [21] Erik Cuevas, Diego Oliva, Daniel Zaldivar, Marco Pérez-Cisneros, and Humberto Sossa. Circle detection using electromagnetism optimization. Information Sciences, 182(1):40–55, 2012. [22] Esmat Rashedi, Hossein Nezamabadi-Pour, and Saeid Saryazdi.Gsa: a gravitational search algorithm. Information sciences, 179(13):2232–2248, 2009. [23] H Shayeghi and J Dadashpour. Anarchic society optimization based pid control of an automatic voltage regulator (avr) system. Electrical and Electronic Engineering, 2(4):199–207, 2012. [24] Manuel López-Ibáñez, Jérémie Dubois-Lacoste, Thomas Stützle, and Mauro Birattari. The irace package, Iterated Race for Automatic Algorithm Configuration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Université libre de Bruxelles, Belgium, 2011. [25] Kalyanmoy Deb. An Efficient Constraint Handling Method for Genetic Algorithms. Computer Methods in Applied Mechanics and Engineering, Vol. 186, No. 2/4, pp. 311--338, 2000. Página 58