JP4032070B2 - Circuit layout optimization problem processing method and circuit layout optimization problem processing program recording computer-readable recording medium - Google Patents

Description

  The present invention relates to a circuit layout optimization problem in which, for example, each circuit on a large scale integration circuit (LSI; large scale integration) is optimally arranged. More generally, a plurality of elements (arrangements) are arranged in a two-dimensional space or more. The present invention relates to a circuit arrangement optimization problem processing method and a computer-readable recording medium recording a circuit arrangement optimization problem processing program suitable for use in processing an element arrangement optimization problem for arranging elements in an optimal state.

Specifically, the element placement optimization problem is a problem in which a plurality of elements for which connection relationships are defined are optimally placed in a required space (or a required area if the elements are two-dimensional). It is called the graph mapping problem.
For example, in the above-described LSI, if the optimum arrangement of each circuit on the LSI can be obtained, the LSI can be reduced in size, and the wiring property connecting the respective circuits can be minimized to improve the wiring performance. Therefore, the processing speed in the LSI can be increased.

The element arrangement optimization problem is performed by executing an optimization problem solving algorithm (eg, genetic algorithm, min-cut method, n-element exchange method, etc.) to determine the optimum arrangement of a plurality of elements in the space, and based on the determination. A plurality of elements can be processed by placing them in the space.
Here, when the size of the element placement optimization problem is large (that is, when the number of elements for which the optimum placement is to be obtained is very large), each element is used to enable the optimization problem solving algorithm to be executed at high speed. Without considering the size of each element, each element is regarded as a point (or the same shape) to determine the optimum arrangement of the elements.

However, since each element has a unique size, even if the elements are arranged based on the optimum arrangement determined in this way, the elements may overlap with each other or a gap may be generated between the elements. There is a problem that sparseness and density may occur.
Therefore, in order to process an element placement optimization problem with a large problem scale at high speed, the optimization problem solving algorithm is executed without considering the size of each element, and the resulting element arrangement is eliminated. There is a need.

  The present invention has been devised in view of such problems, so that the element arrangement optimization problem with a large problem scale can be solved by eliminating the sparseness and density caused in the arrangement of elements so that the elements can be arranged uniformly in the space. A circuit layout optimization problem processing program for operating a computer to process an element layout optimization problem, and to provide a circuit layout optimization problem processing method capable of high-speed processing It is an object of the present invention to provide a computer-readable recording medium on which is recorded.

For this reason, the circuit layout optimization problem processing method of the present invention uses a computer equipped with a CPU to maintain the connection relationship when arranging a plurality of elements for which a connection relationship is defined in a required space. A circuit layout optimization problem processing method for eliminating the density of the plurality of elements in an arrangement state, wherein an input step for inputting information on the plurality of elements in the initial arrangement state to the computer as an arrangement result; The arrangement result input in the input step is configured by dividing the space, and a partial space including a plurality of elements is expressed as a gene, and the arrangement result includes the arrangement of the gene. Prepare multiple chromosomes corresponding to, use these chromosomes, and chromosomes that can reduce the density of multiple elements have a large fitness value Genetic algorithm using応度function by executing in the CPU, and the first algorithm execution step of obtaining the chromosome with the highest fitness value as the best chromosome, while the execution of the first algorithm executing step For each of a plurality of generated chromosomes, for each subspace of each chromosome used in the genetic algorithm, at least one of the plurality of elements included in the subspace is a place where the element density is high local density rid algorithm includes a second algorithm executing step you run in the CPU, said genetic algorithm and the second algorithm executing step in the first algorithm executing step of moving to the element density is low location from In the local sparse / dense elimination algorithm, the optimal chromosome fitness value is less than the reference value. The first algorithm execution step is performed to determine the optimal chromosome having a fitness value equal to or higher than the reference value, and to reduce the density of the plurality of elements in the initial arrangement state while maintaining the connection relationship. The solution is output as a solved solution (claim 1).

At this time, the first algorithm executing step, when performing said genetic algorithm, at least one of the subspaces is selected from the plurality of partial spaces in said chromosome, the partial space in other chromosomes Crossover as a genetic operation can be executed by exchanging with the subspace corresponding to (Claim 2 ).

Moreover, the first algorithm executing step, when performing said genetic algorithm, towards a particular subspace of among the plurality of partial spaces in said chromosome, corresponding to the subspace of other chromosomes portion If the density is eliminated than space by pasting the partial space corresponding to the partial space in the chromosome to the subspace said other chromosomes may perform crossover as genetic operations (Claim 3 ).

Moreover, the first algorithm executing step, when performing said genetic algorithm, moving at least one element of the plurality of elements in at least one subspace in the upper Symbol plurality of subspaces Thus, mutation as a genetic operation can be performed (claim 4 ).

Here, the second algorithm executing step, as the topical manner compressional solve algorithm, the movement of the element that put the partial space regarded as the motion of the fluid, so that the element density is uniform partial space can be in consideration of the viscosity of the fluid using an algorithm analogy is applied hydrodynamic moving elements in the partial space (claim 5).

In here, the second algorithm execution step can be moved while preserving the vicinity among multiple elements, at least one element of the plurality of elements included in the partial space ( Claim 6 ).

Further, the second algorithm executing step, while preserving the order among multiple components, can also be moved at least one element of the plurality of elements included in the partial space (according Item 7 ).

Specifically, the second algorithm executing step, as the topical manner compressional solve algorithm, regarded as a modification operation in the morphing movement of elements that put the partial space, each partial space, said initial placement determine the morphing center on the basis of the state near Ru information about multiple elements, move at least one element of the plurality of elements included in the partial space to a location spaced from said morphing center It is possible to execute an algorithm to which the analogy of morphing to be applied is applied (claim 8 ).

Here, in the second algorithm execution step, when moving at least one element of the plurality of elements included in the subspace to a place separated from the morphing center, the second algorithm execution step moves from the morphing center. The distance to the element to be can be linearly expanded (claim 9 ).
In the second algorithm execution step, when moving at least one element of the plurality of elements included in the partial space to a place separated from the morphing center, the second algorithm is executed from the morphing center. the distance until the element can be expanded nonlinearly (0 claim 1).

Also, the circuit layout optimization problem processing method of the present invention uses a computer equipped with a CPU to maintain an initial layout while arranging a plurality of elements for which connection relationships are defined in a required space. A circuit layout optimization problem processing method for eliminating the density of the plurality of elements in a state, an input step for inputting information on the plurality of elements in the initial placement state to the computer as a placement result; with respect to the arrangement results input at said input step, the width of each of the plurality of subspaces to the space Ru are configured as obtained by dividing expressed as a first gene, said first gene a first chromosome consisting of SEQ Make several, fitness function which Rutotomoni using these first chromosome, chromosome that can reduce the density of a plurality of elements it takes a large fitness value The first genetic algorithm for each of the plurality of space corresponding to the plurality of first chromosome that is generated during the execution of the first steps, the first step to run by the CPU using the above the subspace containing a plurality of elements configured and each as obtained by dividing the space in the width of the first partial space corresponding to the chromosomes and expressed as a second gene, Ri Do from the second gene of SEQ a second chromosome corresponding to the arrangement results preparing a plurality Rutotomoni using these second chromosome, the second genetic algorithm using said fitness function, to greater than the number of generations predetermined by executing a repeating the CPU, the second chromosome with the highest fitness value as an intermediate chromosome, a second step of multiple acquired in correspondence with each of said plurality of first chromosome second step For each of the plurality of second chromosome that is generated during the execution of, for each subspace of the second chromosome used in the second genetic algorithm, multiple which is Ru contained in the subspace And a third step of executing, on the CPU, a local sparse / dense cancellation algorithm for moving at least one of the elements from a location where the element density is high to a location where the element density is low , the first step comprising: Based on the fitness values of the plurality of intermediate chromosomes acquired in the second step, the intermediate chromosome having the highest fitness value is acquired as the optimal chromosome from the plurality of intermediate chromosomes, The first genetic algorithm, the second genetic algorithm in the second step, and the local sparse / dense elimination algorithm in the third step are adapted to optimize the optimal chromosome. It is repeatedly executed until the fitness value becomes equal to or higher than the reference value, and the first step is performed for a plurality of optimal chromosomes whose fitness values are equal to or higher than the reference value in the initial arrangement state while maintaining the connection relationship. It is characterized in that it is output as a solution in which the density of the elements is eliminated (claim 1 1 ).

Further, according to the circuit layout optimization problem processing method of the present invention, when a plurality of elements for which connection relations are defined are placed in a required space, an initial placement is performed while maintaining the connection relation using a computer having a CPU A circuit layout optimization problem processing method for eliminating the density of the plurality of elements in a state, an input step for inputting information on the plurality of elements in the initial placement state to the computer as a placement result; with respect to the arrangement results input at said input step, the width of each of the plurality of subspaces to the space Ru are configured as obtained by dividing expressed as a first gene, said first gene a first chromosome consisting of SEQ Make several, adaptability Rutotomoni using these first chromosome, chromosome that can reduce the density of a plurality of elements it takes a large fitness value A first step to run a first genetic algorithm using the number of the CPU, for each of a plurality of space corresponding to the plurality of first chromosome that is generated during the execution of the first step, the space width of the subspaces corresponding to the chromosome of the first after dividing the subspace of multiple, for each subspace, of at least one of the multiple elements that is part on the subspace A plurality of intermediate arrangement results corresponding to a plurality of first chromosomes are acquired by executing a local sparse / dense elimination algorithm for moving an element from a place with a high element density to a place with a low element density , a second step that to calculate the respective fitness values of a plurality of intermediate placement results in the CPU, respectively are constructed and a plurality of the space as divided by the width of the subspace corresponding to the chromosome of the first Part containing the element A space is expressed as a second gene, a plurality of second chromosomes comprising the sequence of the second gene and corresponding to the arrangement result are prepared, the second chromosome is used, and the fitness function is And executing the second genetic algorithm used by the CPU to obtain the second chromosome having the highest fitness value as the optimal chromosome , and the first step comprises the second step. Based on the fitness value calculated in the step, the intermediate placement result having the highest fitness value is obtained as the optimum placement result from the plurality of intermediate placement results, and the first genetic algorithm in the first step And the local sparse / dense elimination algorithm in the second step is repeatedly executed until a predetermined number of generations is exceeded in the first genetic algorithm, and the third step includes: With respect to the optimal placement result obtained by repeatedly executing the first genetic algorithm in the first step and the local sparse / dense elimination algorithm in the second step, the optimal chromosome fitness value is The second genetic algorithm is repeatedly executed until a reference value or higher is reached, and an optimal chromosome having a fitness value equal to or higher than the reference value is selected for a plurality of elements in the initial arrangement state while maintaining the connection relationship. It is characterized by outputting a solution which solves the density (claim 1 2).

