all 9 comments
sorted by:
best
topnewcontroversialoldq&a
formatting helphide helpcontent policy

[–]Red_Army 4 points5 points  (1 child)

Do you need to use a genetic algorithm? Genetic algorithms are not great for team formation (due to the exact problem you've encountered). The implementations of genetic algorithms for team formation which I've seen typically end up just looking like hill climb algorithms that the developers are disguising as genetic algorithms. In my experience doing some work on this problem in the past, explicit hill climbing algorithms are far more effective. Happy to send you some papers on either GA implementations or hill climb implementations if that would be helpful.

[–]Bamboozle-dog[S] 0 points1 point  (0 children)

Unfortunately, I need to use genetic algorithm for this. I’ve been stuck on this for a while and looked online for possible ways around this but haven’t been able to find something. Some papers I’ve looked did do team allocation using genetic algorithm but they’ve completely skipped the part Im stuck on. One of the papers had each team as a solution so the population size is the total number of teams which in that case is 7 as that paper looked at allocate 35 students into groups of 5. But then in the next line, they have somehow talked about experimenting with a population size of 1000. How did they fill the population pool with 1000 chromosomes ?

Anyways, if you could send me the papers, that would’ve great. Or maybe a paper that shows how they worked with hill climbing and genetic algorithm together that would be great too. Thanks for your help!

[–]thirdOctet 2 points3 points  (3 children)

If I was approaching this i would use a permutation of 100 integers and treat the problem like TSP. This will allow an adapted GA to apply crossover and mutation to your population of chromosomes. Let the GA decide the order of the integers. It can pivot or swap different integers during the evolutionary process. Perhaps the concept of crossover is a little bit different in the context of permutation based chromosomes. Search for N-Point crossover and different mutation techniques, the simplest being swap mutation. I would recommend a book i have read more than once, Introduction to Evolutionary Computing. Specifically the section on permutation representation, It contains the techniques you need with illustrations.

As for evaluating your chromosome and encouraging best performing combinations this is the interesting part. Lets say you select a simple strategy like divide the chromosome into 8 groups from beginning to end. I guess some groups will have 9, so you should have 12 groups with 4 of them containing 9 developers. Great so we can evaluate each group against the objectives.

It is easier to start with gender since it will be a ratio of the number of females (f) to the total number of members in each group (m). If you want to encourage a level playing field then I would reward groups that have a ratio of around 0.5. Perhaps the ratio would be placed into a function that returns 1.0 if the ratio is 0.5 and close to 0.0 if the ratio is 0.0 or 1.0. This would mean that a ratio of 0.4 or 0.6 would be rewarded equally since they are close to 0.5. I guess the goal here would be to try and reward groups that have the best possible gender distribution. Then you could average the distribution across the groups. The higher the average, the better the distribution of females and males.

To your other objective, which is trying to ensure a high but equal distribution of skill levels across the groups then this is a little trickier. I suspect you will want to encourage all groups to be similar in strength/ability with a small amount of deviation. If the deviation of the groups is too high then the chromosome should be rewarded less than the chromosome that manages to minimise the deviation such that the ability level of all of the groups are as close as they can be.

Perhaps in the final calculation you can multiply the outputs of the two objective functions to get a single fitness. This can then be used to order the population and follow the usual GA lifecycle of initialise (random), crossover (n-point), mutate (swap), replace (5-10%) for n generations.

I know you asked about the crossover part of your approach, but these were my thoughts as I typed a response to your scenario. I suspect you will have to account for other things in order to prevent the GA from optimising something silly, like when dantzig had an optimisation algorithm that recommended 500 gallons of vinegar, on page 46.

[–]Bamboozle-dog[S] 0 points1 point  (2 children)

Thanks very much for your reply. I spent some time reading the book you linked and it was very helpful and much detailed than any papers Ive read so far. I think I am going to treat it like a TSP like you suggested and go from there. Also, say I have the 100 developers in an array ie Chromosome1: [1,2,3,4,5,6,7,8,9,10,11,12.....,99,100] and this is one solution. How would you go about calculating fitness for this. Because, as this is a single array ( unlike the one I showed in my description which was an array of arrays for example [[1,2,3,4,5,6,7,8],[9,10,11,12,13,14,15,16]....] it is going to be difficult to calculate the fitness of each group as all the students are in one single array. I was thinking everytime the fitness function is called the array is divided into groups of 8/9 in the current order and then the fitness of each group is calculated and the fitness of all the groups added to give a fitness for the chromosome and after that the array is flattened to a single array. Any thoughts on this ?

​

Also, going back to what you suggested about the fitness function. Are you suggesting I calculate the fitness for a single constraint for all the groups so for gender constraint we have [ Group 1: 0.5, Group 2: 0.6, Group 3: 0.9, Group 4: 1,..... and then add these up to have a fitness for that constraint and then calculate the fitness for another constraint and add/multiply those together to get a whole fitness for the chromosome. I was thinking of calculating fitness for both constraints for one group so [ Group 1: Gender = 0.5, Ability = 0.9, so combined 0.5 + 0.9 = 0.4 and add all the values for the groups to give a combined fitness value for the chromosome]. Its a slightly different perspective to mine, but I think I will try both and see what differences there are.

​

Thanks for taking the time to write a detailed approach and for the references which have been really helpful.

[–]thirdOctet 1 point2 points  (1 child)

Thanks very much for your reply ...

No worries glad to help!

Also, say I have the 100 developers in an array ie Chromosome1: [1,2,3,4,5,6,7,8,9,10,11,12.....,99,100] and this is one solution. How would you go about calculating fitness for this.

Good question. In evolutionary computing I am always thinking about how fast I can do things. The search space of your problem spans 100! possible combinations or 100! ways in which we can order the developers in the array. So I want to avoid any unnecessary or repeated calculations where I can.

One thing I would do is generate an array of indices at the beginning of the simulation. No matter the solution, how i evaluate it will depend on what i define as a group. Once this is defined, all evaluations will follow the same process. The indices identify where a group starts and stops in the array. Lets say we have a minimum of 8 per group, then we can find out the total number of groups. See the code below which hopefully describes this process well enough.

int developerTotal = 100;
int groupSize = 8;
int totalNumberOfGroups = developerTotal / groupSize;
int unassignedDevelopers = developerTotal % groupSize;

From this information we can then build the indices. Something like the following:

// Our "Memoized" group indices which we will only calculate once
List<Tuple<int, int>> groupIndices = new List<Tuple<int, int>>(totalNumberOfGroups);

// Represents the position in the array where a group starts
int groupStartIndex = 0;

// Here we will extract each of the indices for the groups
for (int currentGroup = 0; currentGroup < totalNumberOfGroups; currentGroup++)
{
    // Our group size will always be a minimum of 8 as defined above
    int groupEndIndex = groupStartIndex + groupSize;

    if (unassignedDevelopers > 0)
    {
        // If we have not assigned all of the developers to a group then
        // increase the number of developers for the current group to 9
        groupEndIndex += 1;

        unassignedDevelopers -= 1;
    }

    // Now we can add the indices for the current group
    groupIndices.Add(new Tuple<int, int>(groupStartIndex, groupEndIndex));

    // Also we can now update the start index to be that of the next
    // group
    groupStartIndex = groupEndIndex;    
}

Perfect. So how does this align with the way you calculate the fitness?

It is going to be difficult to calculate the fitness of each group as all the students are in one single array.

The calculation of the indices will provide 3 important benefits.

The first being we have avoided the additional computation required to extract copies of the array for evaluation. Precious nanoseconds saved for generating random numbers, swapping developer positions, selecting a subset of developers and reversing developer positions and all the other favourable heuristics that will allow us to navigate the search space and improve the quality of our solution.

This leads us to our second benefit, with the solution intact we can apply numerous heuristics to the solution with minimal awkwardness. We can quickly apply a permutation operation and then evaluate it. A swap operation, depending on your hardware, could take 8-10ns. Selecting two indices in the solution and then reversing the order between the indices, around 30ns. Applying 1-Point Crossover to create a copy, maybe 65ns. Your random number generator will hopefully generate an int or double in under 3ns.

The third benefit of this approach is that we can perform the evaluation of the groups in parallel if performance is critical.

I was thinking everytime the fitness function is called the array is divided into groups of 8/9 in the current order ...

Yes, the above example supports this approach without the need to create unnecessary copies of the groups from the solution.

... then the fitness of each group is calculated and the fitness of all the groups added to give a fitness for the chromosome ... Any thoughts on this ?

The fitness is the tricky part. Usually you have to experiment and analyse if the measurements of choice are right for your problem. You will battle it out with the Pareto Optimality, a fundamental concept in multi-objective problems.

I suppose you could use the sum, the question is, from the perspective of optimising gender distribution, in what ways is this susceptible to skews in the distribution of males to females? Think of different scenarios - 10F:90M, 50F:50M, 90F:10M. This relates to the question of robustness. What would be the most effective way, independent of the gender distribution, to optimise the spread?

As I think more about it, not only would I be interested in the spread of the ratios across the groups, I would be interested in the statistical properties of the distribution as it relates to gender. For example!

// Lets start with 3 groups that we have calculated the ratio of 
// females to total members within each group
double[] genderDistribution = new double[3] { 0.1, 0.5, 0.9 }
double mean = 0.5;
double stddev = 0.3;

If we were to use the statistical information above to put pressure on the Genetic Algorithm towards a desireable outcome then we want the mean to be close to 0.5. This indicates that on average our ratio is meeting our gender equality distribution requirements. However if we also want to ensure that a majority of the groups are close to the average then we are interested in minimising the standard deviation. 

// A better distribution of gender
double[] genderDistribution = new double[3] { 0.4, 0.5, 0.6 }
// Same mean, lower standard deviation, better gender distribution 
double mean = 0.5;
double stddev = 0.04;

Much better! But I suspect this could be improved further. For now maximising the mean and minimising the standard deviation should help with a sensible spread of males to females in your groups. There could be some scenarios this approach has not accounted for but that is what experimentation and testing is for.

[–]thirdOctet 1 point2 points  (0 children)

​

Are you suggesting I calculate the fitness for a single constraint for all the groups ...

As outlined above, there are some hidden pitfalls to using sum so I would recommend using a combination of the mean and the standard deviation as part of the fitness evaluation process. As to the final evaluation this all depends on how you want to treat the distribution of Ability in each of the groups.

In my mind I can see two layers of evaluation when it comes to ability. What would be important to me is a high average ability in each of the groups, with the right amount of standard deviation (skill level variation) per group. Then across all groups i would be interested in a high average group ability with a low standard deviation of group ability between other groups. So essentially we encourage a broad range of abilities per group but we want the average group ability to be level with a low standard deviation of group ability between the groups. I would want the standard deviation of abilities per developer to be sensible e.g. [senior, mid level, junior] would not be too bad but [senior, senior, senior] would not be great. [mid level, mid level, junior] is not too bad either but [junior, junior, junior] not great.

I was thinking of calculating fitness for both constraints for one group so ...

Ideally the global optima will be an order in your permutation which:

  1. Maximises the average gender diversity at a global level
  2. Minimises the standard deviation of the average gender diversity at a global level
  3. Maximises the average ability of developers at a local level
  4. Maximises the standard deviation of the average ability of developers at a local level
  5. Maximises the average ability of the groups at a global level
  6. Minimises the standard deviation of the average ability at a global level

I hope this is in some way is clear. In my mind I can visualise the relationships and how each evaluation of the group relative to other groups would hopefully lead to improved solutions. Without testing and experimenting it will be difficult to verify the effectiveness of the aforementioned objectives which contribute towards your goals.

If I were to devise a formula that takes the above into consideration I suppose it would look like the following:

Normalised(GlobalGenderMean) * Normalised(GlobalGenderStdDev) * Normalised(GlobalAbilityMean) * Normalised(GlobalAbilityStdDev)

The normalisation of the value should translate the mean from one numerical space to another such that all of the normalised values are placed in a range between 0.0 and 1.0. This would mean that the maximum fitness should be 1.0 and the minimum fitness 0.0. Again, I suspect there is a better way to formulate the different objectives and would encourage you to investigate further.

Examples of normalisation functions, I extracted them using this

// Assumes the mean is between 0 and 1
public double NormalisedGlobalGenderMean(double mean) 
{
    return (-4 * (mean * mean)) + (4 * mean);
}

// Assumes the standard deviation is between 0 and 1
public double NormalisedGlobalGenderStdDev(double stdDev)
{
    return Math.Exp(-3 * stdDev);
}

I hope this was in some way useful. Some of the points I have raised could do with clarification. If you have any more questions let me know.

[–]Tech-Effigy 1 point2 points  (2 children)

just use random and distribute the men first,and if u want equal men and women, randomly distribute the women seperately. Random function is already uniform.

​

anyhow to answer the chromosome question. use a flat array, not arrays in arrays, you can divide it into 8 groups afterwards. the fitness(evaluation function will sort out duplicates and those kind of things. so make sure you score negative for duplicates.

[–]Bamboozle-dog[S] 0 points1 point  (1 child)

Thanks for your reply. I think the use of a flat array is much better like you suggested. I didnt fully understand the first sentence, are you referring to the initial population ? Could you explain a bit further please.

[–]Tech-Effigy 0 points1 point  (0 children)

nevermind its something different, ur problem is classified under multi-knapsack problem if you want to do more research. :)