CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 20
  1. #1
    Join Date
    Nov 2014
    Posts
    7

    Genetic Algorithm idea or alternative

    Hello, I've been given a requirement, it's similar to a GA but I dont find the correct way to do it in a GA way or if there is some kind of optimization algorithm to solve it better.

    Take a tipical GA optimization problem. We have M people (p1,...pm) and N task (t1,...tn) we have a 2x2 matrix of how perform each people in each task, we can code the chromosome of the GA as an N-size array so each position is who is assigned to this task, for example with 3 task if we have {p3,p1,p5} means person 3 is in charge of task 1, person 1 of task 2, etc.
    Then we can have the population of chromosomes, iterate, mutation, selection, etc...

    Ok, but the problem is not exactly this (the classical optimization problem I've read and coded works perfectly)

    The problem changes so we want a solution like "give me the best 2 people for task 1, and the best 3 people for task 5" (and we have some other objectives like we've to penalize people far (location) from task, but we can ignore this, at the moment)
    Another requeriment is that we want a pool of different good solutions so the user can choose which one he prefers, this is one of the reasons we tried with a Genetic Algorithm approach...

    Of course the simply brute-force solution to find the 2 better from task 1 and then the 3 best from task 5 did not work because some of the best for solution 3 could be choosen in task 1 etc in my previuous example and of course we dont have a pool of different good and different solutions...


    So my question is how can we code the chromosome to work with it and be a solution for the problem "find 2 for task 1 and 2 for task 3..." or find a better alternative, wich kind of algorithm I've to search and study for this problem...

    Regards.

  2. #2
    Join Date
    Nov 2014
    Posts
    7

    Re: Genetic Algorithm idea or alternative

    I've though a possible chromosome representation, chaining tasks, I mean in the example "give me the best 2 people for task 1, and the best 3 people for task 5" the chromosome will be {people in task 1 + people in task 2}, for example with 5 person, and task 1 and 3 a example chromochromosome could be {{0,0,1,1,0}{1,1,0,0,0}} that means for task 1 we choose person 3 and 4 and for task 3 person 1 and 2 (if we want to code all task chromososme could be {{0,0,1,1,0}{0,0,0,0,0}{1,1,0,0,0}} the same with task 2 with zero workers...

    A little tricky for selection/mutation part of the GA but it can work.

    If somebody think there is a better chromosome alternative let me know and specially if somebody know which optimization algorithm different to GA is best suited for this problem let me know so I can study it...

    Regards.

  3. #3
    Join Date
    Jul 2013
    Posts
    576

    Re: Genetic Algorithm idea or alternative

    Why don't you start by presenting the actual problem.

    Okay you have M people and N tasks but then what?

  4. #4
    Join Date
    Nov 2014
    Posts
    7

    Re: Genetic Algorithm idea or alternative

    I though the problem was presented first with a typical problem and after that what changes, but perhaps I did not explain it correctly.

    The problem.
    We have N task and M people that have competence in each task.
    We're asked for a set of people that maximices the question "i need a number of people for task i and another number for task j etc..." for example I need 2 people for task 3, one for task 1, 4 for task 6 and nobody for the rest of tasks.
    And if possible dont give me only the best solution, but a set of near-optimal solutions so I can choose the best from my (user) subjective point of view...

    I hope this definition is more clear, my apologizes if the first one was not clear and sorry for my bad English.

    Regards

  5. #5
    Join Date
    Jul 2013
    Posts
    576

    Re: Genetic Algorithm idea or alternative

    Quote Originally Posted by z80z80 View Post
    The problem.
    We have N task and M people that have competence in each task.
    We're asked for a set of people that maximices the question "i need a number of people for task i and another number for task j etc..." for example I need 2 people for task 3, one for task 1, 4 for task 6 and nobody for the rest of tasks.
    So each person can perform any task. It's not that some people are better at certain tasks (according to some measure of skill level)?

    Say there are lots of people (M is very big). Then there is nothing to optimize really. It's just to assign all people that's needed to all tasks.

    But say there's a shortage of people (M isn't big enough). I would assume that you then would try to find the lowest cost distribution of available people to the tasks. The question is, how do you measure the cost (of tasks being short of people)?
    Last edited by razzle; November 12th, 2014 at 09:12 AM.

  6. #6
    Join Date
    Nov 2014
    Posts
    7

    Re: Genetic Algorithm idea or alternative

    Quote Originally Posted by razzle View Post
    Say there are lots of people (M is very big). Then there is nothing to optimize really. It's just to assign all people that's needed to all tasks.

    But say there's a shortage of people (M isn't big enough). I would assume that you then would try to find the lowest cost distribution of available people to the tasks. The question is, how do you measure the cost (of tasks being short of people)?
    I think is some kind of optimization problem (but I've no idea about optimization algorithms)
    Each person has a score in each task, but is not as easy as take the highest on task 1 then the highest on task 2 etc...
    As example Bob has {10,7,7,0,9} And Alice {8,4,3,8,1} If we take Bob for task one, then for task 2 we have only Alice, total score 10+4=14, but if we Take Alice for task 1 and Bob for 2, we have 8+7=15.
    And we're not asked to find the best for each task we have to ask questions like "find me a good solution for 2 people doing task 1, 0 for task 2 and 4 for task 3"

    With Genetic Algorithms, we'll get a good or local optimal solution, and if we run the algorithm again we'll find possibly a different solution.

    This feature to get different good solutions is desirable, we have to present user with some options, in our example the solution with overall score 15 is better but perhaps the user prefer another with a slighly lower score

    I have some limited understanding on genetic algorithms so this is the reason I tried to planify the solution like a genetic algorithm, but perhaps I can find find optimal solutions for such problem there should be some optimization algorithms or something similar, better than my approach but I dont know even their name or where to find information about them.

    That why I'm asking info on related algorithms suited for this problem or perhaps a better Genetic Algorithm approach (for example coding in a better way the chromosome that is a representation of a individual in a Genetic Algorithm, etc...)

    About your question about how to measure cost, I've the score data.
    For example:
    .............Bob....Alice....Razzle....Peter
    C++.........5........6..........8..........9
    Java.........9.........8..........7.........8
    C#...........7.........5..........7.........2
    Algorithms.4.........6.........10.........8
    And the user ask "find me 2 good C++ programmers and 2 good Algorithms designers"

    And we can assume there are more people that requested, if we request for N people in total for different tasks, total number of people is N or more. (usually many more... but never less that number of requested people)
    Last edited by z80z80; November 12th, 2014 at 10:50 AM.

  7. #7
    Join Date
    Feb 2013
    Posts
    58

    Re: Genetic Algorithm idea or alternative

    such problem has no clear optimization per se. Ye Just may run db w/ scores of each employee & h(is/er) current task + each task must be rated too, for capability to re-flow resources from low-important tasks . By the way, personal scores cannot be very informative: you need to take into account social collisions between employees. F.e., you choose two high-ranked programmers, but they hate each other & all their collaboration falls apart each time.

  8. #8
    Join Date
    Nov 2014
    Posts
    7

    Re: Genetic Algorithm idea or alternative

    What do you mean with "run db with scores"?

    And yes personal scores are subjective are not very informative, not only social collisions but is a subjective measure, but these are the requeriments... (the programmers sample is not the real one but would be similar)
    I think the "subjective measurement" would be the failure point at the end and not if I can find the "optimization algorithm" but I've to solve only the "technical part"...

  9. #9
    Join Date
    Jul 2013
    Posts
    576

    Re: Genetic Algorithm idea or alternative

    Quote Originally Posted by z80z80 View Post
    As example Bob has {10,7,7,0,9} And Alice {8,4,3,8,1} If we take Bob for task one, then for task 2 we have only Alice, total score 10+4=14, but if we Take Alice for task 1 and Bob for 2, we have 8+7=15.
    And we're not asked to find the best for each task we have to ask questions like "find me a good solution for 2 people doing task 1, 0 for task 2 and 4 for task 3"
    Okay, as far as I can see the closest standard problem to your problem is the Generalized Assignment Problem (GAP).

    http://en.wikipedia.org/wiki/General...gnment_problem

    GAP is NP-complete and there should be both exact and approximation algorithms available in the form of off-the-shelf packages you could use. But developing your own GA may still make sense because it will be easier to bend and stretch if you need to go beyond the standard GAP formulation.

    I've found a research paper where GA is used to tackle GAP. Even though it solves the exact GAP problem you may learn something you can apply to your own maybe somewhat modified GAP (the GAP formulation is at 2.1),

    http://www.lac.inpe.br/~lorena/gap/cga_revised.pdf

    ---

    Comments to the links I supplied:

    1. Wikipedia has a maximize profit formulation whereas the paper has a minimize cost formulation. pij holds what you refer to as "score data" and that's a kind of profit but it can easily be turned into cost (by just negating all "scores"). These formulations are equivalent.

    2. What Wikipedia calls wi and the paper calls ci is the number of programmers assigned to task i.

    3. The weight matrix called wij (in both Wikipedia and the paper) has 1 in all positions in your case so basically it can be removed. It's because programmers in your case don't possess any property that could be thought of as a "weight".

    4. The criterion called {all items assigned} in the paper reads xij = 1 in the paper but xij <= 1 in Wikipedia. The difference is that in the former case all programmers must be assigned a task which they don't have to in the latter.
    Last edited by razzle; November 15th, 2014 at 04:59 AM.

  10. #10
    Join Date
    Feb 2013
    Posts
    58

    Re: Genetic Algorithm idea or alternative

    Quote Originally Posted by z80z80 View Post
    What do you mean with "run db with scores"?
    db is database.
    And yes personal scores are subjective are not very informative, not only social collisions but is a subjective measure, but these are the requeriments... (the programmers sample is not the real one but would be similar)
    I think the "subjective measurement" would be the failure point at the end and not if I can find the "optimization algorithm" but I've to solve only the "technical part"...
    i don't fully agree w/ you about subjective measurements: any measurement is only approximation of real value. the more data of person you have, the more accurate estimation upon his/her scores (for given task at whatever conditions) you can calculate. Another question is methodology to harvest needful data

  11. #11
    Join Date
    Feb 2013
    Posts
    58

    Re: Genetic Algorithm idea or alternative

    @Razzle
    But since GAP is NP-complete GA may be the preferred solution strategy anyway. And even though GAP is the closest standard problem to yours it may not be that exact problem you want to solve and then GA is easier to bend and stretch.
    oh, such fearful term "NP-complete" for most cases, it's quite possible to develop statistical model w/o so dramatic complexity

  12. #12
    Join Date
    Jul 2013
    Posts
    576

    Re: Genetic Algorithm idea or alternative

    Quote Originally Posted by S@rK0Y View Post
    oh, such fearful term "NP-complete" for most cases, it's quite possible to develop statistical model w/o so dramatic complexity
    If you're referring to stochastic approaches then the Genetic Algorithm (GA) the OP is already using is one of them.

    No one is afraid of NP-completeness but once you know your problem is in this category you know that for big data sets it's tractable only if some sort of approximation strategy is used. There are essentially two kinds. One that finds the exact solution to a relaxed problem and one that searches for a near optimum solution to the original problem. GA belongs to the latter.
    Last edited by razzle; November 14th, 2014 at 08:58 AM.

  13. #13
    Join Date
    Feb 2013
    Posts
    58

    Re: Genetic Algorithm idea or alternative

    Quote Originally Posted by razzle View Post
    If you're referring to stochastic approaches then the Genetic Algorithm (GA) the OP is already using is one of them.

    #1#No one is afraid of NP-completeness but once you know your problem is in this category you know that for big data sets it's tractable only if some sort of approximation strategy is used. There are essentially two kinds. One that finds the #2#exact solution to a relaxed problem and one that searches for a near optimum solution to the original problem. GA belongs to the latter.
    #1 NP-complete, in most of cases, means NO-SOLUTION AT ALL, the're Just no computing muscle to run such kind of things. But we must keep in mind that NPC is very child of lack of data. So i urgently pushed upon methods to harvest needful data.

    #2 exact solution is more theoretical thing, rather than Practical. Even systems of linear equations get approximated.

  14. #14
    Join Date
    Jul 2013
    Posts
    576

    Re: Genetic Algorithm idea or alternative

    Quote Originally Posted by S@rK0Y View Post
    #1 NP-complete, in most of cases, means NO-SOLUTION AT ALL, the're Just no computing muscle to run such kind of things. But we must keep in mind that NPC is very child of lack of data. So i urgently pushed upon methods to harvest needful data.

    #2 exact solution is more theoretical thing, rather than Practical. Even systems of linear equations get approximated.
    You're wrong on both accounts but I won't get into why. I've wasted too much time on you already (in this and other threads). Your unintelligible baloney is starting to get on my nerves. So for health reasons I'm going to have to ignore you from now on. Sorry.
    Last edited by razzle; November 16th, 2014 at 05:36 AM.

  15. #15
    Join Date
    Feb 2013
    Posts
    58

    Cool Re: Genetic Algorithm idea or alternative

    Quote Originally Posted by razzle View Post
    You're wrong on both accounts but I won't get into why. I've wasted too much time on you already (in this and other threads). Your unintelligible baloney is starting to get on my nerves. So for health reasons I'm going to have to ignore you from now on. Sorry.
    Razzle, let's be on topic, Please, w/o funny personal assaults. If you have something to defend your point -- share it, otherwise it's better to keep Silence Actually, i'd like to see HOW-TO deal w/ NPC & HOW-TO get true values, instead of approximation F.i. i want fast integer factorization, so you fearlessly can help me out

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured