JP7449975B2 - Information processing device, information processing method, program - Google Patents

Description

The present invention relates to an information processing device, an information processing method, and a program.

Conventionally, using evolutionary calculation algorithms such as genetic algorithms, evaluation is performed by repeatedly performing selection, crossover, and mutation processing on multiple individuals to generate multiple next-generation individuals. Techniques for generating high-quality individuals have been proposed.

Patent Document 1 discloses that in order to generate individuals that satisfy the constraint conditions, selection, crossover, and mutation processes are performed on N individuals to generate N individuals of the next generation that satisfy the temporary constraint conditions. A solution search device is described that repeatedly performs the following steps. Here, each time the solution search device generates the next generation individual, it updates the temporary constraint so that it approaches the constraint.

Japanese Patent Application Publication No. 2014-160399

Here, in the evolutionary calculation algorithm, an individual usually has one chromosome (genetic information in which genes are arranged in a row), but may have a plurality of different chromosomes (condition information). For example, as in individual X1 shown in FIG. 3, chromosomes may be associated with each of the items B1 to B4. In this case, in processing using an evolutionary calculation algorithm, for example, when mutation processing is performed on one individual, mutation processing is performed at random positions (genetic loci) for each item. For this reason, there was a problem that the convergence of individual evaluation values was low and the processing of the evolutionary calculation algorithm was not efficient.

Therefore, an object of the present invention is to provide a technique for efficiently executing processing of an evolutionary calculation algorithm.

One aspect of the present invention is
An information processing device that determines conditions of multiple elements using an evolutionary calculation algorithm,
Acquire a plurality of condition information sets including condition information for each of the plurality of elements, evaluate each of the plurality of condition information sets, and perform crossover processing and mutation processing to obtain the next generation of the plurality of condition information. and determining means for determining conditions of the plurality of elements by repeatedly generating a set,
The crossover process is a process of crossing condition information of the same elements in two condition information sets,
If the first element and the second element among the plurality of elements satisfy a predetermined relationship according to the degree of similarity, when performing the crossover process, the determining means determines that the first element is When performing the crossover process on the condition information and when performing the crossover process on the condition information of the second element , the condition information of the first element and the condition of the second element are the same at the same intersection point. performing the crossover processing on each piece of information ;
This is an information processing device characterized by the following.

According to this configuration, when the first element and the second element satisfy a predetermined relationship according to the degree of similarity, the same crossover process is performed on the condition information (chromosomes) of these two elements. It will be done. For this reason, it becomes possible to execute processing for the condition information of two elements at once.
Optimization processing using an evolutionary calculation algorithm can be made more efficient (simplified). Further, when the same crossover process is performed on the condition information of a plurality of elements, the condition information tends to become similar. Therefore, for example, when the first element and the second element satisfy a predetermined relationship depending on the degree of similarity, the condition information that gives a high evaluation is similar to the first element and the second element. If it exists, the convergence of evolutionary calculation algorithms will improve.

Note that the condition information is, for example, information on a one-dimensional array, and is a "chromosome" in an evolutionary calculation algorithm. The condition information set is an "individual" in the evolutionary calculation algorithm.

In the above information processing device, the determining means performs the mutation process if the predetermined relationship depending on the degree of similarity between the first element and the second element among the plurality of elements is satisfied. In this case, the condition information of the first element is subjected to mutation, and the same mutation may be performed to the condition information of the second element. According to this, not only crossover processing but also mutation processing can be performed on the condition information of two elements, which further improves the efficiency of optimization processing using evolutionary calculation algorithms. (simplification).

The above information processing device further includes a control means for classifying the plurality of elements into a plurality of groups according to the degree of similarity between the plurality of elements, and the first element and the second element The case where the predetermined relationship based on the degree of similarity is satisfied may be the case where the first element and the second element are classified into the same group. According to this, it becomes possible to perform crossover processing for each group, so that optimization processing using an evolutionary calculation algorithm can be made more efficient (simplified).

In the above information processing apparatus, the control means may determine the degree of similarity between the plurality of elements according to an attribute of each element.

In the above information processing device, the plurality of elements are mutually different types of products, and the attributes are information associated with each product, such as category, product name, manufacturer information, specifications, price, The information may include at least one of a product description and a sales start date.

In the above information processing device, the plurality of elements may be different types of products, and the condition information for each of the plurality of products may indicate whether the product is in stock at each of the plurality of storage locations. According to this, it becomes possible to determine the placement of each type of product in each storage location.

In the above information processing device, the determining means calculates an evaluation value for each of the plurality of condition information sets, and the evaluation value is determined based on the number of storage locations where the product is stored per one type of product, and The value may be based on the shipping cost of the product based on past shipping performance data. According to this, it becomes possible for the information processing device to perform an evaluation that takes into account both the management cost at the storage location and the delivery cost. In other words, it becomes possible to appropriately determine the placement of each type of product in each storage location.

The present invention also relates to an information processing method, an electronic device, a control method for an electronic device, an information processing system, a product management system, a product management device, a product management method, and an optimization processing device that include at least a part of the functions and processes described above. , it can be considered as an optimization method. Further, the present invention can also be understood as a program that causes a computer to execute each means (each step of an information processing method) of an information processing device (electronic device), or a storage medium that non-temporarily stores the program. .

