12

Section 4.2 of "Essentials of Metaheuristics" has a wealth of information on alternative ways of encoding graph structures via Genetic Algorithms. With particular regard to evolving ANNs, I would personally not be inclined to implement this sort of thing 'from scratch': The field of neuroevolution has been around for some time, and the implementation some ...


11

Evolutionary algorithms are a family of optimization algorithms based on the principle of Darwinian natural selection. As part of natural selection, a given environment has a population of individuals that compete for survival and reproduction. The ability of each individual to achieve these goals determines their chance to have children, in other words to ...


9

A Markov model includes the probability of transitioning to each state considering the current state. "Each state" may be just one point - whether it rained on specific day, for instance - or it might look like multiple things - like a pair of words. You've probably seen automatically generated weird text that almost makes sense, like Garkov (the output of a ...


8

A genetic algorithm is an algorithm that randomly generates a number of attempted solutions for a problem. This set of attempted solutions is called the "population". It then tries to see how well these solutions solve the problem, using a given fitness function. The attempted solutions with the best fitness value are used to generate a new population. ...


7

Mutation is usually defined to be a global operator, i.e. iterated mutation is (eventually) capable of reaching every point in the vector space defined by the geneome. In that sense, mutation alone is certainly 'enough'. Regarding the motivation for crossover - from Essentials of Metaheuristics, p42: Crossover was originally based on the premise that ...


7

As explained in an answer to this AI SE question, GAs are 'satisficers' rather than 'optimizers' and tend not to explore 'outlying' regions of the search space. Rather, the population tends to cluster in regions that are 'fairly good' according to the fitness function. In contrast, I believe the thinking is that novelty affords a kind of dynamic fitness, ...


7

For gomoku, it seems a bit of an overkill to use neural networks or the genetic algorithm as both take a while and more often than not, don't go how you want it to. The gomoku game tree is rather large, but you can get a decent AI from minimax, game tree pruning, and a good heuristic function (that includes counting half and full 2s,3s,4s,...etc.) as opposed ...


6

There are a number of good answers here explaining what genetic algorithms are, and giving example applications. I'm adding some general purpose advice on what they are good for, but also cases where you should NOT use them. If my tone seems harsh, it is because using GAs in any of the cases in the Not Appropriate section will lead to your paper being ...


6

This answer requests a practical example of how one might be used, which I will attempt to provide in addition to the other answers. They seem to due a very good job of explaining what a genetic algorithm is. So, this will give an example. Let's say you have a neural network (although they are not the only application of it), which, from some given inputs, ...


6

Genetic algorithms are an analogy to biology, not a copy of it. The core piece of the analogy is that the "phenotype", or the observable portion of a solution, is constructed from the "genotype", or the internal portion of a solution. For example, a number (the phenotype) can be stored as a binary series of "0"s and "1"s (the genotype), and by changing ...


6

"Trap" functions were introduced as a way to discuss how GAs behave on functions where sampling most of the search space would provide pressure for the algorithm to move in the wrong direction (wrong in the sense of away from the global optimum). For example, consider a four-bit function f(x) such that f(0000) = 5 f(0001) = 1 f(0010) = 1 f(0011) = 2 f(0100)...


6

Novelty search selects for "novel behavior", by some domain-dependent definition of novelty. For example, novelty in a Maze-solving domain might be "difference of route explored". Eventually, networks that take every possible route through the maze will be found, and you could then select the fastest. This would work far better than a naive "objective", like ...


6

i'm the main developer of Neataptic, a Javascript neuro-evolution library. Very effective! Realise that this is how real-life evolution happened as well: we kept on improving against other species, which forced them to improve as well. Very practical, especially if you don't want to set up any 'rules' like you say, it makes the genomes find out what the ...


5

