JPH11154171A - Component placement design support device and component placement method - Google Patents

Abstract

(57) [Summary] To provide a component placement design support device and a component placement method capable of determining a good component placement on a board in a short time. SOLUTION: A storage device 3 for storing component information arranged on a substrate, an initial group generating device 5 for generating a plurality of component arrangement candidates, and a plurality of component arrangement candidates of an initial group with reference to the component information. A plurality of corresponding next-generation component placement candidates are generated, a plurality of next-generation component placement candidates corresponding to the plurality of next-generation component placement candidates are generated, and this process is repeated to generate a plurality of nth-generation component placement candidates. And a component placement analysis unit 7 that determines a final component placement position selected from a plurality of nth generation component placement candidates.
Into the component placement data, which is displayed on the analysis value display 8
Display by

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

[0001] 1. Field of the Invention [0002] The present invention relates to a component placement design support apparatus and a component placement method suitable for determining the placement of components on a board.

[0002]

2. Description of the Related Art As a method for automatically locating components on a substrate such as a printed board, there are known methods such as a pair linking method, a cluster growth method, and a center of gravity method. These methods simply find an arrangement with the shortest wiring length as an optimal solution.

Heretofore, there have been proposed several methods which improve these methods. For example, Japanese Patent Publication No. 8-7759 discloses an automatic component placement processing method that can improve the wiring rate of automatic routing in component placement processing. However, in recent boards, easiness of wiring is not enough, and it is necessary to consider a plurality of conditions such as signal speed and heat generation of components.

[0004] As an optimization method for solving these problems, there is a method using a genetic algorithm (GA). For example, Japanese Patent No. 2526397 proposes a combination optimization device that executes combination optimization at high speed in the field of combination optimization. In the method using GA, the component arrangement state is represented by a gene, and the genetic operation of "selection selection", "crossover" and "mutation" is repeatedly performed on a group of individuals having the gene, thereby obtaining an optimal component. It is common to determine the placement.

[0005]

However, GA is a probabilistic search algorithm, and it takes a long time to process because it requires an iterative procedure. On the other hand, since the number of components on a printed board is huge, from several hundred to several thousand, in the conventional automatic placement system, optimization of component placement by processing considering the overall circuit configuration requires processing time. It is difficult to realize.
Therefore, conventionally, a method has been adopted in which a printed board is divided into small placement target portions, and placement processing is performed for each portion. How to divide the entire printed board into parts to be placed greatly affects the final result of component placement, but the method of dividing is not always established, and it depends on trial and error or empirical rules. ing.

[0006] Of the three types of genetic operations, a gene newly generated by "crossover" and "mutation" genetic operations may have a defect. Here, a defect means that a part is duplicated or missing due to, for example, a genetic operation. Several crossover or mutation schemes that do not create duplications or deletions are possible, but they inhibit gene diversity and adversely affect gene evolution. There is no example in which the component placement problem is regarded as a search problem for the optimal positional relationship between components on a plane, and there is no mention of a method for suppressing the occurrence of lethal genes without inhibiting diversity.

Further, during the repetitive processing of the above three kinds of genetic operations, there is a case where an initial convergence or a local optimal solution is caused due to a property inherent to GA. "Mutations" contribute to escape from this condition, but are naturally limited and require other approaches to suit the problem. However, there is no example mentioning a method for suppressing the occurrence of an initial convergence or a local optimum solution for a component placement problem.

Further, among the three types of genetic operations, “crossover” is an operation most characteristic of GA, but the “crossover” method itself has considerable flexibility and various variations. However, there is no example in which the component placement problem is regarded as a problem of searching for an optimal positional relationship between components on a plane, and a crossover method suitable for such a problem is not mentioned.

SUMMARY OF THE INVENTION Accordingly, an object of the present invention is to provide a component placement design support apparatus and a component placement method capable of determining a good component placement on a board in a short time.

[0010]

SUMMARY OF THE INVENTION The object of the present invention is to provide a storage device for storing component information to be placed on a board, a component placement candidate generating unit for generating a plurality of component placement candidates, and a plurality of component placement candidate generators based on the component information. A plurality of next-generation component placement candidates are generated from the component placement candidates, and a plurality of next-generation component placement candidates are generated from the plurality of next-generation component placement candidates. This is achieved by determining a final component arrangement position from a plurality of nth generation component arrangement candidates, including a component arrangement candidate generation unit that generates candidates.

Here, the component arrangement candidate generation unit generates an n-th generation component arrangement candidate by adding a part during the repetitive processing. It is preferable to add the components in the order of the components having the largest restrictions. The addition of the component is performed so that the component does not overlap and the component does not protrude from the substrate. As described above, initially, the number of components on the board is reduced to a small number, components are sequentially added as the number of generations is increased, and finally component arrangement candidates are generated with a specified number of components. This makes it possible to realize a high-speed processing while maintaining the overall processing of the substrate.