According to the present invention, processing of an evolutionary calculation algorithm can be executed efficiently.

FIG. 1 is a diagram illustrating the arrangement of a plurality of products in a warehouse according to the first embodiment. FIG. 2 is a configuration diagram of the information processing apparatus according to the first embodiment. FIG. 3 is a diagram illustrating each individual according to the first embodiment. FIG. 4 is a diagram illustrating attribute information according to the first embodiment. 5A and 5B are diagrams illustrating crossover processing and mutation processing according to the first embodiment. FIG. 6 is a flowchart of optimization processing according to the first embodiment. FIG. 7 is a flowchart of evaluation value calculation processing according to the first embodiment. 8A and 8B are flowcharts regarding crossover and mutation according to the first embodiment. FIG. 9 is a diagram illustrating crossover processing according to the similarity of products according to the first embodiment. FIG. 10 is a diagram illustrating mutation processing according to the similarity of products according to the first embodiment. FIG. 11 is a flowchart of optimization processing according to modification 1.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the drawings. Note that the present invention is not limited to the described embodiments. Furthermore, not all of the components described in the embodiments are essential to the present invention.

<Embodiment 1>
In the first embodiment, in response to an order from an orderer, a company that delivers (ships) products from a warehouse (storage location) to the orderer ships products of P types (P>2) to Q locations (P>Q, Assume that the storage device is placed in a warehouse where Q>2). Then, the information processing device 1 according to the first embodiment uses a genetic algorithm as an evolutionary calculation algorithm to store Q locations of P types of products so that the delivery cost is low and the warehouse management cost is reduced. (placement conditions for P types of products). Note that instead of the genetic algorithm, an evolutionary calculation algorithm such as a memetic algorithm, an immune-type optimization algorithm, or a distributed genetic algorithm (island model) may be used.

For example, as shown in Figure 1, products B(1) to B(4) are placed in warehouses A(1) to A(3), and from the delivery destination (address) of the orderer to warehouses A(1), A(3), and Assume that (2) and A(3) are close in this order. In this case, if the orderer orders products B(1) and B(4) at the same time, product B(1) will be delivered from warehouse A(1) and product B(4) will be delivered from warehouse A. (3) Two types of products can be delivered at the lowest shipping cost by shipping from (3) onwards. On the other hand, if both products B(1) and B(4) are placed in warehouse A(1), two types of products can be delivered from warehouse A(1), which further reduces delivery costs. can. However, if four types of products B(1) to B(4) are placed in warehouse A(1), three types of products B(1) to B(3) are placed in warehouse A(1). The management cost of warehouse A(1) is higher than when different types of products are arranged.

In view of this, in the first embodiment, the purpose is to reduce the delivery cost when delivering the product to the orderer, and further to reduce the warehouse management cost. In the first embodiment, the information processing device 1 achieves these objectives by controlling crossover processing and mutation processing based on the degree of similarity between P types of products.

(Configuration of information processing device)
The configuration of the information processing device 1 will be described with reference to FIG. 2. The information processing device 1 may be any device (such as a personal computer) as long as it has a processor, a storage medium (memory), etc., and can process information. The information processing device 1 includes an acquisition section 201, an evaluation section 202, a generation section 203, a control section 204, and an attribute storage section 205. Note that a processor included in the information processing device 1 functions as an acquisition unit 201, an evaluation unit 202, a generation unit 203, and a control unit 204. A storage medium (memory) included in the information processing device 1 functions as the attribute storage unit 205.

The acquisition unit 201 acquires (generates) N pieces (N>2) of inventory placement information sets (condition information sets) each having inventory placement information of P types of products as "individuals" in the genetic algorithm. Inventory placement information (condition information) indicates whether the products linked to the inventory placement information are placed in each of warehouses A(1) to A(Q) (inventory availability; placement conditions). It is the "chromosome" in genetic algorithms. Therefore, in the first embodiment, each individual has chromosomes for each of P types of products (elements; items), products B(1) to B(P). That is, each individual has P chromosomes. Specifically, as shown in Figure 3, for each individual product, "0" and "1" are used to indicate whether or not each product is placed in each of warehouses A(1) to A(Q). The one-dimensional array shown is set as a chromosome. For example, for individual X1, if the value of the first column (first gene) of the chromosome of product B (1) is "1", product B (1) will be placed in warehouse A (1). It is shown. On the other hand, for individual X1, if the value of the fifth column (fifth gene) of the chromosome of product B (4) is "0", product B (4) will not be placed in warehouse A (5). It is shown.

In addition, in the inventory location information (chromosome) of each product, each gene may indicate the upper limit or lower limit of the number of the product in each warehouse. For example, for individual X1, if the value of the first column (first gene) of the chromosome of product B (1) is "10", then at least 10 products B (1) are in warehouse A (1). It may also indicate that it will be placed. On the other hand, for individual X1, if the value of the fifth column (fifth gene) of the chromosome of product B (4) is "15", there are at least 15 products B (4) in warehouse A (5). It may also indicate that it will be placed. Furthermore, in the inventory location information (chromosome) for each product, each gene may indicate the size of the location (for example, shelf) used to store the product in each warehouse.

