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

The following data are the result of two separate runs of the CAT system's ConesWorld simulation. Both runs use similar parameters for their initializations. The population consists of 50 agents in each of them; the social topology between them is represented by lBest (each agent having a connection to 2 agents, resulting in a circular chain); the influence is calculated by Majority; the number of cones is 150 (it must be noted that some smaller cones can be consumed by larger cones and not be visible during the simulation); and the A‐values for height, radius, and position are all 3.5

The difference between the two runs is the usage of the system's dynamic landscape. For the first run, the landscape remains static across 20 generations. For the second run, the landscape dynamically updates every 5 generations, for 4 separate landscapes. This combination results in both simulations running for 20 generations, with the second run using (5 generations * 4 landscapes) for its 20. The agents present in each run are persistent in their respective runs, meaning that those agents in the static landscape carry the continuous knowledge of the landscape from initialization until the system stops on the twentieth generation. Similarly, those agents in the dynamic landscape are also persistent, so even though the landscape changes every 5 generations, they continue to possess their past knowledge of the landscape.

The initialization step of each run occurs when the system takes the data used to establish the parameters of the simulation, and generates the given number of cones. While the number of cones is set at 150, a number of these cones are not readily visible, as they are absorbed by the larger cones. Whenever two or more cones overlap, the system is designed to take the maximum of those cones at the given points where they overlap. Those cones subsumed by larger cones in the static landscape will remain hidden throughout the entirety of the run, while those hidden cones in the dynamic landscape have a chance of becoming visible when the dynamic landscape is updated and the dimensions of the cones are altered.

The A‐values fed into the logistics function are used to determine the relative dimensions of each cone. For a given acceptable range of values for the cones to have, each cone will be individually defined based on repeated initial calls of the logistics function as a means of seeding the function, followed by subsequent calls to the function for each newly generated cone. This means that a low A value, which results in the linear results seen in The Cones World section, used for initialization will result in a number of cones that are not terribly dissimilar from one another, the changes in their dimensions being gradual and slight. Using a higher A value, such as 3.5 which was used in these two runs, will result in subsequent calls to the logistics function returning a more chaotic frequency. For this reason, subsequently generated cones can differ dramatically from one another.

A point of interest in Figure 2.9 is the distribution of agents at the time of initialization. They are homogeneously distributed across the landscape, evenly spaced out from one another as well as along the borders of the landscape. With the lBest social network topology visualized, they can be seen connected to one another by a zig‐zagging line and each agent connected to two neighbors. For the purposes of finding a maximum, the early configuration provides a unique sampling of early information for each of the knowledge sources to use. It is for this reason that later we may observe that, once the agents begin to cluster around likely candidates, the dynamic updates can result in a slower ascent back to the maximum. This is because the agents are now tightly clustered and thus yield less relevant data back to their respective knowledge sources.

When viewing the network connections across successive steps, it is possible to see the agents begin to concentrate on a maximum via the convergence of lines. In Figure 2.10, the first two steps depicted on the static landscape on the left indicate that some of the agents have located a local maximum and are investigating it. But as more information is gathered, notice that the large cone towards the right side of the static landscape is abandoned by step 3, as the agents converge more on the overall maximum that has been located. The network takes a denser appearance as more agents gather, and other agents are sent out to explore with the majority remaining with the highest scoring locations.

The shape of the network varies based on the selection made by the user, varying how each agent is able to communicate with its neighbors, and how far information can penetrate the social network. As we can see in Figure 2.11, in a homogeneous topology, all neighbors have an equivalent level of connectedness to all other neighbors. If any given agent has four connections in a homogeneous network topology, then ALL agents have four connections in a homogeneous network topology. Heterogeneity in network topologies can be seen in the uses of subcultures, in which network connections are awarded based on agent merit, and in randomization, in which each agent has access to a random number of others as discussed next in Chapter 3.

Figure 2.9 The initialization stage of the static (above) and dynamic (below) landscape runs.

Figure 2.10 Five steps of the static (left) and dynamic (right) landscape networks.

Figure 2.11 The homogeneous topologies. (a) Ring topology, (b) square topology, (c) global topology, (d) hexagon topology, and (e) octagon topology.