This type of device can be realized using, for example, a genetic algorithm (GA). In such a case, a device for storing component information to be placed on the substrate, an initial population generator for generating a plurality of genes representing component placement candidates, and a gene operation from a plurality of genes by gene manipulation with reference to the component information. And a gene generator for generating a plurality of genes of the next generation from a plurality of genes of the next generation by genetic manipulation, and repeating this to generate a plurality of genes of the nth generation. A component arrangement candidate related to a gene selected from a plurality of genes is configured as a final component arrangement position on the board.

Further, the component placement method according to the present invention includes a step of generating a plurality of next-generation component placement candidates from a plurality of component placement candidates prepared in advance by referring to component information placed on a board; A step of generating a plurality of next-generation component placement candidates from a next-generation component placement candidate, a step of generating a plurality of n-th generation component placement candidates by repeating this, and a step of generating a plurality of n-th generation component placement candidates. Determining the final component arrangement position from the above.

This type of method can also be realized using, for example, a genetic algorithm (GA). In that case, a step of generating a plurality of genes representing the component arrangement candidates,
A step of generating a plurality of next-generation genes from a plurality of genes by genetic manipulation with reference to component information arranged on a substrate, and a step of generating a plurality of next-generation genes from a plurality of next-generation genes by genetic manipulation. Repeating the above process to generate a plurality of nth generation genes, and a process of setting a component placement candidate relating to a gene selected from the nth generation genes to a final component placement position.

Here, the genetic manipulation is to perform at least one of selection, crossover and mutation.
The lethal gene generated by the genetic manipulation of this crossover or mutation is modified by partial movement of parts so as not to impede the diversity of the genetic manipulation. The gene pair to be subjected to crossover processing is determined based on the degree of difference in the content of the gene pair. Thereby, it is possible to suppress initial convergence and local optimal solution generation, and to promote favorable evolution of genes while maintaining the diversity of gene population.

In this type of genetic operation, the plane of the substrate is divided into two regions, and an operation for exchanging components in each region is performed. In this technique, a genetic operation is regarded as a problem of searching for an optimal positional relationship between components in a plane, and the genetic operation is performed using a crossover method suitable for such a problem.

According to such a component placement design support apparatus and component placement method, a good component placement on a board can be determined in a short time.

[0018]

Embodiments of the present invention will be described below. This embodiment relates to the arrangement of components on a printed board, and will be described in detail with reference to the drawings. The genetic algorithm (GA) used in the present embodiment is as follows.
The following document describes this in detail. Holland, John (1975). Adaptation in Natural.
and Artificial Systems, MIT press 1992 ", Gol
dberg, David (1987). Genetic Algorithm in Sear
ch, Optimization, and Machine Learning.Readi
ng, Mass .: Addison-Wesley, Davis, Lawrence (199
0). Handbook of Genetic Algorithms, Van Nost
rand (Japanese translation: Genetic Algorithm Handbook, Kazuzu et al. Morikita Publishing) Here, an outline of GA is described as a summary of the above literature. GA is an algorithm proposed by Holland et al. In the 1970s and inspired by the principles of biological evolution. This can be considered as a method of stochastic search, learning and optimization.

GA is basically a generation / evaluation type algorithm.
Perform three kinds of genetic operations of “crossover” and “mutation”.

Here, the "population" is composed of individuals who are candidates for the optimal solution and is initially generated at random. The characteristics of each individual are represented by genes, and the genes are mapped to the problem space according to rules specific to the problem. Genes usually consist of an information sequence.
Perform genetic manipulations of the species.

"Selection selection" means that each individual is evaluated for fitness in a problem space, and selective mating is performed according to the evaluation value. Basically, the mechanism is such that individuals with higher fitness leave more offspring.

"Crossover" refers to an operation of partially exchanging genes between two individuals. This operation characterizes GA best. For example, a gene represented by a bit string is cut at a randomly selected position and exchanged. For example,
When 11111 and 00000 are cut at the second position and exchanged, 11000 and 00111 are obtained. The purpose of crossover is to obtain a better solution by combining good partial solution and good partial solution.

"Mutation" refers to the generation of an information pattern to maintain the diversity of the population. As a method, two appropriate information pieces selected stochastically in the group are exchanged. By this operation, an information pattern that does not appear at the intersection can be generated.

GA is a mathematical model that simplifies the mechanism of natural selection and hereditary phenomena, and is based on the following rules so that a group of solution candidates for a target problem called an individual adapts to an external environment called an evaluation value. The configuration is generated for each generation. (Rule 1) The higher the fitness, the higher the survival probability. (Rule 2) Generate a new individual based on the old individual. If GA is used as one solution to the optimization problem, (Rule 1) can be regarded as a stochastic search method, and (Rule 2) can be regarded as an empirical search method, and GA has both aspects.

