WO2025071627A1

WO2025071627A1 - Optimization using a genetic algorithm

Info

Publication number: WO2025071627A1
Application number: PCT/US2023/075617
Authority: WO
Inventors: Olumuyiwa Johnson Sanya; Justo Elias MATHEUS VALERO; Mounia CHEKKAI
Original assignee: Schlumberger Canada Ltd; Services Petroliers Schlumberger SA; Geoquest Systems BV; Schlumberger Technology Corp
Current assignee: Schlumberger Canada Ltd; Services Petroliers Schlumberger SA; Geoquest Systems BV; Schlumberger Technology Corp
Priority date: 2023-09-29
Filing date: 2023-09-29
Publication date: 2025-04-03
Anticipated expiration: 2026-03-29

Abstract

Certain aspects of the disclosure provide a method for solving an optimization problem using a genetic algorithm. The method generally includes generating chromosomes; performing iteratively until a termination condition is met; repairing one or more chromosomes that do not meet a first set of a plurality of constraints, determining a fitness score for each of the chromosomes based on at least one objective function and the plurality of constraints; identifying two or more parent chromosomes from the chromosomes using the fitness scores; generating child chromosome(s) from the parent chromosomes, wherein at least one child chromosome is mutated and does not meet a second set of the plurality of constraints; repairing the at least one child chromosome to comply with the second set of constraints; and replacing one or more of the chromosomes having lower fitness scores among the fitness scores determined for the chromosomes with the child chromosome(s).

Description

OPTIMIZATION USING A GENETIC ALGORITHM

BACKGROUND

Field

[0001] Aspects of the present disclosure relate to mathematical optimization, and in particular, to solving a portfolio selection and scheduling optimization problem using a genetic algorithm.

Description of Related Art

[0002] Optimization, also commonly referred to as “mathematical optimization,” is the quantitative process of selecting a “best” solution from a set of feasible solutions. Optimization problems arise in a myriad of disciplines including, but not limited to, medicine, manufacturing, logistics, supply chain, finance, government, physics, economics, and artificial intelligence (Al). For example, in finance, mathematical optimization may be used to choose an optimal mix of assets, which maximize after-tax returns while minimizing risk. As another example, in manufacturing, mathematical optimization may be used to efficiently schedule the production of goods in factories in order to efficiently meet customer orders. Further, mathematical optimization may be used to minimize the wait time for patients in a hospital setting before being seen by a doctor and/or help an electrical power distribution company choose a most cost-effective method for delivering electricity to customers.

[0003] In general, an optimization problem involves minimizing and/or maximizing an objective function of several variables (also referred to as “decisions variable”), which may be subject to restrictions defined by a set of constraints. Thus, optimization problems generally include three elements: (1) objective function(s), (2) decision variables, and (3) constraint(s). When solving optimization problems, values for the decision variables that maximize or minimize the objective function(s) and satisfy all constraint(s) are determined.

[0004] The first element, e.g., the objective function, defines the criterion for evaluating a solution. It is often a mathematical function of the decision variables that converts a solution into a numerical evaluation of that solution. For example, the objective function may be the expected return on a stock portfolio, a company’s production costs or profits, the time of arrival of a vehicle at a specified destination, the vote share of a political candidate, and/or the like. [0005] The second element, e.g., the collection of decision variables, are physical quantities controlled by the decision maker. The decision variables may take on any of a set of possible values that may be manipulated, when solving the optimization problem, to optimize the objective function. Example decision variables include the quantities and/or types of assets to be bought and/or sold, the amounts of resources to be allocated to various activities, the different routes that may be used by shipping companies to fulfill customer orders, the policies to be advocated by a political candidate, and/or the like.

[0006] The third element, e.g., the set of constraints, are a set of restrictions that represent physical, economic, technological, legal, ethical, and/or other limits on what numerical values can be assigned to the decision variables. Constraints may be used to control the range of each decision variable. Example constraints may be related to time, money, and/or resources.

[0007] Various optimization algorithms exist to solve mathematical optimization problems; however, no one optimization algorithm is superior for all optimization problems. Instead, choosing an optimization algorithm depends on, among other aspects, the problem characteristics, the admissible execution time, the available computational resources, and/or the necessity of finding a global optimal solution (e.g., a globally optimal solution is one where there are no other feasible solutions with better objective function values). Two categories of optimization algorithms that may be selected from, to solve optimization problems, include deterministic and stochastic optimization algorithms.

[0008] Deterministic optimization algorithms aim to find the global best result, providing theoretical guarantees that the returned result is the globally optimal result. Examples of methods that implement deterministic optimization include branch-and-bound, cutting plane, outer approximation, interval analysis, and/or the like. Deterministic optimization is proven to be beneficial for solving problems with clear exploitable features that help to compute the globally optimal result. However, deterministic algorithms may have problems tackling black-box problems and/or extremely complex and volatile optimization functions.

[0009] Stochastic optimization algorithms, on the other hand, do not guarantee finding the optimal result for a given problem; however, there is always a probability of finding the globally optimal result (e.g., the probability of finding the globally optimal result increases as the execution time increases). Stochastic optimization may be used to find the optimal solution to an optimization problem that involves uncertainty and/or randomness in the objective function, the constraints, and/or the variables. Stochastic optimization may be used to solve problems that are dynamic, robust, or adaptive. For example, one class of stochastic optimization algorithms includes genetic algorithms, which may be desired for solving problems such as, for example, portfolio selection and/or resource allocation.

SUMMARY

[0010] Certain aspects of the disclosure provide a method for solving an optimization problem using a genetic algorithm. The method generally includes generating a plurality of chromosomes for the optimization problem, wherein: each chromosome comprises a first plurality of genes, each gene represents one or more characteristics associated with a drilling opportunity, and each chromosome represents a solution to the optimization problem; performing iteratively until a termination condition for the genetic algorithm is met: determining whether each of the plurality of chromosomes meets a first set of a plurality of constraints, repairing one or more of the plurality of chromosomes determined not to meet the first set of the plurality of constraints, determining a fitness score for each of the plurality of chromosomes based on at least one objective function and the plurality of constraints; identifying two or more parent chromosomes of the plurality of chromosomes using the fitness score determined for each of the two or more parent chromosomes; generating one or more child chromosomes from the two or more parent chromosomes, wherein: each child chromosome comprises a second plurality of genes, the second plurality of genes comprising at least one gene from each of the two or more parent chromosomes, and at least one child chromosome of the one or more child chromosomes is mutated during the generation of the one or more child chromosomes and does not meet a second set of the plurality of constraints; repairing the at least one child chromosome to comply with the one or more constraints; and replacing one or more of the plurality of chromosomes having lower fitness scores among the fitness scores determined for the plurality of chromosomes with the one or more child chromosomes

[0011] Other aspects provide processing systems configured to perform the aforementioned methods as well as those described herein; non-transitory, computer-readable media comprising instructions that, when executed by a processors of a processing system, cause the processing system to perform the aforementioned methods as well as those described herein; a computer program product embodied on a computer readable storage medium comprising code for performing the aforementioned methods as well as those further described herein; and a processing system comprising means for performing the aforementioned methods as well as those further described herein.

[0012] The following description and the related drawings set forth in detail certain illustrative features of one or more aspects.

DESCRIPTION OF THE DRAWINGS

[0013] The appended figures depict certain aspects and are therefore not to be considered limiting of the scope of this disclosure.

[0014] FIG. 1A depicts an example system for solving an optimization problem using a genetic algorithm.

[0015] FIGS. IB and 1C depict example Gantt chart solutions generated by the example system in FIG. 1A.

[0016] FIG. 2 depicts example steps performed by an optimizer in the example system of FIG. 1A

[0017] FIGS. 3A-3F depict an example of using a genetic algorithm for selecting and scheduling multiple drilling opportunities from a pool of candidate drilling opportunities.

[0018] FIG. 4 depicts an example method of solving an optimization problem using a genetic algorithm.

[0019] FIG. 5 depicts an example processing system on which aspects of the present disclosure can be performed.

[0020] To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the drawings. It is contemplated that elements and features of one embodiment may be beneficially incorporated in other embodiments without further recitation. DETAILED DESCRIPTION

[0021] Genetic algorithms are adaptive heuristic search algorithms (e.g., algorithms that follow an iterative pattern that changes with time) premised on Charles Darwin’s evolutionary ideas of natural selection. Darwin’s theory of evolution by natural selection describes how organisms evolve over generations through the inheritance of physical and/or behavioral traits. According to the theory, individuals with traits that enable them to adapt to their environments will help them survive and have more offspring, and the offspring will inherit and therefore perpetuate those traits. Individuals with less adaptive traits will less frequently survive to pass them on. Over time, the traits that enable species to survive and reproduce will become more frequent in the population and the population will beneficially evolve.

[0022] Genetic algorithms search by simulating evolution, starting from an initial set of solutions for an optimization problem, and generating successive “generations” of solutions. The underlying idea is that “evolution” will find an optimal solution for the optimization problem after a number of successive generations — similar to natural selection.

[0023] For example, a genetic algorithm begins with a population of “individuals” in which each individual represents a possible solution to a particular optimization problem. An individual may be encoded as a finite length vector of components, or variables. With respect to the genetic analogy of genetic algorithms, these individuals are often referred to as “chromosomes” and the variables of each individual are analogous to “genes.” Thus, a chromosome (e.g., a solution or individual) is composed of several genes (e.g., variables).

[0024] The genetic algorithm mimics three evolutionary processes: selection, gene crossover, and mutation. Specifically, during selection, a proportion of the existing population (e.g., a set of chromosomes) is selected to breed a new generation. Individual chromosomes are selected through a fitness-based process, where fitter solutions are typically more likely to be selected. The “fitness” of a solution may be determined by a fitness function, which measures the quality of a solution represented by a chromosome with respect to an objective function. The selected chromosomes form pairs of parents for breeding. Each child (e.g., child chromosome) takes characteristics from its parents (e.g., parents’ chromosomes). Essentially, the child represents a recombination of characteristics from its parents. Some of the characteristics are taken from one parent and some from another. In addition to the recombination, some of the characteristics can mutate. [0025] Because fitter chromosomes are used to produce more children, each subsequent generation is expected to have better fitness. The underlying idea of the genetic algorithm is that, at some point, it is expected that a new generation of chromosomes created will contain a chromosome that will represent a “good enough” solution (e.g., an approximately optimal solution) for the optimization problem.

[0026] Compared with other optimization algorithms, genetic algorithms intrinsically have the advantage of parallelism, which enables the algorithm to evaluate many solutions at once. As such, genetic algorithms are particularly well-suited to solving optimization problems where the space of all feasible solutions is huge, and in some cases, too vast to search exhaustively in any reasonable amount of time (e.g., impossible for a human to practically perform). Further, some other optimization algorithms are serial and can only explore the space of feasible solution to an optimization problem in one direction at a time. This presents a technical problem for these other optimization algorithms if the solution that is discovered turns out to be suboptimal, given all previous work completed may need to be abandoned to start over and determine another solution to the optimization problem. Genetic algorithms provide technical advantages over these other optimization algorithms by generating multiple offspring (e.g., child chromosomes), and thus are able to explore the solution space in multiple directions at once. Accordingly, if one path turns out to produce a suboptimal solution to the optimization problem, this solution can be easily eliminated and work may continue on more optimal chromosomes, thereby providing a greater probability of identifying the optimal solution each time a new generation is formed.

