Granular Computing Approach for Handling Uncertainty in Optimization Problems

Authors:

Assem Ahmed Alsawy (The Agricultural Research Center ((ARC), Giza, Egypt)

Hesham Ahmed Hefny (ISSR-Cairo University, Giza, Egypt)

Keywords: Optimization, Granularity, Granular Computing, Unified Granular Number, Fuzzy Set, Interval, Rough Set, Uncertainty, TSP, Dijkstra’s Algorithm.

Abstract:

Optimization problems got a lot of attention from many researchers; in real world application, there is always uncertainty in problem specification, interval numbers, fuzzy numbers, and rough numbers play important roles in representing uncertain quantities but these heterogeneous types of numbers are forming a challenge in computation. This paper proposes a Unified Granular Number (UGN) that we call G- Number to act as a general form for any uncertain number. G- Number represents higher level of abstract that hold only common properties of different types of uncertain granular numbers while ignoring some particular properties which are not necessary to be considered in such higher abstract level. This paper shows a solution for Uncertain Traveling Salesman Problem (UTSP) also shows a modification for Dijkstra’s algorithm to manipulate different uncertain numbers by applying the idea of G- number; the main benefit of using such a proposed G- number is the ability to represent all types of uncertain numbers using unified formality that greatly simplifies arithmetic operations. The results are compared to the solutions in crisp cases.

References:

[1]. Young, R.C.,” The algebra of many-valued quantities”, Annals of Mathematics, 31, pp. 260–290 (1931).

[2]. Moore, R.E.,” Method and Application of Interval Analysis”, Prentice Hall, London (1979).

[3]. Zadeh, L.A.,” Fuzzy sets”, Information and Control 8, pp. 338–353 (1965).

[4]. Zadeh, L.A.,” The concept of a linguistic variable and its application to approximate reasoning”, Information Sciences, 8 pp 199–249 (1975).

[5]. Pawlak, Z.,” Rough sets”, International Journal of Information & Computer Sciences 11, pp. 341–356 (1982).

[6]. Pedrycz, W. and Gomide, F.,” Fuzzy systems engineering: toward human-centric computing”, John Wiley, Hoboken, NJ, (2007).

[7]. Alinia, Hadis Samadi, and M. R. Delavar. “Tehran’s seismic vulnerability classification using granular computing approach.” Applied Geomatics 3, no. 4 (2011): 229-240.

[8]. Mencar, Corrado, and Anna Maria Fanelli. “Interpretability constraints for fuzzy information granulation.” Information Sciences 178, no. 24 (2008): 4585-4618.

[9]. Wang, Cunpeng. “Data Analysis in Incomplete Information Systems Based on Granular Computing.” In System Science, Engineering Design and Manufacturing Informatization (ICSEM), 2010 International Conference on, vol. 2, pp. 153-155. IEEE, 2010.

[10]. Alsawy, Assem A., and H. A. Hefny. “On Uncertain Granular Number” International Journal of Computer Applications 62(18), pp. 20-27, Foundation of Computer Science, New York, USA, (2013).

[11]. Taha, A. Hamdy. Operations research. Pearson Education, 2003.

[12]. Dijkstra, Edsger W. “A note on two problems in connexion with graphs.”Numerische mathematik 1, no. 1 (1959): 269- 271.

[13]. Bellman, Richard. On a routing problem. No. RAND-P[1]1000. RAND CORP SANTA MONICA CA, 1956.

[14]. Floyd, Robert W. “Algorithm 97: shortest path.” Communications of the ACM 5, no. 6 (1962): 345.

[15]. Johnson, Donald B. “Efficient algorithms for shortest paths in sparse networks.”Journal of the ACM (JACM) 24, no. 1 (1977): 1-13.

[16]. Dorigo,Colorni, Alberto, and Vittorio Maniezzo. “Distributed optimization by ant colonies.” In Proceedings of the first European conference on artificial life, vol. 142, pp. 134-142. 1991.

[17]. Baykasoglu, Adil, Lale Ozbakir, and Pýnar Tapkan. “Artificial bee colony algorithm and its application to generalized assignment problem.” Swarm Intelligence: Focus on Ant and particle swarm optimization (2007): 113-144.

[18]. Alsawy, Assem A., and H. A. Hefny. “Fuzzy-based ant colony optimization algorithm.” In Computer Technology and Development (ICCTD), 2010 2nd International Conference on, pp. 530-534. IEEE, 2010.