IPC분류정보
국가/구분 |
United States(US) Patent
등록
|
국제특허분류(IPC7판) |
|
출원번호 |
UP-0301155
(2005-12-12)
|
등록번호 |
US-7672910
(2010-04-21)
|
발명자
/ 주소 |
|
출원인 / 주소 |
|
대리인 / 주소 |
|
인용정보 |
피인용 횟수 :
10 인용 특허 :
2 |
초록
▼
An augmented Lagrangian genetic algorithm that may be used to generate solutions for optimization problems subject to linear, bound, and non-linear constraints is discussed. The augmented Lagrangian genetic algorithm uses an adaptive mutation operator to separately handle the linear, and bound const
An augmented Lagrangian genetic algorithm that may be used to generate solutions for optimization problems subject to linear, bound, and non-linear constraints is discussed. The augmented Lagrangian genetic algorithm uses an adaptive mutation operator to separately handle the linear, and bound constraints, and uses an augmented Lagrangian framework to handle non-linear constraints. The non-linear constraints are handled by creating a sub-problem without the linear and bound constraints and solving the sub-problem using Lagrange parameter estimates and a penalty factor. The exclusion of the linear constraints and boundary constraints from the sub-problem allows the sub-problem to be resolved in a more effective manner than is possible using conventional techniques.
대표청구항
▼
I claim: 1. In a computing device hosting a technical computing environment used to process constrained optimization problems, a computer-implemented method of performing constrained optimization, comprising: providing a first population of a plurality of individuals for an optimization problem for
I claim: 1. In a computing device hosting a technical computing environment used to process constrained optimization problems, a computer-implemented method of performing constrained optimization, comprising: providing a first population of a plurality of individuals for an optimization problem for a modeled system, the optimization problem including non-linear constraints, linear constraints and bound constraints, the individuals being individual solutions to the optimization problem; formulating a sub-problem from the optimization problem that excludes the linear and bound constraints and includes the non-linear constraints; solving, using the computing device, the sub-problem using a penalty parameter and at least one Lagrange parameter estimate to solve the optimization problem; generating, based on the solution to the sub-problem, a second population of individuals; storing the second population in a computer-readable storage medium, the second population available for use with the modeled system; minimizing, using the computing device, a sequence of the sub-problem to an approximate solution; determining, using the computing device, whether the approximate solution to the sub-problem is minimized to a pre-determined accuracy and whether the approximate solution to the sub-problem satisfies a feasibility condition; increasing, using the computing device, said at least one Lagrangian parameter estimate based on a determination that the approximate solution to the sub-problem is minimized to the pre-determined accuracy and that the approximate solution to the sub-problem satisfies the feasibility condition; and increasing, using the computing device, the penalty parameter in the sub-problem based on a determination that the sub-problem is not minimized to the pre-determined accuracy or that the sub-problem does not satisfy the feasibility condition. 2. The method of claim 1, further comprising: repeating until a stopping criteria is achieved the steps of: minimizing a sequence of the sub-problem to an approximate solution; determining whether the approximate solution to the sub-problem is minimized to a pre-determined accuracy and whether the approximate solution to the sub-problem satisfies a feasibility condition; and increasing, based on a determination that the approximate solution to the sub-problem is minimized to a pre-determined accuracy and that the approximate solution to the sub-problem satisfies a feasibility condition, said at least one Lagrange parameter estimate. 3. The method of claim 1 wherein the at least one Lagrangian parameter estimate is a multiplier for a linear constraint. 4. The method of claim 1 wherein the at least one Lagrangian parameter estimate is a multiplier for a bound constraint. 5. The method of claim 1, further comprising separately solving for the linear and bound constraints, the solving including: selecting an individual for mutation from the first population; generating programmatically an initial step size; generating programmatically a plurality of mutation direction vectors based on the linear and bound constraints, the plurality of mutation direction vectors extending from a plotted location representing the individual selected for mutation generating programmatically a mutated individual along a randomly chosen one of the plurality of mutation direction vectors a distance equal to the initial step size from the plotted location representing the individual selected for mutation; assessing programmatically whether the mutated individual is in a feasible region, the feasible region representing a region encompassing acceptable solutions to the optimization problem considering the linear and bound constraints, wherein the assessing includes: storing the mutated individual as part of second population in a computer-readable medium based on an assessment that the mutated individual is in a feasible region; or based on an assessment that the mutated individual is not in a feasible region, iteratively mutating a different mutated individual along the chosen mutation direction vector using a step size programmatically reduced from the initial step size and assessing whether the different mutated individual is in the feasible region until a different mutated individual is assessed to be in the feasible region, the reduced step size based on the linear and bound constraints; and storing the different mutated individual as part of a second population in a computer-readable medium based on an assessment that the different mutated individual is in a feasible region. 6. The method of claim 5, further comprising: generating a plurality of mutation direction vectors after selecting the individual for mutation; and generating a different mutated individual along each of the plurality of mutation direction vectors using the initial step size. 7. The method of claim 6, further comprising: assessing programmatically each mutated individual generated along the plurality of mutation direction vectors to determine whether each mutated individual is in a feasible region, the feasible region representing an acceptable solution to the optimization problem considering the linear and bound constraints; identifying at least one mutated individual that is not in a feasible region on its selected mutation direction vector; for each of the identified individuals, mutating another individual along the selected mutation direction vector using a second step size programmatically reduced from the initial step size. 8. The method of claim 5, further comprising: based on a programmatic assessment that the individual mutated using the second step size is not in a feasible region, mutating another individual along the mutation direction vector using a different step size programmatically reduced from the step size used in the previous mutation. 9. The method of claim 5, further comprising: generating programmatically, in response to the generation of a reduced step size, at least one new mutation direction vector and at least one new mutated individual for the new mutation direction. 10. The method of claim 1 wherein the sub-problem is solved in parallel using a plurality of computing devices. 11. A computing apparatus hosting a technical computing environment used to process constrained optimization problems, the computing apparatus comprising: a processor configured to process: a first population of individual solutions for an optimization problem for a modeled system that includes non-linear constraints, linear constraints and bound constraints, a genetic algorithm that solves a sub-problem that includes the non-linear constraints and excludes the linear constraints and bound constraints, the sub-problem solved using at least one Lagrangian parameter estimate and a penalty parameter, wherein the genetic algorithm minimizes a sequence of the sub-problem to an approximate solution and determines whether the approximate solution to the sub-problem is minimized to a pre-determined accuracy and whether the approximate solution to the sub-problem satisfies a feasibility condition, wherein the genetic algorithm increases the at least one Lagrangian parameter estimate based on a determination that the approximate solution to the sub-problem is minimized to the pre-determined accuracy and that the approximate solution to the sub-problem satisfies the feasibility condition, and wherein the genetic algorithm increases the penalty parameter in the sub-problem based on a determination that the sub-problem is not minimized to the pre-determined accuracy or that the sub-problem does not satisfy the feasibility condition, and a second population of individual solutions for the optimization problem generated by the genetic algorithm; and a computer-readable storage medium for storing the second population, the second population available for use with the modeled system. 12. In a computing device hosting a technical computing environment used to process constrained optimization problems, a computer-readable storage medium holding computer-executable instructions for performing constrained optimization, the instructions comprising: instructions for providing a first population of a plurality of individuals for an optimization problem for a modeled system, the optimization problem including non-linear constraints, linear constraints and bound constraints; the individuals being individual solutions to the optimization problem; instructions for formulating a sub-problem from the optimization problem that excludes the linear constraints and bound constraints and includes the non-linear constraints; instructions for solving the sub-problem using a penalty parameter and at least one Lagrangian parameter estimate to solve the optimization problem; instructions for generating, based on the solution to the sub-problem, a second population of individuals; instructions for storing the second population in a computer-readable storage medium, the second population available for use with the modeled system; instructions for minimizing a sequence of the sub-problem to an approximate solution; instructions for determining whether the approximate solution to the sub-problem is minimized to a pre-determined accuracy and whether the approximate solution to the sub-problem satisfies a feasibility condition; instructions for increasing said at least one Lagrangian parameter estimate based on a determination that the approximate solution to the sub-problem is minimized to the pre-determined accuracy and that the approximate solution to the sub-problem satisfies the feasibility condition; and instructions for increasing the penalty parameter in the sub-problem based on a determination that the approximate solution to the sub-problem is not minimized to the pre-determined accuracy or that the approximate solution to the sub-problem does not satisfy the feasibility condition. 13. The medium of claim 12, wherein the instructions further comprise: instructions for repeating until a stopping criteria is achieved the steps of: minimizing a sequence of the sub-problem to an approximate solution; determining whether the approximate solution to the sub-problem is minimized to a pre-determined accuracy and whether the approximate solution to the sub-problem satisfies a feasibility condition; and increasing, based on a determination that the approximate solution to the sub-problem is minimized to a pre-determined accuracy and that the approximate solution to the sub-problem satisfies a feasibility condition, said at least one Lagrangian parameter estimate. 14. The medium of claim 12, wherein the instructions further comprise: instructions for selecting an individual for mutation from the first population; instructions for generating programmatically an initial step size; instructions for generating programmatically a plurality of mutation direction vectors based on the linear and bound constraints, the plurality of mutation direction vectors extending from a plotted location representing the individual selected for mutation; instructions for generating programmatically a mutated individual along a randomly chosen mutation direction vector a distance equal to the initial step size from the plotted location representing the individual selected for mutation; instructions for assessing programmatically whether the mutated individual is in a feasible region, the feasible region representing a region encompassing acceptable solutions to the optimization problem considering the linear and bound constraints, wherein the assessing includes: instructions for storing the mutated individual as part of second population in a computer-readable medium based on an assessment that the mutated individual is in a feasible region; or instructions for, based on an assessment that the mutated individual is not in a feasible region, mutating a different mutated individual along the chosen mutation direction vector using a step size programmatically reduced from the initial step size and assessing whether the different mutated individual is in the feasible region until a different mutated individual is assessed to be in the feasible region, the reduced step size based on the linear and bound constraints; and storing the different mutated individual as part of a second population in a computer-readable medium based on an assessment that the different mutated individual is in a feasible region. 15. The medium of claim 14, wherein the instructions further comprise: instructions for generating a plurality of mutation direction vectors after selecting the individual for mutation; and instructions for generating a different mutated individual along each of the plurality of mutation direction vectors using the initial step size. 16. The medium of claim 15, wherein the instructions further comprise: instructions for assessing programmatically each mutated individual generated along the plurality of mutation direction vectors to determine whether each mutated individual is in a feasible region, the feasible region representing an acceptable solution to the optimization problem considering the linear and bound constraints; instructions for identifying at least one mutated individual that is not in a feasible region on its selected mutation direction vector; for each of the identified individuals, instructions for mutating another individual along the selected mutation direction vector using a second step size programmatically reduced from the initial step size. 17. The medium of claim 14, wherein the instructions further comprise: instructions for mutating another individual along the chosen mutation direction vector using a different step size programmatically reduced from the step size used in the previous mutation based on a programmatic assessment that the individual mutated using the second step size is not in a feasible region. 18. The medium of claim 14, wherein the instructions further comprise: instructions for generating programmatically, in response to the generation of a reduced step size, at least one new mutation direction vector and at least one new mutated individual for the new mutation direction.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.