JPH0997246A - Optimization problem solver - Google Patents

Abstract

(57) Abstract: In a chromosome manipulation in a solution calculation by a genetic algorithm, a search space for an optimal solution is made small by fixing a part of a chromosome, and the calculation can be performed in a short time. SOLUTION: An optimization problem solving method comprising a plurality of subgroup optimization means having a partial decomposition fixing part for calculating a fixed part of a solution, and a subgroup communication means for transmitting solution information in the subgroup optimization means. In the apparatus, the partial decomposition fixing unit includes a frequency calculating unit 2 for calculating the frequency of the pattern state of a part of the solution, and a fixed portion calculating unit 3 for calculating the fixed portion based on this frequency.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an optimization problem solving apparatus, and in particular, in a chromosome operation in a solution calculation by a genetic algorithm, by fixing a part of a chromosome, a search space for an optimum solution can be reduced, This relates to a device that can be calculated in a short time.

[0002]

2. Description of the Related Art There is a method for obtaining an exact solution such as a branch-and-bound method as a solution of a combinatorial optimization problem such as a knapsack problem. However, when the scale of the problem increases, the amount of calculation becomes extremely huge. From the point of view, it will not be practical. A genetic algorithm (GA) is known as a method that can obtain a quasi-optimal solution close to the exact optimal solution at high speed.

[0003]

In the genetic algorithm, when the number of constituent elements that make up a chromosome increases, the number of constituent elements required to find a good solution becomes enormous. It is important to reduce the calculation time.

Therefore, in the chromosome manipulation in the solution calculation by the genetic algorithm, by fixing (that is, not changing) a part of the part constituting the solution (that is, the chromosome), the search space for the optimum solution or the suboptimal solution is reduced. Therefore, it is necessary to provide an optimization problem solving device with reduced calculation time.

By the way, a method of fixing a part of a portion constituting a solution has been invented by the present inventors and has been
The patent application was filed on January 17, 1995 as Patent Application No. 5280 in 1995. An object of the present invention is to provide a different method of partial fixation when a bit string is used as a chromosome representation of a genetic algorithm.

[0006]

[Means for Solving the Problems] In order to achieve the above object, an article 1 having a size and a value as shown in FIG.
In the case of solving the knapsack problem of finding the maximum sum of the value of items packed in a knapsack bag of size 100 when -10 exist, in the present invention, FIG.
As shown in (B), the initial group generation unit 1, the frequency calculation unit 2,
An initial fixed part calculation part 3, an evaluation / selection part 4, a crossover part 5, a mutation part 6, a communication part 7, and a fixed part calculation part 8 are provided.

The initial population generation unit 1 randomly creates the chromosomes ~ of the subpopulation as shown in FIG. The variable x ₁ ~x ₁₀ and corresponds to the item 10, "1" when it is selected to pack the goods in knapsack bag, shows a "0" when not selected. Therefore, as for the chromosome, items 1 to 4, 6, 8, and 10 are not selected, and items 5, 7, and 9 are selected.

The frequency calculation section 2 checks the correlation between the variables in the chromosomes of this subpopulation, as will be described later. For example x ₁ and x _2, x ₂ and x _3, x ₁ and x ₃ · · · as the chromosome-for this subpopulation, what "1" between the variables, the state of "0" is present Whether or not to do so, the correlation is calculated and a frequency table described later is created.

The initial fixed portion calculation unit 3 obtains an initial fixed portion as described later based on the frequency table calculated by the frequency calculation unit 2. In this case, as shown in FIG. 1 (D), for example, the initial fixed portion as shown in the lower stage is obtained for 10 components 1 to 10 of the chromosome. Of these, "1" and "0"
Indicates a fixed position and its value ,? Indicates non-fixed.

The evaluation / selection unit 4 includes the chromosomes of the subpopulation
The fitness of, that is, the total value of the items packed in the knapsack bag is calculated, and the value on the right side of FIG. In this example, there are no chromosomes that exceed the size of the knapsack bag (S = 100), but if they do, the fitness is set to zero.

Then, the evaluation / selection unit 4 erases and among the chromosomes with a certain probability and copies and. The crossover part 5 randomly selects 2 for the above-mentioned chromosomes.
The individual pairs are combined to form the pair shown in FIG. For each pair, decide whether to cross or not with a crossover probability. For example, when the third pair shown in FIG. 1 (E) is crossed, first, 0 or 1 is selected with equal probability for each bit and they are replaced to prepare a bit string. At this time, when the exchange bit string as shown in FIG. 1 (F) is prepared, this is shown in FIG. 1 (D).
When the position of "1" or "0" in the initial fixed part matches the position of "0" in the prepared replacement bit string as compared with the initial fixed part shown below, the uniform crossover with partial fixing is replaced. As a bit string, by this, the bits in the + portion of FIG. As a result, the subgroup after the crossover becomes as shown in FIG.

The mutation unit 6 bit-inverts with a mutation probability given in advance to the post-crossover subpopulation. However, the fixed part is not bit-inverted. For example, the 6th bit of the chromosome of the 4th row of the subpopulation shown in FIG. 1 (H) is mutated.

Such an evaluation / selection unit 4 to a mutation unit 6
The above operation is repeated for a predetermined number of generations. Then, for example, after 10 generations, the communication unit 7 compares the chromosomes with adjacent subgroups (for example, north, south, east, and west).

At this time, the fitness of the best chromosome from the adjacent subpopulation and that of its own subpopulation, that is, the fitness of the chromosome having the highest fitness is compared with the fitness of the best chromosome of the adjacent subpopulation.

As a result, the following three can be considered. a. The best chromosomes of its own subpopulation are better, or more adaptable, than any of the best chromosomes of its adjacent subpopulations.

B. The best chromosomes in its own subpopulation are worse than any of the best chromosomes in the adjacent subpopulations, ie, less fit. c. Neither.

A. If the best chromosome of the own subpopulation is better than any of the adjacent subpopulations, a new fixed portion is calculated for the chromosome of the current subpopulation in the fixed portion calculation unit 8 in the same procedure as the portion for which the initial fixed portion was calculated. .
First, a frequency table is obtained, and a new fixed part is obtained.

B. If the best chromosome of the own subpopulation is worse than any of the adjacent subpopulations, the initial fixed portion is calculated in the fixed portion calculation unit 8 for the best chromosomes of the east, west, south, and north adjacent subpopulations. Calculate a new fixed part using the same procedure as. First, a frequency table is obtained, and a new fixed part is obtained.

Then, in addition to the best chromosomes of east, west, south, and north, the chromosomes that always include this fixed portion are randomly selected so that the size of the subpopulation is the same as the original size.
One is generated to form the own subgroup.

C. When neither of the above is true, for example, when the eastern best chromosome is better than the best chromosome of the own subpopulation, the fixed part calculation unit 8 compares the eastern best chromosome with the fixed part of the own subpopulation, Excludes fixed parts that conflict with.

By repeating such a process, the chromosome having the best fitness can be obtained in a short time.

[0022]

BEST MODE FOR CARRYING OUT THE INVENTION Prior to explaining an embodiment of the present invention, the knapsack problem (Knap) used in the present invention is described.
sack problem). There are N items,
Size Si (Si> 0) and value Vi (Vi>)
0) is given (i = 1, 2, ... N),
When selecting some of these items and packing them into a knapsack bag of size S, the problem is that the total size of the packed products does not exceed the size of the puzack bag and a set of products that maximizes the total value is found. Is.

Formally defined as follows. The item i is packed with the variable x _i (x _i = 1) and not packed (x _i =
0). The total value V ({x _i }) of the items in the knapsack bag at that time is

[0024]

[Equation 1]

[0025] At this time, the knapsack problem is

[0026]

[Equation 2]

Can be written as FIG. 1A shows a simple example of 10 items. For convenience, the items are numbered 1 and 2.
... is represented by 10. Knapsack bag size S = 100
The optimum solution of the knapsack problem is {x _i } =
{1, 1, 0, 1, 1, 1, 1, 0, 1, 0}, the optimum value (total value of packed products) is 117, and the total size of packed products is 99.

An embodiment of the present invention will be described with reference to FIGS. 2 is a configuration diagram of the first embodiment of the present invention, FIG. 3 is a detailed diagram of a sub-population optimization unit in the first embodiment of the present invention, and FIG. 4 is an operation explanatory diagram of the present invention.

In the figure, 10 is a group control unit, 11 is an initial group generation unit, 12 is a subgroup communication unit, 13 and 13-1 to 13-13.
-N is a subgroup optimization unit, 14 is a subgroup control unit, 15
Is a partial decomposition fixed calculation unit, 16 is a fitness calculation unit, 17 is a selection calculation unit, 18 is a crossover calculation unit, 19 is a mutation calculation unit, 2
Reference numeral 0 is a local improvement calculation unit, 21 is a partial decomposition fixed change unit, 22 is a partial fixed solution generation unit, and 23 is a partial group storage unit.

The group control unit 10 controls the operations of the initial group generation unit 11 and the sub-group optimization units 13-1, 13-2, ... The sum of the calculation results from the group optimizing units 13-1, 13-2, ..., And the final calculation result, that is, the solution is output.

The initial population generation unit 11 generates each chromosome of each subpopulation. In the embodiment, each subgroup optimization unit 13
, 13-2 ... Each of the chromosomes are generated. In general, it is desirable that the population be made up of chromosomes that are as different as possible. For example, a random number generator is used to create a random bit string having a length of N bits. This is set as one chromosome and prepared for the number of chromosomes of each subpopulation. Now, assuming that N = 10 and the number of chromosomes for each subpopulation is 6, for example, 6 chromosomes of to shown in FIG. 1C are created for one subpopulation. Therefore, if there are 5 subgroups, 3
Zero chromosomes are created.

The subgroup communication unit 12 is the initial group generation unit 1.
The chromosome created in 1 is used for the subpopulation optimization units 13-1, 13
-2 ... 13-n, or subgroup optimization unit 1
Information relating to chromosomes is exchanged between 3-1, 13-2 ... 13-n.

Subgroup optimization units 13, 13-1, 13-
2 ... 13-n calculates the frequency of chromosomes, calculates the fixed part, evaluates, that is, calculates the fitness, and leaves the chromosomes with high fitness and deletes the chromosomes with low fitness. It crosses two chromosomes to obtain a new chromosome, partially inverts a chromosome to mutate it, or repeats inversion a number of times to invert only when the fitness is improved to locally improve. is there.

Therefore, the sub-group optimization unit 1 shown in FIG.
3, each subgroup optimization unit includes a subgroup control unit 14, a partial decomposition fixed calculation unit 15, a fitness calculation unit 16, a selection calculation unit 17, a crossover calculation unit 18, and a mutation calculation unit 19. , The local improvement calculation unit 20, the partial decomposition fixing change unit 21,
A partial fixed solution generation unit 22, a partial group storage unit 23 and the like are provided.

The sub-population control unit 14 stores the data and parameters input from the sub-population control unit 10 in the sub-population storage unit 23.
Input to the subgroup communication unit 12, the chromosome input from the subgroup communication unit 12 to the subgroup storage unit 23, the chromosome held in the subgroup storage unit 23 to the subgroup communication unit 12, partial decomposition fixed The calculation unit 15 to the local improvement calculation unit 20 are selectively operated.

The partial decomposition fixed calculation unit 15 calculates the frequency of the chromosomes of the subpopulation, and calculates the fixed part based on this, and is provided with the frequency calculation unit and fixed part calculation unit shown in FIG. 1B. It is a thing.

Next, the operation of the partial decomposition fixed calculation unit 15 will be described separately for its frequency calculation and fixed partial calculation. When the initial chromosomes of a certain subpopulation are randomly generated and given as the chromosomes ~ shown in Fig. 5 (A), first, the frequency table shown in Fig. 5 (B) is created. In this frequency table, any two bits of the chromosome are "1, 1", "1, 0", "0,
The pattern "1" or "0, 0" is created for the chromosomes ~, and represents the correlation between each bit.

