A two - phase - ACO algorithm for solving nonlinear optimization problems subjected to fuzzy relational equations

Ghodousian, Amin; Zal, Sara

doi:10.22111/ijfs.2024.49652.8760

Document Type : Research Paper

Authors

Faculty of Engineering Science, College of Engineering, University of Tehran, P.O.Box 11365-4563, Tehran, Iran.

https://doi.org/10.22111/ijfs.2024.49652.8760

Abstract

In this paper, we investigate nonlinear optimization problems whose constraints are defined as fuzzy relational equations (FRE) with max-min composition. Since the feasible solution set of the FRE is often a non-convex set and the resolution of the FREs is an NP-hard problem, conventional nonlinear approaches may involve high computational complexity. Based on the theoretical aspects of the problem, an algorithm (called FRE-ACO algorithm) is presented which benefits from the structural properties of the FREs, the ability of discrete ant colony optimization algorithm (denoted by ACO) to tackle combinatorial problems, and that of continuous ant colony optimization algorithm (denoted by ACOR) to solve continuous optimization problems. In the current method, the fundamental ideas underlying ACO and ACOR are combined and form an efficient approach to solve the nonlinear optimization problems constrained with such non-convex regions. Moreover, FRE-ACO algorithm preserves the feasibility of new generated solutions without having to initially find the minimal solutions of the feasible region or check the feasibility after generating the new solutions. The FRE-ACO algorithm has been compared with some related works proposed for solving nonlinear
optimization problems with respect to max-min FREs. The obtained results demonstrate that the proposed algorithm has a higher convergence rate and requires a less number of function evaluations compared to other considered algorithms.

Keywords

Main Subjects

Optimization

References

[1] M. S. Bazaraa, H. D. Sherali, C. M. Shetty, Nonlinear programming: Theory and algorithms, John Wiley and Sons,
New York, NY, 2006. https://doi.org/10.1002/0471787779

[2] M. M. Bourke, D. G. Fisher, Solution algorithms for fuzzy relational equations with max-product composition, Fuzzy
Sets and Systems, 94 (1998), 61-69. https://doi.org/10.1016/S0165-0114(96)00246-1

[3] C. W. Chang, B. S. Shieh, Linear optimization problem constrained by fuzzy max-min relation equations, Information
Sciences, 234 (2013), 71-79. https://doi.org/10.1016/j.ins.2011.04.042

[4] L. Chen, P. P.Wang, Fuzzy relation equations (ii): The branch-point-solutions and the categorized minimal solutions,
Soft Computing, 11(2) (2007), 33-40. https://doi.org/10.1007/s00500-006-0050-1

[5] S. Dempe, A. Ruziyeva, On the calculation of a membership function for the solution of a fuzzy linear optimization
problem, Fuzzy Sets and Systems, 188 (2012), 58-67. https://doi.org/10.1016/j.fss.2011.07.014

[6] F. Di Martino, V. Loia, S. Sessa, Digital watermarking in coding/decoding processes with fuzzy relation equations,
Soft Computing, 10 (2006), 238-243. https://doi.org/10.1007/s00500-005-0477-9

[7] A. Di Nola, S. Sessa, W. Pedrycz, E. Sanchez, Fuzzy relational equations and their applications in knowledge
engineering, Dordrecht: Kluwer Academic Press, 1989. https://doi.org/10.1007/978-94-017-1650-5

[8] M. Dorigo, V. Maniezzo, A. Colorni, Ant system: Optimization by a colony of cooperating agents, IEEE Transactions
on Systems, Man and Cybernetics, 26(1) (1996), 29-41. https://doi.org/10.1109/3477.484436

[9] D. Dubey, S. Chandra, A. Mehra, Fuzzy linear programming under interval uncertainty based on IFS representation,
Fuzzy Sets and Systems, 188 (2012), 68-87. https://doi.org/10.1016/j.fss.2011.09.008

