Cultural Algorithms. Robert G. Reynolds
Читать онлайн книгу.
refining local solutions, often variating only the smallest of feasible changes in any one variable in its search for an improvement to the best known result.
In the CAT System, this is achieved by a tightly clustered local search of areas that deviate only slightly from the position of the best‐known agent. While the Situational Knowledge focuses on the position of agent with the highest fitness, it has a voting system based on different agents and different scores. For example, if a newly discovered agent is found at a tremendous distance from the currently focused‐on position of the Situational Knowledge source, and the increase in performance is minimal, then the Situational Knowledge may vote to remain and more closely examine the immediate area around its currently selected agent.
This influence function is carried out using a roulette wheel, where each piece of the wheel is composed of subsets of elite agents. With regards to the distance between agents described above, agents near possible optimal solutions are subdivided into elite groups, and the roulette wheel's wedges are composed of the best agents from the best subsets. Each agent then spins the wheel and moves to the location given by the best agent selected, plus a randomized position variable addition of the smallest variation possible in the scenario.
Fitness Functions
Each problem available within the CAT System is contained within a Fitness Function, which not only dictates the domain of the problem but also the means by which it can possibly be updated, the metrics by which it can be judged, and any possible cutoff that could be reached by discovering a sought‐after goal.
First basic initialization is performed in which the domain of the problem is established, such as any necessary variables or placeholders, predefined boundaries or caps, or even a maximum possible fitness that the system is to work towards. There are also two functions called CalculateFitness and CalculateFunctionValue. In some cases, it is entirely possible that to get the fitness of a given fitness function, calculating the function itself will yield its fitness. Some other cases have a fitness which is separate from the function value calculated by the fitness function itself. Both Fitness and FunctionValue are calculated by being passed a point in N‐dimensional space, containing the given values for the variables that can alter the results of the system.
If a fitness function has a dimensional input smaller than three (meaning either two or one dimensional inputs), then it is possible for the system to display it in a manner used by the ConesWorld Fitness Function, where the two components of the input represent the X and Z coordinates, and the fitness at that location comprises the Y coordinate (Figure 2.3).
Following these commands are a collection of queries for data such as the constraints of the problem which returns a simple Boolean to denote if an input dimensional point falls within the previously defined domain of the problem. It is also possible to query for the size of the problem's dimensions and the domain constraints themselves.
For some problems that may be defined within the CAT System, it is possible for the actual answer to be known; however, in these cases the system is not aware of how it might reach this particular answer. For example, in an optimization problem, the system may attempt to alter the sizes of various interconnected machinery, each of which has its own constraints it must exist within. The system knows the answer it wants, but not how the parts might be modified to achieve this answer. Another example from ConesWorld has to do with the known dimensions of N‐cones that exist within it, and that it is efficient to query the list of cones for the one with the maximum height. Again, the system knows what the height of the cone is, but it does not need to share the location of that cone with any of the active agents.
Figure 2.3 The fitness of ConesWorld visualized, with the height at any given point representing that point's fitness.
Finally, there is a Change function within each fitness function. While the N‐dimensional points contain all of the variables of the function and can be altered repeatedly throughout the course of the simulation, the purpose of the Change function is to change the domain of the fitness function itself. It could change the structure of an equation, which variables are being used, and the topography of the fitness function itself. This will be further explored in the ConesWorld example given in the following section.
ConesWorld
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).