Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
1998-07-30
2002-01-01
Teska, Kevin J. (Department: 2122)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
C706S012000
Reexamination Certificate
active
06336107
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an automatic arrangement method and an automatic arrangement system in which arrangement knowledge of a plurality of composing elements is automatically obtained from past arrangement examples of the composing elements to determine an optimum (or appropriate) arrangement of the composing elements according to the arrangement knowledge of the composing elements. Also, the present invention relates to a recording medium in which a computer program indicating an automatic arrangement of a plurality of composing elements is recorded to perform the automatic arrangement of the composing elements in a computer.
2. Description of the Related Art
In cases where the number of composing elements is small and restriction for the composing elements is simple, the automatic arrangement of the composing elements can be easily performed. However, in cases where the number of composing elements is large and restriction for the composing elements is complicated, because it is difficult to automatically arrange the composing elements in an appropriate arrangement, the composing elements are manually arranged by a skilled person. As an example of the arrangement of composing elements, the arrangement of composing parts on a printed circuit board (PCB) is known. In this arrangement, an automatic parts arrangement system is used for the composing parts. However, because it is difficult to appropriately arrange the composing parts, the composing parts are manually arranged by a skilled person.
2.1. PREVIOUSLY PROPOSED ART
As an example of the automatic parts arrangement system, an automatic parts arrangement system (H. Yoshimura, S. Miura “Approach from Artificial Intelligence to CAD of the PCB Design” the 10th Annual Conference of JSAI, 1996) is known. In this system, knowledge of composing parts arrangement is extracted from a skilled person by interviewing with the skilled person, the extracted knowledge is reflected on the automatic parts arrangement system, and a plurality of composing parts are automatically arranged on a PCB.
Also, a published unexamined Japanese Patent Application No. H5-342290 “METHOD AND DEVICE FOR ARRANGING ELEMENTS” is disclosed. In this application, attraction and repulsion occurring between elements are calculated, and the position of each element is changed for each minute time according to a sum of the attraction and the repulsion.
2.2. PROBLEMS TO BE SOLVED BY THE INVENTION
However, even though a plurality of composing parts are automatically arranged on a PCB while reflecting knowledge extracted from a skilled person on the automatic parts arrangement system, there is a problem that the arrangement of the composing parts satisfying the skilled person cannot be always obtained. That is, the skilled person has knowledge unconsciously used as well as knowledge consciously used, the knowledge consciously used cannot be extracted by interviewing with the skilled person, so that the knowledge extracted from the skilled person are not sufficient to appropriately arrange the composing parts on the PCB. In particular, because a density of wirings on the PCB and a density of parts attached on the printing substrate have been recently heightened, there is little space between the composing parts on the PCB, it is required that the skilled person performs the trial and error operation many times to appropriately arrange the composing parts on the PCB. Therefore, the knowledge of the skilled person has been more complicated, so that the extraction of the knowledge from the skilled person becomes more difficult. As a result, the composing parts cannot be appropriately arranged on the PCB in a conventional automatic arrangement system according to a conventional automatic arrangement method performed by extracting the knowledge of the parts arrangement from the skilled person.
Also, in cases where elements are arranged according to the method and device for arranging elements disclosed in the published unexamined Japanese Patent Application No. H5-342290, it is required that a function for calculating the attraction and repulsion is prepared in advance, so that there is a problem that a technical knowledge is required for an element arrangement designer to determine the function.
SUMMARY OF THE INVENTION
An object of the present invention is to provide, with due consideration to the drawbacks of such a conventional automatic arrangement method and a conventional automatic arrangement system, an automatic arrangement method and an automatic arrangement system in which positions of a plurality of composing elements are automatically set in an optimum (or appropriate) arrangement without extracting knowledge of element arrangement from a skilled person.
Also, the object is to provide a recording medium for recording a computer program indicating the automatic arrangement method.
The object is achieved by the provision of an automatic arrangement method, comprising the steps of:
preparing a plurality of past examples respectively indicating a past arrangement of a set of composing elements, each past example of composing elements being composed of position information indicating positions of the composing elements and attribute information indicating attributes of the composing elements;
preparing a potential function indicating a potential energy of one composing element;
selecting a plurality of particular past examples corresponding to a plurality of particular composing elements from the past examples;
automatically determining values of one or more parameters included in the potential function according to the particular past examples for each particular composing element;
differentiating each of the potential functions to obtain a force exerted on each particular composing element;
changing a position of each particular composing element according to the force to decrease a total potential energy obtained by summing up the potential energies of the particular composing elements, each potential energy of one particular composing element being obtained by determining a position of the particular composing element in one potential function; and
setting a particular arrangement of the composing elements placed at the changed positions.
In the above steps, in cases where a plurality of particular composing elements are arranged to minimize a sum of a plurality of potential energies obtained by solving a plurality of potential functions corresponding to the particular composing elements, positions of the particular composing elements are set in an optimum (or appropriate) arrangement. Because parameters included in each potential function are automatically determined according to the particular past examples, it is not required to extract knowledge of element arrangement from a skilled person for the purpose of setting the particular composing elements in an optimum arrangement.
Also, because a force exerted on each particular composing element is obtained by differentiating each potential function and a position of each particular composing element is changed according to the force to decrease the sum of the potential energies, the positions of the particular composing elements can be set in an optimum arrangement.
The object is also achieved by the provision of an automatic arrangement method, comprising the steps of:
preparing a plurality of past examples respectively indicating a past arrangement of a set of composing elements, each past example of one set of composing elements being composed of past position information indicating past positions of the composing elements, past attribute information indicating attributes of the composing elements and past connection information indicating a direct connection of each composing element with other composing elements or another composing element;
preparing a prototype of a total potential function indicating a total potential energy of a plurality of composing elements in a potential field made by the composing elements;
inputting particular elem
Oka Natsuki
Uchida Tomohiro
Yoshimura Hiroyuki
Israel Gopstein Clark & Brody
Matsushita Electric Industrial Co. LTD
Starks, Jr. Wilbert L.
Teska Kevin J.
LandOfFree
Method and system of automatic arrangement of composing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system of automatic arrangement of composing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system of automatic arrangement of composing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2840630