Meanwhile in the dynamic landscape, it is possible to see in Figure 2.10. that they are just beginning to cluster as the agents in the static landscape did, when the first dynamic change occurs to the landscape. The agent cluster, which had previously begun congregating on the overall maximum for the dynamic landscape, is suddenly clustered near a new overall maximum, although the centroid of the cluster is not on it. But because the loosely clustered group was near the overall maximum, they were able to then cluster on the maximum and send out exploratory agents to investigate the newly changed landscape. As the A‐value for the dynamic landscape is 3.5, this means that each dynamic shift will be a radical update which can result in the total possible maximum being significantly lower as no cone approaches a height similar to those of a pre‐updated landscape. This will be displayed later in the scoring results of the agents working in the static and dynamic landscapes.

The movement of the social clusters, with regards to the network topologies displayed in Figure 2.11, gives us an idea of how the mass of agents moves, with new, more rewarding locations, being disseminated among the other agents at varying rates depending on the shape of the network topology. As the network change will not only produce new information but will make some old information obsolete. For example, overabundance of connections may be both beneficial and detrimental depending on which information is discovered first. Therefore, any poisonous data introduced into a network can take longer to be purged from the system based on how it is able to move through said network (Figure 2.12).

While continuing the simulation, it is possible to view not only the agents and their network shared network topology, but also the area which each influencing knowledge source encompasses. By identifying each agent with the knowledge source which is influencing it, and then compiling the coordinates of each agent, it is possible to draw a bounding box which contains all agents that adhere to a given knowledge source. The structures of these boxes and their subsequent expansions and contractions can serve to highlight the nature of each knowledge source.

Boxes that contract over successive steps indicate an exploitative knowledge source, such as the Situational knowledge source. These knowledge sources will tend to focus on a known best example and explore in its immediate vicinity for any possible improvement. Boxes that expand over successive steps or trend toward more encompassing sizes typically represent the explorative knowledge sources, such as the Topographical knowledge source. These knowledge sources tend to send out agents to possibly high‐scoring predicted spots based on calculations made with known data.

While explorative search suffers from covering massive amounts of ground with limited agents, exploitative suffers from a blindness brought on from agents that only focus on the immediate. With agents sharing information between knowledge sources, however, both types of knowledge source will benefit.

When the CAT system has finished running its generations across the two landscapes, it is possible to view the results of each generation's top scoring results. In Figure 2.13 these results are depicted, with each line indicating the results of one of the knowledge sources. The static landscape's generations display a steady maintenance of the discovered maximum in the landscape, while the dynamic landscape's generations show the dramatic drop‐off each time a dynamic update of the landscape occurs.

Earlier it was mentioned that the homogeneous distribution of agents during the initialization phase of the runs gave a wide breadth of knowledge to the knowledge sources to use during each subsequent step. This could account for rapid early acquisition of a maximum. However, the dynamic landscape's violent landscape changes, which can result in clusters of agents suddenly being on a low‐scoring point in the landscape in unfamiliar terrain, show a more dramatic difference between the scores of the agents immediately after the shift, and several steps later when the maximum is reclaimed.

Figure 2.12 Five steps of the static (left) and dynamic (right) bounding boxes.

Also due to the chaotic nature of the 3.5 value of A of the dynamic landscape's updates, note that the overall possible maximum changes not only its position but also its magnitude with the shifts. This explains the low yet stable fitness values achieved during different points in the dynamic landscape, where plateaus occur in the data.

Figure 2.13 The KS fitnesses for the static (above) and dynamic (below) landscapes.

In addition, as noted in the discussion of bounding boxes, the exploitative and explorative aspects of the knowledge sources can be discerned from their adherence to a found maximum when viewed by the knowledge source fitnesses. Those exploitative knowledge sources, such as Situational and Historical, will tend to achieve a high fitness and then stay at that level. The explorative knowledges source on the other hand, such as Topographical and Domain, will tend to stay away from the maximum as they seek out more information.

In Figure 2.14, we can see the areas of each bounding box produced by each knowledge source. It can be seen in this visualization that the two most exploitative knowledge sources, situational and historical, regularly have the smallest areas of coverage, while the two most explorative knowledge sources, normative and topographical, cover the largest areas. The domain knowledge source straddles the line between these two methodologies of exploration and exploitation, expanding and contracting itself as data come in, focusing on a transitional region between the more extreme knowledge sources.

Figure 2.14 The span of each Knowledge Source's bounding boxes.

Using this resulting information, it is possible to not only find the solution to a given problem but also to illustrate the in‐depth means by which the solution was found, and how each knowledge source contributed toward a given goal. It is due to this shared responsibility of the knowledge sources to both maintain acquired knowledge and push for the acquisition of new knowledge that the system maintains the balance between all of the knowledge sources as they each assert their influence over the collected individuals of the simulation.