[0027] As described above, in some cases, stochastic optimization, and more specifically genetic algorithms, are used to solve portfolio selection problems. Portfolio selection aims to assess a combination of opportunities from a larger quantity of available alternative opportunities, to determine a combination of opportunities that maximizes expected returns with acceptable levels of risk. In some cases, portfolio selection is used to identify a number of stocks that may help an investor achieve higher financial returns within acceptable risk limits. In some other cases, businesses use portfolio selection to identify a combination of projects and/or opportunities that efficiently optimize a given portfolio for the business.

[0028] For example, business leaders in an oil and gas company may be tasked with identifying a threshold number of optimal drilling opportunities that the company should exploit in an upcoming fiscal year. The threshold number of drilling opportunities may be selected from a large corpus of candidate drilling opportunities, where each drilling opportunity identifies a well owned by the company that may be used to bring to the surface petroleum oil hydrocarbons (referred to herein as “oil”) and/or gaseous hydrocarbons (referred to herein as “gas”) from a particular target drilling location (e.g., each opportunity may have a different well and/or different target drilling location specified). Resource constraints, budget constraints, scheduling constraints, and/or the like may limit the drilling opportunities that are selected by the business leaders to count towards the threshold number of drilling opportunities. Further, business leaders may make their selection of drilling opportunities based on those opportunities that maximize the company’s return on investment, units of production, revenue, and/or the like.

[0029] Selection of the optimal drilling opportunities from a corpus of candidate drilling opportunities may be classified as a non-determini Stic polynomial-time (NP) hard (NP-hard) combinatorial search problem. This NP-hard problem is difficult to solve because it involves a large number of potential solutions (e.g., combinations of drilling opportunities) that need to be checked against objective function(s) and/or constraint s) in order to find the near-optimal combination of drilling opportunities. This is generally an extraordinarily time-consuming process when there are many options (e.g., drilling opportunities) from which to choose when determining the optimal solution. An excessive amount of time may be needed to determine a near-optimal combination of drilling opportunities from the corpus of candidate drilling opportunities. Thus, selection of the threshold number of optimal drilling opportunities is generally impractical to perform by humans (e.g., impractical as a mental process). For example, where 10 drilling opportunities may be selected from a corpus of 50 candidate drilling opportunities, there may be 410,891,126,800 possibilities that need to be analyzed to determine the near-optimal combination of drilling opportunities. Analyzing this large number of possibilities is computationally intensive and impractical for a human to perform.

[0030] Use of a genetic algorithm to solve for the optimal drilling opportunities provides a technical solution to the technical problems associated with such NP-hard combinatorial search problems. For example, in this example when using a genetic algorithm, each drilling opportunity and its associated characteristics is represented as a gene, and multiple genes make up a single chromosome. In other words, each chromosome having a plurality of genes represents a combination of drilling opportunities that represents one solution to the optimization problem. The genetic algorithm begins with an initial population of chromosomes (e.g., solutions, each having a combination of drilling opportunities) and performs selection, gene crossover, and mutation (collectively referred to a “reproduction”), as described above. In particular, (1) fitness scores are determined for each of the chromosomes of the initial population, (2) chromosomes with higher fitness scores are selected as parent chromosomes, (3) child chromosomes are generated from the parent chromosomes using crossover and/or mutation techniques, and (4) a new population of chromosomes is created including at least the generated child chromosomes. This process iteratively continues to generate successive “generations” of solutions to find a near-optimal solution, or in other words, identify optimal drilling opportunities (e.g., drilling opportunities that maximize and/or minimize one or more objective function(s)) from the corpus of candidate drilling opportunities.

[0031] A further technical problem exists, though, in the fact that using crossover and mutation techniques to generate child chromosomes for each new generation may, in some cases, result in chromosomes that no longer respect the constraints defined for the optimization problem (as in the original chromosomes). For example, ten genes may exist to represent ten drilling opportunities, and each chromosome (e.g., solution) may include ten bits, where each bit corresponds to one of the ten genes. In some cases, a number of genes per chromosome may be arbitrarily limited, such as to five bits (e.g., each solution may include only five drilling opportunities). Thus, each chromosome may include five bits of value “1” and five bits of value “0,” where value “0” indicates that the gene corresponding to this bit is not part of the chromosome and value “1” indicates that the gene corresponding to the bit is part of the chromosome. Thus, in the above example, a first parent chromosome may be “ [1, 1, 1, 1, 1, 0, 0, 0, 0, 0] indicating that the first five genes (e.g., genes 1-5 of genes 1-10) are included in the chromosome and a second parent chromosome may be [0, 1, 1, 1, 1, 1, 0, 0, 0, 0] indicating that the second through sixth genes are included in the chromosome (e.g., genes 2-6 of genes 1-10). If crossover is performed to create a child chromosome from these two parents the child chromosome may be [1, 1, 1, 1, 1, 1, 0, 0, 0, 0] where the first five bits are “inherited” from the first parent gene and the second five bits are “inherited” from the second parent gene. Mutation, further applied to the child chromosome may change one or more bits of the created child chromosome. For example, the seventh bit may be changed from a “0” to a “1” such that the chromosome is [1, 1, 1, 1, 1, 1, 1, 0, 0, 0], The child chromosome, created via crossover and mutation, includes seven genes, which violate the gene amount constraint (e.g., five gene limit) defined for the genetic algorithm. Although this chromosome violates at least one constraint defined for the genetic algorithm, the existing algorithm may continue to process this chromosome as part of the successive generation (e.g., at least generate a fitness score for the violating chromosome). In addition to the above example, the use of mutation and crossover techniques to generate child chromosomes may generate child chromosomes that additionally, or alternatively, violate budget constraints, resource constraints (e.g., personnel, equipment, etc. needed for drilling), feasibility constraints (e.g., one well cannot be used to drill in one location while also being used to drill in another location simultaneously), and/or the like defined for the genetic algorithm.

[0032] Processing, via the genetic algorithm, chromosomes that violate one or more constraints defined for the algorithm may increase the number of iterations needed to arrive at an optimal (or approximately optimal solution) thereby increasing time and resources needed to perform the algorithm. Further, a chromosome that violates one or more constraints is very unlikely (if at all likely) to be selected as a solution to the optimization problem. As such, using computational resources to calculate a fitness score for each of these violating chromosomes, especially where multiple violating chromosomes exist in multiple generations, unnecessarily increases resource overhead.

[0033] Another technical problem with using a genetic algorithm to solve the example optimization problem is that the algorithm is unable to simultaneously optimize for both selection and scheduling. At least in the above example, an optimal combination of drilling opportunities does not include drilling opportunities that only maximize ROI, revenue, production, and/or the like, but drilling opportunities that are optimally scheduled according to a rig availability calendar for the company to maximize ROI, revenue, production, and/or the like according to the scheduling constraints. Due to such limitations of existing genetic algorithms, the quality of output solutions produced via these algorithms may be reduced. For example, an inability of the genetic algorithm to optimize for both selection and scheduling may lead to an output solution of the genetic algorithm only optimizing for one of these facets, thus producing a sub-optimal output. [0034] Embodiments described herein overcome the aforementioned technical problems and improve upon the state of the art by providing an improved genetic algorithm that additionally includes (1) steps for repairing chromosomes, including in some cases, after mutation is performed to generate child chromosome(s) (referred to herein as “repair mutation”) and (2) logic to optimize for both selection and scheduling simultaneously. For example, in performing reproduction to create a new generation for analysis, the genetic algorithm further includes steps for identifying and repairing chromosomes determined to violate one or more constraints defined for the algorithm. A chromosome may violate defined constraint(s) where characteristics of at least one gene belonging to the chromosome do not follow restrictions and/or limitations defined for the genetic algorithm. For example, a chromosome having a gene representing a drilling opportunity with an expected duration of the drilling project greater than a time slot during which the drilling project may be scheduled (e.g., a remaining rig availability time slot after scheduling other drilling opportunities associated with other genes in the chromosome) may be in violation of a defined constraint. Additionally, a chromosome may violate defined constraint(s) where the plurality of genes together violate one or more constraints. For example, as described above, a violating chromosome may include more genes than an allowed number of genes per chromosome, may include genes representing drilling opportunities having budgets that when aggregated are above a drilling budget for the upcoming fiscal year, and/or the like. In either of these cases, such chromosomes may be repaired according to techniques described herein.

[0035] As described in detail below, this repair may occur (1) each time a new generation is created (e.g., referred to herein as “chromosome repair”) and (2) each time a child chromosome is generated using mutation techniques (e.g., referred to herein as “repair mutation”). In other words, chromosome repair occurs for each iteration of a genetic algorithm, while repair mutation is performed based on a mutation condition being met (e.g., mutation has been performed). Mutation occurs according to a mutation rate defined for the genetic algorithm, thus the mutation condition is a function of the mutation rate. For example, if a mutation rate is set to 2%, thereby indicating that mutation is to be carried out for every two out of 100 chromosomes generated, then repair mutation may occur (or be attempted) on every two out of the 100 chromosomes generated (e.g., via mutation techniques). [0036] For both chromosome repair and repair mutation, one or more chromosome are evaluated to determine whether these chromosome(s) comply with some set (e.g., one or more) of constraints, and they do not comply, the chromosome(s) are repaired to comply with the constraint(s). However, in chromosome repair, all chromosomes of each new population generated are checked against defined constraint s), while in repair mutation, only those chromosomes which were mutated (e.g., during child chromosome generation) are checked against defined constraint(s) (and repaired, if needed). Further, constraint(s) checked during chromosome repair may be different than constraint(s) checked during repair mutation. For example, during repair mutation, chromosomes may be checked against a budget constraint, while during repair mutation, mutated chromosome(s) may be checked against a feasibility or resource constraint.

[0037] In certain aspects, the additional logic incorporated into genetic algorithms to enable such algorithms to optimize for both selection and scheduling, involves logic for penalizing fitness scores based on a resource schedule. For example, the resource schedule may include information about resource availability, such as rig availability for one or more rigs owned by a company. The rig schedule may indicate when a particular rig is not scheduled and for how long the rig is not scheduled for. A genetic algorithm that optimizes for drilling opportunity scheduling would identify a solution that schedules identified/selected drilling opportunities in each available time slot and for the full duration, to maximize ROI and revenue of each drilling opportunity. Thus, when using the genetic algorithm described herein, chromosomes with genes representing drilling opportunities that are unable to exploit all available resource availability time periods (e.g., including rig availability time periods) and/or are unable to exploit the full resource availability (e.g., a drilling rig is available for four months, yet a drilling opportunity scheduled for this rig availability time period has a project duration less than four months) of one or more right availability time periods may be penalized when calculating the chromosomes’ fitness scores. In this way, the genetic algorithm may not only optimize for selection, but drilling right selection and scheduling simultaneously.

[0038] The improved genetic algorithm, described herein, provides significant technical effects and advantages over existing genetic algorithms, including a significant reduction in time and resources (e g., compute and memory) used to select a solution to the optimization problem while also improving the optimality of a solution output via the genetic algorithm. In particular, the addition of logic enabling the algorithm to solve optimization selection and scheduling problems in combination enables the algorithm to optimize for multiple facets simultaneously and thus help to improve the accuracy of the output solution provided by the algorithm. Further, the addition of repair logic (e.g., for both chromosome repair and repair mutation) in the algorithm enables the algorithm to iterate more quickly and reduce computing overhead by adjusting genes of violating chromosomes (e.g., solutions) before assessing the fitness of a new generation containing the violating chromosomes (e.g., thereby saving time and resources that would have previously been expended to evaluate these violating chromosomes). As such, a near-optimal solution may be determined and provided as output to a user in a short period of time to allow for prompt decision making by users receiving the output. Further, this allows the improved genetic algorithm to be easily scaled.