FIG. 1 is a block diagram showing an embodiment of a component placement design support apparatus according to the present invention. As shown in FIG. 1, the component placement design support device 1 has a storage device 3, a component placement analysis device 4, and an analysis value display 8. The storage device 3 obtains information such as wiring data and component data from the input device 2,
This is stored as a database. Input device 2 is a keyboard or other system. The component arrangement analysis device 4 analyzes the component arrangement based on the information from the storage device 3 and displays the result on the analysis value display 8.

The component arrangement analyzer 4 first generates a group of individuals using the initial group generator 5. This is a solution of a component arrangement candidate (part arrangement candidate) represented by a gene. This population of individuals is sent to population pool 6. The component arrangement candidate generation unit 9 performs the genetic operations of “selection selection”, “crossover”, and “mutation” for these groups over many generations while referring to the storage device 3, and Find individuals with the best genes. The component arrangement analysis unit 7 converts the solid into component arrangement data and various accompanying design data, and displays the result on the analysis value display 8.

The problem of the optimal component placement targeted by the present invention is as follows.
Basically, the obtained component arrangement is good in light of the following evaluation scale. (1) Wiring length Minimize the total wiring length between components based on the wiring table. (2) Distribution of components Parts are evenly arranged so as not to be partially crowded. (3) Functional block Parts are divided into functional blocks. There are also the following restrictions. (1) Overlap of parts The parts must not overlap each other. (2) Protruding parts The parts must not protrude from the printed board.

FIG. 2 shows a printed circuit board 10 having a width Nx and a height N.
This is displayed as y grids 11. In the example of FIG. 2, Nx = 8 and Ny = 7. 1 to Nx for each square 12
Numbers up to × Ny (= 56) are assigned. The parts 13 occupy the cells 12 by a necessary number according to their sizes. For example, parts with number 1 are square numbers 10, 11, 18
And 19, and the part number 3 also occupies 14 and 22.

In the example of FIG. 2, the total number of parts is nine. This state is represented by gene 14 shown in FIG. That is, the gene is a sequence having the length of the number of parts, and each numerical value indicates a cell number. For a part occupying a plurality of cells, the cell number corresponding to the upper left corner of the part is used as the cell number of the part. Thus, the printed board of FIG. 2 can be represented by the gene 14 of FIG. The mesh number M in the gene is arbitrary within the range of (1 ≦ M ≦ NxNy), but this causes the following problem. That is, the following genes are abnormal and are called lethal genes. (1) Overlap of parts If the same mesh number exists in one gene, those parts are overlapped. Even if they are not the same mesh number, for example, if the mesh number of the sixth component is 45, this is the same as the second component. (2) Protruding parts For example, if the grid number of the first part is 8 or 16,
The right half of this part protrudes from the printed board. If it is 49 to 56, the lower half protrudes.

The lethal gene does not represent a valid part arrangement and is ultimately not recognized. However, even a lethal gene can have good genetic properties and can be present in the middle of genetic manipulation. A collection of many genes is a group, and all the individual genes are solution candidates (part arrangement candidates).

For the above-described evaluation scale, an evaluation function is defined as follows. (1) Wiring length The components are wired based on the wiring table. The sum of each wiring is used as an evaluation value. Here, the wiring length H is an area distance and is defined as the following (Equation 1).

[0032]

(Equation 1) That is, as shown in FIG.
This is the product of the horizontal distance Hx between the reference positions 5 and 16 and the vertical distance Hy. The evaluation value of the wiring length Wq is defined as the following (Equation 2).

[0033]

(Equation 2) (2) Distribution of components The distribution is defined as follows in order to arrange components as evenly as possible. The ratio of the number of squares occupied by all the parts to the total number of squares of the printed board is defined as the part density k. In the example of FIG. 2, the total number of cells occupied by parts 1 to 9 is 18 (parts 1 to 2).
Is square 4, parts 4 to 5 occupy square 2, and parts 6 to 9 occupy square 1.) The total number of squares in the printed board is 56, so k = 1.
8/56 = 0.321. Next, all the component densities k _i within the unit area are calculated. The evaluation value Wd of the distribution is defined as the following (Equation 3).

[0034]

(Equation 3) If the unit area is 3 × 3 = 9 in the example of FIG.
A unit area composed of 2, 3, 9, 10, 11, 17, 18, and 19 corresponds to i = 1 and k ₁ = 4/9 = 0.44
4, cell number 2, 3, 4, 10, 11, 12, 18, 1
The unit area composed of 9, 20 corresponds to i = 2 and k ₂
= 4/9 = 0.444, square numbers 3, 4, 5, 11, 1
The unit area composed of 2, 13, 19, 20, and 21 corresponds to i = 3, and k ₃ = 2/9 = 0.222. Hereinafter, (Equation 3) is calculated for each unit area up to i = 30 by shifting each cell. (3) Group Degree The parts are divided into several groups, and the degree at which the parts of the same group are gathered at the same place is defined as the group degree Wg and defined as the following (Equation 4).

[0035]