The evaluation unit 202 evaluates N individuals (inventory arrangement information set; condition information set). Specifically, the evaluation unit 202 calculates an evaluation value for each of the N individuals based on the delivery cost and the warehouse management cost. The method for calculating the evaluation value will be described in detail later using the flowchart of FIG.

The generation unit 203 executes selection processing, crossover processing, and mutation processing using N individuals to generate N individuals of the next generation. . The generation unit 203 includes a selection unit 211, a crossover processing unit 212, and a mutation processing unit 213.

The control unit 204 controls each component of the information processing device 1 . The control unit 204 (determination unit) may perform all or part of the processing of the acquisition unit 201, evaluation unit 202, and generation unit 203. Further, the control unit 204 determines, based on the evaluation by the evaluation unit 202, whether or not the generation unit 203 should terminate the generation of the next-generation N individuals. The control unit 204 places P types of products in Q locations in the warehouse (each Conditions for placing different types of products in warehouses)
Determine. For example, the control unit 204 determines the placement of P types of products in Q locations in the warehouse according to the chromosome (placement information) indicated by the individual with the highest evaluation value (stock placement information set).

As shown in FIG. 4, the attribute storage unit 205 stores information on the attributes of each of products B(1) to B(P). For example, the attribute information includes a product name (product name), category information (extra-large classification, major classification, medium classification, small classification), color information, and the like. Oversized classification is the most abstract category of products. The categories gradually change into specific categories in the order of extra-large classification, major classification, medium classification, and small classification. For example, as shown in Figure 4, for product B (1), which is a specific gel ink ballpoint pen, the extra-large classification is "Stationery/Office Supplies," the major classification is "Writing Instruments," and the medium classification is "Ballpoint Pens." ", and its subcategory is "gel ink ballpoint pen." Note that the attribute information may include, for example, at least one of manufacturer information (information regarding the manufacturer, series name, or brand name), price, specifications, product description, and sales start date. Specifications are detailed information regarding at least one of the dimensions, weight, and functions of a product. The price is the product price. For example, since a user may purchase multiple products in the same price range at the same time, price is included in the attribute information. The product description is a text that explains the product displayed on a website, etc., and includes a catchphrase. The sales start date is the date on which the sale (sales) of the product started. For example, since multiple products that went on sale on the same day may belong to the same product series (that is, they may be similar), the attribute information includes the release start date.

In addition, the attribute storage unit 205 stores products B(1) to Stores group information in which (P) is classified into a plurality of groups. Here, the process of classifying the product groups is executed by the control unit 204 based on attribute information, for example. For example, products with the same "minor classification" in the attribute have a high degree of similarity (higher than a threshold) and are therefore grouped together into one group. That is, P types of products may be grouped into groups for each "minor category." For example, in the example shown in FIG. 4, product B(1) and product B(4) are both classified into the same group because their "minor category" is "gel ballpoint pen." Note that instead of "minor classification", "medium classification" or "major classification" may be used.

Note that as long as products whose similarity is higher than a threshold value are classified into one group, classification into any group may be performed. For example, the control unit 204 may classify a plurality of products having the same "major classification" of attributes and the same "color information" into one group. Further, the control unit 204 may classify into one group a plurality of products whose product names (names of products) have a similarity higher than a predetermined value. Here, the degree of similarity of product names can be determined using known methods such as ``Levenshtein distance'' or ``cosine similarity'' after converting text information into a vector of continuous values using distributed representation. techniques can be used. Furthermore, groups may be classified by pairing two products whose similarity is higher than a threshold value. Note that there may be cases where only one product belongs to a group, such as when there is no product similar to a certain product. Note that the degree of similarity between products may not be a degree of similarity according to an attribute, but may be a degree of similarity determined from a photograph of the products.

The selection unit 211 deletes M (for example, N/2) individuals from the N individuals of the current generation in descending order of evaluation value. Thereby, the selection unit 211 selects NM individuals with high evaluation values from the N individuals of the current generation. Note that the selection unit 211 may exclude individuals whose evaluation value is lower than a threshold value from among the N individuals. Accordingly, the selection unit 211 may select a plurality of individuals whose evaluation values are equal to or greater than the threshold value. At this time, the selection unit 211 selects any method such as roulette wheel selection, rank selection, elitism, etc., as long as it is highly likely to select individuals with high evaluation values. Individuals may be selected depending on the method.

The crossover processing unit 212 further selects two individuals from the plurality of individuals selected by the selection unit 211, and performs crossover processing on the selected two individuals. As a result, the crossover processing unit 212 generates one next-generation individual. Crossover processing is the process of multiplying the chromosomes (inventory arrangement information) of the same products (elements) in two individuals based on a randomly determined crossover point (genetic locus that serves as the reference for crossover). That's true.