[0039] Additionally, repair mutation in combination with chromosome repair, helps the genetic algorithm arrive at a solution more quickly, while reducing computing resources required to perform such repair. Specifically, because repair mutation checks for constraint(s) different than constraint(s) checked during chromosome repair, there may be even less violating chromosomes in each population generated. Further, because repair mutation does not check every chromosome against every child chromosome generated and instead performs the check, and any necessary repair, according to a mutation rate (e.g., where the mutation rate is less than 100%), compute resources are saved while also still allowing for repair mutation to check for non-compliance with additional constraint s) (e.g., beyond those checked during chromosome repair). If these additional constrains were checked during chromosome repair, instead of during repair mutation (e.g., based on a mutation rate), every chromosome would need to be checked, thereby using additional compute resources. Further, repair mutation checks only those chromosomes which have been mutated, and mutated chromosomes may be more susceptible to violating constraint s) defined for the genetic algorithm.

[0040] Notably, the improved genetic algorithm described herein provides many other advantages, including its flexibility to fit any specific objectives and/or constraints, as well as its ability to easily scale to any complex problem involving a large number of genes, objective functions, and/or constraints. Further, the algorithm is capable of providing unbiased output to a user. In particular, the improved genetic algorithm described herein helps to ensure that the returned solution to the optimization problem is data-driven and removed from any bias.

Example System for Solving an Optimization Problem Using a Genetic Algorithm

[0041] FIG. 1A depicts an example system 100 for solving an optimization problem. More specifically, example system 100 includes an optimizer 110 configured to use genetic algorithm 111 to solve an optimization problem, where genetic algorithm I l l is designed to optimize for both selection and scheduling simultaneously. Further, genetic algorithm 111 includes steps for repairing chromosome(s), generated via genetic algorithm 111, to comply with constraint s) defined for genetic algorithm 111.

[0042] In some embodiments, system 100 is implemented via a cloud-based platform as a web application (e.g., software that runs in a web browser). One example of a cloud-based platform is a Dataiku® platform made commercially available by Dataiku of New York City, New York. In some cases, the engine behind the web application consists of a genetic algorithm optimizer coded in python language within a Dataiku python recipe. In some cases, the python scripts may be used as standalone applications and/or maybe easily embedded in any other software, such as FDPlan® made available by Schlumberger® Ltd. of Houston, Texas.

[0043] Optimizer 110 in system 100 is configured to receive as input, a plurality of opportunities 102, at least one objective function 104, and one or more constraints 106, including, a resource schedule 108. The plurality of opportunities 102 include various investments that may be exploited by a person and/or company. Each opportunity 102, received by optimizer 110 as input, may include one or more characteristics associated with the opportunity.

[0044] Optimizer 110 is configured to use characteristics of each of the plurality of opportunities 102 to select a near-optimal (e g., a “best”) combination of opportunities 102 from the plurality of opportunities 102. The near-optimal combination of opportunities 102 may minimize and/or maximize one or more objective functions 104 (e.g., also received by optimizer 110 as input). The near-optimal combination of opportunities 102 includes at least two opportunities 102, and less than all of the plurality of opportunities 102 received by optimizer 110.

[0045] As an illustrative example, in some cases, the plurality of opportunities 102 include drilling opportunities that a company may consider exploiting in an upcoming fiscal year. Each drilling opportunity identifies a well owned by the company that may be used to drill for oil and/or gas from a particular target drilling location. Each drilling opportunity may identify a different well and/or different target drilling location. For example, where ten target drilling locations are being considered for exploitation, the company owns five wells, and each well may be used for each of the target drilling locations, then fifty drilling opportunities may be considered by optimizer 110 when selecting the near-optimal combination.

[0046] Further, each drilling opportunity may include one or more associated characteristics. The character! stic(s) for each drilling opportunity may include information about a total expected revenue for the drilling opportunity (e.g., expected amount of income to be generated by the drilling opportunity), total expected capital expenditures (e.g., money expected to be spent to exploit the drilling opportunity), and/or operational expenditures (e.g., money expected to be spent on the ongoing costs of carrying out the drilling opportunity, such as wages, rental fees, etc.). Further, the characteristic(s) for each drilling opportunity may include information about a total expected barrels of oil equivalent (BOE) volume (e.g., BOE is a measure of hydrocarbon volume in terms of the barrels of crude oil that would have the same energy content), an expected BOE volume per year, a total expected gas volume (e.g., where the drilling opportunity is meant to obtain gas), an expected gas volume per year, a total expected oil volume (e.g., where the drilling opportunity is meant for drilling for oil), an expected oil volume per year, an after tax cash amount, and/or a cost per unit of production of oil and/or gas. The one or more characteristics may also include a well identifier associated with a well that is to be used for drilling (e.g., well 1, well #1,222, etc.), a target drilling location identifier associated with the target drilling location (e.g., target location 1, Permian Basin, Middle East, etc.), and/or a duration expected to carry out the drilling opportunity (e.g., months, days, etc.). In some cases, the character! stic(s) include a risk score for the drilling opportunity. The risk score may take into consideration geological risk (e.g., refers to both the difficulty of extraction and the possibility that the accessible reserves in any deposit will be smaller than estimated), political risk (e.g., a range of regulations limit where, when and how extraction is done, and these regulations may differ from one location to the next), cost risks, price risks, supply and demand risks, safety risks, and/or the like.

[0047] As described above, the objective function 104 defines the criteria for evaluating a solution to the optimization problem. It is a mathematical function that converts a solution into a numerical evaluation of that solution. One or more objective functions 104 may be provided to optimizer 110. In some cases, the objective function 104 is a function for measuring oil or gas production for a solution (e.g., a combination of drilling opportunities), a cost of the solution, a cost per unit of production for the solution, a cumulative risk score for the solution, and/or the like. Thus, in cases where the objective function 104 is a function for measuring a cost of the solution, a lower cost solution may be a more optimal solution than a solution with a higher calculated cost. Alternatively, in cases where the objective function 104 is a function for measuring oil production, a higher oil production solution may be a more optimal solution than a solution with lower expected oil production.

[0048] Constraint s) 106 (also received by optimizer 110) are logical conditions that a solution to an optimization problem must satisfy. Constraint s) 106 reflect real -world limits on production capacity, market demand, available funds, and/or the like. For example, in some cases where the determined solutions are combinations of drilling opportunities, the constraints 106 may include a budget for the solution, such that the drilling opportunities that make up the solution together do not cost more (e.g., operational expenditures, capital expenditures, etc.) than a pre-determined budget. In some cases where the determined solutions are combinations of drilling opportunities, the constraints 106 may include a risk threshold for the solution, such that the cumulative risk score of the drilling opportunities that make up the solution is below the risk threshold. In some cases where the determined solutions are combinations of drilling opportunities, the constraints 106 may include an oil or gas production minimum for the solution, such that the drilling opportunities that make up the solution together produce at least the minimum required oil or gas amount. As described below, optimizer 110 handles constraint(s) 106 by penalizing solutions that do not abide by constraint(s) 106.

[0049] In some cases, constrain^ s) 106 include resource schedule 108. Resource schedule 108 includes information about what resources can be used to service opportunities 102, when the resources are available for use, and under what conditions. In cases where opportunities 102 are drilling opportunities, resource schedule 108 may include information about when oil or gas drilling equipment, such as powering systems, rotary drilling equipment, circulation systems (e.g., system that circulates mud in a drilling hole and extracts rock cuttings to the surface), and/or hoisting and lifting systems, is available. Oil or gas drilling equipment may be unavailable when such equipment is being used for another drilling opportunity and/or is undergoing maintenance. In some cases, resource schedule 108 may also include information about available personnel and/or site managers needed to carry out each of the drilling opportunities.

[0050] Optimizer 110 may use genetic algorithm 111 to generate an initial set of solutions (e g., also referred to herein as “chromosomes”), where each solution includes a plurality of opportunities 102 (e.g., also referred to herein as “genes”). Optimizer 110 may use genetic algorithm 111 to simulate evolution, starting from the initial set of solutions, and generate successive “generations” of solutions until a termination condition is met. A near-optimal (“best”) solution from each generation generated may be determined and stored (e.g., cached). The near- optimal solution from each generation is a solution that minimizes and/or maximizes objective function(s) 104 to the greatest extent (e.g., has a highest fitness score) among other solutions in the respective generation. For example, if 100 generations are created by optimizer 110, then 100 solutions may be cached, where each solution is the near-optimal solution of a corresponding generation of solutions.

[0051] An optimal solution, e.g., solution 114, may be determined as the most near-optimal solution from the near-optimal solutions stored (e.g., cached) for each generation created. The most near-optimal solution minimizes and/or maximizes objective function(s) 104 to the greatest extent (e.g., has the highest fitness score) among other near-optimal solutions (e.g., solutions cached for other generations).

[0052] Solution 114 includes information about one or more opportunities selected from the plurality of opportunities 102 received as input by optimizer 110. For example, in FIG. 1A, solution 114 includes a selection of opportunity 102(1), opportunity 102(4), and opportunity 102(9) from the plurality of opportunities 102 received by optimizer 110. Further, solution 114 indicates when each of opportunities 102(1), 102(4), and 102(9) are to be carried out, based on resource availability in resource schedule 108. For example, opportunity 102(1) may occur during a first time period where all necessary resources for opportunity 102(1) are available and opportunity 102(4) may occur during a second time period where all necessary resources for opportunity 102(4) are available, where the first time period occurs earlier in time than the second time period. [0053] In some cases, the selected opportunities 102 are provided as a schedule 116, and more specifically, a Gantt chart. A Gantt chart is a graphical depiction of a project schedule. A Gantt chart is a type of bar chart showing the start and finish dates of various projects, and in this cases, selected opportunities 102. FIGS. IB and 1C depict example Gantt chart solutions generated by system 100 in FIG. 1A. Example Gantt chart solutions illustrated in FIG. IB and FIG. 1C may be provided to a user via a user interface, such that the user may make a decision about what opportunities 102 to exploit.

[0054] As shown in FIG. IB, in some cases, optimizer 110 outputs a single scenario of selected opportunities organized in a Gantt chart. In this example, the selected opportunities include opportunities 22, 16, 105, 31, 59, and 47. The selected opportunities are presented in a schedule 116, and more specifically, within time periods where resources are available for carrying out each of the respective opportunities. In some cases, the solution further includes economic and/or production insights about the selected combination of opportunities. For example, the insights may include information about total oil volume, total revenue, total cost, schedule duration, a sum oil volume for a particular year, dollar over volume, and/or total risk for the selected opportunities.

[0055] In some other cases, as shown in FIG. 1C, optimizer 110 outputs multiple scenarios of selected opportunities organized in a Gantt chart. In FIG. 1C, three scenarios of different selected opportunities and/or different schedules are provided in schedule 116. Providing multiple scenarios may allow a user to compare the different scenarios and make a decision based on the provided information.

