Warunkowa wartość oczekiwana funkcji celu w konstrukcji algorytmów przybliżonych dla zagadnień permutacyjnych

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

Warianty tytułu

EN

Conditional expected value of objective function in approximate algorithms for pemutational problems

• Języki publikacji: PL

Abstrakty

PL

W artykule zaprezentowano rezultaty prac nad zaawansowanymi algorytmami ewolucyjnymi stosowanymi w optymalizacji zagadnień permutacyjnych. Wprowadzenie dodatkowego parametru - warunkowej wartości oczekiwanej funkcji celu pozwala na ocenę jakości rozwiązań częściowo ustalonych. Może być on stosowany jako pomocnicze kryterium wyboru i konstrukcji nowych rozwiązań, w celu poprawy efektywności projektowanych algorytmów.

EN

This paper investigates an application of advanced evolutionary algorithms in optimization of permutation problems. The introduction of additional parameter in algorithms - the expected value of objective function - allows effective evaluation of quality of partially fixed solutions. The parameter can be used as auxiliary criterion for selection and construction of new solutions, increasing the effectiveness of designed algorithms.

Słowa kluczowe

PL

kwadratowe zagadnienie przydziału; QAP; algorytmy przybliżone; algorytmy ewolucyjne; warunkowa wartość oczekiwana funkcji celu

EN

quadratic assignment problem; QAP; approximate algorithms; evolutionary algorithms; conditional expected value of objective function

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2005
• Tom: T. 9, z. 1-2
• Strony: 47--56
• Opis fizyczny: Bibliogr. 11 poz., rys., wykr.

Twórcy

autor

Chmiel W.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

autor

Kadłuczka P.

• Katedra Automatyki, Akademia Górniczo-Hutnicza w Krakowie

Bibliografia

• [1] Chmiel W . , Kadłuczka P . : Zastosowanie warunkowej wartoœci oczekiwanej funkcji celu w konstrukcji algorytmów przybliżonych. Automatyzacja Procesów Dyskretnych, Optymalizacja Dyskretna , WNT, 2004, 17
• [2] Chmiel W . : Parametry charakteryzujące własności przestrzeni rozwiązań dla problemu QAP. Półrocznik AGH Automatyka , 2003, 7, 637
• [3] Filipowicz B . , Wala K . : Algorytmy optymalizacji kwadratowego zagadnienia przydziału. Kwart. AGH Elektrotechnika , 1992, 1
• [4] Chmiel W . : Algorytmy ewolucyjne w optymalizacji przydziału zadań z kwadratową funkcją celu. Kraków , AGH 2004 ( Praca doktorska )
• [ 5 ]Raghavan P . : Probabilistic construction of deterministic algorithms: approximating packing integer programs. J . Computer and System , 1988, 37, 130
• [6] Alon , N . , Ed ros P . , Spencer J . : The probabilistic method . New York , Willey 1992
• [7] Gutin G . , Yeo A . : Polynomial Algorithms for the TSP and the QAP with a Factorial Domination Number . Discrete Applied Mathematics , June 2002, 119, 107
• [8] Bac h E. , Shallit J . : Algorithmic number theory. Cambridge , MIT Press , MA 1996, 1
• [9] Gutin G . , Yeo A . : TSP heuristics with large domination number . Technical Report , No. 12/98, Dept. Maths and Stats. , Brunel University , 1998
• [10] Burkard R . E . , Karisch S . E . , Rend l F . : QAPLIB-A Quadratic Assignment Problem Library. E uropean Journal of Operational Resarch, 1991, 55 , 11 5
• [11] Kadłuczka P . , Chmiel W . : Efektywność algorytmu ewolucyjnego wykorzystującego warunkową wartość funkcji celu . Półrocznik AGH Automatyka , t. 9, z. 1–2, 2005 ,