By the way, the computer-readable recording medium on which the circuit arrangement optimization problem processing program of the present invention is recorded is arranged in the initial arrangement while maintaining the connection relation when arranging a plurality of elements in which the connection relation is defined in a required space. A computer-readable recording medium recording a circuit arrangement optimization problem processing program for processing a circuit arrangement optimization problem for eliminating the density of the plurality of elements in a state by a computer having a CPU. When the information related to the plurality of elements in the initial arrangement state is input to the computer as an arrangement result , the circuit arrangement optimization problem processing program divides the space with respect to the input arrangement result. A partial space that is configured as a thing and includes a plurality of elements each is expressed as a gene, and from the sequence of the gene Chromosome corresponding to Ri該placement result Make several, with use of these chromosomes, the genetic algorithm using the fitness function chromosomes that can reduce the density of a plurality of elements takes a large fitness value A first algorithm executing means for acquiring a chromosome having the highest fitness value as an optimal chromosome by being executed by the CPU , and each of a plurality of chromosomes generated during the execution of the first algorithm executing means ; Then, for each subspace of each chromosome used in the genetic algorithm, at least one element of the plurality of elements included in the subspace is moved from a place where the element density is high to a place where the element density is low. local density eliminates algorithm causes to function the computer as the second algorithm executing means you run in the CPU, the first The topical manner compressional eliminated algorithm in said genetic algorithm and the second algorithm execution unit in algorithms executing means, fitness value of the best chromosome are repeatedly performed until the reference value or more, the first algorithm execution unit And causing the computer to function so as to output an optimal chromosome having a fitness value equal to or higher than the reference value as a solution that eliminates the density of the plurality of elements in the initial arrangement state while maintaining the connection relationship. (Claim 1 3 ).
Further, the computer-readable recording medium recording the circuit arrangement optimization problem processing program according to the present invention is arranged in the initial arrangement while maintaining the connection relation when arranging a plurality of elements in which the connection relation is defined in a required space. A computer-readable recording medium recording a circuit arrangement optimization problem processing program for processing a circuit arrangement optimization problem for eliminating the density of the plurality of elements in a state by a computer having a CPU. When the information related to the plurality of elements in the initial arrangement state is input to the computer as an arrangement result, the circuit arrangement optimization problem processing program divides the space with respect to the input arrangement result. Each width of a plurality of partial spaces configured as a thing is expressed as a first gene, and from the sequence of the first gene A first genetic algorithm using a fitness function in which a plurality of first chromosomes are prepared, the first chromosome is used, and a chromosome capable of reducing the density of a plurality of elements takes a large fitness value The first execution means for executing the CPU, and the portion corresponding to the first chromosome for each of the plurality of spaces corresponding to the plurality of first chromosomes generated during the execution of the first execution means A partial space that is configured by dividing the space by the width of the space and that includes a plurality of elements each is expressed as a second gene, and is composed of a sequence of the second gene and corresponds to the arrangement result. To prepare a plurality of chromosomes, use these second chromosomes, and repeatedly execute the second genetic algorithm using the fitness function on the CPU until a predetermined number of generations are exceeded. Second execution means for obtaining a plurality of second chromosomes having the highest fitness value as intermediate chromosomes corresponding to each of the plurality of first chromosomes, and during execution of the second execution means For each of the plurality of second chromosomes to be generated, at least of the plurality of elements included in the subspace for each subspace of each second chromosome used in the second genetic algorithm The computer is caused to function as third execution means for executing a local sparse / dense elimination algorithm for moving one element from a place having a high element density to a place having a low element density by the CPU. Based on the fitness values of the plurality of intermediate chromosomes acquired by the second execution means, the intermediate chromosome having the highest fitness value is acquired as the optimal chromosome from the plurality of intermediate chromosomes, The first genetic algorithm in the first execution means, the second genetic algorithm in the second execution means, and the local sparse / dense elimination algorithm in the third execution means are based on the optimal chromosome fitness value. It is repeatedly executed until the value becomes equal to or greater than the value, and the first execution means selects an optimal chromosome having a fitness value equal to or greater than the reference value, while maintaining the connection relationship, the plurality of elements in the initial arrangement state are sparse / dense The computer is caused to function so as to be output as a solution that solves the problem (claim 14).
Furthermore, the computer-readable recording medium on which the circuit arrangement optimization problem processing program of the present invention is recorded has an initial arrangement while maintaining the connection relation when arranging a plurality of elements in which the connection relation is defined in a required space. A computer-readable recording medium recording a circuit arrangement optimization problem processing program for processing a circuit arrangement optimization problem for eliminating the density of the plurality of elements in a state by a computer having a CPU. When the information related to the plurality of elements in the initial arrangement state is input to the computer as an arrangement result, the circuit arrangement optimization problem processing program divides the space with respect to the input arrangement result. The width of each of a plurality of subspaces configured as a thing is expressed as a first gene, and the sequence of the first gene A first genetic algorithm using a fitness function in which a plurality of first chromosomes are prepared, and the first chromosome is used, and a chromosome capable of reducing the density of a plurality of elements takes a large fitness value. First execution means for executing the CPU on the CPU, and a portion corresponding to the first chromosome for each of a plurality of spaces corresponding to the plurality of first chromosomes generated during the execution of the first execution means After dividing this space into a plurality of partial spaces by the width of the space, for each partial space, at least one of the plurality of elements included in the partial space is reduced in the element density from the place where the element density is high. By executing a local sparse / dense elimination algorithm for moving to a place by the CPU, a plurality of intermediate arrangement results corresponding to the plurality of first chromosomes are acquired, and the respective fitness of the plurality of intermediate arrangement results Second execution means for calculating the CPU by the CPU, and a partial space that is configured by dividing the space by the width of the partial space corresponding to the first chromosome and each includes a plurality of elements as the second gene A plurality of second chromosomes comprising the sequence of the second gene and corresponding to the arrangement result, and using the second chromosome and the second genetic using the fitness function By executing the algorithm on the CPU, the computer functions as third execution means for acquiring the second chromosome having the highest fitness value as the optimal chromosome, and the first execution means includes the second execution means. Based on the fitness value calculated by the execution means, an intermediate placement result having the highest fitness value is obtained as the optimum placement result from the plurality of intermediate placement results, and the first inheritance in the first execution means is obtained. The local sparse / dense elimination algorithm in the second execution means is repeatedly executed until a predetermined number of generations is exceeded in the first genetic algorithm, and the third execution means is in the first execution means. The optimal chromosome fitness value is greater than or equal to a reference value with respect to the optimal arrangement result obtained by repeatedly executing the local sparse / dense cancellation algorithm in the first genetic algorithm and the second execution means. The second genetic algorithm is repeatedly executed until the optimal chromosome whose fitness value is greater than or equal to the reference value is eliminated, and the sparseness of the plurality of elements in the initial arrangement state is eliminated while maintaining the connection relationship. The computer is made to function so as to be output as a solution (claim 15).

As described above in detail, according to the present invention, when a plurality of elements connecting relationship is defined to place the required space, execute the automatic answering Step perform a genetic algorithm, the local density eliminates algorithm by providing the answering step, even when processing a scale of large elements layout optimization problem, there is an advantage that can be performed to eliminate the density of high speed elements (claim 1-5, 8, 1 1 to 15 ).

Further, according to the circuit arrangement optimization problem processing method of the present invention, the second algorithm execution step moves the elements while preserving the proximity between the plurality of elements, or preserves the order between the plurality of elements. However, since the elements can be moved, the range of circuit layout optimization problems that can be processed can be expanded (claims 6 and 7 ).
Furthermore, since the second algorithm execution step can linearly expand the distance from the morphing center to the element to be moved, or nonlinearly increase the distance from the morphing center to the element to be moved. , it is possible to expand the range of layout optimization problem This can handle (claim 9, 1 0).

In addition, the second algorithm execution step sequentially adds elements to be de-dense-resolved, considers fixed arrangement elements to be elements to be de-dense-decomposed, reduces the amount of movement of large elements, and elements to be moved the or move at once, since it or gradually moving the moving target element, Ru can expand the range of arrangement optimization problem that can be further processed.

Furthermore, when the first algorithm execution step executes the genetic algorithm, a first island having a population of chromosomes divided in the vertical direction and a second island having a population of chromosomes divided in the horizontal direction are obtained. since it is also possible to use, can hold a variety of chromosomal as the solution candidates in the population, to search the optimal solution efficiently, Ru can be performed to eliminate the density of elements more efficiently.

Embodiments of the present invention will be described below with reference to the drawings.
(A) Description of Configuration of Placement Optimization Problem Processing Device FIG. 1 is a block diagram showing a configuration of a placement optimization problem processing device (circuit placement optimization problem processing device; hereinafter referred to as a placement optimization problem processing device). The arrangement optimization problem processing apparatus 1 shown in FIG. 1 is for executing the arrangement optimization problem processing method (circuit arrangement optimization problem processing method; hereinafter referred to as arrangement optimization problem processing method) of the present invention. .
Here, in FIG. 1, 5A is a display unit for displaying various setting screens and optimum arrangement results of elements obtained by processing, and 5 is a display control unit for controlling the display state on the display unit 5A, 7B. Is an input unit such as a keyboard or a mouse for referring to display data on the display unit 5A and an operator inputs response information for the display data, and 7D is an input control unit for controlling the input unit 7B.

Reference numeral 8 denotes a disk device. The disk device 8 stores all information (such as an OS) necessary for operating the layout optimization problem processing apparatus 1, and a layout optimization problem described later. A processing program is stored.
6 is an external file read / write unit, 6A is an external file, 7A is a print unit, and 7C is a print control unit. The external file read / write unit 6 and the print unit 7A are respectively instructed from the input unit 7B. Accordingly, the optimum arrangement of the plurality of nodes displayed on the display unit 5A is recorded on the external file 6A or a predetermined sheet.

Reference numeral 4 denotes a CPU for comprehensively managing each unit constituting the arrangement optimization problem processing apparatus 1.
The CPU 4 functions as a first algorithm execution unit and a second algorithm execution unit when arranging a plurality of elements having a defined connection relationship in a required space.

Here, the first algorithm executing means executes a genetic algorithm described later, and the second algorithm executing means executes a local sparse / dense elimination algorithm described later.
More specifically, the first algorithm executing means executes a genetic algorithm when information on the initial arrangement state of the plurality of elements is input, and eliminates the density of the plurality of elements in the initial arrangement state. To do.

The second algorithm executing means executes a local sparse / dense cancellation algorithm when information on the intermediate arrangement state of the plurality of elements after the sparse / dense is canceled by the first algorithm executing means, This further eliminates the density of the plurality of elements in the intermediate arrangement state.
In addition, after executing the combination of the first algorithm execution means and the second algorithm execution means to obtain the optimum value of the parameter to be used when executing the local sparse / dense elimination algorithm, It is also possible to execute the two-algorithm execution means to cancel the density of the plurality of elements in the initial arrangement state.

  Actually, the functions corresponding to the first algorithm execution means and the second algorithm execution means are programs (circuit arrangements) recorded on a recording medium such as the disk device 8 or CD-ROM (not shown). An optimization problem processing program (hereinafter referred to as an arrangement optimization problem processing program) is read into a memory (RAM) (not shown), and the program is started and executed by the CPU 4 to realize the operation of the CPU 4.

Here, the placement optimization problem processing program is for processing a placement optimization problem in which a plurality of elements for which connection relations are defined is placed in a desired state in an optimal state, and the first algorithm. The computer functions as an execution means and a second algorithm execution means.
The arrangement optimization problem processing program is recorded on, for example, a CD-ROM, and is used by being installed in the disk device 8 in the computer from the CD-ROM or the like.

That is, the above-described disk device 8, CD-ROM, and the like correspond to a computer-readable recording medium that records an arrangement optimization problem processing program.
As described above, the layout optimization problem processing apparatus 1 according to the present embodiment includes the CPU 4, the display unit 5A, the display control unit 5, the external file reading / writing unit 6, the printing unit 7A, the printing control unit 7C, and the input unit. This can be realized by using a general computer system (computer) having 7B, input control unit 7D, disk device 8 and the like.

Then, the placement optimization problem processing apparatus 1 processes the placement optimization problem in which the plurality of placement elements 9 are placed in an optimum state in the placement area 10 as described below.
(B) Description of Arrangement Optimization Problem Processing Method of the Present Invention (b1) Basic Concept First, the basic concept of the arrangement optimization problem processing method of the present invention will be described with reference to FIGS. 4 and 5, reference numeral 9 denotes an element (hereinafter referred to as an arrangement element), and in FIGS. 3 to 5, reference numeral 10 denotes a space for arranging the arrangement element 9 (hereinafter referred to as an arrangement area). Show.

  According to the arrangement optimization problem processing method of the present invention, when arranging a plurality of arrangement elements 9 with a defined connection relationship in a required arrangement area 10, first, the arrangement optimization problem processing apparatus 1 receives the plurality of arrangements. An initial arrangement result (information on the initial arrangement state) of the element 9 is input (step S1 in FIG. 2). Here, since each of the placement elements 9 has a unique size, generally, an initial placement result in a state in which the placement elements 9 are unevenly placed in the placement region 10 and density is generated is input.

When the initial arrangement result of the arrangement element 9 is input, the arrangement optimization problem processing apparatus 1 cancels the density of the arrangement element 9 (step S2 in FIG. 2).
Here, in step S2, a genetic algorithm is executed (step S3 in FIG. 2; first algorithm execution step) and a local sparse / dense elimination algorithm is executed (step S4 in FIG. 2; second algorithm execution). Step).

  Specifically, in step S3, a genetic algorithm (GAc) or a genetic algorithm (GAp) is executed as a genetic algorithm, and in step S4, a hydrodynamic analogy is applied as a local sparse / dense cancellation algorithm. An algorithm or an algorithm to which a morphing analogy is applied is executed. GA is an abbreviation for Genetic Algorithm.

Details of these algorithms will be described later.
The case where the genetic algorithm (GAp) is executed in step S3 will be described in “(b4) Description of the second embodiment”.
Here, when executing the genetic algorithm (GAc) (step S3), first, the initial arrangement result for replicating the initial arrangement result of the arrangement element 9 input in step S1 to become the parent chromosome is obtained. Create multiple. Subsequently, as shown in FIGS. 3B and 3A, the arrangement region 10 is divided in an appropriate width in the vertical direction or the horizontal direction to form a partial region 10a. Then, the genetic algorithm (GAc) is defined to be crossed in units of the partial area 10a, and the genetic algorithm (GAc) is executed, thereby eliminating the density of the arrangement elements 9 in the initial arrangement state.

  For example, FIG. 4A shows an example of the arrangement element 9 in the intermediate arrangement state in which the density is eliminated in step S3 when the arrangement area 10 is divided in the vertical direction. In the example shown in FIG. 4A, the density of the arrangement elements 9 is not completely eliminated only by executing the genetic algorithm (GAc). FIG. 4B shows the density of the arrangement elements 9 in the intermediate arrangement state shown in FIG.