[0056] Optimizer 110 is configured to produce solutions 114, such as those illustrated in FIGS. IB and 1C, based on performing workflow 200 depicted in FIG. 2. As illustrated, workflow 200 combines tasks, such as gene encoding 212, chromosome generation 214, chromosome repair 215, fitness score calculation 216 (including chromosome caching 217), parent chromosome(s) determination 218, child chromosome(s) generation 220, repair mutation 222 (e.g., based on a mutation rate as depicted in FIG. 3E), chromosome(s) replacement 224, determining whether a termination condition has been met at 226, and solution determination 228. Use of workflow 200 enables optimizer 120 to solve an optimization problem while optimizing for both selection and scheduling of opportunities 102. [0057] Although not meant to be limiting to this particular example, workflow 200 is described below for a scenario in which a user desires to determine which drilling opportunities (for a total of five drilling opportunities), from a corpus of candidate drilling opportunities, are ideal for maximizing revenue, while minimizing costs and adhering to resource constraints (e.g., rig availability) identified for an upcoming fiscal year. In particular, FIGS. 3A-3F depict an example of using a genetic algorithm for selecting and scheduling multiple drilling opportunities from a corpus of candidate drilling opportunities. As illustrated in FIG. 3A, the corpus of candidate drilling opportunities include opportunities 1-10 (e.g., Opp 1-10). Each drilling opportunity identifies a well owned by the company that may be used to bring to the surface oil and/or gas from a particular target drilling location. Each opportunity may have a unique combination of a well and a target location.

[0058] Characteristics of each drilling opportunity may be stored in datastore 302. For this example, the characteristics include information about total expected revenue, total expected cost, and duration of each drilling opportunity, however other characteristics may be stored for other examples. Such information, stored in datastore 302, may be used by optimizer 110 to identify the near-optimal combination of opportunities among opportunities 1-10 that maximize revenue, minimize cost, and adhere to the company’s resource constraints (e.g., rig availability) for drilling.

[0059] FIGS. 2 and 3A-3F are described in conjunction below.

[0060] As illustrated in FIG. 2 and 3B, workflow 200 begins with gene encoding 212. Gene encoding 212 involves representing each opportunity and its corresponding characteristics as a gene. For example, in FIG. 3B, gene encoding 212 includes generating a plurality of genes 306, and more specifically, ten genes where each gene represents one of the ten drilling opportunities. Each gene may include encoded information about one or more characteristics associated with the drilling opportunity represented by the respective gene.

[0061] Workflow 200 then proceeds with chromosomes generation 214, where many individual solutions, also referred to herein as “chromosomes,” are randomly generated to form an initial population. The population size may be based on an input value 312 (e.g., provided by a user) indicating a number of chromosomes to generate. The population size may be selected such that the population size is large enough to allow for a solution to the optimization problem to be identified via workflow 200 (e.g., a population size that is too small may result in a failure to find an optimal solution). Example population sizes include 50 (e.g., in cases where the number of decision variables is less than five), 100, and 200.

[0062] Each chromosome includes a plurality of genes represented, in this example, as a string of binary values (e.g., a string of Is and 0s). In particular, each value of “0” or “1” included in each chromosome may correspond to a particular gene. A “0” value included in a chromosome may indicate that the gene associated with this value is not present in the chromosome. Alternatively, a “1” value included in a chromosome may indicate that the gene associated with this value is present in the chromosome. In some cases, the number of genes included per generated chromosome may be based on an input value 310 (e g., provided by a user) indicating a number of genes per chromosome. Input value 310 may be a value consistent with the original optimization problem. For example, if the optimization problem identifies that the “best” ten drilling projects need to be identified. Then, input value 310 may also be equal to ten. In some other cases, input value 310 is not specified, and instead, a maximum possible number of genes, which minimize or maximize the optimization problem’s objective(s) while also respecting the problem’s constraint(s), may be determined.

[0063] For example, as illustrated in FIG. 3B, six chromosomes are randomly generated, where each chromosome includes five genes (e.g., where each gene represents one or more characteristics associated with a drilling opportunity (Opp. 1-10)). Each chromosome may include five genes based on the optimization problem indicating that five drilling opportunities are to be selected in the determined near-optimal solution. The first binary value included in each chromosome corresponds to gene 1, the second binary value included in each chromosome corresponds to gene 2, the third binary value included in each chromosome corresponds to gene 3, and so forth. A value of “0” indicates that the corresponding gene is missing from the chromosome (e.g., a corresponding drilling opportunity is not included in the solution) while a value of “1” indicates that the corresponding gene is present in the chromosome (e.g., a corresponding drilling opportunity is included in the solution). For example, chromosome 1 randomly generated from genes 1-10 is represented as [1, 1, 0, 1, 0, 1, 0, 1, 0, 0], Thus, chromosome 1 includes genes 1, 2, 4, 6, and 8 (e.g., a total of five genes), but does not include genes 3, 5, 7, 9, and 10.

[0064] Workflow 200 then proceeds with chromosome repair 215. Chromosome repair 215 involves determining whether each of the plurality of chromosomes of the current population (e.g., generated during chromosomes generation 214) meet a first set of a plurality of constraints, or simply referred to as a first set of constraints (e.g., such as a first set of constraints 313 in FIG. 3B) For example, two constraints may be defined for the genetic algorithm, including a budget constraint and a schedule constraint. The first set of constraints may include the budget constraint but not the schedule constraint. Thus, during chromosome repair 215, each of the plurality of chromosomes of the current population are checked against the budget constraint, but not the schedule constraint. Chromosomes which do not meet this budget constraint are repaired.

[0065] For example, in FIG. 3B, chromosome repair 215 begins with checking whether chromosomes 1-6 each meet a first set of constraints 313. The first set of constraints 313 include a budget constraint. In this example, chromosome 2 is determined not to meet the budget constraint and is thus repaired by adjusting the 9^th and 10^th binary values of this chromosome. More specifically, chromosome 2 represented as [0, 1, 1, 0, 0, 1, 1, 0, 1, 0] includes genes 2, 3, 6, 7, and 9 (and does not include genes 1, 4, 5, 8, and 10). Cost characteristics for genes 2, 3, 6, 7, and 9, when aggregated, are above the budget set for carrying out these drilling opportunities. Accordingly, two genes (e.g., the 9^th and 10^th binary values) of child chromosome 2 are altered, in this example, such that the cost of drilling opportunities represented by genes in chromosome 2 is less than the defined budget.

[0066] Workflow 200 then proceeds with fitness score calculation 216 (e.g., shown in FIG. 3C) to calculate a fitness score for each chromosome. The fitness score represents how well a chromosome (e.g., an individual solution) performs in solving a given problem. The fitness score is a metric that guides the evolutionary process, given the chromosomes selected for reproduction and the chromosomes discarded are based on the determined fitness scores for these chromosomes.

[0067] The fitness score calculated for each chromosome evaluates the quality of the chromosome (e.g., individual solution) based on the optimization problem’s objective(s) and constraint(s). More specifically, the fitness function measures the ability of each chromosome to achieve one or more objective functions defined for the optimization problem (e.g., provided as input 316 in FIG. 3C), while also adhering to one or more constraints (e.g., provided as input 318 in FIG. 3C) In some cases, determining the fitness score for each chromosome includes (1) increasing the fitness score for chromosomes having genes that increase an objective function and (2) decreasing the fitness score for chromosomes having genes that decrease the objective function. For example, an objective function defined for an optimization problem may be a function for measuring revenue generated by each chromosome. A chromosome that maximizes the amount of revenue generated may be given a higher fitness score than another chromosome that generates less revenue.

[0068] In some other cases, determining the fitness score for each chromosome includes (1) decreasing the fitness score for chromosomes having genes that increase an objective function and (2) increasing the fitness score for chromosomes having genes that decrease the objective function. For example, an objective function defined for an optimization problem may be a function for measuring cost incurred by each chromosome. A chromosome that minimizes the amount of cost incurred may be given a higher fitness score than another chromosome that incurs a greater amount of cost.

[0069] In some cases, multiple objective functions may be used to determine the fitness score for each chromosome. For example, an objective function defined for an optimization problem may be a function for measuring revenue and cost. A chromosome that maximizes the amount of revenue generated while also minimizing cost may be assigned a highest fitness score.

[0070] In some cases, the fitness score determined for each chromosome is further based on whether or not genes belonging to each chromosome respect constraint(s) defined for the optimization problem. For example, a fitness score determined for a chromosome may be decreased when (1) at least one gene of the first plurality of genes of the chromosome does not meet at least one of the constraint(s), or (2) the first plurality of genes of the chromosome do not meet at least one of the constraint(s). For example, in a scenario where each gene corresponds to a drilling opportunity, a constraint defined for the optimization problem may declare a maximum cost allowed for each gene (e.g., a maximum cost allowed for each drilling opportunity). A chromosome that includes at least one gene that is expected to incur costs greater than the maximum cost may be penalized (e.g., its fitness score may be decreased). As another example, in a scenario where each gene corresponds to a drilling opportunity, a constraint defined for the optimization problem may declare a total maximum cost allowed for all genes belonging to a chromosome. A chromosome that includes genes with an aggregate cost greater than the maximum total cost may be penalized. [0071] In some cases, the constraint(s) include a resource schedule (e.g., such as resource schedule 108 in FIG. 1). A chromosome that includes genes that are unable to be scheduled according to the resource schedule (e.g., do not meet the constraint) may be penalized when determining their fitness score. For example, in a scenario where each gene corresponds to a drilling opportunity, the resource schedule may indicate one or more time periods when one or more resources (e.g., rigs, personnel, etc.) for drilling are available. A chromosome may be penalized (e.g., via their fitness score) for not meeting the resource schedule when less than all of the drilling opportunities associated with genes of the chromosome are able to be scheduled in the one or more time periods when the one or more resources are available. In particular, the resource schedule may include three time periods of two months each where resources are available. A chromosome having three genes corresponding to three drilling opportunities may be unable to meet this resource schedule when two of the drilling opportunities have an expected duration of two months while the third drilling opportunity has an expected duration of four months (e.g., four months > two month time period).

[0072] In some cases, the genes belonging to each chromosome are randomly scheduled when the respective chromosome is created. For example, in FIG. 3B, chromosome 1 randomly generated from genes 1-10 and represented as [1, 1, 0, 1, 0, 1, 0, 1, 0, 0] includes genes 1, 2, 4, 6, and 8. A randomly generated schedule determined for these genes may schedule gene 2 first, gene 4 second, gene 1 third, gene 6 fourth, and gene 8 fifth. A fitness score calculated for this chromosome may take into account this scheduling created for the genes. For example, if the resource schedule does not allow for this scheduling of the genes (e.g., corresponding to drilling opportunities) based on the when resources are available, then the fitness score generated for this chromosome may be penalized.

[0073] As illustrated in FIG. 3C, six fitness scores 320 are calculated, where each fitness score 320 corresponds to one of the six chromosomes. As described above, optimizer 110 is being used to identify a chromosome (e.g., having multiple genes corresponding to drilling opportunities) that maximizes revenue, minimizes cost, and adheres to the company’s resource constraints (e.g., rig availability) for drilling. Accordingly, a chromosome with a highest fitness score (e.g., chromosome 6 with a fitness score = 10) maximizes revenue and minimizes cost the most out of all of chromosomes 1-6, while also adhering to the company’s resource constraints. Similarly, a chromosome with a lowest fitness score (e.g., chromosome 3 with a fitness score = 1.9) may maximize revenue and minimize cost the least, and/or may adhere to the company’s resource constraints the least out of all of chromosomes 1-6.

[0074] The fitness score calculated for chromosome 1 is based on characteristics associated with genes belonging to chromosome 1. More specifically, characteristics provided in FIG. 3A for genes 1, 2, 4, 6, and 8 (e.g., because chromosome 1 is represented as [1, 1, 0, 1, 0, 1, 0, 1, 0, 0]) are used to calculate the fitness score for chromosome 1. Further, a random order of genes 1, 2, 4, 6, and 8, included in chromosome 1, is also used to calculate the fitness score for chromosome one (e g., based on a resource schedule). Similar techniques are also used to calculate the fitness score for chromosomes 2-6.

