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