The frequency table is composed of four numbers, the vertical axis indicates i (1-9) shown in FIG. 5A, and the horizontal axis indicates j (2).
10) is shown. These four numbers show how many times there are patterns of a combination of 2 bits of i and j, and the numbers at the upper left are the patterns “1, 1”.
, The lower left number indicates the output frequency of the pattern "0, 1", the upper right number indicates the output frequency of the pattern "1, 0", and the lower right number indicates the pattern "0, 0". Indicates the output frequency.

Therefore, the four numbers on the upper left side shown in the frequency table of FIG. 5B are when i = 1 and j = 2, that is, in FIG.
It shows the state of the leftmost 2-bit pattern of the chromosome shown in (A). In the leftmost 2 bits of this chromosome, the pattern of "1, 1" is twice, "0,
The pattern of "1" is once, the pattern of "1, 0" is twice,
The number on the upper left side indicates that the pattern of "0, 0" exists once.

Similarly, the four numbers on the lower right side of the frequency table of FIG. 5B are "1" when i = 9 and j = 10, that is, in the 2-bit pattern on the rightmost side of the chromosomes. "1" pattern is 0, "0, 1" pattern is three times, "1,
This indicates that the pattern of “0” exists twice and the pattern of “0, 0” exists once.

Next, for fixed part calculation, the frequency threshold value is set to 6, and F11 (i, j) + F00 (i, j) ≧ 6 or F10 (i, j) + F01 (i) shown in FIG. 5B. , J) ≧ 6 is searched for (i, j). As a result, (2, 7) and (5, 10) are detected from the frequency table of FIG. These positions 2, 7, 5 and 10 are fixed positions, and the values of “1” and “0” of them are F11 (i, j) or F00.
The larger value of (i, j), F10 (i, j) or F01 (i, j) is selected. If they are the same, select randomly.

As a result, as the fixed part, the second, fifth, seventh and tenth bit positions are fixed to "1" and "0" as shown in FIG. 5 (C). What? Indicates non-fixed. In the present invention, fixed / non-fixed is determined by paying attention to the relationship between each bit and other bits in this way. Generally, a subgroup having a strong correlation between bits in a chromosome (bit string) is fixed. Therefore, as described above, a set of variables in which the same value frequently appears in the subgroup, for example, (2,
7) and (5, 10) were detected and those variables were set as the fixed part.

That is, a certain positive integer (hereinafter referred to as the number of variables, K = 2 in the above example) is determined (2≤K <N, N
Is the bit length of the chromosome). A set of variables (x _j1 , x _j2 , x _j3 ,
... x _jK ) has a value of (0, 0, 0, ... 0, 0),
(1, 0, 0, ... 0, 0), (1, 1, 0, ...)
0,0) ..., (1,1,1, ... 1,0),
The frequencies of (1, 1, 1, ... 1, 1) (total of 2 ^K ways) are calculated for all chromosomes in the subpopulation. That is, make a frequency table.

The value of the variable set is (p ₁ , p ₂ , ... P _K ).
, The frequency is Fp ₁ , p ₂ , ... P _K (x _j1 , x
_{, j2} , ..., X _jK ).

[0045]

(Equation 3)

At this time

[0047]

[Equation 4]

Satisfy A certain threshold value (hereinafter referred to as a frequency threshold value) T (0 <T ≦ M) is prepared. For a set of values (p ₁ , p ₂ , ..., P _K ),

[0049]

(Equation 5)

A set of variables (x_j1, X_j2, ...
., X_jK) Exists, x_j1, X _j2, ..., x_jK
Is included in the fixed part. Alternatively, you can use a set of values
(P₁, P₂・ ・ ・ P_K), F_p1,_p2..._pK(X_j1, X_j2, ..., x_jK) ≧ T satisfying a set of variables (x_j1, X_j2, ..., x_jK)exist
When you do x_j1, X_j2, ..., x_jKIncluded in the fixed part
You may make it do.

As another method, K and T are set to 1
It is also possible to prepare a plurality of types without being limited to each type, and to combine them with the fixed parts obtained by the above-mentioned calculation method, for example, to obtain a set sum and use it as the fixed part. .

The fitness calculator 16 calculates the fitness of each chromosome in the subpopulation. That is, the sum V ({x _i }) of the values of the items packed in the knapsack bag is calculated. At this time, the total sum of the sizes is also calculated, and when there is a chromosome that exceeds the size of the knapsack bag, the fitness is set to zero.

For example, the sum of fitness and size is calculated for the chromosomes shown in FIG. In this example, there is no chromosome that exceeds the size of the knapsack bag S = 100, but the fitness of that chromosome is zero.

The selection calculator 17 leaves the chromosomes with high fitness among the chromosomes in the subpopulation and deletes those with low fitness. When this deletion is performed, a highly adaptable one is duplicated in the same subgroup if necessary. At this time, roulette
By selecting the wheel, the probability can be determined and the selection of residual elimination can be performed. If the fitness of the chromosome k is H _k , the survival of the chromosome k is selected by probability = H _k / (H ₁ + H ₂ + ... + H _N ).

In the example of FIG. 6 (A), as shown in FIG. 6 (B), the sum of fitness of each chromosome is 487, so that these six chromosomes have a probability of 72/487 and 86/4, respectively.
87, 116/487, 73/487, 49/487,
It is allowed to be duplicated and selected until it becomes a total of 6 in 91/487. As a result, the chromosome as shown in FIG. 6C is selected by the selection operation.

The evaluation / selection unit 4 in FIG.
Is composed of the fitness calculator 16 and the selection calculator 17. The crossover calculation unit 18 further performs a crossover operation on the selected chromosome. First, two pairs are randomly combined for each of the six chromosomes shown in FIG.
The pair P ₁ , P ₂ , P ₃ shown in FIG. 7 is obtained. This pair P ₁
About P ₃ , a crossover probability given in advance determines whether or not to cross each pair. In this case, the pair P ₁
And P ₂ are not crossed, but the pair P ₃ is crossed. There are uniform crossover and uniform crossover with partial fixation in the crossover, but in the present invention, since the fixed part is calculated based on the correlation of the chromosomes as described above, the latter crossover is based on the uniform crossover with partial fixation. I do.

