## Software: ## (c) Vicenç Torra ## Current version: 20230316 ## ## Software for non-additive measures and integrals ## (these measures are also known as fuzzy measures, monotonic games, ## and include belief functions, k-additive measures, ## distorted probabilities) ## Software includes Choquet and Sugeno integrals, ## measure identification from examples, Shapley values, indices, etc. ## File with examples. ## ## This software is about the optimal transport problem for non-additive measures. ## Use the following reference for this paper: ## V. Torra, The transport problem for non-additive measures, ## European Journal of Operational Research, 2023 ## https://doi.org/10.1016/j.ejor.2023.03.016 ## ## References on aggregation functions and non-additive measures: ## V. Torra, Y. Narukawa (2007) Modeling Decisions, Springer. ## V. Torra, Y. Narukawa, M. Sugeno (eds.) (2013) ## Non-additive measures: theory and applications, Springer. ## On the (max, \oplus)-transform: ## V. Torra, (Max,\oplus)-transforms and genetic algorithms for ## fuzzy measure identification, Fuzzy Sets and Systems 451 (2022) 253-265 ## https://doi.org/10.1016/j.fss.2022.09.008 ## ## exec(open("prog.vectors.matrices.web.txt").read()) ## exec(open("prog.choquet.web.txt").read()) ## exec(open("prog.transport.web.txt").read()) ## ## EXAMPLES AND CALCULATIONS ----------------------------- ## ## ## Additive measures fmX = [0.0,0.2,0.3,0.5,0.5,0.7,0.8,1.0] fmY = [0.0,0.2,0.2,0.4,0.6,0.8,0.8,1.0] fmXMxT = fromFM2MaxSum (fmX, 3) fmYMxT = fromFM2MaxSum (fmY, 3) fmXMoT = fromFM2Moebius (fmX, 3) fmYMoT = fromFM2Moebius (fmY, 3) fmXp = [0.0,0.5,0.3,0.8,0.2,0.7,0.5,1.0] ## Same as fmX but different order fmXpMxT = fromFM2MaxSum (fmXp, 3) ## [0, 0.5, 0.3, 0.3, 0.2, 0.2, 0.2, 0.2] ## ciShapley(fmXp,3) ## [0.19999999999999998, 0.3, 0.5] ## fromFM2Moebius(fmXp,3 ) ## [0, 0.5, 0.3, 0.0, 0.2, 0.0, 0.0, 0.0] ## Cost tables and functions fmtCostPr21XY = [[0,5,5],[5,0,5],[5,5,0]] fmtTCostEx10 = fmtBuildCostTable (fmtCostEx10, 3, 3) fmtTCostPr21 = fmtBuildCostTable (fmtCostPr21(fmtCostPr21XY), 3, 3) fmtTCostPr21p = fmtBuildCostTable (fmtCostEx10, 3, 3) ## Optimal transport and Wasserstein distance with Max-Sum transform solMxEx10 = fmtOptimalTransport(fmtTCostEx10,fmXMxT,3,fmYMxT,3) solMxPr21 = fmtOptimalTransport(fmtTCostPr21,fmXMxT,3,fmYMxT,3) ## Assignments in table form latexTableEx10 = fmtFromAssign2TabLatex (solMxEx10['x'], 3, fmX, fmXMxT, 3, fmY, fmYMxT) latexTablePr21 = fmtFromAssign2TabLatex (solMxPr21['x'], 3, fmX, fmXMxT, 3, fmY, fmYMxT) ## print(latexTableEx10) ## print(latexTablePr21) # solMxPr21['x'] - solMxEx10['x'] wDisMxEx10 = fmtWassersteinDistance(fmtTCostEx10,fmXMxT,3,fmYMxT,3) # 0.19999999999999996 wDisMxPr21 = fmtWassersteinDistance(fmtTCostPr21,fmXMxT,3,fmYMxT,3) # 0.4999999999999999 ## The following is equivalent to the Wasserstein distance: assg*cost ## waDMxEx10 = vectorProduct(solMxEx10['x'], fmtTCostEx10) # 0.19999999999999996 ## waDMxPr21 = vectorProduct(solMxPr21['x'], fmtTCostPr21) # 0.4999999999999999 ## For additive measures, we can use the Mobius transform. OT + Wasserstein distance solMoEx10 = fmtOptimalTransport(fmtTCostEx10,fmXMoT,3,fmYMoT,3) wDisMxEx10Mo = fmtWassersteinDistance(fmtTCostEx10,fmXMoT,3,fmYMoT,3) # 0.09999999999999998 ## The following is equivalent to above: assgn*cost ## waDMxEx10 = vectorProduct(solMoEx10['x'], fmtTCostEx10) # 0.09999999999999998 ## Examples using measures using Def. 23 (Torra, EJOR, 2023) costTX_X = fmtCostMeasure (fmXMxT, 3, fmXMxT, 3, [[0,1,2],[1,0,1],[2,1,0]], 1) costTY_Y = fmtCostMeasure (fmYMxT, 3, fmYMxT, 3, [[0,1,2],[1,0,1],[2,1,0]], 1) costTX_Y = fmtCostMeasure (fmXMxT, 3, fmYMxT, 3, [[0,1,2],[1,0,1],[2,1,0]], 1) costTXpY = fmtCostMeasure (fmXpMxT, 3, fmYMxT, 3, [[0,1,2],[1,0,1],[2,1,0]], 1) sol_TX_Y = fmtOptimalTransport(costTX_Y,fmXMxT,3,fmYMxT,3) sol_TXpY = fmtOptimalTransport(costTXpY,fmXpMxT,3,fmYMxT,3) tLt_TX_Y = fmtFromAssign2TabLatex (sol_TX_Y['x'], 3, fmX, fmXMxT, 3, fmY, fmYMxT) tLt_TXpY = fmtFromAssign2TabLatex (sol_TXpY['x'], 3, fmXp, fmXpMxT, 3, fmY, fmYMxT) wsD_TX_X = fmtWassersteinDistance (costTX_X,fmXMxT,3,fmXMxT,3) wsD_TY_Y = fmtWassersteinDistance (costTY_Y,fmYMxT,3,fmYMxT,3) wsD_TX_Y = fmtWassersteinDistance (costTX_Y,fmXMxT,3,fmYMxT,3) wsD_TXpY = fmtWassersteinDistance (costTXpY,fmXpMxT,3,fmYMxT,3) costG_Y = fmtCostMeasure (fmG, 3, fmY, 3, [[0,1,2],[1,0,1],[2,1,0]], 1) ## Example: case1 ## 000,001,010,011,100,101,110,111 fmXc1 = [ 0.0, 1.0, 1.0, 1.0, 0.0, 1.0, 1.0, 1.0] fmYc1 = [ 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0, 1.0] ## Optimal transport for these measures, Max-Sum transform fmXc1MxT = fromFM2MaxSum (fmXc1, 3) fmYc1MxT = fromFM2MaxSum (fmYc1, 3) solc1MxT = fmtOptimalTransport(fmtTCostEx10,fmXc1MxT,3,fmYc1MxT,3) ## print(fmtFromAssign2TabLatex (solc1MxT['x'], 3, fmXc1, fmXc1MxT, 3, fmYc1, fmYc1MxT)) ## Same with Mobius transform, but as it has negative values, solution is not good fmXc1MoT = fromFM2Moebius (fmXc1, 3) fmYc1MoT = fromFM2Moebius (fmYc1, 3) ## solc1MoT = fmtOptimalTransport(fmtTCostEx10,fmXc1MoT,3,fmYc1MoT,3) ## print(fmtFromAssign2TabLatex (solc1MoT['x'], 3, fmXc1, fmXc1MoT, 3, fmYc1, fmYc1MoT)) ## Example: case2 ## 0000,0001,0010,0011,0100,0101,0110,0111, 1000,1001,1010,1011,1100,1101,1110,1111 fmXc2 = [ 0.0, 1.0, 1.0, 1.0, 0.0, 1.0, 1.0, 1.0, 0.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0] fmYc2 = [ 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0] ## Optimal transport for these measures, Max-Sum transform fmXc2MxT = fromFM2MaxSum (fmXc2, 4) fmYc2MxT = fromFM2MaxSum (fmYc2, 4) solc2MxT = fmtOptimalTransport(fmtBuildCostTable(fmtCostEx10, 4, 4),fmXc2MxT,4,fmYc2MxT,4) ## print(fmtFromAssign2TabLatex (solc2MxT['x'], 4, fmXc2, fmXc2MxT, 4, fmYc2, fmYc2MxT)) ## Same with Mobius transform, but as it has negative values, solution is not good fmXc2MoT = fromFM2Moebius (fmXc2, 4) fmYc2MoT = fromFM2Moebius (fmYc2, 4) ## solc2MoT = fmtOptimalTransport(fmtBuildCostTable(fmtCostEx10, 4, 4),fmXc2MoT,4,fmYc2MoT,4) ## print(fmtFromAssign2TabLatex (solc2MoT['x'], 4, fmXc2, fmXc2MoT, 4, fmYc2, fmYc2MoT))