The Aerospace Corporation

Timothy Guy Thompson

Matthew Phillip Ferringer

Ronald Scott Clifton

Marc David DiPrinzio

Kyle D Hanifen

Catherine F Horan

Systems and methods are provided for performing multi-objective optimizations with a relatively large number of objectives to which optimization is to be performed. The objectives of the optimization problem may be partitioned to two or more subsets (e.g., overlapping or non-overlapping subsets) of objectives, and partial optimization(s) may be performed using a subset or combination of subsets of the objectives. One or more of the partial optimizations may use one or more pareto-optimized chromosomes from a prior partial optimization. A final full optimization may be performed according to all of the objectives of the optimization problem and may use one or more chromosomes of any preceding partial optimization as a starting point for finding a final solution to the optimization problem. Any variety of processes may be employed to mitigate archive explosion that may be associated with relatively large objective sets.

Progressive objective addition in multi-objective heuristic systems and methods

Systems and methods are provided for operating to an initial optimized baseline solution to a multi-objective problem. As the initial optimized baseline solution is determined, some regions, such as local or global maxima, minima, and/or saddle points in the objective space may be mapped. The mapping may be performed by storing mesh chromosomes corresponding to some of the features (e.g., extrema, saddle points, etc.) in the objective space along with the location of those chromosomes within the objective space (e.g., objective values corresponding to each of the objectives). The mesh chromosome may be used in subsequent re-optimization problems, such as with reformulation. Although in a re-optimization the objectives, decision variables, and or objective/constraint models may change, the mesh chromosomes may still provide information and direction for more quickly and/or with reduced resources converge on a re-optimized solution.

Systems and methods for multi-objective optimizations with objective space mapping

Systems and methods are provided for providing an optimized solution to a multi-objective problem. Potential solutions may be generated from parent solutions to be evaluated according to multiple objectives of the multi-objective problem. If the potential solutions are infeasible, the potential solutions may be perturbed according to a perturbation model to bring the potential solution to feasibility, or at least a reduced level of constraints. The perturbation models may include a weight vector that indicates the amount of perturbation, such as in a forward and/or reverse direction, of decision variables of the potential solutions. In some cases, the perturbation models may be predetermined. In other cases, the perturbation models may be learned, such as based on training constraint data. Additionally, potential solutions may be generated in a secondary optimization where a constraint based optimization may be performed to drive to generating a feasible solution for further evaluation according to objective values.

Systems and methods for multi-objective optimizations with decision variable perturbations

Systems and methods are provided for generating an initial optimized baseline solution to a multi-objective problem. As the baseline solution is implemented, live (e.g., real-time or near real-time) data associated with one or more parameters may be received and compared to expectations of those parameters with the implementation of the initial optimized solution. If a deviation is detected between the expectation of the time progression of the parameters and live data associated with the parameter, then that deviation may be compared to a threshold. If the deviation meets a threshold condition, then an irregular operation may be declared and a new baseline solution may be implemented. The new baseline solution may be obtained as a re-optimized solution.

Systems and methods for multi-objective optimizations with live updates

Systems and methods are provided to engage in multi-objective optimization where there may be potential solutions for evaluation (e.g., chromosomes) that each have one or more conditional genes. The value of each of the conditional genes in each of the chromosomes may be equivalent to one of a plurality of hidden genes in each of the chromosomes. The value of each of the conditional genes may be evaluated prior to determining objective values of each of the chromosomes. The objective values of each of the chromosomes may be used to evaluate the potential solutions embodied in the chromosomes and further drive to more optimized solutions. The use of the conditional genes in the chromosomes may reduce the amount of constraint violation checks that may need to be performed.

Systems and methods for multi-objective heuristics with conditional genes

Systems and methods are provided to engage in multi-objective optimization where there may be one or more constraints. At least one of the constraints may be soft constraints, such that if a potential solution to the multi-objective optimization problem violates only soft constraint(s), then that potential solution may be allowed to persist in a population of potential solutions that may be used to propagate child potential solutions. Potential solutions that violate soft constraints may be tested for non-domination sorting against other potential solutions that violate soft constraints and based at least in part on values associated with the soft constraint violations.

