JP2004355220A - Search time shortening system, search time shortening method, and program thereof - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To provide an optimum solution search time shortening system, the search time shortening method, and a program thereof at the genetic algorithm that the processing time to obtain an optimum solution is short, while maintaining equal accuracy to the traditional genetic algorithm, using the method that at the initial generation the genetic operation is began with a part of the individual numbers and from the halfway generation the remainder of individuals is invested additionally. <P>SOLUTION: The system is a search time shortening system performing a solution of optimization problem by combining an evaluation means which evaluates individuals based on the genetic algorithm and a genes operation means which performs a genetic operation to individuals. The system is provided with an input means inputting the number of the individuals whose genetic operation is executed from the initial generation, the number of all generations with which the genetic operation is executed, the number of individuals added from the halfway generation, and the number of generations in which the individuals are added. The evaluation means takes out the specified number of individuals, that is, the initial individual numbers as the object of the genetic operation, and begins application of the genetic algorithm to them; and while performing counting of generation number every time the genetic operation is executed by the genes operation means, performs the evaluation of genetically operated individuals. <P>COPYRIGHT: (C)2005,JPO&NCIPI

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a combinatorial optimization problem using a genetic algorithm.In particular, in the early generations, the genetic algorithm is applied to a part of individuals, and the conventional genetics are introduced by inputting the remaining individuals from intermediate generations. TECHNICAL FIELD The present invention relates to a system for shortening the search time for an optimal solution in a genetic algorithm, which has the same accuracy as a genetic algorithm, but has a short processing time until an optimal solution is obtained, a search time reducing method, and a program therefor.
[0002]
[Prior art]
In the combinatorial optimization problem, as one of the methods for obtaining an optimal solution in a relatively short time, a calculation method and a genetic algorithm using the evolutionary process of a living organism as a model are often used.
[0003]
Genetic algorithms represent a combination of elements that make up an individual as a gene, and repeat one or more genetic operations (selection / selection, crossover, mutation, individual generation) on the individual with that gene to create one or more optimal This is a method for searching for a solution.
[0004]
The selection / selection of genetic operations determines what individuals will be left in the next generation and what type of individuals will be eliminated. However, there are methods such as leaving individuals with the highest evaluation value, leaving individuals selected at random, and combining a plurality of methods.
[0005]
In the crossover, two individuals are selected, and elements (genes) constituting the individuals are switched at random positions.
[0006]
Mutation is performed by performing an operation such as exchanging two randomly selected genes in one individual, and performing a conversion that cannot be performed by crossover.
[0007]
In the individual generation, an individual that has undergone selection / selection, crossover, and mutation is generated as the next generation.
[0008]
In this way, a plurality of generations are performed on an individual targeted for genetic manipulation.
[0009]
For each individual operated as described above, the state of adaptation to the environment is evaluated, and an evaluation value is set for each individual. This is repeatedly executed until the specified number of generations or the specified evaluation value (threshold) is reached.
[0010]
As a document related to the present invention, regarding the efficiency of searching for an optimal solution by a genetic algorithm, a character distribution is determined for each character position with respect to a character string representing an individual, and each character is determined based on the character distribution. Patent Literature 1 discloses a technique of obtaining the degree of randomness for each character and setting a higher mutation rate at a character position having a higher degree of randomness to improve the efficiency of the genetic operation.
[0011]
Further, Non-Patent Document 1 is a book that describes a genetic algorithm.
[0012]
[Patent Document 1]
JP-A-10-228460 (Page 5-13, FIG. 1)
[Non-patent document 1]
Saito Iba: Basics of Genetic Algorithms, Ohmsha, 1993 (pages 1-10)
[0013]
[Problems to be solved by the invention]
Genetic algorithms have the advantage that as the number of individuals generated increases, the type of solution increases and the possibility of obtaining an optimal solution increases, but the processing time required to obtain a solution in proportion to the number of individuals generated is It has the disadvantage of increasing.
Also, if the number of individuals is small, the processing time is shortened, but there is a problem that the possibility of convergence to a local solution (a solution that is not the optimal solution) increases because the types of solutions decrease.
[0014]
The present invention, in the first generation, by adding the remaining individuals from the middle generation starting with a part of the number of individuals, until obtaining the optimal solution while having the same accuracy as the conventional genetic algorithm An object of the present invention is to provide an optimal solution search time reduction system, a search time reduction method, and a program therefor in a genetic algorithm that solves the above-described problem that the processing time is short.
[0015]
[Means for Solving the Problems]
A first search time reduction system according to the present invention is a search time reduction method for solving a combination optimization problem by an evaluation means for evaluating an individual based on a genetic algorithm and a genetic operation means for performing a genetic operation on an individual. System
Addition of the number of individuals performing genetic operations from the first generation (hereinafter referred to as the initial number of individuals), the total number of generations performing the genetic operation (hereinafter referred to as the total number of generations), and the middle generations Input means for inputting the number of individuals (hereinafter referred to as the number of additional individuals) and the number of generations of the generation to which the individual is added (hereinafter referred to as the number of additional generations),
The evaluation means takes out the individuals of the number designated by the initial number of individuals as targets of the genetic operation and starts applying a genetic algorithm, and counts the number of generations each time the genetic operation is performed by the genetic operation means. Perform the genetic manipulation, and evaluate the individual.
The genetic manipulation means returns the individual that has performed the genetic operation by performing a genetic operation on the individual that has been evaluated by the evaluation means to the evaluation means,
Further, when the counted number of generations matches the number of additional generations, the evaluation means adds new individuals corresponding to the number of additional individuals as targets of the genetic operation, and the counted number of generations matches the total number of generations. Then preparing to end the genetic manipulation.
[0016]
In a second search time reduction system according to the present invention, in the first invention, the gene manipulation means includes, for generations from the first generation to the number of additional generations, the number of individuals specified by the initial number of individuals. Perform a genetic operation on the individuals, and for the generations from the number of additional generations +1 to the total number of generations, perform a genetic operation on the total number of the initial individuals and the additional individuals. Prepare to do.
[0017]
In a third search time reduction system according to the present invention, in the first invention, the genetic operation means performs genetic operations of selection / selection, crossover, mutation, and individual generation, and crossover and mutation are designated. Performing an operation according to the generated incidence.
[0018]
A fourth search time reduction system according to the present invention, in the first invention, comprises that the evaluation means evaluates an individual according to an evaluation rule registered in a storage device in advance.
[0019]
A first search time reduction method according to the present invention is to reduce a search time in a search time reduction system that solves a combination optimization problem by performing a genetic operation on a plurality of individuals over a plurality of generations based on a genetic algorithm. The method,
Addition of the number of individuals performing genetic operations from the first generation (hereinafter referred to as the initial number of individuals), the total number of generations performing the genetic operation (hereinafter referred to as the total number of generations), and the middle generations And the number of generations (hereinafter referred to as the number of additional generations) of the generation to which the individual is added, and the count field for the number of generations is initialized to 1. A first step to
A second step of taking out the number of individuals specified by the initial number of individuals and subjecting the individuals to processing of a genetic algorithm;
A third step of comparing whether the number of generations in the count field of the number of generations matches the number of additional generations,
A fourth step of adding as many individuals as the number of the additional individuals as targets of the genetic algorithm when they match in the comparison of the second step;
A fifth step of evaluating the individual when there is no match in the comparison of the third step and when an individual is added in the fourth step;
A sixth step of performing a genetic operation on all individuals evaluated in the fifth step,
A seventh step of comparing whether the value of the generation number count field matches the total generation number;
If the comparisons in the seventh step do not match, an eighth step is to add 1 to the value of the generation count field and return to the third step;
A ninth step of outputting information of an individual with a high evaluation score when the comparison in the seventh step matches,
Is provided.
[0020]
A first program of the present invention is a program executed by a search time reduction system that performs a genetic operation on a plurality of individuals over a plurality of generations based on a genetic algorithm and solves a combination optimization problem,
On the computer,
Addition of the number of individuals performing genetic operations from the first generation (hereinafter referred to as the initial number of individuals), the total number of generations performing the genetic operation (hereinafter referred to as the total number of generations), and the middle generations And the number of generations (hereinafter referred to as the number of additional generations) of the generation to which the individual is added, and the count field for the number of generations is initialized to 1. A first step to
A second step of taking out the number of individuals specified by the initial number of individuals and subjecting the individuals to processing of a genetic algorithm;
A third step of comparing whether the number of generations in the count field of the number of generations matches the number of additional generations,
A fourth step of adding as many individuals as the number of the additional individuals as targets of the genetic algorithm when they match in the comparison of the second step;
A fifth step of evaluating the individual when there is no match in the comparison of the third step and when an individual is added in the fourth step;
A sixth step of performing a genetic operation on all individuals evaluated in the fifth step,
A seventh step of comparing whether the value of the generation number count field matches the total generation number;
If the comparisons in the seventh step do not match, an eighth step is to add 1 to the value of the generation count field and return to the third step;
A ninth step of outputting information of an individual with a high evaluation score when the comparison in the seventh step matches,
Is executed.
[0021]
BEST MODE FOR CARRYING OUT THE INVENTION
Next, embodiments of the present invention will be described in detail with reference to the drawings.
[0022]
First, the configuration of the first and second embodiments of the present invention will be described with reference to FIG.
[0023]
The present invention includes an input device 101 such as a keyboard connected to a computer 100 such as a personal computer, an output device 102 such as a display device such as a display or a printing device such as a printer, and a storage device 103 such as a magnetic disk device. And a program that operates on the main storage device of the computer 100.
[0024]
An input unit 110 that receives input data from the input device 101 as individual programs that operate on the computer 100 and instructs control of the overall operation;
An environment defining means 111 for defining a component composed of genetic information of the individual;
An evaluation rule defining means 112 for defining a rule for evaluating an individual;
Random number generating means 113 for generating random numbers,
An initial individual generation unit 114 that generates a specified number of individuals based on the contents of the environment definition unit 111 using random numbers by the random number generation unit 113;
Genetic manipulation means 115 for performing genetic manipulation on the individual,
Evaluation means 117 for calculating an evaluation value of an individual for each individual;
Output means 118 for outputting the individual information having a high evaluation value to the output device 102 after the execution of the designated number of generations.
[0025]
Hereinafter, the case where the timetable of the school is determined by applying the genetic algorithm will be described. For example, suppose that there is a university from one year to four years, and there are three classes (classes) of A, B, and C in each school year. Further, it is assumed that classes are held every day from Monday to Saturday until the fifth hour, and the total number of class hours per week for each class is 30 hours.
[0026]
The problem is to set the subjects for each class from Monday to Saturday as a timetable for each class of the fourth grade. One individual at this time shall include a continuous 30-hour timetable from Monday to Friday of one class for all classes of the fourth grade, and the gene of the individual shall be the subject of each time (for example, English conversation, English composition, etc.). And At that time, the individual is composed of 360 (= 4th grade X3 class X6 days X5 hours) elements (genes). This is shown in FIG. According to FIG. 4, the first 30 elements are the timetable from the 1st Monday to the 5th Saturday of the A-class for one year, the next 30 elements are the timetable for the one-year B class, and the last 30 elements are the four-year Class timetable.
[0027]
Genetic operations on individuals defined in this way are performed in the same class and between the same classes.
[0028]
The environment definition means 111 sets the total number of hours for each subject in each week in each class of each academic year in the storage device 103. For example, the total English conversation time per week for the A class per year is 4 hours, the English composition is 3 hours, and so on.
The total number of hours for this course is close to 30 hours for each class, and less than 30 hours is free time. If there is free time, the number of free hours in the week is also captured in the same manner as the number of hours in each subject, so that the total number of hours in the week is 30 hours.
[0029]
The evaluation rule definition unit 112 registers, in the storage device 103, the evaluation rules for evaluating the individual and the scores of the individual evaluation rules. For example,
・ Deductions will be made for timetables in which subjects are not continuous for two consecutive hours.
-Points will be deducted if subjects are assigned at times when teachers are not convenient.
・ If there is more than 2 hours of free time until the next lesson, points will be deducted.
・ If there is a shortage of classrooms at the same time as the judgment of an empty classroom, points will be deducted.
・ If the same subject is assigned more than once on the same day, points will be deducted.
Various rules are registered for restrictions on setting the equal timetable.
[0030]
Further, the points to be deducted are adjusted by taking into account the weight of the rules. In addition to deductions, points may be added if they are in line with the rules. Also, the score for the rule once set is not fixed but can be changed as appropriate.
[0031]
The random number generation means 113 creates a plurality of sets of permutations in which the order of numbers from 1 to 30 is randomly arranged, for example, and registers them in the storage device 103 in accordance with the number of individuals and the number of classes.
[0032]
The initial individual generator 114 generates a designated number of initial individuals. At this time, a set of permutations from 1 to 30 generated by the random number generation means 113 is taken out, and individual elements are created according to the time information of each subject of each class registered by the environment definition means 111. For example, if the first registered subject is English conversation and the total number of hours per week is 4 hours for the A class for one year, the first subject on Monday is 4th from the top of the permutation of the 4-hour English conversation. The time period is set to 1, and the time period is randomly arranged on the individual corresponding to the A-class timetable for one year. The initial individual generating means 114 registers the individual generated by performing the above operation for all classes in the storage device 103.
[0033]
The genetic operation means 115 performs a genetic operation (selection / selection, crossover, mutation, individual generation) on subjects constituting each individual.
[0034]
The evaluation unit 117 reads the rules registered by the evaluation rule definition unit 112 from the storage device 103 for the individual to be operated before the start of the genetic operation for each generation, and evaluates each individual according to the defined rules. And set an evaluation value for each individual. Further, the evaluation means 117 counts the number of executed generations and ends the genetic operation processing when detecting the number of generations to be ended.
[0035]
Next, the operation of the embodiment of the present invention will be described with reference to the drawings.
[0036]
The flowchart of FIG. 2 shows a case where a specific generation is not specified, and the flowchart of FIG. 3 shows a case where a specific generation is specified.
[0037]
The operation of the first embodiment of the present invention will be described with reference to the flowchart of FIG.
[0038]
The user inputs information necessary for setting a timetable from the input device 101. The timetable setting target periods include, for example, one day, week, two weeks, and month. Further, the number of hours for starting the lesson is designated every day. Also, enter the target grade and the number of departments (classes) per grade. Further, the subject type and the total number of hours of the subject for each class to be conducted within the timetable setting target period are input.
[0039]
The input unit 110 of the computer 100 passes the input information to the environment definition unit 111, and the environment definition unit 111 creates configuration information including the number of constituent elements of the individual based on the contents, and stores the configuration information in the storage device 103. It is stored as information (step S1). For example, if the fourth grade, the number of subjects per grade, is 3 and the courses are open every day from Monday to Saturday for 5 hours, the composition information of the individual on the timetable for each subject in each grade is as shown in FIG. In this case, 360 elements (genes) are included.
[0040]
The user subsequently inputs the symbolized evaluation rule for evaluating each individual and the score of the evaluation rule, and the evaluation rule definition means 112 registers this in the storage device 103 as evaluation rule information (step S2). In the description of the present embodiment, the total number of hours per week for each class is uniformly 30 hours, but it is not always necessary to set the same number of hours.
[0041]
Subsequently, the user inputs the number of individuals to be generated (for example, 5000 individuals) and the number of generations to be executed (for example, 200 generations).
[0042]
Upon receiving this, the input unit 110 passes the generated individual number information to the random number generation unit 113 and instructs the random number generation.
[0043]
The random number generation unit 113 extracts the number of elements constituting an individual for each class from the environment information generated by the environment definition unit. The random number generation means 113 randomly creates a permutation of all integers from 1 to the number of elements extracted for each class by the designated number of individuals × the number of classes, and registers it in the storage device 103 (step S3). , Is notified to the input means 110. Subsequently, the input unit 110 designates the number of individuals to be generated and instructs the initial individual generation unit 114 to generate individuals.
[0044]
The initial individual generating means 114 randomly identifies the subject type based on the configuration information of the individual extracted from the environment information, the subject of each class, the total number of hours of the subject, and the random permutation generated by the random number generating means 113. When the individuals are arranged above and the specified number of individuals are generated, they are registered in the storage device 103 (step S4).
[0045]
Next, the input unit 110 notifies the evaluation unit 117 of the number of generations to be executed and the number of individuals to be executed.
[0046]
Upon receiving the notification, the evaluation unit 117 performs the initial population generation process, extracts from the storage device 103 generated and registered by the initial individual generation unit 114 the number of individuals to be notified and executes, and counts the number of generations. The field is initialized as 1 (step S5).
[0047]
The evaluation means 117 reads out the evaluation rules registered by the evaluation rule definition means 112 from the storage device 103 at the time of evaluation, and applies the registered rules one by one to the individual to be evaluated. Penalties will be penalized for breaking the rules, and points will be added for breaking the rules. The evaluation is performed by applying all the rules defined in this way. The scored result is set and stored for each individual (step S6). When the initial individual is generated, the same fixed score is assigned to each individual.
[0048]
Next, the genetic operation means 115 performs a genetic operation on the individual to be evaluated. Specifically, the following operations are performed in order.
(1) The following methods are available for selection and selection.
[0049]
-Leave one or more individuals with the best evaluation value.
[0050]
・ Leave two randomly selected individuals with good evaluation values.
[0051]
・ Leave randomly selected individuals.
(2) The following methods are available for crossover. In the case of crossover, all individuals to be evaluated are divided into sets of two individuals in advance according to random numbers, and crossover is performed between individuals of the same set.
[0052]
-Swap the genes behind each other from a certain place randomly divided between the same class of individuals of the same set. For example, if the class A of the year is divided between the 2nd and 3rd period on Wednesday, the genetic information from the 3rd period on the Wednesday and the 5th period on Saturday of the 1st A class of the other individual of the same group is Replace with the relevant part of the other individuals in the set.
[0053]
-The two parts of the same set of individuals that are randomly separated between the same classes are replaced with corresponding parts of other individuals.
(3) There are the following methods for mutation.
[0054]
-Swap two randomly selected genes of the same class of one individual.
[0055]
-Swap a plurality of randomly selected genes of the same class of one individual.
[0056]
In the case of crossover and mutation, the incidence of 0% to 100% is separately defined in advance, and the genetic operation in each generation is performed or not performed according to the incidence (step S7). The numerical value of this% can also be set by the user.
[0057]
Next, it is confirmed whether or not the above-described genetic operation has been performed for all individuals targeted (step S8). If the process has not been performed for all individuals, the process returns to (Step S7). When the execution has been completed for all individuals, the process returns to the evaluation means 117.
[0058]
The evaluation unit 117 checks whether the genetic operation has been completed for all the generations (step S9). If the processing has not been completed for all the generations, 1 is added to the count field of the number of generations (step S10). Then, the process returns to (Step S6) to execute the individual evaluation.
[0059]
When all the generations have been evaluated in the evaluation of (Step S8), the output unit 118 executes the final evaluation and designates the genetic information of the individual having the highest evaluation score or the genetic score of the individual having the highest evaluation score and the evaluation score. The output is output to the output device 102 for the number of individuals, and the process ends (step S11).
[0060]
In the present embodiment, the number of individuals generated by the initial outbreak does not change. Therefore, if the number of individuals is large, the possibility of obtaining an optimal solution is high, but the processing time is long.
[0061]
Next, the operation of the second embodiment will be described with reference to the flowchart of FIG.
[0062]
In the flowchart of FIG. 3, (Step S12) and (Step S13) are added in the middle of the flowchart of FIG. 2, and the contents of (Step S1) to (Step S11) are the same as those in FIG.
[0063]
In the present embodiment, when the number of specific generations is specified by the user and the number of executed generations reaches the specified specific number of generations, the content to be added is added to the individual to be evaluated. This is the same as the embodiment. Mainly, differences from the first embodiment will be described.
[0064]
First, the user generates the number of individuals (for example, 5000 individuals), the number of generations to be executed (for example, 200 generations), the number of individuals to be executed from the beginning (for example, 1000 individuals), the number of individuals to be added in the middle (for example, 4000 individuals), The number of specific generations (for example, 100 generations) to add individuals on the way is input.
[0065]
Next, the input unit 110 notifies the information input by the user to the evaluation unit 117.
[0066]
In (Step S5) and (Step S6), the evaluation means 117 takes out individuals corresponding to the number of individuals to be executed from the beginning from the storage device 103, and initializes the count field of the number of generations as 1. Then, an evaluation is performed for each individual.
[0067]
Next, the evaluation means 117 checks whether the number of specific generations to which individuals are added on the way has been reached (step S12). If the number of specific generations has been reached, an unevaluated individual is input from the storage device 103 and added to the evaluation target in accordance with the number of individuals to be added from the middle of the previous reception (step S13). (Step S6). After the evaluation is completed (step S7), the genetic operation is performed.
[0068]
If it is not the specific generation in the evaluation in (Step S12), the evaluation in (Step S6) is performed.
[0069]
In the case of the present embodiment, the number of individuals is changed according to the processing stage. First, a small number of individuals are generated in the initial outbreak, and evaluation and genetic operations are repeated for this individual until a specific generation. When reaching the specific generation, the number of individuals is added, and individuals are added up to the same number of individuals as in the first embodiment. Thereafter, the evaluation and the genetic operation are repeated until the termination condition is satisfied.
[0070]
In the second embodiment, the processing time can be reduced by reducing the number of individuals from the initial population generation to the specific generation. Further, since the number of individuals is added in a specific generation, a deep search can be performed by treating the same number of individuals as in the second embodiment, and the possibility of obtaining an optimal solution can be increased. Rather than processing the required number of individuals at once, increasing the number of individuals in a stepwise manner enables processing in a short time while maintaining the accuracy of the second embodiment. it can.
[0071]
Finally, the processing time of each of the two embodiments described above is calculated.
[0072]
In both embodiments, it is assumed that the number of individuals handled is 5,000, the termination condition (the number of termination generations) is 200 generations, and the time required for evaluation and genetic operation of one individual is 1 second.
[0073]
In the case of the first embodiment, the processing is simply repeated until 5,000 individuals reach the termination condition, and the processing time is 5,000 × 200 generations × 1 second = 1,000,000,000 seconds.
[0074]
In the second embodiment, the initial number of individuals is 1,000, and 4,000 individuals are added at the 100th generation.
[0075]
The processing time in this case is 1,000 × 100 generation × 1 second + 5,000 × 100 generation × 1 second = 600,000 seconds.
[0076]
In the second embodiment, it can be seen that the processing time is reduced by 40% as compared with the first embodiment. In addition, since the number of processing individuals in the second embodiment is the same as that in the first embodiment, it can be said that it has the same accuracy as that in the first embodiment. In the second embodiment, the number of individuals to be initially input, the number of generations to add an individual, and the number of individuals to be added in the generation to be added can be appropriately changed.
[0077]
Further, in the second embodiment, the description has been made based on the case where the genetic algorithm is applied to the creation of the timetable. However, the initial number of individuals, the number of individuals to be added, the number of generations to add the number of individuals, and the number of end generations are specified. Thus, the present invention can be applied to a combination optimization problem using various genetic algorithms.
[0078]
【The invention's effect】
There are three effects of the present invention. First, a timetable can be easily created by performing a task of setting a timetable by applying a genetic operation algorithm.
[0079]
Secondly, "the processing time can be shortened" and thirdly, "the same accuracy as that of the conventional method can be maintained". As described above, this reduces the number of individuals from the initial population generation to the specific generation, and gradually increases the number of individuals in the specific generation, thereby conducting a deep search by treating the same number of individuals as in the conventional method. This is because the optimal solution can be obtained in a short time.
[Brief description of the drawings]
FIG. 1 is a block diagram illustrating a configuration of an embodiment of the present invention.
FIG. 2 is a flowchart illustrating an operation of the first exemplary embodiment of the present invention.
FIG. 3 is a flowchart illustrating an operation of the second exemplary embodiment of the present invention.
FIG. 4 is an explanatory diagram of individual components for creating a timetable according to the embodiment of this invention.
[Explanation of symbols]
REFERENCE SIGNS LIST 100 computer 101 input device 102 output device 103 storage device 110 input means 111 environment definition means 112 evaluation rule definition means 113 random number generation means 114 initial individual generation means 115 gene manipulation means 117 evaluation means 118 output means