[10] A. ElSaid, F. El Jamiy, J. Higgins, B. Wild, T. Desell, Optimizing long short-term memory recurrent neural
networks using ant colony optimization to predict turbine engine vibration, Applied Soft Computing, 73 (2018),
969-991. https://doi.org/10.1016/j.asoc.2018.09.013

[11] Y. R. Fan, G. H. Huang, A. L. Yang, Generalized fuzzy linear programming for decision making under uncertainty:
Feasibility of fuzzy solutions and solving approach, Information Sciences, 241 (2013), 12-27. https://doi.org/10.
1016/j.ins.2013.04.004

[12] S. C. Fang, G. Li, Solving fuzzy relation equations with a linear objective function, Fuzzy Sets and Systems, 103
(1999), 107-113. https://doi.org/10.1016/S0165-0114(97)00184-X

[13] S. Freson, B. De Baets, H. De Meyer, Linear optimization with bipolar max-min constraints, Information Sciences,
234 (2013), 3-15. https://doi.org/10.1016/j.ins.2011.06.009

[14] A. Ghodousian, Optimization of linear problems subjected to the intersection of two fuzzy relational inequalities
defined by Dubois-Prade family of t-norms, Information Sciences, 503 (2019), 291-306. https://doi.org/10.1016/
j.ins.2019.06.058

[15] A. Ghodousian, A. Babalhavaeji, An effcient genetic algorithm for solving nonlinear optimization problems defined
with fuzzy relational equations and max- Lukasiewicz composition, Applied Soft Computing, 69 (2018), 475-492.
https://doi.org/10.1016/j.asoc.2018.04.029

[16] A. Ghodousian, M. S. Chopannavaz, Solving linear optimization problems subject to bipolar fuzzy relational equalities
defined with max-strict compositions, Information Sciences, 650 (2023), 119696. https://doi.org/10.1016/
j.ins.2023.119696

[17] A. Ghodousian, E. Khorram, Fuzzy linear optimization in the presence of the fuzzy relation inequality constraints
with max-min composition, Information Sciences, 178 (2008), 501-519. https://doi.org/10.1016/j.ins.2007.
07.022

[18] A. Ghodousian, E. Khorram, Linear optimization with an arbitrary fuzzy relational inequality, Fuzzy Sets and
Systems, 206 (2012), 89-102. https://doi.org/10.1016/j.fss.2012.04.009

[19] A. Ghodousian, M. Naeeimib, A. Babalhavaeji, Nonlinear optimization problem subjected to fuzzy relational equations
defined by Dubois-Prade family of t-norms, Computers and Industrial Engineering, 119 (2018), 167-180.
https://doi.org/10.1016/j.cie.2018.03.038

[20] A. Ghodousian, M. Raeisian Parvari, A modified PSO algorithm for linear optimization problem subject to the
generalized fuzzy relational inequalities with fuzzy constraints (FRI-FC), Information Sciences, 418-419 (2017),
317-345. https://doi.org/10.1016/j.ins.2017.07.032

[21] A. Ghodousian, B. Sepehri Rad, O. Ghodousian, A non-linear generalization of optimization problems subjected to
continuous max-t-norm fuzzy relational inequalities, Soft Computing, 28 (2024), 4025-4036. https://doi.org/10.
1007/s00500-023-09376-2

[22] A. Ghodousian, F. S. Yousefi, Linear optimization problem subjected to fuzzy relational equations and fuzzy constraints, Iranian Journal of Fuzzy Systems, 20(2) (2023), 1-20. https://doi.org/10.22111/IJFS.2023.7552

[23] F. F. Guo, Z. Q. Xia, An algorithm for solving optimization problems with one linear objective function and
finitely many constraints of fuzzy relation inequalities, Fuzzy Optimization and Decision Making, 5 (2006), 33-47.
https://doi.org/10.1007/s10700-005-4914-0

[24] S. M. Guu, Y. K. Wu, Minimizing a linear objective function with fuzzy relation equation constraints, Fuzzy
Optimization and Decision Making, 12 (2002), 1568-4539. https://doi.org/10.1023/A:1020955112523