Systems and methods for multi-objective evolutionary algorithms with soft constraints

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.

Systems and methods for multi-objective evolutionary algorithms with category discovery

Systems and methods are provided to determine launch parameters of satellites of a satellite constellation that provides optimized performance of the satellite constellation over the service lifetime of the satellite constellation. The launch parameters may be determined by considering perturbing accelerations of one or more of the satellites for the purposes of optimizing the launch parameters of the satellites of the satellite constellation. The systems and methods may include heuristic optimization and high-fidelity astrodynamic modeling methodologies.

Systems and methods for optimizing satellite constellation deployment

Systems and methods are provided to enable vector scalability in evolutionary algorithms to enable execution of optimization problems having a relatively large number of variables. A subset of the total number of variables of a chromosome data structure may be considered relative to a baseline known solution for the purpose of evaluating one or more objective functions of the evolutionary algorithm.

Systems and methods for vector scalability of evolutionary algorithms

Systems and methods may include identifying an input population of parent epsilon chromosome data structures; combining genes of each selected pair of parent epsilon chromosome data structures according to at least one evolutionary operator to generate a plurality of child epsilon chromosome data structures, each child epsilon chromosome data structure providing one or more genes each having a respective candidate epsilon value representing a respective step size or spacing for the respective problem objective; and evaluating each of the plurality of child epsilon chromosome data structures according to one or more epsilon objective functions to generate respective epsilon objective function values for each child epsilon chromosome data structure, where each epsilon objective function is associated with a respective goal associated with at least one a priori criterion, where each respective epsilon objective function value indicates an extent to which each respective goal can be achieved.

Systems and methods for auto-adaptive control over converged results for multi-dimensional optimization

Embodiments of the invention may provide systems and methods for supporting restricted search capabilities in high-dimensional spaces. These example restricted search capabilities may allow for an unbiased search that is simply restricted to those regions of interest to a decision maker. It will be appreciated that a restricted search does not mean that additional constraints, such as preference or biasing information, are utilized to reduce the search space into some feasible sub-space of the original optimization problem. Instead, the example restricted search may limit the search to a certain sub-space of the full multi-dimensional tradeoff space.

Systems and methods for supporting restricted search in high-dimensional spaces

Systems and methods may include an application program interface that enables a user to: specify parameters associated with an evolutionary algorithm, where an execution of the evolutionary algorithm is in accordance with the specified parameters; define a chromosome data structure that includes a plurality of variables that are permitted to evolve in value in accordance with the execution of the evolutionary algorithm in order to generate one or more child chromosome data structures; identify one or more objective functions for evaluating chromosome data structures, including the generated one or more child chromosome data structures; and define an output format for providing one or more optimal chromosome data structures of the evaluated generated child chromosome data structures as designs to the identified objective functions.

Systems and methods for an application program interface to an evolutionary software program

Systems and methods may include receiving a respective plurality of objective function values for each chromosome data structure of a population, where the respective plurality of objective function values are obtained based upon an evaluation of each chromosome data structure; mapping the respective objective function values to respective epsilon values, where the respective epsilon values define a respective address associated with the plurality of objective functions; and performing non-domination sorting of the population to generate a reduced population of chromosome data structures; and performing epsilon non-dominated sorting to identify an elite set of addresses, where the prior steps are performed for a current generation, where the elite set of addresses are compared to a prior elite set of addresses for a predetermined number of prior generations to determine one or more variance values, where the one or more variance values are utilized to determine whether a current job of an evolutionary algorithm is to be halted.

Systems and methods for box fitness termination of a job of an evolutionary software program

Systems and methods may include receiving a pair of parent chromosome data structures, where each parent chromosome data structure provides a plurality of genes representative of variables that are permitted to evolve; combining genes of the two parent chromosome data structures to generate at least one first child chromosome data structure; evaluating the at least one first child chromosome data structures according to a plurality of constraint functions to generate a respective plurality of constraint function values for each of the at least one first child chromosome data structure, where the constraint functions define constraints on a feasible solution set; determining whether any of the at least one first child chromosome data structure is within the feasible solution set.

Growing community of inventors

Purcellville, VA, United States of America

Timothy Guy Thompson