It was just a toy problem, but it produced some nice looking images. It was Misha Paauw, considered by some to be the Polygon Prophet, who truly scientificalized the problem. “It’s a non-trivial optimization problem” says Arne Meijs, master student AI, “and a great testing ground for heuristic algorithms, especially since it’s so visible.”

An earlier study on paintings-from-polygons did exactly that: test heuristic algorithms. Plant propagation did well, it always does. Hillclimbing did well. But simulated annealing failed miserably. “The suspicion was that the high value of the temperature parameter within the algorithm ruined the results” says Sven Boogmans, master student Information Studies.

Cooling schedules

In a follow up study, Redouane Dahmani tried nine new parameterizations (“cooling schedules”) for the simulated annealing algorithm [2]. This time it worked, and the results were much better. “Mostly, it just depends on the average temperature” says Redouane, “From literature, similar effects are known for other problems. But in this case, the performance can be functionally mapped to the average temperature.”

Outliers

Yet, this is not the end of the story. “Even though the average temperature is a solid predictor for performance, some very fierce feedback at the time of presentation showed us that our findings cannot be correct for all possible cooling schedules. And then there’s the outliers: two of the schedules perform significantly better than seven others. We have no idea what’s going on there, but we’re dying to find out. We need to take things pedestrianally in untangling this little mystery.”

The paper is the latest in a series of publications by UvA students  on Paintings-from-polygons and the plant propagation algorithm [1]-[8]. The International Conference on Computational Creativity, originally set for Coimbra Portugal, was held completely online due to Covid-19.

References:

[1] “Paintings, Polygons and Plant Propagation”, M. Paauw, D. van den Berg, International Conference on Computational Intelligence in Music, Sound, Art and Design 2019.

[2] “Paintings-from-Polygons: Simulated Annealing”, R. Dahmani, S. Boogmans, A. Meijs, D. van den Berg, 11th International Conference on Computational Creativity, ICCC'20.

[3] “Simplified Paintings-from-Polygons is NP-Hard”, D. van den Berg, Evo* 2020, 2020, 15.

[4] “Fireworks Algorithm versus Plant Propagation Algorithm”, W. Vrielink, W., & D. van den Berg, In IJCCI 2019 (pp. 101-112).

[5] “Plant Propagation & Hard Hamiltonian Graphs“, Sleegers, J., & D. van den Berg, Evo* 2020, 10.

[6] “Plant Propagation Parameterization: Offspring & Population Size”, M. de Jonge, & D. van den Berg, Evo* 2020, 19.

[7] “Looking for the Hardest Hamiltonian Cycle Problem Instances”, Sleegers, J., & D. van den Berg, IJCCI 2020: Proceedings of the 12th International Joint Conference on Computational Intelligence.

[8] “Parameter Sensitivity Patterns in the Plant Propagation Algorithm” , M. de Jonge, & D. van den Berg, IJCCI 2020: Proceedings of the 12th International Joint Conference on Computational Intelligence.