8
$\begingroup$

I posted this question earlier on stackoverflow, where it was closed as off-topic. I hope it survives here.

I our climbing gym, the routes need to be re-set from time to time. The following rules apply:

  • We have climbing holds with a number of different colors in varying quantities. - When a route is set in a sector, no other route with the same color must be set in that sector or in the nearby sectors to avoid confusion.
  • Some color combinations must be avoided in a sector, like white/gray or red/pink.
  • The goal is to have four routes in each sector, less is ok if four would break the above rules.

I have tried two different approaches by now. The first one was Simulated Annealing where I initialized the wall with a random pattern of colors (but with a given color weight) and computed a badness for each color combination. This badness was also computed for combinations between one sector and its neighbours. In each iteration a randomly chosen route from the worst sector was swapped with a route from a randomly chosen other sector. This showed some sort of convergence, but the result was not usable (i.e. the resulting state contained sectors with double or triple colors).

I then approached the problem from the opposite side and started with an empty wall. This time, every color had a concentration which decayed from one sector to the adjacent sectors. The concentration of similar colors was also increased, i.e. a red route increased the concentration of orange in a sector and nearby. A weighted random source of colors (the bucket) gave me the next color for the wall, which was placed at the sector with the lowest concentration of this color. If a concentration was above a certain threshold, the color was not added (but put back into the bucket). This was a partial success because the result state did not contain any double colors - but some sectors were empty or contained only one color.

So: What could be an appropriate algorithm for solving this problem, given the above rules? I'll happily add more information when required.