Therefore, the placement optimization problem processing apparatus 1 executes the local sparse / dense elimination algorithm when the intermediate placement result (information regarding the intermediate placement state) of the placement element 9 after the sparse / dullness is eliminated in step S3. Thus, the density of the arrangement elements 9 in the intermediate arrangement state is further eliminated (step S4).
In step S4, a local sparse / dense elimination algorithm is executed to move the arrangement element 9 from a place where the arrangement element density is high to a low place in the partial area 10a of the arrangement area 10 divided in step S3. The density of the arrangement elements 9 in the intermediate arrangement state is eliminated. Hereinafter, a method of executing the local sparse / dense cancellation algorithm to cancel the sparseness of the placement element 9 is referred to as a local sparse / dense cancellation method (LO).

FIG. 5A shows the result of eliminating the density of the arrangement elements 9 in the intermediate arrangement state shown in FIG. FIG. 5B shows the density of the arrangement elements 9 in the arrangement state shown in FIG.
Furthermore, in the placement optimization problem processing apparatus 1, it is determined whether or not the density of the placement element 9 has been eliminated in step S2 (whether the placement result obtained in step S4 satisfies a predetermined density elimination condition) (step S2). S5) When it is determined that the density of the arrangement element 9 has been eliminated, the process is terminated (YES route in step S5).

On the other hand, if it is determined that the sparse / dense of the arrangement element 9 has not been eliminated, after changing the parameters of the genetic algorithm and the parameters of the local sparse / eliminate algorithm (from the NO route of step S5 to step S6), The operations after step S2 described above are repeated.
As described above, according to the layout optimization problem processing method of the present invention, when a plurality of layout elements 9 for which connection relations are defined are arranged in a required layout area 10, a genetic algorithm (GAc) is executed to perform initial processing. After the arrangement element 9 in the arrangement state is eliminated, the local density elimination algorithm is executed to further eliminate the density of the arrangement element 9 in the intermediate arrangement state. Also when processing is performed, the density of the arrangement elements 9 can be eliminated at high speed.

  That is, according to the layout optimization problem processing method of the present invention, since the sparse / dense elimination method using the genetic algorithm (GAc) is used, the global search method of the genetic algorithm (GAc) can be used to efficiently arrange the layout elements 9. In addition to eliminating the density, the calculation speed of the placement optimization problem processing apparatus 1 can be increased by contributing to an increase in fitness, so that the placement optimization problem can be processed at high speed.

At this time, since the local sparse / dense elimination algorithm is executed and the local sparse / dense elimination method (LO) is executed, the sparse / dense elimination can be effectively performed with good visibility.
As described above, the placement optimization problem processing method according to the present invention includes a first algorithm execution step for executing a genetic algorithm when a plurality of placement elements 9 for which connection relations are defined is placed in a required space, and a local algorithm. By providing the second algorithm execution step for executing the sparse / dense elimination algorithm, the sparse / dense of the plurality of placement elements 9 in the initial placement state is eliminated, and the plurality of placement elements 9 are optimally placed in the placement region 10. Although the placement optimization problem to be placed is processed, each embodiment in which the first algorithm execution step and the second algorithm execution step are combined will be described in detail below.

(B2) Description of First Embodiment A placement optimization problem processing method according to the first embodiment of the present invention will be described.
In the layout optimization problem processing method according to the first embodiment, the genetic algorithm (GAc) is executed in the first algorithm execution step (step S3 in FIG. 2), and the second algorithm execution step (step S4 in FIG. 2). ) Executes an algorithm to which an analogy of fluid dynamics is applied as a local sparse / dense elimination algorithm.

Here, the genetic algorithm (GAc) executed in the first embodiment is a genetic algorithm for directly eliminating the density of the arrangement elements 9 by regarding the arrangement result of the arrangement elements 9 as a chromosome.
That is, in the layout optimization problem processing method according to the first embodiment, after applying the genetic algorithm (GAc) to each chromosome (that is, the layout result of the layout element 9), control parameters ( That is, by applying a local sparse / dense elimination method (LO) having a different arrangement element 9 movement method to each chromosome, the sparseness of the arrangement element 9 is effectively eliminated. This placement optimization problem processing method can be expressed as GAc + LO.

Here, the sparse / dense elimination method using the genetic algorithm (GAc) will be described with reference to FIGS.
First, the genetic algorithm is explained. The genetic algorithm is a technology that imitates the genetic mechanism of an organism and applies it to engineering, and can be considered as a method of probabilistic search, learning, and optimization. .

In the process of evolution of organisms, when a new individual (child) is born from an existing individual (parent), crossing of chromosomes of the individual, gene mutation on the chromosome, etc. occur. Individuals that do not adapt to the environment are deceived, and individuals that adapt to the environment survive to become new parents and create new offsprings, so that a group of individuals adapted to the environment survives.
The degree to which each individual adapts to the environment is determined by chromosomes (one-dimensional strings of genes), but in genetic algorithms, solution candidates for the placement optimization problem are expressed as chromosomes that are one-dimensional strings of genes. The Then, the fitness function corresponding to the so-called environment corresponds to a so-called environment, and an fitness function that takes a larger value is defined for the chromosome.

In the genetic algorithm, in order to generate chromosomes (solutions that optimize the objective function) that can be the optimal solution of the problem by changing the gene sequence of the chromosomes, various chromosomes as shown in FIG. Genetic operations (selection / self-replication, crossover and mutation) are performed.
Here, selection / self-replication (Reproduction) is an operation to select an individual having a highly-adapted chromosome in a group with a higher probability to be a next generation parent (see FIG. 9). Crossover is an operation to create a new individual (child) by exchanging part of two parental chromosomes (see Fig. 10). Mutation is a part of one chromosome gene. Is an operation of changing the individual by randomly replacing (see FIG. 11).

Then, by performing these genetic operations, it is possible to obtain a chromosome with a higher fitness value (ie, a solution that optimizes the objective function).
Here, in the first embodiment, the first algorithm execution step expresses the arrangement state of the plurality of arrangement elements 9 as a gene, and as a solution candidate for the problem of arranging the plurality of arrangement elements 9 in the arrangement area 10, A genetic algorithm (GAc) is executed by using a chromosome which is composed of the sequence of the gene and is defined as the arrangement region 10.

First, in the first algorithm execution step, when executing the genetic algorithm (GAc), the chromosome is divided into a plurality of band-like regions by dividing the arrangement region 10 into a plurality of partial regions 10a.
That is, in the first algorithm execution step, the arrangement results of the arrangement elements 9 are duplicated as necessary, and these are used as parent chromosomes. Next, as described above, the arrangement region 10 is divided into bands in the vertical direction or the horizontal direction (see FIGS. 3A and 3B), and the chromosome is divided into a plurality of band regions. However, when executing the genetic algorithm (GAc), it is assumed that the dividing direction is the same for all chromosomes.

Subsequently, in the first algorithm execution step, at least one band region selected from the plurality of band regions in the chromosome is converted into a band region corresponding to the band region in another chromosome (this band region is the band region). Crossover as a genetic operation is performed by exchanging for the same element as the element included in the region.
An example of crossover is shown in FIG. As shown in FIG. 6, the chromosomes 11 and 12 are stochastically selected as parent chromosomes to make copies of these, and among the band-like regions A _{1 to} A _{4 of} the chromosome 11 and the band-like regions B _{1 to} B ₄ of the chromosome 12 Crossover is performed by exchanging the selected strip regions with each other. 6, replace the band-like region B ₃ strip-like regions A ₃ and chromosome 12 in chromosome 11, examples give the band region _{A 1, A 2, B 3} , A 4 chromosome 13 of the child consisting of the It is shown. FIG. 6 shows an example in which one band-like region of chromosomes is selected, and this portion is exchanged between chromosomes to perform crossover. The crossover may be executed by exchanging these parts.

  Further, in the first algorithm execution step, the density of a certain band-like region among the plurality of band-like regions in one chromosome is eliminated compared to the band-like region corresponding to the band-like region in the other chromosome. In some cases, crossover as a genetic operation may be executed by pasting the band-like region in the chromosome to the band-like region corresponding to the band-like region in another chromosome.

For example, one or a plurality of the zonal regions R _i (i = 1,..., N) of one chromosome having a remarkable arrangement element 9 are selected, and if the corresponding zonal region R _i ′ ( If the density of the arrangement elements 9 of i = 1,..., N) is less than the banded region R _{i of} one chromosome, the banded region R _i ′ of the other chromosome is pasted to the corresponding part of one chromosome Thus, crossover can be executed.

Further, the density of the arrangement element 9 in the band-like region R _i of one chromosome is compared with the density of the arrangement element 9 in the corresponding band-like area R _i ′ of the other chromosome, and if the density of the other chromosome is less By pasting the region R _i ′ to the corresponding part of one chromosome, and conversely, if there is a band-like region R _i with low density on one chromosome, it is pasted to the corresponding part of the other chromosome, Crossover may be performed.

Further, in the first algorithm execution step, at least one of the plurality of arrangement elements 9 is moved in at least one of the plurality of band-like areas, whereby a genetic operation is performed. Mutation is performed.
Here, an example of the mutation is shown in FIG. As shown in FIG. 7, mutation is executed by selecting a placement element 9 with a certain probability and moving the placement element 9 randomly within a region R _i to which the placement element 9 belongs. In FIG. 7, the arrangement element 9 to be moved is shaded.

Finally, in the first algorithm execution step, selection as a genetic operation is performed using a fitness value function (fitness function) that allows a chromosome with a small density of the plurality of arrangement elements 9 to take a large fitness value. Is done.
Here, when executing the selection, a fitness value function defined as follows may be used.

Fitness value = constant− (maximum value of arrangement element density−minimum value of arrangement element density) (1)
Fitness value = constant− (area of arrangement area where arrangement element density is below average arrangement element density) (2)
Fitness value = constant− (area of arrangement area where arrangement element density is equal to or higher than average arrangement element density) (3)
Furthermore, a local sparse / dense elimination method (LO) will be described with reference to FIGS.

As described above, the local sparse / dense elimination method (LO) executes the local sparse / dense elimination algorithm to move the placement element 9 from a place where the placement element density is high to a place where the placement element density is low in the partial area 10a of the placement area 10. This eliminates the density of the arrangement elements 9 in the intermediate arrangement state. Note that the local sparse / dense elimination method (LO) is applied to each chromosome (each placement result).
Here, in the first embodiment, as the local sparse / dense elimination algorithm, the sparse / dense of the arrangement element 9 is eliminated using an algorithm to which an analogy of fluid dynamics is applied.

An analogy of hydrodynamics is that the movement of the arrangement element 9 in the partial area 10a of the arrangement area 10 is regarded as a kind of fluid movement, the mutual influence of the flow (movement) of the arrangement element 9 in the adjacent partial area 10a, The mutual influence of the flow in the same partial region 10a is considered in the analogy of viscosity.
When the density of the arrangement elements 9 is eliminated using an algorithm to which an analogy of fluid mechanics is applied, first, the arrangement area 10 is divided into a predetermined width in the vertical direction or the horizontal direction, and the arrangement area 10 10 is divided into a plurality of band-like regions.

Here, in the first embodiment, when the genetic algorithm is executed, the arrangement region 10 is divided into a plurality of partial regions 10a, so that the partial region 10a can be used as a belt-like region as it is.
Further, the arrangement area 10 may be divided into a plurality of band-like areas by newly dividing the arrangement area 10 again.

In this case, when the number of divided vertically band-like region and N present, each band region is S _1, S _2, ..., can be represented by S _N. Similarly, when the number of the divided strip-like region in the horizontal direction and M present, each swathe T _1, T _2, ..., can be represented by T _M. In addition, the width | variety of each strip | belt-shaped area | region ( _Si , _Ti ) may each differ.
Further, if the division of the arrangement area 10 is hierarchized, the density of the arrangement elements 9 can be easily made uniform. In addition, when the division | segmentation of the arrangement | positioning area | region 10 is made fine, there exists a method (refer FIG. 12 (a)-FIG.12 (d)) which advances division symmetrically, and a method which advances division asymmetrically.

On the other hand, if the arrangement area 10 is subdivided from the beginning without being divided hierarchically, the calculation time can be reduced as compared with the method of dividing the arrangement hierarchically.
When the placement area 10 is divided into a plurality of strip-shaped region, the configuration element 9 located in the band-like region T _i (S _i), this band-like region T _i (S _i) in the placement element density uniformly in Move to be. That is, imitating the movement of the fluid from a high density place to a low place, moving the placement element 9 from a high density position to a low density position.

That is, in the second algorithm execution step (step S4 in FIG. 2), at least one placement element 9 among the plurality of placement elements 9 in the intermediate placement state is placed from a place where the placement element density is high. By moving to a lower place, an algorithm to which an analogy of hydrodynamics is applied is executed.
When the arrangement area 10 is divided into a plurality of partial areas 10a, the second algorithm execution step includes at least one of the plurality of arrangement elements 9 included in the partial area 10a in the divided partial area 10a. One placement element 9 is moved from a place where the placement element density is high to a place where the placement element density is low.

Here, when the arrangement element 9 is moved, the following method can be used.
(1) Preservation of proximity In terms of fluid analogy, adjacent placement elements 9 are not easily separated away due to viscosity.
Accordingly, as shown in FIGS. 14A and 14B, the adjacent arrangement elements 9 are moved so as to be located close to each other after the movement.

That is, in the second algorithm execution step, at least one of the plurality of arrangement elements 9 can be moved while preserving the proximity between the plurality of arrangement elements 9.
(2) Preserving Order As shown in FIGS. 15A and 15B, when a certain arrangement element 9 and another arrangement element 9 have a predetermined positional relationship (for example, when a certain arrangement element 9 is In the case where the position is on the right side or the right side of another position element 9), the position elements 9 are moved so that the two position elements 9 maintain this positional relationship even after the movement.

This serves to preserve the relative positional relationship between the placement elements 9 given by the solution of the placement optimization problem.
That is, in the second algorithm execution step, at least one of the plurality of arrangement elements 9 can be moved while preserving the order between the plurality of arrangement elements 9.

(3) Sequential addition method Instead of considering the movement of all the arrangement elements 9 at a time, the movement of only a few arrangement elements 9 is considered at first. After moving these few placement elements 9 and making the density of these few placement elements 9 uniform, a small number of placement elements 9 are again selected from the placement elements 9 not yet considered, and the movement has already ended. Is added to the set of arranged elements 9. Then, the arrangement element 9 is moved again so that the density of the arrangement elements 9 is made uniform for the set of arrangement elements 9 to which the arrangement elements 9 are newly added.

For example, as shown in FIG. 16A, the arrangement element 9 is divided into a set of arrangement elements 9 indicated by reference numeral A and a set of arrangement elements 9 indicated by reference numeral B. In FIG. 16A, the arrangement element 9 indicated by reference numeral A is indicated by diagonal lines, and the arrangement element 9 indicated by reference numeral B is indicated by shading.
First, as shown in FIGS. 16 (b) and 16 (c), the density of the set of arrangement elements 9 indicated by symbol A is eliminated, and the density is eliminated as shown in FIG. 16 (d). A set of arrangement elements 9 indicated by reference numeral B is added to the set of arrangement elements 9. Subsequently, as shown in FIG. 16E, the density of the set of the arrangement elements 9 indicated by the symbol B is eliminated.

In other words, in the second algorithm execution step, the arrangement elements 9 that are the objects of the density elimination can be sequentially added when the density of the plurality of arrangement elements 9 in the intermediate arrangement state is eliminated.
(4) Consideration of Fixed Arrangement Elements The fixed arrangement element is an arrangement element 9 that cannot be moved. However, when there is a fixed arrangement element, only the arrangement elements 9 other than the fixed arrangement element are considered without considering the fixed arrangement element. If moved, the arrangement element density around the fixed arrangement element tends to increase.

Therefore, in order to prevent the arrangement elements 9 from being accumulated around the fixed arrangement elements, when there are fixed arrangement elements among the plurality of arrangement elements 9, the fixed arrangement elements are also eliminated in the second algorithm execution step. It is preferable to consider the arrangement elements 9 to be targeted and eliminate the density of the plurality of arrangement elements 9 in the intermediate arrangement state.
(5) Consideration of Large Arrangement Elements If there is an arrangement element that occupies the arrangement area 10 in comparison with other arrangement elements 9, if this large arrangement element is moved, the large arrangement element becomes a large number of arrangement elements 9. Since they tend to overlap, there is a risk of significantly increasing the placement element density.

In order to avoid this, the movement amount of a large arrangement element should be relatively small compared to the movement amounts of other arrangement elements 9.
That is, when there is a large arrangement element among the plurality of arrangement elements 9, in the second algorithm execution step, the movement amount of the large arrangement element is reduced to reduce the movement amount of the plurality of arrangement elements 9 in the intermediate arrangement state. It is preferable to eliminate the density.

In addition, as shown in FIG. 17, care is required when a large arrangement element 9a exists in the arrangement area 10 so as to straddle the band-like area T _i and the band-like area T _{i + 1} . In particular, when the movement direction of the arrangement element 9 around the large arrangement element 9a is opposite between the band-like region T _i and the band-like region T _{i + 1} , it is necessary to prevent the large arrangement element 9a from moving.
(6) Method for eliminating the density of the band-like region having a high arrangement element density The method for eliminating the density of the band-like region S _i (T _i ) having a high arrangement element density is performed by moving the arrangement elements 9 at once (at a time). There are a method of eliminating the high density belt-like regions S _i (T _i ) and a method of gradually moving the placement elements 9 gradually (in steps) to increase the placement element density in steps.

That is, in the second algorithm execution step, when the density of the plurality of arrangement elements 9 in the intermediate arrangement state is eliminated, the arrangement elements 9 to be moved may be moved at once, or the elements to be moved May be gradually moved.
Thereby, in the layout optimization problem processing method according to the first embodiment, in the first algorithm execution step, when information on the initial layout state of the plurality of layout elements 9 is input, the genetic algorithm (GAc) is calculated. As a result, the density of the plurality of arrangement elements 9 in the initial arrangement state is eliminated.

In the second algorithm execution step, when information on the intermediate arrangement state of the plurality of arrangement elements 9 after the density is eliminated in the first algorithm execution step, the local density elimination algorithm is executed. Further, the density of the plurality of arrangement elements 9 in the intermediate arrangement state is further eliminated.
By executing the first algorithm execution step and the second algorithm execution step as described above, it is possible to process an arrangement optimization problem in which the plurality of arrangement elements 9 are arranged in an optimum state in the arrangement area 10.

As described above, according to the layout optimization problem processing method according to the first embodiment of the present invention, the local density using a genetic algorithm (GAc) and the algorithm to which an analogy of fluid dynamics is applied. Since the resolution method (LO) is combined, the increase in fitness can be accelerated and the speed of the genetic algorithm (GAc) can be realized.
Moreover, in the genetic algorithm (GAc), crossover suitable for eliminating the density of the arrangement elements 9 is introduced, so that the solution can be generated efficiently and the optimum solution can be searched efficiently. .

Furthermore, the second algorithm execution step moves the placement element 9 while preserving the proximity between the plurality of placement elements 9, or moves the placement element 9 while preserving the order between the plurality of placement elements 9. As a result, the range of layout optimization problems that can be processed can be expanded.
In addition, when the second algorithm execution step eliminates the density of the arrangement elements 9, the arrangement elements 9 that are the targets for the density elimination are sequentially added, or the fixed arrangement elements are also regarded as the arrangement elements 9 that are the objects of the density elimination. Since the movement amount of the large arrangement element 9 can be reduced, the arrangement element 9 to be moved can be moved all at once, or the arrangement element 9 to be moved can be gradually moved. The range can be expanded.

  In the above description, the genetic algorithm (GAc) is performed in the first algorithm execution step, and then the local algorithm is performed in the second algorithm execution step. The case where the sparse / dense elimination method using the local algorithm (GAc) and the local sparse / dense elimination method (LO) are combined has been described. However, while the first algorithm execution step is executing the genetic algorithm (GAc), the second By executing the local sparse / dense elimination algorithm in the algorithm execution step, the sparse / dense elimination method by the genetic algorithm (GAc) and the local sparse / dense elimination method (LO) can be combined.

The operation of the arrangement optimization problem processing apparatus 1 at this time will be described using the flowchart shown in FIG.
First, the initial optimization result (information regarding the initial arrangement state) of the plurality of arrangement elements 9 is input to the arrangement optimization problem processing apparatus 1 (step A1).
When the initial placement result of the placement element 9 is input, the placement optimization problem processing apparatus 1 prepares a population of chromosomes by making a copy of the placement result in the first algorithm execution step (step A2). ).

  Subsequently, in the second algorithm execution step, for each chromosome (each placement result), a local sparse / dense elimination method (LO) is executed in which the method for dividing the placement region 10 is the same but other control parameters are different. Attempts are made to eliminate the density of the arrangement result (step A3). The local sparse / dense elimination method (LO) is executed using an algorithm to which an analogy of fluid dynamics is applied.

