Komputerowy algorytm optymalizacji oparty na teorii "małych światów"

• Autorzy: Bieś G.

Warianty tytułu

EN

Computer optimization algorithm based on "small-worlds" phenomenon

• Języki publikacji: PL

Abstrakty

PL

W opracowaniu przedstawiono komputerowy algorytm optymalizacji o nazwie Algorytm "Małe Światy" (AMS), wykorzystujący mechanizm przeszukiwania przestrzeni dopuszczalnych rozwiązań problemu optymalizacyjnego opartego na fenomenie zjawiska "małych światów". W algorytmie zaproponowano metody wyznaczania lokalnych i dalekich kontaktów dla modelu sieci o właściwościach "małego świata", korzystając z teorii rachunku prawdopodobieństwa połączonego z pozycyjnym systemem liczbowym. Uzyskane wyniki testów wskazują, że algorytm skutecznie przeszukuje znaczne obszary dopuszczalnych wartości funkcji celu, znajdując rozwiązania optymalne. Właściwości te sugerują, że zaprezentowane rozwiązania mogą być przydatną metodą optymalizacyjną.

EN

The paper presents a computer algorithm optimization, called Algo-rithm "Small-Worlds" (ASW), that uses mechanism of search the space of feasible solutions the optimization problem based on the "small-worlds" phenomenon. In the algorithm the determination of local and distant contacts for the "small-world" network model, using theory of probability combined with positional numeral system is used. In order to validate the algorithm with respect to the theory of J.M. Kleinberg, conducted test by finding the shortest path between any two points in two-dimensional networks of different sizes [Tab. 1]. Benchmarks of algorithm (ASW) as compared with genetic algorithm (GA) for finding an extremum functions and polynomial coefficients are given. The tests results indicate [Tab. 2] that algorithm provides effective mechanisms to search large areas of the limit values objective function and finds optimal solution. These properties suggest that presented solutions can be a useful method for solving optimization problems.

Słowa kluczowe

PL

teoria "małych światów"; algorytm ewolucyjny; optymalizacja funkcji

EN

"small-worlds" phenomenon; evolutionary algorithm

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2011
• Tom: R. 57, nr 7
• Strony: 733--736
• Opis fizyczny: Bibliogr. 6 poz., rys., tab., wzory

Twórcy

autor

Bieś G.

• Komenda Powiatowa Policji w Dąbrowie Tarnowskiej, Berka Joselewicza 4, 33-200 Dąbrowa Tarnowska,

Bibliografia

• [1] Milgram S.: The Small World Problem. Psychology Today, 1967, pp. 60-67.
• [2] Kleinberg J.: Navigation in a small world. Nature, 406: 845, 2000.
• [3] Kleinberg J.: The Small-World Phenomenon: An Algorithmic Perspective. Cornell Computer Science Technical Report, 1999. 99-1776.
• [4] Haifeng Du, Jie Shao, Feldman Marcus W.: An Optimization Algorithm Based on the Small-World Phenomenon. 2008.
• [5] Watts, D. and Strogatz S. H.: Collective dynamics of 'small-world' networks. Nature. 393(4):440-42, 1998.
• [6] http://pl.wikipedia.org/wiki/System_liczbowy