Читать книгу Cultural Algorithms - Robert G. Reynolds - Страница 28

As previously stated, each problem in the CAT System is represented by a fitness function. The example fitness function here concerns the problem of seeking a maximum point across a two‐dimensional landscape made up of a variable number of cones. Each cone is defined as a pair of coordinates, a height, and a radius. The number of cones can be defined by the user as denoted in the overview, and the more cones there are, the greater the possibility that there could be multiple cones with an equal, maximum value, as well as more local maxima to hinder the agents seeking the maximum.

The constraints defined during the initialization of ConesWorld include the dimension variables of the two‐dimensional landscape which neither the cones nor the agents can exceed, the maximum and minimum values for the dimensions of the cones, and the rate of change for updates. As it is possible for the ConesWorld fitness function to update its topography, changing the location and dimensions of the cones, these constraints serve to limit what changes can take place in the cones.

In addition to the constraints and basic domain knowledge of the ConesWorld problem, there is also a series of flags for each cone. These flags indicate the directional change a cone may take during an update. There are strict maximum and minimum values that the dimension variables of a cone may change between. The movement between these extremes is cyclical in nature, moving the cone first toward one extreme and then back toward another, similar to how the pistons in an engine can move up and down. Should a cone undergoing an update exceed its dimensional limits, its flag is switched to denote its new increasing or decreasing status, and the amount by which it exceeding its limit then becomes additional change in its new dimension.

For an example of this, assume the cone height limits are set between 1 and 3, and the rate of change is restricted to 0.25 at the most for any single update. If a cone's height is already at 2.80 with its directional flag indicating that it should increase, it will have 0.25 added to it, and it will exceed the height limit of 3 by 0.05. In this case, its flag will be triggered to indicate that it is now decreasing, and the overflow of 0.05 will be taken away from the height of the cone, resulting in a cone of 2.95 height. The next update to the cone, for example 0.20, will result in the cone's height being updated to 2.75, as its directional flag is still indicating that it is decreasing. This decrease will continue until the cone hits the lower limit, at which point the flag will be toggled, the overflow will be added back in, and the cycle will continue again.

While the rate of change is a fixed value, during an update it is not necessarily the only possible rate of change. It simply defines the maximum possible rate of change, but not how wildly the rate of change can vary between any two cones. For that, there are a set of user‐defined variables which are known as the A‐values, one for each of the variables of all cones, height, radius, and spatial dimension. It is entirely possible to specify that one particular aspect, such as the height of the cone, should wildly vary between a set minimal rate of change and a set maximum rate of change, while another aspect should change at a set rate, while a third aspect should predictably variate between one extreme to the next (Figure 2.4).

Figure 2.4 A small ConesWorld topography update of position only.

As the topography of ConesWorld is subject to change if the user defines multiple landscapes for it to generate during a given run, it is entirely possible that new maximum values for the function would be created. At the same time past maximum values might vanish as the cones lower in height. Due to this process of vanishing and reappearing maximums, agents need to adjust their movements and mechanisms to explore the environment for new viable maximum points. This can result in a dramatic downturn in the scoring for a group of agents during an update cycle.

As seen in Figure 2.5, those points on the graph where an upward trend is suddenly interrupted by a dramatic drop in score, followed by a rapid ascension to a steady upward trend is a clear indication of a topographical update occurring in the system. Here what had been a maximum suddenly becomes a non‐maximum, and the agents need to branch out to find the location of the new maximum point. Depending on how dramatically the landscape changes, the reclamation of the previous score may be instantaneous or take several generations to rediscover. For example, a topography where the height and radius of all cones remains static but their positions gradually change places, as seen in Figure 2.4, will result in momentary drop‐offs and then rapid return to the maximum score.

It should also be noted that as there is no guarantee that the absolute allowable maximum height for a cone will be present in any simulation. In fact, it is entirely possible for the overall maximum score to lower over the lifespan of a simulation given multiple topographical updates, as depicted in Figure 2.6. In this case, the height of the cones varied with each update resulting in lower possible maximums due to the shifting nature of the overall possible maximum.

To control this shift, a logistics function is utilized, which produces a change variable that fluctuates between a range of 0 and 1, and this rate of fluctuation may be controlled by the earlier described A‐values that may be set by the user.

Figure 2.5 The Knowledge Source fitness of a ConesWorld simulation undergoing regular topographical update every 20 ticks.

Figure 2.6 ConesWorld KS Fitness with a regular topographical update at every 50 ticks, with variable cone heights.