35

The main idea is that by allowing suboptimal individuals to survive, you can switch from one "peak" in the evolutionary landscape to another through a sequence of small incremental mutations. On the other hand, if you only are allowed to go uphill it requires a gigantic and massively unlikely mutation to switch peaks. Here is a diagram showing the ...


19

No. This direction is unlikely to be useful, for two reasons: Most computer scientists believe that P $\ne$ NP. Assuming P $\ne$ NP, this means there does not exist any polynomial-time algorithm to solve any NP-complete problem. If you want your neural network to solve the problem in a reasonable amount of time, then it can't be too large, and thus the ...


16

I don't know the actual reason, but it feels intuitive: let's think about what the diploid nature of genes does in RL. In essence it allows the recessive gene to remain in the gene pool even if it's currently at disadvantage to exist, and occasionally resurface, giving two things - first, it doesn't go extinct and can re-multiply if it becomes advantageous; ...


13

Nick Alger's answer is very good, but I'm going to make it a little more mathematical with one example method, the Metropolis-Hastings method. The scenario that I'm going to explore is that you have a population of one. You propose a mutation from state $i$ to state $j$ with probability $Q(i,j)$, and we also impose the condition that $Q(i,j) = Q(j,i)$. We ...


11

First of all - the example doesn't seem well suited because you would probably use some regression or classical ML methods to solve this. Secondly - you are referring to a general problem of feature selection (Kira, Rendell, 1992) or attribute selection (Hall, Holmes, 2003) or variable selection (Guyon, Elisseeff, 2003) or variable subset selection (Stecking,...


10

The key point in deciding whether or not to use genetic algorithms for a particular problem centers around the question: what is the space to be searched? If that space is well-understood and contains structure that can be exploited by special-purpose search techniques, the use of genetic algorithms is generally computationally less efficient. ...


9

In searching around for an online presence for one of the classics in this field (Coffman, Denning: Operating Systems Theory, Prentice Hall, 1983) I came upon what looks like a comprehensive textbook with a Google books preview Pinedo: Scheduling: Theory, Algorithms, and Systems, Springer 2008. The author's homepage also has pages devoted to each of his ...


9

It looks like you're dealing with premature convergence. In other words, your population fills itself with individuals that represent the suboptimal solution and/or individuals that are (too) close to said solution. The basic framework of a genetic algorithm is as follows: P <- Population of size N with N random individuals. evaluate fitness of all ...


9

No. Just knowing the size of the search space is not enough to tell whether GA will work or not. It also depends on the objective function (the "shape" of it), e.g., whether it is smoothly varying or not, how many local minima it has, and so on. There is no good theory to know whether GA will work or not. Ultimately, all you can do is try it and see. As ...


8

The typical approach is performing several runs of the evolutionary algorithm (EA) and plot the average performance over time (average performance of best-of-run-individual NOT population average). A good rule of thumb is performing a minimum of 30 runs (of course 50-100 runs is better). The average is better than the best-value-achieved-in-a-set-of-runs ...


8

It seems other answers while informative/ helpful are not actually understanding your question exactly and are reading a little too much into it. You didn't ask if neural networks would outperform other methods, you only asked if they could be applied to NP complete problems. The answer is yes, with some success and this has been known for decades and there ...


7

The advantage of using a GA is that you are able to explore broader search spaces by following paths which come from potentially worse candidates. There should be worse candidates making it through in order to explore these different areas of the search, not many but definitely a few. If you start taking only the very best every time you remove this ...


6

Actually, selection algorithms take both approaches. One way is what you suggested and the other is that individuals with higher fitness are selected and those with lower ones are not. The approach you pick for selection is also tailored to the problem you are trying to model. In an experiment back in school, we were trying to evolve card players by having ...


6

If you're asking for a homework assignment, then I can't really help you, because the answer really depends on how your professor interprets the taxonomy. But if you're asking for your own edification, I can give you my view. First, the distinctions between the four classes you list (particularly between 1, 3, and 4) are largely historic. There are still ...


6

It increases the convergence speed of the GA, which is a double-edged sword. You want the algorithm to find good solutions quickly, but not so quickly that is has not been able to sample sufficiently large areas of the space that it's not just doing a very local search around the initial population. Another option that can work well is to be elitist, but ...


