CHEMICAL REACTION-TYPE METAHEURISTIC

• US 20100057650A1
• Filed: 07/06/2009
• Published: 03/04/2010
• Est. Priority Date: 08/29/2008
• Status: Active Grant

• Current Assignee: Jang Partners LLC (Intellectual Ventures LLC)
• Original Assignee: Jang Partners LLC (Intellectual Ventures LLC)
• Inventors: LI, VICTOR ON-KWOK, Lam, Albert Yun Sang
• Granted Patent: US 8,706,423 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: B82Y 10/00 Nanotechnology for information processing, storage or transmission, e.g. quantum computing or single electron logic
• CPC Class Codes: G06N 3/006 based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
• CPC Class Codes: G16B 5/00 ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks
• CPC Class Codes: G16B 99/00 Subject matter not provided for in other groups of this subclass
• CPC Class Codes: G16C 20/10 Analysis or design of chemical reactions, syntheses or processes
• CPC Class Codes: G16C 20/70 Machine learning, data mining or chemometrics

Abstract

Subject matter disclosed herein relates to various embodiments of a chemical reaction-type metaheuristic. According to an embodiment, solutions to an objective function can be determined by iteratively searching for a minimum energy state of one or more interactions of molecules in a chemical reaction. The molecules in the chemical reaction can be assigned to represent the possible outcomes of the objective function. In a specific embodiment, the interactions of the molecules can modeled as on-wall ineffective collisions, decompositions, inter-molecular ineffective collisions, and synthesis. The type of interaction can affect where the next molecular structure is searched.

Claims

1. A chemical reaction-type metaheuristic computing platform for solving computational problems, comprising:

an initialization module for;

obtaining an objective function that is subject to constraints and the number of possible solutions to the objective function, and

assigning molecular structures and chemical reaction parameters;

an iteration module for implementing the chemical reaction-type metaheuristic that models one or more interactions of the assigned molecular structures to reach a low energy stable state, wherein energy values of the one or more interactions are determined and recorded in a memory of the computing platform, wherein the iteration module continues a series of iteration steps until a stopping criteria is met, wherein the minimum energy value recorded in the memory after the stopping criteria is met provides a global minimum; and

an output module for obtaining the solution for the objective function that corresponds to the global minimum and outputting the solution for the objective function that corresponds to the global minimum to a display.

2. The chemical reaction-type metaheuristic computing platform according to claim 1, wherein the one or more interactions of the assigned molecular structures comprises at least one of on-wall ineffective collision;

decomposition;

inter-molecular ineffective collision; and

synthesis.

3. The chemical reaction-type metaheuristic computing platform according to claim 1, wherein each iteration step includes:

determining a reaction type of a current interaction, wherein the reaction type is one of on-wall ineffective collision, decomposition, inter-molecular ineffective collision, and synthesis;

obtaining an energy value for the current interaction;

comparing the energy value for the current interaction with the stopping criteria; and

selecting a next interaction according to the energy value of the current interaction.

4. The chemical reaction-type metaheuristic computing platform according to claim 3, wherein each iteration step further includes:

comparing the energy value for the current interaction with the lowest energy value recorded in the memory of the computing platform; and

recording the energy value for the current interaction into the memory of the computing platform if the energy value for the current interaction is lower than the lowest energy value recorded in the memory of the computing platform.

5. A method, comprising:

executing instructions on a computing platform so that one or more interactions of molecules in a chemical reaction represented within said computing platform by digital electronic signals reaches a low energy stable state via digital electronic signal implementation of a chemical reaction-type metaheuristic, wherein the digital electronic signal implementation of the chemical reaction-type metaheuristic comprises using digital electronic signals to process one or more outcomes for an objective function; and

executing instructions on the computing platform to output to a display the one or more outcomes for the objected function corresponding to a minimum value for the low energy stable state.

6. The method of claim 5, wherein said executing instructions on the computing platform so that one or more interactions of molecules in the chemical reaction reaches the low energy stable state comprises implementing with digital electronic signals one or more elementary reactions of the group consisting of an on-wall ineffective collision;

a decomposition;

an inter-molecular ineffective collision; and

a synthesis.

