JPH0812676B2 - Combination optimization device - Google Patents

Description

Detailed Description of the Invention

[0001]

The present invention relates to various design issues, in order to particularly solving important combinatorial optimization problem in the design and layout design of logical circuits, most co from a plurality of arrangement data conversion rules including heuristic algorithm
Placement data considered to be effective for lowering the strike
By probabilistically prioritizing the selection of conversion rules during search, it is possible to obtain a solution at high speed and to obtain an optimal solution.
Or, the present invention relates to a combinatorial optimizer capable of obtaining a suboptimal solution .

[0002]

2. Description of the Related Art In recent years, combinatorial optimizing devices have been actively used in fields such as logic circuit design. A design problem can be generally solved as a combinatorial optimization problem, but there is a problem that an enormous amount of calculation time is required as the number of combinations increases, so that an excellent combinatorial optimization device is needed.

As a combination optimization device, science (S. Kirkpatrick, CDGelatt, MPVecchi, "Optimiza
tion by Simulated Annealing ", Vol.220, No.4598, p
p.671-680, 1983) A method called simulated annealing found in other literature is known. Hereinafter, a conventional combination optimization device will be described with reference to FIG.

FIG. 6 shows the configuration of a conventional arrangement data optimizing means. The placement data optimizing means optimizes the initial placement data when given. In FIG. 6, 61 is new placement data generation means for converting the original placement data to create new placement data, 62 is cost calculation means for calculating the cost of the new placement data, and 63 is the cost of the new placement data. Arrangement data selecting means for comparing the cost of the arrangement data and selecting the next arrangement data, 64 is a temperature loop end detecting means for ending the search process at each temperature under a certain condition, and 65 is a temperature updating means for decreasing the temperature. , 66 are search end detecting means for ending the search process when the cost of the arrangement data does not change.

First, it is assumed that appropriate initial placement data is given. The new arrangement data generation means 61 generates new arrangement data by randomly deforming the original arrangement data. The cost calculation means 62 calculates the cost of the new placement data. The placement data selecting means 63 calculates the cost of the new placement data and compares it with the cost of the original placement data. The means selects the placement data of the next step based on the cost difference Δc (cost of new placement data-cost of original placement data). When △ c <0, the new placement data is adopted, and when △ c> 0, exp (-△ c / T)
With the probability of, the new placement data is adopted as the placement data for the next step. At other times, the arrangement data does not change.
Here, T is a parameter called temperature. Even if the cost increases, it is possible to reach the placement data having the global minimum cost value by stochastically adopting the new placement data. Temperature loop end detection means 64
Determines whether to lower the temperature based on a certain condition. For example, after converting 100 times at the same temperature, the temperature is lowered. The temperature updating means 65 reduces the temperature. The search end detecting means 66 ends the search process when the cost cannot be reduced any more.

[0006]

However, in the above-mentioned conventional configuration, since the conversion of the arrangement data is limited to the random micro-deformation, the convergence to the optimum arrangement data is slow and a huge calculation time is required. There were challenges. In addition,
Search using conversion of placement data only in the direction in which the
Is only the local optimal solution near the initial configuration data
However, there is a problem in the accuracy of the solution.

The present invention solves the above-mentioned problems of the prior art, and includes a placement data conversion means and a heat conversion means by random microdeformation.
No arrangement data conversion means based on uristic knowledge
The purpose is to prepare a plurality of placement data conversion rules of various methods, to make it easy to select placement data conversion rules that effectively reduce costs as a result, and to find the optimal or suboptimal placement data at high speed. To do.

[0008]

Means for Solving the Problems] To achieve this object, the combination optimizing apparatus in the present invention, the initial arrangement data generating means for generating an appropriate initial placement data, the first
Initial placement data generated by the temporary placement data generation means
Starting from, the search is repeated until the placement data is maximized.
Optimizing placement data optimization means and the placement data optimization
The conversion means converts the placement data during the search.
Random placement data conversion rules and heuristics for
Placement data that stores multiple unique placement data conversion rules
By the conversion rule storage means and the arrangement data optimization means
Optimal placement data storage for storing optimized placement data
It is composed of means .

Further, the arrangement data optimizing means is characterized by the arrangement
A plurality of layout data stored in the data conversion rule storage means
Data conversion rules, each of which is proportional to the numerical value of its strength.
Placement data that selects one placement data conversion rule depending on the rate
Data conversion rule selecting means and selected layout data conversion rule
New by converting the current placement data using
New layout data generation means for generating layout data;
The new layout data generated by the layout data generation means
Cost of calculating the difference between the cost of the strike and the original placement data
The calculation means and the cost calculated by the cost calculation means
Adopt new placement data from the difference of temperature and the value of temperature parameter
Placement data selection means for determining whether or not the placement data
Each allocation is based on the value of the cost difference when selected by the selection means.
Arrangement data conversion rule for adjusting strength of arrangement data conversion rule
The adjustment process and the search process for each temperature parameter are terminated.
Temperature loop end detection means for determining whether or not to end
And a temperature updating means for reducing the temperature parameter, and the arrangement
When the cost of data is stable
It is composed of search end detection means for ending the search .