[0075] Fitness score calculation 216 also includes chromosome caching 217. Chromosome caching 217 involves caching a chromosome with a “best” fitness score in the current population of chromosomes. A chromosome with a “best” fitness score may be a chromosome with a highest fitness score among the fitness scores determined for chromosomes within a population. For example, in FIG. 3C, chromosome caching involves caching chromosome 6 (e.g., fitness score = 10 is the highest fitness score).

[0076] Workflow 200 then proceeds with parent chromosomes determination 218, where a proportion of the existing population of chromosomes is selected to breed a new generation of chromosomes. One or more chromosomes are selected as parent chromosomes based on their respective fitness scores, where “fitter” solutions (e.g., chromosomes associated with higher fitness scores) are more likely to be selected. In some cases, parent chromosome(s) determination 218 involves selecting the chromosomes with the highest fitness scores as the parent chromosomes. In some other cases, parent chromosomes determination 218 involves selecting the chromosomes with the highest fitness scores as the parent chromosome(s) from a random sample of the current population of chromosomes (e.g., less than all) (e.g., referred to as “tournament selection”).

[0077] Tournament selection is a stochastic process that mimics the competition among individuals (e.g., chromosomes) in a population. Tournament selection works by randomly selecting a subset of chromosomes from the population, referred to as the “tournament size.” The chromosomes in this subset compete against each other, and the chromosome with the highest fitness score is selected as a parent chromosome for reproduction. This process is repeated until a desired number of parent chromosomes are selected.

[0078] For example, as illustrated in FIG. 3C, two tournaments are used to select two parent chromosomes from the six existing chromosomes belonging to the current population. Two parent chromosomes are selected based on receiving input 342 (e.g., provided by a user) indicating a number of parent chromosomes that are to be selected for this optimization problem. In the first tournament, K chromosomes are selected from the six existing chromosomes, where ? is an input 344 (e.g., provided by a user) and a positive integer indicating that indicates the “tournament size.” In this example, K= 3 such that three chromosomes randomly selected from the population include chromosome 1, chromosome 4, and chromosome 5. Chromosome 4 has a highest fitness score (e.g., fitness score = 6); thus, chromosome 4 is selected as the first parent chromosome. In the second tournament, three chromosomes randomly selected from the population include chromosome 1, chromosome 2, and chromosome 5. Chromosome 1 has a highest fitness score (e.g., fitness score = 4.2); thus, chromosome 1 is selected as the second parent chromosome.

[0079] Workflow 200 then proceeds with child chromosome(s) generation 220, where one or more child chromosomes are generated from the selected parent chromosomes. Each child chromosome includes multiple genes, where the genes include at least one gene from each parent chromosome used to create the child chromosome.

[0080] Child chromosome(s) are generated by combining genes of a pair of parent chromosomes, referred to as “crossover,” and then, in some cases, making random changes to at least one gene of a single chromosome, referred to as “mutation.” Specifically, in some cases, mutation occurs at a mutation rate less than 100% of the time, such that mutation does not occur every time a child chromosome is generated via crossover at child chromosome(s) generation 220. For example, the mutation rate may be equal to 3%, thereby indicating that mutation is to be carried out for every three out of 100 chromosomes generated (e.g., via crossover).

[0081] Different types of crossover include (1) single point crossover and (2) two-point crossover. In single point crossover, a single point on both parents' chromosomes is picked randomly, and designated a “crossover point.” Genes to the right of that point are swapped between the two parent chromosomes. This results in two offspring (e.g., two child chromosomes), each carrying some genetic information from both parents. For example, a crossover point designated as the middle of each parent chromosome, may result in two child chromosomes each having a different 50% of the genes of each parent chromosome. Alternatively, in A -point crossover, N random points are chosen (e.g., where N is an integer greater than zero) on the pair of parent chromosomes, and the genetic material is exchanged at these points to create child chromosomes.

[0082] Mutation involves altering the gene sequence of a pair of parent chromosomes (e.g., that have been crossed over). Different types of mutation include (1) bit flip mutation, (2) swap mutation, (3) scramble mutation, and/or the like. In bit flip mutation, values of one or more genes of a parent chromosome are flipped. For example, a value of “0” may be changed to “1,” and vice versa. In swap mutation, two genes with different values (e.g., one gene with a value of “0” and one gene with a value of “1”) are selected from a parent chromosome and their values are swapped. In scramble mutation, a subset of our genes of a parent chromosome are selected and their values are then scrambled.

[0083] For example, as illustrated in FIG. 3D, both crossover and mutation techniques are used to generate two new child chromosomes (e.g., where mutation techniques are only applied during the creation of the first child chromosome). Two child chromosomes are created based on input 346 (e.g., provided by a user) indicating a number of child chromosomes to create. Alternatively, input 346 may indicate a number of crossover iterations and/or mutation iterations that are to be carried out to generate the child chromosomes.

[0084] Although the example in FIG. 3D illustrates both crossover and mutation occurring, as mentioned above, in some iterations only crossover may be performed to generate child chromosome(s) (e.g., based on a pre-defined mutation rate).

[0085] In the example, when performing crossover (e.g., single point crossover), the crossover point is selected as the middle point of each chromosome such that five bits are on the left of the crossover point and five bits are on the right of the crossover point. The left five bits of parent chromosome 1 (e.g., left 50%) and the right five bits of parent chromosome 2 (e.g., right 50%) are combined to create child chromosome 1. Similarly, the right five bits of parent chromosome 1 (e.g., right 50%) and the left five bits of parent chromosome 2 (e.g., left 50%) are combined to create child chromosome 2. Further, swap mutation is performed, in this example, on child chromosome 1. In particular, a value of “0” and a value of “ 1” in child chromosome 1 are swapped (e.g., trade places) to create mutated child chromosome 1. [0086] Crossover and/or mutation are important steps that help promote exploration by altering genes of parent chromosomes to create potentially better offspring (e.g., better solutions to the optimization problem). While crossover is generally beneficial and improves the convergence speed of a genetic algorithm, there are cases where such techniques result in child chromosomes that do not adhere to at least one constraint defined for the optimization problem. For example, a child chromosome created may include six values of “1” indicating that six genes belong to the chromosome when only five genes are allowed per chromosome. As another example, a child chromosome created may include at least one gene having a characteristic that does not respect a constraint defined for the optimization problem (e.g., duration of an opportunity associated with a gene is greater than a duration of available resources defined by a resource schedule provided as input to optimizer 110). As another example, genes which make up a chromosome may together have a cumulative cost above a budget defined for the optimization problem. It is noted that this is not an exhaustive list and many other violations may exist for chromosomes created via such mutation and/or cross techniques.

[0087] In cases where mutation techniques have been used to generate child chromosome(s), workflow 200 then proceeds with repair mutation 222. Repair mutation 222 involves identifying and repairing child chromosomes (e.g., created via mutation techniques) determined to violate a second set of constraints defined for the genetic algorithm. The second set of constraints may be different then the first set of constraints checked during chromosome repair 215. In some cases, repairing a chromosome during repair mutation 222 includes changing one or more of the genes of a child chromosome (e.g., created via mutation techniques) such that the child chromosome complies with the second set of constraints (e.g., where a set includes one or more constraints).

[0088] Repair mutation may occur when mutation techniques are used to create child chromosome(s) at child chromosome(s) generation 220. As described above, use of mutation techniques to create child chromosome(s) may be based on a pre-defined mutation rate.

[0089] FIG. 3E illustrates repair mutation 222 being activated based on a mutation rate. For example, if the mutation rate is equal to 2% indicating that mutation is expected to be carried out for two out of 100 chromosomes generated, then the repair mutation 222 is also expected to be carried out for two out of 100 chromosomes generated. [0090] For example, as illustrated in FIG. 3D, mutated child chromosome 1 generated via child chromosome(s) generation 220 was generated using mutation techniques; thus, repairmutation 222 is activated for this chromosome. Repair mutation 222 involves determining whether the chromosome violates a second set of constraints 350 (shown in FIG. 3D), and repairing the chromosome if the chromosome does, in fact, violate the second set of constraints 350. In this example, child chromosome 3 violates a scheduling constraint (e.g., provided as second set of constraints 350) defined for the optimization problem. For example, mutated child chromosome 1 represented as [1, 1, 0, 1, 0, 0, 1, 1, 0, 0] includes genes 1, 2, 4, 7, and 8 (and does not include genes 3, 5, 6, 9, and 10). Duration characteristics for genes 1, 2, 4, 6, and 9 may not meet a resource schedule (e.g., a constraint). Accordingly, genes (e.g., two genes) of mutated child chromosome 1 are altered, in this example, such that the drilling opportunities adhere to the resource availability indicated by the resource scheduled.

[0091] Including steps for repair mutation enables optimizer 110 to iterate more quickly and reduce computing overhead by adjusting genes of violating child chromosomes (when repairing chromosomes at the specified mutation rate) before creating a new generation, as well as repairing and assessing the fitness of the new generation containing the violating chromosomes, which leads to time and resource savings that may have previously been expended to evaluate these violating chromosomes.

[0092] Workflow 200 then proceeds with chromosome(s) replacement 224. Chromosome(s) replacement 224 includes replacing one or more of the chromosomes in the initial population with the child chromosomes generated and, in some cases, repaired at child chromosome(s) generation 220 and repair mutation 222, respectively. The population size may stay the same; thus, the amount of chromosomes replaced in the initial population may be equal to the number of child chromosomes generated. The chromosomes replaced by the child chromosomes may be less “fit” chromosomes in the initial population (e.g., chromosomes with lower fitness scores).

[0093] For example, as illustrated in FIG. 3F, chromosome(s) replacement 224 includes replacing chromosome 2 and chromosome 3 in the initial population (e.g., shown at 356 and 358) with repaired mutated child chromosome 1 and child chromosome 2. Chromosomes 2 and 3 are chromosomes selected for replacement given these chromosomes have the lowest fitness scores among the fitness scores calculated for chromosomes in the initial population. After replacement, the new population 360 (also referred to as the “new generation”) contains previous chromosome 1, previous chromosome 4, previous chromosome 5, previous chromosome 6, previous repaired mutated child chromosome 1, and previous child chromosome 2 (e.g., for a total population size equal to six chromosomes).

[0094] Workflow 200 then proceeds, to step 226, with determining whether a termination condition for the genetic algorithm (e.g., genetic algorithm 111 in FIG. 1A) has been met. In some cases, the termination condition for the genetic algorithm is met when an iteration counter reaches a threshold. In some cases, the termination condition for the genetic algorithm is met when a near- optimal chromosome of the new population of chromosomes created (e.g., chromosome from the new list of chromosomes having a highest fitness score) is different than a near-optimal chromosome of a previous population of chromosomes, associated with a previous iteration (or multiple previous populations associated with previous iterations), by less than a threshold amount (e.g., provides less than a threshold amount of improvement over a “best” chromosome of one or more previous populations of chromosomes).

[0095] For example, in FIG. 3F, the threshold may be set to 200 generations. As such, the termination condition may be met only when 200 generations have been created using the steps outlined in workflow 200 above. Because only two generations have been created, workflow 200 may return to chromosome repair 215 (e.g., illustrated in FIG. 2 and FIG. 3B). Alternatively, in cases where the termination condition is met, then workflow 200 proceeds to solution determination 228. Solution determination 228 includes optimizer 110 determining the solution to the optimization problem (e.g., such as solution 114 in FIG. 1A).

