Dobór parametrów w równoległych algorytmach genetycznych dla problemu plecakowego

• Autorzy: Anna Gryko-Nikitin

Warianty tytułu

Selection of Various Parameters of Parallel Evolutionary Algorithm for Knapsack Problems

• Języki publikacji: PL

Abstrakty

Celem artykułu jest prezentacja metodyki doboru parametrów równoległego algorytmu ewolucyjnego. Dobór parametrów zaprezentowany zostanie na przykładzie problemu plecakowego, którym może być przybliżony np. problem doboru akcji do koszyka inwestycyjnego. Dyskretny problem plecakowy należy do zadań optymalizacyjnych NP-trudnych o złożoności obliczeniowej określanej jako O(n2). Do zbioru metod rekomendowanych do rozwiązywania dyskretnego problemu plecakowego należą między innymi: algorytmy zachłanne, programowanie dynamiczne oraz wspomniane algorytmy ewolucyjne w wersji równoległej.(abstrakt oryginalny)

EN

The aim of the paper is the presentation of the methodology for selection of various parameters of parallel evolutionary algorithm. The selection process will be presented on the example of knapsack problem, which can be used for example for the problem of selection of investment shares to the cart. Discreet knapsack problem is one of the optimization tasks of NP-hard with computational complexity known as O (n2). The methods which are recommended for solving discrete knapsack problem are: greedy algorithms, dynamic programming, and mentioned above evolutionary algorithms in the parallel version.(original abstract)

Słowa kluczowe

PL

Taksonomia

EN

Taxonomy

• Czasopismo: Prace Naukowe Uniwersytetu Ekonomicznego we Wrocławiu. Taksonomia
• Rocznik: 2013
• Tom: 21
• Numer: nr 279 Klasyfikacja i analiza danych - teoria i zastosowania
• Strony: 301--310

Twórcy

autor

Anna Gryko-Nikitin

• Politechnika Białostocka

Bibliografia

• Aguirre H., Tanaka K., Sugimura T., Cooperative model for genetic operators to improve GAs, Proc. IEEE ICIIS 1999, pp. 98-109.
• Arabas J., Wykłady z algorytmów ewolucyjnych, Wyd. Naukowo-Techniczne, Warszawa 2001.
• Chan M.C., Wong C.C., Cheung B.K., Tang G.Y., Genetic algorithms in multi-stage portfolio optimization system. In proceedings of the eighth international conference of the Society for Computational Economics, Computing in Economics and Finance, Aix-en-Provence, France 2002.
• Chodak G., Kwaśnicki W., Zastosowanie algorytmów genetycznych w prognozowaniu popytu, "Gospodarka Materialowa & Logistyka" 2002, nr 4.
• Deb K., Agrawal S., Understanding interactions among genetic algorithm parameters, "Foundations of Genetic Algorithms" 1999, pp. 265-286.
• Eklund S.E., A massively parallel architecture fir distributed genetic algorithms, "Parallel Computing" 2004, vol. 30.
• Feder-Sempach E., Ryzyko inwestycyjne. Analiza polskiego rynku akcji, CeDeWu, Warszawa 2011.
• Fernandez-Prieto J.A., Canada-Bago J., Gadeo-Martos M.A., Velasco J.R., Optimisation of control parameters for genetic algorithms to test computer networks under realistic traffic loads, "Applied Soft Computing" 2011, 11(4), pp. 3744-3752.
• Goldberg D.E., Algorytmy genetyczne i ich zastosowanie, Wydawnictwo-Naukowo Techniczne, Warszawa 1995.
• Grefenstette J.J., Optimization of control parameters for genetic algorithms, Ieee Transactions on Systems, Man, and Cybernetics 1986, vol. SMC-16, no. 1.
• Kumar R., Banerjee N., Analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem, "Theoretical Computer Science" 2006, 358 , pp. 104-120.
• Lobo F.G., Goldberg D.E., The parameter-less genetic algorithm in practice, "Information Sciences" 2004, vol. 167.
• Michalewicz Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, Wyd. Naukowo- -Techniczne, Warszawa 1999.
• Sakurai Y., Takada K., Kawabe T., Tsuruta S., A metod to Control Parameters of Evolutionary Algorithms by using Reinforcement Learning, 2010 Sixth International Conference on Signal-Image Technology and Internet Based Systems, 2010 IEEE.
• Spillman R., Solving Large Knapsack Problems with a Genetic Algorithm, Systems, Man and Cybernetics, 1995. Intelligent Systems for the 21st Century, IEEE International Conference on, 1995, vol. 1, pp. 632-637.
• Taheri J., Sharif S., Xing P., Zomaya A.Y., Paralleled Genetic Algorithm for Solving the Knapsack Problem in the Cloud, P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), 2012 Seventh International Conference on, 2012 , pp. 303-308.
• Tarczyński W., Rynki kapitałowe. Metody ilościowe. Vol II, Agencja Wydawnicza "Placet", Warszawa 1997.
• Zhao T., Yang L., Man Z., A MSM-PGA based on multi-agent for solving 0-1 knapsack problem, [in:] Computer Science and Information Technology, 2008. ICCSIT'08. International Conference on. IEEE, 2008, pp. 898-902.