Furthermore, in the first algorithm execution step, crossover, mutation and selection as genetic operations are performed on each chromosome (steps A4 to A6), and the chromosome with the highest fitness value (optimum chromosome) is adapted. It is determined whether the degree value is equal to or greater than a predetermined reference value, or whether the arrangement result has been eliminated (step A7).
When it is determined that the optimal fitness value of the chromosome is not equal to or greater than a predetermined reference value, or the arrangement result is not resolved, the process after step A3 is repeated (NO route of step A7). ) If it is determined that the optimal fitness value of the chromosome is equal to or higher than a predetermined reference value or the density of the arrangement result has been eliminated, the optimal chromosome is output as a solution to the arrangement optimization problem. Thus, the processing in the placement optimization problem processing apparatus 1 is completed (YES route in step A7).

Even if it does in this way, the same advantage as what was mentioned above can be acquired.
Further, when executing the local sparse / dense elimination method (LO) using an algorithm to which an analogy of fluid mechanics is applied, as shown in FIGS. Each of the placement elements 9 is moved while being divided in the direction, and each placement element 9 is moved by dividing the other placement region 10 in the horizontal direction to move the specific placement element 9 in the vertical division (moving direction). And the movement amount) and the movement in the horizontal division (movement direction and movement amount) are considered as vectors, for example, and by combining the two vectors, the movement direction and movement amount of the specific arrangement element 9 are determined. The specific arrangement element 9 may be moved based on this.

(B3) Description of Modified Example of First Embodiment In the first embodiment described above, when the second algorithm execution step executes the local sparse / dense elimination method (LO), as a local sparse / dense elimination algorithm, Although the case where an algorithm to which a dynamic analogy is applied has been described, the second algorithm execution step can use an algorithm to which a morphing analogy is applied as a local sparse / dense resolution algorithm.

  The morphing analogy imitates morphing, which is an image processing technique that gradually transforms a two-dimensional image into another image, and morphs the movement of the arrangement element 9 in the partial area 10a of the arrangement area 10. This is taken as a deformation operation in. However, unlike the morphing of the image processing technique, the size and shape of the arrangement element 9 itself are not changed, and only the position coordinates of the arrangement element 9 on the arrangement area 10 are changed.

  When the density of the arrangement elements 9 is eliminated by the morphing analogy, as shown in the first embodiment, each band-like area obtained by dividing the arrangement area 10 is shown in FIG. As shown to (a), the center point (morphing center part) C at the time of moving the arrangement | positioning element 9 is determined, respectively. Then, as shown in FIG. 19 (b), with the center point C as a reference, the placement elements are maintained while maintaining the relative positional relationship between the placement elements 9 according to the distance from the center point C to the placement elements. The distance between the arrangement elements 9 is increased by increasing the coordinates of the arrangement elements 9, and the arrangement elements 9 are arranged in the direction of the arrangement elements 9 (that is, the arrangement elements 9 are arranged radially from the center point C in the direction in which the arrangement elements 9 exist). Move).

Here, the center point C of the morphing can be determined by any of the following methods.
(1) Method using the center of gravity of the arrangement element 9 This is a method in which the position of the center of gravity of the arrangement element 9 is used as the center of morphing.
That is, when the coordinates of each placement element 9 are (x ₁ , y ₁ ), (x ₂ , y ₂ ),..., (X _M ′, y _M ′), the center of the morphing is its center of gravity,

It is a method.
(2) Method based on the number of placement elements 9 In each strip-like region of the placement region 10, the number of placement elements 9 that are perpendicular to the X-axis of the strip-like region and are located on both sides of this line are equal. A line (a line perpendicular to the X axis that bisects the number of arrangement elements in the X direction) is equal to the number of arrangement elements 9 that are perpendicular to the Y axis of the belt-like region and are located on both sides of the line. A line (a line perpendicular to the Y axis that bisects the number of arranged elements in the Y direction) is determined. And it is the method which makes the intersection of these two lines the center of morphing.

(3) Method Based on Area of Arrangement Element 9 In each band-like area of arrangement area 10, the area of arrangement element 9 which is a line perpendicular to the X axis of the band-like area and located on both sides of this line is equal. The line (a line perpendicular to the X axis that bisects the total area of the arrangement element in the X direction) and the area of the arrangement element 9 that is perpendicular to the Y axis of the belt-like region and is located on both sides of this line Are equal to each other (a line perpendicular to the Y axis that bisects the total area of the arranged elements in the Y direction). And it is the method which makes the intersection of these two lines the center of morphing.

  That is, in the second algorithm execution step, a center point C is determined based on information (the centroid, total number, total area, etc. of the arrangement elements 9) regarding the plurality of arrangement elements 9 in the intermediate arrangement state, and the plurality of arrangement elements 9 By moving at least one arrangement element 9 out of 9 to a location separated from the center point C, an algorithm to which a morphing analogy is applied is executed.

  When the placement area 10 in which the plurality of placement elements 9 are placed is divided into a plurality of belt-like areas (or partial areas 10a), the second algorithm execution step determines the center point C for each belt-like area, In the belt-like region, at least one of the plurality of placement elements 9 included in the belt-like region is moved to a place separated from the center point C.

