SA-OT: Simulated Annealing for Optimality Theory

Please, give the details of your model, and we shall run SA-OT for you. This site is useful for models with a finite number of candidates, and you are asked to list them all. Unfortunately, if your model consists of an infinite (or extremely high) number of candidates, you will have to write your own simulation, in which you describe the elements of your model

Articles on SA-OT

Examples

The unordered tableau:

You have to give the violations assigned by each constraint to each candidate in the form of a usual OT tableau. This tableau is unordered, however: the order in which the constraints appear will not affect the simulation. Therefore, you may run the simulation with different hierarchies without having to rewrite the tableau. Even more, you can leave out a constraint from the hierarchy, without having to re-edit the tableau. I hope that this may save you much unnecessary work. If fact, you will specify the hierarchy only later, here you only specify the constraints.

Cells in the tableau are divided by the & symbol (for users of LaTeX...). If you have a tableau as a table in a Word document, first convert it to a text and specify the & symbol as the divider between cells. Then, you can simply copy-paste it to your browser. If you have edited your tableau in some other format, hopefully you can also find a simple way to transform it.

At the end of a row, type one Enter (new-line character). Do not worry if your browser starts a new line without you having typed Enter: it does not count as a new-line. If you prefer, you may also insert empty lines between the rows. Yet, importantly, do not begin the tableau with an empty line! The first line must be the header, that is, the list of the constraints.

The top leftmost cell will be ignored. If you wish, you could add here the input, as it is usual in OT. Then come the constraints, separated by the & symbol. Be careful to use exactly the same constraint names as below. Upper and lower cases are considered as different. Do not use the following symbols in the name of a constraint: '&', ':', space, tab. Spaces (and tabs) are ignored.

Why don't you just rename your constraints for the sake of the simulation as A, B, C, etc., to save yourself some troubles? Alternatively, you can copy-paste the name of the constraints to the latter fields.

From the second row onwards, the first cell always contains the name of the candidate, and the following cells the violation levels (the number of violation marks) it incurs by the constraints. If the third cell in the first row contains the constraint name PARSE, then the third cell of each further (non empty) row should contain the violations assigned by constraint PARSE. Do not forget to count the leftmost empty cell in the first row, which corresponds to the first cell in each row containing the candidate's name.

The precaution just mentioned about the constraints' names apply also for the candidates' names. Yet, the same character string can be used both as the name of a candidate and as the name of a constraint: they do not interfere with each other.

The violation levels (number of violation marks) should be given as numbers. Alternatively, you can give them as a sequence of stars (*), but then no other character (except of blank spaces) can occur in this cell. The program also works with non-integer and negative values, as violation levels. Empty cells in the tableau will be interpreted as zero violation mark---this should save you some typing.

The tableau does not have to look nice, but a nicely organised tableau may help your work. Examples:

Inp &	A &	B &	C &	D &	E
cand1 &	1 &	0 &	0 &	2 &	1
cand2 &	3 &	0 &	0 &	0 &	1
cand3 &	1 &	1 &	2 &	1 &	1

The following tableau is equally fine (at least, for the program...), and is equivalent to the previous one:

& Contr1 & Faithfulness-VerY(Important) & C3 & 4 & PaRSe
candidate-A & 1 &     & 0    &      2 & 1.000
this_is_also_a_candidate & * * *     &    & 0 &    & 1
third & 1 &     1     & *  * & * & 1

It may be handy to create the tableau separately -- for instance, in your favourite text editor -- and to copy-paste to here. Then, you can more easily edit it, and you may also want to save it for later usage.

Neighbourhood structure

Here, you have to define the neighbourhood structure on the candidate set.

Each row begins with the candidate whose neighbours you are defining in that row. After the first ':' symbol, its neighbours are listed, and separated from each other by an & symbol. The last neighbour listed must not be followed by an & symbol, but the line should be terminated by a new-line character. Spaces, tabs and empty lines will be ignored.

For instance, if the neighbours of candidate cand3 are candidates apple, pear, candidate5 and Santa-Claus, then you should add the following row:

cand3 : apple & pear & candidate5 & Santa-Claus

Similarly:

