Method and system of automatic arrangement of composing elements
First Claim
1. A method for automatically arranging a plurality of particular electric parts of an electric device at an optimum arrangement on a printed circuit board,by using a plurality of past examples respectively indicating a past arrangement of a set of electric parts of the electric device, each past example of electric parts being composed of position information indicating positions of the set of electric parts and attribute information indicating attributes of the set of electric parts, also by using information indicative of a potential function including one or more parameters for indicating a potential energy of each electric part of the set of electric parts, the plurality of past examples and the information indicative of the potential function being stored in a storing unit, the method comprising the steps of:
- selecting a plurality of particular past examples corresponding to the plurality of particular electric parts from the past examples stored in the storing unit;
automatically determining values of the one or more parameters of the potential function according to the particular past examples for each particular electric part;
differentiating each of the potential functions to obtain a force exerted on each particular electric part to be arranged on the printed circuit board;
changing, under calculation, a position of each particular electric part to be arranged on the printed circuit board according to the force so as to decrease a total potential energy obtained by summing up the potential energies of the particular electric parts, each potential energy of one particular electric part being obtained by determining a position of the particular electric part in one potential function;
determining a particular arrangement of the particular electric parts placed at the changed positions as the optimum arrangement; and
outputting information indicating the determined optimum arrangement through an outputting device.
1 Assignment
0 Petitions
Accused Products
Abstract
past positions of a plurality of composing elements indicated by various past arrangement examples are given to each potential function corresponding to one composing element, and parameter values of the potential functions corresponding to the composing elements are automatically set on condition that a past total potential energy obtained by solving the potential functions is minimized. Thereafter, the parameter values are given to the potential functions in which a position of any composing element is not determined, and particular positions of the composing elements are determined on condition that a total potential energy obtained by solving the potential functions is minimized. Because each potential function corresponding to one composing element has an attraction term indicating the attraction between the composing element and the other composing elements and an attraction-repulsion term indicating the setting of the composing element at a position spaced at moderate distances from the other composing elements, the particular positions of the composing elements are set in an optimum arrangement. Accordingly, the optimum arrangement of the composing elements can be automatically obtained without extracting any arrangement knowledge from a skilled person.
14 Citations
60 Claims
-
1. A method for automatically arranging a plurality of particular electric parts of an electric device at an optimum arrangement on a printed circuit board,
by using a plurality of past examples respectively indicating a past arrangement of a set of electric parts of the electric device, each past example of electric parts being composed of position information indicating positions of the set of electric parts and attribute information indicating attributes of the set of electric parts, also by using information indicative of a potential function including one or more parameters for indicating a potential energy of each electric part of the set of electric parts, the plurality of past examples and the information indicative of the potential function being stored in a storing unit, the method comprising the steps of: -
selecting a plurality of particular past examples corresponding to the plurality of particular electric parts from the past examples stored in the storing unit;
automatically determining values of the one or more parameters of the potential function according to the particular past examples for each particular electric part;
differentiating each of the potential functions to obtain a force exerted on each particular electric part to be arranged on the printed circuit board;
changing, under calculation, a position of each particular electric part to be arranged on the printed circuit board according to the force so as to decrease a total potential energy obtained by summing up the potential energies of the particular electric parts, each potential energy of one particular electric part being obtained by determining a position of the particular electric part in one potential function;
determining a particular arrangement of the particular electric parts placed at the changed positions as the optimum arrangement; and
outputting information indicating the determined optimum arrangement through an outputting device. - View Dependent Claims (2, 3, 4)
determining the values of the parameters for each particular electric part on condition that a sum of a plurality of potential energies obtained by setting positions of the particular electric parts indicated by the particular past examples to the potential functions is minimized.
-
-
3. An automatic arrangement method according to claim 1 in which the step of automatically determining values of one or more parameters includes the step of:
equalizing the values of the parameters for a first particular electric part with those for a second particular electric part in cases where one attribute of the first particular electric part is the same as that of the second particular electric part.
-
4. An automatic arrangement method according to claim 1 in which the step of automatically determining values of one or more parameters includes the step of:
equalizing the values of the parameters for a first particular electric part with those for a second particular electric part in cases where one attribute of the first particular electric part is similar to that of the second particular electric part.
-
5. A method for automatically arranging a plurality of particular electric parts of an electric device at an optimum arrangement on a printed circuit board,
by using a plurality of past examples respectively indicating a past arrangement of a set of electric parts of the electronic device, each past example being composed of past position information indicating past positions of the set of electric parts, past attribute information indicating attributes of the set of electric parts and past connection information indicating a direct connection of each electric part with other electric parts or another electric part, also by using a prototype of a total potential function indicating a total potential energy of the set of electric parts, the plurality of past examples and the information indicative of the potential function being stored in a storing unit, the method comprising the steps of: -
inputting particular part information of the plurality of particular electric parts, the particular part information including particular attribute information, indicating attributes of the particular electric parts, and particular connection information, indicating a direct connection of each particular electric part with at least one other particular electric part;
selecting a plurality of particular past examples corresponding to the particular electric parts from the past examples stored in the storing unit, the particular past examples including particular past position information of the particular electric parts, particular past attribute information of the particular electric parts and particular past connection information of the particular electric parts;
producing a total past potential function corresponding to the particular electric parts from the prototype of the total potential function according to the particular past attribute information and the particular past connection information;
setting values of one or more parameters included in the total past potential function as a set of parameter values;
calculating a total past potential energy of the particular electric parts from the total past potential function by giving both of;
one set of parameter values to the total past potential function to determine an equation of the total past potential function; and
particular past positions of the particular electric parts indicated by the particular past position information to the equation of the total past potential function to solve the equation each time the set of parameter values is set while changing the parameter values;
determining a particular set of parameter values on condition that the total past potential energy calculated according to the particular set of parameter values is minimized;
producing the total potential function corresponding to the particular electric parts from the prototype of the total potential function according to the particular attribute information and the particular connection information;
giving the particular set of parameter values to the total potential function to determine a particular equation of the total potential function;
determining a particular set of positions of the particular electric parts on condition that a particular total potential energy of the particular obtained from the particular equation of the total potential function is minimized by giving the particular set of positions to the particular equation of the total potential function;
adopting a particular arrangement of the particular electric parts determined by the particular set of positions of the particular electric parts as the optimum arrangement of the particular electric parts; and
outputting the adopted optimum arrangement through an outputting device. - View Dependent Claims (6, 7, 8, 9, 10, 11, 12)
calculating the values of the parameters on condition that a past potential energy obtained by solving the total past potential function is minimized by giving the values of the parameters and past positions of the particular electric parts indicated by the particular past position information of the particular past examples to the total past potential function.
-
-
7. An automatic arrangement method according to claim 6 in which the step of producing a total past potential function comprises the steps of:
-
producing a past potential function corresponding to each particular electric part from the prototype of the total potential function according to the particular past attribute information and the particular past connection information of the particular past examples, a potential energy of each particular electric part being obtained by solving the past potential function corresponding to the particular electric part; and
summing up the past potential functions corresponding to the particular electric parts to obtain the total past potential function, and the step of calculating the values of the parameters comprises the step of;
calculating values of one or more parameters of each past potential function on condition that a sum of a plurality of past potential energies obtained by solving the past potential functions is minimized by giving the values of the parameters and past positions of the particular electric parts indicated by the particular past position information of the particular past examples to each past potential function.
-
-
8. An automatic arrangement method according to claim 5 in which the step of producing the total potential function comprises the steps of:
-
producing a potential function corresponding to each particular electric part from the prototype of the total potential function according to the particular attribute information and the particular connection information of the part information, a potential energy of each particular electric part being obtained by solving the potential function corresponding to the particular electric part; and
summing up the potential functions corresponding to the particular electric parts to obtain the total potential function, and the step of setting values of one or more parameters comprises the steps of;
classifying the potential functions into a plurality of groups of potential functions, a plurality of particular electric parts corresponding to a plurality of potential functions in the same group having the same attribute indicated by the particular attribute information of the particular electric parts; and
setting values of one or more parameters used in each potential function on condition that the parameter values of one potential function of one group are the same as those of another potential function of the same group.
-
-
9. An automatic arrangement method according to claim 5 in which the step of producing the total potential function comprises the steps of:
-
producing a potential function corresponding to each particular electric part from the prototype of the total potential function according to the particular attribute information and the particular connection information of the part information, a potential energy of each particular electric part being obtained by solving the potential function corresponding to the particular electric part; and
summing up the potential functions corresponding to the particular electric parts to obtain the total potential function, and the step of setting values of one or more parameters comprises the steps of;
classifying the potential functions into a plurality of groups of potential functions, a plurality of particular electric parts corresponding to a plurality of potential functions in the same group having a plurality of attributes indicated by the particular attribute information of the particular electric parts, the attributes of the potential functions being similar to each other; and
setting values of one or more parameters used in each potential function on condition that the parameter values of one potential function of one group are the same as those of another potential function of the same group.
-
-
10. An automatic arrangement method according to claim 5 in which the step of determining a particular set of positions comprises the steps of:
-
setting a position Ri(t−
Δ
t) of each particular electric part at a time t−
Δ
t, the symbol Δ
t denoting a minute time;
setting a position Ri(t) of each particular electric part at a time t;
giving the positions Ri(t) of the particular electric parts to the particular equation of the total potential function;
solving the particular equation of the total potential function to calculate a potential energy Ei(t) of each particular electric part at a time t;
calculating a position Ri(t+Δ
t) of each particular electric part at a time t+Δ
t according to an equation
Ri(t+Δ
t)=2*Ri(t)−
Ri(t−
Δ
t)−
1/m*□
iEtot*(Δ
t)2,the symbol □
i denoting a nabla, and the symbol Etot denoting a total energy of the particular electric parts; and
repeating the calculation of the positions of the particular electric parts to obtain the particular set of positions Ri(T) at a particular time T, a value of □
iEtot being almost zero.
-
-
11. An automatic arrangement method according to claim 10 in which the particular part information includes initial position information indicating a plurality of initial positions Ri(0), Ri(−
- Δ
t) of the particular electric parts.
- Δ
-
12. An automatic arrangement method according to claim 5 in which the step of using a prototype of a total potential function comprises the steps of:
-
adding an attraction term to the prototype of the total potential function to express an attraction between one electric part E1 and the other electric parts E2 for each electric part E1, the total potential energy of the electric parts indicated by the attraction term decreasing as each of the electric parts E2 becomes close to the electric part E1; and
adding a repulsion-attraction term to the prototype of the total potential function to express a repulsion between each electric part E1 and the other electric parts E2 not to overlap the electric part E1 with the electric parts E2 and an attraction between each electric part E1 and the other electric parts E2 not to arrange the electric parts E2 far from the electric part E1, the total potential energy of the electric parts indicated by the repulsion-attraction term decreasing as the electric parts E2 approach positions spaced at moderate distances from the electric part E1.
-
-
13. An automatic arrangement system for automatically arranging a plurality of particular electric parts of an electric device at an optimum arrangement on a printed circuit board, the system comprising:
-
past example storing means for storing a plurality of past examples respectively indicating a past arrangement of a set of electric parts of the electric device, each past example being composed of past position information indicating past positions of the set of electric parts, past attribute information indicating attributes of the set of electric parts and past connection information indicating a direct connection of each electric part with other electric parts or another electric part;
total potential function storing means for storing a prototype of a total potential function indicating a total potential energy of the set of electric parts;
element information receiving means for receiving particular part information of the plurality of particular electric parts, the particular part information being composed of particular attribute information indicating attributes of the particular electric parts and particular connection information indicating a direct connection of each particular electric part with other particular electric parts or another particular electric part;
past example selecting means for selecting a plurality of particular past examples corresponding to the particular electric parts from the past examples, the particular past examples being composed of particular past position information of the particular electric parts, particular past attribute information of the particular electric parts and particular past connection information of the particular electric parts;
parameter value determining means for producing a total past potential function corresponding to the particular electric parts from the prototype of the total potential function according to the particular past attribute information and the particular past connection information of the particular past examples, setting values of one or more parameters included in the total past potential function as a set of parameter values each time the parameter values are changed, determining an equation of the total past potential function by giving one set of parameter values to the total past potential function, calculating a total past potential energy of the particular electric parts from the equation of the total past potential function by giving particular past positions of the particular electric parts indicated by the particular past position information to the equation of the total past potential function each time the parameter values are changed, and determining a particular set of parameter values on condition that the total past potential energy calculated according to the particular set of parameter values is minimized; and
optimum arrangement determining means for producing the total potential function corresponding to the particular electric parts from the prototype of the total potential function according to the particular attribute information and the particular connection information of the particular part information, giving the particular set of parameter values to the total potential function to determine a particular equation of the total potential function, determining a particular set of positions of the particular electric parts on condition that a particular total potential energy of the particular electric parts obtained from the particular equation of the total potential function is minimized by giving the particular set of positions to the particular equation of the total potential function, adopting a particular arrangement of the particular electric parts determined by the particular set of positions of the particular electric parts as the optimum arrangement of the particular electric parts, and outputting the adopted optimum arrangement through an outputting device. - View Dependent Claims (14, 15, 16)
parameter value setting means for calculating the values of the parameters on condition that a past potential energy obtained by solving the total past potential function is minimized by giving the values of the parameters and past positions of the particular electric parts indicated by the particular past position information of the particular past examples to the total past potential function.
-
-
15. An automatic arrangement system according to claim 13 in which the parameter value determining means includes:
parameter value setting means for producing a past potential function corresponding to each particular electric part from the prototype of the total potential function according to the particular past attribute information and the particular past connection information of the particular past examples and setting values of one or more parameters used in one past potential function for each particular electric part, a particular set of parameter values being determined by the parameter value determining means for each particular electric part on condition that a sum of a plurality of past potential energies obtained by solving the past potential functions is minimized in cases where the particular set of parameter values and past positions of the particular electric parts indicated by the particular past position information of the particular past examples are given to each past potential function.
-
16. An automatic arrangement system according to claim 13 in which the prototype of the total potential function stored in the total potential function storing means has an attraction term and a repulsion-attraction term, an attraction between one electric part E1 and the other electric parts E2 being expressed by the attraction term for each electric part E1, the total potential energy of the electric parts indicated by the attraction term decreasing as each of the electric parts E2 becomes close to the electric part E1, a repulsion between each electric part E1 and the other electric parts E2 not to overlap the electric part E1 with the electric parts E2 and an attraction between each electric part E1 and the other electric parts E2 not to arrange the electric parts E2 far from the electric part E1 being expressed by the repulsion-attraction term, and the total potential energy of the electric parts indicated by the repulsion-attraction term decreasing as the electric parts E2 approach positions spaced at moderate distances from the electric part E1.
-
17. A recording medium for recording a method for controlling a computer to implement a sequence of steps of a software program for automatically arranging a plurality of electric parts of an electric device in an optimum arrangement on a printed circuit board, the sequence of steps comprising:
-
automatically determining values of one or more parameters included in a potential function according to a past arrangement example for each electric part, the parameters indicating a potential energy of each electric part to be arranged on the printed circuit board;
differentiating each potential function to obtain a force exerted on each electric part to be arranged on the printed circuit board;
changing a position of each electric part to be arranged on the printed circuit board according to the force so as to decrease a total potential energy of the electric parts; and
determining a particular arrangement of the electric parts placed at the changed positions as the optimum arrangement.
-
-
18. A method for automatically arranging a plurality of electric parts providing circuitry of an electric device at an optimum arrangement on a printed circuit board, comprising the steps of:
-
determining an arranging order of the plurality of electric parts in a first classifier system according to attributes of the electric parts and one or more connection conditions among the electric parts;
determining an arranging position determining method for each electric part in the arranging order in a second classifier system according to the attributes and the connection conditions;
determining an arranged position of each electric part in an arrangement area or an area surrounding the arrangement area on the printed circuit board according to the arranging position determining method determined for each electric part in the arranging order;
judging in a third classifier system whether or not the change of the arranged position of each electric part is required according to the attributes and the arranged positions of the electric parts and the connection conditions among the electric parts in the arranging order;
detecting a position changing method for one electric part in the third classifier system in cases where it is judged that the change of the arranged position of each electric part is required;
changing the arranged position of one electric part according to the position changing method for each electric part, in cases where it is judged that the change of the arranged position is required, to determine the arranged positions of the electric parts as the optimum arrangement in the arrangement area; and
outputting information indicting the determined optimum arrangement through an outputting device. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40)
setting one or more attributes in a condition part of the first classifier system as a first condition rule of a first rule for each first rule;
setting an arrangement priority degree in an action part of the first classifier system as a first action rule of one first rule for each first rule;
activating one first rule corresponding to one first condition rule, in which the attributes agreeing with those of one electric part are set, for each electric part;
detecting one arrangement priority degree set in the first action rule of the activated first rule for each electric part; and
determining the arranging order of the electric parts according to the arrangement priority degrees of the electric parts.
-
-
20. An automatic arrangement method according to claim 19 in which the step of determining an arranging order further includes the step of:
changing each of the first rules respectively composed of one first condition rule and one first action rule in the first classifier system according to a genetic algorithm.
-
21. An automatic arrangement method according to claim 19 in which the step of determining an arranging order further includes the steps of:
-
producing an initial condition rule and an initial action rule of each first rule according to past arrangement examples of the electric parts;
setting the initial condition rule as one first condition rule of one first rule for each first rule;
setting the initial action rule as one first action rule of one first rule for each first rule; and
changing each of the first rules in the first classifier system according to a genetic algorithm.
-
-
22. An automatic arrangement method according to claim 18 in which the step of determining an arranging position determining method includes the steps of:
-
setting one or more attributes in a condition part of the second classifier system as a second condition rule of a second rule for each second rule;
setting one arranging position determining method in an action part of the second classifier system as a second action rule of one second rule for each second rule;
activating one second rule corresponding to one second condition rule, in which the attributes agreeing with those of one electric part are set, for each electric part; and
detecting one arranging position determining method set in the second action rule of the activated second rule for each electric part.
-
-
23. An automatic arrangement method according to claim 22 in which the step of determining an arranging position determining method further includes the step of:
changing each of the second rules respectively composed of one second condition rule and one second action rule in the second classifier system according to a genetic algorithm.
-
24. An automatic arrangement method according to claim 22 in which the step of determining an arranging position determining method further includes the steps of:
-
producing an initial condition rule and an initial action rule of each second rule according to past arrangement examples of the electric parts;
setting the initial condition rule as one second condition rule of one second rule for each second rule;
setting the initial action rule as one second action rule of one second rule for each second rule; and
changing each of the second rules in the second classifier system according to a genetic algorithm.
-
-
25. An automatic arrangement method according to claim 18 in which the step of judging in a third classifier system includes the steps of:
-
setting an arrangement condition in a condition part of the third classifier system as a third condition rule of a third rule for each third rule;
setting one judgement about a position change and one position changing method in an action part of the third classifier system as a third action rule of one third rule for each third rule;
preparing a particular arrangement condition of one electric part according to the attributes and arranged position of the electric part and the arrangement area for each electric part;
activating one third rule corresponding to one third condition rule, in which the arrangement condition agreeing with one particular arrangement condition of one electric part is set, for each electric part; and
detecting one judgement about a position change and one position changing method set in the third action rule of the activated third rule for each electric part.
-
-
26. An automatic arrangement method according to claim 25 in which the step of judging in a third classifier system further includes the step of:
changing each of the third rules respectively composed of one third condition rule and one third action rule in the third classifier system according to a genetic algorithm.
-
27. An automatic arrangement method according to claim 25 in which the step of judging in a third classifier system further includes the steps of:
-
producing an initial condition rule and an initial action rule of each third rule according to past arrangement examples of the electric parts;
setting the initial condition rule as one third condition rule of one third rule for each third rule;
setting the initial action rule as one third action rule of one third rule for each third rule; and
changing each of the third rules in the third classifier system according to a genetic algorithm.
-
-
28. An automatic arrangement method according to claim 18 in which the step of determining an arranging order includes the steps of:
-
setting one or more attributes in a condition part of the first classifier system as a first condition rule of a first rule for each first rule;
setting an arrangement priority degree in an action part of the first classifier system as a first action rule of one first rule for each first rule;
setting a fitness value to each first rule of the first classifier system;
activating one or more first rules corresponding to one or more first condition rules, in which the attributes agreeing with those of one electric part are set, for each electric part;
selecting a particular first rule from the activated first rules at a selection probability proportional to the fitness value of the particular first rule for each electric part;
detecting one arrangement priority degree set in the first action rule of the particular first rule for each electric part; and
determining the arranging order of the electric parts according to the arrangement priority degrees of the electric parts.
-
-
29. An automatic arrangement method according to claim 28 in which the step of determining an arranging order further includes the step of:
adjusting each of the fitness values set to the first rules in the first classifier system according to a reinforcement learning.
-
30. An automatic arrangement method according to claim 28 in which the step of determining an arranging order includes the steps of:
-
producing an initial fitness value of each first rule according to past arrangement examples of the electric parts;
setting the initial fitness value as one fitness value of one first rule for each first rule; and
adjusting each of the fitness values in the first classifier system according to a reinforcement learning.
-
-
31. An automatic arrangement method according to claim 28 in which the step of determining an arranging order further includes the steps of:
-
changing each of the first rules respectively composed of one first condition rule and one first action rule in the first classifier system according to a genetic algorithm; and
adjusting each of the fitness values set to the first rules in the first classifier system according to a reinforcement learning.
-
-
32. An automatic arrangement method according to claim 18 in which the step of determining an arranging position determining method includes the steps of:
-
setting one or more attributes in a condition part of the second classifier system as a second condition rule of a second rule for each second rule;
setting one arranging position determining method in an action part of the second classifier system as a second action rule of one second rule for each second rule;
setting a fitness value to each second rule of the second classifier system;
activating one or more second rules corresponding to one or more second condition rules, in which the attributes agreeing with those of one electric part are set, for each electric part;
selecting a particular second rule from the activated second rules at a selection probability proportional to the fitness value of the particular second rule for each electric part; and
detecting one arranging position determining method set in the second action rule of the particular second rule for each electric part.
-
-
33. An automatic arrangement method according to claim 32 in which the step of determining an arranging position determining method further includes the steps of:
-
producing an initial fitness value of each second rule according to past arrangement examples of the electric parts;
setting the initial fitness value as one fitness value of one second rule for each second rule; and
adjusting each of the fitness values in the second classifier system according to a reinforcement learning.
-
-
34. An automatic arrangement method according to claim 32 in which the step of determining an arranging position determining method further includes the step of:
adjusting each of the fitness values set to the second rules in the second classifier system according to a reinforcement learning.
-
35. An automatic arrangement method according to claim 32 in which the step of determining an arranging position determining method further includes the steps of:
changing each of the second rules respectively composed of one second condition rule and one second action rule in the second classifier system according to a genetic algorithm; and
adjusting each of the fitness values set to the second rules in the second classifier system according to a reinforcement learning.
-
36. An automatic arrangement method according to claim 18 in which the step of judging in a third classifier system includes the steps of:
-
setting an arrangement condition in a condition part of the third classifier system as a third condition rule of a third rule for each third rule;
setting one judgement about a position change and one position changing method in an action part of the third classifier system as a third action rule of one third rule for each third rule;
setting a fitness value to each third rule of the third classifier system;
preparing a particular arrangement condition of one electric part according to the attributes and arranged position of the electric part and the arrangement area for each electric part;
activating one or more third rules corresponding to one or more third condition rules, in which the arrangement condition agreeing with one particular arrangement condition of one electric part is set, for each electric part;
selecting a particular third rule from the activated third rules at a selection probability proportional to the fitness value of the particular third rule for each electric part; and
detecting one judgement about a position change and one position changing method set in the third action rule of the particular third rule for each electric part.
-
-
37. An automatic arrangement method according to claim 36 in which the step of judging in a third classifier system includes the steps of:
-
producing an initial fitness value of each third rule according to past arrangement examples of the electric parts;
setting the initial fitness value as one fitness value of one third rule for each third rule; and
adjusting each of the fitness values in the third classifier system according to a reinforcement learning.
-
-
38. An automatic arrangement method according to claim 36 in which the step of judging in a third classifier system further includes the step of:
adjusting each of the fitness values set to the third rules in the third classifier system according to a reinforcement learning.
-
39. An automatic arrangement method according to claim 36 in which the step of judging in a third classifier system further includes the steps of:
-
changing each of the third rules respectively composed of one third condition rule and one third action rule in the third classifier system according to a genetic algorithm; and
adjusting each of the fitness values set to the third rules in the third classifier system according to a reinforcement learning.
-
-
40. An automatic arrangement method according to claim 18 in which the step of changing the arranged position includes the steps of:
-
producing an evaluation value according to the arranged positions of the electric parts and the arrangement area;
judging that the arranged positions of the electric parts are set in an optimum arrangement in cases where the evaluation value is equal to or lower than a reference value;
judging that the arranged positions of the electric parts are not set in an optimum arrangement in cases where the evaluation value is higher than the reference value;
revising the first, second and third classifying systems according to a genetic algorithm or a reinforcement learning to produce a revised evaluation value equal to or lower than the reference value.
-
-
41. An automatic arrangement system for automatically arranging a plurality of electric parts providing circuitry of an electric device at an optimum arrangement on a printed circuit board, the system comprising:
-
element information receiving means for receiving element information indicating the plurality of electric parts;
electric part storing means for storing one or more attributes of each electric part received by the element information receiving means;
electric part arranging order determining means, having a first classifier system, for determining an arranging order of the received electric parts in the first classifier system according to the attributes of the electric parts;
arranging position determining means, having a second classifier system, for determining an arranging position determining method for each electric part in the arranging order of the electric parts in the second classifier system according to the attributes and determining an arranged position of each electric part in an arrangement area or an area surrounding the arrangement area on the printed circuit board according to the arranging position determining method;
arranged position change judging means, having a third classifier system, for judging in the third classifier system whether or not the change of the arranged position of each electric part is required according to the attributes and the arranged positions of the electric parts and producing a position changing method for one electric part in the third classifier system in cases where it is judged that the change of the arranged position of each electric part is required;
electric part arranging means for changing the arranged position of one electric part according to the position changing method, in cases where it is judged in the third classifier system that the change of the arranged position of each electric part is required, to determine the arranged positions of the electric parts as the optimum arrangement in the arrangement area; and
outputting means for outputting information indicating the determined optimum arrangement through an outputting device. - View Dependent Claims (42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57)
a first condition rule for indicating a group of one or more attributes of the electric part, a plurality of particular first rules of a plurality of particular first condition rules, which indicate a plurality of groups of attributes of the electric parts received by the part information receiving means, being activated; and
a first action rule for indicating an arrangement priority degree of the electric part, the arranging order of the electric parts being determined according to the arrangement priority degrees indicated by a plurality of particular first action rules of the particular first rules.
-
-
43. An automatic arrangement system according to claim 42, further comprising:
first learning means for performing the learning of the first classifier system to change each of the first rules according to a genetic algorithm.
-
44. An automatic arrangement system according to claim 42, further comprising:
-
initial rule producing means for producing an initial condition rule and an initial action rule of each first rule according to past arrangement examples of the electric parts, setting the initial condition rule as one first condition rule of one first rule for each first rule, setting the initial action rule as one first action rule of one first rule for each first rule; and
learning means for performing the learning of the first classifier system to change each of the first rules in the first classifier system according to a genetic algorithm.
-
-
45. An automatic arrangement system according to claim 41 in which the second classifier system of the arranging position determining means comprises a plurality of second rules respectively corresponding to one electric part, wherein each second rule of one electric part comprises:
-
a second condition rule for indicating a group of one or more attributes of the electric part, a particular second rule of a particular second condition rule, which indicates a particular group of attributes of one electric part, being activated for each electric part in the arranging order of the electric parts; and
a second action rule for indicating one arranging position determining method applied for the electric part, the arranging position determining method indicated by a particular second action rule of one activated particular second rule being determined for each electric part in the arranging order of the electric parts.
-
-
46. An automatic arrangement system according to claim 45, further comprising:
learning means for performing the learning of the second classifier system to change each of the second rules according to a genetic algorithm.
-
47. An automatic arrangement system according to claim 45, further comprising:
-
initial rule producing means for producing an initial condition rule and an initial action rule of each second rule according to past arrangement examples of the electric parts, setting the initial condition rule as one second condition rule of one second rule for each second rule, setting the initial action rule as one second action rule of one second rule for each second rule; and
learning means for performing the learning of the second classifier system to change each of the second rules in the second classifier system according to a genetic algorithm.
-
-
48. An automatic arrangement system according to claim 41 in which the third classifier system of the arranged position change judging means comprises a plurality of third rules respectively corresponding to one electric part, wherein each third rule of one electric part comprises:
-
a third condition rule for indicating an arrangement condition of the electric part, a particular third rule of a particular third condition rule, which indicates a particular arrangement condition of one electric part, being activated for each electric part in the arranging order of the electric parts; and
a third action rule for indicating one judgement about a position change and one position changing method applied for the electric part, a position change of one electric part being judged according to the judgement about a position change indicated by a particular third action rule of one activated particular third rule, and the position changing method indicated by the particular third action rule being produced for each electric part in the arranging order of the electric parts.
-
-
49. An automatic arrangement system according to claim 48, further comprising:
learning means for performing the learning of the third classifier system to change each of the third rules according to a genetic algorithm.
-
50. An automatic arrangement system according to claim 48, further comprising:
-
initial rule producing means for producing an initial condition rule and an initial action rule of each third rule according to past arrangement examples of the electric parts, setting the initial condition rule as one third condition rule of one third rule for each third rule, setting the initial action rule as one third action rule of one third rule for each third rule; and
learning means for performing the learning of the third classifier system to change each of the third rules in the third classifier system according to a genetic algorithm.
-
-
51. An automatic arrangement system according to claim 41, further comprising:
-
evaluation value calculating means for calculating an evaluation value from the arranged positions of the electric parts determined by the electric part arranging means and the arrangement area;
control means for judging whether or not the learning of the first, second and third classifier systems is required according to the evaluation value calculated by the evaluation value calculating means; and
learning means for revising the first, second and third classifier systems according to a genetic algorithm or a reinforcement learning.
-
-
52. An automatic arrangement system according to claim 41 in which the first classifier system of the electric part arranging order determining means comprises a plurality of first rules respectively corresponding to one electric part, wherein each first rule of one electric part comprises:
-
a first condition rule for indicating a group of one or more attributes of the electric part, one or more first rules of one or more first condition rules, which indicate the same group of attributes of each electric part received by the part information receiving means, being activated;
a first action rule for indicating an arrangement priority degree of the electric part, one or more arrangement priority degrees of one or more first action rules of the activated first rules being selected for each electric part; and
a fitness value for indicating the fitness of the electric part, a particular first rule being selected from the activated first rules at a selection probability proportional to the fitness value of the particular first rule for each electric part, and the arranging order of the electric parts being determined according to the arrangement priority degrees indicated by a plurality of particular first action rules of the particular first rules.
-
-
53. An automatic arrangement system according to claim 52 further comprising:
first learning means for performing the learning of the first classifier system to adjust each of the fitness values of the first rules according to a reinforcement learning.
-
54. An automatic arrangement system according to claim 41 in which the second classifier system of the arranging position determining means comprises a plurality of second rules respectively corresponding to one electric part, wherein each second rule of one electric part comprises:
-
a second condition rule for indicating a group of one or more attributes of the electric part, one or more second rules of one or more second condition rules, which indicate the same particular group of attributes of one electric part, being activated for each electric part in the arranging order of the electric parts;
a second action rule for indicating one arranging position determining method applied for the electric part; and
a fitness value for indicating the fitness of the electric part, a particular second rule being selected from the activated second rules at a selection probability proportional to the fitness value of the particular second rule for each electric part, and the arranging position determining method indicated by a particular second action rule of the particular second rule being determined for each electric part in the arranging order of the electric parts.
-
-
55. An automatic arrangement system according to claim 54 further comprising:
second learning means for performing the learning of the second classifier system to adjust each of the fitness values of the second rules according to a reinforcement learning.
-
56. An automatic arrangement system according to claim 41 in which the third classifier system of the arranged position change judging means comprises a plurality of third rules respectively corresponding to one electric part, wherein each third rule of one electric part comprises:
-
a third condition rule for indicating an arrangement condition of the electric part, one or more third rules of one or more third condition rules, which indicate the same particular arrangement condition of one electric part, being activated for each electric part in the arranging order of the electric parts; and
a third action rule for indicating one judgement about a position change and one position changing method applied for the electric part; and
a fitness value for indicating the fitness of the electric part, a particular third rule being selected from the activated third rules at a selection probability proportional to the fitness value of the particular third rule for each electric part, a position change of one electric part being judged according to the judgement about a position change indicated by a particular third action rule of the activated particular third rule, and the position changing method indicated by the particular third action rule being produced for each electric part in the arranging order of the electric parts.
-
-
57. An automatic arrangement system according to claim 56 further comprising:
- learning means for performing the learning of the third classifier system to adjust each of the fitness values of the third rules according to a reinforcement learning.
-
58. A recording medium for recording a method for controlling a computer to implement a sequence of steps of a software program for automatically arranging a plurality of electric parts of an electric device in an optimum arrangement on a printed circuit board, the sequence of steps comprising:
-
determining an arranging order of the plurality of electric parts in a first classifier system according to attributes of the electric pars and one or more connection conditions among the electric parts;
determining an arranging position determining method for each electric part in the arranging order in a second classifier system according to the attributes and the connection conditions;
determining an arranged position of each electric part in an arrangement area or an area surrounding the arrangement area on the printed circuit board according to the arranging position determining method determined for each electric part in the arranging order;
judging in a third classifier system whether or not the change of the arranged position of each electric part is required according to the attributes and the arranged positions of the electric parts and the connection conditions among the electric parts in the arranging order;
detecting a position changing method for one electric part in the third classifier system in cases where it is judged that the change of the arranged position of each electric part is required; and
changing the arranged position of one electric part according to the position changing method for each electric part, in cases where it is judged that the change of the arranged position is required, to determine the arranged positions of the electric parts as the optimum arrangement in the arrangement area.
-
-
59. A method for automatically arranging a plurality of particular composing elements at an optimum arrangement in an enclosed field, comprising the steps of:
-
preparing a plurality of past examples in a storing unit, the 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 set of composing elements and attribute information indicating attributes of the set of composing elements;
also preparing in the storing unit information indicative of a potential function including one or more parameters for indicating a potential energy of each composing element of the set of composing elements;
selecting a plurality of particular past examples corresponding to a plurality of particular composing elements from the past examples stored in the storing unit;
automatically determining values of the one or more parameters of 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 to be arranged in the enclosed field;
changing, under calculation, a position of each particular composing element to be arranged in the enclosed field according to the force so as 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;
determining a particular arrangement of the particular composing elements placed at the changed positions as the optimum arrangement; and
outputting the determined optimum arrangement through an outputting device.
-
-
60. A method for automatically arranging a plurality of particular composing elements at an optimum arrangement in an enclosed field, comprising the steps of:
-
preparing a plurality of past examples in a storing unit, the past examples respectively indicating a past arrangement of a set of composing elements, each past example being composed of past position information indicating past positions of the set of composing elements, past attribute information indicating attributes of the set of composing elements and past connection information indicating a direct connection of each composing element with other composing elements or another composing element;
also preparing in the storing unit a prototype of a total potential function indicating a total potential energy of the set of composing elements;
inputting particular element information of the plurality of particular composing elements, the particular element information including particular attribute information, indicating attributes of the particular composing elements, and particular connection information, indicating a direct connection of each particular composing element with at least one other particular composing element;
selecting a plurality of particular past examples corresponding to the particular composing elements from the past examples stored in the storing unit, the particular past examples including particular past position information of the particular composing elements, particular past attribute information of the particular composing elements and particular past connection information of the particular composing elements;
producing a total past potential function corresponding to the particular composing elements from the prototype of the total potential function according to the particular past attribute information and the particular past connection information;
setting values of one or more parameters included in the total past potential function as a set of parameter values;
calculating a total past potential energy of the particular composing elements from the total past potential function by giving both of;
one set of parameter values to the total past potential function to determine an equation of the total past potential function; and
particular past positions of the particular composing elements indicated by the particular past position information to the equation of the total past potential function to solve the equation each time the set of parameter values is set while changing the parameter values;
determining a particular set of parameter values on condition that the total past potential energy calculated according to the particular set of parameter values is minimized;
producing the total potential function corresponding to the particular composing elements from the prototype of the total potential function according to the particular attribute information and the particular connection information;
giving the particular set of parameter values to the total potential function to determine a particular equation of the total potential function;
determining a particular set of positions of the particular composing elements on condition that a particular total potential energy of the particular composing elements obtained from the particular equation of the total potential function is minimized by giving the particular set of positions to the particular equation of the total potential function;
adopting a particular arrangement of the particular composing elements determined by the particular set of positions of the particular composing elements as the optimum arrangement of the particular composing elements; and
outputting the adopted optimum arrangement through an outputting device.
-
Specification