Data processing: artificial intelligence – Knowledge processing system – Knowledge representation and reasoning technique
Reexamination Certificate
2006-11-15
2011-11-08
Gaffin, Jeffrey A (Department: 2129)
Data processing: artificial intelligence
Knowledge processing system
Knowledge representation and reasoning technique
C706S019000
Reexamination Certificate
active
08055600
ABSTRACT:
The present invention relates to methods and systems for applying evolutionary algorithms to generate robust search strategies for problems including decision variables. In one aspect, the invention encodes genomes of at least one triplet comprising a variable, assignment priority, and assigned value. The genome may later be decoded to determine a partial or complete assignment of values to variables. If a partial assignment is reached, a search strategy may be applied to generate a complete or more complete assignment. The genomes may also be evolved to produce offspring genomes.One type of evolutionary operator, called the Lamarckian operator is introduced, wherein the similarities, differences, and unbound variables resulting from the decoding of two or more parent genomes are collected. These collections are then used to encode an offspring genome, building upon the strengths of the parents.
REFERENCES:
Fonseca et al., Multiobjective Optimization and Multiple Constraint Handling with Evolutionary Algorithms I: A Unified Formulation, 1995.
Shibuya et al., Integration of Multi-objective and Interactive Genetic Algorithms and its Application to Animation Design, 1999.
Stanford Encyclopedia of Philosophy Supplement to Set Theory, 2002.
Yokota et al., Genetic Algorithm for Non-Linear Mixed Integer Programming Problems and Its Applications, Computers ind. Engng vol. 30, No. 4, pp. 905-917, 1996.
Bartak “Theory and Practice of Constraint Propagation.” pp. 7-14, CPDC 2001.
Rechenberg, Ingo (1973) “Evolution strategy: optimization of technical systems according to the principals of biological evolution”, Stuttgart: Fromman-Holzboog.
Schwefel, H.-P. (1977) “Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie”, Basel: Birkhaeuser.
Schwefel, H.-P. (1987), “Collective Phenomena in Evolutionary Systems,” 31st Ann. Mtg. Int'l. Soc. for General System Research, Budapest, pp. 1025-1033.
Schwefel, H.-P. (1994), “Evolution and Optimum Seeking,” Dortmund <retrieved from http://1s1 1-www.cs.uni-dortmund.de/lehre/wiley/>.
Goldberg D. E. et al., “Messy Genetic Algorithms : Motivation, Analysis, and First Results,” Complex Systems, vol. 3, n 5, pp. 493-530, (1989). (Also TCGA Report 89003).
Dumeur, R., “Evolution Through Cooperation: The Symbiotic Algorithm,” Lecture Notes in Computer Science, Vol. 1063, Selected Papers from the European conference on Artificial Evolution, pp. 145-158, ISBN:3-540-61108-8, Publisher Springer-Verlag London, UK (1995).
Dumeur et al., “Applying Evolutionary Search to Generate Robust Constraint Programming Search Strategies”, Kluwer Academic Publishers, pp. 1-30, (2006).
Baldwin, J. M., “A New Factor in Evolution,” American Naturalist 30, pp. 441-451, 536-553, (1896).
Deb, K., et al., “A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGAII,” in: M. Schoenauer, K. Deb, G. Rudolph, X. Yao, E. Lutton, J. J. Merelo and H.-P Schwefel (eds.):Proceedings of the Parallel Problem Solving from Nature VI Conference. Paris, France, pp. 849-858, Springer. Lecture Notes in Computer Science No. 1917, (2000).
Falkenauer, E. et al., “A Genetic Algorithm for Bin Packing and Line Balancing,” Proceedings of the IEEE 1992 International Conference on Robotics and Automation, pp. 1186-1192, (1992).
Goldberg, D. E. et al., “Don't Worry, Be Messy,” in: R. Belew and L. Booker (eds.): Proceedings of the Fourth International Conference on Genetic Algorithms, San Mateo, CA, pp. 24-30, Morgan Kaufman, (1991).
Heitkoetter, J., “Collection of 48 0/1 Multiple Knapsack Problems,” http://people.brunel.ac.uk/mastjjb/jeb/orlib/files/mknap2.txt, 44 pages.
Holland, J. H., “Adaptation in Natural and Artificial Systems,” Ann Arbor, MI: University of Michigan Press, (1975).
Walshaw, C. et al., “Multilevel Mesh Partitioning for Heterogeneous Communication Networks,” Future Generation Computer Systems,17(5), pp. 601-623 (2001).
Shaw, P, “A Constraint for Bin Packing,” in: Proceedings of the 10th Int'l. Conf. on Principles and Practice of Constraint Programming (CP 2004). pp. 648-662, (2004).
Smith, J. and T. C. Fogarty, “Self Adaptation of Mutation Rates in a Steady State Genetic Algorithm,” International Conference on Evolutionary Computation, pp. 318-323 (1996). <retrieved from http://www.cems.uwe.ac.uk/˜jsmith/ on May 22, 2007>.
Syswerda, G., “A Study of Reproduction in Generational and Steady State Genetic Algorithms,” G. J. E. Rawlins (ed.): Foundations of Genetic Algorithms. Morgan Kaufmann Publishers, pp. 94-101, (1991).
Trick, M., “Michael Trick: Operations Research Page,” <http://mat.gsia.cmu.edu/COLOR/instances.html> <last viewed 2005>, 3 pages.
Walshaw, C., “The Graph Partitioning Archive:: Colouring Annexe,” <http://staffweb.cms.gre.ac.uk/wc06/partition/index-colour.html> <last viewed 2005>, 19 pages.
Schwefel, H. P.: 1965, “Kybernetische Evolution als Strategie der experimentellen Forschung in der Stromungstechnik”. Master's thesis, Technical University of Berlin.
Dumeur Renaud
Puget Jean-Francois
Shaw Paul
Brown, Jr. Nathan
Carey, Rodriguez, Greenberg & Paul
Gaffin Jeffrey A
Greenberg, Esq. Steven M.
International Business Machines - Corporation
LandOfFree
Systems and methods for applying evolutionary search to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Systems and methods for applying evolutionary search to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Systems and methods for applying evolutionary search to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4296802