candidate5 : apple & cand3 & Santa-Claus
Santa-Claus : cand3 & DonaldDuck & apple & pear & cherry
apple : DonaldDuck
pear :
LonelyLady :

Usually, if candidate A has a neighbour B, then B also has A as neighbour. Nonetheless, nothing forces you to do so. Moreover, a candidate may have no neighbour at all. In the above example, candidate pear is a dead-end: the simulation can reach it through candidate Santa-Claus, but cannot leave it. Candidate LonelyLady is a different type of neighbour-less candidate: the only way to reach it is by using it as an initial candidate. This will happen for it appears as the head of some row, and then the simulation will be stuck in this state.

Importantly, if you do not list a candidate here, it will not be used in the simulation. If a candidate does not appear as the head of some row, no simulation will use it as the initial candidate, and will be considered as having no neighbour. This is the case of candidate cherry in the above example, which thus behaves also as a dead-end, similarly to candidate pear. Candidate melon does not appear anywhere, so it does not exists from the viewpoint of the simulation (even if you want GEN to produce it).

Once the simulation is in a particular state, each listed neighbour will be picked with equal a priori probability. That is, if a certain candidate has four neighbours, then each of them will have 25% chance to be chosen as a possible target state (before the algorithm decides whether to really move there). You can increase the a priori probability of picking some neighbour by entering it more times: each token will have equal probability.

For instance, suppose that whenever the random walker is positioned at the candidate cand3, you want the neighbour pear be picked with probability 0.4, whereas the other three candidates with probability 0.2. Then, you can enter the following line:

cand3 : apple & pear & pear & candidate5 & Santa-Claus

cand8 : cand1 & cand1 & cand2 & cand2 & cand2 & cand3 & cand3 & cand3 & cand3 & cand3

A last, but very important remark: double check whether you have not misspelled any of the candidates' name! Similarly to the tableau, you may want to edit the neighbourhood structure in a separate text editor, and save it as a file.

K-values

Here, you define the ranking of the constraints, and some more stuff.

In SA-OT, each constraint has an index (a rank or a K-value). The higher a constraint is ranked in the hierarchy, the higher value it receives.

In each row, you have to put the name of a constraint (exactly as spelled in the tableau), followed by a ':' symbol, and followed by its K-value. Spaces and tabs are ignored.

By default, the lowest ranked constraint is assigned K=0, and the K-values increase gradually. For instance, if your hierarchy is A >> B >> C >> D, then you may want to type:

A : 3
B : 2
C : 1
D : 0

The order in which you enter the rows, as well as blank space within the rows do not matter:

A : 3
C     :    1

   D : 0
B :   2

Assigning different K-values is also possible. The following values still correspond to the same hierarchy, though the simulation may return different frequencies:

A : 15
B : 2.3
C : 0
D : -2

When you press the button to run the simulation, the results will appear in a new window. Then, you may come back to this window, and change something. Frequently, you will change the hierarchy, re-rank two constraints, or leave out a constraint. Then, you do not have to change the previous fields (the tableau, for instance), but simply to assign the constraints new K-values.

For instance, if you decide to remove constraint D from the above hierarchy and to rerank B and C, then you can re-run your simulation simply with the following K-values:

A : 3
B : 1
C : 2

Parameters for dropping temperature:

The simulation diminishes temperature T using a double linear cycle:

for K = K-max to K-min step - K-step
    for t = t-max to t-min step - t-step
       core of the loop
   end-for t
end-for K

Importantly, the end of each cycle is not reached. For instance, if t were equal or lower than t-min, than the core of the loop is not run anymore. Therefore, the default value of t-min is 0, although t can never reach 0. Note that K-step and t-step have positive values.

In other words, the two variables take usually the following values:

K = K-max ; K-max - K-step ; K-max - 2 x K-step ; ... ; K-min + K-step
t = t-max ; t-max - t-step ; t-max - 2 x t-step ; ... ; t-min + t-step

Typical values are:

