Tuesday, August 29, 2006
Decision Support System - Part II – Prof. Chandan Bhattacharya
Decision Support System – Prof. Chandan Bhattacharya – 17th July, 2006.
GENETIC ALGORITHM
Genetic Algorithm is a way of solving problems by mimicking the same process or processes that the Mother Nature uses.
It is basically a searching process with approach to optimization of the problem based on same sample data. They use the same combination of selection, recombination & mutation to evolve a solution to a given problem.
At the beginning of a run of a genetic algorithm, a large population of random chromosomes (a string of real numbers / a binary string) is created. Each one, when decoded with represents a different solution to the problem. Let there are ‘M’ no of Chromosomes in the initial composition. The following steps are repeated until a solution is found.
1) Test each chromosome to see how good it is at solving the problem & assign a fitness score accordingly. The fitness score is a measure of how good that chromosome is to solve the given problem.
2) Select 2 members from the current population. The chance of being selected is proportional to the chromosome fitness.
3) Dependent on the crossover rate, crossover the bits from each chosen chromosome at a randomly chosen point.
4) State through the chosen chromosomes bits & flip dependent on the mutation rate.
5) Repeat step 2,3 & 4 until a new population of n number has been created.
CROSSOVER RATE
This is simply the chance that 2 chromosomes will swap their bits. Crossover is performed by selecting the random gene along the length of the chromosomes & swapping all the genes after that point.
X 10111001 011101
Y 11001011 101000
Becomes: -
X 10111001 101000 (final output)
Y 11001011 011101
Informative part is called MOTIF & the rest is called CROSSOVER.
Diagram
MUTATION
This is the chance that a bit within a chromosome will be fit (0 changes to 1 & 1 becomes 0). This is usually a very low chance. Whenever chromosomes are chosen from the chains the algorithm first checks to see if crossover should be applied & then the algorithm iterates down the length to each chromosome mutating the bits if applicable.
Given the digits 0 through 9 & operators +, -, X, / find a sequence that will represent a given target number. The operators will be applied sequentially from left to right as you read.
Eg: 4 – 3 * 6 = 1 * 6 = 6
23 => 6 + 5 * 4 / 2 + 1 (9 genes)
= 0110 1010 0101 1100 0100 1101 0010 1010 0001
= 011010100101110001001101001010100001 (Chromosome)
This has been obtained from the chart below: -
0 - 0000
1 - 0001
2 - 0010
3 - 0011
4 - 0100
5 - 0101
6 - 0110
7 - 0111
8 - 1000
9 - 1001
+ - 1010
- - 1011
* - 1100
/ - 1101
blank - 1110
blank - 1111
Steps: -
1) First we need to encode a possible solution as a string of bits to represent all the different characters available to the solution. This will represent a gene.
Each chromosome will be made up of several genes. The above, show all the different genes required to encode the problem.
The possible genes 1100 1111 will remain unused & will be ignored by the algorithm if encountered. Hence the target no 23 would represent 9 genes as follows. These genes all together form the chromosome.
FITNESS FUNCTION
This can be the most difficult part of the algorithm to figure out. It really depends on the problem to solve. The general idea is to give a higher fitness score; the closer a chromosome comes to solving the problem.
A fitness score can be assigned that is universally proportional to the difference between the solution & the value, a decoded chromosome represents.
Assuming solution target no is 42, the fitness score of the chromosome mentioned above
1 / (42 – 23) = 1 / 19
If a solution is found, a divide by zero, error would occur, as the fitness would be 1/ 42 – 42. This is not a problem, as we are looking for a solution and not a mathematical data.
Decision Support System – Prof. Chandan Bhattacharya – 25th July, 2006.
NEURAL NETWORK
A Neural Network is a massively parallel-distributed processor made up of simple processing unit, which has a natural characteristic for storing experimental knowledge and making it available for use. It resembles the brain in 2 respects: -
1) Knowledge is acquired by the network from its environment through a learning process.
2) Inter-neuron connection strengths, known as synaptic weight, are used to store the acquired knowledge.
BENEFITS OF NEURAL NETWORKS
1) Non-linearity – An artificial neuron can be linear or non linear. A neural network made up of an interconnection of nonlinear neurons is itself a non linear.
2) Input / Output Mapping – A popular technique of learning, called supervised learning involves modification of the synaptic weights of a neural network by applying a set of labelled training samples or task examples.
3) Adaptability – Neural Networks have a built in capability to adopt their synaptic weights, to changes in the surrounding environment.
A neural network trained to operate in a specific environment can easily be retrained to deal with minor changes in the operating environmental conditions.
4) Evidential Response – In the context of pattern classification, a neural network can be designed to provide information not only about which particular pattern to select but also about the confidence of the decision made.
5) Contextual Information – Knowledge is represented by the very structure 7 activation state of a neural network. Every neuron in a network is potentially affected by the global activity of all other neurons in the network.
6) Neurobiological analogy – The design of a neural network is motivated by analogy of the brain, which is a living proof of fault tolerant parallel processing.
Diagram 1
Diagram 2
(Mapping how should work if we make analogy to a human brain)
Nonlinear Model of Neuron
A neuron is an information-processing unit that is fundamental to the operation of a neural network.
The diagram above shows the model of a neuron, which forms the basis of designing artificial neural network. The model comprises of the following key elements.
1) A set of synapse or connecting links, each of which is characterised by a weight or strength of its own. A signal ‘xj’ (1 <= j <= n) Specially ‘xj‘ at the input of synapse j connected to neuron k is multiplied by the synaptic weight ‘wkj’. Unlike a synapse in the brain, the synaptic weight of an artificial neuron may be negative as well as positive values.
2) An adder for summing the input signals, weighted by the respective synapse of the neuron forms a linear combiner.
3) An activation function for limiting the amplitude of the output of a neuron is called squashing function.
The neural model includes an externally applied bias denoted by ‘bk’ which has the effect of increasing or lowering the net input of the activation function.
In mathematical terms we now may describe a neuron k by the following equation: -
m
Uk = Σ Wkj xj
j=1
Yk = Φ (uk + bk )
Where,
x1, x2 …….xn are the input signals,
wk1, wk2 ………xkn are the synaptic weights of neuron k
uk is the linear combiner output
bk is the bias
Φ() is the activation function &
yk is the output signal of neuron ‘k’.
Inparticular depending on whether the bias bk is +ve or –ve the relationship between the induced local field for activation potential vk of the neuron k and the linear combined output uk is modified by induced local field.
DIFFERNECE BETWEEN NEURAL NETWORK AND EXPERT SYSTEM
Expert system like post-traditional systems seek to emulate or model, human experts way of solving a set of problems. The Knowledge Engineers observe humans, builds a model of their expertise and writes a computer programs or algorithm that implements the model. The program incorporates specific rules, which are derived from human experts & their experience in a limited problem domain. Neural Networks do not model human intelligence nor to use knowledge engineers to solve a specific problem. Instead of putting intelligence into program neural network designers.
Others:-
FUZZY LOGIC
Professor Zadeh reasoned that people do not require precise numerical information input & yet they are capable of highly adoptive control. If feedback controllers could be programmed to accept noisy, imprecise input they could be much more effective and perhaps easier to implement.
Fuzzy Logic is a problem solving Control System methodology that lend itself to implement in systems ranging from simple, small embedded micro-controllers to large, networked, multi-channel PC or Work-Stations based data acquisition and Control Systems. It can be implemented in Hardware, Software or a combination of both. If fuzzy logic provides a simple way to arrive at a definite conclusion based upon vague, ambiguous, imprecise, noisy or even missing input information.
Fuzzy Logic incorporates a simple, rule based IF X AND Y THEN Z approach to a solving control problem rather than attending to model a system mathematically. The fuzzy logic model is empirically based and relies on operator’s experience rather than technical understanding of the system.
Fuzzy Logic requires some numerical parameters in order to operate such as what is considered to be significant error and significant rate of change of error, but exact values of these numbers are usually not critical unless very responsive performance is required.
WHY USE FUZZY LOGIC
1) It is inherently robust since it does not require precise, noise free inputs. The output control is a smooth control function despite a wide range of input variations.
2) Since the Fuzzy logic Controllers processes user defined rules, it can be modified easily to improve or alter system performances.
3) Fuzzy Logic is not limited to a few feedback inputs nor is it necessary to measure or compute rate of change parameters.
4) Because of the rule based operation any reasonable number of inputs can be processed and numerous output can be generated with more limited responsibilities.
5) Fuzzy Logic can control non-linear system that would be difficult or impossible to model mathematically.
Suppose we want to design a simple proportional temperature controller with an electric healing element and a variable speed cooling fan. A positive element output calls for 0 – 100 % heat while a negative signal output calls for 0 – 100 % cooling. Control is achieved through proper balance and control of these two active devices.
Diag DSS 4
Cmd: Target Temperature
Temp: Feedback sensor in Controlled environment.
Error: Cmd – Temp ( + = too cold ; - = too hot )
Cmd-dot : Time derivative or Error ( + = getting hotter ; - = getting cooler )
Output: HEAT or NO CHANGE or COOL
A simple block diagram of the Control System
Notations:
N – Negative error or error dot in input level
Z – Zero(0) error or error dot in input level
P – Positive error or error dot in input level
H – Heat output response
- - No change
C – Cool
Rule Structure & Rule Matrix: (assuming 3 X 3 matrix)
Diag DSS 5
Rule Structure:
1) If Cmd - Temp – N and d/dt [Cmd – Temp)] = N then output = C
2) If Cmd - Temp – Z and d/dt [Cmd – Temp)] = N then output = H
3) If Cmd - Temp – P and d/dt [Cmd – Temp)] = N then output = H
4) If Cmd - Temp – N and d/dt [Cmd – Temp)] = Z then output = C
5) If Cmd - Temp – Z and d/dt [Cmd – Temp)] = Z then output = NC
6) If Cmd - Temp – P and d/dt [Cmd – Temp)] = Z then output = H
7) If Cmd - Temp – N and d/dt [Cmd – Temp)] = P then output = C
8) If Cmd - Temp – Z and d/dt [Cmd – Temp)] = P then output = C
9) If Cmd - Temp – P and d/dt [Cmd – Temp)] = P then output = H
Definition:
System Status Input:
[Error] – P – Too Cold
Z – Just Right
N – Too Hot
[Error dot] – P – Getting Hotter
Z – Not Changing
N – Getting Colder
System Status Output:
H – Call for heating
C – Call for Cooling
NC – No Change
GENETIC ALGORITHMS
Genetic Algorithms are a way of solving problems by mimicking the same process that the nature uses. They use the same combination of selection recombination and mutation to evolve a solution to a problem. Every organism has a set of rules. These rules are encoded in the genes of an organism, which in turn are connected together into long strings called chromosomes. A typical chromosome may look like follows when it is coded in binary sequences: -
10010010110010………………..
At the beginning of run of genetic algorithm, a large population of random chromosomes is created. Each one, when decoded will represent a different solution to the problem. Let us assume that there are N chromosomes in the initial population. The following steps are repeated until a solution is found: -
1) Test each chromosome to see how good it is at solving the problems and assign a fitness score accordingly. The fitness score is a measure of how good that chromosome is at solving the problem.
2) Select two members from the current population. The chance of being selected is proportional to the chromosome fitness.
3) Dependent on the crossover rate, crossover the bits from each chosen chromosomes at a randomly chosen point.
4) Step through the chosen chromosome bits and flip dependent on the mutation rate.
5) Repeat step II, III, IV until a new population of N members has been created.
Soln: - max[min[(A,B),(B,D)],min{A,C),(C,D)]]
So, max[min[0.8,.05],min[9,6]]
= max[0.5,0.6]
= 0.6
GENETIC ALGORITHM
Genetic Algorithm is a way of solving problems by mimicking the same process or processes that the Mother Nature uses.
It is basically a searching process with approach to optimization of the problem based on same sample data. They use the same combination of selection, recombination & mutation to evolve a solution to a given problem.
At the beginning of a run of a genetic algorithm, a large population of random chromosomes (a string of real numbers / a binary string) is created. Each one, when decoded with represents a different solution to the problem. Let there are ‘M’ no of Chromosomes in the initial composition. The following steps are repeated until a solution is found.
1) Test each chromosome to see how good it is at solving the problem & assign a fitness score accordingly. The fitness score is a measure of how good that chromosome is to solve the given problem.
2) Select 2 members from the current population. The chance of being selected is proportional to the chromosome fitness.
3) Dependent on the crossover rate, crossover the bits from each chosen chromosome at a randomly chosen point.
4) State through the chosen chromosomes bits & flip dependent on the mutation rate.
5) Repeat step 2,3 & 4 until a new population of n number has been created.
CROSSOVER RATE
This is simply the chance that 2 chromosomes will swap their bits. Crossover is performed by selecting the random gene along the length of the chromosomes & swapping all the genes after that point.
X 10111001 011101
Y 11001011 101000
Becomes: -
X 10111001 101000 (final output)
Y 11001011 011101
Informative part is called MOTIF & the rest is called CROSSOVER.
Diagram
MUTATION
This is the chance that a bit within a chromosome will be fit (0 changes to 1 & 1 becomes 0). This is usually a very low chance. Whenever chromosomes are chosen from the chains the algorithm first checks to see if crossover should be applied & then the algorithm iterates down the length to each chromosome mutating the bits if applicable.
Given the digits 0 through 9 & operators +, -, X, / find a sequence that will represent a given target number. The operators will be applied sequentially from left to right as you read.
Eg: 4 – 3 * 6 = 1 * 6 = 6
23 => 6 + 5 * 4 / 2 + 1 (9 genes)
= 0110 1010 0101 1100 0100 1101 0010 1010 0001
= 011010100101110001001101001010100001 (Chromosome)
This has been obtained from the chart below: -
0 - 0000
1 - 0001
2 - 0010
3 - 0011
4 - 0100
5 - 0101
6 - 0110
7 - 0111
8 - 1000
9 - 1001
+ - 1010
- - 1011
* - 1100
/ - 1101
blank - 1110
blank - 1111
Steps: -
1) First we need to encode a possible solution as a string of bits to represent all the different characters available to the solution. This will represent a gene.
Each chromosome will be made up of several genes. The above, show all the different genes required to encode the problem.
The possible genes 1100 1111 will remain unused & will be ignored by the algorithm if encountered. Hence the target no 23 would represent 9 genes as follows. These genes all together form the chromosome.
FITNESS FUNCTION
This can be the most difficult part of the algorithm to figure out. It really depends on the problem to solve. The general idea is to give a higher fitness score; the closer a chromosome comes to solving the problem.
A fitness score can be assigned that is universally proportional to the difference between the solution & the value, a decoded chromosome represents.
Assuming solution target no is 42, the fitness score of the chromosome mentioned above
1 / (42 – 23) = 1 / 19
If a solution is found, a divide by zero, error would occur, as the fitness would be 1/ 42 – 42. This is not a problem, as we are looking for a solution and not a mathematical data.
Decision Support System – Prof. Chandan Bhattacharya – 25th July, 2006.
NEURAL NETWORK
A Neural Network is a massively parallel-distributed processor made up of simple processing unit, which has a natural characteristic for storing experimental knowledge and making it available for use. It resembles the brain in 2 respects: -
1) Knowledge is acquired by the network from its environment through a learning process.
2) Inter-neuron connection strengths, known as synaptic weight, are used to store the acquired knowledge.
BENEFITS OF NEURAL NETWORKS
1) Non-linearity – An artificial neuron can be linear or non linear. A neural network made up of an interconnection of nonlinear neurons is itself a non linear.
2) Input / Output Mapping – A popular technique of learning, called supervised learning involves modification of the synaptic weights of a neural network by applying a set of labelled training samples or task examples.
3) Adaptability – Neural Networks have a built in capability to adopt their synaptic weights, to changes in the surrounding environment.
A neural network trained to operate in a specific environment can easily be retrained to deal with minor changes in the operating environmental conditions.
4) Evidential Response – In the context of pattern classification, a neural network can be designed to provide information not only about which particular pattern to select but also about the confidence of the decision made.
5) Contextual Information – Knowledge is represented by the very structure 7 activation state of a neural network. Every neuron in a network is potentially affected by the global activity of all other neurons in the network.
6) Neurobiological analogy – The design of a neural network is motivated by analogy of the brain, which is a living proof of fault tolerant parallel processing.
Diagram 1
Diagram 2
(Mapping how should work if we make analogy to a human brain)
Nonlinear Model of Neuron
A neuron is an information-processing unit that is fundamental to the operation of a neural network.
The diagram above shows the model of a neuron, which forms the basis of designing artificial neural network. The model comprises of the following key elements.
1) A set of synapse or connecting links, each of which is characterised by a weight or strength of its own. A signal ‘xj’ (1 <= j <= n) Specially ‘xj‘ at the input of synapse j connected to neuron k is multiplied by the synaptic weight ‘wkj’. Unlike a synapse in the brain, the synaptic weight of an artificial neuron may be negative as well as positive values.
2) An adder for summing the input signals, weighted by the respective synapse of the neuron forms a linear combiner.
3) An activation function for limiting the amplitude of the output of a neuron is called squashing function.
The neural model includes an externally applied bias denoted by ‘bk’ which has the effect of increasing or lowering the net input of the activation function.
In mathematical terms we now may describe a neuron k by the following equation: -
m
Uk = Σ Wkj xj
j=1
Yk = Φ (uk + bk )
Where,
x1, x2 …….xn are the input signals,
wk1, wk2 ………xkn are the synaptic weights of neuron k
uk is the linear combiner output
bk is the bias
Φ() is the activation function &
yk is the output signal of neuron ‘k’.
Inparticular depending on whether the bias bk is +ve or –ve the relationship between the induced local field for activation potential vk of the neuron k and the linear combined output uk is modified by induced local field.
DIFFERNECE BETWEEN NEURAL NETWORK AND EXPERT SYSTEM
Expert system like post-traditional systems seek to emulate or model, human experts way of solving a set of problems. The Knowledge Engineers observe humans, builds a model of their expertise and writes a computer programs or algorithm that implements the model. The program incorporates specific rules, which are derived from human experts & their experience in a limited problem domain. Neural Networks do not model human intelligence nor to use knowledge engineers to solve a specific problem. Instead of putting intelligence into program neural network designers.
Others:-
FUZZY LOGIC
Professor Zadeh reasoned that people do not require precise numerical information input & yet they are capable of highly adoptive control. If feedback controllers could be programmed to accept noisy, imprecise input they could be much more effective and perhaps easier to implement.
Fuzzy Logic is a problem solving Control System methodology that lend itself to implement in systems ranging from simple, small embedded micro-controllers to large, networked, multi-channel PC or Work-Stations based data acquisition and Control Systems. It can be implemented in Hardware, Software or a combination of both. If fuzzy logic provides a simple way to arrive at a definite conclusion based upon vague, ambiguous, imprecise, noisy or even missing input information.
Fuzzy Logic incorporates a simple, rule based IF X AND Y THEN Z approach to a solving control problem rather than attending to model a system mathematically. The fuzzy logic model is empirically based and relies on operator’s experience rather than technical understanding of the system.
Fuzzy Logic requires some numerical parameters in order to operate such as what is considered to be significant error and significant rate of change of error, but exact values of these numbers are usually not critical unless very responsive performance is required.
WHY USE FUZZY LOGIC
1) It is inherently robust since it does not require precise, noise free inputs. The output control is a smooth control function despite a wide range of input variations.
2) Since the Fuzzy logic Controllers processes user defined rules, it can be modified easily to improve or alter system performances.
3) Fuzzy Logic is not limited to a few feedback inputs nor is it necessary to measure or compute rate of change parameters.
4) Because of the rule based operation any reasonable number of inputs can be processed and numerous output can be generated with more limited responsibilities.
5) Fuzzy Logic can control non-linear system that would be difficult or impossible to model mathematically.
Suppose we want to design a simple proportional temperature controller with an electric healing element and a variable speed cooling fan. A positive element output calls for 0 – 100 % heat while a negative signal output calls for 0 – 100 % cooling. Control is achieved through proper balance and control of these two active devices.
Diag DSS 4
Cmd: Target Temperature
Temp: Feedback sensor in Controlled environment.
Error: Cmd – Temp ( + = too cold ; - = too hot )
Cmd-dot : Time derivative or Error ( + = getting hotter ; - = getting cooler )
Output: HEAT or NO CHANGE or COOL
A simple block diagram of the Control System
Notations:
N – Negative error or error dot in input level
Z – Zero(0) error or error dot in input level
P – Positive error or error dot in input level
H – Heat output response
- - No change
C – Cool
Rule Structure & Rule Matrix: (assuming 3 X 3 matrix)
Diag DSS 5
Rule Structure:
1) If Cmd - Temp – N and d/dt [Cmd – Temp)] = N then output = C
2) If Cmd - Temp – Z and d/dt [Cmd – Temp)] = N then output = H
3) If Cmd - Temp – P and d/dt [Cmd – Temp)] = N then output = H
4) If Cmd - Temp – N and d/dt [Cmd – Temp)] = Z then output = C
5) If Cmd - Temp – Z and d/dt [Cmd – Temp)] = Z then output = NC
6) If Cmd - Temp – P and d/dt [Cmd – Temp)] = Z then output = H
7) If Cmd - Temp – N and d/dt [Cmd – Temp)] = P then output = C
8) If Cmd - Temp – Z and d/dt [Cmd – Temp)] = P then output = C
9) If Cmd - Temp – P and d/dt [Cmd – Temp)] = P then output = H
Definition:
System Status Input:
[Error] – P – Too Cold
Z – Just Right
N – Too Hot
[Error dot] – P – Getting Hotter
Z – Not Changing
N – Getting Colder
System Status Output:
H – Call for heating
C – Call for Cooling
NC – No Change
GENETIC ALGORITHMS
Genetic Algorithms are a way of solving problems by mimicking the same process that the nature uses. They use the same combination of selection recombination and mutation to evolve a solution to a problem. Every organism has a set of rules. These rules are encoded in the genes of an organism, which in turn are connected together into long strings called chromosomes. A typical chromosome may look like follows when it is coded in binary sequences: -
10010010110010………………..
At the beginning of run of genetic algorithm, a large population of random chromosomes is created. Each one, when decoded will represent a different solution to the problem. Let us assume that there are N chromosomes in the initial population. The following steps are repeated until a solution is found: -
1) Test each chromosome to see how good it is at solving the problems and assign a fitness score accordingly. The fitness score is a measure of how good that chromosome is at solving the problem.
2) Select two members from the current population. The chance of being selected is proportional to the chromosome fitness.
3) Dependent on the crossover rate, crossover the bits from each chosen chromosomes at a randomly chosen point.
4) Step through the chosen chromosome bits and flip dependent on the mutation rate.
5) Repeat step II, III, IV until a new population of N members has been created.
Soln: - max[min[(A,B),(B,D)],min{A,C),(C,D)]]
So, max[min[0.8,.05],min[9,6]]
= max[0.5,0.6]
= 0.6
# posted by HOTWINTER @ 9:48 PM 