For example, select individual X1 as the first individual as shown in FIG. 5A, select individual X2 as the second individual, and cross-cross the two chromosomes of product B(1) of the two individuals. A case will be explained below. At this time, assuming that the position between the 5th and 6th columns of the chromosomes is the crossover point, the crossover processing unit 212 intersects the 1st to 5th columns of the chromosomes of product B(1) of the first individual X1. , and the 6th to 12th columns of the chromosomes of product B(1) of the second individual X1. As a result, the crossover processing unit 212 generates the chromosome of product B(1) of the next generation individual Xa. The crossover processing unit 212 generates the next generation individual Xa by performing similar processing on the chromosomes of products B(2) to B(P) of the individual X1 and the individual X2. Note that the number of intersection points is not limited to one point, but may be two or three points. Further, the crossover process may be a uniform crossover.

The mutation processing unit 213 performs mutation processing on the individuals generated by the crossover processing. As a result, the mutation processing unit 213 generates one next-generation individual. Mutation processing means changing (inverting) the gene (information) at one random location (genetic locus) in the chromosome of each product of one individual.

For example, a case will be described in which mutation processing is performed on the chromosome of product B(1) in individual X1 as shown in FIG. 5B. At this time, if the mutation target (target position) is the gene in the fifth column of the chromosome, the mutation processing unit 213 changes "0" indicated by the gene in the fifth column to "1" ( (invert). As a result, the mutation processing unit 213 generates the chromosome of product B(1) of the next generation individual Xb. The crossover processing unit 212 generates the next generation individual Xb by performing similar processing on the chromosomes of products B(2) to B(P) of the individual X1.

(About optimization processing)
With reference to the flowchart of FIG. 6, an optimization process for optimizing individuals (optimizing each chromosome) by determining a set of N individuals with high evaluation values will be described. The processing in the flowchart of FIG. 6 is realized by a processor in the information processing device 1 executing a program stored in a storage medium.

In step S1001, the acquisition unit 201 acquires N individuals as current generation individuals. At this time, the acquisition unit 201 may randomly generate N individuals, or may acquire N individuals input by the user. At this time, the acquisition unit 201 generates each individual such that, for example, if the product is different in one individual, the chromosomes of the product are also different. Note that the acquisition unit 201 may acquire each individual such that the chromosomes of a plurality of products belonging to the same group (multiple products that are similar to each other) are the same. Alternatively, the acquisition unit 201 may acquire each individual such that the chromosomes of a plurality of products belonging to the same group are similar to each other. Here, "two chromosomes are similar to each other" means, for example, that the degree of matching (degree of coincidence) between the two chromosomes is greater than or equal to a predetermined value (for example, 90% or 95%).

In the first embodiment, the acquisition unit 201 acquires N individuals of the current generation that satisfy the constraint conditions. Here, the constraint conditions are, for example, that the inventory capacity of each warehouse is not exceeded, that the shipping capacity of each warehouse is not exceeded, that the inventory capacity of each product is unchanged, and that each product is placed in at least one location. includes at least one condition of Note that the constraint condition may not be set, and the acquisition unit 201 may acquire the N individuals of the current generation without any constraints.

In step S1002, the evaluation unit 202 calculates evaluation values for each of the N individuals of the current generation. The evaluation value calculation process (calculation method) will be described later using the flowchart of FIG.

In step S1003, the control unit 204 determines whether the termination conditions for the optimization process are satisfied. For example, the control unit 204 determines that the termination condition is satisfied when the minimum value or maximum value of the evaluation values of the N individuals of the current generation is larger than the threshold value. Further, the control unit 204 may determine that the end condition is satisfied if the average value or median value of the evaluation values of the N individuals of the current generation is larger than a threshold value. Further, the control unit 204 may determine that the end condition is satisfied when a set number of generations is reached (for example, when the process in step S1003 has been executed a specific number of times). If it is determined that the termination condition is satisfied, the optimization process ends. If it is determined that the termination condition is not satisfied, the process advances to step S1004. Note that when the optimization process is completed, the control unit 204 determines the N individuals of the current generation as the N optimized individuals. Through the process in step S1003, the control unit 204 can control the generation and evaluation of N individuals of the next generation to be repeated until N individuals satisfying the termination condition are generated.

In step S1004, the selection unit 211 removes (deletes) M (for example, N/2) individuals from the N individuals of the current generation in descending order of evaluation value. Thereby, the selection unit 211 selects NM individuals with high evaluation values from the N individuals of the current generation. Further, the selection unit 211 may remove individuals whose evaluation values are smaller than a threshold value from the N individuals of the current generation. Thereby, the selection unit 211 can select a plurality of individuals whose evaluation values are equal to or greater than the threshold value from the N individuals of the current generation. Furthermore, the selection unit 211 may determine which individuals to remove from the N individuals of the current generation, depending on how much each individual satisfies the constraint conditions (the amount of constraint violations).

The control unit 204 controls to repeat the processing of steps S1005 and S1006 until the next generation of N individuals is generated. That is, once the next generation of N individuals is generated, the process advances to step S1007.

In step S1005, the crossover processing unit 212 selects two individuals from the plurality of individuals selected by the selection unit 211 in step S1004. Then, the crossover processing unit 212 generates one next-generation individual by performing crossover processing using the two selected individuals. Details of the process in step S1005 will be described later using the flowchart of FIG. 8A.

In step S1006, the mutation processing unit 213 performs mutation processing using one individual generated by the crossover process with a specific probability (for example, a probability of 0.5%). Generate the next generation of individuals. Details of the process in step S1006 will be described later using the flowchart in FIG. 8B.

In step S1007, the control unit 204 updates the N individuals of the current generation. Specifically, the control unit 204 treats the N individuals of the next generation generated by the generation unit 203 as N individuals of the current generation.

(Evaluation value calculation process; S1002)
Details of the evaluation value calculation process performed by the evaluation unit 202 will be described with reference to the flowchart in FIG. 7. Note that the processing in the flowchart of FIG. 7 is performed individually for each of the N individuals of the current generation. Below, a case will be described in which the process of the flowchart in FIG. 7 is performed for the individual X1.

In step S2001, the evaluation unit 202 determines, from the chromosomes of each product of the individual X1, how many warehouses each product is placed in (index α). For example, in individual X1 shown in FIG. 3, the chromosomes of product B(1) include six numbers of "1", so it can be determined that product B(1) is placed in six warehouses. On the other hand, since the chromosome of product B(2) includes three numbers of "1", it can be determined that product B(2) is placed in three warehouses. Then, the evaluation unit 202 calculates the average value (index α) of the warehouses where the product is placed per one type of product as the management cost. In the example of individual X1 in Figure 3, product B (1) is placed in six warehouses, product B (2) is placed in three warehouses, and product B (3) is placed in three warehouses. , Product B (4) is placed in six warehouses, so the average value is 4.5. Note that the index α may be any index as long as it indicates the management cost of the warehouse (product). In addition, in the inventory location information (chromosomes) for each product, if each gene indicates the lower limit of the number of products in each warehouse, the management cost is, for example, the total number of products arranged. .

In step S2002, the evaluation unit 202 acquires shipping performance data indicating the past product shipping performance for a predetermined period. For example, the shipping record data is data in which information on shipped (delivered) products and information on the orderer's address (product delivery destination) are associated for each shipment (each order) over a predetermined period in the past. I have just that much. These pieces of information are stored in advance in a storage medium of the information processing device 1 or the like.

In step S2003, the evaluation unit 202 calculates the shipping cost for each shipment based on the chromosome information of the individual X1 and the shipping record data. For example, a method of calculating the shipping delivery cost when an orderer as shown in FIG. 1 orders product B(1) and product B(4) will be described. Then, products B(1) to B(3) are placed in warehouse A(1) closest to the orderer's address, and product B(1) is placed in warehouse A(2), which is the second closest to the orderer's address. , B(3) and place products B(2) and B(4) in warehouse A(3), which is the third closest to the orderer's address. Assume. In this case, product B (1) will be delivered to the orderer from warehouse A (1) closest to the orderer's address, and product B (4) will be delivered to the orderer from warehouse A (3). The orderer can receive each item as soon as possible. Therefore, in this case, the effort required for delivery is equal to the distance D1 from warehouse A (1) to the orderer's address and the distance D3 from warehouse A (3) to the orderer's address. Become. Therefore, for example, the evaluation unit 202 calculates the sum of D1 and D3 as the delivery cost in this case.

On the other hand, for example, if an orderer as shown in Figure 1 orders product B (1) and product B (3), both products will be delivered to the orderer's address from warehouse A (1). , each item will be delivered to the orderer as soon as possible. Therefore, for example, the evaluation unit 202 calculates the distance D1 from the warehouse A(1) to the orderer's address as the delivery cost in this case.

Note that the evaluation unit 202 may calculate the delivery cost for each shipment by taking various other factors into consideration. For example, the evaluation unit 202 may consider the weight and size of each product, whether the product can be shipped at the same time as other products, the number of processing steps required for each shipment, and the like. In other words, the shipping cost may be any cost that increases as the effort or expense required for each delivery (each shipment) increases. In addition, regarding the shipping method, rather than shipping each item so that it reaches the orderer as soon as possible, for example, it is possible to ship multiple ordered items at once even if the warehouse is far from the orderer's address. It may be shipped with emphasis on

In step S2004, the evaluation unit 202 calculates the total value (index β) of the delivery costs calculated for each shipment in step S2003.

In step S2005, the evaluation unit 202 calculates the "average value of the warehouse where the product is located per one type of product" (index α) calculated in step S2001 and the "total value of delivery costs" calculated in step S2004. ” (index β), the evaluation value of individual X1 is calculated. For example, the evaluation unit 202 calculates a value obtained by dividing the predetermined value Th by the product of the index α and the index β = Th/αβ as the evaluation value. Alternatively, for example, the evaluation value may be a value obtained by dividing the predetermined value Th by the sum of the index α and the index β = Th/(α+β). Note that the evaluation unit 202 may calculate the evaluation value using any method as long as the smaller the index α is, the higher the evaluation value is calculated, and the smaller the index β is, the higher the evaluation value is calculated.

Note that in the above, the evaluation unit 202 calculates two values: "the average value of the number of warehouses in which each type of product is located" (index α) and "the total value of delivery costs" (index β). Although the evaluation value of individual X1 was calculated based on the index, other indexes may be used. For example, the evaluation unit 202 may calculate the evaluation value of the individual X1 as the index α (management cost) based on the variance of the number of product types in each warehouse. Furthermore, for example, the evaluation unit 202 may calculate the evaluation value such that the evaluation value of the individual X1 becomes higher as the number of warehouses in which no one type of product is placed is higher. If there is a warehouse that does not store even one type of product, the warehouse can be used for other purposes, or the warehouse itself can be eliminated, allowing businesses to make efficient use of their assets.

Furthermore, in step S2005, the evaluation unit 202 may evaluate whether each individual corresponds to a non-inferior solution in the Pareto solution analysis, using the two indicators α and β as evaluation values. A non-inferior solution means that there is no other individual in which both the index α and the index β are lower than the individual to be evaluated (that is, all evaluations are superior). For example, for three individuals, for individual X1, the index α = 4 and β = 5, for individual X2, the index α = 3, β = 7, and for individual X3, the index α = 5, β = 6. shall be. In this case, since there is no individual for which both the indices α and β are lower than the individual X1, the individual X1 can be evaluated as a non-inferior solution. Similarly, individual X2 can also be evaluated as a non-inferior solution. On the other hand, since both the indices α and β of the individual X1 are lower than those of the individual X3, the individual X3 can be evaluated as not being a non-inferior solution (being an inferior solution). Note that even in this case, the number of indicators may be three or more instead of two. Further, when evaluating whether each individual is a non-inferior solution in this way, for example, in step S1004, the selection unit 211 deletes an individual corresponding to an inferior solution from among the N individuals, Select only individuals that correspond to non-inferior solutions.

(Processing of the crossover processing unit; Step S1005)
Details of the process performed by the crossover processing unit 212 in step S1005 will be described with reference to the flowchart in FIG. 8A.

In step S3001, the crossover processing unit 212 selects two individuals from the plurality of individuals selected by the selection unit 211 in step S1004. At this time, the crossover processing unit 212 may select two individuals at random, or may select two individuals by increasing the probability that an individual with a higher evaluation value will be selected.

In step S3002, the crossover processing unit 212 randomly determines a crossover point for each group of products based on the group information stored in the attribute storage unit 205. Therefore, the same intersection point is determined for products belonging to the same group. Note that the crossover processing unit 212
The method may be divided into cases in which the crossover points are determined for each group of products according to a predetermined probability, and cases in which the crossover points for each chromosome of P types of products are randomly determined. For example, in step S3002, the crossover processing unit 212 determines a crossover point for each product group with a probability of 80%, and randomly determines a crossover point for each chromosome of P types of products with a probability of 20%. You may do so with a probability of According to this, the same processing is not always performed on the chromosomes of a plurality of products belonging to the same group, making it easier to generate chromosomes that also take into account the unique characteristics of each product.

In step S3003, the crossover processing unit 212 performs crossover processing on the chromosomes of each product using the two individuals selected in step S3001. At this time, the crossover processing unit 212 performs crossover processing on the chromosomes of each product based on the crossover point determined in step S3002. Thereby, the crossover processing unit 212 generates one next-generation individual. In other words, the same crossover process is performed for chromosomes of products belonging to the same group.

For example, assume that the crossover processing unit 212 selects individual X2 as the first individual in step S3001, selects individual X1 as the second individual, and generates the next generation individual Xa (FIG. 9 reference). In this case, in step S3002, the crossover processing unit 212 determines the position between the 4th column and the 5th column as the crossover point for the group G1 to which product B(1) and product B(4) belong. , it is assumed that the position between the 5th column and the 6th column is determined as the intersection point for group G2 to which product B(2) belongs. At this time, as shown in FIG. 9, for product B(1), the crossover processing unit 212 uses the genes in the 1st to 4th columns of the chromosome of product B(1) of individual X2 and the product B(1) of individual X1. The chromosome of individual Xa is generated by multiplying the genes in the fifth column and subsequent rows of the chromosome in 1). Similarly, for product B(4), the crossover processing unit 212 uses the genes in columns 1 to 4 of the chromosome of product B(4) of individual X2 and the genes in columns 5 of the chromosome of product B(4) of individual X1. The chromosomes of individual Xa are generated by multiplying with the genes from the second order onwards. On the other hand, for product B(2), the crossover processing unit 212 uses the genes in columns 1 to 5 of the chromosome of product B(2) of individual X2 and the genes in columns 6 of the chromosome of product B(2) of individual X1. The chromosomes of individual Xa are generated by multiplying with the genes from the second order onwards.

