×

On random generation of fuzzy measures. (English) Zbl 1284.28013

Summary: In this paper we deal with the problem of obtaining a random procedure for generating fuzzy measures. We use the fact that the polytope of fuzzy measures is an order polytope, so that it has special properties that allow to build a uniform algorithm. First, we derive an exact procedure based on an existing procedure to generate random linear extensions; then, we study the applicability of this algorithm to the polytope of fuzzy measures, showing that the complexity grows dramatically with the cardinality of the referential set. Next, we study other heuristics appearing in the literature for the polytope of fuzzy measures; our results seem to mean that these procedures cannot be applied to this case either. Finally, we propose another heuristic that reduces the complexity and could be used instead of the other procedures. We finish comparing the performance of this heuristic with the other possibilities, showing that our alternative seems to work better for the polytope of fuzzy measures.

MSC:

28E10 Fuzzy measure theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beliakov, G.; Mesiar, R.; Valášková, L., Fitting generated aggregation operators to empirical data, Int. J. Uncertainty Fuzziness Knowl. Based Syst., 12, 2, 219-236 (2004) · Zbl 1073.28012
[3] Brightwell, G.; Winkler, P., Counting linear extensions, Order, 8, 3, 225-242 (1991) · Zbl 0759.06001
[4] Bubley, R.; Dyer, M., Faster random generation of linear extensions, Discrete Math., 20, 81-88 (1999) · Zbl 0934.65005
[5] Choquet, G., Theory of capacities, Ann. Inst. Fourier, 5, 131-295 (1953) · Zbl 0064.35101
[6] Combarro, E. F.; Miranda, P., Identification of fuzzy measures from sample data with genetic algorithms, Comput. Oper. Res., 33, 10, 3046-3066 (2006) · Zbl 1086.90069
[7] Combarro, E. F.; Miranda, P., Adjacency on the order polytope with applications to the theory of fuzzy measures, Fuzzy Sets Syst., 180, 384-398 (2010) · Zbl 1227.05035
[8] Dedekind, R., Über Zerlegungen von Zahlen durch ihre grössten gemeinsamen Teiler, Festschrift Hoch Braunschweig Ges. Werke, II, 103-148 (1897), (in German) · JFM 28.0186.04
[9] Denneberg, D., Non-Additive Measures and Integral (1994), Kluwer Academic: Kluwer Academic Dordrecht, The Netherlands · Zbl 0826.28002
[10] Devroye, L., Non-Uniform Random Variate Generation (1986), Springer-Verlag: Springer-Verlag New York · Zbl 0593.65005
[11] Grabisch, M.; Marichal, J.-L.; Mesiar, R.; Pap, E., Aggregation Functions (2009), Cambridge University Press
[13] Grabisch, M.; Nicolas, J.-M., Classification by fuzzy integral-performance and tests, Fuzzy Sets Syst. (Special Issue on Pattern Recognition), 65, 255-271 (1994)
[14] Huber, M., Fast perfect sampling from linear extensions, Discrete Math., 306, 2006, 420-428 (2006) · Zbl 1090.60064
[16] Karzanov, A.; Khachiyan, L., On the conductance of order Markov chains, Order, 8, 1, 7-15 (1995) · Zbl 0736.06002
[17] Koshevoy, G., Distributive lattices and product of capacities, J. Math. Anal. Appl., 219, 427-441 (1998) · Zbl 0910.06007
[18] Lee, K.-M.; Leekwang, H., Identification of \(\lambda \)-measures by genetic algorithms, Fuzzy Sets Syst., 75, 301-309 (1995) · Zbl 0867.68093
[19] Lerche, D.; Sörensen, P., Evaluation of the ranking probabilities for partial orders based on random linear extensions, Chemosphere, 53, 981-992 (2003)
[20] Lerche, D.; Sörensen, P.; Bruggemann, R., Improved estimation of the ranking probabilities in partial orders using random linear extensions by approximation of the mutual ranking probability, J. Chem. Inf. Comput. Sci., 43, 1471-1480 (2003)
[21] Leydold, J.; Hörmann, W., A sweep-plane algorithm for generating random tuples in simple polytopes, J. Math. Comput., 67, 1617-1635 (1998) · Zbl 0903.65003
[22] De Loof, K.; De Meyer, H.; De Baets, B., Exploiting the lattice of ideals representation of a poset, Fund. Inf., 71, 2,3, 309-321 (2006) · Zbl 1110.06001
[23] De Loof, K.; De Baets, B.; De Meyer, H., On the random generation and counting of weak order extensions of a poset with given class cardinalities, Inf. Sci., 177, 220-230 (2007) · Zbl 1111.06001
[24] De Loof, K.; De Baets, B.; De Meyer, H., On the random generation of monotone data sets, Inf. Process. Lett., 107, 216-220 (2008) · Zbl 1186.68568
[25] De Loof, K.; De Baets, B.; De Meyer, H.; Brüggemann, R., A guide to poset ranking, Combinatorial Chem. High Throughput Screening, 11, 734-744 (2008)
[26] De Loof, K.; De Baets, B.; De Meyer, H., Approximation of average ranks in posets, MATCH—Commun. Math. Comput. Chem., 66, 219-229 (2011) · Zbl 1265.05592
[27] Nourine, L.; Habib, M.; Medina, R.; Steiner, G., Efficient algorithms on distributive lattices, Discrete Appl. Math., 110, 169-187 (2001) · Zbl 0983.06009
[28] Matousek, J., Lectures on Discrete Geometry (2002), Springer-Verlag New York, Inc.: Springer-Verlag New York, Inc. Secaucus, NJ, USA · Zbl 0999.52006
[29] Miranda, P.; Combarro, E. F., On the structure of some families of fuzzy measures, IEEE Trans. Fuzzy Syst., 15, 6, 1068-1081 (2007)
[30] Miranda, P.; Grabisch, M.; Gil, P., p-Symmetric fuzzy measures, Int. J. Uncertainty Fuzziness Knowl. Based Syst., 10, Suppl., 105-123 (2002) · Zbl 1068.28013
[31] Miranda, P.; Grabisch, M.; Gil, P., Identification of non-additive measures from sample data, (Kruse, R.; Della Riccia, G.; Dubois, D.; Lenz, H.-J., Planning Based on Decision Theory, CISM Courses and Lectures, vol. 472 (2003), Springer Verlag), 43-63 · Zbl 1390.62007
[32] Rubinstein, R. Y.; Kroese, D. P., Simulation and the Monte Carlo Method (2007), Wiley
[34] Stanley, R., Two poset polytopes, Discrete Comput. Geom., 1, 1, 9-23 (1986) · Zbl 0595.52008
[37] Valiant, L., The complexity of enumerating and reliability problems, SIAM J. Comput., 8, 410-421 (1979) · Zbl 0419.68082
[38] Wierzchoń, S. T., An algorithm for identification of fuzzy measures, Fuzzy Sets Syst., 9, 69-78 (1983) · Zbl 0504.28012
[39] Wilson, D. B., Mixing times of lozenge tiling and card shuffling Markov chains, Ann. Appl. Probab., 14, 1, 274-325 (2004) · Zbl 1040.60063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.