Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
1997-09-08
2001-11-13
Hafiz, Tariq R. (Department: 2762)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C705S002000, C706S013000, C707S793000
Reexamination Certificate
active
06317732
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
This application relates to U.S. Ser. No. 274,016 filed Jul. 12, 1994, now U.S. Pat. No. 5,623,580 issued Apr. 22, 1997, assigned to Hitachi, Ltd. and Hitachi Engineering Co., Ltd., the disclosure of which is incorporated herein by reference.
BACKGROUND OF THE INVENTION
The present invention relates to a planning system and a planning method, and more particularly to technology for offering meshing information when an assigned section is to be taken charge of by a plurality of persons in distributing and collecting items and discussing various problems, technology for offering meshing information for conducting strength test of an article, technology for offering work division information when a work is to be conducted by a plurality of persons or technology for offering meshing information technology for conducting city planning, and further particularly to linear programming system and method suitable for determining a solution with a simple construction as to a problem for unifying the meshing.
The meshing planning and designing relates to a problem to divide a given assigned section (one to three-dimension) by a given divisor and determine such a solution that makes weights of the divided sections, for example, areas, weights or work amounts uniform for each divided section.
This problem is considered as a kind of clustering problem. Namely, it is equivalent to “determine a direct sum partition {S
1
, . . . , S
n
} (where S
i
is a set of divisions) of a definite set of patterns W which minimizes summation of distortion (S
1
, . . . , S
n
) (where S
i
is a set of divisions) for such W”.
There are only a definite number of methods for direct sum partitioning the definite set W having M elements into N partial sets and hence it has been known that this problem can necessarily be solved by an enumeration method in principle but the number of cases (the number of combinations) of such direct sum partition is:
1
N
!
∑
k
=
1
N
(
-
1
)
N
N
-
k
C
k
K
M
(
1
)
Accordingly, in an actual problem, for example, in case of M>1,000 and N>100, it is a huge number and it is very difficult to get a solution within a practical time even if a today's fastest computer is used.
For this problem, an LBG algorithm as disclosed in the article “Algorithm for Pattern Recognition and Learning”, Bunnichi Sohgoh Shuppan, by Y. Kamisaka and K. Ozaki, p. 112~119 or various OR (operations research method) techniques have been proposed.
However, the planning method disclosed in the above reference includes at least two problems.
First, in order to determine an optimum meshing plan, a repetitive process of at least third power of the number N of elements of a problem in question is needed and it is very difficult to determine a solution at a high speed.
Secondly, there is a problem of very low probability of reaching an optimum solution.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a planning system and planning method for determining a solution which makes uniform the weights of divided sections of an assigned section divided by a given divisor, for example, areas, weights or work amounts uniform with a simple construction for a problem in the assigned section in distributing and collecting articles and visiting for various discussions.
It is another object of the present invention to provide a planning system and planning method for determining a solution which makes uniform the weights of a set of divisions of an assigned section divided by a given divisor for a problem of the assigned section with a simple construction and reaching an optimum solution.
In order to solve the above problems and achieve the objects of the present invention, the planning system of the present invention includes the following aspects.
A planning system for dividing an object continuously composed by a plurality of elements having weights by a given divisor and determining a solution, by the planning, for a problem to average total values of the weights of respective divided subsets, comprising a planning device for preparing an objective function representing items to be averaged and designing a plan to minimize the value of the objective function and a memory device for storing at least variables necessary for designing the plan.
The planning device comprises:
an objective function value operation unit for calculating an objective function value of an initial plan;
reproduction unit for generating random numbers having a range of the number of elements of a set composed by elements contacting to boundary planes of the divided subsets, said random numbers having an equally-opportunity-selectable distribution or a normal distribution, selecting at least one element based on the random numbers, equally-opportunity-selecting one of the subsets to which the element contacts and scheduling the plan such that the selected element is rendered to belong to the selected subset; and
a plan renewal unit for comparing the objective function value for the previous plan and the objective function value for the new plan and sequentially determining the plan having a smaller objective function value as an optimum plan candidate.
In accordance with another aspect of the present invention, there is provided a planning system for dividing an object continuously composed by a plurality of elements having weights by a given divisor and determining a solution, by the planning, for a problem to average total values of the weights of respective divided subsets, comprising a setting device for accepting at least the object of the problem and variables necessary for solving the problem, a planning device for preparing an objective function representing items to be averaged in said problem and designing a plan to minimize the value of the prepared objective function, a memory device for storing at least variables necessary for designing the plan and a display device for displaying a result of the planning.
The said planning device comprises:
an initial plan read unit for reading a previously prepared initial plan;
an objective function value operation unit for calculating an objective function value of an initial plan;
reproduction unit for generating random numbers having a range of the number of elements of a set composed by elements contacting to boundary planes of the divided subsets, with the random numbers having an equally-opportunity-selectable distribution or a normal distribution, selecting at least one element based on the random numbers, equal-opportunity-selecting one of the subsets to which the element contacts and scheduling the plan such that the selected element is rendered to belong to the selected subset;
a plan renewal unit for comparing the objective function value for the previous plan and the objective function value for the new plan and sequentially determining the plan having a smaller objective function value as an optimum plan candidate; and
a control unit for starting the objective function value operation unit, the plan renewal unit and said reproduction unit a predetermined number of times and displaying a final optimum plan on the display unit.
The objective function value operation unit is constructed as an unit to calculate the following formula representing a standard deviation of weights of the elements of the divided subsets as the objective function value:
∑
i
=
1
n
(
X
_
-
x
i
)
2
/
n
(
2
)
where n is a divisor, x
i
is a summation of weights of the elements of i-th divided set, and {overscore (X)} is a mean value from x
1
to x
n
.
The objective function value operation unit is preferably a unit for calculating a difference between a difference between summations of weights of at most two unaltered subsets and a difference between those of at most two altered subsets as the objective function value.
The plan renewal unit is preferably constructed to compare, when sequentially determining the optimum plan candidate, compares a difference between the objective function plans in the previo
Inoue Haruki
Mizutani Mayumi
Shiozawa Masami
Yoshikawa Satoru
Antonelli Terry Stout & Kraus LLP
Hafiz Tariq R.
Hitachi Engineering Co. Ltd.
Starks Wilbert L.
LandOfFree
Planning system and planning method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Planning system and planning method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Planning system and planning method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2596426