As I see it, it all comes down to game theory, which can be said to form the foundation of successful decision making, and is particularly useful in a context, such as computing, where all parameters can be defined. (Where it runs into trouble is with the aggregate complexity of the parameters per the "combinatorial explosion", although Machine Learning has ...


5

Over the last few years, evolutionary computation research has shown increasing interest in including some aspect of epigenetics. For example: A 2008 paper by Tanev and Yuta Work from Lee Spector's genetic programming group A recent paper by Ricalde and Banzhaf


5

As observed in another answer, all you need to apply Genetic Algorithms (GAs) is to represent a potential solution to your problem in a form that is subject to crossover and mutation. Ideally, the fitness function will provide some kind of smooth feedback about the quality of a solution, rather than simply being a 'Needle in a Haystack'. Here are some ...


5

Crossover allows to combine two parents (vs. mutation, which only uses one parent). In some cases, it is useful (e.g., if you train a FPS bot, if one parent is good at shooting and another parent is good at moving, it makes sense to combine them). In some other cases, it is not.


5

In a genetic algorithm, crossover (recombination) is the analogy to mating in the real world. For example, you have some genetic information from each parent. In the case of an optimization where you have vectors of features (design variables), you could represent it as vector 1 and 2. Imagine each vector has 10 values. You grab the first 5 from vector 1, ...


5

Biological and artificial evolution work around pretty much the same principles. Fitness and selection: In biology, the fittest organisms in an ecosystem are more likely to survive long enough to reproduce, passing on their genes in the process. In artificial evolution, our organisms are in fact solutions to our problem, which can be evaluated to determine ...


5

Genetic algorithms and Neural Networks both are "general" methods, in the sense that they are not "domain-specific", they do not rely specifically on any domain knowledge of the game of Mario. So yes, if they can be used to successfully learn how to play Mario, it is likely that they can also be applied with similar success to other Platformers (or even ...


5

There is no "best language" for any problem. There are too many variables to consider, even when advising a single person with a single project plan. If the choice is between Python and C++, I would generally advise: If you want to implement from scratch and learn how the algorithm works, use Python with numeric/accelerated libraries such as NumPy or ...


5

I would like to add this as a comment to Martin Thoma's answer, but I do not have enough reputation to comment... However, the most important point he stresses out for me is the definition of "perfect". Since the question was already tagged "philosophy", I think that the answer can be a bit philosophically here ;) The point we miss, is that there is no ...


5

Mutation is an operation which is applied to a single individual in the population. It can e.g. introduce some noise in the chromosome. For example, if the chromosomes are binary, a mutation may simply be the flip of a (random) bit (gene). Crossover is an operation which takes as input two individuals (often called the "parents") and somehow combines their ...


4

When thinking about crossover its important to think about the fitness landscape. Consider a hypothetical scenario where we are applying a genetic algorithm to find a solution that performs well at 2 tasks. This could be from Franck's example (moving and shooting) for an AI, or perhaps it could be predicted 2 outputs in a genetic machine learning scenario, ...


4

An ability that is commonly attributed to intelligence is problem solving. Another one is learning (improving itself from experience). Artificial intelligence can be defined as "replicating intelligence, or parts of it, at least in appearance, inside a computer" (dodging the definition of intelligence itself). Genetic algorithms are computational problem ...


4

Using evolutionary algorithms to evolve neural networks is called neuroevolution. Some neuroevolution algorithms optimize only the weights of a neural network with fixed topology. That sounds not like what you want. Other neuroevolution algorithms optimize both the weights and topology of a neural net. These kinds of algorithms seem more appropriate for ...


4

If you read Steven Levy's book, Artificial Life,you will find, as I did, the distinction between biological and "artificial" life blurred. If you think about it, what exactly is "life", anyway? A set of complex systems with emergent behavior capable of evolution and adaptation. A prototypical biologist may not define life that way. Indeed, he would, not ...


4

"Life" is a definition humans use to classify objects according to the types of behavior humans perceive as unique to living creatures. Scientists and philosophers tend to define something as "alive" if it manifests some specific properties found in living organisms, such as self-replication, adaptation to the environment, homeostasis and capability to ...


4

As @Thomas W said, you can be pretty immaginative when you're developing mutation and crossover methods. Each problem has its own caracteristics and, therefore, requires a different strategy. BUT, from my experience, I'd say that 90% of crossovers and mutation on real numbers genotypes are solved using the BLX-α algorithm. Crossover: This algorithm is ...


4

It is actually the other way around: connection IDs is what is debated! Nodes always have innovation IDs (in the image, it is just their identifying number). Node IDs are sufficient to identify connections. If a connection links nodes 3 and 6, then it is the same as another connection linking nodes 3 and 6: no need for an extra ID. So why the extra ...


Only top voted, non community-wiki answers of a minimum length are eligible