Wielofazowa metoda różnicowania populacji w algorytmie ewolucyjnym

• Autorzy: Chmiel W. , Kadłuczka P.

Warianty tytułu

EN

A multi-phase diversification method of population in the evolutionary algorithm

• Konferencja: XVI Krajowa Konferencja Automatyzacji Procesów Dyskretnych, (2008, Gliwice, Polska)
• Języki publikacji: PL

Abstrakty

PL

Zastosowana w algorytmie ewolucyjnym koncepcja zmiennej w czasie strategii sukcesji ma na celu sterowanie zbieżnością algorytmu. Początkowa faza obliczeń różnicuje w większym stopniu rozwiązania w populacji niż fazy późniejsze. Prawdopodobieństwo wstawienia nowo wygenerowanego rozwiązania do populacji, zmienne w kolejnych etapach, jest uzależnione od wartości funkcji przystosowania oraz od pewnej funkcji rozkładu prawdopodobieństwa. Jako zagadnienie testowe dla zaproponowanego algorytmu przyjęto NP-trudne kwadratowe zagadnienie przydziału.

EN

This paper investigates a new advanced evolutionary algorithm for optimization of permutation problems. Implementation of varying in time strategy of succession in evolution algorithms enables controlling the population diversification. In early phases of optimization the diversification of population is greater than the later ones. During all phases the probability of adding solution to population depends on the solution fitness function and certain probability density function. The experiments were performed for standard test problems of quadratic assignment problems (QAP).

Słowa kluczowe

PL

algorytm ewolucyjny; bioinformatyka; kwadratowe zagadnienie przydziału; algorytm GASA

EN

evolutionary algorithm; bioinformatic; quadratic assignment problems; GASA algorithm

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2008
• Tom: z. 151
• Strony: 195--202
• Opis fizyczny: bibliogr. 7 poz.

Twórcy

autor

Chmiel W.

autor

Kadłuczka P.

• Katedra Automatyki, AGH al. Mickiewicza 30, 30-059 Kraków tel. [phone],

Bibliografia

• 1. Burkard R.E., Karisch S.E., Rendl F.: QAPLIB-A Quadratic Assignment Problem Library. European Journal of Operational Research, 1991, 55, 115.
• 2. Croes G. A.: A Method for Solving Traveling-Salesman Problems: Operations Research. Vol. 6, No. 6 (Nov. - Dec, 1958), p. 791-812.
• 3. Kadłuczka P., Chmiel W.: Zastosowanie własności zagadnienia QAP w konstrukcji algorytmów ewolucyjnych. AGH, Kraków 2004, s. 112-120.
• 4. Filipowicz B., Wala K.: Algorytmy optymalizacji kwadratowego zagadnienia przydziału. Kwartalnik Elektrotechnika, z.l, Wydawnictwo AGH, Kraków 1992, 32-42.
• 5. Goldberg D. E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley Publishing Company, 1989.
• 6. Michalewicz Z.: Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag, 1995.
• 7. Nissen V.: Evolutionäre Algorithmen Darstellung, Beispiele, betriebswirtschaftliche Anwendungs-möglichkeiten, Deutscher Universitäts Verlag, Wiesbaden 1994.