[0096] As described above, the solution identified by optimizer 110 may be a chromosome cached for a previous population of chromosomes (e.g., via chromosome caching 217) or a chromosome in the most-recently generated population of chromosomes. More specifically, the solution may be a most near-optimal (e.g., “best”) chromosome selected from a pool of chromosomes including the cached chromosomes and the near-optimal chromosome (e.g., with highest fitness score) for the last generated population of chromosomes. For example, the pool of chromosomes may include 100 chromosomes where 100 populations of chromosomes were generated using workflow 200. A most near-optimal chromosome (e.g., with the best fitness score) in this pool of chromosomes may be selected as the solution. . In some cases, this solution is provided to a user via a user interface. In some other cases, more than one solution is selected.

Example Operations for Solving an Optimization Problem Using a Genetic Algorithm

[0097] FIG. 4 depicts an example method 400 of solving an optimization problem using a genetic algorithm. Method 400 may be performed by one or more processor(s) of a computing device, such as processor(s) 502 of processing system 500 described below with respect FIG. 5.

[0098] Method 400 begins, at step 402, with generating a plurality of chromosomes for the optimization problem. Each chromosome may include a first plurality of genes. Each gene may represent one or more characteristics associated with a drilling opportunity. Further, each chromosome may represent a solution to the optimization problem.

[0099] In certain aspects, the one or more characteristics of each gene includes at least one of, for the drilling opportunity associated with the respective gene: a well identifier, a target drilling location identifier, a total revenue, a capital expenditures, an operational expenditure, a barrels of oil equivalent (BOE) volume, a gas volume, an oil volume, a cost per unit of production of oil or gas, a duration, or a risk score.

[0100] Method 400 proceeds, at step 404, with performing steps 406-418 iteratively until a termination condition for the genetic algorithm is met. In certain aspects, the termination condition for the genetic algorithm is met when an iteration counter reaches a threshold. In certain aspects, the termination condition for the genetic algorithm is met when a current highest fitness score among the fitness scores determined for the plurality of chromosomes associated with a current iteration is different than a previous highest fitness score among the fitness score determined for the plurality of chromosomes associated with a previous iteration by less than a threshold.

[0101] Method 400 proceeds, at step 406, with determining whether each of the plurality of chromosomes meets a first set of a plurality of constraints.

[0102] Method 400 proceeds, at step 408, with repairing one or more of the plurality of chromosomes determined not to meet the first set of the plurality of constraints.

[0103] Method 400 proceeds, at step 410, with determining a fitness score for each of the plurality of chromosomes based on at least one objective function and the plurality of constraints. In certain aspects, the at least one objective function comprises a function for measuring at least one of: oil or gas production for one or more drilling opportunities, a cost of the one or more drilling opportunities, a cost per unit of production for the one or more drilling opportunities, a risk of the one or more drilling opportunities, or a duration of completion of the one or more drilling opportunities. In certain aspects, the plurality of constraints include a schedule, the schedule indicates one or more time periods when one or more resources are available; and the first plurality of genes of the chromosome do not meet the schedule when less than all of the drilling opportunities associated with the first plurality of genes are able to be scheduled in the one or more time periods when the one or more resources are available. In certain aspects, the plurality of constraints comprises at least one of: a budget for one or more drilling opportunities, a risk threshold for the one or more drilling opportunities, or an oil or gas production minimum for the one or more drilling opportunities.

[0104] In certain aspects, determining the fitness score for each of the plurality of chromosomes based on the at least one objective function and the plurality of constraints includes: for each chromosome of the plurality of chromosomes: increasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome increase the at least one objective function; and decreasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome decrease the at least one objective function. In certain aspects, determining the fitness score for each of the plurality of chromosomes based on the at least one objective function and the plurality of constraints includes: for each respective chromosome of the plurality of chromosomes: decreasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome increase the at least one objective function; and increasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome decrease the at least one objective function. In certain aspects, determining the fitness score for each of the plurality of chromosomes based on the at least one objective function and the plurality of constraints includes: for each respective chromosome of the plurality of chromosomes, decreasing the fitness score corresponding to the chromosome when at least one of: at least one gene of the first plurality of genes of the chromosome does not meet at least one of the plurality of constraints, or the first plurality of genes of the chromosome do not meet at least one of the plurality of constraints. [0105] Method 400 proceeds, at step 412, with identifying two or more parent chromosomes of the plurality of chromosomes using the fitness score determined for each of the two or more parent chromosomes.

[0106] In certain aspects, identifying the two or more parent chromosomes of the plurality of chromosomes using the fitness score determined for each of the two or more parent chromosomes includes: randomly selecting two or more sets of chromosomes from the plurality of chromosomes; and selecting a chromosome from each of the two or more sets of chromosomes having a greatest fitness score among the fitness scores determined for the chromosomes of each respective set of chromosomes.

[0107] Method 400 proceeds, at step 414, with generating one or more child chromosomes from the two or more parent chromosomes. Each child chromosome may include a second plurality of genes. The second plurality of genes may include at least one gene from each of the two or more parent chromosomes. Further, at least one child chromosome of the one or more child chromosomes is mutated during the generation of the one or more child chromosomes and does not meet a second set of the plurality of constraints.

[0108] In certain aspects, generating the one or more child chromosomes from the two or more parent chromosomes includes, for each of the one or more child chromosomes combining a first percentage of the first plurality of genes of a first parent chromosome of the two or more parent chromosomes with a second percentage of the first plurality of genes of a second parent chromosome of the two or more parent chromosomes. In certain aspects, generating the one or more child chromosomes from the two or more parent chromosomes further includes mutating the at least one child chromosome, wherein mutating the at least one child chromosome includes changing one or more genes in the first percentage of the first plurality of genes belonging to the first parent chromosome or changing one or more genes in the second percentage of the first plurality of genes belonging to the second parent chromosome.

[0109] Method 400 proceeds, at step 416, with repairing the at least one child chromosome to comply with the one or more constraints. In certain aspects, repairing the at least one child chromosome to comply with the one or more constraints comprises changing one or more of the second plurality of genes belonging to the at least one child chromosome. [0110] Method 400 proceeds, at step 418, with replacing one or more of the plurality of chromosomes having lower fitness scores among the fitness scores determined for the plurality of chromosomes with the one or more child chromosomes.

[OHl] In certain aspects, method 400 further includes determining the termination condition for the genetic algorithm is met; and determining a solution to the optimization problem associated with a chromosome from the plurality of chromosomes.

[0112] Note that FIG. 4 is just one example of a method, and other methods including fewer, additional, or alternative steps are possible consistent with this disclosure.

Example Processing System for

[0113] FIG. 5 depicts an example processing system 500 configured to perform various aspects described herein, including, for example, method 400 as described above with respect to FIG. 4

[0114] Processing system 500 is generally an example of an electronic device configured to execute computer-executable instructions, such as those derived from compiled computer code, including without limitation personal computers, tablet computers, servers, smart phones, smart devices, wearable devices, augmented and/or virtual reality devices, and others.

[0115] In the depicted example, processing system 500 includes one or more processors 502, one or more input/output devices 504, one or more display devices 506, one or more network interfaces 508 through which processing system 500 is connected to one or more networks (e.g., a local network, an intranet, the Internet, or any other group of processing systems communicatively connected to each other), and computer-readable medium 570. In the depicted example, the aforementioned components are coupled by a bus 510, which may generally be configured for data exchange amongst the components. Bus 510 may be representative of multiple buses, while only one is depicted for simplicity.

[0116] Processor(s) 502 are generally configured to retrieve and execute instructions stored in one or more memories, including local memories like computer-readable medium 570, as well as remote memories and data stores. Similarly, processor(s) 502 are configured to store application data residing in local memories like the computer-readable medium 570, as well as remote memories and data stores. More generally, bus 510 is configured to transmit programming instructions and application data among the processor(s) 502, display device(s) 506, network interface(s) 508, and/or computer-readable medium 570. In certain embodiments, processor(s) 502 are representative of a one or more central processing units (CPUs), graphics processing unit (GPUs), tensor processing unit (TPUs), accelerators, and other processing devices.

[0117] Input/output device(s) 504 may include any device, mechanism, system, interactive display, and/or various other hardware and software components for communicating information between processing system 500 and a user of processing system 500. For example, input/output device(s) 504 may include input hardware, such as a keyboard, touch screen, button, microphone, speaker, and/or other device for receiving inputs from the user and sending outputs to the user.

[0118] Display device(s) 506 may generally include any sort of device configured to display data, information, graphics, user interface elements, and the like to a user. For example, display device(s) 506 may include internal and external displays such as an internal display of a tablet computer or an external display for a server computer or a projector. Display device(s) 506 may further include displays for devices, such as augmented, virtual, and/or extended reality devices. In various embodiments, display device(s) 506 may be configured to display a graphical user interface.

[0119] Network interface(s) 508 provide processing system 500 with access to external networks and thereby to external processing systems. Network interface(s) 508 can generally be any hardware and/or software capable of transmitting and/or receiving data via a wired or wireless network connection. Accordingly, network interface(s) 508 can include a communication transceiver for sending and/or receiving any wired and/or wireless communication.

[0120] Computer-readable medium 570 may be a volatile memory, such as a random access memory (RAM), or a nonvolatile memory, such as nonvolatile random access memory (NVRAM), or the like. In this example, computer-readable medium 570 includes optimizer 512, gene encoding component 514, chromosome generation component 516, termination determination component 518, fitness score calculation component 520, parent chromosome(s) determination component 522, child chromosome(s) generation component 524, chromosome(s) replacement component 526, repair component 528 (e.g., for chromosome repair and/or repair mutation), genetic algorithm 530, genes 532, chromosomes 534, fitness scores 536, objective function(s) 538, constraint(s) 540, gene characteristics 542, populations/generations 544, resource schedule 546, genetic algorithm output 548, generating logic 550, performing logic 552, determining logic 554, identifying logic 556, repairing logic 558, replacing logic 560, increasing/decreasing logic 562, selecting logic 564, combining logic 566, and changing logic 568.

[0121] In certain aspects, optimizer 512 is configured to use a genetic algorithm to solve an optimization problem.

[0122] In certain aspects, gene encoding component 514 is configured to represent each opportunity and its corresponding characteristics as a gene.

[0123] In certain aspects, chromosome generation component 516 is configured to randomly generate individual solutions (e.g., chromosomes) to form an initial population.

[0124] In certain aspects, termination determination component 518 is configured to determine whether a termination condition for a genetic algorithm has been met or not.

[0125] In certain aspects, fitness score calculation component 520 is configured to calculate a fitness score for each chromosome.

[0126] In certain aspects, parent chromosome(s) determination component 522 is configured to select a proportion of an existing population of chromosomes to breed a new generation of chromosomes.

[0127] In certain aspects, child chromosome(s) generation component 524 is configured to generate one or more child chromosomes from selected parent chromosomes. In certain aspects, child chromosome(s) generation component 524 is configured to perform crossover and/or mutation.

[0128] In certain aspects, chromosome(s) replacement component 526 is configured to replace one or more of the chromosomes in an initial population with one or more child chromosomes.

[0129] In certain aspects, repair component 528 is configured to identify and repair chromosomes determined to violate one or more defined constraints. For example repair component 528 may be configured to identify each chromosome of a population that violates a first set of constraints, and repair as needed. Further, the repair component may be configured to identify mutated child chromosomes that violate a second set of constraints, and repair as needed. The first set of constraints may be different than the second set of constraints. The first and second sets of constraints may each include one or more constraints.

