Source: http://patentados.com/patente/procedimiento-sistema-resolucion-problemas-optimizacion-mediante-redes.1/
Timestamp: 2016-10-23 01:27:08+00:00

Document:
PROCEDIMIENTO Y SISTEMA PARA LA RESOLUCION DE PROBLEMAS DE OPTIMIZACION MEDIANTE REDES DE DISPOSITIVOS MOVILES. (1)
PROCEDIMIENTO Y SISTEMA PARA LA RESOLUCION DE PROBLEMAS DE OPTIMIZACION MEDIANTE REDES DE DISPOSITIVOS MOVILES.Procedimiento y sistema para la resolución de problemas de optimización mediante redes de dispositivos móviles que consiste en el aprovechamiento de la capacidad de computación de los dispositivos móviles y la comunicación mediante el estándar Bluetooth{reg} para la transferencia de datos en un entorno distribuido donde todos los dispositivos cooperan para la resolución de problemas complejos. El procedimiento de la invención que se plantea consiste en ejecutar algoritmos bioinspirados en dispositivos móviles que se comunican mediante la tecnología Bluetooth{reg}. Cada dispositivo se comunica con los demás sin la intervención de ningún servidor central que gestione todo el proceso, o bien, en una arquitectura cliente - servidor (o maestro - esclavo) en donde el servidor es una computadora central que ejecutará un determinado algoritmo de optimización mientras que los clientes (los dispositivos móviles) ejecutarán algoritmos bioinspirados de forma independiente.Tipo: Patente de Invención. Resumen de patente/invención. Número de Solicitud: P201100062. Solicitante: UNIVERSIDAD DE MALAGA.Nacionalidad solicitante: España.Inventor/es: FERNÁNDEZ LEIVA,Antonio José, COTTA PORRAS,Carlos.Fecha de Publicación: 9 de Enero de 2014.Clasificación Internacional de Patentes:SECCION G — FISICA > COMPUTO; CALCULO; CONTEO > TRATAMIENTO DE DATOS DIGITALES ELECTRICOS (computadores... > G06F1/00 (Detalles no cubiertos en los grupos G06F 3/00 - G06F 13/00 y G06F 21/00 (arquitecturas de computadores universales con programas grabados G06F 15/76))
facebookPin itFragmento de la descripción: PROCEDIMIENTO Y SISTEMA PARA LA RESOLUCIÓN DE PROBLEMAS DE OPTIMIZACIÓN MEDIANTE REDES DE DISPOSITIVOS MÓVILES DESCRIPCIÓN 5 Es un objeto de la presente invención un procedimiento y un sistema para el aprovechamiento de la capacidad de computación de los dispositivos móviles y la comunicación mediante el estándar Bluetooth® para la transferencia de datos en un entorno distribuido donde todos los dispositivos cooperan para la resolución de problemas complejos. El procedimiento de la 1 O invención que se plantea consiste en ejecutar algoritmos bioinspirados en dispositivos móviles que se comunican mediante tecnología inalámbrica, preferentemente Bluetooth® o similar. Cada dispositivo se comunica con los demás sin la intervención de ningún servidor central que gestione todo el proceso, o bien, en una arquitectura cliente -servidor (o maestro - esclavo) en donde el servidor es una computadora central que ejecutará un determinado 15 algoritmo BnB (Branch and Bound, ramificación y poda) mientras que los clientes (los dispositivos móviles) ejecutarán algoritmos bioinspirados de forma independiente. ESTADO DE LA TÉCNICA ANTERIOR 2 O Bajo el término de algoritmos bioinspirados se engloba a un amplio conjunto de técnicas de resolución de problemas de optimización complejos basadas en la emulación de los procesos naturales de la biología. Entre las técnicas bioinspiradas se encuentran por ejemplo los algoritmos evolutivos, las redes neuronales, los sistemas de lógica difusa y las colonias de hormigas entre otros. Estos algoritmos son llamados así porque se inspiran en procesos 2 5 biológicos y algunos de ellos, en concreto los algoritmos evolutivos, particularmente en su base genético-molecular. Se ha demostrado que, en problemas de optimización, estas técnicas alcanzan soluciones óptimas (o cercanas a las óptimas) con un coste computacional aceptable que es muchas veces menos que el que consumen otras muchas técnicas de resolución de problemas de optimización. 30 Por otra parte, las técnicas de Ramificación y Poda (BnB, por sus siglas en inglés Branch and Bound) son ampliamente utilizadas en la resolución de problemas de optimización. Muy básicamente, estas técnicas realizan una enumeración parcial del espacio de soluciones basándose en la generación de un árbol de expansión implícito. Inicialmente, se considera un 3 5 nodo que representa el espacio de soluciones completo y que, sucesivamente, es ramificado en otros nodos que representan particiones del espacio de búsqueda original. Adicionalmente, se utilizan cotas para podar aquellas ramas del árbol que no conducen a la solución óptima, reduciendo considerablemente el espacio de búsqueda. Básicamente en un algoritmo de Ramificación y Poda se realizan tres etapas. La primera de ellas, denominada Selección, se encarga de extraer un nodo de entre el conjunto de nodos 5 vivos. La forma de escogerlo varía dependiendo directamente de la estrategia de búsqueda que decidamos para el algoritmo. En la segunda etapa, la Ramificación, se construyen los posibles nodos hijos del nodo seleccionado en el paso anterior. Por último se realiza la tercera etapa, la Poda, en la que se eliminan algunos nodos creados en la etapa anterior. Esto contribuye a disminuir en lo posible el espacio de búsqueda y así atenuar la complejidad de estos 1 O algoritmos basados en la exploración de un árbol de posibilidades. Aquellos nodos no podados pasan a formar parte del conjunto de nodos vivos, y se comienza de nuevo por el proceso de selección. El algoritmo finaliza cuando no quedan más nodos por explorar. Para cada nodo del árbol dispondremos de una función de coste que nos estime el valor 15 óptimo de la solución si continuáramos por ese camino. De esta manera, si la cota que se obtiene para un nodo, que por su propia construcción deberá ser mejor que la solución real (a lo sumo, igual que ella) , es peor que una solución ya obtenida por otra rama, podemos podar esa rama pues no es interesante seguir por ella. Evidentemente no podremos realizar ninguna poda hasta que hayamos encontrado alguna solución. Por supuesto, las funciones de coste han 2 O de ser monótonas respecto a la profundidad del árbol, es decir, si consideramos por ejemplo un problema de minimización, entonces si h es una función de coste entonces h (n) <= h (n') para todo n' nodo descendiente den. 2 5 Recientemente, los firmantes de la invención aquí descrita han especificado en su artículo ("On the Hybridization of Memetic Algorithms With Branch-and-Bound Techniques", IEEE Transactions on Systems, Man, and Cybernetics, Part B 37 (1) : 77-83, 2007) un modelo híbrido paralelizable entre estas una técnica de BnB y un algoritmo bioinspirado (concretamente un algoritmo genético AG) que ha resultado ser exitoso en la resolución de 3 O problemas de optimización. Este modelo o procedimiento de cómputo considera dos formas diferentes de abordar los problemas de optimización combinatoria que no son excluyentes y pueden trabajar juntas para resolver un problema determinado. La integración entre los dos algoritmos se lleva a cabo mediante una fase de comunicación en la que el AG envía su mejor solución al BnB y viceversa, el BnB envía al AG un conjunto de soluciones parciales 3 5 prometedoras convertidas en soluciones completas mediante técnicas ávidas. El BnB usa la solución recibida para realizar el proceso de poda en la cola de nodos vivos, eliminando los problemas parciales cuya cota superior sea inferior a la solución hallada por el AG. El BnB O 5 O inyecta información de las regiones más prometedoras del árbol de búsqueda en la población del AG, de forma que siempre haya una población heterogénea en las generaciones del AG. Por otro lado, Bluetooth® es una tecnología de comunicación inalámbrica que define una plataforma estandarizada en la que destaca el bajo consumo y bajo coste de sus elementos, facilitando una comunicación sin cables entre dispositivos móviles. Se incluye dentro de la especificación de esta tecnología tanto los detalles de cómo se ha de llevar a cabo el enlace de comunicación entre los dispositivos, como los detalles de la capa de aplicación por la que se podrá explotar las funcionalidades de estas comunicaciones. Bluetooth® opera en el rango de radiofrecuencia de los 2.4GHz (2.400-2.4835 GHz) que no requiere licencia de uso en ningún lugar del mundo. Se guarda una banda de 2 MHz en el comienzo y 3.5 MHz final del rango para cumplir con las regulaciones de todos los países. La tecnología de comunicaciones Bluetooth® hace posible la transmisión de voz y datos entre diferentes dispositivos mediante un enlace de radiofrecuencia. Estos dispositivos deben llevar integrado hardware específico para dar soporte a esta tecnología. Entre los dispositivos más comunes encontramos teléfonos móviles, computadoras de mano (Palm, Pocket PC) , cámaras digitales, ordenadores portátiles e impresoras. EXPLICACIÓN DE LA INVENCIÓN El problema técnico objetivo que soluciona la presente invención es el incremento de la velocidad de cómputo en la resolución de problemas de optimización en la asignación de recursos, aprovechando de forma distribuida una pluralidad de elementos móviles, en donde todos los dispositivos cooperan en dicha resolución. En la presente invención se entiende por dispositivo móvil tanto PDAs, como teléfonos móviles, ordenadores portátiles, Smartphone, o cualquier dispositivo móvil con capacidad de comunicación inalámbrica vía Bluetooth®. Más... Reivindicaciones: 12 1. Procedimiento para la resolución de problemas de optimización mediante redes de 5 dispositivos móviles mediante el incremento de la velocidad de cómputo en la resolución de problemas de optimización en la asignación de recursos. aprovechando de forma distribuida una pluralidad de dispositivos móviles, en donde todos los dispositivos cooperan en la resolución de una instancia o variable del problema de optimización que se caracteriza porque (a) comprende al menos una red de dispositi vos móviles para cada instancia o variable de un 10 problema de optimización a resolver, (b) donde cada uno de los dispositivos móviles de la red implementa de forma independi ente un algoritmo de optimización dedicado a la resolución de una única instancia o variable del problema de optimización, (e) de tal fonna que cuando un dispositivo móvil de la red actuando en modo cliente o esclavo se encuentra dentro del radio de alcance de otro dispositivo actuando en modo servidor o maestro se establece una 15 comunicación entre ambos dispositivos (d) mediante transferencia de candidatos a soluciones (obtenidas por los algoritmos ejecutados en cada uno de los dichos dispositivos móviles) para la instancia o variable que mediante la red de dispositivos móvi les se trata de resolver en el contexto del problema de optimización en cuestión. 20 2. Procedimi ento de acuerdo con la reivindicación anterior que se caracteriza porque un mismo dispositivo móvil de la red pueden adoptar el rol (o funcionar en modo) de (a) cliente o esclavo, en cuyo caso el dispositivo tomará la iniciativa en las comunicaciones realizando la búsq ueda de dispositivos y servicios y se conectará a algún dispositivo o servicio que esté resolviendo la instancia o variable actual en viando individuos O candidatos a 25 soluciones al dispositivo o servicio con el que el dispositivo cliente conecte; o de (b) servidor O maestro, donde el dispositivo queda a la escucha para que un dispositivo cliente se pueda conectar a él y le transmita individuos o candidatos a soluciones; pudiendo el mismo dispositivo adoptar (e) ambos roles simultáneamente, en cuyo caso el dispositivo podrá tanto tomar la iniciativa en las comunicaciones (modo O rol cliente) como quedar escuchando 3 O conexiones (modo o rol servidor) . 3. Procedimiento de acuerdo con cualquiera de las rei vindicaciones anteriores que se caracteriza porque el algoritmo de optimización es un algoritmo bioinspirado o bien un algoritmo de ramificación y poda. 35 4, -Procedimiento de acuerdo con la reivindicación anterior que se caracteriza porque el algoritmo bioinspirado es un algoritmo genético. 5. Procedi miento de acuerdo con la reivindicación que se caracteriza porque la comunicación entre los dispositivos se realiza de forma sincrona o asíncrona. . 6. Procedimiento de acuerdo con las reivindicaciones anteriores que se caracteriza porque puede existir más de una piconet involucrada en el esquema global de res~lución dando lugar a subestructuras que se comunican mediante dispositivos esclavos comunes a las piconets entre las cuales se establece la comunicación. 7. Procedimiento de acuerdo con cualquiera de las reivindicaciones anteriores que se caracteriza porque comprende además al menos un dispositivo que consiste en un servidor o computador central que implementa un algoritmo de optimización dedicado a la resolución de una única instancia o variable del problema de optimización, pudiendo dicho computador central adoptar los roles de (a) servidor o maestro, donde el dispositivo queda a la escucha para que un dispositivo cliente se pueda conectar a él y le transmita individuos o candidatos a soluciones; o de (b) cliente o esclavo, en cuyo caso el dispositivo tomará la iniciativa en las comunicaciones realizando la búsqueda de dispositivos y servicios, y se conectará a algún dispositivo o servicio que esté resolviendo la instancia o variable actual enviando individuos o candidatos a soluciones al dispositivo o servicio con el que el dispositivo cliente conecte; pudiendo el mismo dispositivo adoptar (e) ambos roles simultáneamente, en cuyo caso el dispositivo podrá tanto quedar escuchando conexiones (modo o rol servidor) como tomar la iniciativa en las comunicaciones (modo o rol cliente) . 8, -Procedimiento de acuerdo con la reivindicación anterior caracterizado porque (a) tanto el computador central como cada uno de los dispositivos móviles de la red implementan de forma independiente un algoritmo de optimización dedicado a la resolución de una única instancia o variable del problema de optimización, (b) de tal forma que cuando un dispositivo móvil de la red actuando en modo cliente o esclavo se encuentra dentro del radio de alcance del computador central actuando en modo servidor o maestro se establece una comunicación entre ambos dispositivos Ce) mediante transferencia de candidatos a soluciones (para la instancia o variable que mediante la red de dispositivos móviles se trata de resolver en el contexto del problema de optimización en cuestión) desde el dispositivo móvil hacia el computador central y desde el computador central a cada uno de los dispositivos móviles con el fin de mejorar la búsqueda de soluciones de forma independiente en cada uno de ellos. 3. 9. Procedimiento de acuerdo con cua1quiera de las reivindicaciones 7 u 8 que se caracteriza porque el algoritmo de optimización que implementa cada uno de los dispositivos AS solicitud F.Efectlva 18/07/2013 14 móviles es un algoritmo bioinspirado y el algoritmo de optimización que implementa el computador central es un algoritmo de ramificación y poda. 5 10. Procedimiento de acuerdo con la reivindicación anterior que se caracteriza porque el algoritmo de optimización que implementa cada unO de los dispositivos móviles es un algoritmo genético. 10 15 II.~ Sistema para la reso lución de problemas de optimización mediante redes de dispositivos móviles que comprende medios para implementar el procedimiento de las reivindicaciones I a 10 que se caracteriza porque cada dispositivo móvil comprende, al menos, dos subsistemas que se lanzan en hebras independientes y donde estos subsistemas cooperan entre sí y realizan labores claramente diferenciadas: el subsi stema de ejecución del algoritmo de optimización cuya función es la de instanciar un problema y ejecutar su resolución; y el subsistema de comunicaciones, el cual desacopla la ejecución del algoritmo del proceso de comunicaciones, que se reali za de forma independiente. 2 O 12.~ Sistema de acuerdo con la rei vi ndicación anterior que se caracteriza porque el subsistema de comunicaciones se compone de dos módulos principales que realizan las labores de cliente uno y de servidor el otro, ambos utilizan el protocolo SPP para comunicarse; y donde para adquirir el ro] de cliente, tendrá que estar activo el módulo de cliente, para adquirir el rol de servidor, tendrá que estar activo el módulo de servidor y para adquirir el rol P2P cliente/servidor, tendrán que estar activos ambos módulos. 25 << Patente anterior (8 de Enero de 2014)Patente siguiente (9 de Enero de 2014) >>
Otras patentes de UNIVERSIDAD DE MALAGA1. Sistema electrónico para la medición de gases. (09 Dic. 2015)2. Silla de ruedas plegable. (01 Dic. 2015)3. Métodos implementados en computador y sistemas informático de activación y desactivación automáticas de transmisiones concurrentes de datos entre dispositivos conectados a una red. (11 Nov. 2015)4. Deshidratación de sorbitol a isosorbida en ausencia de disolvente mediante catálisis heterogénea usando resinas sulfónicas como catalizadores. (16 Oct. 2015)5. Firma de microarn como indicador del riesgo de recurrencia temprana en pacientes con cáncer de mama. (15 Oct. 2015)6. Unidades aritméticas y conversores asociados. (01 Oct. 2015)7. Sistema robótico de asistencia a la cirugía mínimamente invasiva de puerto único capaz de acomodar su movimiento a la anatomía de la pared abdominal. (30 Sep. 2015)8. Unidades aritméticas en coma fija y conversores asociados. (29 Sep. 2015)9. Sumadores coma flotante y conversores. (29 Sep. 2015)10. Dispositivos coma flotante y conversores. (29 Sep. 2015)11. Dispositivos para operaciones de multiplicación-suma fusionadas en coma flotante y conversores asociados. (29 Sep. 2015)12. Multiplicadores coma flotante y conversores asociados. (29 Sep. 2015)13. Firma de microarn como indicador del riesgo de recurrencia temprana en pacientes con cáncer de mama. (17 Sep. 2015)14. Uso de anticuerpos frente a la enzima sod-3 para la inhibición del proceso de la angiogénesis y aplicaciones de dichos anticuerpos y de dicha enzima sod-3. (16 Sep. 2015)15. Dispositivo para la fijación del injerto en mosaicoplastia de tracción. (27 Jul. 2015)16. Kit para mosaicoplastia de tracción. (02 Jul. 2015) Patente actualizada el 11 de Agosto de 2014. Inventos patentados en España en los últimos 80 años. Clasificación Internacional de Patentes CIP 2015. · Inventos patentados en España. Acerca de · Contacto · Patentados.com desde 2007 hasta 2016 // Última actualización: 20/10/2016.

References: resolución 
 resolución 
 RESOLUCIÓN 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución 
 resolución