For uniform crossover, "0" or "1" is selected with equal probability for each bit forming a chromosome, and a replacement bit string is prepared by arranging them. For example, FIG. 7B is prepared. Uniform crossover between chromosomes A and B without partial fixation is
If the corresponding bit of the exchanged bit string is "1", it means that the bits are exchanged between the chromosomes A and B, and if it is "0", it remains as it is.

For example, as shown in FIG. 7C, chromosomes A and B
7), when uniform crossover is performed based on the exchanged bit string shown in FIG. 7B, the + -marked bits are exchanged, and after crossover, the chromosomes A ′ and B ′ are obtained.

By the way, in the uniform crossover with partial fixation, a replacement bit string in which the replacement bit corresponding to the fixed position is always "0" is prepared so that the fixed position does not enter all the "1" parts of the replacement bit string. To do. Bit replacement is performed in the same way as without partial fixing.

For example, when the fixed part is as shown in FIG. 7 (D), the replacement bit string shown in (E) of FIG.
The portion corresponding to the fixed position is “0”, so the requirement is satisfied, but the replacement bit string shown in (E) of FIG. 7 does not satisfy the requirement because the second portion from the left is not “0”.

When the exchange bit string is as shown in FIG. 7 (E) and the chromosomes A and B are as shown in FIG. 7 (F),
Since the bit of the + mark is exchanged, after the crossover by the uniform crossover with the partial fixation, A ′ and B ′ of FIG.
It becomes as shown in.

Therefore, in the selection calculation unit 17, the selected chromosomes shown in FIG.
In each pair of chromosomes shown in FIG.
Performs uniform crossover with partial fixing according to a predetermined crossover probability. As a result, it occurs crossover pair P ₃ shown in FIG. 7 (A), when the replacement bit string is a view 7 (E), as shown in FIG. 8 (A), a bit of + marks pair P ₃ Swapping occurs and the pair P ₃ ′ is obtained. As a result, the subgroup after the crossover becomes as shown in FIG. When this replacement is performed in a plurality of pairs by probability, different replacement bit strings are prepared for each pair.

The mutation calculator 19 performs bit inversion with a mutation probability given in advance for the chromosome. However, the fixed part is not bit-inverted. For example, when a mutation occurs in the 6th bit of the chromosome in the 4th row of the subpopulation shown in FIG. 8B, the mutation results in that shown in FIG. 8C.

The local improvement calculation unit 20 repeats the bit inversion described in the mutation calculation unit 19 a plurality of times with a given probability. At this time, the fitness is inverted only when the fitness increases, and when the fitness does not increase even when the fitness is reversed, the reversal is not performed.

As shown in FIG. 9A, the partial decomposition fixing changing unit 21 has the best chromosome of its own subpopulation optimizing unit 13-1 and the subpopulation optimizing units 13-2, 13-3, 13 adjacent thereto. −
4 and 13-5 are compared with the best chromosome to change the fixed part in the own subpopulation optimizing unit 13-1.

That is, in a certain generation, the local sub-group optimization unit 1
It is assumed that 3-1 updates the fixed part. At this point, what is held by the sub-group optimization unit 13-1 is as shown in FIG.
The six chromosomes shown in (B), the fixed part of which is shown in FIG.
As shown in (C), the adjacent sub-group optimization unit 13
-2, 13-3, 13-4, 13-5, the highest fitness chromosome, that is, the best chromosome, is shown in FIG.
(D).

Each subgroup optimization unit 13-1, 13-2,
13-3, 13-4, 13-5, etc. are provided with comparison units not shown, and these are connected to a square lattice torus by the subgroup communication unit 12 to connect the chromosomes of adjacent subgroups. It is configured so that the fitness can be detected.

In the example shown in FIG. 9A, when the chromosome held in the subpopulation optimizing unit 13-1 is used as the chromosome of its own subpopulation, the adjacent subpopulation optimizing units 13-2, 13-
The chromosomes held at 3, 13-4 and 13-5 are called east, west, south and north chromosomes, respectively. Then, the following processing is performed.

First, the fitness of the best chromosome, which is the highest fitness chromosome of the subpopulation, is compared with the fitness of the best chromosome of each adjacent subpopulation. This considers the following three cases.

When the best chromosome of the own subpopulation is better than any of the adjacent subpopulations, that is, when the fitness of the best chromosome of the own subpopulation is higher than that of each of the best chromosomes of the adjacent subpopulation.

When the best chromosome of the own subpopulation is worse than any of the adjacent subpopulations, that is, when the fitness of the best chromosome of the own subpopulation is lower than that of each of the best chromosomes of the adjacent subpopulation.

When neither of the above is true. The method of changing the fixed part is different in each case. Each case will be described below.

If the best chromosome of the own subpopulation is better than any of the best chromosomes of the adjacent subpopulations, then FIG.
For the chromosomes of the current subpopulation shown in (B), a new fixed part is calculated by the same procedure as that for calculating the initial fixed part in FIG. First, as shown in FIG. 10A, a frequency table is obtained.

Then, with the frequency threshold value as 6, a search is made for (i, j) such that F11 (i, j) + F00 (i, j) ≧ 6 or F10 (i, j) + F01 (i, j) ≧ 6. As a result, (3, 7) and (5, 9) are detected from the frequency table of FIG. These positions 3, 5, 7, 9 are fixed positions, and their values are F11 (i, j) or F00 (i, j), F10.
Select the larger value of (i, j) or F01 (i, j). If they are the same, select randomly. As a result, FIG.
Fixed parts "0" and "1" at bit positions as shown in (B)
A new fixed part with is obtained. Note that in FIG. 10 (B)? Indicates non-fixed.

There are no changes to the subpopulation chromosomes themselves. The size of the subgroup and the frequency threshold may be different for each generation. If the ratio of the fixed part is already a certain value or more than the non-fixed part, the fixed part is not calculated again.