7. The method of claim 5, wherein said objective function comprises a non-deterministic polynomial-time hard (NP-hard) problem.

8. The method of claim 5, wherein the digital electronic signal implementation of the chemical reaction-type metaheuristic comprises using digital electronic signals to process one or more outcomes for one or more of electronic component placement, allocating channels in radio network, assigning sensor reports in tracking with sensors, cell placement for integrated circuit chip, and circuit design.

9. A computer-implemented method comprising:

executing instructions on a computing platform to apply digital electronic processing to an objective function subject to constraints in order to obtain one or more outcomes for said objective function, wherein said digital electronic processing is applied to said objective function via implementation of a chemical reaction-type metaheuristic in which digital electronic signals representing one or more interactions of molecules in a chemical reaction are processed digitally to reach a low energy stable state.

10. The method of claim 9, wherein said one or more outcomes for said objective function subject to constraints comprises one or more improved outcomes for electronic component placement, allocating channels in radio network, assigning sensor reports in tracking with sensors, cell placement for integrated circuit chip, or circuit design.

11. The computer-implemented method of claim 9, wherein said executing instructions on the computing platform to perform digital electronic signal implementation of said chemical reaction-type metaheuristic comprises implementing said chemical reaction-type metaheuristic using digital electronic signals to process one or more outcomes for said objective function subject to constraints;

said objective function subject to constraints comprising an otherwise computationally intractable problem.

12. An apparatus comprising:

a computing platform, said computing platform being adapted to;

execute instructions so that one or more interactions of molecules in a chemical reaction represented within said computing platform by digital electronic signals reaches a low energy stable state via digital electronic signal implementation of a chemical reaction type metaheuristic, the digital electronic signal implementation of the chemical reaction-type metaheuristic processing one or more outcomes for an objective function; and

output to a display the one or more outcomes for the objected function corresponding to a minimum value for the low energy stable state.

13. The apparatus of claim 12, wherein said computing platform being further adapted execute instructions to implement one or more of:

an on-wall ineffective collision;

a decomposition;

an inter-molecular ineffective collision; and

a synthesis, so that the one or more interactions of molecules in the chemical reaction represented within said computing platform by digital electronic signals reaches the low energy stable state via said digital electronic signal implementation of said chemical reaction-type metaheuristic.

14. The apparatus of claim 12, wherein said objective function comprises a nondeterministic polynomial-time hard (NP-hard) problem.

15. An apparatus comprising:

a computing platform, said computing platform being adapted to;

perform digital electronic signal implementation of a chemical reaction-type metaheuristic, in which digital electronic signals represent one or more interactions of molecules in a chemical reaction to reach a low energy stable state; and

apply a digital electronic process to obtain one or more outcomes for an objective function subject to constraints via said digital electronic signal implementation of said chemical reaction-type metaheuristic.

16. The apparatus of claim 15, wherein said objective function subject to constraints comprises an otherwise computationally intractable problem.

17. An apparatus comprising:

means for representing in digital electronic signals one or more interactions of molecules in a chemical reaction to reach a low energy stable state via a digital electronic signal implementation of a chemical reaction-type metaheuristic; and

means for obtaining in digital electronic signals one or more possible outcomes to a problem based at least in part on said digital electronic signal implementation of said chemical reaction-type metaheuristic.

18. The apparatus of claim 17, wherein said means for representing in digital electronic signals one or more interactions of molecules is configured to represent, in digital electronic signals, one or more elementary reactions of the group consisting of an on-wall ineffective collision;

a decomposition;

an inter-molecular ineffective collision; and

a synthesis.

19. The apparatus of claim 17, further comprising means for applying said representation in digital electronic signals to a non-deterministic polynomial-time hard (NP-hard) problem.

20. An apparatus comprising:

means for performing digital electronic signal implementation of a chemical reaction-type metaheuristic, in which digital electronic signals represent one or more interactions of molecules in a chemical reaction to reach a low energy stable state; and

means for applying a digital electronic process to obtain one or more outcomes for an objective function subject to constraints via said means for performing digital electronic signal implementation of said chemical reaction-type metaheuristic.

21. The apparatus of claim 20, wherein said objective function subject to constraints comprises an otherwise computationally intractable problem.