Thermodynamic simulated annealing schedule for combinatorial optimization problems

• US 20030014225A1
• Filed: 07/13/2001
• Published: 01/16/2003
• Est. Priority Date: 07/13/2001
• Status: Abandoned Application

• Current Assignee: Juan Francisco De Vicente
• Original Assignee: Juan Francisco De Vicente
• Inventors: De Vicente, Juan Francisco
• Application Number:
  US09/682,043
• Publication Number:
  US 20030014225A1
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

Combinatorial Optimization problems arise in different areas of engineering. Simulated Annealing is a useful combinatorial optimization method. Nevertheless, to achieve high performance with Simulated Annealing costly experimental studies in fine tuning the annealing schedule are required. Present disclosure provide a Thermodynamic Simulated Annealing Schedule (TSAS) to ease simulated annealing application. TSAS is derived from both Thermodynamics and Information Theory. TSAS adapts to the problem and cost function while providing high performance.

Claims

1. A Thermodynamic Simulated Annealing Schedule to ease Simulated Annealing (SA) application in solving combinatorial optimization problems, where the temperature is updated after each local transformation as:

a) the initial temperature while either the global cost variation is positive or all previous probabilities of acceptance are equal to one.

b) proportional to the global cost-decrement achieved at this moment divided by the sum over all previous iterations of the natural logarithm of the applied probabilities of acceptance.