Here, how to determine the movement amount of the placement element 9 will be described below.
(1) Linear expansion of the movement amount of the placement element 9 In proportion to the distance from the center point C of the morphing to the center of the placement element 9 (that is, linearly), the direction from the center point C toward the placement element 9 To move the arrangement element 9.
That is, in the second algorithm execution step, when moving at least one of the plurality of arrangement elements 9 to a place separated from the center point C, the process from the center point C to the arrangement element 9 to be moved is performed. The distance can be expanded linearly.

(2) Non-linear expansion of the movement amount of the placement element 9 When the placement element 9 is moved from the morphing center point C in the direction of the placement element 9, the distance moved is from the center point C to the placement element 9. It is defined by a non-linear function corresponding to the distance to the center.
Specifically, since the arrangement element 9 is close and dense in the vicinity of the center point C, the movement amount of the arrangement element 9 in the vicinity of the center point is increased, while the inside of the divided belt-like area (or partial area 10a) is increased. In order to move the placement element 9, the movement amount of the placement element 9 in the vicinity of the border of the band-like region is made smaller.

That is, in the second algorithm execution step, when moving at least one of the plurality of arrangement elements 9 to a location separated from the center point C, the process from the center point C to the arrangement element 9 to be moved is performed. It is also possible to increase the distance nonlinearly.
Even when the local sparse / dense elimination method (LO) is executed using an algorithm to which such a morphing analogy is applied, the same advantages as those in the first embodiment described above can be obtained.

Further, when the second algorithm execution step moves the placement element 9 to a location separated from the center point C, the distance from the center point C to the placement element 9 to be moved is linearly expanded, Since the distance from the point C to the placement element 9 to be moved can be increased nonlinearly, the range of placement optimization problems that can be processed can be expanded.
Even in the placement optimization problem processing method according to the modification of the first embodiment, when eliminating the density of the placement elements 9, as described in the first embodiment, a sequential addition method may be used, A fixed arrangement element or a large arrangement element can be considered, or the arrangement element 9 can be moved at once or gradually.

(B4) Description of Second Embodiment An arrangement optimization problem processing method according to the second embodiment of the present invention will be described.
In the placement optimization problem processing method according to the second embodiment, the genetic algorithm (GAp) is executed in the first algorithm execution step (step S3 in FIG. 2), and the second algorithm execution step (step S4 in FIG. 2). ), An algorithm to which the analogy of fluid dynamics described above in the first embodiment is applied is executed as a local sparse / dense elimination algorithm.

Here, the genetic algorithm (GAp) executed in the second embodiment is a genetic algorithm for optimizing the width of dividing the arrangement region 10 in the local sparse / dense elimination method (LO).
That is, the placement optimization problem processing method according to the second embodiment applies the genetic algorithm (GAp) to each chromosome consisting of a list of widths that divide the placement region 10 which is a parameter of the local sparse / dense elimination method (LO). By doing so, the division of the arrangement area 10 is optimized to efficiently eliminate the density of the arrangement elements 9.

In other words, in this method, in order to optimize the division method of the arrangement region 10, the parameter (width of the arrangement region 10) in the local sparse / dense elimination method (LO) is genetically set with the given arrangement as the initial arrangement. This is a method for efficiently eliminating the density by optimizing with an algorithm (GAp).
This placement optimization problem processing method can be expressed as GAp + LO.

  That is, in the second embodiment, the first algorithm execution step expresses a parameter used in the local sparse / dense elimination algorithm executed in the second algorithm execution step as a gene, and solves the problem of determining this parameter. A genetic algorithm (GAp) is executed by using a chromosome comprising the sequence of the gene as a candidate.

Here, the parameters are composed of information defining the width for dividing the arrangement region 10 (information defining the size of the partial region 10a) and other control parameters for the local density elimination method (LO).
That is, in the genetic algorithm (GAp), a chromosome composed of a list of information that defines the width of the partial region 10a and a list of control parameters for other local sparse / dense resolution (LO) is used.

For example, in the case of dividing the layout region 10 in the vertical direction, the band region S _1, S _2, ..., respectively W _1, W ₂ the widths of the S _N, ..., chromosomal structure when formed into a W _N, FIG. 20 shows. Here, the sum of the widths W ₁ , W ₂ ,..., W _N must be equal to the lateral width of the placement region 10. Chromosome 14 also has control parameters a ₁ and a _{2 of} other local sparse / dense elimination methods as genes.

Then, in the first algorithm execution step, the weighted average of the genes of the two parent chromosomes is used as the gene of the child chromosome, so that the crossover as a genetic operation is executed.
An example of crossover is shown in FIG. As shown in FIG. 21, chromosomes 15 and 16 are stochastically selected as parent chromosomes to make a copy of these, taking an appropriate weighted average of the chromosome 15 gene and the chromosome 16 gene, and taking this as the child chromosome. Crossover is performed by setting 17 genes.

Incidentally, in FIG. _{21, W 1 ~W 4 ...,} M 1 ~M 4 ..., Z 1 ~Z 4 ... it is band region S _1, S _2, ..., and the width of the S _N, a ₁ ... , B ₁ ..., C ₁ ... Indicate other control parameters of the local density cancellation method (LO).
here,
Z _i = (W _i + M _i ) / 2 (4)
c _i = (a _i + b _i ) / 2 (5)
It is.

In addition, in the first algorithm execution step, while adjusting so that the sum of the information defining the width of the partial region 10a included in the parameter does not change, a part of the zonal region of the chromosome is changed to the zonal region of another chromosome. Crossing as a genetic operation may be performed by pasting the corresponding band-like region.
For example, when pasting a portion of one chromosome to another chromosome, the width W _1, W _2, ..., crossover while adjusting the gene from the original to the other chromosome such that the sum of W _N does not change execution To do. The same applies when a part of the other chromosome is attached to one chromosome.

Further, in the first algorithm execution step, at least two genes of the chromosome are selected, and an arbitrary numerical value is added to the selected gene, thereby changing the sum of information defining the width of the partial region 10a included in the parameter. The mutation as a genetic operation is executed in such a manner that the mutation is not performed.
In other words, mutations are caused by randomly giving small changes to chromosomal genes. Specifically, a predetermined number is added to one of the selected genes, while a predetermined number is added from the other gene. By subtracting, mutation is executed while adjusting so that the total sum of information defining the width of the partial region 10a does not change.

Here, an example of the mutation is shown in FIG. As shown in FIG. 22, any two genes W ₃ and W ₅ of the chromosome 18 are selected and a small positive random number ΔW is added to the gene W ₅ while subtracting the random number ΔW from the gene W ₃ The chromosome 18 is changed to the chromosome 18 'while adjusting so that the total sum of the information defining the width of the region 10a does not change. In the example shown in FIG. 22, the chromosome 18 is also mutated by adding a random number Δa having a small absolute value to the control parameter a ₂ of other local sparse / dense elimination (LO).

More generally, if any two genes of the chromosome are W _i , W _j , a small positive random number is ΔW, and the genes after mutation are W _i ′, W _j ′, the genes W _i ′, W _j 'Can be expressed as follows.
W _i ′ = W _i −ΔW (6)
W _j ′ = W _j + ΔW (7)
In addition, in the first algorithm executing step, any of the m genes W _i1 chromosome, W _i2, ..., select W _im, [Delta] W _i1 small random absolute value, [Delta] W _i2, ..., using the [Delta] W _im Te, these genes W _i1, W _i2, ..., gene W _i1 subjected to a mutation in the _{W im ', W i2',} ..., may generate the W _im '.

At this time, genes W _i1 ′, W _i2 ′,..., W _im ′ can be expressed as follows.
W _ik ′ = W _ik + ΔW _ik
However, ΔW _i1 + ΔW _i2 +... + ΔW _im = 0 (8)
As described above, in the second embodiment, in the first algorithm execution step, a plurality of optimal value candidates (optimum width candidates) for the division width of the arrangement region 10 are obtained by executing the genetic algorithm (GAp). It is done.

Thereafter, in the second algorithm execution step, the placement area 10 is divided by each of the plurality of optimum width candidates obtained in the first algorithm execution step, and a local sparse / dense elimination method (LO) is executed, thereby An attempt is made to eliminate the density of the plurality of arrangement elements 9 in the arrangement state.
In the second embodiment, the process returns to the first algorithm execution step again. In the first algorithm execution step, the fitness value function defined as follows (that is, the plurality of arrangement elements 9) Selection as a genetic operation is performed using a fitness value function that allows a chromosome that can reduce sparseness to have a large fitness value), and a chromosome as a placement result that is least sparsely sparse is selected. .

Fitness value = constant− (maximum arrangement element density−minimum arrangement element density) (9)
Fitness value = constant− (area of arrangement area where arrangement element density is below average arrangement element density) (10)
Fitness value = constant− (area of arrangement area where arrangement element density is greater than or equal to average arrangement element density) (11)
In other words, using these fitness value functions, it is possible to improve the local sparse / dense cancellation method (LO) and, as a result, improve the sparse / dense cancellation of the placement element 9.

That is, in the layout optimization problem processing method according to the second embodiment, the parameters used when executing the local sparse / dense elimination algorithm are executed by combining the first algorithm execution step and the second algorithm execution step. By obtaining the optimum value of a certain division width, the density of the plurality of arrangement elements 9 in the initial arrangement state is eliminated.
Thereby, the arrangement optimization problem of arranging the plurality of arrangement elements 9 in the arrangement area 10 in an optimum state can be processed.

As described above, according to the layout optimization problem processing method according to the second embodiment of the present invention, the division of the layout area 10 is optimized by the genetic algorithm (GAp). Can be eliminated.
Further, a plurality of arrangement regions 10 are divided by various widths designated by each chromosome obtained by executing the genetic algorithm (GAp), and different local sparse / dense resolution methods (LO) are divided into the plurality of arrangement regions 10. And the optimum local sparse / dense elimination method (LO) is found, so that the optimum division method of the arrangement region 10 can be searched.

As described below, while the first algorithm execution step executes the genetic algorithm (GAp), the second algorithm execution step executes the local sparse / dense elimination algorithm, It is also possible to combine a genetic algorithm (GAp) and a local sparse / dense elimination method (LO).
The operation of the arrangement optimization problem processing apparatus 1 at this time will be described with reference to the flowchart shown in FIG.

First, the initial optimization result (information regarding the initial arrangement state) of the plurality of arrangement elements 9 is input to the arrangement optimization problem processing apparatus 1 (step B1).
When the initial arrangement result of the arrangement element 9 is input, the arrangement optimization problem processing apparatus 1 prepares a chromosome group using the local sparse / dense elimination (LO) parameter as a gene by the first algorithm execution step. (Step B2).

  Subsequently, in the second algorithm execution step, the local density cancellation method (LO) corresponding to each chromosome tries to eliminate the density [that is, the plurality of arrangement regions 10 are divided by the width specified by each chromosome. Then, for each arrangement region 10, the local density is eliminated by the local density elimination method (LO)], and the fitness value is calculated (step B 3). The local sparse / dense elimination method (LO) is executed using an algorithm to which an analogy of fluid dynamics is applied.

  Thereafter, in the first algorithm execution step, each chromosome is subjected to crossover and mutation as genetic operations (steps B4 and B5), and the fitness value of the chromosome having the highest fitness value (optimal chromosome) is obtained. Is equal to or greater than a predetermined reference value, or when the arrangement region 9 is divided by a width determined by the chromosome having the highest fitness value and the local sparse / dense elimination method (LO) is executed, the arrangement element 9 It is determined whether or not the result of resolution elimination is satisfactory (step B6).

  When it is determined that the optimal fitness value of the chromosome is not equal to or greater than a predetermined reference value, or the result of the sparse / dense elimination of the arrangement element 9 is not satisfactory, the processes after step B3 are repeated (step B6). If the optimal chromosome fitness value is greater than or equal to a predetermined reference value, or if it is determined that the sparse / dense elimination result of the arrangement element 9 is satisfactory, then the arrangement element 9 at that time Is output as a solution to the placement optimization problem, and the processing in the placement optimization problem processing apparatus 1 ends (YES route in step B6).

Even if it does in this way, the same advantage as what was mentioned above can be acquired.
Also in the layout optimization problem processing method according to the second embodiment, when eliminating the sparseness of the layout elements 9, as described in the first embodiment, the sequential addition method may be used, or the fixed layout elements may be used. It is possible to consider a large arrangement element, move the arrangement element 9 all at once, or move it gradually.

(B5) Description of Modified Example of Second Embodiment In the second embodiment described above, when the second algorithm execution step executes the local sparse / dense elimination method (LO), the local sparse / dense elimination algorithm is used. As described above, the case where an algorithm to which an analogy of fluid dynamics is applied has been described. As in the case of the modified example of the first embodiment described above, the second algorithm execution step is performed as the above-described morphing as a local sparse / dense elimination algorithm. An algorithm to which the analogy is applied can also be used.