Edit 1 - More information:

  • my test case has 15 sectors,
  • each sector should contain 4 routes
  • the real gym has 3 buildings with an average of 50 sectors each
  • some sectors are arranged around pillars, some are connected by roofs
  • we have about 10 different hold colors
  • the height of the sectors varies between 6 (beginner's section) and 20 meters (13 vertical + 7 roof), so they consume different amounts of holds. However, the average is about 12 and this can be considered constant.
  • there is a limited amount of each color, the amounts are not equal
  • some colors are easier, some more difficult (i. e. we can create a yellow route of any difficulty, whereas creating a very easy orange route for kids will be almost impossible)
  • some sectors are "easier", so easy colors should go there (this is optional, our route setters can make things harder or easier within a wide range).
  • we can safely say which colors go well together in a sector or in neighbouring sectors and which combinations don't. There are some surprises, such as white and black (bad combo): both turn to gray while rubber (shoes) or chalk (hands) is left on them.
  • some hold colors are combinations like violet/white (in a stripey pattern).

Edit 2: Some Questions about Genetic Algorithms

I now downloaded and compiled ParadisEO and even got my IDE (I'm using Code::Blocks) to compile the QuickStart example. ParadisEO offers genetic algorithms with a single objective as well as multi-objective GA. GertVdE suggested to calculate the fitness of each sector and to maximize the sum of all sectors' fitnesses as a single objective. Could I also maximize the fitness of each sector with a multi-objective GA? That would be some 50 objectives.

Also, I'm struggling with the definition of a sensible crossover function. As the maximum amount of each color is fixed, crossing can lead to illegal states. If I allow more than the previously given maximum amount, the overall pattern might converge to a repitition of less "toublesome" combinations where the troublesome colors have been thrown out. On the other hand I can also throw out excess colors until the maximum is reached, making the crossover function non-conservative.

(I am completely new to genetic algorithms)

Improve this question
$\endgroup$
7
  • $\begingroup$ @Christophe Shouldn't you add a restriction on the minimal/maximal distance between two holds in a route? $\endgroup$
    – GertVdE
    Feb 4, 2013 at 10:27
  • $\begingroup$ Currently I only want to decide which colors go where. What hold sizes, shapes and the distance between holds are actually set in a route depends on the desired route grade (difficulty) and the route setter's personal style. $\endgroup$
    – Christoph
    Feb 4, 2013 at 10:34
  • $\begingroup$ @Christophe: ok. but the problem is still too vague: how many different colors do you have? how many sectors do you need to fill? If you ignore the "quality" of the different routes as you mentioned before, do you want to take into account the total amount of holds you have available in each color and the average number of holds per route (or the exact amount, if you know). If not, you must assume you have an infinite amount of each color. $\endgroup$
    – GertVdE
    Feb 4, 2013 at 11:02
  • $\begingroup$ In every climbing gym that I've been in, the holds for a particular route are marked on the wall adjacent to the hold with colored tape---the color is particular to the route. This gives the route setter the freedom to choose from all the holds without regard to their color. Are you sacrificing route quality for a color aesthetic? $\endgroup$
    – Glenn
    Feb 6, 2013 at 5:59
  • $\begingroup$ @Glenn: Well, where were you? There might be local ways of handling this. In our climbing gym (and, in fact, all those I've been to) the routes are marked by hold colors (this is in Hamburg and around). Tape tends to fall off and is sometimes barely visible from 13 meters below. We have enough holds for the route setters to choose from and until now we never had the feeling that we were sacrificing route quality. $\endgroup$
    – Christoph
    Feb 6, 2013 at 9:11

2 Answers 2

Reset to default
2
$\begingroup$

I would solve the problem stated above using a genetic algorithm approach. You code each solution as a vector of integers:

  • Assume a maximal amount of routes per sector as M (you choose); assume N sectors
  • Create a coding vector of size M*N where each segment represents a sector and each item in the segment represents a route
  • Assign colors by integer value, the index; use 0 as no route (to allow for less routes than M)
  • For each color index, have the RGB values

Then you define a fitness function as a weighted sum of the minimal color difference in each sector and the amount of routes in a sector (the amount of zeros in the vector). You can use the Paradiseo framework or Inspyred for an implementation of Genetic Algorithms.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I have no experience in python, so I'll try Paradiseo. I also have Matlab at work so I could dedicate some extra hours to this. A generic color difference function will not work (see added information), but I can come up with a fitness function that takes into account the routes in a sector and all routes around. $\endgroup$
    – Christoph
    Feb 4, 2013 at 12:17
  • $\begingroup$ For Matlab (or Octave), you can use this GA package $\endgroup$
    – GertVdE
    Feb 4, 2013 at 12:42
  • $\begingroup$ I'll see if I can start with Paradiseo (C++ will be easier to extend when I have a good algorithm and want to add a UI or other things). If that is too hard, I'll fall back to Matlab. Matlab's global optimization toolbox should also work, shouldn't it? It includes genetic algorithms. $\endgroup$
    – Christoph
    Feb 4, 2013 at 12:54
  • 1
    $\begingroup$ Let me add a trivial remark: since permuting colors in the same route will not change the fitness function, you can create a table of all "n choose k" possible color combinations for a single sector, and store instead of a color vector a index to a row in this table. By doing so, given two routes, the color compatibility computations reduce to a simple lookup into a small triangular matrix (the diag being the merit of the color combination per se.) $\endgroup$
    – Stefano M
    Feb 4, 2013 at 15:50
  • 1
    $\begingroup$ I would accept this answer because I was able to implement a GA for this problem with ParadisEO in two days. It is still work in progress, but it seems to run fine and I'll have to refine some things. Is it appropriate to post some details of my implementation as an extra answer? $\endgroup$
    – Christoph
    Feb 10, 2013 at 23:02
0
$\begingroup$

Here is a brief overview of my current implementation, I'll try to stick to the concepts and not go into language details. I used the ParadisEO Framework which is C++ template library for genetic algorithms and added some boost here and there.

Climbing hold colors

The hold colors are stored in an XML file as a pair of color name and amount. The amounts found in a file are added up and normalized. This makes it possible to express an amount as either a total count of routes that can be set with this color or as a percentage. An ID is assigned to each color, starting with 1. Zero is reserved for an "empty" route.

Color Combination Penalties

Some colors don't go well together in one sector or in adjacent sectors. Every not-so-good color combination is described by the two color names (as in the previous XML file, see above) and an arbitrary "badness". Internally, the badness values are stored in a matrix which is indexed by color IDs.

The Wall

The Wall is a class that derives from ParadisEO's genome representation class so that ParadisEO can manipulate and evaluate it, but some more functionality is added. Each gene represents one route color by ID (including zero, or empty). Sectors are represented by a pair of indices to the genes, so that each sector has a beginning and an end. I used iterators to the genes first, but the Wall object has to be copy constructible, which would invalidate iterators without additional work. Currently, all sectors have 4 routes, but that will be configurable in the future.

The Wall also has a color bucket. This bucket contains a counter for each color, distributed as described in the color XML file. The color counts add up to the total number of routes in the Wall. A color can be picked from the bucket, decreasing the counter, and it can also be put back, increasing the counter.

A color can only be added to a sector if the sector doesn't already contain that color (the sector must remain "legal" when the color is added).

Evaluation Operator

The evaluation operator sums up all badness values in a sector using the badness matrix described above. Each sector's value is stored in the fitness vector (that's also part of the Wall class), so this is a multi-objective GA. I might change that if it becomes necessary.

Two Point Crossover Operator

The crossover operator takes two parents, creates a copy of each (the offsprings) and then performs a two-point crossover by recombining whole sectors. The advantage of this is that sectors remain legal (no double colors). The disadvantage of any crossover operation (for this problem) is that the resulting offsprings can contain excess colors if colors were clustered in the parents. A repair function was added that removes excess routes (color zero) randomly. The offsprings therefore have less routes than the parents of the repair changed the offspring.

Mutation 1: Add route

The potential decrease in routes in the offsprings is accounted for by an "add route" operator. It takes a color from the Wall's bucket and adds it somewhere. If that's not a legal operation, it does nothing (sometimes there is no legal place for a remaining color).

Mutation 2: Random exchange

Two random routes of two random sectors are swapped. This pair of swapping is generated until the resulting sectors are legal, then the swap is executed.

Mutation 3: Shift

A number of sectors is shifted one place to the left.

I'm out of time now, but I might add more information later. Especially the evaluation is quite simple as it is, and the components were programmed as a proof of conecpt. The GA indeed does optimize the Wall to some extent, but the results are not ready for real use. I'm sure this will improve when I've talked to the route setters and more rules for evaluation are available. Pictures will also come when they are available.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.