Método de determinación del arreglo óptimo
Descripción general
 Las estructuras tridimensionales con polígonos como componentes se generan automáticamente usando una computadora. ] Primero, ingrese la configuración inicial y las condiciones de restricción 11. Posteriormente, la población inicial fue generado mediante el establecimiento de la etapa de entrada condición inicial 11, 12 inicializa el número de generaciones para generar una estructura tridimensional mediante la aplicación de la regla de la disposición de polígono decodifica al gen estructural inicial, Realizar la visualización 14. A continuación, 15 a la inversa de la energía calculada y se obtuvo como hay átomo en cada vértice del polígono como el valor de evaluación, y seleccionar el alto valor de evaluación individual como padre, nuevos individuos sometidos a cruce, etc. al gen 16. Si el número de generaciones excede el número de generaciones dado en la etapa de evaluación final 17, el programa finaliza. De lo contrario, regrese al paso 14 de visualización de ocurrencia. ] Se espera que descubra estructuras que nadie podría imaginar. Además, al habilitar la configuración de la estructura inicial, es posible orientar la evolución hasta cierto punto.
Campo técnico
La presente invención se refiere a una determinación de disposición óptima para generar automáticamente una estructura tridimensional en una computadora determinando los elementos constitutivos de una estructura tridimensional como un polígono y determinando la disposición del polígono usando una técnica de optimización. Método.
Antecedentes de la técnica
La generación de estructuras tridimensionales es una tecnología requerida en muchos campos, como el arte CG y la predicción de estructura de estructuras atómicas sólidas. Normalmente, el diseñador crea un mapa de desarrollo y lo construye para obtener una estructura. También se han realizado intentos para automatizar este proceso de generación. Tal ejemplo se describe en las páginas 518 a 523 del Journal of Artificial Intelligence Society, volumen 9 (4) (1994). Es decir, utilizando el algoritmo genético de la regla de disposición de los elementos constitutivos de la estructura tridimensional, evolucione la regla de colocación, intentando obtener una nueva estructura, una tras otra. El algoritmo genético es un algoritmo que modela la adaptación evolutiva de organismos vivos. Codificando el sistema objetivo (estructura tridimensional en este caso) en genes representados por cadenas de bits binarios y preparando múltiples individuos que tienen tales genes como una población inicial. Para esta población, los individuos son evaluados por la función de evaluación dada previamente, los genes se seleccionan sobre la base de la evaluación, las operaciones genéticas como el cruce se realizan en los genes seleccionados, y la reproducción Crea un individuo En el algoritmo genético, al probar esta operación reproductiva de selección, tratamos de obtener mejores individuos.
Tarea de solución
En la generación de estructuras a partir del mapa de desarrollo convencional, es difícil predecir estructuras tridimensionales a partir de diagramas de evolución bidimensional, por lo que es un aspecto muy de prueba y error y es muy difícil, nadie puede hacerlo. Se han realizado intentos para automatizar tales tareas difíciles mediante el uso de algoritmo genético con la regla de disposición de los constituyentes como genes, pero en el método convencional, los elementos constitutivos de la estructura eran círculos y esferas. Sin embargo, al considerar el mundo real, no hacemos círculos o bolas como elementos constituyentes. Por ejemplo, las células que constituyen organismos vivos están compuestas de poliedros, y los fullerenos y similares tienen hexágonos con átomos de C en cada vértice. Al llenar el espacio con elementos constitutivos, es imposible llenarlo sin espacios en círculos y esferas, pero usar un polígono regular como el hexágono puede llenarse sin espacios. Además, en el método convencional, dado que el proceso de selección del algoritmo genético se realiza por la subjetividad del operador, es posible utilizar algo que es difícil de describir claramente como la belleza, pero, por otro lado, se puede realizar una automatización completa. No hubo. Sumario de la invención Por lo tanto, un objeto de la presente invención es proporcionar un método para automatizar por completo el proceso de generación de una estructura expandiendo los elementos constituyentes en polígonos y proporcionando funciones de evaluación claras.
Solución
Con el fin de lograr el objeto anterior, en la presente invención, se usa un polígono como un componente de una estructura tridimensional. En el mundo real, los polígonos regulares no son necesariamente elementos constitutivos, pero aquí usamos polígonos regulares para simplificar el cálculo. Desarrollamos una estructura tridimensional mediante el uso de algoritmos genéticos que consisten en reglas que hacen que la situación circundante sea la parte de la condición, luego dónde ubicar un nuevo polígono como parte del comportamiento y usar algoritmos genéticos. Cada vez que se genera una nueva estructura mediante un algoritmo genético, se muestra en una pantalla y se realiza una visualización para ayudar a comprender la estructura de una estructura tridimensional. Además, suponiendo que haya átomos presentes en cada vértice de un polígono, la selección se realiza automáticamente utilizando la energía de toda la estructura como una función de evaluación, y el proceso de generación en sí mismo es completamente automático.
Al expandir los componentes de una estructura tridimensional de un círculo o una esfera a un polígono, es posible generar una estructura que se ajuste al mundo real más que el método convencional. Además, al usar reglas de colocación de polígonos como genes y usar energía como una función de evaluación, no es necesario que el operador realice selecciones, y es posible generar completa y automáticamente una estructura tridimensional.
En primer lugar, la figura 10 muestra un diagrama de configuración del sistema de una computadora utilizada en la presente invención. El ordenador utilizado en este sistema está compuesto por una unidad de entrada 101, una CPU 102, una pantalla 103 y una memoria externa 104. En primer lugar, la configuración inicial (configuración de parámetros como la estructura inicial, el número de generaciones, etc.) y la configuración de las condiciones de restricción se realizan en la unidad de entrada 101. A continuación, en base a los parámetros introducidos, la CPU 102 genera una población inicial, realiza un algoritmo genético y genera automáticamente nuevos individuos. Cuando se genera un nuevo individuo mediante algoritmo genético, se muestra un individuo en la pantalla 103. Además, los datos de individuos excelentes entre grupos de cada generación se almacenan en la memoria externa 104. El proceso de evolución puede ser determinado por los datos almacenados en la memoria externa 104, y sirve como una guía para la determinación de parámetros. Este método puede implementarse en cualquier computadora siempre que tenga una configuración de sistema como se muestra en la Fig. Sin embargo, en algoritmos genéticos, si el número de individuos es pequeño, la población convergerá a un individuo antes de buscar lo suficiente, por lo que es necesario un cierto número de individuos. Por lo tanto, se requiere una memoria correspondiente. Además, teniendo en cuenta la cantidad de cálculos necesarios para generar y visualizar estructuras tridimensionales, se necesitan sistemas más allá de las estaciones de trabajo. En el algoritmo genético, es fácil de implementar en una computadora paralela ya que el cálculo de decodificación, evaluación, etc. de los genes de cada individuo se puede realizar independientemente de otros cálculos individuales.
A continuación, se muestra un diagrama de flujo de la presente invención en la figura 1 y se explicará el flujo básico. Es decir, se ingresan una condición inicial y una condición de restricción en el paso de entrada de condición inicial 11. Posteriormente, en la etapa 12 de generación de grupo inicial, se generan e inicializan una pluralidad de individuos que tienen genes en el grupo de reglas de disposición de polígonos con un número aleatorio. Luego, en el paso 13, se inicializa el número de generaciones. El número de generaciones puede ser pensado como un índice que indica si o sometidos muchas veces la operación tales como la reproducción de selección, que se describirá más adelante, se asume que la primera generación transcurrido cuando se genera una nueva población mediante la realización de una reproducción de selección a la población actual. A continuación, en el paso 14, para cada individuo en el grupo, se genera realmente una estructura tridimensional basada en la regla de disposición que es el gen y se visualiza, y en el paso 15 el valor de evaluación se obtiene mediante la función de evaluación. En el paso 16, los individuos que se convertirán en padres de la próxima generación se seleccionan a una tasa proporcional al valor de evaluación obtenido en el paso 17, y las operaciones genéticas se realizan en individuos para convertirse en padres para obtener nuevos individuos. Esta selección, repetición se repite para formar una nueva población. En el paso 17, si el número de generaciones se ha incrementado y ha transcurrido el número predeterminado de generaciones, la ejecución finaliza, de lo contrario, el proceso vuelve al paso 14. Al repetir tal bucle, se pueden obtener individuos con valores de evaluación más altos, es decir, individuos más adaptados.
A continuación, se describirá en detalle el caso en el que los tipos de polígonos que constituyen la estructura tridimensional son 5, 6 y 7 polígonos con referencia a la FIG.
En la presente invención, la regla de disposición se usa como un elemento constitutivo de genes. La Figura 2 muestra cómo expresar reglas. Además, aunque la regla está representada por una representación binaria, la tabla de códigos utilizada en ese momento se muestra en la FIG. La regla 21 consiste en una parte de condición 22 y una parte de acción 23. La parte de condición 22 describe en qué estado se describe el polígono al que se aplica la regla, y como se muestra en la figura 2 (A), el tipo de un polígono en contacto con cada lado del hexágono numerado como Describe Como hay cuatro estados de un polígono que está en contacto con cada lado, como un pentágono, un hexágono, un hexágono o nada tocado, se requieren 2 bits, cada uno de los cuales está representado por un código de tipo código 31. Por otro lado, la sección de acción 23 describe qué polígono (tipo 25) se va a colocar nuevamente en cualquiera de los lados numerados (lugar 26) como se muestra en la figura 2 (A). Como el lugar 26 es uno de los seis lados, toma 3 bits y cada uno está representado por el código del código de lugar 33. Como el tipo es uno de 5, 6 y 7 polígonos, se usa el código del tipo de código 32 Está representado por 2 bits. Por lo tanto, se requiere un total de 5 bits en toda la sección de acción 23.
La Figura 4 muestra la expresión génica. El gen 41 está representado por reglas de ordenamiento secuencial. Cuando todas las reglas posibles están vinculadas a los genes, no es necesario incluir la parte de la condición en los genes, y es suficiente usar como gen las partes de comportamiento de cada regla dispuesta en orden. Como la parte de condición de la regla describe el tipo (2 bits) del polígono que está en contacto con los seis lados, tiene 12 bits de longitud, por lo que pueden existir 212 reglas (estados). Por lo tanto, la longitud del gen es todo estado * cantidad de bits de parte de acción = 212 × 5 bits de longitud. Por lo tanto, al aplicar una regla a un cierto polígono, primero convierta el gen a la tabla de reglas 42, verifique las circunstancias que rodean al polígono al que se aplicará la regla (tipo de polígono adyacente) (Cadena de bits binarios). A continuación, esta cadena de bits binarios se interpreta como un número entero, y se accede a la tabla de reglas 42 con este número entero como una clave. Específicamente, cuando el hexágono está en contacto con el sexto lado y nada está en contacto con los cinco lados restantes, la situación se representa como 00.00.00.00.00.10. Convierte esta cadena de bits binarios en un entero. En este caso, será 2 para que pueda acceder a la segunda parte de acción. Un gen puede expresarse de forma compacta construyendo un gen solo por la parte de comportamiento sin incluir la parte de condición.
Aquí, se describirá la entrada de la condición inicial y la condición de restricción en la etapa de entrada de condición inicial 11 de la figura 1. Para la entrada de condición inicial, establezca la probabilidad de inicialización del gen y la estructura inicial. En la configuración de probabilidad de inicialización de genes, el gen de cada individuo se inicializa por número aleatorio al generar la población inicial, pero se establece la probabilidad de que se establezca 1 en ese gen. Los genes consisten en un grupo de acciones de múltiples reglas de colocación, y la parte de comportamiento consistió en el tipo de polígono que se colocará recientemente y el lugar donde colocarlo. Además, el código que representa el tipo se representó como hexágono 000 como el código de tipo 32 en la figura 3, y 001, 010, 001 como los cinco y siete polígonos restantes. En otras palabras, el hecho de que 1 es fácil de colocar en el código de la sección de acción significa que es más probable que se organicen los 5º y 7º polígonos. Cuando se disponen 5, 7 polígonos, la curvatura cambia, por lo que es probable que se produzca una estructura más complicada. También establecemos la estructura inicial como la condición inicial. La estructura inicial es una estructura tridimensional antes de aplicar la regla, y la aplicación de reglas siempre comienza desde esta estructura inicial. La figura 5 muestra un ejemplo de la estructura inicial. En el caso más simple, comienza desde el hexágono 51 en la figura 6 (A), y como un caso más complicado, la estructura anular 52 de la figura 5 (B) o la estructura cilíndrica 52 Comience con el objeto 53, y así sucesivamente. En la presente invención, se supone que dicha estructura inicial puede establecerse libremente. Como el ajuste de la estructura inicial se puede establecer libremente de esta manera, la estructura de la estructura tridimensional generada se puede controlar hasta cierto punto. Además, evita arreglos infinitos y también ingresa condiciones de restricción para realizar el procesamiento en tiempo real. Específicamente, como se explica en 11, limite el número de polígonos que se generarán y el espacio ocupado por la estructura.
A continuación, se describirá en detalle el proceso (aparición) de crear una estructura a partir de genes en el paso 14 de la figura 1. La Fig. 6 muestra el diagrama de flujo. Primero, en el paso 61, el gen se convierte en una tabla de reglas. A continuación, en el paso 62, se enumeran los polígonos que pueden organizar nuevos polígonos a su alrededor. Por lo tanto, en el caso en que los polígonos están dispuestos en todas las direcciones, está fuera de esta lista. Entonces, si la lista está vacía, en la etapa 63 se examina el entorno de polígonos en en el paso 64 a la parte superior de la lista, que accede a la tabla de reglas como una clave, la obtención de una unidad de comportamiento a ser reglas de colocación ejecutados. Luego, en el paso 65, se verifica si esta regla es aplicable. Por ejemplo, es imposible colocar nuevamente un polígono donde se encuentra un polígono. Alternativamente, la regla no puede aplicarse incluso cuando la condición de restricción definida en el paso 11 de la figura 1 no se satisface. Si se puede aplicar la regla, se coloca un nuevo polígono de acuerdo con la regla en el paso 66, el polígono al principio de la lista se elimina de la lista en el paso 67 y el proceso vuelve al paso 63. Este proceso se repite hasta que la lista se vacía, por lo que se construye una estructura tridimensional.
Un ejemplo de ocurrencia se muestra en la FIG. Aquí, se supone que la estructura inicial es el hexágono 71 más simple, y la tabla de reglas almacena partes de acción de las reglas 72, 74 y 75. Por lo tanto, en el primer paso, solo el hexágono 71 es un polígono al cual se puede aplicar la regla. Como no hay nada alrededor de este hexágono, se aplica la regla 72 con la condición de 00.00.00.00.00.00 y la parte de acción 01.001 organiza un nuevo polígono. La parte de acción toma la forma y la forma del lugar, por lo que en este ejemplo es 01 y 001, respectivamente, por lo que el tipo es hexagonal y el lugar es 1 de acuerdo con la tabla de códigos de la Fig. Por lo tanto, se coloca un nuevo hexágono 73 en un lado numerado 1 del primer hexágono 71. El lado del polígono que se va a organizar recientemente se numera con el lado que está en contacto con el polígono al que se aplica la regla (es decir, el primer hexágono 71) se establece en 0. En el siguiente paso, dos del primer hexágono 71 y el nuevo polígono 73 obtenidos al aplicar la regla 72 al hexágono son los polígonos a los que se puede aplicar la regla. Dado que el hexágono está en contacto con solo el borde 1 71, la parte de condición es 00.01.00.00.00.00, de modo que la acción parte 01.000 (tipo es hexágono, ubicación es el borde 0) de la regla 74 se ejecuta. Como resultado, se coloca un nuevo hexágono 76 para estar en contacto con el lado 0 del primer hexágono 71. De forma similar, un nuevo hexágono 77 se dispone aplicando la regla 75 al hexágono 73. En el siguiente paso, hay cuatro polígonos que se pueden aplicar a la regla, y se coloca un nuevo polígono aplicando la regla a estos cuatro polígonos. De esta manera, las reglas se aplican secuencialmente a los individuos generados hasta la última vez para construir la estructura.
A continuación, en el paso 15 de la figura 1, se evalúa la estructura así formada. En la presente invención, se supone que hay un átomo en el vértice de la esquina de un polígono que es un componente de una estructura tridimensional, se calcula la energía, y su recíproco se toma como un valor de evaluación. Es decir, se supone que la energía E se requiere para doblar el plano formado por hexágonos en un cilindro. También se supone que cuando el pentágono está en este cilindro, la energía aumenta en E5 cuando la superficie es convexa, y la energía E7 cuando la superficie de entrada se vuelve cóncava se eleva. Este E, E 5, E 7 se usa para expresar la energía de la estructura tridimensional.
La figura 8 muestra la imagen mostrada. El sistema de visualización 81 de la presente invención en la figura 10 está constituido por una pluralidad de ventanas de visualización 82, y los individuos que tienen valores de evaluación altos en el grupo se muestran en cada ventana de visualización. En la ventana de visualización, se supone que se puede realizar una ampliación, rotación, etc. para un individuo, es decir, una estructura tridimensional.
A continuación, se describirá la etapa reproductiva de selección 16 de la figura 1. En función del valor de evaluación calculado como se describe anteriormente, seleccione el padre de la próxima generación. En este momento, se utiliza un método de ruleta para seleccionar un individuo con una probabilidad correspondiente al valor de evaluación de cada individuo a la suma de los valores de evaluación de todos los individuos. A continuación, se aplica un operador genético al gen del individuo seleccionado, y se genera un individuo que tiene un nuevo gen. La figura 9 muestra un ejemplo de una operación genética. Como operación genética, se usa un cruce 91 en la figura 9A y una mutación 93 en la figura 9B. Crossover es una operación de determinar al azar un punto de cruce 92 y volver a ensamblar el gen en el punto de cruce, y la mutación es una operación de inversión de un poco de un gen con una cierta probabilidad pequeña. Se generan individuos que heredan las características del padre por operación genética y aún difieren de los padres. Varias estructuras se generan automáticamente repitiendo la operación anterior (generación) un cierto número de veces.
Aunque las realizaciones que usan algoritmos genéticos se han descrito anteriormente, la presente invención no se limita a esto, y la presente invención también es aplicable a otros métodos de optimización.
También es posible usar un método como el recocido simulado.
Efecto de la invención
De acuerdo con la presente invención, es posible generar automáticamente una estructura tridimensional que tenga polígonos como elementos constitutivos, por ejemplo, usando un algoritmo genético, es posible generar fácilmente una estructura tridimensional de acuerdo con él, y 3 Se espera que sea útil para comprender la estructura dimensional.
La figura 1 es un diagrama de flujo de una realización de acuerdo con la presente invención.
La figura 2 es un diagrama que muestra un ejemplo de una expresión de regla.
La figura 3 es un diagrama que muestra un ejemplo de un código utilizado para una regla.
La figura 4 muestra la expresión génica en la presente invención.
La figura 5 muestra un ejemplo de una estructura inicial.
La figura 6 es un diagrama de flujo del procedimiento de generación en la presente invención.
La figura 7 muestra un ejemplo de ocurrencia en la presente invención.
La figura 8 es un diagrama que muestra un ejemplo de visualización en la presente invención.
La figura 9 muestra un ejemplo de funcionamiento genético.
La figura 10 es un diagrama de configuración del sistema de una computadora utilizada en la presente invención.
Figura 9 ... ... 11 ... Entrada de condición inicial, 14 ... indicación de ocurrencia, 15 ... evaluación, 16 ... reproducción selectiva, 21 ... regla, 22 ... parte de condición, 23 ... parte de acción, 24 ... amable, 25 ... amable, 26 ... lugar, 31 ... tipo de código (parte de condición), 32 tipo de código (parte de acción), 33 ... código de lugar, 41 ... gen, 42 ... tabla de reglas, 51 ... hexágono, 52 ... forma de anillo, 53 ... tubular , 71 ... Estructura inicial, 72 ... Hexágono obtenido al aplicar 72 a la regla 1, 73 ... 71, 74 ... Regla 2, 75 ... Regla 3, 76 ... 71 Hexágono obtenido aplicando 74 , 76 ... 73 hexágono, 81 ... imagen de visualización, 82 ... ventana de visualización, 91 ... cruce, 92 ... punto de cruce, 93 ... mutación, 101 ... sección de entrada, 102 ... sección de CPU, 103 ... pantalla, 104 ... memoria externa.
Reclamo
Reivindicación 1 Un componente de una estructura tridimensional es un polígono, una regla de disposición de un polígono es un gen, una disposición de polígono se determina automáticamente mediante el uso de un algoritmo genético basado en una función de evaluación predeterminada, y 3 Y generando una estructura dimensional.
2. Un método óptimo de determinación de la disposición de acuerdo con la reivindicación 1, en el que se puede establecer una estructura inicial de la estructura tridimensional antes de la aplicación de la regla, optimizando así la estructura de la estructura tridimensional después de la aplicación de la regla Método de determinación del Arreglo.
3. Un método de determinación de disposición óptima según la reivindicación 1, en el que un átomo está presente en un vértice del polígono y se usa una energía del polígono como un valor de evaluación para automatizar un proceso de evaluación en el algoritmo genético.
Dibujo :
Application number :1997-006822
Inventors :株式会社日立製作所
Original Assignee :鈴木芳生、井原茂男