106105173.pdf
Document Details
Indian Institute of Technology, Kharagpur
Tags
Full Transcript
INTRODUCTION TO SOFT COMPUTING Prof. Debasis Samanta Computer Science and Engineering IIT Kharagpur INDEX S. Page No Topic No....
INTRODUCTION TO SOFT COMPUTING Prof. Debasis Samanta Computer Science and Engineering IIT Kharagpur INDEX S. Page No Topic No. Week 1 1 Introduction To Soft Computing 1 2 Introduction To Fuzzy Logic 17 Fuzzy Membership Functions (Contd.) And Defining Membership 3 Functions 39 4 Fuzzy Operations 59 5 Fuzzy Relations 76 Week 2 6 Fuzzy Relations (Contd.) & Fuzzy Propositions 97 7 Fuzzy Implications 113 8 Fuzzy Inferences 132 9 Defuzzification Techniques (Part-I) 147 10 Defuzzification Techniques (Part-I) (Contd.) 168 Week 3 11 Fuzzy Logic Controller 193 12 Fuzzy Logic Controller (Contd.) 215 13 Fuzzy Logic Controller (Cond.) 234 14 Concept Of Genetic Algorithm 249 15 Concept Of Genetic Algorithm (Contd.) and GA Strategies 268 Week 4 16 GA Operator: Encoding schemes 286 17 GA Operator: Encoding schemes (Contd.) 305 18 GA Operator: Selection 324 19 GA Operator: Selection (Contd.) 345 20 GA Operator : Crossover techniques 366 Week 5 21 GA Operator: Crossover (Contd.) 393 22 GA Operator: Crossover (Contd.) 411 23 GA Operator: Mutation and others 430 24 Multi-objective optimization problem solving 453 25 Multi-Objective Optimization Problem Solving (Contd.) 473 Week 6 26 Concept Of Domination 497 27 Non-Pareto Based Approaches To Solve MOOPS 514 28 Non-Pareto Based Approaches To Solve MOOPS (Contd.) 536 29 Pareto-Based Approaches To Solve MOOPS 551 30 Pareto-Based Approaches To Solve MOOPS (Contd.) 565 Week 7 31 Pareto-Based Approach To Solve MOOPS 582 32 Pareto-Based Approach To Solve MOOPS (Contd.) 602 33 Pareto-Based Approach To Solve MOOPS (Contd) 620 34 Introduction To Artificial Neural Network 637 35 ANN Architectures 656 Week 8 36 Training ANNs 678 37 Training ANNs (Contd..) 696 38 Training ANNs (Contd..) 713 39 Training ANNs (Contd..) 729 40 Soft Computing Tools 747 Introduction to Soft Computing Prof. Debasis Samanta Department of Computer Science & Engineering Indian Institute of Technology, Kharagpur Lecture – 01 Introduction to soft computing I take this opportunity to welcome you to the course Soft Computing. In today’s lecture we will discuss about basic concept of soft computing. So, basically we know exactly soft computing is related to in some sets computing. (Refer Slide Time: 00:25) So, basically what is the concept of computation, we will learn about it. After these things as the term soft computing so there may be something which is called the hard computing so we learn about the hard computing next. And then in what way a soft computing is different from the hard computing. And then obviously, the natural question that arises that how the soft computing can be achieved and to understand better the soft computing we should know exactly what are the differences between the hard computing and soft computing. And there is also another concept it is basically the combination of the two computing paradigms, hard computing and soft computing it is called the hybrid 1 computing. So, in today’s lecture we will try to cover these are the different concepts here. (Refer Slide Time: 01:24) Now, let us first concept of computation. So, we know exactly a computing means there are certain input and then there is a procedure by which the input can be converted into some output. So, in the context of computing, so the input is called the antecedent and then output is called the consequence and then computing is basically mapping. Here we see, so f is the function f is the function basically which is responsible to convert x the input and to some output. So, this is the concept of computing is basically. So, in other words, computing is nothing but is a mapping function, mapping from set of input to output. Now, this mapping is also alternatively called as formal method also it is called an algorithm, so basically algorithm to solve a problem. 2 (Refer Slide Time: 02:36) Now, say let us see, exactly what are the different characteristics of computing? So, computing is that, for a given input it always give a particular output. This means that it should provide a precise solution. And in order to achieve from a given set of input to an output it should follow some setup unambiguous and accurate step. And the next characteristic is that, it should it is suitable for some problems which is easy to model mathematically. This means that for which there is an algorithm is available. (Refer Slide Time: 03:21) 3 Now this is the concept of computing and this concept is first time coined by a mathematician is Lotfi Aliasker Zade. So, he is only termed as LAZ and he basically is the first person to introduce the concept of hard computing as a part of the concept of computing in general. So, according to LAZ the computing we can say it is hard computing if it provides precise result and the step that is required to solve the problem is unambiguous and then the control action; that means, those are the steps that is require is formally defined by means of some mathematical formula or some algorithm. So, if a computing concept follows these are the three different characteristics then we say that computing is hard computing. (Refer Slide Time: 04:27) Now, I will come to some example of hard computing. We know in order to solve numerical problems for example, finding root of polynomials or finding an integration or derivation we usually follow some mathematical models and therefore, it is an example of hard computing. Now, searching and sorting techniques are frequently used in many softwares. So, these are the basically followed by some unambiguous steps and it always gives the precise result and it is basically defined correctly by means of an algorithm. So, it is an example of hard computing. There are many problems related to the computational geometry for example, finding the shortest tour in a graph, finding closest pair of points given a set of points etcetera is basically is a task of hard computing. And there are many many such examples can be 4 given. So, these are the concept of hard computing. And now, let us come to the concept of soft computing. (Refer Slide Time: 05:39) So, as I told you the hard computing first time proposed by LAZ. He himself also defined the concept of soft computing first times. According to him, the soft computing is defined as a collection of methodologies that aim to exploit the tolerance for imprecision and uncertainty to achieve tractability, robustness, and low solution cost. Now, here I have underlined few things that you can mark it. So, the first thing it is basically tolerance for imprecision this is important. This means that the result that is obtained using the soft computing not necessarily to be precised and obviously, the result is uncertain. This because if you solve this problem several times it may give different result different time. And is a robustness, means it can tackle any sort of input noise including, so that is why it gives the robustness. And very important concept is called the low solution cost. Some problems if we follow hard computing then it is computationally expensive. However, if we follow soft computing then it is computationally very cheap; that means, we can find a solution in real time. Now, so if this is the concept of some soft computing where the result is not necessarily to be precised, the step that needs to be followed is not necessarily the certain or unambiguous and then the result that can be obtained is also not necessarily to be same always. Then how this can be achieved? So, in principle the soft computing concept 5 follow three computing paradigms. These are called fuzzy logic, neural computing and probabilistic reasoning. So, these are basically the soft computing paradigms and is basically these concepts the fuzzy logic, neural computing or probabilistic reasoning, if you see, this is the exactly the way the human can solve their own program. So, that is why the role model for soft computing is in fact human mind. (Refer Slide Time: 08:23) Now, let us see what are the different characteristics of soft computing? We have discussed little bit about it. So, soft computing is one concept of computing which does not require any mathematical model. So, it does not require any mathematical model or problem; that means, it does not necessary that an algorithm should be followed or the problem that we have to solve should be expressed in terms of mathematical formulation. And it may not yield the precise solution, the solution that is not that it will give you always the same or a unique. It can give time to time the different solution for the same problem even with the same input also. But the solution is near about the accurate value. And algorithms are adaptive; that means, it can adjust to the change of any dynamical situation. I, by the means of dynamical situation, I want to mean that if the input is changes, suppose you want to solve one problem which require only two inputs, but later on the same problem require where twenty input is required. So, the same problem same computing concept can be easily adapted into whatever be the number of inputs are there, whatever the input values 6 maybe there, whatever the other parameters that is involved in order to solve the problem. Now, so I told you that a human mind is the role model behind the soft computing and actually it is some biological inspired methodology. So, that also constitute the concept of human behavior, such as genetics, the evolution, the behaviors of ant colony, swarming of particles, our nervous system, etcetera. So, basically the way the different natural phenomena works for us if we follow the same method and then try to solve our own problem this is basically the way exactly the use of soft computing to solve our own problem. (Refer Slide Time: 10:35) Now, I will give some example of soft computing so that we can understand how the soft computing can works for us. And in this example this is example is basically extracted from the hand written character recognition. Now, the different people if we collect the hand written character they can give the same characters in a different form. Now, even we know exactly whatever the different form or the way the people can write we can understand easily. For example there is a different way the input is given here and we can exactly step it here we exactly tell that this is [Aa]. Now, how it basically happens is basically we learn by the process that this is the letter resemble to a particular alphabets [Aa]. So, it is in the same way we learn it and this learned somehow stored in our memory and this is the learning phase and these learning basically works for us to 7 recognize any unseen characters or unseen letters. And these basically the way actually our neural network our nervous system works and based on this concept the artificial neural network has been evolved and it is followed there. (Refer Slide Time: 12:02) Now, another example say, suppose a person wants to invest some money and for which the different the banks are available with the different policies, the different schemes and there is a flexibility for the person to invest all or some money into the different banks so that he can return the maximum profit. Now, here is the one problem that how we can store the, how we can invest the money in different bank so that we can get the maximum return. So, this concept is basically can be followed using some probabilistic reasoning or it is called the evolutionary computing for example, genetic algorithm can be followed to solve these kind of problem. 8 (Refer Slide Time: 12:59) Another example it is from the robotics say, suppose one robot wants to move from here to these place and there are many obstacles are there. Now, so how the robots can calculate his movement so that without any collision, with any objects, he can move from his current location to target location within a shortest time. Now, this kind of problem, in fact, has lot of uncertainty or impreciseness, defining so for the input is concern. Because the robot is works like that. And then that kind of uncertainty can be solved using the concept called the fuzzy logic. So, fuzzy logic is an important parts of soft computing. Now, here is again another question. So, we have discussed three different problems hand written character recognition, allocation of money into the different banks and then movement of the robots in three different corners. Now, the first example that we have discussed that it is the problem which can be solved very effectively efficiently using artificial neural network. The second problem that we have discussed it basically solved using some probabilistic reasoning and it is basically one problem called evolutionary computing or genetic algorithm. The third problem that we have discussed it is basically the fuzzy logic, how the fuzzy logic can be exercised to solve some problem where lot of uncertainty involved. 9 (Refer Slide Time: 14:48) Now, I want to, now discuss about the different techniques that can be followed or the different techniques which is basically behind the above concepts. For example, how a student learn from his teacher? Here the two part is involved one is the student and is the teacher. Now, consider student is basically a computing machine and teacher is basically once two I mean gets some output for a given input like. So, how a student is learn from his teacher or basically how such a system can be developed, here the teacher is responsible to develop a system and here system is student. So, usually teacher ask questions and tell the answer. Then there is another way teacher puts some questions and hints an answers and ask whether the answers are correct or not, students here basically to check whether the answer correct or not. Students then, students thus learn a topic and store in his memory. So, basically by the process if we discuss several time the same different questions, different answers, different questions, hints to the different answer for the same question or different answers for the different questions. So, students listen to those and then by the process learn a topic and whatever the students learns it basically store in his memory. Now, based on the knowledge he then can solve many new problems assigned to him. So, basically it is a concept of learning how to learn something and then based on this learning how he can solve the problem. 10 So, this is the way exactly our human brain works in fact. And based on this concept the artificial neural network is used for example, hand written character can be recognized. (Refer Slide Time: 16:45) Now, another example, so how world selects the best? It is basically a natural process. So, in this process is basically starts with a population and initially it consider a random population. So, when our worlds evolve first time it is started with some population and is a random population. Random means whatever the objects these are possible there and it then reproduces, reproduces to develop another population, we called it is a next generation. And then all the population that we obtained so we rank them and select the superior individuals. So, here basically population generation, then reproduction and reproduction followed by the ranking and then it basically selects based on this ranking the best individuals. So, basically best population or best solution. Now, the concept of genetic algorithm is based exactly on the same phenomena, it is called is basically genetics. And here in this context the population is synonymous to solution. So, we can start with some random solution those are not necessary to be an optimal and then we have to reproduce from this set of solution another solution and then select the best solution. The same thing can be repeated several times ultimately until we can achieve the best result. Now, here selection of superior solution is synonymous to exploring the optimal solution. 11 Now, here we can see all the method that can be followed in a probabilistic manner or in a randomized sense. So, that is why the genetic algorithm follows a probabilistic reasoning to solve problem particularly solving optimization problem. (Refer Slide Time: 18:45) Now, as another example how a doctor treats his patient? Here doctor is a one party and patient is another party. Now, patient wants to solve his problem with the help of doctor. So, doctor is the computing system in this case. So, usually it works like this. Doctor asks the patient about the problem that he is suffering and doctor find the symptoms of disease from the patients input, and then doctor prescribe some tests and medicine. This is the exactly the way the fuzzy logic works. So, fuzzy logic take some input which is basically related to solving some problem and then based on this inputs he predict certain output. So, here symptoms are correlated with disease and you know whatever the disease doctor will guess or patient will tell they are basically not a certain; there are some uncertainty with the input. So, this is why it is called the symptoms are correlated with disease uncertainty and then the doctor prescribe medicines or whatever the test it is also fuzzily; so that means, with certain uncertainty. So, fuzzy means it is uncertain in this sense. 12 (Refer Slide Time: 20:11) Now, let us discuss about hard computing versus soft computing. Now, so for the hard computing is concerned it requires a precisely stated analytical model and obviously, it is a computational expensive on methodology. On the other hand soft computing it is imprecision, tolerance to imprecision means we can be happy with some solution which is not exactly the precise one and with uncertainty, the partial truth and approximation may works for us. Only the requirement that is that the problem which cannot be solved using hard computing in real time can be solved using soft computing in a real time. The concept of hard computing basically based on few concept called the binary logic, crisp system, numerical analysis and some crisp software; the software basically if run for the same input it always give the same output. Whereas, the concept that is followed in soft computing is based on the fuzzy logic, the neural networks, and probabilistic reasoning which is totally different than the concept that is followed in hard computing. And so, hard computing basically has the characteristics of precision and categoricity, it works for a certain kind of input and it works well for that input. Whereas, the soft computing is a characteristic of approximation; exact result is not required, but it can be near accurate result and dispositionality; that means, it can be applied to varieties of input, the different type of input, different number of inputs as well as. 13 (Refer Slide Time: 22:09) Now, another differences another differences between hard computing and soft computing it is deterministic whereas, the soft computing is stochastic means probabilistic. It requires exact input data in case of soft computing it basically requires an ambiguous and noisy data. Hard computing usually is followed strictly sequential methods; however, the soft computing can be carried out using parallel computation. Hard computing produces precise answers whereas, soft computing can yields approximate answers. So, these are the differences between hard computing and soft computing and I hope you have understood the difference between the two. 14 (Refer Slide Time: 23:05) Now, so there is hybrid computing. It is basically combination of the two into solving a particular problem. So, few portion of the problem can be solved using hard computing for which we have a mathematical formulation for that particular part and then where we required a precise input. And there are some part of the same problem maybe which cannot be solved in real time for which no good algorithm is available and we also do not required accurate result some near accurate result is sufficient for us then we can solve soft computing for that part and then mixing together is basically the hybrid computing. So, if we know hybrid hard computing, if we know soft computing and if we know some problems where whatever the characteristic involved to solve either hard computing way of soft computing way we can inter mix the two approaches and then hybrid computing can be obtained. 15 (Refer Slide Time: 24:14) Now, in this course you will be able to learn basic concepts of fuzzy algebra and then how to solve problems using fuzzy logic. Then we will be able to learn the framework of genetic algorithm and solving varieties of optimization problems. And then how to build an artificial neural network and train it with input data to solve a number of problems which are not possible solve with hard computing. Thank you. 16 Introduction to Soft Computing Prof. Debasis Samanta Department of Computer Science & Engineering Indian Institute of Technology, Kharagpur Lecture – 02 Introduction to Fuzzy Logic We will start our lecture. This is the beginning of the topics, the fuzzy logic. So, fuzzy logic is an essential component for the soft computing. So, today we will learn about basic concept of fuzzy logic and to understand the fuzzy system we should familiar our self with different terminologies. So, we will explain the different terminology related to the fuzzy logic. (Refer Slide Time: 00:47) So, the first is what is fuzzy logic? In fact, fuzzy logic is a language we can say more precisely is a mathematical language like any language you know. So, this language is also used to express something which is meaningful to others. So, it is a language this means that, it has grammar, it has it own syntax, the meaning like a language for communication like English. Now, like fuzzy logic there are many mathematical languages we know. So, one language is called relational algebra which is based on the operations on set. So, this is also called relational logic. Boolean logic is basically based on the operations on Boolean variables it is Boolean algebra it is also called. And predicate logic or it is called 17 the predicate algebra, which is basically operations based on the well-formed formulae or proposition also called the predicate propositions. It is very interesting that fuzzy logic like relation logic, Boolean logic and predicate logic, it also deals with some elements; the elements on which this fuzzy logic depends is called fuzzy set and it is also alternatively call the fuzzy algebra. And another interesting fact is that the fuzzy logic essentially combined the different algebras like relational algebra, Boolean algebra and predicate algebra together. So, it is basically a mixture of the different mathematical languages to define another new language that is the fuzzy logic. (Refer Slide Time: 02:47) Now, so the word fuzzy may not be new to us. So, if we search dictionary the meaning of fuzzy is not clear or it is called noisy it is like that. Now as an example so we see one figure here we see one figure here this is the figure now. So, sometimes we see that is the picture on this slide is clear. So, we can say yeah the picture on this slide is fuzzy; that means not clear whatever the wording it is clear we may say that it is not clear or there are many noise in the image. So, the image is noisy, image is fuzzy. In other words we can understand the meaning of the fuzzy if we see it’s antonym. The antonym of fuzzy is crisp. Now crisp in the sense that if we say there is a there are 2 regions and if we say the boundary if the boundary is not clear then we can say the 2 regions are separated fuzzily, on the other hand if there is a strong boundary by which we 18 can easily distinguish 2 regions clearly then we can say that the boundary is crisp. So, this way we can understand the fuzzy versus crisp. We learn many thing about this fuzzy versus crisp in our next slides next discussion. (Refer Slide Time: 04:41) So, we have a little bit understanding about the meaning of fuzzy. Our next discussion exactly with some examples. So, how the 2 logic may be say logic with fuzzy sets and logic with crisp set. Ok. So, I say here set. Anyway, so I will discuss about what exactly the crisp set it is anyway. So, fuzzy logic versus crisp logic. Now say, if we ask some questions and then answer to that question if has the clear meaning then we can say that answer is having crisp answer. So, crisp answer usually expressed in the form of either yes or no, true or false, like this. As an example, suppose the question is that we have to identify a liquid now, any liquid like milk, water, coca, sprite is given and then if we ask the question that is the liquid colorless? Now you have to give the answer in terms of only 2 things, yes or no. Then it is called the crisp answer. So, this way we can understand exactly the crisp crisp system. 19 (Refer Slide Time: 05:59) And alternative to crisp system the fuzzy answer let us see how the fuzzy answers can be like. So, if we ask one questions and the answer can be of many instead only 2 solid answers. So, the answer may be may be, may not be, absolutely, partially, etcetera. So, there are many many form, many values for the same answer. (Refer Slide Time: 06:29) 20 So, this is basically the concept of fuzzy answer. I can illustrate the concept with an example. Say, fuzzy system is like the question is, is the person honest? And a person is given as an input let them are the Ankit or Rajesh, Santhosh, Kabita, Salmon like. So, if we ask the question is the person honest say Ankit. So, their answer may be extremely honest, very honest, honest time to time or extremely dishonest. Now so for a for a question unlike the crisp question, for the fuzzy questions, or for a question the fuzzy answer, on like the crisp answer may have different what is called the answers. Now so, this different answers if it is there for the same question then which is the correct answer actually. Because all answers seems to be acceptable or rejectable. Now which answer is there? Now, we can give a score to each answer. So, here I have given a score here for each answer. For example, extremely honest 99, very honest 75, honest at times 55, extremely dishonest 35. So, this means that if it is a 2 valued answer like say crisp answer then only 2 and then score will be on 100 and another is 0 whatever it is there. But here the different values of the score. This means that the answer which is a very honest it is also the correct, but correct with a validity score it is called the 75. Now obviously, question that arise that, how we know what is the score actually? So, we will discuss about that how the score for a for an answer can be calculated and that can be tagged into that answer to signifying that how answer is significant or how answer is acceptable, so far the question is concerned. Anyway so the idea is that, these are the answer is called the fuzzy answer for a given question unlike the crisp answer. 21 (Refer Slide Time: 08:41) Now, in fact our world can be better described fuzzily. This is because if I say what is the temperature today? So, you can get an answer like very hot, some people can say that comfortable, the extreme or very cold it is like this. So, this means that for the same question, the answer can be different if the same question is fired to many people. But everybody can give the answer according to their own estimation whatever it is there, but the answer is like that. Like the temperature another what will be the weather today? So, if I ask to predict it to some expert person then he will give the answer fuzzily; that means, yeah weather is sunny today, may be sunny, may not be sunny, may be cloudy or it is like that. So, the answer can be for same questions of different form and different form has their own value and then we have to take all the values, in fact, and then process it. So, that the answer is acceptable to us. 22 (Refer Slide Time: 09:52) Now, so the best idea it is that the system that we are using it is basically better can be described fuzzily or it is basically the system or we can say that everything is in the form of a fuzzy and then we can take the fuzzy manners or the fuzzy way to describe any system rather. So, if we describe a system in the in the way of in the way the fuzzy decides then this system is called the fuzzy system. Now typically the fuzzy system has many ingredients or elements. So obviously, the input and output is the part of any system that we have already discuss in the first lecture itself. So, if this is the entire system then these are input and then output, now need not to say that input is obviously in the form of a crisp. Because we usually give input to the system in the form of a crisp value. Similarly, the output also should be in the form of a crisp value. So, in this system there are 2 boundaries one input and output. Input and output are in the form of a crisp value. However, input can be transformed into some fuzzy form and then the fuzzy system can come into play. And so in this type of fuzzy system there are many constituents many elements are there. So, the first element is called the fuzzy elements and taking one or more fuzzy elements we can discuss about the fuzzy set and then many fuzzy sets can be connected with the set of another element it’s called the fuzzy rules and finally, a set of fuzzy rules can 23 govern us to decide is called the fuzzy implication or it is called the inferences and these whole the things constitute what is called our fuzzy system. In other words, to understand the fuzzy system, it is our task to understand what exactly a fuzzy element it is. And then what is a fuzzy set and then using the fuzzy set how the fuzzy rules can be obtained. And then how the inferences can be described in the form of a fuzzy rules. And that all these things if we learn it, then we will be in a position to discuss about the fuzzy system. So, in our subsequent lectures we will basically discuss about all these elements one by one. Today will discuss about the fuzzy elements first. (Refer Slide Time: 12:33) Now, let us see exactly what is the fuzzy elements. So, fuzzy elements basically essentially it a fuzzy set. So, we can better describe a fuzzy set in the form of a crisp set actually. So, we know exactly the concept of set. So, this the traditional set that we know it is, in fact, is a crisp set. For an example, say X denotes a crisp set and it denotes the entire population of India. Then you can say what are the elements? Yourself, myself are the elements belongs to the set X. Now, I can derive one set again from this set X or some other means suppose it is the H. H is the another set it denotes all Hindu population. So, any element that is means any person or any individuals belongs to this set is the set composition itself. For example, here h1, h2, h3 all these things are the elements to this set they are basically individual who basically satisfy some characteristics being Hindu population. Like Hindu 24 population we can define another set say all Muslim population for example, these are the set of all Muslim individuals. So, these are the example of crisp set and we know any crisp set can be better describe in the form of a graphs or it is a venn diagram. So, we have we have shown one venn diagram here. For this H, M and X whole the things are basically shown here and we can see that there are the 2 boundaries. The 2 boundary essentially difference or basically define solidly the 2 regions. One region belongs to H and another region belongs to M and these 2 regions a basically belongs to another bigger region. So, this bigger region is basically called universe of discourse in this case it is X. So, all the regions whatever it is there has a solid boundary and that is why they called the crisp set. (Refer Slide Time: 14:47) Now, so like crisp set the fuzzy set is also almost similar, but little bit difference is there; difference so for the presentation is concerned. For an example, so suppose X, X denotes a set and let the set be all students in NPTEL. So, this is the universal of discourse in this case. Now, I let us define one set belong to this X, let this set be S. And we define this set S as all good students. Now let us see how the same thing can be defined using a fuzzy manner. So, we define the set S as a 2 things in each elements; one is s the elements itself 25 and g(s) some measurement of S itself, where s is any element belong to X and g(s) is a measurement. Now this measurement, in fact, we can say measuring the goodness of a student. Now, for example, if I want to measure the or evaluate a student. So, how I can evaluate? I can take some exams and I can take the marks obtained by the students in that exam. So, g(s) can be same type of measurement like. So, it is a goodness measure. It is or rather it is called the measurement that that the s belongs to the set S. So, for example, here again we can see. So, suppose there are few students which are Rajat, Kabita, Salman, Ankit like and their measurement is expressed here for a Rajat is having the score 0.8, Kabita having 0.7, Salman 0.1 and Ankit a 0.9. So, this set signifies that all students who belongs to this set like Rajat, Kabita, Salman they are the good student, but goodness is defined by means of measure. In other word Salman if he is a good student then Ankit is also good student. But Salman being a good student his score is 0.1 and Ankit his score is 0.9. So, the difference between the two is basically how they have their own membership values; that mean, 0.1 0.9 whatever it is there, but all them belongs to the good student in fact. All though Salman may scoreless or Ankit may score highest here. All of them are the good students belongs to the good students actually. Now, here another point you can note that the measurement value that we have mentioned here is basically in between 0 to 1. Actually it is the concept that is followed in fuzzy logic all the measurement value g(s) like. So, value should have in 0 to 1 both inclusive. So, any value in between 0 and 1 are the basically taken as the membership value for this one. 26 (Refer Slide Time: 18:06) Now, so we have a little bit understanding about the fuzzy sets and let us see what are the difference, the salient differences between the crisp set and the fuzzy set. So, the differences between the two sets are defined in the form of a table. So, if we define a crisp set it is basically is a collection of elements; that means one part only, so s. Where as if it is a fuzzy set then it is a collection of ordered pair it is called. The first part is the element itself and second part is the measurement of that element itself. So, sometimes this measurement (s) in fuzzy theory it is called the degree of S or it is also called membership value of S. So, what you have understood is that a crisp set is a collection of elements whereas a fuzzy set is a collection of ordered pairs. So two things together form one element in the fuzzy set. Now, inclusion of an element, any element say, s into the set a S capital S is crisps, that is it has strict boundary, yes or no. If that element belongs to the set yes or no we can easily justify that one. However, inclusion of an element s into F the which is a fuzzy set is present then with a degree of membership. In other words a same element say, s can belongs to two fuzzy set F and G, but with different membership values. For example, if F denotes the good student and G denotes the bad students then same element say, s can belongs to the good student as well as bad student, but with different membership value. For example, s appears in F with membership value 0.7 whereas; the same element belongs to the set G with membership value say 0.3. So, it is like these. 27 So, same elements may appear into the two sets with different membership values whereas, same element may not appear into two crisp set, it is either in one set or another. So, there may be ok. (Refer Slide Time: 20:27) So, we have understood about few definition about the fuzzy set versus crisp set. Now we will discuss about, one point you can note is as, I already told you the membership values or degree of membership value we can say alternatively like this. Degree of values, degree of membership values or membership values that can be their if an element belongs to fuzzy set with any value 0 to 1, inclusive and then any value in between 0 to 1 inclusive. On the other hand, the same element actually if it is a crisp set can also express in the form of a fuzzy form with the membership value 1 and 0 only. For example, here is the set H. So, if that element presents there, then I can say the degree of membership one. If the element does not belongs to that set then we can say the degree of membership is 0. So, basically this is a fuzzy set essentially with the membership value 0 and 1. Now with this understanding if we do not write this one this one and this one then we can say that h is a crisp set which elements are h1, h2, hL. On the other hand if it is the membership value 0; that means, this element does not belong to this set. So, in this case the Person becomes a null set. So, basically 0 and 1 being the two extreme values can be expressed to define a crisp set in the form of a fuzzy 28 set. So, this way we can say that a crisp set is a fuzzy set, because anyway crisp set can be converted in the fuzzy set easily. But a fuzzy set cannot be expressed always in the form of a crisp set. Because their membership value not necessarily always 0 and one in between 0 and 1. So, this is the one conclusion that we can infer it from our discussion that the crisp set is a fuzzy set, but a fuzzy set is not necessarily a crisp set. (Refer Slide Time: 22:31) So, we have understanding about the fuzzy set versus crisp set or we can say crisp logic versus fuzzy logic little bit. Now let see one important point here, so far the fuzzy set decision is concerned the membership value and there is a question that how the membership value each elements can be decided and who can decide this membership values for each elements which belongs to the fuzzy set. I can give an example. Say suppose all cities in India or more precisely say suppose there 6 cities in India like Bangalore, Bombay, Hyderabad, Kharagpur, Madras, Delhi right and I want to define one set let the name of the set is city of comfort. Now I have decided some value let the values for each set belongs to the set like Bangalore is 0.95 and so on. Now so the idea is that how this comfort of the Bangalore city 0.95 can be decided. There are certain population vote or something like population opinion or any way feedback whatever you can consider by this feedback, if we normalize those feed back into the value this one then it will give us to a fuzzy values. 29 So, this way we can have the fuzzy membership and regarding the membership value we will discuss in details in due time. (Refer Slide Time: 23:58) Now there is another example which I would like to mention here. So, that we can understand the concept of crisps versus fuzzy. The idea it is here, say we know exactly how to grade the marks obtain by a students in a subjects. So, basically this is the grading formula, now these are the grading, that we can we can see that there is a strict boundary between one marks to another. So, a marks will be either belongs to the grade A or it is EX or B, but cannot be a same marks belongs to the 2 different grade. For example, one mark which is there in this it can belong to this one, that mean the marks can be EX, marks can be A, marks can be B, if it is marks in EX it is definitely with certain membership value is a 0.2 if it is belong to B then maybe it is 0.3 if it is belongs to A then maybe it is 0.9. So, there is a there is a concept and this is basically the example of crisps formulation for the marks. Now the same thing if we do it in a fuzzy formulation it will look like this. 30 (Refer Slide Time: 25:14) So, this is basically the graphical display of the crisp formulation and the fuzzy formulation we can see it is the fuzzy formulation. (Refer Slide Time: 25:22) So, here we can note that any marks for example, any marks say it is this one this is the marks. So, this marks is basically these basically denote the D grade and these basically denotes the P grade. So, this marks both belongs to the P grade and both belongs to the D grade. If it is if we draw like this so if it is a D grade then this is the membership value and if it the P grade then this is the membership value. 31 So, the same marks belong to the two sets P or D with the different membership values. (Refer Slide Time: 26:03) Some examples further can be used for example, temperature is high. So, we can discuss it with is in a fuzzy form low pressure, color of apple, sweetness of orange, weight of mango and so on so on. So, these are the few examples which basically we know. So, these are the input and then they can be discuss in a fuzzy form also. (Refer Slide Time: 26:29) Now, for the definition we will start with few terminologies. So, the first that a membership function and so it can be defined like this. If X is a universe of discourse 32 and if any element x, which is belongs to this X, then a fuzzy set A which is defined in X is defined as a set of ordered pairs, as I told you ordered pairs x and (x). So, this is the concept of fuzzy sets and definition of basically membership function and these fuzzy set. (Refer Slide Time: 27:05) So, here as an example that how fuzzy set can be X is the all cities in India and A is a fuzzy set City of comfort and then this fuzzy set can be discussed using this form. Now, membership functions may have any value. They are with either discrete membership values. Here I can show I show one example here where the all. 33 (Refer Slide Time: 27:22) So, these are the elements in between has the membership value this one in these element the membership value is this one here these one so this one. So, the different elements so different element have the different membership value and it is called the discrete what is called the values of the membership function. So, the membership values can be discrete, the membership values can be also continuous domain. (Refer Slide Time: 28:00) 34 And the element also can be a discrete. Here in this example all the element that belongs to these are defined in terms of discrete, quantities. The membership values also may be discrete or continuous. (Refer Slide Time: 28:27) So, what I want to say is that the element can be either discrete value or continuous value likewise any membership values for element can be of discrete values or it can be of continuous values. So, this is an example which basically shows how the membership values is continuous. For example, in this region, so membership values for any element in a continuous domain can be described by means of this curve. So, it like this whatever it is. So, membership value can be a discrete value element can be discrete value, the membership the value can be continuous the elements also can be continuous. 35 (Refer Slide Time: 28:57) Now, there are a few more things or their terminologies are there. I will quickly cover this terminologies within one minute. So that we can understand about it. So, the first terminology is called the support. The support of an element is of a fuzzy set denotes that whose membership value is greater than x. So, all these elements are basically the support which is belong to define this fuzzy set whose membership function is like this. So, what you can say that a fuzzy set in fact can be disclaim by means of a graph. (Refer Slide Time: 29:26) 36 Regarding these things will discuss in detail later on. Now here core A. Core A is basically all elements a which are having membership values is equal to 1. Now here the core A all these elements having the membership values 1. So, these basically denotes the core A and we can understand that core A essentially a fuzzy sets. (Refer Slide Time: 29:48) So, normality. Now a fuzzy set can be a termed as a normal it is basically a Boolean value either 0 or 1 or the crisp value if it contains at least one element which core value is non-empty; that means, it has at least one element whose membership value is one. And if it does not contain any element whose membership value is not equal to one then it is not a normal. So, normality is false. 37 (Refer Slide Time: 30:15) Now, crossover point. So they are the elements whose membership value exactly 0.5 is called the crossover point. For example, in this graph we can say this is the two elements it has the membership value 0.5 this also has the membership value 0.5. So, this element and this element whose belongs to the set x is basically the crossover point in this case. Few more terminologies we will discuss as the time is short so will discuss in the next lectures. Thank you. 38 Introduction to Soft Computing Prof. Debasis Samanta Department of Computer Science & Engineering Indian Institute of Technology, Kharagpur Lecture - 03 Fuzzy membership functions (Contd.) and Defining Membership functions So, we are discussing about some notations and terminologies that is required to understand the concept of fuzzy logic. So, few terminology we have discussed in the last lecture and today we will continue the same discussion, we will discuss few more terminology and so first is called the fuzzy singleton. (Refer Slide Time: 00:30) So, if a fuzzy set consists of only one element whose membership value is exactly one then such a fuzzy set is called the fuzzy singleton. For example, here this is the one fuzzy sets all the elements having the different membership values, but there is one element whose membership value is this one is basically one then it is called the fuzzy singleton. So, fuzzy singleton is like this. And now, we will discuss about another two important terms it is called the alpha cut and then strong alpha cut. 39 (Refer Slide Time: 01:05) The alpha cut of a fuzzy set it is denoted as A, A suffix alpha it is denoted as alpha A. The alpha cut is basically the crisp set x set of element say x such that, the membership values of this element is >=, where alpha is a predefined values and need not to say that alpha is basically a value in between 0 and 1 both inclusive. So, for example, A0.5 if I say like this; that means, it is basically the crossover points, the set of all crossover points that belongs to the set A. Likewise the strong alpha cut the difference between the two is basically greater than equals and in case of strong alpha cut it is basically greater than symbol otherwise the they are the same. So, we can easily understand that a support that we have discussed about is at A0 complements is basically complements and complement means other than the elements which belongs to 0 is A complement will discuss about the complement is just like a set complement you know inverse actually and similarly we also can say core A same as A1 from the previous discussion that we know. So, it is like this. So, core A is basically the alpha cut where =1. 40 (Refer Slide Time: 02:49) Now, we can define another term is called the bandwidth, bandwidth of a fuzzy set A. It is basically the difference between the two values of the element namely x 1 and x2 such that x1 and x2 both are the two crossover points. Obviously, if there is if there is a fuzzy set which contains more than two elements at the crossover point then that two extreme crossover point can be used to decide their bandwidth. So, bandwidth is basically the difference between the two extreme crossover points x1 and x2 like this. (Refer Slide Time: 03:37) 41 Now, we will discuss again a fuzzy set as a symmetric or asymmetric. We define a fuzzy set as symmetric with respect to one element x=c such that all membership values for all the elements in this region has the same and there is a corresponding membership corresponding elements having the same values. Alternatively or mathematically we can say that if the two elements x+ c and x−c have the same values for all element x that belongs to this set then we can say such a fuzzy set as the crisp set. In other word, crisp set is basically symmetry in form. But if we draw one then this then this is not a crisp set. Because here some elements and all elements may not have the same values like this one. So, this is the concept of symmetric fuzzy set. (Refer Slide Time: 04:39) The next is basically open and closed fuzzy sets. Now, here this is the one description of fuzzy set we can say open left. Now, we say the open left a fuzzy set is if it satisfy this definition. Now, we can say for the open left all elements which is beyond the x−∞ this side is =1 because it is basically one and limit x+ ∞ after this point is basically 0. So, there are two extreme limits this one where all elements is 0 and here all elements is one then such a fuzzy set along within this portion is called open. Similarly, we can write open right here, here all elements which x+ ∞ is basically one and here all elements which x−∞ is 0. So, this definition it is called the open right. So, open left and open right. Similarly the closed if we say for all element x−∞ and all element x+ ∞ if there the value is 0 then all this is basically called a fuzzy sets and this type of 42 fuzzy set is called the closed. So, there are maybe three different form of a fuzzy set are there open left or open right or closed. So, any fuzzy sets can be belongs to this category only either open left, open right or closed. Now, one thing just we want to clarify it is here and is there any link between fuzzy and probability. Now, there may be certain what is called the link or relation because if we see the fuzzy membership values is in between 0 and 1 both inclusive. (Refer Slide Time: 06:49) Similarly, if we say the probability value of something it also has the value in between 0 and 1 like this one. So, for the values are concerned both fuzzy and probability is synonymous, but there is a difference again. All these 0.1 or some decimal in between 0 and 1 alternatively can be expressed in the form of a percentage. So, 60 percent is equal to 0.6 like this one. So, anyway, that whether it is expressing the form of a decimal 0 point something or it is a percentage there is basically relation between the two things in that way, but there is a clear cut difference between the two, I want to clarify this I mean difference between the two with an examples. So, first example suppose a patient when come to the doctor and doctor carefully diagnose the patients and prescribe the medicine. Then what exactly the thing it happens is that doctor prescribes a medicine with certain certainty, let this certainty be 60 percent. This means that the patient is suffering from the flue and for that he is sure about this 43 is that 60 percent. In other words, that disease for which he prescribed the medicine will be cured with certainty of 60 percent and there is again uncertainty 40 percent. So, this is a concept that is related to the fuzzy actually it is the certainty or clarity or the guarantee like. On the other hand if it is the probability then we can say that probability is also 60 percent or sort of things or 0.6 like. For example, India suppose we will win the T-20 tournament with a chance 60 percent. If I say so it means that, we have certain statistics or some previous experience that out of hundred matches India won 60 matches. So, 60 percent in this case and 60 percent in the previous case has the two different significance. So, in the first case in case of doctor patient scenario it is basically the certainty and in the second case the 60 percent is based on the previous experience. So, this certainty versus experience this basically defined the fuzzy versus a probability. (Refer Slide Time: 09:12) Now, likewise this fuzzy versus probability there is another relation that is also related to this fuzzy and probability also it is just in the form of prediction versus product forecasting. So, fuzzy versus probability is also in many way analogical to prediction versus forecasting. Now, we can say the prediction when you start guessing about something. So, it is a guess, fuzzy means it is a guessing power. On the other hand forecasting means if we can say something based on the previous information or based on our previous experience, it is the 44 forecasting. So prediction, in other words, the prediction is based on the best guesses from the experts that basically who does it and forecasting is based on the data which you are already have in your mind and based on the processing of the data you can you can tell something. So, this is a forecasting. So, if prediction is related to fuzzy then we can say the forecasting is related to the other, that means, its probability. So, these are the things actually. So, sometimes we little bit get confused what about the fuzzy versus probability or like this one. (Refer Slide Time: 10:28) Now, next our point of discussion is basically fuzzy membership function. We have some idea about it and one thing I want to again mention it here a fuzzy set can be described better in the form of a graph that mean it is a graph versus all elements and their membership values. So, we can define in the form of a set theoretic form or in the form of a graph. So, in this slides we can see this is the one fuzzy sets and this is also another fuzzy sets. Now, the difference between the two fuzzy sets here is that here the elements which belongs to these fuzzy sets are having discrete values. So, there will be no element which in between 2 and 3 like. So, there will be no element there. But here is all elements in between the range 0 to 60 are belongs to this one. So, it is the elements say 21 and it is the fuzzy set is there. We have also discussed about that the membership values can be discrete value also. So, here it looks at all values are possible. So, here also the continuous values for all membership values and here need not to say it is also the continuous values of all membership values. So, that we have already discussed in the previous lectures that the membership function can be 45 on a discrete universe of discourse or can be a continuous universe of discourse, the membership value can be again discrete values or it can be again continuous values. So, whatever be the values it is there we have to express, maybe it is mathematically or using some graphical representation. So, these are the two examples where we had give the two fuzzy sets in the form of a graph. (Refer Slide Time: 12:17) Now, I want to give more graphical representation of the standard some fuzzy sets. So, these figures basically show some typical examples of the fuzzy sets and they are defined in terms of the membership function actually. And that this is the general looks that usually a fuzzy sets takes. And in the first, this is the one fuzzy set it is having the membership function in the form of a triangular shape. So, this is another fuzzy sets whose membership function is expressed in the form of a trapezoidal shape. This is another membership function I did basically curve it is look like a bell curve. So, it is called bell function bell membership function like. And it is the one membership function which does not have any a specific shape it is arbitrary shape is called the non uniform fuzzy sets. And this is also an example it is also a non-uniform fuzzy sets, however, it has some special meaning. So, this is the one fuzzy set it is called the open left, this is another fuzzy set is called the open right and this basically called the fuzzy set closed. In this sense it is also a closed, these are all the closed fuzzy set actually. 46 So, these are the all closed or open whatever I told you that either fuzzy sets can be open or open left, open right or is a closed anyway. So, these are the typical form of the fuzzy set which usually consider in our fuzzy system, in our fuzzy theorem and another point is that how such a fuzzy set can be better described in some mathematical notation so that we can process them in our future fuzzy system design. (Refer Slide Time: 14:02) I am going to discuss these things how a membership functions can be better mathematically described and then that mathematical specification can be used to process in subsequent requirement. So, in this direction first let us discuss about this is the one fuzzy sets or a membership function and this membership function as I told you it is a triangular membership function. So, usually this is can be described mathematically using this triangle and x is an element and this membership function can be defined by means of three parameters a b c. So, three parameters are the three what is called a meaningful direction here and in terms of these three parameters the membership function can be described mathematically using like this. So, it is clear that if x≤a , it is like this then this is 0 and in between a and b the membership function can be defined by this, this is basically slope whatever it is. Similarly, in between this one, this is another slope it can be defined like this and so for the element x> 0 this one it is basically 0. So, what you can say whatever the graphical representation which looks like this it can be described mathematically using this form. So, 47 this is a mathematical expression that a fuzzy set can be defined and definitely this fuzzy set is defined over a continuous universe of discourse. (Refer Slide Time: 15:48) Now, this is the triangular membership function using the same concept same idea we can define the other membership function. For example, in this slides we can show the trapezoid the membership function. However, unlike triangular membership function here we need the 4 different parameters they are called a b c d. So, these are the parameters are like here and in terms of these 4 parameters we can define this membership function like the if x≤a it is 0. And if x is in between a and b that means, in this one, so it is basically this one, which can be expressed by this form. And in between b and c this is a x, so it is basically 1. And in between c and d this is the slope which can be described by this one and if x> d then this is 0. So, with this, this concept can be describes in a mathematical manner this membership function now. So, this is a trapezoidal membership function triangular and trapezoidal are the two most frequently used membership function in fuzzy system in order to design a fuzzy system. 48 (Refer Slide Time: 16:55) The another important membership function that is more popular in fuzzy in order to describe a fuzzy system and this is called the Gaussian membership function. A Gaussian membership function typically takes in terms of two parameters c and sigma. So, is c basically is the middle point of this it is called the centroid or median mean and sigma is defined is a range between these two in between 0.1c and 0.9c if c is defined here then this 0.1c and 0.9c. So, this range is basically sigma. Anyway, so if we define two parameters like c and sigma then this membership function can be better expressed in the form of a mathematic notation using this one. So this basically the formula for Gaussian distribution, that is why it is called the Gaussian form. If we plot this form for a given values of c and sigma and for different values of x then the graph will look like this. As this graph is looks like a bell shaped, so it is called the bell shape membership function also. 49 (Refer Slide Time: 18:12) So, this is the one popular membership function like this is the membership and there are many more and another is called the Cauchy membership function. So, it is just like a Gaussian membership function, but this membership function defined in terms of three parameters a b c. And using these three parameter how a membership function is defined it is expressed here and it has two characteristics here that it considered two points for the slope. So, slope at this point it is called the c−a and another is c +a the slope of this point is basically b/ 2 a and at this point is −b/2 a. So, if we define a b and c then all these values their slope and point can be defined and accordingly the membership function can be defined. So, the membership function that can be defined using Cauchy membership function is this and if we plot this membership function for a given the values of a b c then the graph will look like which is shown here. 50 (Refer Slide Time: 19:14) So, this is the another popular Cauchy membership, Cauchy membership function or it is sometimes is called the generalized bell. Now, this is a typical example of generalized bell for particular value of a b c where a=b=1 and c=0 ; that means, it is basically c=0 and these are the function and if we plot these things you essentially if we plot this one then it can give back up like this. So, we can plot it and then you can have this curve. So, this is basically graphical representation of this one. (Refer Slide Time: 19:47) 51 So, there are few more membership function. Anyway before going to these things for the for the different values of a b c and whatever it is there, so this membership function will look the difference shape and hence the different membership function or the different fuzzy elements can be defined. So, this is basically the idea about the membership function can be expressed in the form of a graph as well as in the form of a some mathematical notation. (Refer Slide Time: 20:06) Now, this is another very popular the membership function it is called the sigmoidal membership function. A typical look of the sigmoidal function is shown here in this form. It is basically indeed form the s. So, that is why it is called the sigmoidal membership function just like a s. This kind of the membership function defined in terms of two parameters a and c, where c denotes the point it is like this and a is any arbitrary value, it is basically called the slope of this point at a. Now, if we take this kind of values then the sigmoid function can be plotted and if we follow this expression. So, if this is the expression if we follow then graph can be obtained for this expression for different values of a, it is shown like here. So, we can see here one example. If x∞ as you show it is basically, in this way is basically closed right and in this case it is basically open right. Because for all value the x which is ¿∞ the membership value is 1 and few here for all value the x−∞ the membership value is 0. So, sigmoid is typically like this and for the different values of a, the different curve will be obtained. For one values of a, the curve will be like, for another value of a the curve will be 52 like, for another is there and so on. So, if we change the values of a, the different pattern of the curve will be obtained. So, what I want to mention here is that this is an important function, which can have the different values of a and c and the different membership functions can be obtained and hence the different fuzzy sets, the different form of the fuzzy set look of the fuzzy set also can be obtained. So, this is another membership function that is very much popular in the design of fuzzy system. (Refer Slide Time: 22:08) Now, we come we can discuss one example. So, that how these membership functions can be used. We are discussing about one idea about that how the grading in the form of a crisp. 53 (Refer Slide Time: 22:21) So, these are the crisp formulation of the grading and here the same thing which can be discussed in the form of a fuzzy, another fuzzy representation. So, for example, the grade this one is one and grade is this one. So, these are the two different form. So, as we say, this can be discussed with some function and this kind of membership function can be discussed by means of say Cauchy MF or generalized bell like. So, basically this membership function can be used to different what is called the fuzzy sets in the different range. So, this is a one fuzzy set in one range, this is another fuzzy sets and this is another fuzzy sets like. So, we can use the same formulation for defining membership function. In this case other than these sets or other than these sets, these two sets can be defined either using open left or closed left with another membership function, but all the other membership function in between the range and they can be defined in terms of some graph or in terms of some mathematical notation say Cauchy membership function like and then they are basically called the different fuzzy set. For example, if we define one membership function in this form, we can say that these are bad fuzzy sets; where the universe of discourse is this one; and the elements belong to this is this one; within this element up to this is the membership elements see value is one and after this thing membership value is decided by this what is called the function. Similarly, the another membership function like this one. It can be defined in terms of this is a universe of discourse; the elements is in between, for all elements it is 0, for all other 54 element is 0 and in between this the membership value will be decided by the type of the curve. So, these are the basically the way which we can use to define the membership function for the different elements. So, we have understood about the different membership functions and their mathematical representation. (Refer Slide Time: 24:24) We will quickly cover few more concept about the membership function the two concept it is called the concentration and the dilation. So, the idea is that, if A is a fuzzy set given to you right, then we can define another fuzzy set then let this fuzzy set be A k , where k is some μA ( x ) value that may be greater than equals to greater than 1, such that this [ is the new ¿ ¿k membership values for the element x which is belongs to the set A k. So, this means that if A is known with μ A ( x ) is a membership value then we can derive another fuzzy set Ak with membership value this one. And for k > 1, if it is like this, then it is called the concentration. Similarly, if it is k < 1 the same thing if whole goods then it is called the dilation. So, this is a very important concept that from a given fuzzy set we can find more fuzzy sets many more fuzzy sets, this fuzzy sets can be obtained by simply using some mathematical notation like this concentration or dilation. 55 Now, you can recall each fuzzy set basically used to express something say high temperature or low pressure or sweet apple whatever it is there. So, such a things in fuzzy concept it is called the linguistic hedge. That means, high temperature the linguist hedge it is that temperature is high, but temperature is high; that means, the different temperature is high with the different membership values. Similarly, if we say the pressure is low; that means, the different pressure can be termed as low and then same pressure can be termed as belongs to low pressure or high pressure. So, here pressure low, pressure high they are called the linguistic hedge. Likewise there are many linguistic hedge. For example, related to our age. We can define related to our age say young, middle aged and old. So, these are the three fuzzy sets if you can define then from these three fuzzy sets, we can easily define another fuzzy set likes a very young, not very young or like this one. Similarly if the old is a fuzzy set, very old, very very old, extremely old all these fuzzy sets. Now, the question is that how these kind of fuzzy sets can be obtained if a fuzzy set is available already with us. Here is an example we can use or you can use the concept of concentration and dilation to do these things. Now, here for example, μExtremely old say if we know that μx is a fuzzy set which is defined for the old fuzzy set and x is any elements belong to the fuzzy set old then any elements belongs to the fuzzy set extremely old having the membership value μExtremely old ( x ) that can be obtain like this. So, it is basically μold ( x ) x (¿ ¿2) that is the original fuzzy sets having the membership value and we can take (¿¿ 2)2. So, ¿ ¿ this is basically gives that very old, this is very very old and this is basically extremely old. So, these are the different linguistics can be obtained and here we have used the concept of concentration. Now, similarly if more or less old if μx is defined for the old fuzzy sets then more or less for k value say 0.5 we can define this one. So, it is called the dilation. Now, graphically the same thing can be plotted nicely we can say it. Here is an example. 56 (Refer Slide Time: 28:04) So, we can write it. So, if suppose this is the fuzzy set young. Then by applying the dilation we can say the very young we can define like this another fuzzy set. Similarly if this is the fuzzy set old then using the concentration we can define another fuzzy set a very old like this one. So, the different fuzzy sets can be obtained different fuzzy sets can be obtained from existing fuzzy sets if we follow some concentration and dilation formula. Here is few example again, μ young ( x ) is one fuzzy set defining membership function fuzzy set young defining each membership function as μ young ( x ) and it is supposed defined by means of bell shaped curve that we have discussed and this is the curve. Then μold also another fuzzy set which is defined by another bell shaped curve which is like this one. Now, given these two we can define the other not young. So, not young can be defined 1−μ young ( x ). So, this is the another fuzzy sets the value or membership values belongs to another fuzzy set let the name of the fuzzy set be not young. So, this can be derived from the fuzzy set young. So, as another example young, but not too young we can define this kind of concept. So, μ young ( x ) and it is complement of this one. So, it is young and it is not young. So, young, but not young can be defined by this one. Now, regarding this kind of formulation we will discuss in details in our next lectures. So, what I want to say here that given a fuzzy set we can derive another fuzzy set easily using 57 some mathematical computation and formulation. So, these are the things it is there we have discussed about the concept of fuzzy sets first and then we learned about what is the difference between crisp set, versus fuzzy sets. Subsequently we learned about the different membership function that is with which we can define fuzzy sets and then different properties in it. And how the membership function can be better mathematically expressed also we have learned it. And we will discuss about the different fuzzy set operation in our next lecture. Thank you. 58 Introduction to Soft Computing Prof. Debasis Samanta Department of Computer Science & Engineering Indian Institute of Technology, Kharagpur Lecture – 04 Fuzzy operations So, we have learned about fuzzy set. Fuzzy set is the basic element in fuzzy system. Today we are going to learn about the different operations on fuzzy sets. (Refer Slide Time: 00:30) So, the different operations on the fuzzy set in many ways similar to the operation those are application to the crisp set. And this is the normal set that we have learned in set theory, the operation those are applicable they are in crisp set such as union, intersection, complement all those things also are applicable to the fuzzy sets. But the definition of all these operations are with different implications. So, we learn one by one the operations on the fuzzy set. So, let us first discuss about the union operation of two fuzzy set. Now here A and B are two fuzzy set suppose. So, union of two fuzzy sets is denoted by the symbol ∪. This is the usual symbol that is used they are in crisp set. So, A ∪ B denotes the union of two fuzzy sets A and B. Now the union operation whenever it is performed on the two fuzzy set it will basically give the membership functions for each elements which are belongs to the union of two fuzzy sets, the membership values for different elements in the union of the two fuzzy set is defined by this expression. 59 So, if we see this expression. So, union operation for any element x which belongs to the union of two fuzzy set A and B is basically max(μ A ( x ) , μ B ( x )) , where μA ( x ) denotes the membership values for an element x belongs to fuzzy set A and μB ( x ) denotes the membership value of the any element x belongs to fuzzy set B. Now, let us have an example. Say, here A is a fuzzy set which is defined with the different membership values for different element shown here, similarly B is the another fuzzy set. Now the union of two fuzzy set is denoted as C which is A ∪B is basically this is the fuzzy sets. So, union operation gives another fuzzy set. Now here we can see how we have obtain the membership values for the different elements which belongs to the sets C. So, here 0.5 it is obtained as the max of these two value 0.5 and 0.2 it is as per the definition. Similarly 0.3 it is basically max of the two values membership values they are in the set A and B and likewise. So, this way we can obtain the union operation of the two fuzzy sets. Now, the same thing can be better explained with the help of a graph. So, here we see the graphical representation of two fuzzy sets A and B. The graphical representation means it is basically a representation of the membership function how they change a change with the different values of elements belongs to the two sets. Say here the two sets with the universe of discourse. So, this is basically the universe of discourse of the two sets and the fuzzy set A is defined by it is membership function for the different element, which is denoted here, this is the membership element, membership function for the fuzzy set A. Similarly this denotes the membership elements for the fuzzy set B. Now as the union operation is basically max of the two values. So, upto this portion so this is the B and this is A, so the max is this one. So, these basically the union upto this part upto this part and then so union of these and these basically the max. So, it is this 1 this part is the rest of the value upto this one. So, this way we obtain the membership function of the union of the 2 fuzzy set which is represented by this graph. 60 (Refer Slide Time: 05:02) Now let us discuss the intersection operation. Intersection operation of two fuzzy sets is denoted by this symbol it is ∩. So, here and the membership functions of the resultant fuzzy set A ∩B is denoted by this expression and you can say in case of union it was max whereas, in case of intersection we have to take the minimum of the two values of the membership for which the A and B belongs. Now, as an example A is the another set and B is the another set and the intersection of the two set is represented here. Now here whenever we go for intersection for the element x1 then we have to take the minimum. So, we take the minimum from here. So, it is the minimum. So, here 0.1 which is in A and 0.3 for x2 which is in B and in the union operation where the x 2 has the value minimum this one so 0.1. So, this way we can obtain the intersection of two fuzzy sets. Now, the same thing again can be drawn graphically. So, this is the fuzzy sets A and this is the fuzzy sets B and we have to take the minimum of the two. So, for upto these part minimum of A and B it is basically this one. So, we can obtain this part and for the rest minimum of this one is this one, so we can take this one. So, this graph basically shows the membership functions of the union of two fuzzy sets A and B. 61 (Refer Slide Time: 07:01) Now another operation on the fuzzy set is called the complement. The union operation and intersection operation are the binary operation, because they needs two fuzzy sets whereas, the complement operation is an unary operation, which is applicable to only one fuzzy set. The complement operation on any fuzzy set A is represented by the symbol A c. So, it is basically a complement of the fuzzy set A and the resultant value of the membership functions is defined by this expression μ A ( x ) is; that means, is a membership function of c the resultant fuzzy set is c and it is denoted as 1−μ A ( x ) where μA ( x ) denotes the membership function for the fuzzy set A. c Now, if this is an example. So, A is the fuzzy set and then it is compliment A is like this. So, for x 1 we have to take the this formula 1−μ ( x ) , so it is 0.5. So, for the 0.1 it is 0.9 for 0.4 it is 0.6. So, the complement operation is straight forward. The same thing again can be shown graphically. So, this is the fuzzy set for this is the fuzzy set A where the membership function is like this. Now it’s complement, so the complement value of these is basically this one and complement value of these basically this one. So, the resultant value of the membership function for the complement A is basically this one. So, this way the complement operation can be obtained. 62 (Refer Slide Time: 08:55) So, these are the very simple operations union, intersection and complement. There are few more operations. The first operation in this context is called algebraic product or vector product. Now algebraic product or vector product is denoted by a dot symbol; algebraic product or vector product is denoted by the dot symbol, A ∙ B where A is a fuzzy set and B is another fuzzy set. So, the membership function for the resultant fuzzy set is denoted by this and it is obtained using this formula. It is basically simple as a product of the values of the membership functions belongs to the fuzzy set A and B. Now if A is a fuzzy set {x 1 ,0.5 } and {x 2 ,0.3 } this is the fuzzy set and B {x 1 ,0.1 } {x 2 ,0.2 } then the μ A ∙ B ( x ) for C that can be obtained. So, x1 and it is basically product 0.5 and 0.1. So, it will give you 0.05. Similarly x 2 it will give you 0.06 and so on. So, this way the product can be obtained. So, this is the vector product. Now like vector product is a scalar product where α is a constant; α is a constant usually value in between 0 and 1 both inclusive. So, the scalar product of a vector A is denoted by this formula, μαA ( x ) where αA is a basically scalar product of the fuzzy set A and it’s new membership value is defined as is a product of α and the membership values of the function μA ( x ). 63 (Refer Slide Time: 11:24). Now, there are few more operations one by one let us discuss them. So, the first operation is sum of the two fuzzy set A and B, it is denoted by the sum of the two fuzzy set A and B is denoted by A + B , + operation and it’s new membership function is denoted by this expression. It is easy to evaluate if we know the μ A ( x ) for the fuzzy set A and μB ( x ) for the fuzzy set B, then μ A +B for the fuzzy set A + B obtained using this formula. Now, the difference operation on two fuzzy set A and B is denoted by this notation A−B , which is equivalent as the A ∩B C and it can be obtained using this expression μ A− B ; that means, membership value of the difference of the two fuzzy set A and B is same as the membership values of μ A ∩ B ( x ). So, if we can calculate. So, better idea is that we can C C calculate the A ∩B and then the μ can be obtained easily from there. Now, there are disjunctive sum it is denoted by this expression A ⊕B like and it can be obtained using this one. So, ( AC ∩B) ∪( A ∩ BC ). So, this means that if we know these operations first and then this operation then we will be able to calculate A ⊕ B. Now this is the disjunctive sum. Next is bounded sum, bounded sum expression is basically denoted by this where A and B are the two fuzzy sets and the membership values of the resultant fuzzy set it is denoted by this, it is basically obtained using this formula. So, it is basically take the minimum of {1, μ A ( x )+ μ B ( x ) } fuzzy set B. 64 So, this is bounded sum and another is bounded difference. The bounded difference is expressed by this notation and it’s membership value can be obtained using this formula. It is the maximum of {0, μ A ( x )+ μ B ( x )−1 }. So, we can take the maximum of these two values for each element x, then we can obtain the fuzzy set membership values of the elements which belongs to the bounded difference. (Refer Slide Time: 14:31) Now equality and power, these are the other two fuzzy sets. We say two fuzzy sets A and B they are equal and it is denoted by it is denoted by it is denoted by this expression A=B. So, two fuzzy sets are equal if for all elements belong to the set has the same membership value, so which is represented by this expression. Now power of a fuzzy set which is denoted as A α , where α is a constant any value, then the resultant fuzzy sets whose membership value can be obtained using this expression, where this is the membership values μ of the resultant fuzzy sets and μ A ( x ) is the original fuzzy sets and here (¿¿ A ( x ))α. α ¿ So, it is a exponential operation that can be applied for each elements belongs to the set x then we can obtain the resultant membership values belongs to the set A α. Now we can note if α>1 then it is called the concentration and if α0.5 , so it is expanding, that means, this is the P1 and P2 , it will calculate the chromosome any one region within this region. 407 (Refer Slide Time: 24:32) So, this is the idea about the simulated binary crossover techniques that is there and now, simulated binary crossover has a number of advantages compared to the previous two techniques that we have discussed and as in case of linear crossover and blend crossover in this technique also, we will be able to generate large number offspring from 2 parents. So, in that case what we have to do is that we have to generate as many as random number as many we want to have the children's and it in fact allows more exploration with diverse values of offspring, which is comparable to the both linear as well as the binary the blend crossover technique. Here the results, usually gives more accurate results compare to the linear and blend crossover techniques and usually it gives the global optima, whereas other two techniques usually stuck into the local optima and it basically terminates with a less number of iterations because number of iterations that is required to run the GA is it is in fact, observe that more in case of linear than blend crossover. So, in that sense it is also cost effective, although it is the costly operation in case of crossover, but so far the GA iteration is concerned it require less, so that means, effectively it is a faster GA algorithm than the crossover technique if we follow linear and blend cross over technique. And here, actually crossover techniques are independent of the length of the chromosome, whatever be the values of the chromosome, that means, the parent values have many number of gene absolutely no problem, we will be able to run effectively using the same techniques. 408 So, it is fast in that case because the same alpha dash that can be used to calculate the different gene values for the chromosomes, if we take the different this one. So, in the same line we will be able to follow, no need to discuss, no need to consider the different gene ' values and the different α and then different random number generation, it is not required. So, in one set the same α ' can be used to calculate the different gene values for the offspring for the different parent values or different parent values of the different genes. (Refer Slide Time: 26:46) So, this is the advantage of this one. However, it is suffering for another limitation as well as computationally expensive compared to the binary crossover technique. I am now comparing not the linear crossover or blend crossover, but the binary cross over which we followed in case of the binary coded GA. So, if we see, all the binary cross over techniques are very fast and straight forward and pretty simple also, whereas this similar type binary crossover is little bit computationally expensive. Now, again there is a decision regarding the probability distribution function, if you do not choose the proper probability distribution function or if you do not choose the q values, that is required in case of I mean in probability distribution function decision, then you may lead to an erroneous results and premature convergence. So, user needs to be little bit careful about choosing the right values of probability distribution; right probability functions for contracting as well as expanding function and also the correct values the q that is to be used in the probability distribution function. 409 So, this is the technique that we have discussed so far the simulated binary crossover is concerned and so we have so far discussed about the two different GA technique, one is the binary coded GA, another is real coded GA and there are several crossover operations. We have learned in binary coded GA and then, just now we have learned about the crossover techniques in the real coded GA. There is another GA encoding scheme which we will discuss, this is the order GA and we will discuss the crossover techniques that is required for the order GA in the next class. Thank you. 410 Introduction to Soft Computing Prof. Debasis Samanta Department of Computer Science & Engineering Indian Institute of Science, Kharagpur Lecture – 22 GA Operator: Crossover (Contd.) So, different GA encoding scheme follow the different pattern of chromosome. The binary coded GA follow the binary patterns. The real coded GA follow the real values of the gene values and depending on the patterns that it is following binary coded GA. So, the binary cross over techniques were used. We have learned over the binary crossover techniques. Now, real value coded GA, again it is a totally different than the binary crossover techniques because it needs the several totally different what is called the treatment. Now, we are going to discuss another GA technique. It is called the order GA and the crossover technique that is there in the order coded GA. (Refer Slide Time: 01:04) Now, again the order coded GA as we know, it is basically based on the concept of the sequence of the values that is there in the GA. So, the sequence is important. As the sequence is important for example, the travelling salesman problem if we follow that all the values that is there in the chromosome should not be repeated and they should follow certain sequence actually. Now, this means that if we follow the binary crossover techniques; obviously, these 411 are the basically in terms of symbols, so no real values are involved. So, that is why we cannot apply the real coded GA. However, the binary coded GA cannot, the crossover technique that is used in binary coded GA also cannot be applied here, this an example because how the binary coded the crossover technique that is followed there in binary coded cannot be applied here. Now, if you considered say binary crossover technique namely the single point crossover technique, we can recall that we have to generate a K point there, so if this is the K point, then basically the swapping these two, so it is swapping these two, swapping these two, we will get this one and then swapping this one also will get this one. So, it is basically from these two parent chromosome using the binary single point crossover we will get it, but you can note that this parent chromosome is not a fusible chromosome or in order to acceptable chromosome because A it is common here, B, B is copied here and all the chromosome that is not all so possibly present here. So, this is not a valid chromosome or this is also similarly not a valid chromosome. That means, the simple single point crossover technique that is used there in binary crossover, it is not applicable to the order GA in fact. So, this means that order GA needs a different treatment, so far the crossover operation is concerned. (Refer Slide Time: 03:01) 412 So, we will discuss about the different crossover technique that is followed in case of order coded GA, we have listed few important techniques five important techniques are there, it is one is called the Single-point order crossover, then second is Two-point order crossover, then Precedence-preservation crossover, it is called the PPX, then Position based crossover and then Edge recombination crossover. All these crossover techniques we will discuss one by one in the next subsequent slides. (Refer Slide Time: 03:29) Now, in order to discuss the different technique that we have mentioned in the last slides, we will follow certain assumption for all the techniques to discuss. The first is that we will consider that the length of the chromosome be denoted as L. L is an assumption that the length of the chromosome this one. P1 and P2 are the two parents which are selected at random from the meeting pool and C1 and C2 denotes the two children which we want to derived from the P1 and P2 by virtue of the crossover techniques followed there. So, these are the assumptions. Under this assumption, we will be able to discuss each technique one by one. Let us first start with Single point crossover technique in order GA. 413 (Refer Slide Time: 04:13) Now, so if L be the length of the chromosome and P1 and P2 are the two chromosomes. Then, in this technique the first task is to generate one number that number should be in between 1 and L and let this number be K. So, it is basically the same as single point crossover is a kinetochore point like. So, K point is to be decided first. Once, the K point is decided this K point is decided then is the next point, next task is we have to copy. So, K point is a kinetochore point that is the point that can define the two parts in both parents, so left part and right part or you can say left schema and then right schema. Then, the second step, copy the left schema of P1 into the children C1. C1 is initially empty and then left schema of P2 into C2 and then for the schema in the right side of C1 copy the gene value from P2 in the same order as they appear, but not already present in the left schema. So, if you repeat the same procedure to compute C2 from P1 , then you will produce the two children solution. So, this is a technique or scheme that is there we have to follow it. Now, let us see how these techniques are there as an illustration, so that you can understand this technique better. 414 (Refer Slide Time: 05:40) So, we assume these are the two solution appearance P1 and P2 and then a random K point is decided, this is the K point from where the left schema and right schema. So, this party is the left schema and this is the right schema for the parent P1 , similarly this is a left schema for the parent P2 and the right schema for the parent P2. Now, according to this technique, so idea is that, we will copy the left schema from P1 to C1. So, it is basically copy, this part is copied to this one and for the rest of the part we will copy from the P2 ; from the P2 , but provided that value is already not present in the left part. For example, i