General question about crossover operator for a genetic algorithm

[markiv]

Hey guys, this is my first time working on a genetic algorithm. It seems to me that the algorithm is primarily defined by how you choose to define your crossover operator and fitness function. Let's say the crossover takes two parents and produces one child. Is it necessary/good/bad/etc that the child should have a higher fitness than either of its parents? Or do we let the selection function take care of making sure that our population increases in fitness over time?

 

[swartzism]

It technically depends on the goal of you GA, but the way that I had it explained to me was this:

You take an initial population of M and F parents. You combine them and produce children. You take the children with a lower fitness than your continuation criteria, you shoot them in the head, and you move on. Morbid, but it does a good job of getting the point of the algorithm.

What language are you writing in? I have an evolutionary algorithm written in Fortran 90 from a few years ago that you could take a look at. It's from college, so it's not perfect, but it might give you good ideas.

 

[jhae2.718]

Artificial Intelligence - A Modern Approach by Russell and Norvig and Machine Learning by Mitchell offer high level overviews of genetic algorithms.

The population's overall fitness will increase over time due to the way the GA works. It's common to basically have three ways to create the new population:

1. Elite children
2. Crossover
3. Mutation

Elite children are the elements of the population with the highest fitness. A fixed number of these elites will automatically join the next generation.

Crossover combines two individuals to produce two offspring. The parents are generally chosen probabilistically according to the following function, where $h$ is an individual hypothesis, $\Phi(h)$ is the fitness function, and $n$ is the population size:
$$P(h_i \text{ is selected}) = \frac{\Phi(h_i)}{\sum_{j=1}^n \Phi(h_j)}$$
Then, you either do single-point crossover, two-point crossover, or uniform crossover to create two offspring.

Mutation is then applied to the population. Generally speaking, a percentage of the population is chosen with uniform probability and each chosen individual has a random bit inverted.

So, basically, the fitness function drives which individuals are selected to move on; technically speaking, the fitness function solely assigns a numerical score representing the quality of the hypothesis; the actual genetic algorithm decides which individuals are kept. Crossover is a method to generate new individuals which may or may not be more fit than the parents.

Of course, the above details can change based on the way the GA is implemented.

 

[markiv]

Thanks for the feedback.

What language are you writing in? I have an evolutionary algorithm written in Fortran 90 from a few years ago that you could take a look at. It's from college, so it's not perfect, but it might give you good ideas.

The final program will likely be written in C, but I may write it in Python first for proof of concept. If you do have code though, I'd like to look at it.

Artificial Intelligence - A Modern Approach by Russell and Norvig and Machine Learning by Mitchell offer high level overviews of genetic algorithms.

The population's overall fitness will increase over time due to the way the GA works. It's common to basically have three ways to create the new population:

1. Elite children
2. Crossover
3. Mutation

Elite children are the elements of the population with the highest fitness. A fixed number of these elites will automatically join the next generation.

Crossover combines two individuals to produce two offspring. The parents are generally chosen probabilistically according to the following function, where $h$ is an individual hypothesis, $\Phi(h)$ is the fitness function, and $n$ is the population size:
$$P(h_i \text{ is selected}) = \frac{\Phi(h_i)}{\sum_{j=1}^n \Phi(h_j)}$$
Then, you either do single-point crossover, two-point crossover, or uniform crossover to create two offspring.

Mutation is then applied to the population. Generally speaking, a percentage of the population is chosen with uniform probability and each chosen individual has a random bit inverted.

So, basically, the fitness function drives which individuals are selected to move on; technically speaking, the fitness function solely assigns a numerical score representing the quality of the hypothesis; the actual genetic algorithm decides which individuals are kept. Crossover is a method to generate new individuals which may or may not be more fit than the parents.

Of course, the above details can change based on the way the GA is implemented.

Thanks a lot for the references, they look very good. After browsing around the internet about GA, though, there's this question that keeps coming up that I haven't found an answer to. I know single-point, two-point, and uniform crossovers are all different ways to crossover two individuals, but are these the only ways to perform a crossover? For example, I'd like to represent each individual in my population as pair of permutations, but permutations don't exactly lend themselves to these types of crossover. I've thought of ways of "combining" two individuals in such a way that the offspring "resembles" the parents, but they aren't any of the 3 mentioned above. Must they be so?

 

[jhae2.718]

Crossover is basically just swapping parts of two parents to create two children, so you're fine. There are other types of crossover defined for different types of individuals; trees for example can't use the types of crossover defined above.