[25] S. M. Guu, Y. K. Wu, Minimizing a linear objective function under a max-t-norm fuzzy relational equation constraint,
Fuzzy Sets and Systems, 161 (2010), 285-297. https://doi.org/10.1016/j.fss.2009.03.007

[26] M. Higashi, G. J. Klir, Resolution of finite fuzzy relation equations, Fuzzy Sets and Systems, 13 (1984), 65-82.
https://doi.org/10.1016/0165-0114(84)90026-5

[27] K. Krynicki, J. Jaen, E. Navarro, An ACO-based personalized learning technique in support of people with acquired
brain injury, Applied Soft Computing, 47 (2016), 316-331. https://doi.org/10.1016/j.asoc.2016.04.039

[28] H. C. Lee, S. M. Guu, On the optimal three-tier multimedia streaming services, Fuzzy Optimization and Decision
Making, 2(1) (2002), 31-39. https://doi.org/10.1023/A:1022848114005

[29] P. K. Li, S. C. Fang, On the resolution and optimization of a system of fuzzy relational equations with sup-t composition, Fuzzy Optimization and Decision Making, 7 (2008), 169-214. https://doi.org/10.1007/s10700-008-9029-y

[30] P. Li, Y. Liu, Linear optimization with bipolar fuzzy relational equation constraints using Lukasiewicz triangular
norm, Soft Computing, 18 (2014), 1399-1404. https://doi.org/10.1007/s00500-013-1152-1

[31] P. Li, Y. Wang, A matrix approach to latticized linear programming with fuzzy-relation inequality constraints, IEEE
Transactions on Fuzzy Systems, 21 (2013), 781-788. https://doi.org/10.1109/TFUZZ.2012.2232932

[32] C. H. Lin, A rough penalty genetic algorithm for constrained optimization, Information Science (NY), 241 (2013),
119-137. https://doi.org/10.1016/j.ins.2013.04.001

[33] J. L. Lin, Y. K. Wu, S. M. Guu, On fuzzy relational equations and the covering problem, Information Science, 181
(2011), 2951-2963. https://doi.org/10.1016/j.ins.2011.03.004

[34] J. Liu, J. Liu, Applying multi-objective ant colony optimization algorithm for solving the unequal area facility layout
problems, Applied Soft Computing, 74 (2019), 167-189. https://doi.org/10.1016/j.asoc.2018.10.012

[35] C. C. Liu, Y. Y. Lur, Y. K. Wu, Linear optimization of bipolar fuzzy relational equations with max- Lukasiewicz
composition, Information Sciences, 360 (2016), 149-162. https://doi.org/10.1016/j.ins.2016.04.041

[36] D. Lobo, V. Lopez-Marchante, J. Medina, On measuring the solvability of a fuzzy relation equation, In: M. Cornejo,
L. T. K’oczy, J. Medina, E. Ram’ırez-Poussa, (eds) Computational Intelligence and Mathematics for Tackling

Complex Problems 5. Studies in Computational Intelligence, 1127. Springer, Cham, (2024). https://doi.org/10.
1007/978-3-031-46979-4

[37] J. Loetamonphong, S. C. Fang, Optimization of fuzzy relation equations with max-product composition, Fuzzy Sets
and Systems, 118 (2001), 509-517. https://doi.org/10.1016/S0165-0114(98)00417-5

[38] J. Lu, S. C. Fang, Solving nonlinear optimization problems with fuzzy relation equations constraints, Fuzzy Sets
and Systems, 119 (2001), 1-20. https://doi.org/10.1016/S0165-0114(98)00471-0

[39] L. C. Lu, T. W. Yue, Mission-oriented ant-team ACO for min-max MTSP, Applied Soft Computing, 76 (2019),
436-444. https://doi.org/10.1016/j.asoc.2018.11.048

[40] J. Lv, X. Wang, M. Huang, ACO-inspired ICN routing mechanism with mobility support, Applied Soft Computing,
58 (2017), 427-440. https://doi.org/10.1016/j.asoc.2017.04.040

[41] A. V. Markovskii, On the relation between equations with max-product composition and the covering problem, Fuzzy
Sets and Systems, 153 (2005), 261-273. https://doi.org/10.1016/j.fss.2005.02.010

