Author Topic: Genetic Algorithm  (Read 1621 times)

Offline Brazilian Fan

  • Sr. Member
  • ****
  • Posts: 303
Genetic Algorithm
« on: February 21, 2007, 11:50:58 AM »
Does anyone has any info (overview, source codes in Java/C++ etc.) regarding Genetic Algorithms?

Offline dm-horus

  • Hero Member
  • *****
  • Posts: 1047
    • Division 32 Community
Always outnumbered. Never outgunned.

Offline Brazilian Fan

  • Sr. Member
  • ****
  • Posts: 303
Genetic Algorithm
« Reply #2 on: February 21, 2007, 12:30:55 PM »
Thanks  (thumbsup)  

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4445
Genetic Algorithm
« Reply #3 on: February 21, 2007, 10:24:40 PM »
The wiki article was pretty good.

Just wondernig what you're planning to do with this stuff. If you have to ask what it is, I'm sort of wondering if it's really the tool you'd need or even want to use. The techniques are used to find global optimas and from what I can tell, it's mostly used for fairly obscure abstract problems. Problems that are usually fairly simple to describe every detail precisely, but would require searching an exponentially large space to find the answer to with certainty.

If you're thinking of using it for some sort of game AI, this might not be the best tool. It's hard to apply this sort of technique to any game. Even a really really simple one can be challenging. Plus it's not known for speed, and the accuracy of the solutions can be quite terrible. Not just the initial approximation either. If the parameters aren't set right, it might never converge to a good solution. You also have to figure out how to distinguish a good solution from a bad solution. That alone isn't always an easy task. especially since a binary yes/no answer isn't useful for this technique. So if it's simulating playing a game and determine if the player won or lost, that's not enough info to make changes to lead to a better solution.
 

Offline Brazilian Fan

  • Sr. Member
  • ****
  • Posts: 303
Genetic Algorithm
« Reply #4 on: February 22, 2007, 05:20:38 AM »
It's for a basic AI I'm testing, not related to any game. The AI's main objective is to scan a virtual location and take decisions based on that scan.

I was thinking to use GA because many specialized sites pointed GA as a good solution to resolve some decisions the AI would take.

The main problem is: I understand the logic behind GA, but it's tricky for me to implement it in C++   :heh:

Any other options?

Thanks  :D  

Offline Brazilian Fan

  • Sr. Member
  • ****
  • Posts: 303
Genetic Algorithm
« Reply #5 on: February 22, 2007, 09:14:41 AM »
What about Neural Networks? It's probably the best self-adapting method out there

Offline White Claw

  • Hero Member
  • *****
  • Posts: 714
Genetic Algorithm
« Reply #6 on: February 22, 2007, 06:15:50 PM »
Really, the hard part of any learning AI (I think as Hooman was pointing out) is that it's hard to teach the AI. It takes many (many) iterations to teach the AI something. The hard part with something like a game is that there are so many inputs and they are so variable that it's a difficult / long process to teach a net with any kind of hope of it being any better than a "simple" AI that cheats.

And like he said, there needs to be a scale of "good" and "bad" or the net will not learn in any useful manner. Such as "how long did it take to get out of the maze" as opposed to "did I get out of the maze". If the AI always runs till it makes it out of the maze, then it will always have a winning solution (but not necessarily what you want) unless you tell it how bad or good it did.

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4445
Genetic Algorithm
« Reply #7 on: February 24, 2007, 12:43:39 AM »
Ok, well based on your initial description, I would have serious doubts that GAs would be a very useful tool for what you want to do. Neural networks seem kind of the same in many respects, but possibly a little better suited. White Claw is right though, it takes a long time to train machine learning algorithms, and you really need good feedback and training functions. Without those, there's almost no way to do the training, never mind good training.


Keep in mind what the really basic purpose of each type of algorithm is. A genetic algorithm is used to approximate something that is not exactly known or can't be exactly known. So maybe there is a function that models certain behavior, but you don't know how to write that function explicitly. Using a GA would be useful if you needed an approximating function. Maybe you don't know what the function is exactly, but you know it has certain behaviors or properties which you can test for. Using the results of the test, you can modify the approximating function little by little until you get better test results. Keep in mind that this requires some way of testing the apropriateness of the approximating function. You also need to be able to rank the approximating functions to determine which ones to "breed". If you want a decent ranking so the breeding process makes sense, then your test function will need a bit more ganularity than yes/no. This method would seem to work best when the function you're looking for is continuous, and by making small adjustments, you get a little bit smaller or farther from where you want to be. If it has erratic behavior, where small changes can produce large changes in the fitness, than the approximations will become erratic rather than converge on a nice solution. Also, for any practical purposes, you will need to know what exactly "small" means, as you will need to use an actual small value when implementing this. Also, that "small" value might not be the same throughout your attempt to solve the problem.