In step S3004, the crossover processing unit 212 determines whether the individuals generated in step S3003 satisfy the same constraint conditions as in the acquisition of N individuals in step S1001. If it is determined that the constraint conditions are satisfied, the processing of this flowchart ends. If it is determined that the constraint condition is not satisfied, the process returns to step S3002. Note that if it is determined that the constraint condition is not satisfied, the process may return to step S3001. Note that the process of this flowchart may end after the crossover process is performed in step S3003 without performing the process in step S3004. In other words, the process of this flowchart may end even if the individual generated in step S3003 does not satisfy the constraint conditions.

(Processing of mutation processing unit; step S1006)
Details of the process performed by the mutation processing unit 213 in step S1006 will be described with reference to the flowchart in FIG. 8B.

In step S4001, the mutation processing unit 213 determines whether to perform mutation processing on one individual generated by crossover processing, based on a preset probability. For example, the mutation processing unit 213 determines that mutation processing will not be performed with a probability of 99.5%, and determines that mutation processing will be performed with a probability of 0.5%. If it is determined that mutation processing is to be performed, the process advances to step S4002. If it is determined that mutation processing is not to be performed, the processing of this flowchart ends. When the process of this flowchart ends, the mutation processing unit 213 determines the individual generated by the crossover process as the next generation individual.

