Optimized seeding of evolutionary algorithm based simulations

Seed candidate solutions can be inserted into the later generations of the population of an optimization problem during an evolutionary algorithm based simulation. Seed candidate solutions can be determined in response to an evolutionary algorithm based simulator receiving a problem description of an optimization problem. The seed candidate solutions can be sorted according to the seed candidate solutions' fitness. The simulator can start an evolutionary algorithm based simulation with a randomly generated initial population. The simulator can detect a condition for inserting seed candidate solutions into the population. The simulator can then insert the first seed candidate into the current population that is generated by the simulator in accordance with the evolutionary algorithm. A solution to the optimization problem can be determined based on successive generation of candidate solutions and insertion of additional seed candidate solutions in subsequent generations of the population.

BACKGROUND

Embodiments of the inventive subject matter generally relate to the field of evolutionary algorithm based simulations, and, more particularly, to optimizing seeding of evolutionary algorithm based simulations.

Evolutionary algorithms use biological techniques based on biological evolution, reproduction, mutation, recombination, and natural selection to find solutions to optimization problems. Simulations that implement evolutionary algorithms act upon populations, such that individuals in a population represent candidate solutions to an optimization problem. The candidate solutions are evaluated for fitness and the population “evolves” as successive generations of the population are selected/generated based on the biological techniques. As the population evolves, overall fitness of the population tends to increase. A solution to the optimization problem is found when the overall fitness of the population has reached a satisfactory level. Simulations based on evolutionary algorithms can perform well for finding solutions to problems in engineering, biology, economics, robotics, etc. because fitness evaluation functions can be tailored to fit the problems.

SUMMARY

Embodiments include a method directed to determining that a criterion for inserting seed candidate solutions for an optimization problem has been met while an evolutionary algorithm based computer simulation is running and after a first selected generation of candidate solutions has been determined by the computer simulation. In some embodiments, at least a first dataset that represents a first seed candidate solution and can be inserted into a current generation of candidate solutions generated by the computer simulation in response to determining that the criterion for inserting seed candidate solutions has been met. A solution for the optimization problem can be generated from the computer simulation based, at least in part, on a successive generation of candidate solutions produced after said inserting, into the current generation of candidate solutions generated by the computer simulation, at least the first dataset that represents the first candidate solution.

Embodiments include a computer program product for optimizing seeding of evolutionary algorithm based simulations. The computer program product comprises a computer usable medium having computer usable program code. In some embodiments, the computer usable program code is configured to determine that a criterion for inserting seed candidate solutions for an optimization problem has been met while an evolutionary algorithm based computer simulation is running and after a first selected generation of candidate solutions has been determined by the computer simulation. At least a first dataset that represents a first seed candidate solution and can be inserted into a current generation of candidate solutions generated by the computer simulation in response to determining that the criterion for inserting seed candidate solutions has been met. A solution for the optimization problem can be generated from the computer simulation based, at least in part, on a successive generation of candidate solutions produced after said inserting, into the current generation of candidate solutions generated by the computer simulation, at least the first dataset that represents the first candidate solution.

Embodiments include a computer program product for optimizing seeding of evolutionary algorithm based simulations. The computer program product comprises a computer usable medium having computer usable program code. In embodiments, the computer usable program code is configured to determine a plurality of seed candidate solutions to insert into an optimization problem. Fitness metrics of each of the plurality of seed candidate solutions can be determined. When a criterion for inserting seed candidate solutions has been met by a first selected generation of candidate solutions while an evolutionary algorithm based computer simulation is running, the plurality of seed candidate solutions can be inserted into subsequent generations of candidate solutions based, at least in part, on the fitness metrics.

Embodiments include an apparatus comprising a processing unit, a network interface, and an evolutionary algorithm based simulator. In some embodiments, the evolutionary algorithm based simulator is operable to determine that a criterion for inserting seed candidate solutions for an optimization problem has been met while an evolutionary algorithm based computer simulation is running and after a first selected generation of candidate solutions has been determined by the computer simulation. At least a first dataset that represents a first seed candidate solution and can be inserted into a current generation of candidate solutions generated by the computer simulation in response to determining that the criterion for inserting seed candidate solutions has been met. A solution for the optimization problem can be generated from the computer simulation based, at least in part, on a successive generation of candidate solutions produced after said inserting, into the current generation of candidate solutions generated by the computer simulation, at least the first dataset that represents the first candidate solution.