When the best chromosome of the own subpopulation is worse than any of the adjacent subpopulations, the best chromosome of the adjacent subpopulation shown in FIG. 9 (D) is regarded as one subpopulation, and the initial fixed portion is obtained. Compute a new fixed part using the same procedure as that for computing. First, as shown in FIG. 11A, a frequency table is obtained.

Then, with the frequency threshold value set to 4, a search is made for (i, j) such that F11 (i, j) + F00 (i, j) ≧ 4 or F10 (i, j) + F01 (i, j) ≧ 4. . Thereby, from the frequency table of FIG. 11A, (2, 5), (2, 7), (3, 9), (5,
7) is detected. These positions 2, 3, 5, 7, 9 are fixed positions, and their values are F11 (i, j) or F00 (i, j), F10 (i, j) or F01.
Select the larger value of (i, j). If they are the same, select randomly. As a result, a new fixed part having fixed parts "0" and "1" at the bit position as shown in FIG. 11B is obtained. Note that in FIG. 11B? Indicates non-fixed. Then, the partial fixed solution generation unit 22 described later
It constitutes its own subgroup shown in (C).

The size of the subgroup and the frequency threshold may be different for each generation. When neither of the above is true, for example, when the eastern best chromosome “0011100101” is better than the best chromosome of the own subpopulation, this is compared with the fixed part of the own subpopulation as shown in FIG. 9C. That is, the "east" chromosome 0011100101 fixed part? ? 0? ? ? 1? ? ? Compare. And the fixed part which contradicts is excluded.

In this example, both the 3rd bit and the 7th bit of the fixed part differ from the "east" chromosome, which is better than the chromosome of the own subpopulation, so this contradictory fixed part is removed and a new fixed part is created. All as below? Becomes

New fixed part? ? ? ? ? ? ? ? ? ? There are no changes to the subpopulation chromosomes themselves. As described above, the partial fixed solution generator 22 randomly generates a chromosome containing a new fixed part obtained by calculating the common part of the best chromosomes of the adjacent partial groups, and reconstructs its own partial group. . In the above example, when the new fixed part shown in FIG. 11 (B) is transmitted from the partial disassembly / fixing / changing part 21, “East”, “West” shown in FIG. 9 (D),
In addition to the best chromosomes of “north” and “south”, two chromosomes that always include this new fixed part are randomly generated so that the size of the subpopulation becomes the original size.
The new own subgroup shown in (C) is constructed.

In the above description, an example in which four adjacent subgroups, east, west, north, and south, are used has been described, but the adjacent subgroups are not limited to this.
Two or five or more can be set as appropriate.

