Post
by lottoarchitect » Wed Oct 05, 2011 5:44 pm
--- BUILDING TECHNIQUES IN DEPTH ---
Building from scratch sequentially in small increments
This is the most important building technique to get very good results almost all the time, especially when small coverings are the target. This is also the recommended way to approach a construction when we don't have a reference of the needed b parameter, which is usually the case when filters, L>1, dual coverage etc are used. For simple coverings, repositories is a good guide for the b parameter.This approach also allows to observe the current state of the optimization and helps in making sensible decisions of what action to take i.e. add more blocks or change the bias/search criteria.
Why small increments? The simple answer is we give the engine the chance to bring the current set of blocks quicker to a much more optimal state before adding more blocks to reach the desired construction properties. This has to do with the complexity of a covering and the intersection of the blocks. An example will make this a bit clear. Suppose we want to build a covering that requires 20 blocks. If we start right away with all 20 blocks (set the b=20), then the engine has to deal with 20 individual blocks to bring them to optimal formation. Consider this situation against an initial start of b=10 blocks optimized and then adding another 10 blocks to be further optimized. In the first case of 20 blocks, WG has to deal with 20 blocks which has to bring them in a good intersection altogether at once. In the case of 10 blocks however, a good intersection can be achieved much quicker because of the reduced blocks WG has to deal with. Adding 10 blocks after that is easier to the engine because it has to merge the new blocks to an already good intersection generated with the initial 10 blocks. It turns out, this approach is faster in producing the desired outcome. Of course, WG will eventually make an equivalent construction even if we start using 20 blocks but it will take longer.
So, use this strategy as often as you can. It demands input from the user on when to add new blocks/change bias as required but it will give good results quicker.
How many blocks to add in each increment? If we know the final b, then 10-20% of that value is a good increment of blocks to use. For example, building an 100 blocks covering, increments of 10-20 blocks is a good range to use. However avoid adding just one block per increment because experience has shown a single block is tougher to merge nicely with the previously optimized set of blocks compared to i.e. 10 added blocks. So the answer is not too many and not too few.
Also it is important to observe the improvements line at the progress tab. This usually help us identify when to add extra blocks or if it is time to change the bias. Explanation of this below at the "picking the right bias" part. During the later stages of the incremental approach, when we are approaching an 100% coverage, a more conservative increment of blocks is usually the best to do. So, if we are e.g. 98% coverage and try to make it 100%, if we so far added 10 blocks per increment, it will be a good idea to reduce it to e.g. 5 blocks per increment.
When the final b is unknown, any initial b value that offers around 20-30% coverage is a good starting point.
CAUTION: Do not stay in each increment till no further improvements occurring no matter what you try. Usually, when no improvements occur, even after changing to a tighter search/algorithm, that means we have managed to produce a "concrete set of blocks" as I call it. A "concrete set of blocks" is blocks that together form a very tight "relationship" which is very difficult to break/change when adding more blocks. So, if new blocks are added, it gets quite tougher to be merged nicely to the "concrete set of blocks". So, any new blocks could be something like a foreign intruder to the initial concrete set and will not become part of a nicely blended set of blocks as it should be. So, as soon as you observe a delay in new improvements, it is probably a good time to take an action (add blocks/change bias). A "concrete set of blocks" should be ideally our final covering to play since this represents a robust construction within its own context. Just keep in mind it is tough to add blocks in such a tight construction and the reason it is not advisable to let this happen during increments. The auto-bias of the engine, after the addition of new blocks, attempts to "break" a concrete set but generally it is better not to be in such a condition during an increment step. Avoiding "concrete sets of blocks" during various increments will pay off at the later increments where the coverage obtained will be higher simply because all the blocks are nicely blended to our cause.
Building from a smaller good covering
Building from a bigger good covering
Picking the right bias expansion/tension for the task
Recall that the engine needs to utilize bad moves in order to make better improvements. The engine also incorporates an auto-bias mechanism which aims to bypass "difficult" situations. A difficult situation is a condition of no matter what we try to change, we can't see an improvement or any change attempted leads to a much worse construction. It is a similar situation to the "concrete set of blocks" discussed above, although to a lesser extend because the engine on its own tries not to reach that state anyway.
The result of auto-bias can be seen at the engine chart. All this auto-bias adjustment works behind the scenes.
However, we are still in need (as per the current WG 1.8.3 release) to tell the engine what is considered a difficult situation and how to tackle this to our benefit. Both sliders adjust the engine on how to react to a difficult situation. In the broadest abstract idea, we can tell the engine that as soon as it faces a difficult situation to attempt to get away from it as soon as possible. On the other extreme side, we can tell the engine to insist in the current difficult situation and dig deeper to find improvements. Between those two extreme approaches, there is a whole range of possible setups.
What is a normal search condition for the engine? If you observe the engine chart, you can see it go up and down in an almost regular pattern and staying within a a steady range of the auto-bias selected by the engine (the values at the vertical axis of the chart). When you see such a smooth behavior, this means the engine can make changes so no need for any special action. From our end, all we need to observe is if the improvements text indicates that we, at least, occasionally equal the best coverage detected by the engine [Improvements : x (y / z), y should not be 0 after a while and in the range of 1-10% of the z - not a strict rule]. If we see y = 0 after i.e. z = 100000 internal moves, then we definitely need to take some action. That means the engine cannot approach the best covering (in terms of coverage) no matter what changes it has performed. This is also identifiable by observing the current coverage against the best the engine has found so far. If it is constantly changing in a range higher than the best found for a while, without giving the "feeling" it approaches the best coverage, then we say the engine has gone "out of focus". Usually in both situations the best action to take is to lower the expansion slider. However, as we keep saying all the time, if we are in the position of having a very low expansion value (which should be avoided), a better solution would be to switch to the "extensive" algorithm and increase the expansion (to compensate for the much tighter search extensive performs) following the same advice above of what we have to observe.
When we have a difficult situation? Occasionally we see a spike upwards in the engine chart. This means that the engine attempts to make changes but they have all been rejected. This is where the auto-bias kicks in. This instruct the engine to allow more bad moves so to get away from that difficult situation.
How quickly to get away from a difficult situation? This is controlled by the left slider (expansion).
How quickly to get back in normal search after a difficult situation? This is controlled by the right slider (tension). The initial default 0 setting is almost the ideal setting for this slider because it translates as a balance between getting back to normal search (as soon as we have moved away from a difficult situation) in a reasonable time. Increasing this to values greater than 0 means we will delay getting back in normal search. The drawback of such a setting is that due to auto-bias increase we may have moved quite far from the difficult situation. The task is to let the engine "break" a difficult situation by doing some rearrangement (by worsening the covering) which will lead to an improvement at a later stage. Increasing the tension value beyond 0 usually does not allow getting back in track for the 99% of the cases, so it should be avoided. On the other hand, although the default 0 value is recommended almost all the time, especially when we are close to make a close-covering (100% coverage) it can be beneficial to lower this value, even down to -1000 (in progressive steps). An alternative building approach is to use a very low tension right of the start e.g. set it to -950 and utilize only the expansion slider. I have seen good results with this approach as well and there maybe a good reason for this. Such a low value translates as we'll get back to normal search quicker so if the expansion has managed to change adequately (during the auto-bias increase) the covering, we don't get far away from that point and trap a near-by improvement. However, in such a tight tension we are in danger of not letting the engine adequately break a difficult situation (stuck in a local minimum). Perhaps a more conservative setting in the range -900 to 0 could be used. Since each covering is unique to its building demands, trying various settings on this slider could be the best guide. As a rule of thumb, always start with the 0 setting and after trying other various approaches (change expansion, search algorithm), we can try adjusting this control. Finally, a final reason we may decide to adjust this control is when we have moved the expansion slider very close to the minimum (recall we should avoid such a low setting) and we see the coverage "getting" away from the current best coverage and not equaling it at all, as the normal search example above. This is a good indication that we should lower the tension control.