Fuzzy Integer Linear Programming : a Genetic Algorithm

• Autorzy: Stefan Chanas , Adam Kasperski

Warianty tytułu

Rozmyte całkowitoliczbowe programowanie liniowe : algorytm genetyczny

• Języki publikacji: EN

Abstrakty

EN

The problem of fuzzy integer programming is considered, in which all the coefficients are fuzzy numbers of the L-R type. As the solution concept the approach of Tong is adopted, proposed in [8] for the problem with real decision variables. That approach is not only extended to the case of integer decision variables here, but also generalised to allow any (not only regular) shapes of the fuzzy coefficients as well as other fuzzy preference relations (not only the one based on the possibility measure) for comparing objective function values. Three algorithms for solving the problem are proposed. The first algorithm is genetic, the second is based on the tabu search idea and the third algorithm (the most effective one) is a combination of the two previous ones. The paper presents also the results of a computational experiment conducted on an exemplary model with 12 variables and 10 constructions. (original abstract)

Przeanalizowano problem całkowitoliczbowego programowania liniowego z rozmytymi współczynnikami reprezentowanymi przez liczby rozmyte typu L-R . Za koncepcję rozwiązania przyjęto propozycję Tonga [8], którą przystosowano do dyskretnych zmiennych decyzyjnych, a także uogólniono w ten sposób, by do reprezentacji rozmytych współczynników w problemie można było stosować rozmyte liczby o dowolnym, nie tylko trójkątnym, kształcie. Do porównywania rozmytych wielkości można używać jedną z czterech różnych rozmytych relacji preferencji (Tong w swojej koncepcji stosował jedynie relację opartą na mierze możliwości). Zaproponowano trzy heurystyczne algorytmy rozwiązania: algorytm genetyczny "tabu search" oraz algorytm będący kombinacją dwóch poprzednich algorytmów. Przedstawiono także wyniki eksperymentu obliczeniowego, przeprowadzonego na problemie 12 zmiennymi decyzyjnymi i 10 ograniczeniami. (abstrakt oryginalny)

Słowa kluczowe

EN

Algorithms; Genetic algorithms; Linear programming

PL

Algorytmy; Algorytmy genetyczne; Programowanie liniowe

• Czasopismo: Badania Operacyjne i Decyzje
• Rocznik: 2001
• Numer: nr 1
• Strony: 21--39

Twórcy

autor

Stefan Chanas

• Politechnika Wrocławska

autor

Adam Kasperski

• Politechnika Wrocławska

Bibliografia

• [1] BELLMAN R.E., ZADEH L.A., Decision-making in fuzzy environment, Management Science B 17, (1970), 141-164 I.
• [2] CHANAS S., On interval and fuzzy number linear programming, Institute of Industrial Engineering and Management, Technical University of Wrocław, Raport PRE nr 60, Wrocław 1995.
• [3] CHANAS S., DELGADO M., VERDEGAY J.L., VILA M.A., Ranking fuzzy numbers in the setting of random sets, Information Sciences, 69 (1993), 201-217.
• [4] DUBOIS D., PRADE H., Operations on fuzzy numbers. Int. J. Systems Science, 30 (1978), 613-626.
• [5] Dubois D., PRADE H., Ranking fuzzy numbers in the setting of possibility theory, Information Sciences, 30 (1983), 183-224.
• [6] KASPERSKI A., Wybrane problemy optymalizacji dyskretnej z nieprecyzyjnie określonymi parametrami, Technical University of Wrocław, M.Sc. Thesis, 1998.
• [7] MICHALEWICZ Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, 1996.
• [8] TONG S., Interval number and fuzzy number linear programmings, Fuzzy Sets and Systems, 66 (1994).
• [9] Young-Jou Lai, Ching-Lai Hwang, Fuzzy Mathematical Programming. Methods and Applications, Lecture Notes in Economics and Mathematical Sciences 394, Springer-Verlag, 1992.
• [10] ZADEH L.A., The concept of a linguistic variable and its application to approximate reasoning I, II, III, Inform. Sci., 8 (1975), 199-249; 301-357; 9 43-80.