[42] Z. Matusiewicz, J. Drewniak, Increasing continuous operations in fuzzy max-* equations and inequalities, Fuzzy
Sets and Systems, 232 (2013), 120-133. https://doi.org/10.1016/j.fss.2013.03.009

[43] M. Mizumoto, H. J. Zimmermann, Comparison of fuzzy reasoning method, Fuzzy Sets and Systems, 8 (1982),
253-283. https://doi.org/10.1016/S0165-0114(82)80004-3

[44] H. Nobuhara, K. Hirota, F. Di Martino, W. Pedrycz, S. Sessa, Fuzzy relation equations for compression/
decompression processes of color images in the RGB and YUV color spaces, Fuzzy Optimization and Decision
Making, 4 (2005), 235-246. https://doi.org/10.1007/s10700-005-1892-1

[45] W. Pedrycz, On generalized fuzzy relational equations and their applications, Journal of Mathematical Analysis
and Applications, 107 (1985), 520-536. https://doi.org/10.1016/0022-247X(85)90329-4

[46] W. Pedrycz, Granular computing: Analysis and design of intelligent systems, CRC Press, Boca Raton, 2013.
https://doi.org/10.1201/b14862

[47] W. Pedrycz, A. V. Vasilakos, Modularization of fuzzy relational equations, Soft Computing, 6 (2002), 3-37. https:
//doi.org/10.1007/s005000100125

[48] K. Peeva, Resolution of fuzzy relational equations-methods, algorithm and software with applications, Information
Sciences, 234 (2013), 44-63. https://doi.org/10.1016/j.ins.2011.04.011

[49] S. Perez-Carabaza, E. Besada-Portas, J. A. Lopez-Orozco, J. M. de la Cruz, Ant colony optimization for multi-UAV
minimum time search in uncertain domains, Applied Soft Computing, 62 (2018), 789-806. https://doi.org/10.
1016/j.asoc.2017.09.009

[50] I. Perfilieva, Fuzzy function as an approximate solution to a system of fuzzy relation equations, Fuzzy Sets and
Systems, 147 (2004), 363-383. https://doi.org/10.1016/j.fss.2003.12.007

[51] I. Perfilieva, Finitary solvability conditions for systems of fuzzy relation equations, Information Sciences, 234 (2013),
29-43. https://doi.org/10.1016/j.ins.2011.04.035

[52] I. Perfilieva, V. Nov´ak, System of fuzzy relation equations model of IF-THEN rules, Information Sciences, 177(16)
(2007), 3218-3227. https://doi.org/10.1016/j.ins.2006.11.006

[53] D. Praveen Kumar, A. Tarach, A. Chandra Sekhara Rao, ACO-based mobile sink path determination for wireless
sensor networks under non-uniform data constraints, Applied Soft Computing, 69 (2018), 528-540. https://doi.
org/10.1016/j.asoc.2018.05.008

[54] X. B. Qu, X. P. Wang, M. H. Lei, Conditions under which the solution sets of fuzzy relational equations over
complete Brouwerian lattices form lattices, Fuzzy Sets and Systems, 234 (2014), 34-45. https://doi.org/10.
1016/j.fss.2013.03.017

[55] W. Rudin, Principles of mathematical analysis, New York: McGraw-Hill, 1976.

[56] E. Sanchez, Resolution of composite fuzzy relation equations, Information and Control, 30 (1976), 38-48. https:
//doi.org/10.1016/S0019-9958(76)90446-0

[57] E. Sanchez, Solution in composite fuzzy relation equations: Application to medical diagnosis in Brouwerian logic,
in: M. M. Gupta. G. N. Saridis, B. R. Games (Eds.), Fuzzy Automata and Decision Processes, North-Holland, New
York, (1977), 221-234. https://doi.org/10.1016/B978-1-4832-1450-4.50017-1

[58] B. S. Shieh, Minimizing a linear objective function under a fuzzy max-t-norm relation equation constraint, Information
Sciences, 181 (2011), 832-841. https://doi.org/10.1016/j.ins.2010.10.024

