The impact of increased optimization problem dimensionality on cultural algorithm performance

Yang YangDigitalCommons 2015

Abstract

In this research, we investigate the performance of Cultural Algorithms (CA) 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. The system was applied to the solution of 60 randomly generated problems that ranged from 2-dimensional to 5-dimensional problem spaces. Our findings indicate that as landscape dimensionality increases, the Cultural Algorithm requires significantly more computational resources to reach an optimal solution. Furthermore, the influence of landscape complexity becomes harder to discern, and the fitness of individuals influenced by exploratory knowledge sources decreases more sharply than those influenced by exploitative sources. Crucially, we found that a homogeneous social fabric is insufficient to handle increases in problem dimensionality beyond 2D, suggesting the need for dynamic heterogeneous social structures.

Introduction

Global optimization involves finding the absolute best solution in a landscape characterized by numerous deceptive local peaks. As the number of variables, or dimensions, increases, the search space expands exponentially—a challenge known as the "curse of dimensionality." Cultural Algorithms (CAs) address this by mimicking human cultural evolution through two levels: a Population Space (agents searching the landscape) and a Belief Space (a shared repository of knowledge). While CAs have demonstrated success in low-dimensional spaces, this study evaluates their scalability and performance as dimensionality increases from 2D to 5D.

Methodology

The research utilizes the Cultural Algorithms Toolkit (CAT) 2.0, built on the Repast agent-based simulation framework. The model incorporates several key components:

Knowledge Sources (KS)

The Belief Space is divided into five distinct knowledge sources:

  • Normative: Maintains ranges of acceptable values.
  • Situational: Stores specific elite examples.
  • Domain: Identifies landscape patterns.
  • Historical: Tracks significant past events.
  • Topographical: Creates spatial maps of the landscape.

Social Fabric and Decision Making

Unlike standard CAs where individuals operate independently, this model connects agents in a Square Topology. This social fabric allows individuals to influence their neighbors' choice of knowledge source. Decision-making is governed by an Incentive-based Majority Win rule, where agents weight the "votes" of their neighbors based on the average fitness of the knowledge source being utilized.

Social Metrics

To measure population diversity and exploration, the study introduces "Social Tension," defined as the average Euclidean distance between connected neighbors.

Experimental Design

The study employs the Cone’s World Generator to create synthetic benchmarks. This generator produces multi-dimensional surfaces with "cones" of varying heights and slopes. Landscape dynamics are adjusted using a logistic function to create three classes of problems: Fixed (static), Periodic (predictable), and Chaotic (highly unpredictable). A total of 60 random problems were generated, covering 15 configurations for each dimensionality from 2D to 5D.

Results

The experimental results highlight the significant impact of dimensionality on CA performance:

  • Success Rates: While 2D and 3D problems were solved with high reliability, the success rate dropped to 33% for 5D problems within a 2,000-generation limit.
  • Resource Scaling: The average number of generations required for a successful run increased from approximately 28 in 2D to 1,659 in 5D. Computational time scaled dramatically from 40 seconds to nearly 4 hours (13,440 seconds).
  • Accuracy: The "Average Difference" between the found solution and the true optimum increased from 0.039 in 2D to 0.243 in 5D, indicating a loss of precision in higher dimensions.

Discussion

Exploratory vs. Exploitative Knowledge

A key insight from the t-test results is the divergence in performance between knowledge sources. Exploratory sources (Normative and Topographical) suffered significantly as dimensions increased, as the mapping requirements became too vast. Conversely, exploitative sources (Situational, Domain, and History) remained relatively stable, focusing on local refinement rather than global mapping.

Social Tension and Complexity

In unsuccessful high-dimensional runs, "Social Tension" was observed to drop prematurely, indicating that agents clustered around local peaks too early. This loss of diversity prevented the population from discovering the global optimum. Furthermore, while landscape complexity (static vs. chaotic) was a major factor in 3D, by 5D, the sheer volume of the search space became the dominant hurdle, making specific landscape characteristics less influential.

The Social Bottleneck

The study concludes that a static, homogeneous social network (the square grid) acts as a bottleneck in high dimensions. Such a structure lacks the flexibility required to effectively distribute innovations across the population as the search space grows.

Conclusion

This research demonstrates that while Cultural Algorithms are effective for low-dimensional optimization, their performance is constrained by the social fabric as dimensionality increases. A homogeneous social fabric is sufficient for 2D problems but falls off quickly thereafter. Future work should focus on developing dynamic heterogeneous topologies and more nuanced social metrics to maintain population diversity and improve the scalability of CAs for high-dimensional global optimization.

Summary updated

Abstract

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.
BibTeX
@inproceedings{yang2015impact,
  author = {Yang Yang},
  title = {{The impact of increased optimization problem dimensionality on cultural algorithm performance}},
  booktitle = {DigitalCommons},
  year = {2015},
}
Figure