Solving fuzzy shortest path problem with a new neural network model




Скачать 14.56 Kb.
НазваниеSolving fuzzy shortest path problem with a new neural network model
Дата09.10.2012
Размер14.56 Kb.
ТипДокументы




اولین کنفرانس بین المللی انجمن ایرانی تحقیق در عملیات --- دانشگاه کیش --- بهمن 1386



Solving fuzzy shortest path problem with a new neural network model


Sohrab Effati 1, Morteza Pakdaman2

Department of mathematics, Tarbiat Moallem University of Sabzevar, Sabzevar, Iran


Abstract:

A new neural network model for solving fuzzy shortest path problem is proposed. We solved the neural network model with Euler method. This model can be applied for solving any fuzzy linear programming problem with fuzzy coefficients in objective function.


  1. Model definition

A fuzzy shortest path problem can be formulated as follows:





This problem is one of the important models in theory of networks. Many problems in applications such as transportation, communication and routing can be modeled as a shortest path problem (SPP). There are several traditional algorithms for solving this special linear programming problem such as simplex method ( see [1]) or Dijkstra algorithm (See [2]). But in real world phenomena the arc lengths ('s ) are not really known and so they aren't crisp. In this condition we can formulate a fuzzy shortest path problem (FSPP), where 's are (triangular or trapezoidal) fuzzy numbers . Yinzhen et al ([3]), solved FSPP with a neural network. Their method was based on penalization. Here we introduce a more simple fuzzy neural network as follows.


  1. Solving Method

To solve FSPP, we introduce the following fuzzy optimization problem:

(2)

Where A is the matrix of technological coefficients for FSPP. (Note that here for simplicity and to save space, we skipped most fuzzy introductory requirements and just state some results ) .

Theorem 2.1 (see [4]). Suppose is a fuzzy function with then if is differentiable ( fuzzy differentiable), then are differentiable functions and we have : .


Definition 2. 1 (see [4]). Let be a fuzzy mapping (E is the set of all fuzzy numbers), where is an open subset of. Let and stands for the partial differentiation with respect to the i th variable. Assume that for all (the cuts of ) have continuous partial derivatives. Define: . (3)

If for each i=1,...,n, (3), defines the cuts of a fuzzy number, then we will say that is differentiable at x , and we write :.We call the gradient of fuzzy function at x .

Theorem2. 2 (see [4]). Let be a differentiable fuzzy function at ( is an open set) if is a point of local minimum then.

If we apply theorem 2.2 for problem (2), we should have: . Or we should have . Now according this, we introduce the neural network model as:

(4)

We proved that this model is convergent to the optimal solution of FSPP. Note that here is not fuzzy and stands for fuzzy derivative of . Now we can solve (4) with any numerical methods (for solving fuzzy differential equations). We solved this neural network model with Euler method.


3. Conclusions


In this extended abstract of our paper, we proposed a new neural network model for solving fuzzy shortest path problem. This method can be applied for solving any fuzzy linear programming problem with fuzzy coefficients in the objective function. Quickly convergence, simple computer programming and applicability for large networks are some advantages of this method.


References


[1]. M.S. Bazaraa, John J. Jarvis, H.D. Sherali, Linear programming and network flows, John Wiley and Sons, New York, (1992).

[2]. G.B Dantzig, M. N Thapa, Linear programming, Springer, New York, (1997).

[3]. Yinzhen Li, Mitsuo Gen and Kenichi Ida, Solving fuzzy shortest path problems by neural network, Computers ind. Engng, Vol. 31 (1996) 861-865.

[4]. M. Panigrahi, G. Panda, S. Nanda, Convex fuzzy mapping with differentiability and its application in fuzzy optimization, European Journal of Operational Research (Article in press).

1 Effati@sttu.ac.ir

2 Pakdaman.m@gmail.com

Похожие:

Solving fuzzy shortest path problem with a new neural network model iconIn the tsp a salesman has a list of cities to travel to and must visit each city exactly once using the shortest overall path. The problem is easy to

Solving fuzzy shortest path problem with a new neural network model iconSupporting collaborative problem solving: supporting collaboration and supporting problem solving

Solving fuzzy shortest path problem with a new neural network model iconGorbachenko V. I., Artyuhina E. V. Meshless neural network algorithm solving boundary value problems, based on the approximation of the nonlinear dependence
Горбаченко В. И., Артюхина Е. В. Бессеточные нейросетевые алгоритмы решения краевых задач, основанные на аппроксимации нелинейных...
Solving fuzzy shortest path problem with a new neural network model iconGa-based fuzzy neural controller design for municipal incinerators

Solving fuzzy shortest path problem with a new neural network model iconAdaptive approximation based control : unifying neural, fuzzy and traditional

Solving fuzzy shortest path problem with a new neural network model icon11. 1 Problem Solving and Systems Development

Solving fuzzy shortest path problem with a new neural network model iconCommunity Policing and Problem Solving

Solving fuzzy shortest path problem with a new neural network model iconMeteorology exercises and Problem Solving

Solving fuzzy shortest path problem with a new neural network model iconIntroduction to Problem Solving in the Information Age

Solving fuzzy shortest path problem with a new neural network model iconOn (I) mechanizability of human mind versus consideration regarding meta problem, problem of complexity and chance/randomness (II) defence of utilitarian model of human behavior (decision making)

Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница