The impact of increased optimization problem dimensionality on cultural algorithm performance
Yang Yang · Human Biology · 2015
ABSTRACT The Impact of Increased Optimization Problem Dimensionality on Cultural Algorithm Performance by Yang Yang August 2015 Advisor: Dr. Robert Reynolds Major: Computer Science Degree: Master of Science In this thesis, we investigate the performance of Cultural Algorithms when dealing with the increasing dimensionality of optimization problems. The research is based on previous cultural algorithm approaches with the Cultural Algorithms Toolkit, CAT 2.0, which supports a variety of co-evolutionary features at both the knowledge and population levels. In this project, the system was applied to the solution of 60 randomly generated problems that ranged from 2-dimensional to 5-dimensional problem spaces. As a result, we were able to produce the following conclusions with regard to our overall objectives: 1. As the landscape dimensionality increases, the Cultural Algorithm needs more computation resource to reach an optimal solution in terms of the number of generations used and the overall time cost. 2. As the landscape dimensionality increases, the influence of the landscape’s complexity upon the performance is harder to discern. 3. As the landscape dimensionality increase, the fitness of individuals influenced by exploratory knowledge sources will decrease. But individuals influenced by exploitative knowledge sources will be affected much less. 4. As landscape dimensionality increase, the average social tension of individuals will be lower and social tension will cool down more frequently. This is because the homogeneous topology employed (square) is not sufficient to create diversity in the population. 5. A homogeneous social fabric is not sufficient to handle increases in problem dimensionality after a certain point. It is sufficient for 2 dimensions, but falls off quickly after that. It suggests that a dynamic heterogeneous social fabric will be more useful for problems of higher dimensionality.