DESCRIPTION OF EMBODIMENT(S)

The description that follows includes exemplary systems, methods, techniques, instruction sequences, and computer program products that embody techniques of the present inventive subject matter. However, it is understood that the described embodiments may be practiced without these specific details. For instance, although examples refer to evolutionary algorithm based simulations, embodiments can utilize specific types of evolutionary algorithms (e.g., genetic algorithms, genetic programming, evolutionary programming, evolution strategy, etc.) suited to fit a particular type of optimization problem being solved. In other instances, well-known instruction instances, protocols, structures, and techniques have not been shown in detail in order not to obfuscate the description.

The candidate solutions to an optimization problem comprise a set of potential parameters than can be applied to variables in the problem. For example, an electronic design may be optimized. Variables in the electronic design can include transmission line length, transmission line spacing, driver strengths, etc. The candidate solutions represent a set of potential parameters that can be applied to the line length, transmission line spacing, and driver strength variables in the electronic design. Usually, an initial population (i.e., generation 0) of candidate solutions is randomly chosen based on a domain of the optimization problem. The randomly generated initial population tends to be unfit, so it can take many generations for the population to reach a satisfactory level of fitness. Seeding helps to decrease the number of generations generated to find an optimal solution. Usually, the initial population is seeded with candidate solutions that are likely to be near optimal solutions so that the initial population comprises seed candidate solutions and randomly generated candidate solutions. The seed candidate solutions are usually more fit than the randomly generated candidate solutions and have a higher likelihood of being chosen for successive generations. So, weaker candidate solutions are eliminated from the population much faster. However, quickly eliminating weaker candidate solutions can cause an evolutionary algorithm based simulation to converge on local optima (e.g., the seeds themselves, and/or minor variations of the seeds) because strong components of the weaker candidate solutions may never have a chance to affect the population.

Seed candidate solutions can be inserted into the later generations of the population of an optimization problem during an evolutionary algorithm based simulation. Inserting seed candidate solutions into later generations allow weaker candidate solutions with strong components or attributes to survive, thus allowing succeeding generations to inherit the stronger components. Seed candidate solutions can be determined based on a problem description of an optimization problem. The seed candidate solutions can be sorted according to the seed candidate solutions' fitness. The evolutionary algorithm based simulator can start an evolutionary algorithm based simulation with a randomly generated initial population. The evolutionary algorithm based simulator can later detect a condition for inserting seed candidate solutions into the population. For example, the evolutionary algorithm based simulator can detect that a number of generations has reached a threshold. As another example, the evolution algorithm based simulator can detect that overall fitness of the population has reached a threshold. The evolutionary algorithm based simulator can then insert the first seed candidate into the current population that is generated/selected by the evolutionary algorithm based simulator in accordance with the evolutionary algorithm. A solution to the optimization problem can be determined based on a generation of candidate solutions influenced by the insertion of additional seed candidate solutions in Nthgenerations of the population.

FIG. 1is an example conceptual diagram of inserting seed candidate solutions during an evolutionary algorithm based simulation. At stage A, an evolutionary algorithm based simulator101receives a problem description113. The problem description113can define the optimization problem. Examples of optimization problems include input/output (I/O) circuit design, high performance computing (HPC) bidding, adder design, compiler tuning, etc. The problem description113can indicate variables of the optimization problem, a domain for the candidate solutions, constraints, a fitness evaluation function, seed candidate solutions, criteria for inserting the seed candidate solutions, termination criteria, etc.

