Source: http://www.google.sh/patents/US8131656
Timestamp: 2013-05-20 14:45:25
Document Index: 244832972

Matched Legal Cases: ['art 1', 'art 2', 'art 1', 'art 2', 'art 1', 'art 2']

Patent US8131656 - Adaptive optimization methods - Google PatentsSearch Images Play Gmail Drive Calendar Translate Books More »Advanced Patent Search | Web History | Sign inAdvanced Patent SearchPatentsMethods and systems for optimizing a solution set. A solution set is generated, and solutions in the solution set are evaluated. Desirable solutions from the solution set are selected. A structural model is created using the desirable solutions, and a surrogate fitness model is created based on the structural...http://www.google.sh/patents/US8131656?utm_source=gb-gplus-sharePatent US8131656 - Adaptive optimization methodsPublication numberUS8131656 B2Publication typeGrantApplication number11/701,066Publication date6 Mar 2012Filing date31 Jan 2007Priority date31 Jan 2006Also published asUS20070208677InventorsDavid E. GoldbergClaudio F. LimaFenando G. LoboKumara SastryOriginal AssigneeThe Board Of Trustees Of The University Of IllinoisBoard Of Trustees Of The University Of Illinois, TheU.S. Classification706/13706/14International ClassificationG06F15/18Cooperative ClassificationG06N7/005G06N3/12European ClassificationG06N 3/12G06N 7/00PReferencesPatent Citations (40)Non-Patent Citations (132)Referenced by (2)External LinksUSPTOUSPTO AssignmentEspacenetAdaptive optimization methodsUS 8131656 B2Abstract Methods and systems for optimizing a solution set. A solution set is generated, and solutions in the solution set are evaluated. Desirable solutions from the solution set are selected. A structural model is created using the desirable solutions, and a surrogate fitness model is created based on the structural model and the desirable solutions. A new solution set may be generated and/or evaluated, based on analyzing at least one of the structural model and the surrogate fitness model, and determining a method for generating a new solution set and/or evaluating the new solution set based at least in part on the analyzing.
PRIORITY CLAIM AND REFERENCE TO RELATED APPLICATION This application claims the benefit of U.S. Provisional Application Ser. No. 60/763,801, filed Jan. 31, 2006, under 35 U.S.C. �119.
STATEMENT OF GOVERNMENT INTEREST This invention was made with Government support under Contract Number F49620-03-1-0129 awarded by Air Force Office of Scientific Research (AFOSR). The Government has certain rights in the invention.
BACKGROUND OF THE INVENTION This invention relates generally to the field of methods for optimization, and in preferred embodiments relates more particularly to the field of genetic and evolutionary algorithms (GAs). The invention further relates generally to computer programs and computer-aided methods for optimization.
One type of optimization method is the genetic or evolutionary algorithm (GA). In GAs, individual variables are analogous to �genes�, and a particular solution to an optimization problem, including a plurality of variables, is analogous to a �chromosome�. The variables may be, for example: bits; discrete, fixed-length representations; vectors; strings of arbitrary length; program codes; etc. Other types of optimization methods include, but are not limited to, evolutionary computing, operations research (OR), global optimization methods, meta-heuristics, artificial intelligence and machine learning techniques, etc., and methods of the present invention may be applicable to one or more of these optimization methods as well.
Those knowledgeable in the art will appreciate that �fitness� generally refers to how good a candidate solution is with respect to the problem at hand. Fitness may also be thought of as solution quality, and fitness evaluation therefore may be thought of as solution quality assessment, a function evaluation, or an objective value evaluation. Fitness evaluation may be, for example, objective, subjective (e.g., by a human), and/or via a vector of evaluations (e.g., multiobjective optimization).
Through multiple iterations of evaluating individuals within a population for fitness, and through generating new populations based at least partly on �survival of the fittest� for solutions, GAs can be used to provide acceptable or optimal solutions for a variety of problems. However, concerns exist regarding the use of GAs and other optimization methods.
Another concern is the amount of resources required for the fitness evaluation step. When faced with a large-scale problem, the step of evaluating the fitness or quality of all of the solutions can demand high computer resources and execution times. To improve efficiency, fitness evaluation may be handed off to a computational procedure to determine fitness. However, for large-scale problems, the task of computing even a sub-quadratic number of function evaluations can be daunting. This is especially the case if the fitness evaluation is a complex simulation, model, or computation. The fitness evaluation step often presents a time-limiting �bottleneck� on performance that makes use of some conventional GAs impractical for some applications.
Thus, a number of optimization techniques for GAs have been employed in the art having at least a partial goal of reducing the number of fitness evaluations necessary to achieve convergence. Optimizations have led to so-called �competent� GAs, which are GAs that solve large, hard problems quickly, reliably, and accurately.
Linked variables may be thought of as forming �module� or, as referred to herein, �building blocks (BBs)�. Understanding that most GAs process building blocks, and using this understanding to solve problems, can aid in design of GAs. In certain embodiments, once identified in some way, such BBs may be manipulated in groups to provide new populations. As one non-limiting example, mutation may be performed as a BB-wise operation, as opposed to a simple bit-wise operation.
SUMMARY OF THE INVENTION A method for optimizing a solution set is provided according to exemplary embodiments of the present invention. A solution set is generated, and solutions in the solution set are evaluated. Desirable solutions from the solution set are selected. A structural model is created using the desirable solutions, and a surrogate fitness model is created based on the structural model and the desirable solutions.
BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 shows an exemplary optimization method incorporating one or more techniques for efficiency enhancement, according to embodiments of the present invention;
DETAILED DESCRIPTION Some embodiments of the present invention are directed to methods and program products for optimizing a solution set for a problem. Those knowledgeable in the art will appreciate that embodiments of the present invention lend themselves well to practice in the form of computer program products. Accordingly, it will be appreciated that embodiments of the invention may comprise computer program products comprising computer-executable instructions stored on a computer-readable medium that when executed cause a computer to undertake certain steps. Other embodiments of the invention include systems for optimizing a solution set, with an example being a processor-based system capable of executing instructions that cause it to carry out a method of the invention. Results of exemplary methods may be displayed on one or more displays and/or stored in a suitable memory. It will accordingly be appreciated that description made herein of a method of the invention may likewise apply to a program product of the invention and/or to a system of the invention.
One type of efficiency enhancement technique is parallelization. Non-limiting examples of parallelization techniques are disclosed in Cant�-Paz, E., Efficient and accurate parallel genetic algorithms, Boston, Mass.: Kluwer Academic Press, 2000. Generally, parallelization increases the amount of hardware used to solve a problem to speed along a solution, such as by providing hardware for parallel computation. However, parallel computation is notoriously susceptible to so-called serial and communications bottlenecks that diminish the efficiency of the added hardware. Fortunately, even the simplest master-slave GAs have been shown to exhibit linear speedups for numbers of processors up to the limit {square root over (nTf/TC)}, where n is the required population size, Tf is the time per function evaluation, and TC is the time required for communication between master and slave per evaluation. More careful parallelization can effectively use additional processors, and this idea can be exploited by embodiments of the present invention.
Evaluation relaxation takes an expensive fitness evaluation and tries to �cheapen� it in a variety of ways. In stochastic simulation, for example, fewer samples may be tried. In complex field problems or elsewhere where numerical simulations of differential or integral equations are necessary, techniques of discretization scheduling may be used. It may also be possible to inherit fitness values from previous evaluations in a systematic manner or create explicit fitness surrogates. Examples of evaluation relaxation techniques are known in the art. One of the challenges in evaluation relaxation is to differentiate between bias and variance as sources of error and to use an appropriate strategy (temporal vs. spatial, respectively) for each type.
Another efficiency enhancement technique, referred to herein as �time continuation�, concerns efficient time budgeting. Time continuation deals with the tradeoffs between schemes involving large populations running for a single or small number of generations (epochs) versus smaller populations running through several continuation generations. Thus, time continuation asks about the appropriate temporal sequence of the solution procedure; i.e., is it population oriented, essentially sequential, or a mix? This represents an exploitation-exploration tradeoff by considering when the algorithm should stop working with the current population and attempt to explore new regions of the search space. Examples of time continuation are disclosed in Srivastava, R., Time Continuation in Genetic Algorithms, Masters Thesis, University of Illinois at Urbana-Champaign, Urbana, Ill., 2002, which is incorporated by reference herein.
Different problems and approaches may lead to different population sizes for the initial solution set. By way of example only, in a 10�4 trap function problem, the solution space has a total of 240 different potential solutions. When optimizing such a solution through an exemplary method of the invention, an initial solution set may be created of a population size of about 1600 through random or other sampling of the solution space.
Referring again to FIG. 1, a number of desirable solutions are selected from the solution set. Preferably, this is done by evaluating the fitness of all of the solutions in the solution set (step 103), and selecting the desirable solutions based on the evaluated fitness (step 104). Those knowledgeable in the art will appreciate that �fitness� generally refers to how good a candidate solution is with respect to the problem at hand. Fitness may also be thought of as solution quality, and fitness evaluation therefore thought of as solution quality assessment or an objective value evaluation.
Fitness estimation, though it may include some amount of calculation, is computationally less expensive (i.e., requires less processing power) and requires less execution time than fitness calculation, but also provides less precision. Thus, a fitness calculation is also referred to as an �expensive fitness evaluation� herein.
Some balance preferably should be achieved between accuracy of fitness determination and computation resources consumed. Thus, decision criteria may be used to determine whether fitness estimation, fitness calculation, or a proportion of each will be used to determine fitness. Examples of these decision criteria may be found, for example, in co-pending U.S. patent application Ser. No. 11/343,195, filed Jan. 30, 2006, entitled �METHODS FOR EFFICIENT SOLUTION SET OPTIMIZATION�, which is incorporated herein by reference. Additional discussion of decision criteria is also provided below.
At least two models, a structural model (step 106) and a fitness surrogate model (step 108), are then built based at least on the selected solutions. The structural model (step 106) should be representative, in some manner, of the desirable solutions. The structural model also preferably provides some knowledge, either implicit or explicit, of a relationship between variables. As used herein, the terms �structure,� �structural�, and �structured� when used in this context are intended to be broadly interpreted as referring to inferred or defined relations between variables. Based on the type of model, the illustrative embodiment of FIG. 1 creates a structural model by data mining the structural information provided by the selected desirable solutions. In certain embodiments, the structural information may also be partly provided by previously selected solutions.
Other steps of curve fitting in addition to performing a least squares fit may likewise be performed. For example, an additional step believed to be useful is to perform a recursive least squares fit. A step of performing a recursive least squares fit will provide the benefit of avoiding creating the model from the �ground up� on every iteration. Instead, a previously created model can be modified by considering only the most recently generated expensive data points from a database of previous expensive fitness calculations. In many applications, this may provide significant benefits and advantages. Those knowledgeable in the art will appreciate that many other known steps of fitting coefficients using stored data points will be useful.
Based on the analysis of the structural model and/or the fitness surrogate model, one or more efficiency enhancement techniques may be performed that affect generation of new solution sets, fitness evaluation of solutions, model building, etc. As one non-limiting example, if evaluation relaxation is to be used (step 112), the structural model may be used to infer the form of the surrogate model when forming the surrogate fitness model. The surrogate fitness model may be used to partially or fully replace the expensive fitness evaluation. Additionally, data mining the surrogate fitness model can provide criteria for determining the proportion of new solutions that are evaluated (step 103) using the surrogate fitness model and the expensive fitness evaluation. Exemplary criteria to consider are provided in U.S. patent application Ser. No. 11/343,195. Other examples of exemplary criteria that may be used with the surrogate fitness model are disclosed in Sastry, K., Pelikan, M. & Goldberg, D. E., �Efficiency enhancement of genetic algorithms via building-block-wise fitness estimation�, Proceedings of the IEEE International Conference on Evolutionary Computation, 720-727, 2004; Pelikan, M. & Sastry, K., �Fitness inheritance in the Bayesian optimization algorithm�, Proceedings of the Genetic and Evolutionary Computation Conference, 2, 48-59, 2004; and Sastry, K., Lima, C. F., & Goldberg, D. E., �Evaluation relaxation using substructural information and linear estimation�, Proceedings of the 2006 Genetic and Evolutionary Computation Conference, 419-426, 2004. These documents are incorporated herein by reference.
As another example, if time continuation is to be used (step 114), the structural model may be used to infer the form of the surrogate fitness model, and the surrogate fitness model may be used to infer scaling, signal-to-noise ratio, etc., to decide an optimal proportion of crossover and mutation dominated search. In exemplary, non-limiting embodiments, the selected method for generating new solutions can be affected by the decided proportion. Exemplary criteria for time continuation that can be met by analyzing the structural model and/or the surrogate fitness model can be found in Sastry, K. and Goldberg, D. E., �Let's get ready to rumble: Crossover versus mutation head to head�, Proceedings of the Genetic and Evolutionary Computation Conference, 2, 126-137, 2004; Sastry, K. & Goldberg, D. E., �Designing competent mutation operators via probabilistic model building of neighborhoods�, Proceedings of the Genetic and Evolutionary Computation Conference, 2, 114-125, 2004; and Lima, C., Sastry, K., Goldberg, D. E., & Lobo, F., �Combining competent crossover and mutation operators: A probabilistic model building approach�, Proceedings of the 2005 Genetic and Evolutionary Computation Conference, 735-742, 2005. These documents are incorporated herein by reference.
If hybridization is to be used (step 116), the structural model may be used to infer the form of the surrogate fitness model, and may also be used in particular embodiments to infer the neighborhoods used by local-search operators. The surrogate fitness model may used to optimally decide between the proportion of global and local search, to choose the best local search among the available local search methods, and/or to perform evaluations of solutions. Exemplary hybridization criteria that may be met by analyzing the structural model and/or the surrogate fitness model is disclosed in Goldberg, D. E. & Voessner, S., �Optimizing global-local search hybrids�, Proceedings of the Genetic and Evolutionary Computation Conference, 220-228, 1999; Colletti, B. W. & Barnes, J. W., �Using group theory to construct and characterize metaheuristic search neighborhoods�, In Rego, C. & B. Alidaee, B. (eds.), Adaptive Memory and Evolution: Tabu Search and Scatter Search, 303-329, Boston, Mass., 2004, Kluwer Academic Publishers; Vaughan, D., Jacobson, S. H., & Armstrong, D., �A new neighborhood function for discrete manufacturing process design optimization using generalized hill climbing algorithms�, ASME Journal of Mechanical Design, 122(2), 164-171, 2000; and Lima., C. F., Pelikan, M., Sastry, K., Butz, M. V., Goldberg, D. E., & Lobo, F. G., �Substructural neighborhoods for local search in the Bayesian optimization algorithm�, Parallel Problem Solving from Nature (PPSN IX), 232-241, 2006. These documents are incorporated herein by reference.
If parallelization is to be used (step 118), for example, the structural model may be used to infer the form of the surrogate, and may also be used to infer the topology of parallel function evaluation and/or to infer the topology of parallel architecture. The surrogate model may be used to optimally decide a parallel architecture and values of critical parameters for a parallel GA method. The surrogate fitness model may also be used for parallel function evaluation. Exemplary hybridization criteria that may be met by analyzing the structural model and/or the surrogate fitness model is disclosed in Cant�-Paz, E., �Efficient and accurate parallel genetic algorithms�, Boston, Mass.: Kluwer Academic Publishers, 2000. This document is incorporated herein by reference.
Referring once again to FIG. 1, a step of generating new solutions is performed in block 120. The new solutions may collectively be thought of as a new solution set. There are various particular steps suitable for accomplishing this. For example, a model may be used to generate new solutions. The model may be a different model than a previously built model, including the structural model built in step 106. It may be any of a variety of models, for example, that use the desirable solutions selected in block 104 to predict other desirable solutions. Probabilistic models, predictive models, genetic and evolutionary algorithms, probabilistic model building genetic algorithms (also known as estimation of distribution algorithms), Nelder-Mead simplex method, tabu search, simulated annealing, Fletcher-Powell-Reeves method, metaheuristics, ant colony optimization, particle swarm optimization, conjugate direction methods, memetic algorithms, and other local and global optimization algorithms may be used. The step of block 120 may therefore itself include multiple sub-steps of model creation. In this manner, the method of FIG. 1 and other invention embodiments may be �plugged into� other models to provide beneficial speed-up in evaluation. Other efficiency enhancement techniques such as hybridization (step 116) and parallelization (step 118) may be used to further speed up evaluation depending on the decisions made during these steps.
S overall =S competence *S parallel *S relaxation *S continuation *S hybridization This multiplicative enhancement can be substantial. However, tight integration of probabilistic model building and one or more efficiency enhancement techniques may in some cases yield supermultiplicative improvements that may be, for example, several orders of magnitude above improvements obtained independently.
Take the case of parallelization, for example. Structural information about the problem being solved may be used to use parallel processing capability more effectively, according to the embodiment shown in FIG. 1. Cant�-Paz, Efficient and accurate parallel genetic algorithms, Boston, Mass.: Kluwer Academic Press, 2000, develops essential theory confirmed by experimental results to help design effective parallel genetic algorithms. These ideas may be used together with the structural information learned in probabilistic model building procedures to best utilize different kinds of parallel computing.
S relaxation = 1 ( 1 + p i ) 1.5 ⁢ ( 1 - p i ) The results of using substructural information in fitness estimation indicates that only 1% of the individuals need fitness evaluation (the remaining 99% are estimated through fitness inheritance) and yield a speedup of 30-53, as shown in FIG. 2. This is in contrast to a modest speedup of 1.3 provided by a simple inheritance mechanism that does not exploit the substructural information.
The estimation of substructural fitnesses can be significantly improved by using least squares and recursive least squares methods. The usage of least-square estimate not only makes the fitness estimation procedure more robust for deterministic problems, but also makes it tractable to use with noisy, overlapping, and hierarchical fitness functions. Furthermore, using substructural fitness basis�for which the population scales as O(2km log m)�is significantly efficient over using polynomial kernel in support vector machines�for which the population scales O(lk), where k is the BB size, and m is the number of BBs. It appears that speedups that can be achieved by using a least-squares estimate of substructural fitness are significantly greater than those obtained to date.
Sastry and Goldberg, �Let's get ready to rumble: crossover versus mutation head to head�, Proceedings of the Genetic and Evolutionary Computation Conference, 2, 126-137, 2004, analyzed the relative advantages between crossover and mutation on a class of deterministic and stochastic additively separable problems. For that study, the authors assumed that the crossover and mutation operators had perfect knowledge of the problem structure and effectively exchanged or searched among competing BBs. They used facetwise models of convergence time and population sizing to determine the scalability of each operator-based algorithm. The analysis shows that for additively separable deterministic problems, the BB-wise mutation is more efficient than crossover, while for the same problems with additive Gaussian noise, the crossover-based algorithm outperforms the mutation approach. The results show that the speed-up of using BB-wise mutation on deterministic problems is O(√{square root over (k)} log m), where k is the BB size and m is the fixed number of BBs. In the same way, the speed-up of using crossover on stochastic problems with fixed noise variance is O(√{square root over (k)}m/log m). Thus, the robustness and strength of GAs lies in using both crossover and mutation. In some ways, this approach relates to hybridization optimization.
In this manner, exemplary methods of the present invention are useful to adjust problem solving dynamically by adapting the search strategy to the domain features of the problem being solved. For example, often a user is presented with a fixed, limited amount of computational resource (e.g., computing time). In time continuation, a choice must be made between, for example, using a large pool of solutions but not having time to fully converge, or using a smaller, more limited pool of solutions but being able to come closer to convergence. Aspects of the present invention provide steps for analyzing the problem at hand to make the best choice between these alternatives. Some methods of the invention can continuously update�they may make one change on an early iteration and a different one on a later iteration.
One known PMBGA is the extended compact genetic algorithm (eCGA), described in Harik, G., �Linkage learning via probabilistic modeling in the ECGA�, IlliGAL Report No. 99010, Urbana, Ill.: University of Illinois at Urbana-Champaign. As with other model builders, such as the Bayesian optimization algorithm (BOA), the eCGA has been successful in tackling large difficulty problems with little or no prior problem knowledge across a spectrum of problem areas.
An exemplary mutation operator based on this probabilistic model building procedure is the building-block-wise mutation algorithm (BBMA), which is a BB-wise mutation operator that performs local search in the building block space. A more particular example of the BBMA is the extended compact mutation algorithm (eCMA), which is described in Sastry and Goldberg, �Designing competent mutation operators via probabilistic model building of neighborhoods�, Proceedings of the Genetic and Evolutionary Computation Conference, 2, 114-125, 2004.
In an exemplary PMBHGA described herein, both operators are based on the probabilistic procedure of the eCGA. The model sampling procedure of eCGA, which mimics the behavior of an idealized recombination�where BBs are exchanged without disruption�is used as the competent crossover operator. On the other hand, the eCMA�which uses the BB partition information to perform local search in the BB space�is used as the competent mutation operator. The resulting exemplary PMBHGA, referred to herein as a hybrid extended compact genetic algorithm (heCGA), makes use of the problem decomposition information for 1) effective recombination of BBs and 2) effective local search in the BB neighborhood.
∑ i = 1 m ⁢ ⁢ k i = l . Then each partition i requires 2k i −1 independent frequencies to completely define its marginal distribution. Taking into account that each frequency is of size log2(n+1), where n is the population size, the model complexity Cm is given by
C m = log 2 ⁡ ( n + 1 ) ⁢ ∑ i = 1 m ⁢ ⁢ ( 2 k i - 1 ) The compressed population complexity, Cp, quantifies the data compression in terms of the entropy of the marginal distribution over all partitions. Therefore, Cp is given by
C p = n ⁢ ∑ i = 1 m ⁢ ⁢ ∑ j = 1 2 k i ⁢ ⁢ - p ij ⁢ log 2 ⁡ ( p ij ) where pij is the frequency of the jth gene sequence of the genes belonging to the ith partition. In other words, pij=Nij/n, where Nij is the number of chromosomes in the population (after selection) possessing bit sequence jε└1,2k i ┘ for the ith partition. Note that a BB of size k has 2k possible bit sequences, where the first is denoted by 00.0 and the last by 11.1.
An example of s-wise tournament selection is described in Goldberg, Korb, and Deb, �Messy genetic algorithms: Motivation, analysis, and first results�, Complex Systems, 3(5), 493-530, 1989, which is incorporated herein by reference.
The eCGA performs a greedy MPM search at every generation. The greedy search starts with the simplest possible model, assuming that all variables are independent (as with the compact GA (Harik, Lobo, & Goldberg, 1999)), and then keeps merging partitions of genes whenever the MDL score metric is improved. All possible merges of two subsets are considered. This process goes on until no further improvement is possible. An algorithmic description of this greedy search can be found in, for example, Sastry & Goldberg, �Designing competent mutation operators via probabilistic model building of neighborhoods�, Proceedings of the Genetic and Evolutionary Computation Conference, 2, 2004, 114-125, which is incorporated herein by reference.
The exemplary probabilistic model building BB-wise mutation algorithm (BBMA) is a selectomutative algorithm that performs local search in the BB neighborhood. It induces good neighborhoods as linkage groups. Instead of using a bit-wise mutation operator that scales polynomially with order k as the problem size increases, the BBMA uses a BB-wise mutation operator that scales subquadratically, as shown by Sastry and Goldberg, �Designing competent mutation operators via probabilistic model building of neighborhoods�, Proceedings of the Genetic and Evolutionary Computation Conference, 2, 2004, 114-125, which is incorporated herein by reference. For BB identification, an exemplary BBMA, the extended compact mutation algorithm (eCMA), uses the probabilistic model building procedure of eCGA. However, other probabilistic model building techniques can be used with similar or better results. Once the linkage groups are identified, an enumerative BB-wise mutation operator (e.g., as disclosed in Sastry and Goldberg, �Let's get ready to rumble: Crossover versus mutation head to head�, Proceedings of the Genetic and Evolutionary Computation Conference, 2, 2004, 126-137) is used to find the best schema for each detected partition. The resulting mutation varies between bit-wise and BB-wise, and a search varies between hillclimbing and deterministic or random.
5.1) create 2k−1 unique individuals with all possible schema in the current BB partition (the rest of the individual remains the same and equal to the best solution found so far); and 5.2) evaluate all 2k−1 individuals and retain the best for mutation in the other BB partitions. The performance of the BBMA can be slightly improved by using a greedy heuristic to search for the best among competing BBs in each partition. Even so, the scalability of BBMA is determined by the population size required to identify the BB partitions accurately. It has previously been shown that the number of function evaluations scales as o(2k m1.05)≦nfe≦o(2km2.1).
6.1) increase the BB instances frequencies of the mutated individual by s (step 212); 6.2) decrease the BB instances frequencies of the previous best individual by s (step 214); 7) generate a new population according to the updated MPM (step 216);
p(x1x2x3)
p(x4x5x6)
p(x7x8)
p(x9)
0.11 − s/n
0.18 − s/n
0.23 − s/n
0.03 + s/n
0.02 + s/n
0.31 + s/n
In an exemplary operation of the inventive heCGA, a hybrid scheme using a deterministic BB search is used. Computational experiments were performed in various problems of bounded difficulty. Following a design approach to problem difficulty, the described algorithms are tested on a set of problems that combine the core of three well-known problem difficulty dimensions: 1) intra-BB difficulty�deception; 2) inter-BB difficultly�scaling; and 3) extra-BB difficulty�noise. For that, we assume that the problem at hand is additively decomposable and separable, such that
f ⁡ ( X ) = ∑ i = 0 m - 1 ⁢ ⁢ f i ⁡ ( x I i ) where Ii is the index set of the variables belonging to the ith subfunction. As each subfunction is separable from the rest, each index set Ii is a disjoint tuple of variable indexes.
For each algorithm, we empirically determine the minimal number of function evaluations to obtain a solution with at least m−1 building blocks solved; that is, the optimal solution with an error of α=1/m. For each eCGA, and eCMA, we use a bisection method over the population size to search for the minimal sufficient population size to achieve a target solution. However, for heCGA, an interval halving method is more appropriate given the algorithm behavior as the population increases, as will be shown below. The results from the minimal sufficient population size are averaged over 30 bisection runs. In each bisection run, the number of BBs solved with a given population size is averaged over another 30 runs. Thus, the results for the number of function evaluations and the number of generations spent are averaged over 900 (30�30) independent runs. For all experiments, tournament selection without replacement is used with size s=8.
f trap ⁡ ( u ) = { 1 if ⁢ ⁢ u = k 1 - d - u * 1 - d k - 1 otherwise where u is the number of 1s in the string, k is the size of the trap function, and d is the fitness signal between the global optimum and the deceptive optimum. In the experiments described below we use d=1/k. Considering m copies of this trap function, the global boundedly deceptive function is given by
f d ⁡ ( X ) = ∑ i = 0 m - 1 ⁢ ⁢ f trap ⁡ ( x ki , x ki + 1 , � ⁢ ⁢ x ki + k - 1 ) FIG. 4 presents the results obtained for the boundedly deceptive function. The number of BBs (or subfunctions) is varied between 2 and 20, for k={4, 5}. For example, where k=4, d=0.25. As we can see, eCGA needs smaller populations than eCMA and heCGA to solve the problem; however, eCGA takes more function evaluations than both algorithms. This happens because in eCGA (1) the BBs are discovered in a progressive way and 2) more generations are required to exchange the right BBs. Although increasing the population size for eCGA accelerates the BB identification process, additional generations are still needed to mix the correct BBs into a single individual. Since eCGA (like every selectorecombinative GA) always has to spend this mixing time, relaxing the BB identification process (using smaller populations, thus saving function evaluations) to a certain point seems to be the best way to tune eCGA performance.
f ds ⁡ ( X ) = ∑ i = 0 m - 1 ⁢ ⁢ 2 i ⁢ f trap ⁡ ( x ki , x ki + 1 , � ⁢ ⁢ x ki + k - 1 ) This function has the interesting property that a high scaled subfunction gives more fitness contribution than the sum of all subfunctions below it. When solving this problem with a GA in the initial generations, the signal that comes from the low-salient BBs is negligible when faced with the decision making that is being done between the high-salient BBs. Whenever the higher BBs are solved, the next higher scaled BBs will have their time of attention by the GA, and so on. Given this property, the correct BB partitions can only be discovered in a sequential way, which contrasts with the uniformly scaled case where the problem structure can be captured in the first generation with a sufficiently large population size. Therefore, eCMA is not able to solve exponentially scaled problems with reasonable population sizes, as has been recognized before. The model built based on the selected initial random individuals will only be able to get the high-salient BB partitions, failing the rest. Thus, the model of eCMA has to be updated at a regular schedule to be able to capture the BBs structure in a sequential manner.
Given the heCGA, PMBHGA, or other hybrid methods, the time continuation technique can be incorporated into the overall model in FIG. 1. For example, the evaluation step in heCGA (step 204) may be incorporated into step 103 of FIG. 1, and may be affected by the results of a surrogate fitness model, as constructed in step 112. Generation of a new population in heCGA (step 216) may be affected by analyzing a structural model and a surrogate fitness model. Exemplary changes may include emphasizing, de-emphasizing, or even removing one or more operators, such as the mutation operators and/or the population sampling operators. Alternatively or additionally, the amount of mutation vs. probabilistic sampling may be affected by determining a population size n for a new population. As shown in FIGS. 4-9, changing the population can cause the proportion of probabilistic sampling (e.g., crossover) to mutation to change. This latter method allows the heCGA to be used as a �black box�, without alteration. Thus, heCGA, PMBHGA or other hybrid methods may be adapted either by emphasizing or de-emphasizing operators, and/or by changing parameters from outside the method.
p ⁡ ( X ) = ∏ i = 1 ℓ ⁢ ⁢ p ⁡ ( X i | Π i ) Where X=(X1, X2, . . . , Xl) is a vector of all the variables of the problem, Πi is the set of parents of Xi (nodes from which there exists an edge to Xi), and p(Xi|Πi) is the conditional probability of Xi given its parents Πi.
f est ⁡ ( X 1 , X 2 , � ⁢ , X ℓ ) = f _ + ∑ i = 1 ℓ ⁢ ⁢ ( f _ ⁡ ( X i | Π i ) - f _ ⁡ ( Π i ) ) , where f is the average fitness of all solutions used to learn the surrogate, f(Xi|Πi) denotes the average fitness of solutions with Xi and Πi, and f(Πi) is the average fitness of all solutions with Πi.
Fitness information may also be incorporated in Bayesian networks with decision trees or graphs in a similar way. In this case, the average fitness of each instance for every variable should be stored in every leaf of the decision tree or graph. The fitness averages in each leaf are now restricted to solutions that satisfy the condition specified by the path from the root of the tree to the leaf. An example of this methodology is described in Pelikan, M., & Sastry, K., �Fitness inheritance in the Bayesian optimization algorithrim�, In Deb, K. e.a. (Ed.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004), Part II, LNCS 3103 (pp. 48-59), 2004.
An exemplary run of this hillclimbing method is described in Lima, C. F., Pelikan, M., Sastry, K., Butz, M., Goldberg, D., and Lobo, F. G., �Substructural Neighborhoods for Local Search in the Bayesian Optimization Algorithm�, Parallel Problem Solving from Nature (PPSN IX), 2006, 232-241, which is incorporated herein by reference. In this exemplary substructural hillclimber, we use the reverse order of that used to sample the variables of new solutions, where each node is optimized by its parents. By doing so, higher-order dependencies within the same linkage group are optimized first. This procedure aims to reduce the possibility of doing incorrect decisions when considering problems whose lower-order statistics lead the search away from global optima.
Other configurations are possible. Aspects of exemplary embodiments enable optimization methods, such as but not limited to competent genetic and evolutionary algorithms, to solve extraordinarily difficult problems in the most various disciplines without requiring of the user significant knowledge about the solver mechanics, which is not the case for standard genetic algorithms. Extensions beyond domains of discrete, fixed-length representations to real vectors, strings of arbitrary length, or program codes, are straightforward, and therefore preferred embodiments offer a very general method for efficiency enhancement of powerful search algorithms. Furthermore, it is possible to incorporate such time continuation in many different competent genetic algorithms such as the Bayesian optimization algorithm above, hierarchical Bayesian optimization algorithm (hBOA), dependency structure matrix driven genetic algorithm (DSMGA), etc. Embodiments of the present invention may also be very valuable as an add-on to other systems and methods. Designing an optimal hybrid scheme can depend strongly on problem nature. Global-local search hybrid theory (Goldberg & Voessner, �Optimizing global-local search hybrids�, Proceedings of the Genetic and Evolutionary Computation Conference, 220-228, 1999) may be useful in such designs.
The results shown and described above indicate the robustness of using both search operators�crossover and mutation�in the context of adaptive genetic and evolutionary computing, such as PMBGAs, as it is known to be advantageous for traditional GAs. Given the observed robustness of heCGA, for example, such adaptive genetic and evolutionary computing should be suitable in various types of problems for applying in a �black-box system� basis.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS600621328 Mar 199521 Dec 1999Hitachi, Ltd.Method for learning data processing rules from graph informationUS633610915 Apr 19971 Jan 2002Cerebrus Solutions LimitedMethod and apparatus for inducing rules from data classifiersUS687986011 Mar 200312 Apr 2005Cochlear LimitedCochlear implant MAP optimization with use of a genetic algorithmUS68921917 Feb 200010 May 2005Koninklijke Philips Electronics N.V.Multi-feature combination generation and classification effectiveness evaluation using genetic algorithmsUS689219222 Jun 200010 May 2005Applied Systems Intelligence, Inc.Method and system for dynamic business process management using a partial order plannerUS70434629 Nov 20019 May 2006Honda Research Institute Europe GmbhApproximate fitness functionsUS70434631 Apr 20049 May 2006Icosystem CorporationMethods and systems for interactive evolutionary computing (IEC)US704716918 Jan 200216 May 2006The Board Of Trustees Of The University Of IllinoisMethod for optimizing a solution setUS71367106 Jun 199514 Nov 2006Hoffberg Family Trust 1Ergonomic man-machine interface incorporating adaptive pattern recognition based control systemUS724305621 Feb 200210 Jul 2007Honda Research Institute Europe GmbhStrategy parameter adaptation in evolution strategiesUS72809869 Feb 20049 Oct 2007The Board Of Trustees Of The University Of IllinoisMethods and program products for optimizing problem clusteringUS732497929 Aug 200329 Jan 2008Bbn Technologies Corp.Genetically adaptive neural network classification systems and methodsUS73281943 Jun 20055 Feb 2008Aspeed Software CorporationMethod and system for conditioning of numerical algorithms for solving optimization problems within a genetic frameworkUS732819520 Nov 20025 Feb 2008Ftl Systems, Inc.Semi-automatic generation of behavior models continuous value using iterative probing of a device or existing component modelUS735651820 Aug 20048 Apr 2008Icosystem CorporationMethods and systems for multi-participant interactive evolutionary computingUS73632809 Nov 200122 Apr 2008Honda Research Institute Europe GmbhMethods for multi-objective optimization using evolutionary algorithmsUS736328124 Jan 200522 Apr 2008Honda Research Institute Europe GmbhReduction of fitness evaluations using clustering techniques and neural network ensemblesUS742851411 Jan 200523 Sep 2008Honda Research Institute Europe GmbhSystem and method for estimation of a distribution algorithmUS744430928 Oct 200228 Oct 2008Icosystem CorporationMethod and system for implementing evolutionary algorithmsUS745112127 Sep 200511 Nov 2008Intel CorporationGenetic algorithm for microcode compressionUS745778623 Aug 200525 Nov 2008General Electric CompanyPerformance enhancement of optimization processesUS2003005561418 Jan 200220 Mar 2003The Board Of Trustees Of The University Of IllinoisMethod for optimizing a solution setUS2003022071630 May 200327 Nov 2003Pharmix CorporationMethod and apparatus for automated design of chemical synthesis routesUS2004018126611 Mar 200316 Sep 2004Honert Christopher Van DenCochlear implant MAP optimization with use of a genetic algorithmUS2004022083930 Apr 20034 Nov 2004Ge Financial Assurance Holdings, Inc.System and process for dominance classification for insurance underwriting suitable for use by an automated systemUS200402549011 Apr 200416 Dec 2004Icosystem CorporationMethods and systems for interactive evolutionary computing (IEC)US2005011855729 Nov 20042 Jun 2005American Board Of Family Medicine, Inc.Computer architecture and process of user evaluationUS2005011998320 Aug 20042 Jun 2005Bonabeau EricMethods and systems for multi-participant interactive evolutionary computingUS200501773519 Feb 200411 Aug 2005The Board Of Trustees Of The University Of IllinoisMethods and program products for optimizing problem clusteringUS2005020998224 Jan 200522 Sep 2005Honda Research Institute Europe GmbhReduction of fitness evaluations using clustering techniques and neural network ensemblesUS2005021687924 Mar 200429 Sep 2005University Technologies International Inc.Release planningUS2005025668411 Jan 200517 Nov 2005Jin YaochuSystem and method for estimation of a distribution algorithmUS200502764792 May 200515 Dec 2005The Board Of Trustees Of The University Of IllinoisMethods and systems for computer based collaborationUS2006018491623 Nov 200517 Aug 2006Baum EricMethod and system for constructing cognitive programsUS2006021227930 Jan 200621 Sep 2006The Board of Trustees of the University of Illinois andMethods for efficient solution set optimizationUS200602250035 Apr 20055 Oct 2006The Regents Of The University Of CaliforniaEngineering design system using human interactive evaluationUS2007011269820 Oct 200517 May 2007Corporation, International Business MachinesComputer controlled method using genetic algorithms to provide non-deterministic solutions to problems involving physical restraintsUS2007020867731 Jan 20076 Sep 2007The Board Of Trustees Of The University Of IllinoisAdaptive optimization methodsUS200702089966 Mar 20066 Sep 2007Ricoh Co., Ltd.Automated document layout designUS2009007028012 Sep 200712 Mar 2009International Business Machines CorporationMethod for performance bottleneck diagnosis and dependency discovery in distributed systems and computer networksNon-Patent CitationsReference1Albert & Goldberg, "Efficient Discretization Scheduling in Multiple Dimensions." Proceedings of the Genetic and Evolutionary Computation Conference, pp. 271-278, 2002. (Also IlliGAL Report No. 2002006).2Albert & Goldberg, "Efficient Evaluation Relaxation Under Integrated Fitness Functions." Intelligent Engineering Systems Through Artificial Neural Networks, 11, pp. 165-170, 2001. (Also IlliGAL Report No. 2001024).3Alias & Llora, "Evolutionary Weight Tuning Based on Diphone Pairs for Unit Selection Speech Synthesis." In EuroSpeech, 2, pp. 1333-1336, Geneve, Switzerland (2003).4Alias, Llora, Idiondo, Sevillano, Formiga & Socoro, "Perception-Guided and Phonetic Clustering Weight Tuning Based on Diphone Pairs for Unit Selection TTS." In Proceedings of the 8th International Conference on Spoken Language Processing (ICSLP), pp. 1333-1336. Jeju Island, Korea, 2004.5Armstrong & Jacobson, "Data Independent Neighborhood Functions and Strict Local Optima." Discrete Applied Mathematics, 146(3), pp. 233-243, 2005.6Back, T., "Selective Pressure in Evolutionary Algorithms: A Characterization of Selection Mechanisms." Proceedings of the First IEEE Conference on Evolutionary Computation, pp. 57-62, 1994.7Baluja, S. (1994). "Population-based incremental learning: A method of integrating genetic search based function optimization and competitive learning." (Technical Report CMU-CS-94-163). Carnegie Mellon University.8Barbulescu, Watson, Whitley, Howe, "Scheduling Space-Ground Communications for the Air Force Satellite Control Network." Journal of Scheduling, 7(1), pp. 7-34, 2004.9Barnes, Dimova, Dokov, "The Theory of Elementary Landscapes." Applied Mathematical Letters, 16, pp. 337-343, 2003.10Bartelemy & Haftka, "Approximation Concepts for Optimum Structural Design-A Review." Structural Optimization, 5, pp. 129-144, 1993.11Bartelemy & Haftka, "Approximation Concepts for Optimum Structural Design�A Review." Structural Optimization, 5, pp. 129-144, 1993.12Bergener, Bruckhoff & Igel, "Evolutionary Parameter Optimization for Visual Obstacle Detection." Proc. Advanced Concepts for Intelligent Vision Systems, (ACIVS99), pp. 104-109, 1999.13Bertsekas, D., "Incremental Least Squares Methods and the Extended Kalman Filter." SIAM Journal on Optimization, 6(3), pp. 807-822, 1996).14Beyer, H., "Toward a Theory of Evolution Strategies: Self-adaptation." Evolutionary Computation, 3(3), pp. 311-347, 1996.15Biles, J., "Genjam: A Genetic Algorithm for Generating Jazz Solos." Proc. Int. Computer Music Conf., pp. 131-137, 1994.16Black & Tokuda, "Blizzard Challenge-2005: Evaluating Corpus-based Speech Synthesis on Common Datasets." In Proceedings of the 9th International Conference on Speech Communication and Technology (InterSpeech), pp. 77-80. Lisboa, Portugal, 2005.17Black & Tokuda, "Blizzard Challenge�2005: Evaluating Corpus-based Speech Synthesis on Common Datasets." In Proceedings of the 9th International Conference on Speech Communication and Technology (InterSpeech), pp. 77-80. Lisboa, Portugal, 2005.18Black, A., "Perfect Synthesis for All of the People All of the Time." In IEEE TTS Workshop 2002 (keynote). Santa Monica, USA, 2002 (4 pages).19Booker, Dennis, Frank, Serafini, Torczon & Trosset, "A Rigorous Framework for Optimization of Expensive Functions by Surrogates." (Technical Report). Hampton, VA: National Aeronautics and Space Administration (NASA). ICASE Report No. 98-47, 1998.20Bull, "On Model-Based Evolutionary Computation." Soft Comp., 3, pp. 76-82, 1999.21Burke & Smith, "A Multi-Stage Approach for the Thermal Generator Maintenance Scheduling Problem." Proc. 1999 Congress Evolutionary Computation, 2, pp. 1085-1092, Piscataway, NJ: IEEE Jul. 1999.22Cantu-Paz & Goldberg, "On the Scalability of Parallel Genetic Algorithms." Evolutionary Computation, 7(4), pp. 429-449, 1999.23Cantu-Paz, "A Summary of Research on Parallel Genetic Algorithms," Tech. Rep. 95007, IlliGAL Rep., 1995.24Carpenter & Barthelemy, "A Comparison of Polynomial Approximations and Artificial Neural Nets as Response Surfaces." Struc. Optimiz., 5, pp. 1166-1174, 1993.25Chen & Goldberg, "Introducing Start Expression Genes to the Linkage Learning Genetic Algorithm." In Parallel Problem Solving from Nature (PPSN VII), pp. 351-360, 2002, Springer. (IlliGAL Report No. 2002007).26Chen, Goldberg, Ho, Sastry, "Fitness Inheritance in Multiobjective Optimization." Proceedings of the Genetic and Evolutionary Computation Conference, pp. 319-326, 2002. (Also IlliGAL Report No. 2002017).27Coello-Coello, C., "An Updated Survey of Evolutionary Multiobjective Optimization Techniques: State of the Art and Future Trends." Proc. 1999 Congress on Evolutionary Computation, pp. 3-13, Piscataway, NJ: IEEE, 1999.28Coello-Coello, C., "An Updated Survey of GA-Based Multi-objective Optimization Techniques." (Technical Report Lania-RD-09-08). Laboratorio Nacional de Informatica Avanzada (LANIA), Xalapa, Veracruz, Mexico, Dec. 1998.29Coletti, Barnes, Dokov, "A Note on Characterizing the k-OPT Neighborhood Via Group Theory." Journal of Heuristics, 5, pp. 47-51, 1999.30Colletti & Barnes, "Using Group Theory to Construct and Characterize Metaheuristic Search Neighborhoods." In Rego & Alidaee (eds.), Adaptive Memory and Evolution: Tabu Search and Scatter Search, pp. 303-329, Boston, MA: Kluwer Academic Publishers (2004).31Cooper & Herskovits, "A Bayesian Method for the Induction of Probabilistic Networks from Data." Machine Learning, 9, pp. 309-347, 1992.32Coorman, Fackrell, Rutten & Van Coile, "Segment Selection in the L&H RealSpeak Laboratory TTS System." In ICSLP, 2, pp. 395-398, Beijing, China, 2000.33Deb, Agrawal, Pratab & Meyarivan, "A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II" (KanGAL report 200001). Indian Institute of Technology, 2000.34Dennis & Torczon, "Managing Approximation Models in Optimization." In Alexandrov & Hussaini, (Eds.), Multidisciplinary Design Optimization: State-of-the-Art, pp. 330-347, Philadelphia, PA: SIAM (1997).35Dunham, Fridshal, D., Fridshal, R. & North, "Design by Natural Selection." Synthese, 15, pp. 254-259, 1963.36El-Beltagy, Nair & Keane, "Metamodeling Techniques for Evolutionary Optimization of Expensive Problems: Promises and Limitations." Proc. Genetic and Evolutionary Computation Conf., pp. 196-203, 1999.37Etxeberria & Larranaga, "Global Optimization Using Bayesian Networks." In Rodriguez, et al, (Eds.), Second Symposium on Artificial Intelligence (CIMAF-99), pp. 332-339, Havana, Cuba, 1999.38Goldberg & Voessner, "Optimizing Global-local Search Hybrids." Proceedings of the Genetic and Evolutionary Computation Conference, pp. 220-228, 1999. (Also IlliGAL Report No. 99001).39Goldberg, D., "Making Genetic Algorithms Fly: A Lesson from the Wright Brothers." Advanced Technology for Developers, 2, pp. 1-8 (1993).40Goldberg, D., "The Race, the Hurdle, and the Sweet Spot." In Bentley, (Ed.), Evolutionary Design by Computers, pp. 105-118. San Francisco, CA: Morgan Kaufmann, 1999.41Goldberg, D., "Using Time Efficiently: Genetic-evolutionary Algorithms and the Continuation Problem." Proceedings of the Genetic and Evolutionary Computation Conference, pp. 212-219, 1999. (Also IlliGAL Report No. 99002).42Goldberg, D.E. et al., "DISCUS: Distributed innovation and scalable collaboration in uncertain settings." (IlliGAL Report No. 2003017). Urbana, IL: University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, 2003.43Goldberg, D.E., et al., "Discovering deep building blocks for component genetic algorithms using chance discovery via KeyGraphs." In Oshawa, Y., McBurney, P. (Eds.), Chance Discovery (pp. 276-302). Berlin: Springer-Verlag, 2002.44Goldberg, Deb, Kargupta & Harik, "Rapid, Accurate Optimization of Difficult Problems Using Fast Messy Genetic Algorithms." Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 56-64, 1993.45Goldberg, Korb & Deb, "Messy Genetic Algorithms: Motivation, Analysis, and First Results." Complex Systems, 3(5), pp. 493-530, 1989 (Also TCGA Report No. 89001).46Grierson & Pak, "Optimal Sizing, Geometrical and Topological Design Using a Genetic Algorithm." Struc. Optimiz., 6(3), pp. 151-159, 1993.47Handa, "The Effectiveness of Mutation Operation in the Case of Estimation of Distribution Algorithms." Biosystems 87, pp. 243-251, 2007.48Hansen & Ostermeier, "Completely Derandomized Self-adaptation in Evolution Strategies." Evolutionary Computation, 9(2), pp. 159-195, 2001.49Harik & Goldberg, "Learning Linkage." Foundations of Genetic Algorithms 4, 4, pp. 247-262, 1997. (Also IlliGAL Report No. 96006).50Harik G. Linkage learning via probabilistic modeling in the ECGA. IIIiGAL Technical Report 99010. Urbana, IL, University of Illinois at Urbana-Champaign. Jan. 1999.51Harik, Cantu-Paz, Goldberg & Miller, "The Gambler's Ruin Problem, Genetic Algorithms, and the Sizing of Populations." Evolutionary Computation, 7(3), pp. 231-253, 1999. (Also IlliGAL Report No. 96004).52Harik, G., "Linkage Learning Via Probabilistic Modeling in the ECGA." (IlliGAL Report No. 99010), Urbana, IL: Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 1999.53Harik, Lobo & Goldberg, "The Compact Genetic Algorithm." IEEE Transactions on Evolutionary Computation, 3(4), pp. 287-297, 1999.54Harwig & Barnes, "An Adaptive Tabu Search Approach for 2-Dimensional Orthogonal Packing Problems." Military Operations Research (31 pages), 2006.55Heckendorn & Wright, "Efficient Linkage Discovery by Limited Probing." Evolutionary Computation, 12(4), pp. 517-545, 2004.56Heckerman, Geiger & Chickering, "Learning Bayesian Networks: The Combination of Knowledge and Statistical Data." (Technical Report MSR-TR-94-09). Redmond, WA: Microsoft Research, pp. 197-243, 1994.57Henriet, D., "The Copeland Choice Function An Axiomatic Characterization." Social Choice and Welfare (1985) 2 p. 49-63.58Hunt & Black, "Unit Selection in a Concatentative Speech Synthesis System Using a Large Speech Database." In ICASSP, 1, pp. 373-376, Atlanta, USA, 1996.59Jin et al. A Framework for Evolutionary Optimization with Approximate Fitness Functions. IEEE Transactions on Evolutionary Computation, vol. 6 No. 5, Oct. 2002.60Jin, Olhofer & Sendhoff, "Managing Approximate Models in Evolutionary Aerodynamic Design Optimization." Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 523-528, 2000.61Jin, Y. A comprehensive survey of fitness approximation in evolutionary computation. Soft Computing-A Fusion of Foundations, Methodologies and Applications archive. vol. 9 , Issue 1 (Jan. 2005) pp. 3-12.62Jin, Y. A comprehensive survey of fitness approximation in evolutionary computation. Soft Computing�A Fusion of Foundations, Methodologies and Applications archive. vol. 9 , Issue 1 (Jan. 2005) pp. 3-12.63Jin, Y. et al. A framework for evolutionary optimization with approximate fitness functions, IEEE Transactions on Evolutionary Computation, 6(5):481-494, 2002.64Jin, Y., "A Comprehensive Survey of Fitness Approximation in Evolutionary Computation." Soft Computing Journal, 9(1), pp. 3-12, 2005.65Jin, Y., "A Framework for Evolutionary Optimization with Approximate Fitness Functions." IEEE Transactions on Evolutionary Computation, 6(5), pp. 481-494, 2002.66Kosorukoff, Alex, "Human Based Genetic Algorithm", Illinois Genetic Algorithims Laboratory p. 3464-3469, SMC, 2001.67Levin, Jonathan et al., "An Introduction to Vote-Counting Schemes", The Journal of Economic Perspectives, vol. 9, No. 1 (Winter, 1995) p. 3-26.68Lima, Pelikan, Sastry, Butz, Goldberg, Lobo, "Substructural Neighborhoods for Local Search in the Bayesian Optimization Algorithm." Parallel Problem Solving from Nature (PPSN IX), pp. 232-241, 2006. Available: ftp://ftp-illigal.ge.uiuc.edu/pup/paperspIlliGALs/2006021.pdf.69Lima, Sastry, Goldberg, Lobo, "Combining Competent Crossover and Mutation Operators: A Probabilistic Model Building Approach." Proceedings of the 2005 Genetic and Evolutionary Computation Conference, pp. 735-742, 2005. (Also IlliGAL Report No. 2005002).70Llora, Alias, Formiga, Sastry & Goldberg, "Evaluation Consistency in iGAs: User Contradictions as Cycles in Partial-Ordering Graphs." University of Illinois at Urbana-Champaign, Urbana, IL: Illinois Genetic Algorithms Laboratory, 2005. (Also IlliGAL Report No. 2005022).71Llora, Sastry, Goldberg, Gupta & Lakshmi, "Combating User Fatigue in iGAs: Partial Ordering, Support Vector Machines and Synthetic Fitness." Proceedings of Genetic and Evolutionary Computation Comference 2005 (GECCO-2005), pp. 1363-1371, 2005. (Also IlliGAL Report No. 2005009).72Llora, X., et al., Enhanced innovation: A fusion of chance discovery and evolutionary computation to foster creative processes and decision making, (IliGAL Report No. 2004012), University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2004.73MacKay, "Information-based Objective Functions for Active Data Selection." Neural Comput., 4(4), pp. 305-318, 1992.74Masui, T., "Graphic Object Layout with Interactive Genetic Algorithms." Proc IEEE Workshop Visual Languages, pp. 74-80, 1992.75Meron & Hirose, Efficient Weight Training for Selection Based Synthesis. In EuroSpeech, 5, pp. 2319-2322 (1999). Budapest, Hungary.76Merz, P., "Memetic Algorithms for Combinatorial Optimization Problems: Fitness Landscapes and Effective Search Strategies." Doctoral dissertation, University of Siegen, Germany, 2000 (Part 1 of 2-pp. 1-136).77Merz, P., "Memetic Algorithms for Combinatorial Optimization Problems: Fitness Landscapes and Effective Search Strategies." Doctoral dissertation, University of Siegen, Germany, 2000 (Part 2 of 2-pp. 137-207).78Merz, P., "Memetic Algorithms for Combinatorial Optimization Problems: Fitness Landscapes and Effective Search Strategies." Doctoral dissertation, University of Siegen, Germany, 2000 (Part 1 of 2�pp. 1-136).79Merz, P., "Memetic Algorithms for Combinatorial Optimization Problems: Fitness Landscapes and Effective Search Strategies." Doctoral dissertation, University of Siegen, Germany, 2000 (Part 2 of 2�pp. 137-207).80Miller & Goldberg, "Genetic Algorithms, Tournament Selection, and the Effects of Noise." Complex Systems, 9(3), pp. 193-212, 1995. (Also IlliGAL Report No. 95006).81Miller, B., "Noise, Sampling, and Efficient Genetic Algorithms." Doctoral dissertation, University of Illinois at Urbana-Champaign, General Engineering Department, Urbana, IL, May 1997. (Also IlliGAL Report No. 97001).82Miller, Nicholas R., "Graph-Theoretical Approaches to the Theory of Voting", American Journal of Political Science, vol. 21, No. 4, (Nov. 1977) p. 769-803.83Moscato, P., "On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms." (Technical Report C3P 826). Pasadena, CA: Caltech Concurrent Computation Program, California Institute of Technology, 1989.84Moulin, H., "Choosing from a Tournament", Social Choice and Welfare (1986) 3 p. 271-291.85Muhlenbein & Schlierkamp-Voosen, "Predictive Models for the Breeder Genetic Algorithm: I. Continuous Parameter Optimization." Evolutionary Computation, 1(1), pp. 25-49, 1993.86Munetomo & Goldberg, "Linkage Identification by Non-Monotonicity Detection for Overlapping Functions." Evolutionary Computation, 7(4), pp. 377-398, 1999.87Ohsawa, Y., et al., "Chance Discovery", Berlin: Springer-Verlag (2003).88Ohsawa, Y., et al., "KeyGraph Automatic indexing by co-occurrence graph based on building construction metaphor", Proceedings of Advances in Digital Libraries, 12-18 (1998).89Ostermeier, "A Derandomized Approach to Self Adaptation of Evolutionary Strategies." Evolut. Comput., 2(4), pp. 369-380, 1994.90Pelikan & Goldberg, "Escaping Hierarchical Traps with Competent Genetic Algorithms." Proceedings of the Genetic and Evolutionary Computation Conference, pp. 511-518, 2001. (Also IlliGAL Report No. 2000020).91Pelikan & Sastry, "Fitness inheritance in the Bayesian Optimization Algorithm." Proceedings of the Genetic and Evolutionary Computation Conference, 2, pp. 48-59, 2004. (Also IlliGAL Report No. 2004009).92Pelikan, Goldberg & Cantu-Paz, "BOA: The Bayesian Optimization Algorithm." In Banzhaf et al, (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99, pp. 525-532, San Francisco, CA: Morgan Kaufmann (1999). (Also IlliGAL Report No. 99003).93Pelikan, Goldberg & Lobo, "A Survey of Optimization by Building and Using Probabilistic Models." Computational Optimization and Applications, 21(1), pp. 5-20, 2002. (Also IlliGAL Report No. 99018).94Pelikan, Goldberg, Cantu-Paz, "Bayesian Optimization Algorithm, Population Sizing, and Time to Convergence." In Whitley, Goldberg, Cantu-Paz, Spector, Parmee & Beyer, (Eds.), Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2000), pp. 275-282, Las Vegas, NV: Morgan Kaufmann (Jul. 10-12, 2000). (Also IlliGAL Report No. 2000001).95Pelikan, M. et al. Hierarchical Bayesian optimization algorithm: toward a new generation of evolutionary algorithms. SICE 2003 Annual Conference. vol. 3, Aug. 4-6, 2003 pp. 2738-2743 vol. 3.96Pelikan, M., "Bayesian Optimization Algorithm: From Single Level to Hierarchy." Doctoral dissertation, University of Illinois at Urbana-Champaign, Urbana, IL, 2002. (Also IlliGAL Report No. 2002023).97Pelikan, M., "Hierarchical Bayesian Optimization Algorithm: Toward a New Generation of Evolutionary Algorithms." Springer, pp. 2738-2743 (2005).98Plutowski & White, "Selecting Concise Training Sets from Clean Data." IEEE Trans. Neural Networks, 4, pp. 305-318, 1993.99Ratle, "Accelerating the Convergence of Evolutionary Algorithms by Fitness Landscape Approximation." In Parallel Problem Solving from Nature, Eiben, Back, Schoenauer & Schwefel (Eds.), vol. V., pp. 87-96, Berlin, Germany. Springer (1998.100Redmond & Parker, "Actuator Placement Based on Reachable Set Optimization for Expected Disturbance." J. Optimiz. Theory Applic., 90(2), pp. 279-300, Aug. 1996.101Rosenbrock, "An Automatic Method for Finding the Greatest or Least Value of a Function." Comput. J., 3(3), pp. 175-184, 1960.102Sacks, Welch, Michell & Wynn, "Design and Analysis of Computer Experiments." Statist. Sci., 4, pp. 409-435, 1989.103Santarelli, Goldberg & Yu, "Optimization of a Constrained Feed Network for an Antenna Array Using Simple and Competent Genetic Algorithm Techniques." Military and Security Application of Evolutionary Computation (MSAEC-2004), Workshop Proceedings at the Genetic and Evolutionary Computation Conference, 2004 (3 pages).104Santarelli, Yu, Goldberg, Altschuler, O'Donnell & Southall (in press), "Military Antenna Design Using Simple and Competent Genetic Algorithms." Computer and Mathematics with Applications and Mathematical and Computer Modeling (72 pages), 2005.105Sastry & Goldberg, "Genetic Algorithms, Efficiency Enhancement, and Deciding Well with Fitness Functions with Differing Bias Values." Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2002), pp. 536-543, 2002. (Also IlliGAL Report No. 2002003).106Sastry & Goldberg, "Designing Competent Mutation Operators Via Probabilistic Model Building of Neighborhoods." Proceedings of the Genetic and Evolutionary Computation Conference, 2, pp. 114-125. (Also IlliGAL Report No. 2004006).107Sastry & Goldberg, "Don't Evaluate, Inherit." Proceedings of the Genetic and Evolutionary Computation Conference. pp. 551-558, 2001. (Also IlliGAL Report No. 2001013).108Sastry & Goldberg, "Genetic Algorithms, Efficiency Enhancement, and Deciding Well with Differing Fitness Bias Values." Proceedings of the Genetic and Evolutionary Computation Conference, pp. 536-543, 2002a. (Also IlliGAL Report No. 2002003).109Sastry & Goldberg, "Genetic Algorithms, Efficiency Enhancement, and Deciding Well with Differing Fitness Variances." Proceedings of the Genetic and Evolutionary Computation Conference, pp. 528-535, 2002b. (Also IlliGAL Report No. 2002002).110Sastry & Goldberg, "Let's Get Ready to Rumble: Crossover Versus Mutation Head to Head." Proceedings of the Genetic and Evolutionary Computation Conference, 2, pp. 126-137, 2004. (Also IlliGAL Report No. 2004005).111Sastry , Abbass & Goldberg, "Sub-structural Niching in Non-Stationary Environments." Urbana, IL: Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, 2004. (Also IlliGAL Report No. 2004035).112Sastry , Goldberg & Pelikan, "Efficiency Enhancement of Probabilistic Model Building Genetic Algorithms." Urbana, IL: University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, 2004. (Also IlliGAL Report No. 2004020).113Sastry , K., "Evaluation-Relaxation Schemes for Genetic and Evolutionary Algorithms." Master's thesis, University of Illinois at Urbana-Champaign, General Engineering Department, Urbana, IL, 2001. (Also IlliGAL Report No. 2002004).114Sastry, Johnson, Goldberg & Bellon, "Genetic Programming for Multiscale Modeling." International Journal of MultiScale Computational Engineering, 2(2), pp. 239-256, 2004.115Sastry, K. et al. Efficiency Enhancement of Genetic Algorithms via Building-Block-Wise Fitness Estimation. Evolutionary Computation, 2004. CEC2004. Congress on vol. 1, Jun. 19-23, 2004 pp. 720-727 vol. 1.116Sastry, Lima, & Goldberg, "Evaluation Relaxation Using Substructural Information and Linear Estimation." Proceedings of the 2006 Genetic and Evolutionary Computation Conference, pp. 419-426, 2006. (Also IlliGAL Report No. 2006003).117Sastry, Pelikan, & Goldberg, "Efficiency Enhancement of Genetic Algorithms Via Building-block-wise Fitness Estimation." Proceedings of the IEEE International Conference on Evolutionary Computation, pp. 720-727, 2004. (Also IlliGAL Report No. 2004010).118Schwarz, G., "Estimating the Dimension of a Model." The Annals of Statistics, 6, pp. 461-464, 1978.119Sebag & Ducoulombier, "Extending Population-Based Incremental Learning to Continuous Search Spaces." Lecture Notes in Computer Science, 1498, pp. 418-427, 1998.120Simpson, Mauery, Korte & Mistree, "Comparison of Response Surface and Kriging Models for Multidisciplinary Design Optimization." AIAA, Tech. Rep., 1998 (11 pages).121Sims, "Artificial Evolution for Computer Graphics." Comput. Graph., 25(4), pp. 319-328, 1991.122Smith, Dike & Stegmann, "Fitness Inheritance in Genetic Algorithms." In Proceedings of the ACM Symposium on Applied Computing, pp. 345-350, 1995. New York, NY, USA: ACM.123Spears, W., "Crossover or Mutation?" In Whitley, (ed.), Foundations of Genetic Algorithms 2, pp. 221-237. San Mateo, CA: Morgan Kaufmann (1993).124Srivastava, R., "Time Continuation in Genetic Algorithms." Masters thesis, University of Illinois at Urbana-Champaign, Urbana, IL, 2002. (Also ILLiGAL Report No. 2002021) Available: ftp://ftp-illigal.ge.uiuc.edu/pub/papers/IlliGALs/2002021.ps.Z.125Stocai, Klimeck, Salazar-Lazaro, Keymeulen & Thakoor, "Evolutionary Design of Electronic Devices and Circuits." Proc. 199 Congress on Evolutionary Computation, pp. 1271-1278, Piscataway, NJ: IEEE, Jul. 1999.126Takagi, H., "Interactive Evolutionary Computation: Fusion of the Capabilities of EC Optimization and Human Evaluation." Proceedings of the IEEE, 89(9), pp. 1275-1296, 2001.127Thierens, D., "Scalability Problems of Simple Genetic Algorithms." Evolutionary Computation, 7(4), 331-352, 1999.128Toda, Kawai & Tsuzaki, "Optimizing Sub-Cost Functions for Segment Selection Based on Perceptual Evaluations in Concatentative Speech Synthesis." In Proceedings of ICASSP, pp. 657-660. Montreal, Canada, 2004.129Vaughan, Jacobson, Armstrong, "A New Neighborhood Function for Discrete Manufacturing Process Design Optimization Using Generalized Hill Climbing Algorithms." ASME Journal of Mechanical Design, 122(2), pp. 164-171, 2000.130Vijayakumar & Ogawa, "Improving Generalization Ability Through Active Learning." IECE Trans. Inform. Syst., E82-D(2), pp. 480-487, 1999.131Watson, J., "Empirical Modeling and Analysis of Local Search Algorithms for the Job-shop Scheduling Problem." Doctoral dissertation, Colorado State University, Fort Collins, CO, 2003 (Part 1 of 2�pp. 1-130).132Watson, J., "Empirical Modeling and Analysis of Local Search Algorithms for the Job-shop Scheduling Problem." Doctoral dissertation, Colorado State University, Fort Collins, CO, 2003 (Part 2 of 2�pp. 131-217).Referenced byCiting PatentFiling datePublication dateApplicantTitleUS829671130 Sep 201023 Oct 2012Synopsys, Inc.Method and apparatus for using entropy in ant colony optimization circuit design from high level synthesisUS2010023253325 Aug 200916 Sep 2010Lee Daniel ChonghwanMethods of Selecting Signal Transmitting, Receiving, and/or Sensing Devices with Probabilistic Evolutionary Algorithms in Information Conveyance SystemsRotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google