As described above, even when the local sparse / dense elimination method (LO) is executed using the algorithm to which the morphing analogy is applied, the same advantages as those of the second embodiment described above can be obtained.
Also in this case, when the density of the arrangement elements 9 is eliminated, as described in the first embodiment, a sequential addition method is used, a fixed arrangement element or a large arrangement element is considered, It goes without saying that it can be moved to or gradually moved.

(B6) Description of Third Embodiment A placement optimization problem processing method according to the third embodiment of the present invention will be described.
In the layout optimization problem processing method according to the third embodiment, the genetic algorithm (GAp) is being executed in the first algorithm execution step (step S3 in FIG. 2). Executes the genetic algorithm (GAc) and the second algorithm execution step (step S4 in FIG. 2) executes the local sparse / dense elimination algorithm, so that the genetic algorithm (GAp, GAc) and the local sparse / dense elimination method are executed. (LO).

In other words, the layout optimization problem processing method according to the third embodiment executes the genetic algorithm (GAc) at the end of each generation or at the end of multiple generations when obtaining an optimal solution using the genetic algorithm (GAp). In addition, a local sparse / dense elimination method (LO) is performed during the execution of the genetic algorithm (GAc).
That is, in this method, the genetic algorithm (GAc) and the local sparse / dense elimination method (LO) are inserted inside the genetic algorithm (GAp), and can be expressed as GAp + (GAc + LO).

The operation of the arrangement optimization problem processing apparatus 1 at this time will be described with reference to the flowchart shown in FIG.
First, the initial optimization result (information regarding the initial arrangement state) of the plurality of arrangement elements 9 is input to the arrangement optimization problem processing apparatus 1 (step C1).
When the initial placement result of the placement element 9 is input, the placement optimization problem processing apparatus 1 uses the first algorithm execution step to perform a genetic algorithm (using a local sparse / dense elimination method (LO) parameter) as a gene. A population of chromosomes of GAp) is prepared (step C2).

Subsequently, in the first algorithm execution step, crossover and mutation, which are genetic operations in the genetic algorithm (GAp), are performed on each chromosome (steps C3 and C4).
During the execution of the genetic algorithm (GAp), the genetic algorithm (GAc) is further executed by the first algorithm execution step, and the local sparse / dense elimination algorithm is executed by the second algorithm execution step. (Steps C5 to C12).

That is, in the first algorithm execution step, a population of chromosomes of the genetic algorithm (GAc) is prepared by making a copy of the initial placement result of the placement element 9 obtained in step C1 (step C5).
A plurality of genetic algorithms (by a width specified by a plurality of chromosomes of the genetic algorithm (GAp)) are divided by the division method of the arrangement region 10 specified by the plurality of chromosomes of the genetic algorithm (GAp). The arrangement region 10 which is a chromosome of GAc) is divided (step C6).

Further, in the first algorithm execution step, crossover and mutation, which are genetic operations in the genetic algorithm (GAc), are performed on each chromosome (steps C7 and C8).
Thereafter, in the second algorithm execution step, for each chromosome (each placement result), a local sparse / dense elimination method (LO) in which the division method of the placement region 10 is the same but other control parameters are different is executed. An attempt is made to eliminate the density of the arrangement result (step C9). The local sparse / dense elimination method (LO) is executed using an algorithm to which an analogy of fluid dynamics is applied or an algorithm to which an analogy of morphing is applied.

Further, in the first algorithm execution step, it is determined that the genetic algorithm (GAc) is performed on each chromosome after selection that is a genetic operation in the genetic algorithm (GAc) is performed (step C10). It is determined whether the number of generations has been exceeded (step C11).
If it is determined that the predetermined number of generations has not been exceeded (that is, if it is determined that the genetic algorithm (GAc) for the predetermined number of generations has not yet been executed), step C7 is performed. When the subsequent processing is repeated (NO route of step C11), when it is determined that the predetermined number of generations has been exceeded (that is, when it is determined that the genetic algorithm (GAc) for the predetermined number of generations has been executed) The fitness value of the optimal chromosome in the genetic algorithm (GAc) is set as the fitness value of the chromosome of the genetic algorithm (GAp) (from the YES route in step C11 to step C12).

  Thereafter, in the first algorithm execution step, the process returns to the execution of the genetic algorithm (GAp) again, and each chromosome is subjected to selection that is a genetic operation in the genetic algorithm (GAp) (step C13). It is determined whether the fitness value of the chromosome having the degree value (optimal chromosome) is equal to or greater than a predetermined reference value or whether the arrangement result has been eliminated (step C14).

  If it is determined that the optimal fitness value of the chromosome is not equal to or greater than a predetermined reference value, or the arrangement result is not resolved, the process after step C3 is repeated (NO route of step C14). ) If it is determined that the optimal fitness value of the chromosome is equal to or higher than a predetermined reference value or the density of the arrangement result has been eliminated, the optimal chromosome is output as a solution to the arrangement optimization problem. Then, the processing in the placement optimization problem processing apparatus 1 is completed (YES route in step C14).

  As described above, according to the layout optimization problem processing method according to the third embodiment of the present invention, it is possible to obtain the same effect as each of the embodiments described above, and during the execution of the genetic algorithm (GAp), Since the genetic algorithm (GAc) and the local sparse / dense elimination method (LO) are combined and executed, the genetic algorithm (GAp) can be further increased in speed.

(B7) Description of Fourth Embodiment A placement optimization problem processing method according to the fourth embodiment of the present invention will be described.
In the layout optimization problem processing method according to the fourth embodiment, the genetic algorithm (GAc) is being executed in the first algorithm execution step (step S3 in FIG. 2). Executes the genetic algorithm (GAp) and the second algorithm execution step executes the local sparse / dense elimination algorithm, thereby combining the genetic algorithm (GAp, GAc) and the local sparse / dense elimination (LO). It is.

That is, the layout optimization problem processing method according to the fourth embodiment executes the genetic algorithm (GAp) at the end of each generation or at the end of multiple generations when obtaining an optimal solution by the genetic algorithm (GAc). In addition, a local sparse / dense cancellation method (LO) is performed during the execution of the genetic algorithm (GAp).
That is, this method optimizes the division width of the arrangement region 10 by executing a combination of the genetic algorithm (GAp) and the local sparse / dense elimination method (LO) as described above in the second embodiment, The genetic algorithm (GAc) is executed using the arrangement region 10 divided by the division width as a chromosome of the genetic algorithm (GAc), and a solution is searched for more efficiently.

This placement optimization problem processing method can be expressed as GAc + (GAp + LO).
The operation of the arrangement optimization problem processing apparatus 1 at this time will be described using the flowchart shown in FIG.
First, the initial optimization result (information on the initial arrangement state) of the plurality of arrangement elements 9 is input to the arrangement optimization problem processing apparatus 1 (step D1).

When the initial placement result of the placement element 9 is input, the placement optimization problem processing apparatus 1 creates a copy of the initial placement result in the first algorithm execution step, thereby generating a population of chromosomes of the genetic algorithm (GAc). Prepared (step D2).
During execution of the genetic algorithm (GAc), the genetic algorithm (GAp) is further executed by the first algorithm execution step, and the local sparse / dense elimination algorithm is executed by the second algorithm execution step. (Steps D3 to D9).

That is, in the first algorithm execution step, a population of chromosomes of the genetic algorithm (GAp) using the parameters of the local sparse / dense elimination method (LO) as genes is prepared (step D3).
Subsequently, in the first algorithm execution step, crossover and mutation, which are genetic operations in the genetic algorithm (GAp), are performed on each chromosome (steps D4 and D5).

  Then, in the second algorithm execution step, the arrangement area 10 is divided by the division width represented by each chromosome, and the local sparse / dense elimination method (LO) is executed to try to eliminate the sparse / dense. A fitness value is calculated based on the result of the cancellation method (LO) (step D6). The local sparse / dense elimination method (LO) is executed using an algorithm to which an analogy of fluid dynamics is applied or an algorithm to which an analogy of morphing is applied.

Furthermore, in the first algorithm execution step, a selection that is a genetic operation in the genetic algorithm (GAp) is performed on each chromosome, and a chromosome having a large fitness value is selected (step D7). Thereafter, it is determined whether the number of generations determined to perform the genetic algorithm (GAp) has been exceeded (step D8).
When it is determined that the predetermined number of generations has not been exceeded (that is, when it is determined that the genetic algorithm (GAp) for the predetermined number of generations has not yet been executed), the above step D4 When the subsequent processing is repeated (NO route of step D8), when it is determined that the predetermined number of generations has been exceeded (that is, when it is determined that the genetic algorithm (GAp) for the predetermined number of generations has been executed) Is determined to be the optimal chromosome in the genetic algorithm (GAp) (from the YES route in step D8 to step D9).

  Thereafter, in the first algorithm execution step, the process returns to the execution of the genetic algorithm (GAc) again, and by the division method of the arrangement region 10 specified by the chromosome of the genetic algorithm (GAp) determined in the above step D9 [ie, The arrangement region 10 that is the chromosome of the genetic algorithm (GAc) is divided (with the width specified by the chromosome of the genetic algorithm (GAp) determined in step D9) (step D10).

Further, in the first algorithm execution step, crossover, mutation, and selection, which are genetic operations in the genetic algorithm (GAc), are performed on each chromosome (steps D11 to D13).
Then, it is determined whether the fitness value of the chromosome having the highest fitness value (optimal chromosome) is greater than or equal to a predetermined reference value or whether the arrangement result has been eliminated (step D14).

  When it is determined that the optimal fitness value of the chromosome is not equal to or greater than a predetermined reference value, or the arrangement result is not resolved, the processing after step D10 is repeated (NO route of step D14). ) If it is determined that the optimal fitness value of the chromosome is equal to or higher than a predetermined reference value or the density of the arrangement result has been eliminated, the optimal chromosome is output as a solution to the arrangement optimization problem. As a result, the processing in the placement optimization problem processing apparatus 1 ends (YES route of step D14).

  As described above, according to the layout optimization problem processing method according to the fourth embodiment of the present invention, it is possible to obtain the same effect as each of the embodiments described above, and during the execution of the genetic algorithm (GAc), Since the genetic algorithm (GAp) and the local sparse / dense elimination method (LO) are executed in combination, the genetic algorithm (GAc) can be further increased in speed.

(B8) Others In the first, third, and fourth embodiments described above, the genetic operation (GAc) is performed using the chromosome (that is, the arrangement region 10) divided in the same direction in either the vertical direction or the horizontal direction. Although the case of executing is described, the genetic operation (GAc) can also be executed using chromosomes divided in different directions.

The model used in this case is called an island model, and this island model will be described with reference to FIG.
The island model shown in FIG. 26 includes a first island 20 having a plurality of chromosome groups 21 divided in the vertical direction and a second island 22 having a plurality of chromosome groups 23 divided in the horizontal direction.

The first island 20 only needs to have at least one group 21, and the second island 22 only needs to have at least one group 23.
That is, in the first algorithm execution step, when the genetic algorithm (GAc) is executed, a plurality of strips are formed by dividing the arrangement region 10 in which the plurality of arrangement elements 9 are arranged into a plurality of partial regions 10a in the vertical direction. A first island 20 having at least one chromosome group 21 divided vertically in the region and a plurality of arrangement regions 10 in which the plurality of arrangement elements 9 are arranged are divided into a plurality of partial regions 10a in the horizontal direction. The second island 22 having at least one chromosome group 23 divided in the horizontal direction in the band-like region is used.

  Each of the groups 21 and 23 usually develops independently based on the genetic algorithm (GAc) or the local sparse / dense elimination method (LO). However, every time the genetic algorithm (GAc) is executed for an appropriate number of generations. Next, chromosomes are selected from one group 21 of the first island 20 and one group 23 of the second island 22 by some method, and crossover as a genetic operation is performed using these chromosomes having different division directions as parent chromosomes. The resulting child chromosomes can then be returned to their respective populations 21 and 23.

At this time, crossing between chromosomes having different division directions can be performed as follows.
(1) First method of crossover A chromosome selected from the group 21 is divided in the vertical direction, and when a local sparse / dense resolution method (LO) is applied to this chromosome, a specific arrangement element 9 belongs to it. It moves by a defined amount in a defined direction within the strip area. Let the amount of movement at this time be a vector x ₁ ′.

On the other hand, the chromosome selected from the group 23 is divided in the horizontal direction, and when this chromosome is subjected to the local sparse / dense elimination method (LO), the specific arrangement element 9 is defined in the band-like region to which it belongs. Move by a fixed amount in the direction. Let the amount of movement at this time be a vector x ₂ ′.
Then, the movement amount of the arrangement element 9 is obtained as a combined vector x ₁ ′ + x ₂ ′, and the arrangement element 9 is moved by the movement amount in each parental chromosome, whereby the chromosome selected from the group 21 and the group 23 Crossover is performed with the chromosomes selected from the above to generate child chromosomes, and each of the generated child chromosomes is returned to the original population.

  That is, in the first algorithm execution step, when executing the genetic algorithm (GAc), the local sparse / dense elimination method (LO) is applied to the chromosome belonging to the first island 20 while the chromosome belonging to the second island 22 is applied. By applying a local sparse / dense elimination method (LO), a specific arrangement element 9 within each region of the chromosome is moved. Then, a vector sum of the movement amounts of the specific arrangement element 9 in the chromosome belonging to the first island 20 and the chromosome belonging to the second island 22 is obtained, and the specific arrangement element 9 in each chromosome according to the vector sum. , The crossing as a genetic operation is executed between the chromosome belonging to the first island 20 and the chromosome belonging to the second island 22.

