Systems and Methods for Multi-Objective Evolutionary Algorithms with Category Discovery

Patent metadata

Field	Value
Publication number	US-2017011292-A1
Application number	US-201514796299-A
Country	US
Kind code	A1
Filing date	Jul 10, 2015
Priority date	Jul 10, 2015
Publication date	Jan 12, 2017
Grant date	—

Abstract

Systems and methods are provided to engage in multi-tiered optimization where there may be a first multi-objective optimization and a second constraint optimization. The multi-objective optimization may be used to drive to one or more goals of the optimization problem. The constraint optimization or minimization may be used to drive towards a reduced and/or no constraint situation where the solution to the overall problem is feasible or near-feasible.

First claim

That which is claimed:

1 . A method, comprising:
identifying, by one or more processors, a plurality of items, including a first item and a second item; identifying, by the one or more processors, a plurality of categories, including a first category and a second category; providing, by the one or more processors, a first allocation of items by allocating the first item to the first category and the second item to the second category; identifying, by the one or more processors, one or more constraint models; determining, by the one or more processors and based at least in part on the one or more constraint models, that the first allocation of items is infeasible; providing, by the one or more processors, a second allocation of items by allocating the first item to a third category; determining, by the one or more processors and based at least in part on the one or more constraint models, that the second allocation is feasible; and providing, by the one or more processors, the second allocation as a feasible solution to a multi-objective optimization problem.

2 . The method of claim 1 , further comprising:
determining a first chromosome based at least in part on the second allocation; identifying at least one objective model; determining a set of objective values based at least in part on the at least one objective model and the first chromosome; and comparing the set of respective objective values to one or more other sets of respective objective values to determine that the first chromosome is an optimized solution to the multi-objective optimization problem.

3 . The method of claim 2 , wherein determining that the first chromosome is an optimized solution to the multi-objective optimization problem comprises:
identifying that the respective objective values are not dominated by the one or more other sets of respective objective values.

4 . The method of claim 1 , wherein determining that the second allocation is feasible comprises:
determining a first constraint value corresponding to the first item, based at least in part on the third category and the one or more constraint models; determining a second constraint value corresponding to the second item, based at least in part on the second category and the one or more constraint models; identifying that the first constraint value satisfies a first threshold condition; and identifying that the second constraint value satisfies a second threshold constraint.

5 . The method of claim 4 , wherein determining that the second allocation is feasible further comprises identifying that a plurality of items, including the first item and the second item, are allocated to respective categories, such that respective constraints corresponding to each of the plurality of items meets a respective threshold condition.

6 . The method of claim 1 , wherein the multi-objective optimization problem is a pricing problem and the first item is a first product type to be priced at a first price and the second item is a second product type that is to be priced at a second price, wherein the first price corresponds to the first category and the second price corresponds to the second category.

7 . The method of claim 1 , wherein the first allocation is generated based at least in part on a third allocation and a fourth allocation.

8 . The method of claim 7 , wherein the third allocation and fourth allocation are received from an objective optimization engine.

9 . The method of claim 7 , wherein the first allocation is generated by blending the third allocation and the fourth allocation, wherein blending comprises selecting one or more first item allocations selected from the third allocation and combining the one or more first item allocations with one or more second item allocations selected from the fourth allocation.

10 . The method of claim 1 , wherein determining that the first allocation of items is infeasible comprises determining that the first item allocated to the first category results in a constraint value that fails to meet a threshold condition and wherein providing the second allocation of items by allocating the first item to a third category is based at least in part on the determining that the first item allocated to the first category results in the constraint value that fails to meet the threshold condition.

11 . A system, comprising:
a memory that stores computer-executable instructions; at least one processor configured to access the memory, wherein the at least one processor is further configured to execute the computer-executable instructions to: identify a plurality of items, including a first item and a second item; identify a plurality of categories, including a first category and a second category; provide a first allocation of items by allocating the first item to the first category and the second item to the second category; identify one or more constraint models; determine, based at least in part on the one or more constraint models, that the first allocation of items is infeasible; provide a second allocation of items by allocating the first item to a third category; determine, based at least in part on the one or more constraint models, that the second allocation is feasible; and provide the second allocation as a feasible solution to a multi-objective optimization problem.

12 . The system of claim 11 , wherein the at least one processor is further configured to execute the computer-executable instructions to:
determine a first chromosome based at least in part on the second allocation; identify at least one objective model; determine a set of objective values based at least in part on the at least one objective model and the first chromosome; and compare the set of respective objective values to one or more other sets of respective objective values to determine that the first chromosome is an optimized solution to the multi-objective optimization problem.

13 . The system of claim 12 , wherein the at least one processor to determine that the first chromosome is an optimized solution to the multi-objective optimization problem comprises the at least one processor to identify that the respective objective values are not dominated by the one or more other sets of respective objective values.

14 . The system of claim 11 , wherein the at least one processor to determine that the second allocation is feasible comprises the at least one processor to:
determine a first constraint value corresponding to the first item, based at least in part on the third category and the one or more constraint models; determine a second constraint value corresponding to the second item, based at least in part on the second category and the one or more constraint models; identify that the first constraint value satisfies a first threshold condition; and identify that the second constraint value satisfies a second threshold constraint.

15 . The system of claim 14 , wherein the at least one processor to determine that the second allocation is feasible further comprises the at least one processor to identify that a plurality of items, including the first item and the second item, are allocated to respective categories, such that respective constraints corresponding to each of the plurality of items meets a respective threshold condition.

16 . The system of claim 11 , wherein the multi-objective optimization problem is a pricing problem and the first item is a first product type to be priced at a first price and the second item is a second product type that is to be priced at a second price, whe

Assignees

• Aerospace Corp

Inventors

• Thompson Timothy Guy

Classifications

• G06N3/126 Primary

  Evolutionary algorithms, e.g. genetic algorithms or genetic programming · CPC title