Claims (6)

A search time reduction system for solving a combination optimization problem by an evaluation means for evaluating an individual based on a genetic algorithm and a genetic operation means for performing a genetic operation on the individual,
Addition of the number of individuals performing genetic operations from the first generation (hereinafter referred to as the initial number of individuals), the total number of generations performing the genetic operation (hereinafter referred to as the total number of generations), and the middle generations Input means for inputting the number of individuals (hereinafter referred to as the number of additional individuals) and the number of generations of the generation to which the individual is added (hereinafter referred to as the number of additional generations),
The evaluation means takes out the individuals of the number designated by the initial number of individuals as targets of the genetic operation and starts applying a genetic algorithm, and counts the number of generations each time the genetic operation is performed by the genetic operation means. Perform the genetic manipulation, and evaluate the individual.
The genetic manipulation means returns the individual that has performed the genetic operation by performing a genetic operation on the individual that has been evaluated by the evaluation means to the evaluation means,
Further, when the counted number of generations matches the number of additional generations, the evaluation means adds new individuals corresponding to the number of additional individuals as targets of the genetic operation, and the counted number of generations matches the total number of generations. Then, the genetic operation is terminated, and the search time is reduced. 2. The genetic operation means according to claim 1, wherein the genetic operation means performs a genetic operation on the number of individuals specified by the initial number of individuals for generations from a first generation to the number of additional generations. A search time reduction system, wherein, for the generations from the +1 generation to the total number of generations, a genetic operation is performed on the number of individuals obtained by adding the initial number of individuals and the number of additional individuals. 2. The search according to claim 1, wherein the genetic operation means performs genetic operations of selection / selection, crossover, mutation, and individual generation, and performs crossover and mutation according to a specified incidence rate. Time saving system. 2. The search time reduction system according to claim 1, wherein the evaluation unit evaluates the individual according to an evaluation rule registered in a storage device in advance. A search time reduction method in a search time reduction system for performing a genetic operation over a plurality of generations on a plurality of individuals based on a genetic algorithm to solve a combination optimization problem,
Addition of the number of individuals performing genetic operations from the first generation (hereinafter referred to as the initial number of individuals), the total number of generations performing the genetic operation (hereinafter referred to as the total number of generations), and the middle generations And the number of generations (hereinafter referred to as the number of additional generations) of the generation to which the individual is added, and the count field for the number of generations is initialized to 1. A first step to
A second step of taking out the number of individuals specified by the initial number of individuals and starting processing of the genetic algorithm;
A third step of comparing whether the number of generations in the count field of the number of generations matches the number of additional generations,
A fourth step of newly adding as many individuals as the number of the additional individuals as targets of the genetic algorithm when they match in the comparison of the second step;
A fifth step of evaluating all individuals when there is no match in the comparison of the third step, and when an individual is added in the fourth step,
A sixth step of performing a genetic operation on all individuals evaluated in the fifth step,
A seventh step of comparing whether the value of the generation number count field matches the total generation number;
If the comparisons in the seventh step do not match, an eighth step is to add 1 to the value of the generation count field and return to the third step;
A ninth step of outputting information of an individual with a high evaluation score when the comparison in the seventh step matches,
A method for shortening a search time, comprising: A program executed by a search time reduction system that performs a genetic operation on a plurality of individuals based on a genetic algorithm over a plurality of generations and solves a combination optimization problem,
On the computer,
Addition of the number of individuals performing genetic operations from the first generation (hereinafter referred to as the initial number of individuals), the total number of generations performing the genetic operation (hereinafter referred to as the total number of generations), and the middle generations And the number of generations (hereinafter referred to as the number of additional generations) of the generation to which the individual is added, and the count field for the number of generations is initialized to 1. A first step to
A second step of taking out the number of individuals specified by the initial number of individuals and starting processing of the genetic algorithm;
A third step of comparing whether the number of generations in the count field of the number of generations matches the number of additional generations,
A fourth step of newly adding as many individuals as the number of the additional individuals as targets of the genetic algorithm when they match in the comparison of the second step;
A fifth step of evaluating all individuals when there is no match in the comparison of the third step, and when an individual is added in the fourth step,
A sixth step of performing a genetic operation on all individuals evaluated in the fifth step,
A seventh step of comparing whether the value of the generation number count field matches the total generation number;
If the comparisons in the seventh step do not match, an eighth step is to add 1 to the value of the generation count field and return to the third step;
A ninth step of outputting information of an individual with a high evaluation score when the comparison in the seventh step matches,
A program that executes

Images