(2) Second method of crossover The chromosome selected from the group 21 has a band-like region divided in the vertical direction. This band-like region is read as a band-like region divided in the horizontal direction, and the chromosome of the group 23 Is incorporated into a chromosome selected from the group 21 and a chromosome selected from the group 23 to generate a child chromosome.

For example, if the arrangement elements 9 _{1 to} 9 ₃ are included in a certain band-like region divided in the vertical direction in the chromosome selected from the group 21, these arrangements are first arranged in the chromosome divided in the horizontal direction selected from the group 23. A band-like region including elements 9 _{1 to} 9 ₃ is found.
Then, the chromosomes are divided laterally, the result of finding the band-like region including these layout elements 91 _to 93 _3, the strip-like regions certain of the layout elements 9 _1, 9 ₂ band regions divided in the transverse direction It included in the arrangement elements 9 ₃ and were included in the other strip regions. In addition, the band-like region including the layout elements 9 _1, 9 _2, and also included other layout elements 9 _4.

At this time, the chromosomes are divided laterally, the arrangement with read as layout elements 9 _1, 9 ₂ and other layout elements 9 ₄ the configuration element 9 ₃ in strip regions included, are included in other strip-like regions by replaced elements 9 ₃ and layout elements 9 _4, it can be read a band-shaped region that is divided longitudinally in a strip region which is divided in the transverse direction.
Similarly, the band-like region in the chromosome selected from the group 23 is replaced with the band-like region divided in the vertical direction and incorporated into the chromosome of the group 21 to select the chromosome selected from the group 21 and the group 23. Crossover may be performed between chromosomes.

  That is, in the first algorithm execution step, when executing the genetic algorithm (GAc), a band-like region including a specific arrangement element 9 in a chromosome belonging to the first island 20 (or the second island 22) is extracted and extracted. The second band 22 (or the first island 20) is replaced with the band-shaped region in the chromosome belonging to the second island 22 (or the first island 20) and returned to the second island 22 (or the first island 20). Crossover as a genetic operation is executed between the chromosomes belonging to the island 22.

The operation of the arrangement optimization problem processing apparatus 1 at this time will be described with reference to the flowchart shown in FIG.
First, the initial optimization result (information on the initial arrangement state) of the plurality of arrangement elements 9 is input to the arrangement optimization problem processing apparatus 1 (step E1).
When the initial placement result of the placement element 9 is input, the placement optimization problem processing apparatus 1 makes a group of genetic algorithm (GAc) chromosomes by making a copy of the initial placement result in the first algorithm execution step. N are prepared (step E2).

  Next, in the first algorithm execution step, the N populations are divided into α populations and β populations (that is, α + β = N), and the chromosomes of the α populations are divided vertically, while β The first island 20 having α sets of chromosomes 21 divided vertically and the second island having β sets of chromosomes 23 divided horizontally are divided by horizontally dividing the chromosomes of 22 (step E3).

In the first algorithm execution step, the genetic algorithm (GAc) is executed independently for each of the groups 21 and 23 (step E4).
During execution of this genetic algorithm (GAc), every time a predetermined number of generations elapse, crossover is performed between populations having chromosomes divided in the same direction (step E5). That is, in the first island 20, crossover is performed between the chromosomes of a certain group 21 and the chromosomes of another group 21, while in the second island 22, the chromosomes of a certain group 23 and the other groups 23. Crossover is performed between the chromosomes.

Further, every time a predetermined number of generations elapses, crossover between groups having chromosomes divided in different directions is performed (step E6). That is, crossover is performed between the chromosomes of the population 21 belonging to the first island 20 and the chromosomes of the population 23 belonging to the second island 22. At this time, a local sparse / dense elimination method (LO) is also applied to each chromosome.
Then, it is determined whether the fitness value of the chromosome having the highest fitness value (optimal chromosome) is greater than or equal to a predetermined reference value, or whether the arrangement result has been eliminated (step E7).

  If it is determined that the optimal fitness value of the chromosome is not equal to or greater than a predetermined reference value or the density of the arrangement result is not eliminated, the processing after step E4 is repeated (NO route of step E7). ) If it is determined that the optimal fitness value of the chromosome is equal to or higher than a predetermined reference value or the density of the arrangement result has been eliminated, the optimal chromosome is output as a solution to the arrangement optimization problem. Then, the processing in the placement optimization problem processing apparatus 1 ends (YES route in step E7).

In this way, by adopting an island model that performs crossover between populations with chromosomes divided in different directions, the diversity of chromosomes that are candidate solutions in populations 21 and 23 can be maintained, which is optimal. The solution can be searched efficiently, and the density of the arrangement elements 9 can be eliminated more efficiently.
Further, in the first to fourth embodiments described above, when executing the local sparse / dense elimination method (LO) while executing the genetic algorithm (GAc, GAp), the second algorithm execution step is fixed. Although the case of using an algorithm (an algorithm to which an analogy of fluid mechanics is applied and an algorithm to which an analogy of morphing is applied) has been described, it is more preferable to change the algorithm used for each generation. In addition, you may apply the local sparse / dense elimination method (LO) which changes for every chromosome.

Further, in the second algorithm execution step, the local sparse / dense elimination method (LO) may be performed without dividing the arrangement region 10.
Further, in the first algorithm execution step, the mutation of the genetic algorithm (GAc, GAp) may be executed without dividing the chromosome (arrangement region 10).
A specific example of the layout optimization problem to which the present invention can be applied is shown below.

(1) Cell placement problem in LSI design Since cells have a size, there is generally a constraint that cells should not overlap.
Here, it is possible in principle to obtain an optimal cell arrangement by nonlinear programming (for example, hill-climbing method) in consideration of this constraint, but it handles a cell arrangement optimization problem on a practical scale. In general, it is difficult to obtain an optimal cell arrangement more efficiently.

For this reason, if the cell arrangement [see FIG. 28 (a)] is obtained by nonlinear programming without taking this constraint into consideration, and then the cell density is eliminated by the method described in the present invention [FIG. 28 (b). )], An optimal cell arrangement can be obtained more efficiently.
(2) Floor plan A floor plan is a kind of LSI placement problem, and refers to a problem in which the length of each side of the cell is variable, although the area of the cell to be placed is fixed.

  When solving this problem, it is possible to eliminate the density by using the method described in the present invention (see FIGS. 29A and 29B).

It is a block diagram which shows the structure of the arrangement | positioning optimization problem processing apparatus which performs the arrangement | positioning optimization problem processing method of this invention. It is a flowchart for demonstrating the arrangement | positioning optimization problem processing method of this invention. (A), (b) is a figure which shows a mode that a layout area is each divided | segmented and a partial area | region is formed. (A), (b) is a figure which shows an example of the arrangement | positioning element in an intermediate arrangement state, respectively. (A), (b) is a figure which shows the result of having eliminated the density of the arrangement element in an intermediate arrangement state, respectively. It is a figure which shows an example of crossover in the genetic algorithm (GAc) used with the arrangement | positioning optimization problem processing method concerning 1st Embodiment of this invention. It is a figure which shows an example of the mutation in the genetic algorithm (GAc) used with the arrangement | positioning optimization problem processing method concerning 1st Embodiment of this invention. It is a figure for demonstrating a general genetic algorithm. It is a figure for demonstrating a general genetic algorithm. It is a figure for demonstrating a general genetic algorithm. It is a figure for demonstrating a general genetic algorithm. (A)-(d) is a figure which shows the division method of the arrangement | positioning area | region at the time of performing the local sparse / dense elimination method (LO) used with the arrangement | positioning optimization problem processing method concerning 1st Embodiment of this invention, respectively. It is. (A)-(c) shows an example of the movement method of the arrangement | positioning element using the algorithm to which the analog of the fluid dynamics used in the arrangement | positioning optimization problem processing method concerning 1st Embodiment of this invention was applied, respectively. FIG. (A), (b) is another example of an arrangement element moving method using an algorithm to which an analogy of fluid dynamics used in the arrangement optimization problem processing method according to the first embodiment of the present invention is applied. FIG. (A), (b) is another example of an arrangement element moving method using an algorithm to which an analogy of fluid dynamics used in the arrangement optimization problem processing method according to the first embodiment of the present invention is applied. FIG. (A)-(e) is another example of the movement method of the arrangement | positioning element using the algorithm to which the analog of fluid dynamics used in the arrangement | positioning optimization problem processing method concerning 1st Embodiment of this invention was applied, respectively. FIG. It is a figure which shows the other example of the movement method of the arrangement | positioning element using the algorithm to which the analog of fluid dynamics used in the arrangement | positioning optimization problem processing method concerning 1st Embodiment of this invention was applied. It is a flowchart for demonstrating the other example of the arrangement | positioning optimization problem processing method concerning 1st Embodiment of this invention. (A), (b) is an example of an arrangement element moving method using an algorithm to which a morphing analogy used in the arrangement optimization problem processing method according to the modification of the first embodiment of the present invention is applied. FIG. It is a figure which shows an example of the chromosome in the genetic algorithm (GAp) used with the arrangement | positioning optimization problem processing method concerning 2nd Embodiment of this invention. It is a figure which shows an example of the crossing in the genetic algorithm (GAp) used with the arrangement | positioning optimization problem processing method concerning 2nd Embodiment of this invention. It is a figure which shows an example of the mutation in the genetic algorithm (GAp) used with the arrangement | positioning optimization problem processing method concerning 2nd Embodiment of this invention. It is a flowchart for demonstrating the other example of the arrangement | positioning optimization problem processing method concerning 2nd Embodiment of this invention. It is a flowchart for demonstrating the arrangement | positioning optimization problem processing method concerning 3rd Embodiment of this invention. It is a flowchart for demonstrating the arrangement | positioning optimization problem processing method concerning 4th Embodiment of this invention. It is a figure which shows an island model. It is a flowchart for demonstrating the arrangement | positioning optimization problem processing method using an island model. (A), (b) is a figure which shows the example which applied this invention to the cell arrangement | positioning problem, respectively. (A), (b) is a figure which shows the example which applied this invention to the floor plan, respectively.

Explanation of symbols

1 Placement optimization problem processor 4 CPU
DESCRIPTION OF SYMBOLS 5 Display control part 5A Display part 6 External file read / write part 6A External file 7B Input part 7D Input control part 8 Disk apparatus 9, 9a Arrangement element (element)
10 Placement area (space)
10a Partial area (partial space)
11-18, 18 'chromosome 20 first island 21,23 population 22 second island

Claims (15)