The evolutionary algorithm based simulator101generates a population of an initial generation (i.e., generation 0) based on the received problem description (103). The population comprises a plurality of candidate solutions to the optimization problem. Each of the candidate solutions can be represented by a dataset that can be organized based on the variables of the optimization problem. Each dataset stores one value/parameter for each of the variables, such that an optimization problem with N variables has datasets comprising N parameters. The evolutionary algorithm based simulator101determines a number of candidate solutions to generate based on the problem description113. For example, the problem description113indicates that the population should comprise100candidate solutions. The evolutionary algorithm based simulator101can randomly generate parameters for the candidate solutions based on the domain indicated in the problem description113. For example, the optimization problem can comprise three variables: var—1, var—2, and var—3. The domain indicates that parameters in the candidate solution should lie within ranges (0, 10), (5, 26], and [−10, 10] for var—1, var—2, and var—3, respectively. The domain also specifies that var—1 and var—3 cannot be equal in any particular candidate solution. So, the evolutionary algorithm based simulator101generates random numbers (i.e., the parameters) for each of the variables based on the ranges and makes sure that the generated random numbers are not the same for var—1 and var—3. The evolutionary algorithm based simulator101continues to generate groups of three random numbers for var—1, var—2, and var—3 until the number of candidate solutions is reached. After determining the initial population, the evolutionary algorithm based simulator101begins an evolutionary algorithm based simulation.

The evolutionary algorithm based simulator101evaluates the population (105). The evolutionary algorithm based simulator101evaluates each candidate solution based on applying the parameters indicated in the candidate solutions to variables in the optimization problem and running a simulation of the candidate solution. For example, an electronic design can be defined in the problem description113. The evolutionary algorithm based simulator101can generate simulation decks for each candidate solution based on applying the parameters indicated by each candidate solution to variables of the electronic design. The evolutionary algorithm based simulator101can run a simulation of each simulation deck using a Simulation Program with Integrated Circuit Emphasis (SPICE) simulation tool and collect results of each simulation. As another example, the problem description113indicates a computer program to be optimized. The evolutionary algorithm based simulator101can run the computer program for each of the candidate solutions by applying the parameters of the candidate solutions to variables of the computer program. The evolutionary algorithm based simulator101can collect results of each run of the computer program. The techniques (e.g., SPICE simulations, running computer programs, etc.) for evaluating the population can be defined as part of the fitness evaluation function indicated in the problem description113.

The evolutionary algorithm based simulator101determines fitness of the population (107). The fitness can be represented by a numerical value within a range specified in the problem description113. For example, the fitness can be represented by a percentage. Determining fitness of the population107can comprise determining individual fitness metrics of each candidate solution. The evolutionary algorithm based simulator101can determine each candidate solution's individual fitness metric based on the fitness evaluation function indicated in the problem description113. For example, the evolutionary algorithm based simulator101can analyze the simulation results of each candidate solution based on indicated heuristics. The evolutionary algorithm based simulator101can determine the fitness of the population based on aggregating the individual fitness metrics. For example, the evolutionary algorithm based simulator101can average the individual fitness metrics. As another example, the evolutionary algorithm based simulator101can take the median of the individual fitness metrics.

The evolutionary algorithm based simulator101determines if termination criteria has been met (111). Termination criteria can be indicated in the problem description113. For example, the evolutionary algorithm based simulation may terminate when fitness of the population reaches an indicated satisfactory level. As another example, the evolutionary algorithm based simulation may terminate when fitness of the population reaches a plateau. As another example, the evolutionary algorithm based simulation may terminate when a specified number of generations has been reached. If termination criteria have been met, a solution117is output by the evolutionary algorithm based simulator101. The solution117can comprise indications of each of the candidate solutions that constitute the population at termination, individual fitness metrics of each of the candidate solutions, simulation/test results, etc.

If the termination criteria have not been met, the evolutionary algorithm based simulator101determines a next generation of the population (109). For example, the current generation is generation 0, so the evolutionary algorithm based simulator101determines a generation 1. The evolutionary algorithm based simulator101can determine the next generation in accordance with a combination of biological techniques based on evolution, reproduction, mutation, recombination, and natural selection. For example, the evolutionary algorithm based simulator101can select a certain number of the candidate solutions of generation 0 to remain unchanged in generation 1 based on survival of the fittest techniques. The unchanged individuals can represent a portion of the population of generation 1. As another example, the evolutionary algorithm based simulator101can select candidate solutions from generation 0 as parents to reproduce offspring candidate solutions for a portion of the population of generation 1. As another example, another portion of the population can be generated based on mutating candidate solutions of generation 0. In addition, a seeding unit115can insert candidate solutions into the next generation when the seeding unit115detects a condition for inserting the candidate solutions. After the next generation of the population is determined, the evolutionary algorithm based simulator101repeats the evaluation (105) and determination of fitness (107) on the next generation. The blocks105,107,111, and109repeat for each successive generation until termination criteria is met.