In step S4002, the mutation processing unit 213 randomly determines mutation target positions (genetic loci) for each group stored in the attribute storage unit 205. Therefore, the same mutation target position (genetic locus) is determined for products belonging to the same group.

In step S4003, the mutation processing unit 213 performs mutation processing on the chromosome of each product using one individual generated by the crossover processing. At this time, the mutation processing unit 213 performs mutation processing on the target position determined in step S4002 for the chromosome of each product. Thereby, the mutation processing unit 213 generates one next-generation individual. In other words, the chromosomes of products belonging to the same group are subjected to the same mutation process.

For example, assume that the mutation processing unit 213 selects the individual X2 in step S4001 and generates the next generation individual Xb (see FIG. 10). In this case, in step S4002, the mutation processing unit 213 determines the genetic locus in the fourth column as the mutation target position for group G1 to which product B(1) and product B(4) belong, and Assume that the genetic locus in the 6th column for group G2 to which B(2) belongs has been determined as the mutation target position. At this time, as shown in FIG. 10, for product B(1), the mutation processing unit 213 inverts the gene in the fourth column of product B(1) of individual X1, thereby changing the chromosome of individual Xb. generate. Similarly, for product B(4), the mutation processing unit 213 generates the chromosome of individual Xb by inverting the gene in the fourth column of the chromosome of product B(4) of individual X1. On the other hand, for product B(2), the mutation processing unit 213 generates the chromosome of individual Xb by inverting the gene in the sixth column of the chromosome of product B(2) of individual X1.

