Cultural Algorithm (CA) in MATLAB

This package is a MATLAB implementation of the Cultural Algorithm (CA), a metaheuristic based on social evolution. In CA, a population of individuals evolves together with a shared body of knowledge called the culture. The Cultural Algorithm was introduced by Robert G. Reynolds in 1994.

How the Cultural Algorithm works

CA has two levels. The population space holds the individuals, which are candidate solutions. The belief space holds the culture, the knowledge that the population has gathered so far. The two levels talk to each other in every iteration:

1. Acceptance. An acceptance function chooses which individuals may add to the culture. In this code, these are the best individuals of the population.
2. Adjustment. The accepted individuals update the belief space.
3. Influence. The culture guides how every individual changes in the next iteration.

So the culture works like a shared memory. Good experience from one generation is stored in it and passed on to the next.

The culture in this code

In this code, the culture has two parts: situational knowledge (the best solution found) and normative knowledge (an interval for each variable, built from the accepted individuals).

The normative interval of variable $j$ has a lower end $l_j$ and an upper end $u_j$, and each end remembers the cost of the individual that set it. An accepted individual moves an end when it lies outside the interval, or when its cost is lower than the stored cost of that end. The width of the interval is $s_j = u_j - l_j$.

The code has four ways to let the culture influence the population. Three of them are commented out. The active one uses both parts of the culture. Each variable of each individual takes a Gaussian step with a standard deviation of $\alpha\, s_j$, and the direction of the step points toward the best solution:

where $b_j$ is variable $j$ of the situational knowledge. If $x_j$ already equals $b_j$, the code keeps the random sign of the step. As the accepted individuals gather in a smaller region, the intervals shrink, and the steps get smaller.

The example and its settings

The example minimizes the Sphere function with 10 variables in the range from $-10$ to $10$, using a population of 50 and 1000 iterations. The acceptance ratio pAccept is 0.35, so the best round(0.35*50), which is 18, individuals adjust the culture in each iteration. The step coefficient alpha is 0.3. The parameter beta (0.5) is used only by the fourth influence method, which is commented out.

What is in the download

• main.m: starts the example by calling ca
• ca.m: the main algorithm, with its settings
• AdjustCulture.m: updates the culture from the accepted individuals
• Sphere.m: the cost function
• LICENSE and README.md

To try it, run main.m in MATLAB. The files are in the Cultural Algorithm folder of the download. The program prints the best cost of every iteration and then plots the best cost against the iteration number on a logarithmic scale.

The script creates the first population with unifrnd, a function of the Statistics and Machine Learning Toolbox, so it probably needs that toolbox.

To solve your own problem, write a cost function that takes a row vector and returns a number, and set CostFunction, nVar, VarMin and VarMax at the top of ca.m. To try another influence method, uncomment its block in the main loop of ca.m and comment out the active one.

Check the result

For the Sphere example, compare the best coordinates with the origin and the cost with the known minimum of 0. The normative intervals control the scale of new steps, so a narrow interval can reduce exploration. When experimenting with the commented influence methods, keep only the intended method active and record which one produced the result. Repeat runs before drawing conclusions about the acceptance ratio or step coefficient.

Related posts

• YPEA is a MATLAB toolbox that includes CA and 14 other algorithms that share one problem definition.
• Imperialist Competitive Algorithm in MATLAB is another metaheuristic inspired by human society.

Mostapha Kalami Heris, Cultural Algorithm (CA) in MATLAB (YPEA125), Yarpiz, 2015. https://yarpiz.com/cultural-algorithm-ypea125

@misc{yarpiz-ypea125,
  author = {{Mostapha Kalami Heris}},
  title = {{Cultural Algorithm (CA) in MATLAB}},
  howpublished = {Yarpiz},
  year = {2015},
  note = {Code YPEA125},
  url = {https://yarpiz.com/cultural-algorithm-ypea125}
}