K-max: the index (K-value) of the highest ranked constraint + (at least) 1
K-min: lower than the index of the lowest ranked constraint. If you have assigned index 0 to the lowest ranked constraint, then K-min is a negative number. Additionally, it should be low enough so that a local optimum can be reached, in function of the other parameters (primarily t-step), and of the search space. Yet, don't make the simulation run unnecessarily much. Typically, K-step = -10 / t-step, (but not more than K-step=-2) should work.
K-step: typically, 1.
t-max: typically, 3.
t-min: typically, 0.
t-step: this is the parameter that can change the most, because it directly influences the number of iterations -- hence, the precision of the simulation. Typical values might be: 3, 1, 0.3, 0.1, 0.03, 0.01.

If you still feel uncertain about the meaning of these values, just leave these fields empty. The program will fill them with the following default values automatically:

K-max: the highest specified K-value + 1
K-min: the lowest specified K-value - 3
K-step: 1
t-max: 3
t-min: 0
t-step: 0.3
Number of runs: 3

For more details, look at the literature.

Number of runs

In one run, each of the candidates listed in the neighbourhood structure is used once as the initial candidate for the random walk. In other words, one run corresponds to as many simulations as the number of candidates in your model. By setting a higher number, you can run the simulation more than once from each candidate. If, for instance, you set it as 100, the simulation is run 100 times the number of the candidates.

You may happen not to wish to run the simulation from all candidates as initial state. I am afraid you have to wait the program performs all the calculations. Then, you can select the runs you are interested in from the output.

If you leave this field empty, the default value will be 3.

Verbose output

By leaving this box unchecked, the simulation only returns a list in the form: "initial candidate -> output". Each row corresponds to one run of the simulation, which was launched with the initial candidate specified, and returned the given output. At the end, you will also find a summary listing the different outputs just produced, together with their frequencies.

If you check this box, however, you can follow the details of each simulation in a table. It will be especially useful if you want to better understand simulated annealing in general, or the behaviour of your own model, in particular. Later on, you will prefer to uncheck this box, and save time thereby.

Each row of such a table begins with the actual value of the control parameter called "temperature" < K-T, t >. Observe the way temperature drops during the simulation, and compare it to the parameter values you have specified.

Then follows the candidate that constitutes the present state of the simulation. After "--> ?", a second candidate appears: the simulation has picked this one of the neighbours of the original candidate, and ponders whether to step there. You can check that the chosen target candidate is really a neighbour of the previous one, according to the neighbourhood structure you have just entered. Looking through the simulation, you can also check if all possible neighbours of a certain form are really chosen sooner or later. Comparing a row to the beginning of the next row will reveal whether the simulation has finally moved to the next candidate or has decided to stay in the previous state.

At the end of each row, you can follow how the two candidates are compared. For each constraint, the number of the violation marks assigned to the target candidate and to the original candidate is given, as well as their difference. Compare these values to the unranked tableau you have specified. Constraints are considered in decreasing order, following your hierarchy (that is, the decreasing order of the K-values of the constraints). The comparison stops once a fatal constraint is found: a constraint that assigns a different number of violation marks to the two candidates.

At this point, the simulation will also tell you what it has done. If the target candidate is not worse, the simulation moves there. This happens either if the first non-zero difference is negative (the target candidate is assigned less violation marks); or if the two candidates incur exactly the same violations.

Otherwise, the first non-zero difference will be positive, and the question is if the actual temperature is higher or lower than the K-value of the fatal constraint. Whenever this happens you can compare yourself the temperature's actual K-T to the K-value you have specified for the fatal constraint. If the constraint is highly ranked (compared to the temperature), then the system does not move. In the case the constraint is ranked lowly (its K-value is lower then the K-T of the temperature), the system will move. Finally, if the temperature is exactly in the domain of the fatal constraint, a random number is generated and compared to exp(-d/t). (Here, d is the violation difference of the fatal constraint, and t is the second component of the temperature.) In this case, both values will be presented, and you can check that the system moves only if the random number generated is lower than exp(-d/t).

For a more detailed and motivated description of the algorithm, consult the references listed on the literature page. Yet, if you are at least superficially familiar with it, studying the details of the verbose output of this demo should help you in better understanding what is really happening in SA-OT. I do hope that you will find it useful and enjoy it!