Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: specialized genetic operators

Sortuj według:

Ogranicz wyniki do:

Algorytm genetyczny z mutacją ruletkową

Dudek G.

Informatyka Teoretyczna i Stosowana

2007

R. 7, nr 12

91-107

Przedstawiono algorytm genetyczny z reprezentacją binarną i nowym operatorem mutacji wykorzystującym metodę koła ruletki. Prawdopodobieństwo mutacji bitu w klasycznym algorytmie genetycznym jest stałe. W proponowanej metodzie uzależnia się to prawdopodobieństwo od przebiegu procesu ewolucyjnego. Loci, których mutacja z 0 na 1 (z 1 na 0) we wcześniejszych generacjach poprawiła ocenę chromosomu, mutowane są częściej z 0 na 1 (z 1 na 0). Do ustalenia prawdopodobieństwa mutacji bitu używa się metody koła ruletki. Metodę zobrazowano przykładami optymalizacji kombinatorycznej ze zmiennymi binarnymi. W jednomodalnych problemach optymalizacji kombinatorycznej odnotowano przyspieszenie zbieżności algorytmu do optimum.

A genetic algorithm with binary representation and a new operator or mutation using the roulette wheel method is presented. The probability of the bit mutation in a classical genetic algorithm is fixed. In the proposed method this probability is dependent on the history of the evolutionary process. Loci, whose mutation from 0 to 1 (from 1 to 0) improved the evaluation of the chromosome in early generations, are mutated frequently tram 0 to 1 (from 1 to 0). The roulette mutation bas adaptive control of the probability of the lotus mutation. Each locus of the chromosome bas two coefficients of mutation intensity: from 0 to 1- w 0-1 and from 1 to 0 - w 1-0. The values of these coefficients are updated in each generation after mutation. If the mutation from 0 to 1 (from 1 to 0) brings positive effects (an increase in the chromosome fitness), the value of the appropriate w 0-1 (w 1-0) coefficient increases. In case of negative effects the value of the coefficient decreases. A high value of w 0-1(i) gives information that in the previous realization of the evolutionary process the change of ith bit from 0 to 1 (from 1 to 0) in most cases brought the improvement in fitness. The probability of the bit mutation from 0 to l (from 1 to 0) - p 0-1(i) (p 1-0(i)) is proportional to the w 0-1(i) (w 1-0(i)) value for this bit. The bits for mutation are chosen using the roulette wheel method. The roulette wheel is composed of two sectors "0-1" and "1-0". Each locus bas the subsector S 0-1(i) in the "0-1" sector and subsector S 1-0(i) in the "1-0" sector. The sizes of these subsectors are dependent on the probabilities p 0-1(i) and p 1-0(i). The operation of mutation consists of: sampling with replacement of q chromosomes and a number indicating subsector on the roulette wheel which in turn determines the lotus for mutation and direction of mutation (from 0 to 1 or from 1 to 0) for each of the above mentioned chromosomes. The experiments showed that the operator of roulette mutation significantly speeds up the convergence of the algo-rithm in the unimodal tasks of the combinatorial optimization. The effectiveness of the roulette mutation depends on the availability of information about the sensitivity of objective function to the changes in the variable values. If the direction of an influence of a certain variable on the value of the objective function depends on the values of others variables, it may lead to the improper operation of the roulette mutation, deterioration of the exploratory properties and to the convergence of the algorithm to the local optimum.