The operation of the present invention will be described by the following steps based on the flowchart shown in FIG. S1. First, for example, when a solution of a knapsack problem is generated, the number N of items, the size and value of each item, and the size of a knapsack bag are input as data to the group control unit 10. For example, as shown in FIG. 1 (A), the size and value of 10 items, the size of a knapsack bag, such as 100, are input. Also, as parameters, the number of chromosomes per subpopulation (6 in the above example), the number of fixed partial change generations (eg, every 10th generation, crossover probability, mutation rate, local improvement rate,
Enter the selection probability. These data and parameters are input to the subpopulation optimizing units 13-1, 13-2, ..., And the initial population generation unit 11.

Now, assuming that the number of sub-population optimizing units is 5, the initial-population generating unit 11 has 6 chromosomes per sub-population optimizing unit, that is, 6 × 5 = 30 chromosomes in total, for example. Create using a random number generator. Then, the created chromosomes are distributed to the sub-group optimization units 13-1, 13-2, ... In this way, for example, the subpopulation optimizing unit 13-1 receives the chromosome as shown in FIG. In this way, the initial chromosome population is generated.

S2. Subgroup optimization units 13-1, 13-
In 2 ..., as shown in FIG.
Calculates the frequency of the chromosomes of the subpopulation based on these 6 chromosomes, and calculates the fixed portion based on this. Therefore, first, a frequency table is created as shown in FIG. Then, search for (i, j) whose F11 (i, j) + F00 (i, j) or F10 (i, j) + F01 (i, j) is, for example, 6 or more, and search for (2,7), ( 5, 1
0) is detected, and as described above, as shown in FIG. 5 (C), the second, fifth, seventh and tenth bit positions are “1”,
The fixed part fixed at "0" is calculated.

S3. After obtaining the fixed portion in this way, the next-generation population is obtained by performing evaluation, selection, crossover, mutation, etc. of the chromosome population in each subpopulation. For example, the fitness calculation unit 16 calculates the fitness of the chromosomes shown in FIG. 6A, the selection calculation unit 17 selects residual elimination by, for example, roulette wheel selection, and the crossover calculation unit 18 performs the calculation of FIG. The crossover operation as described with reference to FIG. 8A is performed, and the mutation operation unit 19 performs the operation shown in FIG.
Mutation is performed as described in (D). Then, the local improvement calculation unit 20 repeats the inversion according to a certain probability. In this way, a next-generation subpopulation of chromosomes is obtained. That is, if this is performed once for the initial chromosome population, it becomes a second-generation subpopulation, and if it is performed twice, it becomes a third-generation subpopulation.

S4. The sub-group control unit 14 uses the above (3)
When it is determined that the improvement will be further advanced each time, the above (3) is repeated without determining the end. S5. Then, when this iteration is repeated a predetermined number of times, for example, 10 times, the intermediate result is exchanged with the adjacent subgroup. For example, as shown in FIG. 9, in the own subpopulation optimization unit 13-1, the adjacent subpopulation optimization unit 13-
The best chromosome of each subgroup is received from 2, 13-3, 13-4, 13-5 via the subgroup communication unit 12.

For example, "East", "West", "North", "South"
When the best chromosomes of the adjacent sub-populations are transmitted, the local sub-population optimization unit 13-1 calculates the fitness of these best chromosomes. Of course, the fitness may be transmitted together. The best chromosomes of these adjacent subpopulations are then compared for better or worse than the best chromosomes of their subpopulation.

S6. Depending on the result of this comparison,
, Or change the fixed part or reorganize the own subgroup. That is, when the best chromosome of the own subpopulation is better than any of the best chromosomes of the adjacent subpopulations, the fixed part in the own subpopulation is recalculated as described above, and the fixed part is set as the fixed part. In this case, the size of the subgroup and the frequency threshold are S
It does not have to be the same as 2. It may be different for each generation. However, when the ratio of the fixed portion is already higher than a certain fixed value than the non-fixed portion, the fixed portion is not calculated again.

If the best chromosome of the own subpopulation is worse than any of the best chromosomes of the adjacent subpopulations, the best chromosomes of the adjacent subpopulations are collected and regarded as one subpopulation. Calculate the fixed part.
In this case, the size of the subgroup and the frequency threshold do not have to be the same as S2, and may differ for each generation. Then, randomly generate a chromosome containing the fixed part,
This and the best chromosomes of adjacent subpopulations must be included, as shown in Figure 1.
As shown in 1 (C), the own subgroup is reconstructed.

If neither of the above is true, as described above, the best chromosome of the adjacent subpopulation that is better than the best chromosome of its own subpopulation is compared with the fixed portion of its own subpopulation, and the inconsistent fixed portion is removed. At this time, the own subpopulation may include the best chromosome of the adjacent subpopulation.

For example, if the value of a certain bit of the fixed part is "0" and the value of the bit at the corresponding position of the best chromosome of the adjacent subpopulation is "1", the bit of "0" is excluded from the fixed part. .

S7. In each of the subgroup optimization units,
The same processing as in step S3 is performed. This is repeated until the termination condition is satisfied. The process ends when it is determined that further improvement cannot be made. Then, the chromosome at that time is output from the group control unit 10 as a calculation result.

With such a configuration, the results shown in FIG. 14 were obtained for the following knapsack problem. The knapsack problem used is the number of items = 900, the size of the item is an integer value from 1 to 1000, and its value is 1 to 1
It was an integer value up to 000. These values were given using pseudo-uniform random numbers. The larger the size, the greater the value. The sample correlation coefficient of size and value = 0.97. Knapsack size (upper limit) = 200000.

In the genetic algorithm, the selection method is roulette wheel selection, the crossover method is uniform crossover in non-fixed GA, the uniform crossover with partial fixed GA is used, and the mutation is bit inversion. And no local improvement was used. The parameter value of the genetic algorithm is 64 (= 8 × 8), and 40 chromosomes in the subgroup.
(Total number of chromosomes: 2560), fixed part change every 20 generations, crossover probability 0.6, mutation rate 0.001. Note that these are not the best combination of parameter values.

The simulation was carried out up to the 8000th generation. For comparison, the solution was not partially fixed, but a parallel genetic algorithm in which the solution was divided into subgroups was also simulated.

FIG. 14 compares the number of generations for which a solution was found. The best value (solution) in the 0th generation is 201346, the solution 220,000 is the 484th and 306th generations, and the solution 225500 is the 7673rd and 128th, respectively.
I have found it in the 9th generation. The ratio of the number of generations (rate of acceleration) was 1.6 and 6.0. By performing partial fixing, it is shown that the search time is shortened, that is, the number of generations required to find a more optimal solution is reduced.

It can be seen that by performing partial fixing in this way, the number of generations required to find a more optimal solution is reduced, that is, the search time is shortened. A second embodiment of the present invention will be described based on FIGS. 12 and 13. 12 and 13, 30 is a group control unit, 31 is a subgroup communication unit, 32, 32-1 to 32-m are subgroup optimization units, 33 is a subgroup control unit, and 34 is a partial decomposition fixed calculation unit. , 35 is a solution generator, 36 is a fitness calculator, 37 is a selection calculator, 38 is a crossover calculator, 39 is a mutation calculator, 4
Reference numeral 0 is a local improvement calculation unit, 41 is a partial decomposition fixed change unit, 42 is a partial fixed solution generation unit, and 43 is a partial group storage unit.

In the first embodiment of the present invention, the collective control unit 10
Based on the data and parameters input to the subgroup optimization unit 13-1, 13-2 ...
Although the required number of chromosomes has been generated and transmitted to the population control unit 30 in the solution generation unit 35 in the second embodiment of the present invention, as representatively shown by the subpopulation optimization unit 32 in FIG.
The number of chromosomes required for the sub-population optimizing units 32-1, 32-2, ... Is generated based on the data and parameters input to. Since the others are the same, detailed description of the operation is omitted.

The group control unit 30 corresponds to the group control unit 10, the subgroup communication unit 31 corresponds to the subgroup communication unit 12, and the subgroup optimization units 32, 32-1, 32-2 ...
· Subgroup optimization units 13, 13-1, 13-2 ...
The partial group control unit 33 corresponds to the partial group control unit 14, and the partial solution fixed calculation unit 34 corresponds to the partial solution fixed calculation unit 15.
The fitness calculation unit 36 corresponds to the fitness calculation unit 16, the selection calculation unit 37 corresponds to the selection calculation unit 17, the crossover calculation unit 38 corresponds to the crossover calculation unit 18, and the mutation calculation unit 3
Reference numeral 9 corresponds to the mutation calculation unit 19, and the local improvement calculation unit 40
Corresponds to the local improvement calculation unit 20, and the partial decomposition fixing change unit 41
Corresponds to the partial decomposition fixed change unit 21, and the partial fixed solution generation unit 4
Reference numeral 2 corresponds to the partial fixed solution generation unit 22, and the partial group storage unit 4
3 corresponds to the partial group storage unit 23.

In the second embodiment of the present invention, since the initial chromosome populations are generated in parallel in each of the subpopulation optimizing units 32-1, 32-2, ..., The calculation can be performed in a short time.

In the above description, as shown in FIGS. 5 (A) and 5 (B), the frequency table is a combination of 2-bit chromosomes (i, j).
However, the present invention is not limited to this.

For example, when the size of the subgroup (the number of variables) K = 3 when the chromosome is given as shown in FIG. 15 (A), the fixed part is obtained as follows. This is K = 2
Can be calculated similarly as an extension of. For convenience, the three variables are represented by i, j, k. Similar to the case of K = 2, the following frequencies are obtained.

That is, the frequency F111 (i, j, k), F
110 (i, j, k), F101 (i, j, k), F1
00 (i, j, k), F011 (i, j, k), F01
0 (i, j, k), F001 (i, j, k), F000
Find (i, j, k).

Since there are three variables, the frequency table becomes a three-dimensional three-dimensional table. Therefore, as in the case of K = 2 shown in FIG. Since it cannot be described, no concrete value is described here.

For example, when the frequency threshold value is 6, F1
11 (i, j, k) + F000 (i, j, k) ≧ 6 or F110 (i, j, k) + F001 (i, j, k) ≧
6 or F101 (i, j, k) + F010 (i, j,
k) ≧ 6 or F100 (i, j, k) + F011
Any one of (i, j, k) ≧ 6 holds (i, j
Find j, k).

In this case, there is one set, which is (2, 7,
It was 9). The frequencies at this time are: F111 (2,7,9) = 0, F110 (2,7,9)
= 0, F101 (2, 7, 9) = 0, F100 (2,
7,9) = 3 F000 (2,7,9) = 0, F001 (2,7,9)
= 0, F010 (2, 7, 9) = 0, F011 (2,
7, 9) = 3.

These positions 2, 7, 9 are fixed positions,
Their values are F100 (2, 7, 9) and F011.
Compare (2, 7, 9) with the larger value. Assuming that F100 (2, 7, 9)> F011 (2, 7, 9)
Then, the fixed portion is as shown in FIG. Here, "1" and "0" are fixed positions and their values, and? Indicates non-fixed. Since this example is the same, one of them is randomly selected, and the fixed portion is as shown in FIG. 15C, for example.

Further, when the chromosomes are given as shown in FIG. 15D and the size of the subgroup (the number of variables) K = 4, the fixed part is obtained as follows. For convenience, the four variables are represented by i, j, k, and l.

First, the frequency F1111 (i, j, k, l),
F1110 (i, j, k, l), F1101 (i, j,
k, l), F1100 (i, j, k, l), F0000
(I, j, k, l), F0001 (i, j, k, l),
F0010 (i, j, k, l), F0011 (i, j,
k, l), F1011 (i, j, k, l), F1010
(I, j, k, l), F1001 (i, j, k, l),
F1000 (i, j, k, l), F0100 (i, j,
k, l), F0101 (i, j, k, l), F0110
(I, j, k, l) and F0111 (i, j, k, l) are obtained.

For example, when the frequency threshold value is 5, F1111 (i, j, k, l) + F0000 (i,
j, k, l) ≧ 5 or F1110 (i, j, k, l)
+ F0001 (i, j, k, l) ≧ 5 or F1101
(I, j, k, l) + F0010 (i, j, k, l) ≧
5 or F1100 (i, j, k, l) + F0011
(I, j, k, l) ≧ 5 or F1011 (i, j,
k, l) + F0100 (i, j, k, l) ≧ 5 or F
1010 (i, j, k, l) + F0101 (i, j,
k, l) ≧ 5 or F1001 (i, j, k, l) + F
0110 (i, j, k, l) ≧ 5 or F1000
(I, j, k, l) + F0111 (i, j, k, l) ≧
Variable set (i, j, k, l) such that any of 5 holds
Look for.

In this case, there is one set of (2, 7, 9,
It was 10). F1111 (2, 7, 9, 10) = 0, F1110
(2, 7, 9, 10) = 0, F1101 (2, 7, 9,
10) = 0, F1100 (2, 7, 9, 10) = 0, F
0000 (2, 7, 9, 10) = 0, F0001 (2,
7, 9, 10) = 0, F0010 (2, 7, 9, 10)
= 0, F0011 (2, 7, 9, 10) = 0, F101
1 (2, 7, 9, 10) = 0, F1010 (2, 7,
9,10) = 0, F1001 (2,7,9,10) =
3, F1000 (2, 7, 9, 10) = 0, F0100
(2, 7, 9, 10) = 0, F0101 (2, 7, 9,
10) = 0, F0110 (2, 7, 9, 10) = 2, F
0111 (2,7,9,10) = 1 These positions 2, 7, 9, 10 are fixed positions, and their values are F1001 (2, 7, 9, 10) and F0110.
(2, 7, 9, 10) compared to the larger value, that is, F
Select 1001 (2, 7, 9, 10).

As a result, the fixed portion becomes each bit position of 2, 7, 9, 10 and its value becomes "1001". That is, it becomes as shown in FIG. We also show an example of calculating the fixed part under different conditions using the same chromosome population. For example, as shown in FIG. 16A, the partial chromosome population is given by the total number of chromosomes M = 8 and the number of bits of each chromosome = 10.

At this time, the fixed part is calculated by the number of variables K and the frequency threshold T under the following conditions 1) and 2). Condition 1): K = 3, T = 6 Condition 2): K = 2, T = 8 Condition 1) Frequency F111 (i, j, k), F110 (i, with respect to a set of variables (i, j, k) j, k), F
101 (i, j, k), F100 (i, j, k), F0
00 (i, j, k), F001 (i, j, k), F01
0 (i, j, k) and F011 (i, j, k) are obtained. And F111 (i, j, k) + F000
(I, j, k) ≧ 6 or F110 (i, j, k) + F
001 (i, j, k) ≧ 6 or F101 (i, j,
k) + F010 (i, j, k) ≧ 6 or F100
Search for (i, j, k) that satisfies any of (i, j, k) + F011 (i, j, k) ≧ 6.