The above-mentioned object is achieved by the apparatus having the above-mentioned configuration.

[0011]

With this configuration, the search can be started from the initial arrangement data generated by the initial arrangement data generating means, and the optimum or sub-optimal arrangement data can be obtained while converting the arrangement data using various arrangement data conversion rules. it can. The operation will be described below.

The initial arrangement data generating means generates an initial value of appropriate arrangement data. It may be randomly generated using random numbers, or an approximate solution may be generated by some heuristic method.

The layout data optimizing device optimizes the layout data by repeating the conversion based on the initial value of the layout data. First, an initial temperature parameter is set as an initial setting, and an initial value of a number called the strength held by each of the plurality of arrangement data conversion rules stored in the arrangement data conversion rule storage means is set. Next, only one is stochastically selected based on the strength of each arrangement data conversion rule, and the selected conversion rule is applied to generate new arrangement data. Then, the cost of the new placement data is calculated and compared with the cost of the original placement data, and the cost difference Δ
Based on c (cost of new placement data-cost of original placement data), decide whether or not to adopt new placement data. When Δc <0, the new placement data is adopted, and even when Δc> 0, the new placement data is adopted with a probability of exp (-Δc / T).
Use the placement data for the next step. At other times, the arrangement data does not change. Here, T is a temperature parameter. If adopted, the arrangement data conversion rule is adjusted. If the cost decreases, based on the decrease,
Increase the strength of the transformation rules applied. For example, | △ c |
Increase by a constant multiple of. When the cost increases, the strength of the applied conversion rule is decreased based on the increase. For example, it is decreased by a constant multiple of | Δc |.

After that, it is determined whether the temperature can be lowered. One example of the determination method is that the temperature may be lowered after the conversion is performed a certain number of times. The temperature is lowered by decreasing the temperature parameter T, and the search is continued. However, the search process ends when the cost of the placement data no longer decreases compared to the previous one.

The layout data and the cost thereof at the time when the search is completed are stored in the optimum layout data storage means, and this is the solution to be obtained.

A point effective in the above operation is that a conversion rule to be actually applied is stochastically selected from a plurality of arrangement data conversion rules based on its strength, and the strength is dynamically adjusted. Therefore, it is easy to select a conversion rule that effectively reduces the cost. Therefore, the calculation time for obtaining the optimum or sub-optimal arrangement data can be shortened. Also, since the conversion rule is applied stochastically, there is a high possibility that a global optimum value will be obtained.

[0017]

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 is an overall configuration diagram of an embodiment of the present invention. In FIG. 1, 11 is initial placement data generating means, 12 is placement data optimizing means, 13 is optimal placement data storage means, and 14 is placement data conversion rule storage means.

FIG. 2 is a block diagram of the arrangement data optimizing means in the embodiment of the present invention. 21 is arrangement data conversion rule selection means, 22 is new arrangement data generation means, 23 is cost calculation means, 24 is arrangement data selection means, 25 is arrangement data conversion rule adjusting means, 26 is temperature loop end detection means, and 27 is temperature. The updating means 28 is a search end detecting means.

FIG. 3 is an algorithm of the arrangement data optimizing means in the embodiment of the present invention, FIG. 4 is an arrangement data conversion rule adjusting algorithm in the embodiment of the present invention, and FIG. 5 is an explanatory diagram in the embodiment of the present invention.

The operation of the above arrangement will be described below. Consider the traveling salesman problem as an example of a combinatorial optimization problem. The traveling salesman problem is a problem of finding a route with the smallest total distance among routes that visit each of the N cities only once when the positions of the N cities are given. The total distance is used as the cost, and the placement data is a permutation in which the cities that are visited are arranged in order. For example, in the case of 5 cities, one arrangement data is (5, 3, 2, 4,
In 1), the cost is the sum of d53, d32, d24, d41 and d15. However, dij is the distance between city i and city j.

Now, the arrangement data conversion rules stored by the arrangement data conversion rule storage means 14 are two, that is, rule 1 and rule 2. The rule 1 is a part of the route at random.
Arrangement data conversion rule that replaces
A heuristic placement day that switches roads in ascending order
Data conversion rule . The initial arrangement data generation means 11 uses the random numbers to generate the initial arrangement data (5, 2, 3, 4,
1) is generated.

The layout data optimizing means 12 optimizes the layout data by repeating the conversion based on the initial layout data. This will be described with reference to FIGS. First, an initial temperature parameter is appropriately set as an initial setting, and an initial value of strength held by the two arrangement data conversion rules is set (301). It is assumed that the initial value of each strength is set to the same value. Next, only one is stochastically selected based on the strength of the arrangement data conversion rule (302).