In step S4004, the mutation processing unit 213 determines whether the individuals generated in step S4003 satisfy the same constraint conditions as in the acquisition of N individuals in step S1001. If it is determined that the constraint conditions are satisfied, the processing of this flowchart ends. If it is determined that the constraint condition is not satisfied, the process returns to step S4002. Note that the process in this flowchart may end after the mutation process is performed in step S4003 without performing the process in step S4004. In other words, the process of this flowchart may end even if the individual generated in step S4003 does not satisfy the constraint conditions.

According to the first embodiment, the same crossover process and the same mutation process are performed on the chromosomes of products (items) that are highly similar to each other. Therefore, in individuals (solutions) that are processed using a genetic algorithm (evolutionary calculation algorithm), products that are similar to each other tend to have similar chromosomes. In other words, products that are similar to each other are more likely to be placed in the same warehouse.

This is consistent with the finding that products that are similar to each other are likely to be ordered at the same time, so it is preferable to place them in the same warehouse. Therefore, when placing products in each of a plurality of warehouses, the convergence of the evaluation values of the genetic algorithm (evolutionary calculation algorithm) increases. Furthermore, since it is sufficient to determine one crossover point and one mutation target position for each group, the process of determining the crossover point and mutation target position can be simplified. Therefore, even if one inventory location information set (condition information set; individual) has inventory location information (condition information; chromosomes) for many elements (products; items),
Optimization processing can be performed efficiently.

In the first embodiment, the information processing device 1 performs the same crossover process and the same mutation process on chromosomes of products belonging to the same group. However, the information processing device 1 may perform the same processing on the chromosomes of products belonging to the same group by performing only one of the same crossover processing and the same mutation processing.

Further, in the first embodiment, the number of individuals in each generation is set to a fixed value (=N), but the number of individuals may be different for each generation. For example, the value of N may become smaller or larger as the generations progress.

(Modification 1)
Note that the optimization process is not limited to the process shown in the flowchart shown in FIG. The optimization process may be the process shown in the flowchart shown in FIG. At this time, in FIG. 11, steps S5001 to S5004 are performed instead of steps S1004 to S1006 shown in FIG. Below, only the processing of steps S5001 to S5004 will be explained. Note that the processing in steps S5001 to S5004 is repeatedly executed under the control of the control unit 204 until the generation of N individuals of the next generation is completed.

In step S5001, the control unit 204 controls the step to proceed to any one of steps S5002 to S5004 based on the branch probability. Here, the branch probability may be set in advance by the user, or may change as the generation of the individual progresses. For example, the branching probabilities are such that the probability of proceeding to step S5002 (selection process) is 50%, the probability of proceeding to step S5003 (crossover process) is 49.5%, and the probability of proceeding to step S5004 (mutation process) is 50%. The probability is set to be 0.5%.

In step S5002, the selection unit 211 selects one of the N individuals of the current generation as the next generation individual. Here, the selection unit 211 increases the probability of selecting the individual as the next generation individual, for example, the higher the evaluation value of the individual. Furthermore, the selection unit 211 may select an individual with the highest evaluation value among the N individuals that have not yet been selected.

In step S5003, the crossover processing unit 212 selects two individuals from the N individuals of the current generation. Then, as in steps S3002 to S3004 (see FIG. 8A), the crossover processing unit 212 generates one next-generation individual by performing crossover processing using the two selected individuals.