There is one set, which is (2, 4, 8). F111 (2,4,8) = 1, F110 (2,4,8)
= 3, F101 (2,4,8) = 0, F100 (2,
4, 8) = 0, F000 (2,4,8) = 0, F001
(2, 4, 8) = 3, F010 (2, 4, 8) = 0, F
011 (2, 4, 8) = 1 Therefore, the fixed positions are 2, 4, and 8. The values of those positions are F110 (2, 4, 8) and F001 (2, 4, 8).
Both are the same as 3, so choose one at random,
1, 1, 0, and the fixed part is as shown in FIG. 16 (B).

Condition 2) For the set of variables (i, j), the frequency F11 (i, j),
F10 (i, j), F01 (i, j), F00 (i,
j) is calculated. As a result, the frequency table shown in FIG. 16C is obtained. 4 in the column corresponding to each (i, j) in this frequency table
Two values are arranged, but this is F11 in order from the left.
(I, j), F10 (i, j), F01 (i, j), F
00 (i, j) is shown.

From this frequency table, (i, j) satisfying either F11 (i, j) + F00 (i, j) ≧ 8 or F10 (i, j) + F01 (i, j) ≧ 8 is searched. However, in this case, no set exists. Therefore, the fixed part is all-shaped as shown in FIG. , Only the non-fixed part with no fixed value.

