انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

GA5

After crossover, the strings are subjected to mutation. Mutation prevents the algorithm to be trapped in a local minimum. Mutation plays the role of recovering the lost genetic materials as well as for randomly disturbing genetic information. Mutation of a bit involves flipping a bit, changing 0 to 1 and vice-versa.

Flipping

Flipping of a bit involves changing 0 to 1 and 1 to 0 based on a mutation chromosome generated.

5.7 Replacement

Replacement is the last stage of any breeding cycle. Two parents are drawn from a fixed size population, they breed two children, but not all four can return to the population, so two must be replaced i.e., once off springs are produced, a method must determine which of the current members of the population, if any, should be replaced by the new solutions. The technique used to decide which individual stay in a population and which are replaced in on a par with the selection in influencing convergence . Basically, there are two kinds of methods for maintaining the population; generational updates and steady state updates.

In a steady state update, new individuals are inserted in the population as soon as they are created, as opposed to the generational update where an entire new generation is produced at each time step. The insertion of a new individual usually necessitates the replacement of another population member.

5.7.1 Random Replacement

The children replace two randomly chosen individuals in the population. The parents are also candidates for selection. This can be useful for continuing the search in small populations, since weak individuals can be introduced into the population.

5.7.2 Weak Parent Replacement

In weak parent replacement, a weaker parent is replaced by a strong child. With the four individuals only the fittest two, parent or child, return to population. This process improves the overall fitness of the population when paired with a selection technique

that selects both fit and weak parents for crossing, but if weak individuals and discriminated against in selection the opportunity will never raise to replace them.

5.7.3 Both Parents

Both parents replacement is simple. The child replaces the parent. In this case, each individual only gets to breed once. As a result, the population and genetic material moves around but leads to a problem when combined with a selection technique that strongly favors fit parents: the fit breed and then are disposed of.

5.8 Search Termination (Convergence Criteria)

In short, the various stopping condition are listed as follows:

• Maximum generations–The genetic algorithm stops when the specified number of generation’s have evolved.

• Elapsed time–The genetic process will end when a specified time has elapsed.

Note: If the maximum number of generation has been reached before the specified time has elapsed, the process will end.

• No change in fitness–The genetic process will end if there is no change to the population’s best fitness for a specified number of generations.

Note: If the maximum number of generation has been reached before the specified number of generation with no changes has been reached, the process will end.

• Stall generations–The algorithm stops if there is no improvement in the objective function for a sequence of consecutive generations of length Stall generations.

• Stall time limit–The algorithm stops if there is no improvement in the objective function during an interval of time in seconds equal to Stall time limit.

 Example//TSP problem using GA