At stage B, the seeding unit115determines points in the domain that solutions are likely to be found (“seed candidate solutions”) from the problem description113. The seed candidate solutions can be selected by a designer of the problem based on the designer's experience.

At stage C, the seeding unit115determines fitness metrics of each of the seed candidate solutions. The seeding unit115uses the fitness evaluation function indicated in the problem description113to determine the fitness metrics of each of the seed candidate solutions. For example, the seeding unit115simulates each of the seed candidate solutions and determines fitness metrics based on the results of the simulation.

Stages B and C can occur while the initial population is generated (103) by the evolutionary algorithm based simulator101.

At stage D, the seeding unit115determines that a criterion for inserting seed candidate solutions into the population has been met. Criteria for inserting seed candidate solutions can be indicated in the problem description113. For example, the seeding unit115determines that seed candidate solutions should be inserted after a certain number of generations have been determined. The seeding unit115determines if a variable representing a number of the current generation equals the number of generations. As another example, the seeding unit can determine that an aggregate fitness metric of the population determined in block107meets a fitness threshold indicated in the problem description113. As another example, the seeding unit determines that seed candidate should be inserted when either the number of generations is met or the fitness threshold is satisfied.

At stage E, the seeding unit115inserts one or more of the seed individuals into the population of the next generation according to fitness of the seed candidate solutions. For example, the seeding unit115inserts seed candidate solutions into successive generations in the order of least to most fit. The insertions into the successive generations can be based on an insertion interval that defines the average number of generations between insertions of the seed candidate solutions. As another example, seed candidate solutions can be inserted based on the fitness of each seed candidate solution and fitness of the population. For example, seed candidate solutions with fitness within a threshold of the population's fitness can be inserted.

The seeding unit115can deposit datasets representing the seed candidate solutions into a memory location accessible by both the evolutionary algorithm based simulator101and the seeding unit115. The evolutionary algorithm based simulator101can determine the seed candidate solutions from the memory location. Before determining candidate solutions for the population of the next generation based on the biological techniques, the evolutionary algorithm based simulator101can check the memory location. If a dataset is found in the memory location, the evolutionary algorithm based simulator101can add the dataset representing the candidate solutions into the population of the next generation then determine the remainder of candidate solutions for the next generation based on the biological techniques.

AlthoughFIG. 1depicts the seeding unit115as a separate entity from the evolutionary algorithm based simulator101, the seeding unit115can be a component of the evolutionary algorithm based simulator101.

FIGS. 2-3are flowcharts depicting example operations for inserting seed candidate solutions during an evolutionary algorithm based simulation. At block201, seed candidate solutions are determined in response to an evolutionary algorithm based simulator receiving a problem description. The problem description can indicate the seed candidate solutions. For example, the problem description can indicate a reference to datasets that represent the seed candidate solutions. Each dataset can comprise one parameter for each variable defined in the problem description.

At block203, fitness metrics of each of the seed candidate solutions is determined. The fitness metrics can be determined using a fitness evaluation function indicated in the problem description. The problem description can include a code/script implementing the fitness evaluation function, a reference to the code, a code hash value, etc. The fitness metrics can be represented by a numerical value within a specified range. A designer of the optimization problem can provide the fitness evaluation function and range for the fitness metrics. A fitness metric of each seed candidate solution can be stored in the dataset that represents the seed candidate solution.

At block205, the seed candidate solutions are sorted based on fitness. In this example, the seed candidate solutions can be sorted from least to most fit based on the fitness metrics.

At block207, an insertion interval for inserting seed candidate solutions into a population are determined. The insertion interval can indicate the average number of generations between insertions of the seed candidate solutions into the population. For example, an insertion interval of 0.5 can indicate that an average of two seed candidate solutions should be inserted into every generation. As another example, an insertion interval of 2 can indicate that an average of one seed candidate solution should be inserted every other generation.

At block209, a plurality of random numbers is generated based on a count of the seed candidate solutions and the insertion interval. The plurality of random numbers can be generated within the range of 0 to the count multiplied by the insertion interval (i.e., between 0 and (count*insertion interval)). An average distance between the random numbers should be close to the insertion interval because the random numbers were generated based on the count and the insertion interval.

