Localized simulated annealing

• US 5,745,735 A
• Filed: 10/26/1995
• Issued: 04/28/1998
• Est. Priority Date: 10/26/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hathaway, David James, Cohn, John Maxwell
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): FREJD, RUSSELL WARREN
• Application Number:
  US08/549,405
• Time in Patent Office: 915 Days
• Field of Search: 395/500, 395/21, 395/13, 395/20, 395/920, 364/491, 364/408, 364/490, 364/468.28, 364/578, 382/14, 430/5, 324/309
• US Class Current: 703/6
• CPC Class Codes: G06F 2111/06 Multi-objective optimisation, e.g. Pareto optimisation using simulated annealing [SA], ant colony algorithms or genetic algorithms [GA]
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement

Abstract

According to the present invention, a method of optimization by simulated annealing is provided that uses a spatial metric to localize the simulated annealing temperature, the move set, and the objects which the moves operate on. The method keeps a local history of the optimization process. The localization allows the simulated annealing process to adaptively control the annealing schedule of each local region independently. This allows the annealing temperature, move set, and the objects upon which the move set operates to each be adjusted for each region independently to maximize efficiency. This results in optimization of all regions in a quick and efficient manner.

Claims

1. An adaptive method for creating a simulated annealing schedule to solve an optimization problem by simulated annealing, wherein the optimization problem is represented by a global cost function, and wherein the simulated annealing solves said problem by proposing and selecting a plurality of moves from a move set, the method comprising the steps of:

a) localizing said problem represented by said global cost function into a plurality of regions;

b) maintaining an annealing history for each said region; and

c) determining a simulated annealing temperature for each of said plurality of regions, each of said simulated annealing temperatures being a function of its associated annealing history.

2. The method of claim 1 further comprising the step of generating a localized move set for each of said plurality of regions, and adjusting said localized move sets according to said associated annealing history maintained for said region corresponding to said localized move sets.

3. The method of claim 1 further comprising the step of adjusting a probability of a move being proposed that affects at least one of the plurality of regions according to the localized annealing history of said at least one region.

4. The method of claim 1 wherein said move set operates upon a plurality of objects, and further comprising the step of localizing said objects which said move set operates upon and adjusting said objects said move set operates upon for each of said plurality of regions according to said associated annealing history maintained for said region corresponding localized objects.

5. The method of claim 1 wherein said move set operates upon a plurality of objects, and further comprising the step of preferentially selecting an object on which to perform a move according to said annealing histories maintained for said plurality of regions.

6. The method of claim 1 wherein the step of determining an annealing history for each of said problem regions further comprises the steps of:

recording the moves proposed that would effect each said region; and

recording the percentage of said moves accepted for each said region.

7. A simulated annealing method of optimizing a combinatorial problem, said problem having a global cost function to be minimized, the method comprising the steps of:

a) localizing said problem into a plurality of regions;

b) determining a plurality of annealing schedules, each annealing schedule associated with one of said plurality of regions, wherein each of said plurality of annealing schedules is adaptively determined according to an annealing history of said associated region;

c) proposing a move in said problem, said move affecting at least one region, and wherein said move changes said global cost function; and

d) evaluating said move according to said temperature of said at least one affected region and said change of global cost function.

8. The method of claim 7 wherein each of said plurality of annealing schedules includes an annealing temperature, wherein each of said annealing temperatures is adaptively determined according to said annealing history of said associated region.

9. The method of claim 7 wherein each of said plurality of annealing schedules includes a move set, wherein each of said move sets is adaptively determined according to said annealing history of said associated region, and wherein the step of proposing a move comprises selecting said move from a move set.

10. The method of claim 7 wherein the step of proposing a move further comprises the step of:

randomly proposing said move and wherein each of said plurality of annealing schedules includes a probability of said move being selected, and wherein the probability of a move being selected is adaptively determined according to said annealing history of said associated region.

11. The method of claim 7 wherein each of said plurality of annealing schedules includes objects which a move set operates upon, wherein the objects which a move set operates upon are adaptively determined according to said annealing history of said associated region.

12. The method of claim 7 wherein each of said plurality of annealing schedules includes an annealing temperature, a move set, and a probability of a move being selected, and wherein said annealing temperature, said move set, and said probability of a move being selected are each adaptively determined according to said annealing history of said associated region.

13. The method of claim 7 wherein said problem is localized according to physical region.

14. The method of claim 7 wherein said problem is localized according to connection.

15. The method of claim 8 wherein said proposed move affects a plurality of said localized regions, and wherein said proposed move is evaluated according to said geometric mean of said temperatures of said plurality of affected regions.

16. The method of claim 8 wherein said proposed move affects a plurality of said localized regions, and wherein said proposed move is evaluated according to said arithmetic mean of said temperatures of said plurality of affected regions.

17. A simulated annealing method of optimizing a combinatorial problem, said problem having a global cost function to be minimized, the method comprising the steps of:

a) dividing up said problem into a plurality of spatial regions;

b) selecting a plurality of temperatures, each temperature associated with one of said spatial regions, wherein each said temperature is adaptively selected according to an annealing history of said associated spatial region;

c) proposing a move in said problem, wherein said move is proposed adaptively according to said plurality of temperatures, said move effecting at least one spatial region, and wherein said move changes said global cost function;

d) evaluating said proposed move, wherein said move is accepted if it improves said global cost function, and wherein said move is accepted if it degrades said global cost function according to a probability which is a function of said mean temperature of said at least one effected region.

18. The method of claim 17 wherein the step of proposing a move comprises selecting a move from a move set, wherein said move set is localized according to said problem regions.