Further, according to the present invention, the calculation method of the fixed part can be changed according to the situation change. In the initial stage of the search of the genetic algorithm, that is, in the early generations, the chromosome population generally varies considerably. Therefore, the calculation of the fixed part has relatively loose conditions, for example, K = 3, T =
6 and then, for example, after 100 generations, the variation in the chromosome population has decreased, so relatively strict conditions,
For example, K = 3 and T = 8 are used. In general, the larger K and T are, the smaller the fixed portion obtained by calculation becomes, and the stricter the condition becomes.

In the present invention, the fixed parts can be calculated under different conditions, and the fixed parts obtained from them can be combined to form a new fixed part other than these. It is assumed that there are certain conditions 1) and 2), and the fixed position and its value are obtained from them. If a position is contained only in either of them, put it in a new fixed part separate from both. Also, when a certain position is included in both,
Only when both values match, put it in the new fixed part.

For example, as shown in FIG. 17, when the results from the conditions 1) and 2) are obtained, the variable 2 is included in both, and the values are the same, so that the variable 2 is put in a new fixed part.
However, although variable 4 is included in both, the values do not match, so it cannot be included in the new fixed part. Also variable 3,
Since 7 is included only in condition 2, it is put in a new fixed part. Since the variable 8 is included only in the condition 1, it is put in a new fixed part. In this way, a new fixed part as shown in FIG. 17 is obtained.

According to the present invention, a portion having a large correlation is detected by the frequency table and the fixed portion is obtained based on the detected portion, so that an appropriate fixed portion can be detected.

[0121]

According to the present invention described in claim 1, the correlation between chromosome parts is made less likely to be broken by genetic manipulation, and as a result, the calculation time is shortened. According to the present invention described in claim 2, the fixed portion of the chromosome in the subpopulation can be more accurately determined, and thereby the calculation time can be shortened.

According to the present invention described in claim 3, the fixed portion of the chromosome can be more accurately determined in response to the change in the subpopulation as the generation progresses. Can be shortened.

[Brief description of drawings]

FIG. 1 is a principle configuration diagram of the present invention.

FIG. 2 is a configuration diagram of an embodiment of the present invention.

FIG. 3 is a configuration diagram of a sub-population optimization unit according to an embodiment of the present invention.

FIG. 4 is an operation explanatory diagram (1) of the present invention.

FIG. 5 is an operation explanatory diagram (2) of the present invention.

FIG. 6 is an operation explanatory diagram (3) of the present invention.

FIG. 7 is an operation explanatory diagram (4) of the present invention.

FIG. 8 is an explanatory view (No. 5) of the operation of the present invention.

FIG. 9 is an operation explanatory diagram (6) of the present invention.

FIG. 10 is an operation explanatory diagram (7) of the present invention.

FIG. 11 is an operation explanatory diagram (8) of the present invention.

FIG. 12 is a configuration diagram of a second embodiment of the present invention.

FIG. 13 is a configuration diagram of a sub-population optimization unit in the second embodiment of the present invention.

FIG. 14 is an explanatory diagram of a generation for which a solution is found in the present invention.

FIG. 15 is another example of the fixed partial calculation explanatory diagram in the present invention.

FIG. 16 is an explanatory diagram when a fixed part is calculated under different conditions for the same chromosome group in the present invention.

FIG. 17 is an explanatory diagram of another fixed part calculated by combining fixed parts obtained under different conditions in the present invention.

[Explanation of symbols]

 1 initial population generation unit 2 frequency calculation unit 3 initial fixed sub-calculation unit 4 evaluation / selection unit 5 crossover unit 6 mutation unit 7 communication unit 8 fixed sub-calculation unit 10 group control unit 11 initial population optimization unit 12 initial group communication unit 13, 13-1 to 13-n Sub-population optimization part 14 Sub-population control part 15 parts Decomposition fixed calculation part 16 Fitness calculation part 17 Selection calculation part 18 Crossover calculation part 19 Mutation calculation part 20 Local improvement calculation part 21 part Solution fixed change unit 22 Partial fixed solution generation unit 23 Subgroup storage unit

Front page continued (72) Inventor Yukiko Yoshida 1015 Kamiodanaka, Nakahara-ku, Kawasaki-shi, Kanagawa Inside Fujitsu Limited

Claims (3)

[Claims] 1. An optimization problem comprising a plurality of subgroup optimizing means having a partial decomposition fixing part for calculating a fixed part of a solution and a subgroup communicating means for transmitting solution information in the subgroup optimizing means. In the solution apparatus, the partial decomposition fixing unit includes a frequency calculating unit that calculates the frequency of the pattern state of a part of the solution, and a fixed portion calculating unit that calculates the fixed portion based on this frequency. Problem solving device. 2. The fixed part is calculated for each size of several subgroups of chromosomes when the fixed part is calculated, and these are combined to form a fixed part. Optimization problem solver. 3. The optimization problem solving method according to claim 1, wherein when the fixed portion is calculated, the fixed portion is obtained by changing the threshold value of the size or frequency of the subgroup of chromosomes according to the generation. apparatus.