In step S5004, the mutation processing unit 213 randomly selects one individual from among the N individuals of the current generation. Then, similarly to steps S4002 to S4004 (see FIG. 8B), the mutation processing unit 213 generates one next-generation individual by performing mutation processing using the selected one individual. .

According to Modification 1, some individuals having excellent evaluation values among the N individuals of the current generation are also used as individuals of the next generation. Therefore, if an individual with an excellent evaluation value exists in the current generation, that individual can be left to the next generation. Therefore, it is possible to reduce the possibility that a particularly good individual will not ultimately remain among the N individuals, thereby increasing the possibility that a better individual can be determined in the optimization process.

(Other embodiments)
In the above example, regarding a company that delivers products from a warehouse to an orderer in response to an order from an orderer, products of P types (P>2) are placed in Q locations (Q>2) of warehouses. explained. On the other hand, this is an example of optimization using an evolutionary calculation algorithm, in which chromosomes (condition information) are set for each of multiple elements of each individual (condition information set), and multiple elements that are similar to each other The present invention is applicable to any example in which it is envisaged that the chromosomes of the chromosomes are optimized to similar chromosomes.

For example, when placing P types of books in Q stores (bookstores), the number of types of books per store and the predicted sales at all stores based on the individual's chromosomes and past performance are calculated. An example of determining an individual with a high evaluation value based on the following may be used. In this case, the individual has chromosomes that indicate whether each type of book is placed in Q stores. Book attributes include, for example, genre (novel, manga, magazine, etc.), author's name, release date, and the like.

For example, when P types of movies are shown at Q movie theaters, "types of movies to be screened per movie theater" and "all movies according to the individual's chromosomes and performance in the past week" are determined. An example of determining an individual with a high evaluation value based on "predicted sales at a store" may also be used. In this case, the movie attributes include, for example, genre (anime, Japanese movie, foreign movie, etc.), director, studio, and the like.

The configurations and processes described in each embodiment of the present invention described above can be used in arbitrary combination with each other.

1: Information processing device, 201: Acquisition unit, 202: Evaluation unit,
203: generation unit, 204: control unit, 205: attribute storage unit,
211: Selection unit, 212: Crossover processing unit, 213: Mutation processing unit

Claims (9)

An information processing device that determines conditions of multiple elements using an evolutionary calculation algorithm,
Acquire a plurality of condition information sets including condition information for each of the plurality of elements, evaluate each of the plurality of condition information sets, and perform crossover processing and mutation processing to obtain the next generation of the plurality of condition information. and determining means for determining conditions of the plurality of elements by repeatedly generating a set,
The crossover process is a process of crossing condition information of the same elements in two condition information sets,
If the first element and the second element among the plurality of elements satisfy a predetermined relationship according to the degree of similarity, when performing the crossover process, the determining means determines that the first element is When performing the crossover process on the condition information and when performing the crossover process on the condition information of the second element , the condition information of the first element and the condition of the second element are the same at the same intersection point. performing the crossover processing on each piece of information ;
An information processing device characterized by: When performing the mutation process, the determining means determines whether the first element and the second element among the plurality of elements satisfy the predetermined relationship according to the degree of similarity. performing mutation on the condition information of the element and performing the same mutation on the condition information of the second element;
The information processing device according to claim 1, characterized in that: further comprising a control means for classifying the plurality of elements into a plurality of groups according to the degree of similarity between the plurality of elements,
The case where the first element and the second element satisfy the predetermined relationship according to the degree of similarity is the case where the first element and the second element are classified into the same group. is,
The information processing device according to claim 1 or 2, characterized in that: The control means determines the degree of similarity between the plurality of elements according to an attribute of each element.
The information processing device according to claim 3, characterized in that: The plurality of elements are mutually different types of products,
The attributes are information associated with each product, and include at least one of category, product name, manufacturer information, specifications, price, product description, and sales start date. The information processing device according to claim 4. The plurality of elements are mutually different types of products,
Condition information for each of multiple products indicates whether the product is in stock at each of multiple storage locations.
The information processing device according to claim 1 or 2, characterized in that: The determining means calculates an evaluation value for each of the plurality of condition information sets,
The evaluation value is a value based on the number of storage locations where each type of product is stored and the shipping cost of the product based on past shipping performance data.
7. The information processing apparatus according to claim 6. An information processing method for determining conditions of multiple elements using an evolutionary calculation algorithm,
Acquire a plurality of condition information sets including condition information for each of the plurality of elements, evaluate each of the plurality of condition information sets, and perform crossover processing and mutation processing to obtain the next generation of the plurality of condition information. a determining step of repeatedly generating a set to determine conditions for the plurality of elements;
The crossover process is a process of crossing condition information of the same elements in two condition information sets,
In the determining step, if the first element and the second element among the plurality of elements satisfy a predetermined relationship according to the degree of similarity, when performing the crossover process, the first element is When performing the crossover process on the condition information and when performing the crossover process on the condition information of the second element , the condition information of the first element and the condition of the second element are the same at the same intersection point. performing the crossover processing on each piece of information ;
An information processing method characterized by: A program for causing a computer to execute each step of the information processing method according to claim 8.

Images