(Equation 4) The meaning of g _i will be described with reference to the example of FIG. 2. Parts 1, 4 and 7 are group 1, parts 2, 5 and 8 are group 2
Then, the components 3, 6, and 9 are set to a group 3. Then, since there is no part of another group in the area occupied by group 1 (rectangular shape with cell numbers 10 and 43 diagonally), g ₁ = 0, and the area occupied by group 2 (cell numbers 28 and 47 Since there is a part 6 (mesh occupancy 1) of another group in the rectangle (diagonal rectangle), g ₂ = 1, and in the area occupied by group 3 (rectangle with diagonal squares 14 and 48) Parts 5 of other group (Mask occupation 2)
, G ₃ = 2. Therefore, in this case, Wg = 0 + 1 + 2 + 1 = 4. Here, the last 1 is for convenience to guarantee the existence of the reciprocal of Wg even when g _i is all 0.

The evaluation values Wq, Wd, and Wg defined as described above indicate that the smaller the value, the better the component arrangement. The fitness is determined from the three evaluation values, and the selection of genes is performed based on the fitness. The fitness is determined so as to decrease as the evaluation value increases.

In the first generation, the genes 14 as shown in FIG. 3 are generated at random by the number of groups (50 in this example) using random numbers. That is, the part number (FIGS. 2, 3)
In the example of (1) to (9), mesh numbers (1 to 56 in the examples of FIGS. 2 and 3) are randomly generated so that the mesh numbers do not overlap, and are generated as one gene. However, this causes the following problem. One of them is the protrusion of parts from the printed board. For example, if the mesh number of the first component is a multiple of 8 such as 8 or 16, the right half of this component will protrude from the printed board. If the cell numbers are 49 to 56, the lower half is protruding. Another problem is the overlap of parts. This situation can occur because some parts occupy more than one cell. For example, if the mesh number of the sixth component is 45, this means that the second component overlaps the second component. For example, the number 1 component has a size of 2 × 2, so if given the rightmost and lowermost cell numbers of the printed board, it alone becomes a contradictory gene, that is, a lethal gene. The cell numbers at the right end and the bottom row are 1 in total.
Since there are four, the probability that the first component does not protrude from the printed board is (56-14) / 56. Next, when considering the second component, the probability of not protruding from the printed board is also (55-14) / 55, but the possibility of overlapping with the first component is taken into consideration. Eight places near the first part correspond to this. (However, if the first part happens to be placed at the corner or edge of the printed board, the number of applicable parts will be less than eight places.) Eventually, if the first and second parts are arranged at random, the protrusion and overlap The probability of not occurring is as follows (Equation 5).

[0038]

(Equation 5) That is, a size 2 × 2 on a size 8 × 7 printed board
By arranging only two parts, about half become lethal genes. If the calculation is continued and all nine parts are arranged at random, the probability of obtaining a healthy gene as shown in FIG. 3 is about 5 × 10 ⁻⁴ . That is, stochastically, only one healthy gene can be obtained in 2000 trials. Moreover, in FIG. 2, the area occupied by the components is considerably smaller than the area of the printed board. In an actual printed circuit board, this area ratio is more than doubled, but the probability of obtaining a healthy gene is substantially equal to zero. Therefore, in order to avoid this inefficiency, a sequential addition method of parts is adopted. The sequential addition method is to reduce the number of parts to a very small number at first, and to make many genes sound even if parts are randomly arranged. Each time the processing of one generation is completed, the ratio of healthy genes in the population is checked.
Add. Parts should be placed where they do not protrude or overlap.

Then, the next generation is processed to evolve the population. If the ratio of healthy genes is less than the predetermined value, the process proceeds to the next generation without adding components. By doing so, the number of parts increases sequentially while maintaining the ratio of healthy genes at a certain value, and finally reaches the specified number of parts. According to this method, the evolution of the group and the increase of the parts are performed in parallel until the specified number of parts is reached, and after the specified number is reached, only the evolution of the group proceeds.

When parts are added, it is more efficient to add the parts according to the following criteria than to select the parts at random. In other words, parts having a large factor for generating a lethal gene are preferentially added. In the early stage, since there are many empty places on the printed board, the actual occurrence rate of the lethal gene is low even if components having a large factor for generating the lethal gene are arranged. The population evolves in this state, increasing the additional tolerance, ie the proportion of healthy genes in the population. In this way, as the generation progresses and the number of empty places on the printed board decreases, the tolerance for addition decreases, but later, parts with a small cause of lethal gene occurrence will remain, realizing highly efficient processing as a whole it can. A part having a large cause of lethal gene generation is generally a part having a large size. However, in an actual printed board, a part having a restriction condition such as a wiring length is also a target.

By crossover or mutation, a large number of genes having at least one of overlapping and protruding parts are generated. Unless special measures are taken, such genes have a low fitness and will be quickly eliminated. However, such a gene cannot be said to be essentially inferior. If only the overlapping and protruding parts of the parts are corrected, the gene is considered to be an excellent gene in many cases. Therefore, only the defective portion is corrected so that even such a gene can be prevented from being selected. When placing a part on a board based on genetic information, if the part already exists at that position, or if it is placed at that position and protrudes from the board, the part position is moved in four directions (up, down, left, right). Move in 8 directions by adding 4 angular directions). As a result, if there is no problem in a certain position, the part is placed in that position, and the gene is rewritten to correspond to it. A specific method of the correction will be described below.