[0130] In certain aspects, genetic algorithm 530 is an adaptive heuristic search algorithm configured to search for an optimal solution by simulating evolution, starting from an initial set of solutions for an optimization problem, and generating successive “generations” of solutions.

[0131] In certain aspects, genes 532 each represent one or more characteristics associated with a drilling opportunity.

[0132] In certain aspects, chromosomes 534 each represent a solution to an optimization problem. Chromosomes 534 may include a plurality of genes 532.

[0133] In certain aspects, fitness scores 536 are functions that measure the quality of a solution, represented by a chromosome, with respect to one or more objective functions and/or one or more constraints.

[0134] In certain aspects, objective function(s) 538 defines the criterion for evaluating a solution.

[0135] In certain aspects, constraint(s) 540 is are a set of restrictions that represent physical, economic, technological, legal, ethical, and/or other limits for genes 532 and/or chromosomes 534.

[0136] In certain aspects, gene characteristics 542 are characteristics associated with a particular drilling opportunity.

[0137] In certain aspects, populations/generations 544 include a plurality of chromosomes 534 that are evaluated via genetic algorithm 530.

[0138] In certain aspects, resource schedule 546 defines the availability of one or more resources over one or more time periods, in some cases, specifically for carrying out one or more drilling opportunities.

[0139] In certain aspects, genetic algorithm output 548 includes multiple drilling opportunities selected from a pool of candidate drilling opportunities, as well as a schedule for performing each of the selected drilling opportunities. [0140] In certain aspects, generating logic 550 includes logic for generating a plurality of chromosomes for an optimization problem. In certain aspects, generating logic 550 includes logic for generating one or more child chromosomes from the two or more parent chromosomes.

[0141] In certain aspects, performing logic 552 includes logic for performing steps iteratively until a termination condition for the genetic algorithm is met.

[0142] In certain aspects, determining logic 554 includes logic for determining a fitness score for each of the plurality of chromosomes based on at least one objective function and one or more constraints. In certain aspects, determining logic 554 includes logic for determining the termination condition for the genetic algorithm is met. In certain aspects, determining logic 554 includes logic for determining the solution to the optimization problem associated with a chromosome from the plurality of chromosomes. In certain aspects, determining logic 554 includes logic for determining whether each of the plurality of chromosomes meets a first set of a plurality of constraints.

[0143] In certain aspects, identifying logic 556 includes logic for identifying two or more parent chromosomes of the plurality of chromosomes using the fitness score determined for each of the two or more parent chromosomes.

[0144] In certain aspects, repairing logic 558 includes logic for repairing the at least one child chromosome to comply with a second set of the plurality of constraints. In certain aspects, repairing logic 558 includes logic for repairing one or more of the plurality of chromosomes determined not to meet a first set of the plurality of constraints.

[0145] In certain aspects, replacing logic 560 includes logic for replacing one or more of the plurality of chromosomes having lower fitness scores among the fitness scores determined for the plurality of chromosomes with the one or more child chromosomes.

[0146] In certain aspects, increasing/decreasing logic 562 includes logic for increasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome increase the at least one objective function. In certain aspects, increasing/decreasing logic 562 includes logic for decreasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome decrease the at least one objective function. In certain aspects, increasing/decreasing logic 562 includes logic for decreasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome increase the at least one objective function. In certain aspects, increasing/decreasing logic 562 includes logic for increasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome decrease the at least one objective function.

[0147] In certain aspects, selecting logic 564 includes logic for randomly selecting two or more sets of chromosomes from the plurality of chromosomes. In certain aspects, selecting logic 564 includes logic for selecting a chromosome from each of the two or more sets of chromosomes having a greatest fitness score among the fitness scores determined for the chromosomes of each respective set of chromosomes. In certain aspects, selecting logic 564 includes logic for selecting a first parent chromosome of the two or more parent chromosomes.

[0148] In certain aspects, combining logic 566 includes logic for combining a first percentage of the first plurality of genes of a first parent chromosome of the two or more parent chromosomes with a second percentage of the first plurality of genes of a second parent chromosome of the two or more parent chromosomes.

[0149] In certain aspects, changing logic 568 includes logic for changing one or more of the second plurality of genes belonging to the at least one child chromosome.

[0150] In certain aspects, changing logic 568 includes logic for changing one or more of the first plurality of genes belonging to the first parent chromosome.

[0151] Note that FIG. 5 is just one example of a processing system consistent with aspects described herein, and other processing systems having additional, alternative, or fewer components are possible consistent with this disclosure.

Example Clauses

[0152] Implementation examples are described in the following numbered clauses:

[0153] Clause 1 : A method for solving an optimization problem using a genetic algorithm, comprising: generating a plurality of chromosomes for the optimization problem, wherein: each chromosome comprises a first plurality of genes, each gene represents one or more characteristics associated with a drilling opportunity, and each chromosome represents a solution to the optimization problem; performing iteratively until a termination condition for the genetic algorithm is met: determining a fitness score for each of the plurality of chromosomes based on at least one objective function and one or more constraints; identifying two or more parent chromosomes of the plurality of chromosomes using the fitness score determined for each of the two or more parent chromosomes; generating one or more child chromosomes from the two or more parent chromosomes, wherein: each child chromosome comprises a second plurality of genes, the second plurality of genes comprising at least one gene from each of the two or more parent chromosomes, and at least one child chromosome of the one or more child chromosomes does not meet at least one of the one or more constraints; repairing the at least one child chromosome to comply with the one or more constraints; and replacing one or more of the plurality of chromosomes having lower fitness scores among the fitness scores determined for the plurality of chromosomes with the one or more child chromosomes.

[0154] Clause 2: The method of Clause 1, wherein the one or more characteristics of each gene comprises at least one of, for the drilling opportunity associated with the respective gene: a well identifier, a target drilling location identifier, a total revenue, a capital expenditure, an operational expenditure, a total barrels of oil equivalent (BOE) volume, a BOE volume per year, a total gas volume, a gas volume per year, an oil volume, an oil volume per year, an after tax cash amount, a cost per unit of production of oil or gas, a duration, or a risk score.

[0155] Clause 3: The method of any one of Clauses 1-2, wherein repairing the at least one child chromosome to comply with the one or more constraints comprises changing one or more of the second plurality of genes belonging to the at least one child chromosome.

[0156] Clause 4: The method of any one of Clauses 1-3, wherein determining the fitness score for each of the plurality of chromosomes based on at least one objective function and one or more constraints comprises: for each chromosome of the plurality of chromosomes: increasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome increase the at least one objective function; and decreasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome decrease the at least one objective function.

[0157] Clause 5: The method of any one of Clauses 1-3, wherein determining the fitness score for each of the plurality of chromosomes based on at least one objective function and one or more constraints comprises: for each respective chromosome of the plurality of chromosomes: decreasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome increase the at least one objective function; and increasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome decrease the at least one objective function.

[0158] Clause 6: The method of any one of Clauses 1-5, wherein the at least one objective function comprises a function for measuring at least one of: oil or gas production for one or more drilling opportunities, a cost of the one or more drilling opportunities, a cost per unit of production for the one or more drilling opportunities, a risk of the one or more drilling opportunities, or a duration of completion of the one or more drilling opportunities.

[0159] Clause 7: The method of any one of Clauses 1-7, wherein determining the fitness score for each of the plurality of chromosomes based on at least one objective function and one or more constraints comprises: for each respective chromosome of the plurality of chromosomes, decreasing the fitness score corresponding to the chromosome when at least one of: at least one gene of the first plurality of genes of the chromosome does not meet at least one of the one or more constraints, or the first plurality of genes of the chromosome do not meet at least one of the one or more constraints.

[0160] Clause 8: The method of Clause 7, wherein: the one or more constraints comprise a schedule, the schedule indicates one or more time periods when one or more resources are available; and the first plurality of genes of the chromosome do not meet the schedule when less than all of the drilling opportunities associated with the first plurality of genes are able to be scheduled in the one or more time periods when the one or more resources are available.

[0161] Clause 9: The method of any one of Clauses 1-8, wherein the one or more constraints comprises at least one of: a budget for one or more drilling opportunities, a risk threshold for the one or more drilling opportunities, or an oil or gas production minimum for the one or more drilling opportunities.

[0162] Clause 10: The method of any one of Clauses 1-9, identifying the two or more parent chromosomes of the plurality of chromosomes using the fitness score determined for each of the two or more parent chromosomes comprises: randomly selecting two or more sets of chromosomes from the plurality of chromosomes; and selecting a chromosome from each of the two or more sets of chromosomes having a greatest fitness score among the fitness scores determined for the chromosomes of each respective set of chromosomes.

[0163] Clause 11 : The method of any one of Clauses 1-10, wherein generating the one or more child chromosomes from the two or more parent chromosomes comprises, for each of the one or more child chromosomes combining a first percentage of the first plurality of genes belonging to a first parent chromosome of the two or more parent chromosomes with a second percentage of the first plurality of genes belonging to a second parent chromosome of the two or more parent chromosomes.

[0164] Clause 12: The method of Clause 11, wherein generating the one or more child chromosomes from the two or more parent chromosomes further comprises at least one of, for at least one of the one or more child chromosomes: changing one or more genes in the first percentage of the first plurality of genes belonging to the first parent chromosome; or changing one or more genes in the second percentage of the first plurality of genes belonging to the second parent chromosome.

[0165] Clause 13: The method of any one of Clauses 1-12, wherein the termination condition for the genetic algorithm is met when an iteration counter reaches a threshold.

[0166] Clause 14: The method any one of Clauses 1-13, wherein the termination condition for the genetic algorithm is met when a current highest fitness score among the fitness scores determined for the plurality of chromosomes associated with a current iteration is different than a previous highest fitness score among the fitness score determined for the plurality fo chromosomes associated with a previous iteration by less than a threshold.

[0167] Clause 15: The method of any one of Clauses 1-13, further comprising determining the termination condition for the genetic algorithm is met; and determining the solution to the optimization problem is associated with a chromosome from the plurality of chromosomes associated with one iteration of the iterations performed having a highest fitness score.

[0168] Clause 16: A processing system, comprising: a memory comprising computerexecutable instructions; and a processor configured to execute the computer-executable instructions and cause the processing system to perform a method in accordance with any one of Clauses 1-15. [0169] Clause 17: A processing system, comprising means for performing a method in accordance with any one of Clauses 1-15.

[0170] Clause 18: A non-transitory computer-readable medium storing program code for causing a processing system to perform the steps of any one of Clauses 1-15.

[0171] Clause 19: A computer program product embodied on a computer-readable storage medium comprising code for performing a method in accordance with any one of Clauses 1-15.

Additional Considerations

[0172] The preceding description is provided to enable any person skilled in the art to practice the various embodiments described herein. The examples discussed herein are not limiting of the scope, applicability, or embodiments set forth in the claims. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments. For example, changes may be made in the function and arrangement of elements discussed without departing from the scope of the disclosure. Various examples may omit, substitute, or add various procedures or components as appropriate. For instance, the methods described may be performed in an order different from that described, and various steps may be added, omitted, or combined. Also, features described with respect to some examples may be combined in some other examples. For example, an apparatus may be implemented or a method may be practiced using any number of the aspects set forth herein. In addition, the scope of the disclosure is intended to cover such an apparatus or method that is practiced using other structure, functionality, or structure and functionality in addition to, or other than, the various aspects of the disclosure set forth herein. It should be understood that any aspect of the disclosure disclosed herein may be embodied by one or more elements of a claim.