[59] K. Socha, M. Dorigo, Ant colony optimization for continuous domain, European Journal of Operational Research,
185 (2008), 1155-1173. https://doi.org/10.1016/j.ejor.2006.06.046

[60] I. Stankovi´c, Z. Jan˘ci´c, M. ´Ciri´c, I. Mici´c, S. Stanimirovi´c, Two-mode weakly linear systems of fuzzy relation
equations: Structures of solutions, computation methods, and applications, Information Sciences, 686 (2025), 121319.
https://doi.org/10.1016/j.ins.2024.121319

[61] F. Sun, X. P. Wang, X. B. Qu, Minimal join decompositions and their applications to fuzzy relation equations over
complete Brouwerian lattices, Information Sciences, 224 (2013), 143-151. https://doi.org/10.1016/j.ins.2012.
10.038

[62] P. Z. Wang, Latticized linear programming and fuzzy relation inequalities, Journal of Mathematical Analysis and
Applications, 159(1) (1991), 72-87. https://doi.org/10.1016/0022-247X(91)90222-L

[63] Y. K. Wu, Optimization of fuzzy relational equations with max-av composition, Information Sciences, 177 (2007),
4216-4229. https://doi.org/10.1016/j.ins.2007.02.037

[64] Y. K. Wu, S. M. Guu, A note on fuzzy relation programming problems with max-strict-t-norm composition, Fuzzy
Optimization and Decision Making, 3 (2004), 271-278. https://doi.org/10.1023/B:FODM.0000036862.45420.ea

[65] Y. K. Wu, S. M. Guu, Minimizing a linear function under a fuzzy max-min relational equation constraints, Fuzzy
Sets and Systems, 150 (2005), 147-162. https://doi.org/10.1016/j.fss.2004.09.010

[66] Y. K. Wu, S. M. Guu, An efficient procedure for solving a fuzzy relation equation with max-Archimedean t-norm
composition, IEEE Transactions on Fuzzy Systems, 16 (2008), 73-84. https://doi.org/10.1109/TFUZZ.2007.
902018

[67] Y. K. Wu, S. M. Guu, J. Y. Liu, Reducing the search space of a linear fractional programming problem under fuzzy
relational equations with max-Archimedean t-norm composition, Fuzzy Sets and Systems, 159 (2008), 3347-3359.
https://doi.org/10.1016/j.fss.2008.04.007

[68] Q. Q. Xiong, X. P. Wang, Fuzzy relational equations on complete Brouwerian lattices, Information Sciences, 193
(2012), 141-152. https://doi.org/10.1016/j.ins.2011.12.030

[69] Y. Yan, H. S. Sohn, G. Reyes, A modified ant system to achieve better balance between intensification and diversification for the traveling salesman problem, Applied Soft Computing, 60 (2017), 256-267. https://doi.org/10.
1016/j.asoc.2017.06.049

[70] X. P. Yang, X. G. Zhou, B. Y. Cao, Single-variable term semi-latticized fuzzy relation geometric programmingwith
max-product operator, Information Sciences, 325 (2015), 271-287. https://doi.org/10.1016/j.ins.2015.07.015

[71] X. P. Yang, X. G. Zhou, B. Y. Cao, Latticized linear programming subject to max-product fuzzy relation inequalities
with application in wireless communication, Information Sciences, 358-359 (2016), 44-55. https://doi.org/10.
1016/j.ins.2016.04.014

[72] X. P. Yang, X. G. Zhou, B. Y. Cao, Min-max programming problem subject to addition-min fuzzy relation inequalities,
IEEE Transactions on Fuzzy Systems, 24(1) (2016), 111-119. https://doi.org/10.1109/TFUZZ.2015.
2428716

A two - phase - ACO algorithm for solving nonlinear optimization problems subjected to fuzzy relational equations

References

References

Volume 21, Issue 5September and October 2024Pages 151-174

Volume 21, Issue 5
September and October 2024
Pages 151-174