6

How to rank the individuals of a population based on both diversity and fitness? You can combine diversity and fitness into a single score: $$score(i) = fitness(i) + k \cdot diversity(i)$$ It's a standard approach and doesn't require significant changes to the algorithm. Unfortunately $k$ is problem-specific. Alternatively change the standard GA to a ...


5

As a simple method, you can use the roulette wheel selection. The idea is that every individual has a chance to be selected as a parent, but the more fit an individual is, the more likely it is to be selected. Let $f_i$ be the fitness of the individual $i$. The probability $p_i$ of choosing $i$ as a parent for the next round is $p_i = f_i / \sum_{j=1}^{N}$, ...


5

In short: AST representations of programs are more easily analyzed, manipulated, and transformed, while preserving and enforcing the existence of a formally defined program meaning through the transformations. I am asssuming that the reader knows already what is an abstract syntax tree (AST), and does not need to be shown examples. The question is an issue ...


5

Adding on Raphael's answer: in a hybrid genetic algorithm (HGA), mutation plays a different role than it does in a "pure" GA. The local refinement requirement of the mutation operator is unnecessary in the existence of an explicit local operator allowing the mutation operator to take a more exploratory role (see Evolutionary algorithms with local search ...


4

Generally speaking, evolutionary algorithms stop well short of trying to model real biology, and this is one example of something that occurs in nature but not in commonly used evolutionary algorithms. Instead, we tend to use a system where all individuals have only one value for each gene, and they're all "active". Replication, mutation, and recombination ...


4

Your selection method may lie at the root of this. You are currently using truncation selection, which applies a very high selective pressure and reduces diversity by not allowing elements from worse solutions to be preserved to possibly be useful again in future generations. You should try different selection methods, in particular roulette selection or ...


4

The wording of the original paper that introduced Differential Evolution is such that the authors consider DE a different thing from Genetic Algorithms or Evolution Strategies. Example: Choosing a subgroup of parameters for mutation is similiar to a process known as crossover in GAs or ESs. Another one: A further disadvantage of GAs is the amount ...


4

There is no minimum to population size but it has a few drawbacks when it is too low. when it is too low your genetic algorithm is almost going to be a deterministic or greedy algorithm and besides that you are going to lose the effect of weak answers. it has been proved that even the weakest answer can move the algorithm to a good answer. The nature of ...


4

Neural networks do not actually solve NP-complete problems. What they do do is solve problems which are remarkably close to NP-complete problems. One big feature of neural networks is that they are not obliged to find the "right" answer every time. They are allowed to be "wrong." For example, you might be solving a bin-packing problem, and come to a ...


4

The details depend on your fitness function, which you have not shared. With your modification, you can only ever jump from one local optimum to the slope of another. Hence, you will certainly get little diversity if there are few local optima or the local optima are far apart but you do only small steps (e.g. local mutations). In the first case, little ...


4

There have been hundreds of papers published over the years on training neural networks with GAs. Here's a starting point Neuroevolution. The basic problem though is that stochastic gradient descent works really well in vastly less computation time.


3

I have never done this before, and obviously don't have access to said data, but a potentially good way to do this would be through clustering. For each employee, we have an n-dimensional vector, where each dimension cooresponds to a different task. Then, we can use clustering to group "similar" employees together; however, this is going to be solely ...


3

As I pointed out in the comments, the primary feature of interest for understanding how a genetic algorithm (or evolution, even) explores the fitness landscape is the fitness function. In this case, you specified an extremely simple fitness function with no epistasis. This was a standard assumption for analytical tractability when biology first started out (...


3

Start with a population, where every candidate is "good", where "good" means they contain at least one occurrence of substrings "01" and "011". For the mutation operator, flip a coin. If the result is heads, choose a random substring of length 2 and change it to "01". If the result is tails, choose a random substring of length 3 and change it to "011". For ...


3

As you say, there are no universal parameter settings, which means that you won't find a source that cites any such settings. Instead, you find some papers who tune the parameters to their particular problem, and you find many, many others that simply take a "standard" set of parameter settings without much attempt to justify them. In that case, it's not ...


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