[0173] As used herein, a phrase referring to “at least one of’ a list of items refers to any combination of those items, including single members. As an example, “at least one of: a, b, or c” is intended to cover a, b, c, a-b, a-c, b-c, and a-b-c, as well as any combination with multiples of the same element (e.g., a-a, a-a-a, a-a-b, a-a-c, a-b-b, a-c-c, b-b, b-b-b, b-b-c, c-c, and c-c-c or any other ordering of a, b, and c).

[0174] As used herein, the term “determining” encompasses a wide variety of actions. For example, “determining” may include calculating, computing, processing, deriving, investigating, looking up (e.g., looking up in a table, a database or another data structure), ascertaining and the like. Also, “determining” may include receiving (e.g., receiving information), accessing (e.g., accessing data in a memory) and the like. Also, “determining” may include resolving, selecting, choosing, establishing and the like.

[0175] The methods disclosed herein comprise one or more steps or actions for achieving the methods. The method steps and/or actions may be interchanged with one another without departing from the scope of the claims. In other words, unless a specific order of steps or actions is specified, the order and/or use of specific steps and/or actions may be modified without departing from the scope of the claims. Further, the various operations of methods described above may be performed by any suitable means capable of performing the corresponding functions. The means may include various hardware and/or software component(s) and/or module(s), including, but not limited to a circuit, an application specific integrated circuit (ASIC), or processor. Generally, where there are operations illustrated in figures, those operations may have corresponding counterpart means-plus- function components with similar numbering.

[0176] The following claims are not intended to be limited to the embodiments shown herein, but are to be accorded the full scope consistent with the language of the claims. Within a claim, reference to an element in the singular is not intended to mean “one and only one” unless specifically so stated, but rather “one or more.” Unless specifically stated otherwise, the term “some” refers to one or more. No claim element is to be construed under the provisions of 35 U.S.C. §112(f) unless the element is expressly recited using the phrase “means for” or, in the case of a method claim, the element is recited using the phrase “step for.” All structural and functional equivalents to the elements of the various aspects described throughout this disclosure that are known or later come to be known to those of ordinary skill in the art are expressly incorporated herein by reference and are intended to be encompassed by the claims. Moreover, nothing disclosed herein is intended to be dedicated to the public regardless of whether such disclosure is explicitly recited in the claims.

Claims

WHAT IS CLAIMED IS:

1. A method for solving an optimization problem using a genetic algorithm, comprising: generating a plurality of chromosomes for the optimization problem, wherein: each chromosome comprises a first plurality of genes, each gene represents one or more characteristics associated with a drilling opportunity, and each chromosome represents a solution to the optimization problem; performing iteratively until a termination condition for the genetic algorithm is met: determining whether each of the plurality of chromosomes meets a first set of a plurality of constraints; repairing one or more of the plurality of chromosomes determined not to meet the first set of the plurality of constraints; determining a fitness score for each of the plurality of chromosomes based on at least one objective function and the plurality of constraints; identifying two or more parent chromosomes of the plurality of chromosomes using the fitness score determined for each of the two or more parent chromosomes; generating one or more child chromosomes from the two or more parent chromosomes, wherein: each child chromosome comprises a second plurality of genes, the second plurality of genes comprising at least one gene from each of the two or more parent chromosomes, and at least one child chromosome of the one or more child chromosomes is mutated during the generation of the one or more child chromosomes and does not meet a second set of the plurality of constraints; repairing the at least one child chromosome to comply with the second set of the plurality of constraints; and replacing one or more of the plurality of chromosomes having lower fitness scores among the fitness scores determined for the plurality of chromosomes with the one or more child chromosomes.

2. The method of Claim 1, wherein the one or more characteristics of each gene comprises at least one of, for the drilling opportunity associated with the respective gene: a well identifier, a target drilling location identifier, a total revenue, a capital expenditure, an operational expenditure, a total barrels of oil equivalent (BOE) volume, a BOE volume per year, a total gas volume, a gas volume per year, a total oil volume, an oil volume per year, an after tax cash amount, a cost per unit of production of oil or gas, a duration, or a risk score.

3. The method of Claim 1, wherein repairing the at least one child chromosome to comply with the second set of the plurality of constraints comprises changing one or more of the second plurality of genes belonging to the at least one child chromosome.

4. The method of Claim 1, wherein determining the fitness score for each of the plurality of chromosomes based on the at least one objective function and the plurality of constraints comprises: for each chromosome of the plurality of chromosomes: increasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome increase the at least one objective function; and decreasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome decrease the at least one objective function.

5. The method of Claim 1, wherein determining the fitness score for each of the plurality of chromosomes based on the at least one objective function and the plurality of constraints comprises: for each respective chromosome of the plurality of chromosomes: decreasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome increase the at least one objective function; and increasing the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome decrease the at least one objective function.

6. The method of Claim 1, wherein the at least one objective function comprises a function for measuring at least one of: oil or gas production for one or more drilling opportunities, a cost of the one or more drilling opportunities, a cost per unit of production for the one or more drilling opportunities, a risk of the one or more drilling opportunities, a duration of completion of the one or more drilling opportunities.

7. The method of Claim 1, wherein determining the fitness score for each of the plurality of chromosomes based on at least one objective function and the plurality of constraints comprises: for each respective chromosome of the plurality of chromosomes, decreasing the fitness score corresponding to the chromosome when at least one of: at least one gene of the first plurality of genes of the chromosome does not meet at least one of the plurality of constraints, or the first plurality of genes of the chromosome do not meet at least one of the plurality of constraints.

8. The method of Claim 7, wherein: the plurality of constraints comprises a schedule, the schedule indicates one or more time periods when one or more resources are available; and the first plurality of genes of the chromosome do not meet the schedule when less than all of the drilling opportunities associated with the first plurality of genes are able to be scheduled in the one or more time periods when the one or more resources are available.

9. The method of Claim 1, wherein the plurality of constraints comprises at least one of: a budget for one or more drilling opportunities, a risk threshold for the one or more drilling opportunities, or an oil or gas production minimum for the one or more drilling opportunities.

10. The method of Claim 1, identifying the two or more parent chromosomes of the plurality of chromosomes using the fitness score determined for each of the two or more parent chromosomes comprises: randomly selecting two or more sets of chromosomes from the plurality of chromosomes; and selecting a chromosome from each of the two or more sets of chromosomes having a greatest fitness score among the fitness scores determined for the chromosomes of each respective set of chromosomes.

11. The method of Claim 1, wherein generating the one or more child chromosomes from the two or more parent chromosomes comprises, for each of the one or more child chromosomes combining a first percentage of the first plurality of genes belonging to a first parent chromosome of the two or more parent chromosomes with a second percentage of the first plurality of genes belonging to a second parent chromosome of the two or more parent chromosomes.

12. The method of Claim 11, wherein generating the one or more child chromosomes from the two or more parent chromosomes further comprises mutating the at least one child chromosome, wherein mutating the at least one child chromosome comprises: changing one or more genes in the first percentage of the first plurality of genes belonging to the first parent chromosome; or changing one or more genes in the second percentage of the first plurality of genes belonging to the second parent chromosome.

13. The method of Claim 1, wherein the termination condition for the genetic algorithm is met when an iteration counter reaches a threshold.

14. The method of Claim 1, wherein the termination condition for the genetic algorithm is met when a current highest fitness score among the fitness scores determined for the plurality of chromosomes associated with a current iteration is different than a previous highest fitness score among the fitness score determined for the plurality of chromosomes associated with a previous iteration by less than a threshold.

15. The method of Claim 1, further comprising determining the termination condition for the genetic algorithm is met; and determining the solution to the optimization problem is associated with a chromosome from the plurality of chromosomes associated with one iteration of the iterations performed having a highest fitness score.

16. A sy stem compri si ng : one or more processors; and at least one memory, the one or more processors and the at least one memory configured to: generate a plurality of chromosomes for an optimization problem, wherein: each chromosome comprises a first plurality of genes, each gene represents one or more characteristics associated with a drilling opportunity, and each chromosome represents a solution to the optimization problem; perform iteratively until a termination condition for a genetic algorithm is met: determine whether each of the plurality of chromosomes meets a first set of a plurality of constraints; repair one or more of the plurality of chromosomes determined not to meet the first set of the plurality of constraints; determine a fitness score for each of the plurality of chromosomes based on at least one objective function and the plurality of constraints; identify two or more parent chromosomes of the plurality of chromosomes using the fitness score determined for each of the two or more parent chromosomes; generate one or more child chromosomes from the two or more parent chromosomes, wherein: each child chromosome comprises a second plurality of genes, the second plurality of genes comprising at least one gene from each of the two or more parent chromosomes, and at least one child chromosome of the one or more child chromosomes is mutated during the generation of the one or more child chromosomes and does not meet a second set of the plurality of constraints; repair the at least one child chromosome to comply with the second set of the plurality of constraints; and replace one or more of the plurality of chromosomes having lower fitness scores among the fitness scores determined for the plurality of chromosomes with the one or more child chromosomes.

17. The system of Claim 16, wherein the one or more characteristics of each gene comprises at least one of, for the drilling opportunity associated with the respective gene: a well identifier, a target drilling location identifier, a total revenue, a capital expenditure, an operational expenditure, a total barrels of oil equivalent (BOE) volume, a BOE volume per year, a total gas volume, a gas volume per year, a total oil volume, an oil volume per year, an after tax cash amount, a cost per unit of production of oil or gas, a duration, or a risk score.

18. The system of Claim 16, wherein to repair the at least one child chromosome to comply with the second set of the plurality of constraints, the one or more processors and the at least one memory are configured to change one or more of the second plurality of genes belonging to the at least one child chromosome.

19. The system of Claim 16, wherein to determine the fitness score for each of the plurality of chromosomes based on the at least one objective function and the plurality of constraints, the one or more processors and the at least one memory are configured to: for each chromosome of the plurality of chromosomes: increase the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome increase the at least one objective function; and decrease the fitness score corresponding to the chromosome when the first plurality of genes of the chromosome decrease the at least one objective function.

20. A non-transitory computer-readable medium comprising instructions that, when executed by one or more processors of a computing system, cause the computing system to perform operations for solving an optimization problem using a genetic algorithm, the operations comprising: generating a plurality of chromosomes for the optimization problem, wherein: each chromosome comprises a first plurality of genes, each gene represents one or more characteristics associated with a drilling opportunity, and each chromosome represents a solution to the optimization problem; performing iteratively until a termination condition for the genetic algorithm is met: determining whether each of the plurality of chromosomes meets a first set of a plurality of constraints; repairing one or more of the plurality of chromosomes determined not to meet the first set of the plurality of constraints; determining a fitness score for each of the plurality of chromosomes based on at least one objective function and the plurality of constraints; identifying two or more parent chromosomes of the plurality of chromosomes using the fitness score determined for each of the two or more parent chromosomes; generating one or more child chromosomes from the two or more parent chromosomes, wherein: each child chromosome comprises a second plurality of genes, the second plurality of genes comprising at least one gene from each of the two or more parent chromosomes, and at least one child chromosome of the one or more child chromosomes is mutated during the generation of the one or more child chromosomes and does not meet a second set of the plurality of constraints; repairing the at least one child chromosome to comply with the second set of the plurality of constraints; and replacing one or more of the plurality of chromosomes having lower fitness scores among the fitness scores determined for the plurality of chromosomes with the one or more child chromosomes.