At block211, the plurality of random numbers is sorted from smallest to largest.

At block213, one of the plurality of random numbers is assigned to each of the seed candidate solution based on the fitness metrics. The assignment can be made such that the smallest random number is assigned to the least fit seed candidate solution and the largest random number is assigned to the most fit seed candidate solution. Assigning one of the plurality of random numbers to each of the seed candidate solutions can comprise storing the random number in a dataset that represents each of the candidate solutions. Each of the plurality random numbers can indicate a generation of the population to insert the corresponding seed candidate solutions. For example, when the generation number is equal to one of the plurality of random numbers, a seed candidate solution corresponding to the random number can be inserted into the population. An average number of generations between insertions of the seed candidate solutions should be the insertion interval because the random numbers were generated based on the insertion interval. Flow continues at block301ofFIG. 3.

FIG. 3is a flowchart depicting example operations for inserting seed candidate solutions during an evolutionary algorithm based simulation that continues fromFIG. 2. At block301, it is determined if a criterion for inserting seed candidate solutions into the population has been met by the current generation. Once the criterion is met, seed individuals can be inserted into the next generation. For example, the criterion indicates that seed individuals should be inserted after a certain number of generations of the population have been evaluated. As another example, the criterion indicates that seed individuals should be inserted after a fitness threshold has been satisfied by the population. When an aggregate fitness metric of the candidate solutions that constitute the population is equal to or greater than the fitness threshold, seed candidate solutions can be inserted into the population. The fitness metric can be based on an average of the candidate solutions' fitness metrics, a median of the candidate solutions fitness metrics, etc. In addition, the criterion can be based on a combination of a fitness threshold and a number of generations. For example, a criterion indicates that seed individuals can be inserted after the fitness of the population satisfies the fitness threshold and a certain number of generations have been evaluated.

At block303, a loop begins for each subsequent generation.

At block305, an offset of the generation is determined. The offset can represent a number of generations that have been generated and evaluated by the evolutionary algorithm based simulator since the criterion was met.

At block307, it is determined if one of the random numbers is equal to the offset. If one of the random numbers is equal to the offset, flow continues at block309. If none of the random numbers are equal to the offset, flow continues at block311.

At block309, the seed candidate solution associated with the random number is inserted into the population of the generation. For example, an evolutionary algorithm based simulator can locate a dataset that represents the seed candidate solution based on the random number. The evolutionary algorithm based simulator can insert the dataset into the generation of candidate solutions. In some examples, the population may be comprised of multiple demes/sub-populations. Inserting the seed candidate solution can comprise determining one of the sub-populations in which the seed candidate solution should be inserted. For example, the evolutionary algorithm based simulator can insert the seed candidate solution into a randomly selected sub-population. As another example, the evolutionary algorithm based simulator can select the sub-population based on fitness and insert the seed candidate solution into the most fit sub-population.

At block311, the loop for each subsequent generation ends.

Seeding a population with candidate solutions that are significantly more fit than other individuals in the population can cause the weaker individuals to be eliminated too rapidly. Seed candidate solutions can be inserted into the population when an aggregate fitness metric of the population is within a threshold of the seed candidate solutions' fitness metrics so that seed candidates are not inserted until the fitness of the population reaches the seed candidates' fitness levels.FIG. 4is a flowchart of example operations for inserting seed candidate solutions during an evolutionary algorithm based simulation based on fitness. Flow begins at block401, where seed candidate solutions are determined in response to an evolutionary algorithm based simulator receiving a problem description.

At block403, fitness metrics of each of the seed candidate solutions is determined. The fitness metrics can be determined using a fitness evaluation function indicated in the problem description.

At block405, the seed candidate solutions are sorted from least to most fit.

At block407, a loop begins for each generation.

At block409, an aggregate fitness metric of the population is determined. Determining the aggregate fitness metric can comprise determining individual fitness metrics of each of the candidate solutions that constitute the population. The individual fitness metrics can be determined based on a fitness evaluation function indicated in the problem description. The aggregate fitness metric can be based on an average of the individual fitness metrics, a median of the fitness metrics, etc. If the population is comprised of multiple demes/sub-populations, aggregate fitness metrics can be determined for each sub-population along with the aggregate fitness metric of the entire population.