So does your solution look like some sort of continuous function? Is the main question basically "how much"? Say, how much fuel to use up in various thrusters to guide a ship around various meteors in a safe way while minimizing fuel use, possibly in the presence of uncertain effects, such as gravity or magnetism from an irregular or unknown shaped/sized object like the meteors you're avoiding?


Or does your solution need to be more of a yes/no response to various things? Perhaps many yes/no responses to your inputs. Or can yes/no responses you need be modeled by simple cutoff values for a function like the one described above? Is there a precise optimum solution? Or maybe there are cases where a number of choices are just as good. Would a random solution is such cases be better than a deterministic solution? Say, if you wanted the AI to be a little less pridicatable, so an opponent had to guess the best way to defeat what it was trying to do. Does your AI really need to learn? And if it does, what does it need to learn? Or perhaps you just need to learn how to solve a particular problem? Maybe once you understand it better, there is a solution the AI can deterministically come to in all cases and doesn't need to learn or adapt it's behavior to the same input because of a history of past inputs.


If you're looking for more of a "what to do" question rather than a "how much" question, then there are other method to think about. Neural Nets are often used in a "what to do" context, but they are really more of a "how much" type of solution technique. Usually what they do in the "what to do" case, is they use some sort of cutoff values on the "how much" outputs to decide on simple yes/no answers. Also, there can be many outputs, not just many inputs, so a single net might answer many questions. There are also many types of neural nets. Some use very restrictive input and output spaces or structural constraints that can affect how they work quite a bit. But the basic idea behind most neural nets is to model some sort of unknown function, which is usually continuous.


If you're looking more for hard decisions, then either of these techniques might not be suitable. Especially if you want hard decisions that are always determinisitic, where the same answers to the same questions will always produce good behavior. (Or possibly a random answer from some finite set). Something like navigating a research tech tree would be an example of this sort of problem. What tech to research next given a desired destination tech. Maybe you're learning objective is to traverse the tech tree even if it changes from one problem instance to another. Such as if someone set an OP2 mission object to research a certain tech, but they provided a custom tech tree. Then your AI might need to scan the tech tree and determine the dependencies to find what it needed to do to reach the destination. In that case, the choices made might very well be deterministic (or random if you're choosing which independent branch of a tree to work on first). Here there is no concept of an approximating continuous function.




So I guess the next question is, what type of objects are you scanning for? What decisions do you need to make?

Then try to further clarify them. Such as what restrictions are there on the system. How are the objects quantified? How are the decisions determined to be good or bad decisions? Are the decisions yes/no or some sort of continuous value? You really need to have more details to select a good AI technique, but so far it sounds like GAs are probably not the way to go, and Neural Nets might not be either. (But if they are, there's probably more research and literature on NN than on GAs, and they're probably a little less hard to program and work with).
 

Offline White Claw

  • Hero Member
  • *****
  • Posts: 714
Genetic Algorithm
« Reply #8 on: February 24, 2007, 09:28:10 AM »
Of course, on the other hand, you never asked for our inputs on how to attack your specific problem. Hopefully the provided links gave you the samples you were looking for...  :D (We do tend to get side tracked.)

Offline Hooman

  • Administrator
  • Hero Member
  • *****
  • Posts: 4445
Genetic Algorithm
« Reply #9 on: February 24, 2007, 05:42:31 PM »
lol, yes. Indeed we do.
 

Offline Brazilian Fan

  • Sr. Member
  • ****
  • Posts: 303
Genetic Algorithm
« Reply #10 on: February 25, 2007, 06:00:12 PM »
I am writing this AI focused on two objectives:

    1. Learn more in-depth C++ and programming in general

    2. Make experiences with a self-adapting set of rules (AI)

Because GA would meet my 2nd, and probably my 1st, objective (as I thought).

After I learned how 'different' GA's was from what I wanted, I started to look for another one.

Neural Nets were best suited for what I was intending.

The fist 'test' was feed the AI with limited information (representing, in it's own way, some kind of 'visual') and the AI should navigate the virtual location avoiding any type of obstacles. It would learn from it's mistakes, classifying it's actions using fuzzy logic (excellent, good, normal, bad, awful). It tries to use more 'excellent' actions than 'normal' or 'bad' actions.

There is no yes/no questions or answers, it takes any of the four options (move up, move down, move right and move left) based on it's visual information.

Anyway, this is just a test, I don't pretend to make a 'Above-Human' AI that would take all over the world, MHAUAHUAHAUHAUHAUAHUAH.

And thanks for the advices