In FIG. 5, when an attempt is made to place the fourth part at the position of the grid number 35, the right half is already placed.
It will overlap with the number part. Therefore, when the position is moved up, down, left, and right, it can be understood that if the position is moved up or left by one grid, it can be placed without any problem. Therefore, the part position is moved up or left, and the gene is rewritten as such. Such an operation is performed for all parts.

In this case, the order in which the parts are placed is a problem.
Parts that have a large influence on the inconvenience of the arrangement such as overlapping of parts and protrusion from the printed board, that is, parts having large dimensions are arranged first. However, such correction processing is of course not perfect, and not all lethal genes can be converted into healthy genes. However, if the correction processing is performed as much as possible, there is a remarkable effect as a whole group.

When the component cannot be arranged based on the genetic information, the position of the component is moved in four directions (up, down, left and right, or four directions in the diagonal direction to eight directions) to determine whether the part can be arranged. Investigate, and adopt the movement direction that can be arranged first. At this time, the order in which the four directions (or eight directions) are checked is not fixed but is determined stochastically by random numbers. As a result, the moving direction is not biased in a certain direction, and as a result, the diversity of gene manipulation increases, and thus the gene population is efficiently evolved.

FIG. 6 shows the gene population at an early stage. This figure shows the first 10 genes in the population. In this example, since the number of parts is 24, the length of the gene is 24. In the case of the first gene, the first part is arranged in the mesh number 30 and the second part is arranged in the mesh number 33.
As for the second gene, the first part is arranged in mesh number 13, the second part is arranged in mesh number 39, and so on. As you can see from the whole gene population, the content of the gene is not entirely or partly similar. This is because a gene is randomly generated initially using random numbers. Genes are evolved by repeatedly performing genetic operations such as “selection selection”, “crossover” and “mutation” on a population consisting of these genes. As a result, similar genes increase.

FIG. 7 shows the 25th generation gene population.
The first 10 genes are shown. As can be seen from the figure, the contents of each gene are very similar, and the contents of the first gene and the fifth gene are exactly the same. Genes having the same or almost the same content are referred to as closely related genes.

FIG. 8 is a plot of the number of generations on the horizontal axis and the number of closely related genes on the vertical axis. The solid line indicates the number of genes having the same content, the dotted line indicates the number of genes having different contents only in one place, and the chain line indicates the number of genes having different contents only in two places. As can be seen from FIG. 8, the generation of the closely related gene was already observed before the 10th generation, and once decreased after the 10th generation, it rapidly increased again from the 20th generation and decreased again around the 30th generation. However, it has been increasing since then. Even if crossover is performed between genes having the same content, the generated gene is the same as the parent. Even if they do not have the same contents, the genes generated when crossing between similar genes are very similar to the parent. There is no problem if such a phenomenon occurs as a result of sufficient evolution of the gene population, but otherwise, this phenomenon is detrimental to the evolution of the gene population.

In order to suppress this phenomenon, the contents of both genes are examined for the pair of genes to be crossed over, and if the contents are the same, one gene is exchanged for another gene having a different content to perform crossover. Is carried out. Alternatively, if the difference between the contents is less than a predetermined number, one gene is replaced with another gene whose number of the difference is larger than the predetermined number, and the crossover is performed. This treatment efficiently evolves the gene population.

FIG. 9 shows the change in the number of closely related genes when this treatment was performed. As can be seen from FIG. 9, signs of the occurrence of a closely related gene are seen before the tenth generation, but the increase is suppressed. From around the 20th generation, the number of closely related genes increases, but the number is considerably smaller than when no suppression treatment was performed.

FIGS. 10A and 10B show a very small printed board for explaining the crossover method in the present invention. FIGS. 10A and 10B are arbitrarily selected from the gene population for the crossover process. 1 shows a pair of individuals of a father and mother, respectively. The crossover method used in the present invention uses the relative positional relationship of parts on a printed board represented by a gene as a genetic element.

FIG. 11 shows the gene expression of these individuals. That is, the gene is composed of an information sequence composed of mesh numbers. As shown in FIG. 10, first, the individual father and mother that are the targets of crossover are divided into four parts by two vertical and horizontal straight lines whose positions are determined by random numbers. Then, two areas are defined by setting the diagonal portions to be the same area. That is, of the four parts, an area composed of the upper left part and the lower right part is the first area, and the remaining part, that is, the area composed of the upper right part and the lower left part, is the second area. Although the number of regions is set to two here, the number of regions can be set to three or more by setting a plurality of vertical and horizontal dividing lines.

The descendants 1 and 2 shown in FIGS. 12A and 12B are generated as follows. In the child 1, the first area is the same as the father's first area, and the second area is the same as the mother's second area. On the other hand, in the child 2, the first area is the same as the mother's first area, and the second area is the same as the father's second area. Through this processing, the child 1 and the child 2 shown in FIGS. 12A and 12B are generated. FIG. 13 shows the genes of child 1 and child 2 corresponding to this.

When the above-described crossover method is performed for all gene pairs, the following problem occurs. As can be seen from the description in the preceding paragraph, the first area portion is completely copied from father to child 1 or from mother to child 2. While the second
The contents of the area portion are changed as described later.
The fact that the copy portion is fixed for all gene pairs is a factor inhibiting the diversity of gene evolution due to crossover.
Therefore, the relationship between the first region and the second region is reversed for each gene pair, whereby the "crossover" processing is equalized on the printed board, and the gene population is efficiently evolved.

Looking closely at the genes thus produced, the genes are abnormal and these are lethal genes. That is, in the child 1, there are two No. 4 and No. 5 parts, and No. 2 and No. 8 parts have disappeared. In the child 2, there are two No. 2 and No. 8 parts, and
The parts No. 5 and No. 5 have disappeared. Such a defect is corrected as follows. First, in the child 1, the first area inherited from the father is left as it is, and the second area inherited from the mother is
Make corrections to the area. There is no problem with the third part in that part, so it is left as it is. The next part No. 5 already needs to be corrected because it already exists in the first area. The same can be said for the fourth component in the second area. Replace these part numbers with non-existent part numbers. That is, the fifth is changed to the second and the fourth is changed to the eighth. For the child 2, the first area inherited from the mother is left as it is, and the same processing is performed thereafter. FIG. 14A shows the result of the correction in this manner.
(B) shows each. FIG. 15 shows the genes resulting from the correction, and these genes are all healthy genes.

Although crossover processing without lethal gene generation is possible by the above method, a drawback of this method is that a correction process deviating from the principle of crossover is required in the process. This inconvenience can be avoided by changing the cell numbers as shown in FIGS. 16 (a) and 16 (b). That is, the mesh numbers are consecutive within the same area. By renumbering, the genes of the father and mother are as shown in FIG. It should be noted that the definition of this gene is different from that described above, and is composed of an information sequence in which part numbers or blanks are arranged in the order of cell numbers. According to this gene, cell numbers 1 to 6 are the first area and cell numbers 7 to 12 are the second area. That is, since the gene for the crossover is cut at the boundary of the region, the gene itself is not cut.

Since the gene shown in FIG. 17 uses a part number as gene information, it is necessary to convert this into order information. In order to convert to an ordinal expression, a part number list arranged in numerical order is defined, and this number is used as a gene according to the order of each part number in the remaining list. In this example, since the number of parts is 8 and the number of blanks is 4, the first list is as follows. -------------------------------------------------------------------------- No. 1 2 3 4 5 6 7 8 9 10 11 12 ---------------------- −−−−−−−−−−−−−−−−−−−−−−−− Part No. 1 2 3 4 5 6 7 8 * * * * * −−−−−−−−−−−−−−−−−− −−−−−−−−−−−−−−− When taking the father's gene in FIG. 17 as an example, the first is a blank, so number 9 is given as the first blank, and at the same time, it is deleted from the list and the number becomes To be presumed. So the new list looks like this: −−−−−−−−−−−−−−−−−−−−−−−−−−− No.1 2 3 4 5 6 7 8 9 9 10 11 −−−−−−−−−−−−− −−−−−−−−−−−−−−−−− Part number 1 2 3 4 5 6 7 8 * * * −−−−−−−−−−−−−−−−−−−−−−−− Next, since the 6th part is in the sixth position in the list, the number 6 is given, and at the same time, the part is deleted from the list and the number is set in advance. So the new list looks like this: -------------------------------------------------------------------------- Number 1 2 3 4 5 6 7 8 9 9 10---------------------------------------------------------------------- −−−−−−−−−−−− Part number 1 2 3 4 5 7 8 * * * * −−−−−−−−−−−−−−−−−−−−−−−−−−− The fourth part is assigned the number 4 since it is the fourth part in the list, and is deleted from the list at the same time, and the number is set in advance. So the new list looks like this: --------------------------------------------------------------------------- Number 1 2 3 4 5 6 7 8 9 ------------------------ −−−−−− part number 1 2 3 5 7 8 * * * −−−−−−−−−−−−−−−−−−−−−−−−−− Next, the 5th part is the fourth in the list. , The number 4 is given, and at the same time it is removed from the list and the number is brought forward. So the new list looks like this: −−−−−−−−−−−−−−−−−−−−−− No.1 2 3 4 5 6 7 8 −−−−−−−−−−−−−−−−−−−−−−− -Part number 1 2 3 7 8 * * * --------------------------- At the same time, they are removed from the list and the numbers are made up front.
In the same manner, the following sequence is obtained. Father 9, 6, 4, 4, 1, 5, 4, 4, 4, 2, 1, 1 Mother 8, 8, 8, 1, 1, 4, 5, 1, 4, 2, 2, 1 18 are genes expressed in order. Applying the principle of crossover processing to this gene, the child 1 is obtained by combining the first region of the father and the second region of the mother, and the child 2 is obtained by combining the first region of the mother and the second region of the father. Generate. The gene thus generated is shown in FIG. Since the genes in FIG. 19 are naturally expressed in order, they are inversely converted to the part number genes by the reverse procedure of the conversion. FIG. 20 shows genes whose information is the inversely converted part numbers. FIGS. 21A and 21B show the child 1 and the child 2 as printed boards based on this gene. This is a sound printed board with no missing parts and no duplication as seen in FIG. It also shows that some of the genes have been inherited from their parents.