At block411, it is determined if a least fit candidate solution is within a threshold of the aggregate fitness metric. The threshold can be indicated in the problem description. For example, the least fit seed candidate's fitness metric is within the threshold if the least fit seed candidate's fitness metric does not deviate more than 10 percent from the aggregate fitness metric. More than one of the candidate solutions' fitness metrics can be within the threshold of the aggregate fitness metric. If the least fit seed candidate's fitness metric is within a threshold of the aggregate fitness metric, flow continues at block413. If the least fit seed candidate's fitness metric is not within a threshold of the aggregate fitness metric, flow continues at block415.

At block413, the least fit seed candidate solution is inserted into the population of the next generation. When the least fit seed candidate solution is inserted, the fitness metric of the next least fit candidate is compared to the aggregate fitness metric, and so on until there are no more seed candidate solutions to insert. In addition, more than one seed candidate solution can be inserted into the population when more than one of the seed candidate solutions' fitness metrics are within the threshold of the aggregate fitness metric. If the population comprises multiple sub-populations, one of the sub-populations can be selected for inserting the least fit seed candidate solution. For example, the sub-population can be selected randomly. The least fit seed candidate solution can be inserted into the selected sub-population when the seed candidate solution's fitness metric is within a threshold of the sub-population's aggregate fitness metric.

At block415, the loop ends.

Although examples refer to inserting seed candidate solutions from least to most fit, embodiments are not so limited. For example, the seed candidate solutions can be inserted into successive generations in random order. Each seed candidate solution can be assigned a random number. Seed candidate solutions can be sorted based on the corresponding random numbers. An insertion interval, N, can indicate the frequency for inserting the seed candidate solutions. So, the seed candidate solutions can be inserted every N generations based on the smallest to largest random numbers. As another example, all of the seed candidate solutions can be inserted into a selected generation at the same time.

Embodiments are not limited to the example flowcharts depicted in the above figures. Embodiments can perform additional operations, fewer operations, operations in parallel, etc. For instance, referring toFIG. 2the operations for sorting the seed candidate solutions and sorting the random numbers can occur in parallel.

FIG. 5depicts an example computer system. A computer system includes a processor unit501(possibly including multiple processors, multiple cores, multiple nodes, and/or implementing multi-threading, etc.). The computer system includes memory507. The memory507may be system memory (e.g., one or more of cache, SRAM, DRAM, zero capacitor RAM, Twin Transistor RAM, eDRAM, EDO RAM, DDR RAM, EEPROM, NRAM, RRAM, SONOS, PRAM, etc.) or any one or more of the above already described possible realizations of machine-readable media. The computer system also includes a bus503(e.g., PCI bus, ISA, PCI-Express bus, HyperTransport® bus, InfiniBand® bus, NuBus bus, etc.), a network interface505(e.g., an ATM interface, an Ethernet interface, a Frame Relay interface, SONET interface, wireless interface, etc.), and a storage device(s)509(e.g., optical storage, magnetic storage, etc.). The computer system also includes an evolutionary algorithm based simulator521. The evolutionary algorithm based simulator521finds solutions to optimization problems in accordance with evolutionary algorithms. The evolutionary algorithm based simulator521comprises a seeding unit522. The seeding unit522can determine that a criterion for inserting seed candidate solutions into a generation of candidate solutions is satisfied and insert seed candidate solutions into the generation based on a fitness criterion and/or an insertion interval. Any one of these functionalities may be partially (or entirely) implemented in hardware and/or on the processing unit501. For example, the functionality may be implemented with an application specific integrated circuit, in logic implemented in the processing unit501, in a co-processor on a peripheral device or card, etc. Further, realizations may include fewer or additional components not illustrated inFIG. 5(e.g., video cards, audio cards, additional network interfaces, peripheral devices, etc.). The processor unit501, the storage device(s)509, and the network interface505are coupled to the bus503. Although illustrated as being coupled to the bus503, the memory507may be coupled to the processor unit501.

While the embodiments are described with reference to various implementations and exploitations, it will be understood that these embodiments are illustrative and that the scope of the inventive subject matter is not limited to them. In general, techniques for optimizing seeding of evolutionary algorithm based simulations as described herein may be implemented with facilities consistent with any hardware system or hardware systems. Many variations, modifications, additions, and improvements are possible.