Since the strengths are the same now, it is assumed that rule 1 is selected according to the probability. The selected conversion rule rule 1 is applied to generate new layout data (303). It is assumed that the new placement data generated is (5, 3, 2, 4, 1). The cost of the new placement data is calculated (304), compared with the cost of the original placement data, and the new placement data is compared based on the cost difference Δc (cost of new placement data-cost of original placement data). Decide whether to adopt (30
5). When △ c <0, the new layout data is adopted, and △
When c> 0, new placement data is adopted with a probability of exp (-Δc / T) and becomes placement data for the next step. At other times, the arrangement data does not change. Here, it is assumed that the one with the increased cost (Δc> 0) is adopted.

If it is adopted, the arrangement data conversion rule is adjusted (306). When the cost decreases, the strength of the selected conversion rule is increased based on the decrease (42). For example, it is increased by a constant multiple of | Δc |. If the cost increases, based on the increase,
The strength of the selected conversion rule is reduced (43). For example, it is decreased by a constant multiple of | Δc |. Since the cost has increased now, it is assumed that the strength of rule 1 is reduced by a constant multiple of | Δc |. Then, it is determined whether the temperature can be lowered (308). The determination method is, for example, that the temperature may be lowered after conversion is performed a certain number of times.
In the example, the temperature is not yet lowered and the search process is not terminated (310). Again, one conversion rule is stochastically selected based on the strength of the arrangement data conversion rule (3
02).

Now, it is assumed that rule 1 and rule 2 have different strengths, rule 2 is easier to select, and rule 2 is stochastically selected. Apply the selected conversion rule rule 2 to generate new placement data (30
3). Now, rule 2 is a conversion rule for converting to heuristic, and the new arrangement data is (4, 3, 2, 1, 5)
Assume that Calculate the cost of new placement data (30
4) Determine whether to adopt the new placement data by comparing with the cost of the original placement data (305).

Here, it is assumed that the cost is reduced and the system is adopted. If adopted, the arrangement data conversion rule is adjusted (306). Since the cost has decreased this time, the strength of rule 2 is increased by a constant multiple of | Δc |, and the probability of being selected from the next time is further increased (42). Then, it is determined whether the temperature can be lowered (308). If it is determined that the update is allowed, the temperature parameter T is reduced (3
09). Then, when the cost of the arrangement data does not decrease from the previous one, the search process ends (31
0).

The layout data and the cost thereof at the time when the search is completed are stored in the optimum layout data storage means 13, and this is the solution to be obtained. In this example, the heuristic
Strict rules are effective in reducing costs
And with a high probability of being selected, the optimal solution can be quickly approached.
Ku. However, rule 1 with randomness is also relatively small
Since it is a probability but selected, it is hard to fall into the local optimal solution.
Yes.

[0029]

As described above, according to the present invention, by increasing the probability that the layout data conversion rule that has the effect of reducing the cost is selected, the efficiency of the search can be improved and a high-quality solution can be obtained at high speed. Can be asked.

[Brief description of drawings]

FIG. 1 is an overall configuration diagram of an embodiment of the present invention

FIG. 2 is a block diagram of arrangement data optimizing means in the embodiment of the present invention.

FIG. 3 is an algorithm of arrangement data optimizing means in the embodiment of the present invention.

FIG. 4 is a layout data conversion rule adjustment algorithm in the embodiment of the present invention.

FIG. 5 is an explanatory diagram of an embodiment of the present invention.

FIG. 6 is a block diagram of an arrangement data optimizing device in a conventional combination optimizing device.

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Shinji Nojima Shinji Nojima 1006 Kadoma, Kadoma City, Osaka Prefecture Matsushita Electric Industrial Co., Ltd. (56) Reference JP-A-2-242474 (JP, A)

Claims (1)

[Claims] 1. Initial placement data for generating initial placement data
Data generating means and the initial arrangement generated by the initial arrangement data generating means.
By starting from the data and repeating the search,
Placement data optimizing means for optimizing data and placement in the process in which the placement data optimizing means performs a search.
Random placement data transformation rules for transforming data
And multiple heuristic placement data transformation rules
Arrangement data conversion rule storage means for storing conversion rules of
And the placement data optimized by the placement data optimizing means.
A layout data conversion means for storing layout data, and the layout data optimization means stores the layout data conversion rule.
Of a plurality of arrangement data conversion rules stored in the storage means
The probability proportional to the strength of each
Select placement data conversion rule Select placement data conversion rule
Method and the selected placement data conversion rule.
New configuration data by converting
The arrangement data generating means and the new arrangement data generated by the new arrangement data generating means.
The difference between the data cost and the original placement data cost
The cost calculation means, and the cost difference and the temperature pattern calculated by the cost calculation means.
Determine whether to adopt new placement data from the value of the parameter
Of the placement data selection means and the cost difference when the placement data selection means selects
Placement data that adjusts the strength of each placement data conversion rule from the value
Conversion rule adjustment means and whether to end the search process for each temperature parameter
Temperature loop end detection means for determining whether or not the temperature parameter is decreased, temperature update means for decreasing the temperature parameter, and a search process when the cost of the arrangement data does not change
And a search end detection means for ending the scan
Combining optimization device .