Algorytm genetyczny z mutacją ruletkową

• Autorzy: Dudek G.

Warianty tytułu

EN

A genetic algorithm with a roulette wheel mutation

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

algorytm genetyczny; mutacja; specjalizowane operatory genetyczne; optymalizacja kombinatoryczna

EN

genetic algorithm; mutation; specialized genetic operators; combinatorial optimization

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Informatyka Teoretyczna i Stosowana
• Rocznik: 2007
• Tom: R. 7, nr 12
• Strony: 91--107
• Opis fizyczny: Bibliogr. 18 poz., rys., tab.

Twórcy

autor

Dudek G.

• Wydział Elektryczny, Politechnika Częstochowska al. Armii Krajowej 17, 42-200 Częstochowa,

Bibliografia

• [1] Holland J., Adaptation in Natural and Artificial Systems, University of Michigan 1975.
• [2] Fogel L.J., Owens A.J., Walsh M.J., Artificial Intelligence through Simulated Evolution, Wiley, New York 1966.
• [3] Koza J., Genetic Programming, MIT Press, Cambridge MA 1992.
• [4] Rechenberg I., Cybernetic Solution Path of an Experimental Problem, Royal Aircraft Establishment Library Translation 1122, Famborough UK 1965.
• [5] Michalewicz Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, WNT, Warszawa 1996.
• [6] Galar R., Miękka selekcja w losowej adaptacji globalnej w RD. Próba biocybernetycznego ujęcia rozwoju, Wydawnictwo Politechniki Wrocławskiej, Wrocław 1990.
• [7] Arabas J., Wykłady z algorytmów ewolucyjnych, WNT, Warszawa 2001.
• [8] Goldberg D.E., Algorytmy genetyczne i ich zastosowania, WNT, Warszawa 1995.
• [9] Bäck T., Fogel D.B., Michalewicz Z. (edytorzy), Handbook of Evolutionary Computation, IOP Publishing Ltd and Oxford University Press, 1997.
• [10] Brzozowski W., Optymalizacja eksploatacji elektrowni z pomocą algorytmu genetycznego, Materiały konferencyjne Algorytmy Ewolucyjne i Optymalizacja Globalna, Potok Złoty 1997, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa 1997, 25-32.
• [11] Gen M., Cheng R., Genetic Algorithms and Engineering Design, John Wiley & Sons, New York 1997.
• [12] Chambers L., (edytor), The Practical Handbook of Genetic Algorithms. Application, Chapman & Hall/CRC 2001.
• [13] Brown T.A., Genomy, WN PWN, Warszawa 2001.
• [14] Cairns J., Overbaugh J., Miller S., The origin of mutants, Nature 1988,335, 142-145.
• [15] Bäck T, Self-adaptation in genetic algorithms, Proceedings of the First European Conference in Artificial Life. MIT Press, Cambridge MA 1992.
• [16] Dudek G., Unit Commitment by Genetic Algorithm with Specialized Search Operators, Electric Power Systems Research 2004, 72, 299-308.
• [17] Mitchell M., Forrest S., Holland J.H., The Royal Road for Genetic Algorithms: Fitness Landscapes and GA Performance. W Toward a Practice of Autonomous Systems: Proceedings of the First European Conference in Artificial Life, MIT Press, Cambridge MA 1992.
• [18] Richter J.N., Paxton J., Adaptive Evolutionary Algorithms on Unitation, Royal Road and Long-Path Functions. Proceedings of the Fourth IASTED International Conference Computational Intelligence, Calgary, Canada 2005, 381-386.