When the above-described crossover method is performed for all gene pairs, the following problem occurs. As can be seen from the description in the preceding paragraph, the first area portion is completely copied from father to child 1 or from mother to child 2. While the second
The contents of the area portion are changed as described later.
The fact that the copy portion is fixed for all gene pairs is a factor inhibiting the diversity of gene evolution due to crossover.
Therefore, the relationship between the first region and the second region is reversed for each gene pair, whereby the "crossover" processing is equalized on the printed board, and the gene population is efficiently evolved.

As described above, according to the component placement apparatus using the genetic algorithm of the present invention, no matter how complicated the model is constructed, if the method of calculating the fitness is clear, the solution candidate represented by the gene is expressed. An optimal solution or a sub-optimal solution can be obtained only by performing a predetermined genetic operation on the group of.

Further, according to the component placement design support apparatus based on the genetic algorithm using the partial modification method of the present invention, even if the gene is a lethal gene caused by crossover or mutation, the gene is a potentially superior gene. If it is,
By applying a partial correction to this, it is possible to pass on its excellent genetic properties to the next generation with a high probability, and it is possible to obtain an optimal solution or a sub-optimal solution at a high speed.

Furthermore, according to the component placement design support apparatus of the present invention based on a genetic algorithm using the kinship crossing restriction method, even if a kin gene occurs during the evolution of the gene population, the crossover between the kin genes is restricted. Therefore, a good evolutionary state can be maintained without increasing the number of closely related genes, and an optimal solution or a suboptimal solution can be obtained at high speed.

Furthermore, according to the component placement design support apparatus of the present invention based on a genetic algorithm using the crossover method, even if any design condition is set for the relative positional relationship between components, the adaptability can be improved. As long as the calculation method is clear, an optimal solution or a sub-optimal solution can be obtained at a high speed only by performing a predetermined genetic operation on a group of solution candidates represented by a gene.

[0062]

According to the present invention, it is possible to obtain a component placement design support apparatus and a component placement method capable of determining a good component placement on a board in a short time.

[Brief description of the drawings]

FIG. 1 is a configuration diagram showing one embodiment of a component placement design support apparatus according to the present invention.

FIG. 2 is a diagram showing a printed board showing an application example of the present invention.

FIG. 3 is a diagram showing a gene expression showing an application example of the present invention.

FIG. 4 is a diagram showing a definition of an area distance used in the present invention.

FIG. 5 is a diagram showing a description of a partial correction method used in the present invention.

FIG. 6 is a diagram showing an example of an initial gene population.

FIG. 7 is a diagram showing an example of a 25th generation gene population.

FIG. 8 is a diagram showing the relationship between the number of generations and the number of closely related genes.

FIG. 9 shows the relationship between the number of generations after treatment and the number of closely related genes.

FIGS. 10A and 10B are examples of board models each showing a parent and a mother;

FIG. 11 is a diagram showing a gene expression of a parent individual.

FIGS. 12A and 12B are examples of board models each showing a child;

FIG. 13 is a diagram showing gene expression of a child individual.

FIGS. 14A and 14B are examples of board models each showing a child;

FIG. 15 is a diagram showing a gene expression of a child individual.

FIGS. 16A and 16B are examples of board models each showing a parent and a mother;

FIG. 17 is a diagram showing a gene expression of a parent individual.

FIG. 18 is a diagram showing a gene expression of a parent individual.

FIG. 19 is a diagram showing gene expression of a child individual.

FIG. 20 is a diagram showing gene expression of a child individual.

FIGS. 21A and 21B are examples of board models each showing an individual child;