When arranging a plurality of elements having a defined connection relationship in a required space, a computer having a CPU is used to eliminate the density of the plurality of elements in the initial arrangement state while maintaining the connection relationship. A circuit layout optimization problem processing method,
An input step for inputting information on a plurality of elements in the initial arrangement state to the computer as an arrangement result;
For the arrangement result input in the input step, a partial space that is configured as a division of the space and each includes a plurality of elements is expressed as a gene, and the arrangement result includes the sequence of the gene. the chromosome corresponding to a plurality prepared with use of these chromosomes, performing a genetic algorithm using the fitness function chromosomes that can reduce the density of a plurality of elements takes a large fitness value by the CPU A first algorithm execution step for obtaining a chromosome having the highest fitness value as an optimal chromosome ,
For each of a plurality of chromosomes generated during the execution of the first algorithm execution step , for each subspace of each chromosome used in the genetic algorithm, among the plurality of elements included in the subspace and a second algorithm executing step you run in the CPU of the at least one local density eliminates algorithm element an element density moves from a high place to the element density is low location,
The genetic algorithm in the first algorithm execution step and the local sparse / dense elimination algorithm in the second algorithm execution step are repeatedly executed until the optimal chromosome fitness value becomes a reference value or more,
The first algorithm execution step outputs an optimal chromosome having a fitness value equal to or greater than the reference value as a solution in which the plurality of elements in the initial arrangement state are eliminated while maintaining the connection relationship. A circuit layout optimization problem processing method characterized by the above.   When the first algorithm executing step executes the genetic algorithm, at least one subspace selected from the plurality of subspaces in the chromosome is assigned to a portion corresponding to the subspace in another chromosome. 2. The circuit layout optimization problem processing method according to claim 1, wherein crossover as a genetic operation is executed by exchanging with a space.   When the first algorithm execution step executes the genetic algorithm, a specific subspace in the plurality of subspaces in the chromosome is more than a subspace corresponding to the subspace in another chromosome. If the sparseness is eliminated, crossover as a genetic operation is performed by pasting the subspace in the chromosome to a subspace corresponding to the subspace in the other chromosome. The circuit layout optimization problem processing method according to claim 1.   The first algorithm execution step moves at least one element of the plurality of elements in at least one subspace of the plurality of subspaces when executing the genetic algorithm, 2. The circuit layout optimization problem processing method according to claim 1, wherein mutation as a genetic operation is executed. Second algorithm executing step, as the topical manner compressional solve algorithm, capture the movement of the element that put the partial space as the motion of the fluid, so that the element density is uniform partial space, the fluid 2. The circuit layout optimization problem processing method according to claim 1, wherein an algorithm to which an analogy of fluid dynamics for moving an element in the subspace is applied in consideration of the viscosity of the circuit is used. Second algorithm executing step, while preserving the vicinity among multiple elements, characterized in that moving at least one element of the plurality of elements included in the partial space, claim circuit layout optimization problem processing method 5 described. Second algorithm executing step, while preserving the order among multiple elements, characterized in that moving at least one element of the plurality of elements included in the partial space, claim circuit layout optimization problem processing method 5 described. Second algorithm executing step, as the topical manner compressional solve algorithm, regarded as a modification operation in the morphing movement of elements that put the partial space, each partial space, Ru initial arrangement near the double A morphing analogy that determines a morphing center based on information on a number of elements and moves at least one element of the plurality of elements included in the subspace to a location separated from the morphing center. The circuit layout optimization problem processing method according to claim 1 , wherein the applied algorithm is executed. When the second algorithm execution step moves at least one element of the plurality of elements included in the subspace to a place separated from the morphing center, the element to be moved from the morphing center 9. The circuit layout optimization problem processing method according to claim 8 , wherein the distance to is linearly expanded. When the second algorithm execution step moves at least one element of the plurality of elements included in the subspace to a place separated from the morphing center, the element to be moved from the morphing center 9. The circuit layout optimization problem processing method according to claim 8 , wherein the distance to is increased nonlinearly. When arranging a plurality of elements having a defined connection relationship in a required space, a computer having a CPU is used to eliminate the density of the plurality of elements in the initial arrangement state while maintaining the connection relationship. A circuit layout optimization problem processing method,
An input step for inputting information on a plurality of elements in the initial arrangement state to the computer as an arrangement result;
With respect to the arrangement results input at said input step, the width of each of the plurality of subspaces to the space Ru are configured as obtained by dividing expressed as a first gene, said first gene a first chromosome consisting of SEQ Make several, first using a fitness function which Rutotomoni using these first chromosome, chromosome that can reduce the density of a plurality of elements takes a large fitness value a first step to run a genetic algorithm in the CPU,
Each of a plurality of spaces corresponding to a plurality of first chromosomes generated during the execution of the first step is configured by dividing this space by a partial space width corresponding to the first chromosome. the subspace containing a plurality of elements and each is expressed as a second gene, the second chromosome by preparing a plurality corresponding to Ri該placement result such a second gene sequences, these second Rutotomoni using chromosome of a second genetic algorithm using said fitness function, by executing a repeating said CPU to a predetermined excess of number of generations, the second chromosome with the highest fitness value A second step of acquiring a plurality of corresponding intermediate chromosomes corresponding to each of the plurality of first chromosomes,
For each of a plurality of second chromosomes generated during the execution of the second step, each subspace of each second chromosome used in the second genetic algorithm is included in the subspace. local density eliminates algorithm for moving to the at least one element element density is higher away from the element density is low location of the multiple elements includes a third step of executing by the CPU Re that,
The first step acquires the intermediate chromosome having the highest fitness value from the plurality of intermediate chromosomes as the optimal chromosome based on the fitness values of the plurality of intermediate chromosomes acquired in the second step. And
The first genetic algorithm in the first step, the second genetic algorithm in the second step, and the local sparse resolution algorithm in the third step are such that the optimal fitness value of the chromosome is not less than a reference value. It is executed repeatedly until
The first step outputs an optimal chromosome having a fitness value equal to or greater than the reference value as a solution in which the plurality of elements in the initial arrangement state are eliminated while maintaining the connection relation. A circuit layout optimization problem processing method. When arranging a plurality of elements having a defined connection relationship in a required space, a computer having a CPU is used to eliminate the density of the plurality of elements in the initial arrangement state while maintaining the connection relationship. A circuit layout optimization problem processing method,
An input step for inputting information on a plurality of elements in the initial arrangement state to the computer as an arrangement result;
With respect to the arrangement results input at said input step, the width of each of the plurality of subspaces to the space Ru are configured as obtained by dividing expressed as a first gene, said first gene a first chromosome consisting of SEQ Make several, first using a fitness function which Rutotomoni using these first chromosome, chromosome that can reduce the density of a plurality of elements takes a large fitness value a first step to run a genetic algorithm in the CPU,
For each of a plurality of space corresponding to the plurality of first chromosome that is generated during the execution of the first step, multiple subspaces of the space by the width of the subspaces corresponding to the chromosomes of the first after divided, for each subspace, the local density eliminates the element density of at least one element from the element density is higher location of the elements of several of the Ru contained in the subspace moves to a lower location by executing the algorithm by the CPU, the second step it calculates to obtain a plurality of intermediate placement results corresponding to the plurality of first chromosome, the respective fitness values of the plurality of intermediate placement results by the CPU When,
The space is configured by dividing the space by the width of the partial space corresponding to the first chromosome, and the partial space including a plurality of elements is expressed as a second gene, and is composed of the sequence of the second gene. By preparing a plurality of second chromosomes corresponding to the arrangement result, using these second chromosomes, and executing the second genetic algorithm using the fitness function on the CPU, the best adaptation is achieved. and a third step of obtaining the second chromosome having a degree value as an optimum chromosomes,
The first step acquires an intermediate arrangement result having the highest fitness value from the plurality of intermediate arrangement results as an optimum arrangement result based on the fitness value calculated in the second step,
The first genetic algorithm in the first step and the local sparse resolution algorithm in the second step are repeatedly executed until a predetermined number of generations are exceeded in the first genetic algorithm;
In the third step, the optimal arrangement result obtained by repeatedly executing the first genetic algorithm in the first step and the local sparse / dense cancellation algorithm in the second step The second genetic algorithm is repeatedly executed until the fitness value of the chromosome is equal to or higher than the reference value, and the optimal chromosome having the fitness value equal to or higher than the reference value is maintained in the initial arrangement state while maintaining the connection relationship. A circuit layout optimization problem processing method, characterized in that the solution is output as a solution in which the density of a plurality of elements is eliminated . When arranging a plurality of elements for which connection relations are defined in a required space, a circuit layout optimization problem for eliminating the density of the plurality of elements in the initial arrangement state while maintaining the connection relation is A computer-readable recording medium recording a circuit layout optimization problem processing program for processing by the computer,
The circuit layout optimization problem processing program is
When information regarding a plurality of elements in the initial arrangement state is input to the computer as an arrangement result, the input arrangement result is configured as a result of dividing the space, and a plurality of elements are respectively added to the computer. Representing a partial space as a gene, preparing multiple chromosomes that consist of the sequence of the gene and corresponding to the arrangement result, and using these chromosomes, chromosomes that can reduce the density of multiple elements are large fitness A first algorithm executing means for acquiring a chromosome having the highest fitness value as an optimal chromosome by executing a genetic algorithm using a fitness function that takes a value by the CPU ; and
For each of a plurality of chromosomes generated during execution of the first algorithm execution means , for each subspace of each chromosome used in the genetic algorithm, among the plurality of elements included in the subspace at least one local density eliminates algorithm for moving an element from an element density is higher location to the element low density locations with to function the computer as the second algorithm executing means you run in the CPU,
The genetic algorithm in the first algorithm execution means and the local sparse / dense elimination algorithm in the second algorithm execution means are repeatedly executed until the optimal chromosome fitness value becomes a reference value or more,
The first algorithm executing means outputs an optimal chromosome having a fitness value equal to or greater than the reference value as a solution in which the plurality of elements in the initial arrangement state are eliminated while maintaining the connection relationship. A computer-readable recording medium having a circuit arrangement optimization problem processing program recorded thereon, wherein the computer is caused to function. When arranging a plurality of elements for which connection relations are defined in a required space, a circuit layout optimization problem for eliminating the density of the plurality of elements in the initial arrangement state while maintaining the connection relation is A computer-readable recording medium recording a circuit layout optimization problem processing program for processing by the computer,
The circuit layout optimization problem processing program is
When information regarding a plurality of elements in the initial arrangement state is input to the computer as an arrangement result, each of a plurality of partial spaces configured as a result of dividing the space with respect to the input arrangement result The width of the first gene is expressed as a first gene, a plurality of first chromosomes comprising the sequence of the first gene are prepared, and the first chromosome is used, and the density of a plurality of elements can be reduced. First execution means for executing, on the CPU, a first genetic algorithm using a fitness function in which a chromosome has a large fitness value;
For each of the plurality of spaces corresponding to the plurality of first chromosomes generated during the execution of the first execution means, the space is divided by the width of the partial space corresponding to the first chromosome. A partial space that is configured and includes a plurality of elements each is expressed as a second gene, and a plurality of second chromosomes that are composed of the sequence of the second gene and that correspond to the placement result are prepared. And the second genetic algorithm using the fitness function is repeatedly executed by the CPU until the number of generations exceeds a predetermined number, whereby the second chromosome having the highest fitness value is obtained. A second execution means for obtaining a plurality of intermediate chromosomes corresponding to each of the plurality of first chromosomes; and
For each of a plurality of second chromosomes generated during the execution of the second execution means, for each of the subspaces of each second chromosome used in the second genetic algorithm, within the subspace Causing the computer to function as third execution means for executing, on the CPU, a local sparse / dense elimination algorithm for moving at least one element of a plurality of elements included from a place having a high element density to a place having a low element density ,
Based on the fitness values of the plurality of intermediate chromosomes acquired by the second execution means, the first execution means selects an intermediate chromosome having the highest fitness value from the plurality of intermediate chromosomes as an optimal chromosome. Get as
The first genetic algorithm in the first execution means, the second genetic algorithm in the second execution means, and the local sparse / dense elimination algorithm in the third execution means are based on the optimal chromosome fitness value. It is executed repeatedly until it exceeds the value,
The first execution means outputs an optimal chromosome having a fitness value equal to or higher than the reference value as a solution in which the density of the plurality of elements in the initial arrangement state is eliminated while maintaining the connection relationship. A computer-readable recording medium having a circuit arrangement optimization problem processing program recorded thereon, wherein the computer functions. When arranging a plurality of elements for which connection relations are defined in a required space, a circuit layout optimization problem for eliminating the density of the plurality of elements in the initial arrangement state while maintaining the connection relation is A computer-readable recording medium recording a circuit layout optimization problem processing program for processing by the computer,
The circuit layout optimization problem processing program is
When information regarding a plurality of elements in the initial arrangement state is input to the computer as an arrangement result, each of a plurality of partial spaces configured as a result of dividing the space with respect to the input arrangement result The width of the first gene is expressed as a first gene, a plurality of first chromosomes comprising the sequence of the first gene are prepared, and the first chromosome is used, and the density of a plurality of elements can be reduced. First execution means for executing, on the CPU, a first genetic algorithm using a fitness function in which a chromosome has a large fitness value;
For each of a plurality of spaces corresponding to a plurality of first chromosomes generated during execution of the first execution means, this space is divided into a plurality of partial spaces with a width of the partial space corresponding to the first chromosome. For each partial space, a local sparse / dense elimination algorithm for moving at least one element of a plurality of elements included in the partial space from a place where the element density is high to a place where the element density is low A second execution means for acquiring a plurality of intermediate placement results corresponding to the plurality of first chromosomes and calculating a fitness value of each of the plurality of intermediate placement results by the CPU; ,
The space is configured by dividing the space by the width of the partial space corresponding to the first chromosome, and the partial space including a plurality of elements is expressed as a second gene, and is composed of the sequence of the second gene. By preparing a plurality of second chromosomes corresponding to the arrangement result, using these second chromosomes, and executing the second genetic algorithm using the fitness function on the CPU, the best adaptation is achieved. Causing the computer to function as third execution means for acquiring the second chromosome having a degree value as an optimal chromosome,
The first execution means acquires an intermediate arrangement result having the highest fitness value from the plurality of intermediate arrangement results as an optimum arrangement result based on the fitness value calculated by the second execution means,
The first genetic algorithm in the first execution means and the local sparse / dense cancellation algorithm in the second execution means are repeatedly executed until the number of generations predetermined in the first genetic algorithm exceeds a predetermined number of generations;
With respect to the optimal arrangement result obtained by the third execution means repeatedly executing the first genetic algorithm in the first execution means and the local sparse / dense elimination algorithm in the second execution means, The second genetic algorithm is repeatedly executed until the fitness value of the optimal chromosome is equal to or higher than a reference value, and an optimal chromosome having a fitness value equal to or higher than the reference value is maintained while maintaining the connection relationship. A computer-readable recording medium storing a circuit arrangement optimization problem processing program, wherein the computer functions so as to output a solution in which the density of a plurality of elements in an initial arrangement state is eliminated.

Images