Knowledge-based solution to dynamic optimization problems using cultural algorithms

Cultural Algorithm (CA) naturally contains self-adaptive components that can make it an ideal model for use in dynamic environments through the utilization of belief space knowledge. This knowledge can be used to influence the evolution process in a self-adaptive way. Cultural Algorithms are computational self-adaptive models which consist of three major components; a belief space, a population space, and a communication channel. The problem solving experience of the selected individuals is generalized and stored as knowledge in the belief space. This knowledge is then utilized to control the evolution of the population space by means of an influence function.; In this thesis we examine the role of five different knowledge structures and their relative contribution to the problem solving process in dynamic environments. In particular, we investigate the contribution of situational knowledge, normative knowledge, topographical knowledge, domain knowledge, and history knowledge structures to the problem-solving process. The first three were previously used in Cultural Algorithms to solve static problems. The latter two were added here to deal with local and global dynamics respectively. The Cultural Algorithm implemented here employed a master influence function that was able to learn to adjust the likelihood that each knowledge source would be used to influence changes in the population based upon their relative performance.; The Cultural Algorithm was used in conjunction with the Morrison & DeJong's problem generator [Morrison 1999] and was applied to static, magnitude dominant, frequency dominant, and deceptive dynamic environments. The result of these experiments demonstrated the following: (1) The presence of the five knowledge sources in the belief space of Cultural Algorithms improved the solution quality and efficiency over that of the corresponding population only evolutionary model. (2) Three phases of problem solving emerged in terms of the relative use of different knowledge sources; coarse-grained, fine-grained, and backtracking. (3) These operator combinations were held together by the synergistic interaction of their component knowledge sources relative to the phase of the problem solving process. (4) The results suggest that the knowledge sources used in a cultural system are a response to the dynamics of the problems solved by that culture.