[Explanation of symbols]

 REFERENCE SIGNS LIST 1 component placement design support device 2 input device 3 storage device 4 component placement analysis device 5 initial group generator 6 group pool 7 component placement analyzer 8 analysis value display 9 component placement candidate generator

 ──────────────────────────────────────────────────続 き Continued on the front page (72) Inventor Kazuo Sato 216 Totsuka-cho, Totsuka-ku, Yokohama-shi, Kanagawa Prefecture Inside Hitachi Advanced Systems Co., Ltd. (72) Inventor Hideyuki Doi 216 Totsuka-cho, Totsuka-ku, Yokohama-shi, Kanagawa Stock Hitachi Advanced Systems, Inc.

Claims (20)

[Claims] 1. A storage device for storing component information to be placed on a board, a component placement candidate generating unit that generates a plurality of component placement candidates, and a next generation device from the plurality of component placement candidates based on the component information. A plurality of component placement candidates of the next generation are generated from the plurality of next-generation component placement candidates, and a plurality of component placement candidates of the n-th generation are generated by repeating this. A component placement design support device, comprising: a placement candidate generation unit, configured to determine a final component placement position from the plurality of nth generation component placement candidates. 2. The component placement design support apparatus according to claim 1, wherein the component placement candidate generating unit generates the nth generation component placement candidate by adding a component during the repetitive processing. 3. The component placement design support apparatus according to claim 2, wherein the component addition is performed in the order of the component having the largest restriction. 4. The component placement design support apparatus according to claim 2, wherein the addition of the component is performed so that the component does not overlap and the component does not protrude from the substrate. 5. A plurality of next-generation component placement candidates corresponding to a plurality of previously prepared component placement candidates are generated by referring to component information to be placed on a board, and the plurality of next-generation component placement candidates are generated. A plurality of corresponding next-generation component placement candidates are generated, and by repeating this, a plurality of n-th generation component placement candidates are generated, and a component placement position is selected from the plurality of n-th generation component placement candidates. A component placement design support device characterized by being constituted. 6. The component placement design support apparatus according to claim 5, wherein said board is a printed board. 7. The component placement design support apparatus according to claim 5, wherein the component information includes data of a size and a shape of the component. 8. A device for storing component information to be placed on a substrate, an initial population generating device for generating a plurality of genes representing component placement candidates, and a gene manipulation by referring to the component information to generate a next gene from the plurality of genes. A plurality of genes of the next generation, further comprising a plurality of genes of the next generation from the plurality of next-generation genes by genetic manipulation, and a gene generator for generating a plurality of n-th gene by repeating this, A component placement design support device, wherein a component placement candidate related to a gene selected from the plurality of nth generation genes is set as a final component placement position on a substrate. 9. A storage device for storing component information to be placed on a substrate, and a plurality of next-generation component placement candidates corresponding to a plurality of component placement candidates prepared in advance by referring to the component information, A plurality of next-generation component placement candidates corresponding to the plurality of next-generation component placement candidates are generated, and by repeating this, a plurality of n-th generation component placement candidates are generated, and the plurality of n-th generation component placement candidates are generated. A component arrangement analysis device for outputting the final component arrangement position selected from the above as component arrangement data, and a display for displaying the component arrangement data. 10. The component placement analysis device according to claim 1, wherein the component placement candidate is represented by a gene, and the gene is evolved by a genetic operation to generate a plurality of nth generation component placement candidates. 9. The component arrangement design support device according to item 9. 11. A step of generating a plurality of next-generation component arrangement candidates from a plurality of component arrangement candidates prepared in advance by referring to component information arranged on a substrate; A step of generating a plurality of component placement candidates of the next-next generation, a step of generating a plurality of component placement candidates of the n-th generation by repeating this, and a final component placement from the plurality of component placement candidates of the n-th generation Determining a position. 12. The component placement method according to claim 11, wherein at least one of the steps of generating the component placement candidate includes a step of adding a component. 13. The component placement method according to claim 12, wherein the component addition is performed in the order of the component having the largest restriction. 14. The component placement method according to claim 12, wherein the addition of the component is performed so that the component does not overlap and the component does not protrude from the substrate. 15. The step of generating the component placement candidate comprises:
12. The component arranging method according to claim 11, further comprising a step of partially correcting an unavoidable violation of the arrangement state. 16. A step of generating a plurality of genes representing candidate component arrangements; a step of generating a plurality of next-generation genes from the plurality of genes by genetic manipulation with reference to component information arranged on a substrate; A step of generating a plurality of next-generation genes from the plurality of next-generation genes by an operation, a step of generating a plurality of n-th generation genes by repeating this, and selecting from the plurality of n-th generation genes As a final component placement position for the component placement candidate relating to the selected gene. 17. The component placement method according to claim 16, wherein the genetic operation performs at least one of selection, crossover, and mutation. 18. The method according to claim 17, wherein the lethal gene generated by the genetic manipulation of the crossover or mutation is corrected by a partial movement of the part. 19. The component placement method according to claim 17, wherein the gene pair to be subjected to the crossover processing is determined based on the difference between the contents of the gene pair. 20. The method according to claim 16, further comprising the step of dividing the plane of the substrate into two regions and exchanging components in each region.